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;
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 = ?";
72 # $islandpair{$a,$b}= [ $start_island_ix, $end_island_ix ]
74 my $specific= !grep { !defined $_ } @islandids;
77 foreach my $src_i (0..$#islandids) {
78 my $src_isle= $islandids[$src_i];
79 my $src_cond= $sd_condition->('sell',$src_i);
81 foreach my $dst_i ($src_i..$#islandids) {
82 my $dst_isle= $islandids[$dst_i];
83 my $dst_cond= $sd_condition->('buy',$dst_i);
84 if ($dst_i==$src_i and !defined $src_isle) {
85 # we always want arbitrage, but mentioning an arch
86 # once shouldn't produce intra-arch trades
88 "($dst_cond AND sell.islandid = buy.islandid)";
90 push @dst_conds, $dst_cond;
92 if ($specific && !$confusing &&
93 # With a circular route, do not carry goods round the loop
94 !(($src_i==0 || $src_i==$#islandids) &&
95 $dst_i==$#islandids &&
96 $src_isle == $islandids[$dst_i])) {
97 if ($islandpair{$src_isle,$dst_isle}) {
99 print "confusing $src_i $src_isle $dst_i $dst_isle\n";
101 $islandpair{$src_isle,$dst_isle}=
106 push @flow_conds, "$src_cond AND (
113 SELECT sell_islands.islandname org_name,
114 sell_islands.islandid org_id,
115 sell.price org_price,
116 sell.qty org_qty_stall,
117 sell_stalls.stallname org_stallname,
118 sell.stallid org_stallid,
119 sell_uploads.timestamp org_timestamp,
120 buy_islands.islandname dst_name,
121 buy_islands.islandid dst_id,
123 buy.qty dst_qty_stall,
124 buy_stalls.stallname dst_stallname,
125 buy.stallid dst_stallid,
126 buy_uploads.timestamp dst_timestamp,
127 ".($qa->{ShowStalls} ? "
128 sell.qty org_qty_agg,
131 (SELECT sum(qty) FROM sell AS sell_agg
132 WHERE sell_agg.commodid = commods.commodid
133 AND sell_agg.islandid = sell.islandid
134 AND sell_agg.price = sell.price) org_qty_agg,
135 (SELECT sum(qty) FROM buy AS buy_agg
136 WHERE buy_agg.commodid = commods.commodid
137 AND buy_agg.islandid = buy.islandid
138 AND buy_agg.price = buy.price) dst_qty_agg,
140 commods.commodname commodname,
141 commods.commodid commodid,
142 commods.unitmass unitmass,
143 commods.unitvolume unitvolume,
145 buy.price - sell.price unitprofit
147 JOIN sell ON commods.commodid = sell.commodid
148 JOIN buy ON commods.commodid = buy.commodid
149 JOIN islands AS sell_islands ON sell.islandid = sell_islands.islandid
150 JOIN islands AS buy_islands ON buy.islandid = buy_islands.islandid
151 JOIN uploads AS sell_uploads ON sell.islandid = sell_uploads.islandid
152 JOIN uploads AS buy_uploads ON buy.islandid = buy_uploads.islandid
153 JOIN stalls AS sell_stalls ON sell.stallid = sell_stalls.stallid
154 JOIN stalls AS buy_stalls ON buy.stallid = buy_stalls.stallid
155 JOIN dists ON aiid = sell.islandid AND biid = buy.islandid
160 AND buy.price > sell.price
161 ORDER BY org_name, dst_name, commodname, unitprofit DESC,
162 org_price, dst_price DESC,
163 org_stallname, dst_stallname
166 my $sth= $dbh->prepare($stmt);
167 $sth->execute(@query_params);
170 my $distquery= $dbh->prepare("
171 SELECT dist FROM dists WHERE aiid = ? AND biid = ?
175 my $d= $dists{$from}{$to};
176 return $d if defined $d;
177 $distquery->execute($from,$to);
178 $d = $distquery->fetchrow_array();
179 defined $d or die "$from $to ?";
180 $dists{$from}{$to}= $d;
184 my @cols= ({ NoSort => 1 });
188 foreach my $name (@_) {
189 my $col= { Name => $name, %$base };
190 $col->{Numeric}=1 if !$col->{Text};
195 if ($qa->{ShowStalls}) {
196 $addcols->({ Text => 1 }, qw(
197 org_name org_stallname
198 dst_name dst_stallname
201 $addcols->({Text => 1 }, qw(
205 $addcols->({ Text => 1 }, qw(commodname));
206 $addcols->({ DoReverse => 1 },
207 qw( org_price org_qty_agg dst_price dst_qty_agg
209 $addcols->({ DoReverse => 1, SortColKey => 'MarginSortKey' },
212 $addcols->({ DoReverse => 1 },
213 qw( unitprofit MaxQty MaxCapital MaxProfit dist
215 foreach my $v (qw(MaxMass MaxVolume)) {
217 DoReverse => 1, Total => 0, SortColKey => "${v}SortKey" }, $v);
222 % if ($qa->{'debug'}) {
225 <% join(' | ',@query_params) |h %>
229 <& dumptable:start, qa => $qa, sth => $sth &>
232 % while ($got= $sth->fetchrow_hashref()) {
235 my $f= $flows[$#flows];
238 grep { $f->{$_} ne $got->{$_} }
239 qw(org_id org_price dst_id dst_price commodid)
241 # Make a new flow rather than adding to the existing one
244 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 $f->{MarginSortKey}= sprintf "%d",
289 $f->{'dst_price'} * 10000 / $f->{'org_price'};
290 $f->{Margin}= sprintf "%3.1f%%",
291 $f->{'dst_price'} * 100.0 / $f->{'org_price'} - 100.0;
293 $f->{ExpectedUnitProfit}=
294 $f->{'dst_price'} * (1.0 - $loss_per_league) ** $f->{'dist'}
297 $dists{'org_id'}{'dst_id'}= $f->{'dist'};
299 my @uid= $f->{commodid};
300 foreach my $od (qw(org dst)) {
305 $f->{"${od}_stallid"}
306 if $qa->{ShowStalls};
308 $f->{UidLong}= join '_', @uid;
316 my $this= $uue % $base;
317 print STDERR "uue=$uue this=$this ";
322 $cmpu .= chr($this + ($this < 26 ? ord('a') :
323 $this < 52 ? ord('A')-26
325 print STDERR " uue=$uue this=$this cmpu=$cmpu\n";
326 die "$cmpu $uue ?" if length $cmpu > 20;
330 $f->{UidShort}= $cmpu;
332 if ($qa->{'debug'}) {
337 my $v= m/^[a-z]/ ? ord($&)-ord('a') :
338 m/^[A-Z]/ ? ord($&)-ord('A')+26 :
339 m/^[0-9]/ ? ord($&)-ord('0')+52 :
345 #print STDERR "(next)\n";
347 die "$f->{UidShort} $_ ?" unless defined $mul;
348 $outuid[$#outuid] += $v * $mul;
350 #print STDERR "$f->{UidShort} $_ $& v=$v mul=$mul ord()=".ord($&).
351 # "[vs.".ord('a').",".ord('A').",".ord('0')."]".
352 # " outuid=@outuid\n";
357 my $recons_long= join '_', @outuid;
358 $f->{UidLong} eq $recons_long or
359 die "$f->{UidLong} = $f->{UidShort} = $recons_long ?";
362 if (defined $qa->{"R$f->{UidShort}"} &&
363 !defined $qa->{"T$f->{UidShort}"}) {
370 % my $optimise= $specific && !$confusing && @islandids>1;
374 % if (@islandids<=1) {
375 Route contains only one location.
378 Route contains archipelago(es), not just specific islands.
381 Route is complex - it visits the same island several times
382 and isn't a simple loop.
384 Therefore, optimal voyage trade plan not calculated.
386 % } else { # ========== OPTMISATION ==========
395 sprintf "%+.20f %s", $_->{ExpectedUnitProfit}, $_->{Var}
402 foreach my $flow (@flows) {
403 if ($flow->{Suppress}) {
409 foreach my $od (qw(org dst)) {
410 my $cstname= join '_', (
415 $flow->{"${od}_price"},
416 $flow->{"${od}_stallid"},
419 push @{ $avail_csts{$cstname}{Flows} }, $flow->{Var};
420 $avail_csts{$cstname}{Qty}= $flow->{"${od}_qty_agg"};
423 foreach my $cstname (sort keys %avail_csts) {
424 my $c= $avail_csts{$cstname};
426 ". sprintf("%-30s","$cstname:")." ".
427 join("+", @{ $c->{Flows} }).
428 " <= ".$c->{Qty}."\n";
431 foreach my $ci (0..($#islandids-1)) {
433 foreach my $f (@flows) {
434 next if $f->{Suppress};
435 next if $f->{'org_id'} == $f->{'dst_id'};
436 next unless grep { $f->{'org_id'} == $_ }
438 next unless grep { $f->{'dst_id'} == $_ }
439 @islandids[$ci+1..@islandids-1];
441 #print " RELEVANT $ci $f->{Ix} ";
443 #print " RELEVANT $ci COUNT ".scalar(@rel_flows)." ";
444 next unless @rel_flows;
445 foreach my $mv (qw(mass volume)) {
446 my $max_vn= "max_$mv";
447 my $max= $mv eq 'mass' ? $max_mass : $max_volume;
448 $max= 1e9 unless defined $max;
449 #print " DEFINED MAX $mv $max ";
451 ". sprintf("%-10s","${mv}_$ci:")." ".
452 join(" + ", map { ($_->{"unit$mv"}*1e-3).' f'.$_->{Ix} } @rel_flows).
455 if (defined $max_capital) {
457 ". sprintf("%-10s","capital_$ci:")." ".
458 join(" + ", map { ($_->{"org_price"}).' f'.$_->{Ix} } @rel_flows).
467 ", map { "$_->{Var} >= 0" } @flows)."
474 ", map { "f$_" } (0..$#flows))."
479 if ($qa->{'debug'}) {
488 my $input= pipethrough_prep();
489 print $input $cplex or die $!;
490 my $output= pipethrough_run_along($input, undef, 'glpsol',
491 qw(glpsol --tmlim 2 --memlim 5 --intopt --cuts --bfs
492 --cpxlp /dev/stdin -o /dev/stdout));
493 print "<pre>\n" if $qa->{'debug'};
494 my $found_section= 0;
499 print encode_entities($_) if $qa->{'debug'};
500 if (m/^\s*No\.\s+(Row|Column) name\s+(?:St\s+)?Activity\s/) {
501 die "$_ $found_section ?" if $found_section>0;
505 next unless $found_section==1;
506 if (!length $continuation) {
507 next if !$continuation && m/^[- ]+$/;
512 if (m/^ \s* \d+ \s+ \w+ $/x) {
517 $_= $continuation.$_;
519 my ($varname, $qty) = m/^
521 (\w+) \s+ (?: [A-Z*]+ \s+ )?
524 if ($varname =~ m/^f(\d+)$/) {
526 my $flow= $flows[$ix] or die;
527 $flow->{OptQty}= $qty;
528 $flow->{OptProfit}= $flow->{'unitprofit'} * $qty;
529 $flow->{OptCapital}= $flow->{OptQty} *
530 $flow->{'org_price'};
531 } elsif ($varname =~ m/^(mass|volume)_(\d+)$/) {
532 my ($mv,$ix) = ($1,$2);
533 $total_massvol[$ix]{$mv}= $qty;
536 print "</pre>\n" if $qa->{'debug'};
537 my $prerr= "\n=====\n$cplex\n=====\n$glpsol_out\n=====\n ";
538 pipethrough_run_finish($output,$prerr);
539 map { defined $_->{OptQty} or die "$prerr $_->{Ix}" } @flows;
541 # die $prerr if grep { ! } @flows;
543 # die $prerr if map {
546 $addcols->({ DoReverse => 1, Special => sub {
547 my ($flow,$col,$v,$spec) = @_;
548 if ($flow->{ExpectedUnitProfit} < 0) {
550 $spec->{String}= '(Small margin)';
551 $spec->{Align}= 'align=center';
556 $addcols->({ Total => 0, DoReverse => 1 }, qw(
562 % } # ========== OPTIMISATION ==========
566 % my $cdspan= $qa->{ShowStalls} ? ' colspan=2' : '';
567 % my $cdstall= $qa->{ShowStalls} ? '<th>Stall</th>' : '';
568 <table id="trades" rules=groups>
571 <% $qa->{ShowStalls} ? '<colgroup span=2>' : '' %>
583 <th<% $cdspan %>>Collect
584 <th<% $cdspan %>>Deliver
586 <th colspan=2>Collect
587 <th colspan=2>Deliver
593 <th colspan=3>Planned
598 <th>Island <% $cdstall %>
599 <th>Island <% $cdstall %>
620 <tr id="trades_sort">
621 % foreach my $col (@cols) {
625 % foreach my $flowix (0..$#flows) {
626 % my $flow= $flows[$flowix];
627 % my $rowid= "id_row_$flow->{UidShort}";
628 <tr id="<% $rowid %>" class="datarow<% $flowix & 1 %>">
629 <td><input type=hidden name=R<% $flow->{UidShort} %> value="">
630 <input type=checkbox name=T<% $flow->{UidShort} %> value=""
631 <% $flow->{Suppress} ? '' : 'checked' %> >
633 % while ($ci < @cols) {
634 % my $col= $cols[$ci];
637 % Align => ($col->{Text} ? '' : 'align=right')
639 % my $v= $flow->{$col->{Name}};
640 % if ($col->{Special}) { $col->{Special}($flow,$col,$v,$spec); }
641 % $col->{Total} += $v
642 % if defined $col->{Total} and not $flow->{Suppress};
643 % $v='' if !$col->{Text} && !$v;
644 % my $sortkey= $col->{SortColKey} ?
645 % $flow->{$col->{SortColKey}} : $v;
646 % $ts_sortkeys{$ci}{$rowid}= $sortkey;
647 <td <% $spec->{Span} ? "colspan=$spec->{Span}" : ''
649 %>><% exists $spec->{String} ? $spec->{String} : $v |h %>
650 % $ci += $spec->{Span};
653 <tr id="trades_total">
656 % foreach my $ci (3..$#cols) {
657 % my $col= $cols[$ci];
659 % if (defined $col->{Total}) {
660 <% $col->{Total} |h %>
665 <&| tabsort, cols => \@cols, table => 'trades', rowclass => 'datarow',
666 throw => 'trades_sort', tbrow => 'trades_total' &>
667 ts_sortkeys= <% to_json_protecttags(\%ts_sortkeys) %>;
670 <input type=submit name=update value="Update">
672 % if ($optimise) { # ========== TRADING PLAN ==========
674 % my $iquery= $dbh->prepare('SELECT islandname FROM islands
675 % WHERE islandid = ?');
677 % my $total_total= 0;
680 <h1>Voyage trading plan</h1>
682 % foreach my $i (0..$#islandids) {
685 % $iquery->execute($islandids[$i]);
686 % my ($islandname) = $iquery->fetchrow_array();
688 <strong>Start at <% $islandname |h %></strong>
690 % my $this_dist= $distance->($islandids[$i-1],$islandids[$i]);
691 % $total_dist += $this_dist;
692 <strong>Sail to <% $islandname |h %></strong>
693 - <% $this_dist |h %> leagues </td>
698 foreach my $od (qw(org dst)) {
699 foreach my $f (@flows) {
700 next if $f->{Suppress};
701 next unless $f->{"${od}_id"} == $islandids[$i];
702 next unless $f->{OptQty};
703 my $arbitrage= $f->{'org_id'} == $f->{'dst_id'};
704 my $loop= $islandids[0] == $islandids[-1] &&
705 ($i==0 || $i==$#islandids);
706 next if $loop and ($arbitrage ? $i :
707 !!$i == !!($od eq 'org'));
708 my $price= $f->{"${od}_price"};
709 my $stallname= $f->{"${od}_stallname"};
710 my $todo= \$flowlists{$od}{
712 (sprintf "%07d", ($od eq 'dst' ?
713 9999999-$price : $price)),
721 $$todo->{'commodname'}= $f->{'commodname'};
722 $$todo->{'stallname'}= $stallname;
723 $$todo->{Price}= $price;
724 $$todo->{Timestamp}= $f->{"${od}_timestamp"};
725 $$todo->{Qty} += $f->{OptQty};
726 $$todo->{Total}= $$todo->{Price} * $$todo->{Qty};
727 $$todo->{Stalls}= $f->{"${od}Stalls"};
728 $$todo->{"${od}Arbitrage"}= 1 if $arbitrage;
732 my ($total, $total_to_show);
734 my $show_total= sub {
735 my ($totaldesc, $sign) = @_;
736 if (defined $total) {
737 die if defined $total_to_show;
738 $total_total += $sign * $total;
739 $total_to_show= [ $totaldesc, $total ];
744 my $show_total_now= sub {
746 return unless defined $total_to_show;
747 my ($totaldesc,$totalwas) = @$total_to_show;
751 <td colspan=2><% $xinfo %>
752 <td colspan=2 align=right><% $totaldesc %>
753 <td align=right><% $totalwas |h %> total
755 $total_to_show= undef;
758 % my $show_flows= sub {
759 % my ($od,$arbitrage,$collectdeliver) = @_;
760 % my $todo= $flowlists{$od};
761 % return unless $todo;
762 % foreach my $tkey (sort keys %$todo) {
763 % my $t= $todo->{$tkey};
764 % next if $t->{"${od}Arbitrage"} != $arbitrage;
765 % $show_total_now->('');
766 % if (!$age_reported++) {
767 % my $age= $now - $t->{Timestamp};
768 % my $cellid= "da_${i}";
769 % $da_ages{$cellid}= $age;
771 (Data age: <span id="<% $cellid %>"><% prettyprint_age($age) %></span>)
772 % } elsif (!defined $total) {
776 % $total += $t->{Total};
777 % my $span= 0 + keys %{ $t->{Stalls} };
778 % my $td= "td rowspan=$span";
779 <tr class="datarow<% $dline %>">
780 <<% $td %>><% $collectdeliver %>
781 <<% $td %>><% $t->{'commodname'} |h %>
783 % my @stalls= sort keys %{ $t->{Stalls} };
785 % my $name= $stalls[$_[0]];
790 <<% $td %> align=right><% $t->{Price} |h %> poe ea.
791 <<% $td %> align=right><% $t->{Qty} |h %> unit(s)
792 <<% $td %> align=right><% $t->{Total} |h %> total
794 % foreach my $stallix (1..$#stalls) {
795 <tr class="datarow<% $dline %>">
796 % $pstall->($stallix);
804 $show_flows->('dst',0,'Deliver'); $show_total->('Proceeds',1);
805 $show_flows->('org',1,'Collect'); $show_total->('(Arbitrage) outlay',-1);
806 $show_flows->('dst',1,'Deliver'); $show_total->('(Arbitrage) proceeds',1);
807 $show_flows->('org',0,'Collect'); $show_total->('Outlay',-1);
809 if ($i < $#islandids) {
810 $totals .= "In hold $total_massvol[$i]{mass} kg,".
811 " $total_massvol[$i]{volume} l";
812 my $delim= '; spare ';
814 my ($max, $got, $units) = @_;
815 return unless defined $max;
817 $totals .= sprintf "%g %s", ($max-$got), $units;
820 $domv->($max_mass, $total_massvol[$i]{mass}, 'kg');
821 $domv->($max_volume, $total_massvol[$i]{volume}, 'l');
824 $show_total_now->($totals);
828 <td colspan=2>Total distance: <% $total_dist %> leagues.
829 <td colspan=3 align=right>Overall net cash flow
830 <td align=right><strong><%
831 $total_total < 0 ? -$total_total." loss" : $total_total." gain"
834 <& query_age:dataages, id2age => \%da_ages &>
836 % } # ========== TRADING PLAN ==========