title: Standardise a Phinary Number

text:
# Question
Title: Standardise a Phinary Number
## Background

Most people on here should be familiar with a few integer base systems: decimal, binary, hexadecimal, octal. E.g. in the hexadecimal system, a number \\$abc.de\_{16}\\$ would represent

$$a\times16^2 + b\times16^1 + c\times16^0 + d\times16^{-1} + e\times16^{-2}$$

However, one can also use non-integer bases, like irrational numbers. Once such base uses the golden ratio \\$φ = \frac{1+√5}2 ≈ 1.618...\\$. These are defined analogously to integer bases. So a number \\$abc.de\_φ\\$ (where \\$a\\$ to \\$e\\$ are integer digits) would represent

$$a\timesφ^2 + b\timesφ^1 + c\timesφ^0 + d\timesφ^{-1} + e\timesφ^{-2}$$

Note that in principle any of the digits could be negative (although we're not used to that) - we'll represent a negative digit with a leading \\$\text{~}\\$. For the purpose of this question we restrict ourselves to digits from \\$\text{~}9\\$ to \\$9\\$, so we can unambiguously write a number as one string (with tildes in between). So

$$-2\timesφ^2 + 9\timesφ^1 + 0\timesφ^0 + -4\timesφ^{-1} + 3\timesφ^{-2}$$

would be written as \\$\text{~}290.\text{~}43\\$. We call such a number a **phinary number**.

A phinary number can always be represented in *standard form*, which means that the representation uses only digits \\$1\\$ and \\$0\\$, without containing \\$11\\$ anywhere, and with an optional minus sign to indicate that the entire number is negative. (Interestingly, every integer has a unique finite representation in standard form.)

Representations which are not in standard form can always be converted into standard form using the following observations:

1. \\$011\_φ = 100\_φ\\$ (because \\$φ^2 = φ + 1\\$)
2. \\$0200\_φ = 1001\_φ\\$ (because \\$φ^2 + \frac1φ = 2φ\\$)
3. \\$0\text{~}10\_φ = \text{~}101\_φ\\$ (because \\$φ - \frac1φ = 1\\$)

In addition:

4. If the most significant digit is \\$\text{~}1\\$ (with the rest of the number being standard form), the number is negative, and we can convert it into standard form by swapping all \\$1\\$ and \\$\text{~}1\\$, prepending a minus sign, and applying the above three rules again until we obtain the standard form.

Here is an example of such a normalisation of \\$1\text{~}3.2\text{~}1\_φ\\$ (I'm using additional spaces for positive digits, to keep each digit position aligned):

```

      1~3. 2~1<sub>φ</sub>         Rule:
=     0~2. 3~1<sub>φ</sub>         (3)
=    ~1~1. 4~1<sub>φ</sub>         (3)
=  ~1 0 0. 4~1<sub>φ</sub>         (3)
=  ~1 0 0. 3 0 1<sub>φ</sub>       (3)
=  ~1 0 1. 1 0 2<sub>φ</sub>       (2)
=  ~1 1 0. 0 0 2<sub>φ</sub>       (1)
=  ~1 1 0. 0 1 0 0 1<sub>φ</sub>   (2)
= - 1~1 0. 0~1 0 0~1<sub>φ</sub>   (4)
= - 0 0 1. 0~1 0 0~1<sub>φ</sub>   (3)
= - 0 0 1.~1 0 1 0~1<sub>φ</sub>   (3)
= - 0 0 0. 0 1 1 0~1<sub>φ</sub>   (3)
= - 0 0 0. 0 1 1~1 0 1<sub>φ</sub> (3)
= - 0 0 0. 0 1 0 0 1 1<sub>φ</sub> (3)
= - 0 0 0. 0 1 0 1 0 0<sub>φ</sub> (1)

```

Yielding \\$-0.0101\_φ\\$.

For further reading, Wikipedia has a very informative article on the topic.

## The Challenge

Hence, or otherwise, write a program or function which, given a string representing a phinary number (as described above), outputs its standard form, without leading or trailing zeroes. The input does not necessarily contain the phinary point, but will always contain the digit left of it (so no \\$.123\\$). The output must always include the phinary point and at least one digit to the left of it.

You may take input via STDIN, ARGV or function argument and either return the result or print it to STDOUT.

You may use a different algorithm than the above procedure as long as it is in principle correct and exact for arbitrary (valid) inputs - that is, the only limits which could potentially break your implementation should be technical limitations like the size of built-in data types or the available RAM. For instance, evaluating the input as a floating-point number and then picking digits greedily is not allowed, as one could find inputs for which floating-point inaccuracies would lead to incorrect results.

This is code golf, the shortest answer (in bytes) wins.

## Test Cases

```
Input       Output

1           1.
9           10010.0101
1.618       10000.0000101
1~3.2~1     -0.0101
0.~1021     0. (or -0.)
105.~2      1010.0101
~31~5.~1    -100000.1001

```

# Answer
> 6 votes
# Javascript (ES6) - ~~446~~ ~~418~~ ~~422~~ 420 bytes

Minified:

```
F=s=>{D=[];z='000000000';N=t=n=i=e=0;s=(z+s.replace(/^([^.]*)$/,'$1.')+z).replace(/~/g,'-').replace(/-?\d/g,s=>((D[n++]=s/1),0));for(;i<n-3;i=j){if(p=D[j=i+1]){if(!e&&p<0){D=D.map(k=>-k);N=~N;p=-p}e=1}d=D[i];x=D[i+2];m=D[i+3];if(p<0){d--;p++;x++;e=j=0}if(p>1){d++;m++;p-=2;e=j=0}if(!d&&p*x==1){d=p;e=j=p=x=0}D[i]=d;D[i+1]=p;D[i+2]=x;D[i+3]=m}return(N?'-':'')+s.replace(/0/g,()=>D[t++]).replace(/^(0(?!\.))+|0+$/g,'')}

```

Expanded:

```
F = s => {
    D = [];
    z = '000000000';
    N = t = n = i = e = 0;
    s = (z + s.replace( /^([^.]*)$/, '$1.' ) + z).replace( /~/g, '-' ).
        replace( /-?\d/g, s => ((D[n++]=s/1),0) );

    for( ; i < n-3; i = j ) {
        if( p = D[j = i+1] ) {
            if( !e && p < 0 ) {
                D = D.map( k=>-k );
                N = ~N;
                p = -p;
            }
            e = 1;
        }
        d = D[i];
        x = D[i+2];
        m = D[i+3];

        if( p < 0 ) {
            d--;
            p++;
            x++;
            e = j = 0;
        }
        if( p > 1 ) {
            d++;
            m++;
            p-=2;
            e = j = 0;
        }
        if( !d && p*x == 1 ) {
            d = p;
            e = j = p = x = 0;
        }

        D[i] = d;
        D[i+1] = p;
        D[i+2] = x;
        D[i+3] = m;
    }

    return (N ? '-' : '') + s.replace( /0/g, ()=>D[t++] ).replace( /^(0(?!\.))+|0+$/g, '' );
}

```

The code produces a function `F` that performs the specified conversion.

It's a tough problem to golf. Numerous edge cases creep up that prevent simplification of the code. In particular, dealing with negatives is a pain, both in terms of parsing and in terms of logical handling.

I should note that the code only handles a "reasonable range" of inputs. To extend the domain of the function without bound, the number of zeros in `z` can be increased, and the constant bounding the `while( c++ < 99 )` loop can be increased. The range currently supported is already overkill for the supplied test cases.

### Sample Outputs

```
F('1')          1.
F('9')          10010.0101
F('1~3.2~1')    -0.0101
F('0.~1021')    -0.
F('105.~2')     1010.0101
F('~31~5.~1')   -100000.1001

```

The `-0.` isn't pretty, but the answer is still correct. I can fix it if necessary.

# Answer
> 3 votes
# Haskell, 336 bytes

```
z=[0,0]
g[a,b]|a*b<0=g[b,a+b]
g x=x<z
k![a,b,c,d]=[b,a+b,d-c+read k,c]
p('.':s)=1:0:2`drop`p s
p('~':k:s)=['-',k]!p s
p(k:s)=[k]!p s
p[]=1:0:z
[1,0]&y='.':z?y
[a,b]&y=[b,a+b]?y
x@[a,b]?y@[c,d]|x==z,y==z=""|g y='-':x?[-c,-d]|g[c-1,d]='0':x&[d,c+d]|g[c,d-1]='1':x&[d,c+d-1]|0<1=[b-a,a]?[d-c,c]
m[a,b,c,d]=[1,0]?[a*d+b*c-a*c,a*c+b*d]
f=m.p

```

This is the greedy algorithm, but with an exact representation `[a,b]` of numbers *a* \+  (*a*, *b* ∈ ℤ) to avoid floating-point errors. `g[a,b]` tests whether *a* \+  \< 0. Usage example:

```
*Main> f "9"
"10010.0101"
*Main> f "1~3.2~1"
"-0.0101"
*Main> f "0.~1021"
"0."

```

---
Tags: code-golf, number, arithmetic, number-theory, base-conversion
---


title: Standard loopholes only

text:
# Question
Title: Standard loopholes only
So, you're browsing Programming Puzzles & Code Golf, and you see a new challenge. The author (*gasp*) forgot to say "No standard Loopholes". You decide to take advantage of this situation, and you read the answer from a file/network. However, you need to make sure that your answer is actually shorter than the legitimate answers, so you golf it, too.

# The Challenge

Write a complete program that prints out the contents of the file `definitelynottheanswer.txt` to STDOUT. This text file only contains valid ASCII characters. Alternatively, the program can get the file location from STDIN or command line args. The only input allowed is the file location if you choose to get the location from the user; otherwise, no input is allowed. There is no reward for getting the file location from the user, but the user input of the file location does not count against the byte total (in other words, `definitelynottheanswer.txt` wouldn't be included in the byte score).

The program must not write to STDERR.

## Bonus

Retrieve the file from the internet *instead* of a file (the URL must be user-supplied). **Reward: multiply source length by 0.85**

# Scoring

* This is , so the lowest score,`program length (bytes) * bonus`, wins.
* No (other) standard loopholes.
* If the language does not support reading files from disk, it cannot be used (sorry).

# Answer
> 14 votes
# GNU sed, 0 bytes

Even better..

# Answer
> 2 votes
# Bash, 7 bytes * .85 = 5.9 bytes

```
curl $1

```

zzz

# Answer
> 1 votes
# Pyth - 2 bytes * .85 = 1.7

```
'z

```

Does not work online.

# Answer
> 1 votes
## Bash, 6 bytes

```
cat $1

```

Provide filename as a command line argument. Probably breaks if the argument contains spaces or newlines or weird chars or whatever.

# Answer
> 1 votes
# CJam, 1.7 bytes

```
qg

```

For security reasons, this does not work in the online interpreter.

---
Tags: code-golf, file-system
---


title: Shortening str.replace()

text:
# Question
Title: Shortening str.replace()
In Python it is often necessary to use `str.replace(a,b)`, however `.replace` is rather long and feels unnecessary. So is there a shorter alternative to `str.replace`.

Alternatively is there a similar trick to how you can use `r=range` for golfing for `str.replace`?

## Example code for golfing

```
m=input()
f="hello"
print m.replace('t','Ushd')
print m.replace('h','gyhj')
print f.replace('o','%£&')

```

# Answer
```
r=str.replace;print r('abc','b','c')

```

The magic is real.

Shortening str.replace()
> 3 votes

# Answer
### Regex Replace

You can use `re.sub`, but it will take several uses to pay off if you're only doing it one character at a time.

```
import re
s="hello"
r=s.replace('h','m')
r=re.sub('h','m',s)

```

### Translate

You may also wish to look at `string.translate`, which can be used for large numbers of single-character replacements. **Requires Python 3.** If using Python 2, `maketrans` is required first. For an example, see here. In Python 3, it's used like this (taking a literal dictionary of ASCII values):

```
print("hello".translate({104:109}))

```

Output:

```
mello

```
> 3 votes

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


# Question
Title: n-queens problem, displaying more than one solution available
as some of you may know, n-queens problem is a set of algorithm puzzle that given a 'n x n' where n is the board size of a (let's say) chessboard, and the main goal is for the n queens (where n is the number of the queens) not be able to 'attack' one another in the board.

now I have a set of **console code** where user can input the board size (with an exception of less than 4x4), and the program will display one solution for the board size inputted. here's the code sample in C++:

```
#include <windows.h>
#include <iostream>
#include <string>

using namespace std;

class point
{
public:
int x, y;
point() { x = y = 0; }
void set( int a, int b ) { x = a; y = b; }
};

class nQueens
{
public:
void solve( int c )
{
    _count = c;
    int len = (c + 1) * (c + 1);
    _queens = new bool[len]; memset( _queens, 0, len );
    _cl = new bool[c]; memset( _cl, 0, c );
    _ln = new bool[c]; memset( _ln, 0, c );
    point pt; pt.set( rand() % c, rand() % c );
    putQueens( pt, c );
    displayBoard();
    delete [] _queens; delete [] _ln; delete [] _cl;
}

private:
void displayBoard()
{
    system( "cls" );
    const string t = "+---+", q = "| Q |", s = "|   |";
    COORD c = { 0, 0 };
    HANDLE h = GetStdHandle( STD_OUTPUT_HANDLE );
    for (int y = 0, cy = 0; y < _count; ++y)
    {
        int yy = y * _count;
        for ( int x = 0; x < _count; x++ )
        {
            SetConsoleCursorPosition( h, c ); cout << t;
            c.Y++; SetConsoleCursorPosition( h, c );
            if (_queens[x + yy]) cout << q; else cout << s;
            c.Y++; SetConsoleCursorPosition( h, c );
            cout << t; c.Y = cy; c.X += 4;
        }
        cy += 2; c.X = 0; c.Y = cy;
    }
}

bool checkD( int x, int y, int a, int b )
{
    if ( x < 0 || y < 0 || x >= _count || y >= _count ) return true;
    if ( _queens[x + y * _count] ) return false;
    if ( checkD( x + a, y + b, a, b ) ) return true;
    return false;
}

bool check( int x, int y )
{
    if ( _ln[y] || _cl[x] )        return false;
    if ( !checkD( x, y, -1, -1 ) ) return false;
    if ( !checkD( x, y,  1, -1 ) ) return false;
    if ( !checkD( x, y, -1,  1 ) ) return false;
    if ( !checkD( x, y,  1,  1 ) ) return false;
    return true;
}

bool putQueens( point pt, int cnt )
{
    int it = _count;
    while (it)
    {
        if ( !cnt ) return true;
        if ( check( pt.x, pt.y ) )
        {
            _queens[pt.x + pt.y * _count] = _cl[pt.x] = _ln[pt.y] = true;
            point tmp = pt;
            if ( ++tmp.x >= _count ) tmp.x = 0;
            if ( ++tmp.y >= _count ) tmp.y = 0;
            if ( putQueens( tmp, cnt - 1 ) ) return true;
            _queens[pt.x + pt.y * _count] = _cl[pt.x] = _ln[pt.y] = false;
        }
        if ( ++pt.x >= _count ) pt.x = 0;
        it--;
    }
    return false;
}

int          _count;
bool*        _queens, *_ln, *_cl;
};

int main( int argc, char* argv[] )
{
nQueens n; int nq;
while( true )
{
    system( "cls" );
    cout << "Enter board size bigger than 3 (0 - 3 to QUIT): "; cin >> nq;
    if ( nq < 4 ) return 0;
    n.solve( nq ); cout << endl << endl;
    system( "pause" );
}
return  0;
}

```

now, as the code only display **one solution** only, where 4x4 should have more than one solution available, your challenge is to make the code to be able to display **more than one solution** should it's possible, and displaying the 'graphic' solution (console is recommended). C++ is recommended, but other programming language is more than welcome. Good luck!

# Answer
## Python 2.7

Nice object-oriented solution:

```
class Queen(object):
    def __init__(self, row, col):
        self.row = row
        self.col = col

    @property
    def u(self):
        'Return the SW-NE diagonal by starting row'
        return self.col + self.row

    @property
    def v(self):
        'Return the NW-SE diagonal by starting column'
        return self.col - self.row

class Solver(object):
    '''
    Solver which iterates over solutions.  Each iterator produces a
    string representation of a valid solution.
    '''
    def __init__(self, n):
        self.n = n
        self.queens = [Queen(r, 0) for r in range(n)]

    def __iter__(self):
        return self

    def next(self):
        self.step()
        while not self.is_valid():
            self.step()
        # Draw the solution
        line = ('+---' * self.n) + '+\n'
        text = line
        for row in range(self.n):
            text += '| %s |\n' % ' | '.join(' Q'[c == self.queens[row].col] for c in range(self.n))
            text += line
        return text

    def step(self, _row=None):
        'Increment the solution one step'
        if _row == -1:
            raise StopIteration
        if _row is None:
            _row = self.n - 1
        self.queens[_row].col += 1
        if self.queens[_row].col == self.n:
            self.queens[_row].col = 0
            self.step(_row - 1)

    def is_valid(self):
        'Return True if the queens are all safe'
        qc = len(self.queens)
        return all(len(set(getattr(q, p) for q in self.queens)) == qc for p in ['row', 'col', 'u', 'v'])

if __name__ == '__main__':
    n = int(raw_input('Enter n:'))
    for s in Solver(n):
        print(s)

```
> 2 votes

# Answer
## PHP

Using a simple recursive approach.

```
<?
function q($n,$t=[],$r=1,$S=str_repeat){
  foreach($r>$n?$t:[]as$v)echo$f=$S('+---',$n)."+\n",$S('|   ',$n)."|\n"|$S(' ',$v*4-2).q;
  for(;$s<$n?$r-$s^abs($c=$p-$t[$s++])&&$c:q($n,$t+[$r=>$p],$r+1)?:$n>=$p+=$s=1;);echo$f;
}
q(4);

```

Sample output for `$n=4`:

```
+---+---+---+---+
|   | q |   |   |
+---+---+---+---+
|   |   |   | q |
+---+---+---+---+
| q |   |   |   |
+---+---+---+---+
|   |   | q |   |
+---+---+---+---+
+---+---+---+---+
|   |   | q |   |
+---+---+---+---+
| q |   |   |   |
+---+---+---+---+
|   |   |   | q |
+---+---+---+---+
|   | q |   |   |
+---+---+---+---+

```
> 4 votes

# Answer
# Mathematica

The positions of *n* queens on an *n* x *n* chessboard can be represented as a permutation of *n*. For example, The permutation, {3, 1, 4, 2}, is shorthand for the idea that there are 4 queens at {{row3, col1}, {row1, col2}, {row4, col3}, {row2, col4}.

`array[{3, 1, 4, 2}]` returns the complete array, with 1' s now representing queens.

> {{0, 1, 0, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}, {0, 0, 1, 0}}

This could be displayed as a grid through `Grid@array[{3, 1, 4, 2}]`.

or as a board, using `board[{3, 1, 4, 2}]`. The black squares are those occupied by a queen.

`solutionQ[{3, 1, 4, 2}]` displays the board and whether or not that board is a solution.

```
array[pos_]:=ReplacePart[ConstantArray[0,{l=Length[pos],l}],Partition[Riffle[pos,Range[Length[pos]]],2]/.{{a_,b_}:> ({a,b}-> 1)}]
board[pos_]:=ArrayPlot[array[pos],ImageSize->120,Mesh-> True]

solutionQ[pos_]:=
  Module[{b,safeQ, len=Length[pos],files},
  b=array[pos];
  safeQ[b1_]:=(Max[Tr/@Table[Diagonal[b1,k],{k,-(len-2),len-2}]])<2;
  {board[pos],safeQ[b]\[And]safeQ[Reverse/@b]}]

solutions[gridSize_]:=Cases[solutionQ/@Permutations[Range[gridSize]],{_,True}][[All,1]]

```

## Results

```
Table[Print[n , " queens solutions: ", Row@solutions[n]], {n, 4, 6}]

```

---

```
Table[Print[ "Number of solutions in a ", n, " by ", n, " table: ", solutions[n] // Length],
{n, 7, 8}]

```

> Number of solutions in an 7 by 7 table: 40
> Number of solutions in an 8 by 8 table: 92
> 4 votes

# Answer
# Haskell (ideone)

```
import System.Environment (getArgs)

data Board = Board {
  field :: [Int],
  size :: Int
}

-- | Checks whether the board has a conflict
conflict :: Board -> Bool
conflict b = any (==x) xs || step (-1) x xs || step 1 x xs
  where (x:xs) = field b
        step _ _ [] = False
        step s p (x:xs)
          | (s+p) == x = True
          | otherwise  = step (s+p) p xs

-- | Returns all boards one can get by placing a queen in the next column
place :: Board -> [Board]
place b = place' b 1
  where place' b s
          | s > size b        = []
          | conflict newboard = rest
          | otherwise         = newboard:rest
          where newboard = Board newfield (size b)
                newfield = s:(field b)
                rest     = place' b (s+1)

-- | Returns all boards one can get for the n-th queen problem
placeAll :: Int -> [Board]
placeAll n = foldl (>>=) [Board [] n] (replicate n place)

-- | Creates a String from a board
prettyPrint :: Board -> String
prettyPrint b = unlines.map prettyLine.field$b
  where prettyLine n = replicate (n - 1) '.' ++ "@" ++ replicate ((size b) - n) '.'

-- | Shows the first two solutions obtained by placeAll
main = do
  [s] <- getArgs
  mapM_ putStrLn . map prettyPrint . take 2 . placeAll . read $ s

```

Sample output

```
$ runghc nqueens.hs 12
...........@
........@...
..........@.
.@..........
.........@..
.......@....
.....@......
...@........
......@.....
....@.......
..@.........
@...........

..........@.
........@...
...........@
.@..........
.........@..
.......@....
.....@......
...@........
......@.....
....@.......
..@.........
@...........

$ time runghc nqueens.hs 48
..............................................@.
...........................................@....
...............................................@
.............................................@..
.........................................@......
............................................@...
..........................................@.....
........................................@.......
......................................@.........
....................................@...........
.......................................@........
.....................................@..........
...................................@............
.................................@..............
...............................@................
..................................@.............
................................@...............
..............................@.................
............................@...................
..........................@.....................
.............................@..................
...........................@....................
.........................@......................
.......................@........................
.....................@..........................
........................@.......................
......................@.........................
....................@...........................
..................@.............................
................@...............................
...................@............................
.................@..............................
...............@................................
.............@..................................
...........@....................................
..............@.................................
............@...................................
..........@.....................................
........@.......................................
.@..............................................
.........@......................................
.......@........................................
.....@..........................................
...@............................................
......@.........................................
....@...........................................
..@.............................................
@...............................................

...............................................@
.............................................@..
...........................................@....
..............................................@.
.........................................@......
............................................@...
..........................................@.....
........................................@.......
......................................@.........
....................................@...........
.......................................@........
.....................................@..........
...................................@............
.................................@..............
...............................@................
..................................@.............
................................@...............
..............................@.................
............................@...................
..........................@.....................
.............................@..................
...........................@....................
.........................@......................
.......................@........................
.....................@..........................
........................@.......................
......................@.........................
....................@...........................
..................@.............................
................@...............................
...................@............................
.................@..............................
...............@................................
.............@..................................
...........@....................................
..............@.................................
............@...................................
..........@.....................................
........@.......................................
.@..............................................
.........@......................................
.......@........................................
.....@..........................................
...@............................................
......@.........................................
....@...........................................
..@.............................................
@...............................................

runghc nqueens.hs 48  0,16s user 0,02s system 93% cpu 0,189 total

```
> 1 votes

# Answer
Ocaml :

```
let print_list list =
  List.iter print_int list;
    print_newline();;

let infect x y list =
  let rec infect_rec x y n  = function
      [] -> false
    | a :: r -> if (y = a) then true
      else if ( y = a + x - n ) then true
      else if ( y = a - x + n ) then true
      else infect_rec x y (n-1) r in
    infect_rec x y (x-1) list;;

let rec add_queen x n queen =
  if x > n then print_list queen
  else
    for i = 1 to n do
      if (infect x i queen) = false
      then add_queen (x+1) n (i :: queen)
    done
;;

add_queen 1 8 [];;

```
> 1 votes

# Answer
My short but quite readable Python solution:

```
def nqueens(n):
    def state(n):
        return set((i,j) for i in range(n) for j in range(n))
    def move(i,j,n):
        line = lambda ci,cj: set((i+d*ci,j+d*cj) for d in range(-n,n+1))
        return line(1,0) | line(0,1) | line(1,1) | line(1,-1)
    def solve(n1, s=state(n), r=()):
        if n1==0: yield tuple(sorted(r))
        for x in s: yield from solve(n1-1, s-move(x[0],x[1],n), r+(x,))
    return solve(n)

```

The state of computation is represented as possible moves, and a move as the possibilities is going to remove from current state, so applying a move to a state is just set difference.

Can also generate all the solutions.

Printing the (first) solution:

```
def sol2str(s,n):
    return '\n'.join(' '.join('X' if (row,col) in s else '.' for col in range(n)) for row in range(n))

n = 8
print(sol2str(next(nqueens(n)),n))

. . . . . X . .
X . . . . . . .
. . . . X . . .
. X . . . . . .
. . . . . . . X
. . X . . . . .
. . . . . . X .
. . . X . . . .

```
> 1 votes

# Answer
This solution is a slight trolling, but since it's not specified what solutions are considered to be the same, I guess it should qualify :). Let the original program be compiled as `queens`. Then the extension is:

```
#!/bin/bash
queens "$@" >tmpfile
cat tmpfile
tac tmpfile

```

**Explanation:** A mirrored solution is obviously also a solution. And it must be different from the original one: Pick a queen not positioned in the middle row from the original solution and Let `(x,y)` be its position (so `y != n-y-1`). Then the original and mirrored solutions differ at `(x,n-y-1)`. There is a queen at `(x,n-y-1)` in the mirrored solution, but the position must be empty in the original one.
> 0 votes

# Answer
**Groovy**

```
s = (0..7).permutations().findAll{
   def x=0,y=0
   Set a=it.collect{it-x++}
   Set b=it.collect{it+y++}
   a.size()==it.size()&&b.size()==it.size()
}

```

Delivers a list of all queen solutions like this:

```
[ [4, 7, 3, 0, 6, 1, 5, 2],
  [6, 2, 7, 1, 4, 0, 5, 3],
  ... ]

```

For graphical representation add:

```
s.each { def size = it.size()
         it.each { it.times { print "|_" }
                   print "|Q"
                   (size-it-1).times { print "|_" }
                   println "|"
                 }
         println ""
         }

```

which looks like this (2 examples of the 92 solutions):

```
|Q|_|_|_|_|_|_|_|
|_|_|_|_|_|_|Q|_|
|_|_|_|Q|_|_|_|_|
|_|_|_|_|_|Q|_|_|
|_|_|_|_|_|_|_|Q|
|_|Q|_|_|_|_|_|_|
|_|_|_|_|Q|_|_|_|
|_|_|Q|_|_|_|_|_|

|_|_|_|_|Q|_|_|_|
|_|Q|_|_|_|_|_|_|
|_|_|_|_|_|Q|_|_|
|Q|_|_|_|_|_|_|_|
|_|_|_|_|_|_|Q|_|
|_|_|_|Q|_|_|_|_|
|_|_|_|_|_|_|_|Q|
|_|_|Q|_|_|_|_|_|

```

**Explanation**:

My first Groovy experiment. I am loving the closures and the conciseness of this language!

Lets take it apart:

```
   (0..7).permutations()

```

// returns a list of all permutations of the sequence \[0,1,2,3,4,5,6,7\]

```
   .findAll{

```

Find and return all elements for which the following closure returns true

Here is how we check if all queens are safe:

```
   def x=0,y=0
   Set a=it.collect

```

Transform all integers in the permutations using the closure:

```
        {  it-x++ }

```

We need to check if 2 queens are on the same diagonal.

Mathematically a diagonally rising line is: y = x + const

```
   Set b=it.collect{it+y++}

```

A falling line is y = -x + const Our closures return const = x+y (or x-y respectively)

We add them to a Set to find duplicates. A Duplicate means 2 queens have the same function (are on the same diagonal).

```
   a.size()==it.size()&&b.size()==it.size() }

```

The last statement in the closure returns true if there are no duplicates, so all queens are safe!
> 0 votes

---
Tags: popularity-contest, chess
---


title: Remove Whitespace from a Java Program

text:
# Question
Title: Remove Whitespace from a Java Program
In this challenge, you will be given the source code of a **Java** program. Your task is to write a function or full program that will remove the whitespace from this program. The whitespace-removed program should work exactly the same as the original program. Your program can be in any language. In this challenge, every space, tab, and newline will be considered whitespace.

## Summary

Input can be through command-line arguments, function parameters, or STDIN/equivalent. Output will be the input program without whitespace through STDOUT/equivalent, **along with an integer representing the amount of whitespace removed**. Your score will be determined by `(number of bytes) - (whitespace removed in sample program)`

## Sample Program (You can remove 104 whitespace characters from this)

```
class Condition {
    public static void main(String[] args) {
        boolean learning = true;

        if (learning == true) {
            System.out.println("Java programmer");
        }
        else {
            System.out.println("What are you doing here?");
        }
    }
}

```

http://pastebin.com/0kPdqZqZ

Whitespace-free version: `class Condition{public static void main(String[]args){boolean learning=true;if(learning==true){System.out.println("Java programmer");}else{System.out.println("What are you doing here?");}}}`

## Clarifications from Comments (see below)

* The programs passed as input will be at the same whitespace complexity as the sample program.
* The programs will not contain comments.

## Closing question

Due to the amount of confusion involved with the question, I have decided to close the competition and accept @MartinBüttner's answer. Sorry for any misunderstanding. However, I would believe the answers to be good as a tool for java golfers, which is why I did not delete the question.

# Answer
> 5 votes
# CJam, 25 bytes - 83 removed = -58

Since Java doesn't have multiline strings nor significant indentation, we can simply remove all leading spaces. Also, since there won't be any comments, and statements will not be split across lines (as per the OP's comments), I think I should be able to remove all newlines as well.

That makes for safe and short code with pretty decent savings for the test file:

```
q_,\N/{S\+e`1>e~}%_oNos,-

```

Test it here.

For the test case it yields

```
class Condition {public static void main(String[] args) {boolean learning = true;if (learning == true) {System.out.println("Java programmer");}else {System.out.println("What are you doing here?");}}}
83

```

# Answer
> 3 votes
# JavaScript (ES6), 72 bytes - 92 removed = -20

(partially invalid?)

```
x=>(z=x.replace(/\s*[{}()=;]\s*/g,y=>y.trim()))+`
`+(x.length-z.length)

```

The output:

```
class Condition{public static void main(String[] args){boolean learning=true;if(learning==true){System.out.println("Java programmer");}else{System.out.println("What are you doing here?");}}

```

I believe the one space I could still remove is the one in `(String[] args)`, but this would not be worth it. This is pretty much the lowest score JS can get (for this specific case, anyway).

# Answer
> 2 votes
# Ruby, 63 bytes - 104 removed = -41

edit: 104 *bytes* that is.

```
$><<j=(i=$<.read).gsub(/(?<=\W)\s|\s(?=\W)/,"")
p i.size-j.size

```

Removes all newlines, so the printed number at the end comes on the same line too:

```
$ curl -s http://pastebin.com/raw.php?i=0kPdqZqZ | ruby remove_whitespace.rb
class Condition{public static void main(String[]args){boolean learning=true;if(learning==true){System.out.println("Java programmer");}else{System.out.println("What are you doing here?");}}}104

```

# Answer
> 1 votes
# Python, 92 bytes - 88 removed = 4

```
import re,sys
p=sys.stdin.read()
s=re.sub('\s+(=|{|}|(|))\s+',r'\1',p)
print len(p)-len(s),s

```

Test it here

Once again, regex to the rescue. There's a strange discrepancy between ideone and my python install - I'm getting 90 chars removed.

jprog.py source:

```
#!/usr/bin/env python

print """class Condition {
    public static void main(String[] args) {
        boolean learning = true;

        if (learning == true) {
            System.out.println("Java programmer");
        }
        else {
            System.out.println("What are you doing here?");
        }
    }
}"""

```

# Answer
> 1 votes
# Java 8 : 79 Bytes

```
s->{System.out.print(s.replaceAll("(\\s+|\\n)?(\\{|\\}|=+|;)(\\s+|\\n)", "$2"));}

```

Regular expression with grouping can remove the extra white spaces between curly braces and equals sign used in assignment or equality check.

Regular expression is something like, `(\s+|\n)?({|}|=+|;)(\s+|\n)`

It will provide following output, which is valid Java program.

```
class Condition{public static void main(String[] args){boolean learning=true;if (learning==true){System.out.println("Java programmer");}else{System.out.println("What are you doing here?");}}}

```

---
Tags: code-challenge, java, parsing, whitespace
---


title: King of the Hill - Firefighters

text:
# Question
Title: King of the Hill - Firefighters
It is a dry summer in the prairie. The four farmers in the area realize that they can corner the market on corn by burning their neighbors crops. But they need a strategy for doing so; that is where you come in.

Your task is to write a bot to tell the farmers what to burn. The goal is to finish the game with the largest area of unburnt land. The playing field is a 32x32 grid. Each cell may be one of the following:

`. - Ground`

`@ - A bot`

`# - Ash`

`W - Wet ground`

`1,2,3,4,5, or 6 - Fire`

Fire grows in intensity by 1 each turn. Once it is 3 or higher, it will set cells next to it (horizontally or vertically) on fire. After fire hits 6, it turns into ash.

On each turn, bots receive as STDIN the following: bot starting x, bot starting y, bot current x position, bot current y position, and the board, separated by newlines. An example:

```
8
22
6
24
................................
................................
................................
.....................1..........
....................1#1.........
...................1#363........
....................16@1........
.....................31.........
................................
.........1.1....................
........15#62...................
........15@2....................
.........32.....................
................................
................................
................................
................................
................................
................................
................................
................................
................................
....4.1.........................
.....1#3........................
.....@3.........................
.....W..........................
................................
................................
................................
................................
................................
................................

```

(in this instance you are the bot in the bottom left).

You must output three characters, with an optional newline, representing the following:

Move - one of `L, R, U, D, or S (stay)`

Action - one of `B (burn), P (pour water) or X (do nothing)`

Direction - one of `L, R, U, D or S` \- controls which cell you perform the action on

Fire does not affect bots.

Turn order is as follows: All bots move; all bots perform actions; then environmental rules happen. If you pour water on the ground, it will be wet (`W`) for one turn. Fire will not spread to wet ground. If you pour water on wet ground, it will continue to be wet. If you pour water on fire, it turns back to regular ground. You cannot do anything to ash.

Rounds are run with 4 bots at a time. The round ends after 50 turns, or when one bot runs out of unburnt ground, whichever comes first. Your score is calculated as the number of ground or wet ground cells in the 9x9 square centered on where your bot started.

Here is an example bot; it picks all three letters randomly and generally ends up burning down its own fields.

RandomBurner:

```
#!/usr/bin/env python
import random
print random.choice('LRUDS')+random.choice('BPX')+random.choice('LRUDS')

```

Rules:

* No filesystem access outside of your own folder.
* You may write to files if you need to store persistent data between turns, but only up to a maximum of 1kb per bot
* You may not overwrite anybody else's bot
* If you output an invalid move, your bot will sit still. If you output an invalid action, your bot will do nothing.
* Please stick to common languages that can be run on a OSX or Linux box.

Controller code can be found here.

## Initial results:

```
Average of 15 rounds:
---------------------
81 Farmer
56 CautiousBot
42 GetOff
41 Visigoth
40 DontBurnMeBro
37 FireFighter
35 Pyro
11 Protector

```

**Update**: Added Farmer, CautiousBot, GetOff, FireFighter, and Pyro.

# Answer
> 5 votes
# Visigoth

Visigoth tries to burn its enemies to the ground. It hopes to do this before anyone else gets to its land.

Run: `python visigoth.py`

```
#!/usr/bin/python

''' Charge the enemy and burn them to the ground. '''

import sys

data = sys.stdin.readlines()

startx, starty, x, y = [int(i) for i in data[0:4]]
field = [list(i) for i in data[4:]]

otherbots = []
for i in range(32):
    for j in range(32):
        if field[i][j]=='@': #bot
            if i!=y and j!=x:
                otherbots.append([j,i])

min_bot = otherbots[0]
for bot in otherbots:
    if abs(bot[0]-x)+abs(bot[1]-y) < abs(min_bot[0]-x)+abs(min_bot[1]-y):
        min_bot = bot

dx = min_bot[0]-x
dy = min_bot[1]-y

if abs(dy)>abs(dx):
    if dy>0:
        move = 'U'
    else:
        move = 'D'
else:
    if dx>0:
        move = 'R'
    elif dx<0:
        move = 'L'
    else:
        move = 'S'

if max(abs(x-startx), abs(y-starty))>4:
    if 0<x<31 and 0<y<31:
        dirs = {'U':(-1,0), 'D':(1,0), 'L':(0,-1), 'R':(0,1)}
        for i in dirs:
            if field[dirs[i][0]][dirs[i][1]] in ('.', 'W'):
                action = 'B'+i
                break
        else:
            # No free land nearby, go out in a blaze of glory
            action = 'BS'
    else:
        action = 'BS'
else:
    # Don't set own field on fire
    action = 'XS'

print move+action

```

This is my first entry, constructive criticism is appreciated!

# Answer
> 4 votes
# Java, Protector

Attempts to surround his field with a fence of ash.

**Edit:** Improved logic a bit. Probably won't make a difference.

```
import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

/**
 * Created 10/6/15
 *
 * @author TheNumberOne
 */
public class Protecter {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Point start = new Point(in.nextInt(), in.nextInt());
        Point current = new Point(in.nextInt(), in.nextInt());
        in.nextLine();
        String output = "";
        char[][] board = new char[32][];
        for (int i = 0; i < 32; i++){
            board[i] = in.nextLine().toCharArray();
        }
        List<Point> danger = new ArrayList<>();
        List<Point> close = new ArrayList<>();
        List<Point> closeDanger = new ArrayList<>();
        List<Point> fence = new ArrayList<>();
        for (int i = 0; i < 32; i++){
            for (int j = 0; j < 32; j++){
                Point p = new Point(i, j);
                char c = board[j][i];
                if (Math.abs(p.x - start.x) < 10 && Math.abs(p.y - start.y) < 10){
                    if ((c + "").matches("\\d")){
                        danger.add(p);
                    }
                }
                if (distance(current, p) == 1){
                    close.add(p);
                }
                if ((Math.abs(p.x - start.x) == 10 || Math.abs(p.y - start.y) == 10) && !(c + "").matches("#|\\d|@")){
                    fence.add(p);
                }
            }
        }
        closeDanger = new ArrayList<>(danger);
        closeDanger.retainAll(close);
        danger.sort(Comparator.comparingInt(a -> distance(current, a) / (board[a.y][a.x] - '0')));
        if (danger.size() > 0){
            output += moveTo(current, danger.get(0));
        } else {
            fence.sort(Comparator.comparingInt(a -> distance(current, a)));
            if (fence.size() == 0){
                output += "S";
            } else {
                output += moveTo(current, fence.get(0));
            }
        }
        closeDanger.sort(Comparator.comparingInt(a -> board[a.y][a.x] - '0'));
        if (closeDanger.size() > 0){
            output += "P";
            output += moveTo(current, closeDanger.get(0));
        } else {
            if (danger.size() == 0) {
                List<Point> closeFence = new ArrayList<>(fence);
                closeFence.retainAll(close);
                if (closeFence.size() > 0) {
                    output += "B";
                    output += moveTo(current, closeFence.get(0));
                } else {
                    if (!fence.contains(current)){
                        output += "PS";
                    } else {
                        output += "BS";
                    }
                }
            } else {
                if (!fence.contains(current)){
                    output += "PS";
                } else {
                    output += "BS";
                }
            }
        }
        System.out.println(output);
    }

    private static String moveTo(Point from, Point to) {
        if (from.x > to.x){
            return "L";
        }
        if (from.x < to.x){
            return "R";
        }
        if (from.y > to.y){
            return "U";
        }
        if (from.y < to.y){
            return "D";
        }
        return "S";
    }

    private static int distance(Point p1, Point p2){
        return Math.abs(p1.x - p2.x) + Math.abs(p2.y - p1.y);
    }

}

```

Place in a file named `Protector.java`.

Compile with: `javac Protector.java`
Run with: `java Protector`

# Answer
> 2 votes
# DontBurnMeBro

Another Python entry. Guaranteed not to be the first to die (I think).

```
#!/usr/bin/python

print "SPS"

```

# Answer
> 2 votes
# Pyro, python

Pyro likes fire. Pyro loves fire. Pyro lives in fire. I'm thinking "Pyro from TF2". Pyro likes to burn things. He won't burn his own territory, but he will try to get out of it, using a simple "pathfinding" algorithm.

import sys
import random
inpu          = sys.stdin.readlines()
ox,oy,x,y     = [int(i) for i in inpu[0:4]]
board         = [list(i) for i in inpu[4:]]
adjacentcells = [[[board[y+b][x+c],b,c] for b in range(-1,2)] for c in range(-1,2)]
action        = ""
infield=max(abs(ox-x),abs(oy-y))<=9
# let's find out what Pyro will do!
if not infield: # Pyro won't burn what's in his field.
    for row in adjacentcells:
        for entry in row:
            cell,a,b=entry
            if(a!=b):   # Can't act on these cells.
                if cell==".":   # burn it!!!!!!
                    action = "B"
                    if(a==0):
                        direction = {-1:"L",1:"R"}[b]
                    else:
                        direction = {-1:"D",1:"U"}[a]
            if action: break;
        if action: break;
    # Pyro doesn't care where he goes, so long as
    # Pyro's not in the field of Pyro.
    move = random.choice("LRUDS")
else:   # Thought Pyro hates water, Pyro must protect SOMETHING.
    action    = "P"
    direction = "S"
    # get the direction towards the center
    # Pyro will move away from ox and oy to
    # towards the center, if in the field.
    # Pyro will do this by first going right/left,
    # then going up/down. (This behaviour is
    # removed when he leaves his field.)
    cx = cy = 16
    while max(abs(cx-x),abs(cy-y))<=9:
        cx = random.randint(0,31)
        cy = random.randint(0,31)
    if(cx-x>0): #is to the left of the center
        move = "R"
    elif(cx-x<0): #is to the right of the cenetr
        move = "L"
    elif(cy-y>0): # is above center
        move = "D"
    elif(cy-y<0): # is below center
        move = "U"
    else:   # is at center (something went wrong!)
        move   = "S"
        action = "B"
if not move:
    move = "S"
if not action:
    action = "B"
if not direction:
    direction = "S"
print(move+action+direction)

""" Here, have a face!
MMMMMMMMMMMMMMMMMMMMMMMdyo/:-.````.:+sdMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMNs/....----...``````.omMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMh/``..-://+//:-..````````/mMMMMMMMMMMM
MMMMMMMMMMMMMMMm:````..-:////:--..``````````sMMMMMMMMMM
MMMMMMMMMMMMMMs```````....--....`````````````/NMMMMMMMM
MMMMMMMMMMMMM/````````````````````````````````:NMMMMMMM
MMMMMMMMMMMM/```......``````````````````.......+mMMMMMM
MMMMMMMMMMMo.:::::::::::-````````````.-:::::::::/+yNMMM
MMMMMMMMMNs:-..-------::::.`````````://:-------..-:/hMM
MMMMMMMMm+:..---:::::---:::.```````::::---:::::--.`-/sM
MMMMMMMN+:`.---:::/:/:---:::``````.:::.--:::/:/:--.`:/h
MMMMMMMh:-`---://o+///:---::.`````-::---://oo///:--..:+
MMMMMMMs:..--:/+/sss+//:-.::.`````-::.-://+osyo//:-.-::
MMMMMMMs:----///+sosso/:--::``````.::.-://+oosso+:-.::/
MMMMMMMd:::-:/++/osyso+/--::```````::-://+/osyso+/--::s
MMMMMMMMs:/::::+ooos+o+/:::.```````.::::/+ooos/o+/:/:+N
MMMMMMMMMs://:+osooo+o+/::.``.....``.:/:/osoos+o+//:+mM
MMMMMMMMMM--:/++ysyoo+/:-...........`.-:/+ssso++/:-yNMM
MMMMMMMMMMs``.-:://::-..`.....---....``..--::::-.`.MMMM
MNNMddhyys+-.```````````...--:::::-...````````````+MMMM
////.-:///:-..``````````.:///++o/o+/:/.```````````yMMMM
---.`.-:::--..`````````..+//+ooo+++///.```````````mMMMM
/.--``..--...``````````..--:/+oo+/:--..``````````.MMMMM
s --.```...````````````...--/+++++/-...````````.`/MMMMM
d .--```````````````````...-::::::-...````````.-/+MMMMM
M.`--`  ````````````````....------....````````.-/.dMMMM
M+ .-.  `````````````````.:::::::::::.`````````.-sMMMMM
Mm``--`  ``````````````-://///////////:-````````/MMMMMM
MM: --.  ````````````.://::--......-::///-``````yMMMMMM
MMd`.-.  ``````````.:/::-..-:::::::.``-::::.````NMMMMMM
MMM+.--`  `````````:::-.-::-.......-::-`--::```+MMMMMMM
MMMN---`  ````````.--..:-.```````````..-`.--.``dMMMMMMM
MMMMd--.` `````..`.-.`-````````````````.-`...`/MMMMMMMM
MMMMMNh+ss/oydNMd``.`.`````````````````````.`.NMMMMMMMM
MMMMMMMMMMMMMMMMMd.``.```````````````````````dMMMMMMMMM
MMMMMMMMMMMMMMMMMMm:```````````````````````-dMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMy.```````````````````.oNMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMNs-```````````````:sNMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMmy+:-.````.:+ymMMMMMMMMMMMMMMMM
"""

# Answer
> 2 votes
## GetOff, Python

GetOff just wants to keep his land for himself, and he's not afraid to chase those damn bots all over his land, squirting them with his water gun until they leave. While its property is not being violated, it makes tries its best to make sure his land doesn't get burned.

```
#!/usr/bin/env python

import sys

fire = ['1','2','3','4','5','6']

move = ''
ad = ''

data = sys.stdin.readlines()

startx, starty, x, y = [int(i) for i in data[0:4]]
board = [list(i) for i in data[4:]]

top = starty-4
bottom = starty+5
right = startx+5
left = startx-4

bots = []
for i in range(32):
    for j in range(32):
        if board[i][j]=='@':
            if i != y and j != x:
                bots.append([j,i])

fires = []
for i in range(32):
    for j in range(32):
        if board[i][j] in fire: #fire
            fires.append([j,i])

for bot in bots:
    if left < bot[0] < right and top < bot[1] < bottom: # if there's a bot in the field
        if bot[0] > x:
            move = 'R'
        elif bot[0] < x:
            move = 'L'
        elif bot[1] > y:
            move = 'D'
        elif bot[1] < y:
            move = 'U'
        else:
            move = 'S'
    else:
        nearest_fire = []
        for f in fires:
            if left < f[0] < right and top < f[1] < bottom:
                if nearest_fire == []:
                    nearest_fire = f
                elif (f[0]-x)+(f[1]-y) < (nearest_fire[0]-x)+(nearest_fire[1]-y):
                    nearest_fire = f
        if nearest_fire == []:
            move = 'S'
        else:
            if nearest_fire[0] > x:
                move = 'R'
            elif nearest_fire[0] < x:
                move = 'L'
            elif nearest_fire[1] > y:
                move = 'D'
            elif nearest_fire[1] < y:
                move = 'U'
            else:
                move = 'S'

if board[x-1][y] in fire: # position immediately to the left
    ad = 'L'
elif board[x+1][y] in fire: # position immediately to the right
    ad = 'R'
elif board[x][y-1] in fire: # position immediately up
    ad = 'U'
elif board[x][y+1] in fire: # position immediately down
    ad = 'D'
else:
    ad = 'S'

print(move+'P'+ad)

```

# Answer
> 2 votes
# Farmer, Java

The farmer only cares about his crops. He constantly watches his field for possible fires or invaders.

```
import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Farmer {

    public static void main(String[] args) {
        //row == y
        //col == x
        Scanner in = new Scanner(System.in);
        Point start = new Point(in.nextInt(), in.nextInt());
        Point current = new Point(in.nextInt(), in.nextInt());
        in.nextLine();
        char[][] board = new char[32][];
        for (int row = 0; row < 32; row++){
            board[row] = in.nextLine().toCharArray();
        }
        final List<Point> firesInField = new ArrayList<>();
        final List<Point> enemiesInField = new ArrayList<>();
        for (int row = 0; row < 32; row++) {
            for (int col = 0; col < 32; col++) {
                Point p = new Point(col, row);
                if (!isInField(start, p))
                    continue;
                char c = board[row][col];
                if (isFire(c)) {
                    firesInField.add(p);
                } else if (c == '@' && col != current.x && row != current.y) {
                    enemiesInField.add(p);
                }
            }
        }
        List<Point> destinations = firesInField.size() > 0 ? firesInField : enemiesInField;

        if (destinations.size() > 0) {
            //take short paths to eliminate more fires
            destinations.sort(Comparator
                    .comparingInt((Point p) -> distance(p, current))
                    .thenComparingInt(p -> -1 * (board[p.y][p.x] - '0')));
            Point dest = destinations.get(0);
            print(moveTo(current, dest), "P", moveTo(current, dest));
        }

        //TODO start fires if an enemy has more intact ground

        //walk back to center
        print(moveTo(current, start), "P", moveTo(current, start));
    }

    private static void print(String move, String action, String actionMove) {
        System.out.println(move + action + actionMove);
        System.exit(0);
    }

    private static boolean isInField(Point centerOfField, Point toTest) {
        //add one extra, to prevent fires that are very near
        return distance(centerOfField, toTest) <= 10 && Math.abs(centerOfField.x - toTest.x) <= 5 && Math.abs(centerOfField.y - toTest.y) <= 5;
    }

    private static boolean isFire(char c) {
        return c == '1' || c == '2' || c == '3' || c == '4' || c == '5' || c == '6';
    }

    private static String moveTo(Point from, Point to) {
        if (from.x > to.x){
            from.x--;
            return "L";
        }
        if (from.x < to.x){
            from.x++;
            return "R";
        }
        if (from.y > to.y){
            from.y--;
            return "U";
        }
        if (from.y < to.y){
            from.y++;
            return "D";
        }
        return "S";
    }

    private static int distance(Point p1, Point p2){
        return Math.abs(p1.x - p2.x) + Math.abs(p2.y - p1.y);
    }
}

```

# Answer
> 1 votes
# FireFighter, Java

Fights *all* fires.

```
import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

/**
 * Created 10/7/15
 *
 * @author TheNumberOne
 */
public class FireFighter {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Point start = new Point(in.nextInt(), in.nextInt());
        Point current = new Point(in.nextInt(), in.nextInt());
        in.nextLine();
        String output = "";
        char[][] board = new char[32][];
        for (int i = 0; i < 32; i++) {
            board[i] = in.nextLine().toCharArray();
        }

        List<Point> danger = new ArrayList<>();
        List<Point> close = new ArrayList<>();
        List<Point> closeDanger;
        for (int i = 0; i < 32; i++){
            for (int j = 0; j < 32; j++){
                Point p = new Point(i, j);
                char c = board[j][i];
                if ((c + "").matches("\\d")){
                    danger.add(p);
                }
                if (distance(current, p) == 1){
                    close.add(p);
                }
            }
        }
        closeDanger = new ArrayList<>(danger);
        closeDanger.retainAll(close);

        Comparator<Point> comparator = Comparator.comparingInt((Point a) -> board[a.y][a.x]).reversed();

        danger.sort(comparator);
        danger.sort(Comparator.comparingInt(a -> distance(start, a)));
        if (danger.size() > 0){
            output += moveTo(current, danger.get(0));
        } else {
            output += moveTo(current, start);
        }
        closeDanger.sort(comparator);
        if (closeDanger.size() > 0){
            output += "P" + moveTo(current, closeDanger.get(0));
        } else {
            output += "PS";
        }
        System.out.println(output);
    }

    private static String moveTo(Point from, Point to) {
        if (from.x > to.x){
            return "L";
        }
        if (from.x < to.x){
            return "R";
        }
        if (from.y > to.y){
            return "U";
        }
        if (from.y < to.y){
            return "D";
        }
        return "S";
    }

    private static int distance(Point p1, Point p2){
        return Math.abs(p1.x - p2.x) + Math.abs(p2.y - p1.y);
    }

}

```

# Answer
> 0 votes
# Keeper, Python 2

```
import sys

Out = ["S", "P", "S"]

StX = int(sys.stdin.readline()) - 1
StY = int(sys.stdin.readline()) - 1
NowX = int(sys.stdin.readline()) - 1
NowY = int(sys.stdin.readline()) - 1
Map = []
for i in range(32):
    Map.append(sys.stdin.readline())

Pos = [NowX, NowY]
Area = [[StX, StY]]
for x in range(StX-4, StX+4):
    for y in range(StY-4, StY+4):
        Area.append([x, y])

Fires = []
for y in range(32):
    for x in range(32):
        if Map[y][x] in "123456":
            Fires.append([x, y])

Danger = []
for Tile in Area:
    if Map[Tile[1]][Tile[0]] in "123456":
        Danger.append(Tile)

Distance = {}
i = -1
for Fire in Danger:
    i += 1
    Distance[(Pos[0] - Fire[0], Pos[1] - Fire[1])] = i

i = min(Distance)
Closest = Danger[Distance[i]]

if Closest[0] > Pos[0]:
    Out[0] = Out[2] = "R"
    Pos[0] += 1
if Closest[0] < Pos[0]:
    Out[0] = Out[2] = "L"
    Pos[0] -= 1
if Closest[0] == Pos[0]:
    if Closest[1] > Pos[1]:
        Out[0] = Out[2] = "D"
        Pos[1] += 1
    if Closest[1] < Pos[1]:
        Out[0] = Out[2] = "U"
        Pos[1] -= 1

if Closest[0] + 1 == Pos[0] and Closest[1] == Pos[1]:
    Out[2] = "L"
if Closest[0] - 1 == Pos[0] and Closest[1] == Pos[1]:
    Out[2] = "R"
if Closest[1] + 1 == Pos[1] and Closest[0] == Pos[0]:
    Out[2] = "U"
if Closest[1] - 1 == Pos[1] and Closest[0] == Pos[0]:
    Out[2] = "D"
if Closest[0] == Pos[0] and Closest[1] == Pos[1]:
    Out[2] = "S"

print "".join(Out)

```

Could be simplified, but I'm tired.

The Keeper tries to keep its field from harm. If a fire appears, it hurries over to it and puts it out as fast as it can.

I may add accommodation for incoming fires as well.

# Answer
> 0 votes
# CautiousBot, Node.js (ES5)

This bot goes out and tries to set fire to other bots' land. It even sits on top of the fire for 3 ticks to hide it! However, one can never be too cautious, so it always makes sure it is close enough to put out any fires on its own land.

Notes:

* Uses a state file called `state.json` stored in its working directory, used to store information about other bots' initial positions and to determine how long to hide a started fire. *This must be deleted once the round is over (eg, when some bot has won).* Otherwise the bot will be confused on the next round. (Let me know if this breaks rules.)
* Requires the `split` module.

```
#!/usr/bin/env node

// imports
var fs       = require("fs");
var splitmod = require("split");

// variables
var startX, startY, currentX, currentY, board = [], state = {};
var DEBUG = false;

// utility functions
function debug(){
    if(DEBUG) console.log.apply(console, arguments);
}

// calculates manhattan distance which is also the number of turns it will take to get somewhere
function manhattan(x1, y1, x2, y2){
    return Math.abs(x2 - x1) + Math.abs(y2 - y1);
}

// calculates chebyshev distance (mostly used for determining if a bot is within someone's plot)
function chebyshev(x1, y1, x2, y2){
    return Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1));
}

// gets the board character at x, y
function get(x, y){
    return board[y][x];
}

function readState(){
    try {
        state = JSON.parse(fs.readFileSync('state.json').toString());
        debug("Opened state file");
    } catch(e){
        // it must be the first turn
        createState();
    }
}

function writeState(){
    fs.writeFileSync('state.json', JSON.stringify(state));
    debug("Wrote state file");
}

// finds out where all the other bots are
function getBotPositions(){
    var positions = [];
    for(var x = 0; x < 32; x++){
        for(var y = 0; y < 32; y++){
            if(get(x, y) == '@' && x != currentX && y != currentY){
                positions.push({x: x, y: y});
            }
        }
    }
    return positions;
}

function createState(){
    debug("Creating state");
    // take a loot at where other bots are to record their land locations
    var botLands = getBotPositions();
    state['botLands'] = botLands;

    state['turn'] = 0; // which turn is it?
    state['lastFireTurn'] = -999; // which turn was the last one where this bot set a fire?
}

// finds whether a plot of land (defined by its center) has fire on it
function isLandBurning(x, y){
    for(var dx = -4; dx < 5; dx++){
        for(var dy = -4; dy < 5; dy++){
            if(get(x + dx, y + dy).match(/[1-6]/) != null) return true;
        }
    }
    return false;
}

// finds the fire with the highest number (and therefore the one to put out first)
function findFire(x, y){
    var highestNum = 0;
    var fire = {x: x, y: y};
    for(var dx = -4; dx < 5; dx++){
        for(var dy = -4; dy < 5; dy++){
            if(get(x + dx, y + dy).match(/[1-6]/) != null){
                var num = parseInt(get(x + dx, y + dy));
                if(num > highestNum){
                    highestNum = num;
                    fire = {x: x + dx, y: y + dy};
                }
            }
        }
    }
    return fire;
}

// figures out where to go to get somewhere
function getDirection(x1, y1, x2, y2){
    var direction = 'S';
    var cycx = Math.abs(y2 - y1) / Math.abs(x2 - x1);

    if(cycx < 1){
        if(x2 > x1) direction = 'R';
        if(x2 < x1) direction = 'L';
    } else {
        if(y2 > y1) direction = 'D';
        if(y2 < y1) direction = 'U';
    }

    debug("Getting direction", x1, y1, x2, y2, "result", direction);

    return direction;
}

// read input
var dataCycle = 0;
process.stdin.pipe(splitmod()).on('data', function(line){
    switch(dataCycle){
    case 0:
        startX = parseInt(line);
        break;
    case 1:
        startY = parseInt(line);
        break;
    case 2:
        currentX = parseInt(line);
        break;
    case 3:
        currentY = parseInt(line);
        break;
    default:
        board.push(line);
    }

    dataCycle++;
}).on('end', function(){
    // main bot code
    readState();
    state['turn']++;
    debug("It is turn", state['turn']);

    // get bot positions
    var botPositions = getBotPositions();

    var action = {type:'X', direction:'S'};
    var move   = 'S';

    var isMyLandBurning = isLandBurning(startX, startY);
    if(isMyLandBurning){ // hurry over there ASAP!
        debug("Bot land is burning!");
        var pos = findFire(startX, startY);
        debug("Fire found at", pos);
        move = getDirection(currentX, currentY, pos.x, pos.y);
        // simulate the move and figure out if/where to dump the water
        var newX = currentX + (move == 'R') - (move == 'L');
        var newY = currentY + (move == 'D') - (move == 'U');
        if(chebyshev(newX, newY, pos.x, pos.y) < 5){
            // on its own land, start dropping water like a madman
            debug("Dropping water");
            action.type = 'P';

            // if it can put out the target fire, then do that
            if(manhattan(newX, newY, pos.x, pos.y) == 1) action.direction = getDirection(newX, newY, pos.x, pos.y);
            // it's not in range of the target fire, so use the time to put out other fires
            // if it's moving on top of a fire, put that out
            else if(get(newX, newY).match(/[1-6]/) != null) action.direction = 'S';
            // if there's a fire around it then put that out
            else if(get(newX + 1, newY).match(/[1-6]/) != null) action.direction = 'R';
            else if(get(newX - 1, newY).match(/[1-6]/) != null) action.direction = 'L';
            else if(get(newX, newY + 1).match(/[1-6]/) != null) action.direction = 'D';
            else if(get(newX, newY - 1).match(/[1-6]/) != null) action.direction = 'U';
            else action.direction = 'S';
        }
    } else {
        // are there any bots that could start a fire when this bot is 6+ tiles away?
        var headBack = false;
        for(var i = 0; i < botPositions.length; i++){
            var otherBot = botPositions[i];
            var dist = manhattan(otherBot.x, otherBot.y, startX, startY) - 4;
            var myDist = manhattan(currentX, currentY, startX, startY);
            if(dist + 6 < myDist){
                headBack = true;
                break;
            }
        }
        if(headBack){ // they're probably up to no good
            debug("Bots are dangerously close, heading back");
            move = getDirection(currentX, currentY, startX, startY);
        } else if(state['turn'] - state['lastFireTurn'] < 3) { // no bots near own plot, time to consider other options
            debug("Hiding fire");
            // sneakily hide the fire if one was set :)
        } else { // last option is to go find land to burn
            debug("Finding land to burn");
            var closestX = 999, closestY = 999;
            for(var i = 0; i < state.botLands.length; i++){
                var otherLand = state.botLands[i];
                if(!isLandBurning(otherLand.x, otherLand.y) && chebyshev(currentX, currentY, otherLand.x, otherLand.y) > 4){ // find someone to burn
                    // use [-3, 3] here because on the first turn, the bots could have moved before this bot had a chance to see them
                    // meaning that the [-3, 3] region is the only one that is guaranteed to be on their land
                    for(var dx = -3; dx < 4; dx++){
                        for(var dy = -3; dy < 4; dy++){
                            var type = get(otherLand.x + dx, otherLand.y + dy);
                            var distThere = manhattan(currentX, currentY, otherLand.x + dx, otherLand.y + dy);
                            var distShortest = manhattan(currentX, currentY, closestX, closestY);
                            // find normal land, or wet land that will dry by the time the bot gets to it
                            if((type == '.' || type == '@' || (type == 'W' && distThere > 1)) && distThere < distShortest){
                                closestX = otherLand.x + dx;
                                closestY = otherLand.y + dy;
                            }
                        }
                    }
                }
            }
            if(closestX != 999 && closestY != 999){ // land found; go there
                debug("Target acquired", closestX, closestY);
                debug("Burning land");
                move = getDirection(currentX, currentY, closestX, closestY);
                if(move == 'S'){ // is it on the land? If so, then burn it
                    action.type = 'B';
                    action.direction = 'S';
                    state['lastFireTurn'] = state['turn']; // record when the fire was set
                }
            } else { // everyone else's land already has a fire
                debug("Default action");
                // default to heading back; one can never be too safe!
                move = getDirection(currentX, currentY, startX, startY);
            }
        }
    }

    // save the state file
    writeState();
    // output the action
    console.log(move + action.type + action.direction);
});

```

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


# Question
Title: Curse you Turing!!! Make a partial halting solver that yells at Turing when he tries to break it
Here goes a quick proof by Alan Turing that there is no program `H` that can solve the halting problem. If there was, you could make a program `X` such that `X(n) = if H(n,n) == Halt then output X(n) else output ":-)"`. What is the value of `H(X,X)`?

Your job is to make a partial halting solver, such that when some `X` of your choice is inputted, your program will output "Curse you Turing!!!" repeatedly.

Specifically, you will make two programs in the same programming language. One will be `H`, the partial halting solver. Given a program `P` (in the same programming language) and an input, H will:

* output "halts" if `P` halts
* output "no halts" if `P` doesn't halt
* If `P` is program `X` (with input `X`), output "Curse you Turing!!!" infinitely, on different lines.
* If `H` isn't `X`, and `H` can't figure out if `P` halts, go into an infinite loop without output.

Program `X`, will be given an input `n`, and then it will check `H(n,n)`. If it outputs "not halts", it will terminate at some point. For any other result of `H(n,n)`, it will go into an infinite loop. The output of `X` is unimportant.

`H` and `X` will not have access to external resources. Specifically, that means that there is a mutual-quine-aspect to this problem.

As to how hard `H` has to try to figure out whether a program halts:

* Once it determines that its input isn't `X` and `X`, it will run the program with the input for 10 seconds. If it terminates (either correctly or with error) it will output "halts".
* You must identify an infinite number of "no halts" programs.

Oh, and this may be go without saying, but the programming language needs to be Turing complete (I knew you were thinking of an esoteric language without infinite loops. Sorry.) (That said, Turing complete subsets of languages are also okay.)

Your score is the number of bytes in `H`. Least number of bytes wins!

Bonuses:

* -50 bytes: If `H` captures output from its input program, and reoutputs it but with "PROGRAM OUTPUT: " in front of every line. (This is only done when `H` runs the program to test it.)
* -20 bytes: If `H` outputs "halts" based on criteria other than time as well.

Try and find a fun combination of `H` and `X` calls to put together to make it interesting (like `H(H,(X,X))` or even more crazy stuff.)

# Answer
> 2 votes
# Mathematica, ~~140~~ ~~138~~ 127 bytes

```
H=(While[#==#2[[1]]=="While[#~H~{#}==\"halts\"]&",Print@"Curse you Turing!!!"];TimeConstrained[#=="#&"||ToExpression@#@@#2;"halts",10,"no halts"])&

```

Defines a function `H` that takes a function string and argument list as arguments. This also receives the -20 bonus, with the extra criteria being that if the program is `#&`, then it halts. This is to show that it is flawed. Here is the `X`:

```
While[#~H~{#}=="halts"]&

```

---
Tags: code-golf, math, quine
---