# Question
Title: Given r and n, find first n numbers of x where moving first digit of x to last gives x/r = y
## Objective

Given input `r` and `n` find the first `n` natural numbers `x` such that if we rotate the first digit to the last place we obtain `x/r`.

You may assume that `2 <= r <= 9` and `1 <= n <= 65535`.

You may write a program which takes input from stdin or command-line arguments; or you may write a function which takes `r` and `n` as parameters. Output, however, should be to stdout. Output should be one line per value of `x`, formatted as `x/r=y`, in order of increasing `x`.

Your solution must be able to handle all valid cases within one minute on a reasonable desktop computer.

### Test cases

Input: `4 5`
Output:

```
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205

```

Input: `5 1`
Output: `714285/5=142857`

This is code-golf, so least bytes win. Winning answer will be accepted 4 weeks from now (2014-09-19).

Credits for this question go to my colleague, who allowed me to post this question here :)

# Answer
> 7 votes
# Haskell, ~~182~~ 179

Second version, probably further golfable, but with "proper" algorithm this time. In particular, it finishes within a few minutes with `r=4` and `n=65535`, but then again my computer is neither reasonable nor a desktop, so chances are this stays within a minute on other machines.

```
n#r=take n$[s(10^k*a+d)++'/':s r++'=':s d++s a|k<-[0..],a<-[1..9],let(d,m)=divMod(a*(10^k-r))(10*r-1),m<1]
s=show
main=interact$unlines.(\(r:n:_)->n#fromIntegral r).map read.words

```

It is based on the idea that `x=10^k*a + m`, where its first digit `0≤a≤9` is moved to the end to obtain `y=10*m+a`. A little maths reveals that `m` can be obtained as `a*(10^k-r)/(10*r-1)`, so we simply scan `a` over `[1..9]` for every `k` from 0 to infinity, and keep and print the first `n` results for which the above expression for `m` is integral.

The `fromIntegral` is required because `read`ing a list with `n` as one of its elements in `main`, in combination with the use of `n` in `take`, would force `r` to `Int` throughout, which results in nasty overflows with the big numbers in question. I could have used `genericTake`, but that requires an `import`.

This code also has the benefit of being almost trivial to expand to bases other than 10.

Input is read from `stdin`, the two values can be separated by any whitespace.

# Answer
> 2 votes
# C 468

```
#include <stdlib.h>
#include <stdio.h>
#define a(s)fputs(s,stdout);
#define b(c)putchar(c);
int r;int z(char*s,int m){for(int i=0;i++<=m;)a(s)b(47)b(r+48)b(61)char*t=s;
while(*++t==48);a(t)while(m--)a(s)b(*s)b(10)}char x[10][60];
int main(int c,char**v){r=atoi(v[1]);int n=atoi(v[2]),q=10*r-1,d=0,p;
while(d++<9){p=r*d;char*y=x[d];do{p*=10;*y++=p/q+48;p%=q;}while(p!=r*d);}
d=1;p=q=0;while(n--){r==5&p<6?z(x[7],7*q+p++):(z(x[d],(r==5&d==7)?7*q+6:q),
++d>9?q+=d=1,p=0:0);}}

```

(Some newlines not counted in the byte count have been added above to eliminate scroll bars. Yes, the final newline is counted.)

Expects arguments on the command line, and assumes standard output accepts ASCII. Runtime is O(number of bytes output) = O(n\*n).

No, I can't use `printf`. That takes too much time and pushes the program over the minute limit on my desktop. As it is, some test cases take about 30 seconds.

The algorithm treats the output as strings, not numbers, since they quickly get enormous, and there are strong patterns in the output.

Somewhat ungolfed:

```
#include <stdlib.h>
#include <stdio.h>

/* r is as in the problem description */
int r;

void show_line(const char* num, int repeats) {
    for (int i=0; i <= repeats; ++i)
        fputs(num, stdout);
    printf("/%c=", '0'+r);

    /* Assume the repeated num is a solution. Just move the first
       digit and skip any resulting leading zeros. */
    const char* num_tail = num;
    ++num_tail;
    while (*num_tail=='0')
        ++num_tail;
    fputs(num_tail, stdout);
    while (repeats--)
        fputs(num, stdout);
    printf("%c\n", *num);
}

/* sol[0] is unused. Otherwise, sol[d] is the repeating digits in the
   decimal representation of (r*d)/(10*r-1). */
char sol[10][60];

int main(int argc, char** argv) {
    r = atoi(argv[1]);
    int n = atoi(argv[2]);
    int q = 10*r-1;
    int d = 0;

    /* Populate the strings in sol[]. */
    while (d++<9) {
        int p = r*d;
        char* sol_str = sol[d];

        /* Do the long division p/q in decimal, stopping when the remainder
           is the original dividend. The integer part is always zero. */
        do {
            p *= 10;
            *sol_str++ = p/q + '0';
            p %= q;
        } while (p != r*d);
    }

    /* Output the answers. */
    d = 1;
    int repeats = 0;
    int r5x7_repeats = 0;
    while (n--) {
        if (r==5 && r5x7_repeats<6) {
            show_line(x[7], 7*repeats + r5x7_repeats);
        } else {
            if (r==5 && d==7)
                show_line(x[d], 7*repeats + 6);
            else
                show_line(x[d], repeats);
            if (++d > 9) {
                d = 1;
                ++repeats;
                r5x7_repeats = 0;
            }
        }
    }
}

```

### Proof

that the program solves the problem:

(In the proof, take all operators and functions to be the real mathematical functions, not the computer operations that approximate them. `^` denotes exponentiation, not bitwise xor.)

For clarity, I'll use a function `ToDec` to describe the ordinary process of writing a number as a sequence of decimal digits. Its range is the set of ordered tuples on `{0...9}`. For example,

```
ToDec(2014) = (2, 0, 1, 4).

```

For a positive integer `n`, define `L(n)` to be the number of digits in the decimal representation of `n`; or,

```
L(n) = 1+floor(log10(n)).

```

For a positive integer `k` and a non-negative integer `n` with `L(n)<k`, define `Rep_k(n)` to be the real number obtained by adding zeros in front of the decimal digits of `n`, if necessary to get `k` digits total, and then infinitely repeating those `k` digits after the decimal point. E.g.

```
Rep_4(2014) = .201420142014...
Rep_5(2014) = .020140201402...

```

Multiplying `Rep_k(n) * 10^k` gives the digits of `n` before the decimal point, and the (zero-padded) digits of `n` infinitely repeated after the decimal point. So

```
Rep_k(n) * 10^k = n + Rep_k(n)
Rep_k(n) = n / (10^k - 1)

```

Given a positive integer `r`, suppose `x` is a solution to the problem, and

```
ToDec(x) = ( x_1, x_2, ..., x_k )

```

where `x_1 != 0` and `k = L(x)`.

To be a solution, `x` is a multiple of `r`, and

```
ToDec(x/r) : ( x_2, x_3, ..., x_k, x_1 ).

```

Applying the `Rep_k` function gives a nice equation:

```
10*Rep_k(x) = x_1 + Rep_k(x/r)

```

Using its closed form from above,

```
10x / (10^k - 1) = x_1 + x / r / (10^k - 1)
x = x_1 * r * (10^k-1) / (10r - 1)

```

`x_1` must be in the set `{1 ... 9}`. `r` was specified to be in the set `{2 ... 9}`. Now the only question is, for what values of `k` does the above formula for `x` give a positive integer? We'll consider each possible value of `r` individually.

When `r` = 2, 3, 6, 8, or 9, `10r-1` is 19, 29, 59, 79, or 89, respectively. In all cases, the denominator `p = 10r-1` is prime. In the numerator, only `10^k-1` can be a multiple of `p`, which happens when

```
10^k = 1 (mod p)

```

The set of solutions is closed under addition and under subtraction that does not result in a negative number. So the set comprises all the multiples of some common factor, which is also the least positive solution for `k`.

When `r = 4` and `10r-1 = 39`; or when `r = 7` and `10r-1 = 69`, the denominator is 3 times a different prime `p=(10r-1)/3`. `10^k-1` is always a multiple of 3, and again no other factor in the numerator can be a multiple of `p`, so again the problem reduces to

```
10^k = 1 (mod p)

```

and again the solutions are all the multiples of the least positive solution for `k`.

\[Not finished...\]

# Answer
> 0 votes
# Python 3 - ~~223~~ 179 bytes

Python implementation of TheSpanishInquisition's solution:

```
r,n=map(int,input().split());k=0
while 1:
 for a in range(1,10):
  D,M=divmod(a*(10**k-r),10*r-1)
  if M==0:
   print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
   if n==0:exit()
 k+=1

```

Run:

* `python3 <whatever you named it>.py`
* Takes input on stdin
* Input space separated

Output:

```
$python3 <whatever you named it>.py
4 8
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
615384/4=153846
717948/4=179487
820512/4=205128

```

Findings:

https://oeis.org/A092697 is the first value for each r.

It seems that only certain values of k produce answers, and that the interval is regular. E.g. for r = 4:

```
Form: k [a, a, ...]
0 []
1 []
2 []
3 []
4 []
5 [1, 2, 3, 4, 5, 6, 7, 8, 9]
6 []
7 []
8 []
9 []
10 []
11 [1, 2, 3, 4, 5, 6, 7, 8, 9]
12 []
13 []
14 []
15 []
16 []
17 [1, 2, 3, 4, 5, 6, 7, 8, 9]
18 []
19 []
20 []
21 []
22 []
23 [1, 2, 3, 4, 5, 6, 7, 8, 9]

```

The intervals are:

* 2 = 18
* 3 = 28
* 4 = 6
* 5 = 6 (5 seems to be an anomaly, as for most values of r, there are clumps of 9, 5 forms clumps of 9 and 1 (with only a = 7 working), see below)
* 6 = 58
* 7 = 22
* 8 = 13
* 9 = 44

This forms https://oeis.org/A094224.

Using these values, a more efficient version can be built:

```
import math

def A094224(n):
    return [18,28,6,6,58,22,13,44][n-2]

r,n=map(int,input().split());k=A094224(r)-1
H={}
while 1:
    for a in range(1,10):
        D,M=divmod(a*10**k-a*r,10*r-1)
        if M==0:
            print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
            if n==0:exit()
    k+=A094224(r)

```

However, I can't (yet) prove that this continues mathematically.

Results for r = 5:

```
0 []
1 []
2 []
3 []
4 []
5 [7]
6 []
7 []
8 []
9 []
10 []
11 [7]
12 []
13 []
14 []
15 []
16 []
17 [7]
18 []
19 []
20 []
21 []
22 []
23 [7]
24 []
25 []
26 []
27 []
28 []
29 [7]
30 []
31 []
32 []
33 []
34 []
35 [7]
36 []
37 []
38 []
39 []
40 []
41 [1, 2, 3, 4, 5, 6, 7, 8, 9]

```

---
Tags: code-golf, math, number-theory, restricted-time
---


# Question
Title: Swing Through Trees with Your Grappling Hook
You have found the path through the forest and now plan on travelling along it. However, just before you start on your journey, the ground turns into lava.

You manage to scurry up the nearest tree (the trees have inexplicably not burnt up), but now you are faced with a problem: how can you get out of the forest when the floor is lava? The answer hits you like a good idea for a programming challenge - you can use your magical grappling hook (made from a piece of the canoe earlier) to swing through the trees and the branches!

However, you're not sure *which* trees and branches you need to swing on to get there. Luckily, you have your programming skills, so you decide to draw a program on your arm to tell you which trees to swing on. However, there is not much surface area on your arm, so you must make the program as small as possible.

We can represent a forest using a `n` by `m` array. The following characters will make up the array:

* `T`: A tree. You can land here. You cannot use your grappling hook on this. You can swing through this.
* `P`: Functions the same as `T`. You start here.
* `Q`: Functions the same as `T`. This is the goal.
* `+`: A branch. You cannot land here. You can use your grappling hook on this. You can swing through this.
* `*`: A man-eating spider. If you land here, you die. If you use your grappling hook on this, you die. If you swing through this, you die.
* `-`: Regular ground, in other words, lava. You cannot land here. You cannot use your grappling hook on this. You can swing through this. All area outside of the given array is this type.

Here is an example of what a forest might look like:

```
               y
----T---+------12
---------------11
----T---+---T--10
---------------9
T-+-T-+-T------8
---------------7
------------+--6
----+----------5
+-------+------4
---------------3
----P---+-*-Q--2
---------------1
T-+-T-+-T------0
012345678911111
x         01234

```

I will refer to coordinates with the notation `(x,y)`, as shown on the axes.

You begin from `P` and have to make your way to `Q`. To do this, you swing from tree `T` to tree `T` using branches `+`. You can attach your grappling hook on any branch that is orthogonal to you - that is, a branch that is either on the same x position or y position that you are in. For instance, if you were at the position `(4,8)` in the example forest, you could attach your grappling hook to the positions `(2,8)`, `(6,8)`, or `(4,5)`. You can attach this even if there are trees or other branches between you and the branch.

Once you attach your grappling hook onto a branch, you will travel a distance in the direction of the branch equal to twice the distance between your initial position and the branch. In other words, your final position will be the same distance from the branch as your starting position, just on the opposite side. A more formal definition of how the movement works is below. A subscript of `v` is the final position, `u` is the initial position, and `b` is the position of the branch.

$$(x\_v, y\_v) = (2x\_b-x\_u, 2y\_b-y\_u)$$

Note that if there is a spider between your initial position and your final position, you cannot go there. For example, in the example forest the swing from `(4,2)` to `(12,2)` is not possible because you would run into the spider at `(10,2)`.

The goal is, using this swinging through branches method, to travel from the point `P` to the point `Q` in the *fewest* swings possible. For instance, in the example forest, the shortest path is:

1. From `(4,2)` to `(4,8)` using `(4,5)`
2. From `(4,8)` to `(0,8)` using `(2,8)`
3. From `(0,8)` to `(0,0)` using `(0,4)`
4. From `(0,0)` to `(4,0)` using `(2,0)`
5. From `(4,0)` to `(4,10)` using `(4,5)`
6. From `(4,10)` to `(12,10)` using `(8,10)`
7. From `(12,10)` to `(12,2)` using `(12,6)`

***Input***

Input is from whichever method is convenient (STDIN, command line arguments, `raw_input()`, etc.), except it may not be pre-initialized as a variable. Input starts with two comma separated integers `n` and `m` representing the size of the board, then a space, and then the forest as a single long string. For instance, the example forest as an input would look like this:

```
15,13 ----T---+-------------------------T---+---T-----------------T-+-T-+-T---------------------------------+------+----------+-------+-------------------------P---+-*-Q-----------------T-+-T-+-T------

```

***Output***

Output a space-separated list of comma separated tuples indicating the coordinates of the branches that you must swing to. For instance, for the above input the output would be:

```
4,5 2,8 0,4 2,0 4,5 8,10 12,6

```

You may have noticed that this is not the only shortest path through the forest - indeed, going to `(8,8)`, down to `(8,0)`, left to `(4,0)` and continuing as normal from there takes exactly the same number of swings. In these cases, your program may output *either* of the shortest paths. So the output:

```
4,5 6,8 8,4 6,0 4,5 8,10 12,6

```

is also allowed. This is , so the entry with the shortest number of bytes wins. If you have questions or my explanation is not clear, ask in the comments.

# Answer
### GolfScript, 196 characters

```
' '/(~):H;,):W(\~/-1%'*':S*:^{:I,,{I=79>},:A{{[\1$1$+2/]}+A/}%{)I=43=\$.~I<>S&!\~+1&!&&},}:C~S^W/zip*C{{.H/\H%W*+}%}%+:B;^'P'?]]{{(B{0=1$=},\;\`{\1>\+}+/}%.{0=^=81=},:|!}do;|0=1>-1%{.W%','@W/' '}/

```

A horrible piece of GolfScript code - however it works as desired. The algorithm is not optimal but fairly fast, the example is running well below a second on my computer.

```
> 15,13 ----T---+-------------------------T---+---T-----------------T-+-T-+-T---------------------------------+------+----------+-------+-------------------------P---+-*-Q-----------------T-+-T-+-T------
4,5 2,8 0,4 2,0 4,5 8,10 12,6

```
> 4 votes

---
Tags: code-golf, graph-theory
---


title: Traders to the Death

text:
# Question
Title: Traders to the Death
You are a foreign trader, hoping to make a profit. There are 5 goods people wish to trade: `A`pricots, `B`oars, `C`anaries, `D`affodils, and `E`arwigs. Starting in the winter, you need to decide what to produce. Then, in the fall, you travel and spend your days trading for a profit.

## Gameplay

You start the game with 10 of each product in storage. Each year, you will consume 2 of each product.

At the beginning of the game, you receive a list of 5 products, along with the amount you will be able to produce each year (ex:`5-A,6-B,3-C,12-D,4-E`). You then will return a letter A through E deciding what to produce.

Then, in the fall time you will bring your products (including those in storage) to the market. You have 50 turns to trade.

You must decide if you want to `P`urchase, `S`ell, or `L`eave the market. The buyers will then be paired up randomly with the sellers. If a group has extra, the random extras will miss out this turn. If a trader is skipped, they will receive `S`, otherwise, `T`. The seller must decide what he wants to sell, and amount (ex:`3-A`), and then what he would accept (ex:`5-B,2-D,1-E`) (The values are *any of* not *all of*). The buyer will then be told what product the seller is selling, then the products the seller will take for it, and he can choose a product to trade for it (ex: `D` or `X` for nothing).

After all trades are over, or after you have left the market, you will consume 2 of each product, and the year starts over. If you have less than 2 of any 1 product, you will die (and passed `Q`).

Your score will be the number of years you last, and after 50 games, your scores will be averaged for your total score.

## Optional moves

At any time you can return `G` to query your goods

At any time you can return `N` to query the number of new products in your inventory (produced by any player in the past year, and new products will be traded before old products)

At any time you can return `T` for the current Turn phrase: `P`roduce, `M`arket, or `T`rading

During a trade, you can query `I` for an identifier unique to the player you are trading with.

During a trade, you can return `M` to query the number of people trading

## How to code it:

You may use any standard language, and must include a `command.txt` which is the command to run your program.

The general flow of your program should be:

```
Get productivity
While alive:
    Output product you want to produce
    While in trading:
        Output whether you want to purchase or sell
        Get whether or not you were skipped.  If not skipped:
            If purchasing:
                print product you offer, and products you will accept
            Else:
                Get product offered, products being accepted, and choose the product you will give

```

I have a tester program here. To use it, create a folder in the bots folder with your bot's name. Add a `command.txt`, your program, and anything else your program needs. I will be adding submissions as they come in. If you don't want to install the languages required to run some or all of them, you just need to delete the command.txt in the bot's folder.

## Inner Workings

There will be 5 bots for each program submitted. The ID will be different for bots of the same type.

I will call the amount a person can produce a given product the productivity. Each product will be given a base productivity, where all of the base productivity will add up to 30. One of the scores will be ensured to be at most 3, and all will be at least 2.

Then, each player's productivity will vary from the base productivity (One value will vary by +2, another +1, then +0, -1, and the remaining value will vary by -2).

The base productivity will change from game to game.

## Scores:

```
seer:                10.128 years
level_headed_trader: 8.196 years
introvert:           6.856 years
random_ando:         5.408 years
hoarder_trader:      4.12 years
ratio_trader:        3.532 years
scared_trader:       3.056 years

```

# Answer
# Seer

This program predicts the future, and he chooses the trades which will increase his expected lifespan.

This isn't completely finished, because he only knows how to buy things but not sell things, so expect an update in the future. Regardless, I believe that he will be competitive as-is.

```
$| = 1;
@names = ('A','B','C','D','E');
@counts = (12,12,12,12,12);
%names = ('A',0,'B',1,'C',2,'D',3,'E',4);

sub predict{
 local @a = @_;
 local $minval = 1000;
 local $minloc = 0;
 for(0..~~@a-1){
  if($a[$_]<$minval){
   $minloc = $_;
   $minval = $a[$_]
  }
  $a[$_]-=2;
 }
 if($minval <= 1){return (0,@a)}
 if($minval == 100){return (10000,@a)}
 $a[$minloc] += $productivity[$minloc];
 local @b = predict(@a);
 @b[0]++;
 return @b;
}

sub choice{
 local @a = @_;
 local $minloc = 0;
 local $minval = 1000;
 for(0..~~@a-1){
  if($a[$_]<$minval){
   $minloc = $_;
   $minval = $a[$_]
  }
 }
 return $minloc;
}

$productivity = <>;
@productivity = split(',',$productivity);

#@c = predict(@counts);
#print "@c\n";
$alive = 1;
while($alive){
 for(0..4){
  $counts[$_] -= 2;
 }
 $choice = choice(@counts);
 print "$names[$choice]\n";
 $counts[$choice] += $productivity[$choice];
 for(1..50){
  print "P\n";
  chomp($in = <>);
  if($in eq "T"){
   chomp($forsale = <>);
   ($quantity,$type) = split("-",$forsale);
   $type = $names{$type};
   #print "$quantity, $type\n";
   chomp($in = <>);
   @options = split(",",$in);
   @baseline = predict(@counts);
   $lifespan = shift @baseline;
   $basescore = $lifespan * 1000;
   @bestcounts = @counts;
   for(0..4){
    $basescore -= 10**(-1 * $baseline[$_]);
   }
   #print "Base: $basescore\n";
   @hypo = ();
   $bestscore = $basescore;
   $choice = "X";
   for(0..$#options){$curchoice = $_;
    ($cost,$ctype) = split("-",$options[$curchoice]);
    $ctype = $names{$ctype};
    @tempcounts = @counts;
    $tempcounts[$type] += $quantity;
    $tempcounts[$ctype] -= $cost;
    @curhypo = predict(@tempcounts);
    @hypo[$curchoice] = [@curhypo];
    #print "@curhypo\n";
    $lifespan = shift @curhypo;
    $score = $lifespan * 1000;
    for(0..4){
     $score -= 10**(-1 * $curhypo[$_]);
    }
    #print"$score\n";
    if($score > $bestscore){
     $bestscore = $score;
     $choice = $names[$ctype];
     @bestcounts = @tempcounts;
    }
   }
   print "$choice\n";
   @counts = @bestcounts;
  }
  #print"@counts\n";
  #@c = predict(@counts);
  #print "@c\n";
 }
}

```

I run this program like so:

```
perl seer.plx

```
> 3 votes

# Answer
# Level-headed Trader

This bot tries to make his quantities as equal as possible

## command.txt

```
python leveller.py

```

## leveller.py

```
import sys

def current_goods():
    print "G"
    return parse_goods(readline())

def parse_goods(good_string):
    return dict([(a, int(b))
                 for a, b in [product.split("-")
                              for product in good_string.split(",")]])

def get_minimum(goods):
    cur_min = 200
    min_good = "X"
    for good, amount in goods.items():
        if amount < cur_min:
            min_good = good
            cur_min = amount
    return min_good

def get_maximum(goods):
    cur_max = -1
    max_good = "X"
    for good, amount in goods.items():
        if amount > cur_max:
            max_good = good
            cur_max = amount
    return max_good

def add_goods(x, y):
    return {k: int(x.get(k, 0)) + int(y.get(k, 0)) for k in set(x) | set(y)}

def readline():
    line = sys.stdin.readline().strip()
    if line == 'Q' or not line:
        exit()
    return line

def output_goods(goods):
    print ",".join([good+"-"+str(amount) for good, amount in goods.items()])

def output_good(good, amount):
    print good+"-"+str(amount)

def current_turn_is(turn):
    print "T"
    return readline() == turn

turns = MARKET, PRODUCE, TRADING, SKIPPED = "M", "P", "T", "S"
market_options = PURCHASE, SELL = "P", "S"
items = APRICOTS, BOARS, CANARIES, DAFFODILS, EARWIGS, NOTHING = "A", "B", "C", "D", "E", "X"

productivity = parse_goods(readline())
while True:
    product_to_produce = get_minimum(current_goods())
    print product_to_produce
    while current_turn_is(MARKET):
        print SELL
        if readline() != SKIPPED:
            maximum = get_maximum(current_goods())
            goods = {"A": 1, "B": 1, "C": 1, "D": 1, "E": 1}
            del goods[maximum]
            output_good(maximum, 1)
            output_goods(goods)

```
> 4 votes

# Answer
# Scared Trader

This trader avoids getting low numbers

## command.txt

```
python scared.py

```

## scared.py

```
import sys

def current_goods():
    print "G"
    return parse_goods(readline())

def parse_goods(good_string):
    return dict([(a, int(b))
                 for a, b in [product.split("-")
                              for product in good_string.split(",")]])

def get_minimum(goods):
    cur_min = 200
    min_good = "X"
    for good, amount in goods.items():
        if amount < cur_min:
            min_good = good
            cur_min = amount
    return min_good

def get_maximum(goods):
    cur_max = -1
    max_good = "X"
    for good, amount in goods.items():
        if amount > cur_max:
            max_good = good
            cur_max = amount
    return max_good

def add_goods(x, y):
    return {k: int(x.get(k, 0)) + int(y.get(k, 0)) for k in set(x) | set(y)}

def readline():
    line = sys.stdin.readline().strip()
    if line == 'Q' or not line:
        exit()
    return line

def output_goods(goods):
    print ",".join([good+"-"+str(amount) for good, amount in goods.items()])

def output_good(good, amount):
    print good+"-"+str(amount)

def current_turn_is(turn):
    print "T"
    return readline() == turn

turns = MARKET, PRODUCE, TRADING, SKIPPED = "M", "P", "T", "S"
market_options = PURCHASE, SELL = "P", "S"
items = APRICOTS, BOARS, CANARIES, DAFFODILS, EARWIGS, NOTHING = "A", "B", "C", "D", "E", "X"

productivity = parse_goods(readline())
while True:
    current = current_goods()
    min_product = get_minimum(current)
    min_amount = current[min_product]
    product_to_produce = min_product if min_amount < 4 else get_minimum(productivity)
    print product_to_produce
    while current_turn_is(MARKET):
        print SELL
        if readline() != SKIPPED:
            current = current_goods()
            maximum = get_maximum(current)
            minimum = get_minimum(current)
            to_offer = {maximum: max(productivity[maximum]/productivity[minimum], 1)}
            output_good(minimum, 1)
            output_goods(goods=to_offer)

```
> 4 votes

# Answer
# Hoarder Trader

This trader tries to get as many products as possible.

## command.txt

```
python hoarder.py

```

## hoarder.py

```
import sys

def current_goods():
    print "G"
    return parse_goods(readline())

def parse_goods(good_string):
    try:
        return dict([(a, int(b))
                     for a, b in [product.split("-")
                                  for product in good_string.split(",")]])
    except:
        raise IOError(good_string)

def get_minimum(goods):
    cur_min = 200
    min_good = "X"
    for good, amount in goods.items():
        if amount < cur_min:
            min_good = good
            cur_min = amount
    return min_good

def get_maximum(goods):
    cur_max = -1
    max_good = "X"
    for good, amount in goods.items():
        if amount > cur_max:
            max_good = good
            cur_max = amount
    return max_good

def add_goods(x, y):
    return {k: int(x.get(k, 0)) + int(y.get(k, 0)) for k in set(x) | set(y)}

def readline():
    line = sys.stdin.readline().strip()
    if line == 'Q' or not line:
        exit()
    return line

def output_goods(goods):
    print ",".join([good+"-"+str(amount) for good, amount in goods.items()])

def output_good(good, amount):
    print good+"-"+str(amount)

def current_turn_is(turn):
    print "T"
    return readline() == turn

turns = MARKET, PRODUCE, TRADING, SKIPPED = "M", "P", "T","S"
market_options = PURCHASE, SELL = "P", "S"
items = APRICOTS, BOARS, CANARIES, DAFFODILS, EARWIGS, NOTHING = "A", "B", "C", "D", "E", "X"

productivity = parse_goods(readline())
while True:
    product_to_produce = get_minimum(add_goods(current_goods(), productivity))
    print product_to_produce
    while current_turn_is(MARKET):
        print PURCHASE
        if readline() != SKIPPED:
            offered_good = parse_goods(readline())
            accepted_goods = parse_goods(readline())
            minimum = get_minimum(accepted_goods)
            current = current_goods()
            if minimum not in current or current[minimum] < accepted_goods[minimum]:
                print NOTHING
            elif accepted_goods[minimum] < offered_good.values()[0]:
                print minimum
            elif accepted_goods[minimum] == offered_good.values()[0] \
                    and productivity[minimum] > productivity[offered_good.keys()[0]]:
                print minimum
            else:
                print NOTHING

```
> 3 votes

# Answer
# Ratio Trader

This bot offers products matching the ratio of his productivity

## command.txt

```
python ratio.py

```

## ratio.py

```
import sys

def current_goods():
    print "G"
    return parse_goods(readline())

def parse_goods(good_string):
    return dict([(a, int(b))
                 for a, b in [product.split("-")
                              for product in good_string.split(",")]])

def get_minimum(goods):
    cur_min = 200
    min_good = "X"
    for good, amount in goods.items():
        if amount < cur_min:
            min_good = good
            cur_min = amount
    return min_good

def get_maximum(goods):
    cur_max = -1
    max_good = "X"
    for good, amount in goods.items():
        if amount > cur_max:
            max_good = good
            cur_max = amount
    return max_good

def add_goods(x, y):
    return {k: int(x.get(k, 0)) + int(y.get(k, 0)) for k in set(x) | set(y)}

def readline():
    line = sys.stdin.readline().strip()
    if line == 'Q' or not line:
        exit()
    return line

def output_goods(goods):
    print ",".join([good+"-"+str(amount) for good, amount in goods.items()])

def output_good(good, amount):
    print good+"-"+str(amount)

def current_turn_is(turn):
    print "T"
    return readline() == turn

turns = MARKET, PRODUCE, TRADING, SKIPPED = "M", "P", "T", "S"
market_options = PURCHASE, SELL = "P", "S"
items = APRICOTS, BOARS, CANARIES, DAFFODILS, EARWIGS, NOTHING = "A", "B", "C", "D", "E", "X"

productivity = parse_goods(readline())
while True:
    current = current_goods()
    min_product = get_minimum(current)
    min_amount = current[min_product]
    product_to_produce = min_product if min_amount < 4 else get_minimum(productivity)
    print product_to_produce
    while current_turn_is(MARKET):
        print SELL
        if readline() != SKIPPED:
            current = current_goods()
            maximum = get_maximum(current)
            minimum = get_minimum(current)
            to_offer = {maximum: max(productivity[maximum]/productivity[minimum], 1)}
            output_good(minimum, 1)
            output_goods(goods=to_offer)

```
> 3 votes

# Answer
# Family Farmers - Java

The five family farmers do their best to cover all production options with whoever can make the most in any category working on that category. However, after the initial assignments the family members all strike out on their own; they don't collude after the initial assignments. I may get around to having them help each other while trading.

**FamilyFarmers.java**

```
import java.io.IOException;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.channels.FileLock;
import java.nio.file.FileSystems;
import java.nio.file.Path;
import java.nio.file.StandardOpenOption;
import java.util.Scanner;

public class FamilyFarmers {
    final int MIN_PRODUCTION_CUTOFF = 4; // If my decision making has ended up
                                            // with a family member producing
                                            // less than this number, he will
                                            // just produce his most productive
                                            // item
    final int NUMBER_PRODUCTS = 5;
    final int MAX_TRADES = 50; // The number of trades per phase
    final byte EOF = 04;
    final byte NEW_LINE = 10;
    final int BILLBOARD_SIZE = 1000;

    boolean alive = true;

    int[] myInventory;

    int myNumber;
    // Primarily, the line this instance of the program will be printing on in
    // the billboard number 0 will be the "boss", and will do a bunch of the
    // calculations (To avoid them being done multiple times)
    MappedByteBuffer familyBillboard;
    String myProduct; // What product (single string character) we will be
                        // making
    Scanner stdin = new Scanner(System.in);

    /**
     * @param args
     *            A string in the form A-#,B-#,C-#,D-#,E-# representing the
     *            productivity of each good.
     * @throws IOException
     * @throws InterruptedException
     * @throws UnexpectedPhaseTokenException
     */
    public static void main(String[] args) throws IOException, InterruptedException {
        new FamilyFarmers();
    }

    public FamilyFarmers() throws IOException, InterruptedException {
        Runtime.getRuntime().addShutdownHook(new Thread() {
            public void run() {
                familyBillboard.clear();
                familyBillboard.put(new byte[familyBillboard.limit()]);
                Runtime.getRuntime().halt(0);
            }
        });
        initialSetup();
        mainLoop();
    }

    protected void mainLoop() throws InterruptedException {
        int tradeCounter = 0; // 50 trades per phase
        String currentStage;
        int toTrade = -1;
        int toGet = -1;
        boolean purchase = false;

        while (alive) {
            System.out.println("T");
            currentStage = stdin.nextLine();
            if (currentStage.equals("P")) { // Production period
                System.out.println(myProduct);
                /*
                System.out.println("G");
                String currentInv = stdin.nextLine();
                myInventory = parseProducts(currentInv);
                toTrade = getMostProduct();
                toGet = getLeastProduct();
                */
                tradeCounter = 0;

            } else if (currentStage.equals("M")) { // Market
                System.out.println("G");
                String currentInv = stdin.nextLine();
                myInventory = parseProducts(currentInv);
                tradeCounter++;
                purchase = (Math.random() >= 0.5);
                toTrade = getMostProduct();
                toGet = getLeastProduct();

                // If my goods are fairly even, it's time to head home!
                if (myInventory[toTrade] - myInventory[toGet] <= 2) {
                    System.out.println("L");
                    continue;
                }

                // If I don't have much to trade...
                if (toTrade <= 6) {
                    // But my goods levels are fairly even...
                    if (toGet >= 4) {
                        // I'll just leave the market
                        System.out.println("L");
                    }
                }

                if (purchase) {
                    System.out.println("P");
                } else {
                    System.out.println("S");
                }

            } else if (currentStage.equals("T")) {
                String toSend = "";
                if (purchase) { // Buying
                    boolean finished = false;
                    String offer = stdin.nextLine();
                    offer += "," + stdin.nextLine();
                    String[] offers = parseOffer(offer);
                    int quantityOffered = Integer.parseInt(offers[0].split("-")[0]);
                    int productOffered = offers[0].split("-")[1].charAt(0) - 65;

                    // This loop will probably never get off the first
                    // iteration...
                    // Go through the offers, blindly pick the first one that
                    // looks good.
                    for (int index = 1; index < offers.length && !finished; index++) {
                        int quantityDesired = Integer.parseInt(offers[index].split("-")[0]);
                        int productDesired = offers[index].split("-")[1].charAt(0) - 65;

                        // If the request would leave me with less than two, I'm
                        // not interested
                        if (quantityDesired - (myInventory[productDesired]) > 2) {
                            // Too rich for my blood!
                            continue;
                        }
                        if (productDesired == toGet) {
                            // I'm not interested in trading what I'm trying to
                            // get!
                        }
                        if (productOffered == toGet) {
                            // Since this is what I want to trade for, I'll be
                            // willing to consider different offers than
                            // otherwise

                            if (quantityDesired <= quantityOffered * 1.25
                                    && myInventory[productDesired] - quantityDesired > 4) {
                                System.out.println((char) (productDesired + 65));
                                finished = true;
                            }

                            // If I would otherwise die without the product,
                            // I'll accept a really bad trade
                            // (Remember that the incoming offers are already
                            // sorted least to highest)
                            if (myInventory[toGet] < 2 && tradeCounter > MAX_TRADES / 2) {
                                System.out.println((char) (productDesired + 65));
                                finished = true;
                            }
                        }

                        // If the product is what I'm trying to trade, and the
                        // offer isn't too bad
                        if (productDesired == toTrade && quantityOffered * 1.25 <= quantityDesired) {
                            System.out.println((char) (productDesired + 65));
                            finished = true;
                        }

                        // If I am offered either as much as or more of
                        // something, I'll do it.
                        if (quantityOffered >= quantityDesired) {
                            System.out.println((char) (productDesired + 65));
                            finished = true;
                        }
                    }

                    if (!finished) {
                        // If we get this far, nothing struck my fancy
                        System.out.println("X");
                    }

                } else { // Selling
                    int[] toBuy = getSameProducts(toGet);

                    // Make some self-beneficial offers in the first few rounds.
                    if (tradeCounter <= 5) {
                        toSend = "" + ("2-" + ((char) (toTrade + 65)));
                        for (int index = 0; index < toBuy.length; index++) {
                            toSend += (",3-" + ((char) (toBuy[index] + 65)));
                        }
                    } else {
                        // Basic offer. Just offer 1:1 for what I want.
                        toSend = "" + ("2-" + ((char) (toTrade + 65)));
                        for (int index = 0; index < toBuy.length; index++) {
                            toSend += (",2-" + ((char) (toBuy[index] + 65)));
                        }
                    }

                    // If trading has been going for awhile and I would die the
                    // next turn, I frantically offer everything I have for what
                    // I need to survive one more turn. This is probably a
                    // terrible strategy!
                    if (myInventory[toGet] < 2 && tradeCounter > MAX_TRADES / 2) {
                        toSend += ("4-" + ((char) (toTrade + 65))) + ",2-" + ((char) (toGet + 65));
                    }

                    if (toSend.length() < 6) {
                        // I couldn't find enough to sell...
                        System.out.println(toSend + "," + toSend);
                        // That's safe, right?
                        break;
                    }

                    // Put the products I would accept on a line after the
                    // product I want to sell
                    String[] splitSend = toSend.split(",");
                    toSend = splitSend[0] + "\n";
                    boolean first = true; // Don't prepend a comma on the first string

                    for (int index = 1; index < splitSend.length; index++) {
                        if (!first){
                            toSend += ",";
                        }
                        toSend += splitSend[index];
                        first = false;
                    }

                    System.out.println(toSend);

                }

            } else if (currentStage.equals("S")) { // I was skipped! Darn it!
            } else {
                // AAK! I received a token I don't know what to do with! I must
                // be dead...
                alive = false;
            }
        }
    }

    /**
     * Returns the offers, sorted from least product desired to most, with the
     * product being offered at the first index
     *
     * @param offer
     * @return String[] index 0 contains the product being offered, the
     *         following indicies are the desired products ordered from least to
     *         most
     */
    protected String[] parseOffer(String offer) {
        String[] splitOffers = offer.split(",");

        // Sort. Just using selection sort. The first index contains the string
        // with the product being asked for,
        // so should not be sorted.
        for (int index = 1; index < splitOffers.length; index++) {
            int indexOfMin = index;
            int minimum = Integer.parseInt(splitOffers[index].split("-")[0]);
            for (int jdex = index + 1; jdex < splitOffers.length; jdex++) {
                int thisValue = Integer.parseInt(splitOffers[jdex].split("-")[0]);
                if (thisValue < minimum) {
                    indexOfMin = jdex;
                    minimum = thisValue;
                }
            }
            String temp = splitOffers[index];
            splitOffers[index] = splitOffers[indexOfMin];
            splitOffers[indexOfMin] = temp;

        }

        return splitOffers;
    }

    /**
     * Returns an array of the indices of the product which I have the same
     * quantity of in myInventory
     *
     * @param startingIndex
     *            - The index of a value to match
     * @return
     */
    protected int[] getSameProducts(int startingIndex) {
        int[] toReturn = new int[0];

        for (int index = startingIndex + 1; index < myInventory.length; index++) {
            if (myInventory[index] == myInventory[startingIndex]) {
                int[] temp = new int[toReturn.length + 1];
                for (int jdex = 0; jdex < toReturn.length; jdex++) {
                    temp[jdex] = toReturn[jdex];
                }
                temp[temp.length - 1] = index;
                toReturn = temp;
            }
        }

        return toReturn;
    }

    /**
     * Returns the index of the product which I have the least of in myInventory
     * I can't help but feel that this lacks object-oriented design...
     *
     * @return
     */
    protected int getLeastProduct() {
        int toReturn = 0;

        for (int index = 1; index < myInventory.length; index++) {
            toReturn = myInventory[index] < myInventory[toReturn] ? index : toReturn;
        }

        return toReturn;
    }

    /**
     * Returns the index of the product which I have the most of in myInventory
     * I can't help but feel that this lacks object-oriented design...
     *
     * @return
     */
    protected int getMostProduct() {
        int toReturn = 0;

        for (int index = 1; index < myInventory.length; index++) {
            toReturn = myInventory[index] > myInventory[toReturn] ? index : toReturn;
        }

        return toReturn;
    }

    /**
     * Returns an int[] containing the productivity of each product in
     * alphabetical order
     *
     * @param products
     * @return
     */
    protected int[] parseProducts(String products) {
        int[] toReturn;
        // Split the string so that each line of the array has #-P
        String[] lineProductivities = products.split(",");

        // Split each string in the array so that it is just the number
        for (int index = 0; index < lineProductivities.length; index++) {
            lineProductivities[index] = lineProductivities[index].split("-")[0];
        }

        toReturn = new int[lineProductivities.length];

        for (int index = 0; index < lineProductivities.length; index++) {
            toReturn[index] = Integer.parseInt(lineProductivities[index]);
        }

        return toReturn;
    }

    /**
     * Append my productivity string to the family billboard. If the file was
     * empty when I got here (contained no newlines), I am the boss! The boss
     * gives orders.
     *
     * @throws IOException
     * @throws InterruptedException
     */
    protected void initialSetup() throws IOException, InterruptedException {
        String input;
        myNumber = 0;
        FileChannel familyBillboardFC;
        Path billboardPath = FileSystems.getDefault().getPath("family_billboard.txt");
        FileLock billboardLock;
        byte[] argsByteArray;

        byte currentByte = 0;

        input = stdin.nextLine();

        // Open the file and lock it
        familyBillboardFC = FileChannel.open(billboardPath, StandardOpenOption.WRITE, StandardOpenOption.READ);
        billboardLock = familyBillboardFC.lock();

        // Map the contents of the file to a space in memory
        familyBillboard = familyBillboardFC.map(FileChannel.MapMode.READ_WRITE, 0, BILLBOARD_SIZE);

        // Convert the incoming string into an array of bytes
        argsByteArray = input.getBytes();

        for (int index = 0; index < BILLBOARD_SIZE; index++) {
            currentByte = familyBillboard.get();
            if (currentByte == NEW_LINE) {
                myNumber++;
                familyBillboard.mark();
            }
        }

        if (myNumber == 0) {
            familyBillboard.position(0);
            familyBillboard.mark();
        }
        familyBillboard.reset();

        for (byte b : argsByteArray) {
            familyBillboard.put(b);
        }
        familyBillboard.put(NEW_LINE);
        familyBillboard.put(EOF);

        billboardLock.release();

        Thread.sleep(100); // Give other programs a chance to launch

        // Boss needs to wait for awhile to make sure the others have finished
        // writing...
        // I don't have any idea how to do this in an intelligent fashion. It is
        // *probably* safe to sleep for a few hundred milliseconds, but I'm not
        // certain. Instead, I'll try to take out a new lock. If I succeed
        // twice, the file must be finished!
        int counter = 0;
        while (myNumber == 0) {
            billboardLock = familyBillboardFC.tryLock();
            if (billboardLock != null) {
                billboardLock.release();
                counter++;
            } else {
                counter = 0;
                Thread.sleep(10);
            }
            if (counter >= 2) {
                giveOrders();
                break;
            }
        }

        byte foo = familyBillboard.get();
        // Until the boss has written out the instructions, sleep
        while (foo < 65) {
            Thread.sleep(10);
            familyBillboard.reset();
            foo = familyBillboard.get();
        }

        familyBillboard.reset();
        myProduct = String.valueOf((char) familyBillboard.get());
    } // initialSetup()

    /**
     * Run by the boss. Tries to sort the family so that every product is
     * covered and so that whoever can produce the most of a product is
     * producing it. Writes the character code representing the product to
     * produce to the first character of the relevant line in the family
     * billboard.
     */
    protected void giveOrders() {
        final int MAX_LINE_LENGTH = 24;
        int numberMembers = 0;
        byte currentByte = 0;
        Integer[][] productivities; // Table of member's productivities
        char[] selections; // Who will make what. selections[#] = the production
                            // letter for member #

        familyBillboard.position(0);

        // I have seen the rules to these games change. It's easy for me to
        // accommodate more (or less than) 5 instances now. It may not be easy
        // later
        while (currentByte != EOF) {
            currentByte = familyBillboard.get();
            if (currentByte == NEW_LINE) {
                numberMembers++;
            }
        }
        currentByte = 0;
        familyBillboard.reset();

        selections = new char[numberMembers];

        productivities = new Integer[numberMembers][NUMBER_PRODUCTS];

        for (int index = 0; index < numberMembers; index++) {
            byte[] currentLineBytes = new byte[MAX_LINE_LENGTH];
            String currentLine;

            // Read the next line
            for (int jdex = 0; jdex < currentLineBytes.length; jdex++) {
                currentByte = familyBillboard.get();
                if (currentByte == NEW_LINE) {
                    break;
                }
                currentLineBytes[jdex] = currentByte;
            }
            currentLine = new String(currentLineBytes);
            currentByte = 0;

            int[] lineProductivities = parseProducts(currentLine);

            // Need to iterate to get the int[] to Integer[]
            for (int jdex = 0; jdex < NUMBER_PRODUCTS; jdex++) {
                productivities[index][jdex] = lineProductivities[jdex];
            }

        }

        // If there are at least as many producers as products, select the most
        // productive for each producer. If there are overlaps, move the smaller
        // one to the second most productive and re-check for overlaps. If there
        // are overlaps and the productivity is tied, compare the second highest
        // and so on.
        // TODO What if members > 5?
        if (numberMembers <= NUMBER_PRODUCTS) {
            int[] overlapResult;
            for (int index = 0; index < selections.length; index++) {
                selections[index] = (char) (maxInArray(productivities[index]) + 65);
                // Can convert from a max value in productivities to a
                // human-readable character by adding 65, since 0 -> A, 1 -> B,
                // etc.
            }

            int counter = 0; // I imagine there is a possibility of this loop
                                // not terminating. I will use this counter to
                                // forcefully break it.

            // While there is an overlap
            while ((overlapResult = arrayHasOverlaps(selections)) != null && overlapResult[0] != -1) {
                byte productIndex = (byte) (selections[overlapResult[0]] - 65);
                // 0 through the number of production options, where A = 0, B =
                // 1, etc.
                if (productivities[overlapResult[0]][productIndex] > productivities[overlapResult[1]][productIndex]) {
                    int index = findNextHighestFromIndex(productivities[overlapResult[1]], productIndex);
                    selections[overlapResult[1]] = (char) (index + 65);
                }
                if (productivities[overlapResult[1]][productIndex] > productivities[overlapResult[0]][productIndex]) {
                    int index = findNextHighestFromIndex(productivities[overlapResult[0]], productIndex);
                    selections[overlapResult[0]] = (char) (index + 65);
                }
                // Things are beginning to get mega hairy
                if (productivities[overlapResult[0]][productIndex] == productivities[overlapResult[1]][productIndex]) {
                    int index0 = findNextHighestFromIndex(productivities[overlapResult[0]], productIndex);
                    int index1 = findNextHighestFromIndex(productivities[overlapResult[1]], productIndex);
                    if (productivities[overlapResult[0]][index0] > productivities[overlapResult[1]][index1]) {
                        selections[overlapResult[0]] = (char) (index0 + 65);
                    } else {
                        // I can't be bothered to go any further with this... If
                        // they're tied here, then to heck with it!
                        selections[overlapResult[1]] = (char) (index1 + 65);
                    }
                }

                counter++;
                if (counter > BILLBOARD_SIZE) {
                    break;
                }
            }
        }

        // Check for less than my minimum cutoff. If one is, set it to its max.
        for (int index = 0; index < selections.length; index++) {
            byte b = (byte) (selections[index] - 65);
            if (productivities[index][b] < MIN_PRODUCTION_CUTOFF) {
                selections[index] = (char) (maxInArray(productivities[index]) + 65);
            }
        }

        // Write the product to produce to the correct line
        familyBillboard.position(0);
        familyBillboard.put((byte) selections[0]);
        // If we find a newline, write the selected character to the next
        // spot. Otherwise, read the next character
        for (int index = 1; index < selections.length;) {
            byte thisByte = familyBillboard.get();
            if (thisByte == NEW_LINE) {
                familyBillboard.put((byte) selections[index]);
                index++;
            }
        }
    }

    /**
     * Look through the array. Find an element that is either later in the array
     * and <= the value at the incoming index and > the value at the toReturn
     * index, or earlier in the array and < the value at the current index and >
     * the value at toReturn. If we weren't able to set the new index (Maybe we
     * are already at the max value) return the index of the largest value
     *
     * @param array
     *            the array to search in
     * @param incomingIndex
     *            the index of the value to begin searching with
     * @return an index as described
     */
    protected int findNextHighestFromIndex(Integer[] array, int incomingIndex) {
        int toReturn = incomingIndex;
        int comparisonValue = -1; // The value at toReturn
        int index = (incomingIndex + 1) % array.length;

        for (int counter = 0; counter < array.length; counter++) {
            if (index > incomingIndex && array[index] == array[incomingIndex]) {
                // If we have found an equal value later in the array, return
                // immediately. In the unlikely event everything is equal,
                // don't just take the value at the bottom index!
                return index;
            }
            if (index > incomingIndex && array[index] < array[incomingIndex] && array[index] > comparisonValue) {
                toReturn = index;
                comparisonValue = array[toReturn];
            }
            if (index < incomingIndex && array[index] < array[incomingIndex] && array[index] > comparisonValue) {
                toReturn = index;
                comparisonValue = array[toReturn];
            }

            index++;
            index %= array.length; // How often do you get to use %= ?
        }

        if (comparisonValue == -1) {
            // In the unlikely event we weren't able to set comparisonValue
            // (maybe we are already at the minimum?)
            toReturn = maxInArray(array);
            // This will probably contribute to those endless loops I mentioned
            // above!
        }

        return toReturn;
    }

    /**
     * Checks the array for any two elements being the same. If two are, return
     * the indices. If not, return {-1, -1}
     *
     * @param selections
     *            The array to examine
     * @return Indices of the overlapping elements or {-1, -1}
     */
    protected int[] arrayHasOverlaps(char[] selections) {
        int[] toReturn = new int[] { -1, -1 };
        for (int index = 0; index < selections.length - 1; index++) {
            for (int jdex = index + 1; jdex < selections.length; jdex++) {
                if (selections[index] == selections[jdex]) {
                    toReturn[0] = index;
                    toReturn[1] = jdex;
                    return toReturn;
                }
            }
        }
        return toReturn;
    }

    /**
     * Returns the index of the max value of an array. In the case of a tie,
     * returns the earliest index.
     *
     * @param array
     *            the array to read
     * @return the index of the largest element in the array
     */
    protected <T extends Comparable<T>> byte maxInArray(T[] array) {
        byte currentMax = 0;
        for (byte index = 0; index < array.length; index++) {
            currentMax = array[index].compareTo(array[currentMax]) > 0 ? index : currentMax;
        }
        return currentMax;
    }
}

```

**command.txt**

```
cd bots/family_farmer && java FamilyFarmers

```

It can be compiled with

```
javac FamilyFarmer.java

```

There should also be another blank file, family\_billboard.txt, in the bots/family\_farmer folder.
> 3 votes

# Answer
# Introvert - Java

This bot is so introverted, it would rather die than talk to anyone in trading, so it immediately leaves market if it is there. However, it doesn't want to die so it tries to keep its supplies up as long as possible.

**Introvert.java**

```
import java.util.Scanner;

public class Introvert{

    static int[] current = {10,10,10,10,10};
    static int[] potentialProduction = new int[5];
    static boolean alive = true;

    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        String input = s.nextLine();
        String[] inputArray = input.split(",");
        for(int i = 0; i < 5; i++){
            potentialProduction[i] = Integer.parseInt(inputArray[i].replaceAll("\\D+",""));
        }

        while(alive){
            int pos = decideProduction();
            produce(pos);
            System.out.println("L");
            for(int i = 0; i < 5; i++){
                current[i] -= 2;
                if(current[i] < 0)
                    alive = false;
            }
        }
        s.nextLine(); //read final `q` message
    }

    public static int decideProduction(){
        int lowestPotential = 9999;
        int lowestPotentialPosition = 9999;
        for(int i = 0; i < 5; i++){
            if(current[i] == 2 || current[i] == 3){
                lowestPotentialPosition = i;
                break;
            }
            int potential = current[i] + potentialProduction[i];
            if(potential < lowestPotential){
                lowestPotential = potential;
                lowestPotentialPosition = i;
            }
        }
        switch(lowestPotentialPosition){
            case 0: System.out.println("A"); return 0;
            case 1: System.out.println("B"); return 1;
            case 2: System.out.println("C"); return 2;
            case 3: System.out.println("D"); return 3;
            case 4: System.out.println("E"); return 4;
            default: System.out.println("A"); return 0;
        }
    }

    public static void produce(int pos){
        current[pos] += potentialProduction[pos];
    }

}

```

**command.txt**

```
java Introvert

```

Compile with

```
javac Introvert.java

```

Note: I did this on my lunch break and my work computer doesn't have the jdk or python so I have not been able to test it at all. If it does not work let me know and I will try to fix it.
> 2 votes

# Answer
# Random Ando

Every KOTH should have a random bot. Coded, hopefully, so that it won't make invalid deals (like trying to sell more than what it has in stock).

```
--RandomAndo

math.randomseed(os.time()) math.random()math.random()math.random()

ITEMS = {"A", "B", "C","D", "E"}
MARKETOPTION = {"P", "S"}
MyGoods = {0,0,0,0,0}

local function readline() -- checks for the dying "Q" or just reads line
    local line = io.read("*l")
    if line == "Q" then
        os.exit()
    end

    return line
end

local function getCurrentTurn() -- asks for M,T,P
    print("T")
    return readline()
end

local function getRandom(array) -- returns for a random element in array
    local r=math.random(#array)
    return array[r]
end

local function getRandomMyItems() -- make a list of items I have and return a random one (no more than one of)
    local rgood=math.random(5)
    local amount=1
    while MyGoods[rgood] <= 0 do
        rgood=math.random(5)
    end
    return amount.."-"..ITEMS[rgood]
end

local function parseGoods(goodString) -- specialized to getMyGoods atm
    local goods={0,0,0,0,0}
    local c = 1
    example = "5-A,6-B,3-C,12-D,4-E"
    for good in goodString:gmatch("%d+%p[ABCDE]") do
        goods[c]=goods[c]+good:match("%d+")
        c=c+1
    end

    return goods
end

local function getMyGoods() -- asks for my goods
    print("G")
    local temp = parseGoods(readline())
    for i=1,5 do
        MyGoods[i]=temp[i]
    end
end

productivity = readline() -- doesn't matter

while true==true do

    print(getRandom(ITEMS)) -- produce random item

    while getCurrentTurn()=="M" do
        getMyGoods()

        local action=getRandom(MARKETOPTION) -- make a random market decision
        if action == "S" then -- offer to sell 1 of a random item I  have in stock, will take any 2 offered
            print("S")
            if readline()=="T" then
                print(getRandomMyItems())
                print("2-A,2-B,2-C,2-D,2-E")
            end
        elseif action == "P" then -- if I can do the deal, I will
            print("P")
            if readline()=="T" then
                local offered=readline()
                local accepted =readline()
                local taccepted={}
                for i in accepted:gmatch("%d+%p[ABCDE]") do
                    oitem =i:match("[ABCDE]")
                    oamount = i:match("%d+")
                    for k=1,5 do
                        if ITEMS[k]==oitem and MyGoods[k]>=tonumber(oamount) then
                            table.insert(taccepted, oitem)
                        end
                    end
                    if #taccepted>=1 then
                        print(getRandom(taccepted))
                    else
                        print("X")
                    end
                end
            end
        elseif action == "L" then
            print("L")
        end
    end
end

```

command.txt should be:

```
lua RandomAndo.lua

```
> 1 votes

---
Tags: king-of-the-hill
---


title: Tips for golfing in LiveScript

text:
# Question
Title: Tips for golfing in LiveScript
What general tips do you have for golfing in LiveScript? I'm looking for ideas that can be applied to code golf problems in general that are at least somewhat specific to LiveScript (e.g. "remove comments" is not an answer). Please post one tip per answer.

# Answer
# Take advantage of curried functions and Prelude.ls

If the function is already curried, it can be much shorter overall. Also, Prelude.ls is the ***standard library***, and its functions are often very useful. This means, unless otherwise specified, this library is 100% allowed. Examples:

```
f=->[1 to &0].reduce (*) # space required
f=->product [1 to &0]

s=(.reduce (+))
s=sum                    # better yet, avoid defining this when possible

d=(.map (*2))
d=map (*2)               # Sometimes even shorter than native methods

r=->&0.reduce (-&1-)
r=->fold1 (-&1-),&0      # Equal if starting value is required.

a.=sort!
a=sort a                 # sometimes the same length

a.=sort ->&1.length-&0.length # space before arrow required
a.=sort over (-),(.length)    # slightly more functional
a=sortBy (.length)            # specific builtin, always prefer CamelCase

```
> 2 votes

# Answer
# Positional function arguments

In LiveScript, `&` is a shorthand for `arguments`. `arguments[0]` can be shortened to `&[0]`, which can be shortened to `&.0`, which in turn can be shortened to `&0`.

**Before:**

```
f=(x,y)->x+y

```

**After:**

```
f=->&0+&1

```
> 1 votes

# Answer
# `.n` over `[n]`, `\n` over `['n']`, etc.

This won't work for computed indices and members, but with static ones, it shaves bytes. Examples:

```
f[0]
f.0

f['str']
f\str

f['str with spaces']
f'str with spaces'

```

This will not work with other literals, such as RegExps, booleans, `null`, `void`, etc.
> 1 votes

# Answer
# Use partial functions when possible (with discretion)

Partial functions can drastically shorten many operations. Examples:

```
f=->it^2
f=(^2)

s=->&0.length==&1.length
s=over(==),(.length)

```

It isn't always better, though. Example:

```
# [[a, b], [c, d], [e, f]] -> (a+b)*(c+d)*(e*f)
f=(|>map sum|>product)
f=product map sum # these are actually curried

```
> 1 votes

# Answer
# `it` instead of explicit function argument

If you have a function with a single argument and you only refer to it at most twice, use `it` instead.

**Before:**

```
f=(x)->x+x

```

**After:**

```
f=->it+it

```
> 0 votes

# Answer
# Short form of `switch`

Use `|` instead of `case` and `|_` instead of `default`. Also, pipes themselves terminate statements.

**Before:**

```
switch x;case 1=>f;case 2=>g;default=>h

```

**After:**

```
switch x|1=>f|2=>g|_=>h

```
> 0 votes

# Answer
Avoid explicit commas and dots

This:

```
foo(1, 2, 3).bar

```

can be just:

```
foo(1 2 3)bar

```
> 0 votes

# Answer
Use the shortest function syntax possible

this:

```
->&0+&1

```

can be written:

```
(+)

```

and this:

```
->it.foo - it.bar

```

can be written:

```
(.foo- it.bar) # notice the dash position

```
> 0 votes

---
Tags: code-golf, tips
---


title: Linking without a Link

text:
# Question
Title: Linking without a Link
**Introduction**

Hello! This is my second post, and I decided to do one which is more language specific, since my last one was very much orientated towards mathematical languages, and thus did not leave room for languages like JavaScript or HTML. If there is anyway to make this more clear, or to tidy up a wording problem, please do not hesitate to leave a comment below this post.

**The Task**

You have to create a JavaScript program which, when pasted into chrome's omnibar will open up the wonderful Google page.

**The Catch**

You may not use any characters within the google URL ("ceghlmopstw") or those characters in any other base. Also, you may not use any other links, redirect links or IP addressed.

**Extra Information**

* You can put JavaScript code in the omnibar by doing "JavaScript://Code"
* You cannot copy and paste javascript code into the omnibar. The code below will actually strip the "javascript:" part, the result of which is to simply search for "alert("Hello World!"). To get around this, I suggest typing your code in an IDE, such as Notepad++ without the "JavaScript:" and then add it in the omnibar when you go to test it.

javascript:alert("Hello World!")
* As this is code golf, the shortest entry wins!

**Bonuses**

* Each bonus will take away a certain amount of points from the **total** amount of characters, bonuses that are percentages will stack, so if one received a 20% bonus and a 25% bonus, they would in essence receive a 45% bonus.
* **25%** \- Changeable - You can change the website URL without doing complicated maths, or having to change the entire code!
* **50 chars** \- NoScript - Don't use any JavaScript! I have no idea how your going to achieve this!
* **25 chars** \- Exceptional - Don't use the ".:/" characters in your code. Removed from the main task as "JavaScript:" requires a colon.
* **15 chars** \- Multi-lingual - Make a solution that makes use of 3 or more languages!

**TL;DR**

You must code something to put in the chrome omnibar, that then redirects you to https://www.google.com without using the characters "ceghlmopstw"

**Leader Board**

```
soktinpk - 24  - Exceptional - First post to complete it in a way I had expected!
Someone  - -40 - NoScript    - Used a redirect link however.  Points for finding one without those characters, all of the ones I just found did!
Von llya - -37 - NoScript    - Used an IP address!

```

# Answer
# Javascript - 49 chars + (Exceptional bonus) = 24

There's a catch for this one; you have to have it open on this page. Also it will break as more links come to it. It requires jQuery.

```
javascript:$("a")[35][(r=(""+{})[5])+(""+!1)[2]+"i"+r+"k"]()

```

Commented version

```
$("a")[35] // Gets the 35th link (to google)
[
  (r=(''+{})[5]) // ''+{} is "[object Object]" get 5th char "c", assign it to variable r
  +(''+!1)[2] // grabs "l"
  +"i"+r+"k" // "ick" which makes "click" function
]() // Execute

```

As more links get published, you have to update the `35` to accomodate. (Again, it only runs on this page).

Tested on Chrome 35.0.1916.153
> 3 votes

# Answer
# No JavaScript

```
x.vu/zffW4Z

```

It took quite some searching to find an URL shortener that (a) was still around, and (b) avoided the prohibited characters.
> 2 votes

---
Tags: code-golf, javascript
---


title: Put a list in order

text:
# Question
Title: Put a list in order
With a window similar to the one pictured below, you are given a list of strings, which you want to put in alphabetical order.

As shown, you have five operations:

* Move up \[U\] - moves the selected string up one place
* Move down \[D\] - moves the selected string down one place
* Move first \[F\] - moves the selected string to the top of the list
* Move last \[L\] - moves the selected string to the bottom of the list
* Reverse \[R\] - reverses the order of the list

Using STDIN, accept a number (how many strings), followed by the unordered list of strings. Each string consists of 2-99 lower case English letters. (The example above would not be a valid input.)

Using STDOUT, print the way to put the list in order. First, mention an item to select, and then the operations(s) to perform on it in order to put the list in alphabetical order.

For example: `February U December F May D D June D R D...`

Explanation: Click February, move it up 1. Select December, move it to top. May, move it down twice. June, move down once, reverse the list, move down again...

Since there are obviously many valid solutions, you must choose the shortest possible. That is, choose the method with the fewest number of operations (7 in the above example).

If there's a tie among correct outputs to the input, resolve it in the following order.

1. Choose the one with the fewest string selections (4 in the above example).
2. Choose the one with the fewest operations, counting consecutive identical operations (on one string) as one (6 in the above example).
3. Choose the one with shortest output (least number of total characters, counting spaces).
4. Choose the one with the output that comes first alphabetically.

This is code-golf; the shortest submission which always produces the correct output wins.

## Examples

* IN `2 zz abc`
    + OUT `zz D`
* IN `3 cc bb aa`
    + OUT `aa R`
* IN `4 abc def cd ccc`
    + OUT `abc L R`
* IN `6 rr mm nn oo qq pp`
    + OUT `pp U rr L`

### Additional examples (provided by Scott Leadley, any errors are mine and not ypnypn's)

Some difficult cases:

* **IN** =\> **OUT**
* `6 xx aa dd bb ee cc` =\> `dd L ee L xx L`
* `7 aa bb ee cc dd ff gg` =\> `ee D D`
* `8 dd ww aa bb cc xx yy zz` =\> `ww D D D dd D D D`
    + (**not** the minimial number of moves, which would be `cc F bb F aa F`)

Permutations of 4 items `aa bb cc dd` with sort paths of length \>1:

* **IN** =\> **OUT**
* `4 aa cc dd bb` =\> `bb F D`
* `4 aa dd cc bb` =\> `aa L R`
* `4 bb aa dd cc` =\> `aa F cc U`
* `4 bb dd aa cc` =\> `aa F cc U`
* `4 bb dd cc aa` =\> `bb D D R`
* `4 cc aa bb dd` =\> `cc D D`
* `4 cc aa dd bb` =\> `bb F aa F`
* `4 cc bb aa dd` =\> `dd F R`
* `4 cc bb dd aa` =\> `dd F R`
* `4 cc dd aa bb` =\> `bb F aa F`
* `4 cc dd bb aa` =\> `cc D R`
* `4 dd aa cc bb` =\> `aa L R`
* `4 dd bb aa cc` =\> `cc F D R`
* `4 dd bb cc aa` =\> `bb D R`
* `4 dd cc aa bb` =\> `aa D R`

Variations on a theme, 4 items `aaaaa bbbb ccc dd` where string length makes a difference:

* **IN** =\> **OUT**
* `4 ccc dd aaaaa bbbb` =\> `ccc L dd L`
* `4 bbbb aaaaa dd ccc` =\> `bbbb D dd D`
* `4 bbbb dd aaaaa ccc` =\> `dd L bbbb D`
* `4 ccc aaaaa dd bbbb` =\> `ccc L dd L`
* `4 ccc dd bbbb aaaaa` =\> `dd F R`
* `4 dd bbbb ccc aaaaa` =\> `ccc R D`
* `4 dd ccc aaaaa bbbb` =\> `bbbb R D`

# Answer
> 2 votes
**Python 2 - ~~593~~ 521**

It's very brute-force with some efficiencies so it would actually finish. The 6-item list I'm testing with is taking around 5 seconds on my laptop.

```
$ time echo 5 xx aa dd bb ee cc | python order.py
dd L ee L xx L

real    0m4.444s
user    0m4.388s
sys 0m0.051s

```

Note that I'm ignoring the number in the input. I find it useless.

```
import sys
def d(l,s,o,f):
 p=len(o)
 tl=tuple(l)
 if tl in s and p>=len(s[tl]) or f and p>=len(f):
  return
 if l==sorted(l):
  return o if not f or p<len(f) else None
 s[tl]=o
 x=d(l[::-1],s,o+[l[-1]+' R'],f)or f
 for n,i in enumerate(l):
  for j,k in ([(l[:n]+[l[n+1],l[n]]+l[n+2:],'D'),(l[:n]+l[n+1:]+[l[n]],'L')]if(n!=len(l)-1)else[])+([(l[:n-1]+[l[n-1],l[n]]+l[n+1:],'U'),([l[n]]+l[:n]+l[n+1:],'F')]if(n!=0)else[]):
   x=d(j,s,(o+[i+' '+k]),x)or x
 return x
print ' '.join(d(sys.stdin.read().split()[1:],{},[],[]))

```

Ugh, I just realized I'm not handling multiple operations on the same value correctly. I'll try to fix that.

# Answer
> 0 votes
# Ruby 2.0

With the operator set \[U,D,F,L\], the fewest number of string selects to sort the list is the number of items in the list minus the longest common subsequence. To add the R operator, just reverse the string and apply the same rule. Unfortunately, minimizing string selects is not the same as minimizing the number of operations. For example, for an input of `8 dd ww aa bb cc xx yy zz`, the correct answer is `ww D D D dd D D D`, but the fewest number of operations (that meets the other criteria in the question) would be `cc F bb F aa F`. This means that a much larger portion of the set of possible sort paths needs to be explored.

This solution uses a depth-first search strategy and alpha-beta pruning. It's important to lower the alpha value rapidly to minimize the search depth, otherwise the search tree explodes exponential. E.g. to determine the sort path with the minimum score for OP's introductory example, sorting months in calendar order to lexical order, will probably take a few decades with this program's current scoring method. The program finds the minimum number of string selects, 8, very quickly. Unfortunately, that still leaves an enormous tree to walk through.

I'm using gnome sort as my scoring function because:

1. it's simple to understand and modify
2. the scoring *usually* converges to the optimal alpha quickly
3. this implementation is faster than my LCS function implementation
4. it will golf better than the LCS function

Number 4 would be sufficient. Everything else is a bonus.

For a depth-first search, the order in which operations are explored has a significant impact on the search time. Since any non-empty set of N items can be sorted with ≤ N-1 F(irst) or L(ast) operations, those operations are tried first.

```
# gnome sort
def gnomeSort(a)
    selects = 0
    previous = nil
    i = 1
    while i < a.size
        if a[i-1] <= a[i]
            # the array a[0..i] is sorted
            i += 1      # take another bite
        else
            if a[i] != previous
                previous = a[i]
                selects += 1
            end
            a[i], a[i-1] = a[i-1], a[i]
            if (i > 1)
                i -= 1
            end
        end
    end
    return selects
end
def score(a)
    return gnomeSort(a.dup)
end

# squeeze out unnecessary operands
def consolidate(a)
    # separate operands and operators
    x = []                      # operands
    f = []                      # operators
    a.each_slice(2) { |a,b|
        x << a
        f << b
    }
    n = x.size                  # number of (operand operator) pairs
    if n>=2
        # replace all R operands with the lexically lower operand
        #   from the right or left
        f.each_with_index{|v,i|
            if v=='R'
                leftOperand = x[i-1]
                rightOperand = x[i+1]
                # handle left & right edge cases
                leftOperand = rightOperand.succ  if i==0
                rightOperand = leftOperand.succ  if i>=n-1
                x[i] = [leftOperand, rightOperand].min
            end
        }

        # replace repeated operands with <nil>
        x = x.chunk{|e|e}.map{|v|v[1].fill(nil,1)}.flatten
    end
    return [x, f]
end

@solutions = []
@operation = []
@operation[3] = ->(a, i) {
        # swap a[i] and a[i-1]
        return nil  if i<1 || i>=a.size
        v = a[i]
        a[i-1], a[i] = a[i], a[i-1]
        return [ v, 'U' ]
    }
@operation[0] = ->(a, i) {
        # move a[i] after a.last
        return nil  if i+1>=a.size
        a.push(v=a.delete_at(i))
        return [ v, 'L' ]
    }
@operation[4] = ->(a, i) {
        # reverse the whole array
        v = a[i]
        a.reverse!
        return [ v, 'R' ]
    }
@operation[1] = ->(a, i) {
        # move a[i] before a.first
        return nil  if i<=0
        a.unshift(v=a.delete_at(i))
        return [ v, 'F' ]
    }
@operation[2] = ->(a, i) {
        # swap a[i] and a[i+1]
        return nil  if i<0 || i+1>=a.size
        v = a[i]
        a[i], a[i+1] = a[i+1], a[i]
        return [ v, 'D' ]
    }

def alphaSort(depth, a, selected, selects, sortPath)
  depth += 1
  return  if selects > @alpha
  return  if selects>@alpha || selects+depth>a.size+1
  if a.each_cons(2).all?{ |x, y| x <= y }
    # found a sort path
    @alpha = selects
    @solutions << sortPath.flatten.compact
  else
    selectsFromHere = score(a)
    if @alpha > selects+selectsFromHere
      @alpha = selects+selectsFromHere
    else
    end
    @operation.each do |op|
      a.each_index do |i|
        b = a.dup
        branch = sortPath.dup << op[b,i]
        alphaSort(depth, b, a[i], selects+(selected==a[i] ? 0 : 1), branch)
      end
    end
  end
end

#       input
a = ARGF.read.scan(/\w+/m)      # alternative, $*[0].scan(/\w+/m)
a.shift                         # ignore the item count

#       depth-first search of sort operations
@alpha = [a.size-1, score(a), score(a.reverse)+1].min + 1
alphaSort(0, a, nil, 0, [])

#       winnow the set of solutions
# determine the minimum number of string selects to solve
# short-circuit if selects to solve is 0 (already sorted)
@solutions.map!{|v|consolidate v}
minSelects = @solutions.map{|v|v[0].compact.size}.min
if !minSelects
    puts
    exit
end
# keep only solutions with the minimum number of string selects
@solutions.reject!{ |v| v[0].compact.size > minSelects }

# determine the minimum number of moves in the remaining solutions
minMoves = @solutions.map{|v|v[1].size}.min
# keep only solutions with the minimum number of moves
@solutions.reject!{ |v| v[1].size > minMoves }

#       beauty contest
# turn into strings
solutions = @solutions.map{|v|v[0].zip(v[1]).flatten.compact*' '}
# keep the shortest strings
minLength = solutions.map{|v|v.size}.min
solutions.reject!{ |v| v.size > minLength }
# print the string that "that comes first alphabetically"
puts solutions.sort.first

```

It passes this perl TAP test suite:

```
use strict;
use warnings;

use Test::More qw(no_plan);
#use Test::More tests => 61;

#       solution executable
my $solver = 'ruby2.0 sortshort.rb';
my $nonTrivial = 1;

#       "happy" path

#       examples from OP
is( `echo 2 zz abc | $solver 2>&1`, "zz D\n", 'OP example #1');
is( `echo 3 cc bb aa | $solver 2>&1`, "aa R\n", 'OP example #2');
is( `echo 4 abc def cd ccc | $solver 2>&1`, "abc L R\n", 'OP example #3');
is( `echo 6 rr mm nn oo qq pp | $solver 2>&1`, "pp U rr L\n", 'OP example #4');

# example from bizangles
is( `echo 6 xx aa dd bb ee cc | $solver 2>&1`, "dd L ee L xx L\n", 'wascally wabbit, challenges deep diver (from bizangles)');

SKIP: {
  skip('non-trivial tests', 2)  unless $nonTrivial;

  # 7 item example; bizangles' python solution (circa 2014-08-22) requires higher sys.setrecursionlimit() and takes about 5 minutes
  is( `echo 7 aa bb ee cc dd ff gg | $solver 2>&1`, "ee D D\n", 'shallow');

  # minimizing the number of selects scores better than minimizing moves
  # minimizing moves                =>  cc F bb F aa F
  # minimizing selects              =>  dd D D D D ww D D D D,  ww D D D dd D D D,  ww L U U U dd D D D,  etc.
  # minimizing selects, then moves  =>  ww D D D dd D D D
  is( `echo 8 dd ww aa bb cc xx yy zz | $solver 2>&1`, "ww D D D dd D D D\n", 'joker, minimize selects before moves');
}

#       exhaustive variations on a theme with 1 item ["aa"]
is( `echo 1 aa | $solver 2>&1`, "\n", 'permutations of 1, #1');

#       exhaustive variations on a theme with 2 items ["ab", "c"]
is( `echo 2 ab c | $solver 2>&1`, "\n", 'permutations of 2, #1');
# test OP's requirement that a string be selected before reverse operation
is( `echo 2 c ab | $solver 2>&1`, "c D\n", 'permutations of 2, #2');

#       exhaustive variations on a theme with 3 items ["five", "four", "three"]
is( `echo 3 five four three | $solver 2>&1`, "\n", 'permutations of 3, #1');
is( `echo 3 five three four | $solver 2>&1`, "four U\n", 'permutations of 3, #2');
is( `echo 3 four five three | $solver 2>&1`, "five F\n", 'permutations of 3, #3');
is( `echo 3 four three five | $solver 2>&1`, "five F\n", 'permutations of 3, #4');
is( `echo 3 three five four | $solver 2>&1`, "three L\n", 'permutations of 3, #5');
is( `echo 3 three four five | $solver 2>&1`, "five R\n", 'permutations of 3, #6');

#       selected variations on a theme with 5 items ["aa", "bb", "cc", "dd", "ee"]
is( `echo 5 aa bb cc dd ee | $solver 2>&1`, "\n", 'permutations of 5, #1, already sorted');
# two sort paths of length 1
is( `echo 5 aa bb cc ee dd | $solver 2>&1`, "dd U\n", 'permutations of 5, #2, single U or D');
is( `echo 5 aa bb ee cc dd | $solver 2>&1`, "ee L\n", 'permutations of 5, #4, single L');
is( `echo 5 bb cc aa dd ee | $solver 2>&1`, "aa F\n", 'permutations of 5, #31, single F');
is( `echo 5 ee dd cc bb aa | $solver 2>&1`, "aa R\n", 'permutations of 5, #120, reverse sorted');

#       exhaustive variations on a theme with 4 items ["aa", "bb", "cc", "dd"]
# sort paths of length 0
is( `echo 4 aa bb cc dd | $solver 2>&1`, "\n", 'permutations of 4, #1');
# sort paths of length 1
is( `echo 4 aa bb dd cc | $solver 2>&1`, "cc U\n", 'permutations of 4, #2');
is( `echo 4 aa cc bb dd | $solver 2>&1`, "bb U\n", 'permutations of 4, #3');
is( `echo 4 aa dd bb cc | $solver 2>&1`, "dd L\n", 'permutations of 4, #5');
is( `echo 4 bb aa cc dd | $solver 2>&1`, "aa F\n", 'permutations of 4, #7');
is( `echo 4 bb cc aa dd | $solver 2>&1`, "aa F\n", 'permutations of 4, #9');
is( `echo 4 bb cc dd aa | $solver 2>&1`, "aa F\n", 'permutations of 4, #10');
is( `echo 4 dd aa bb cc | $solver 2>&1`, "dd L\n", 'permutations of 4, #19');
is( `echo 4 dd cc bb aa | $solver 2>&1`, "aa R\n", 'permutations of 4, #24');

# sort paths of length 2
is( `echo 4 aa cc dd bb | $solver 2>&1`, "bb F D\n", 'permutations of 4, #4');
is( `echo 4 aa dd cc bb | $solver 2>&1`, "aa L R\n", 'permutations of 4, #6');
is( `echo 4 bb aa dd cc | $solver 2>&1`, "aa F cc U\n", 'permutations of 4, #8');
is( `echo 4 bb dd aa cc | $solver 2>&1`, "aa F cc U\n", 'permutations of 4, #11');
is( `echo 4 bb dd cc aa | $solver 2>&1`, "bb D D R\n", 'permutations of 4, #12');
is( `echo 4 cc aa bb dd | $solver 2>&1`, "cc D D\n", 'permutations of 4, #13');
is( `echo 4 cc aa dd bb | $solver 2>&1`, "bb F aa F\n", 'permutations of 4, #14');
is( `echo 4 cc bb aa dd | $solver 2>&1`, "dd F R\n", 'permutations of 4, #15');
is( `echo 4 cc bb dd aa | $solver 2>&1`, "dd F R\n", 'permutations of 4, #16');
is( `echo 4 cc dd aa bb | $solver 2>&1`, "bb F aa F\n", 'permutations of 4, #17');
is( `echo 4 cc dd bb aa | $solver 2>&1`, "cc D R\n", 'permutations of 4, #18');
is( `echo 4 dd aa cc bb | $solver 2>&1`, "aa L R\n", 'permutations of 4, #20');
is( `echo 4 dd bb aa cc | $solver 2>&1`, "cc F D R\n", 'permutations of 4, #21');
is( `echo 4 dd bb cc aa | $solver 2>&1`, "bb D R\n", 'permutations of 4, #22');
is( `echo 4 dd cc aa bb | $solver 2>&1`, "aa D R\n", 'permutations of 4, #23');

#       variations on a theme with 4 items ["aaaaa", "bbbb", "ccc", "dd"]
# force choice by string length
is( `echo 4 ccc dd aaaaa bbbb | $solver 2>&1`, "ccc L dd L\n", 'permutations of 4, #17');
is( `echo 4 dd bbbb aaaaa ccc | $solver 2>&1`, "ccc F D R\n", 'permutations of 4, #21');
is( `echo 4 bbbb aaaaa dd ccc | $solver 2>&1`, "bbbb D dd D\n", 'permutations of 4, #8');
is( `echo 4 bbbb dd aaaaa ccc | $solver 2>&1`, "dd L bbbb D\n", 'permutations of 4, #11');
is( `echo 4 ccc aaaaa dd bbbb | $solver 2>&1`, "ccc L dd L\n", 'permutations of 4, #14');
is( `echo 4 ccc dd bbbb aaaaa | $solver 2>&1`, "dd F R\n", 'permutations of 4, #18');
is( `echo 4 dd aaaaa ccc bbbb | $solver 2>&1`, "aaaaa L R\n", 'permutations of 4, #20');
is( `echo 4 dd bbbb ccc aaaaa | $solver 2>&1`, "ccc R D\n", 'permutations of 4, #22');
is( `echo 4 dd ccc aaaaa bbbb | $solver 2>&1`, "bbbb R D\n", 'permutations of 4, #23');

# identical items in list
is( `echo 2 aa aa | $solver 2>&1`, "\n", '1 repeat #1');
is( `echo 3 aa aa bb | $solver 2>&1`, "\n", '1 repeat #2');
is( `echo 3 aa bb aa | $solver 2>&1`, "aa F\n", '1 repeat #3');
is( `echo 3 bb aa aa | $solver 2>&1`, "aa R\n", '1 repeat #4');
is( `echo 4 aa cc bb aa| $solver 2>&1`, "aa L R\n", '1 repeat #5');
is( `echo 5 cc bb aa bb cc | $solver 2>&1`, "aa F cc L\n", '2 repeats');

#       "sad" path

# not explicitly excluded, so cover this case
#       exhaustive variations on a theme with 0 items []
is( `echo 0 | $solver 2>&1`, "\n", 'permutations of 0, #1');

#       "bad" path
# none!

exit 0;

```

---
Tags: code-golf, sorting
---