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 16:37 <ceb> if tehre are 2 rows which take the same object and sell it for the
  39             same profit at two other islands, choose the shortest route as the
  40             preferred one
  41 16:37 <ceb> coconut buy 10 sell 16, at luthien or jorvik, in that example
  42 16:38 <ceb> Do you see what I mean?
  43
  44 16:38 <ceb> I don't know how hard this is, but can you show only the suggested
  45             trades to start ith and have a button to show all?
  46 16:39 <ceb> Also, maybe colour to highlight the suggested trades?
  47
  48 16:40 <ceb> can it give a total investment/profit for the suggested trades?
  49 16:40 <ceb> columns should be sortable with the small arrows as before
  50
  51 16:46 <Diziet> Oh the unticking has become broken.
  52
  53 16:51 <ceb> YPP interfaces have price then qty. You have qty then price. This
  54             is confusing!
  55 16:51 <ceb> the max column ordering is OK
  56 16:51 <ceb> (alo profit and suggested are OK)
  57 16:52 <Diziet> Err, you want qty on the left in those two but on the right in
  58                collect and deliver ?
  59 16:53 <ceb> Yes (price and capital are not the same thing)
  60 16:53 <Diziet> OK
  61 16:53 <ceb> for max the order in which you want to think about it is 'I need to
  62             buy ten of them and that will cost me $total price)
  63 16:54 <ceb> s/)/'/
  64
  65 16:46 <ceb> Also trading plan not functional but I guess you know that :-)
  66
  67 Also:
  68 - potential cost of losses
  69 - max volume/mass
  70
  71 ========== TODO ==========
  72
  73 </%doc>
  74 <%args>
  75 $dbh
  76 @islandids
  77 @archipelagoes
  78 $qa
  79 </%args>
  80 <%perl>
  81
  82 my @flow_conds;
  83 my @query_params;
  84
  85 my $sd_condition= sub {
  86         my ($bs, $ix) = @_;
  87         my $islandid= $islandids[$ix];
  88         if (defined $islandid) {
  89                 return "${bs}.islandid = $islandid";
  90         } else {
  91                 push @query_params, $archipelagoes[$ix];
  92                 return "${bs}_islands.archipelago = ?";
  93         }
  94 };
  95
  96 my %islandpair;
  97 # $islandpair{$a,$b}= [ $start_island_ix, $end_island_ix ]
  98
  99 my $specific= !grep { !defined $_ } @islandids;
 100 my $confusing= 0;
 101
 102 foreach my $src_i (0..$#islandids) {
 103         my $src_isle= $islandids[$src_i];
 104         my $src_cond= $sd_condition->('sell',$src_i);
 105         my @dst_conds;
 106         foreach my $dst_i ($src_i..$#islandids) {
 107                 my $dst_isle= $islandids[$dst_i];
 108                 my $dst_cond= $sd_condition->('buy',$dst_i);
 109                 if ($dst_i==$src_i and !defined $src_isle) {
 110                         # we always want arbitrage, but mentioning an arch
 111                         # once shouldn't produce intra-arch trades
 112                         $dst_cond=
 113                                 "($dst_cond AND sell.islandid = buy.islandid)";
 114                 }
 115                 push @dst_conds, $dst_cond;
 116
 117                 if ($specific && !$confusing &&
 118                     # With a circular route, do not carry goods round the loop
 119                     !($src_i==0 && $dst_i==$#islandids &&
 120                       $src_isle == $islandids[$dst_i])) {
 121                         if ($islandpair{$src_isle,$dst_isle}) {
 122                                 $confusing= 1;
 123                         } else {
 124                                 $islandpair{$src_isle,$dst_isle}=
 125                                         [ $src_i, $dst_i ];
 126                         }
 127                 }
 128         }
 129         push @flow_conds, "$src_cond AND (
 130                         ".join("
 131                      OR ",@dst_conds)."
 132                 )";
 133 }
 134
 135 my $stmt= "
 136         SELECT  sell_islands.islandname                         org_name,
 137                 sell_islands.islandid                           org_id,
 138                 sell.price                                      org_price,
 139                 buy_islands.islandname                          dst_name,
 140                 buy_islands.islandid                            dst_id,
 141                 buy.price                                       dst_price,
 142 ".($qa->{ShowStalls} ? "
 143                 sell.stallid                                    org_stallid,
 144                 sell_stalls.stallname                           org_stallname,
 145                 sell.qty                                        org_qty,
 146                 buy.stallid                                     dst_stallid,
 147                 buy_stalls.stallname                            dst_stallname,
 148                 buy.qty                                         dst_qty,
 149 " : "
 150                 sum(sell.qty)                                   org_qty,
 151                 sum(buy.qty)                                    dst_qty,
 152 ")."
 153                 commods.commodname                              commodname,
 154                 commods.commodid                                commodid,
 155                 commods.unitmass                                unitmass,
 156                 commods.unitvolume                              unitvolume,
 157                 buy.price - sell.price                          unitprofit
 158         FROM commods
 159         JOIN buy  on commods.commodid = buy.commodid
 160         JOIN sell on commods.commodid = sell.commodid
 161         JOIN islands as sell_islands on sell.islandid = sell_islands.islandid
 162         JOIN islands as buy_islands  on buy.islandid  = buy_islands.islandid
 163 ".($qa->{ShowStalls} ? "
 164         JOIN stalls  as sell_stalls  on sell.stallid  = sell_stalls.stallid
 165         JOIN stalls  as buy_stalls   on buy.stallid   = buy_stalls.stallid
 166 " : "")."
 167         WHERE   (
 168                 ".join("
 169            OR   ", @flow_conds)."
 170         )
 171           AND   buy.price > sell.price
 172 ".($qa->{ShowStalls} ? "" : "
 173         GROUP BY commods.commodid, org_id, org_price, dst_id, dst_price
 174 ")."
 175         ORDER BY org_name, dst_name, commodname, unitprofit DESC,
 176                  org_price, dst_price DESC
 177      ";
 178
 179 my $sth= $dbh->prepare($stmt);
 180 $sth->execute(@query_params);
 181 my @flows;
 182
 183 my @cols;
 184
 185 my $addcols= sub {
 186         my $base= shift @_;
 187         foreach my $name (@_) {
 188                 push @cols, { Name => $name, %$base };
 189         }
 190 };
 191
 192 if ($qa->{ShowStalls}) {
 193         $addcols->({ Text => 1 }, qw(
 194                 org_name org_stallname
 195                 dst_name dst_stallname
 196         ));
 197 } else {
 198         $addcols->({Text => 1 }, qw(
 199                 org_name dst_name
 200         ));
 201 }
 202 $addcols->({ Text => 1 }, qw(commodname));
 203 $addcols->({},
 204         qw(     org_qty org_price dst_qty dst_price
 205                 Margin unitprofit MaxQty
 206                 MaxCapital MaxProfit
 207         ));
 208
 209 </%perl>
 210
 211 % if ($qa->{'debug'}) {
 212 <pre>
 213 <% $stmt |h %>
 214 <% join(' | ',@query_params) |h %>
 215 </pre>
 216 % }
 217
 218 <& dumptable:start, qa => $qa, sth => $sth &>
 219 % {
 220 %   my $f;
 221 %   while ($f= $sth->fetchrow_hashref()) {
 222 <%perl>
 223
 224         $f->{Ix}= @flows;
 225         $f->{Var}= "f$f->{Ix}";
 226
 227         $f->{MaxQty}= $f->{'org_qty'} < $f->{'dst_qty'}
 228                 ? $f->{'org_qty'} : $f->{'dst_qty'};
 229         $f->{MaxProfit}= $f->{MaxQty} * $f->{'unitprofit'};
 230         $f->{MaxCapital}= $f->{MaxQty} * $f->{'org_price'};
 231
 232         $f->{Margin}= sprintf "%3.1f%%",
 233                 $f->{'dst_price'} * 100.0 / $f->{'org_price'} - 100.0;
 234
 235         $f->{"org_stallid"}= $f->{"dst_stallid"}= 'all'
 236                 if !$qa->{ShowStalls};
 237
 238         my @uid= $f->{commodid};
 239         foreach my $od (qw(org dst)) {
 240                 push @uid,
 241                         $f->{"${od}_id"},
 242                         $f->{"${od}_price"};
 243                 push @uid,
 244                         $f->{"${od}_stallid"}
 245                                 if $qa->{ShowStalls};
 246         }
 247         $f->{UidLong}= join '_', @uid;
 248
 249         my $base= 31;
 250         my $cmpu= '';
 251         map {
 252                 my $uue= $_;
 253                 my $first= $base;
 254                 do {
 255                         my $this= $uue % $base;
 256 print STDERR "uue=$uue this=$this ";
 257                         $uue -= $this;
 258                         $uue /= $base;
 259                         $this += $first;
 260                         $first= 0;
 261                         $cmpu .= chr($this + ($this < 26 ? ord('a') :
 262                                               $this < 52 ? ord('A')-26
 263                                                          : ord('0')-52));
 264 print STDERR " uue=$uue this=$this cmpu=$cmpu\n";
 265 die "$cmpu $uue ?" if length $cmpu > 20;
 266                 } while ($uue);
 267                 $cmpu;
 268         } @uid;
 269         $f->{UidShort}= $cmpu;
 270
 271         if ($qa->{'debug'}) {
 272                 my @outuid;
 273                 $_= $f->{UidShort};
 274                 my $mul;
 275                 while (m/./) {
 276                         my $v= m/^[a-z]/ ? ord($&)-ord('a') :
 277                                m/^[A-Z]/ ? ord($&)-ord('A')+26 :
 278                                m/^[0-9]/ ? ord($&)-ord('0')+52 :
 279                                die "$_ ?";
 280                         if ($v >= $base) {
 281                                 push @outuid, 0;
 282                                 $v -= $base;
 283                                 $mul= 1;
 284 #print STDERR "(next)\n";
 285                         }
 286                         die "$f->{UidShort} $_ ?" unless defined $mul;
 287                         $outuid[$#outuid] += $v * $mul;
 288
 289 #print STDERR "$f->{UidShort}  $_  $&  v=$v  mul=$mul  ord()=".ord($&).
 290 #                       "[vs.".ord('a').",".ord('A').",".ord('0')."]".
 291 #                       "  outuid=@outuid\n";
 292
 293                         $mul *= $base;
 294                         s/^.//;
 295                 }
 296                 my $recons_long= join '_', @outuid;
 297                 $f->{UidLong} eq $recons_long or
 298                         die "$f->{UidLong} = $f->{UidShort} = $recons_long ?";
 299         }
 300
 301         if ($qa->{"R$f->{UidShort}"} && !$qa->{"T$f->{UidShort}"}) {
 302                 $f->{Suppress}= 1;
 303         }
 304
 305         push @flows, $f;
 306
 307 </%perl>
 308 <& dumptable:row, qa => $qa, sth => $sth, row => $f &>
 309 %   }
 310 <& dumptable:end, qa => $qa &>
 311 % }
 312
 313 % my $optimise= $specific && !$confusing && @islandids>1;
 314 % if (!$optimise) {
 315
 316 <p>
 317 % if (@islandids<=1) {
 318 Route is trivial.
 319 % }
 320 % if (!$specific) {
 321 Route contains archipelago(es), not just specific islands.
 322 % }
 323 % if ($confusing) {
 324 Route is complex - it visits the same island several times
 325 and isn't a simple loop.
 326 % }
 327 Therefore, optimal trade pattern not calculated.
 328
 329 % } else { # ========== OPTMISATION ==========
 330 <%perl>
 331
 332 my $cplex= "
 333 Maximize
 334
 335   totalprofit:
 336                   ".(join " +
 337                   ", map { "$_->{unitprofit} $_->{Var}" } @flows)."
 338
 339 Subject To
 340 ";
 341
 342 my %avail_csts;
 343 foreach my $flow (@flows) {
 344         if ($flow->{Suppress}) {
 345                 $cplex .= "
 346    $flow->{Var} = 0
 347 ";
 348                 next;
 349         }
 350         foreach my $od (qw(org dst)) {
 351                 my $cstname= join '_', (
 352                         'avail',
 353                         $flow->{'commodid'},
 354                         $od,
 355                         $flow->{"${od}_id"},
 356                         $flow->{"${od}_price"},
 357                         $flow->{"${od}_stallid"},
 358                 );
 359
 360                 push @{ $avail_csts{$cstname}{Flows} }, $flow->{Var};
 361                 $avail_csts{$cstname}{Qty}= $flow->{"${od}_qty"};
 362         }
 363 }
 364 foreach my $cstname (sort keys %avail_csts) {
 365         my $c= $avail_csts{$cstname};
 366         $cplex .= "
 367    ".   sprintf("%-30s","$cstname:")." ".
 368         join("+", @{ $c->{Flows} }).
 369         " <= ".$c->{Qty}."\n";
 370 }
 371
 372 $cplex.= "
 373 Bounds
 374         ".(join "
 375         ", map { "$_->{Var} >= 0" } @flows)."
 376
 377 End
 378 ";
 379
 380 if ($qa->{'debug'}) {
 381 </%perl>
 382 <pre>
 383 <% $cplex |h %>
 384 </pre>
 385 <%perl>
 386 }
 387
 388 {
 389         my $input= pipethrough_prep();
 390         print $input $cplex or die $!;
 391         my $output= pipethrough_run_along($input, undef, 'glpsol',
 392                 qw(glpsol --cpxlp /dev/stdin -o /dev/stdout));
 393         print "<pre>\n" if $qa->{'debug'};
 394         my $found_section= 0;
 395         while (<$output>) {
 396                 print encode_entities($_) if $qa->{'debug'};
 397                 if (m/^\s*No\.\s+Column name\s+St\s+Activity\s/) {
 398                         die if $found_section>0;
 399                         $found_section= 1;
 400                         next;
 401                 }
 402                 next unless $found_section==1;
 403                 next if m/^[- ]+$/;
 404                 if (!/\S/) {
 405                         $found_section= 2;
 406                         next;
 407                 }
 408                 my ($ix, $qty) =
 409                         m/^\s*\d+\s+f(\d+)\s+\S+\s+(\d+)\s/ or die "$_ ?";
 410                 my $flow= $flows[$ix] or die;
 411                 $flow->{OptQty}= $qty;
 412                 $flow->{OptProfit}= $flow->{'unitprofit'} * $qty;
 413                 $flow->{OptCapital}= $flow->{OptQty} * $flow->{'org_price'};
 414         }
 415         print "</pre>\n" if $qa->{'debug'};
 416         pipethrough_run_finish($output, 'glpsol');
 417         die unless $found_section;
 418 };
 419
 420 $addcols->({}, qw(
 421                 OptQty
 422         ));
 423 $addcols->({ Total => 0 }, qw(
 424                 OptCapital OptProfit
 425         ));
 426
 427 </%perl>
 428
 429 % } # ========== OPTIMISATION ==========
 430
 431 % {
 432 %       my $cdspan= $qa->{ShowStalls} ? ' colspan=2' : '';
 433 %       my $cdstall= $qa->{ShowStalls} ? '<th>Stall</th>' : '';
 434 <table rules=groups>
 435 <colgroup span=1>
 436 <colgroup span=2>
 437 <% $qa->{ShowStalls} ? '<colgroup span=2>' : '' %>
 438 <colgroup span=1>
 439 <colgroup span=2>
 440 <colgroup span=2>
 441 <colgroup span=2>
 442 <colgroup span=3>
 443 %       if ($optimise) {
 444 <colgroup span=3>
 445 %       }
 446 <tr>
 447 <th>
 448 <th<% $cdspan %>>Collect
 449 <th<% $cdspan %>>Deliver
 450 <th>
 451 <th colspan=2>Collect
 452 <th colspan=2>Deliver
 453 <th colspan=2>Profit
 454 <th colspan=3>Max
 455 %       if ($optimise) {
 456 <th colspan=3>Suggested
 457 %       }
 458
 459 <tr>
 460 <th>
 461 <th>Island <% $cdstall %>
 462 <th>Island <% $cdstall %>
 463 <th>Commodity
 464 <th>Qty
 465 <th>Price
 466 <th>Qty
 467 <th>Price
 468 <th>Margin
 469 <th>Unit
 470 <th>Qty
 471 <th>Capital
 472 <th>Profit
 473 %       if ($optimise) {
 474 <th>Qty
 475 <th>Capital
 476 <th>Profit
 477 %       }
 478 % }
 479
 480 % foreach my $flow (@flows) {
 481 <tr>
 482 <td><input type=hidden   name=R<% $flow->{UidShort} %> value="">
 483     <input type=checkbox name=T<% $flow->{UidShort} %> value=""
 484        <% $flow->{Suppress} ? '' : 'checked' %> >
 485 %       foreach my $ci (0..$#cols) {
 486 %               my $col= $cols[$ci];
 487 %               my $v= $flow->{$col->{Name}};
 488 %               $col->{Total} += $v if defined $col->{Total};
 489 %               $v='' if !$col->{Text} && !$v;
 490 <td <% $col->{Text} ? '' : 'align=right' %>><% $v |h %>
 491 %       }
 492 % }
 493 <tr>
 494 <th>
 495 <th colspan=2>Total
 496 % foreach my $ci (2..$#cols) {
 497 %       my $col= $cols[$ci];
 498 <td align=right>
 499 %       if (defined $col->{Total}) {
 500 <% $col->{Total} |h %>
 501 %       }
 502 % }
 503 </table>
 504
 505 <input type=submit name=update value="Update">
 506
 507 % if ($optimise) { # ========== TRADING PLAN ==========
 508 %
 509 % my $iquery= $dbh->prepare('SELECT islandname FROM islands
 510 %                               WHERE islandid = ?');
 511 %
 512 <h1>Voyage trading plan</h1>
 513 <table>
 514 % foreach my $i (0..$#islandids) {
 515 <tr><td colspan=4><strong>
 516 %       $iquery->execute($islandids[$i]);
 517 %       my ($islandname) = $iquery->fetchrow_array();
 518 %       if (!$i) {
 519 Start at <% $islandname |h %>
 520 %       } else {
 521 Sail to <% $islandname |h %>
 522 %       }
 523 </strong>
 524 %    foreach my $od (qw(dst org)) {
 525 %       my $sign= $od eq 'dst' ? -1 : +1;
 526 %       foreach my $f (sort {
 527 %                       $a->{'commodname'} cmp $b->{'commodname'}
 528 %               or $sign * ($a->{"${od}_price"} <=> $b->{"${od}_price"})
 529 %               or      $a->{"${od}_stallname"} cmp $b->{"${od}_stallname"}
 530 %               } @flows) {
 531 %               next if $f->{Suppress};
 532 %               next unless $f->{"${od}_id"} == $islandids[$i];
 533 %               next unless $f->{OptQty};
 534 <tr>Buy or sell flow
 535 %       }
 536 %    }
 537 % }
 538 </table>
 539 %
 540 % } # ========== TRADING PLAN ==========
 541
 542 <%init>
 543 use CommodsWeb;
 544 use Commods;
 545 </%init>