3 This is part of the YARRG website. YARRG is a tool and website
4 for assisting players of Yohoho Puzzle Pirates.
6 Copyright (C) 2009 Ian Jackson <ijackson@chiark.greenend.org.uk>
7 Copyright (C) 2009 Clare Boothby
9 YARRG's client code etc. is covered by the ordinary GNU GPL (v3 or later).
10 The YARRG website is covered by the GNU Affero GPL v3 or later, which
11 basically means that every installation of the website will let you
14 This program is free software: you can redistribute it and/or modify
15 it under the terms of the GNU Affero General Public License as
16 published by the Free Software Foundation, either version 3 of the
17 License, or (at your option) any later version.
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 GNU Affero General Public License for more details.
24 You should have received a copy of the GNU Affero General Public License
25 along with this program. If not, see <http://www.gnu.org/licenses/>.
27 Yohoho and Puzzle Pirates are probably trademarks of Three Rings and
28 are used without permission. This program is not endorsed or
29 sponsored by Three Rings.
32 This Mason component is the core trade planner for a specific route.
44 da_pageload= Date.now();
49 my $loss_per_league= defined $routeparams->{LossPerLeaguePct}
50 ? $routeparams->{LossPerLeaguePct}*0.01 : 1e-7;
51 my $loss_per_delay_slot= 1e-8;
58 my $expected_total_profit;
60 my $sd_condition= sub {
62 my $islandid= $islandids[$ix];
63 if (defined $islandid) {
64 return "${bs}.islandid = $islandid";
66 push @query_params, $archipelagoes[$ix];
67 return "${bs}_islands.archipelago = ?";
71 my $specific= !grep { !defined $_ } @islandids;
73 my %ipair2subflowinfs;
74 # $ipair2subflowinfs{$orgi,$dsti}= [ [$orgix,$distix], ... ]
77 # $subflows[0]{Flow} = { ... }
78 # $subflows[0]{Org} = $orgix
79 # $subflows[0]{Dst} = $dstix
81 foreach my $org_i (0..$#islandids) {
82 my $org_isle= $islandids[$org_i];
83 my $org_cond= $sd_condition->('sell',$org_i);
85 foreach my $dst_i ($org_i..$#islandids) {
86 my $dst_isle= $islandids[$dst_i];
87 # Don't ever consider sailing things round the houses:
88 next if defined $dst_isle and
89 grep { $dst_isle == $_ } @islandids[$org_i..$dst_i-1];
90 next if defined $org_isle and
91 grep { $org_isle == $_ } @islandids[$org_i+1..$dst_i];
93 if ($dst_i==$org_i and !defined $org_isle) {
94 # we always want arbitrage, but mentioning an arch
95 # once shouldn't produce intra-arch trades
96 $dst_cond= "sell.islandid = buy.islandid";
98 $dst_cond= $sd_condition->('buy',$dst_i);
100 push @dst_conds, $dst_cond;
103 push @{ $ipair2subflowinfs{$org_isle,$dst_isle} },
107 push @flow_conds, "$org_cond AND (
114 SELECT sell_islands.islandname org_name,
115 sell_islands.islandid org_id,
116 sell.price org_price,
117 sell.qty org_qty_stall,
118 sell_stalls.stallname org_stallname,
119 sell.stallid org_stallid,
120 sell_uploads.timestamp org_timestamp,
121 buy_islands.islandname dst_name,
122 buy_islands.islandid dst_id,
124 buy.qty dst_qty_stall,
125 buy_stalls.stallname dst_stallname,
126 buy.stallid dst_stallid,
127 buy_uploads.timestamp dst_timestamp,
128 ".($qa->{ShowStalls} ? "
129 sell.qty org_qty_agg,
132 (SELECT sum(qty) FROM sell AS sell_agg
133 WHERE sell_agg.commodid = commods.commodid
134 AND sell_agg.islandid = sell.islandid
135 AND sell_agg.price = sell.price) org_qty_agg,
136 (SELECT sum(qty) FROM buy AS buy_agg
137 WHERE buy_agg.commodid = commods.commodid
138 AND buy_agg.islandid = buy.islandid
139 AND buy_agg.price = buy.price) dst_qty_agg,
141 commods.commodname commodname,
142 commods.commodid commodid,
143 commods.unitmass unitmass,
144 commods.unitvolume unitvolume,
146 buy.price - sell.price unitprofit
148 JOIN sell ON commods.commodid = sell.commodid
149 JOIN buy ON commods.commodid = buy.commodid
150 JOIN islands AS sell_islands ON sell.islandid = sell_islands.islandid
151 JOIN islands AS buy_islands ON buy.islandid = buy_islands.islandid
152 JOIN uploads AS sell_uploads ON sell.islandid = sell_uploads.islandid
153 JOIN uploads AS buy_uploads ON buy.islandid = buy_uploads.islandid
154 JOIN stalls AS sell_stalls ON sell.stallid = sell_stalls.stallid
155 JOIN stalls AS buy_stalls ON buy.stallid = buy_stalls.stallid
156 JOIN dists ON aiid = sell.islandid AND biid = buy.islandid
161 AND buy.price > sell.price
162 ORDER BY org_name, dst_name, commodname, unitprofit DESC,
163 org_price, dst_price DESC,
164 org_stallname, dst_stallname
167 my $sth= $dbh->prepare($stmt);
168 $sth->execute(@query_params);
171 my $distquery= $dbh->prepare("
172 SELECT dist FROM dists WHERE aiid = ? AND biid = ?
176 my $d= $dists{$from}{$to};
177 return $d if defined $d;
178 $distquery->execute($from,$to);
179 $d = $distquery->fetchrow_array();
180 defined $d or die "$from $to ?";
181 $dists{$from}{$to}= $d;
185 my @cols= ({ NoSort => 1 });
189 foreach my $name (@_) {
190 my $col= { Name => $name, %$base };
191 $col->{Numeric}=1 if !$col->{Text};
196 if ($qa->{ShowStalls}) {
197 $addcols->({ Text => 1 }, qw(
198 org_name org_stallname
199 dst_name dst_stallname
202 $addcols->({Text => 1 }, qw(
206 $addcols->({ Text => 1 }, qw(commodname));
207 $addcols->({ DoReverse => 1 },
208 qw( org_price org_qty_agg dst_price dst_qty_agg
210 $addcols->({ DoReverse => 1, SortColKey => 'MarginSortKey' },
213 $addcols->({ DoReverse => 1 },
214 qw( unitprofit MaxQty MaxCapital MaxProfit dist
216 foreach my $v (qw(MaxMass MaxVolume)) {
218 DoReverse => 1, Total => 0, SortColKey => "${v}SortKey" }, $v);
223 % if ($qa->{'debug'}) {
226 <% join(' | ',@query_params) |h %>
230 <& dumptable:start, qa => $qa, sth => $sth &>
233 % while ($got= $sth->fetchrow_hashref()) {
236 my $f= $flows[$#flows];
239 grep { $f->{$_} ne $got->{$_} }
240 qw(org_id org_price dst_id dst_price commodid)
242 # Make a new flow rather than adding to the existing one
245 Ix => scalar(@flows),
248 $f->{"org_stallid"}= $f->{"dst_stallid"}= 'all'
249 if !$qa->{ShowStalls};
252 foreach my $od (qw(org dst)) {
254 $got->{"${od}_stallname"}
256 $got->{"${od}_qty_stall"}
261 <& dumptable:row, qa => $qa, sth => $sth, row => $f &>
263 <& dumptable:end, qa => $qa &>
271 print 'No profitable trading opportunities were found.';
275 foreach my $f (@flows) {
277 $f->{MaxQty}= $f->{'org_qty_agg'} < $f->{'dst_qty_agg'}
278 ? $f->{'org_qty_agg'} : $f->{'dst_qty_agg'};
279 $f->{MaxProfit}= $f->{MaxQty} * $f->{'unitprofit'};
280 $f->{MaxCapital}= $f->{MaxQty} * $f->{'org_price'};
282 $f->{MaxMassSortKey}= $f->{MaxQty} * $f->{'unitmass'};
283 $f->{MaxVolumeSortKey}= $f->{MaxQty} * $f->{'unitvolume'};
284 foreach my $v (qw(Mass Volume)) {
285 $f->{"Max$v"}= sprintf "%.1f", $f->{"Max${v}SortKey"} * 1e-6;
288 my $sfis= $ipair2subflowinfs{$f->{'org_id'},$f->{'dst_id'}};
289 foreach my $sfi (@$sfis) {
294 Var => sprintf "f%ss%s_c%d_p%d_%d_p%d_%d",
297 $sfi->[0], $f->{'org_price'},
298 $sfi->[1], $f->{'dst_price'}
300 push @{ $f->{Subflows} }, $subflow;
301 push @subflows, $subflow;
304 $f->{MarginSortKey}= sprintf "%d",
305 $f->{'dst_price'} * 10000 / $f->{'org_price'};
306 $f->{Margin}= sprintf "%3.1f%%",
307 $f->{'dst_price'} * 100.0 / $f->{'org_price'} - 100.0;
309 $f->{ExpectedUnitProfit}=
310 $f->{'dst_price'} * (1.0 - $loss_per_league) ** $f->{'dist'}
313 $dists{'org_id'}{'dst_id'}= $f->{'dist'};
315 my @uid= $f->{commodid};
316 foreach my $od (qw(org dst)) {
321 $f->{"${od}_stallid"}
322 if $qa->{ShowStalls};
324 $f->{UidLong}= join '_', @uid;
332 my $this= $uue % $base;
333 #print STDERR "uue=$uue this=$this ";
338 $cmpu .= chr($this + ($this < 26 ? ord('a') :
339 $this < 52 ? ord('A')-26
341 #print STDERR " uue=$uue this=$this cmpu=$cmpu\n";
342 die "$cmpu $uue ?" if length $cmpu > 20;
346 $f->{UidShort}= $cmpu;
348 if ($qa->{'debug'}) {
353 my $v= m/^[a-z]/ ? ord($&)-ord('a') :
354 m/^[A-Z]/ ? ord($&)-ord('A')+26 :
355 m/^[0-9]/ ? ord($&)-ord('0')+52 :
361 #print STDERR "(next)\n";
363 die "$f->{UidShort} $_ ?" unless defined $mul;
364 $outuid[$#outuid] += $v * $mul;
366 #print STDERR "$f->{UidShort} $_ $& v=$v mul=$mul ord()=".ord($&).
367 # "[vs.".ord('a').",".ord('A').",".ord('0')."]".
368 # " outuid=@outuid\n";
373 my $recons_long= join '_', @outuid;
374 $f->{UidLong} eq $recons_long or
375 die "$f->{UidLong} = $f->{UidShort} = $recons_long ?";
378 if (defined $qa->{"R$f->{UidShort}"} &&
379 !defined $qa->{"T$f->{UidShort}"}) {
386 % my $optimise= $specific;
391 Route contains archipelago(es), not just specific islands.
393 Therefore, optimal voyage trade plan not calculated.
395 % } else { # ========== OPTMISATION ==========
404 foreach my $sf (@subflows) {
405 my $eup= $sf->{Flow}{ExpectedUnitProfit};
406 $eup *= (1.0-$loss_per_delay_slot) ** $sf->{Org};
408 %+.20f %s", $eup, $sf->{Var};
416 foreach my $flow (@flows) {
417 if ($flow->{Suppress}) {
418 foreach my $sf (@{ $flow->{Subflows} }) {
424 foreach my $od (qw(org dst)) {
425 my $limname= join '_', (
427 'i'.$flow->{"${od}_id"},
428 'c'.$flow->{'commodid'},
429 $flow->{"${od}_price"},
430 $flow->{"${od}_stallid"},
433 push @{ $avail_lims{$limname}{SubflowVars} },
434 map { $_->{Var} } @{ $flow->{Subflows} };
435 $avail_lims{$limname}{Qty}= $flow->{"${od}_qty_agg"};
438 foreach my $limname (sort keys %avail_lims) {
439 my $c= $avail_lims{$limname};
441 sprintf(" %-30s","$limname:")." ".
442 join("+", @{ $c->{SubflowVars} }).
443 " <= ".$c->{Qty}."\n";
446 foreach my $ci (0..($#islandids-1)) {
449 foreach my $f (@flows) {
450 next if $f->{Suppress};
451 my @relsubflow= grep {
454 } @{ $f->{Subflows} };
455 next unless @relsubflow;
456 die unless @relsubflow == 1;
457 push @rel_subflows, @relsubflow;
458 #print " RELEVANT $ci $relsubflow[0]->{Var} ";
460 #print " RELEVANT $ci COUNT ".scalar(@rel_subflows)." ";
461 if (!@rel_subflows) {
462 foreach my $mv (qw(mass volume)) {
463 $sail_total[$ci]{$mv}= 0;
468 my $applylimit= sub {
469 my ($mv, $f2val) = @_;
470 my $max= $routeparams->{"Max".ucfirst $mv};
471 $max= 1e9 unless defined $max;
472 #print " DEFINED MAX $mv $max ";
474 ". sprintf("%-10s","${mv}_$ci:")." ".
476 #print " PART MAX $_->{Var} $_->{Flow}{Ix} ";
477 $f2val->($_->{Flow}) .' '. $_->{Var};
482 $applylimit->('mass', sub { $_[0]{'unitmass'} *1e-3 });
483 $applylimit->('volume', sub { $_[0]{'unitvolume'}*1e-3 });
484 $applylimit->('capital', sub { $_[0]{'org_price'} });
491 ", map { "$_->{Var} >= 0" } @subflows)."
498 ", map { $_->{Var} } @subflows)."
503 if ($qa->{'debug'}) {
512 my $input= pipethrough_prep();
513 print $input $cplex or die $!;
514 my $output= pipethrough_run_along($input, undef, 'glpsol',
515 qw(glpsol --tmlim 2 --memlim 5 --intopt --cuts --bfs
516 --cpxlp /dev/stdin -o /dev/stdout));
517 print "<pre>\n" if $qa->{'debug'};
518 my $found_section= 0;
523 print encode_entities($_) if $qa->{'debug'};
524 if (m/^\s*No\.\s+(Row|Column) name\s+(?:St\s+)?Activity\s/) {
525 die "$_ $found_section ?" if $found_section>0;
529 if (m/^Objective:\s+totalprofit = (\d+\.\d*) /) {
530 $expected_total_profit= $1;
532 next unless $found_section==1;
533 if (!length $continuation) {
534 next if !$continuation && m/^[- ]+$/;
539 if (m/^ \s* \d+ \s+ \w+ $/x) {
544 $_= $continuation.$_;
546 my ($varname, $qty) = m/^
548 (\w+) \s+ (?: [A-Z*]+ \s+ )?
551 if ($varname =~ m/^f(\d+)s(\d+)_/) {
552 my ($ix,$orgix) = ($1,$2);
553 my $flow= $flows[$ix] or die;
554 my @relsubflow= grep { $_->{Org} == $orgix }
555 @{ $flow->{Subflows} };
556 die "$ix $orgix @relsubflow" unless @relsubflow == 1;
557 my $sf= $relsubflow[0];
559 $sf->{OptProfit}= $qty * $flow->{'unitprofit'};
560 $sf->{OptCapital}= $qty * $flow->{'org_price'};
561 } elsif ($varname =~ m/^(mass|volume)_(\d+)$/) {
562 my ($mv,$ix) = ($1,$2);
563 $sail_total[$ix]{$mv}= $qty;
566 print "</pre>\n" if $qa->{'debug'};
567 my $prerr= "\n=====\n$cplex\n=====\n$glpsol_out\n=====\n ";
568 pipethrough_run_finish($output,$prerr);
569 map { defined $_->{OptQty} or die "$prerr $_->{Flow}{Ix}" } @subflows;
572 $addcols->({ DoReverse => 1, TotalSubflows => 1, Special => sub {
573 my ($flow,$col,$v,$spec) = @_;
574 if ($flow->{ExpectedUnitProfit} < 0) {
576 $spec->{String}= '(Small margin)';
577 $spec->{Align}= 'align=center';
582 $addcols->({ Total => 0, DoReverse => 1, TotalSubflows => 1 }, qw(
588 % } # ========== OPTIMISATION ==========
592 % my $cdspan= $qa->{ShowStalls} ? ' colspan=2' : '';
593 % my $cdstall= $qa->{ShowStalls} ? '<th>Stall</th>' : '';
594 <table id="trades" rules=groups>
597 <% $qa->{ShowStalls} ? '<colgroup span=2>' : '' %>
609 <th<% $cdspan %>>Collect
610 <th<% $cdspan %>>Deliver
612 <th colspan=2>Collect
613 <th colspan=2>Deliver
619 <th colspan=3>Planned
624 <th>Island <% $cdstall %>
625 <th>Island <% $cdstall %>
646 <tr id="trades_sort">
647 % foreach my $col (@cols) {
651 % foreach my $flowix (0..$#flows) {
652 % my $flow= $flows[$flowix];
653 % my $rowid= "id_row_$flow->{UidShort}";
654 <tr id="<% $rowid %>" class="datarow<% $flowix & 1 %>">
655 <td><input type=hidden name=R<% $flow->{UidShort} %> value="">
656 <input type=checkbox name=T<% $flow->{UidShort} %> value=""
657 <% $flow->{Suppress} ? '' : 'checked' %> >
659 % while ($ci < @cols) {
660 % my $col= $cols[$ci];
663 % Align => ($col->{Text} ? '' : 'align=right')
665 % my $cn= $col->{Name};
667 % if (!$col->{TotalSubflows}) {
671 % $v += $_->{$cn} foreach @{ $flow->{Subflows} };
673 % if ($col->{Special}) { $col->{Special}($flow,$col,$v,$spec); }
674 % $col->{Total} += $v
675 % if defined $col->{Total} and not $flow->{Suppress};
676 % $v='' if !$col->{Text} && !$v;
677 % my $sortkey= $col->{SortColKey} ?
678 % $flow->{$col->{SortColKey}} : $v;
679 % $ts_sortkeys{$ci}{$rowid}= $sortkey;
680 <td <% $spec->{Span} ? "colspan=$spec->{Span}" : ''
682 %>><% exists $spec->{String} ? $spec->{String} : $v |h %>
683 % $ci += $spec->{Span};
686 <tr id="trades_total">
689 % foreach my $ci (3..$#cols) {
690 % my $col= $cols[$ci];
692 % if (defined $col->{Total}) {
693 <% $col->{Total} |h %>
698 <&| tabsort, cols => \@cols, table => 'trades', rowclass => 'datarow',
699 throw => 'trades_sort', tbrow => 'trades_total' &>
700 ts_sortkeys= <% to_json_protecttags(\%ts_sortkeys) %>;
703 <input type=submit name=update value="Update">
705 % if ($optimise) { # ========== TRADING PLAN ==========
707 % my $iquery= $dbh->prepare('SELECT islandname FROM islands
708 % WHERE islandid = ?');
710 % my $total_total= 0;
713 <h1>Voyage trading plan</h1>
715 % foreach my $i (0..$#islandids) {
718 % $iquery->execute($islandids[$i]);
719 % my ($islandname) = $iquery->fetchrow_array();
721 <strong>Start at <% $islandname |h %></strong>
723 % my $this_dist= $distance->($islandids[$i-1],$islandids[$i]);
724 % $total_dist += $this_dist;
727 foreach my $sf (@subflows) {
728 next unless $sf->{Org} < $i && $sf->{Dst} >= $i;
730 $sf->{OptQty} * $sf->{Flow}{'dst_price'};
733 <strong>Sail to <% $islandname |h %></strong>
734 - <% $this_dist |h %> leagues,
735 <% $total_value %>poe at risk
741 #print "<tr><td colspan=6>" if $qa->{'debug'};
742 foreach my $od (qw(org dst)) {
743 #print " [[ i $i od $od " if $qa->{'debug'};
744 foreach my $sf (@subflows) {
746 next if $f->{Suppress};
747 next unless $sf->{ucfirst $od} == $i;
748 #print " FLOW $f->{Ix} SUB #$sf->{Org}..$sf->{Dst} "
750 next unless $sf->{OptQty};
751 my $arbitrage= $f->{'org_id'} == $f->{'dst_id'};
752 die if $arbitrage and $sf->{Org} != $sf->{Dst};
753 my $price= $f->{"${od}_price"};
754 my $stallname= $f->{"${od}_stallname"};
755 my $todo= \$flowlists{$od}{
757 (sprintf "%07d", ($od eq 'dst' ?
758 9999999-$price : $price)),
766 $$todo->{'commodname'}= $f->{'commodname'};
767 $$todo->{'stallname'}= $stallname;
768 $$todo->{Price}= $price;
769 $$todo->{Timestamp}= $f->{"${od}_timestamp"};
770 $$todo->{Qty} += $sf->{OptQty};
771 $$todo->{Total}= $$todo->{Price} * $$todo->{Qty};
772 $$todo->{Stalls}= $f->{"${od}Stalls"};
773 $$todo->{"${od}Arbitrage"}= 1 if $arbitrage;
775 #print "]] " if $qa->{'debug'};
777 #print "</tr>" if $qa->{'debug'};
779 my ($total, $total_to_show);
781 my $show_total= sub {
782 my ($totaldesc, $sign) = @_;
783 if (defined $total) {
784 die if defined $total_to_show;
785 $total_total += $sign * $total;
786 $total_to_show= [ $totaldesc, $total ];
791 my $show_total_now= sub {
793 return unless defined $total_to_show;
794 my ($totaldesc,$totalwas) = @$total_to_show;
798 <td colspan=2><% $xinfo %>
799 <td colspan=2 align=right><% $totaldesc %>
800 <td align=right><% $totalwas |h %> total
802 $total_to_show= undef;
805 % my $show_flows= sub {
806 % my ($od,$arbitrage,$collectdeliver) = @_;
807 % my $todo= $flowlists{$od};
808 % return unless $todo;
809 % foreach my $tkey (sort keys %$todo) {
810 % my $t= $todo->{$tkey};
811 % next if $t->{"${od}Arbitrage"} != $arbitrage;
812 % $show_total_now->('');
813 % if (!$age_reported++) {
814 % my $age= $now - $t->{Timestamp};
815 % my $cellid= "da_${i}";
816 % $da_ages{$cellid}= $age;
818 (Data age: <span id="<% $cellid %>"><% prettyprint_age($age) %></span>)
819 % } elsif (!defined $total) {
823 % $total += $t->{Total};
824 % my $span= 0 + keys %{ $t->{Stalls} };
825 % my $td= "td rowspan=$span";
826 <tr class="datarow<% $dline %>">
827 <<% $td %>><% $collectdeliver %>
828 <<% $td %>><% $t->{'commodname'} |h %>
830 % my @stalls= sort keys %{ $t->{Stalls} };
832 % my $name= $stalls[$_[0]];
837 <<% $td %> align=right><% $t->{Price} |h %> poe ea.
838 <<% $td %> align=right><% $t->{Qty} |h %> unit(s)
839 <<% $td %> align=right><% $t->{Total} |h %> total
841 % foreach my $stallix (1..$#stalls) {
842 <tr class="datarow<% $dline %>">
843 % $pstall->($stallix);
851 $show_flows->('dst',0,'Deliver'); $show_total->('Proceeds',1);
852 $show_flows->('org',1,'Collect'); $show_total->('(Arbitrage) outlay',-1);
853 $show_flows->('dst',1,'Deliver'); $show_total->('(Arbitrage) proceeds',1);
854 $show_flows->('org',0,'Collect'); $show_total->('Outlay',-1);
856 if ($i < $#islandids) {
857 $totals .= "In hold $sail_total[$i]{mass}kg,".
858 " $sail_total[$i]{volume} l";
859 my $delim= '; spare ';
861 my ($max, $got, $units) = @_;
862 return unless defined $max;
864 $totals .= sprintf "%g %s", ($max-$got), $units;
867 $domv->($routeparams->{MaxMass}, $sail_total[$i]{mass}, 'kg');
868 $domv->($routeparams->{MaxVolume}, $sail_total[$i]{volume}, 'l');
871 $show_total_now->($totals);
875 <td colspan=2>Total distance: <% $total_dist %> leagues.
876 <td colspan=3 align=right>Overall net cash flow
877 <td align=right><strong><%
878 $total_total < 0 ? -$total_total." loss" : $total_total." gain"
881 <& query_age:dataages, id2age => \%da_ages &>
882 Expected average profit:
883 approx. <strong><% sprintf "%d", $expected_total_profit %></strong> poe
884 (considering expected losses, but ignoring rum consumed)
886 % } # ========== TRADING PLAN ==========