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.
47 da_pageload= Date.now();
52 my $loss_per_league= defined $lossperleaguepct ? $lossperleaguepct*0.01 : 1e-7;
53 my $loss_per_delay_slot= 1e-8;
60 my $expected_total_profit;
62 my $sd_condition= sub {
64 my $islandid= $islandids[$ix];
65 if (defined $islandid) {
66 return "${bs}.islandid = $islandid";
68 push @query_params, $archipelagoes[$ix];
69 return "${bs}_islands.archipelago = ?";
73 my $specific= !grep { !defined $_ } @islandids;
75 my %ipair2subflowinfs;
76 # $ipair2subflowinfs{$orgi,$dsti}= [ [$orgix,$distix], ... ]
79 # $subflows[0]{Flow} = { ... }
80 # $subflows[0]{Org} = $orgix
81 # $subflows[0]{Dst} = $dstix
83 foreach my $org_i (0..$#islandids) {
84 my $org_isle= $islandids[$org_i];
85 my $org_cond= $sd_condition->('sell',$org_i);
87 foreach my $dst_i ($org_i..$#islandids) {
88 my $dst_isle= $islandids[$dst_i];
89 # Don't ever consider sailing things round the houses:
90 next if defined $dst_isle and
91 grep { $dst_isle == $_ } @islandids[$org_i..$dst_i-1];
92 next if defined $org_isle and
93 grep { $org_isle == $_ } @islandids[$org_i+1..$dst_i];
95 if ($dst_i==$org_i and !defined $org_isle) {
96 # we always want arbitrage, but mentioning an arch
97 # once shouldn't produce intra-arch trades
98 $dst_cond= "sell.islandid = buy.islandid";
100 $dst_cond= $sd_condition->('buy',$dst_i);
102 push @dst_conds, $dst_cond;
105 push @{ $ipair2subflowinfs{$org_isle,$dst_isle} },
109 push @flow_conds, "$org_cond AND (
116 SELECT sell_islands.islandname org_name,
117 sell_islands.islandid org_id,
118 sell.price org_price,
119 sell.qty org_qty_stall,
120 sell_stalls.stallname org_stallname,
121 sell.stallid org_stallid,
122 sell_uploads.timestamp org_timestamp,
123 buy_islands.islandname dst_name,
124 buy_islands.islandid dst_id,
126 buy.qty dst_qty_stall,
127 buy_stalls.stallname dst_stallname,
128 buy.stallid dst_stallid,
129 buy_uploads.timestamp dst_timestamp,
130 ".($qa->{ShowStalls} ? "
131 sell.qty org_qty_agg,
134 (SELECT sum(qty) FROM sell AS sell_agg
135 WHERE sell_agg.commodid = commods.commodid
136 AND sell_agg.islandid = sell.islandid
137 AND sell_agg.price = sell.price) org_qty_agg,
138 (SELECT sum(qty) FROM buy AS buy_agg
139 WHERE buy_agg.commodid = commods.commodid
140 AND buy_agg.islandid = buy.islandid
141 AND buy_agg.price = buy.price) dst_qty_agg,
143 commods.commodname commodname,
144 commods.commodid commodid,
145 commods.unitmass unitmass,
146 commods.unitvolume unitvolume,
148 buy.price - sell.price unitprofit
150 JOIN sell ON commods.commodid = sell.commodid
151 JOIN buy ON commods.commodid = buy.commodid
152 JOIN islands AS sell_islands ON sell.islandid = sell_islands.islandid
153 JOIN islands AS buy_islands ON buy.islandid = buy_islands.islandid
154 JOIN uploads AS sell_uploads ON sell.islandid = sell_uploads.islandid
155 JOIN uploads AS buy_uploads ON buy.islandid = buy_uploads.islandid
156 JOIN stalls AS sell_stalls ON sell.stallid = sell_stalls.stallid
157 JOIN stalls AS buy_stalls ON buy.stallid = buy_stalls.stallid
158 JOIN dists ON aiid = sell.islandid AND biid = buy.islandid
163 AND buy.price > sell.price
164 ORDER BY org_name, dst_name, commodname, unitprofit DESC,
165 org_price, dst_price DESC,
166 org_stallname, dst_stallname
169 my $sth= $dbh->prepare($stmt);
170 $sth->execute(@query_params);
173 my $distquery= $dbh->prepare("
174 SELECT dist FROM dists WHERE aiid = ? AND biid = ?
178 my $d= $dists{$from}{$to};
179 return $d if defined $d;
180 $distquery->execute($from,$to);
181 $d = $distquery->fetchrow_array();
182 defined $d or die "$from $to ?";
183 $dists{$from}{$to}= $d;
187 my @cols= ({ NoSort => 1 });
191 foreach my $name (@_) {
192 my $col= { Name => $name, %$base };
193 $col->{Numeric}=1 if !$col->{Text};
198 if ($qa->{ShowStalls}) {
199 $addcols->({ Text => 1 }, qw(
200 org_name org_stallname
201 dst_name dst_stallname
204 $addcols->({Text => 1 }, qw(
208 $addcols->({ Text => 1 }, qw(commodname));
209 $addcols->({ DoReverse => 1 },
210 qw( org_price org_qty_agg dst_price dst_qty_agg
212 $addcols->({ DoReverse => 1, SortColKey => 'MarginSortKey' },
215 $addcols->({ DoReverse => 1 },
216 qw( unitprofit MaxQty MaxCapital MaxProfit dist
218 foreach my $v (qw(MaxMass MaxVolume)) {
220 DoReverse => 1, Total => 0, SortColKey => "${v}SortKey" }, $v);
225 % if ($qa->{'debug'}) {
228 <% join(' | ',@query_params) |h %>
232 <& dumptable:start, qa => $qa, sth => $sth &>
235 % while ($got= $sth->fetchrow_hashref()) {
238 my $f= $flows[$#flows];
241 grep { $f->{$_} ne $got->{$_} }
242 qw(org_id org_price dst_id dst_price commodid)
244 # Make a new flow rather than adding to the existing one
247 Ix => scalar(@flows),
250 $f->{"org_stallid"}= $f->{"dst_stallid"}= 'all'
251 if !$qa->{ShowStalls};
254 foreach my $od (qw(org dst)) {
256 $got->{"${od}_stallname"}
258 $got->{"${od}_qty_stall"}
263 <& dumptable:row, qa => $qa, sth => $sth, row => $f &>
265 <& dumptable:end, qa => $qa &>
273 print 'No profitable trading opportunities were found.';
277 foreach my $f (@flows) {
279 $f->{MaxQty}= $f->{'org_qty_agg'} < $f->{'dst_qty_agg'}
280 ? $f->{'org_qty_agg'} : $f->{'dst_qty_agg'};
281 $f->{MaxProfit}= $f->{MaxQty} * $f->{'unitprofit'};
282 $f->{MaxCapital}= $f->{MaxQty} * $f->{'org_price'};
284 $f->{MaxMassSortKey}= $f->{MaxQty} * $f->{'unitmass'};
285 $f->{MaxVolumeSortKey}= $f->{MaxQty} * $f->{'unitvolume'};
286 foreach my $v (qw(Mass Volume)) {
287 $f->{"Max$v"}= sprintf "%.1f", $f->{"Max${v}SortKey"} * 1e-6;
290 my $sfis= $ipair2subflowinfs{$f->{'org_id'},$f->{'dst_id'}};
291 foreach my $sfi (@$sfis) {
296 Var => sprintf "f%ss%s_c%d_p%d_%d_p%d_%d",
299 $sfi->[0], $f->{'org_price'},
300 $sfi->[1], $f->{'dst_price'}
302 push @{ $f->{Subflows} }, $subflow;
303 push @subflows, $subflow;
306 $f->{MarginSortKey}= sprintf "%d",
307 $f->{'dst_price'} * 10000 / $f->{'org_price'};
308 $f->{Margin}= sprintf "%3.1f%%",
309 $f->{'dst_price'} * 100.0 / $f->{'org_price'} - 100.0;
311 $f->{ExpectedUnitProfit}=
312 $f->{'dst_price'} * (1.0 - $loss_per_league) ** $f->{'dist'}
315 $dists{'org_id'}{'dst_id'}= $f->{'dist'};
317 my @uid= $f->{commodid};
318 foreach my $od (qw(org dst)) {
323 $f->{"${od}_stallid"}
324 if $qa->{ShowStalls};
326 $f->{UidLong}= join '_', @uid;
334 my $this= $uue % $base;
335 #print STDERR "uue=$uue this=$this ";
340 $cmpu .= chr($this + ($this < 26 ? ord('a') :
341 $this < 52 ? ord('A')-26
343 #print STDERR " uue=$uue this=$this cmpu=$cmpu\n";
344 die "$cmpu $uue ?" if length $cmpu > 20;
348 $f->{UidShort}= $cmpu;
350 if ($qa->{'debug'}) {
355 my $v= m/^[a-z]/ ? ord($&)-ord('a') :
356 m/^[A-Z]/ ? ord($&)-ord('A')+26 :
357 m/^[0-9]/ ? ord($&)-ord('0')+52 :
363 #print STDERR "(next)\n";
365 die "$f->{UidShort} $_ ?" unless defined $mul;
366 $outuid[$#outuid] += $v * $mul;
368 #print STDERR "$f->{UidShort} $_ $& v=$v mul=$mul ord()=".ord($&).
369 # "[vs.".ord('a').",".ord('A').",".ord('0')."]".
370 # " outuid=@outuid\n";
375 my $recons_long= join '_', @outuid;
376 $f->{UidLong} eq $recons_long or
377 die "$f->{UidLong} = $f->{UidShort} = $recons_long ?";
380 if (defined $qa->{"R$f->{UidShort}"} &&
381 !defined $qa->{"T$f->{UidShort}"}) {
388 % my $optimise= $specific;
393 Route contains archipelago(es), not just specific islands.
395 Therefore, optimal voyage trade plan not calculated.
397 % } else { # ========== OPTMISATION ==========
406 foreach my $sf (@subflows) {
407 my $eup= $sf->{Flow}{ExpectedUnitProfit};
408 $eup *= (1.0-$loss_per_delay_slot) ** $sf->{Org};
410 %+.20f %s", $eup, $sf->{Var};
418 foreach my $flow (@flows) {
419 if ($flow->{Suppress}) {
420 foreach my $sf (@{ $flow->{Subflows} }) {
426 foreach my $od (qw(org dst)) {
427 my $limname= join '_', (
429 'i'.$flow->{"${od}_id"},
430 'c'.$flow->{'commodid'},
431 $flow->{"${od}_price"},
432 $flow->{"${od}_stallid"},
435 push @{ $avail_lims{$limname}{SubflowVars} },
436 map { $_->{Var} } @{ $flow->{Subflows} };
437 $avail_lims{$limname}{Qty}= $flow->{"${od}_qty_agg"};
440 foreach my $limname (sort keys %avail_lims) {
441 my $c= $avail_lims{$limname};
443 sprintf(" %-30s","$limname:")." ".
444 join("+", @{ $c->{SubflowVars} }).
445 " <= ".$c->{Qty}."\n";
448 foreach my $ci (0..($#islandids-1)) {
451 foreach my $f (@flows) {
452 next if $f->{Suppress};
453 my @relsubflow= grep {
456 } @{ $f->{Subflows} };
457 next unless @relsubflow;
458 die unless @relsubflow == 1;
459 push @rel_subflows, @relsubflow;
460 #print " RELEVANT $ci $relsubflow[0]->{Var} ";
462 #print " RELEVANT $ci COUNT ".scalar(@rel_subflows)." ";
463 if (!@rel_subflows) {
464 foreach my $mv (qw(mass volume)) {
465 $sail_total[$ci]{$mv}= 0;
470 my $applylimit= sub {
471 my ($mv, $max, $f2val) = @_;
472 $max= 1e9 unless defined $max;
473 #print " DEFINED MAX $mv $max ";
475 ". sprintf("%-10s","${mv}_$ci:")." ".
477 #print " PART MAX $_->{Var} $_->{Flow}{Ix} ";
478 $f2val->($_->{Flow}) .' '. $_->{Var};
483 $applylimit->('mass', $max_mass, sub { $_[0]{'unitmass'} *1e-3 });
484 $applylimit->('volume', $max_volume, sub { $_[0]{'unitvolume'}*1e-3 });
485 $applylimit->('capital',$max_capital,sub { $_[0]{'org_price'} });
492 ", map { "$_->{Var} >= 0" } @subflows)."
499 ", map { $_->{Var} } @subflows)."
504 if ($qa->{'debug'}) {
513 my $input= pipethrough_prep();
514 print $input $cplex or die $!;
515 my $output= pipethrough_run_along($input, undef, 'glpsol',
516 qw(glpsol --tmlim 2 --memlim 5 --intopt --cuts --bfs
517 --cpxlp /dev/stdin -o /dev/stdout));
518 print "<pre>\n" if $qa->{'debug'};
519 my $found_section= 0;
524 print encode_entities($_) if $qa->{'debug'};
525 if (m/^\s*No\.\s+(Row|Column) name\s+(?:St\s+)?Activity\s/) {
526 die "$_ $found_section ?" if $found_section>0;
530 if (m/^Objective:\s+totalprofit = (\d+\.\d*) /) {
531 $expected_total_profit= $1;
533 next unless $found_section==1;
534 if (!length $continuation) {
535 next if !$continuation && m/^[- ]+$/;
540 if (m/^ \s* \d+ \s+ \w+ $/x) {
545 $_= $continuation.$_;
547 my ($varname, $qty) = m/^
549 (\w+) \s+ (?: [A-Z*]+ \s+ )?
552 if ($varname =~ m/^f(\d+)s(\d+)_/) {
553 my ($ix,$orgix) = ($1,$2);
554 my $flow= $flows[$ix] or die;
555 my @relsubflow= grep { $_->{Org} == $orgix }
556 @{ $flow->{Subflows} };
557 die "$ix $orgix @relsubflow" unless @relsubflow == 1;
558 my $sf= $relsubflow[0];
560 $sf->{OptProfit}= $qty * $flow->{'unitprofit'};
561 $sf->{OptCapital}= $qty * $flow->{'org_price'};
562 } elsif ($varname =~ m/^(mass|volume)_(\d+)$/) {
563 my ($mv,$ix) = ($1,$2);
564 $sail_total[$ix]{$mv}= $qty;
567 print "</pre>\n" if $qa->{'debug'};
568 my $prerr= "\n=====\n$cplex\n=====\n$glpsol_out\n=====\n ";
569 pipethrough_run_finish($output,$prerr);
570 map { defined $_->{OptQty} or die "$prerr $_->{Flow}{Ix}" } @subflows;
573 $addcols->({ DoReverse => 1, TotalSubflows => 1, Special => sub {
574 my ($flow,$col,$v,$spec) = @_;
575 if ($flow->{ExpectedUnitProfit} < 0) {
577 $spec->{String}= '(Small margin)';
578 $spec->{Align}= 'align=center';
583 $addcols->({ Total => 0, DoReverse => 1, TotalSubflows => 1 }, qw(
589 % } # ========== OPTIMISATION ==========
593 % my $cdspan= $qa->{ShowStalls} ? ' colspan=2' : '';
594 % my $cdstall= $qa->{ShowStalls} ? '<th>Stall</th>' : '';
595 <table id="trades" rules=groups>
598 <% $qa->{ShowStalls} ? '<colgroup span=2>' : '' %>
610 <th<% $cdspan %>>Collect
611 <th<% $cdspan %>>Deliver
613 <th colspan=2>Collect
614 <th colspan=2>Deliver
620 <th colspan=3>Planned
625 <th>Island <% $cdstall %>
626 <th>Island <% $cdstall %>
647 <tr id="trades_sort">
648 % foreach my $col (@cols) {
652 % foreach my $flowix (0..$#flows) {
653 % my $flow= $flows[$flowix];
654 % my $rowid= "id_row_$flow->{UidShort}";
655 <tr id="<% $rowid %>" class="datarow<% $flowix & 1 %>">
656 <td><input type=hidden name=R<% $flow->{UidShort} %> value="">
657 <input type=checkbox name=T<% $flow->{UidShort} %> value=""
658 <% $flow->{Suppress} ? '' : 'checked' %> >
660 % while ($ci < @cols) {
661 % my $col= $cols[$ci];
664 % Align => ($col->{Text} ? '' : 'align=right')
666 % my $cn= $col->{Name};
668 % if (!$col->{TotalSubflows}) {
672 % $v += $_->{$cn} foreach @{ $flow->{Subflows} };
674 % if ($col->{Special}) { $col->{Special}($flow,$col,$v,$spec); }
675 % $col->{Total} += $v
676 % if defined $col->{Total} and not $flow->{Suppress};
677 % $v='' if !$col->{Text} && !$v;
678 % my $sortkey= $col->{SortColKey} ?
679 % $flow->{$col->{SortColKey}} : $v;
680 % $ts_sortkeys{$ci}{$rowid}= $sortkey;
681 <td <% $spec->{Span} ? "colspan=$spec->{Span}" : ''
683 %>><% exists $spec->{String} ? $spec->{String} : $v |h %>
684 % $ci += $spec->{Span};
687 <tr id="trades_total">
690 % foreach my $ci (3..$#cols) {
691 % my $col= $cols[$ci];
693 % if (defined $col->{Total}) {
694 <% $col->{Total} |h %>
699 <&| tabsort, cols => \@cols, table => 'trades', rowclass => 'datarow',
700 throw => 'trades_sort', tbrow => 'trades_total' &>
701 ts_sortkeys= <% to_json_protecttags(\%ts_sortkeys) %>;
704 <input type=submit name=update value="Update">
706 % if ($optimise) { # ========== TRADING PLAN ==========
708 % my $iquery= $dbh->prepare('SELECT islandname FROM islands
709 % WHERE islandid = ?');
711 % my $total_total= 0;
714 <h1>Voyage trading plan</h1>
716 % foreach my $i (0..$#islandids) {
719 % $iquery->execute($islandids[$i]);
720 % my ($islandname) = $iquery->fetchrow_array();
722 <strong>Start at <% $islandname |h %></strong>
724 % my $this_dist= $distance->($islandids[$i-1],$islandids[$i]);
725 % $total_dist += $this_dist;
728 foreach my $sf (@subflows) {
729 next unless $sf->{Org} < $i && $sf->{Dst} >= $i;
731 $sf->{OptQty} * $sf->{Flow}{'dst_price'};
734 <strong>Sail to <% $islandname |h %></strong>
735 - <% $this_dist |h %> leagues,
736 <% $total_value %>poe at risk
742 #print "<tr><td colspan=6>" if $qa->{'debug'};
743 foreach my $od (qw(org dst)) {
744 #print " [[ i $i od $od " if $qa->{'debug'};
745 foreach my $sf (@subflows) {
747 next if $f->{Suppress};
748 next unless $sf->{ucfirst $od} == $i;
749 #print " FLOW $f->{Ix} SUB #$sf->{Org}..$sf->{Dst} "
751 next unless $sf->{OptQty};
752 my $arbitrage= $f->{'org_id'} == $f->{'dst_id'};
753 die if $arbitrage and $sf->{Org} != $sf->{Dst};
754 my $price= $f->{"${od}_price"};
755 my $stallname= $f->{"${od}_stallname"};
756 my $todo= \$flowlists{$od}{
758 (sprintf "%07d", ($od eq 'dst' ?
759 9999999-$price : $price)),
767 $$todo->{'commodname'}= $f->{'commodname'};
768 $$todo->{'stallname'}= $stallname;
769 $$todo->{Price}= $price;
770 $$todo->{Timestamp}= $f->{"${od}_timestamp"};
771 $$todo->{Qty} += $sf->{OptQty};
772 $$todo->{Total}= $$todo->{Price} * $$todo->{Qty};
773 $$todo->{Stalls}= $f->{"${od}Stalls"};
774 $$todo->{"${od}Arbitrage"}= 1 if $arbitrage;
776 #print "]] " if $qa->{'debug'};
778 #print "</tr>" if $qa->{'debug'};
780 my ($total, $total_to_show);
782 my $show_total= sub {
783 my ($totaldesc, $sign) = @_;
784 if (defined $total) {
785 die if defined $total_to_show;
786 $total_total += $sign * $total;
787 $total_to_show= [ $totaldesc, $total ];
792 my $show_total_now= sub {
794 return unless defined $total_to_show;
795 my ($totaldesc,$totalwas) = @$total_to_show;
799 <td colspan=2><% $xinfo %>
800 <td colspan=2 align=right><% $totaldesc %>
801 <td align=right><% $totalwas |h %> total
803 $total_to_show= undef;
806 % my $show_flows= sub {
807 % my ($od,$arbitrage,$collectdeliver) = @_;
808 % my $todo= $flowlists{$od};
809 % return unless $todo;
810 % foreach my $tkey (sort keys %$todo) {
811 % my $t= $todo->{$tkey};
812 % next if $t->{"${od}Arbitrage"} != $arbitrage;
813 % $show_total_now->('');
814 % if (!$age_reported++) {
815 % my $age= $now - $t->{Timestamp};
816 % my $cellid= "da_${i}";
817 % $da_ages{$cellid}= $age;
819 (Data age: <span id="<% $cellid %>"><% prettyprint_age($age) %></span>)
820 % } elsif (!defined $total) {
824 % $total += $t->{Total};
825 % my $span= 0 + keys %{ $t->{Stalls} };
826 % my $td= "td rowspan=$span";
827 <tr class="datarow<% $dline %>">
828 <<% $td %>><% $collectdeliver %>
829 <<% $td %>><% $t->{'commodname'} |h %>
831 % my @stalls= sort keys %{ $t->{Stalls} };
833 % my $name= $stalls[$_[0]];
838 <<% $td %> align=right><% $t->{Price} |h %> poe ea.
839 <<% $td %> align=right><% $t->{Qty} |h %> unit(s)
840 <<% $td %> align=right><% $t->{Total} |h %> total
842 % foreach my $stallix (1..$#stalls) {
843 <tr class="datarow<% $dline %>">
844 % $pstall->($stallix);
852 $show_flows->('dst',0,'Deliver'); $show_total->('Proceeds',1);
853 $show_flows->('org',1,'Collect'); $show_total->('(Arbitrage) outlay',-1);
854 $show_flows->('dst',1,'Deliver'); $show_total->('(Arbitrage) proceeds',1);
855 $show_flows->('org',0,'Collect'); $show_total->('Outlay',-1);
857 if ($i < $#islandids) {
858 $totals .= "In hold $sail_total[$i]{mass}kg,".
859 " $sail_total[$i]{volume} l";
860 my $delim= '; spare ';
862 my ($max, $got, $units) = @_;
863 return unless defined $max;
865 $totals .= sprintf "%g %s", ($max-$got), $units;
868 $domv->($max_mass, $sail_total[$i]{mass}, 'kg');
869 $domv->($max_volume, $sail_total[$i]{volume}, 'l');
872 $show_total_now->($totals);
876 <td colspan=2>Total distance: <% $total_dist %> leagues.
877 <td colspan=3 align=right>Overall net cash flow
878 <td align=right><strong><%
879 $total_total < 0 ? -$total_total." loss" : $total_total." gain"
882 <& query_age:dataages, id2age => \%da_ages &>
883 Expected average profit:
884 approx. <strong><% sprintf "%d", $expected_total_profit %></strong> poe
885 (considering expected losses, but ignoring rum consumed)
887 % } # ========== TRADING PLAN ==========