title: 3 and 5 Litre Jug Puzzle

text:
# Question
Title: 3 and 5 Litre Jug Puzzle
You may have seen this one in *Die Hard: With a Vengeance*... This question is based on the famous 3 and 5 Litre Jug Puzzle, but with a slightly different slant.

Golf up some code that when given an integer between 1 and 100 will provide you with the quickest instructions to measure out into a tank, the corresponding number of litres of water from a fountain, using a 3 litre jug and a 5 litre jug.

There are no gradations on either of the jugs; the fountain is abundant in supply of water, and the tank is assumed to be emptied out upon the start of each execution of the code.

You cannot access water from the tank once it goes into the tank.

The format of execution is as follows:

**Input:**

`4` for example.

**Output**

Output each numbered step, as shown, followed by a tally of the volumes of the 5L jug, the 3L jug and the tank. Tally format also shown below. The number of steps must also be outputted at the end of the steps.

`1) Fill 5L jug`

`5L: 5, 3L: 0, T: 0`

`2) Pour from 5L jug into 3L jug`

`5L: 2, 3L: 3, T: 0`

`3) Empty 3L jug`

`5L: 2, 3L: 0, T: 0`

`4) Pour from 5L jug into 3L jug`

`5L: 0, 3L: 2, T: 0`

`5) Fill 5L jug`

`5L: 5, 3L: 2, T: 0`

`6) Pour from 5L jug into 3L jug`

`5L: 4, 3L: 3, T: 0`

`7) Pour from 5L jug into tank`

`5L: 0, 3L: 3, T: 4`

`Volume measured out in 7 turns`

Example 2

Input: `8`

Output:

`1) Fill 5L jug`

`5L: 5, 3L: 0, T: 0`

`2) Pour from 5L jug into tank`

`5L: 0, 3L: 0, T: 5`

`3) Fill 3L jug`

`5L: 0, 3L: 3, T: 5`

`4) Pour from 3L jug into tank`

`5L: 0, 3L: 0, T: 8`

`Volume measured out in 4 turns`

**Conventions**

1. `Fill xL jug` \- fills the associated jug to the top from the fountain
2. `Empty xL jug` \- empties the contents of the associated jug into the fountain
3. `Pour from xL jug into yL jug` \- Pours the contents of the xL jug into the yL jug
4. `Pour from xL jug into tank` \- Pours the contents of the xL jug into the tank

Shortest code wins.

# Answer
> 6 votes
## Ruby, ~~407~~ ~~376~~ ~~365~~ ~~331~~ ~~324~~ 323

This is getting kind of hard to read...

```
x=y=n=d=0
g=gets.to_i
"#{[43435,102,t=45,t,12,t,12,t,t][g+~d]||12}".chars{|c|n+=1
puts [eval(["x-=t=[3-y,x].min;y+=t"+t=";'Pour from 5L jug into 3L jug'","x=5;'Fill 5L jug'","d+=x;x=0"+t.sub(/3.+/,"tank'")][c.ord%3].tr t='35xy',c<?3?t:'53yx'),"5L: #{x}, 3L: #{y}, T: #{d}"]}while g>d
$><<"Volume measured out in #{n} turns"

```

Takes input on STDIN. Example run for N=10:

```
Fill 5L jug
5L: 5, 3L: 0, T: 0
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
Fill 5L jug
5L: 5, 3L: 0, T: 5
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 10
Volume measured out in 4 turns

```

# Answer
> 5 votes
# T-SQL 2012: ~~1410~~ 1302

Another quixotic attempt at a question in SQL, but this one offered an enjoyable opportunity to play with some of the new window function options in version 2012. In addition, it exploits recursive CTEs, which may be nothing impressive in most programming languages, but recursion in SQL is like switching from horse and buggy to a Ferrari.

The engine at the heart of this is in lines 5-12, which uses a recursive CTE and a window function to build a table of most of the numbers needed to solve the problem. Note in particular the test for 3, 4, 6, or 9, which ensures an optimal approach to the solution by 3s from those numbers onward. (Technically, it's a tie for 4 between the 3-1 approach and the 2-2, but doing it this way golfed me a lot of characters.) Then it's a simple matter to join to a lookup table of the optimal steps for different chunks of the problem and use another window function to properly number the steps.

If you don't have MS SQL lying around, play with it on SQLFiddle.

```
DECLARE @i INT=42,@l VARCHAR(9)='L jug ',@k VARCHAR(99)='into tank
5L: 0, 3L: 0, T: ',@o VARCHAR(99)='
5L: 5, 3L: 0, T: ',@n CHAR(1)='
',@5 VARCHAR(99)=') Pour from 5',@3 VARCHAR(99)=') Pour from 3'
;WITH t AS (SELECT @i i,(@i-@i%5)%5 j
UNION ALL
SELECT i-5,(i-i%5)%5+5 FROM t WHERE i>=5 AND i NOT IN(6,9)
UNION ALL
SELECT i-3,3FROM t WHERE i in(3,4,6,9)
UNION ALL
SELECT i-i,i FROM t WHERE i<3 AND i>0)
SELECT t.i,t.j,v.s,ROW_NUMBER()OVER(PARTITION BY t.j ORDER BY t.i DESC)x,SUM(t.j)OVER(ORDER BY t.i DESC ROWS UNBOUNDED PRECEDING)y INTO #q FROM(VALUES(1,5),(2,3),(3,2),(5,2))v(i,s) JOIN t ON t.j = v.i
SELECT z.b FROM(SELECT ROW_NUMBER()OVER(ORDER BY q.i DESC,w.s)a,CAST(ROW_NUMBER()OVER(ORDER BY q.i DESC,w.s)AS VARCHAR)+w.v+CAST(y-CASE WHEN q.s!=w.s THEN q.j ELSE 0 END AS VARCHAR)b
FROM(VALUES(5,1,') Fill 5'+@l+@o),(5,2,@5+@l+@k),(3,1,') Fill 3'+@l+@n+'5L: 0, 3L: 3, T: '),(3,2,@3+@l+@k),(2,1,') Fill 5'+@l+@o),(2,2,@5+@l+' into 3'+@l+@n+'5L: 2, 3L: 3, T: '),(2,3,@5+@l+@k),(1,1,') Fill 3'+@l+@n+'5L: 0, 3L: 3, T: '),(1,2,@3+@l+'into 5'+@l+@n+'5L: 3, 3L: 0, T: '),(1,3,') Fill 3'+@l+@n+'5L: 3, 3L: 3, T: '),(1,4,@3+@l+'into 5'+@l+@n+'5L: 5, 3L: 1, T: '),(1,5,@3+@l+'into tank'+@o))w(i,s,v)JOIN #q q ON w.i=q.j
UNION
SELECT 99,'Volume measured out in '+CAST(COUNT(*)AS VARCHAR)+' turns'
FROM #q)z

```

Results for the input 42:

```
1) Fill 5L jug
5L: 5, 3L: 0, T: 0
2) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
3) Fill 5L jug
5L: 5, 3L: 0, T: 5
4) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 10
5) Fill 5L jug
5L: 5, 3L: 0, T: 10
6) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 15
7) Fill 5L jug
5L: 5, 3L: 0, T: 15
8) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 20
9) Fill 5L jug
5L: 5, 3L: 0, T: 20
10) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 25
11) Fill 5L jug
5L: 5, 3L: 0, T: 25
12) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 30
13) Fill 5L jug
5L: 5, 3L: 0, T: 30
14) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 35
15) Fill 5L jug
5L: 5, 3L: 0, T: 35
16) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 40
17) Fill 5L jug
5L: 5, 3L: 0, T: 40
18) Pour from 5L jug  into 3L jug
5L: 2, 3L: 3, T: 40
19) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 42
Volume measured out in 9 turns

```

### Edit:

Golfed out a decent score improvement by

* eliminating an unnecessary +5 in the first row of the CTE, and the WHERE clause it necessitated
* in-lining the VALUES tables, saving costly DECLARE statements
* remembering to convert Windows double-byte CRLFs to Unix style this time.

# Answer
> 5 votes
# Javascript: 481

First attempt at golfing, advice appreciated

```
n=["3L jug","5L jug","tank"];l=[0,0,0];t=[3,5,0];h=0;c=console;function e(d){l[d]=t[d];c.log(++h+") Fill "+n[d]);k()}function m(d,g){s=l[d];f=l[g];b=s+f>t[g];l[g]=b?t[g]:f+s;l[d]=b?s-(t[g]-f):0;c.log(++h+") Pour from "+n[d]+" into "+n[g]);k()}function k(){c.log("5L: "+l[1]+", 3L: "+l[0]+", T: "+l[2])}a=prompt();for(t[2]=a;4<a;)e(1),m(1,2),a-=5;2<a&&(e(0),m(0,2),a-=3);1<a&&(e(1),m(1,0),m(1,2),a=0);0<a&&(e(0),m(0,1),e(0),m(0,1),m(0,2));c.log("Volume measured out in "+h+" turns")

```

It messes up with some numbers because it doesn't check if it's better to pour 3 or 5, example: 9 gives 9 turns instead of 6, I might fix it later

Paste it in console

From 553 to 481 thanks to @WallyWest

# Answer
> 3 votes
## **Java, 610**

```
class X{int n,c=0,t=0;public void static main(String[]a){n=Integer.parseInt(a[0]);String s,b,f,k,m,u;b="5L";s="3L";k="tank";u="Fill %s jug\n5L: %d, 3L: %d, T: %d";m="\nPour from %s jug into %s\n5L: %d, 3L: %d, T: %d";f=u+m;for(;n>4;)z(f,2,5,b,5,0,t,b,k,0,0,t+=5);while(n!=0){if(n==1)z(f+f+m,5,1,s,0,3,t,s,b,3,0,t,s,3,3,t,s,b,5,1,t,s,k,5,0,t+1);if(n==3)z(f,2,3,s,0,3,t,s,k,0,0,t+3);z(f+m,3,2,b,5,0,t,b,s,2,3,t,b,k,0,3,t+=2);if(n==2)z("Empty 3L jug\n5L: 0, 3L: 0,T: %d",1,0,t)}z("Volume measured out in %d turns",0,0,c)}void z(String s,int o,int w,Object...a){c+=o;n-=w;System.out.println(String.format(s,a))}}

```

I took the solution of Sumedh and golfed it. I wanted to put it in the comments but my reputation isn't enough :( . It's a 40% less, I think it should at least be shared. Still far from first though...

Here is ungolfed:

```
    class X{
    int n,c=0,t=0;
    public void static main(String[] a){
        n=Integer.parseInt(a[0]);
        String s,b,f,k,m,u;
        b="5L";
        s="3L";
        k="tank";
        u="Fill %s jug\n5L: %d, 3L: %d, T: %d";
        m="\nPour from %s jug into %s\n5L: %d, 3L: %d, T: %d";
        f=u+m;
        for(;n>4;)z(f,2,5,b,5,0,t,b,k,0,0,t+=5);
        while(n!=0)
        {
            if(n==1)z(f+f+m,5,1,s,0,3,t,s,b,3,0,t,s,3,3,t,s,b,5,1,t,s,k,5,0,t+1);
            if(n==3)z(f,2,3,s,0,3,t,s,k,0,0,t+3);
            z(f+m,3,2,b,5,0,t,b,s,2,3,t,b,k,0,3,t+=2);
            if(n==2)z("Empty 3L jug\n5L: 0, 3L: 0,T: %d",1,0,t);
        }
        z("Volume measured out in %d turns",0,0,c);
    }
    void z(String s,int o, int w,Object... a){
        c+=o;
        n-=w;
        System.out.println(String.format(s,a));
    }
}

```

**NB:** it works only on the first run. Rerun it and the result will be wrong (due to a global variable).

The following version is safe, but we lose 2 char, going from 610 to 612:

```
    class X{
    int n,c,t;
    public void static main(String[] a){
        n=Integer.parseInt(a[0]);
        String s,b,f,k,m,u;
        t=c=0;
        b="5L";
        s="3L";
        k="tank";
        u="Fill %s jug\n5L: %d, 3L: %d, T: %d";
        m="\nPour from %s jug into %s\n5L: %d, 3L: %d, T: %d";
        f=u+m;
        for(;n>4;)z(f,2,5,b,5,0,t,b,k,0,0,t+=5);
        while(n!=0)
        {
            if(n==1)z(f+f+m,5,1,s,0,3,t,s,b,3,0,t,s,3,3,t,s,b,5,1,t,s,k,5,0,t+1);
            if(n==3)z(f,2,3,s,0,3,t,s,k,0,0,t+3);
            z(f+m,3,2,b,5,0,t,b,s,2,3,t,b,k,0,3,t+=2);
            if(n==2)z("Empty 3L jug\n5L: 0, 3L: 0,T: %d",1,0,t);
        }
        z("Volume measured out in %d turns",0,0,c);
    }
    void z(String s,int o, int w,Object... a){
        c+=o;
        n-=w;
        System.out.println(String.format(s,a));
    }
}

```

Sample output for N=69:

```
Fill 5L jug
5L: 5, 3L: 0, T: 0
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
Fill 5L jug
5L: 5, 3L: 0, T: 5
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 10
Fill 5L jug
5L: 5, 3L: 0, T: 10
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 15
Fill 5L jug
5L: 5, 3L: 0, T: 15
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 20
Fill 5L jug
5L: 5, 3L: 0, T: 20
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 25
Fill 5L jug
5L: 5, 3L: 0, T: 25
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 30
Fill 5L jug
5L: 5, 3L: 0, T: 30
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 35
Fill 5L jug
5L: 5, 3L: 0, T: 35
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 40
Fill 5L jug
5L: 5, 3L: 0, T: 40
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 45
Fill 5L jug
5L: 5, 3L: 0, T: 45
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 50
Fill 5L jug
5L: 5, 3L: 0, T: 50
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 55
Fill 5L jug
5L: 5, 3L: 0, T: 55
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 60
Fill 5L jug
5L: 5, 3L: 0, T: 60
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 65
Fill 5L jug
5L: 5, 3L: 0, T: 65
Pour from 5L jug into 3L
5L: 2, 3L: 3, T: 65
Pour from 5L jug into tank
5L: 0, 3L: 3, T: 67
Empty 3L jug
5L: 0, 3L: 0,T: 67
Fill 5L jug
5L: 5, 3L: 0, T: 67
Pour from 5L jug into 3L
5L: 2, 3L: 3, T: 67
Pour from 5L jug into tank
5L: 0, 3L: 3, T: 69
Volume measured out in 33 turns

```

# Answer
> 2 votes
# Java: 984

Here's the code

```
class X{public static void main(String[] s){int n=Integer.parseInt(s[0]);int t=0;int c=0;while(n>4){n-=5;System.out.println("Fill 5L jug\n5L: 5, 3L: 0, T: "+t+"\nPour from 5L jug into tank\n5L: 0, 3L: 0, T: "+(t+5));t+=5;c+=2;}while(n!=0){switch(n){case 1:System.out.println("Fill 3L jug\n5L: 0, 3L: 3, T: "+t+"\nPour from 3L jug into 5L jug\n5L: 3, 3L: 0, T: "+t+"\nFill 3L jug\n5L: 3, 3L: 3, T: "+t+"\nPour from 3L jug into 5L jug\n5L: 5, 3L: 1, T: "+t+"\nPour from 3L jug into tank\n5L: 5, 3L: 0, T: "+(t+1));n=0;c+=5;break;case 3:System.out.println("Fill 3L jug\n5L: 0, 3L: 3, T: "+t+"\nPour from 3L jug into tank\n5L: 0, 3L: 0, T: "+(t+3));n=0;c+=2;break;default:System.out.println("Fill 5L jug\n5L: 5, 3L: 0, T: "+t+"\nPour from 5L jug into 3L jug\n5L: 2, 3L: 3, T: "+t+"\nPour from 5L jug into tank\n5L: 0, 3L: 0, T: "+(t+2));n-=2;c+=3;t+=2;if(n==2){System.out.println("Empty 3L jug\n5L: 0, 3L: 0,T: "+t);c++;}break;}}System.out.println("Volume measured out in "+c+" turns");}}

```

Input is from command line. for example: java X 4

# Answer
> 2 votes
## Python 2.7 - 437

Not the shortest code, but I think this is the most optimal way of solving this.

As I stated in the comments, the most optimal way to calculate this:

1. Take as many chunks of 5L as possible - `divmod(amount,5)`. This will give you one of 4,3,2,1 as the remainder.
2. Take 3 (if possible) from the remainder.
3. Which leaves either 1 or 2 as the remainder. Use the optimal solution for either which can be known ahead of time as:

1. 1L, 5 steps : 3L -\> 5L, 3L -\> 5L, leaving 1L in the 3L, 3L (holding 1L) -\> tank
    2. 2L, 3 steps : 5L -\> 3L, leaves 2L in the 5L, 5L (holding 2L) -\> tank

The code:

```
j,T="%dL jug","tank"
A="\n5L: %d, 3L: %d, T: %d"
F,P="Fill "+j+A,"Pour from "+j+" into %s"+A
f,r=divmod(input(),5)
o,t=f*5,[]
for i in range(f):o+=[F%(5,5,0,5*i),P%(5,T,0,0,5*i+5)]
if r>2:o+=[F%(3,0,3,t),P%(3,T,0,0,t+3)];r-=3;t+=3
if r==2:o+=[F%(5,5,0,t),P%(5,j%3,2,3,t),P%(5,T,0,3,t+2)]
if r==1:o+=[F%(3,0,3,t),P%(3,j%5,3,0,t),F%(3,3,3,t),P%(3,j%5,5,1,t),P%(3,T,5,0,t+1)]
print"\n".join(o),'\n',"Volume measured out in %d turns"%len(o)

```

And an output for 4L in 7 steps:

```
Fill 3L jug
5L: 0, 3L: 3, T: 0
Pour from 3L jug into tank
5L: 0, 3L: 0, T: 3
Fill 3L jug
5L: 0, 3L: 3, T: 3
Pour from 3L jug into 5L jug
5L: 3, 3L: 0, T: 3
Fill 3L jug
5L: 3, 3L: 3, T: 3
Pour from 3L jug into 5L jug
5L: 5, 3L: 1, T: 3
Pour from 3L jug into tank
5L: 5, 3L: 0, T: 4
Volume measured out in 7 turns

```

# Answer
> 2 votes
# C, 567 609

```
#define r printf
#define l r("5L: %d, 3L: %d, T: %d\n", a, b, T);
#define j(x,y,z,w) r("%d) "#x" %dL jug\n", i++, y),z=w,l
#define e j(Empty,3,b,0)
#define f j(Fill,5,a,5)
#define g j(Fill,3,b,3)
#define o(x,y,z,w) r("%d) Pour from %dL jug into "x"\n", i++, y,z),w;l
#define t(x,y) T+=x,o("tank",y,0,x=0)
#define p(x) o("%dL jug",5,3,(a-=x,b+=x))
int N,T,i;q(x){int a=0,b=0;switch(x){case 5:f t(a,5) break;case 3:g t(b,3) break;case 1:case 2:case 4:f if(x-2){e p(2)f p(1)if(x-4){e p(3)}}t(a,5)}N-=x;}main(){T=0,i=1,scanf("%d",&N);while(N>5)q((N-6)&&(N-9)?5:3);q(N);r("Volume measured out in %d turns",i-1);}

```

previous invalid version:

```
#define r printf
#define l r("5L: %d, 3L: %d, T: %d\n", a, b, T);
#define j(x,y,z,w) r("%d) "#x" %dL jug\n", i++, y),z=w,l
#define e j(Empty,3,b,0)
#define f j(Fill,5,a,5)
#define g j(Fill,3,b,3)
#define o(x,y,z,w) r("%d) Pour from %dL jug into "x"\n", i++, y,z),w;l
#define t o("tank",5,0,a=0)
#define p(x) o("%dL jug",5,3,(a-=x,b+=x))
int N,T,i;q(x){int a=0,b=0;switch(x){case 5:f t break;case 3:g t break;case 1:case 2:case 4:f if(x-2){e p(2)f p(1)if(x-4){e p(3)}}t}N-=x;}main(){T=0,i=1,scanf("%d",&N);while(N>5)q(5);q(N);r("Volume measured out in %d turns",i-1);}

```

and here is the code degolfed:

```
#define r printf
#define l r("5L: %d, 3L: %d, T: %d\n", a, b, T);
#define j(x,y,z,w) r("%d) "#x" %dL jug\n", i++, y),z=w,l
#define e j(Empty,3,b,0)
#define f j(Fill,5,a,5)
#define g j(Fill,3,b,3)
#define o(x,y,z,w) r("%d) Pour from %dL jug into "x"\n", i++, y,z),w;l
#define t o("tank",5,0,a=0)
#define p(x) o("%dL jug",5,3,(a-=x,b+=x))
int N,T,i;
q(x)
{
    int a=0,b=0;
    switch(x)
    {
        case 5:
            f
            t
            break;
        case 3:
            g
            t
            break;
        case 1:
        case 2:
        case 4:
            f
            if(x-2)
            {
                e
                p(2)
                f
                p(1)
                if(x-4)
                {
                    e
                    p(3)
                }
            }
            t
    }
    N-=x;
}
main()
{
    T=0,i=1,scanf("%d",&N);
    while(N>
    5)q(5);
    q(N);
    r("Volume measured out in %d turns",i-1);
}

```

# Answer
> 2 votes
# Smalltalk (Smalltalk/X), 568 560 516

input in n:

```
    T:=j:=J:=c:=0.m:={'Pour from'.' into'.' 3L jug'.' 5L jug'.[j:=j+3.'Fill'].[J:=J+5.'Fill'].[t:=j.j:=0.''].[t:=J.J:=0.''].[r:=j min:5-J.j:=j-r.J:=J+r.''].[r:=J min:3-j.J:=J-r.j:=j+r.''].[T:=T+t.' into tank'].[c:=c+1.'\5L: %1 3L: %2 T: %3\'bindWith:J with:j with:T].['Volume measured out in %1 turns'bindWith:c]}.[n>=0]whileTrue:[s:=n.n:=0.(s caseOf:{0->[n:=-1.'<'].1->'42;02813;42;02813;062:;'.2->'53;03912;073:;'.3->'42;062:;'.4->[n:=1.'42;062:;']}otherwise:[n:=s-5.'53;073:;'])do:[:c|(m at:c-$/)value withCRs print]]

```

boy this is definitely the most obfuscated program I've ever written...

Edit: Some other Smalltalks may not allow autodeclared workspace variables and you'll have to prepend declarations. Also bindWith: may be different (expandWith:'\<p\>').

sample output for n=17:

```
Fill 5L jug
5L: 5, 3L: 0, T: 0
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
Fill 5L jug
5L: 5, 3L: 0, T: 5
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 10
Fill 5L jug
5L: 5, 3L: 0, T: 10
Pour from 5L jug into tank
5L: 0, 3L: 0, T: 15
Fill 5L jug
5L: 5, 3L: 0, T: 15
Pour from 5L jug into 3L jug
5L: 2, 3L: 3, T: 15
Pour from 5L jug into tank
5L: 0, 3L: 3, T: 17
Volume measured out in 9 turns

```

# Answer
> 2 votes
# C (480 465 bytes)

```
#define P printf(
#define O(x) P"%d) Pour from %dL jug into "x"\n"
#define S P"5L: %d, 3L: %d, T: %d\n",F,H,g);}
F,H,s,g,x;l(j){P"%d) Fill %dL jug\n",++s,j);St(j,o,m){O("%dL jug"),++s,j,(j^5)?5:3);Se(j,i){O("tank"),++s,j);Smain(){scanf("%d",&x);while(x>4){x-=5;l(F=5);g+=5;e(5,F=0);}while(x>2){x-=3;l(H=3);g+=3;e(3,H=0);}(x^2)?(x^1)?0:(l(H=3),t(3,H=0,F=3),l(H=3),t(3,H=1,F=5),g++,e(3,H=0)):(l(F=5),t(5,F=2,H=3),g+=2,e(5,F=0));P"Volume measured out in %d turns",s);}

```

**Optimal version (adds 10 bytes)**

```
#define P printf(
#define O(x) P"%d) Pour from %dL jug into "x"\n"
#define S P"5L: %d, 3L: %d, T: %d\n",F,H,g);}
F,H,s,g,x;l(j){P"%d) Fill %dL jug\n",++s,j);St(j,o,m){O("%dL jug"),++s,j,(j^5)?5:3);Se(j,i){O("tank"),++s,j);Smain(){scanf("%d",&x);while(x>4&&x^6&&x^9){x-=5;l(F=5);g+=5;e(5,F=0);}while(x>2){x-=3;l(H=3);g+=3;e(3,H=0);}(x^2)?(x^1)?0:(l(H=3),t(3,H=0,F=3),l(H=3),t(3,H=1,F=5),g++,e(3,H=0)):(l(F=5),t(5,F=2,H=3),g+=2,e(5,F=0));P"Volume measured out in %d turns",s);}

```

Likely more golfing to be done here - the output functions were killing me. This should give the optimal solution (least number of steps). Similar to other code here, it fills and empties 5L jugs until it gets below 5 and then switches to 3L jugs. It tests for 2 special cases (6 and 9) and if it finds them switches to 3L jugs. The instructions for getting 1L and 2L are hard coded.

**More readable version:**

```
#define P printf(
#define O(x) P"%d) Pour from %dL jug into "x"\n"
#define S P"5L: %d, 3L: %d, T: %d\n",F,H,g);}
F,H,s,g,x;
l(j)
{
    P"%d) Fill %dL jug\n",++s,j);S

t(j,o,m)
{
    O("%dL jug"),++s,j,(j^5)?5:3);S

e(j,i)
{
    O("tank"),++s,j);S

main()
{
    scanf("%d",&x);
    //while(x>4&&x^6&&x^9)     <--optimal version
    while(x>4)
    {
        x-=5;l(F=5);g+=5;e(5,F=0);
    }
    while(x>2)
    {
        x-=3;l(H=3);g+=3;e(3,H=0);
    }
    (x^2)?
        (x^1)?
            0
             :
            (l(H=3),t(3,H=0,F=3),l(H=3),t(3,H=1,F=5),g++,e(3,H=0))
             :(l(F=5),t(5,F=2,H=3),g+=2,e(5,F=0));
    P"Volume measured out in %d turns",s);
}

```

**Edits:**

* Removed 10 bytes that gave the optimum performance for the scored version based on the OP's clarification.
* Shave 5 bytes by converting function to definition.

**Test output for n = 11 (optimal version):**

```
11
1) Fill 5L jug
5L: 5, 3L: 0, T: 0
2) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
3) Fill 3L jug
5L: 0, 3L: 3, T: 5
4) Pour from 3L jug into tank
5L: 0, 3L: 0, T: 8
5) Fill 3L jug
5L: 0, 3L: 3, T: 8
6) Pour from 3L jug into tank
5L: 0, 3L: 0, T: 11
Volume measured out in 6 turns

```

# Answer
> 2 votes
## T-SQL(2012): 794 689 580

Inspired by @Jonathan-Van-Matre 's T-SQL answer in combination with @Lego-Stormtroopr's algorithm. I wanted to do this because I enjoyed the 99 Bottles of Beer challenge so much.

I tried to keep window (`OVER`) functions at a minimum in preference of math/bool functions.

SQLFiddle is here.

```
WITH n AS(SELECT 11 n UNION ALL SELECT n-IIF(n>4,5,3)FROM n WHERE n>2)SELECT n, a,LEN(a)L,i=IDENTITY(INT,1,1),'L jug'j INTO #t FROM n JOIN(VALUES(3303),(33900),(5550),(55900),(2550),(259323),(25903),(1303),(139530),(1333),(139551),(13950))x(a)ON RIGHT(LEFT(12335,n),1)=LEFT(a,1)ORDER BY n DESC SELECT LTRIM(i)+') '+REPLACE(IIF(L=4,'Fill ','Pour ')+RIGHT(a/100,L-3),9,j+' into ')+IIF(L=5,'tank',j)  +'
5L: '+LTRIM((A%100)/10)+', 3L: '+LTRIM(A%10)+', T: '+LTRIM(SUM(IIF(L=5,LEFT(a,1),0))OVER(ORDER BY i))FROM #t UNION SELECT 'Volume measured out in ' +LTRIM(MAX(i))+' turns'FROM #t

```

Input: `11`

```
1) Fill 5L jug
5L: 5, 3L: 0, T: 0
2) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 5
3) Fill 5L jug
5L: 5, 3L: 0, T: 5
4) Pour from 5L jug into tank
5L: 0, 3L: 0, T: 10
5) Fill 3L jug
5L: 0, 3L: 3, T: 10
6) Pour from 3L jug into
5L jug 5L: 0, 3L: 3, T: 10
7) Fill 3L jug
5L: 3, 3L: 3, T: 10
8) Pour from 3L jug into 5L jug
5L: 5, 3L: 1, T: 10
9) Pour from 3L jug into tank
5L: 5, 3L: 0, T: 11
Volume measured out in 9 turns

```

Human-readable:

```
WITH n AS(
  SELECT 11 n
    UNION ALL
  SELECT n-IIF(n>4,5,3)
  FROM n
  WHERE n>2
)
SELECT n, a,LEN(a) L, i = IDENTITY(INT,1,1), 'L jug'j
INTO #t
FROM n
JOIN(VALUES
     (3303),(33900),
     (5550),(55900),
     (2550),(259323),(25903),
     (1303),(139530),(1333),(139551),(13950)
    )x(a)
ON RIGHT(LEFT(12335,n),1) = LEFT(a,1)
ORDER BY n DESC

 SELECT LTRIM(i)+') '
  + REPLACE(IIF(L=4,'Fill ','Pour ')
  + RIGHT(a/100,L-3),9,j+' into ')+IIF(L=5,'tank',j)
  +'
5L: ' + LTRIM((A%100)/10) + ', 3L: ' + LTRIM(A%10) + ', T: '
  + LTRIM(SUM(IIF(L=5,LEFT(a,1),0))OVER(ORDER BY i)) FROM #t
UNION ALL
 SELECT 'Volume measured out in ' +LTRIM(MAX(i))+' turns'FROM #t
 DROP TABLE #t

```

# Answer
> 1 votes
# Python 3 (417 chars)

```
P=print
D=divmod
N=['3L jug','5L jug','tank',0]
M=999
R=[0,0,0,M]
F=[3,5,M,M]
def o(a,b):k=a==3;P(['Pour from %s into %s','Empty %s','Fill %s'][k*2+(b==3)]%[(N[a],N[b]),(N[b])][k]);d=min(R[a],F[b]-R[b]);R[a]-=d;R[b]+=d;P('5L:',R[1],'3L:',R[0],'T:',R[2]);N[3]+=1
k,r=D(int(input()),5)
for i in'0'*k:o(3,1);o(1,2)
for x in['','c1c12','d46','c2','d434d46'][r]:o(*D(int(x,16),4))
P('Volume measured out in',N[3],'turns')

```

## Explained

Note that we have 4 objects, namely, the 3L jug, the 5L jug, the tank, and the foutain. The only operations we can do is to move water from object `a` to object `b`. This is what function `o(a, b)` do in my code, it move water and print it and keep counting.

## Tricks

* `N=['3L jug','5L jug','tank',0]`. Here I need the last element to avoid `IndexError`. Also, it can be used as the global counting variable, without the expansive `global` keyword. For example, `N[3] += 1`
* Since `0 <= a < 4, 0 <= b < 4` in function `o(a, b)`, we can encode `(a, b)` into a hex digit using `(a << 2) | b`, and decode it using `divmod(x, 4)`. With this trick, all 5 solutions(`reminder=0, 1, 2, 3, 4`), can be encoded into array `['','c1c12','d46','c2','d434d46']`, which is a little bit shorter than it's original form:

`A=[
 (),
 ((3,0),(0,1),(3,0),(0,1),(0,2)),
 ((3,1),(1,0),(1,2)),
 ((3,0),(0,2)),
 ((3,1),(1,0),(0,3),(1,0),(3,1),(1,0),(1,2))
]`

## Sample Output(n = 17)

```
17
Fill 5L jug
5L: 5 3L: 0 T: 0
Pour from 5L jug into tank
5L: 0 3L: 0 T: 5
Fill 5L jug
5L: 5 3L: 0 T: 5
Pour from 5L jug into tank
5L: 0 3L: 0 T: 10
Fill 5L jug
5L: 5 3L: 0 T: 10
Pour from 5L jug into tank
5L: 0 3L: 0 T: 15
Fill 5L jug
5L: 5 3L: 0 T: 15
Pour from 5L jug into 3L jug
5L: 2 3L: 3 T: 15
Pour from 5L jug into tank
5L: 0 3L: 3 T: 17
Volume measured out in 9 turns

```

# Answer
> 1 votes
COBOL (IBM Enterprise COBOL) 192 *lines* of 72 characters

This is a Proof of Concept for the Question, and the start of one for Golf-COBOL :-)

The question asks for the quickest. So, implement parallelism. Even one person can readily fill one 3L jug and one 5L jug at the same time.

Simply divide the input by eight, also leaving the remainder. Do some quick 5L/3L fills to the number of times eight fits exactly, then deal with the one through seven litres remaining.

The most interesting of the remainder is for four litres. Doing it as one litre plus three litres pushes a lot less water around, only 18 litres vs 23 for the other possibilities.

The Code (working)

```
   ID DIVISION
   PROGRAM-ID
   DATA DIVISION
   WORKING-STORAGE SECTION
   1.
   88 g1 VALUE ' '.
   2  PIC X
   88 H VALUE 'F'.
   88 I VALUE 'E'.
   88 J VALUE 'T'.
   2 PIC X
   88 K VALUE 'F'.
   88 L VALUE 'E'.
   88 M VALUE 'T'.
   1 R
   2 A1 PIC 999
   2 B PIC 99
   2 C PIC 9
   1 E
   2 e2 PIC X(120) VALUE "  ) Fill both jugs"
   2 e3 PIC X(120)
   88 O VALUE "5L: 0, 3L: 0, T: 000".
   2 e4 PIC X(120) VALUE "  ) Empty both jugs"
   2 e5 PIC X(120)
   2 e1 occurs 32 depending on p pic x(240)
   2 e6 pic x(99)
   1 F PIC 999 VALUE 0
   1 P PIC 99 VALUE 0
   1 P1 PIC 99
   PROCEDURE DIVISION
   ACCEPT A1
   DIVIDE A1 BY 8 GIVING B REMAINDER C
   set o to true
   move e3 to e5
   move 5 to e3(5:1)
   move 3 to e3(12:1)
   PERFORM D1 B TIMES
   EVALUATE C
   WHEN 1
   MOVE ZERO TO R
   SET K TO TRUE
   PERFORM N
   SET M TO TRUE
   PERFORM N
   SET K TO TRUE
   PERFORM N
   SET M TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   WHEN 2
   MOVE ZERO TO R
   SET H TO TRUE
   PERFORM N
   SET J TO TRUE
   PERFORM N
   SET I TO TRUE
   PERFORM N
   WHEN 3
   MOVE ZERO TO R
   SET K TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   WHEN 4
   MOVE ZERO TO R
   SET K TO TRUE
   PERFORM N
   SET M TO TRUE
   PERFORM N
   SET K TO TRUE
   PERFORM N
   SET M TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   SET K TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   WHEN 5
   MOVE ZERO TO R
   SET H TO TRUE
   PERFORM N
   SET I TO TRUE
   PERFORM N
   WHEN 6
   MOVE ZERO TO R
   SET K TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   SET K TO TRUE
   PERFORM N
   SET L TO TRUE
   PERFORM N
   WHEN 7
   MOVE ZERO TO R
   SET H TO TRUE
   PERFORM N
   SET I TO TRUE
   PERFORM N
   SET H TO TRUE
   PERFORM N
   SET J TO TRUE
   PERFORM N
   SET I TO TRUE
   PERFORM N
   END-EVALUATE
   string "Volume measured out in " delimited size P " turns"
   delimited size into e6
   if  e6(24:1) = 0
   move e6(25:) to e6 (24:)
   end-if
   move p to p1
   perform d2 p times
   DISPLAY E(481:)
   GOBACK
   D1
   ADD 1 TO P
   MOVE P TO E(1:2)
   move e2 to e1(p)
   move e3 to e1(p)(121:)
   ADD 1 TO P
   MOVE P TO E(241:2)
   ADD 8 TO F
   MOVE F TO E(378:3)
   move e4 to e1(p)
   move e5 to e1(p)(121:)
   MOVE F TO E(138:3)
   N
   ADD 1 TO P
   SET O TO TRUE
   EVALUATE TRUE
   WHEN K

   MOVE 3 TO B
   string p delimited size ") Fill 3L jug" delimited by size
   into e1(p)
   WHEN M
   COMPUTE C = C + B
   IF  C > 5
   COMPUTE B = C - 5
   MOVE 5 TO C
   ELSE
   MOVE 0 TO B
   END-IF
   string  P delimited size ") Pour from 3L jug into 5L jug"
   delimited size into e1(p)
   WHEN L
   ADD B TO F
   MOVE 0 TO B
   string  P delimited size ") Empty 3L jug into tank"
   delimited size into e1(p)
   END-EVALUATE
   EVALUATE TRUE
   WHEN H
   MOVE 5 TO C
   string  P delimited size ") Fill 5L jug"
   delimited size into e1(p)
   WHEN J
   COMPUTE B = C + B
   IF  B > 3
   COMPUTE C = B - 3
   MOVE 3 TO B
   ELSE
   MOVE 0 TO C
   END-IF
   string  P delimited size ") Pour from 5L jug into 3L jug"
   delimited size into e1(p)
   WHEN I
   ADD C TO F
   MOVE 0 TO C
   string  P delimited size ") Empty 5L jug into tank"
   delimited size into e1(p)
   END-EVALUATE
   string  "5L: " delimited size
       C delimited size ", 3L: " delimited size B(2:)
   ", T: " delimited size F delimited size
   into e1(p)(121:)
   SET g1 TO TRUE
   d2
   perform d3 2 times
   if  e1(p1)(1:1) = 0
   move e1(p1)(2:) to e1(p1)(1:120)
   end-if
   subtract 1 from p1
   d3
   if  e1(p1)(138:1) = 0
   move e1(p1)(139:) to e1(p1)(138:)
   end-if

```

This gets an absolute shed-load of diagnostic messages for code starting in the wrong place and shortage of required full-stops.

None of the diagnostics indicate any impact on the object code. So, despite it being a busted RC=8 I know the object will be OK, so linked it and ran it.

Here are the outputs for one to eight litres. After that, all results can be intuited. 17 and 100 are included as examples of the parallelism.

There is still much that can be done to squeeze the program down in characters, the correct output was the important thing first. Counting the characters when they are on fixed-length lines is another thing entirely.

Sample output:

```
1) Fill 3L jug
5L: 0, 3L: 3, T: 0
2) Pour from 3L jug into 5L jug
5L: 3, 3L: 0, T: 0
3) Fill 3L jug
5L: 3, 3L: 3, T: 0
4) Pour from 3L jug into 5L jug
5L: 5, 3L: 1, T: 0
5) Empty 3L jug into tank
5L: 5, 3L: 0, T: 1
Volume measured out in 5 turns

1) Fill 5L jug
5L: 5, 3L: 0, T: 0
2) Pour from 5L jug into 3L jug
5L: 2, 3L: 3, T: 0
3) Empty 5L jug into tank
5L: 0, 3L: 3, T: 2
Volume measured out in 3 turns

1) Fill 3L jug
5L: 0, 3L: 3, T: 0
2) Empty 3L jug into tank
5L: 0, 3L: 0, T: 3
Volume measured out in 2 turns

1) Fill 3L jug
5L: 0, 3L: 3, T: 0
2) Pour from 3L jug into 5L jug
5L: 3, 3L: 0, T: 0
3) Fill 3L jug
5L: 3, 3L: 3, T: 0
4) Pour from 3L jug into 5L jug
5L: 5, 3L: 1, T: 0
5) Empty 3L jug into tank
5L: 5, 3L: 0, T: 1
6) Fill 3L jug
5L: 5, 3L: 3, T: 1
7) Empty 3L jug into tank
5L: 5, 3L: 0, T: 4
Volume measured out in 7 turns

1) Fill 5L jug
5L: 5, 3L: 0, T: 0
2) Empty 5L jug into tank
5L: 0, 3L: 0, T: 5
Volume measured out in 2 turns

1) Fill 3L jug
5L: 0, 3L: 3, T: 0
2) Empty 3L jug into tank
5L: 0, 3L: 0, T: 3
3) Fill 3L jug
5L: 0, 3L: 3, T: 3
4) Empty 3L jug into tank
5L: 0, 3L: 0, T: 6
Volume measured out in 4 turns

1) Fill 5L jug
5L: 5, 3L: 0, T: 0
2) Empty 5L jug into tank
5L: 0, 3L: 0, T: 5
3) Fill 5L jug
5L: 5, 3L: 0, T: 5
4) Pour from 5L jug into 3L jug
5L: 2, 3L: 3, T: 5
5) Empty 5L jug into tank
5L: 0, 3L: 3, T: 7
Volume measured out in 5 turns

1) Fill both jugs
5L: 5, 3L: 3, T: 0
2) Empty both jugs
5L: 0, 3L: 0, T: 8
Volume measured out in 2 turns

1) Fill both jugs
5L: 5, 3L: 3, T: 0
2) Empty both jugs
5L: 0, 3L: 0, T: 8
3) Fill both jugs
5L: 5, 3L: 3, T: 8
4) Empty both jugs
5L: 0, 3L: 0, T: 16
5) Fill 3L jug
5L: 0, 3L: 3, T: 16
6) Pour from 3L jug into 5L jug
5L: 3, 3L: 0, T: 16
7) Fill 3L jug
5L: 3, 3L: 3, T: 16
8) Pour from 3L jug into 5L jug
5L: 5, 3L: 1, T: 16
9) Empty 3L jug into tank
5L: 5, 3L: 0, T: 17
Volume measured out in 9 turns

1) Fill both jugs
5L: 5, 3L: 3, T: 0
2) Empty both jugs
5L: 0, 3L: 0, T: 8
3) Fill both jugs
5L: 5, 3L: 3, T: 8
4) Empty both jugs
5L: 0, 3L: 0, T: 16
5) Fill both jugs
5L: 5, 3L: 3, T: 16
6) Empty both jugs
5L: 0, 3L: 0, T: 24
7) Fill both jugs
5L: 5, 3L: 3, T: 24
8) Empty both jugs
5L: 0, 3L: 0, T: 32
9) Fill both jugs
5L: 5, 3L: 3, T: 32
10) Empty both jugs
5L: 0, 3L: 0, T: 40
11) Fill both jugs
5L: 5, 3L: 3, T: 40
12) Empty both jugs
5L: 0, 3L: 0, T: 48
13) Fill both jugs
5L: 5, 3L: 3, T: 48
14) Empty both jugs
5L: 0, 3L: 0, T: 56
15) Fill both jugs
5L: 5, 3L: 3, T: 56
16) Empty both jugs
5L: 0, 3L: 0, T: 64
17) Fill both jugs
5L: 5, 3L: 3, T: 64
18) Empty both jugs
5L: 0, 3L: 0, T: 72
19) Fill both jugs
5L: 5, 3L: 3, T: 72
20) Empty both jugs
5L: 0, 3L: 0, T: 80
21) Fill both jugs
5L: 5, 3L: 3, T: 80
22) Empty both jugs
5L: 0, 3L: 0, T: 88
23) Fill both jugs
5L: 5, 3L: 3, T: 88
24) Empty both jugs
5L: 0, 3L: 0, T: 96
25) Fill 3L jug
5L: 0, 3L: 3, T: 96
26) Pour from 3L jug into 5L jug
5L: 3, 3L: 0, T: 96
27) Fill 3L jug
5L: 3, 3L: 3, T: 96
28) Pour from 3L jug into 5L jug
5L: 5, 3L: 1, T: 96
29) Empty 3L jug into tank
5L: 5, 3L: 0, T: 97
30) Fill 3L jug
5L: 5, 3L: 3, T: 97
31) Empty 3L jug into tank
5L: 5, 3L: 0, T: 100
Volume measured out in 31 turns

```

---
Tags: code-golf, math, puzzle-solver
---


title: Is this word on the boggle board?

text:
# Question
Title: Is this word on the boggle board?
## Introduction

After a day of drinking and watching the world cup, you sit down to play friendly game of boggle. Tempers rise as you are accused of wasting everyone's time with nonsense words that aren't even on the board! You may be seeing double, but surely you're thinking straight enough to write a program that will verify that your words are on the board.

## Your Task

Write a program, script, or function that takes a boggle board and a word as input, and returns True if the word is on the board and False if the word isn't.

The input will be in the form of six `\n` delimited lines. The first five lines will comprise the 5x5 boggle board and will each contain five capital letters. The sixth line will contain the word-in-question, also in all capital letters.

Sample input:

```
AJNES
TNFTR
LSAIL
UDNEX
EQGMM
DAFTER

```

The output can be anything that unambiguously signifies True or False in your programming language of choice and adheres to standard conventions of zero, null, and empty signifying False.

Sample output for above input:

```
1

```

## I/O Guidelines

* The input may be read from stdin, and answer output to stdout.

Or

* The input may be a single string argument to a function, and answer be the return value of that function.

## Boggle Rules

* A word is 'on the board' if you can construct the word via a path of consecutive, adjacent, non-repeating tiles on the board.
* A tile is considered adjacent to the eight tiles that surround it (diagonal paths are allowed). Tiles on the edge of the board are adjacent to only five tiles. Tiles in the corner are adjacent to only three.
* Consecutive letters in the word must be adjacent, the `i`th letter in the word must be adjacent to the `i-1`th and `i+1`th.
* A letter may appear in a word more than once, but you cannot use the same square on the boggle board more than once per word.
* The online boggle site wordsplay.net may be useful if you have never played boggle before, but want to get a feel for these rules.

Unlike regular boggle:

* You do NOT have to worry about the word being a valid English word.
* There will be NO `Qu` single tile.
* The word-in-question may be of any length \> 0

## Example

On the board of

```
AJNES
TNFTR
LSAIL
UDNEX
EQGMM

```

These words should return True: FATE, DATING, STANDS, LIFTS.

These words should return False: SADDEN, SULTANS, EXIST, SUEDE, QUEST

This is a code-golf challenge, so shortest code wins!

# Answer
> 12 votes
### GolfScript, 74 characters

```
:^n%5>)]){{^@==}+29,\,{{+}+1$/}%\;}/{:s$..&=[s{.@-\}*;]1567`{7&.~)}%-!&},,

```

The input must be given on STDIN. Prints the number of valid paths on the board, i.e. `0` for none and a positive number (true) else.

You can test the example online.

*Code with some comments:*

```
:^              # assign the input to variable ^
n%              # split at newlines
5>              # truncate array such that [WORD] remains
)])             # prepares [[]] and WORD on the stack

# the following loop generates all possible paths (valid and invalid ones)
# by looking up all index combinations which yield the correct word
{               # loop over all characters
  {^@==}+29,\,  # get all indices of current character in the board
  {{+}+1$/}%\;  # append any index to all lists in the result set
}/              # end loop

# filter the results list for valid paths
{               # {...}, -> apply filter
  :s            # save path to variable s
  $..&=         # check if all numbers in path are unique
  [s{.@-\}*;]   # calculate differences along the path
  1567`{7&.~)}% # generate the array [1 -1 5 -5 6 -6 7 -7] of valid
                # differences
  -!            # check if all differences were valid
  &             # are both conditions fulfilled?
},              # end of filter block

,               # count the number of remaining paths

```

# Answer
> 13 votes
# Javascript (E6) 137 ~~160 175 190~~

Less than 2\*Golfscript. Moral victory ...

```
F=a=>[...a].some((e,p,b)=>(Q=(p,n)=>p>29||b[p]!=b[n]||(b.r|=!b[++n])||(b[p]=b[n+~[1,5,6,7].map(q=>Q(p+q,n)|Q(p-q,n),b[p]=0)]))(p,30)&b.r)

```

**Edit** Golfed code reorganization. Again and again

**Ungolfed** Last version, a bit tricky to follow

```
F = a =>
  [...a] // input string to array, 30 chars of board then the target word
  .some ( // use some to scan the board, return true when found
      (e,p,b)=> // params to callback: element, position, complete array
      (         // NB array b has no .r property, so use it for return value (it's undefined at start)
        Q = (p,n) =>         // Scan function, p=position in board, n=nth char of target word
          p > 29 ||          // Chaek if going outside the board to the target word
          b[p] != b[n] ||    // if invalid char at current position, return
          (b.r |= !b[++n]) ||  // if at end of target, set r to 1 and return (also increment n )
          (                  // else... (NB next tree lines are coalesced in golfed code)
            b[p] = 0,        // remove current char (to avoid reusing)
            [1,5,6,7].map( q => Q(p+q,n)|Q(p-q,n)), // recursive call for + - 1,5,6,7
            b[p] = b[n-1]    // put current char into array again
          )
      )(p,30) & b.r // initial position 0 in target word is 30 in the array
  )

```

**Ungolfed** First version , should be clearer

```
F = a => (
  b = a.split('\n'),
  w = b.pop(),
  r = 0,
  Q = (p, n) =>
    (r |= !w[n]) ||
    (
      b[p] = 0,
      [1,5,6,7,-1,-5,-6,-7].map( q => b[q+=p]==w[n] && Q(q,n+1)),
      b[p] = w[n-1]
    ),
  b = [...b+''],
  b.map((e, p) => e==w[0] && Q(p,1)),
  r
)

```

**Usage**

```
F("AJNES\nTNFTR\nLSAIL\nUDNEX\nEQGMM\nLIFTS\nDAFTER")

```

**Test**

```
['DAFTER', 'STANDS', 'LIFTS', 'FATE', 'DATING' ,
 'SADDEN','SULTANS', 'EXIST', 'SUEDE', 'QUEST']
.map(w => [w, F("AJNES\nTNFTR\nLSAIL\nUDNEX\nEQGMM\n" +w)])

```

Output:

```
[["DAFTER", true], ["STANDS", true], ["LIFTS", true], ["FATE", true], ["DATING", true],
["SADDEN", false], ["SULTANS", false], ["EXIST", false], ["SUEDE", false], ["QUEST", false]]

```

# Answer
> 6 votes
# J - 75 char

Eugh, this one looks nasty. And not even tying with Golfscript! This is a function taking a string as its sole argument. You can use any one-character delimiter as long as it's found at the end of each line, including the last.

```
+/@([:*/"1^:2(2(=*)@-/\>@~.)S:1)@{@(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)@(<;._2)

```

An explanation follows. Note that the function can be cleaved into 5 distinct top-level parts, each separated by `@`, so we will treat each of those parts separately, from right to left.

* `(<;._2)` \- This splits the lines up on the newlines/separator characters. It uses the character at the end of the string as the character on which to split. We put everything into boxes (`<`) because if we don't we get some padding issues when J gives us the result back.
* `(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)` \- For each letter in the word to check, create a list of indices in the Boggle board where one can find that letter.

+ `{:` is the last split piece (the word to check) and `}:` is everything but the last (the Boggle board).
    + `&:>` opens up the boxes we made previously, with the useful byproduct of turning `}:` into a 2D array of characters. `=/` then makes a copy of this Boggle board for each letter in the word, and turns the positions into booleans depending on whether the letter in the board matched that letter in the word.
    + `((<@#:i.)5 5)` is a short way of expressing a 5x5 array of indices. `x#:y` is converts `y` into an array of the base `x` representation. (Well, almost. The truth is more complex, but this works for our purposes.)
    + `<@#~&,"2` \- For each letter's resulting boolean matrix, collect all the correspondingly true indices together. `"2` makes everything work on on the right results, `#~&,` does the selecting, and `<@` collects each result into a box to prepare for the next step.
* `{` \- This verb, used monadically, is called Catalogue, and it takes a list of boxes as argument. It combines the insides of each box in every possible way. So e.g. a catalogue on some boxes containing the strings "AB" and "abc" would give the results "Aa", "Ab", "Ac", "Ba", "Bb", "Bc".

Running this on our boxed list of lists of indices makes every possible combination of indices. This can be a big set if there the word is long and there are many repeated letters, but also empty if any letter is not on the board. We also note that we reuse tiles in some of these paths: we will account for this later.
* `([:*/"1^:2(2(=*)@-/\>@~.)S:1)` \- Here we check each path to see if it's valid.

+ `(...)S:1` applies the `(...)` to each path and collects the results into a flat list. This is crucial because the result of `{` is a multi-dimensional array, and we don't care about the structure of that array, just its contents at each box.
    + `2(=*)@-/\>` gives a 1 if each coordinate of each index is at most one away from the one following it, and 0 otherwise. The `2` and the `/\` are responsible for doing this pairwise.
    + `*/"1^:2` logical-ANDs these all together at the end. The `[:` part is a structural thing in J, don't worry about it.
    + Adding `@~.` to the `>` is actually a clever way to exclude paths with repeated entries. `~.` takes the unique items of a list, so the list is shortened if it self-intersects, and shorter lists get automatically padded with 0s when they're put together, like the way that the results are combined as they come out of `S:`. This is ultimately shorter than explicitly excluding self-intersecting paths.
* `+/` \- Finally, we simply add everything together at the end. The result is the number of valid paths that make the word on the board, with 0 meaning no paths, i.e. this word is not on the board. For the cost of one character, we can write `+./` (logical-ORing everything together) instead, which will explicitly give a boolean 1 or 0.

Here are some example runs. You can get the J interpreter at jsoftware.com or try it online at tryj.tk.

```
   NB. the  0 : 0 ... )  thing is how you do multiline strings in J
   +/@([:*/"1^:2(2(=*)@-/\>@~.)S:1)@{@(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)@(<;._2) 0 : 0
AJNES
TNFTR
LSAIL
UDNEX
EQGMM
DAFTER
)
1
   b =: +/@([:*/"1^:2(2(=*)@-/\>@~.)S:1)@{@(((<@#:i.)5 5)<@#~&,"2{:=/&:>}:)@(<;._2)
   b 'AJNES TNFTR LSAIL UDNEX EQGMM FATE '    NB. any separator will do
1
   b 'AJNES TNFTR LSAIL UDNEX EQGMM SADDEN '  NB. not on the board
0
   b 'AJNES TNFTR LSAIL UDNEX EQGMM SANDS '   NB. self-intersecting path
0
   b 'AJNES TNFTR LSAIL UDNEX EQGMM MEND '    NB. multiple paths
2

```

# Answer
> 5 votes
# Python, 207 204 203

```
g=raw_input
r=range
b=''.join(g()for _ in r(5))
w=g()
s=lambda b,w,i:0<=i<25and(not w or(b[i]==w[0])*any(s(b[:i]+'_'+b[i+1:],w[1:],i+j+k*5-6)for j in r(3)for k in r(3)))
print any(s(b,w,i)for i in r(25))

```

Replacing `... (b[i]==w[0])*any ...` with `... b[i]==w[0]and any ...` gives much better performance at the cost of 2 characters.

# Answer
> 2 votes
# Prolog - 315

```
r(L):-get_char(C),(C='\n',!,L=[];r(T),L=[C|T]).
b(0,[]):-!.
b(N,[R|T]):-M is N-1,r(R),b(M,T).
d(-1). d(0). d(1).
d([A,B],[C,D]):-d(X),C is A+X,d(Y),D is B+Y.
f([L|W],B,P,U):-P=[X,Y],nth(Y,B,R),nth(X,R,L),\+member(P,U),(W=[];d(P,Q),f(W,B,Q,[P|U])).
m:-b(5,B),r(W),f(W,B,_,[]),write(t);write(f).
:-initialization(m).

```

I thought Prolog might be a good language for this one, with the built-in backtracking support, but I guess it's more handicapped by needing a variable for almost every computed value.

Tested with GNU Prolog; should be compliant with ISO Prolog.

Ungolfed:

```
get_line(Line) :-
    get_char(C),
    (   C='\n', !, Line=[]
    ;   get_line(Tail), Line=[C|Tail]
    ).

% The cut prevents recursion to help_get_board(-1, MoreRows)
% (and golfs one character shorter than putting N>0 in the second rule).
help_get_board(0, []) :- !.
help_get_board(N, [Row|Tail]) :-
    M is N-1, get_line(Row), help_get_board(M, Tail).

% The golfed version doesn't define an equivalent to get_board/1.
% help_get_board(5,Board) is used directly instead.
get_board(Board) :- help_get_board(5,Board).

small(-1). small(0). small(1).
step([X1,Y1],[X2,Y2]) :-
    small(DX), X2 is X1+DX,
    small(DY), Y2 is Y1+DY.

% The golfed version doesn't define an equivalent to letter_at/3.
% See find_word/4.
letter_at([X,Y], Letter, Board) :-
    nth(Y, Board, Row),
    nth(X, Row, Letter).

find_word([Letter|Word], Board, Pos1, Used) :-
%    letter_at(Pos1, Letter, Board),  % "inlined" to next three lines:
    ( Pos1 = [X,Y],
      nth(Y, Board, Row),
      nth(X, Row, Letter) ),
    \+member(Pos1, Used),
    (   Word=[]
    ;
        step(Pos1, Pos2),
        find_word(Word, Board, Pos2, [Pos1|Used])
    ).

main :-
    get_board(Board),
    get_line(Word),
    % Begin at any position. Initially no positions are "Used".
    find_word(Word, Board, _, []).

```

---
Tags: code-golf, decision-problem, boggle
---


title: Battleship game

text:
# Question
Title: Battleship game
Given the scheme of the fleet of the human player, let the user choose which coordinates attack each turn.
The "computer player" will then attack on its turn following the classic rules of battleship. (The computer player must be able to win, you can't make the computer attack every turn the same cell)

The schemes must contain all the needed ships, this is the list:

```
[ ][ ]               x 4

[ ][ ][ ]            x 3

[ ][ ][ ][ ]         x 2

[ ][ ][ ][ ][ ][ ]   x 1

```

The scheme must follow the example below, and must be one for each player.

```
[ ][ ]   [ ]      [ ][ ][ ][ ]
         [ ]
[ ]      [ ]   [ ][ ][ ]   [ ]
[ ]                        [ ]
[ ]
[ ]            [ ]         [ ]
               [ ]         [ ]
[ ][ ]                     [ ]

            [ ][ ][ ][ ][ ][ ]

```

To input the player scheme you can just hard-code it in your script or let the user insert it in some way (use a specific char to separate rows or let user inser one row per time etc, up to you), the important thing is that your player must be able to easily insert a new scheme (no minified/compressed input so).

The fleet owned by the computer must be randomly generated by the script.

The coordinates are a number(1-10) and a letter(A-L), this is an example battlefield with coordinates:

```
      A  B  C  D  E  F  G  H  I  L
   |‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
 1 | [ ][ ]   [ ]      [ ][ ][ ][ ]
 2 |          [ ]
 3 | [ ]      [ ]   [ ][ ][ ]   [ ]
 4 | [ ]                        [ ]
 5 | [ ]
 6 | [ ]            [ ]         [ ]
 7 |                [ ]         [ ]
 8 | [ ][ ]                     [ ]
 9 |
10 |             [ ][ ][ ][ ][ ][ ]

```

Each turn the script must ask which coordinates hit, and return an indication:

* **not hit** = the selected coordinates doesn't match a part of a ship
* **hit** = the selected coordinates does match part of a ship but the ship is not yet sunk
* **hit and sunk** = the selected coordinates does match part of a ship and the ship is sunk

Then it will have to make the computer hit a cell (bonus points if you can write a smart script that will be challenging) and indicate to user which cell was hit and if one of his ships was hit (same indications of above).

Example "gameplay" log:

```
Your coordinates: A1
hit
Enemy coordinates: C1
not hit
Your coordinates: B1
hit and sunk

```

if the user chooses two times the same coordinates consider it as **not hit** or just ignore it

The expected **final** outputs (when one of the two players has not ships available) are the two schemes with the coordinates hit by the computer player marked with an `x`, example of the first scheme:

```
[x][x]   [x]      [x][x][x][ ]
 x       [x]
[ ] x    [x]   [ ][ ][x]   [x]
[ ]                        [x]
[ ]       x
[x]            [x]         [ ]
               [x]    x    [ ]
[ ][ ] x                   [ ]

    x       [ ][ ][x][ ][ ][ ]

```

It's probably not the easiest code-golf challenge here but as usual, the shortest code will win.

# Answer
> 1 votes
Well, better late than never. I remembered doing something like this in a school class long time ago... Ungolfed and waaaaaay too long.

```
#include <iostream>
#include <ctime>
#include <sstream>
#include <cstdlib>
using namespace std;

class board{
private:
    char grid[10][10];
public:
    void initializeGrid(){
        for (int row=0; row<10; row++){
            for (int column=0; column<10; column++){
                grid[row][column]='~';
            }
        }
    }
    void displayGrid(bool hideShips=false){
        int y=10;
        for (int i=0; i<10; i++){
            if (y!=10){cout<< " ";}
            cout<<y;
            for (int c=0; c<10; c++){
                cout<<" ";
                if (grid[i][c]=='X'){
                    if (hideShips==true){
                        cout<<"~";
                    }else{
                        cout<<grid[i][c];
                    }
                }else{cout<<grid[i][c];}
            }
            y--;
            cout<<endl;
        }
        cout<<"   A B C D E F G H I J"<<endl;
    }
    char getSpace(int x, int y){
        return grid[y][x];
    }
    void addSpace(char space, int x, int y){
        grid[y][x]=space;
    }
};

class ship{
private:
    int length;
    board* boardOP;
public:
    ship(int L, board* BOP){
        length=L;
        boardOP=BOP;
    }
    bool buildShip(int *X, int *Y, int dX, int dY, board *boardOP){
        int shipStore[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
        for(int i=0; i<length; i++){
            shipStore[i*2]=*X;
            shipStore[i*2+1]=*Y;
            if (*Y+dY<10&&*Y+dY>-1
              &&*X+dX<10&&*X+dX>-1
              &&boardOP->getSpace(*X+dX,*Y+dY)=='~'){
                *Y=*Y+dY;
                *X=*X+dX;
            }else{return false;}
        }
        for(int c=0; c/2<length; c+=2){
            boardOP->addSpace('X',shipStore[c],shipStore[c+1]);
        }
        return true;
    }
    int getLength(){return length;}
};

class player{
protected:
    board* thisBoardOP;
    board* otherBoardOP;
    int X;
    int Y;
    int hits;
public:
    virtual void go(){}
    player(){
        hits=0;
    }
    bool won(){
        if(hits==17){return true;
        }else{return false;}
    }
    bool hit(){
        if (otherBoardOP->getSpace(X-1,10-Y)=='X'){
            cout<<"hit!"<<endl;
            hits++;
            otherBoardOP->addSpace('#',X-1,10-Y);
            return true;
        }else{
            cout<<"miss!"<<endl;
            otherBoardOP->addSpace('O',X-1,10-Y);
            return false;
        }
    }
    void arrangeShips(){
        ship aircraftCarrier(5,thisBoardOP);
        positionShip(&aircraftCarrier);

        ship battleship(4,thisBoardOP);
        positionShip(&battleship);

        ship cruiser(3,thisBoardOP);
        positionShip(&cruiser);

        ship destroyer(3,thisBoardOP);
        positionShip(&destroyer);

        ship patrolBoat(2,thisBoardOP);
        positionShip(&patrolBoat);
    }
    void positionShip(ship* type){
        while(1){
            int dY=0;
            int dX=0;
            dX=(rand()%2)-(rand()%2);
            if(dX==0){
                dY=(rand()%2);
                if(dY==0){(dY)--;}
            }else{dY=0;}
            int Y=(rand()%10);
            int X=(rand()%10);
            if (thisBoardOP->getSpace(X,Y)=='~'){
                if (type->buildShip(&X,&Y,dX, dY,thisBoardOP)==false){
                    dX*=-1;
                    dY*=-1;
                    if (type->buildShip(&X,&Y,dX,dY,thisBoardOP)==true){return;}
                }else{return;}
            }
        }
    }
};

class human: public player{
public:
    human(board* tBOP, board* oBOP){
        thisBoardOP=tBOP;
        otherBoardOP=oBOP;
    }
    void go(){
        setXY();
        hit();
        cout<<X<<endl;
        cout<<Y<<endl;
    }
    void setXY(){
        string input;
        while(1){
            do{
                cout<<endl<<"Enter x coordinate:"<<endl;
                char letterX='\0';
                cin>>input;
                if (input.length()==1){letterX=input[0];}
                X=convertLetter(letterX);
                if(X==0){cout<<endl<<"Please enter a valid letter between A-J"<<endl;}
            }while(X==0);
            do{
                cout<< endl<<"Enter y coordinate:"<<endl;
                cin>>input;
                stringstream(input)>>Y;
                if(Y>10||Y<1){cout<<"Please enter a valid number between 1-10"<<endl;}
            }while(Y>10||Y<1);
            if(otherBoardOP->getSpace(X-1,10-Y)=='#'
             ||otherBoardOP->getSpace(X-1,10-Y)=='O'){
                cout<<endl<<"You cannot shoot a space that has already been hit!"<<endl;
            }else{break;}
        }
    }
    int convertLetter(char letter){
        if (int(letter)>64&&int(letter)<75){
            return int(letter)-64;
        }else if(int(letter)>96&&int(letter)<107){
            return int(letter)-96;
        }
        return 0;
    }
};

class computer: public player{
private:
    int originX;
    int originY;
    int vX;
    int vY;
    bool foundEnd1;
    bool foundEnd2;
    bool foundDirection;
    bool oppositeCheck;
    int distance;
    int count;
public:
    computer(board* tBOP, board* oBOP){
        thisBoardOP=tBOP;
        otherBoardOP=oBOP;
        originX=0;
        originY=0;
        vX=0;
        vY=0;
        foundEnd1=false;
        foundEnd2=false;
        foundDirection=false;
        oppositeCheck=false;
        distance=2;
        count=0;
    }
    void go(){
        setXY();
        if(hit()==true){
            if(originX==0){
                originX=X;
                originY=Y;
            }else if(foundDirection==false){
                foundDirection=true;
                if(oppositeCheck==true){
                    if(vX<0||vY<0){foundEnd1=true;
                    }else{foundEnd2=true;}
                }
            }
        }else if(foundDirection==true){
            if (X-originX>0||Y-originY>0){foundEnd1=true;
            }else{foundEnd2=true;}
        }
    }
    void setXY(){
        if(originX!=0){
            if(foundEnd1==false
             ||foundEnd2==false){
                if(foundDirection==false){
                    findDirection();
                }else{
                    findRest();
                }
            }
            if(foundEnd1==true
             &&foundEnd2==true){
                originX=0;
                originY=0;
                vX=0;
                vY=0;
                foundEnd1=false;
                foundEnd2=false;
                foundDirection=false;
                oppositeCheck=false;
                distance=2;
                count=0;
            }
        }
        if (originX==0){
            do{
                X=(rand()%10)+1;
                Y=(rand()%10)+1;
            }while(otherBoardOP->getSpace(X-1,10-Y)=='O'
                 ||otherBoardOP->getSpace(X-1,10-Y)=='#');
        }
    }
    void findDirection(){
        if(count==0){
            vX=(rand()%2)-(rand()%2);
            if(vX==0){
                vY=(rand()%2);
                if(vY==0){(vY)--;}
            }else{vY=0;}
        }
        while(count<4){
            if(count==2){oppositeCheck=false; int i=vX; vX=vY; vY=i;
            }else if(count!=0){oppositeCheck=true; vX*=-1; vY*=-1;}
            count++;
            if(originX+vX<11&&originX+vX>0
             &&originY+vY<11&&originY+vY>0
             &&otherBoardOP->getSpace((originX+vX)-1,10-(originY+vY))!='#'
             &&otherBoardOP->getSpace((originX+vX)-1,10-(originY+vY))!='O'){
                X=originX+vX;
                Y=originY+vY;
                return;
            }
        }
        foundEnd1=true;
        foundEnd2=true;
    }
    void findRest(){
        int adjustment=0;
        if(foundEnd1==true){
            if(vX<0||vY<0){adjustment=1;
            }else{adjustment=-distance;}
        }else if(foundEnd2==true){
            if(vX<0||vY<0){adjustment=-distance;
            }else{adjustment=1;}
        }else{
            adjustment=(rand()%2);
            if(adjustment==0){adjustment=-distance;}
        }
        if (vX<0||vY<0){adjustment*=-1;}
        int i=0;
        while(i<2&&(foundEnd1==false||foundEnd2==false)){
            if (vX==0){
                if(originY+vY+adjustment>0
                 &&originY+vY+adjustment<11
                 &&otherBoardOP->getSpace(originX-1,10-(originY+vY+adjustment))!='#'
                 &&otherBoardOP->getSpace(originX-1,10-(originY+vY+adjustment))!='O'){
                        Y=originY+vY+adjustment;
                    if(adjustment==1||adjustment==-1){vY+=adjustment;}
                    distance++;
                        return;
                }
            }else{
                if(originX+vX+adjustment>0
                 &&originX+vX+adjustment<11
                 &&otherBoardOP->getSpace((originX+vX+adjustment)-1,10-originY)!='#'
                 &&otherBoardOP->getSpace((originX+vX+adjustment)-1,10-originY)!='O'){
                        X=originX+vX+adjustment;
                    if(adjustment==1||adjustment==-1){vX+=adjustment;}
                    distance++;
                        return;
                }
            }
            if(adjustment==1){adjustment=-distance; foundEnd1=true;
            }else if(adjustment==-1){adjustment=distance; foundEnd2=true;
            }else if(adjustment==distance){adjustment=-1; foundEnd1=true;
            }else{adjustment=1; foundEnd2=true;}
            i++;
        }

    }
};

int main(){
    srand((unsigned int)(time(0)));

    board boardO1;
    boardO1.initializeGrid();

    board boardO2;
    boardO2.initializeGrid();

    human humanO(&boardO2,&boardO1);
    humanO.arrangeShips();

    computer computerO(&boardO1,&boardO2);
    computerO.arrangeShips();

    player* playerOP=&humanO;

    while(1){
        boardO1.displayGrid(true);
        cout<<endl;
        boardO2.displayGrid();
        playerOP->go();
        if(playerOP->won()==true){
            cout<<endl;
            if(playerOP==&humanO){
                cout<<"You win!"<<endl;
            }else{
                cout<<"Computer wins!"<<endl;
            }
            cout<<endl;
            boardO1.displayGrid(true);
            cout<<endl;
            boardO2.displayGrid();
            break;
        }
        if (playerOP==&humanO){playerOP=&computerO;
        }else{playerOP=&humanO;}
    }

    return 0;
}

```

**Result:**

```
./a.out
10 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 9 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 8 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 7 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 6 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 5 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 3 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
   A B C D E F G H I J

10 ~ ~ ~ ~ ~ ~ ~ ~ X ~
 9 ~ ~ ~ X ~ ~ ~ ~ X ~
 8 X ~ ~ X ~ ~ ~ ~ X ~
 7 X ~ ~ X ~ ~ ~ ~ X ~
 6 X ~ ~ ~ ~ X X X X ~
 5 X ~ ~ ~ ~ ~ ~ ~ ~ ~
 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 3 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 1 ~ ~ ~ ~ ~ ~ ~ ~ X X
   A B C D E F G H I J

Enter x coordinate:
d

Enter y coordinate:
4
hit!
4
4
10 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 9 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 8 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 7 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 6 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 5 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 4 ~ ~ ~ # ~ ~ ~ ~ ~ ~
 3 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
   A B C D E F G H I J

10 ~ ~ ~ ~ ~ ~ ~ ~ X ~
 9 ~ ~ ~ X ~ ~ ~ ~ X ~
 8 X ~ ~ X ~ ~ ~ ~ X ~
 7 X ~ ~ X ~ ~ ~ ~ X ~
 6 X ~ ~ ~ ~ X X X X ~
 5 X ~ ~ ~ ~ ~ ~ ~ ~ ~
 4 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 3 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 1 ~ ~ ~ ~ ~ ~ ~ ~ X X
   A B C D E F G H I J
miss!
10 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 9 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 8 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 7 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 6 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 5 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 4 ~ ~ ~ # ~ ~ ~ ~ ~ ~
 3 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
   A B C D E F G H I J

10 ~ ~ ~ ~ ~ ~ ~ ~ X ~
 9 ~ ~ ~ X ~ ~ ~ ~ X ~
 8 X ~ ~ X ~ ~ ~ ~ X ~
 7 X ~ ~ X ~ ~ ~ ~ X ~
 6 X ~ ~ ~ ~ X X X X ~
 5 X ~ ~ ~ ~ ~ ~ ~ ~ ~
 4 ~ ~ ~ O ~ ~ ~ ~ ~ ~
 3 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 1 ~ ~ ~ ~ ~ ~ ~ ~ X X
   A B C D E F G H I J

Enter x coordinate:
d

Enter y coordinate:
7
miss!
4
7
10 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 9 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 8 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 7 ~ ~ ~ O ~ ~ ~ ~ ~ ~
 6 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 5 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 4 ~ ~ ~ # ~ ~ ~ ~ ~ ~
 3 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
   A B C D E F G H I J

10 ~ ~ ~ ~ ~ ~ ~ ~ X ~
 9 ~ ~ ~ X ~ ~ ~ ~ X ~
 8 X ~ ~ X ~ ~ ~ ~ X ~
 7 X ~ ~ X ~ ~ ~ ~ X ~
 6 X ~ ~ ~ ~ X X X X ~
 5 X ~ ~ ~ ~ ~ ~ ~ ~ ~
 4 ~ ~ ~ O ~ ~ ~ ~ ~ ~
 3 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 1 ~ ~ ~ ~ ~ ~ ~ ~ X X
   A B C D E F G H I J
miss!
10 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 9 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 8 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 7 ~ ~ ~ O ~ ~ ~ ~ ~ ~
 6 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 5 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 4 ~ ~ ~ # ~ ~ ~ ~ ~ ~
 3 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
   A B C D E F G H I J

10 ~ ~ ~ ~ ~ ~ ~ ~ X ~
 9 ~ ~ ~ X ~ ~ ~ ~ X ~
 8 X ~ ~ X ~ ~ ~ ~ X ~
 7 X ~ ~ X ~ ~ ~ ~ X ~
 6 X ~ ~ ~ ~ X X X X ~
 5 X ~ ~ ~ ~ ~ ~ ~ ~ ~
 4 O ~ ~ O ~ ~ ~ ~ ~ ~
 3 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 2 ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
 1 ~ ~ ~ ~ ~ ~ ~ ~ X X
   A B C D E F G H I J

Enter x coordinate:
d

Enter y coordinate:
4

You cannot shoot a space that has already been hit!

```

# Answer
> 0 votes
Since this is a rather involved problem, I'll be going at it step by step and posting here.

First part, computer board generation:

I used a very simple (yet rules-abiding) algorithm to determine where to put the boats.

```
from random import randint as t
r=range
a=10
d=(0,9)
s=[0]*a
c = [['' for _ in r(a)] for _ in r(a)]
for _ in "1234":
 k=t(0,6)
 c[k][s[k]],c[k][s[k]+1]=['d'+_]*2
 s[k]+=2
for _ in "123":
 k=t(0,6)
 while(s[k]>7):
  k=t(*d)
 c[k][s[k]],c[k][s[k]+1],c[k][s[k]+2]=['s'+_]*3
 s[k]+=3
for _ in "12":
 k=t(0,8)
 while(s[k]>6):
  k=t(*d)
 for q in r(4):
  c[k][s[k]+q]='r'+str(_)
 s[k]+=4
 for _ in r(0,6):
  c[9][s[9]+_]='b1'
s[9]+=6

#Testing
for line in c:
 print(line)

```

A pretty standard output for the algorithm is:

```
['', '', '', '', '', '', '', '', '', '']
['d1', 'd1', 's1', 's1', 's1', 'r1', 'r1', 'r1', 'r1', '']
['d2', 'd2', 'd3', 'd3', '', '', '', '', '', '']
['s3', 's3', 's3', 'r2', 'r2', 'r2', 'r2', '', '', '']
['s2', 's2', 's2', '', '', '', '', '', '', '']
['d4', 'd4', '', '', '', '', '', '', '', '']
['', '', '', '', '', '', '', '', '', '']
['', '', '', '', '', '', '', '', '', '']
['', '', '', '', '', '', '', '', '', '']
['b1', 'b1', 'b1', 'b1', 'b1', 'b1', '', '', '', '']

```

---
Tags: code-golf
---


title: Underhanded contest: The OS war

text:
# Question
Title: Underhanded contest: The OS war
We all know how the discussion about which is the best operating system caused a lot of flame-wars. Your goal is now, to provide decisive "proof" that your favorite operating system is better... ah, no, much better, to provide decisive "proof" that another operating system is bad.

**The task: Write a program, that does some calculations, and it works correctly on at least one OS and incorrectly on at least another one.**

* the program should do at least some calculations, so it has to read some simple input (preferably on the standard input, or if from files if you want, but misusing little endian/big endian would not only be cheap, but also obvious), and provide some output depending on the input. The calculations should be meaningful and justified, for example solving a real life or a mathematical problem.
* you should specify both operating systems, stating on which one it will work correctly, and on which one it won't. Both operating systems should be well known, and from roughly the same time (so no DOS 1.0 versus a modern OS). **It is advised to provide a short description about the cause of the difference (especially if you suspect many people would not realize it) in spoiler tags.**

> like this

* the cause of the difference has to be subtle, so no `#ifdef _WIN32` or similar, please! Remember, your goal is to "prove" that this specific system is bad, so people should not be able to (immediately) spot your trick!
* if there is a very strange or very unusual part in your code, you have to justify it in comments why it is there. Of course, this "justification" can/will be a big lie.

**Scoring:**

This is not a golf! The code should be well organized, and kept simple. Remember, your goal is to hide a bug into it so that people won't suspect it. The simpler the code, the less suspicious it is.

The winner will be decided by votes. The most votes after approximately 10 days after the first valid submission wins. Generally, answers where the code is easy to read and understand, yet the bug is well hidden, and even if discovered, can be attributed to a mistake rather than malice, should be voted up. Similarly, it should be worth much more if the bug just causes an incorrect result, rather than just causing the program to crash or to not do anything.

As usual, I withhold the right to choose an answer as a winner if it is not more than either 10% or 1 point below the one with the most votes, on any subjective criteria.

# Answer
> 15 votes
# Unix shell + standard utilities

Let's write a shell script that finds the process (owned by any user) that has used the most CPU time, and kills all processes with the same name. I suppose that counts as reading in data (from the system) and performing a calculation. (That behavior could be useful for processes that fork off many processes, such as fork bombs and Google Chromium.)

The following should be a portable way to get the name of the process with the greatest CPU time (I tried to avoid obvious Linuxisms but haven't tested it on Solaris):

```
ps -A -o time= -o comm= | sort | tail -n 1 | cut -d ' ' -f 2

```

So our script is simply

```
killall `ps -A -o time= -o comm= | sort | tail -n 1 | cut -d ' ' -f 2`

```

Run as root for best results, so that it can kill processes from other users.

## Linux and BSD

This works on Linux and should work on the BSDs, because `killall arg` kills processes named `arg`.

## Solaris

However, on Solaris, if a user happens to be running a program named `9` in an infinite loop, the script will *bring down the system*. This is because:

> On Solaris, `killall arg` means to *kill all processes* with the signal `arg`. So the command line becomes `killall 9`. As `9` is the number for SIGKILL on Solaris, this will kill all processes and thereby bring down the system.

N.B.

> This shell injection issue doesn't apply on Linux, because even though the malicious user could supply some special argument like `-KILL` as a process name, `killall -KILL` will harmlessly print a usage message.

# Answer
> 18 votes
# Python

This program opens the image specified on the command line and displays it.

```
import Image
import sys

with open(sys.argv[1]) as f:
    im = Image.open(f)
    im.show()

```

Works on linux, does not work on windows.

This is due to the way windows opens files. Binary mode must be specified for this to work properly on all operating systems.

# Answer
> 5 votes
## GTB

```
:"-→_[_+_→_]

```

On the computer it works, but on my TI-84 calculator it doesn't. Why?

> On the calculator RAM overflows and is potentially cleared, while on the emulator for Windows, RAM cannot be overflown by the emulator because of limited allocation.

# Answer
> 5 votes
# Little Endian (Intel x86) vs. Big Endian (IBM Power7)

Any file format where there are multi-byte binary quantities in non-host order runs the risk of being misinterpreted. Here's a function which takes raw audio, say extracted from a WAV file (which is a Microsoft little endian file format), halves the amplitude and outputs the attenuated audio.

```
#include <stdio.h>

int main()
{
    short audio;
    while (fread(&audio, sizeof(short), 1, stdin))
    {
        audio >>= 1;
        fwrite(&audio, sizeof(short), 1, stdout);
    }
    return 0;
}

```

In little endian machines, this works great, but in big endian machines, it's a disaster. E.g.

```
01001101 11001110 -> CE4D (little endian format)

```

Shift right on little endian:

```
00100110 01100111 -> 8726 (correct)

```

Shift right on big endian:

```
00100110 11100111 -> E726 (not correct)

```

Note that some of the nybbles are correct! In fact, it's a 50:50 chance that the output will be correct, depending on whether the least significant bit of the sound sample is 0 or 1!

So when you listen to this audio, it's like half amplitude but with some jarring loud high pitched noise overlaid. Quite startling if you're not prepared for it!

# Answer
> 5 votes
## C

This solution to problem 100 (about Collatz sequence) is accepted by UVa Online Judge.

However, this code only works correctly on **\*nix** platform since `long` type is implemented as 64-bit signed integer. On **Windows**, the code invokes undefined behavior, since `long` type is implemented as 32-bit signed integer, while one of the intermediate value in `cyc()` function needs at least 32-bit to represent.

```
#include <stdio.h>

#define swap(a, b, t) t __tmp__ = a; a = b; b = __tmp__;
#define M 1000000

short l[M] = {0, 1};

int cyc(long n) { // HERE
    if (n < M && l[n]) return l[n];
    n = n & 0x1 ? 3 * n + 1 : n >> 1;
    return n < M ? (l[n] = cyc(n)) + 1 : cyc(n) + 1;
}

int max(int a, int b) { return a > b ? a : b; }

int main() {
    #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    #endif
    int i, j, m;
    while (scanf("%d %d", &i, &j) == 2) {
          printf("%d %d ", i, j);
          if (i > j) { swap(i, j, int); }
          for (m = 0; i <= j; i++)
              m = max(m, cyc(i));
          printf("%d\n", m);
    }

    return 0;
}

```

Another way to make this further incompatible is to put the array `l` inside `main()` and make corresponding changes to `cyc()` function. Since the executable is set to request for 2 MB stack by default on Windows, the program crashes right away.

# Answer
> 2 votes
## Python

I came across this on StackOverflow when looking for input timeouts.

```
 import signal
 TIMEOUT = 5

 def interrupted(signum, frame):
     print 'interrupted!'
 signal.signal(signal.SIGALRM, interrupted)

 def input():
     try:
         print 'You have 5 seconds to type in your stuff...'
         foo = raw_input()
         return foo
     except:
         return

 signal.alarm(TIMEOUT)
 s = input()
 signal.alarm(0)
 print 'You typed', s

```

This does not work for Windows.

# Answer
> 0 votes
## Linux + bash + GNU coreutils

```
rm --no-preserve-root -R -dir /

```

This will erase the root folder and everything in it which doesn't exist in Windows, even if you install bash for Windows :)

---
Tags: popularity-contest, underhanded
---


title: Fastest player for Dots and Boxes

text:
# Question
Title: Fastest player for Dots and Boxes
The challenge is to write a solver for the classic pencil and paper game Dots and Boxes . Your code should take two integers `m` and `n` as input which specifies the size of the board.

> Starting with an empty grid of dots, players take turns, adding a single horizontal or vertical line between two unjoined adjacent dots. A player who completes the fourth side of a 1×1 box earns one point and takes another turn. (The points are typically recorded by placing in the box an identifying mark of the player, such as an initial). The game ends when no more lines can be placed. The winner of the game is the player with the most points.

You can assume that either `n = m` or `n = m - 1` and `m` is at least 2.

The challenge is to `solve` the largest possible Dots and Boxes game in under a minute. The size of a game is simply `n*m`. The output of your code should be `win` , `draw` or `lose` which should be the result for the first player assuming both players play optimally.

Your code must be compilable/runnable on ubuntu using easily installable and free tools. Please report your score as the largest area you can solve on your computer in 1 minute together with the time. I will then test the code on my computer and make a rank ordered table of entries.

In the case of a tie-break, the winner will be the fastest code on the largest size board it can solve in under a minute.

---

It would be better if the code outputted not just win or lose but the actual score as well. This makes for a sanity check of correctness.

# Answer
> 16 votes
## C99 - 3x3 board in 0.084s

**2020 edit/disclaimer:** See comments section. It looks like there may have been errors in the original code. Proceed to the remainder of this answer with some skepticism until it is fixed.

**Edit:** I refactored my code and did some deeper analysis on the results.

**Further Edits:** Added pruning by symmetries. This makes 4 algorithm configurations: with or without symmetries X with or without alpha-beta pruning

**Furthest Edits:** Added memoization using a hash table, finally achieving the impossible: solving a 3x3 board!

Primary features:

* straightforward implementation of minimax with alpha-beta pruning
* very little memory management (maintains dll of valid moves; O(1) updates per branch in the tree search)
* second file with pruning by symmetries. Still achieves O(1) updates per branch (technically O(S) where S is the number of symmetries. This is 7 for square boards and 3 for non-square boards)
* third and fourth files add memoization. You have control over the hashtable's size (`#define HASHTABLE_BITWIDTH`). When this size is greater than or equal to the number of walls, it guarantees no collisions and O(1) updates. Smaller hashtables will have more collisions and be slightly slower.
* compile with `-DDEBUG` for printouts

Potential improvements:

* fix small memory leak fixed in first edit
* alpha/beta pruning added in 2nd edit
* prune symmetries added in 3rd edit (note that symmetries are *not* handled by memoization, so that remains a separate optimization.)
* memoization added in 4th edit
* currently memoization uses an indicator bit for each wall. A 3x4 board has 31 walls, so this method couldn't handle 4x4 boards regardless of time constraints. the improvement would be to emulate X-bit integers, where X is at least as large as the number of walls.

## Code

Due to lack of organization, the number of files has grown out of hand. All code has been moved to this Github Repository. In the memoization edit, I added a makefile and testing script.

## Results

## Notes on Complexity

Brute-force approaches to dots and boxes blow up in complexity *very quickly*.

Consider a board with `R` rows and `C` columns. There are `R*C` squares, `R*(C+1)` vertical walls, and `C*(R+1)` horizontal walls. That is a total of `W = 2*R*C + R + C`.

Because Lembik asked us to *solve* the game with minimax, we need to traverse to the leaves of the game tree. Let's ignore pruning for now, because what matters is orders of magnitude.

There are `W` options for the first move. For each of those, the next player can play any of the `W-1` remaining walls, etc.. That gives us a search-space of `SS = W * (W-1) * (W-2) * ... * 1`, or `SS = W!`. Factorials are huge, but that's only the beginning. `SS` is the number of *leaf nodes* in the search space. More relevant to our analysis is the total number of decisions which had to be made (i.e. the number of *branches* `B` in the tree). The first layer of branches has `W` options. For each of those, the next level has `W-1`, etc.

```
B = W + W*(W-1) + W*(W-1)*(W-2) + ... + W!

B = SUM W!/(W-k)!
  k=0..W-1

```

Let's look at some small table sizes:

```
Board Size  Walls  Leaves (SS)      Branches (B)
---------------------------------------------------
1x1         04     24               64
1x2         07     5040             13699
2x2         12     479001600        1302061344
2x3         17     355687428096000  966858672404689

```

These numbers are getting ridiculous. At least they explain why the brute-force code seems to hang forever on a 2x3 board. **The search-space of a 2x3 board is 742560 times larger than 2x2**. If 2x2 takes 20 seconds to complete, a conservative extrapolation predicts **over 100 days** of execution time for 2x3. Clearly we need to prune.

## Pruning Analysis

I started by adding very simple pruning using the alpha-beta algorithm. Basically, it stops searching if an ideal opponent would never give it its current opportunities. "Hey look - I win by a lot if my opponent lets me get every square!", thought no AI, ever.

**edit** I have also added pruning based on symmetrical boards. I don't use a memoization approach, just in case someday I add memoization and want to keep that analysis separate. Instead, it works like this: most lines have a "symmetric pair" somewhere else on the grid. There are up to 7 symmetries (horizontal, vertical, 180 rotation, 90 rotation, 270 rotation, diagonal, and the other diagonal). All 7 apply to square boards, but the last 4 don't apply to non-square boards. Each wall has a pointer to it's "pair" for each of these symmetries. If, going into a turn, the board is horizontally symmetric, then only *one of each horizontal pair* needs to be played.

**edit edit** Memoization! Each wall gets a unique id, which I conveniently set to be an indicator bit; the nth wall has the id `1 << n`. The hash of a board, then, is just the OR of all walls played. This is updated at each branch in O(1) time. The size of the hashtable is set in a `#define`. All tests were run with size 2^12, because why not? When there are more walls than bits indexing the hashtable (12 bits in this case), the least significant 12 are masked and used as the index. Collisions are handled with a linked list at each hashtable index. The following chart is my quick-and-dirty analysis of how hashtable size affects performance. On a computer with infinite RAM, we would always set the table's size to the number of walls. A 3x4 board would have a hashtable 2^31 long. Alas we don't have that luxury.

Ok, back to pruning.. By stopping the search high in the tree, we can save *a lot* of time by not going down to leaves. The 'Pruning Factor' is the fraction of all-possible-branches which we had to visit. Brute-force has a pruning factor of 1. The smaller it is, the better.

# Answer
> 4 votes
# Python - 2x2 in 29s

Cross-posting from puzzles. Not especially optimized, but may make a useful starting point for other entrants.

```
from collections import defaultdict

VERTICAL, HORIZONTAL = 0, 1

#represents a single line segment that can be drawn on the board.
class Line(object):
    def __init__(self, x, y, orientation):
        self.x = x
        self.y = y
        self.orientation = orientation
    def __hash__(self):
        return hash((self.x, self.y, self.orientation))
    def __eq__(self, other):
        if not isinstance(other, Line): return False
        return self.x == other.x and self.y == other.y and self.orientation == other.orientation
    def __repr__(self):
        return "Line({}, {}, {})".format(self.x, self.y, "HORIZONTAL" if self.orientation == HORIZONTAL else "VERTICAL")

class State(object):
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.whose_turn = 0
        self.scores = {0:0, 1:0}
        self.lines = set()
    def copy(self):
        ret = State(self.width, self.height)
        ret.whose_turn = self.whose_turn
        ret.scores = self.scores.copy()
        ret.lines = self.lines.copy()
        return ret
    #iterate through all lines that can be placed on a blank board.
    def iter_all_lines(self):
        #horizontal lines
        for x in range(self.width):
            for y in range(self.height+1):
                yield Line(x, y, HORIZONTAL)
        #vertical lines
        for x in range(self.width+1):
            for y in range(self.height):
                yield Line(x, y, VERTICAL)
    #iterate through all lines that can be placed on this board,
    #that haven't already been placed.
    def iter_available_lines(self):
        for line in self.iter_all_lines():
            if line not in self.lines:
                yield line

    #returns the number of points that would be earned by a player placing the line.
    def value(self, line):
        assert line not in self.lines
        all_placed = lambda seq: all(l in self.lines for l in seq)
        if line.orientation == HORIZONTAL:
            #lines composing the box above the line
            lines_above = [
                Line(line.x,   line.y+1, HORIZONTAL), #top
                Line(line.x,   line.y,   VERTICAL),   #left
                Line(line.x+1, line.y,   VERTICAL),   #right
            ]
            #lines composing the box below the line
            lines_below = [
                Line(line.x,   line.y-1, HORIZONTAL), #bottom
                Line(line.x,   line.y-1, VERTICAL),   #left
                Line(line.x+1, line.y-1, VERTICAL),   #right
            ]
            return all_placed(lines_above) + all_placed(lines_below)
        else:
            #lines composing the box to the left of the line
            lines_left = [
                Line(line.x-1, line.y+1, HORIZONTAL), #top
                Line(line.x-1, line.y,   HORIZONTAL), #bottom
                Line(line.x-1, line.y,   VERTICAL),   #left
            ]
            #lines composing the box to the right of the line
            lines_right = [
                Line(line.x,   line.y+1, HORIZONTAL), #top
                Line(line.x,   line.y,   HORIZONTAL), #bottom
                Line(line.x+1, line.y,   VERTICAL),   #right
            ]
            return all_placed(lines_left) + all_placed(lines_right)

    def is_game_over(self):
        #the game is over when no more moves can be made.
        return len(list(self.iter_available_lines())) == 0

    #iterates through all possible moves the current player could make.
    #Because scoring a point lets a player go again, a move can consist of a collection of multiple lines.
    def possible_moves(self):
        for line in self.iter_available_lines():
            if self.value(line) > 0:
                #this line would give us an extra turn.
                #so we create a hypothetical future state with this line already placed, and see what other moves can be made.
                future = self.copy()
                future.lines.add(line)
                if future.is_game_over():
                    yield [line]
                else:
                    for future_move in future.possible_moves():
                        yield [line] + future_move
            else:
                yield [line]

    def make_move(self, move):
        for line in move:
            self.scores[self.whose_turn] += self.value(line)
            self.lines.add(line)
        self.whose_turn = 1 - self.whose_turn

    def tuple(self):
        return (tuple(self.lines), tuple(self.scores.items()), self.whose_turn)
    def __hash__(self):
        return hash(self.tuple())
    def __eq__(self, other):
        if not isinstance(other, State): return False
        return self.tuple() == other.tuple()

#function decorator which memorizes previously calculated values.
def memoized(fn):
    answers = {}
    def mem_fn(*args):
        if args not in answers:
            answers[args] = fn(*args)
        return answers[args]
    return mem_fn

#finds the best possible move for the current player.
#returns a (move, value) tuple.
@memoized
def get_best_move(state):
    cur_player = state.whose_turn
    next_player = 1 - state.whose_turn
    if state.is_game_over():
        return (None, state.scores[cur_player] - state.scores[next_player])
    best_move = None
    best_score = float("inf")
    #choose the move that gives our opponent the lowest score
    for move in state.possible_moves():
        future = state.copy()
        future.make_move(move)
        _, score = get_best_move(future)
        if score < best_score:
            best_move = move
            best_score = score
    return [best_move, -best_score]

n = 2
m = 2
s = State(n,m)
best_move, relative_value = get_best_move(s)
if relative_value > 0:
    print("win")
elif relative_value == 0:
    print("draw")
else:
    print("lose")

```

# Answer
> 2 votes
# Javascript - 1x2 board in 20ms

Online demo available here (warning - **very slow if larger than 1x2 with full search depth**): https://dl.dropboxusercontent.com/u/141246873/minimax/index.html

Was developed for the original win criteria (code golf) and not for speed.

Tested in google chrome v35 on windows 7.

```
//first row is a horizontal edges and second is vertical
var gameEdges = [
    [false, false],
    [false, false, false],
    [false, false]
]

//track all possible moves and score outcome
var moves = []

function minimax(edges, isPlayersTurn, prevScore, depth) {

    if (depth <= 0) {
        return [prevScore, 0, 0];
    }
    else {

        var pointValue = 1;
        if (!isPlayersTurn)
            pointValue = -1;

        var moves = [];

        //get all possible moves and scores
        for (var i in edges) {
            for (var j in edges[i]) {
                //if edge is available then its a possible move
                if (!edges[i][j]) {

                    //if it would result in game over, add it to the scores array, otherwise, try the next move
                    //clone the array
                    var newEdges = [];
                    for (var k in edges)
                        newEdges.push(edges[k].slice(0));
                    //update state
                    newEdges[i][j] = true;
                    //if closing this edge would result in a complete square, get another move and get a point
                    //square could be formed above, below, right or left and could get two squares at the same time

                    var currentScore = prevScore;
                    //vertical edge
                    if (i % 2 !== 0) {//i === 1
                        if (newEdges[i] && newEdges[i][j - 1] && newEdges[i - 1] && newEdges[i - 1][j - 1] && newEdges[parseInt(i) + 1] && newEdges[parseInt(i) + 1][j - 1])
                            currentScore += pointValue;
                        if (newEdges[i] && newEdges[i][parseInt(j) + 1] && newEdges[i - 1] && newEdges[i - 1][j] && newEdges[parseInt(i) + 1] && newEdges[parseInt(i) + 1][j])
                            currentScore += pointValue;
                    } else {//horizontal
                        if (newEdges[i - 2] && newEdges[i - 2][j] && newEdges[i - 1][j] && newEdges[i - 1][parseInt(j) + 1])
                            currentScore += pointValue;
                        if (newEdges[parseInt(i) + 2] && newEdges[parseInt(i) + 2][j] && newEdges[parseInt(i) + 1][j] && newEdges[parseInt(i) + 1][parseInt(j) + 1])
                            currentScore += pointValue;
                    }

                    //leaf case - if all edges are taken then there are no more moves to evaluate
                    if (newEdges.every(function (arr) { return arr.every(Boolean) })) {
                        moves.push([currentScore, i, j]);
                        console.log("reached end case with possible score of " + currentScore);
                    }
                    else {
                        if ((isPlayersTurn && currentScore > prevScore) || (!isPlayersTurn && currentScore < prevScore)) {
                            //gained a point so get another turn
                            var newMove = minimax(newEdges, isPlayersTurn, currentScore, depth - 1);

                            moves.push([newMove[0], i, j]);
                        } else {
                            //didnt gain a point - opponents turn
                            var newMove = minimax(newEdges, !isPlayersTurn, currentScore, depth - 1);

                            moves.push([newMove[0], i, j]);
                        }
                    }

                }

            }

        }//end for each move

        var bestMove = moves[0];
        if (isPlayersTurn) {
            for (var i in moves) {
                if (moves[i][0] > bestMove[0])
                    bestMove = moves[i];
            }
        }
        else {
            for (var i in moves) {
                if (moves[i][0] < bestMove[0])
                    bestMove = moves[i];
            }
        }
        return bestMove;
    }
}

var player1Turn = true;
var squares = [[0,0],[0,0]]//change to "A" or "B" if square won by any of the players
var lastMove = null;

function output(text) {
    document.getElementById("content").innerHTML += text;
}

function clear() {
    document.getElementById("content").innerHTML = "";
}

function render() {
    var width = 3;
    if (document.getElementById('txtWidth').value)
        width = parseInt(document.getElementById('txtWidth').value);
    if (width < 2)
        width = 2;

    clear();
    //need to highlight the last move taken and show who has won each square
    for (var i in gameEdges) {
        for (var j in gameEdges[i]) {
            if (i % 2 === 0) {
                if(j === "0")
                    output("*");
                if (gameEdges[i][j] && lastMove[1] == i && lastMove[2] == j)
                    output(" <b>-</b> ");
                else if (gameEdges[i][j])
                    output(" - ");
                else
                    output("   ");
                output("*");
            }
            else {
                if (gameEdges[i][j] && lastMove[1] == i && lastMove[2] == j)
                    output("<b>|</b>");
                else if (gameEdges[i][j])
                    output("|");
                else
                    output(" ");

                if (j <= width - 2) {
                    if (squares[Math.floor(i / 2)][j] === 0)
                        output("    ");
                    else
                        output(" " + squares[Math.floor(i / 2)][j] + " ");
                }
            }
        }
        output("<br />");

    }
}

function nextMove(playFullGame) {
    var startTime = new Date().getTime();
    if (!gameEdges.every(function (arr) { return arr.every(Boolean) })) {

        var depth = 100;
        if (document.getElementById('txtDepth').value)
            depth = parseInt(document.getElementById('txtDepth').value);

        if (depth < 1)
            depth = 1;

        var move = minimax(gameEdges, true, 0, depth);
        gameEdges[move[1]][move[2]] = true;
        lastMove = move;

        //if a square was taken, need to update squares and whose turn it is

        var i = move[1];
        var j = move[2];
        var wonSquare = false;
        if (i % 2 !== 0) {//i === 1
            if (gameEdges[i] && gameEdges[i][j - 1] && gameEdges[i - 1] && gameEdges[i - 1][j - 1] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j - 1]) {
                squares[Math.floor(i / 2)][j - 1] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
            if (gameEdges[i] && gameEdges[i][parseInt(j) + 1] && gameEdges[i - 1] && gameEdges[i - 1][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j]) {
                squares[Math.floor(i / 2)][j] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
        } else {//horizontal
            if (gameEdges[i - 2] && gameEdges[i - 2][j] && gameEdges[i - 1] && gameEdges[i - 1][j] && gameEdges[i - 1] && gameEdges[i - 1][parseInt(j) + 1]) {
                squares[Math.floor((i - 1) / 2)][j] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
            if (gameEdges[i + 2] && gameEdges[parseInt(i) + 2][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][j] && gameEdges[parseInt(i) + 1] && gameEdges[parseInt(i) + 1][parseInt(j) + 1]) {
                squares[Math.floor(i / 2)][j] = player1Turn ? "A" : "B";
                wonSquare = true;
            }
        }

        //didnt win a square so its the next players turn
        if (!wonSquare)
            player1Turn = !player1Turn;

        render();

        if (playFullGame) {
            nextMove(playFullGame);
        }
    }

    var endTime = new Date().getTime();
    var executionTime = endTime - startTime;
    document.getElementById("executionTime").innerHTML = 'Execution time: ' + executionTime;
}

function initGame() {

    var width = 3;
    var height = 2;

    if (document.getElementById('txtWidth').value)
        width = document.getElementById('txtWidth').value;
    if (document.getElementById('txtHeight').value)
        height = document.getElementById('txtHeight').value;

    if (width < 2)
        width = 2;
    if (height < 2)
        height = 2;

    var depth = 100;
    if (document.getElementById('txtDepth').value)
        depth = parseInt(document.getElementById('txtDepth').value);

    if (depth < 1)
        depth = 1;

    if (width > 2 && height > 2 && !document.getElementById('txtDepth').value)
        alert("Warning. Your system may become unresponsive. A smaller grid or search depth is highly recommended.");

    gameEdges = [];
    for (var i = 0; i < height; i++) {
        if (i == 0) {
            gameEdges.push([]);
            for (var j = 0; j < (width - 1) ; j++) {
                gameEdges[i].push(false);
            }
        }
        else {
            gameEdges.push([]);
            for (var j = 0; j < width; j++) {
                gameEdges[(i * 2) - 1].push(false);
            }
            gameEdges.push([]);
            for (var j = 0; j < (width - 1) ; j++) {
                gameEdges[i*2].push(false);
            }
        }
    }

    player1Turn = true;

    squares = [];
    for (var i = 0; i < (height - 1) ; i++) {
        squares.push([]);
        for (var j = 0; j < (width - 1); j++) {
            squares[i].push(0);
        }
    }

    lastMove = null;

    render();
}

document.addEventListener('DOMContentLoaded', initGame, false);

```

---
Tags: code-challenge, fastest-code
---