title: Plus one sheep minus one sheep

text:
# Question
Title: Plus one sheep minus one sheep
Once upon a time long long ago... when there was no money or stocks yet, people were trading sheep. Even before (but close to) the invention of abacus, the great-grandfather of Warren Buffet decided it was hard to keep track of sheep. He wanted to collect all his belongings and clear all his debt, so that he could invest in a new counting machine he heard that his friend, great-grandfather of Bill Gates was building from sticks and beads. All his trades were atomic i.e. he was either supposed to give exactly one sheep to someone or get exactly one sheep. Of course Grandpa Buffet has more sheep to get then to give. Actually he exactly had 749 sheep to collect and he owed 250 sheep, so he was up by 499 sheep. Because of that he built a barn exactly for 499 sheep beforehand. Then he called all 999 people and told them to get into a queue. The very first man, wanted his sheep but there was no sheep in the barn yet. He didn't like this order and wanted everyone to get in order again but first the givers and then the collectors now. At the 500th men there were no space for new sheep in the barn but there were still 250 to collect before starting to give. He gave all the collected sheep back and make them get in a queue again and went to Grandpa Gates to help him ordering. Somehow they figured out and with the help of 499 sheep, they built a lot of Abacus and lived happily ever after.

Years later, yesterday Bill Gates and Warren Buffet met in a Giving Pledge meeting. They told this story and laughed a lot. Then Gates told Buffet: "You know what, I don't know how my great-grandpa ordered 999 people but I know there are so many ways. Actually I can tell you how many if you let me...". Then he went to his room to write a code to calculate the number of possible orderings that always guarantee there is always sheep or space in the barn until the queue is empty. And he did so but being Bill Gates he has written a recursive function which solves the problem correctly but slowly. So everybody still waits for his answer. Buffet is bored, can you write a better and faster function?

```
p = 749
n = 250
orderings(p,n) = ?

```

Shortest code wins, but it must finish in minutes, not hours or days.

# Answer
> 1 votes
# Pyth, 33 bytes

```
M?+&<HGgtGH&+-499GHgGtHH1g749 250

```

Try it online: Pyth Compiler/Executor. Takes about 3 seconds on my laptop. The online compiler is a bit slower, but also computes the answer in about 15 seconds.

The answer is:

```
160547283350099323317963999889002394629262478407796913030854915361460989263675794524349914992326520887556329626280682363011590724268659750627030457440692447081328860242720905181098211539560301455338502543318855115593179999323115473879753632000

```

### Explanation:

First some pseudo-code of the recursive function. This is quite easy to write.

```
function g(p, n):
   if (p > 0 and n > 0):
      count = 0
      if (occupied_places_in_barn < 499):
         count += g(p-1, n)
      if (occupied_places_in_barn > 0):
         count += g(p, n-1)
      return count
   else:
      return 1 # only one way possible

```

And the Pyth translation:

```
M                                  def g(G,H): return _
    <HG                               H < G
   &   gtGH                                 and g(G-1,H)
            +-499GH                   499-G+H
           &       gGtH                       and g(G,H-1)
  +                                   return sum of these two numbers
 ?                     H1             if H else 1
                         g749 250  call g(749,250) and print

```

**Why is this recursive code so fast?** Doesn't the function `g` iterate over all 1.6\*10^199 possibilities?

No it doesn't. The key here is dynamic programming. We store known results in a cache and lookup the results, when we call the function with the same parameters again. One really cool feature of Python is the `@lru_cache` decorator, which does all the work for you. No need to manually generate such a cache and handle stuff like lookup, storing results, ... And in Pyth it's even simpler, since each function automatically uses such a cache. So in total the function `g` gets executed only 125499 times. Way less than 1.6\*10^199 times.

---
Tags: code-golf, math, combinatorics, permutations
---


title: Not Your Routine Bean Machine

text:
# Question
Title: Not Your Routine Bean Machine
Consider this ASCII version of a mechanism similar to a bean machine or plinko/pachinko game:

```
    O

    ^
   \ ^
  ^ ^ \
 \ ^ / ^
U U U U U
1 2 3 4 5

```

The `O` is a ball that falls down.

* When it hits a `^`, there's a 50-50 chance it will go left or right.
* When it hits a `/`, it always goes left.
* When it hits a `\`, it always goes right.

The ball eventually falls into one of the numbered `U` troughs at the bottom. The question is, what is the probability it will end up in each trough?

For this particular case, the probabilities are `0.0`, `0.1875`, `0.5625`, `0.125`, and `0.125`, for troughs 1 through 5 respectively.

Here's another example with 3 troughs instead of 5. The probabilities are `0.5`, `0.5`, and `0.0`:

```
  O

  /
 ^ ^
U U U
1 2 3

```

In this challenge we will generalize this problem to a mechanism with any number of layers set up in any fashion.

# Challenge

Write a program or function that takes in the ASCII representation of the pyramid structure of the mechanism. (Input via stdin/command line/function arg.)

You may either assume it comes in with spaces that put it in the proper shape, e.g.

```
   ^
  \ ^
 ^ ^ \
\ ^ / ^

```

Or you may assume it comes in with no spaces at all, e.g.

```
^
\^
^^\
\^/^

```

(If desired, you may assume there is a trailing newline and/or some consistent pattern of trailing spaces.)

The input pyramid structure may have any number of levels (aka lines), including zero. Each level has one more `^`, `/`, or `\` than the last, and there are `levels + 1` troughs at the bottom (which aren't part of the input).

You program/function must print/return the list of the probabilities that the ball lands in each of the troughs (in the order leftmost trough to rightmost trough). These should be floating point values that, when printed, have at least 3 decimal places (superfluous zeros or decimal points are not required; `1` is fine for `1.000`, `.5` is fine for `0.500`, etc.). If you wrote a function, you may print the values or return a list/array of the floats.

Any reasonable printed list format is fine. e.g. `0.5 0.5 0.0`, `[0.5 0.5 0.0]`, `[0.5, 0.5, 0.0]`, `{0.5, 0.5, 0.0}`, or `0.5\n0.5\n0.0` would all be alright.

# Examples

**0 Levels:** (boils down to one trivial `U`)

Input: `[no input/empty string given]`
Output: `1.0`

**1 Level:**

Input: `^`
Output: `0.5 0.5`

Input: `/`
Output: `1.0 0.0`

Input: `\`
Output: `0.0 1.0`

**2 Levels:** (second example above)

Input:

```
 /
^ ^

```

Output: `0.5 0.5 0.0`

**3 Levels:**

Input:

```
  ^
 ^ ^
^ ^ ^

```

Output: `0.125 0.375 0.375 0.125`

Input:

```
  \
 / \
/ / \

```

Output: `0.0 0.0 0.0 1.0`

**4 Levels:** (first example above)

Input:

```
   ^
  \ ^
 ^ ^ \
\ ^ / ^

```

Output: `0.0 0.1875 0.5625 0.125 0.125`

**7 Levels:**

Input:

```
      ^
     / ^
    ^ ^ /
   / \ / \
  ^ ^ / ^ \
 ^ \ ^ \ / ^
\ ^ ^ ^ \ ^ /

```

Output: `0.0 0.09375 0.28125 0.4375 0.1875 0.0 0.0 0.0`

# Scoring

The shortest answer in bytes wins. Tiebreaker is earlier post.

# Answer
> 10 votes
# CJam, ~~50 48 45 44 42~~ 40 bytes

```
1]q{iD%"(+0 0+( (\Y/::+ (d2/_a+"S/=~+}/p

```

This expects the input to be without space and have a trailing newline. For example:

```
^
\^
^^\
\^/^

```

> \[0 0.1875 0.5625 0.125 0.125\]

**Algorithm**

The basic idea is that you keep on parsing each character (there are only 4 different characters) and perform different operations on the probability distribution (initially an array containing 1 element of value 1). For each row of input characters (starting with the first character on first row), we maintain a probability array of that same size. Each character acts upon the first probability from the list and pushes the resultant pair to the end of the list. After each line, we sum up pairs from the list to get exact number of items as the items on the next line.

Here are the four characters and the required actions corresponding to each:

* `^` : When this character occurs, you split the current probability to two parts. For example, if we have this on the first line, we have to convert the `[1]` to `[0.5 0.5]`
* `/` : When this characters occurs, we have to put `<current probability> 0` in place of the current probability in the array.
* `\` : When this characters occurs, we have to put `0 <current probability>` in place of the current probability in the array.
* `\n` : When this character occurs, we have a new line. Thus we group together all pairs from above 3 characters and sum them up to get probability of each item for the next line. For ex. `[0 0.5 0.25 0.25]` gets converted to `[0 0.75 0.25]`. Note that the first and last items have an implicit pair (valued 0) before and after them.

Now we only have to identify the right character and perform the right action. Lets use the usual maths here to do that. The ASCII codes for `^`, `\`, `/` and `\n` are `94`, `92`, `47`, and `10`. After a few trials, we get this simple equation to convert these numbers into 0, 1, 2 and 3:

```
"^\/
":ied13f%ed4f%ed

```

gives:

```
Stack: [[94 92 47 10]]
Stack: [[3 1 8 10]]
Stack: [[3 1 0 2]]
3102

```

In an array of length 4, the last `4f%` would be implicit. So we simply do `%13` to the ASCII code of the character and choose the right action from an array of actions.

**Code explanation**:

```
1]                                 e# Initial probability array with 1 probability
  q{                          }/   e# Read the whole input and iterate char by char
    iD%                            e# mod the ASCII code of the character with 13
"(+0 0+( (\Y/::+ (d2/_a+"S/        e# This is our actions array in order of [\ / \n ^]
                           =~      e# We pick the correct action and eval it
                             +     e# Evaling each action will leave one number out of the
                                   e# pairs out of the array. So we put it back in
                                p  e# Print the final probability array

```

Try it online here

# Answer
> 15 votes
# Ruby 140

```
->s{r=[1.0]
s.lines.map{|l|n=[i=0.0]*(r.size+1)
l.scan(/\S/).map{|e|a,b=e>?/?e>?]?[0.5]*2:[0,1]:[1,0]
z=r[i]
n[i]+=z*a
n[i+=1]+=z*b}
r=n}
r}

```

Function that takes as input the string (can be nicely formatted as a pyramid) and returns an array of floats.

Test it online: http://ideone.com/kmsZMe

Pretty straightforward implementation. Here it is ungolfed:

```
F = -> input {
  probabilities = [1.0]

  input.lines.each { |line|

    new_probabilities = [0.0] * (probabilities.size+1)
    elements = line.scan /\S/
    elements.map.with_index{|el, i|
      deltas = el > '/' ? (el > ']' ? [0.5,0.5] : [0,1]) : [1,0]

      d1, d2 = deltas

      new_probabilities[i] += probabilities[i] * d1
      new_probabilities[i + 1] += probabilities[i] * d2
    }
    probabilities = new_probabilities
  }
  return probabilities
}

```

# Answer
> 13 votes
# Ruby, 140 ~~158~~ bytes

~~Don't keep upvoting this when there's a better ruby version.~~ Here are more tricks for you.

Unnamed function with one argument. Must not contain any spaces. May or may not contain a trailing newline.

```
->s{Z=(s.split'
')<<[]
K=[]
F=->i,j,f{k=Z[i][j]
K[i]||=0
k==?^?2.times{|m|F[i+1,j+m,f/2]}:!k ?K[j]+=f :F[i+1,j+(k==?/?0:1),f]}
F[0,0,1.0]
K}

```

~~Wastes 9 bytes on having to handle `0 levels` (empty string).~~ All test cases work out correctly, see here at ideone.

# Answer
> 12 votes
# Pyth, ~~43~~ ~~42~~ 41 bytes

```
umsdc+0sm@c[ZJhkJZKcJ2K)2x"\/"ekC,GH2.z]1

```

This expects the input to be without spaces. Try it online: Pyth Compiler/Executor

# Pyth, 40 bytes (questionable)

```
umsdc+0sm,K@[ZJhkcJ2)x"\/"ek-JKC,GH2.z]1

```

Thanks to @isaacg, for saving one byte. Notice that this version didn't actually work in the version of Pyth, when the question was asked. There was a tiny bug in the compiler. Despite this code uses no new features of Pyth (only stuff that was in the Pyth docs for a long time and should have worked), this might not be a valid answer. Decide for yourself.

Try it online: Pyth Compiler/Executor

### Explanation:

```
umsdc+0sm,K@[ZJhkcJ2)x"\/"ek-JKC,GH2.z]1
u                                   .z]1  reduce G, starting with G = [1], for H in all_input():
                               C,GH         zip(G,H)
        m                                   map each pair k to:
            [ZJhkcJ2)                         create a list [0, k[0], k[0]/2]
                     x"\/"ek                  index of k[1] in "\/" (-1 for "^")
          K@                                  take the correspondent element of the list and store in K
         ,                  -JK               create a pair (K, k[0]-K)
     +0s                                    sum and insert 0 at the begin
    c                              2        chop into pairs
 msd                                        sum up each pair
                                            G gets updated with this new list

```

For instance if I currently have the input probabilities `G = [0.5, 0.5, 0.0]` and the row `H = "^/^"` the following happens:

* zip ... `[(0.5,"^"), (0.5,"/"), (0.0,"^")]`
* create output probabilities ... `[[0.25,0.25], [0.5,0.0], [0.0, 0.0]]`
* 0+sum ... `[0, 0.25, 0.25, 0.5, 0.0, 0.0, 0.0]`
* chop ... `[0,0.25], [0.25,0.5], [0.0,0.0], [0.0]]`
* sum ... `[0.25, 0.75, 0.0, 0.0]`

# Answer
> 8 votes
# C#, ~~274~~ 247 bytes

Nothing fancy, complete program that reads lines (with or without spaces, it just strips them) in from STDIN, and prints space separated results to STDOUT.

```
using Q=System.Console;class P{static void Main(){decimal[]k={1},t;string L;for(int l=0,i;(L=Q.ReadLine())!=null;k=t)for(L=L.Replace(" ",""),t=new decimal[++l+1],i=0;i<l;)t[i]+=k[i]-(t[i+1]=(8-L[i]%8)/2*k[i++]/2);Q.WriteLine(string.Join(" ",k));}}

```

Tidier code with comments:

```
using Q=System.Console;

class P
{
    // / 47
    // \ 92
    // ^ 94

    static void Main()
    {
        decimal[]k={1},t; // k is old array, t is new array

        string L; // L is the current line, R is the current result (1 if no rows)
        for(int l=0,i; // l is length of old array, i is index in old array
            (L=Q.ReadLine())!=null; // for each line of input
            k=t) // swap array over
            for(L=L.Replace(" ",""), // remove spaces
                t=new decimal[++l+1], // create a new array
                i=0;

                i<l;) // for each position

                t[i]+=k[i]-( // add to left position (for last time)
                        t[i+1]=(8-L[i]%8)/2*k[i++]/2 // assign right position (k is decimal)
                    );

        Q.WriteLine(string.Join(" ",k)); // print result
    }
}

```

# Answer
> 7 votes
## Python 3, 113

```
P=[1]
for C in input().split():
 l,*Q=0,
 for p,c in zip(P,C):r=p*"\^/".find(c)/2;Q+=l+r,;l=p-r
 P=Q+[l]
print(P)

```

Repeatedly updates the probability vector `P` in response to each line. This new probability vector `Q` is created one entry at a time. Iterates through the new slots, and computes the contribution from the peg to its right as `r`, while also computing the remaining contribution to the upcoming slot as `p-r`.

Expects each line to end in at least one space to avoid an issue where lines end in a backslash.

# Answer
> 6 votes
# Python 3, 138 bytes

```
def f(s):
 r=[1];p=t=0
 for e in s:
  if'!'<e:b=p==t*-~t/2;r+=[0]*b;t+=b;v=ord(e)%7+1;a=r[p]/2;r[-1]+=v//3*a;r+=v%3*a,;p+=1
 return r[~t:]

```

Works with any whitespaces as they are all filtered out (by `if'!'<e`).

Method:

* We keep an ever expanding list `r` of the probabilities of reaching any obstacles and the implicit troughs below them. We start from the list `[1]`.
* If we are at the first obstacle in a row we need to add an extra `0` to the list for the leading trough. We decide if it is the first obstacle by comparing its index `p` to the next triangular number `t*-~t/2`.
* For every obstacle we add its list-value partially to the last element and partially to a new trailing element. We divide the list-value based on the obstacle character (`^:0.5 0.5; /:1 0; \:0 1`). We use the following method:
    + Take `v = ord(char) mod 7 + 1` yielding `^:4 /:6 \:2`
    + `v div 3 / 2` yields the first fraction (`^:0.5 /:1 \:0`)
    + `v mod 3 / 2` yields the second fraction (`^:0.5 /:0 \:1`)
* The result is the last `t + 1` elements of the final list `r`.

2 bytes thanks to @Sp3000's chat advice.

# Answer
> 4 votes
# Perl, 78

```
#!perl -p0a
@r=($/=1);$^=.5;@r=map$r-$l+($l=$$_*($r=shift@r)),/./g,$r=$l=0for@F;$_="@r"

```

Takes input without spaces.

Try me.

# Answer
> 1 votes
# TI-BASIC, ~~73~~ 76

Takes input one line at a time, and ends when a space is entered on its own, because neither line breaks in strings nor empty strings are legal in TI-BASIC.

```
{1→X
Input Str1
While Str1≠"  //one space
.5seq(inString("^/",sub(Str1,I,1)),I,1,dim(Ans
augment(Ans∟X,{0})+augment({0},∟X-∟XAns→X
Input Str1
End
∟X

```

I'm pretty sure I got the size right (TI-BASIC is tokenized, so each command takes either one or two bytes—seq() takes one, inString() takes two, dim() takes one, and so on. I counted the size manually.)

Although the backslash character is valid in a string, note that there is no way to input one from inside the program unless you have modified your calculator.

# Answer
> 0 votes
## Javascript - 117

Tried using recursion, but that was too long...

Hat tip to xnor for the subtraction idea, which shaved off a dozen or more characters.

```
w=s=>{a=[1];s.split('\n').map(m=>{for(b=[i=0];z=a[i],f=m[i];b[i++]+=z-b[i])b[i+1]=f>']'?z/2:f<':'?0:z;a=b})
return a}

```

Ungolfed:

```
// s must not have spaces
w=s=>{
  // a is the current probability array
  a=[1];
  s.split('\n').map(
    // for each row of input...
    m=>{
      b=[0];  // b is the next row's probability array
      for(i=0; i<m.length;){
        z=a[i]; // z = probability
        f=m[i]; // f = letter
                                  // let's assume i == 0
        b[i+1] = (f>']') ? z/2 :  // if f == '^', b[1] = z/2
          (f<':' ? 0 :            // else if f == '/', b[1] = 0
            z);                   // else b[1] = z
        b[i++]+=z-b[i];           // then add (z-b[1]) to b[0]
      }
      a=z-b    // increment current probability array
    }
  )
  return a;
}

```

---
Tags: code-golf, probability-theory
---


title: Leonhard loves labyrinths

text:
# Question
Title: Leonhard loves labyrinths
## The background

My son Leonhard (4 years old) loves labyrinths. I don't know where he knows labyrinths from, but he paints them and knows quite well how they work:

Recently, he started making a game from his paintings. These are his rules:

* a black square denotes the starting point.
* a hook denotes the exit of the labyrinth (that's where you get pulled out).
* you can collect crowns.
* you can collect gold nuggets (the round things).
* you can go a way forth and back, but not more than that.
* arrows may guide you to the exit. (If he paints a labyrinth for me to solve, they are often misleading).

Annotated version:

* blue: starting point
* orange: crowns
* yellow: area with gold nuggets
* green: hook (exit)
* pink: arrows (mostly misleading)

## The Task

Maybe you know, at the age of 4, kids start telling porky-pies and sometimes he does not follow his own rules, especially if he finds out that he cannot reach the end of the maze any more.

That's where you come into play: since I'm looking for games for kids anyway, you turn his idea into a game where cheating is not possible.

Well, we need some more definitions I'd say:

* the playing field is a `n`*`m` rectangle of equally sized squares.
* a square can have 0 to 4 walls, one on each side.
* a crown is worth 50 points.
* a gold nugget is worth 20 points.
* walking on a square that has already been walked subtracts 1 point.
* squares are marked in a way to identify how often the player walked on it (0, 1 or 2 times)
* the player can walk in 4 directions, except if there is a wall.
* Input device can be anything. Please consider keyboard support.
* The labyrinth must be solvable. I.e. it must be possible to reach the hook from the starting point and it must be possible to collect all the valuables (even if that does not result in the highest possible score).
* If the player gets stuck, the game ends.
* The player must not die by falling off the board. You may put a wall around the complete maze or wrap around edges, whatever you like.
* the program takes an word (0-65535) argument as input. This is the seed for the random number generator. Calling the program with the same seed again results in the same labyrinth.

Bonus:

* calculate the maximum points that can be collected. Consider that due to -1 points it might be better to not collect all items.
* Show the best solution (shortest way to get maximum points)

## The Rules

This is a popularity contest, since I want to be able to read and understand the code and perhaps adapt to new ideas of my son. Sorry, code golfers, maybe you want to create a copy of this question with rules more suitable for golfing, e.g. a console version with all the characters defined.

The most popular game on 3rd of May will become the accepted answer. And, hey, why not publish it in an app store?

# Answer
> 17 votes
# JavaScript

Work in progress. Unfortunately the maze is not always solvable - the limit on back-forward is the real hurdle.

**Edit 1** Cosmetic
**Edit 2** Better gameplay, but the big problem is still there

```
var rows, columns, rowOfs, maze, plPos, points, playing

$('#BNEW').on('click', function() {
    NewMaze();
});
$('#BREP').on('click', function() {
    Start();
});

$(document).on('keydown', function(e) {
    var ok, move, pxy, mz, $td
    switch (e.which)
    {
    case 37:
        (move = -1, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    case 39:
        (move = 1, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    case 38:
        (move = -rowOfs, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    case 40:
        (move = rowOfs, ok = maze[plPos+move] < 9 && maze[plPos+move*2] < 9);
        break;
    }
    if (playing && ok)
    {
        pxy = getXY(plPos)
        mz = maze[plPos] < 8 ? 8 : 9;
        $td = $('#Field table tr').eq(pxy.y).find('td').eq(pxy.x)
        $td.addClass("m"+mz);
        maze[plPos] = mz;
        maze[plPos+move] = mz;
        plPos += move*2;
        mz = maze[plPos];
        PTS.value = mz==7 ? points += 20 : mz==6 ? points += 50 : mz == 8 ? points -= 1 : points;

        pxy = getXY(plPos)
        $td = $('#Field table tr').eq(pxy.y).find('td').eq(pxy.x)
        $td.removeClass("m6 m7")
        $('#Player').finish().animate(playerCss(pxy.x,pxy.y));
        CheckEndGame();
    }
    return !move
});

function CheckEndGame()
{
  var msg = ''
  if (maze[plPos] == 5)
  {
      msg = "Maze completed!";
  }
  else if (maze[plPos+1]==9 && maze[plPos-1]==9
        && maze[plPos+rowOfs]==9 && maze[plPos-rowOfs]==9)
  {
      msg = "You are stuck, try again!";
  }
  if (msg) {
    $("#Msg").text(msg).show();
    playing=false
  }
}

function seed(s) {
    return function() {
        s = Math.sin(s) * 10000; return s - Math.floor(s);
    };
};

function Build()
{
    var i
    var Fill = function(p)
    {
        var d=[rowOfs,-rowOfs,1,-1], i, s, l
        maze[p] = 1
        while(d[0])
        {
            i = random()*d.length|0
            s = d[i]
            if (s != (l=d.pop())) d[i]=l
            if (maze[p+s+s]>8) {
                maze[p+s] = 1, Fill(p+s+s)
            }
        }
    }
    rowOfs = (columns + 1) * 2
    maze = Array(rowOfs * (rows*2+1))
    for (i=0; i < maze.length; i++)
        maze[i] = i % rowOfs? 9 : 0
    Fill(rowOfs+2)
}

function NewMaze()
{
    SEED.value = Math.random()*65536 | 0
    Start()
}

function Start()
{
    var sd = SEED.value || 1
    columns = COLS.value |0 || 18
    rows = ROWS.value | 0 || 12
    COLS.value = columns
    ROWS.value = rows
    random = seed(sd)
    PTS.value = points = 0
    $("#Msg").hide();

    Build()

    plx = random()*columns|0;
    ply = random()*rows|0;
    setPlayer(plx,ply);
    plPos = getPos(plx,ply);
    BlockTriples(plPos);
    AddItems(plPos);
    Draw();
    playing = true;

}

function AddItems(p)
{
    var d=[rowOfs,-rowOfs,1,-1]
    var cells=[]
    // scan all reachable cells and calc distance from start
    var Go = function(p,l)
    {
        var i,t,mark,r
        ++l
        cells.push([p,l])

        maze[p] = 8;
        for(i=0; d[i]; i++)
        {
            t = d[i]
            if (maze[p+t]<2 && maze[p+t+t]<2)
            {
                Go(p+t+t, l)
            }
        }
        maze[p] = 0;
    }
    Go(p,0)
    cells.sort(function(a,b){return a[1]-b[1]})
    cells=cells.slice(10) // cut the shortest distances
    r = random()*10|0; //exit
    r = cells.length-r-1
    maze[cells[r][0]] = 5;
    console.log(r)
    cells = cells.slice(0,r)
    var ncr = rows, nnu = columns
    for(i = ncr+nnu; i; i--)
    {
        r = random()*cells.length|0
        maze[cells[r][0]] = (i > ncr ? 7 : 6);
        cells[r] = cells.pop();
    }

}

function BlockTriples(p)
{
    var d=[rowOfs,-rowOfs,1,-1]
    var Go = function(p)
    {
        var i,t,size=[0,0,0,0],s=1,nw=0,min,minp
        maze[p] = 8
        for(i=0; d[i]; i++)
        {
            t = d[i]
            if (maze[p+t]<9 && maze[p+t+t]<8)
            {
                ++nw
                s += size[i] = Go(p+t+t)
            }
        }
        if (nw > 2) // triple way, block the smallest
        {
            for(i=0,min=1e6; d[i]; i++)
                size[i] && size[i] < min && (min = size[minp = i])
            maze[p + d[minp]] = 5;
        }
        maze[p]=0
        return s
    }
    Go(p)
}

function Draw()
{
    var q=[], i, x, y;
    for(i = rowOfs+2, y = 0; y < rows; y++)
    {
        q.push('<tr>')
        for (x = 0; x < columns; i += 2, x++)
        {
            tcl = 'm'+(maze[i]|0)
            maze[i-1]>8 && (tcl += ' wl')
            maze[i+1]>8 && (tcl += ' wr')
            maze[i-rowOfs]>8 && (tcl += ' wu')
            maze[i+rowOfs]>8 && (tcl += ' wb')
            q.push('<td class="'+tcl+'"></td>')
        }
        q.push('</tr>')
        i += rowOfs+2
    }
    $("#TOUT").html(q.join(''));
    $("#Field").show();
}

function setPlayer(posx, posy)
{
    $('#Player').css(playerCss(posx, posy));
}

function getXY(pos)
{
    return { x: (plPos % rowOfs)/2-1, y: plPos / rowOfs / 2 | 0}
}

function getPos(x, y)
{
   return (x+y*rowOfs)*2 + rowOfs+2;
}

function playerCss(posx, posy)
{
    return{ left: 6+posx*21, top: posy*21+2};
}
```

```
input { width: 3em; margin-right:1em }
table {
  border: 2px solid #000;
  border-collapse: collapse;
  font-size: 8px }
#Field {
  margin: 10px;
  position: relative;
  display: none;
}
td {
    width: 19px; height: 19px;
    padding: 0; margin: 0;
    text-align: center;
}
td.wl { border-left: 2px solid #444; background: #fff }
td.wr { border-right: 2px solid #444; background: #fff }
td.wt { border-top: 2px solid #444;; background: #fff }
td.wb { border-bottom: 2px solid #444; background: #fff }
td.m7 { background: #ffd url(https://i.stack.imgur.com/QUInh.png) -21px 0}
td.m6 { background: #efe url(https://i.stack.imgur.com/QUInh.png) -1px 0}
td.m5 { background: #ddf url(https://i.stack.imgur.com/QUInh.png) -40px 0}
td.m8 { background: #eed }
td.m9 { background: #f55 }
#Player { position: absolute; top:0; left:0; color: #007; background: #fcb; font-size:12px }
#Msg { color: red; font-size:40px; display:none;  }
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
ID:<input id=SEED>
Rows:<input id=ROWS>
Columns:<input id=COLS>
<button id=BNEW>New</button>
<button id=BREP>Replay</button>
<div id=Msg></div>
<div id=Field>
<table id=TOUT border=0 cellspacing=0 cellpadding=0>
</table>
<span id=Player>⛄</span>
</div>
Score: <input readonly id=PTS>
```

# Answer
> 6 votes
# Java

I never complained about GolfScript or CJam, but here's a Java answer for you anyway. This was a really enjoyable challenge. ;)

```
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.geom.Ellipse2D;
import java.util.*;
import javax.swing.*;

public class MazeMaker {
    int row, col, exitRow, exitCol, numCells, score, array[][];
    final int SQWIDTH = 20;
    boolean gameOver = true;
    Ellipse2D.Double ellipse;
    JFrame frame;
    JPanel mazePanel;
    JLabel scoreLabel;

    public MazeMaker() {
        frame = new JFrame("Maze");
        frame.setLayout(new BorderLayout());
        JPanel topPanel = createTopPanel();
        frame.add(topPanel,BorderLayout.NORTH);

        createMazePanel();
        frame.add(new JScrollPane(mazePanel),BorderLayout.CENTER);

        setKeyActions();

        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.pack();
        frame.setVisible(true);
    }

    private void constructArray(int seed, int rows, int cols) {
        array = new int[rows*2-1][cols*2-1];
        for (int[] a : array)
            Arrays.fill(a,-1);
        numCells = (array.length / 2 + 1) * (array[0].length / 2 + 1);
        Random rand = new Random(seed);
        int row = rand.nextInt(array.length / 2 + 1) * 2;
        int col = rand.nextInt(array[0].length / 2 + 1) * 2;
        array[row][col] = 0;
        boolean first = true, a = false, exitFound = false;

        while (true) {
            if (first) {
                int direction = rand.nextInt(4);
                if (direction == 0 && row != 0) {
                    array[row-1][col] = 0;
                    array[row-2][col] = 0;
                    row -= 2;
                    first = false;
                }
                else if (direction == 1 && col != array[0].length - 1) {
                    array[row][col+1] = 0;
                    array[row][col+2] = 0;
                    col += 2;
                    first = false;
                }
                else if (direction == 2 && row != array.length - 1) {
                    array[row+1][col] = 0;
                    array[row+2][col] = 0;
                    row += 2;
                    first = false;
                }
                else if (direction == 3 && col != 0) {
                    array[row][col-1] = 0;
                    array[row][col-2] = 0;
                    col -= 2;
                    first = false;
                }
            }
            else {
                int availableCells = 0;
                boolean up = false, down = false, left = false, right = false;
                if (row != 0 && array[row-2][col] == -1) {
                    availableCells++;
                    up = true;
                }

                if (col != array[0].length-1 && array[row][col+2] == -1) {
                    availableCells++;
                    right = true;
                }

                if (row != array.length-1 && array[row+2][col] == -1) {
                    availableCells++;
                    down = true;
                }

                if (col != 0 && array[row][col-2] == -1) {
                    availableCells++;
                    left = true;
                }

                if (availableCells != 0) {
                    a = true;
                    while (true) {
                        boolean[] b = {up,right,down,left};
                        int i = rand.nextInt(4);
                        if (b[i]) {
                            if (i == 0) {
                                array[row-1][col] = 0;
                                array[row-2][col] = 0;
                                row -= 2;
                            }
                            else if (i == 1) {
                                array[row][col+1] = 0;
                                array[row][col+2] = 0;
                                col += 2;
                            }
                            else if (i == 2) {
                                array[row+1][col] = 0;
                                array[row+2][col] = 0;
                                row += 2;
                            }
                            else if (i == 3) {
                                array[row][col-1] = 0;
                                array[row][col-2] = 0;
                                col -= 2;
                            }
                            break;
                        }
                    }
                }
                else {
                    array[row][col] = 1;
                    if (!exitFound && a) {
                        if (new Random().nextInt(5) == 0) {
                            exitFound = true;
                            exitRow = row;
                            exitCol = col;
                        }
                    }
                    a = false;
                    if (row != 0 && array[row-1][col] == 0 && (array[row-2][col] == 0 || array[row-2][col] == 1)) {
                        array[row-1][col] = 1;
                        array[row-2][col] = 1;
                        row -= 2;
                    }
                    else if (col != array[0].length-1 && array[row][col+1] == 0 && (array[row][col+2] == 0 || array[row][col+2] == 1)) {
                        array[row][col+1] = 1;
                        array[row][col+2] = 1;
                        col += 2;
                    }
                    else if (row != array.length-1 && array[row+1][col] == 0 && (array[row+2][col] == 0 || array[row+2][col] == 1)) {
                        array[row+1][col] = 1;
                        array[row+2][col] = 1;
                        row += 2;
                    }
                    else if (col != 0 && array[row][col-1] == 0 && (array[row][col-2] == 0 || array[row][col-2] == 1)) {
                        array[row][col-1] = 1;
                        array[row][col-2] = 1;
                        col -= 2;
                    }
                }
                if (checkDone()) {
                    if (!exitFound) {
                        exitRow = row;
                        exitCol = col;
                    }
                    break;
                }
            }
        }
    }

    private boolean checkDone() {
        int count = 0;
        for (int k = 0; k < array.length; k+=2) {
            for (int l = 0; l < array[0].length; l+=2) {
                if (array[k][l] == 0 || array[k][l] == 1)
                    count++;
            }
        }
        return count == numCells;
    }

    private JPanel createTopPanel() {
        GridBagLayout l = new GridBagLayout();
        GridBagConstraints c = new GridBagConstraints();
        c.fill = GridBagConstraints.BOTH;

        JPanel panel = new JPanel(l);
        JLabel inputLabel = new JLabel("ID:");
        c.gridwidth = 1;
        l.setConstraints(inputLabel,c);
        panel.add(inputLabel);

        JTextField inputField = new JTextField(5);
        l.setConstraints(inputField,c);
        panel.add(inputField);

        JLabel rowLabel = new JLabel("Rows:");
        l.setConstraints(rowLabel,c);
        panel.add(rowLabel);

        JTextField rowField = new JTextField(3);
        l.setConstraints(rowField,c);
        panel.add(rowField);

        JLabel colLabel = new JLabel("Columns:");
        l.setConstraints(colLabel,c);
        panel.add(colLabel);

        JTextField colField = new JTextField(3);
        l.setConstraints(colField,c);
        panel.add(colField);

        JButton applyButton = new JButton("Apply");
        applyButton.addActionListener(ev -> {
            try {
                int seed = Integer.parseInt(inputField.getText()),
                    rows = Integer.parseInt(rowField.getText()),
                    cols = Integer.parseInt(colField.getText());
                if (seed >= 0 && rows >= 3 && cols >= 3) {
                    gameOver = false;
                    scoreLabel.setText("Score: " + (score = 0));
                    constructArray(seed,rows,cols);
                    row = (int) (Math.random() * (array.length / 2 + 1)) * 2;
                    col = (int) (Math.random() * (array[0].length / 2 + 1)) * 2;
                    frame.setSize((1+SQWIDTH * array[0].length)/2 > 750 ? (1+SQWIDTH * array[0].length)/2 : 750,
                            75+(1+SQWIDTH * array.length)/2);
                    mazePanel.setPreferredSize(new Dimension(
                            (1+SQWIDTH * array[0].length)/2 > 750 ? (1+SQWIDTH * array[0].length)/2 - 15 : 750,
                            15+(1+SQWIDTH * array.length)/2));
                    ellipse = new Ellipse2D.Double(col*SQWIDTH/2+3,row*SQWIDTH/2+3,10,10);
                    setItems();
                    mazePanel.repaint();
                }
            } catch (NumberFormatException ignore) {}
        });
        l.setConstraints(applyButton,c);
        panel.add(applyButton);

        scoreLabel = new JLabel("Score: ");
        c.gridwidth = GridBagConstraints.REMAINDER;
        l.setConstraints(scoreLabel,c);
        panel.add(scoreLabel);

        return panel;
    }

    private void createMazePanel() {
        mazePanel = new JPanel() {
            @Override
            protected void paintComponent(Graphics g) {
                super.paintComponent(g);
                int x = 0, y = 0;
                if (!gameOver) {
                    for (int k = 0; k < array.length; k+=2) {
                        for (int l = 0; l < array[0].length; l+=2) {
                            int n = array[k][l];
                            if (n == 0 || n == 1 || n == 4 || n == 5 || n == 6)
                                g.setColor(Color.white);
                            else if (n == 2)
                                g.setColor(Color.green);
                            else if (n == 3)
                                g.setColor(Color.red);
                            g.fillRect(x, y, SQWIDTH, SQWIDTH);
                            if (n == 4) {
                                g.setColor(new Color(245,209,34));
                                g.fillOval(x+3, y+3, 10, 10);
                            }
                            else if (n == 5) {
                                g.setColor(new Color(255,223,55));
                                g.fillPolygon(new int[]{x,x+3,x+8,x+13,x+16,x+14,x+2},new int[]{y+2,y+6,y+2,y+6,y+2,y+16,y+16},7);
                                g.setColor(new Color(12,234,44));
                                g.fillOval(x+7,y+6,4,7);
                            }
                            else if (n == 6) {
                                Graphics2D g2 = (Graphics2D) g.create();
                                g2.setStroke(new BasicStroke(2,BasicStroke.CAP_ROUND,BasicStroke.JOIN_ROUND));
                                g2.setColor(new Color(108,225,119));
                                g2.drawOval(x+5, y+1, 8, 8);
                                g2.drawLine(x+5, y+3, x+5, y+11);
                                g2.drawArc(x+5, y+8, 7, 7, 180, 180);
                            }
                            g.setColor(Color.black);
                            if (k != array.length-1 && array[k+1][l] == -1)
                                g.fillRect(x-3, y+SQWIDTH-3, SQWIDTH+3, 3);
                            if (l != array[0].length-1 && array[k][l+1] == -1)
                                g.fillRect(x+SQWIDTH-3,y,3,SQWIDTH);
                            x += SQWIDTH;
                        }
                        x = 0;
                        y += SQWIDTH;
                    }
                    g.setColor(Color.red);
                    ((Graphics2D) g).fill(ellipse);
                }
            }
        };
    }

    private void setKeyActions() {
        InputMap im = mazePanel.getInputMap(JComponent.WHEN_IN_FOCUSED_WINDOW);
        ActionMap am = mazePanel.getActionMap();

        im.put(KeyStroke.getKeyStroke("pressed UP"), "up");
        am.put("up", new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (row != 0 && array[row-1][col] != -1 && array[row-2][col] != 3 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    row -= 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.y = row * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });

        im.put(KeyStroke.getKeyStroke("pressed RIGHT"), "right");
        am.put("right",new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (col != array[0].length-1 && array[row][col+1] != -1 && array[row][col+2] != 3 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    col += 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.x = col * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });

        im.put(KeyStroke.getKeyStroke("pressed DOWN"), "down");
        am.put("down", new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (row != array.length-1 && array[row+1][col] != -1 && array[row+2][col] != 3 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    row += 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.y = row * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });

        im.put(KeyStroke.getKeyStroke("pressed LEFT"), "left");
        am.put("left",new AbstractAction() {
            @Override
            public void actionPerformed(ActionEvent ev) {
                if (col != 0 && array[row][col-1] != -1 && array[row][col-2] != -1 && !gameOver) {
                    int n = array[row][col];
                    array[row][col] = n == 0 || n == 1 || n == 4 || n == 5 ? 2 : 3;
                    col -= 2;
                    n = array[row][col];
                    if (n == 4)
                        scoreLabel.setText("Score: " + (score += 20));
                    else if (n == 5)
                        scoreLabel.setText("Score: " + (score += 50));
                    else if (n == 2)
                        scoreLabel.setText("Score: " + (score -= 1));
                    ellipse.x = col * SQWIDTH/2 + 3;
                    mazePanel.repaint();
                }
                if (!gameOver && array[row][col] == 6) {
                    JOptionPane.showMessageDialog(frame, "Huzzah! You found the exit! ", "Finish", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
                else if (!gameOver && checkGameOver()) {
                    JOptionPane.showMessageDialog(frame, "You got trapped! Try again!", "Game over", JOptionPane.PLAIN_MESSAGE);
                    gameOver = true;
                }
            }
        });
    }

    private void setItems() {
        array[exitRow][exitCol] = 6;
        Random r = new Random();
        for (int k = 1; k < (array.length * array[0].length) / 20; k++) {
            int row = r.nextInt(array.length / 2 + 1) * 2,
                col = r.nextInt(array[0].length / 2 + 1) * 2;
            if ((row == this.row && col == this.col) || array[row][col] == 4 || array[row][col] == 5 || array[row][col] == 6)
                k--;
            else
                array[row][col] = r.nextInt(2) + 4;
        }
    }

    private boolean checkGameOver() {
        if (row == 0 && col == 0)
            return (array[row+2][col] == 3 && array[row][col+2] == 3) ||
                   (array[row+1][col] == -1 && array[row][col+2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col+1] == -1);
        else if (row == 0 && col == array[0].length-1)
            return (array[row+2][col] == 3 && array[row][col-2] == 3) ||
                   (array[row+1][col] == -1 && array[row][col-2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col-1] == -1);
        else if (row == array.length-1 && col == 0)
            return (array[row-2][col] == 3 && array[row][col+2] == 3) ||
                   (array[row-1][col] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col+1] == -1);
        else if (row == array.length-1 && col == array[0].length-1)
            return (array[row-2][col] == 3 && array[row][col-2] == 3) ||
                   (array[row-1][col] == -1 && array[row][col-2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col-1] == -1);
        else if (row == 0)
            return (array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+1] == -1) ||
                   (array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row+1][col] == -1 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3);
        else if (col == 0)
            return (array[row][col+2] == 3 && array[row-1][col] == -1 && array[row+1][col] == -1) ||
                   (array[row][col+1] == -1 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col+1] == -1 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col+1] == -1 && array[row-2][col] == 3 && array[row+2][col] == 3) ||
                   (array[row][col+2] == 3 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col+2] == 3 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col+2] == 3 && array[row-2][col] == 3 && array[row+2][col] == 3);
        else if (row == array.length-1)
            return (array[row-2][col] == 3 && array[row][col-1] == -1 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3);
        else if (col == array[0].length-1)
            return (array[row][col-2] == 3 && array[row-1][col] == -1 && array[row+1][col] == -1) ||
                   (array[row][col-1] == -1 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col-1] == -1 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col-1] == -1 && array[row-2][col] == 3 && array[row+2][col] == 3) ||
                   (array[row][col-2] == 3 && array[row-2][col] == 3 && array[row+1][col] == -1) ||
                   (array[row][col-2] == 3 && array[row-1][col] == -1 && array[row+2][col] == 3) ||
                   (array[row][col-2] == 3 && array[row-2][col] == 3 && array[row+2][col] == 3);
        else
            return (array[row-2][col] == 3 && array[row][col+1] == -1 && array[row+1][col] == -1 && array[row][col-1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col+2] == 3 && array[row+1][col] == -1 && array[row][col-1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col+1] == -1 && array[row+2][col] == 3 && array[row][col-1] == -1) ||
                   (array[row-1][col] == -1 && array[row][col+1] == -1 && array[row+1][col] == -1 && array[row][col-2] == 3) ||
                   (array[row-1][col] == -1 && array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+1] == -1) ||
                   (array[row-2][col] == 3 && array[row+1][col] == -1 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-1][col] == -1 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-1][col] == -1 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+1][col] == -1 && array[row][col-2] == 3 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-1] == -1 && array[row][col+2] == 3) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+1] == -1) ||
                   (array[row-2][col] == 3 && array[row+2][col] == 3 && array[row][col-2] == 3 && array[row][col+2] == 3);
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(MazeMaker::new);
    }
}

```

The process of creating the actual maze uses the depth-first search algorithm, but with an iterative approach. Here's how it works.

We start with a 2D array of `int` values, each element being a -1. A random element with even indices is chosen, and its value becomes 0:

```
-1 -1 -1 -1 -1 -1  0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1

```

Then the program enters a loop, checking for available cells until it reaches a state where there are no available cells. This can happen several times, and is when it begins to backtrack. At this time all 0s that it comes across become 1s. Also during this time is when it determines whether an exit should be placed at that location. So at the end of it all, the array could look like this:

```
 0  0  0  0  0  0  1  1  1
 0 -1 -1 -1 -1 -1  0 -1  1
 0  0  0  0  0 -1  0 -1  1
-1 -1 -1 -1 -1 -1  0 -1  1
 0  0  0  0  0  0  0 -1  1
 0 -1 -1 -1 -1 -1 -1 -1  1
 0 -1  1  1  1  1  1 -1  1
 0 -1  1 -1  1 -1 -1 -1  1
 0 -1  1 -1  1  1  1  1  1

```

When there are a predetermined number of 1s or 0s at certain spots in the array, the loop exits. Then, using the array, the resulting maze is drawn:

It's easy to see that the -1s in the array represent walls, and the 0s and 1s are corridors. Items are randomly distributed throughout the maze. The red ellipse is the "player" that you control.

The maze is wrapped in a scroll pane for convenience so that if the size exceeds the frame's maximum size you can scroll to see the rest of the maze.

I'd say the only problem with this is how the end of game check is carried out. I thought about several ways to go about doing it, but I ended up resorting to hard-coding it all. I'm open to suggestions on how it can be done.

# Answer
> 3 votes
# Python

I realize I'm late for the party, but here is my take on this challenge. I went text based as I haven't gotten around to learning pygame, yet. It is Python 3. Change input to raw\_input and it should work in python2 also.

The Hook (exit) is represented by "J". "W" is crowns (50). "G" is Gold nuggets (20). The Player is "O". I experimented with using "P" for the player, but I found "O" easier to Identify.

I used standard depth first maze generation, then add the gold, crowns, hook, and current player position. I did not implement the criteria that all treasure can be obtained.

```
import random

direcs = {'n':[0,-1],
          's':[0,1],
          'w':[-1,0],
          'e':[1,0]}
dirs = ['n','s','e','w']

class maze_space(object):
    def __init__(self):
        self.n = 0
        self.s = 0
        self.e = 0
        self.w = 0
        self.visited = 0
        self.contents = ' '

    def mirror(self,drct,val):
        if drct == 'n' : self.s = val
        if drct == 's' : self.n = val
        if drct == 'e' : self.w = val
        if drct == 'w' : self.e = val

class MazeGame(object):

    def __init__(self,horiz=12,vert=8):
        self.completed = 0
        self.score = 0
        self.grid = [[maze_space() for x in range(horiz)] for y in range(vert)]

        def walk(y,x):
            self.grid[y][x].visited = 1
            drs = self.make_dir_list(y, x)
            random.shuffle(drs)
            for dr in drs:
                yy = y + direcs[dr][1]
                xx = x + direcs[dr][0]
                if not self.grid[yy][xx].visited:
                    setattr(self.grid[y][x], dr, 1)
                    self.grid[yy][xx].mirror(dr, 1)
                    walk(yy, xx)

        y, x = self.pick_row_col()
        walk(y, x)
        self.maze_populate()
        self.printmaze()

    def main_loop(self):
        while not self.completed:
            move = get_move(self.grid, self.cury, self.curx)
            self.make_move(move)
            self.printmaze()

    def pick_row_col(self):
        '''pick a random cell in the grid'''
        row = random.randint(0, len(self.grid) - 1)
        col = random.randint(0, len(self.grid[0]) - 1)
        return row, col

    def make_dir_list(self, y, x):
        '''return list of available move directions'''
        drs = dirs[:]
        if x == 0 : drs.pop(drs.index('w'))
        if y == 0 : drs.pop(drs.index('n'))
        if x == len(self.grid[0]) - 1 : drs.pop(drs.index('e'))
        if y == len(self.grid) - 1 : drs.pop(drs.index('s'))
        return drs

    def maze_populate(self):
        # populate maze with crowns and gold nuggets
        for treasure in ['G', 'W']:
            for _ in range(random.randint(1, len(self.grid[0]))):
                yy, xx = self.pick_row_col()
                self.grid[yy][xx].contents = treasure

        self.cury, self.curx = self.pick_row_col() # start position
        exity, exitx = self.pick_row_col() # hook (exit) position
        #make sure start is not on top of exit
        while self.cury == exity and self.curx == exitx :
            exitx = random.randint(0, len(self.grid[0]) - 1)

        self.grid[self.cury][self.curx].contents = 'O'
        self.grid[exity][exitx].contents = 'J'

    def make_move(self,dr):
        self.grid[self.cury][self.curx].visited += 1
        self.grid[self.cury][self.curx].contents = '.'
            # player has walked twice -> disable
        if self.grid[self.cury][self.curx].visited >= 3:
            self.grid[self.cury][self.curx].contents = 'X'
            drs = self.make_dir_list(self.cury, self.curx)
            for d in drs:
                yyy = self.cury + direcs[d][1]
                xxx = self.curx + direcs[d][0]
                self.grid[yyy][xxx].mirror(d,0)

        yy = self.cury + direcs[dr][1]
        xx = self.curx + direcs[dr][0]
        if self.grid[yy][xx].contents == 'J': self.completed = 1
        if self.grid[yy][xx].contents == 'W': self.score += 50
        if self.grid[yy][xx].contents == 'G': self.score += 20
        if self.grid[yy][xx].contents == '.': self.score -= 1
        self.grid[yy][xx].contents = 'O'
        self.cury, self.curx = yy, xx

    def printmaze(self):
        if self.completed: print('\nMaze complete.  Good job!')
        print('Score: %d'%self.score)
        print('|'+''.join('---' for _ in self.grid[0]))
        for line in self.grid:
            print('|' + ''.join(' %s '%x.contents if x.e else ' %s|'%
                                x.contents for x in line))
            print('|' + ''.join('  -' if x.s else '---' for x in line))

def get_params():
    hor = input('width (default=12): ')
    hor = int(hor) if hor else 12
    ver = input('height (default=8): ')
    ver = int(ver) if ver else 8
    rseed = input('seed : ')
    rseed = int(rseed) if rseed else random.randint(1,65535)
    print(rseed)
    random.seed(rseed)
    print("'J' = hook (exit)\n'O' = Player")
    print("'G' = gold nugget (20 points)\n'W' = Crown (50 points)")
    print('Player may only tread on a given tile twice')
    return hor,ver

def get_move(grid, y, x):
    choice = input('where do you want to move %s q to quit: '%dirs)
    if choice == 'q' : exit()
    if choice in dirs and getattr(grid[y][x],choice): return choice
    return get_move(grid, y, x)

def main():
    hor,ver = get_params()
    maze = MazeGame(hor,ver)
    maze.main_loop()

if __name__ == '__main__':
    main()

```

---
Tags: popularity-contest, game, board-game
---


title: Finding Poly Nemo!

text:
# Question
Title: Finding Poly Nemo!
Oh no! Nemo, our small clown fish is lost in this ASCII ocean and his dad Marlin is trying to find him.

Your task is to get Marlin to Nemo safely. But beware, we have a feeding frenzy Bruce on the loose, so better avoid him at all costs!

**Details**

You are given a rectangular ASCII ocean grid containing only lowercase alphabets `a-z`. This ocean will have `nemo`, `marlin` and `bruce` inside it in the form of a continuous polyomino, always starting from the top most cell in the first column of polyomino. So for example, out of all possible tetrominos, the valid ones are listed in the below snippet

```
nemo

n
e
m
o

no
em

ne
om

nem
  o

  o
nem

n
e
mo

 o
 m
ne

ne
 m
 o

n
emo

ne
 mo

n
em
 o

 mo
ne
```

But forms like these are invalid and won't be present in the input:

```
omen

ne
mo

nem
o

o
m
en

nem
 o

n
eo
m

```

Finally, your task is to find a path from the `marlin` polyomino tile to the `nemo` polyomino tile making sure that any cell in your path is not adjacent to the `bruce` polyomino tile. Your output should replace all alphabets which are not part of the `marlin` tile, `nemo` tile and the path connecting them both with a character from the printable ASCII range (including space) other than the lowercase `a-z`.

**Example**

If the input ocean is as following:

```
oxknvvolacycxg
xmliuzsxpdzkpw
warukpyhcldlgu
tucpzymenmoyhk
qnvtbsalyfrlyn
cicjrucejhiaeb
bzqfnfwqtrzqbp
ywvjanjdtzcoyh
xsjeyemojwtyhi
mcefvugvqabqtt
oihfadeihvzakk
pjuicqduvnwscv

```

(with the 3 polyominos being:

```
...n..........
.mli..........
.ar...........
..............
....b.........
....ruce......
..............
.....n........
.....emo......
..............
..............
..............

```

)

Then a valid solution may look like:

```
...n..........
.mli..........
.ar...........
.u............
.n............
.i............
.z............
.wvjan........
.....emo......
..............
..............
..............

```

Below snippet contains a few more examples:

```
oxknvvolacycxg
xmliuzsxpdzkpw
warukpyhcldlgu
tucpzymenmoyhk
qnvthsalyfrlyn
cibrucejhiaebu
bzqfnfwqtrzqbp
ywvjanjdtzcoyh
xsjeyemojwtyhi
mcefvugvqabqtt
oihfadeihvzakk
pjuicqduvnwscv

...n..........
.mli..........
.ar...........
.u............
qn............
c.............
b.............
ywvjan........
.....emo......
..............
..............
..............

----------------------------------------------

nemokjahskj
sdjsklakdjs
uqiceasdjnn
sbruakmarli

nemokjahskj
..........s
..........n
......marli

----------------------------------------------
```

**Notes**

* The grid will always be a perfect rectangle and will contain only one polyomino tile of `nemo`, `marlin` and `bruce`.
* Your path should not go through `bruce` or any of the 4 adjacent (up, down, left and right) cells of any cell in the `bruce` tile.
* It is always guaranteed that there will be at least one valid path from `marlin` to `nemo`.
* There is no requirement of a shortest path here, so go nuts!
* Even though you don't have to find the shortest path, any cell in the path (path not including marlin or nemo) cannot be adjacent to more than two other cells in the path.
* The path should not go through the `marlin` or `nemo` tiles, as it would then confuse the little fishes in choosing a direction.
* As usual, you may write a program or function, taking input via STDIN (or closest equivalent), command-line argument or function parameter, and producing output via STDOUT (or closest equivalent), return value or function (out) parameter.
* If multi-line input is not possible, then you may assume that the grid is joined by the `|` character instead of `\n`. You may also take the input as an array of grid rows.

This is code golf so the shortest entry in bytes wins.

# Answer
> 4 votes
# Matlab 560

560 bytes when removing all unnecessary spaces, all semicolons and all comments. Could be golfed much more but I am to tired right now (maybe tomorrow...) Good night everyone.

PS: I assumed that the path must have a 4 neighbourhood ('+') connectedness.

```
function c(A)
Z = [0,1,0;1,1,1;0,1,0];
Br = q('bruce');
Bn = conv2(Br,ones(3),'s')>0;
Ne = q('nemo');
Ma = q('marlin');
%construct path marlin to nemo
U=Ma>0;M=A*Inf;
M(U)=0;
for k=1:2*sum(size(A))%upper bound for path length
    %expand
    V=imdilate(U,Z);
    V(Bn)=0;
    M(V-U==1)=k;
    U=V;
    %disp(M)
end
%go back from nemo to marlin
Pr=reshape(1:numel(A),size(A));
[i,j]=find(Ne);
m=M(i(1),j(1));%value
P=A*0;%path image
P(i(1),j(1))=1;
for k=m:-1:1
    %find neighbour of (i(1),j(1)) with value m-1
    U=imdilate(P,Z);
    F = M==k;
    G = F&U;
    mask = Pr == min(Pr(F & U));
    P(mask)=1;
end
A(~P & ~Ma & ~Ne)='.';
disp(A)

    function M = q(s)%find string in matrix, A ascii, M mask
        M = A*0;
        m=numel(s);
        N = M+1;%all neighbours
        for k=1:m;
            M(A==s(k) & N)=k;%only set the ones that were in the neighbourhood of last
            L=M==k;
            N=imdilate(L,Z);
        end
        for k=m:-1:2
            %set all that are not neighbour to next higher highest to zero
            L=M==k;
            N=imdilate(L,Z);
            M(M==k-1 & ~N)=0;
        end
    end

end

```

Calling function : (newlines not necessary)

```
c(['oxknvvolacycxg',
'xmliuzsxpdzkpw',
'warukpyhcldlgu',
'tucpzymenmoyhk',
'qnvtbsalyfrlyn',
'cicjrucejhiaeb',
'bzqfnfwqtrzqbp',
'ywvjanjdtzcoyh',
'xsjeyemojwtyhi',
'mcefvugvqabqtt',
'oihfadeihvzakk',
'pjuicqduvnwscv']);

```

Output:

```
...n..........
.mli..........
.ar...........
..c...........
..v...........
..c...........
..q...........
..vjan........
.....emo......
..............
..............
..............

```

# How it works

### Extracting names

The first part is extracting the names e.g. `nemo`, which is done by the function `q()`. The function first marks everything as 0, then the occurences first letter of the name as `1`, then the second letter as `2` if there is a `1` in the neighbourhood, then the third and so on. After that there should in the case of `nemo` be only one `4`. From that we go backwards until we found the `1` again and then delete all the other numbers that were greater that, so we get back a nice mask where the letters `nemo` are masked. We do this for all three names, and can then proceed to finding a path.

### Finding the path

We start at Marlins positions and send a shockwave throu the hole 'image' step by step. In each step we increase the distance counter and mark the 'pixels' under the wavefront with the current distance. (As it is usually done with shortest path algorithms.) This wavefront obviously gets blocked by the area of Bruce, therefore it will flow around him. This step is repeated until an upper bound is reached. This (admittedly very loose) upper bound is now the circumference of the 'image' (the shortest paths will be way shorter in any case). In the test case it looks something like this:

```
 2 1 1  0  1  2  3  4  5  6  7  8  9 10
 1 0 0  0  1  2  3  4  5  6  7  8  9 10
 1 0 0  1  2  3  4  5  6  7  8  9 10 11
 2 1 1  _  _  _  5  6  7  8  9 10 11 12
 3 2 2  _  _  _  _  _  _  9 10 11 12 13
 4 3 3  _  _  _  _  _  _ 10 11 12 13 14
 5 4 4  _  _  _  _  _  _ 11 12 13 14 15
 6 5 5  6  7  8  9 10 11 12 13 14 15 16
 7 6 6  7  8  9 10 11 12 13 14 15 16 17
 8 7 7  8  9 10 11 12 13 14 15 16 17 18
 9 8 8  9 10 11 12 13 14 15 16 17 18 19
10 9 9 10 11 12 13 14 15 16 17 18 19 20

```

Now start at `nemo` pixels and decrease the distance counter in each step and add a neighbour with the next lower distance (according to that distance map we calculated earlier) to our path.

# Answer
> 3 votes
# Python 2 - 658

Very very inefficient both in time and memory. The function to identify the patterns is the recursive function S, and the function to find the paths is the C, which is basically a horribly inefficient A\* implementation.

```
G=input().split('\n')
R=range
S=lambda g,x,y,s,B:[[(x,y)]+r for a,b in[(-1,0),(0,-1),(0,1),(1,0)]for r in S(g,x+a,y+b,s[1:],B)if B(x,y)and s[0]==g[y][x]]if s else[[]]
C=lambda l,N,B:[i for i in l if i[-1]in N]or C([i+[(i[-1][0]+c,i[-1][1]+d)]for i in l for c,d in [(-1,0),(0,-1),(0,1),(1,0)]if all(1<abs(i[-1][0]+c-a)or 1<abs(i[-1][1]+d-b)for a,b in B)],N,B)
X,Y=len(G[0]),len(G)
N,M,B=[filter(list,[S(G,s,t,e,lambda a,b:0<=a<X and 0<=b<Y and Y*(a-s)+b-t>=0)for s in R(X)for t in R(Y)])[0][0]for e in["nemo","marlin","bruce"]]
print'\n'.join(''.join(G[y][x]if(x,y)in N+M+min([C([[k]],N,B)[0]for k in M],key=lambda i:len(i))else'.'for x in R(X))for y in R(Y))

```

For testing use this (very slightly) less golfed one (which calculates the path once instead for every tile)

```
G=input().split('\n')
R=range
S=lambda g,x,y,s,B:[[(x,y)]+r for a,b in[(-1,0),(0,-1),(0,1),(1,0)]for r in S(g,x+a,y+b,s[1:],B)if B(x,y)and s[0]==g[y][x]]if s else[[]]
C=lambda l,N,B:[i for i in l if i[-1]in N]or C([i+[(i[-1][0]+c,i[-1][1]+d)]for i in l for c,d in [(-1,0),(0,-1),(0,1),(1,0)]if all(1<abs(i[-1][0]+c-a)or 1<abs(i[-1][1]+d-b)for a,b in B)],N,B)
X,Y=len(G[0]),len(G)
N,M,B=[filter(list,[S(G,s,t,e,lambda a,b:0<=a<X and 0<=b<Y and Y*(a-s)+b-t>=0)for s in R(X)for t in R(Y)])[0][0]for e in["nemo","marlin","bruce"]]
s=N+M+min([C([[k]],N,B)[0]for k in M],key=lambda i:len(i))
print'\n'.join(''.join(G[y][x]if(x,y)in s else'.'for x in R(X))for y in R(Y))

```

---
Tags: code-golf, grid, path-finding
---