# Knock down walls in a maze

### Rules:

In this game you start at the top of a rectangular grid of size N x M made up of walls and open spaces. The input is N lines of M characters, where a . specifies an open space and a x specifies a wall. Your program should output the smallest number K such that there exists a path from the top left corner to the bottom right corner (no diagonals) that crosses K walls.

For example, given the input:

..x..
..x..
xxxxx
..x..
..x..


your program should output 2.

### Other examples:

output 4:

xxxxx
x.x.x
x.x.x
x..xx


output 0:

.xxxxxxxx
.x...x...
.x.x.x.x.
.x.x...x.
...xxxxx.


output 6:

xx
xx
xx
xx
xx


### Extra tidbits:

If it makes your life easier, you can specify N and M as command line parameters.

Extra credit if you can have your program print out the path in some form or another.

• :yawn: Dijkstra, with a heap which is a V[2][] and a counter. – Peter Taylor Aug 22 '11 at 7:11
• @Peter Taylor But how short can you make that code? – migimaru Aug 23 '11 at 15:17

## Ruby 1.9 (235)(225)(222) (214)

I don't know if this is shorter than a program based on Dijkstra, but I figured I would try a different approach. This uses regex in a loop to mark each space with the minimal number of walls required to reach it.

w=".{#{/\s/=~s=$<.read}}?" j="([.x])" s[0]=v=s[0]<?x??0:?1 (d=v[-1];n=v.succ![-1] 0while(s.sub!(/#{j}(#{w+d})/m){($1<?x?d: n)+$2}||s.sub!(/(#{d+w})#{j}/m){$1+($2<?x?d: n)}))while/#{j}/=~q=s[-2] p v.to_i-(q==n ?0:1)  Input is specified as a file on the command line, i.e. > ruby1.9.1 golf.rb maze.txt  Ungolfed: # read in the file maze =$<.read

# find the first newline (the width of the maze)
width = /\s/ =~ maze

# construct part of the regex (the part between the current cell and the target cell)
spaces = ".{#{width}}?"

# construct another part of the regex (the target cell)
target = "([.x])"

# set the value of the first cell, and store that in the current wall count
maze[0] = walls = (maze[0] == "x" ? "1" : "0")

# loop until the goal cell is not "." or "x"
while /#{target}/ =~ (goal = s[-2])

# store the current wall count digit and the next wall count digit, while incrementing the wall count
current = walls[-1]; next = walls.succ![-1]

# loop to set all the reachable cells for the current wall count
begin

# first regex handles all cells above or to the left of cells with the current wall count
result = s.sub!(/#{target}(#{spaces + current})/m) {
($1 == 'x' ? next : current) +$2
}

# second regex handles all cells below or to the right of cells with the current wall count
result = result || s.sub!(/(#{current + spaces})#{target}/m) {
$1 + ($2 == 'x' ? next : current)
}
end while result != nil
end

# we reached the goal, so output the wall count if the goal was a wall, or subtract 1 if it wasn't
puts walls.to_i - (goal == next ? 0 : 1)


## Perl 5.10 (164)

undef$/;$_=<>;/\n/;$s="(.{$-[0]})?";substr$_,0,1,($n=/^x/||0);
until(/\d$/){1while s/([.x])($s$n)/$n+($1eq x).$2/se
+s/$n$s\K[.x]/$n+($&eq x)/se;$n++} /.$/;print"\$&\n"


Very much along the same lines as migimaru's solution, only with that extra Perl touch. 5.10 is needed for \K in s///.

• Does this properly handle mazes that require passing through more than 9 walls? – migimaru Aug 25 '11 at 4:35
• @migimaru No. I could get it up to 45 or so with only a modest increase in characters, and up to a nearly-unlimited number with another small increase -- but it wouldn't be quite as pretty. – hobbs Aug 25 '11 at 14:04

Python 406 378 360 348 418 chars

import sys
d={}
n=0
for l in open(sys.argv[1]):
i=0
for c in l.strip():m=n,i;d[m]=c;i+=1
n+=1
v=d[0,0]=int(d[0,0]=='x')
X=lambda *x:type(d.get(x,'.'))!=str and x
N=lambda x,y:X(x+1,y)or X(x-1,y)or X(x,y+1)or X(x,y-1)
def T(f):s=[(x,(v,N(*x))) for x in d if d[x]==f and N(*x)];d.update(s);return s
while 1:
while T('.'):pass
v+=1
if not T('x'):break
P=[m]
s,p=d[m]
while p!=(0,0):P.insert(0,p);x,p=d[p]
print s, P


Simplified Dijkstra, since moves with weight are on x field. It is done in "waves", first loop with finding . fields touching front and set them on same weight, than once find x fields touching front and set them on +1 weight. Repeat while there are no more unvisited fields.

At the end we know weight for every field.

Input is specified as a file on the command line:

python m.py m1.txt


Update: prints path.

C++ version (610 607 606 584)

#include<queue>
#include<set>
#include<string>
#include<iostream>
#include<memory>
#define S second
#define X s.S.first
#define Y s.S.S
#define A(x,y) f.push(make_pair(s.first-c,make_pair(X+x,Y+y)));
#define T typedef pair<int
using namespace std;T,int>P;T,P>Q;string l;vector<string>b;priority_queue<Q>f;set<P>g;Q s;int m,n,c=0;int main(){cin>>m>>n;getline(cin,l);while(getline(cin,l))b.push_back(l);A(0,0)while(!f.empty()){s=f.top();f.pop();if(X>=0&&X<=m&&Y>=0&&Y<=n&&g.find(s.S)==g.end()){g.insert(s.S);c=b[X][Y]=='x';if(X==m&&Y==n)cout<<-(s.first-c);A(1,0)A(-1,0)A(0,1)A(0,-1)}}}


Implements Dijkstra's algorithm.

Un-golfed:

#include<queue>
#include<set>
#include<string>
#include<iostream>
#include<memory>

using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>Q;

int main()
{
int             m,n;
string          line;
vector<string>  board;

cin >> m >> n;getline(cin,l);
while(getline(cin,line))
{
board.push_back(line);
}

priority_queue<Q>   frontList;
set<P>              found;
frontList.push(make_pair(0,make_pair(0,0)));
while(!frontList.empty())
{
Q s=frontList.top();
frontList.pop();
if(   s.second.first>=0
&& s.second.first<=m
&& s.second.second>=0
&& s.second.second<=n
&& found.find(s.second)==found.end()
)
{
found.insert(s.second);
int c=board[s.second.first][s.second.second]=='x';
if(  s.second.first==m
&& s.second.second==n
)
{   cout<<-(s.first-c);
}
frontList.push(make_pair(s.first-c,make_pair(s.second.first+1,s.second.second)));
frontList.push(make_pair(s.first-c,make_pair(s.second.first-1,s.second.second)));
frontList.push(make_pair(s.first-c,make_pair(s.second.first,s.second.second+1)));
frontList.push(make_pair(s.first-c,make_pair(s.second.first,s.second.second-1)));
}
}
}