25
\$\begingroup\$

A 2D board will contain the following objects:

  • ^,>,v, or <: A laser emitter facing up, right, down, or left respectively. There may be more than one. Lasers will travel in a straight line in empty space (empty space is represented with a dot .). Lasers do not pass through emitters.
  • *: A target. Lasers pass through targets. There may be more than one.

The board may also contain the following objects:

  • @: A solid wall. The laser will not pass through here.
  • \: A left-leaning reflector. Changes the direction of lasers according to the following table:

    Direction laser is travelling     Direction of laser after hitting reflector
    Up                                Left
    Right                             Down
    Down                              Right
    Left                              Up
    

    It should be pretty intuitive as to how the reflectors work. Just imagine them as an actual two-sided mirror and the directions should be clear.

  • /: A right-leaning reflector. Changes the direction of lasers according to the following table:

    Direction laser is travelling     Direction of laser after hitting reflector
    Up                                Right
    Right                             Up
    Down                              Left
    Left                              Down
    
  • 1,2,3...9: A portal. The number indicates the channel of the portal - there will be exactly two portals of the same channel (for instance, there won't be three 1's). The portal changes the position of lasers to the position of the other portal of the same channel. For instance:

    >     1     @     1     *
    

    The laser will hit the target because when it hits the first 1, it is teleported to the second 1 on the other side. Lasers retain the same direction that they were in before.

    A portal will not teleport the laser to a portal of a different channel (i.e. a 1 won't teleport the laser to a 9.

Your program will recieve a 2D representation of the board as input. The board will always be rectangular shaped. The output should be True if all the targets have lasers passing through them, or False otherwise.

Here are some test cases:

  1. Input

    >....\
    ..*...
    >./../
    ..*...
    

    Output

    True
    
  2. Input

    >..........\
    1........../
    2..........1
    3..........2
    4..........3
    5..........4
    6..........5
    7..........6
    8..........7
    9..........8
    *..........9
    

    Output

    True
    
  3. Input

    >.@............*
    >..@...........*
    >...@..........*
    >....@.........*
    >.....@........*
    >...*..@........
    >.......@......*
    

    Output

    False
    
  4. Input

    ../\.
    >./**
    

    Output

    False
    
  5. Input

    /.......*.......\/3.....
    @..............//\.\....
    *.............2\.1\/\...
    \..............///.....<
    .........*...//\\/.....\
    >.............\.1.///.4.
    4.......*/...\2\/3/\/..^
    

    Output

    True
    
  6. Input

    vvvvvvvvvvvvvvvvv
    \\\\\\\\\\\\\\\\\
    /////////////////
    \\\\\\\\\\\\\\\\\
    /////////////////
    \\\\\\\\\\\\\\\\\
    /////////////////
    *****************
    

    Output (note the target at the far right)

    False
    
\$\endgroup\$
  • \$\begingroup\$ Wouldn't it make more sense if a right-leaning reflector (/) changed the direction of a laser beam from left (←) to down (↓)? \$\endgroup\$ – squeamish ossifrage Sep 10 '14 at 7:56
  • \$\begingroup\$ @squeamish ossifrage I'm sorry, I don't understand your question. Which reflection rule on the left leaning reflector table do you think is incorrect?​​​​​​​​​​​​​​​ \$\endgroup\$ – absinthe Sep 10 '14 at 7:58
  • \$\begingroup\$ I think you got left and right mixed up \$\endgroup\$ – squeamish ossifrage Sep 10 '14 at 7:59
  • 1
    \$\begingroup\$ What happens if the laser reaches the grid boundary? \$\endgroup\$ – DavidG Sep 10 '14 at 15:15
  • 2
    \$\begingroup\$ @DavidG Nothing, or it bounces back the way it came. (These are equivalent in this case). It does not 'wrap around' as can be seen from example 6. \$\endgroup\$ – Dennis Jaheruddin Sep 10 '14 at 15:22
8
\$\begingroup\$

Python, 310 302 287 278 277 260

Not radically different than the existing Python post, but has one or two noteworthy tricks, I think. It also handles "non-terminating" input, such as 1>1. EDIT: Oops! emitters block lasers.

def t(b):
 w=len(b[0])+1;B=list('@'*w+'@'.join(b));i=l=len(B);C="<>^v@"
 while i:
    j=l-i;i-=1;d=C.find(B[j]);c='.'
    while c not in C:
     if'+'>c:B[j]='.'
     if'0'<c<C:j=(B*2).index(c,j+1)%l
     elif'.'<c:d^=2+(c<C)
     j-=[1,-1,w,-w,j][d];c=B[j%l]
 return'*'not in B

t takes a list of strings (the input lines) and returns a boolean result.

Here's a nice gif of the code being golfed down:

enter image description here

EDIT: Awsome gif courtesy of Will. Thanks Will!

\$\endgroup\$
  • \$\begingroup\$ The spec specifies that "Lasers do not pass through emitters." so 1>1 will terminate. I've not been able to find something that doesn't terminate, though I've not put much effort into it and pretty much assumed it doesn't happen for my implementation. I will of course reconsider if someone can present one. \$\endgroup\$ – VisualMelon Sep 10 '14 at 18:55
  • 4
    \$\begingroup\$ @VisualMelon: The rules are time-symmetric except at spots where lasers are born or die, which means everything has to terminate (since you can always uniquely trace it back to the point where it was born, and emitters can't themselves be part of a loop). \$\endgroup\$ – Micah Sep 10 '14 at 20:47
  • \$\begingroup\$ @Micah hehe, thanks for a proper explanation, like I said I went with intuition and didn't worry about it much, thanks for putting another tool in my box. \$\endgroup\$ – VisualMelon Sep 10 '14 at 21:01
  • \$\begingroup\$ Yup, I read it wrong. \$\endgroup\$ – Ell Sep 10 '14 at 21:10
  • \$\begingroup\$ Hats off to Ell! Very nicely done. I think you can shave a few more bytes off by using the fact that .find(d) returns -1 if not found. If you remove the if-1<d: statement and instead do j+=[-1,1,w,-w,-i][d] at the top of the while loop, a not-found -1 will turn into adding the last element in that array to j, which will make j 0, which we know is @...? \$\endgroup\$ – Will Sep 10 '14 at 21:44
7
\$\begingroup\$

Perl, 647

This is my first ever attempt at code-golf, and I'm a bit embarrassed I didn't even beat the C# score, but I thought it would be interesting (or fun, or just masochistic) to do the entire thing as a series of regex substitutions. (I also thought it would be fun to brush up on my Perl, but by the end I was deeply regretting not implementing it in Ruby or Python.)

I haven't done a lot of testing, but I think it should handle every case.

The grid is input via STDIN. There must be at least one newline in the input (i.e. a single row without a newline won't work).

%s=(d,'[|+#$vk%ZX]',u,'[|+#$^W%KX]',r,'[-G+#>k%KX]',l,'[-G+#<W%ZX]');%o=(d,'[-.*G/k\\\\Z',u,'[-.*G/W\\\\K',r,'[|.*$\\\\/kK',l,'[|.*$\\\\/ZW');for$d(d,u,r,l){$o{$d}.='123456789qwertyuio]'}%u=(d,'.|-+*$G#/Wk%\KZX',u,'.|-+*$G#/kW%\ZKX',r,'.-|+*G$#/Wk%\ZKX',l,'.-|+*G$#/kW%\KZX');@q=split//,"qwertyuio";local$/;$_=<STDIN>;for$i(1..9){$m{$i}=$q[$i-1];$m{$m{$i}}=$i;s/$i/$m{$i}/e}/.*?\n/;$l='.'x((length$&)-1);do{$c=0;for$d(d,u,r,l){%p=(d,"(?<=$s{d}$l)$o{d}",u,"$o{u}(?=$l$s{u})",r,"(?<=$s{r})$o{r}",l,"$o{l}(?=$s{l})");%h=split//,$u{$d};$c+=s!$p{$d}!$h{$&}||($v=$&,($o{$d}=~s/$v// && $s{$d}=~s/]/$m{$v}]/),$v)!es}}while($c);print/\*/?"False\n":"True\n"

Explanation: the code iteratively updates the grid string as the lasers pass through it. - represents a horizontal laser, | a vertical laser, + crossed lasers, K a \ mirror with a laser bouncing off the top, k a / mirror with a laser bouncing off the bottom, Z a \ mirror with a laser bouncing off the bottom, and W a / mirror with a laser bouncing off the top. % is a / mirror with lasers on both sides, while X is a \ mirror with lasers on both sides. (These are case sensitive. I tried to pick letters that look somewhat appropriate--for instance, k and K are somewhat obvious choices--but unfortunately the effect really isn't that helpful. I should really put this info into a table, but I'm exhausted right now.)

Handling portals in the same way (i.e. assigning each digit a set of extra characters based on the possible input/output laser positions) would require 144 characters (including the original 9), so instead, when a laser hits an "input" portal, I add the "output" portal character to the set of characters that emit a laser in the proper direction. (This does require differentiating between input and output portals; I used the letters qwertyuio for this.)

Somewhat un-golfed, with print statements so you can see the substitutions happening (each substitution represents one "round" of laser-progression), and with the g flag added to the main s/// so that it doesn't take so many iterations:

# Throughout, d,u,r,l represents lasers going down, up, left, or right
# `sources` are the character classes representing laser "sources" (i.e. any
# character that can, on the next round, cause a laser to enter the space
# immediately adjacent to it in the proper direction)
%sources=(d,'[|+#$vk%ZX]',u,'[|+#$^W%KX]',r,'[-G+#>k%KX]',l,'[-G+#<W%ZX]');
# `open` characters will not block a laser
%open=(d,'[-.*G/k\\\\Z',u,'[-.*G/W\\\\K',r,'[|.*$\\\\/kK',l,'[|.*$\\\\/ZW');
# One of each portal is changed into the corresponding letter in `qwertyuio`.
# At the start, each portal is 'open' and none of them is a source.
for$d(d,u,r,l){$open{$d}.='123456789qwertyuio]'}
# A mapping of 'open' characters to the characters they become when a laser
# goes through them. (This is used like a hash of hashes; see the assignment
# of `%h` below.)
%update=(d,'.|-+*$G#/Wk%\KZX',
    u,'.|-+*$G#/kW%\ZKX',
    r,'.-|+*G$#/Wk%\ZKX',
    l,'.-|+*G$#/kW%\KZX');
@q=split//,"qwertyuio";
local$/;$_=<STDIN>;
for$i(1..9){
    $m{$i}=$q[$i-1];
    $m{$m{$i}}=$i;
    s/$i/$m{$i}/e}
print "After substituting portals:\n";
print;
print "\n";
# Find the number of characters in each line and create a string of `.`'s,
# which will be used to correlate characters above/below one another in the
# grid with each other.
/.*?\n/;
$l='.'x((length$&)-1);
do{
    $changes=0;
    for$d(d,u,r,l){
        # `patterns` is a mapping from each direction to the regex representing
        # an update that must occur (i.e. a place where a laser must progress).
        # Each pattern is either a lookahead or lookbehind plus the necessary
        # "open" character class.
        %patterns=(d,"(?<=$sources{d}$l)$open{d}",
            u,"$open{u}(?=$l$sources{u})",
            r,"(?<=$sources{r})$open{r}",
            l,"$open{l}(?=$sources{l})");
        %h=split//,$update{$d};
        # Match against the pattern for each direction. Note whether any
        # matches were found.
        $changes+=s!$patterns{$d}!
            # If the "open" character for a map is in the `update` map, return
            # the corresponding value. Otherwise, the "open" character is a
            # portal.
            $h{$&} || ($v=$&,
                        # For portals, remove the input portal from the
                        # proper "open" list and add the output portal to
                        # the proper "source" list.
                       ($open{$d}=~s/$v// && $sources{$d}=~s/]/$m{$v}]/),
                       $v)
                    # This whole substitution should allow `.` to match
                    # newlines (see the definition of `$l` above), and the
                    # replacement must be an expression rather than a string
                    # to facilitate the portal logic. The `g` allows multiple
                    # updates per "frame"; it is left out of the golfed code.
                    !egs
    }
    # Print the next "frame".
    print;
    print "\n";
# Continue updating until no "open" spaces are found.
}while($changes);
# Print whether `*` is still present in the input.
print/\*/?"False\n":"True\n"
\$\endgroup\$
  • \$\begingroup\$ I experimented with this kind of approach (using bool arrays rather than regex) in Python but couldn't get anywhere close to this small. I think this a really thought-provoking approach! My attempts were wrong-headedly influenced by catpad.net/michael/apl with nice vid youtube.com/watch?v=a9xAKttWgP4 and petercollingridge.co.uk/blog/python-game-of-life-in-one-line \$\endgroup\$ – Will Sep 12 '14 at 9:38
  • 1
    \$\begingroup\$ @Will Thanks! I definitely realized how similar my efforts were to GoL around the time I worked out just how feasible it would be to use a different character for each possible combination of lasers going into and out of a portal. I think I might be able to shave off a few more characters, but...this clearly is not the optimal approach! \$\endgroup\$ – Kyle Strand Sep 12 '14 at 15:24
  • \$\begingroup\$ Also, if anyone knows a better way to handle the triple-escaped ``'s in the character classes in the first few lines, that would be lovely... \$\endgroup\$ – Kyle Strand Sep 12 '14 at 16:43
6
\$\begingroup\$

Python 338 351

def t(b):
 L=len;w=L(b[0])+3;b=list("@"*w+"@@".join(b)+"@"*w);w-=1;I=b.index
 for i in range(L(b)):
  c=b[i];d={"^":-w,"<":-1,">":1,"v":w}.get(c)
  if d:
   while c!='@':
    i+=d;c=b[i]
    if c=='*':b[i]='.'
    elif c in '/\\':d={-w:-1,w:1,1:w,-1:-w}[d]*(-1 if c=='/' else 1)
    elif c>'0':i+=I(c)-i or I(c,i+1)-i
 return "*" not in b

My unminified version actually plots the laser paths on the board, which is pretty:

>-+--\
..X..|
>-/--/
..X...

>----------\
1----------/
2----------1
3----------2
4----------3
5----------4
6----------5
7----------6
8----------7
9----------8
X----------9

>-@............*
>--@...........*
>---@..........*
>----@.........*
>-----@........*
>---X--@........
>-------@......*

/-------X+------\/3.....
@........|.....//\+\....
X........|....2\+1\/\...
\--------+----+///+++--<
.........X...//\\/+++--\
>--------+---+\+1+///-4|
4-------X/...\2\/3/\/..^

vvvvvvvvvvvvvvvvv
\\\\\\\\\\\\\\\\\
/////////////////
\\\\\\\\\\\\\\\\\
/////////////////
\\\\\\\\\\\\\\\\\
/////////////////
XXXXXXXXXXXXXXXX*

def debug(board,x,y):
    emit_dir = {
        "^":    ( 0, -1),
        "<":    (-1,  0),
        ">":    ( 1,  0),
        "v":    ( 0,  1),
    }
    class PortalException(Exception): pass
    xdir, ydir = emit_dir[board[y][x]]
    while True:
        # print "step (%d, %d) (%d, %d)" % (x, y, xdir, ydir)
        x += xdir
        y += ydir
        if y < 0 or y >= len(board) or x < 0 or x >= len(board[y]):
            return
        ch = board[y][x]
        if ch == '/':
            xdir, ydir = -ydir, -xdir
        elif ch == '\\':
            xdir, ydir = ydir, xdir
        elif ch in '@^><v':
            return
        elif ch == '*':
            board[y] = board[y][:x] + 'X' + board[y][x+1:]
        elif ch in '.-|':
            ch = ('-' if xdir else '|') if ch == '.' else '+'
            board[y] = board[y][:x] + ch + board[y][x+1:]
        elif ch in '123456789':
            try:
                for r in range(len(board)):
                    for c in range(len(board[r])):
                        if board[r][c] == ch and (r != y or c != x):
                            x, y = c, r
                            raise PortalException()
                raise Exception("could not find portal %s (%d,%d)" % (ch, x, y))
            except PortalException:
                pass
\$\endgroup\$
5
\$\begingroup\$

C# - 515 414 400 bytes

Complete C# program, no nice output like Will's. Works by following the laser path for each emitted individually, and keeping an array of which cells we've visited, so that we can check that we've visited all the stars at the end. Edit: striped a large number of bytes by making everything 1D and by using a char instead of an int to store the current char

w0lf reminded me that I had an under utilized for-loop right in the middle of my code, so I figured I'd better make one last effort and put it to work, and now I'm down to the absolute minimum number of curly braces. I won't pretend to like the collapsing of the second for loop, the code is horribly disorderly now, but it saved a few bytes. In the process I re-wrote the portal handling. I also found a shorter method for performing the "move" with nested rather than aggregated conditional operation.

Golfed code:

using C=System.Console;class P{static void Main(){var S=C.In.ReadToEnd().Replace("\r","");int W=S.IndexOf('\n')+1,l=S.Length,i=l,d,m,n;var M=new int[l];for(char c;i-->0;)for(d="^<v>".IndexOf(c=S[m=i]);c>14&d>-1;d=(m+=d==2?W:d>0?d-2:-W)>=0&m<l&&"@^<v>".IndexOf(c=S[m])<0?d:-1)for(d=c==47?3-d:c==92?d^1:d,M[n=m]=1;c%49<9&&(m=S.IndexOf(c,m+1))==n|m<0;);for(;l-->0;)W*=S[l]==42?M[l]:1;C.WriteLine(W>0);}}

Less golfed code:

using C=System.Console;

class P
{
    static void Main()
    {
        var S=C.In.ReadToEnd().Replace("\r",""); // read the grid, remove pesky carriage returns
        int W=S.IndexOf('\n')+1,l=S.Length,i=l,d,m,n; // find "width"
        var M=new int[l]; // defaults to 0s

        for(char c;i-->0;) // for each cell

            for(d="^<v>".IndexOf(c=S[m=i]); // find initial direction, if any
                c>14&d>-1; // loop only if we have direction
                d=(m+=d==2?W:d>0?d-2:-W) // move (after iteration)
                >=0&m<l&&"@^<v>".IndexOf(c=S[m])<0?d:-1) // terminate if we hit something or go off edge

                for(d=c==47?3-d:c==92?d^1:d, // mirrors
                    M[n=m]=1; // we have seen this spot
                    c%49<9&&(m=S.IndexOf(c,m+1))==n|m<0;); // portals

        for(;l-->0;) // for each cell
            W*=S[l]==42?M[l]:1; // if *, then mul by whether seen

        C.WriteLine(W>0);
    }
}

The new portal handling code utilizes the fact that the String.IndexOf function happily returns -1 (i.e. char not found) if you ask it start looking 1 character beyond the string (throws an exception if you ask it to start any further beyond). This was news to me, but was awfully convenient in this instance.

\$\endgroup\$
  • \$\begingroup\$ +1 Awesome golfing! I just thought of a trick: you could take the m+=(d>0?d-2:0)+(d<3?d-1:0)*W; and shove it in the for, like this: for(char c;i-->0;m+=(d>0?d-2:0)+(d<3?d-1:0)*W). This way, you'll save one char, because you'll lose a semicolon. \$\endgroup\$ – Cristian Lupascu Sep 13 '14 at 16:04
  • \$\begingroup\$ @w0lf made a last effort and managed to collapse the for loops completely, thanks for the nudge ;) \$\endgroup\$ – VisualMelon Sep 14 '14 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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