11
\$\begingroup\$

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.

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

4 Answers 4

3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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///.

\$\endgroup\$
2
  • \$\begingroup\$ Does this properly handle mazes that require passing through more than 9 walls? \$\endgroup\$
    – migimaru
    Aug 25, 2011 at 4:35
  • \$\begingroup\$ @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. \$\endgroup\$
    – hobbs
    Aug 25, 2011 at 14:04
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)));
        }
    }
}
\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.