chiark / gitweb /
Do arbitrage in the middle
[ypp-sc-tools.db-live.git] / yarrg / web / routetrade
1 <%doc>
2
3  This is part of the YARRG website.  YARRG is a tool and website
4  for assisting players of Yohoho Puzzle Pirates.
5
6  Copyright (C) 2009 Ian Jackson <ijackson@chiark.greenend.org.uk>
7  Copyright (C) 2009 Clare Boothby
8
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
12    download the source.
13
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.
18
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.
23
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/>.
26
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.
30
31
32  This Mason component is the core trade planner for a specific route.
33
34
35 ========== TODO ==========
36 16:36 <ceb> alpha,byrne,papaya,turtle,jorvik,luthien is my example
37
38 use POST for update.  Hrrm.
39
40 LATER OR NOT AT ALL
41
42 adjustable potential cost of losses (rather than fixed 1e-BIG per league)
43
44 max volume/mass
45
46 ========== TODO ==========
47
48 </%doc>
49 <%args>
50 $dbh
51 @islandids
52 @archipelagoes
53 $qa
54 </%args>
55 <&| script &>
56   da_pageload= Date.now();
57 </&script>
58
59 <%perl>
60
61 my $now= time;
62 my $loss_per_league= 1e-7;
63
64 my @flow_conds;
65 my @query_params;
66
67 my $sd_condition= sub {
68         my ($bs, $ix) = @_;
69         my $islandid= $islandids[$ix];
70         if (defined $islandid) {
71                 return "${bs}.islandid = $islandid";
72         } else {
73                 push @query_params, $archipelagoes[$ix];
74                 return "${bs}_islands.archipelago = ?";
75         }
76 };
77
78 my %islandpair;
79 # $islandpair{$a,$b}= [ $start_island_ix, $end_island_ix ]
80
81 my $specific= !grep { !defined $_ } @islandids;
82 my $confusing= 0;
83
84 foreach my $src_i (0..$#islandids) {
85         my $src_isle= $islandids[$src_i];
86         my $src_cond= $sd_condition->('sell',$src_i);
87         my @dst_conds;
88         foreach my $dst_i ($src_i..$#islandids) {
89                 my $dst_isle= $islandids[$dst_i];
90                 my $dst_cond= $sd_condition->('buy',$dst_i);
91                 if ($dst_i==$src_i and !defined $src_isle) {
92                         # we always want arbitrage, but mentioning an arch
93                         # once shouldn't produce intra-arch trades
94                         $dst_cond=
95                                 "($dst_cond AND sell.islandid = buy.islandid)";
96                 }
97                 push @dst_conds, $dst_cond;
98
99                 if ($specific && !$confusing &&
100                     # With a circular route, do not carry goods round the loop
101                     !($src_i==0 && $dst_i==$#islandids &&
102                       $src_isle == $islandids[$dst_i])) {
103                         if ($islandpair{$src_isle,$dst_isle}) {
104                                 $confusing= 1;
105                         } else {
106                                 $islandpair{$src_isle,$dst_isle}=
107                                         [ $src_i, $dst_i ];
108                         }
109                 }
110         }
111         push @flow_conds, "$src_cond AND (
112                         ".join("
113                      OR ",@dst_conds)."
114                 )";
115 }
116
117 my $stmt= "             
118         SELECT  sell_islands.islandname                         org_name,
119                 sell_islands.islandid                           org_id,
120                 sell.price                                      org_price,
121                 sell.qty                                        org_qty_stall,
122                 sell_stalls.stallname                           org_stallname,
123                 sell.stallid                                    org_stallid,
124                 sell_uploads.timestamp                          org_timestamp,
125                 buy_islands.islandname                          dst_name,
126                 buy_islands.islandid                            dst_id,
127                 buy.price                                       dst_price,
128                 buy.qty                                         dst_qty_stall,
129                 buy_stalls.stallname                            dst_stallname,
130                 buy.stallid                                     dst_stallid,
131                 buy_uploads.timestamp                           dst_timestamp,
132 ".($qa->{ShowStalls} ? "
133                 sell.qty                                        org_qty_agg,
134                 buy.qty                                         dst_qty_agg,
135 " : "
136                 (SELECT sum(qty) FROM sell AS sell_agg
137                   WHERE sell_agg.commodid = commods.commodid
138                   AND   sell_agg.islandid = sell.islandid
139                   AND   sell_agg.price = sell.price)            org_qty_agg,
140                 (SELECT sum(qty) FROM buy AS buy_agg
141                   WHERE buy_agg.commodid = commods.commodid
142                   AND   buy_agg.islandid = buy.islandid
143                   AND   buy_agg.price = buy.price)              dst_qty_agg,
144 ")."
145                 commods.commodname                              commodname,
146                 commods.commodid                                commodid,
147                 commods.unitmass                                unitmass,
148                 commods.unitvolume                              unitvolume,
149                 dist                                            dist,
150                 buy.price - sell.price                          unitprofit
151         FROM commods
152         JOIN sell ON commods.commodid = sell.commodid
153         JOIN buy  ON commods.commodid = buy.commodid
154         JOIN islands AS sell_islands ON sell.islandid = sell_islands.islandid
155         JOIN islands AS buy_islands  ON buy.islandid  = buy_islands.islandid
156         JOIN uploads AS sell_uploads ON sell.islandid = sell_uploads.islandid
157         JOIN uploads AS buy_uploads  ON buy.islandid  = buy_uploads.islandid
158         JOIN stalls  AS sell_stalls  ON sell.stallid  = sell_stalls.stallid
159         JOIN stalls  AS buy_stalls   ON buy.stallid   = buy_stalls.stallid
160         JOIN dists ON aiid = sell.islandid AND biid = buy.islandid
161         WHERE   (
162                 ".join("
163            OR   ", @flow_conds)."
164         )
165           AND   buy.price > sell.price
166         ORDER BY org_name, dst_name, commodname, unitprofit DESC,
167                  org_price, dst_price DESC,
168                  org_stallname, dst_stallname
169      ";
170
171 my $sth= $dbh->prepare($stmt);
172 $sth->execute(@query_params);
173 my @flows;
174
175 my @cols= ({ NoSort => 1 });
176
177 my $addcols= sub {
178         my $base= shift @_;
179         foreach my $name (@_) {
180                 my $col= { Name => $name, %$base };
181                 $col->{Numeric}=1 if !$col->{Text};
182                 push @cols, $col;
183         }
184 };
185
186 if ($qa->{ShowStalls}) {
187         $addcols->({ Text => 1 }, qw(
188                 org_name org_stallname
189                 dst_name dst_stallname
190         ));
191 } else {
192         $addcols->({Text => 1 }, qw(
193                 org_name dst_name
194         ));
195 }
196 $addcols->({ Text => 1 }, qw(commodname));
197 $addcols->({ DoReverse => 1 },
198         qw(     org_price org_qty_agg dst_price dst_qty_agg
199         ));
200 $addcols->({ DoReverse => 1, SortColKey => 'MarginSortKey' },
201         qw(     Margin
202         ));
203 $addcols->({ DoReverse => 1 },
204         qw(     unitprofit MaxQty
205                 MaxCapital MaxProfit
206         ));
207
208 </%perl>
209
210 % if ($qa->{'debug'}) {
211 <pre>
212 <% $stmt |h %>
213 <% join(' | ',@query_params) |h %>
214 </pre>
215 % }
216
217 <& dumptable:start, qa => $qa, sth => $sth &>
218 % {
219 %   my $got;
220 %   while ($got= $sth->fetchrow_hashref()) {
221 <%perl>
222
223         my $f= $flows[$#flows];
224         if (    !$f ||
225                 $qa->{ShowStalls} ||
226                 grep { $f->{$_} ne $got->{$_} }
227                         qw(org_id org_price dst_id dst_price commodid)
228         ) {
229                 # Make a new flow rather than adding to the existing one
230
231                 $f= {
232                         Ix => scalar(@flows),
233                         Var => "f".@flows,
234                         %$got
235                 };
236                 $f->{"org_stallid"}= $f->{"dst_stallid"}= 'all'
237                         if !$qa->{ShowStalls};
238                 push @flows, $f;
239         }
240         foreach my $od (qw(org dst)) {
241                 $f->{"${od}Stalls"}{
242                         $got->{"${od}_stallname"}
243                     } =
244                         $got->{"${od}_qty_stall"}
245                     ;
246         }
247
248 </%perl>
249 <& dumptable:row, qa => $qa, sth => $sth, row => $f &>
250 %    }
251 <& dumptable:end, qa => $qa &>
252 % }
253
254 <%perl>
255 foreach my $f (@flows) {
256
257         $f->{MaxQty}= $f->{'org_qty_agg'} < $f->{'dst_qty_agg'}
258                 ? $f->{'org_qty_agg'} : $f->{'dst_qty_agg'};
259         $f->{MaxProfit}= $f->{MaxQty} * $f->{'unitprofit'};
260         $f->{MaxCapital}= $f->{MaxQty} * $f->{'org_price'};
261
262         $f->{MarginSortKey}= sprintf "%d",
263                 $f->{'dst_price'} * 10000 / $f->{'org_price'};
264         $f->{Margin}= sprintf "%3.1f%%",
265                 $f->{'dst_price'} * 100.0 / $f->{'org_price'} - 100.0;
266
267         $f->{ExpectedUnitProfit}=
268                 $f->{'dst_price'} * (1.0 - $loss_per_league) ** $f->{'dist'}
269                 - $f->{'org_price'};
270
271         my @uid= $f->{commodid};
272         foreach my $od (qw(org dst)) {
273                 push @uid,
274                         $f->{"${od}_id"},
275                         $f->{"${od}_price"};
276                 push @uid,
277                         $f->{"${od}_stallid"}
278                                 if $qa->{ShowStalls};
279         }
280         $f->{UidLong}= join '_', @uid;
281
282         my $base= 31;
283         my $cmpu= '';
284         map {
285                 my $uue= $_;
286                 my $first= $base;
287                 do {
288                         my $this= $uue % $base;
289 print STDERR "uue=$uue this=$this ";
290                         $uue -= $this;
291                         $uue /= $base;
292                         $this += $first;
293                         $first= 0;
294                         $cmpu .= chr($this + ($this < 26 ? ord('a') :
295                                               $this < 52 ? ord('A')-26
296                                                          : ord('0')-52));
297 print STDERR " uue=$uue this=$this cmpu=$cmpu\n";
298 die "$cmpu $uue ?" if length $cmpu > 20;
299                 } while ($uue);
300                 $cmpu;
301         } @uid;
302         $f->{UidShort}= $cmpu;
303
304         if ($qa->{'debug'}) {
305                 my @outuid;
306                 $_= $f->{UidShort};
307                 my $mul;
308                 while (m/./) {
309                         my $v= m/^[a-z]/ ? ord($&)-ord('a') :
310                                m/^[A-Z]/ ? ord($&)-ord('A')+26 :
311                                m/^[0-9]/ ? ord($&)-ord('0')+52 :
312                                die "$_ ?";
313                         if ($v >= $base) {
314                                 push @outuid, 0;
315                                 $v -= $base;
316                                 $mul= 1;
317 #print STDERR "(next)\n";
318                         }
319                         die "$f->{UidShort} $_ ?" unless defined $mul;
320                         $outuid[$#outuid] += $v * $mul;
321
322 #print STDERR "$f->{UidShort}  $_  $&  v=$v  mul=$mul  ord()=".ord($&).
323 #                       "[vs.".ord('a').",".ord('A').",".ord('0')."]".
324 #                       "  outuid=@outuid\n";
325
326                         $mul *= $base;
327                         s/^.//;
328                 }
329                 my $recons_long= join '_', @outuid;
330                 $f->{UidLong} eq $recons_long or
331                         die "$f->{UidLong} = $f->{UidShort} = $recons_long ?";
332         }
333
334         if (defined $qa->{"R$f->{UidShort}"} &&
335             !defined $qa->{"T$f->{UidShort}"}) {
336                 $f->{Suppress}= 1;
337         }
338
339 }
340 </%perl>
341
342 % my $optimise= $specific && !$confusing && @islandids>1;
343 % if (!$optimise) {
344
345 <p>
346 % if (@islandids<=1) {
347 Route is trivial.
348 % }
349 % if (!$specific) {
350 Route contains archipelago(es), not just specific islands.
351 % }
352 % if ($confusing) {
353 Route is complex - it visits the same island several times
354 and isn't a simple loop.
355 % }
356 Therefore, optimal trade pattern not calculated.
357
358 % } else { # ========== OPTMISATION ==========
359 <%perl>
360
361 my $cplex= "
362 Maximize
363
364   totalprofit:
365                   ".(join " +
366                   ", map {
367                         sprintf "%.20f %s", $_->{ExpectedUnitProfit}, $_->{Var}
368                         } @flows)."
369
370 Subject To
371 ";
372
373 my %avail_csts;
374 foreach my $flow (@flows) {
375         if ($flow->{Suppress}) {
376                 $cplex .= "
377    $flow->{Var} = 0
378 ";
379                 next;
380         }
381         foreach my $od (qw(org dst)) {
382                 my $cstname= join '_', (
383                         'avail',
384                         $flow->{'commodid'},
385                         $od,
386                         $flow->{"${od}_id"},
387                         $flow->{"${od}_price"},
388                         $flow->{"${od}_stallid"},
389                 );
390                         
391                 push @{ $avail_csts{$cstname}{Flows} }, $flow->{Var};
392                 $avail_csts{$cstname}{Qty}= $flow->{"${od}_qty_agg"};
393         }
394 }
395 foreach my $cstname (sort keys %avail_csts) {
396         my $c= $avail_csts{$cstname};
397         $cplex .= "
398    ".   sprintf("%-30s","$cstname:")." ".
399         join("+", @{ $c->{Flows} }).
400         " <= ".$c->{Qty}."\n";
401 }
402
403 $cplex.= "
404 Bounds
405         ".(join "
406         ", map { "$_->{Var} >= 0" } @flows)."
407
408 End
409 ";
410
411 if ($qa->{'debug'}) {
412 </%perl>
413 <pre>
414 <% $cplex |h %>
415 </pre>
416 <%perl>
417 }
418
419 {
420         my $input= pipethrough_prep();
421         print $input $cplex or die $!;
422         my $output= pipethrough_run_along($input, undef, 'glpsol',
423                 qw(glpsol --cpxlp /dev/stdin -o /dev/stdout));
424         print "<pre>\n" if $qa->{'debug'};
425         my $found_section= 0;
426         while (<$output>) {
427                 print encode_entities($_) if $qa->{'debug'};
428                 if (m/^\s*No\.\s+Column name\s+St\s+Activity\s/) {
429                         die if $found_section>0;
430                         $found_section= 1;
431                         next;
432                 }
433                 next unless $found_section==1;
434                 next if m/^[- ]+$/;
435                 if (!/\S/) {
436                         $found_section= 2;
437                         next;
438                 }
439                 my ($ix, $qty) =
440                         m/^\s*\d+\s+f(\d+)\s+\S+\s+(\d+)\s/ or die "$_ ?";
441                 my $flow= $flows[$ix] or die;
442                 $flow->{OptQty}= $qty;
443                 $flow->{OptProfit}= $flow->{'unitprofit'} * $qty;
444                 $flow->{OptCapital}= $flow->{OptQty} * $flow->{'org_price'};
445         }
446         print "</pre>\n" if $qa->{'debug'};
447         pipethrough_run_finish($output, 'glpsol');
448         die unless $found_section;
449 };
450
451 $addcols->({ DoReverse => 1 }, qw(
452                 OptQty
453         ));
454 $addcols->({ Total => 0, DoReverse => 1 }, qw(
455                 OptCapital OptProfit
456         ));
457
458 </%perl>
459
460 % } # ========== OPTIMISATION ==========
461
462 % my %ts_sortkeys;
463 % {
464 %       my $cdspan= $qa->{ShowStalls} ? ' colspan=2' : '';
465 %       my $cdstall= $qa->{ShowStalls} ? '<th>Stall</th>' : '';
466 <table id="trades" rules=groups>
467 <colgroup span=1>
468 <colgroup span=2>
469 <% $qa->{ShowStalls} ? '<colgroup span=2>' : '' %>
470 <colgroup span=1>
471 <colgroup span=2>
472 <colgroup span=2>
473 <colgroup span=2>
474 <colgroup span=3>
475 %       if ($optimise) {
476 <colgroup span=3>
477 %       }
478 <tr class="spong">
479 <th>
480 <th<% $cdspan %>>Collect
481 <th<% $cdspan %>>Deliver
482 <th>
483 <th colspan=2>Collect
484 <th colspan=2>Deliver
485 <th colspan=2>Profit
486 <th colspan=3>Max
487 %       if ($optimise) {
488 <th colspan=3>Planned
489 %       }
490
491 <tr>
492 <th>
493 <th>Island <% $cdstall %>
494 <th>Island <% $cdstall %>
495 <th>Commodity
496 <th>Price
497 <th>Qty
498 <th>Price
499 <th>Qty
500 <th>Margin
501 <th>Unit
502 <th>Qty
503 <th>Capital
504 <th>Profit
505 %       if ($optimise) {
506 <th>Qty
507 <th>Capital
508 <th>Profit
509 %       }
510 % }
511
512 <tr id="trades_sort">
513 % foreach my $col (@cols) {
514 <th>
515 % }
516
517 % foreach my $flowix (0..$#flows) {
518 %       my $flow= $flows[$flowix];
519 %       my $rowid= "id_row_$flow->{UidShort}";
520 <tr id="<% $rowid %>" class="datarow<% $flowix & 1 %>">
521 <td><input type=hidden   name=R<% $flow->{UidShort} %> value="">
522     <input type=checkbox name=T<% $flow->{UidShort} %> value=""
523        <% $flow->{Suppress} ? '' : 'checked' %> >
524 %       foreach my $ci (1..$#cols) {
525 %               my $col= $cols[$ci];
526 %               my $v= $flow->{$col->{Name}};
527 %               $col->{Total} += $v if defined $col->{Total};
528 %               $v='' if !$col->{Text} && !$v;
529 %               my $sortkey= $col->{SortColKey} ?
530 %                       $flow->{$col->{SortColKey}} : $v;
531 %               $ts_sortkeys{$ci}{$rowid}= $sortkey;
532 <td <% $col->{Text} ? '' : 'align=right' %>><% $v |h %>
533 %       }
534 % }
535 <tr id="trades_total">
536 <th>
537 <th colspan=2>Total
538 % foreach my $ci (3..$#cols) {
539 %       my $col= $cols[$ci];
540 <td align=right>
541 %       if (defined $col->{Total}) {
542 <% $col->{Total} |h %>
543 %       }
544 % }
545 </table>
546
547 <& tabsort, cols => \@cols, table => 'trades', rowclass => 'datarow',
548         throw => 'trades_sort', tbrow => 'trades_total' &>
549 <&| script &>
550   ts_sortkeys= <% to_json_protecttags(\%ts_sortkeys) %>;
551   function all_onload() {
552     ts_onload__trades();
553   }
554   window.onload= all_onload;
555 </&script>
556
557 <input type=submit name=update value="Update">
558
559 % if ($optimise) { # ========== TRADING PLAN ==========
560 %
561 % my $iquery= $dbh->prepare('SELECT islandname FROM islands
562 %                               WHERE islandid = ?');
563 % my %da_ages;
564 %
565 <h1>Voyage trading plan</h1>
566 <table rules=groups>
567 % foreach my $i (0..$#islandids) {
568 <tbody>
569 <tr><td colspan=3><strong>
570 %       $iquery->execute($islandids[$i]);
571 %       my ($islandname) = $iquery->fetchrow_array();
572 %       if (!$i) {
573 Start at <% $islandname |h %>
574 %       } else {
575 Sail to <% $islandname |h %>
576 %       }
577 </strong>
578 <%perl>
579      my $age_reported= 0;
580      my %flowlists;
581      foreach my $od (qw(org dst)) {
582         foreach my $f (@flows) {
583                 next if $f->{Suppress};
584                 next unless $f->{"${od}_id"} == $islandids[$i];
585                 next unless $f->{OptQty};
586                 my $price= $f->{"${od}_price"};
587                 my $stallname= $f->{"${od}_stallname"};
588                 my $todo= \$flowlists{$od}{
589                                 $f->{'commodname'},
590                                 (sprintf "%07d", ($od eq 'dst' ?
591                                                 9999999-$price : $price)),
592                                 $stallname
593                         };
594                 $$todo= {
595                         Qty => 0,
596                         orgArbitrage => 0,
597                         dstArbitrage => 0,
598                 } unless $$todo;
599                 $$todo->{'commodname'}= $f->{'commodname'};
600                 $$todo->{'stallname'}= $stallname;
601                 $$todo->{Price}= $price;
602                 $$todo->{Timestamp}= $f->{"${od}_timestamp"};
603                 $$todo->{Qty} += $f->{OptQty};
604                 $$todo->{Total}= $$todo->{Price} * $$todo->{Qty};
605                 $$todo->{Stalls}= $f->{"${od}Stalls"};
606                 if ($f->{'org_id'} == $f->{'dst_id'}) {
607                         $$todo->{"${od}Arbitrage"}= 1;
608                 }
609         }
610      }
611
612      my $total;
613      my $dline= 0;
614      my $show_flows= sub {
615         my ($od,$arbitrage,$collectdeliver) = @_;
616 </%perl>
617 %
618 %       my $todo= $flowlists{$od};
619 %       return unless $todo;
620 %       foreach my $tkey (sort keys %$todo) {
621 %               my $t= $todo->{$tkey};
622 %               next if $t->{"${od}Arbitrage"} != $arbitrage;
623 %               if (!$age_reported++) {
624 %                       my $age= $now - $t->{Timestamp};
625 %                       my $cellid= "da_${i}";
626 %                       $da_ages{$cellid}= $age;
627 <td colspan=3>\
628 (Data age: <span id="<% $cellid %>"><% prettyprint_age($age) %></span>)
629 %               } elsif (!defined $total) {
630 %                       $total= 0;
631 <tbody>
632 %               }
633 %               $total += $t->{Total};
634 %               my $span= 0 + keys %{ $t->{Stalls} };
635 %               my $td= "td rowspan=$span";
636 <tr class="datarow<% $dline %>">
637 <<% $td %>><% $collectdeliver %>
638 <<% $td %>><% $t->{'commodname'} |h %>
639 %
640 %               my @stalls= sort keys %{ $t->{Stalls} };
641 %               my $pstall= sub {
642 %                       my $name= $stalls[$_[0]];
643 <td><% $name |h %>
644 %               };
645 %
646 %               $pstall->(0);
647 <<% $td %> align=right><% $t->{Price} |h %> poe ea.
648 <<% $td %> align=right><% $t->{Qty} |h %> unit(s)
649 <<% $td %> align=right><% $t->{Total} |h %> total
650 %
651 %               foreach my $stallix (1..$#stalls) {
652 <tr class="datarow<% $dline %>">
653 %                       $pstall->($stallix);
654 %               }
655 %
656 %               $dline ^= 1;
657 %       }
658 %    };
659 %    my $show_total= sub {
660 %       my ($totaldesc)= @_;
661 %       if (defined $total) {
662 <tr>
663 <td colspan=3>
664 <td colspan=2 align=right><% $totaldesc %>
665 <td align=right><% $total |h %> total
666 %       }
667 %       $total= undef;
668 %       $dline= 0;
669 <%perl>
670      };
671
672      $show_flows->('dst',0,'Deliver');  $show_total->('Proceeds');
673      $show_flows->('org',1,'Collect');  $show_total->('(Arbitrage) outlay');
674      $show_flows->('dst',1,'Deliver');  $show_total->('(Arbitrage) proceeds');
675      $show_flows->('org',0,'Collect');  $show_total->('Outlay');
676
677 }
678 </%perl>
679 </table>
680 <& query_age:dataages, id2age => \%da_ages &>
681 %
682 % } # ========== TRADING PLAN ==========
683
684 <%init>
685 use CommodsWeb;
686 use Commods;
687 </%init>