Code Golf: Lasers

Question

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,

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){...}.

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)

    );
}

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.

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

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

The newline is just here for wrapping

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

Golfscript - 107 chars

The newline is just there for clarity

10\:@?):&4:$;{0'>^<v'$(:$=@?:*>}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.