views:

6851

answers:

28
+117  Q: 

Code Golf: Lasers

The challenge

The shortest code by character count to input a 2D representation of a board, and output 'true' or 'false' according to the input.

The board is made out of 4 types of tiles:

 # - A solid wall
 x - The target the laser has to hit
 / or \ - Mirrors pointing to a direction (depends on laser direction)
 v, ^, > or < - The laser pointing to a direction (down, up, right and left respectively)

There is only one laser and only one target. Walls must form a solid rectangle of any size, where the laser and target are placed inside. Walls inside the 'room' are possible.

Laser ray shots and travels from its origin to the direction it's pointing. If a laser ray hits the wall, it stops. If a laser ray hits a mirror, it bounces 90 degrees to the direction the mirror points to. Mirrors are two sided, meaning both sides are 'reflective' and may bounce a ray in two ways. If a laser ray hits the laser (^v><) itself, it is treated as a wall (laser beam destroys the beamer and so it'll never hit the target).

Test cases

Input:
    ##########
    #   / \  #
    #        #
    #   \   x#
    # >   /  #
    ########## 
Output:
    true

Input:
    ##########
    #   v x  #
    # /      #
    #       /#
    #   \    #
    ##########
Output:    
    false

Input:
    #############
    #     #     #
    # >   #     #
    #     #     #
    #     #   x #
    #     #     #
    #############
Output:
    false

Input:
    ##########
    #/\/\/\  #
    #\\//\\\ #
    #//\/\/\\#
    #\/\/\/x^#
    ##########
Output:
    true

Code count includes input/output (i.e full program).

+26  A: 

F#, 36 lines, very readable

Ok, just to get an answer out there:

let ReadInput() =
    let mutable line = System.Console.ReadLine()
    let X = line.Length 
    let mutable lines = []
    while line <> null do
        lines <- Seq.to_list line :: lines
        line <- System.Console.ReadLine()
    lines <- List.rev lines
    X, lines.Length, lines

let X,Y,a = ReadInput()
let mutable p = 0,0,'v'
for y in 0..Y-1 do
    for x in 0..X-1 do 
        printf "%c" a.[y].[x]
        match a.[y].[x] with 
        |'v'|'^'|'<'|'>' -> p <- x,y,a.[y].[x]
        |_ -> ()
    printfn ""

let NEXT = dict [ '>', (1,0,'^','v')
                  'v', (0,1,'<','>')
                  '<', (-1,0,'v','^')
                  '^', (0,-1,'>','<') ]
let next(x,y,d) =
    let dx, dy, s, b = NEXT.[d]
    x+dx,y+dy,(match a.[y+dy].[x+dx] with
               | '/' -> s
               | '\\'-> b
               | '#'|'v'|'^'|'>'|'<' -> printfn "false"; exit 0
               | 'x' -> printfn "true"; exit 0
               | ' ' -> d)

while true do
    p <- next p

Samples:

##########
#   / \  #
#        #
#   \   x#
# >   /  #
##########
true

##########
#   v x  #
# /      #
#       /#
#   \    #
##########
false

#############
#     #     #
# >   #     #
#     #     #
#     #   x #
#     #     #
#############
false

##########
#/\/\/\  #
#\\//\\\ #
#//\/\/\\#
#\/\/\/x^#
##########
true

##########
#   / \  #
#        #
#/    \ x#
#\>   /  #
##########
false

##########
#  /    \#
# / \    #
#/    \ x#
#\^/\ /  #
##########
false
Brian
I CAN ACTUALLY READ THIS ONE! MIRACULOUS!
Jeff Atwood
I have to *scroll* to read this one! ;)
hobbs
Java/C# code golf is counted by lines not characters. That's the handicap.
Nathan Feger
@Feger, That's depressing.
strager
@strager its not depressing in 3 years when you're hired in to maintain the code and the original developer has long since left.
Nathan Feger
I pity the fool who is paid to maintain code golf entries.
recursive
This fails using F# in Visual Studio 2010. Seq.to_list doesnt exist (ok, changed it to toList), and then Line 25, incomplete pattern matching.
Russell
Yes, change to_list to toList now. The incomplete match warning is fine; it's code golf, so I didn't do code like: | _ -> failwith "impossible"
Brian
Cool, thanks Brian. My bad - just doesnt run in interactive mode (console.REadLine())
Russell
+32  A: 

C89 (209 characters)

#define M(a,b)*p==*#a?m=b,*p=1,q=p:
*q,G[999],*p=G;w;main(m){for(;(*++p=getchar())>0;)M(<,-1)M
(>,1)M(^,-w)M(v,w)!w&*p<11?w=p-G:0;for(;q+=m,m=*q&4?(*q&1?
-1:1)*(m/w?m/w:m*w):*q&9?!puts(*q&1?"false":"true"):m;);}

Explanation

This monstrosity will probably be difficult to follow if you don't understand C. Just a forewarning.

#define M(a,b)*p==*#a?m=b,*p=1,q=p:

This little macro checks if the current character (*p) is equal to whatever a is in character form (*#a). If they are equal, set the movement vector to b (m=b), mark this character as a wall (*p=1), and set the starting point to the current location (q=p). This macro includes the "else" portion.

*q,G[999],*p=G;
w;

Declare some variables. * q is the light's current location. * G is the game board as a 1D array. * p is the current read location when populating G. * w is the board's width.

main(m){

Obvious main. m is a variable storing the movement vector. (It's a parameter to main as an optimization.)

    for(;(*++p=getchar())>0;)

Loop through all characters, populating G using p. Skip G[0] as an optimization (no need to waste a character writing p again in the third part of the for).

        M(<,-1)
        M(>,1)
        M(^,-w)
        M(v,w)

Use the aforementioned macro to define the lazer, if possible. -1 and 1 correspond to left and right, respectively, and -w and w up and down.

        !w&*p<11
            ?w=p-G
            :0;

If the current character is an end-of-line marker (ASCII 10), set the width if it hasn't already been set. The skipped G[0] allows us to write w=p-G instead of w=p-G+1. Also, this finishes off the ?: chain from the M's.

    for(;
        q+=m,

Move the light by the movement vector.

        m=
        *q&4
            ?(*q&1?-1:1)*(
                m/w?m/w:m*w
            )

Reflect the movement vector.

            :*q&9
                ?!puts(*q&1?"false":"true")
                :m
        ;

If this is a wall or x, quit with the appropriate message (m=0 terminates the loop). Otherwise, do nothing (noop; m=m)

    );
}
strager
Ugh! I was working on a C solution when the fire alarm sounded in my apartment complex. Now I got beat.Nice solution though.
rlbond
@rlbond, Oh wow. O_o
strager
Methinks using a temp variable for your swap and swap/negation steps would save you a couple of characters.
Artelius
@Artelius, Yeah, I realized that, and a few other things. Thanks.
strager
Sneaking in 1 under the perl. Nice.
dmckee
I love the simplicity of this. I'm a lousy C golfer but I enjoy seeing one well done. `cpp` is almost as abusable as perl. :)
hobbs
This just keeps getting better.
mobrule
TCC actually doesn't like the untyped declarations and errors out with `g.c:3: declaration expected` :(
Mark Rushakoff
Just content yourself with the fact that mine depends on *megabytes* of C to get anywhere, whereas yours is nearly self-contained. With that in mind, a result within 15% is excellent. You've also cut far more over the past day than I have. :)
hobbs
@hobbs, Thanks. =] Still working on this... Praying for sub-216.
strager
What's 216? Just 6^3?
hobbs
256-32-8... i.e. 11011000b
strager
Is it legal in C to declare `main` as only taking one parameter? It would make some amount of sense, but it's rather useless (except in golf).
Chris Lutz
@Lutz, It is legal C89, yes.
strager
It would be an implementation defined signature then. But it's certainly not portable, then :) But you really have to put "int" before the global variable declarations :) Or at least a storage specifier like "static". But i would use "int" because it's only 3 chars. But in your loops you can save one char i think by using `while` instead of `for` loops :) So all in all, i think you will be 1 char wider in the end.
Johannes Schaub - litb
And i think you can get completely rid of "puts(char*);". C89 has the implicit function declaration rule, which will take your char* resulting from the string literals just fine. So, actually with all these three changes, your character count will shrink by `11` xD
Johannes Schaub - litb
Johannes Schaub - litb
Taking two parameters would basically make his code two characters longer. And if he wanted to be really evil, he could probably use the second parameter to replace one of his globals. And after checking, yes, you can get rid of puts(char*), as any non-varargs function that returns int can be implicitly declared.
Chris Lutz
Chris Lutz keep in mind that the other parameter will have type "int". So to make it "char**", he has to go to great length, like "main(m,n)char**n;{....}" not really nice -.- So i would just stick to "main(m)" if i were him xD
Johannes Schaub - litb
On `while`: I can't believe I missed that. =X On `puts`: I thought if a function isn't declared it is assumed to accept `int` as parameters and return `int`. I'll have to check. If I'm right, `char *` would cast to `int` then be interpreted as `char *` which may cause portability problems.
strager
It's implicitly declared as "extern int name();" - i.e prototype-less. So if you pass a `char*`, the function receives a `char*` :)
Johannes Schaub - litb
@strager ah hold on, i think miscounted. `while` doesn't seem to save characters -.-
Johannes Schaub - litb
@litb - Ah, I forgot about that part. Would anything terrible happen if he let it be declared as an `int` anyway? The `char **` data would be cast to an `int` but he'd never try to cast it back to a `char **` because he could just use it fairly safely as one of his `int` variables. Or is this breaking too many standards?
Chris Lutz
@chris it's just UB. i'm sure it would work anyway but i'm trying to write non-UB programs even when golfing xD
Johannes Schaub - litb
Removing `puts`'s declaration helped, but not enough to bring it under 170. 209 is pretty good, though, so I think I'll leave it at that. Thanks for your help, guys. I really appreciate it. =] (Anything to dethrone those Perl witches!)
strager
I've got a C solution that sneaks in under 200 characters (uses some similar ideas and variable names to this one) - down here: http://stackoverflow.com/questions/1480023/code-golf-lasers/1491580#1491580
caf
Replace `(m/w?m/w:m*w)` with `w/m` to bring it to 199 characters.
Artelius
+6  A: 

c (K&R) 339 necessary characters after more suggestions from strager.

The physicist in me noted that the propagation and reflection operations are time-reversal invariant, so this version, throws rays from the target and checks to see if the arrive at the laser emitter.

The rest of the implementation is very straight forward and is taken more or less exactly from my earlier, forward going effort.

Compressed:

#define R return
#define C case
#define Z x,y
int c,i,j,m[99][99],Z;s(d,e,Z){for(;;)switch(m[x+=d][y+=e]){C'^':R 1==e;
C'>':R-1==d;C'v':R-1==e;C'<':R 1==d;C'#':C'x':R 0;C 92:e=-e;d=-d;C'/':c=d;
d=-e;e=-c;}}main(){while((c=getchar())>0)c==10?i=0,j++:(c==120?x=i,y=j:
i,m[i++][j]=c);puts(s(1,0,Z)|s(0,1,Z)|s(-1,0,Z)|s(0,-1,Z)?"true":"false");}

Uncompressed(ish):

#define R return
#define C case
#define Z x,y
int c,i,j,m[99][99],Z;
s(d,e,Z)
{
  for(;;)
    switch(m[x+=d][y+=e]){
    C'^': 
      R 1==e;
    C'>': 
      R-1==d;
    C'v': 
      R-1==e;
    C'<': 
      R 1==d;
    C'#':
    C'x':
      R 0;
    C 92:
      e=-e;
      d=-d;
    C'/':
      c=d;
      d=-e;
      e=-c;
    }
}
main(){
  while((c=getchar())>0)
    c==10?i=0,j++:
      (c==120?x=i,y=j:i,m[i++][j]=c);
  puts(s(1,0,Z)|s(0,1,Z)|s(-1,0,Z)|s(0,-1,Z)?"true":"false");
}

There is no input validation, and bad input can send it into an infinite loop. Works properly with input no larger than 99 by 99. Requires a compiler that will link the standard library without including any of the headers. And I think I'm done, strager has me beat by a considerable stretch, even with his help.

I'm rather hoping someone will demonstrate a more subtle way to accomplish the task. There s nothing wrong with this, but it is not deep magic.

dmckee
No need for `=0` on the globals as they are initialized to 0 by default. Replace character constants with their equivalent in decimal. Use `>0` instead of `!=EOF` to check against EOF (and `\0`). You can probably `#define` away some of the code in the `case` like I did with `if`'s. No need for the extra `\n` in the `puts` as `puts` must print a newline anyway. `for(;;)` is shorter than `while(1)`. Hope this helps. =]
strager
@strager: Thanks. I always come at these iteratively, because I don't think that way...
dmckee
`"There is no input validation"` - There shouldn't be any. To make it easy on golfers, input is assumed to always be 'clean' unless otherwise specified.
LiraNuna
@dmckee, Don't worry, us Code Golf pros work iteratively as well. However, we generally use some tricks right from the start (like half the ones I mentioned), but that comes with experience. =]
strager
Unless I'm counting wrong, the program is 390 characters, not 380.
strager
Checking up on me our you? I must have mis-keyed or something, 'cause you're right.
dmckee
`x+=d;y+=e;switch(m[x][y])` can be turned into `switch(m[x+=d][y+=e])`. `R d==-1;` can be turned into `R-1==d`. The `while` doesn't require `{}`, and the `?:` in the loop can be inverted using `c-10` instead of `c==10` as the condition. You can save a few characters (I think) by moving `m[i++][j]=c` to the third part of the `for` loop. Recursion *may* be shorter, too.
strager
+1 for 'time-reversal invariant'
Justicle
+12  A: 

F#, 255 chars (and still rather readable!):

Ok, after a night's rest, I improved this a lot:

let a=System.Console.In.ReadToEnd()
let w,c=a.IndexOf"\n"+1,a.IndexOfAny[|'^';'<';'>';'v'|]
let rec n(c,d)=
 let e,s=[|-w,2;-1,3;1,0;w,1|].[d]
 n(c+e,match a.[c+e]with|'/'->s|'\\'->3-s|' '->d|c->printfn"%A"(c='x');exit 0)
n(c,"^<>v".IndexOf a.[c])

Let's talk through it line by line.

First, slurp all the input into a big one-dimensional array (2D arrays can be bad for code golf; just use a 1D array and add/subtract the width of one line to the index to move up/down a line).

Next we compute 'w', the width of an input line, and 'c', the starting position, by indexing into our array.

Now let's define the 'next' function 'n', which takes a current position 'c' and a direction 'd' which is 0,1,2,3 for up,left,right,down.

The index-epsilon 'e' and the what-new-direction-if-we-hit-a-slash 's' are computed by a table. For example, if the current direction 'd' is 0 (up), then the first element of the table says "-w,2" which means we decrement the index by w, and if we hit a slash the new direction is 2 (right).

Now we recurse into the next function 'n' with (1) the next index ("c+e" - current plus epsilon), and (2) the new direction, which we compute by looking ahead to see what's in the array in that next cell. If the lookahead char is a slash, the new direction is 's'. If it's a backslash, the new direction is 3-s (our choice of encoding 0123 makes this work). If it's a space, we just keep going in the same direction 'd'. And if it's any other character 'c', then the game ends, printing 'true' if the char was 'x' and false otherwise.

To kick things off, we call the recursive function 'n' with the initial position 'c' and the starting direction (which does the initial encoding of direction into 0123).

I think I can probably still shave a few more characters off it, but I am pretty pleased with it like this (and 255 is a nice number).

Brian
You can edit your original answer.
LiraNuna
+68  A: 

Perl, 166 160 characters

Perl, 251 248 246 222 214 208 203 201 193 190 180 176 173 170 166 --> 160 chars.

Solution had 166 strokes when this contest ended, but A. Rex has found a couple ways to shave off 6 more characters:

s!.!$t{$s++}=$&!ge,$s=$r+=99for<>;%d='>.^1<2v3'=~/./g;($r)=grep$d|=$d{$t{$_}},%t;
{$_=$t{$r+=(1,-99,-1,99)[$d^=3*/\\/+m</>]};/[\/\\ ]/&&redo}die/x/?true:false,$/

The first line loads the input into %t, a table of the board where $t{99*i+j} holds the character at row i,column j. Then,

%d=split//,'>.^1<2v3' ; ($r)=grep{$d|=$d{$t{$_}}}%t

it searches the elements of %t for a character that matches > ^ < or v, and simultaneously sets $d to a value between 0 and 3 that indicates the initial direction of the laser beam.

At the beginning of each iteration in the main loop, we update $d if the beam is currently on a mirror. XOR'ing by 3 gives the correct behavior for a \ mirror and XOR'ing by 1 gives the correct behavior for a / mirror.

$d^=3*/\\/+m</>

Next, the current position $r is updated accoring to the current direction.

$r+=(1,-99,-1,99)[$d] ; $_ = $t{$r}

We assign the character at the current position to $_ to make convenient use of the match operators.

/[\/\\ ]/ && redo

Continue if we are on a blank space or a mirror character. Otherwise we terminate true if we are on the target ($_ =~ /x/) and false otherwise.

Limitation: may not work on problems with more than 99 columns. This limitation could be removed at the expense of 3 more characters,

mobrule
Nooo, you're beating me! =[
strager
Okay, got to 323 characters. =D
strager
At your newest: that'd be near impossible to defeat in C. =[
strager
*"if we can assume that the input is smaller than 99 x 99"* Hey, I did. Fragile solutions are pretty common in code golf. Extra points if you can avoid it.
dmckee
I can change 99 to 1E5 to make it very robust at the expense of 3 chars.
mobrule
Your best solution would be more noticeable at the top of the post.
strager
180? Well *that's* quite interesting. And I thought I was done!
hobbs
Lol now looks like we got a new winner eh? xD
Johannes Schaub - litb
You should explain that the for loop's setup changes the laser emitter to a wall so that you can test for false by hitting a wall only. Or you could remove the 10 characters and add 6 characters to your test. 176?
dlamblin
I don't think I'm going to beat you. I'm going to suspend work on mine unless some rubyista gets ahead of me. Congrats. :)
hobbs
But using regular expressions to rotate the board? That was sick. That's like an automatic 20 stroke bonus.
mobrule
166. Oh my. No way I'm cutting more than fifty characters from my solution. =]
strager
Congratulations on getting the shortest answer within the unspecified time span. =]
strager
NOOO!!! Must. beat. Perl. solution :) That is just amazing right there.
Mike Spross
@strager: 'unspecified time span' - All of my code golf were Thursday to Monday. It's called a 'weekend'
LiraNuna
@mobrule: Save six strokes: reorder the first line as `s!.!$t{$s++}=$`, change `%d=split//,.." to `%d=..=~/./g`, and change `grep{..}%t` to `grep..,%t`
A. Rex
Thanks A. Rex -- those are more great suggestions.
mobrule
+15  A: 

353 chars in Ruby:

314 277 chars now!

OK, 256 chars in Ruby and now I'm done. Nice round number to stop at. :)

247 chars. I can't stop.

223 203 201 chars in Ruby

d=x=y=-1;b=readlines.each{|l|d<0&&(d="^>v<".index l[x]if x=l.index(/[>^v<]/)
y+=1)};loop{c=b[y+=[-1,0,1,0][d]][x+=[0,1,0,-1][d]]
c==47?d=[1,0,3,2][d]:c==92?d=3-d:c==35?(p !1;exit):c<?x?0:(p !!1;exit)}

With whitespace:

d = x = y = -1
b = readlines.each { |l|
  d < 0 && (d = "^>v<".index l[x] if x = l.index(/[>^v<]/); y += 1)
}

loop {
  c = b[y += [-1, 0, 1, 0][d]][x += [0, 1, 0, -1][d]]

  c == 47 ? d = [1, 0, 3, 2][d] :
  c == 92 ? d = 3 - d :
  c == 35 ? (p !1; exit) :
  c < ?x ? 0 : (p !!1; exit)
}

Slightly refactored:

board = readlines

direction = x = y = -1
board.each do |line|
  if direction < 0
    x = line.index(/[>^v<]/)
    if x
      direction = "^>v<".index line[x]
    end
    y += 1
  end
end

loop do
  x += [0, 1, 0, -1][direction]
  y += [-1, 0, 1, 0][direction]

  ch = board[y][x].chr
  case ch
  when "/"
    direction = [1, 0, 3, 2][direction]
  when "\\"
    direction = 3 - direction
  when "x"
    puts "true"
    exit
  when "#"
    puts "false"
    exit
  end
end
yjerem
But... you can rename `ch` to `C` or any other 1 char letter to save 2 characters!
LiraNuna
Ok ok, fine... I actually realized that that whole variable is unnecessary as I only use it once. This and a couple other improvements whittled it down to 247 chars.
yjerem
No `i++` (instead of `i+=1`) ?
LiraNuna
Nope. You can do ++i, but it just makes it really really as positive as it used to be.
DigitalRoss
I like the compressed version: #;p
SeanJA
You can save a few more characters by changing `puts "true"` to `puts !!0` and `puts "false"` to `puts !0`
Mike Spross
Oops. Never mind. If I read it more carefully, I would've realized the "refactored" version was there for the sake of showing a readable version.
Mike Spross
A: 

Perl 219
My perl version is 392 342 characters long (I had to handle the case of the beam hitting the laser):
Update, thanks Hobbs for reminding me of tr//, it's now 250 characters:
Update, removing the m in m//, changing the two while loops brought a few savings; there's now only one space required.
(L:it;goto L is the same length as do{it;redo}):

@b=map{($y,$x,$s)=($a,$-[0],$&)if/[<>^v]/;$a++;[split//]}<>;L:$_=$s;$x++if/>/;
$x--if/</;$y++if/v/;$y--if/\^/;$_=$b[$y][$x];die"true\n"if/x/;die"false\n"if
/[<>^v#]/;$s=~tr/<>^v/^v<>/if/\\/;$s=~tr/<>^v/v^></if/\//;goto L

I shaved some, but it barelyjust competes with some of these, albeit late.
It looks a little better as:

#!/usr/bin/perl
@b = map {
    ($y, $x, $s) = ($a, $-[0], $&) if /[<>^v]/;
    $a++;
    [split//]
} <>;
L:
    $_ = $s;
    $x++ if />/;
    $x-- if /</;
    $y++ if /v/;
    $y-- if /\^/;
    $_ = $b[$y][$x];
    die "true\n"  if /x/;
    die "false\n" if /[<>^v#]/;
    $s =~ tr/<>^v/^v<>/ if /\\/;
    $s =~ tr/<>^v/v^></ if /\//;
goto L

Well... Honestly this should be self explanatory if you understand that the @b is an array arrays of characters in each line, and can read the simple regexp and tr statements.

dlamblin
Did you say Perl? Wow!
NTDLS
Tip: you can shorten your mirror code way up. `$_=$s;tr/^v<>/<>^v/` and `$_=$s;tr/v^<>/<>^v/` respectively. Also, you don't need the `m` in `m//`.
hobbs
Sorry, make that second one `$_=$s;tr/v^></<>^v/;`
hobbs
You still have several `if m/.../` that could be `if/.../` saving two characters a pop.
hobbs
You can use `y///` instead of `tr///` to save two characters.
Platinum Azure
+10  A: 

Python

294 277 253 240 232 characters including newlines:

(the first character in lines 4 and 5 is a tab, not spaces)

l='>v<^';x={'/':'^<v>','\\':'v>^<',' ':l};b=[1];r=p=0
while b[-1]:
 b+=[raw_input()];r+=1
 for g in l:
    c=b[r].find(g)
    if-1<c:p=c+1j*r;d=g
while' '<d:z=l.find(d);p+=1j**z;c=b[int(p.imag)][int(p.real)];d=x.get(c,' '*4)[z]
print'#'<c

I had forgotten Python even had optional semicolons.

How it works

The key idea behind this code is using complex numbers to represent positions and directions. The rows are the imaginary axis, increasing downward. The columns are the real axis, increasing to the right.

l='>v<^'; a list of the laser symbols. The order is chosen so that the index of a laser direction character corresponds with a power of sqrt(-1)

x={'/':'^<v>','\\':'v>^<',' ':l}; a transformation table determining how the direction changes when the beam leaves different tiles. The tile is the key, and new directions are the values.

b=[1]; holds the board. The first element is 1 (evaluates as true) so that the while loop will run at least once.

r=p=0 r is the current row number of the input, p is the current position of the laser beam.

while b[-1]: stop loading board data when raw_input returns an empty string

b+=[raw_input()];r+=1 append the next line of input to the board and increment the row counter

for g in l: guess each laser direction in turn

c=b[r].find(g) set the column to the location of the laser or -1 if it's not in the line (or is pointing in a different direction)

if-1<c:p=c+1j*r;d=g if we found a laser, then set the current position p and direction d. d is one of the chars in l

After loading the board into b, the current position p and direction d have been set to those of the laser source.

while' '<d: space has a lower ASCII value than any of the direction symbols, so we use it as a stop flag.

z=l.find(d); index of the current direction char in the l string. z gets used later to both determine the new beam direction using the x table, and to increment the position.

p+=1j**z; increment the position using a power of i. For example, l.find('<')==2 -> i^2 = -1, which would move to the left one column.

c=b[int(p.imag)][int(p.real)]; read the char at the current position

d=x.get(c,' '*4)[z] look up the new direction for the beam in the transformation table. If the current char doesn't exist in the table, then set d to space.

print'#'<c print false if we stopped on anything other than the target.

Theran
`p+=1j**z`: That is sweet.
dmckee
not very pythonic...
nbv4
@dmckee: no, it is insane
Andrea Ambu
+14  A: 

This is was a direct port of Brian's solution to C#3, minus the console interactions. This isn't an entry in the challenge since it isn't a complete program, I was just wondering how some of the F# constructs he used could be represented in C#.

bool Run(string input) {
    var a = input.Split(new[] {Environment.NewLine}, StringSplitOptions.None);
    var p = a.SelectMany((line, y) => line.Select((d, x) => new {x, y, d}))
             .First(x => new[] {'v', '^', '<', '>'}.Contains(x.d));
    var NEXT = new[] {
            new {d = '>', dx = 1, dy = 0, s = '^', b = 'v'},
            new {d = 'v', dx = 0, dy = 1, s = '<', b = '>'},
            new {d = '<', dx = -1, dy = 0, s = 'v', b = '^'},
            new {d = '^', dx = 0, dy = -1, s = '>', b = '<'}
        }.ToDictionary(x => x.d);
    while (true) {
        var n = NEXT[p.d];
        int x = p.x + n.dx,
            y = p.y + n.dy;
        var d = a[y][x];
        switch (d) {
            case '/':  d = n.s; break;
            case '\\': d = n.b; break;
            case ' ':  d = p.d; break;
            default: return d == 'x';
        }
        p = new {x, y, d};
    }
}

Edit: After some experimentation, the following rather verbose search code:

int X = a[0].Length, Y = a.Length;
var p = new {x = 0, y = 0, d = 'v'};
for (var y = 0; y < Y; y++) {
    for (var x = 0; x < X; x++) {
        var d = a[y][x];
        switch (d) {
            case 'v': case '^': case '<': case '>':
                p = new {x, y, d}; break;
        }
    }
}

has been replaced with some much more compact LINQ to Objects code:

var p = a.SelectMany((line, y) => line.Select((d, x) => new {x, y, d}))
         .First(x => new[] {'v', '^', '<', '>'}.Contains(x.d));
Nathan Baulch
omg. What a nice example to demonstrate how mighty linq and c# have become. 1+ for I am a huge c# fan. x)
Emiswelt
+70  A: 

Perl, 177 Characters

The first linebreak can be removed; the other two are mandatory.

$/=%d=split//,' >/^\v';$_=<>;$s='#';{
y/v<^/>v</?do{my$o;$o.=" 
"while s/.$/$o.=$&,""/meg;y'/\\'\/'for$o,$s;$_=$o}:/>x/?die"true
":/>#/?die"false
":s/>(.)/$s$d{$1}/?$s=$1:1;redo}

Explanation:

$/ = %d = (' ' => '>', '/' => '^', '\\' => 'v');

If a right-moving beam runs into an {empty space, up-angled mirror, down-angled mirror} it becomes a {right-moving beam, up-moving beam, down-moving beam}. Initialize $/ along the way -- fortunately "6" is not a valid input char.

$_ = <>;

Read the board into $_.

$s="#";

$s is the symbol of whatever the beam is sitting on top of now. Since the laser emitter is to be treated like a wall, set this to be a wall to begin with.

if (tr/v<^/>v</) {
  my $o;
  $o .= "\n" while s/.$/$o .= $&, ""/meg;
  tr,/\\,\\/, for $o, $s;
  $_ = $o;
}

If the laser beam is pointing any way except right, rotate its symbol, and then rotate the whole board in place (also rotating the symbols for the mirrors). It's a 90 degree left rotation, accomplished effectively by reversing the rows while transposing rows and columns, in a slightly fiendish s///e with side effects. In the golfed code, the tr is written in the form y''' which allows me to skip backslashing one backslash.

die "true\n" if />x/; die "false\n" if />#/;

Terminate with the right message if we hit the target or a wall.

$s = $1 if s/>(.)/$s$d{$1}/;

If there's an empty space in front of the laser, move forward. If there's a mirror in front of the laser, move forward and rotate the beam. In either case, put the "saved symbol" back into the old beam location, and put the thing we just overwrote into the saved symbol.

redo;

Repeat until termination. {...;redo} is two characters less than for(;;){...} and three less than while(1){...}.

hobbs
Rotate the board... Crazy. Regexp... Crazier. O_o
strager
The rotate works by transposing rows with columns, and then reversing the rows... a reflection across y=x and then a reflection across y=0 gives a rotation (plus a translation if this is geometry, but it's not; it's Perl). Actually I'm pretty sure I just figured out how to shave a couple more chars. :)
hobbs
You... You monster!
LiraNuna
LiraNuna: I choose to take that as a compliment.
hobbs
The golf is over. How can you beat rotating a 2D board with regular expressions?!
Konrad Rudolph
Is this solution correct? I get an output of false on the first test case.
mobrule
@mobrule, Here too...
strager
For what it's worth, it's not *just* a regex. The substitution runs in a `while` loop, the `/g` modifier adds another loop over the matches in the string, and the `/e` modifier allows running code for each match. That's nested loops, right there. It's just a lot happens implicitly. That said it's the bit I'm proudest of, and (if you check the revision history) the bit that took the most work to get right.
hobbs
@mobrule: will check. I'll admit to not having run every test case through the last couple changes. :)
hobbs
@mobrule, @strager: It was a desync between my local code and what was posted here. Fixed and tests seem to work. No change in character count.
hobbs
@hobbs, Okay, at least it's fixed now. =] My C solution is slowly approaching 204...
strager
You can get to 199:1. Change `undef$/` to `$/=z` (or any other char that won't be in the input)2. Change `tr,,,` to the old school `y,,,`3. Remove semicolon after `$s=$1`
mobrule
Many thanks. I always forget `y///`! With 200 cracked, I'm going to bed :)
hobbs
this is my favorite thing ever.
anthony
I wanna beat you but I don't know how. ;D
strager
`%d=split//,' >/^\v'` is shorter than `%d=(' ',qw(> / ^ \ v)`
mobrule
Right you are again. I thought of `unpack"C*"` which was longer -- somehow, split didn't cross my mind :)
hobbs
Arg. This is getting more and more difficult for me. =]
strager
wtf? perl programmers are wizards.
Johannes Schaub - litb
@litb, Help me with my C solution!
strager
@strager, if i only could. Your code is already so terse. well done! xD
Johannes Schaub - litb
Wow, that's really great. Funnily enough, I had to try to write a transpose expression in perl golf here. I tried something like yours, but changed to "@_=/.{80}/g; {say map{chop||die}@_;redo}". I wonder if your way would work there better as well, or if what I wrote could be adapted to non-outputting.
`\n` to explicit newlines shaves 3 char. Can you say `my$o` instead of `$o=""`? The best Ruby solution is at 184 now.
mobrule
This is awesome, yes. Who'd have guess that you could rotate the board in less characters than it takes to check the beam direction for movement and reflection. But oddly there's a shorter solution at 180 chars.
dlamblin
Made those changes and a few others and I'm at 182, but I was hoping to lose 3 more chars before I posted :)
hobbs
http://xkcd.com/224/
JStriedl
Sir, you have divideth and conquereth. I salute thee!
Ates Goral
+6  A: 

House of Mirrors

Not an actual entry to the challenge, but I wrote a game based on this concept (not too long back).

It's written in Scala, open-source and available here:

It does a little bit more; deals with colors and various types of mirrors and devices, but version 0.00001 did exactly what this challenge asks. I have lost that version though and it was never optimised for character count anyway.

HRJ
Would it be possible for you to upload a compiled version that works under Windows without having to install scala?
milan1612
Nevermind - I wanted to try out Scala anyway...
milan1612
There is a version with Scala libraries included. Look at the list of downloads. But anyway, if you have installed Scala by now, I am glad I got you to do that :)
HRJ
+1  A: 

C#

1020 characters.
1088 characters (added input from console).
925 characters (refactored variables).
875 characters (removed redundant Dictionary initializer; changed to Binary & operators)

Made a Point not to look at anyone else's before posting. I'm sure it could be LINQ'd up a bit. And the whole FindLaser method in the readable version seems awfully fishy to me. But, it works and it's late :)

Note the readable class includes an additional method that prints out the current Arena as the laser moves around.

class L{static void Main(){
A=new Dictionary<Point,string>();
var l=Console.ReadLine();int y=0;
while(l!=""){var a=l.ToCharArray();
for(int x=0;x<a.Count();x++)
A.Add(new Point(x,y),l[x].ToString());
y++;l=Console.ReadLine();}new L();}
static Dictionary<Point,string>A;Point P,O,N,S,W,E;
public L(){N=S=W=E=new Point(0,-1);S.Offset(0,2);
W.Offset(-1,1);E.Offset(1,1);D();
Console.WriteLine(F());}bool F(){
var l=A[P];int m=O.X,n=O.Y,o=P.X,p=P.Y;
bool x=o==m,y=p==n,a=x&p<n,b=x&p>n,c=y&o>m,d=y&o<m;
if(l=="\\"){if(a)T(W);if(b)T(E);if(c)T(S);
if(d)T(N);if(F())return true;}
if(l=="/"){if(a)T(E);if(b)T(W);if(c)T(N);
if(d)T(S);if(F())return true;}return l=="x";}
void T(Point p){O=P;do P.Offset(p);
while(!("\\,/,#,x".Split(',')).Contains(A[P]));}
void D(){P=A.Where(x=>("^,v,>,<".Split(',')).
Contains(x.Value)).First().Key;var c=A[P];
if(c=="^")T(N);if(c=="v")T(S);if(c=="<")T(W);
if(c==">")T(E);}}

Readable Version (not quite the final golf version, but same premise):

class Laser
{
    private Dictionary<Point, string> Arena;
    private readonly List<string> LaserChars;
    private readonly List<string> OtherChars;

    private Point Position;
    private Point OldPosition;
    private readonly Point North;
    private readonly Point South;
    private readonly Point West;
    private readonly Point East;

    public Laser( List<string> arena )
    {
        SplitArena( arena );
        LaserChars = new List<string> { "^", "v", ">", "<" };
        OtherChars = new List<string> { "\\", "/", "#", "x" };
        North = new Point( 0, -1 );
        South = new Point( 0, 1 );
        West = new Point( -1, 0 );
        East = new Point( 1, 0 );
        FindLaser();
        Console.WriteLine( FindTarget() );
    }

    private void SplitArena( List<string> arena )
    {
        Arena = new Dictionary<Point, string>();
        int y = 0;
        foreach( string str in arena )
        {
            var line = str.ToCharArray();
            for( int x = 0; x < line.Count(); x++ )
            {
                Arena.Add( new Point( x, y ), line[x].ToString() );
            }
            y++;
        }
    }

    private void DrawArena()
    {
        Console.Clear();
        var d = new Dictionary<Point, string>( Arena );

        d[Position] = "*";
        foreach( KeyValuePair<Point, string> p in d )
        {
            if( p.Key.X == 0 )
                Console.WriteLine();

            Console.Write( p.Value );
        }
        System.Threading.Thread.Sleep( 400 );
    }

    private bool FindTarget()
    {
        DrawArena();

        string chr = Arena[Position];

        switch( chr )
        {
            case "\\":
                if( ( Position.X == Position.X ) && ( Position.Y < OldPosition.Y ) )
                {
                    OffSet( West );
                }
                else if( ( Position.X == Position.X ) && ( Position.Y > OldPosition.Y ) )
                {
                    OffSet( East );
                }
                else if( ( Position.Y == Position.Y ) && ( Position.X > OldPosition.X ) )
                {
                    OffSet( South );
                }
                else
                {
                    OffSet( North );
                }
                if( FindTarget() )
                {
                    return true;
                }
                break;
            case "/":
                if( ( Position.X == Position.X ) && ( Position.Y < OldPosition.Y ) )
                {
                    OffSet( East );
                }
                else if( ( Position.X == Position.X ) && ( Position.Y > OldPosition.Y ) )
                {
                    OffSet( West );
                }
                else if( ( Position.Y == Position.Y ) && ( Position.X > OldPosition.X ) )
                {
                    OffSet( North );
                }
                else
                {
                    OffSet( South );
                }
                if( FindTarget() )
                {
                    return true;
                }
                break;
            case "x":
                return true;
            case "#":
                return false;
        }
        return false;
    }

    private void OffSet( Point p )
    {
        OldPosition = Position;
        do
        {
            Position.Offset( p );
        } while( !OtherChars.Contains( Arena[Position] ) );
    }

    private void FindLaser()
    {
        Position = Arena.Where( x => LaserChars.Contains( x.Value ) ).First().Key;

        switch( Arena[Position] )
        {
            case "^":
                OffSet( North );
                break;
            case "v":
                OffSet( South );
                break;
            case "<":
                OffSet( West );
                break;
            case ">":
                OffSet( East );
                break;
        }
    }
}
Metro Smurf
The program should take input. Most commonly from stdin.
LiraNuna
+3  A: 

I believe in Code Reuse, I'd use one of your code as an API :).

  puts Board.new.validate(input)

32 characters \o/... wohoooo

Rishav Rastogi
that's a double bogey!
Jeff Atwood
Golf is just too boring. :)
Rishav Rastogi
Beat you to it:p Board.new.validate input26 characters \o/
Yaraher
Lol man xD This solution is awesome
sinisterff
+8  A: 

C# 3.0

259 chars

bool S(char[]m){var w=Array.FindIndex(m,x=>x<11)+1;var s=Array.FindIndex(m,x=>x>50&x!=92&x<119);var t=m[s];var d=t<61?-1:t<63?1:t<95?-w:w;var u=0;while(0<1){s+=d;u=m[s];if(u>119)return 0<1;if(u==47|u==92)d+=d>0?-w-1:w+1;else if(u!=32)return 0>1;d=u>47?-d:d;}}

Slightly more readable:

bool Simulate(char[] m)
{
    var w = Array.FindIndex(m, x => x < 11) + 1;
    var s = Array.FindIndex(m, x => x > 50 & x != 92 & x < 119);
    var t = m[s];
    var d = t < 61 ? -1 : t < 63 ? 1 : t < 95 ? -w : w;
    var u = 0;
    while (0 < 1)
    {
        s += d;
        u = m[s];
        if (u > 119)
            return 0 < 1;
        if (u == 47 | u == 92)
            d += d > 0 ? -w - 1 : w + 1;
        else if (u != 32)
            return 0 > 1;
        d = u > 47 ? -d : d;
    }
}

The main waste of chars seems to be in finding the width of the map and the position of the laser source. Any ideas how to shorten this?

Noldorin
I'm not sure if this shorter but it's my shot at finding the laser and finding width: using L=List<string>;using P=System.Drawing.Point;using L=List<string>;L r=new L(){"v","<",">","^"};P p=new P();r.ForEach(a =>{int c = 0;v.ForEach(s =>{c++;if(s.IndexOf(a)!=-1){p.X=s.IndexOf(a);p.Y= c;}});});int l=v[0].Length; v is a List<string> containing the table, and it outputs a Point representing laser position + an int representing width
RCIX
better:using L=List<string>;L l=new L(4){"v", "<", ">", "^" };var point=new{x=0,y=0};int c=0;l.ForEach(a=>{m.ForEach(s=>{if(s.IndexOf(a)!=-1){point=new{x=s.IndexOf(a),y=c};}});c++;});int w=m[0].Length;
RCIX
still, don't think that's smaller...
RCIX
Problems asks for a full program, not a function.
strager
+4  A: 

Haskell, 395 391 383 361 339 characters (optimized)

Still uses a generic state machine, rather than anything clever:

k="<>^v"
o(Just x)=x
s y(h:t)=case b of{[]->s(y+1)t;(c:_)->(c,length a,y)}where(a,b)=break(flip elem k)h
r a = f$s 0 a where f(c,x,y)=case i(a!!v!!u)"x /\\"["true",g k,g"v^><",g"^v<>"]of{Just r->r;_->"false"}where{i x y=lookup x.zip y;j=o.i c k;u=j[x-1,x+1,x,x];v=j[y,y,y-1,y+1];g t=f(j t,u,v)}
main=do{z<-getContents;putStrLn$r$lines z}

A readable version:

k="<>^v"    -- "key" for direction
o(Just x)=x -- "only" handle successful search
s y(h:t)=case b of  -- find "start" state
  []->s(y+1)t
  (c:_)->(c,length a,y)
 where (a,b)=break(flip elem k)h
r a = f$s 0 a where -- "run" the state machine (iterate with f)
 f(c,x,y)=case i(a!!v!!u)"x /\\"["true",g k,g"v^><",g"^v<>"] of
   Just r->r
   _->"false"
  where
   i x y=lookup x.zip y -- "index" with x using y as key
   j=o.i c k -- use c as index k as key; assume success
   u=j[x-1,x+1,x,x] -- new x coord
   v=j[y,y,y-1,y+1] -- new y coord
   g t=f(j t,u,v) -- recurse; use t for new direction
main=do
 z<-getContents
 putStrLn$r$lines z
comingstorm
In code golf, readability is no merit.
recursive
+2  A: 

Groovy @ 279 characers

m=/[<>^v]/
i={'><v^'.indexOf(it)}
n=['<':{y--},'>':{y++},'^':{x--},'v':{x++}]
a=['x':{1},'\\':{'v^><'[i(d)]},'/':{'^v<>'[i(d)]},'#':{},' ':{d}]
b=[]
System.in.eachLine {b<<it.inject([]) {r,c->if(c==~m){x=b.size;y=r.size;d=c};r<<c}}
while(d==~m){n[d]();d=a[b[x][y]]()}
println !!d
Milan Ramaiya
+7  A: 

Weighing in at 18203 characters is a Python solution that can:

  • cope with mirrors outside of the 'room'
  • calculate the trajectory when there is no 'room' on the basis of 2D limitations (the spec says lots about what has to be in the 'room' but not if the room has to exist)
  • report back on errors

It still needs tidied up somewhat and I do not know if 2D physics dictate that the beam cannot cross itself...

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
The shortest code by character count to input a 2D representation of a board, 
and output 'true' or 'false' according to the input.

The board is made out of 4 types of tiles:

# - A solid wall
x - The target the laser has to hit
/ or \ - Mirrors pointing to a direction (depends on laser direction)
v, ^, > or < - The laser pointing to a direction (down, up, right and left
respectively)

There is only one laser and only one target. Walls must form a solid rectangle 
of any size, where the laser and target are placed inside. Walls inside the
'room' are possible.

Laser ray shots and travels from it's origin to the direction it's pointing. If
a laser ray hits the wall, it stops. If a laser ray hits a mirror, it is bounces
90 degrees to the direction the mirror points to. Mirrors are two sided, meaning
both sides are 'reflective' and may bounce a ray in two ways. If a laser ray
hits the laser (^v><) itself, it is treated as a wall (laser beam destroys the
beamer and so it'll never hit the target).
"""



SOLID_WALL, TARGET, MIRROR_NE_SW, MIRROR_NW_SE, LASER_DOWN, LASER_UP, \
LASER_RIGHT, LASER_LEFT = range(8)

MIRRORS = (MIRROR_NE_SW, MIRROR_NW_SE)

LASERS = (LASER_DOWN, LASER_UP, LASER_RIGHT, LASER_LEFT)

DOWN, UP, RIGHT, LEFT = range(4)

LASER_DIRECTIONS = {
    LASER_DOWN : DOWN,
    LASER_UP   : UP,
    LASER_RIGHT: RIGHT,
    LASER_LEFT : LEFT
}

ROW, COLUMN = range(2)

RELATIVE_POSITIONS = {
    DOWN : (ROW,     1),
    UP   : (ROW,    -1),
    RIGHT: (COLUMN,  1),
    LEFT : (COLUMN, -1)
}

TILES = {"#" : SOLID_WALL,
         "x" : TARGET,
         "/" : MIRROR_NE_SW,
         "\\": MIRROR_NW_SE,
         "v" : LASER_DOWN,
         "^" : LASER_UP,
         ">" : LASER_RIGHT,
         "<" : LASER_LEFT}

REFLECTIONS = {MIRROR_NE_SW: {DOWN : LEFT,
                              UP   : RIGHT,
                              RIGHT: UP,
                              LEFT : DOWN},
               MIRROR_NW_SE: {DOWN : RIGHT,
                              UP   : LEFT,
                              RIGHT: DOWN,
                              LEFT : UP}}



def does_laser_hit_target(tiles):
    """
        Follows a lasers trajectory around a grid of tiles determining if it
        will reach the target.

        Keyword arguments:
        tiles --- row/column based version of a board containing symbolic
                  versions of the tiles (walls, laser, target, etc)
    """

    #Obtain the position of the laser
    laser_pos = get_laser_pos(tiles)

    #Retrieve the laser's tile
    laser = get_tile(tiles, laser_pos)

    #Create an editable starting point for the beam
    beam_pos = list(laser_pos)

    #Create an editable direction for the beam
    beam_dir = LASER_DIRECTIONS[laser]

    #Cache the number of rows
    number_of_rows = len(tiles)

    #Keep on looping until an ultimate conclusion
    while True:

        #Discover the axis and offset the beam is travelling to
        axis, offset = RELATIVE_POSITIONS[beam_dir]

        #Modify the beam's position
        beam_pos[axis] += offset

        #Allow for a wrap around in this 2D scenario
        try:

            #Get the beam's new tile
            tile = get_tile(tiles, beam_pos)

        #Perform wrapping
        except IndexError:

            #Obtain the row position
            row_pos = beam_pos[ROW]

            #Handle vertical wrapping
            if axis == ROW:

                #Handle going off the top
                if row_pos == -1:

                    #Move beam to the bottom
                    beam_pos[ROW] = number_of_rows - 1

                #Handle going off the bottom
                elif row_pos == number_of_rows:

                    #Move beam to the top
                    beam_pos[ROW] = 0

            #Handle horizontal wrapping
            elif axis == COLUMN:

                #Obtain the row
                row = tiles[row_pos]

                #Calculate the number of columns
                number_of_cols = len(row)

                #Obtain the column position
                col_pos = beam_pos[COLUMN]

                #Handle going off the left hand side
                if col_pos == -1:

                    #Move beam to the right hand side
                    beam_pos[COLUMN] = number_of_cols - 1

                #Handle going off the right hand side
                elif col_pos == number_of_cols:

                    #Move beam to the left hand side
                    beam_pos[COLUMN] = 0

            #Get the beam's new tile
            tile = get_tile(tiles, beam_pos)

        #Handle hitting a wall or the laser
        if tile in LASERS \
        or tile == SOLID_WALL:
            return False

        #Handle hitting the target
        if tile == TARGET:
            return True

        #Handle hitting a mirror
        if tile in MIRRORS:
            beam_dir = reflect(tile, beam_dir)

def get_laser_pos(tiles):
    """
        Returns the current laser position or an exception.

        Keyword arguments:
        tiles --- row/column based version of a board containing symbolic
                  versions of the tiles (walls, laser, target, etc)
    """

    #Calculate the number of rows
    number_of_rows = len(tiles)

    #Loop through each row by index
    for row_pos in range(number_of_rows):

        #Obtain the current row
        row = tiles[row_pos]

        #Calculate the number of columns
        number_of_cols = len(row)

        #Loop through each column by index
        for col_pos in range(number_of_cols):

            #Obtain the current column
            tile = row[col_pos]

            #Handle finding a laser
            if tile in LASERS:

                #Return the laser's position
                return row_pos, col_pos

def get_tile(tiles, pos):
    """
        Retrieves a tile at the position specified.

        Keyword arguments:
        pos --- a row/column position of the tile
        tiles --- row/column based version of a board containing symbolic
                  versions of the tiles (walls, laser, target, etc)
    """

    #Obtain the row position
    row_pos = pos[ROW]

    #Obtain the column position
    col_pos = pos[COLUMN]

    #Obtain the row
    row = tiles[row_pos]

    #Obtain the tile
    tile = row[col_pos]

    #Return the tile
    return tile

def get_wall_pos(tiles, reverse=False):
    """
        Keyword arguments:
        tiles --- row/column based version of a board containing symbolic
                  versions of the tiles (walls, laser, target, etc)
        reverse --- whether to search in reverse order or not (defaults to no)
    """

    number_of_rows = len(tiles)

    row_iter = range(number_of_rows)

    if reverse:
        row_iter = reversed(row_iter)

    for row_pos in row_iter:
        row = tiles[row_pos]

        number_of_cols = len(row)

        col_iter = range(number_of_cols)

        if reverse:
            col_iter = reversed(col_iter)

        for col_pos in col_iter:
            tile = row[col_pos]

            if tile == SOLID_WALL:
                pos = row_pos, col_pos

                if reverse:
                    offset = -1
                else:
                    offset = 1

                for axis in ROW, COLUMN:
                    next_pos = list(pos)

                    next_pos[axis] += offset

                    try:
                        next_tile = get_tile(tiles, next_pos)
                    except IndexError:
                        next_tile = None

                    if next_tile != SOLID_WALL:
                        raise WallOutsideRoomError(row_pos, col_pos)

                return pos

def identify_tile(tile):
    """
        Returns a symbolic value for every identified tile or None.

        Keyword arguments:
        tile --- the tile to identify
    """

    #Safely lookup the tile
    try:

        #Return known tiles
        return TILES[tile]

    #Handle unknown tiles
    except KeyError:

        #Return a default value
        return

def main():
    """
        Takes a board from STDIN and either returns a result to STDOUT or an
        error to STDERR.

        Called when this file is run on the command line.
    """

    #As this function is the only one to use this module, and it can only be
    #called once in this configuration, it makes sense to only import it here.
    import sys

    #Reads the board from standard input.
    board = sys.stdin.read()

    #Safely handles outside input
    try:

        #Calculates the result of shooting the laser
        result = shoot_laser(board)

    #Handles multiple item errors
    except (MultipleLaserError, MultipleTargetError) as error:

        #Display the error
        sys.stderr.write("%s\n" % str(error))

        #Loop through all the duplicated item symbols
        for symbol in error.symbols:

            #Highlight each symbol in green
            board = board.replace(symbol, "\033[01;31m%s\033[m" % symbol)

        #Display the board
        sys.stderr.write("%s\n" % board)

        #Exit with an error signal
        sys.exit(1)

    #Handles item missing errors
    except (NoLaserError, NoTargetError) as error:

        #Display the error
        sys.stderr.write("%s\n" % str(error))

        #Display the board
        sys.stderr.write("%s\n" % board)

        #Exit with an error signal
        sys.exit(1)

    #Handles errors caused by symbols
    except (OutsideRoomError, WallNotRectangleError) as error:

        #Displays the error
        sys.stderr.write("%s\n" % str(error))

        lines = board.split("\n")

        line = lines[error.row_pos]

        before = line[:error.col_pos]

        after = line[error.col_pos + 1:]

        symbol = line[error.col_pos]

        line = "%s\033[01;31m%s\033[m%s" % (before, symbol, after)

        lines[error.row_pos] = line

        board = "\n".join(lines)

        #Display the board
        sys.stderr.write("%s\n" % board)

        #Exit with an error signal
        sys.exit(1)

    #Handles errors caused by non-solid walls
    except WallNotSolidError as error:

        #Displays the error
        sys.stderr.write("%s\n" % str(error))

        lines = board.split("\n")

        line = lines[error.row_pos]

        before = line[:error.col_pos]

        after = line[error.col_pos + 1:]

        symbol = line[error.col_pos]

        line = "%s\033[01;5;31m#\033[m%s" % (before, after)

        lines[error.row_pos] = line

        board = "\n".join(lines)

        #Display the board
        sys.stderr.write("%s\n" % board)

        #Exit with an error signal
        sys.exit(1)

    #If a result was returned
    else:

        #Converts the result into a string
        result_str = str(result)

        #Makes the string lowercase
        lower_result = result_str.lower()

        #Returns the result
        sys.stdout.write("%s\n" % lower_result)

def parse_board(board):
    """
        Interprets the raw board syntax and returns a grid of tiles.

        Keyword arguments:
        board --- the board containing the tiles (walls, laser, target, etc)
    """

    #Create a container for all the lines
    tiles = list()

    #Loop through all the lines of the board
    for line in board.split("\n"):

        #Identify all the tiles on the line 
        row = [identify_tile(tile) for tile in line]

        #Add the row to the container
        tiles.append(row)

    #Return the container
    return tiles

def reflect(mirror, direction):
    """
        Returns an updated laser direction after it has been reflected on a
        mirror.

        Keyword arguments:
        mirror --- the mirror to reflect the laser from
        direction --- the direction the laser is travelling in
    """

    try:
        direction_lookup = REFLECTIONS[mirror]
    except KeyError:
        raise TypeError("%s is not a mirror.", mirror)

    try:
        return direction_lookup[direction]
    except KeyError:
        raise TypeError("%s is not a direction.", direction)

def shoot_laser(board):
    """
        Shoots the boards laser and returns whether it will hit the target.

        Keyword arguments:
        board --- the board containing the tiles (walls, laser, target, etc)
    """

    tiles = parse_board(board)

    validate_board(tiles)

    return does_laser_hit_target(tiles)

def validate_board(tiles):
    """
        Checks an board to see if it is valid and raises an exception if not.

        Keyword arguments:
        tiles --- row/column based version of a board containing symbolic
                  versions of the tiles (walls, laser, target, etc)
    """

    found_laser = False
    found_target = False

    try:
        n_wall, w_wall = get_wall_pos(tiles)
        s_wall, e_wall = get_wall_pos(tiles, reverse=True)
    except TypeError:
        n_wall = e_wall = s_wall = w_wall = None

    number_of_rows = len(tiles)

    for row_pos in range(number_of_rows):
        row = tiles[row_pos]

        number_of_cols = len(row)

        for col_pos in range(number_of_cols):

            tile = row[col_pos]

            if ((row_pos in (n_wall, s_wall) and
                 col_pos in range(w_wall, e_wall))
                or
                (col_pos in (e_wall, w_wall) and
                 row_pos in range(n_wall, s_wall))):
                if tile != SOLID_WALL:
                    raise WallNotSolidError(row_pos, col_pos)
            elif (n_wall != None and
                  (row_pos < n_wall or
                   col_pos > e_wall or
                   row_pos > s_wall or
                   col_pos < w_wall)):

                if tile in LASERS:
                    raise LaserOutsideRoomError(row_pos, col_pos)
                elif tile == TARGET:
                    raise TargetOutsideRoomError(row_pos, col_pos)
                elif tile == SOLID_WALL:
                    if not (row_pos >= n_wall and
                            col_pos <= e_wall and
                            row_pos <= s_wall and
                            col_pos >= w_wall):
                        raise WallOutsideRoomError(row_pos, col_pos)
            else:
                if tile in LASERS:
                    if not found_laser:
                        found_laser = True
                    else:
                        raise MultipleLaserError(row_pos, col_pos)
                elif tile == TARGET:
                    if not found_target:
                        found_target = True
                    else:
                        raise MultipleTargetError(row_pos, col_pos)

    if not found_laser:
        raise NoLaserError(tiles)

    if not found_target:
        raise NoTargetError(tiles)



class LasersError(Exception):
    """Parent Error Class for all errors raised."""

    pass

class NoLaserError(LasersError):
    """Indicates that there are no lasers on the board."""

    symbols = "^v><"

    def __str__ (self):
        return "No laser (%s) to fire." % ", ".join(self.symbols)

class NoTargetError(LasersError):
    """Indicates that there are no targets on the board."""

    symbols = "x"

    def __str__ (self):
        return "No target (%s) to hit." % ", ".join(self.symbols)

class MultipleLaserError(LasersError):
    """Indicates that there is more than one laser on the board."""

    symbols = "^v><"

    def __str__ (self):
        return "Too many lasers (%s) to fire, only one is allowed." % \
               ", ".join(self.symbols)

class MultipleTargetError(LasersError):
    """Indicates that there is more than one target on the board."""

    symbols = "x"

    def __str__ (self):
        return "Too many targets (%s) to hit, only one is allowed." % \
               ", ".join(self.symbols)

class WallNotSolidError(LasersError):
    """Indicates that the perimeter wall is not solid."""

    __slots__ = ("__row_pos", "__col_pos", "n_wall", "s_wall", "e_wall",
                 "w_wall")

    def __init__(self, row_pos, col_pos):
        self.__row_pos = row_pos
        self.__col_pos = col_pos

    def __str__ (self):
        return "Walls must form a solid rectangle."

    def __get_row_pos(self):
        return self.__row_pos

    def __get_col_pos(self):
        return self.__col_pos

    row_pos = property(__get_row_pos)
    col_pos = property(__get_col_pos)

class WallNotRectangleError(LasersError):
    """Indicates that the perimeter wall is not a rectangle."""

    __slots__ = ("__row_pos", "__col_pos")

    def __init__(self, row_pos, col_pos):
        self.__row_pos = row_pos
        self.__col_pos = col_pos

    def __str__ (self):
        return "Walls must form a rectangle."

    def __get_row_pos(self):
        return self.__row_pos

    def __get_col_pos(self):
        return self.__col_pos

    row_pos = property(__get_row_pos)
    col_pos = property(__get_col_pos)

class OutsideRoomError(LasersError):
    """Indicates an item is outside of the perimeter wall."""

    __slots__ = ("__row_pos", "__col_pos", "__name")

    def __init__(self, row_pos, col_pos, name):
        self.__row_pos = row_pos
        self.__col_pos = col_pos
        self.__name = name

    def __str__ (self):
        return "A %s was found outside of a 'room'." % self.__name

    def __get_row_pos(self):
        return self.__row_pos

    def __get_col_pos(self):
        return self.__col_pos

    row_pos = property(__get_row_pos)
    col_pos = property(__get_col_pos)

class LaserOutsideRoomError(OutsideRoomError):
    """Indicates the laser is outside of the perimeter wall."""

    def __init__ (self, row_pos, col_pos):
        OutsideRoomError.__init__(self, row_pos, col_pos, "laser")

class TargetOutsideRoomError(OutsideRoomError):
    """Indicates the target is outside of the perimeter wall."""

    def __init__ (self, row_pos, col_pos):
        OutsideRoomError.__init__(self, row_pos, col_pos, "target")

class WallOutsideRoomError(OutsideRoomError):
    """Indicates that there is a wall outside of the perimeter wall."""

    def __init__ (self, row_pos, col_pos):
        OutsideRoomError.__init__(self, row_pos, col_pos, "wall")



if __name__ == "__main__":
    main()

A bash script to show off the colour error reporting:

#!/bin/bash

declare -a TESTS

test() {
    echo -e "\033[1m$1\033[0m"
    tput sgr0
    echo "$2" | ./lasers.py
    echo
}

test \
"no laser" \
"    ##########
    #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"multiple lasers" \
"    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\  ^ #
    ##########"

test \
"no target" \
"    ##########
    #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"multiple targets" \
"    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\  x #
    ##########"

test \
"wall not solid" \
"    ##### ####
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"laser_outside_room" \
"    ##########
 >  #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"laser before room" \
" >  ##########
    #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"laser row before room" \
"   >
    ##########
    #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"laser after room" \
"    ##########
    #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########  >"

test \
"laser row after room" \
"    ##########
    #     x  #
    # /      #
    #       /#
    #   \\    #
    ##########
  > "

test \
"target outside room" \
"    ##########
 x  #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"target before room" \
" x  ##########
    #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"target row before room" \
"   x
    ##########
    #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"target after room" \
"    ##########
    #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########   x"

test \
"target row after room" \
"    ##########
    #   v    #
    # /      #
    #       /#
    #   \\    #
    ##########
  x "

test \
"wall outside room" \
"    ##########
 #  #   v    #
    # /      #
    #       /#
    #   \\  x #
    ##########"

test \
"wall before room" \
" #  ##########
    #   v    #
    # /      #
    #       /#
    #   \\  x #
    ##########"

test \
"wall row before room" \
"    #
    ##########
    #   v    #
    # /      #
    #       /#
    #   \\  x #
    ##########"

test \
"wall after room" \
"    ##########
    #   v    #
    # /      #
    #       /#
    #   \\  x #
    ########## #"

test \
"wall row after room" \
"    ##########
    #   v    #
    # /      #
    #       /#
    #   \\  x #
    ##########
  #"

test \
"mirror outside room positive" \
"    ##########
 /  #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## "

test \
"mirrors outside room negative" \
"    ##########
 \\  #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"mirror before room positive" \
" \\  ##########
    #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## "

test \
"mirrors before room negative" \
" /  ##########
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"mirror row before room positive" \
"     \\
    ##########
    #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## "

test \
"mirrors row before room negative" \
"     \\
    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"mirror after row positive" \
"    ##########
    #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## /  "

test \
"mirrors after row negative" \
"    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########   /  "

test \
"mirror row after row positive" \
"    ##########
    #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## 
 /  "

test \
"mirrors row after row negative" \
"    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ########## 
 /  "

test \
"laser hitting laser" \
"    ##########
    #   v   \\#
    #        #
    #        #
    #x  \\   /#
    ##########"

test \
"mirrors positive" \
"    ##########
    #   / \\  #
    #        #
    #   \\   x#
    # >   /  #
    ########## "

test \
"mirrors negative" \
"    ##########
    #   v x  #
    # /      #
    #       /#
    #   \\    #
    ##########"

test \
"wall collision" \
"    #############
    #     #     #
    # >   #     #
    #     #     #
    #     #   x #
    #     #     #
    #############"

test \
"extreme example" \
"    ##########
    #/\\/\\/\\  #
    #\\\\//\\\\\\ #
    #//\\/\\/\\\\#
    #\\/\\/\\/x^#
    ##########"

test \
"brian example 1" \
"##########
#   / \\  #
#        #
#/    \\ x#
#\\>   /  #
##########"

test \
"brian example 2" \
"##########
#  /    \\#
# / \\    #
#/    \\ x#
#\\^/\\ /  #
##########"

The unittests used in development:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import unittest

from lasers import *

class TestTileRecognition(unittest.TestCase):
    def test_solid_wall(self):
        self.assertEqual(SOLID_WALL, identify_tile("#"))

    def test_target(self):
        self.assertEqual(TARGET, identify_tile("x"))

    def test_mirror_ne_sw(self):
        self.assertEqual(MIRROR_NE_SW, identify_tile("/"))

    def test_mirror_nw_se(self):
        self.assertEqual(MIRROR_NW_SE, identify_tile("\\"))

    def test_laser_down(self):
        self.assertEqual(LASER_DOWN, identify_tile("v"))

    def test_laser_up(self):
        self.assertEqual(LASER_UP, identify_tile("^"))

    def test_laser_right(self):
        self.assertEqual(LASER_RIGHT, identify_tile(">"))

    def test_laser_left(self):
        self.assertEqual(LASER_LEFT, identify_tile("<"))

    def test_other(self):
        self.assertEqual(None, identify_tile(" "))

class TestReflection(unittest.TestCase):
    def setUp(self):
        self.DIRECTION = LEFT
        self.NOT_DIRECTIO
Metalshark
Laser physics dictate that the beam *can* cross itself. The comment above is an important cultural reference.
dmckee
I think someone misses the point of code-golf...
LiraNuna
This is code-cricket.
Justicle
Tortoise and the Hare approach to code golf. Deliver something with obviously too many characters (91x more than the current winner) but pay attention to every letter of the spec. Slow and steady generally gets me less contract work though.
Metalshark
This is pretty funny.
eyelidlessness
Your unittest seems to be missing some part. It is cut off at "self.NOT_DIRECTIO"
BioGeek
+3  A: 

C++: 388 characters

#include<iostream>
#include<string>
#include<deque>
#include<cstring>
#define w v[y][x]
using namespace std;size_t y,x,*z[]={&y,&x};int main(){string p="^v<>",s;deque<string>v;
while(getline(cin,s))v.push_back(s);while(x=v[++y].find_first_of(p),!(x+1));int 
i=p.find(w),d=i%2*2-1,r=i/2;do while(*z[r]+=d,w=='/'?d=-d,0:w==' ');while(r=!r,
!strchr("#x<^v>",w));cout<<(w=='x'?"true":"false");}

(318 without headers)


How it works:

First, all lines are read in, then, the laser is found. The following will evaluate to 0 as long as no laser arrow was found yet, and the same time assign to x the horizontal position.

x=v[++y].find_first_of(p),!(x+1)

Then we look what direction we found and store it in i. Even values of i are top/left ("decreasing") and odd values are bottom/right ("increasing"). According to that notion, d ("direction") and r ("orientation") are set. We index pointer array z with orientation and add the direction to the integer we get. The direction changes only if we hit a slash, while it remains the same when we hit a back-slash. Of course, when we hit a mirror, then we always change orientation (r = !r).

Johannes Schaub - litb
You're making me do my own C++ solution. =]
strager
@strager, this is getting boring though. Let's do a solution that displays "true" or "false" at compile time xD
Johannes Schaub - litb
added explanation since i think i will keep it at this :)
Johannes Schaub - litb
+8  A: 

Ruby, 176 characters

x=!0;y=0;e="^v<>#x";b=readlines;b.map{|l|(x||=l=~/[v^<>]/)||y+=1};c=e.index(b[y][x])
loop{c<2&&y+=c*2-1;c>1&&x+=2*c-5;e.index(n=b[y][x])&&(p n==?x;exit);c^='  \/'.index(n)||0}

I used a simple state machine (like most posters), nothing fancy. I just kept whittling it down using every trick I could think of. The bitwise XOR used to change direction (stored as an integer in the variable c) was a big improvement over the conditionals I had in earlier versions.

I have a suspicion that the code that increments x and y could be made shorter. Here is the section of the code that does the incrementing:

c<2&&y+=c*2-1;c>1&&x+=(c-2)*2-1

Edit: I was able to shorten the above slightly:

c<2&&y+=c*2-1;c>1&&x+=2*c-5

The current direction of the laser c is stored as follows:

0 => up
1 => down
2 => left
3 => right

The code relies on this fact to increment x and y by the correct amount (0, 1, or -1). I tried rearranging which numbers map to each direction, looking for an arrangement that would let me do some bitwise manipulation to increment the values, because I have a nagging feeling that it would be shorter than the arithmetic version.

Mike Spross
+6  A: 

JavaScript - 265 Characters

Update IV - Odds are this will be the last round of updates, managed to save a couple more characters by switching to a do-while loop and rewriting the movement equation.

Update III - Thanks to the suggestion by strager in regards to removing Math.abs() and putting the variables in the global name space, that coupled with some rearranging of the variable assignments got the code down to 282 characters.

Update II - Some more updates to the code to remove the use of != -1 as well as some better use of variables for longer operations.

Update - When through and made some changes by creating a reference to the indexOf function (thanks LiraNuna!) and removing parenthesis that were not needed.

This is my first time doing a code golf so I'm not sure how much better this could be, any feed back is appreciated.

Fully minimized version:

a;b;c;d;e;function f(g){a=function(a){return g.indexOf(a)};b=a("\n")+1;a=g[c=e=a("v")>0?e:e=a("^")>0?e:e=a("<")>0?e:a(">")];d=a=="<"?-1:a==">"?1:a=="^"?-b:b;do{e=d==-1|d==1;a=g[c+=d=a=="\\"?e?b*d:d>0?1:-1:a=="/"?e?-b*d:d>0?1:-1:d];e=a=="x"}while(a!="#"^e);return e}

Original version with comments:

character; length; loc; movement; temp;
function checkMaze(maze) {
        // Use a shorter indexOf function
        character = function(string) { return maze.indexOf(string); }
        // Get the length of the maze
        length = character("\n") + 1;
        // Get the location of the laser in the string
        character = maze[loc = temp = character("v") > 0 ? temp :
                               temp = character("^") > 0 ? temp :
                               temp = character("<") > 0 ? temp : character(">")];
        // Get the intial direction that we should travel
        movement = character == "<" ? -1 :
                   character == ">" ? 1 :
                   character == "^" ? -length : length;
        // Move along until we reach the end
        do {
            // Get the current character
            temp = movement == -1 | movement == 1;
            character = maze[loc += movement = character == "\\" ? temp ? length * movement : movement > 0 ? 1 : -1 :
                                               character == "/" ? temp ? -length * movement : movement > 0 ? 1 : -1 : movement];                                   
            // Have we hit a target?
            temp = character == "x";
            // Have we hit a wall?
        } while (character != "#" ^ temp);
        // temp will be false if we hit the target
        return temp;
    }

Web page to test with:

<html>
  <head>
    <title>Code Golf - Lasers</title>
    <script type="text/javascript">
    a;b;c;d;e;function f(g){a=function(a){return g.indexOf(a)};b=a("\n")+1;a=g[c=e=a("v")>0?e:e=a("^")>0?e:e=a("<")>0?e:a(">")];d=a=="<"?-1:a==">"?1:a=="^"?-b:b;do{e=d==-1|d==1;a=g[c+=d=a=="\\"?e?b*d:d>0?1:-1:a=="/"?e?-b*d:d>0?1:-1:d];e=a=="x"}while(a!="#"^e);return e}
    </script>
  </head>
  <body>
    <textarea id="maze" rows="10" cols="10"></textarea>
    <button id="checkMaze" onclick="alert(f(document.getElementById('maze').value))">Maze</button>
  </body>
</html>
Rob
how does it take input? I want to test and verify this. Also, you can save a lot of characters if you save a ref to a.indexOf
LiraNuna
@LiraNuna - Good point on the indexOf minimization.
Rob
Replace `index != -1` with `index > 0` please! (Hopefully no one puts the lazer in the top-left corner so `0` wouldn't be returned. =]) You can chain the `var` statements or get rid of them altogether (putting the variables in the global namespace). I think `Math.abs(m)==1` can be replaced with `m==-1|m==1`. Can `movement = ...; location += movement` be optimized to `location += movement =` ?
strager
@strager- Just saw your comment, looks like you posted it up while I was updating the code, down to 300 characters. I'll see what I can do with the elimination of Math.abs().
Rob
`function(a){return g.indexOf(a)}` can be replaced with `function(a)g.indexOf(a)` in recent JavaScript versions.
grawity
+6  A: 

C + ASCII, 197 characters:

G[999],*p=G,w,z,t,*b;main(){for(;(*p++=t=getchar()^32)>=0;w=w|t-42?w:p-G)z=t^86?t^126?t^28?t^30?z:55:68:56:75,b=z?b:p;for(;t=z^55?z^68?z^56?z^75?0:w:-w:-1:1;z^=*b)b+=t;puts(*b^88?"false":"true");}

This C solution assumes an ASCII character set, allowing us to use the XOR mirror trick. It's also incredibly fragile - all the input lines must be the same length, for example.

It breaks under the 200 character mark - but dang it, still haven't beaten those Perl solutions!

caf
=O! +1! Grats on beating me. =]
strager
Most good solutions here make the "all lines are the same length" assumption. All's fair in golf and war.
hobbs
If it was required the lines weren't the same length, I'd add a test case for it. but I clearly said it was intentional :)
LiraNuna
+13  A: 

Golfscript - 83 chars (mashup of mine and strager's)

The newline is just here for wrapping

:|'v^><'.{|?}%{)}?:[email protected]=?{.[10|?).~)1-1]=$+
:$|=' \/x'?\[.\2^.1^'true''false']=.4/!}do

Golfscript - 107 chars

The newline is just there for clarity

10\:@?):&4:$;{0'>^<v'$(:[email protected]?:*>}do;
{[1 0&--1&]$=*+:*;[{$}{3$^}{1$^}{"true "}{"false"}]@*=' \/x'?=~5\:$>}do$

How it works.

First line works out the initial location and direction.
Second line steps through turning whenever the laser hits a mirror.

gnibbler
+4  A: 

Golfscript (83 characters)

Hello, gnibbler!

:\'><v^'.{\?}%{)}?:[email protected]=?{:O[1-1\10?).~)]=P+
:P\=' \/x'?[O.2^.1^'true''false']=.4/!}do
strager
Heya strager! Nice one
gnibbler
golfscript:perl ~= 1:1.7
gnibbler
+6  A: 

Python - 152

Reads input from a file called "L"

A=open("L").read()
W=A.find('\n')+1
D=P=-1
while P<0:D+=1;P=A.find(">^<v"[D])
while D<4:P+=[1,-W,-1,W][D];D=[D,D^3,D^1,4,5][' \/x'.find(A[P])]
print D<5

To read from stdin replace the first line with this

import os;A=os.read(0,1e9)

If you need lowercase true/false change the last line to

print`D<5`.lower()
gnibbler
How many chars does it take to change `True` to `true` and `False` to `false`? ;-)
mobrule
@mobrule, too many ;o)
gnibbler
Couldn't you remove 1 character by changing "print`D<5`" to "print D<5"? Or is there something I'm missing?
Wallacoloo
@wallacoloo, sure can. It's only needed for the lowercase true/false
gnibbler
+5  A: 

Ruby - 146 Chars

A=$<.read
W=A.index('
')+1
until
q=A.index(">^<v"[d=d ?d+1:0])
end
while d<4
d=[d,d^3,d^1,4,5][(' \/x'.index(A[q+=[1,-W,-1,W][d]])or 4)]
end
p 5>d
gnibbler
+5  A: 

PostScript, 359 bytes

First attempt, lots of room for improvement...

/a[{(%stdin)(r)file 99 string readline not{exit}if}loop]def a{{[(^)(>)(<)(v)]{2
copy search{stop}if pop pop}forall}forall}stopped/r count 7 sub def pop
length/c exch def[(>)0(^)1(<)2(v)3>>exch get/d exch def{/r r[0 -1 0 1]d get
add def/c c[1 0 -1 0]d get add def[32 0 47 1 92 3>>a r get c get .knownget
not{exit}if/d exch d xor def}loop a r get c get 120 eq =
KirarinSnow
A: 

F# - 454 (or thereabouts)

Bit late to the game, but can't resist posting my 2d attempt.

Update modified slightly. Now stops correctly if transmitter is hit. Pinched Brian's idea for IndexOfAny (shame that line is so verbose). I haven't actually managed to work out how to get ReadToEnd to return from the Console, so I'm taking that bit on trust...

I'm pleased with this answer, as though it is quite short, it is still fairly readable.

let s=System.Console.In.ReadToEnd()       //(Not sure how to get this to work!)
let w=s.IndexOf('\n')+1                   //width
let h=(s.Length+1)/w                      //height
//wodge into a 2d array
let a=Microsoft.FSharp.Collections.Array2D.init h (w-1)(fun y x -> s.[y*w+x])
let p=s.IndexOfAny[|'^';'<';'>';'v'|]     //get start pos
let (dx,dy)=                              //get initial direction
 match "^<>v".IndexOf(s.[p]) with
 |0->(0,-1)
 |1->(-1,0)
 |2->(1,0)
 |_->(0,1)
let mutable(x,y)=(p%w,p/w)                //translate into x,y coords
let rec f(dx,dy)=
 x<-x+dx;y<-y+dy                          //mutate coords on each call
 match a.[y,x] with
 |' '->f(dx,dy)                           //keep going same direction
 |'/'->f(-dy,-dx)                         //switch dx/dy and change sign
 |'\\'->f(dy,dx)                          //switch dx/dy and keep sign
 |'x'->"true"
 |_->"false"
System.Console.Write(f(dx,dy))
Benjol
They are decoration. Check my other challenges, it's just a formatting thing.
LiraNuna
@LiraNuna, ok as it turns out, this iteration just eats them anyway :)
Benjol
@Benjol, Would be nice to compare with a 1-d implementation. Just add/subtract 1 for left and right and add/subtract w for up and down. I'd expect you'd save quite a few chars
gnibbler
@gnibbler, Brian already did that, I'm not sure I could beat him, but I might give it a try.
Benjol
+7  A: 

I would bet people have been waiting for this one for a LOOOOONG time. (What do you mean, the challenge is over and nobody cares any more?)

Behold... I here present a solution in

Befunge-93!

It weighs in at a whopping 973 charaters (or 688 if you are charitable enough to ignore whitespace, which is only used for formatting and does nothing in actual code).

Caveat: I wrote my own Befunge-93 interpreter in Perl a short while ago, and unfortunately this is all I've really had time with which to test it. I'm reasonably confident in its correctness in general, but it might have an odd limitation with regard to EOF: Since Perl's <> operator returns undef at the end of file, this is processed as a 0 in the numeric context. For C-based implementations where EOF has a different value (-1 say), this code might not work.

003pv   >~v>  #v_"a"43g-!#v_23g03p33v>v
>39#<*v   ::   >:52*-!v   >"rorrE",vg2*
######1   >^vp31+1g31$_03g13gp vv,,<15,
    a#3     >0v       vp30+1g30<>,,#3^@
######p $     0vg34"a"<   >       >vp
^<v>  > ^   p3<>-#v_:05g-!|>:15g-!| $
 >     v^     <   <   <   >^v-g52:< $ 
  v _  >52*"eslaf",,vv|-g53:_      v   
  : ^-"#">#:< #@,,,,<<>:43p0 v0 p34< 
  >">"-!vgv<  ^0p33g31p32-1g3<       
 ^     <#g1|-g34_v#-g34_v#-g34"><v^"<<<<
    v!<^<33>13g1v>03g1-v>03g1+03p$v  $$
>^  _#-v 1>g1-1v>+13pv >03p       v  pp
^_:"^"^#|^g30 <3#   $<           $<>^33
 ^!-"<":<>"v"v^># p#$<>            $^44
^      >#^#_ :" "-#v_ ^   >         ^gg
v  g34$<   ^!<v"/":< >$3p$^>05g43p$ ^55
 >,@   |!-"\"  :_$43g:">"-!|>      ^$32
 *v"x":<      >-^    ^4g52<>:"^" -#v_^
 5>-!#v_"ror"vv$p34g51:<>#|  !-"<":<#|
 ^2,,, ,,"er"<>v      #^^#<>05g43p$$^>^
      >52*"eurt",,,,,@>15g4 3p$$$$  ^#
>:"v"\:"<"\: "^"   -!#^_-!#^_-!      ^
               >                       ^

Explanation

If you're not familiar with the Befunge syntax and operation, check here.

Befunge is a stack-based language, but there are commands that allow one to write characters to the Befunge code. I take advantage of that in two places. First, I copy the entire input onto the Befunge board, but located a couple of lines below the actual written code. (Of course, this is never actually visible when the code runs.)

The other place is near the the upper-left:

######
    a#
######

In this case, the area I've highlighted above is where I store a couple of coordinates. The first column in the middle row there is where I store the x-coordinate for the current "cursor position"; the second column is where I store the y-coordinate; the next two columns are for storing the x- and y-coordinate of the laser beam source when that is found; and the final column (with the 'a' character in it) is eventually overwritten to contain the current beam direction, which obviously changes as the beam's path is traced.

The program starts by placing (0,27) as the initial cursor position. Then input is read one character at a time and placed in the cursor position; newlines merely cause the y-coordinate to increase and the x-coordinate to go back to 0, just like a real carriage return. Eventually undef is read by the interpreter and that 0 character value is used to signal the end of input and move on to the laser iteration steps. When the laser character [<>^v] is read, that is also copied to the memory repository (over the 'a' character) and its coordinates are copied to the columns just to the left.

The end result of all of this is that the entire file is basically copied into the Befunge code, a little ways below the actual code traversed.

Afterwards, the beam location is copied back into the cursor locations, and the following iteration is performed:

  • Check for the current beam direction and increment or decrement the cursor coordinates appropriately. (I do this first to avoid having to deal with the corner case of the laser beam right on the first move.)
  • Read the character at that location.
  • If the character is "#", put newline and "false" on the stack, print, and end.
  • Compare it to all of the beam characters [<>^v]; if there's a match, also print "false\n" and end.
  • If the character is a space, empty the stack and continue.
  • If the character is a forward slash, get the beam direction onto the stack and compare it to each of the direction characters in turn. When one is found, the new direction is stored at that same spot in the code and the loop repeats.
  • If the character is a backslash, do basically the same thing as the above (except with the proper mapping for backslash).
  • If the character is 'x', we've hit the target. Print "true\n" and exit.
  • If the character is none of these, print "error\n" and exit.

If there's enough demand for it, I'll try to point out exactly where in the code all this is accomplished.

Platinum Azure
+1 - Only because it could be misinterpreted to be an EXE opened in notepad.
Kyle Rozendo