# Question
Title: What's the chance that I'll win a door prize?
My local ACM chapter gives out door prizes to people who come to the meetings. You get an increased chance of winning if you solve the programming puzzle, however (but *I* always solve that puzzle). Thus, some people have 1 entry, while others have 2. But wait! The way the raffle program works is not by adding in another entry when someone solves the puzzle. Instead, it keeps track of the number of "lives" a person has, decrementing that if that person is chosen in each pass of it's random sampling algorithm. So it works like this:

```
Doorknob: 1.  xnor: 2.  Justin: 2.  Alex: 1.  Dennis: 2.

```

Then the program randomly chooses one of `[Doorknob, xnor, Justin, Alex, Dennis]`, decrements the number (say it chooses `Justin`):

```
Doorknob: 1.  xnor: 2.  Justin: 1.  Alex: 1. Dennis: 2.

```

And repeats. If someone's number of "lives" goes to `0` (let's choose `Justin` again), they're removed from the list:

```
Doorknob: 1.  xnor: 2.  Alex: 1.  Dennis: 2.

```

This continues until there's one person left; that person is the winner.

Now the real question is, what was the probability that I would have won?

---

You will be given two inputs:

* `n`. This is the number of people entered into the challenge
* `k`. This is the number of people (of those `n`) who have 2 lives. This number always includes you.

So if I had a function `p` and called `p(10, 5)`, that would be the probability of winning the prize where there are 10 people total, 5 of which only have 1 life, whereas 5 (including you) have 2 lives.

---

You are expected to output the probability of winning either exactly, or as a decimal. At any rate, answers must be accurate up to and including the 4th decimal place after the decimal point. Whether or not you round to that digit is up to you.

Your solution may be a randomized solution which outputs the answer to the 4th decimal place with *high probability*. You may assume that the built in RNG you use is truly random, and it must output the correct answer with at least 90% probability.

Furthermore, your code need only work for `n, k <= 1000`, although I did provide test cases larger than that for those curious.

---

## Test Cases

Note: some of these are general formulae.

```
n,    k   |  output
----------+---------
1,    1   |  1
2,    2   |  0.5
2,    1   |  0.75
3,    1   |  11/18 = 0.611111111
1000, 1   |  0.007485470860550352
4,    3   |  0.3052662037037037
k,    k   |  1/k
n,    1   |  (EulerGamma + PolyGamma[1 + n])/n    (* Mathematica code *)
          |  (γ + ψ(1 + n))/n
10,   6   |  0.14424629234373537
300,  100 |  0.007871966408910648
500,  200 |  0.004218184180294532
1000, 500 |  0.0018008560286627948
---------------------------------- Extra (not needed to be a valid answer)
5000, 601 |  0.0009518052922680399
5000, 901 |  0.0007632938197806958

```

For another few checks, take `p(n, 1) * n` as follows:

```
n     |  output
------+---------
1     | 1
2     | 1.5
3     | 1.8333333333333335
10    | 2.928968253968254
100   | 5.1873775176396215
-------------------------- Extra (not needed to be a valid answer)
100000| 12.090146129863305

```

# Answer
# MATL, 42 bytes

```
:<~QXJx`J`tf1Zry0*1b(-tzq]f1=vts3e8<]6L)Ym

```

This uses a probabilistic (Monte Carlo ) approach. The experiment is run a large number of times, from which the probability is estimated. The number of realizations is selected to *ensure* that the result is correct up to the fourth decimal with probability at least 90%. However, this takes a very long time and a lot of memory. In the link below the number of realizations has been reduced by a factor of 106 so that the program ends in a reasonable amout of time; and only the *first* decimal is guaranteed to be accurate with at least 90% probability.

*EDIT (July 29, 2016): due to changes in the language, `6L` needs to be replaced by `3L`. The link below incorporates that modification.*

**Try it online!**

### Background

Let *p* denote the probability to be computed. The experiment described in the challenge will be run for a number *n* of times. Each time, either you win the prize (“*success*”) or you don't. Let *N* be the number of successes. The desired probability can be *estimated* from *N* and *n*. The larger *n* is, the more accurate the estimation will be. The key question is how to select *n* to fulfill to the desired accuracy, namely, to assure that at least 90% of times the error will be less than 10−4.

Monte Carlo methods can be

* *Fixed-size*: a value of *n* is fixed in advance (and then *N* is random);
* *Variable-size*: *n* is determined on the fly by the simulation results.

Among the second category, a common used method is to fix *N* (desired number of successes) and *keep simulating until that number of successes is achieved*. Thus *n* is random. This technique, called *inverse binomial sampling* or *negative-binomial Monte Carlo*, has the advantage that the accuracy of the estimator can be bounded. For this reason it will be used here.

Specifically, with negative-binomial Monte Carlo *x* = (*N*−1)/(*n*−1) is an unbiased estimator of *p*; and the probability that *x* deviates from *p* by more than a given ratio can be upper-bounded. According to equation (1) in this paper (note also that the conditions (2) are satisfied), taking *N* = 2.75·108 or larger ensures that *p*/*x* belongs to the interval \[1.0001, 0.9999\] with at least 90% probability. In particular, this implies that *x* is correct up to the 4th decimal place with at least 90% probability, as desired.

### Code explained

The code uses *N* = `3e8` to save one byte. Note that doing this many simulations would take a long time. The code in the link uses *N* = `300`, which runs in a more reasonable amount of time (less than 1 minute in the online compiler for the first test cases); but this only assures that the *first* decimal is correct with probability at least 90%.

```
:        % Take k implicitly. Range [1 ... k]
<~       % Take n implicitly. Determine if each element in the previous array is
         % less than or equal than n
Q        % Add 1. This gives an array [2 ... 2 1 ... 1]
XJx      % Copy to clipboard J. Delete from stack
`        % Do...while. Each iteration is a Monte Carlo realization, until the
         % desired nunber of successes is reached
  J      %   Push previously computed array [2 ... 2 1 ... 1]
  `      %   Do...while. Each iteration picks one door and decrements it, until
         %   there is only one
    t    %     Duplicate
    f    %     Indices of non-zero elements of array
    1Zr  %     Choose one of them randomly with uniform distribution
    y0*  %     Copy of array with all values set to 0
    1b(  %     Assign 1 to chosen index
    -    %     Subtract
    tzq  %     Duplicate. Number of nonzero elements minus 1. This is falsy if
         %     there was only one nonzero value; in this case the loop is exited
  ]      %   End do...while
  f1=    %   Index of chosen door. True if it was 1 (success), 0 otherwise
  v      %   Concatenate vertically to results from previous realizations
  ts3e8< %   Duplicate. Is the sum less than 3e8? If so, the loop is exited
]        % End do...while
6L)      % Remove last value (which is always 1)
Ym       % Compute mean. This gives (N-1)/(n-1). Implicitly display

```
> 2 votes

# Answer
# Pyth, 34 bytes

```
Mc|!*HJ-GHch*J+*tHgGtH*gtGHKh-GHKG

```

Test suite

Defines a deterministic memoized recursive function `g` taking *n*, *k* as arguments. `g 1000 500` returns `0.0018008560286627952` in about 18 seconds (not included in the above test suite because it times out the online interpreter).

An approximate Python 3 translation would be

```
@memoized
def g(n,k):
    return (not k*(n-k) or (1+(n-k)*((k-1)*g(n,k-1)+g(n-1,k)*(n-k+1)))/(n-k+1))/n

```
> 2 votes

# Answer
## JavaScript (ES6), 65 bytes

```
f=(n,k,d=n-k)=>(!d||(f(n-1,k)*++d*--d+1+(--k&&f(n,k)*k*d))/++d)/n

```

Don't try it with the big numbers though; even f(30, 10) takes a noticeable amount of time.
> 1 votes

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


title: Can Mario go to the end of this map

text:
# Question
Title: Can Mario go to the end of this map
Create a program that determines, given an input of the path, whether Mario can reach the end, denoted by `E`, from the start, denoted by `S`.

A path will look something like this:

```
S = E
=====

```

In a path, the various symbols and what they represent are:

* `=`: wall/floor/ceiling. Mario cannot walk through wall , and cannot fall past a floor, or jump past a ceiling (he would hit his head)
* (space): air. Mario can walk through this, and jump through it, and fall through it
* `S`: air, except showing where Mario starts. This will always appear in the left-most column of the input, at ground level.
* `E`: air, except showing where Mario wants to get. This will always appear in the right-most column of the input, at ground level.

The input will have spaces at every place where Mario could walk.

Mario can only move forward; in this example Mario cannot get to the goal

```
S
===

 ===
   E
====

```

nor can he in this one

```
    E
   ==
==
  #==
==
   ==
==
S  ==
======

```

However, he can reach the space denoted by `#` (which will not appear in input), because he can jump up to four cells high; Mario is superhuman. As another example of his superhumanity:

```
S
=
=
=
=
=
= #
= =
=
=
=
=     E
=======

```

Mario can get to the `E` by falling the great distance, surviving, and walking calmly to `E`. Note that he cannot reach the `#`, because Mario falls straight down.

Mario can jump *really* high, but not very far forward by comparison.

```
S   E
== ==
 = =

```

Mario may attempt to jump the gap, but he will fail, and fall straight in. he cannot reach the end.

Mario can reach the goal in all of these examples:

```
 E
 =
 =
 =
S=
==

```

```
 =
 =   E
S=   =
==   =
 =   =
 =====

```

```
S
=

=  E
====

```

This is code golf, so fewest bytes wins!

# Answer
> 11 votes
## Slip, ~~38~~ ~~27~~ 25 bytes

```
S>(`=<<`P{1,5}>`P>`P*)+#E

```

Requires input to be padded to a rectangle such that there are spaces in every cell Mario needs to traverse (potentially with a leading line full of spaces). Prints either a string representing the valid path (which includes `S`, `E` and all the `=` walked on except the last) or nothing if no path exists.

Test it here.

### Explanation

Slip was Sp3000's entry to our 2D pattern matching language design challenge. It's a bit like a 2D-extension of regex where you can give instructions to the engine's cursor when it's allowed or required to make left or right turns. It also has a convenient feature where you can prevent the cursor from advancing, allowing you to match a single position twice in a row (with different patterns).

Slip doesn't have something comparable to lookarounds in regex, but since you can move over any position multiple times, one can just test the condition and then return. We use this to ensure that we only jump when on the ground by moving into the ground tile after each step.

```
S           Match the starting position S.
>           Turn right, so that the cursor points south.
(           One or more times... each repetition of this group represents
            one step to the right.
  `=          Match a = to ensure we've ended up on ground level before.
  <<          Turn left twice, so that the cursor points north.
  `P{1,5}     Match 1 to 5 non-punctuation characters (in our case, either space,
              S or E, i.e. a non-ground character). This is the jump.
  >           Turn right, so that the cursor points east.
  `P          Match another non-ground character. This is the step to the right.
  >           Turn right, so that the cursor points south.
  `P*         Match zero or more non-ground characters. This is the fall.
)+
#           Do not advance the cursor before the next match.
E           Match E, ensuring that the previous path ended on the exit.

```

# Answer
> 9 votes
# Java ~~234 230 221 216 208 207 205~~ 179 Bytes

Look, I beat C and python? I have acheived true transcendence among mortals! All jokes aside, this was a fun challenge. The following function takes input as an array of column strings each with the same length. If this is against the rules please do let me know. It outputs 1 meaning a successful mario run, and any other value implying a failed mario run.

```
int m(String[]a){int l=a.length-1,z=a[l].indexOf(69),m=a[0].indexOf(83),i=1,x;a[l]=a[l].replace("E"," ");for(;i<=l;m=x,i++){if(m-(x=a[i].indexOf('='))>3|x<1)return-1;}return m-z;}

```

Here is the older logic (which is similar to the current version) with example use and output. Plus some comments explaining the logic

```
/**
 *
 * @author Rohans
 */
public class Mario {

    int m(String[] a) {
//declare variables for the finish the location of mario and the length
        int z, l = a.length - 1, m = a[0].indexOf("S");
        //treat the exit as a space
        z = a[l].indexOf("E");
        a[l] = a[l].replaceAll("E", " ");
        //go through the map
        for (int i = 1, x, r = 1; i <= l; i++) {
            //if mario can safely jump to the next platform (it picks the highest one)
            if (((x = a[i].indexOf("=")) != 0 && (x = a[i].indexOf(" =")) == -1) || m - x > 4) {
                return 0;
            }
            //adjust marios y location
            m = x;
        }
        //make sure mario made it to the end of the level
        return m == z ? 1 : 0;
    }

    public static void MarioTest(String... testCase) {
        System.out.println(new Mario().m(testCase) == 1 ? "Mario made it" : "Mario did not make it");
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        MarioTest("   S=", "=====", "     =", "     =", "=   =", "     E=");

    }

}

```

# Answer
> 7 votes
# Python, ~~260~~ ~~239~~ ~~222~~ ~~215~~ ~~209~~ 206 Bytes,

### try it on ideone (with test cases)

```
f=lambda m,y=-1,x=0:f(m,m[0].find("S"))if y<0else y<len(m[0])-1and x<len(m)and m[x][y]!="="and(m[x][y]=="E"or m[x][y+1]=="="and any(f(m,y-i,x+1)for i in range(5)[:(m[x][y::-1]+"=").find("=")])or f(m,y+1,x))

```

call like: `f([' S=', ' E='])`

### patch notes:

*Now, like some of the other solutions, assumes input is an array of coloumn strings, each starting with a " "*

*Wrapper for old input form:* `g=lambda x:f(map("".join,zip(*([" "*x.index("\n")]+x.split("\n")))))`

*Also, I fixed a bug where Mario could jump through blocks above him.*

### ungolfed version with explanations:

`f` recursivly calls itself in all directions Mario can move to from `y,x`. It returns `True` when it reaches the `"E"nd`, which then goes back through all the function calls until `g` finally returns `True`.

```
def g(x):
    #create a array of strings which are the rows of the input
    global m
    m=x.split("\n")
    m=[" "*len(m[0])]+m # because Mario can jump over sometimes
    #Mario starts at the S
    return f([i for i,a in enumerate(m) if a[0]=="S"][0],0)

def f(y,x):
    #print y,x
    if y>len(m)-2 or x>=len(m[0]) or y<0: return False #out of bounds
    if m[y][x]=="E":return True #Reached the goal
    if m[y][x]=="=":return False #We got stuck inside a wall
    if m[y+1][x]=="=": #if you have ground under your feet
        for i in range(5): #jump max 4
            if f(y-i,x+1): #go one forward and try to go further from there
                return True
    return f(y+1,x) ##fall down

```

# Answer
> 5 votes
## Snails, ~~41~~ ~~37~~ 29 bytes

*Thanks to feersum for some help with avoiding overlapping paths and for saving 4 bytes.*

```
=\S(^=d=\=u\ ,4(r!\=d.),r),\E

```

Requires input to be padded to a rectangle such that there are spaces in every cell Mario needs to traverse (potentially with a leading line full of spaces).

Try it online!

### Explanation

Snails was feersum's entry to our 2D pattern matching language design challenge. Like Slip it's also similar to regex, but the major difference is that a) this one supports assertions (lookarounds) and b) aside from these assertions, it's not possible to traverse any cell in the grid twice. That makes this problem a bit tricky, since there are cases where Mario needs to fall into a hole and jump back out, e.g.:

```
S E
= =
===

```

Apart from these differences, the syntax of the two languages also differs quite a lot.

To circumvent the issue that we can't traverse a cell twice, we always alternate a horizontal step with a vertical step. However, this means that we have need to handle a fall before we step over the ledge. So falls will technically actually go through ground tiles but we'll ensure that they only happen next to open space.

```
=\S        Ensure that the match starts on an S, without actually matching it.
(          This group matches zero or more steps to the right (with a potential
           vertical step after each one).
  ^=         Match a non-ground cell, stepping right (on the first iteration,
             there is no step yet, so this matches the S).
  d=\=       Ensure that there's a ground tile below, so that the step ends on
             a valid position.
  u\ ,4      Match 0 to 4 spaces going up. This the optional jump.
  (          This group matches zero or more steps down, if a fall is valid here.
    r!\=       Ensure that there is no ground-tile right of the current cell.
    d.         Take one step down onto any character.
  ),
  r          Reset the direction to right for the next iteration.
),
\E        Match the exit.

```

# Answer
> 4 votes
# C, ~~256~~ ~~236~~ ~~213~~ 197 bytes

*20 bytes saved by "This will always appear in the left-most column of the input"*
*23 bytes saved thanks to @RohanJhunjhunwala's column-based system*

Try it on ideone, with test cases...

```
k,y,x,h;f(v,l)char**v;{h=strlen(*v);x=strcspn(*v,"S");while(y<l&x<h)if(v[y][x]==69)return 0;else if(v[y][x+1]^61)x++;else{if(v[y+1][x]==61)while(k<4)if(v[y+1][x-++k]^61){x-=k;break;}y++;}return 1;}

```

# Usage:

```
$ ./mario "S=" " =" " =" " =" "E="
main(c,v)char**v;{printf("%s",f(v+1,c-1)==0?"true":"false");}

```

---

Ungolfed with explanation:

```
k,y,x,h; //omitting int for saving 4 bytes, global variables initialize as 0 by default
f(v,l)char**v;{ //saving 2 bytes
    h=strlen(v[0]); //get height of map
    x=strcspn(v[0],"S"); //where is start point?
    while(y<l&&x<h) //while not out of bounds
        if(v[y][x]==69)return 0; //if we hit end return 0 (69 is ASCII E)
        else if(v[y][x+1]!=61)x++; //we fall one block if there isn't floor underneath us (61 is ASCII =)
        else{
            if(v[y+1][x]==61) //if there is a wall in front of us
                while(k<4) //start counting
                    if(v[y+1][x-++k]!=61){ //if found a way
                        x-=k; //go to there
                        break; //we don't want to jump multiple times
                    }
            y++; //finally, walk one block forwards
        }
    return 1; //if out of bounds
}

```

# Answer
> 2 votes
# PHP, ~~399~~ ~~338~~ ~~284~~ ~~265~~ 251 bytes

```
<?function w($m,$p){$w=strpos($m,"
")+1;if($p>strlen($m)|($p%$w)>$w-2|$p<0|'='==$m[$p])return 0;if('E'==$m[$p])die(1);if('='!=$m[$p+$w])return w($m,$p+$w);else for(;$z<5&'='!=$m[$q=$p-$w*$z];$z++)if(w($m,$q+1))die(1);}die(w($m=$argv[1],strpos($m,S)));

```

expects input as command line argument with unix style line breaks and trailing spaces in every line, returns exit code `1` for success, `0` for failure

**breakdown** to function

```
function w($m,$p) // function walk
{
    $w=strpos($m,"\n")+1;
    if($p<0|$p>strlen($m)|($p%$w)>$w-2  // too high / too low / too far right
        | '='==$m[$p]                   // or inside a wall
    )return 0;
    if('E'==$m[$p])return 1;            // Exit found
    if('='!=$m[$p+$w])return w($m,$p+$w); // no wall below: fall down
    else for($z=0;$z<5                  // else: jump
        & '='!=$m[$q=$p-$w*$z]          // do not jump through walls
        ;$z++)
        if(w($m,$q+1))                  // try to walk on from there
            return 1;
    // no success, return failure (NULL)
}
function m($i){$argv=[__FILE__,$i];
    return w($m=$argv[1],strpos($m,S));     // walk through map starting at position of S
}

```

**tests** (on function m)

```
$cases=[
    // examples
    "S = E\n=====",0,
    "S   \n=== \n    \n ===\n   E\n====",0,
    "    E \n   == \n==    \n   == \n==    \n   == \n==    \nS  == \n======",0,
    "S      \n=      \n=      \n=      \n=      \n=      \n=      \n= =    \n=      \n=      \n=      \n=     E\n=======",1,
    "S   E\n== ==\n = = ",0,
    " E\n =\n =\n =\nS=\n==",1,
    "      \n =    \n =   E\nS=   =\n==   =\n =   =\n =====",1,
    "S   \n=   \n    \n    \n    \n    \n    \n    \n=  E\n====",1,
    // additional cases
    "S \n= \n=E",1,
    " == \n == \n    \nS==E\n==  ",1
];
echo'<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';
while($cases)
{
    $m=array_shift($cases);
    $e=array_shift($cases);
    $y=m($m);
    $w=strpos($m,"\n");
    echo"<tr><td><div style=background-color:yellow;width:",$w*8,"px><pre>$m</pre></div>width=$w</td>
        <td>$y</td><td>$e</td><td>",$e-$y?'N':'Y',"</td></tr>";
}
echo'</table>';

```

# Answer
> 2 votes
# Ruby, ~~153~~ 147 bytes

Sorry, Java... your spot as best non-golf lang for the job is being taken over!

Input is a list of column strings, prepended with a single space in the style of how the Slip and Snails solutions require their inputs to be padded with a rectangle of empty space.

Try it online!

```
f=->m,j=0,s=p{c,n=m[j,2]
s||=c=~/S/
e=c=~/E/
s+=1 while(k=c[s+1])&&k!=?=
s==e||(0..4).any?{|i|k&&s>=i&&c[s-i,i]!~/=/&&n&&n[s-i]!=?=&&f[m,j+1,s-i]}}

```

# Answer
> 2 votes
## Grime, 46 bytes (non-competing)

```
A=\E|[S ]&<\ {,-4}/0/./* \ /*/A/\=/./*>
n`\S&A

```

I have updated Grime several times after this challenge was posted, so this answer is not eligible for winning. Some of the changes are so new that I haven't been able to get them into TIO, but once I do, you can try out the program. In any case, my repository contains a version that handles this code correctly.

The program prints `1` if Mario can reach the goal, and `0` if not. The input has to contain spaces in all places Mario needs to visit. For general inputs, I have the following **57-byte** solution:

```
A=\E|[ \bS]&<[ \b]{,-4}/0/[]/* [ \b]/*/A/\=/[]/*>
nb`\S&A

```

## Explanation

The high-level explanation is that the nonterminal `A`, defined on the first line, matches a **1×1** sub-rectangle of the input where Mario can reach the goal. `A` is defined as either the literal `E` (Mario is already at the goal), or as a **1×1** pattern that's on the left column of some **2×n** rectangle containing a valid Mario jump to another match of `A` on the right column. The second line counts the number of matches of `A` that also contain the start character `S`, and prints that.

Here's a break-down of the code:

```
A=\E|[ S]&<\ {,-4}/0/./* \ /*/A/\=/./*>
A=                                       Define A as
  \E|                                    a literal E, or
     [ S]&                               a literal space or S
          <                           >  contained in a larger rectangle
                                         that this bracketed expression matches.
           \ {,-4}/0/./*                 Left half of the bracketed expression:
           \ {,-4}                        Rectangle of spaces with height 0-4,
                  /                       below that
                   0                      the 1x1 rectangle we're currently matching,
                    /.                    below that any 1x1 rectangles
                      /*                  stacked any number of times vertically.
                         \ /*/A/\=/./*   Right half of the bracketed expression:
                         \ /*             Spaces stacked vertically,
                             /A           below that another match of A,
                               /\=        below that a literal =,
                                  /./*    below that 1x1 rectangles stacked vertically.

```

The idea is that the `\ {,-4}` part on the left matches the space through which Mario jumps upward, and the `\ /*` part on the right matches the space trough which he then falls down. We require that he lands on a match of `A` (since we want to reach the goal) that's on top of a `=`. The vertical stacks below both columns will simply guarantee that the columns have the same height, so we can concatenate them (which is what the single space in the middle does). Here's an ASCII art diagram of an example jump, broken into the aforementioned rectangles, and with spaces replaced by `*`s:

```
Left column:     Right column:   +---+---+
a = \ {,-4}      d = \ /*        | * | * |
b = 0            e = A           +   +   + d
c = ./*          f = \=          | * | * |
                 g = ./*       a +   +---+
                                 | * | * | e
                                 +   +---+
                                 | * | = | f
                                 +---+---+
                               b | S | = |
                                 +---+   | g
                               c | = | * |
                                 +---+---+

```

On the second line, the option `n` triggers counting of all matches, instead of finding the first match. In the general solution, the spaces can also be special out-of-input characters, and option `b` causes the input to be padded with out-of-input characters.

I hope all of this makes sense!

---
Tags: code-golf, ascii-art, path-finding
---


title: Verify a Tower of Hanoi solution

text:
# Question
Title: Verify a Tower of Hanoi solution
If you don't know what the Tower of Hanoi is, I'll explain it briefly: There are three rods and some discs each of which has a different size. In the beginning all discs are on the first tower, in sorted order: The biggest one is at the bottom, the smallest at the top. The goal is to bring all the discs over to the third rod. Sounds easy? Here's the catch: You can't place a disc on top of a disc that is smaller than the other disc; you can only hold one disc in your hand at a time to move them to another rod and you can only place the disc on rods, not on the table, you sneaky bastard.

### ascii example solution:

```
  A      B      C
  |      |      |
 _|_     |      |
__|__    |      |

  A      B      C
  |      |      |
  |      |      |
__|__   _|_     |

  A      B      C
  |      |      |
  |      |      |
  |     _|_   __|__

  A      B      C
  |      |      |
  |      |     _|_
  |      |    __|__

```

# Challenge

There are three rods called A,B and C. (You can also call them 1,2 and 3 respectivly if that helps) In the beginning all n discs are on rod A(1).

Your challenge is to verify a solution for the tower of hanoi. You'll need to make sure that:

1. In the end all n discs are on rod C(3).
2. For any given disc at any given state there is no smaller disc below it.
3. No obvious errors like trying to take discs from an empty rod or moving discs to nonexistant rods.

(the solution does not have to be optimal.)

# Input

Your program will receive two inputs:

1. The number of discs n (an integer)
2. The moves which are taken, which will consist of a set of tuples of: (tower to take the currently uppermost disc from),(tower to take this disc to) where each tuple refers to a move. You can choose how they are represented. For example something like the following ways of representing the solution for n=2 which I've drawn in ascii above. (I'll use the first one in the test cases, because it's easy on the eyes):

"A-\>B ; A-\>C ; B-\>C"

\[("A","B"),("A","C"),("B","C")\]

\[(1,2),(1,3),(2,3)\]

"ABACBC"

\[1,2,1,3,2,3\]

# Output

* Truthy, if the conditions that can be found under "challenge" hold.
* Falsy, if they don't.

# Test cases:

### True:

```
n=1, "A->C"

n=1, "A->B ; B->C"

n=2, "A->B ; A->C ; B->C"

n=2, "A->C ; C->B ; A->C ; B->C"

n=2, "A->C ; A->B ; C->B ; B->A ; B->C ; A->C"

n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C ; B->C"

```

### False:

*3rd one suggested by @MartinEnder, 7th by @Joffan*

```
n=1, "A->B"

n=1, "C->A"

n=2, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

n=2, "A->B ; A->C ; C->B"

n=2, "A->C ; A->B ; C->B ; B->A"

n=2, "A->C ; A->C"

n=3, "A->B ; A->D; A->C ; D->C ; A->C"

n=3, "A->C ; A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

n=3, "A->C ; A->B ; C->B ; A->B ; B->C ; B->A ; B->C ; A->C"

n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; C->B"

n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C"

n=4, "A->B ; A->B ; A->B ; A->C ; B->C ; B->C ; B->C"

```

This is code-golf, shortest solution wins. Standard rules and loopholes apply. No batteries included.

# Answer
# Retina, ~~84~~ 80 Bytes

<sup>-5 bytes thanks to Martin Ender</sup>

```
~
 ~$'
$
ABC
{`^(.)(.*)( ~+)\1
$3$2$1
}`^(\W+)(\w)(.*)(?<=\1~+|\w)\2
$3$1$2
^AB

```

Try it online! (plus 5 bytes for line-by-line tests)

The code simulates a full game.

* Input is given as `ACABCBACBABCAC~~~`.
`~~~` means three discs.
* First four lines convert the input to the game format: `ACABCBACBABCAC ~~~ ~~ ~ABC`.
In the beginning the A rod has all 3 discs, and B and C rods are empty.
* Next we have a loop of two steps:
    + Take the first letter in the line, which indicates the next source rod. Find this rod, and take the last disc on in. Remove the letter and move the disc to the stark (pick it up).
    In out example, after the first step, the text will look like: `~CABCBACBABCAC ~~~ ~~ABC`.
    + In the second stage we find the target rod, and move the disc there. We validate the rod is empty, or has a bigger disc at the top: `ABCBACBABCAC ~~~ ~~AB ~C`.
* Finally we confirm the A and B rods are empty - this means all discs are in C (there's an extra space at the last line).
> 7 votes

# Answer
## Retina, ~~167~~ ~~165~~ ~~157~~ ~~150~~ 123 bytes

This totally looks like a challenge that should be solved with a single regex... (despite the header saying "Retina", this is just a vanilla .NET regex, matching valid inputs).

```
^(?=\D*((?=(?<3>1+))1)+)((?=A(?<1-3>.+)|B(?<1-4>.+)|C(?<1-5>.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?!\3|\4)1

```

Input format is the list of instructions of the form `AB`, followed by `n` in unary using the digit `1`. There are no separators. Output is `1` for valid and `0` for invalid.

Try it online! (The first two characters enable a linefeed-separated test suite.)

Alternative solution, same byte count:

```
^(?=\D*((?=(?<3>1+))1)+)((?=A(?<1-3>.+)|B(?<1-4>.+)|C(?<1-5>.+)).(?=A.*(?!\3)(\1)|B.*(?!\4)(\1)|C.*(?!\5)(\1)).)+(?<-5>1)+$

```

This can possibly be shortened by using `1`, `11` and `111` instead of `A`, `B` and `C` but I'll have to look into that later. It might also be shorter to split the program into several stages, but where's the challenge in that? ;)

### Explanation

This solution makes heavy use of .NET's balancing groups. For a full explanation see my post on Stack Overflow, but the gist is that capturing groups in .NET are stacks, where each new capture pushes another substring and where it's also possible to pop from such a stack again. This lets you count various quantities in a string. In this case it lets us implement the three rods directly as three different capturing groups where each disc is represented by a capture.

To move discs around between rods we make use of a weird quirk of the `(?<A-B>...)` syntax. Normally, this pops a capture from stack `B` and pushes onto stack `A` the string between that popped capture and the beginning of this group. So `(?<A>a).(?<B-A>c)` matched against `abc` would leave `A` empty and `B` with `b` (as opposed to `c`). However, due to .NET variable-length lookbehinds it's possible for the captures of `(?<A>...)` and `(?<B-A>...)` to overlap. For whatever reason, if that's the case, the *intersection* of the two groups is pushed onto `B`. I've detailed this behaviour in the "advanced section" on balancing groups in this answer.

On to the regex. Rods `A`, `B` and `C` correspond to groups `3`, `4` and `5` in the regex. Let's start by initialising rod `A`:

```
^                 # Ensure that we start at the beginning of the input.
(?=               # Lookahead so that we don't actually move the cursor.
  \D*             # Skip all the instructions by matching non-digit characters.
  (               # For each 1 at the end of the input...
    (?=(?<3>1+))  # ...push the remainder of the string (including that 1)
                  # onto stack 3.
  1)+
)

```

So e.g. if the input ends with `111`, then group 3/rod `A` will now hold the list of captures `[111, 11, 1]` (the top being on the right).

The next bit of the code has the following structure:

```
(
  (?=A...|B...|C...).
  (?=A...|B...|C...).
)+

```

Each iteration of this loop processes one instruction. The first alternation pulls a disc from the given rod (onto a temporary group), the second alternation puts that that disc onto the other given rod. We'll see in a moment how this works and how we ensure that the move is valid.

First, taking a disc off the source rod:

```
(?=
  A(?<1-3>.+)
|
  B(?<1-4>.+)
|
  C(?<1-5>.+)
)

```

This uses the weird group-intersection behaviour I've described above. Note that group `3`, `4` and `5` will always hold substrings of `1`s at the end of the string whose length corresponds to the disc's size. We now use `(?<1-N>.+)` to pop the top disc off stack `N` and push the intersection of this substring with the match `.+` onto stack `1`. Since `.+` always necessarily covers the entire capture popped off `N`, we know that this simply moves the capture.

Next, we put this disc from stack `1` onto the stack corresponding to the second rod:

```
(?=
  A.*(?!\3)(\1)
|
  B.*(?!\4)(\1)
|
  C.*(?!\5)(\1)
)

```

Note that we don't have to clean up stack `1`, we can just leave the disc there, since we'll put a new one on top before using the stack again. That means we can avoid the `(?<A-B>...)` syntax and simply copy the string over with `(\1)`. To ensure that the move is valid we use the negative lookahead `(?!\N)`. This ensures that, from the position where we want to match the current disc, it's impossible to match the disc already on stack `N`. This can only happen if either a) `\N` will never match because the stack is completely empty or b)`the disc on top of stack`N`is larger than the one we're trying to match with`\1\`.

Finally, all that's left is ensuring that a) we've matched all instructions and b) rods `A` and `B` are empty, so that all discs have been moved onto `C`.

```
(?!\3|\4)1

```

We simply check that neither `\3` nor `\4` can match (which is only the case if both are empty, because any actual disc *would* match) and that we can then match a `1` so that we haven't omitted any instructions.
> 17 votes

# Answer
# Java "only" ~~311 272 263 261 260 259~~ 256 bytes

Saved ~~39~~ countless bytes due to @Frozn noticing an older debug feature as well as some clever golfing tricks.

Golfed version

```
int i(int n,int[]m){int j=0,k=0,i=n;Stack<Integer>t,s[]=new Stack[3];for(;j<3;)s[j++]=new Stack();for(;i-->0;)s[0].push(i);for(;k<m.length;k+=2)if((t=s[m[k+1]]).size()>0&&s[m[k]].peek()>t.peek())return 0;else t.push(s[m[k]].pop());return s[2].size()<n?0:1;}

```

ungolfed with explanation and pretty printed stacks at each step

```
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package codegolf;

/**
 *
 * @author rohan
 */
import java.util.Arrays;
import java.util.Stack;
public class CodeGolf {
    //golfed version
    int i(int n,int[]m){int j=0,k=0,i=n;Stack<Integer>[] s=new Stack[3];for(;j<3;j++)s[j]=new Stack();for(;i-->0;)s[0].push(i);for(;k<m.length;System.out.println(Arrays.toString(s)),k+=2)if(!s[m[k+1]].isEmpty()&&s[m[k]].peek()>s[m[k+1]].peek())return 0;else s[m[k+1]].push(s[m[k]].pop());return s[2].size()==n?1:0;}
    /** Ungolfed
        * 0 as falsy 1 as truthy
        * @param n the number of disks
        * @param m represents the zero indexed stacks in the form of [from,to,from,to]
        * @return 0 or 1 if the puzzle got solved, bad moves result in an exception
        */
    int h(int n, int[] m) {
        //declarations
        int j = 0, k = 0, i = n;
        //create the poles
        Stack<Integer>[] s = new Stack[3];
        for (; j < 3; j++) {
            s[j] = new Stack();
        }
        //set up the first tower using the "downto operator
        for (; i-- > 0;) {
            s[0].push(i);
        }
    //go through and perform all the moves
        for (; k < m.length; System.out.println(Arrays.toString(s)), k += 2) {
            if (!s[m[k + 1]].isEmpty() && s[m[k]].peek() > s[m[k + 1]].peek()) {
                return 0;//bad move
            } else {
                s[m[k + 1]].push(s[m[k]].pop());
            }
        }
        return s[2].size() == n ? 1 : 0;// check if all the disks are done
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
    //test case
        System.out.println( new CodeGolf().h(3,new int[]{0,2,0,1,2,1,0,2,1,0,1,2,0,2})==1?"Good!":"Bad!");
    }

}

```

The ungolfed version has a feature where it will print out what the stacks look like at each step like so...

```
[[2, 1], [], [0]]
[[2], [1], [0]]
[[2], [1, 0], []]
[[], [1, 0], [2]]
[[0], [1], [2]]
[[0], [], [2, 1]]
[[], [], [2, 1, 0]]
Good!

```
> 14 votes

# Answer
# Python 2, ~~186~~ ~~167~~ ~~158~~ ~~135~~ ~~127~~ ~~115~~ ~~110~~ 102 bytes

```
n,m=input()
x=[range(n),[],[]]
for a,b in m:p=x[a].pop();e=x[b];e and 1/(p>e[-1]);e+=p,
if x[0]+x[1]:_

```

Takes input on STDIN in the following format:

```
(1,[(0,1),(1,2)])

```

That is, a Python tuple of the number of discs and a Python list of tuples of `(from_rod,to_rod)`. As in Python, the surrounding parentheses are optional. Rods are zero-indexed.

For example, this test case:

```
n=2; "A->B ; A->C ; B->C"

```

would be given as:

```
(2,[(0,1),(0,2),(1,2)])

```

If the solution is valid, outputs nothing and exits with an exit code of 0. If it is invalid, throws an exception and exits with an exit code of 1. Throws an `IndexError` if moving to a nonexistant rod or trying to take a disc off a rod that has no discs on it, a `ZeroDivisionError` if a disc is placed on top of a smaller disc, or a `NameError` if there are discs left on the first or second rods at the end.

*Saved 13 bytes thanks to @KarlKastor!*

*Saved 8 bytes thanks to @xnor!*
> 9 votes

# Answer
# VBA, ~~234~~ ~~217~~ ~~213~~ 196 bytes

```
Function H(N,S)
ReDim A(N)
While P<Len(S)
P=P+2:F=1*Mid(S,P-1,1):T=1*Mid(S,P,1)
E=E+(T>2):L=L+T-F
For i=1 To N
If A(i)=F Then A(i)=T:Exit For
E=E+(A(i)=T)+(i=N)
Next
Wend
H=L+9*E=2*N
End Function

```

Input format for moves is a string with an even number of digits (012). Invocation is in spreadsheet, =H(\[number of discs\], \[move string\])

The array A holds the rod position of the various discs. A move is simply updating the first occurrence of the "From" rod number into the "To" rod number. If you encounter a "To" rod disc first, or no "From" rod disc, it's an invalid move. The total "rod value" of A is held in L, which needs to end at 2N. Errors are accumulated as a negative count in E.

In common with other solutions, "moving" a disc from a tower to the same tower is not forbidden. I could forbid it for another 6 bytes.

## Results

Function result in first column (the last n=3 case is my addition using an extra rod).

```
TRUE    1   02
TRUE    1   0112
TRUE    2   010212
TRUE    2   02210212
TRUE    2   020121101202
TRUE    3   02012102101202
TRUE    4   010212012021010212102012010212

FALSE   1   01
FALSE   1   20
FALSE   2   02012102101202
FALSE   2   010221
FALSE   2   02012110
FALSE   2   0202
FALSE   3   0202012102101202
FALSE   3   0201210112101202
FALSE   3   02012102101221
FALSE   3   0103023212
FALSE   4   0102120120210102121020120102
FALSE   4   01010102121212

```
> 5 votes

# Answer
# Python 2.7, ~~173~~ ~~158~~ ~~138~~ ~~130~~ ~~127~~ 123 bytes:

```
r=range;a,b=input();U=[r(a,0,-1),[],[]]
for K,J in b:U[J]+=[U[K].pop()]if U[J]<[1]or U[K]<U[J]else Y
print U[-1]==r(a,0,-1)

```

Takes input through the stdin in the format `(<Number of Discs>,<Moves>)` where `<Moves>` is given as an array containing tuples corresponding to each move, which each contain a pair of comma separated integers. For instance, the test case:

```
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"

```

given in the post would be given as:

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

```

to my program. Outputs an `IndexError` if the 3rd condition isn't met, a `NameError` if the 2nd condition isn't met, and `False` if the 1st condition isn't met. Otherwise outputs `True`.
> 5 votes

# Answer
# php, 141 bytes

```
<?php $a=$argv;for($t=[$f=range($a[++$i],1),[],[]];($r=array_pop($t[$a[++$i]]))&&$r<(end($t[$a[++$i]])?:$r+1);)$t[$a[$i]][]=$r;echo$t[2]==$f;

```

Command line script, takes input as the height then a series of array indexes (0 indexed) e.g. 1 0 2 or 2 0 1 0 2 1 2 for the 1 or 2 height shortest test cases.
Echos 1 on true cases and nothing on false ones.
Gives 2 notices and 1 warning so needs to be run in an environment that silences those.
> 2 votes

# Answer
# JavaScript (ES6), 108

```
n=>s=>!s.some(([x,y])=>s[y][s[y].push(v=s[x].pop())-2]<v|!v,s=[[...Array(s=n)].map(_=>s--),[],[]])&s[2][n-1]

```

**Input format:** function with 2 arguments

* arg 1, numeric, number of rings
* arg 2, array of strings, each string 2 characters '0','1','2'

**Output:** return 1 if ok, 0 if invalid, exception if nonexisting rod

**Less golfed** and explained

```
n=>a=>(
  // rods status, rod 0 full with an array n..1, rod 1 & 2 empty arrays
  s = [ [...Array(t=n)].map(_=>t--), [], [] ],
  // for each step in solution, evaluate function and stop if returns true
  err = a.some( ([x,y]) => {
    v = s[x].pop(); // pull disc from source rod
    // exception is s[x] is not defined
    if (!v) return 1; // error source rod is empty
    l = s[y].push(v); // push disc on dest rod, get number of discs in l
    // exception is s[y] is not defined
    if(s[y][l-2] < v) return 1; // error if undelying disc is smaller
  }),
  err ? 0 // return 0 if invalid move
  : s[2][n-1]; // il all moves valid, ok if the rod 2 has all the discs
)

```

**Test** Note: the first row of the Test function is needed to convert the input format given in the question to the input expected by my function

```
F=
n=>s=>!s.some(([x,y])=>s[y][s[y].push(v=s[x].pop())-2]<v|!v,s=[[...Array(s=n)].map(_=>s--),[],[]])&s[2][n-1]

Out=x=>O.textContent+=x+'\n'

Test=s=>s.split`\n`.map(r=>[+(r=r.match(/\d+|.->./g)).shift(),r.map(x=>(parseInt(x[0],36)-10)+''+(parseInt(x[3],36)-10))])
.forEach(([n,s],i)=>{
  var r
  try {
    r = F(+n)(s);
  }
  catch (e) {
    r = 'Error invalid rod';
  }
  Out(++i+' n:'+n+' '+s+' -> '+r)
})

Out('OK')
Test(`n=1, "A->C"
n=1, "A->B ; B->C"
n=2, "A->B ; A->C ; B->C"
n=2, "A->C ; C->B ; A->C ; B->C"
n=2, "A->C ; A->B ; C->B ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C ; B->C"`)

Out('\nFail')
Test( `n=1, "A->B"
n=1, "C->A"
n=2, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=2, "A->B ; A->C ; C->B"
n=2, "A->C ; A->B ; C->B ; B->A"
n=2, "A->C ; A->C"
n=3, "A->B ; A->D; A->C ; D->C ; A->C"
n=3, "A->C ; A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->B ; B->C ; B->A ; B->C ; A->C"
n=3, "A->C ; A->B ; C->B ; A->C ; B->A ; B->C ; C->B"
n=4, "A->B ; A->C ; B->C ; A->B ; C->A ; C->B ; A->B ; A->C ; B->C ; B->A ; C->A ; B->C ; A->B ; A->C"
n=4, "A->B ; A->B ; A->B ; A->C ; B->C ; B->C ; B->C"`)
```

```
<pre id=O></pre>
```
> 1 votes

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


title: Guard your can with your life!

text:
# Question
Title: Guard your can with your life!
# Lets Play Kick The Can!

## Although Moogie is the current winner, if anyone can take his crown they are encouraged to do so

Kick the can is a children's game. Involving one defender, and multiple attackers. Today it is no longer such a game! Your job is to write a bot that plays it, to win, style!

https://en.wikipedia.org/wiki/Kick\_the\_can

There are some key differences in this game. The first key difference is that the game is multiplayer (5v5). The second key difference is that both sets of bots can kill and eliminate enemy players with both mines and thrown bombs! Bots can not see any mines (regardless of distance) or players at greater than five blocks away!

The map is a maze as follows.

This maze is procedurally generated by first creating a maze using a depth first recursive backtracking algorithm. And then placing the shown holes in (as well as make the maze more "imperfect". The maze is 65x65 blocks wide, and zero indexed. Thus the blue flag (can) is at 1,1 and the red flag (can) is at 63,63. Blue team spawns at 2,2 and 3,3 4,4 etc. red team spawns at 62,62 and 61,61, 60,60 etc. The blocks in cyan are bots on the blue team, and the blocks in magenta are red bots. The game is always five versus five. Each bot on the team will use your code (but may store other instance variables (or create local files) to keep track of state and differentiate roles.

---

## Gameplay

Mines can be placed as you can see in gray. And bombs can be thrown a maximum distance of up to four blocks. These travel for up to four blocks through walls and other players killing only the enemies which stand in your way. After each step they have a 40% chance of falling away. So they have 100% chance of 1 range 60% at 2 range 36% at 3 range and 21.6% at three range Placing a mine or throwing a bomb takes one team ammo. This starts at 0 and can be increased by collecting the orange boxes. Note that four (4) of these ammo caches will be conveniently centered. The Bots are lined up in an array of two red and two blue. I.E RRRRRBBBBB. Gaurding the flag is permitted, but beware that being near the flag(i.e less than five blocks) results in slowness, and only allows movent. every three turns. The Arena picks a random starter for each turn. I.E The order can be RBBBBBRRRRR BBBBBRRRRR BBBRRRRRBB etc..

## Objective

Program your five bots (each has the same class file) to successfully navigate the maze and touch the opposing can while being careful not to accidentally knock over ones own can, or step on a mine.

## Programming

The arena and bot entries are currently in Java however a stdin/out wrapper exists for other languages.

The arena code will be made available but here is the relevant details.

### Bot Class

```
public class YourUniqueBotName extends Bot{
public YourUniqueBotName(int x , int y, int team){
super(x,y,team);
//optional code
}
public Move move(){//todo implement this method
//it should output  a Move();
//A move has two paramaters
//direction is from 0 - 3 as such
//         3
//       2-I-0
//         1
// a direction of 4 or higher means a no-op (i.e stay still)
//And a MoveType. This movetype can be
//MoveType.Throw
//MoveType.Mine
//MoveType.Defuse defuse any mine present in the direction given
//MoveType.Move
}
}

```

### Key Methods Available

Note that using any techniques to modify or access data you should generally not have access to is not permitted and will result in disqualification.

```
Arena.getAmmo()[team];//returns the shared ammo cache of your team

Arena.getMap();//returns an integer[] representing the map. Be careful since all enemies more than 5 blocks away (straight line distance) and all mines are replaced with constant for spaces
//constants for each block type are provided such as Bot.space Bot.wall Bot.mine Bot.redTeam Bot.blueTeam Bot.redFlag Bot.blueFlag

Arena.getAliveBots();//returns the number of bots left

getX();//returns a zero indexed x coordinate you may directly look at (but not change X)

getY();//returns a zero indexed y coordinate (y would work to, but do not change y's value)

//Although some state variables are public please do not cheat by accessing modifying these

```

### StdIn/Out wrapper Interface Specification

The interface consists of two modes: initialisation and running.

During initialisation mode, a single INIT frame is sent via stdout. This frame's specification is as follows:

```
INIT
{Team Membership Id}
{Game Map}
TINI

```

Where: {Team Membership Id} is an single character: R or B. B meaning blue team, R meaning red team.

{Game Map} is a series of rows of ascii characters representing one row of the map. The following ascii characters are valid: F = blue flag G = red flag O = open space W = wall

The game will then proceed to send game frames over stdout to each bot as so:

```
FRAME
{Ammo}
{Alive Bot Count}
{Bot X},{Bot Y}
{Local Map}
EMARF

```

Where:

{Ammo} is a string of digits, value will be 0 or greater {Alive Bot Count} is a string of digits, value will be 0 or greater {Box X} is a string of digits representing the X co-ordinate of the bot on the game map. Value will be 0 \<= X \< Map Width. {Box Y} is a string of digits representing the Y co-ordinate of the bot on the game map. Value will be 0 \<= Y \< Map Height. {Local Map} is a series of rows of ascii characters representing the whole map surrounding the bot. The following ascii characters are valid: F = blue flag G = red flag O = open space W = wall R = red team bot B = blue team bot M = mine A = ammo

The Controller expects that your bot will then output (to stdout) a single line response in the format:

```
{Action},{Direction}

```

Where:

{Action} is one of: Move Defuse Mine Throw

{Direction} is a single digit between 0 and 4 inclusive. (see direction information earlier)

NOTE: all strings will be delimited by \n End of Line character.

This will be an elimination tournament. My sample bots will participate as fillers, but I will not award myself the win. In the event of a victory by one of my bots, the title goes to the second place member, and will continue until there is a bot which is not one of mine. Each match consists of 11 rounds of kick the can. If neither team has won a single match by then they both are eliminated. If there is a tie of non-zero score one tie breaker match will be played. If a tie remains both are eliminated. Later rounds may consist of more matches. The seeding of the tournament will be based on the number of upvotes as of 7/31/16 (date subject to change).

Each match lasts 4096 turns. A victory grants one point. A tie or loss grants zero points. Good luck!

Feel free to look at the code or critique it at this GitHub Repo.

https://github.com/rjhunjhunwala/BotCTF/blob/master/src/botctf/Arena.java

---

Note that I do not have interpreters for too many languages on my computer, and I may need volunteers to run the simulation on their computer. Or I can download the language interpreter. Please ensure that your bots.

* Respond in a reasonable amount of time (say 250 ms)
* Will not damage my host machine

# Answer
# NavPointBot, Java 8

Bot is white/blue

This bot nominates a leader from friendly bots each frame that will then assign nav points for each bot to navigate to.

Initally, all bots are on ammo depot finding duty, then two bots are assigned as guards with the remainder looking for ammo and then attacking the enemy flag.

I have found that the game is very dependant on the starting location of depots. As such i cannot really say that this bot is better than any others.

Run with `java NavPointBot`

```
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.UUID;

public final class NavPointBot implements Serializable
{
    private static final int[][] offsets = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};
    private static final List<int[]> navPointsBlue = Arrays.asList(new int[][]{{1,2},{2,1}});
    private static final List<int[]> navPointsRed = Arrays.asList(new int[][]{{63,62},{62,63}});
    transient private static int mapWidth=0;
    transient private static int mapHeight=0;
    transient private char[][] map;
    transient private char team;
    transient private int ammo;
    transient private int botsAlive;
    transient private int enemyFlagX;
    transient private int enemyFlagY;
    private int frameCount;
    private int botX;
    private int botY;
    private String id;
    private int navPointX;
    private int navPointY;

    transient static Object synchObject = new Object(); // used for file read/write synchronisation if multiple instances are run in the same VM

    final static class Data implements Serializable
    {
        int frameCount;
        boolean[][] diffusedMap = new boolean[mapWidth][mapHeight];
        Map<String,NavPointBot> teamMembers = new HashMap<>();
    }

    interface DistanceWeigher
    {
        double applyWeight(NavPointBot p1Bot, PathSegment p1);
    }

    static class PathSegment
    {
        public PathSegment(int tileX, int tileY, int fscore, int gscore, PathSegment parent, int direction, int targetX, int targetY)
        {
            super();
            this.tileX = tileX;
            this.tileY = tileY;
            this.fscore = fscore;
            this.gscore = gscore;
            this.parent = parent;
            this.direction = direction;
            this.targetX = targetX;
            this.targetY = targetY;
        }
        public PathSegment(PathSegment parent)
        {
            this.parent = parent;
            this.targetX = parent.targetX;
            this.targetY = parent.targetY;
        }
        int tileX;
        int tileY;
        int fscore;
        int gscore;
        int direction;
        PathSegment parent;
        int targetX;
        int targetY;
    }

    public static void main(String[] args) throws Exception
    {
        new NavPointBot(UUID.randomUUID().toString());
    }

    private NavPointBot(String id) throws Exception
    {
        this.id = id;
        System.err.println("NavPointBot ("+id+") STARTED");

        Data data;
        while(true)
        {
            String line=readLine(System.in);

            // decode initial frame
            if ("INIT".equals(line))
            {
                // read team membership
                team = readLine(System.in).charAt(0);

                // get the map
                line = readLine(System.in);

                List<char[]> mapLines = new ArrayList<>();
                while(!"TINI".equals(line))
                {
                    mapLines.add(line.toCharArray());
                    line = readLine(System.in);
                }
                map = mapLines.toArray(new char[][]{});
                mapHeight = map.length;
                mapWidth = map[0].length;

                out:
                for (int y = 0; y<mapHeight;y++)
                {
                    for (int x=0; x<mapWidth;x++)
                    {
                        if (map[y][x]==(team=='B'?'G':'F'))
                        {
                            enemyFlagX = x;
                            enemyFlagY = y;
                            break out;
                        }
                    }
                }
                data = readSharedData();
                data.diffusedMap=new boolean[mapWidth][mapHeight];
                writeSharedData(data);

            }
            else
            {
                System.err.println("Unknown command received: "+line);
                return;
            }

            line = readLine(System.in);
            while (true)
            {
                // decode frame
                if ("FRAME".equals(line))
                {
                    frameCount = Integer.parseInt(readLine(System.in));
                    ammo = Integer.parseInt(readLine(System.in));
                    botsAlive = Integer.parseInt(readLine(System.in));
                    line = readLine(System.in);
                    String[] splits = line.split(",");
                    botX = Integer.parseInt(splits[0]);
                    botY = Integer.parseInt(splits[1]);

                    // get the map
                    line = readLine(System.in);

                    int row=0;
                    while(!"EMARF".equals(line))
                    {
                        map[row++] = line.toCharArray();
                        line = readLine(System.in);
                    }
                }
                else
                {
                    System.err.println("Unknown command received: "+line);
                    return;
                }

                data = readSharedData();

                // this bot is nomitated to be the leader for this frame
                if (data.frameCount<frameCount || (frameCount==0 && data.frameCount > 3))
                {
                    data.frameCount=frameCount;

                    List<NavPointBot> unassignedBots = new ArrayList<>(data.teamMembers.values());

                    // default nav points to be enemy flag location.
                    unassignedBots.forEach(t->{t.navPointY=enemyFlagY;t.navPointX=enemyFlagX;});

                    // after 700 frames assume dead lock so just storm the flag, otherwise...
                    if (frameCount<700)
                    {
                        // if the after the initial rush then we will assign guard(s) while we have enemies
                        if (frameCount>70 && botsAlive > data.teamMembers.size())
                        {
                            Map<NavPointBot, PathSegment> navPointDistances = assignBotShortestPaths(unassignedBots,team=='B'?navPointsBlue:navPointsRed,true, new DistanceWeigher() {

                                @Override
                                public double applyWeight( NavPointBot owner ,PathSegment target) {
                                    return target.gscore;
                                }
                            });
                            navPointDistances.keySet().forEach(s->{s.navPointX=navPointDistances.get(s).targetX;s.navPointY=navPointDistances.get(s).targetY;});
                        }

                        // the remaining bots will go to ammo depots with a preference to the middle ammo depots
                        List<int[]> ammoDepots = new ArrayList<>();
                        for (int y = 0; y<mapHeight;y++)
                        {
                            for (int x=0; x<mapWidth;x++)
                            {
                                if (map[y][x]=='A')
                                {
                                    ammoDepots.add(new int[]{x,y});
                                }
                            }
                        }

                        System.err.println("ammoDepots: "+ammoDepots.size());
                        if (ammoDepots.size()>0)
                        {
                            Map<NavPointBot, PathSegment> ammoDistances = assignBotShortestPaths(unassignedBots,ammoDepots,true, new DistanceWeigher() {

                                @Override
                                public double applyWeight( NavPointBot owner ,PathSegment target) {
                                    return target.gscore + (Math.abs(target.targetX-mapWidth/2)+Math.abs(target.targetY-mapHeight/2)*10);
                                }
                            });

                            // assign ammo depot nav points to closest bots
                            ammoDistances.keySet().forEach(s->{s.navPointX=ammoDistances.get(s).targetX;s.navPointY=ammoDistances.get(s).targetY;});
                        }
                    }

                    System.err.println("FRAME: "+frameCount+" SET");
                    data.teamMembers.values().forEach(bot->System.err.println(bot.id+" nav point ("+bot.navPointX+","+bot.navPointY+")"));
                    System.err.println();
                }

                // check to see if enemies are in range, if so attack the closest
                List<int[]> enemies = new ArrayList<>();
                for (int y = 0; y<mapHeight;y++)
                {
                    for (int x=0; x<mapWidth;x++)
                    {
                        if (map[y][x]==(team=='B'?'R':'B'))
                        {
                            int attackDir = -1;
                            int distance = -1;
                            if (x==botX && Math.abs(y-botY) < 4) { distance =  Math.abs(y-botY); attackDir = botY-y<0?1:3;}
                            if (y==botY && Math.abs(x-botX) < 4) { distance =  Math.abs(x-botX); attackDir = botX-x<0?0:2;}
                            if (attackDir>-1)
                            {
                                enemies.add(new int[]{x,y,distance,attackDir});
                            }
                        }
                    }
                }

                enemies.sort(new Comparator<int[]>() {

                    @Override
                    public int compare(int[] arg0, int[] arg1) {
                        return arg0[2]-arg1[2];
                    }
                });

                String action;

                // attack enemy if one within range...
                if (enemies.size()>0)
                {
                    action = "Throw,"+enemies.get(0)[3];
                }
                else
                {
                    // set action to move to navpoint
                    PathSegment pathSegment = pathFind(botX,botY,navPointX,navPointY,map,true);
                    action = "Move,"+pathSegment.direction;

                    // clear mines if within 5 spaces of enemy flag

                    if ((team=='B' && botX>=mapWidth-5 && botY>=mapHeight-5 ) ||
                        (team=='R' && botX<5 && botY<5 ))
                    {
                        if (!data.diffusedMap[pathSegment.parent.tileX][pathSegment.parent.tileY])
                        {
                            action = "Defuse,"+pathSegment.direction;
                            data.diffusedMap[pathSegment.parent.tileX][pathSegment.parent.tileY]=true;
                        }
                    }

                }

                writeSharedData(data);
                System.out.println(action);
                line = readLine(System.in);
            }
        }
    }

    /**
     * assigns bots to paths to the given points based on distance to the points with weights adjusted by the given weigher implementation
     */
    private Map<NavPointBot, PathSegment> assignBotShortestPaths(List<NavPointBot> bots, List<int[]> points, boolean exact, DistanceWeigher weigher) {

        Map<Integer,List<PathSegment>> pathMap = new HashMap<>();
        final Map<PathSegment,NavPointBot> pathOwnerMap = new HashMap<>();

        for (NavPointBot bot : bots)
        {
            for(int[] navPoint: points)
            {
                List<PathSegment> navPointPaths = pathMap.get((navPoint[0]<<8)+navPoint[1]);
                if (navPointPaths == null)
                {
                    navPointPaths = new ArrayList<>();
                    pathMap.put((navPoint[0]<<8)+navPoint[1],navPointPaths);
                }
                PathSegment path = pathFind(bot.botX,bot.botY,navPoint[0],navPoint[1],map,exact);
                pathOwnerMap.put(path, bot);
                navPointPaths.add(path);
            }
        }

        // assign bot nav point based on shortest distance
        Map<NavPointBot, PathSegment> results = new HashMap<>();
        for (int[] navPoint: points )
        {
            List<PathSegment> navPointPaths = pathMap.get((navPoint[0]<<8)+navPoint[1]);

            if (navPointPaths !=null)
            {
                Collections.sort(navPointPaths, new Comparator<PathSegment>() {

                    @Override
                    public int compare(PathSegment p1, PathSegment p2) {

                        NavPointBot p1Bot = pathOwnerMap.get(p1);
                        NavPointBot p2Bot = pathOwnerMap.get(p2);
                        double val = weigher.applyWeight(p1Bot, p1) - weigher.applyWeight(p2Bot, p2);
                        if (val == 0)
                        {

                            return p1Bot.id.compareTo(p2Bot.id);
                        }
                        return val<0?-1:1;
                    }
                });

                for (PathSegment shortestPath : navPointPaths)
                {
                    NavPointBot bot = pathOwnerMap.get(shortestPath);

                    if (!results.containsKey(bot) )
                    {
                        results.put(bot,shortestPath);
                        bots.remove(bot);
                        break;
                    }
                }
            }
        }
        return results;
    }

    /**
     * reads in the previous bot's view of teammates aka shared data
     */
    private Data readSharedData() throws Exception
    {
        synchronized(synchObject)
        {
            File dataFile = new File(this.getClass().getName()+"_"+team);

            Data data;
            if (dataFile.exists())
            {
                FileInputStream in = new FileInputStream(dataFile);
                try {
                    java.nio.channels.FileLock lock = in.getChannel().lock(0L, Long.MAX_VALUE, true);
                    try {
                        ObjectInputStream ois = new ObjectInputStream(in);
                        data = (Data) ois.readObject();
                    } catch(Exception e)
                    {
                        System.err.println(id+": CORRUPT shared Data... re-initialising");
                        data = new Data();
                    }
                    finally {
                        lock.release();
                    }
                } finally {
                    in.close();
                }
            }
            else
            {
                System.err.println(id+": No shared shared Data exists... initialising");
                data = new Data();
            }

            //purge any dead teammates...
            for (NavPointBot bot : new ArrayList<>(data.teamMembers.values()))
            {
                if (bot.frameCount < frameCount-3 || bot.frameCount > frameCount+3)
                {
                    data.teamMembers.remove(bot.id);
                }
            }

            // update our local goals to reflect those in the shared data
            NavPointBot dataBot = data.teamMembers.get(id);
            if (dataBot !=null)
            {
                this.navPointX=dataBot.navPointX;
                this.navPointY=dataBot.navPointY;
            }

            // ensure that we are a team member
            data.teamMembers.put(id, this);

            return data;
        }
    }

    private void writeSharedData(Data data) throws Exception
    {
        synchronized(synchObject)
        {
            File dataFile = new File(this.getClass().getName()+"_"+team);
            FileOutputStream out = new FileOutputStream(dataFile);

            try {
                java.nio.channels.FileLock lock = out.getChannel().lock(0L, Long.MAX_VALUE, false);
                try {
                    ObjectOutputStream oos = new ObjectOutputStream(out);
                    oos.writeObject(data);
                    oos.flush();
                } finally {
                    lock.release();
                }
            } finally {
                out.close();
            }
        }
    }

    /**
     * return the direction to move to travel for the shortest route to the desired target location
     */
    private PathSegment pathFind(int startX, int startY, int targetX,int targetY,char[][] map,boolean exact)
    {
        // A*
        if (startX==targetX && startY==targetY)
        {
            return new PathSegment(targetX,targetY,0, 0,null,4,targetX,targetY);//PathSegment.DEFAULT;
        }
        else
        {
            int[][] tileIsClosed = new int[mapWidth][mapHeight];

            // find an open space in the general vicinity if exact match not required
            if (!exact)
            {
                out:
                for (int y=-1;y<=1;y++)
                {
                    for (int x=-1;x<=1;x++)
                    {
                        if (startX == targetX+x && startY==targetY+y)
                        {
                            return new PathSegment(targetX,targetY,0, 0,null,4,targetX,targetY);//PathSegment.DEFAULT;
                        }
                        else if (targetY+y>=0 && targetY+y<mapHeight && targetX+x>=0 && targetX+x < mapWidth && map[targetY+y][targetX+x]=='O')
                        {
                            targetX+=x;
                            targetY+=y;
                            break out;
                        }
                    }
                }
            }

            PathSegment curSegment = new PathSegment(targetX,targetY,1,1,null,4,targetX,targetY);
            PathSegment newSegment;
            Set<PathSegment> openList = new HashSet<PathSegment>();
            openList.add(curSegment);

            do
            {
                if (openList.isEmpty())
                {
                    break;
                }
              PathSegment currentBestScoringSegment = openList.iterator().next();
              //  Look for the lowest F cost square on the open list
              for (PathSegment segment : openList)
              {
                if (segment.fscore<currentBestScoringSegment.fscore)
                {
                  currentBestScoringSegment = segment;
                }
              }
              curSegment = currentBestScoringSegment;

              // found path
              if (startX==curSegment.tileX && startY==curSegment.tileY)
              {
                break;
              }

              // if not in closed list
              if (tileIsClosed[curSegment.tileX][curSegment.tileY]==0)
              {
                    // Switch it to the closed list.
                    tileIsClosed[curSegment.tileX][curSegment.tileY]=1;
                    // remove from openlist
                    openList.remove(curSegment);

                    // add neigbours to the open list if necessary
                    for (int i=0;i<4;i++)
                    {

                        int surroundingCurrentTileX=curSegment.tileX+offsets[i][0];
                        int surroundingCurrentTileY=curSegment.tileY+offsets[i][1];
                        if (surroundingCurrentTileX>=0 && surroundingCurrentTileX<mapWidth &&
                            surroundingCurrentTileY>=0 && surroundingCurrentTileY<mapHeight )
                        {
                            newSegment = new PathSegment( curSegment);
                            newSegment.tileX = surroundingCurrentTileX;
                            newSegment.tileY = surroundingCurrentTileY;
                            newSegment.direction = i;

                            switch(map[surroundingCurrentTileY][surroundingCurrentTileX])
                            {
                                case 'W':
                                case 'F':
                                case 'G':
                                    continue;
                            }

                          int surroundingCurrentGscore=curSegment.gscore+1 + ((surroundingCurrentTileX!=startX && surroundingCurrentTileY!=startY && map[surroundingCurrentTileY][surroundingCurrentTileX]==team)?20:0);//+map[surroundingCurrentTileY][surroundingCurrentTileX]!='O'?100:0;
                          newSegment.gscore=surroundingCurrentGscore;
                          newSegment.fscore=surroundingCurrentGscore+Math.abs( surroundingCurrentTileX-startX)+Math.abs( surroundingCurrentTileY-startY);
                          openList.add(newSegment);
                        }
                    }
              }
              else
              {
                  // remove from openlist
                  openList.remove(curSegment);
              }
            } while(true);

            return curSegment;
        }
     }

    /**
     * Reads a line of text from the input stream. Blocks until a new line character is read.
     * NOTE: This method should be used in favor of BufferedReader.readLine(...) as BufferedReader buffers data before performing
     * text line tokenization. This means that BufferedReader.readLine() will block until many game frames have been received.
     * @param in a InputStream, nominally System.in
     * @return a line of text or null if end of stream.
     * @throws IOException
     */
    private static String readLine(InputStream in) throws IOException
    {
       StringBuilder sb = new StringBuilder();
       int readByte = in.read();
       while (readByte>-1 && readByte!= '\n')
       {
          sb.append((char) readByte);
          readByte = in.read();
       }
       return readByte==-1?null:sb.toString();

    }

}

```
> 4 votes

# Answer
# Optimised Pathfinder JAVA

Thanks to @Moogie for helping me optimise my messy floodfill pathfinding. Here is the source for the bot. This guy knows how important it is to defend his flag. He alocates three defenders and two attackers. The defenders hang back and defend/gather ammo, the two attackers take (a fairly straight) path to the flag (and collect the ammo at the middle). He shoots anyone he sees, and should be fierce competition. The defenders place mines around the flag and camp until there is no opposition left so they can go and kick the can.

```
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 * todo fight
 */
package botctf;

import botctf.Move.MoveType;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 *
 * @author rohan
 */
public class PathFinderOptimised extends Bot {
    private static final int[][] offsets = new int[][]{{0,-1},{1,0},{0,1},{-1,0}};
    public static boolean shouldCampingTroll = true;
    private int moveCounter = -1;//dont ask
    public boolean defend;

    public PathFinderOptimised(int inX, int inY, int inTeam) {

        super(inX, inY, inTeam);
        //System.out.println("Start");
        //floodFillMap(getX(), getY());
        //System.out.println("Finish");
        defend=inX%2==0;
    }
    public static int[][] navigationMap;

    boolean upMine = false;
    boolean sideMine = false;

        int[][] myMap;

    @Override
    public Move move() {
                moveCounter++;
        myMap=getMap();
        int targetX, targetY;
        int enemyTeam=team==redTeam?blueTeam:redTeam;
        ArrayList<Coord> enemyCoordinates=new ArrayList<>();
        for(int i = 0; i<65;i++){
            for(int j = 0;j<65;j++){
                if(map[i][j]==enemyTeam){
                    enemyCoordinates.add(new Coord(i,j));
                }
            }
        }
        for(Coord enemy:enemyCoordinates){
            int enemyX=enemy.x;
            int enemyY=enemy.y;
         int dX= enemy.x-this.x;
            int dY= enemy.y-this.y;
            //System.out.println(dX+"|"+dY);
            if((dX==0||dY==0)){

                if(Arena.getAmmo()[this.team]>0){

                    if(dX>0&&dX<5){
                    return new Move(0,MoveType.Throw);
                }
                if(dX<0&&dX>-5){
                    return new Move(2,MoveType.Throw);
                }
                if (dY>0&&dY<5){
                    return new Move(1, MoveType.Throw);
                }
                if(dY<0&&dY>-5){
                    return new Move(3,MoveType.Throw);
                }
            }
        }
        }
        if(myMap[x+1][y]==ammo){
            return new Move(0,MoveType.Move);
        }
                if(myMap[x-1][y]==ammo){
            return new Move(2,MoveType.Move);
        }
                                if(myMap[x][y+1]==ammo){
            return new Move(1,MoveType.Move);
        }
                                                                if(myMap[x][y-1]==ammo){
            return new Move(3,MoveType.Move);
        }

int bestOption = 4;
        if (defend) {
if(Arena.getAliveBots()==1){
    defend=false;
}
            int bestAmmoX = -1;
            int bestAmmoY = -1;
            int bestAmmoDist = Integer.MAX_VALUE;
            for (int i = 0; i < 65; i++) {
                for (int j = 0; j < 65; j++) {
                    if (myMap[i][j] == ammo) {
                        int path = pathFind(getX(),getY(),i,j,myMap);
                        if ((path & 0xFFFFFF) < bestAmmoDist) {
                            bestAmmoX = i;
                            bestAmmoY = j;
                            bestAmmoDist = (path & 0xFFFFFF);
                            bestOption = path >> 24;
                        }
                    }
                }
            }
            if (bestAmmoDist<15||Arena.getAmmo()[this.team]==0){
                targetX = bestAmmoX;
                targetY = bestAmmoY;
            } else {
                targetX = team == redTeam ? 62 : 2;
                targetY = team == redTeam ? 62 : 2;
            }
        } else {

            if(this.x>18&this.x<42&&this.y>16&&this.y<44&&myMap[33][33]==ammo){
                targetX=33;
                targetY=33;
            }else{
            if (this.team == redTeam) {
                targetX = 1;
                targetY = 1;
            } else {
                targetX = 63;
                targetY = 63;
            }
            }
        }
        if(upMine&&sideMine){
            if(targetX==2||targetX==62){
                if(targetY==2||targetY==62){
                    targetX+=targetX==2?3:-3;
                    targetY+=targetY==2?3:-3;
                }
            }
        }else if (targetX == getX() && targetY == getY()) {
            if (!upMine) {
                upMine = true;
                if (this.team == redTeam) {
                    return new Move(0, MoveType.Mine);
                } else {
                    return new Move(2, MoveType.Mine);
                }
            }else if(!sideMine){
                sideMine=true;
                if (this.team == redTeam) {
                    return new Move(1, MoveType.Mine);
                } else {
                    return new Move(3, MoveType.Mine);
                }
            }   else {
                return new Move(5, MoveType.Move);
            }
        }

        bestOption = pathFind(getX(),getY(),targetX,targetY,myMap) >> 24;

MoveType m=MoveType.Move;
if(moveCounter%2==0){
    if(this.team==redTeam?x<25&&y<25:x>39&&y>39){
        m=MoveType.Defuse;
    }
}
//System.out.println(bestOption);
        return new Move(bestOption, m);
    }

    /**
     * returns a result that is the combination of movement direction and length of a path found from the given start position to the target
     * position. result is ((direction) << 24 + path_length)
     */
    private int pathFind(int startX, int startY, int targetX,int targetY,int[][] map)
    {
        class PathSegment
        {
            public PathSegment(int tileX, int tileY, int fscore, int gscore, PathSegment parent)
            {
                super();
                this.tileX = tileX;
                this.tileY = tileY;
                this.fscore = fscore;
                this.gscore = gscore;
                this.parent = parent;
            }
            public PathSegment(PathSegment parent)
            {
                this.parent = parent;
            }
            int tileX;
            int tileY;
            int fscore;
            int gscore;
            PathSegment parent;
        }
        // A*
        if (startX==targetX && startY==targetY)
        {
            return 4;
        }
        else
        {
            int[][] tileIsClosed = new int[64][64];

            PathSegment curSegment = new PathSegment(targetX,targetY,1,1,null);
            PathSegment newSegment;
            Set<PathSegment> openList = new HashSet<PathSegment>();
            openList.add(curSegment);

            do
            {
                if (openList.isEmpty())
                {
                    break;
                }
              PathSegment currentBestScoringSegment = openList.iterator().next();
              //  Look for the lowest F cost square on the open list
              for (PathSegment segment : openList)
              {
                if (segment.fscore<currentBestScoringSegment.fscore)
                {
                  currentBestScoringSegment = segment;
                }
              }
              curSegment = currentBestScoringSegment;

              // found path
              if (startX==curSegment.tileX && startY==curSegment.tileY)
              {
                break;
              }

              // if not in closed list
              if (tileIsClosed[curSegment.tileX][curSegment.tileY]==0)
              {
                    // Switch it to the closed list.
                    tileIsClosed[curSegment.tileX][curSegment.tileY]=1;
                    // remove from openlist
                    openList.remove(curSegment);

                    // add neigbours to the open list if necessary
                    for (int i=0;i<4;i++)
                    {
                        final int surroundingCurrentTileX=curSegment.tileX+offsets[i][0];
                        final int surroundingCurrentTileY=curSegment.tileY+offsets[i][1];
                        if (surroundingCurrentTileX>=0 && surroundingCurrentTileX<64 &&
                            surroundingCurrentTileY>=0 && surroundingCurrentTileY<64 )
                        {
                            newSegment = new PathSegment( curSegment);
                            newSegment.tileX = surroundingCurrentTileX;
                            newSegment.tileY = surroundingCurrentTileY;

                          if (map[surroundingCurrentTileX][surroundingCurrentTileY]=='W')
                          {
                              continue;
                          }

                          int surroundingCurrentGscore=curSegment.gscore+1;
                          newSegment.gscore=surroundingCurrentGscore;
                          newSegment.fscore=surroundingCurrentGscore+Math.abs( surroundingCurrentTileX-startX)+Math.abs( surroundingCurrentTileY-startY);
                          openList.add(newSegment);
                        }
                    }
              }
              else
              {
                  // remove from openlist
                  openList.remove(curSegment);
              }
            } while(true);

            if (curSegment.parent.tileX-startX<0) return (2 << 24) | curSegment.gscore;
            else if (curSegment.parent.tileX-startX>0) return (0 << 24) | curSegment.gscore;
            else if (curSegment.parent.tileY-startY<0) return (3 << 24) | curSegment.gscore;
            else if (curSegment.parent.tileY-startY>0) return (1 << 24) | curSegment.gscore;
        }
        throw new RuntimeException("Path finding failed");
     }
}

```
> 1 votes

---
Tags: game, king-of-the-hill, path-finding
---


# Question
Title: Coin Change Problem Enumeration Using N Coins And Each Denomination
The coin change problem is very well documented. Given an infinite supply of coins of denominations `x_1` to `x_m` you need to find the number of combinations which add up to `y`. For example, given `x = {1,2,3}` and `y = 4` we have four combinations:

1. `{1,1,1,1}`
2. `{1,1,2}`
3. `{1,3}`
4. `{2,2}`

# Introduction

There are several variations of the coin change problem. In this variation we have two additional restrictions:

1. Every denomination must be used at least once.
2. Exactly a fixed number of coins must be used in total.

For example, given `x = {1,2,3}`, `y = 36` and `n = 15` where `n` is the total number of coins that must be used, we get four combinations:

1. `{1,2,2,2,2,2,2,2,3,3,3,3,3,3,3}` (1 ones, 7 twos, 7 threes)
2. `{1,1,2,2,2,2,2,3,3,3,3,3,3,3,3}` (2 ones, 5 twos, 8 threes)
3. `{1,1,1,2,2,2,3,3,3,3,3,3,3,3,3}` (3 ones, 3 twos, 9 threes)
4. `{1,1,1,1,2,3,3,3,3,3,3,3,3,3,3}` (4 ones, 1 twos, 10 threes)

# Challenge

The challenge is to write a function `enumerate` in the language of your choice which enumerates all the combinations as described above given:

1. The list of denominations. For example `{1,5,10,25}`. You may use either lists or arrays.
2. A non-negative integer `y` that denotes the sum of every combination.
3. A non-negative integer `n` that denotes the total number of coins.

The order of the arguments doesn't matter. Pointfree functions are allowed.

The output of the `enumerate` function must be a list of combinations. Each combination must be unique and it must be a list of `n` integers which add up to `y`. Every denomination must appear at least once in each combination and no combination must be missing. The ordering of the integers and the combinations doesn't matter. You may use either lists or arrays for the output.

Keep in mind the following edge cases:

1. If both `y` and `n` are zero and the list of denominations is empty then the output is a list of one combination, the empty combination (i.e. `{{}}`).
2. Otherwise, if `y` is zero, `n` is zero or the list of denominations is empty then the output is a list of zero combinations (i.e. `{}`).
3. More generally, if `y` is less than the sum of the denominations or `n` is less than the number of denominations then the output is a list of zero combinations.

Scoring will be based on the size of the entire program in bytes. Note that this includes the `enumerate` function, helper functions, import statements, etc. It does not include test cases.

# Answer
> 2 votes
## 05AB1E, 20 bytes

```
g-¹sã€{Ùvy¹«DO³Qiˆ}¯

```

Input is in the order: `list of values`, `nr of coins`, `sum to reach`.

**Explanation in short**

1. Get all permutations of the coin list of length: `final length - length of unique coin list`
2. Add the list of unique coins to these lists.
3. If the sum equals the sought after sum, save the list
4. Output all saved lists

Try it online

The online compiler can't handle large number of coins.

# Answer
> 4 votes
# MATL, 22 bytes

```
Z^!S!Xu!tsi=Z)"1G@m?@!

```

Input order is: array of denominations, number of coins taken (`n`), desired sum (`y`).

Each combination is displayed on a different line. Empty output is displayed as an empty string (so nothing).

**Try it online!**

The code runs out of memory in the online compiler for the example in the challenge, but works offline with a standard, reasonably modern computer:

```
>> matl
 > Z^!S!Xu!tsi=Z)"1G@m?@!
 >
> [1 2 3]
> 15
> 36
1 1 1 1 2 3 3 3 3 3 3 3 3 3 3
1 1 1 2 2 2 3 3 3 3 3 3 3 3 3
1 1 2 2 2 2 2 3 3 3 3 3 3 3 3
1 2 2 2 2 2 2 2 3 3 3 3 3 3 3

```

### Explanation

```
Z^      % Implicitly input array of denomminations and number of coins n. Compute
        % Cartesian power. This gives 2D array with each "combination"
        % on a different row
!S!     % Sort each row
Xu      % Deduplicate rows
!       % Transpose: rows become columns. Call this array A
ts      % Push a copy, compute sum of each column
i       % Input y (desired sum)
=       % Logical array that contains true if the "combination" has the desired sum
Z)      % Keep only those columns in array A
"       % For each column
  1G    %   Push array of denominations again
  @     %   Push current column
  m     %   Is each denomination present in the column?
  ?     %   If so
    @!  %     Push current column again. Transpose into a row
        %   End if
        % End for
        % Implicitly display stack contents

```

# Answer
> 3 votes
# Python 3, ~~120~~ 106 bytes

```
from itertools import*
lambda d,t,l:[i+d for i in combinations_with_replacement(d,l-len(d))if sum(i+d)==t]

```

An anonymous function that takes input of a tuple of denominations of the form `(x_1, x_2, x_3 ... , x_k)`, a target value, and a number of coins via argument, and returns a list of tuples of the form `[(solution_1), (solution_2), (solution_3), ... (solution_k)]`.

**How it works**

`Itertools`'s `combinations_with_replacement` function is used to generate all `l-len(d)` combinations, with replacement, of the denominations. By appending `d` to each of these combinations, it is guaranteed that each denomination appears at least once, and that the new combination has length `l`. If the elements of a combination sum to `t`, the combination is added to the return list as a tuple.

Try it on Ideone

---

*An alternative method for 108 bytes*

```
from itertools import*
lambda d,t,l:set(tuple(sorted(i+d))for i in product(d,repeat=l-len(d))if sum(i+d)==t)

```

An anonymous function that takes input of a tuple of denominations of the form `(x_1, x_2, x_3 ... , x_k)`, a target value, and a number of coins via argument, and returns a set of tuples of the form `{(solution_1), (solution_2), (solution_3), ... (solution_k)}`.

**How it works (other version)**

This uses the `product` function from `itertools` to generate all `l-len(d)` arrangements of the denominations. By appending `d` to each of these combinations, it is guaranteed that each denomination appears at least once, and that the new combination has length `l`. If the elements of a combination sum to `t`, the combination is sorted, converted from a list to a tuple, and added to the return tuples. Finally, calling `set` removes any duplicates.

Try it on Ideone (other version)

# Answer
> 0 votes
## JavaScript (ES6), 135 bytes

```
g=(a,n,y,r)=>n>0?y>0&&a.map((x,i)=>g(a.slice(i),n-1,y-x,[...r,x])):n|y||console.log(r)
(a,n,y)=>g(a,n-a.length,a.reduce((y,x)=>y-x,y),a)

```

---
Tags: code-golf, combinatorics
---


title: Random character from a string

text:
# Question
Title: Random character from a string
Your goal in this is to pick a random character from a string. If a character appears X times, and there are Y characters, then the chance of that character being picked will be X/Y.

### Input

The program takes a string as an input.

### Output

Your program outputs a character.

### Examples

* `xyz`: x, y, or z
* `xxX`: x, x, or X
* `}^€`: }, ^, or €
* `xxx`: x
* `0123456789`: random number, 0-9

# Answer
# Pyth, 1 byte

```
O

```

Try it online!

### Explanation

From the definition of the operator `O`:

```
op. arg.    func.
O   <col>   Random element of A.

```
> 2 votes

# Answer
# Jelly, 1 byte

```
X

```

Try it online!

### Explanation

From the definition of the operator `X`:

> Arity: 1
>
> Name: Random
>
> Function: choose a random item from z if z is a list, or from 1 to z inclusive if z is a positive integer. If z = 0, return z. Error if z is negative or a decimal.
> 1 votes

# Answer
# CJam, 3 bytes

```
lmR

```

Try it online!

```
lmR
l    read line
 mR  random element

```
> 1 votes

# Answer
# 05AB1E, 2 bytes

```
.R

```

from `Info.txt`:

```
.R      = pop a      push random_pick(a)

```

Try it online!
> 1 votes

# Answer
# C, 30 bytes

This answer must run on a 32-bit platform and requires the GNU C library implementation.

```
f(s){return*(char*)strfry(s);}

```

The `strfry` function shuffles the characters in a string. We first shuffle the input string, then return the first character.
> 1 votes

# Answer
# Actually, 1 byte

```
J

```

Try it online!

### Explanation

From the definition of the operator `J`:

> `4A (J): pop a: push a random integer in [0,a) (randrange(a)); pop [a] or "a": push a random element from [a] or "a" (random.choice([a]|"a"))`
> 0 votes

# Answer
# , 5 bytes

```
?@#{]

```

## Usage

```
>> f =: ?@#{]
>> f 'xyz'
<< x

```

## Explanation

This is a fork, where `f` is `?@#`, `g` is `{`, and `h` is `]`.

Therefore, `(?@#{])'xyz'`, when expanded, would become `((?@#)'xyz') ({) ((])'xyz')`

The `(?@#)` is just a composed function, so `(?@#)'xyz'` expanded would become `?(#'xyz')`.

`#'xyz'` gets the length of `'xyz'`, then `?` generates a random non-negative integer below the length.

The `{` then takes the item at the corresponding index.
> 0 votes

# Answer
# Python 3.5 and Python 2.7, 26 bytes:

```
from random import*;choice

```

A function declaration. Name the function, and then call it like `print(<Function Name>(<String>))`.
> 0 votes

# Answer
# Java 8, 44 bytes

```
x->x.charAt((int)(Math.random()*x.length()))

```

Try it online!
> 0 votes

# Answer
# Javascript, 40 bytes

```
x=>x[Math.floor(x.length*Math.random())]

```

```
f=x=>x[Math.floor(x.length*Math.random())]
alert(f(prompt()))
```
> 0 votes

# Answer
# Perl 6, 11 bytes

```
*.comb.pick

```

```
*.comb.roll

```

### Explanation:

* `*` starts the Whatever lambda
* `.comb` splits the string into a list of grapheme clusters
* `.roll`/`.pick` grabs a single element from the list at random
( so it is effectively a weighted roll )

( There isn't a difference between `.pick` and `.roll` unless you give them an argument that is something other than `1` )

### Usage:

```
say ( *.comb.pick )( 'xxX' ); # ⅔ chance of ｢x｣, ⅓ chance of ｢X｣

my &code = *.comb.pick;

say code 'xyz'; # ⅓ chance of each of ｢x｣ ｢y｣ or ｢z｣

say ('}^€:','0123456789').map: *.comb.pick;

```
> 0 votes

# Answer
# q (4)

Will return a random item from a list:

```
rand

```
> 0 votes

---
Tags: code-golf, string
---