# Question
Title: Create an array of unique ints in a set range
***Goal:***

Write a piece of code that produces a array containing *all* integer values in a set range in random order (upper and lower bounds included).
Use any language you like, but use as little built-in functions as possible (ie PHP's `array_shuffle` should be avoided)

***Rules:***

* All ints in the range must be used once, and only once
* The range can be negative, or positive
* When using JavaScript: ECMAScript6 features are to be avoided
* If you choose to write a function the `function(params){` and closing `}` needn't be counted. Bonus points for clever argument validation/normalization if you do write a function
* Aliases like `m = Math;` or `Array.prototype.p = [].push;` will be counted, using closures/functions, passing `Math` as an argument will be counted as `<argName>=Math;`

***Benchmark:***

As a starting point or target: here's a snippet that meets all of the criteria apart from the randomness. It's approx. 50 bytes long (depending on `v`'s value). That would be a nice target to hit:

```
for(l=3,a=[v=12],i=v>0?-1:1;(v+=i)!=l+i;)a.push(v)

```

Caveats: if `l` is bigger than `v`, the code fails.

# Answer
## APL, 18

```
{(⍺⌊⍵)-1-?⍨1+|⍺-⍵}

```

Takes upper/lower bounds as left/right argument. Works for any bounds, also reversed bounds. Can be shortened to 13 characters if the assumption l\<=u can be made:

```
{⍺-1-?⍨⍵-⍺-1}

```

Try
> 1 votes

# Answer
## GolfScript (26 bytes)

```
~)1$-:x,\{+}+%{;x.*rand}$`

```

Online demo

Could be slightly shorter but at the cost of worse randomisation. By picking random numbers up to the square of the size of the range I come close enough IMO to avoiding collisions.
> 0 votes

# Answer
## JavaScript, 73 bytes

```
for(i=l,s=[];i<=u;)s[i-l]=i++;s.sort(function(){return Math.random()<.5})

```

Assumes `l` and `u` have the lower and upper bounds resp. and `l<=u`
> 0 votes

# Answer
## CJam, 12 (or 10) bytes

Aannnd, if other languages are allowed, here is an answer in CJam

```
{$~1$-),f+mr`}:F;

```

This creates a function `F` , thus not counting the `{` and `}:F;`.

Example Usage:

```
{$~1$-),f+mr`}:F;
[7 -2]F

```

Output:

```
[1 -2 6 2 -1 5 7 0 3 4]

```

If I assume that first integer is always less than the second integer, then the code comes down to **10 bytes**:

```
{1$-),f+mr`}:F;

```

Example usage:

```
{1$-),f+mr`}:F;
-2 7F

```

Output:

```
[1 -2 6 2 -1 5 7 0 3 4]

```

Try it online here
> 0 votes

# Answer
## PYTHON, 21

`list(set(range(l,u+1)))`

* assumes `l <= u`

I believe `set` uses the hash value of the arguments for the order of this list it generates. This generates kind-of random ordering, for example with `l, u = 30, 50`, I get `[32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 30, 31]`. I'd say this still counts though.
> 0 votes

# Answer
## J (11 (or 9))

```
f=:>.-?~@>:@|@-

```

This defines a dyadic function, the arguments of which define the start and end of the range. The order of the arguments doesn't matter. (Does this give me bonus points?)

As per the rules, I'm not counting `f=:` as this is part of the function definition (i.e., what would be `function f(params){`...`}`. An anonymous function would be `(>.-?~@>:@|@-)`, where the `()` can be disregarded according to that rule.

If I can assume the *left* argument to be the *upper* bound, and the *right* argument to be the *lower* bound, it can be shortened to **9**:

```
g=:[-?~@>:@-

```

Or, as an anonymous function, `([-?~@>:@-)`.

Test:

```
   f=:>.-?~@>:@|@-
   g=:[-?~@>:@-
   _5 f 10
_1 2 0 _2 _5 3 _4 _3 1 9 4 10 5 7 6 8
   2 f 10
2 10 5 3 8 4 9 7 6
   10 f 2
2 9 4 5 6 10 3 7 8
   10 f _5
_3 9 4 3 2 6 _2 1 5 8 7 _1 _4 10 _5 0
   10 g 2
2 3 4 7 9 5 6 10 8
   10 g _5
1 2 7 4 3 _4 5 8 6 9 _1 10 0 _5 _2 _3

```
> 0 votes

# Answer
## Perl - 19

```
sort{rand>.5}$l..$v

```

Assuming `$l` and `$v` are already defined. If you wanted to make it a function:

```
sub random_array {
    sort{rand>.5}$_[0].._$[1]
}

```

You can try it with:

```
perl -E'$,=",";$l=1; $v=15; say sort{rand>.5}$l..$v'

```

or

```
perl -E'say random_array(0,5);sub random_array{sort{rand>.5}$_[0]..$_[1]}'

```
> 0 votes

---
Tags: code-golf, random, array
---


title: GPS: Golfed Positioning System

text:
# Question
Title: GPS: Golfed Positioning System
Your mission, should you choose to accept it, is to write code for a GPS receiver.

## Input

* The current time, as nanoseconds from the Unix epoch. \[EDIT: This is optional, please state whether you require it\]
* Four satellite signals, in the following format:
    + The time the signal was sent, as nanoseconds from the Unix epoch. You must be able to handle dates up to and including 2020.
    + The location of the satellite, as Cartesian coordinates, in metres. You must be able to handle values that fit into a signed 32-bit integer (-2,147,483,648 to 2,147,483,647). Only integer coordinates will be given. You may assume valid input (i.e. your position can be calculated)

Input can be provided from command-line arguments, standard input or equivalent, but not from a variable. The input can have any separator characters in it; please specify what your input format is.

## Output

The coordinates of your receiver, to the nearest 1000 metres, using 299,792,458 m/s as the speed of light. Again, I will be lenient with the output format: any separators are acceptable.

## Example

**Input**

```
1412349052664203400
[1412349052692915310,2267943, 13318342, 0]
[1412349052698278110,-3757960, 3500627, 0]
[1412349052691548521,4425976, -1533193, 3469445]
[1412349052687888295,10622179, 11246951, 84184]

```

**Output**

```
(6223615, 5673496, 0)

```

I have made a GeoGebra notebook for this example. Please excuse my extremely sloppy GeoGebra skills.

## How GPS Works

Because the speed of light is finite, there will be a difference between your current time and the time the satellite sent the signal.

1. Use the difference to calculate the distance to the satellite, *d*.
2. You are clearly located somewhere on the surface of a sphere, centered on the satellite, with radius *d*.
3. Once you have two satellites and two spheres, you have to be located somewhere on the intersection of the two sphere surfaces, which is a circle.
4. Adding another satellite reduces the possible positions to just two points, where all three sphere surfaces intersect.
5. The fourth satellite allows you to decide on a specific one of these points. Your task is to calculate the location of this point, where all four spheres intersect. Since you assume valid input, such a point does exist.

## Rules

# Answer
> 2 votes
# MatLab/Octave (164)

I assumed the values to be saved in variables. As I said the posed problem seems to result in something about 200 to 300m off in the z coordinate compared to the given solution so this entry does not work within the 100m precision assuming the given test case is correct.

### How it works

You can interpret your position as the intersectionpoint of four spheres, since you can calculate the distance to each sattelite by the runtime. The points `[x,y,z]` on a sphere with center `[x,y,z]` and radius `r` can be written as an equation (so 4 satelites = 4 equations):

```
(x-x0)^2 + (y-y0)^2 + (z-z0)^2 = r^2

```

Or when expanded / transformed:

```
-2*x0*x -2*y0*y -2*z0*z = r^2 - x0^2 - y0^2 - z0^2 - x^2 - y^2 - z^2

```

As you have 4 equations that look like that you can substract one from the other three, which eliminates the `x^2+y^2+z^2` and get a system of 3 linear equations that can easily be solved for `x,y,z`.

But 3 intersecting spheres would result in two possible points, so a fourth is only needed for choosing the right one of those two points. But if the intersectionpoint of the first three is not exactly on the fourth sphere you cannot get an accurate answer.

Normally for gps you have the earth as fourth sphere, so three satelites could give you a line on which your current position must be (when the current exact time is unknonw). The line intersected with the earth surface results in only two possible points. So by comparing the different timestamps you could estimate on which side of the earth you are.

### Code

```
%input
1412349052664203400

[1412349052692915310,2267943, 13318342, 0;
1412349052698278110,-3757960, 3500627, 0;
1412349052691548521,4425976, -1533193, 3469445;
1412349052687888295,10622179, 11246951, 84184]

%actual code
t=input('');d=input('');
c=299792458e-9;
p=d(:,2:4);
r=(d(:,1)-t)*c;
o=ones(3,1);
q=p(1:3,:)-o*p(4,:);
b=p(1:3,:).^2-o*p(4,:).^2;
s=r(1:3).^2-o*r(4).^2;
(-2*q)\(s-sum(b,2))

```

Output:

```
  1.0e+006 *

   6.223565252948585
   5.673559409007432
   0.000291267494418

```

---
Tags: code-golf, geometry, 3d
---


title: Your car only turns right!

text:
# Question
Title: Your car only turns right!
### Introduction

You have the misfortune of being stuck in a runaway car on an obstacle course. All of the car's features are non-responsive, save for the steering system, which is damaged. It can drive straight, or it can turn right. Can the car be guided to safety?

### Mechanics

Your car begins in the upper-left corner of an 8x8 map, and is trying to get to safety in the lower-right corner. The car has an orientation (initially to the right), measured in 90-degree increments. The car can perform one of two actions:

1. Drive one square forward, or
2. Turn 90 degrees clockwise, then drive one square forward

Note that the car is unable to turn sharply enough to perform a 180-degree turn on a single square.

Some of the squares are obstacles. If the car enters an obstacle square, it crashes. Everything outside the 8x8 course is assumed to be obstacles, so driving off the course is equivalent to crashing.

The lower-right square is the safe square, which allows the car to escape the obstacle course. The starting square and safe square are assumed not to be obstacles.

### Task

You must write a program or function which takes as its input an 8x8 array (matrix, list of lists, etc.), representing the obstacle course. The program returns or prints a Boolean, or something similarly truthy. If it's possible for the car to make it to the safe square without crashing (i.e., if the map is solvable), the output is `True`, otherwise, it's `False`.

### Scoring

Standard code golf rules - the winner is the code with the fewest bytes.

Bonuses:

* If, for a solvable map, your code outputs a valid series of driver inputs which guide the car to the safe square, deduct 10 percentage points from your score. An example output format might be `SRSSR` (indicating Straight, Right, Straight, Straight, Right). This output would replace the standard `True` output.
* If, for an unsolvable map, your code's output distinguishes between situations where a crash is unavoidable, and situations where it's possible to drive around the obstacle course forever, deduct 10 percentage points from your score. An example output might be `Crash` if a crash is unavoidable, or `Stuck` if the car is stuck in the obstacle course forever. These outputs would replace the standard `False` output for an unsolvable map.

### Example

If the program is given an 8x8 array such as this:

```
[[0, 0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0],
 [1, 1, 0, 0, 0, 0, 0, 0],
 [0, 1, 0, 1, 0, 0, 0, 0],
 [0, 0, 1, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 1, 0],
 [0, 0, 0, 0, 0, 0, 1, 0],
 [0, 1, 1, 0, 0, 0, 1, 0]]

```

It would be interpreted as a map like this, with black squares indicating obstacles:

And a possible solution might be:

Since a solution exists, the program should return/print `True` for this map. The sequence of moves shown here is `SSSSRSRRRSRSSRRRSSRSSS`.

# Answer
> 17 votes
# JavaScript (ES6) - 122 124 148 162 172 178 187 190 193 208 bytes

Many thanks to Optimizer and DocMax for helpful suggestions on how to improve this code:

```
F=a=>(D=(x,y,d)=>!D[i=[x,y,d]]&&(D[i]=1,x-=~d%2,y-=~-~d%2,x*y==49||!((x|y)&8||a[y][x])&&(D(x,y,d)||D(x,y,~-d%4))),D(-1,0))

```

Returns `true` (truthy) for solvable and `false` (falsy) for unsolvable.

Works only in Firefox as of today becasue of JavaScript 1.7 features.

**Test Board**

# Answer
> 9 votes
## Python 2 - 123 ~~125 133 146 148 150 154 160~~

`True` on success, `False` on failure.

```
def f(h=1,v=0,b=0,x=0,y=0,c=[]):s=x,y,h,v;a=b,x+h,y+v,c+[s];return(s in c)==(x|y)&8==b[y][x]<(x&y>6or f(h,v,*a)|f(-v,h,*a))

```

You must supply input like `f(b=var_containing_board)`.

### Lambda version - 154

Returns `0` (falsy) for failure, `True` for success.

```
F=lambda b,x=0,y=0,h=1,v=0,c=[]:0if[x,y,h,v]in c or x|y>7or x|y<0 or b[y][x]else x&y==7or F(b,x+h,y+v,h,v,c+[[x,y,h,v]])or F(b,x+h,y+v,-v,h,c+[[x,y,h,v]])

```

Thanks to Will and Brandon for making the function shorter than the lambda. Also for adding more horizontal scrolling :D

Thanks to xnor for superior bit-bashing and logic!

Edit note: I am reasonably confident that `b[y][x]` will never be executed when going out of range. Since we are outside of the board, the history check `s in c` will be `False`. Then the boundary check `(x|y)&8` will be `8`. Then python will not even check the last value of `==` because the first two are already different.

# Answer
> 9 votes
# C (GNU-C), 163 bytes * 0.9 = 146.7

#C (GNU-C), 186 bytes * 0.9 = 167.4

My new version uses a signed rather than unsigned integer. Earlier I was afraid of signed right shift, but I realized since the sign bit is the goal square, it doesn't matter what happens after that.

The function takes an array of bits (ones represent blocked squares) in the form of a 64-bit integer. The bits are arranged least to most significant in the same way you would read a book. It returns -1 for a crash, 0 for driving forever, or 1 for escaping to the bottom right corner.

```
g(long long o) {
    typeof(o) a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;
    for( ;i--;d = D<<8&~o)
        a |= D = d|r,
        r = (r|u)*2&~M&~o,
        u = (u|l)>>8&~o,
        l = ((l|d)&~M)/2&~o;
    return a<0?:-!(d|r|u|l);
}

```

**Test program**

```
f(long long o){typeof(o)a=0,i=255,r=1,u=0,l=0,d=0,M=~0LLU/i,D;for(;i--;d=D<<8&~o)a|=D=d|r,r=(r|u)*2&~M&~o,u=(u|l)>>8&~o,l=((l|d)&~M)/2&~o;return a<0?:-!(d|r|u|l);}
{
    char* s[] = {"Crash", "Stuck", "Escape"};
    #define P(x) puts(s[f(x)+1])
    L ex = 0x4640500C0A034020;
    P(ex);
    L blocked = 0x4040404040404040;
    P(blocked);

    L dead = 0x10002;
    P(dead);

    return 0;
}

```

**Output**

```
Escape
Stuck
Crash

```

Python array-to-hex converter:

```
a2b=lambda(A):"0x%X"%sum(A[i/8][i%8]<<i for i in range(64))

```

# Answer
> 6 votes
# Python, 187 ~~213~~

## 207 chars, 10% bonus for printing path

```
b=map(ord," "*9+" ".join("".join("o "[i]for i in j)for j in input())+" "*9)
def r(p,d,s):
 p+=(1,9,-1,-9)[d]
 if b[p]&1<<d:b[p]^=1<<d;return(s+"S")*(p==79)or r(p,d,s+"S")or r(p,(d+1)%4,s+"R")
print r(8,0,"")

```

On the test input it finds a slightly different path: `SSSSRSRSRRSSRSSRRSRSSRSSSSS`

The general approach is to first turn the input into a spaces and `o`s. Spaces have a hex of `20`, so all four lower bits are unset. `o` has a hex of `6F`, so the low four bits are all set.

A border of `o`s is placed around the board so we don't have to worry about bad indices.

As we walk over the board, we use the bits in each tile to see if we are allowed to pass when coming from that side. In this way, we avoid infinite loops. Its not enough to have a single boolean per tile, as your exit direction depends on your entry direction, so tiles can be visited twice.

We then do a recursive search for a safe path.

# Answer
> 6 votes
# Javascript - ~~270 - 20% = 216~~ 262 - 20% = 210 bytes

Since there ought to be at least one solution that earns both bonuses (and doesn't lead to a ridiculous stack depth ;)...

Minified:

```
V=I=>{n=[N=[0,0,0]];v={};v[N]='';O='C';for(S='';n[0];){m=[];n.map(h=>{[x,y,d]=h;D=i=>[1,0,-1,0][d+i&3];p=v[h];for(j=2;j--;){O=v[c=[X=x+D(j),Y=y+D(3-3*j)),d+j&3]]?'K':O;J=X|Y;J<0||J>7||I[Y][X]||v[c]?O:(m.push(c),v[c]=p+'SR'[j])}S=(x&y)>6?p:S});n=m;}return S||O;};

```

Expanded:

```
V = I => {
    n = [N=[0,0,0]];
    v = {};
    v[N] = '';
    O = 'C';

    for( S = ''; n[0]; ) {
        m = [];
        n.map( h => {
            [x,y,d] = h;
            D = i => [1,0,-1,0][d+i&3];
            p = v[h];
            for( j = 2; j--; ) {
                O = v[c = [X = x+D(j),Y = y+D(3-3*j),d+j&3]] ? 'K' : O;
                J = X|Y;
                J<0 || J>7 || I[Y][X] || v[c] ? O : (
                    m.push( c ),
                    v[c] = p + 'SR'[j]
                );
            }

            S = (x&y) > 6 ? p : S;
        } );
        n = m;
    }
    return S || O;
};

```

`v` is a hashtable with keys that are state triples `(x,y,d)` corresponding to (x,y) coordinate and direction of entry `d`. Each key has an associated value that is the string of `S` (straight) and `R` (turn right) moves required to reach the state represented by the key.

The code also maintains a stack of triples (in variable `n`) that have not been processed yet. The stack initially contains only the triple (0,0,0), corresponding to the state where the car faces right in the (0,0) cell. In the outer loop, `for( S = ... )`, the routine checks if any unprocessed triples remain. If so, it runs each unprocessed triple through the inner loop, `n.map( ...`.

The inner loop does five things:

1. computes the two possible moves (driving straight, turning right) out of the current state
2. if either of these moves leads to a state already registered in the hashtable, it is ignored for further processing. We flag the FALSE output as `K` (stuck), however, since we have found at least one loop where the car can continue to circle forever without crashing.
3. if a state is legal and novel, it is added to the hashtable (`v`) and to the stack of unprocessed triples (`m`) for the next pass of the outer loop
4. when the new state is registered in `v`, its value is set to the value of the originating state (the sequence of moves) plus `R` or `S` based on the current move
5. if `x` and `y` are `7`, the value of the originating state (the sequence of moves taken to reach the originating state) is copied to `S`, since this move sequence is a solution to the problem

After the inner loop terminates, `n` (the stack) is replaced by `m` (the new stack).

After the outer loop terminates (no new states were reached), the function returns its output. If the (7,7) cell was reached, `S` will contain a sequence of moves leading to this cell, and this is outputted. If the cell was not reached, `S` will be the empty string, and the routine falls through to outputting `O`, which will contain `K` (stuck) if and only if a loop was found, or `C` (crash) if the car will inevitably crash.

# Answer
> 4 votes
## Python 339 - 10% = 305 bytes

I used a recursive depth-first search, which is terminated early on success via `exit`. Also printing path on success in the form of `00001010101010101010101110100111001000`, `0` for straight, `1` for right. The answer will be longer than optimal, since it is depth-first. I'm sure some optimizations to the algorithm could bring the byte count down quite a bit.

```
b=input()
D=[(-1,0),(0,-1),(1,0),(0,1)]
def a(l):
 x,y=0,0
 v=2
 for d in l:
  if d=='1':v=(v+1) % 4
  x+=D[v][0]
  y+=D[v][1]
  if x<0 or x>7 or y<0 or y>7:return 0,x,y
  if b[y][x]:return -1,x,y
 return 1,x,y
def c(l):
 if len(l) < 39:
  t,x,y=a(l)
  if t==1:
   if (x,y)==(7,7):
    print l;exit(0)
   c(l+"0")
   c(l+"1")
c("")
print 0

```

---
Tags: code-golf, graph-theory, path-finding, decision-problem
---


title: Coating Every Pancake

text:
# Question
Title: Coating Every Pancake
You have a stack of pancakes on a plate with a glob of syrup on top so thick it can't run down the sides. You won't be happy to eat until both faces of each pancake have at least touched the syrup, but right now only one face of the top pancake has.

You know that the syrup will never soak through even one pancake, but it can be transferred indefinitely via face-to-face contact between two pancakes. Once a face of a pancake has touched syrup it is considered coated in syrup forever, and will make any non-syrup coated face that touches it syrup coated as well. It is possible to transfer syrup to and from the top side of the plate as well.

You proceed to coat every pancake face with syrup by inserting a spatula below one or more pancakes and flipping them all over, exactly as is done in pancake sorting. (Unfortunately this spatula is syrup-resistant, and does not help to distribute the syrup by touching pancake faces.) Sadly you lose track of which pancake faces have touched syrup but you do remember the flips you have made.

*Given your past flips can you determine if your pancakes are all coated with syrup yet?*

# Challenge

Write a program that takes in a positive integer N for the number of pancakes, and a list of positive integers (all \<= N) for the flips you have made so far. Each number in the list represents the number of pancakes that were flipped. Output a truthy value if the pancakes are done being coated and a falsy value if not. (truthy/falsy definition)

The input should come from stdin or the command line and the output should go to stdout (or closest alternatives). It's fine if your input needs a little extra formatting: e.g. `[1, 1, 2, 2]` instead of `1 1 2 2` for the list.

# Examples

Assume N = 2, so we have a stack of two pancakes on a plate, starting with the syrup on top.

If the list is `1 1 2 2`, this means we...

* flip the top pancake - coating the upper face of the bottom pancake
* flip the top again - coating the original bottom face of the top pancake
* flip both - coating the plate
* flip both again - coating the original bottom face of the bottom pancake

Since all four faces are coated the output would be something like `True` or `1`.

If the list is `1 2 2 1`, this means we...

* flip the top pancake - coating the upper face of the bottom pancake
* flip both - coating nothing
* flip both again - coating nothing
* flip the top again - coating the original bottom face of the top pancake

Since the face touching the plate is still syrup-free the output would be something like `False` or `0`.

# Notes

* The flip list may be arbitrarily large and can be empty, in which case the output is falsy.
* The plate acts as a syrup-carrier but it doesn't matter if it gets coated or not. (In fact any flip solution *will* coat the plate because the pancake face it touches must be coated, but regardless.)
* The plate cannot be flipped.
* You can assume these pancakes are unit disks with no sides to speak of, only two opposite faces.

# Scoring

This is code-golf. The shortest solution in bytes wins.

# Answer
# CJam, ~~32~~ ~~30~~ 29 bytes

```
q~2@#2b\{)/(W%)1$0=|@]s:~}/:&

```

Try it online.

### Test cases

```
$ cjam pancakes.cjam <<< '2 [1 1 2 2]'; echo
1
$ cjam pancakes.cjam <<< '2 [1 2 2 1]'; echo
0

```

### How it works

```
q~                            " N, L := eval(input())                                     ";
  2@#2b                       " P := base(2 ** N, 2)                                      ";
       \{                }/   " for F in L:                                               ";
         )/                   "   P := split(P, F + 1)                                    ";
           (W%)               "   T, U, V := P[1:], reverse(P[0])[:-1], reverse(P[-1])[0] ";
               1$0=|          "   V |= U[0]                                               ";
                    @]s:~     "   P := map(eval, str([U, V, T]))                          ";
                           :& " print and(P)                                              ";

```
> 9 votes

# Answer
# Haskell, ~~92~~ ~~90~~ ~~86~~ ~~84~~ ~~114~~ ~~110~~ ~~99~~ 98

the requirement of a full program is so annoying. I wonder why would anyone require this.

```
m(n:s)=all(<1)$foldl(\r@(p:s)n->reverse(take n s)++(p*r!!n):drop n s)[0..n]s
main=readLn>>=print.m

```

this solution works by representing the pile of pancakes by a list of the sides, when adjacent pancakes share the same side. every side is a number, and a side is coated if it has a zero value.

run as:

```
*Main> main
[2,1,1,2,2]
True

```
> 12 votes

# Answer
## Python, 92 bytes

I think this works:

```
s=[1]+[0,0]*input()
for f in input():x=f*2;s[0]=s[x]=s[0]|s[x];s[:x]=s[x-1::-1]
print all(s)

```

It uses a list of pancake faces (plate included) to remember which are coated with syrup. Pancakes are flipped by reversing part of the list, but any syrup is first transferred between the top face and the newly revealed face.

Usage:

```
$ python pancakes.py
2
1, 1, 2, 2
True

```
> 10 votes

# Answer
## Python 2: 75

A simplification of grc's and feersum's solution.

```
n,b=input()
s=[1]+[0]*n
for x in b:s[:x+1]=s[x::-1];s[x]|=s[0]
print all(s)

```

Storing the syrup state of `2*n+1` pancake edges is redundant because touching edges are always the same. This instead remembers the state of each of `n+1` pancake junctions. That way, syrup transfer is automatically accounted for.

The only update needed is to preserve the syrup at the `x` junction when a flip cuts it. This is done by or-ing the post-flip syrup at `0` into `x`.

Taking input twice doesn't affect the character count.

```
s=[1]+[0]*input()
for x in input():s[:x+1]=s[x::-1];s[x]|=s[0]
print all(s)

```
> 8 votes

# Answer
# Python 2, 93 bytes

At first I was going to post my answer, but then grc had already posted a very similar one a minute before. So I tried to come up with some improvements. The only one I could find is to use a lexicographic list comparison instead of `all()`.

Edit: Fixed a mistake introduced by unsuccessfully trying different input methods which doesn't change character count.

```
n,F=input()
L=[1]+2*n*[0]
for f in F:f*=2;L[0]=L[f]=L[0]|L[f];L[:f]=L[~-f::-1]
print[1]*2*n<L

```

Sample input/output:

```
2, [1, 1, 2]

```

```
False

```
> 5 votes

# Answer
## APL, 77

```
∧/⊃{x[1]+←⍺⌷x←⍵⋄(⌽⍺↑x),⍺↓x}/(⌽1+⎕),⊂1,⎕⍴0

```
> 3 votes

# Answer
## Python 2, 107

```
d=[1]+[0,0]*input()
for i in input():n=2*i;d[:n]=reversed(d[:n]);d[n]=d[n-1]=d[n]|d[n-1]
print(all(d[:-1]))

```
> 2 votes

# Answer
# Haskell, ~~129~~ 125

```
t(m:l)=all(any(<1).(\i->foldr(\n->foldr($)[].map(n%))[i]l))[0..m]
n%i|i>n=(i:)|i<n=(n-i:)|1>0=(n:).(0:)
main=readLn>>=print.t

```

Probably not completely golfed yet, but it works without manipulating a list of coated sides. Instead, it works its way backwards to figure out whether a given side of a given pancake has ever come in contact with anything that was the top side at the beginning. `foldr` effectively traverses the list of flips backwards, therefore there is no `reverse`.

So here is the algorithm: We map over all relevant sides (`[0..m]`) and make a list of sides that our side inherits syrup from at each step, starting from the back: initially the list is just `[i]`, but with a flip of `n` pancakes, each entry becomes `[n-i]` if `i<n`, `[n,0]` if `i==n`, and `[i]` if `i>n`. The side in question has been coated if and only if the resulting list after all flips contains a `0` (`any (<1)`). `all` does the rest, and `main` converts all this into a runnable program.

The program takes its input from `stdin` in the form of `[n_pancakes, flip1, flip2, flip3, ...]`, terminated by a newline.
> 2 votes

---
Tags: code-golf, stack
---


title: Preprocessing primality

text:
# Question
Title: Preprocessing primality
## The challenge:

Given an integer *N*, *1 \< N \< 2³¹*, write code that uses the C preprocessor to determine whether *N* is prime, and produces a "Hello world" program if N is prime, or an error otherwise. Make the code as short as possible.
It's not very hard, so don't worry that there are so many rules; most of them are boilerplate.

The following sample code (in `example.c`) works for *N \< 100*:

```
#include <stdio.h>
int main() {
#if (N%2!=0 && N%3!=0 && N%5!=0 && N%7!=0) || (2==N || 3==N || 5==N || 7==N)
printf("Hello world!");
#else
Walkmen;
#endif
}

```

23 is prime but 99 is not, so:

```
c:\golf\preprime>gcc -std=c99 -DN=23 example.c

c:\golf\preprime>a
Hello world!
c:\golf\preprime>gcc -std=c99 -DN=99 example.c
example.c: In function 'main':
example.c:6:1: error: 'Walkmen' undeclared (first use in this function)
 Walkmen;
 ^
example.c:6:1: note: each undeclared identifier is reported only once for each function it appears in
c:\golf\preprime>

```

## Rules

* *1 \< N \< 2147483648*
* *N* will be defined in a macro named `N`. `N` will be written using only the characters `0123456789` and will not begin with `0`.
* The code will be compiled with the command `gcc -std=c99 -DN=<number> <filename>.c [-o <outfile>]`
* If *N* is prime, a valid C99 program must be successfully compiled. When executed, the program's output to `stdout` must be precisely `Hello world!` followed by zero or more newlines.
* If *N* is composite, `gcc` must emit a compiler error. A linker error is not acceptable.
* You may not utilize any GCC extensions.
* You may not assume anything about the name of any file.
* Note: It is not allowed to use implicit types or implicit function declarations.
* Neither `gcc` nor any "Hello world" program may take more than 20 seconds to execute on a typical computer.
* Shortest code length in UTF-8 bytes wins.

For reference, my ungolfed implementation is 571 bytes. Happy golfing!

# Answer
> 3 votes
## 441 characters

OK, here is another approach — this time breaking things down into a giant binary tree of tests. I was hoping this could be done recursively, but the C preprocessor doesn't support recursive functions...so I did this as a fallback.

**Algorithm:** This tests `N` for divisibility by 2 and by all odd numbers up to the square root of 2³². (Note: That's a bit of overkill, because it need only test potential divisors up to the square root of 2³¹, but it's easier to stick to powers of 2.)

```
#define A(x) (N%(x)||N==x)
#define B(x) A(x)&A(x+2)&A(x+4)&A(x+6)
#define C(x) B(x)&B(x+8)&B(x+16)&B(x+24)
#define D(x) C(x)&C(x+32)&C(x+64)&C(x+96)
#define E(x) D(x)&D(x+128)&D(x+256)&D(x+384)
#define F(x) E(x)&E(x+512)&E(x+1024)&E(x+1536)
#define G(x) F(x)&F(x+2048)&F(x+4096)&F(x+6144)
#define H(x) G(x)&G(x+8192)&G(x+16384)&G(x+24576)
#include <stdio.h>
int main(){
#if A(2)&H(3)&H(32771)
printf("Hello world!");
#else
Walkmen;
#endif
}

```

**Notes:**

1. The value `32771` is really just `3+32768`.
2. Yes, the parentheses around `x` in `N%(x)` are indeed needed (but not in `N==x`).
3. Compiles as per instructions and obeys rules of output.
4. Elapsed time for each test of `N` (e.g., each invocation of the compiler) is about 1/6 second on my machine.

# Answer
> 3 votes
# boost/preprocessor, 355

```
#ifndef I
#include "boost/preprocessor.hpp"
#include "boost/preprocessor/slot/counter.hpp"
#include "stdio.h"
#define I BOOST_PP_COUNTER
#define F(z,x,d){int a[((x|d<<8)<2||(x|d<<8)==N||N%(x|d<<8))-1];}
int main(){
#include __FILE__
printf("Hello world!");}
#elif I<182
BOOST_PP_REPEAT(256,F,I)
#include BOOST_PP_UPDATE_COUNTER()
#include __FILE__
#endif

```

boost/preprocessor is part of the boost extension to the standard library for preprocessor programming.

We need both the BOOST\_PP\_REPEAT and the BOOST\_PP\_COUNTER + self-include approaches because of the limitations of the system.

gcc only supports a nested include depth of 200, so the counter approach alone is insufficient. BOOST\_PP\_REPEAT is limited to repeating 256 times, so it doesn't work alone either.

With both approaches together we get up to 51200 repetitions; we need only 46340 (sqrt 2^31) to cover all possible primes.

To actually cause compilation failure we need to generate some code whoses validity depends on primality (since we can't chain together an #if if we're using #includes). The easiest way is to declare an array who's length depends on N%i, since negative array lengths produce a gcc compiler error.

As a bonus the number of error messages is equal to the number of factors :).

### Examples

```
$  gcc -std=c99 -DN=24 primes.c
In file included from primes.c:8:
primes.c: In function ‘main’:
primes.c:11: error: size of array ‘a’ is negative
primes.c:11: error: size of array ‘a’ is negative
primes.c:11: error: size of array ‘a’ is negative
primes.c:11: error: size of array ‘a’ is negative
primes.c:11: error: size of array ‘a’ is negative
primes.c:11: error: size of array ‘a’ is negative

$  gcc -std=c99 -DN=23 primes.c && ./a.out
Hello world!

```

---
Tags: code-golf, primes, c
---


title: Chotchkies Restaurant

text:
# Question
Title: Chotchkies Restaurant
Because there isn't enough xkcd on PPCG...

## Challenge

The challenge is the same as above - given a menu and a total price, you need to find what the customer ordered.

The menu will be supplied as a text file in the format:

```
Name:Price
Name:Price

```

The path to the menu file and the total price should be supplied via argv or STDIN. If you wish, the menu may be supplied via STDIN/argv (instead of newlines, separate each item by commas).

The output should be a list of values. If there are multiple answers, output all of them.

# Example

Menu:

```
Burger:12.60
Pepsi:3.50
Lobster Thermidore:33.10
Ice Cream:23.00

```

Total Price: `68.70`

The output is:

```
Burger
Lobster Thermidore
Ice Cream

```

## Winning

The fastest code given an undisclosed problem wins. The speed will be taken five times and averaged.

# Answer
# Python 2 - Naive implementation - 224

Well, let's start with "the most naive algorithm" as some kind of reference solution:

```
import itertools

path = input()
total = input()

with open(path) as f:
    menu = map(lambda l: l.split(':'), f.read().split('\n'))

names, prices = zip(*menu)
prices = map(float, prices)

for i in range(len(menu)):
    for comb in itertools.combinations(range(len(menu)), i):
        if sum(prices[c] for c in comb) == total:
            for i in comb:
                print names[i]

```

**Input:**

```
"data.txt"
68.70

```

**Output:**

```
Burger
Lobster Thermidore
Ice Cream

```

**Complexity:**

```
O(2^N * N)

```

--\> exponential in the number of menu items `N` (of course)

---

**Edit:**

To reflect the new winning criterion I golfed it down quite a bit:

```
from itertools import*
S=str.split
f,t=S(input())
m=[S(l,':')for l in S(open(f).read(),'\n')]
R=range(len(m))
F=float
for i in R:
 for C in combinations(R,i):
  if sum(F(m[c][1])for c in C)==F(t):
   for j in C:print m[j][0]

```

The input format changed to `data.txt 68.70` (both on one line separated with a whitespace).
> 2 votes

---
Tags: math, fastest-code
---


# Question
Title: Build a pair of spies that will throw stones into a river
Recently at the newly released Puzzling.SE, there was a problem about spies throwing stones into a river that was actually quite challenging:

> Two spies must pass each other two secret numbers (one number per spy), unnoticed by their enemies. They have agreed on a method for doing this using only 26 indistinguishable stones in advance.
>
> They meet at a river, where there is a pile of 26 stones. Starting with the first spy, they take turns throwing a group of stones into the river: the first spy throws some number of stones, then the second one, then the first one again...
>
> Each spy must throw at least one stone on his turn, until all the stones are gone.
>
> They observe all throws and diverge when there are no more stones. They keep silence all the time and no information is exchanged except number of stones thrown at each turn.
>
> How can they exchange the numbers successfully if the numbers can be from 1 to M?

Your task is to build a pair of programs, `spy1` and `spy2`, that can solve this problem for the highest possible `M`.

Your programs will each take a number from `1` to your chosen `M` as input. Then, `spy1` will output a number representing the number of stones it throws into the river, which will be input to `spy2` which will also output a number to be input to `spy1`, and so on until the numbers output add up to `26`. At the end of throwing, each program will output the number it believes the other program had, which must match the number that was actually input to the other program.

Your program must work for all possible ordered pairs of numbers `(i, j)` where both `i` and `j` can vary from `1` to `M`.

The program that works for the largest `M` will be the winner, with the first answer to be posted breaking a tie. Additionally, I will award a +100 reputation bounty to the first solution that is proven to work for `M >= 2286`, and +300 to the first solution that is proven to work for `M >= 2535`.

# Answer
## C#, M = 2535

This implements\* the system which I described mathematically on the thread which provoked this contest. I claim the 300 rep bonus. The program self-tests if you run it either without command-line arguments or with `--test` as a command-line argument; for spy 1, run with `--spy1`, and for spy 2 with `--spy2`. In each case it takes the number which I should communicate from stdin, and then does the throws via stdin and stdout.

* Actually, I've found an optimisation which makes a massive difference (from several minutes to generate the decision tree, to less than a second); the tree which it generates is fundamentally the same, but I'm still working on a proof of that. If you want a direct implementation of the system which I described elsewhere, see revision 2, although you might want to backport the extra logging from `Main` and the better inter-thread comms from `TestSpyIO`.

If you want a test case which completes in less than a minute, change `N` to `16` and `M` to `87`.

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace CodeGolf
{
    internal class Puzzle625
    {
        public static void Main(string[] args)
        {
            const int N = 26;
            const int M = 2535;

            var root = BuildDecisionTree(N);

            if (args.Length == 0 || args[0] == "--test")
            {
                DateTime startUtc = DateTime.UtcNow;
                Console.WriteLine("Built decision tree in {0}", DateTime.UtcNow - startUtc);
                startUtc = DateTime.UtcNow;

                int ok = 0;
                int fail = 0;
                for (int i = 1; i <= M; i++)
                {
                    for (int j = 1; j <= M; j++)
                    {
                        if (Test(i, j, root)) ok++;
                        else fail++;
                    }
                    double projectedTimeMillis = (DateTime.UtcNow - startUtc).TotalMilliseconds * M / i;
                    Console.WriteLine("Interim result: ok = {0}, fail = {1}, projected test time {2}", ok, fail, TimeSpan.FromMilliseconds(projectedTimeMillis));
                }
                Console.WriteLine("All tested: ok = {0}, fail = {1}, in {2}", ok, fail, DateTime.UtcNow - startUtc);
                Console.ReadKey();
            }
            else if (args[0] == "--spy1")
            {
                new Spy(new ConsoleIO(), root, true).Run();
            }
            else if (args[0] == "--spy2")
            {
                new Spy(new ConsoleIO(), root, false).Run();
            }
            else
            {
                Console.WriteLine("Usage: Puzzle625.exe [--test|--spy1|--spy2]");
            }
        }

        private static bool Test(int i, int j, Node root)
        {
            TestSpyIO io1 = new TestSpyIO("Spy 1");
            TestSpyIO io2 = new TestSpyIO("Spy 2");
            io1.Partner = io2;
            io2.Partner = io1;

            // HACK! Prime the input
            io2.Output(i);
            io1.Output(j);

            Spy spy1 = new Spy(io1, root, true);
            Spy spy2 = new Spy(io2, root, false);

            Thread th1 = new Thread(spy1.Run);
            Thread th2 = new Thread(spy2.Run);
            th1.Start();
            th2.Start();

            th1.Join();
            th2.Join();

            // Check buffer contents. Spy 2 should output spy 1's value, so it's lurking in io1, and vice versa.
            return io1.Input() == i && io2.Input() == j;
        }

        private static Node BuildDecisionTree(int numStones)
        {
            NodeValue[] trees = new NodeValue[] { NodeValue.Trivial };
            for (int k = 2; k <= numStones; k++)
            {
                int[] prev = trees.Select(nv => nv.Y).ToArray();
                List<int> row = new List<int>(prev);
                int cap = prev.Length;
                for (int i = 1; i <= prev[0]; i++)
                {
                    while (prev[cap - 1] < i) cap--;
                    row.Add(cap);
                }

                int[] next = row.OrderByDescending(x => x).ToArray();
                NodeValue[] nextTrees = new NodeValue[next.Length];
                nextTrees[0] = trees.Last().Reverse();
                for (int i = 1; i < next.Length; i++)
                {
                    int cp = next[i] - 1;
                    nextTrees[i] = trees[cp].Combine(trees[i - prev[cp]]);
                }

                trees = nextTrees;
            }

            NodeValue best = trees.MaxElement(v => Math.Min(v.X, v.Y));
            return BuildDecisionTree(numStones, best, new Dictionary<Pair<int, NodeValue>, Node>());
        }

        private static Node BuildDecisionTree(int numStones, NodeValue val, IDictionary<Pair<int, NodeValue>, Node> cache)
        {
            // Base cases
            // NB We might get passed val null with 0 stones, so we hack around that
            if (numStones == 0) return new Node(NodeValue.Trivial, new Node[0]);

            // Cache
            Pair<int, NodeValue> key = new Pair<int, NodeValue>(numStones, val);
            Node node;
            if (cache.TryGetValue(key, out node)) return node;

            // The pair-of-nodes construction is based on a bijection between
            //     $\prod_{i<k} T_i \cup \{(\infty, 0)\}$
            // and
            //     $(T_{k-1} \cup \{(\infty, 0)\}) \times \prod_{i<k-1} T_i \cup \{(\infty, 0)\}$

            // val.Left represents the element of $T_{k-1} \cup \{(\infty, 0)\}$ (using null for the $(\infty, 0)$)
            // and val.Right represents $\prod_{i<k-1} T_i \cup \{(\infty, 0)\}$ by bijection with $T_{k-1} \cup \{(\infty, 0)\}$.
            // so val.Right.Left represents the element of $T_{k-2}$ and so on.
            // The element of $T_{k-i}$ corresponds to throwing $i$ stones.
            Node[] children = new Node[numStones];
            NodeValue current = val;
            for (int i = 0; i < numStones && current != null; i++)
            {
                children[i] = BuildDecisionTree(numStones - (i + 1), current.Left, cache);
                current = current.Right;
            }
            node = new Node(val, children);

            // Cache
            cache[key] = node;
            return node;
        }

        class Pair<TFirst, TSecond>
        {
            public readonly TFirst X;
            public readonly TSecond Y;

            public Pair(TFirst x, TSecond y)
            {
                this.X = x;
                this.Y = y;
            }

            public override string ToString()
            {
                return string.Format("({0}, {1})", X, Y);
            }

            public override bool Equals(object obj)
            {
                Pair<TFirst, TSecond> other = obj as Pair<TFirst, TSecond>;
                return other != null && object.Equals(other.X, this.X) && object.Equals(other.Y, this.Y);
            }

            public override int GetHashCode()
            {
                return X.GetHashCode() + 37 * Y.GetHashCode();
            }
        }

        class NodeValue : Pair<int, int>
        {
            public readonly NodeValue Left;
            public readonly NodeValue Right;

            public static NodeValue Trivial = new NodeValue(1, 1, null, null);

            private NodeValue(int x, int y, NodeValue left, NodeValue right) : base(x, y)
            {
                this.Left = left;
                this.Right = right;
            }

            public NodeValue Reverse()
            {
                return new NodeValue(Y, X, this, null);
            }

            public NodeValue Combine(NodeValue other)
            {
                return new NodeValue(other.X + Y, Math.Min(other.Y, X), this, other);
            }
        }

        class Node
        {
            public readonly NodeValue Value;
            private readonly Node[] _Children;

            public Node this[int n]
            {
                get { return _Children[n]; }
            }

            public int RemainingStones
            {
                get { return _Children.Length; }
            }

            public Node(NodeValue value, IEnumerable<Node> children)
            {
                this.Value = value;
                this._Children = children.ToArray();
            }
        }

        interface SpyIO
        {
            int Input();
            void Output(int i);
        }

        // TODO The inter-thread communication here can almost certainly be much better
        class TestSpyIO : SpyIO
        {
            private object _Lock = new object();
            private int? _Buffer;
            public TestSpyIO Partner;
            public readonly string Name;

            internal TestSpyIO(string name)
            {
                this.Name = name;
            }

            public int Input()
            {
                lock (_Lock)
                {
                    while (!_Buffer.HasValue) Monitor.Wait(_Lock);

                    int rv = _Buffer.Value;
                    _Buffer = null;
                    Monitor.PulseAll(_Lock);
                    return rv;
                }
            }

            public void Output(int i)
            {
                lock (Partner._Lock)
                {
                    while (Partner._Buffer.HasValue) Monitor.Wait(Partner._Lock);
                    Partner._Buffer = i;
                    Monitor.PulseAll(Partner._Lock);
                }
            }
        }

        class ConsoleIO : SpyIO
        {
            public int Input()
            {
                return Convert.ToInt32(Console.ReadLine());
            }

            public void Output(int i)
            {
                Console.WriteLine("{0}", i);
            }
        }

        class Spy
        {
            private readonly SpyIO _IO;
            private Node _Node;
            private bool _MyTurn;

            internal Spy(SpyIO io, Node root, bool isSpy1)
            {
                this._IO = io;
                this._Node = root;
                this._MyTurn = isSpy1;
            }

            internal void Run()
            {
                int myValue = _IO.Input() - 1;
                int hisValue = 1;

                bool myTurn = _MyTurn;
                Node n = _Node;
                while (n.RemainingStones > 0)
                {
                    if (myTurn)
                    {
                        if (myValue >= n.Value.X) throw new Exception("Internal error");
                        for (int i = 0; i < n.RemainingStones; i++)
                        {
                            // n[i] allows me to represent n[i].Y values: 0 to n[i].Y - 1
                            if (myValue < n[i].Value.Y)
                            {
                                _IO.Output(i + 1);
                                n = n[i];
                                break;
                            }
                            else myValue -= n[i].Value.Y;
                        }
                    }
                    else
                    {
                        int thrown = _IO.Input();
                        for (int i = 0; i < thrown - 1; i++)
                        {
                            hisValue += n[i].Value.Y;
                        }
                        n = n[thrown - 1];
                    }

                    myTurn = !myTurn;
                }

                _IO.Output(hisValue);
            }
        }
    }

    static class LinqExt
    {
        // I'm not sure why this isn't built into Linq.
        public static TElement MaxElement<TElement>(this IEnumerable<TElement> e, Func<TElement, int> f)
        {
            int bestValue = int.MinValue;
            TElement best = default(TElement);
            foreach (var elt in e)
            {
                int value = f(elt);
                if (value > bestValue)
                {
                    bestValue = value;
                    best = elt;
                }
            }
            return best;
        }
    }
}

```

### Instructions for Linux users

You'll need `mono-csc` to compile (on Debian-based systems, it's in the `mono-devel` package) and `mono` to run (`mono-runtime` package). Then the incantations are

```
mono-csc -out:codegolf31673.exe codegolf31673.cs
mono codegolf31673.exe --test

```

etc.
> 8 votes

# Answer
# Python Tester Program

I figure it would be useful to have a test program which can verify that your implementation is working. Both scripts below work with either Python 2 or Python 3.

Tester program (`tester.py`):

```
import sys
import shlex
from subprocess import Popen, PIPE

def writen(p, n):
    p.stdin.write(str(n)+'\n')
    p.stdin.flush()

def readn(p):
    return int(p.stdout.readline().strip())

MAXSTONES = 26

def test_one(spy1cmd, spy2cmd, n1, n2):
    p1 = Popen(spy1cmd, stdout=PIPE, stdin=PIPE, universal_newlines=True)
    p2 = Popen(spy2cmd, stdout=PIPE, stdin=PIPE, universal_newlines=True)

    nstones = MAXSTONES

    writen(p1, n1)
    writen(p2, n2)

    p1turn = True
    while nstones > 0:
        if p1turn:
            s = readn(p1)
            writen(p2, s)
        else:
            s = readn(p2)
            writen(p1, s)
        if s <= 0 or s > nstones:
            print("Spy %d output an illegal number of stones: %d" % ([2,1][p1turn], s))
            return False
        p1turn = not p1turn
        nstones -= s

    n1guess = readn(p2)
    n2guess = readn(p1)

    if n1guess != n1:
        print("Spy 2 output wrong answer: expected %d, got %d" % (n1, n1guess))
        return False
    elif n2guess != n2:
        print("Spy 1 output wrong answer: expected %d, got %d" % (n2, n2guess))
        return False

    p1.kill()
    p2.kill()

    return True

def testrand(spy1, spy2, M):
    import random
    spy1cmd = shlex.split(spy1)
    spy2cmd = shlex.split(spy2)

    n = 0
    while 1:
        i = random.randrange(1, M+1)
        j = random.randrange(1, M+1)
        test_one(spy1cmd, spy2cmd, i, j)
        n += 1
        if n % 100 == 0:
            print("Ran %d tests" % n)

def test(spy1, spy2, M):
    spy1cmd = shlex.split(spy1)
    spy2cmd = shlex.split(spy2)
    for i in range(1, M+1):
        print("Testing %d..." % i)
        for j in range(1, M+1):
            if not test_one(spy1cmd, spy2cmd, i, j):
                print("Spies failed the test.")
                return
    print("Spies passed the test.")

if __name__ == '__main__':
    if len(sys.argv) != 4:
        print("Usage: %s <M> <spy1> <spy2>: test programs <spy1> and <spy2> with limit M" % sys.argv[0])
        exit()

    M = int(sys.argv[1])
    test(sys.argv[2], sys.argv[3], M)

```

Protocol: The two spy programs specified on the command-line will be executed. They are expected to interact solely though stdin/stdout. Each program will receive its assigned number as the first line of input. In each turn, spy 1 outputs the number of stones to throw, spy 2 reads a number from stdin (representing spy 1's throw), and then they repeat (with positions reversed). When either spy determines that 26 stones have been thrown, they stop and output their guess for the other spy's number.

Example session with a compatible spy1 (`>` denotes input to the spy)

```
> 42
7
> 5
6
> 3
5
27
<program quits>

```

If you choose a very large M, and it takes too long to run, you can switch `test(` for `testrand(` in the last line to run random tests. In the latter case, leave the program running for at least a few thousand trials to build up confidence.

Example program (`spy.py`), for M=42:

```
import sys

# Carry out the simple strategy for M=42

def writen(n):
    sys.stdout.write(str(n)+"\n")
    sys.stdout.flush()

def readn():
    return int(sys.stdin.readline().strip())

def spy1(n):
    m1,m2 = divmod(n-1, 6)
    writen(m1+1)
    o1 = readn() # read spy2's number

    writen(m2+1)
    o2 = readn()

    rest = 26 - (m1+m2+o1+o2+2)
    if rest > 0:
        writen(rest)
    writen((o1-1)*6 + (o2-1) + 1)

def spy2(n):
    m1,m2 = divmod(n-1, 6)
    o1 = readn() # read spy1's number
    writen(m1+1)

    o2 = readn()
    writen(m2+1)

    rest = 26 - (m1+m2+o1+o2+2)
    if rest > 0:
        readn()

    writen((o1-1)*6 + (o2-1) + 1)

if __name__ == '__main__':
    if len(sys.argv) != 2:
        print("Usage: %s [spy1|spy2]" % (sys.argv[0]))
        exit()

    n = int(input())
    if sys.argv[1] == 'spy1':
        spy1(n)
    elif sys.argv[1] == 'spy2':
        spy2(n)
    else:
        raise Exception("Must give spy1 or spy2 as an argument.")

```

Example usage:

```
python tester.py 42 'python spy.py spy1' 'python spy.py spy2'

```
> 1 votes

# Answer
# Java, M = 2535

OK, here is my implementation. At each step one spy makes a move. Each possible move represents a range of codes. The spy chooses the move matching his secret code. As they throw more stones, the range of possible codes reduces until, at the end, for both spies, only one code remains possible according to the moves they did.

To recover the secret codes, you can replay all the moves and compute the corresponding code ranges. At the end, only one code remains for each spy, that is the secret code he wanted to transmit.

Unfortunately, the algorithm relies on a large precomputed table with hundred of thousands of integers. The method couldn't be applied mentally with more than 8-10 stones maybe.

The first file implements the Spy's algorithm. The static part precomputes a `codeCount` table that is later used to compute each move. The second part implements 2 procedures, one to select how many stones to throw, the other to replay a moves to help reconstruct the secret codes.

The second file tests the Spy class extensively. The method `simulate` simulates the process. It uses the Spy class to generate a sequence of throws from the secret codes and then reconstructs the codes from the sequence.

**Spy.java**

```
package stackexchange;

import java.util.Arrays;

public class Spy
{
    // STATIC MEMBERS

    /** Size of code range for a number of stones left to the other and the other spy's range */
    static int[][] codeCount;

    // STATIC METHODS

    /** Transpose an array of code counts */
    public static int[] transpose(int[] counts){
        int[] transposed = new int[counts[1]+1];
        int s = 0;
        for( int i=counts.length ; i-->0 ; ){
            while( s<counts[i] ){
                transposed[++s] = i;
            }
        }
        return transposed;
    }

    /** Add two integer arrays by element.  Assume the first is longer. */
    public static int[] add(int[] a, int[] b){
        int[] sum = a.clone();
        for( int i=0 ; i<b.length ; i++ ){
            sum[i] += b[i];
        }
        return sum;
    }

    /** Compute the code range for every response */
    public static void initCodeCounts(int maxStones){
        codeCount = new int[maxStones+1][];
        codeCount[0] = new int[] {0,1};
        int[] sum = codeCount[0];
        for( int stones=1 ; stones<=maxStones ; stones++ ){
            codeCount[stones] = transpose(sum);
            sum = add(codeCount[stones], sum);
        }
    }

    /** display the code counts */
    public static void dispCodeCounts(int maxStones){
        for( int stones=1 ; stones<=maxStones ; stones++ ){
            if( stones<=8 ){
                System.out.println(stones + ": " + Arrays.toString(codeCount[stones]));
            }
        }
        for( int s=1 ; s<=maxStones ; s++ ){
            int[] row = codeCount[s];
            int best = 0;
            for( int r=1 ; r<row.length ; r++ ){
                int min = r<row[r] ? r : row[r];
                if( min>=best ){
                    best = min;
                }
            }
            System.out.println(s + ": " + row.length + " " + best);
        }
    }

    /** Find the maximum symmetrical code count M for a number of stones */
    public static int getMaxValue(int stones){
        int[] row = codeCount[stones];
        int maxValue = 0;
        for( int r=1 ; r<row.length ; r++ ){
            int min = r<row[r] ? r : row[r];
            if( min>=maxValue ){
                maxValue = min;
            }
        }
        return maxValue;
    }

    // MEMBERS

    /** low end of range, smallest code still possible */
    int min;

    /** range size, number of codes still possible */
    int range;

    /** Create a spy for a certain number of stones */
    Spy(int stones){
        min = 1;
        range = getMaxValue(stones);
    }

    /** Choose how many stones to throw */
    public int throwStones(int stonesLeft, int otherRange, int secret){
        for( int move=1 ; ; move++ ){
            // see how many codes this move covers
            int moveRange = codeCount[stonesLeft-move][otherRange];
            if( secret < this.min+moveRange ){
                // secret code is in move range
                this.range = moveRange;
                return move;
            }
            // skip to next move
            this.min += moveRange;
            this.range -= moveRange;
        }
    }

    /* Replay the state changes for a given move */
    public void replayThrow(int stonesLeft, int otherRange, int stonesThrown){
        for( int move=1 ; move<stonesThrown ; move++ ){
            int moveRange = codeCount[stonesLeft-move][otherRange];
            this.min += moveRange;
            this.range -= moveRange;
        }
        this.range = codeCount[stonesLeft-stonesThrown][otherRange];
    }
}

```

**ThrowingStones.java**

```
package stackexchange;

public class ThrowingStones
{
    public boolean simulation(int stones, int secret0, int secret1){

        // ENCODING

        Spy spy0 = new Spy(stones);
        Spy spy1 = new Spy(stones);

        int[] throwSequence = new int[stones+1];
        int turn = 0;
        int stonesLeft = stones;

        while( true ){
            // spy 0 throws
            if( stonesLeft==0 ) break;
            throwSequence[turn] = spy0.throwStones(stonesLeft, spy1.range, secret0);
            stonesLeft -= throwSequence[turn++];
            // spy 1 throws
            if( stonesLeft==0 ) break;
            throwSequence[turn] = spy1.throwStones(stonesLeft, spy0.range, secret1);
            stonesLeft -= throwSequence[turn++];
        }

        assert (spy0.min==secret0 && spy0.range==1 );
        assert (spy1.min==secret1 && spy1.range==1 );

//      System.out.println(Arrays.toString(throwSequence));

        // DECODING

        spy0 = new Spy(stones);
        spy1 = new Spy(stones);

        stonesLeft = stones;
        turn = 0;
        while( true ){
            // spy 0 throws
            if( throwSequence[turn]==0 ) break;
            spy0.replayThrow(stonesLeft, spy1.range, throwSequence[turn]);
            stonesLeft -= throwSequence[turn++];
            // spy 1 throws
            if( throwSequence[turn]==0 ) break;
            spy1.replayThrow(stonesLeft, spy0.range, throwSequence[turn]);
            stonesLeft -= throwSequence[turn++];
        }
        int recovered0 = spy0.min;
        int recovered1 = spy1.min;

        // check the result
        if( recovered0 != secret0 || recovered1 != secret1 ){
            System.out.println("error recovering (" + secret0 + "," + secret1 + ")"
                    + ", returns (" + recovered0 + "," + recovered1 + ")");
            return false;
        }
        return true;
    }

    /** verify all possible values */
    public void verifyAll(int stones){
        int count = 0;
        int countOK = 0;
        int maxValue = Spy.getMaxValue(stones);
        for( int a=1 ; a<=maxValue ; a++ ){
            for( int b=1 ; b<=maxValue ; b++ ){
                count++;
                if( simulation(stones, a, b) ) countOK++;
            }
        }
        System.out.println("verified: " + countOK + "/" + count);
    }

    public static void main(String[] args) {
        ThrowingStones app = new ThrowingStones();
        Spy.initCodeCounts(26);
        Spy.dispCodeCounts(26);
        app.verifyAll(20);
//      app.verifyAll(26); // never managed to complete this one...
    }

}

```

For reference, the precomputed codeCount array contains the following values:

```
1: [0, 1]
2: [0, 1, 1]
3: [0, 2, 1, 1]
4: [0, 3, 2, 1, 1, 1]
5: [0, 5, 3, 2, 2, 1, 1, 1, 1]
6: [0, 8, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1]

```

This related directly to Peter Taylor's Tk sets. We have:

```
(x,y) in Tk  <=>  y <= codeCount[x]

```
> 1 votes

# Answer
# ksh/zsh, M = 126

In this simple system, each spy throws binary digits to the other spy. In each throw, the first stone is ignored, the next stones are each bit 0, and the last stone is bit 1. For example, to throw 20, a spy would throw 4 stones (ignore, 0, 2, add 4), then throw 3 stones (ignore, 8, add 16), because 4 + 16 = 20.

The set of numbers is not contiguous. 0 to 126 are in, but 127 is out. (If both spies have 127, they need 28 stones, but they have 26 stones.) Then 128 to 158 are in, 159 is out, 160 to 174 are in, 175 is out, 176 to 182 are in, 183 is out, 184 to 186 is in, 187 is out, and so on.

Run an automatic swap with `ksh spy.sh 125 126`, or run individual spies with `ksh spy.sh spy1 125` and `ksh spy.sh spy2 126`. Here, `ksh` can be ksh93, pdksh or zsh.

EDIT 14 Jun 2014: Fix a problem with some co-processes in zsh. They would idle forever and fail to exit, until the user killed them.

```
(( stones = 26 ))

# Initialize each spy.
spy_init() {
    (( wnum = $1 ))  # my number
    (( rnum = 0 ))   # number from other spy
    (( rlog = -1 ))  # exponent from other spy
}

# Read stone count from other spy.
spy_read() {
    read count || exit
    (( stones -= count ))

    # Ignore 1 stone.
    (( count > 1 )) && {
        # Increment exponent.  Add bit to number.
        (( rlog += count - 1 ))
        (( rnum += 1 << rlog ))
    }
}

# Write stone count to other spy.
spy_write() {
    if (( wnum ))
    then
        # Find next set bit.  Prepare at least 2 stones.
        (( count = 2 ))
        until (( wnum & 1 ))
        do
            (( wnum >>= 1 ))
            (( count += 1 ))
        done

        (( wnum >>= 1 ))  # Remove this bit.
        (( stones -= count ))
        print $count      # Throw stones.
    else
        # Throw 1 stone for other spy to ignore.
        (( stones -= 1 ))
        print 1
    fi
}

# spy1 writes first.
spy1() {
    spy_init "$1"
    while (( stones ))
    do
        spy_write
        (( stones )) || break
        spy_read
    done
    print $rnum
}

# spy2 reads first.
spy2() {
    spy_init "$1"
    while (( stones ))
    do
        spy_read
        (( stones )) || break
        spy_write
    done
    print $rnum
}

(( $# == 2 )) || {
    name=${0##*/}
    print -u2 "usage: $name number1 number2"
    print -u2 "   or: $name spy[12] number"
    exit 1
}

case "$1" in
    spy1)
        spy1 "$2"
        exit;;
    spy2)
        spy2 "$2"
        exit;;
esac

(( number1 = $1 ))
(( number2 = $2 ))

if [[ -n $KSH_VERSION ]]
then
    eval 'cofork() { "$@" |& }'
elif [[ -n $ZSH_VERSION ]]
then
    # In zsh, a co-process stupidly inherits its own >&p, so it never
    # reads end of file.  Use 'coproc :' to close <&p and >&p.
    eval 'cofork() {
        coproc {
            coproc :
            "$@"
        }
    }'
fi

# Fork spies in co-processes.
[[ -n $KSH_VERSION ]] && eval 'coproc() { "$@" |& }'
cofork spy1 number1
exec 3<&p 4>&p
cofork spy2 number2
exec 5<&p 6>&p

check_stones() {
    (( stones -= count ))
    if (( stones < 0 ))
    then
        print -u2 "$1 is in trouble! " \
            "Needs $count stones, only had $((stones + count))."
        exit 1
    else
        print "$1 threw $count stones.  Pile has $stones stones."
    fi
}

# Relay stone counts while spies throw stones.
while (( stones ))
do
    # First, spy1 writes to spy2.
    read -u3 count report1 || mia spy1
    check_stones spy1
    print -u6 $count

    (( stones )) || break

    # Next, spy2 writes to spy1.
    read -u5 count report2 || mia spy2
    check_stones spy2
    print -u4 $count
done

mia() {
    print -u2 "$1 is missing in action!"
    exit 1
}

# Read numbers from spies.
read -u3 report1 || mia spy1
read -u5 report2 || mia spy2

pass=true
(( number1 != report2 )) && {
    print -u2 "FAILURE: spy1 put $number1, but spy2 got $report2."
    pass=false
}
(( number2 != report1 )) && {
    print -u2 "FAILURE: spy2 put $number2, but spy1 got $report1."
    pass=false
}

if $pass
then
    print "SUCCESS: spy1 got $report1, spy2 got $report2."
    exit 0
else
    exit 1
fi

```
> 0 votes

---
Tags: code-challenge, combinatorics, puzzle-solver
---


title: Rock, Paper, Scissors, Lizard, Spock

text:
# Question
Title: Rock, Paper, Scissors, Lizard, Spock
Create a function that will take two strings as input and return a single output for the result. Most popular answer wins.

The rules of Rock-paper-scissors-lizard-Spock are:

* Scissors cut paper
* Paper covers rock
* Rock crushes lizard
* Lizard poisons Spock
* Spock smashes scissors
* Scissors decapitate lizard
* Lizard eats paper
* Paper disproves Spock
* Spock vaporizes rock
* Rock breaks scissors

The output for every possible input case is:

```
winner('Scissors', 'Paper') -> 'Scissors cut Paper'
winner('Scissors', 'Rock') -> 'Rock breaks Scissors'
winner('Scissors', 'Spock') -> 'Spock smashes Scissors'
winner('Scissors', 'Lizard') -> 'Scissors decapitate Lizard'
winner('Scissors', 'Scissors') -> 'Scissors tie Scissors'
winner('Paper', 'Rock') -> 'Paper covers Rock'
winner('Paper', 'Spock') -> 'Paper disproves Spock'
winner('Paper', 'Lizard') -> 'Lizard eats Paper'
winner('Paper', 'Scissors') -> 'Scissors cut Paper'
winner('Paper', 'Paper') -> 'Paper ties Paper'
winner('Rock', 'Spock') -> 'Spock vaporizes Rock'
winner('Rock', 'Lizard') -> 'Rock crushes Lizard'
winner('Rock', 'Scissors') -> 'Rock breaks Scissors'
winner('Rock', 'Paper') -> 'Paper covers Rock'
winner('Rock', 'Rock') -> 'Rock ties Rock'
winner('Lizard', 'Rock') -> 'Rock crushes Lizard'
winner('Lizard', 'Spock') -> 'Lizard poisons Spock'
winner('Lizard', 'Scissors') -> 'Scissors decapitate Lizard'
winner('Lizard', 'Paper') -> 'Lizard eats Paper'
winner('Lizard', 'Lizard') -> 'Lizard ties Lizard'
winner('Spock', 'Rock') -> 'Spock vaporizes Rock'
winner('Spock', 'Lizard') -> 'Lizard poisons Spock'
winner('Spock', 'Scissors') -> 'Spock smashes Scissors'
winner('Spock', 'Paper') -> 'Paper disproves Spock'
winner('Spock', 'Spock') -> 'Spock ties Spock'

```

Extra challenge suggested by @Sean Cheshire: Allow custom lists, such as those from this site. With the n-item list, the item loses to the (n-1)/2 previous, and wins over the (n-1)/2 following

# Answer
> 13 votes
# APL

```
vs←{
    n←'Scissors' 'Paper' 'Rock' 'Lizard' 'Spock'
    x←n⍳⊂⍺ ⋄ y←n⍳⊂⍵ ⋄ X←⍺ ⋄ Y←⍵ ⋄ r←{X,⍵,⊂Y}
    x=y:     r (-x=0)↓'ties'
    y=5|1+x: r x⌷'cut' 'covers' 'crushes' 'poisons' 'smashes'
    y=5|3+x: r x⌷'decapitate' 'disproves' 'breaks' 'eats' 'vaporizes'
    ⍵∇⍺
}

```

Output exactly as required in all cases, including tie/ties. No lookup table, except for the actual words.

You can try it on http://ngn.github.io/apl/web/

```
'Spock' vs 'Paper'
Paper  disproves  Spock

```

APL just knows!

# Answer
> 10 votes
## SED

```
#!/bin/sed
#expects input as 2 words, eg: scissors paper

s/^.*$/\L&/
s/$/;scissors cut paper covers rock crushes lizard poisons spock smashes scissors decapitates lizard eats paper disproves spock vaporizes rock breaks scissors/
t a
:a
s/^\(\w\+\)\s\+\(\w\+\);.*\1 \(\w\+\) \2.*$/\u\1 \3 \u\2/
s/^\(\w\+\)\s\+\(\w\+\);.*\2 \(\w\+\) \1.*$/\u\2 \3 \u\1/
t b
s/^\(\w\+\)\s\+\1;\(\1\?\(s\?\)\).*$/\u\1 tie\3 \u\1/
:b

```

# Answer
> 4 votes
Here is a general solution based on a rule string of any size. It performs correct capitalization for the proper name "Spock" and also allows rules for specifying 'tie' instead of 'ties' for plural objects.

```
def winner(p1, p2):
    rules = ('scissors cut paper covers rock crushes lizard poisons Spock'
    ' smashes scissors decapitate lizard eats paper disproves Spock vaporizes'
    ' rock breaks scissors tie scissors'.split())

    idxs = sorted(set(i for i, x in enumerate(rules)
                      if x.lower() in (p1.lower(), p2.lower())))
    idx = [i for i, j in zip(idxs, idxs[1:]) if j-i == 2]
    s=' '.join(rules[idx[0]:idx[0]+3] if idx
          else (rules[idxs[0]], 'ties', rules[idxs[0]]))
    return s[0].upper()+s[1:]

```

Results:

```
>>> winner('spock', 'paper')
'Paper disproves Spock'
>>> winner('spock', 'lizard')
'Lizard poisons Spock'
>>> winner('Paper', 'lizard')
'Lizard eats paper'
>>> winner('Paper', 'Paper')
'Paper ties paper'
>>> winner('scissors',  'scissors')
'Scissors tie scissors'

```

# Answer
> 3 votes
## Python

```
class Participant (object):
    def __str__(self): return str(type(self)).split(".")[-1].split("'")[0]
    def is_a(self, cls): return (type(self) is cls)
    def do(self, method, victim): return "%s %ss %s" % (self, method, victim)

class Rock (Participant):
        def fight(self, opponent):
                return (self.do("break", opponent)  if opponent.is_a(Scissors) else
                        self.do("crushe", opponent) if opponent.is_a(Lizard)   else
                        None)

class Paper (Participant):
        def fight(self, opponent):
                return (self.do("cover", opponent)    if opponent.is_a(Rock)  else
                        self.do("disprove", opponent) if opponent.is_a(Spock) else
                        None)

class Scissors (Participant):
        def fight(self, opponent):
                return (self.do("cut", opponent)       if opponent.is_a(Paper)  else
                        self.do("decaitate", opponent) if opponent.is_a(Lizard) else
                        None)

class Lizard (Participant):
        def fight(self, opponent):
                return (self.do("poison", opponent) if opponent.is_a(Spock) else
                        self.do("eat", opponent)    if opponent.is_a(Paper) else
                        None)

class Spock (Participant):
        def fight(self, opponent):
                return (self.do("vaporize", opponent) if opponent.is_a(Rock)     else
                        self.do("smashe", opponent)    if opponent.is_a(Scissors) else
                        None)

def winner(a, b):
    a,b = ( eval(x+"()") for x in (a,b))
    return a.fight(b) or b.fight(a) or a.do("tie", b)

```

# Answer
> 3 votes
# Ruby, arithmetic approach

The actors can can be arranged in an array in such a way that each actor `a[i]` wins against the actors `a[i+1]` and `a[i+2]`, modulo 5, for instance:

```
%w(Scissors Lizard Paper Spock Rock)

```

Then, for an actor `A` with index `i` we can see how he matches agains actor `B` with index `j` by doing `result = (j-i)%5`: Result `1` and `2` means that actor A won against an actor 1 or 2 places in front of him respectively; `3` and `4` similarly means he lost against an actor behind him in the array. `0` means a tie. (Note that this may be language dependent; in Ruby `(j-i)%5 == (5+j-i)%5` also when `j>i`.)

The most interesting part of my code is the use of this property to find a sorting function of the indices of two actors. The return value will be -1, 0 or 1 as it should:

```
winner,loser = [i,j].sort { |x,y| ((y-x)%5+1)/2-1 }

```

Here's the whole thing:

```
def battle p1,p2
    who = %w(Scissors Lizard Paper Spock Rock)
    how = %w(cut decapitate poisons eats covers disproves smashes vaporizes crushes breaks)
    i,j = [p1,p2].map { |s| who.find_index s }

    winner,loser = [i,j].sort { |x,y| ((y-x)%5+1)/2-1 }

    method = (winner-loser)%5/2
    what = method == 0 && "ties" || how[winner*2 + method-1]

    return "#{who[winner]} #{what} #{who[loser]}"
end

```

# Answer
> 2 votes
## Python

```
def winner(p1, p2):
    actors = ['Paper', 'Scissors', 'Spock', 'Lizard', 'Rock']
    verbs = {'RoLi':'crushes', 'RoSc':'breaks', 'LiSp':'poisons',
             'LiPa':'eats', 'SpSc':'smashes', 'SpRo':'vaporizes',
             'ScPa':'cut', 'ScLi':'decapitate', 'PaRo':'covers',
             'PaSp':'disproves', 'ScSc':'tie'}
    p1, p2 = actors.index(p1), actors.index(p2)
    winner, loser = ((p1, p2), (p2, p1))[(1,0,1,0,1)[p1 - p2]]
    return ' '.join([actors[winner],
                     verbs.get(actors[winner][0:2] + actors[loser][0:2],
                               'ties'),
                     actors[loser]])

```

# Answer
> 2 votes
# Python

---

```
  def winner(p,q):
        if p==q:
           return(' '.join([p,'tie',q]))
        d = {'ca':'cut','ao':'covers','oi':'crushes','ip':'poisons','pc': 'smashes','ci':'decapitate','ia':'eats', 'ap':'disproves', 'po':'vaporizes','oc': 'breaks'}
        [a,b] = [p[1],q[1]]
        try:
           return(' '.join([p,d[a+b],q]))
        except KeyError:
           return(' '.join([q,d[b+a],p]))

```

Using a tricky dictionary.

# Answer
> 2 votes
# C#

### Assumptions

The opponents are arranged in an n-item array where players beat the (n-1)/2 players ahead of them and lose to the (n-1)/2 players behind them. *(With even length lists, the player loses to the ((n-1)/2 + 1) players behind them)*

Player actions are arranged in an array where actions within the range of \[(indexOfPlayer * (n-1)/2)\] to \[(indexOfPlayer * (n-1)/2)) + (n-2)/2 - 1\].

### Additional Info

`CircularBuffer<T>` is a wrapper around an array to create an "infinitely" addressable array. The `IndexOf` function returns the index of an item within the actual bounds of the array.

### The Class

```
public class RockPaperScissors<T> where T : IComparable
{
    private CircularBuffer<T> players;
    private CircularBuffer<T> actions;

    private RockPaperScissors() { }

    public RockPaperScissors(T[] opponents, T[] actions)
    {
        this.players = new CircularBuffer<T>(opponents);
        this.actions = new CircularBuffer<T>(actions);
    }

    public string Battle(T a, T b)
    {
        int indexA = players.IndexOf(a);
        int indexB = players.IndexOf(b);

        if (indexA == -1 || indexB == -1)
        {
            return "A dark rift opens in the side of the arena.\n" +
                   "Out of it begins to crawl a creature of such unimaginable\n" +
                   "horror, that the spectators very minds are rendered\n" +
                   "but a mass of gibbering, grey jelly. The horrific creature\n" +
                   "wins the match by virtue of rendering all possible opponents\n" +
                   "completely incapable of conscious thought.";
        }

        int range = (players.Length - 1) / 2;

        if (indexA == indexB)
        {
            return "'Tis a tie!";
        }
        else
        {
            indexB = indexB < indexA ? indexB + players.Length : indexB;
            if (indexA + range < indexB)
            {
                // A Lost
                indexB = indexB >= players.Length ? indexB - players.Length : indexB;
                int actionIndex = indexB * range + (indexA > indexB ? indexA - indexB : (indexA + players.Length) - indexB) - 1;

                return players[indexB] + " " + actions[actionIndex] + " " + players[indexA];
            }
            else
            {
                // A Won
                int actionIndex = indexA * range + (indexB - indexA) - 1;

                return players[indexA] + " " + actions[actionIndex] + " " + players[indexB];
            }
        }
    }
}

```

### Example

```
string[] players = new string[] { "Scissors", "Lizard", "Paper", "Spock", "Rock" };
string[] actions = new string[] { "decapitates", "cuts", "eats", "poisons", "disproves", "covers", "vaporizes", "smashes", "breaks", "crushes" };

RockPaperScissors<string> rps = new RockPaperScissors<string>(players, actions);

foreach (string player1 in players)
{
    foreach (string player2 in players)
    {
        Console.WriteLine(rps.Battle(player1, player2));
    }
}
Console.ReadKey(true);

```

# Answer
> 1 votes
## Python, one-liner

```
winner=lambda a,b:(
    [a+" ties "+b]+
    [x for x in
        "Scissors cut Paper,Paper covers Rock,Rock crushes Lizard,Lizard poisons Spock,Spock smashes Scissors,Scissors decapitate Lizard,Lizard eats Paper,Paper disproves Spock,Spock vaporizes Rock,Rock break Scissors"
        .split(',')
     if a in x and b in x])[a!=b]

```

# Answer
> 1 votes
Just a small thing I came up with:

```
echo "winners('Paper', 'Rock')"|sed -r ":a;s/[^ ]*'([[:alpha:]]+)'./\1/;ta;h;s/([[:alpha:]]+) ([[:alpha:]]+)/\2 \1/;G"|awk '{while(getline line<"rules"){split(line,a," ");if(match(a[1],$1)&&match(a[3],$2))print line};close("rules")}' IGNORECASE=1

```

Here, rules is the file containing all the rules that were given.

# Answer
> 0 votes
## Python

Inspired by @Tobia's APL code.

```
def winner(p1, p2):
  x,y = map(lambda s:'  scparolisp'.find(s.lower())/2, (p1[:2], p2[:2]))
  v = (' cut covers crushes poisons smashes'.split(' ')[x*(y in (x+1, x-4))] or
       ' decapitate disproves breaks eats vaporizes'.split(' ')[x*(y in (x+3, x-2))])
  return ' '.join((p1.capitalize(), v or 'tie'+'s'*(x!=1), p2)) if v or p1==p2 \
    else winner(p2, p1)

```

Results:

```
>>> winner('Spock', 'paper')
'Paper disproves Spock'
>>> winner('Spock', 'lizard')
'Lizard poisons Spock'
>>> winner('paper', 'lizard')
'Lizard eats paper'
>>> winner('paper', 'paper')
'Paper ties paper'
>>> winner('scissors',  'scissors')
'Scissors tie scissors'

```

# Answer
> 0 votes
# C++

```
#include <stdio.h>
#include <string>
#include <map>
using namespace std ;
map<string,int> type = { {"Scissors",0},{"Paper",1},{"Rock",2},{"Lizard",3},{"Spock",4} };
map<pair<int,int>, string> joiner = {
  {{0,1}, " cuts "},{{0,3}, " decapitates "}, {{1,2}, " covers "},{{1,4}, " disproves "},
  {{2,3}, " crushes "},{{2,0}, " crushes "},  {{3,4}, " poisons "},{{3,1}, " eats "},
  {{4,0}, " smashes "},{{4,2}, " vaporizes "},
} ;
// return 0 if first loses, return 1 if 2nd wins
int winner( pair<int,int> p ) {
  return (p.first+1)%5!=p.second && (p.first+3)%5!=p.second ;
}
string winner( string sa, string sb ) {
  pair<int,int> pa = {type[sa],type[sb]};
  int w = winner( pa ) ;
  if( w )  swap(pa.first,pa.second), swap(sa,sb) ;
  return sa+(pa.first==pa.second?" Ties ":joiner[pa])+sb ;
}

```

A bit of a test

```
int main(int argc, const char * argv[])
{
  for( pair<const string&, int> a : type )
    for( pair<const string&, int> b : type )
      puts( winner( a.first, b.first ).c_str() ) ;
}

```

# Answer
> 0 votes
# Javascript

```
function winner(c1,c2){
    var c = ["Scissors", "Paper", "Rock", "Lizard", "Spock"];
    var method={
        1:["cut", "covers", "crushes", "poisons", "smashes"],
        2:["decapitate", "disproves", "breaks", "eats", "vaporizes"]};
    //Initial hypothesis: first argument wins
    var win = [c.indexOf(c1),c.indexOf(c2)];
    //Check for equality
    var diff = win[0] - win[1];
    if(diff === 0){
        return c1 + ((win[0]===0)?" tie ":" ties ") + c2;
    }
    //If s is -1 we'll swap the order of win[] array
    var s = (diff>0)?1:-1;
    diff = Math.abs(diff);
    if(diff >2){
        diff = 5-diff;
        s= s * -1;
    }
    s=(diff==1)?s*-1:s;
    if(s === -1){
        win = [win[1],win[0]];
    }
    return c[win[0]] + " " + method[diff][win[0]] + " " + c[win[1]];
}

```

# Answer
> 0 votes
# Javascript

I see this isn't a golfing contest, but I had been fiddling with this puzzle for a while before finding this thread, so here goes.

Here's a (standard) js version in 278 characters:

```
function winner(a,b){var c={rock:0,paper:1,scissors:2,spock:3,lizard:4},d="crushe,crushe,cover,disprove,cut,decapitate,smashe,vaporize,poison,eat".split(","),i=c[a],j=c[b],I=i==(j+3)%5;return i^j?i==(j+1)%5||I?a+" "+d[i*2+I]+"s "+b:b+" "+d[j*2+(j==(i+3)%5)]+"s "+a:a+" ties "+b}

```

Or one using E6 features (likely only works in Firefox) in 259 characters:

```
winner=(a,b,c={rock:0,paper:1,scissors:2,spock:3,lizard:4},d="crushe,crushe,cover,disprove,cut,decapitate,smashe,vaporize,poison,eat".split(","),i=c[a],j=c[b],I=i==(j+3)%5)=>i^j?i==(j+1)%5||I?a+" "+d[i*2+I]+"s "+b:b+" "+d[j*2+(j==(i+3)%5)]+"s "+a:a+" ties "+b

```

---
Tags: popularity-contest
---


title: ¿Yo Quiero jQuery?

text:
# Question
Title: ¿Yo Quiero jQuery?
## The Setup

You are given a simple web page with 11 elements:

* 10 `input` elements with IDs `i1` thru `i10`, in order
* one `output` element with ID `out`

The input elements have `value` attributes defined in the HTML source. The value of any given input may be any integer from `0` to `10` inclusive.

The webpage is equipped with the core jQuery 1.10.1 library (as seen in the fiddle), and executes a block of code as soon as the DOM is loaded.

## The Challenge

Six specific challenges are presented below. In each case the objective is to compute some function of the `input`s and place the computation result into the inner HTML of the `output`. Each challenge should be solved independently from the others. The solution to a challenge is the block of code that implements the computation/output (e.g. the code in the "Javascript" window in the fiddle). The length of a solution is the length (in bytes) of this block of code.

All this would seem very simple, if not for some rather interesting restrictions.

## Your Code May...

1. invoke the jQuery function `$()` and pass in arguments
2. define and use variables
3. use `this`
4. read any property of any jQuery object (with `.length` being the most useful)
5. define functions/lambdas, which may subsequently be invoked, stored in variables, and passed as arguments. Functions may accept arguments and `return` values if needed.
6. invoke any of the jQuery DOM traversal methods
7. invoke any of the jQuery DOM manipulation methods, excepting `width`, `height`, `innerWidth`, `innerHeight`, `outerWidth`, `outerHeight`, `offset`, `position`, `replaceAll`, `replaceWith`, `scrollLeft`, `scrollTop`, `css`, `prop`, `removeProp`, which may not be invoked
8. use the operators: object creation `{}`; array creation / index reference / field reference `[]`, function/method invocation `()`, string concatenation `+`, and assignment `=`
9. use string literals

## Your Code May Not...

1. use *any* operators except for those listed above
2. use *any* literals that are not string literals
3. invoke *any* function/method other than those specifically excepted above
4. use *any* control structure or keyword (e.g. `for`, `while`, `try`, `if`, `with`, etc.), excepting `this`, `var`, `let`, functions and lambdas
5. manipulate the DOM in *any* way that results in the injection of code (see more below)
6. access *any* non-user-defined variable or non-user-defined field/property excepting those listed above

## The 6 Challenges

1. Compute the sum of all `input` values that are even, placing the result in the inner HTML of the `output`.
2. Compute the maximum of all `input` values, placing the result in the inner HTML of the `output`.
3. Compute the product of all `input` values `<= 2`, placing the result in the inner HTML of the `output`. If all input values are `> 2`, place `0` into the inner HTML of the `output`.
4. Compute the modal value (i.e. the value with greatest frequency) of all `input` values, placing the result in the inner HTML of the `output`. If the modal value is not unique, place *any one* of the modal values in the inner HTML of the `output`.
5. Let `I1` be the value of input `i1`, `I2` be the value of input `i2`, etc. If the sequence of input values `I1` .. `I10` forms a fence with `I1 < I2`, place `"TRUE"` into the inner HTML out the `output`; otherwise place `"FALSE"` into the inner HTML of the output. Specifically, the fence condition is `I1 < I2 > I3 < I4 > I5 < I6 > I7 < I8 > I9 < I10`.
6. Place a comma-separated list of all `input` values, sorted in ascending order, into the inner HTML of the `output`.

## Scoring

The contest winner is the programmer who submits correct solutions to the greatest number of challenges. In the event of a tie, the winner is the programmer with the lowest total solution length (the sum of the lengths of all solutions). Hence this is a minor variant of code golf.

## Important Notes

Solutions may mangle the DOM (e.g. delete `inputs`, create new elements that appear as visual detritus) so long as the final state of the DOM contains an `output` element with ID `out` and the correctly-computed value.

Solutions may make use of any advanced jQuery selectors and CSS3, excepting features that evaluate expressions or execute code.

Solutions may not modify the HTML source of the document. All DOM manipulation must occur in the script through jQuery.

Solutions *may not* inject code of any kind during DOM traversal/manipulation. This includes (but is not limited to) writing out `script` elements, writing out event attributes containing code, or exploiting the `expression` (IE) or `calc` features of CSS3. This challenge is about creative thinking using sets and trees, and masterful use of jQuery; it is *not* about sneaking code into the DOM or making end runs around the operator restrictions. I reserve the right to disqualify any solution on this basis.

All solutions are realizable, and each can be implemented in fewer than 400 bytes. Your solutions may of course exceed 400 bytes or be far shorter than 400 bytes. This is just my basic guarantee that all 6 problems are solvable using a reasonably small amount of code.

Finally: **When in doubt, please ask.** :)

## Example

Consider the hypothetical challenge: "If 3 or more `input` values equal 5, place `"TRUE"` into the inner HTML of the `output`; otherwise place `"FALSE"` into the inner HTML of the `output`."

One valid solution is:

```
F = () => $('body').append( '<a>TRUE</a>' );
$('input').each( F );
F();
$('a:lt(3)').html( 'FALSE' );
$('#out').html( $('a:eq(' + $('input[value="5"]').length + ')') );

```

**May the best jQuerier win! ;)**

# Answer
## 1. Sum of even inputs, ~~100~~ 94 bytes

```
a=$();(e=$('*:odd')).map(i=>a=a.add(e.slice('0',e.eq(i).val()).clone()));$(out).html(a.length)

```

How it works :

* `a=$();` : Create a new object `a`
* `e=$('*:odd')` : Get all odd elements on the page and assign it to `e`. Interestingly, all odd elements of page actualyl include all even input elements (amongst other things) ;)
* `(e=..).map(i=>...)` : For each of the elements in the object `e`, run the given function where i is the index of the current element.
* `a=a.add(e.slice('0', e.eq(i).val()).clone())` : get the value of the ith element in `e`, slice out that many objects from `e`, clone them and put add them to `a`. Interestingly, again, e has more than 10 elements, so it works for all values of the input boxes. For non input elements in `e`, it just slices 0 elements from `e`.
* `$(out).html(a.length)` : `out` is a global created by browsers for each element with an id. So we just put the length of `a` in the output element's html.

Note that jquery's $() acts as a set, but we are adding clones DOM elements, so it is accumulating and finally giving sum of all even input values.

## 2. Max of all, ~~79~~ 70 bytes

```
a=[];(e=$('*')).map(i=>a[e.eq(i).val()]=e);$(a).map(_=>$(out).html(_))

```

How it works:

* `a=[];` : create a new array `a`
* `e=$('*')` : Query all elements on the page and store it in `e`
* `(e=..).map(i=>...)` : For each of the elements in the object `e`, run the given function where i is the index of the current element.
* `a[e.eq(i).val()]=e` : Get the value of the ith element in `e` (say V) and put `e` in the Vth index of `a`. We use `e` here just to save a byte. Otherwise, `a[e.eq(i).val()]=''` would also work.
* `$(a).map(_=>$(out).html(_))` : This is basically putting each index of `a` into the html of the output element, overriding each time. This ends up with the output node having the value which corresponds to the last index of `a` which corresponds to the highest value in the inputs.

## 3. Product, ~~152 141 133~~ 132 bytes

```
f=(i,g=_=>p=$(i1))=>$('[value='+i+']').map(g);h=p=$();f('1');f('2');f('2',_=>p=p.add(p.clone()));f('0',_=>p=h);$(out).html(p.length)

```

141 -\> 133 reduction thanks to GOTO0 :)

## 4. Modal, ~~116 115~~ 102 bytes

```
a=[];(e=$('*')).map(i=>(v=e.eq(i).val(),a[$('[value='+v+']').length]=v));$(out).html($(a).last()['0'])

```

## 5. Fence, 158 bytes

```
s="TRUE";g=_=>$("*").slice(A.val(),B.val()).map(_=>s="FALSE");f=a=>(A=$(a),B=A.prev(),g(),A=$(a),B=A.next(),g());f(i2);f(i4);f(i6);f(i8);f(i10);$(out).html(s)

```

## 6. Sorted comma separated values, ~~133 85~~ 86 bytes

```
$('*').map(i=>$('[value='+i+']').map(_=>$(out).append(i+'<a>,')));$("a:last").remove()

```

How this works:

* `$('*').map(i=>...)` : Take out all elements from the page and run the method for all of them where `i` is the index of the element.
* `$('[value='+i+']').map(_=>...)` : For each `i`, get all elements whose value is `i` and run the method for each one of them.
* `$(out).append(i+'<a>,')` : Append `i` and an anchor tag with `,` in it to the output element for each element whose value is `i`.
* `$("a:last").remove()` : Remove the last anchor tag to remove the trailing `,`

This works as it picks out all elements with values `i` = 0 through 19 (19 being total number of elements on page) and appends `i,` to the output element the number of times an element with value `i` appears. This takes care of all input element, sorting them in increasing order.

---

Run them on the given JS fiddle page on a latest Firefox.

Please comment if anything is violating rules.
> 9 votes

# Answer
Interesting challenge! Here are the first few to start us off:

### 1. Sum, 122 112 bytes

```
e=$('*')
e.map(i=>e.slice('0',n=e.eq(i).val()).map(x=>e.eq(n).append('<a>')))
e.text($(':not(a):even>a').length)

```

For each input n, append n `<a>` elements to the nth `<input>` element. Then count the `<a>` elements in every odd `<input>` element.

### 2. Maximum, 91 79 bytes

```
e=$('*')
s=$()
e.map(i=>(s=s.add(e.slice('0',e.eq(i).val()))))
e.text(s.length)

```

For each input n, join the first n `<input>` elements with the set `s`. Then count the elements in the set.

### 3. Product, 157 bytes

```
e=$(s='[value=0],[value=1],[value=2],#out')
f=x=>e.slice('0',x.val()).each(i=>f(x.nextAll(s).first().append('<a>')))
f(e.first())
e.text($('#out a').length);

```

A recursive function that, given an element with value n, calls itself with the next element n times and appends an `<a>` to that next element. Then count the `<a>` elements in `<output>`.

Let me know if there are any mistakes or rule breaches.
> 2 votes

---
Tags: code-golf, restricted-source, javascript, set-theory
---


# Question
Title: Find the simplest value between two values
## Goal

Your goal is to find the *simplest* value in an open interval. In other words, given two values `a,b` with `a<b`, output the simplest `x` with `a<x<b`. This is a code golf, so fewest bytes wins.

## Simplicity

All values in this problem are dyadic rationals, which means their binary expansions are finite, or equivalently, are rationals in simplest form `a/2^b` for some integer `a` and non-negative integer `b`. Integers are dyadic rationals with `b=0`.

Being *simpler* means having smaller `b`, tiebroken by smaller absolute value `|a|`.

Equivalently in terms of binary expansions, to find the simpler number:

1. Take the one with a shorter fractional part (fewer binary digits after the point).
2. In case of tie, take the lexicographically earlier one with length the primary sort, ignoring sign.

So, the numbers in simplicity order are

```
0, ±1, ±2, ±3, ±4, ...
±1/2, ±3/2, ±5/2, ...
±1/4, ±3/4, ±5/4, ...
±1/8, ±3/8, ...
±1/16, ...
...

```

There's no need to say which of `±x` is simpler because any interval that contains both candidates also contains `0`, which is simpler than both.

(A bit of background and motivation: In combinatorial game theory, positions in a two-player games have a numerical value representing magnitude of advantage, with the sign saying which player is favored. This value is determined recursively from the two values resulting from the best move of each player. You might guess that one averages them, but in fact it's the simplest value in between.)

## Program requirements

Write, in as few bytes as possible, a *program* or *named function* that takes two dyadic rationals `a,b` and outputs the simplest dyadic rational `x` with `a<x<b`. Input can be function input or STDIN, and output can be function return or printing.

**Input format**

Two dyadic rationals `a,b` in whatever type your languages use for real or finite-precision binary values (float, double, etc). Fraction or rational types that store the value as a numerator and denominator are not acceptable. If you language has no valid type (and only then), you may use binary strings like `101.1101`, or post a comment and we'll work something out.

You are guaranteed that `a,b` are dyadic rationals and `a<b`. Integer values will be given like `3.0`, not `3`.

You can assume you have sufficient precision to store the values, the output, and any intermediate steps exactly. So, you shouldn't worry about precision or overflows. I won't give an explicit bound on inputs, but your algorithm should take a reasonable amount of time on inputs like the test cases.

You may take your two numbers in any reasonable built-in container like pair, tuple, list, array, or set. Structures specifically representing intervals are not allowed though.

**Output**

The simplest dyadic rational strictly between `a` and `b`. The same rules for the input types apply, except outputting `3` rather than `3.0` is OK.

**Test cases**

```
(-1.0, 1.0)
0.0
(0.0, 2.0)
1.0
(0.0, 4.0)
1.0
(0.5, 2.0)
1.0
(-3.25, -2.5)
-3.0
(-4, 1.375)
0.0
(4.5, 4.625)
4.5625
(-1.875, -1.5)
-1.75

```

# Answer
> 4 votes
# Python 2 - 100

I think I revised my entire method for this answer a good 4 or 5 times (which is probably an indication that it's a good code-golf question). I don't know if this answer can be golfed down any more but I do feel as if I'm missing some more clever methodological ways to shorten this.

```
def f(a,b,i=1.):
    r=0if a<0 else(a*i+1)//1/i
    return-f(-b,-a,i)if b<=0 else r if r<b else f(a,b,i*2)

```

# Answer
> 4 votes
# Haskell, ~~61~~ ~~88~~ ~~75~~ 73

```
p!q|p<0= -(-q)!(-p)|r<q=max r 0|0<1=(2*p)!(2*q)/2where r=toEnum$floor$p+1

```

this checks if there is a whole number between the two, and if yes, return the smallest one. if not, multiply the numbers by 2, apply them recursively, divide by 2 and return.
at least, this is how it works in my mind. the actual code is a bit different.

thanks to xnor for his rounding magic

# Answer
> 1 votes
## Java - ~~157~~ ~~187~~ 186

Probably could be golfed more.

Thanks to Quincunx for a byte.

```
void f(float a,float b){for(float i=1,d;;i*=2){for(d=0;d<i*Math.max(Math.abs(b),Math.abs(a));d++){for(float x:new float[]{d/i,-d/i}){if(x<b&&x>a){System.out.print(x);System.exit(0);}}}}}

```

Brute forces all values of the numerator (positive and negative) while the denominator doubles each time.

# Answer
> 1 votes
# C, 98 bytes

Using a recursive algorithm (and the fact that f(a,b) = f(2\*a,2\*b)/2). I also removed some bugs. The right answer is:

```
float n(float a, float b){return (floor(a+1)<ceil(b))?(a<0?(b>0?0:ceil(b-1)):floor(a+1)):n(2*a,2*b)/2;}

```

Which, to meet the prerequisites, is 19 bytes longer than the original one (of 79 bytes)

Full code:

```
#include <stdio.h>
#include <math.h>
float n(float a, float b){return (floor(a+1)<ceil(b))?(a<0?(b>0?0:ceil(b-1)):floor(a+1)):n(2*a,2*b)/2;}
main()
{
    float a = -4.0;
    float b = -1.4;
    printf("%f",n(a,b));
}

```

Just copy-paste it into a random online c compiler and run it.

# Answer
> 1 votes
# Perl (89)

most probably this can still be golfed

```
sub S{($q,$w)=@_;$m=1,$r=0;until($q<$r&&$r<$w){$r=int$q+1;$r<$w||map$_*=2,$m,$q,$w}$r/$m}

```

# Answer
> 1 votes
## Python 3: 80 bytes

```
g=lambda a,b:-g(-b,-a)if b<=0 else int(a+1)*(a>=0)if-~int(a)<b else g(2*a,2*b)/2

```

Ungofed:

```
def g(a,b):
    if b<=0:return -g(-b,-a)
    if int(a+1)<b:return int(a+1)*(a>=0)
    return g(2*a,2*b)/2

```

Can probably be golfed more by changing the `if/else` structure to `and/or`. The obvious transformation fails due to non-short-circuiting on the Falsey output of `0`, but there's likely a rearrangement that does it.

The space in `b<=0 else` can't be removed as usual because the start letter `e` is parsed as part of number literals like `1e6`.

# Answer
> 1 votes
# ES6, ~~68~~ ~~67~~ 59

```
g=(a,b)=>(x=~~(a+1),b>0?x<b?x*(x>0):g(2*a,2*b)/2:-g(-b,-a))

```

this is a port of xnor's solution (basically, the new thing in it was that it checked for having `0` in the range by `*(a>=0)`. couldn't do this in Haskell because Haskell has a type system :) )

this is the first time I used ES6 ever, so this might still be golfable.

---
Tags: code-golf, math, binary, rational-numbers
---