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.
43 da_pageload= Date.now();
49 my $loss_per_league= 1e-7;
55 my $sd_condition= sub {
57 my $islandid= $islandids[$ix];
58 if (defined $islandid) {
59 return "${bs}.islandid = $islandid";
61 push @query_params, $archipelagoes[$ix];
62 return "${bs}_islands.archipelago = ?";
67 # $islandpair{$a,$b}= [ $start_island_ix, $end_island_ix ]
69 my $specific= !grep { !defined $_ } @islandids;
72 foreach my $src_i (0..$#islandids) {
73 my $src_isle= $islandids[$src_i];
74 my $src_cond= $sd_condition->('sell',$src_i);
76 foreach my $dst_i ($src_i..$#islandids) {
77 my $dst_isle= $islandids[$dst_i];
78 my $dst_cond= $sd_condition->('buy',$dst_i);
79 if ($dst_i==$src_i and !defined $src_isle) {
80 # we always want arbitrage, but mentioning an arch
81 # once shouldn't produce intra-arch trades
83 "($dst_cond AND sell.islandid = buy.islandid)";
85 push @dst_conds, $dst_cond;
87 if ($specific && !$confusing &&
88 # With a circular route, do not carry goods round the loop
89 !(($src_i==0 || $src_i==$#islandids) &&
90 $dst_i==$#islandids &&
91 $src_isle == $islandids[$dst_i])) {
92 if ($islandpair{$src_isle,$dst_isle}) {
94 print "confusing $src_i $src_isle $dst_i $dst_isle\n";
96 $islandpair{$src_isle,$dst_isle}=
101 push @flow_conds, "$src_cond AND (
108 SELECT sell_islands.islandname org_name,
109 sell_islands.islandid org_id,
110 sell.price org_price,
111 sell.qty org_qty_stall,
112 sell_stalls.stallname org_stallname,
113 sell.stallid org_stallid,
114 sell_uploads.timestamp org_timestamp,
115 buy_islands.islandname dst_name,
116 buy_islands.islandid dst_id,
118 buy.qty dst_qty_stall,
119 buy_stalls.stallname dst_stallname,
120 buy.stallid dst_stallid,
121 buy_uploads.timestamp dst_timestamp,
122 ".($qa->{ShowStalls} ? "
123 sell.qty org_qty_agg,
126 (SELECT sum(qty) FROM sell AS sell_agg
127 WHERE sell_agg.commodid = commods.commodid
128 AND sell_agg.islandid = sell.islandid
129 AND sell_agg.price = sell.price) org_qty_agg,
130 (SELECT sum(qty) FROM buy AS buy_agg
131 WHERE buy_agg.commodid = commods.commodid
132 AND buy_agg.islandid = buy.islandid
133 AND buy_agg.price = buy.price) dst_qty_agg,
135 commods.commodname commodname,
136 commods.commodid commodid,
137 commods.unitmass unitmass,
138 commods.unitvolume unitvolume,
140 buy.price - sell.price unitprofit
142 JOIN sell ON commods.commodid = sell.commodid
143 JOIN buy ON commods.commodid = buy.commodid
144 JOIN islands AS sell_islands ON sell.islandid = sell_islands.islandid
145 JOIN islands AS buy_islands ON buy.islandid = buy_islands.islandid
146 JOIN uploads AS sell_uploads ON sell.islandid = sell_uploads.islandid
147 JOIN uploads AS buy_uploads ON buy.islandid = buy_uploads.islandid
148 JOIN stalls AS sell_stalls ON sell.stallid = sell_stalls.stallid
149 JOIN stalls AS buy_stalls ON buy.stallid = buy_stalls.stallid
150 JOIN dists ON aiid = sell.islandid AND biid = buy.islandid
155 AND buy.price > sell.price
156 ORDER BY org_name, dst_name, commodname, unitprofit DESC,
157 org_price, dst_price DESC,
158 org_stallname, dst_stallname
161 my $sth= $dbh->prepare($stmt);
162 $sth->execute(@query_params);
165 my $distquery= $dbh->prepare("
166 SELECT dist FROM dists WHERE aiid = ? AND biid = ?
170 my $d= $dists{$from}{$to};
171 return $d if defined $d;
172 $distquery->execute($from,$to);
173 $d = $distquery->fetchrow_array();
174 defined $d or die "$from $to ?";
175 $dists{$from}{$to}= $d;
179 my @cols= ({ NoSort => 1 });
183 foreach my $name (@_) {
184 my $col= { Name => $name, %$base };
185 $col->{Numeric}=1 if !$col->{Text};
190 if ($qa->{ShowStalls}) {
191 $addcols->({ Text => 1 }, qw(
192 org_name org_stallname
193 dst_name dst_stallname
196 $addcols->({Text => 1 }, qw(
200 $addcols->({ Text => 1 }, qw(commodname));
201 $addcols->({ DoReverse => 1 },
202 qw( org_price org_qty_agg dst_price dst_qty_agg
204 $addcols->({ DoReverse => 1, SortColKey => 'MarginSortKey' },
207 $addcols->({ DoReverse => 1 },
208 qw( unitprofit MaxQty MaxCapital MaxProfit dist
210 foreach my $v (qw(MaxMass MaxVolume)) {
212 DoReverse => 1, Total => 0, SortColKey => "${v}SortKey" }, $v);
217 % if ($qa->{'debug'}) {
220 <% join(' | ',@query_params) |h %>
224 <& dumptable:start, qa => $qa, sth => $sth &>
227 % while ($got= $sth->fetchrow_hashref()) {
230 my $f= $flows[$#flows];
233 grep { $f->{$_} ne $got->{$_} }
234 qw(org_id org_price dst_id dst_price commodid)
236 # Make a new flow rather than adding to the existing one
239 Ix => scalar(@flows),
243 $f->{"org_stallid"}= $f->{"dst_stallid"}= 'all'
244 if !$qa->{ShowStalls};
247 foreach my $od (qw(org dst)) {
249 $got->{"${od}_stallname"}
251 $got->{"${od}_qty_stall"}
256 <& dumptable:row, qa => $qa, sth => $sth, row => $f &>
258 <& dumptable:end, qa => $qa &>
264 print 'No profitable trading opportunities were found.';
268 foreach my $f (@flows) {
270 $f->{MaxQty}= $f->{'org_qty_agg'} < $f->{'dst_qty_agg'}
271 ? $f->{'org_qty_agg'} : $f->{'dst_qty_agg'};
272 $f->{MaxProfit}= $f->{MaxQty} * $f->{'unitprofit'};
273 $f->{MaxCapital}= $f->{MaxQty} * $f->{'org_price'};
275 $f->{MaxMassSortKey}= $f->{MaxQty} * $f->{'unitmass'};
276 $f->{MaxVolumeSortKey}= $f->{MaxQty} * $f->{'unitvolume'};
277 foreach my $v (qw(Mass Volume)) {
278 $f->{"Max$v"}= sprintf "%.1f", $f->{"Max${v}SortKey"} * 1e-6;
281 $f->{MarginSortKey}= sprintf "%d",
282 $f->{'dst_price'} * 10000 / $f->{'org_price'};
283 $f->{Margin}= sprintf "%3.1f%%",
284 $f->{'dst_price'} * 100.0 / $f->{'org_price'} - 100.0;
286 $f->{ExpectedUnitProfit}=
287 $f->{'dst_price'} * (1.0 - $loss_per_league) ** $f->{'dist'}
290 $dists{'org_id'}{'dst_id'}= $f->{'dist'};
292 my @uid= $f->{commodid};
293 foreach my $od (qw(org dst)) {
298 $f->{"${od}_stallid"}
299 if $qa->{ShowStalls};
301 $f->{UidLong}= join '_', @uid;
309 my $this= $uue % $base;
310 print STDERR "uue=$uue this=$this ";
315 $cmpu .= chr($this + ($this < 26 ? ord('a') :
316 $this < 52 ? ord('A')-26
318 print STDERR " uue=$uue this=$this cmpu=$cmpu\n";
319 die "$cmpu $uue ?" if length $cmpu > 20;
323 $f->{UidShort}= $cmpu;
325 if ($qa->{'debug'}) {
330 my $v= m/^[a-z]/ ? ord($&)-ord('a') :
331 m/^[A-Z]/ ? ord($&)-ord('A')+26 :
332 m/^[0-9]/ ? ord($&)-ord('0')+52 :
338 #print STDERR "(next)\n";
340 die "$f->{UidShort} $_ ?" unless defined $mul;
341 $outuid[$#outuid] += $v * $mul;
343 #print STDERR "$f->{UidShort} $_ $& v=$v mul=$mul ord()=".ord($&).
344 # "[vs.".ord('a').",".ord('A').",".ord('0')."]".
345 # " outuid=@outuid\n";
350 my $recons_long= join '_', @outuid;
351 $f->{UidLong} eq $recons_long or
352 die "$f->{UidLong} = $f->{UidShort} = $recons_long ?";
355 if (defined $qa->{"R$f->{UidShort}"} &&
356 !defined $qa->{"T$f->{UidShort}"}) {
363 % my $optimise= $specific && !$confusing && @islandids>1;
367 % if (@islandids<=1) {
371 Route contains archipelago(es), not just specific islands.
374 Route is complex - it visits the same island several times
375 and isn't a simple loop.
377 Therefore, optimal voyage trade plan not calculated.
379 % } else { # ========== OPTMISATION ==========
388 sprintf "%.20f %s", $_->{ExpectedUnitProfit}, $_->{Var}
395 foreach my $flow (@flows) {
396 if ($flow->{Suppress}) {
402 foreach my $od (qw(org dst)) {
403 my $cstname= join '_', (
408 $flow->{"${od}_price"},
409 $flow->{"${od}_stallid"},
412 push @{ $avail_csts{$cstname}{Flows} }, $flow->{Var};
413 $avail_csts{$cstname}{Qty}= $flow->{"${od}_qty_agg"};
416 foreach my $cstname (sort keys %avail_csts) {
417 my $c= $avail_csts{$cstname};
419 ". sprintf("%-30s","$cstname:")." ".
420 join("+", @{ $c->{Flows} }).
421 " <= ".$c->{Qty}."\n";
427 ", map { "$_->{Var} >= 0" } @flows)."
432 if ($qa->{'debug'}) {
441 my $input= pipethrough_prep();
442 print $input $cplex or die $!;
443 my $output= pipethrough_run_along($input, undef, 'glpsol',
444 qw(glpsol --cpxlp /dev/stdin -o /dev/stdout));
445 print "<pre>\n" if $qa->{'debug'};
446 my $found_section= 0;
450 print encode_entities($_) if $qa->{'debug'};
451 if (m/^\s*No\.\s+Column name\s+St\s+Activity\s/) {
452 die if $found_section>0;
456 next unless $found_section==1;
463 m/^\s*\d+\s+f(\d+)\s+\S+\s+(\d+)\s/ or die "$_ ?";
464 my $flow= $flows[$ix] or die;
465 $flow->{OptQty}= $qty;
466 $flow->{OptProfit}= $flow->{'unitprofit'} * $qty;
467 $flow->{OptCapital}= $flow->{OptQty} * $flow->{'org_price'};
469 print "</pre>\n" if $qa->{'debug'};
470 my $prerr= "\n=====\n$cplex\n=====\n$glpsol_out\n=====\n ";
471 pipethrough_run_finish($output,$prerr);
472 die $prerr unless $found_section;
475 $addcols->({ DoReverse => 1 }, qw(
478 $addcols->({ Total => 0, DoReverse => 1 }, qw(
484 % } # ========== OPTIMISATION ==========
488 % my $cdspan= $qa->{ShowStalls} ? ' colspan=2' : '';
489 % my $cdstall= $qa->{ShowStalls} ? '<th>Stall</th>' : '';
490 <table id="trades" rules=groups>
493 <% $qa->{ShowStalls} ? '<colgroup span=2>' : '' %>
505 <th<% $cdspan %>>Collect
506 <th<% $cdspan %>>Deliver
508 <th colspan=2>Collect
509 <th colspan=2>Deliver
515 <th colspan=3>Planned
520 <th>Island <% $cdstall %>
521 <th>Island <% $cdstall %>
542 <tr id="trades_sort">
543 % foreach my $col (@cols) {
547 % foreach my $flowix (0..$#flows) {
548 % my $flow= $flows[$flowix];
549 % my $rowid= "id_row_$flow->{UidShort}";
550 <tr id="<% $rowid %>" class="datarow<% $flowix & 1 %>">
551 <td><input type=hidden name=R<% $flow->{UidShort} %> value="">
552 <input type=checkbox name=T<% $flow->{UidShort} %> value=""
553 <% $flow->{Suppress} ? '' : 'checked' %> >
554 % foreach my $ci (1..$#cols) {
555 % my $col= $cols[$ci];
556 % my $v= $flow->{$col->{Name}};
557 % $col->{Total} += $v
558 % if defined $col->{Total} and not $flow->{Suppress};
559 % $v='' if !$col->{Text} && !$v;
560 % my $sortkey= $col->{SortColKey} ?
561 % $flow->{$col->{SortColKey}} : $v;
562 % $ts_sortkeys{$ci}{$rowid}= $sortkey;
563 <td <% $col->{Text} ? '' : 'align=right' %>><% $v |h %>
566 <tr id="trades_total">
569 % foreach my $ci (3..$#cols) {
570 % my $col= $cols[$ci];
572 % if (defined $col->{Total}) {
573 <% $col->{Total} |h %>
578 <&| tabsort, cols => \@cols, table => 'trades', rowclass => 'datarow',
579 throw => 'trades_sort', tbrow => 'trades_total' &>
580 ts_sortkeys= <% to_json_protecttags(\%ts_sortkeys) %>;
583 <input type=submit name=update value="Update">
585 % if ($optimise) { # ========== TRADING PLAN ==========
587 % my $iquery= $dbh->prepare('SELECT islandname FROM islands
588 % WHERE islandid = ?');
590 % my $total_total= 0;
593 <h1>Voyage trading plan</h1>
595 % foreach my $i (0..$#islandids) {
598 % $iquery->execute($islandids[$i]);
599 % my ($islandname) = $iquery->fetchrow_array();
600 % my $this_dist= $distance->($islandids[$i-1],$islandids[$i]);
601 % $total_dist += $this_dist;
603 <strong>Start at <% $islandname |h %></strong>
605 <strong>Sail to <% $islandname |h %></strong>
606 - <% $this_dist |h %> leagues </td>
611 foreach my $od (qw(org dst)) {
612 foreach my $f (@flows) {
613 next if $f->{Suppress};
614 next unless $f->{"${od}_id"} == $islandids[$i];
615 next unless $f->{OptQty};
616 my $arbitrage= $f->{'org_id'} == $f->{'dst_id'};
617 my $loop= $islandids[0] == $islandids[-1] &&
618 ($i==0 || $i==$#islandids);
619 next if $loop and ($arbitrage ? $i :
620 !!$i == !!($od eq 'org'));
621 my $price= $f->{"${od}_price"};
622 my $stallname= $f->{"${od}_stallname"};
623 my $todo= \$flowlists{$od}{
625 (sprintf "%07d", ($od eq 'dst' ?
626 9999999-$price : $price)),
634 $$todo->{'commodname'}= $f->{'commodname'};
635 $$todo->{'stallname'}= $stallname;
636 $$todo->{Price}= $price;
637 $$todo->{Timestamp}= $f->{"${od}_timestamp"};
638 $$todo->{Qty} += $f->{OptQty};
639 $$todo->{Total}= $$todo->{Price} * $$todo->{Qty};
640 $$todo->{Stalls}= $f->{"${od}Stalls"};
641 $$todo->{"${od}Arbitrage"}= 1 if $arbitrage;
647 my $show_flows= sub {
648 my ($od,$arbitrage,$collectdeliver) = @_;
651 % my $todo= $flowlists{$od};
652 % return unless $todo;
653 % foreach my $tkey (sort keys %$todo) {
654 % my $t= $todo->{$tkey};
655 % next if $t->{"${od}Arbitrage"} != $arbitrage;
656 % if (!$age_reported++) {
657 % my $age= $now - $t->{Timestamp};
658 % my $cellid= "da_${i}";
659 % $da_ages{$cellid}= $age;
661 (Data age: <span id="<% $cellid %>"><% prettyprint_age($age) %></span>)
662 % } elsif (!defined $total) {
666 % $total += $t->{Total};
667 % my $span= 0 + keys %{ $t->{Stalls} };
668 % my $td= "td rowspan=$span";
669 <tr class="datarow<% $dline %>">
670 <<% $td %>><% $collectdeliver %>
671 <<% $td %>><% $t->{'commodname'} |h %>
673 % my @stalls= sort keys %{ $t->{Stalls} };
675 % my $name= $stalls[$_[0]];
680 <<% $td %> align=right><% $t->{Price} |h %> poe ea.
681 <<% $td %> align=right><% $t->{Qty} |h %> unit(s)
682 <<% $td %> align=right><% $t->{Total} |h %> total
684 % foreach my $stallix (1..$#stalls) {
685 <tr class="datarow<% $dline %>">
686 % $pstall->($stallix);
692 % my $show_total= sub {
693 % my ($totaldesc, $sign)= @_;
694 % if (defined $total) {
697 <td colspan=2 align=right><% $totaldesc %>
698 <td align=right><% $total |h %> total
699 % $total_total += $sign * $total;
706 $show_flows->('dst',0,'Deliver'); $show_total->('Proceeds',1);
707 $show_flows->('org',1,'Collect'); $show_total->('(Arbitrage) outlay',-1);
708 $show_flows->('dst',1,'Deliver'); $show_total->('(Arbitrage) proceeds',1);
709 $show_flows->('org',0,'Collect'); $show_total->('Outlay',-1);
714 <td colspan=2>Total distance: <% $total_dist %> leagues.
715 <td colspan=3 align=right>Overall net cash flow
716 <td align=right><strong><%
717 $total_total < 0 ? -$total_total." loss" : $total_total." gain"
720 <& query_age:dataages, id2age => \%da_ages &>
722 % } # ========== TRADING PLAN ==========