Code Golf: Lasers

code-golflanguage-agnosticrosetta-stone

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

Best Answer

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,

Related Topic