17
\$\begingroup\$

The purpose of this challenge is to figure out whether all the dominoes will fall, given an input string representing a top view of the table.

Input format

The program can take the input as a single string with newlines or a list of strings. Spaces denote, well, empty spaces, and the rest represent dominoes.

The start domino and the direction the dominoes start to fall will be denoted by one of <(left),> (right), ^ (up), v(down). There will be exactly one start domino in the input.

The other dominoes will be represented by one of the following four characters:

  • | - falls right when pushed from the left, falls left when pushed from the right
  • - - falls up when pushed from the bottom, falls down when pushed from above
  • / - falls right when pushed from the top and vice versa, falls left when pushed from the bottom and vice versa
  • \ - falls left when pushed from the top and vice versa, falls right when pushed from the bottom and vice versa.

Basically, | and - keep the momentum going in the same direction, and the slashes (/ and \) cause quarter-turns.

Dominoes may not fall twice. If a domino falls, you may consider that an empty space in the next iteration.

Pushing - from the left or right and pushing | from the top or bottom are undefined behavior.

Output

A truthy/consistent value if all the dominoes will fall, and a consistent falsy value otherwise

Here's an example to make it a bit more clear (o represents a fallen domino for the sake of this example):

Step 1 - Starts at the 4th domino in the first row
\||<
-
-  -
\||\

Step 2 - start domino has fallen
\||o
-
-  -
\||\

Step 3 - Go left because start was '<'
\|oo
-
-  -
\||\

Step 4 - keep going left
\ooo
-
-  -
\||\

Step 5 - keep going left
\ooo
-
-  -
\||\

Step 6 - keep going to left, will go down next
oooo
-
-  -
\||\

Step 7 - change direction, go down because of '\'
oooo
o
-  -
\||\

Step 8 - keep going down
oooo
o
o  -
\||\

Step 9 - go down, will go left next because of '\'
oooo
o
o  -
o||\

Oops! Can't go any further, so output should be a falsy value

Rules

Just to clarify, there's no gravity or anything. The direction depends on the position of the domino (/, \, |, or -)

This is , so shortest code in bytes wins.

More test cases:

Truthy

>
_________________________________________________________

\|||<
-
-
/|||
__________________________________________________________

     \|/
     /|/
       -
       -
    \||\
    ^

Falsy

\|/
- -
/|/|  <-This last '|' doesn't fall, because the '/' before it has already fallen once
  ^
__________________________________________________________

|< |  <- This last '|' doesn't fall, because the dominoes don't wrap around.
__________________________________________________________

>||\||   Because after the '\', it tries to go up

Undefined behavior:

>-       Can't push '-' from the left
```
\$\endgroup\$
9
  • \$\begingroup\$ Related (harder than this), also related. Sandbox \$\endgroup\$
    – user
    Sep 20, 2020 at 19:04
  • \$\begingroup\$ Okay, I just realized this challenge also exists, but I believe it's sufficiently different from this question \$\endgroup\$
    – user
    Sep 20, 2020 at 19:16
  • \$\begingroup\$ The behavior of the slashes is a little unexpected to me, I would expect naïvely for >||\|| to be truthy but based on the description it seems falsy. Could you add it as a test case? \$\endgroup\$
    – Wheat Wizard
    Sep 20, 2020 at 19:32
  • \$\begingroup\$ @WheatWizard Yup, done. Could you tell me why you expected it to be truthy so I can clear that up in my question better? \$\endgroup\$
    – user
    Sep 20, 2020 at 19:34
  • 2
    \$\begingroup\$ I would expect a domino like that to fall on a diagonal, hitting either above or to the right. It is just sort of the way dominoes seem to fall in real life. But here each domino can only hit one potential place. \$\endgroup\$
    – Wheat Wizard
    Sep 20, 2020 at 19:37

3 Answers 3

7
\$\begingroup\$

Charcoal, 86 69 bytes

WS⊞υι≔⪫υ¶θ≔v>^<ηPθ…θ⌈Eη⌕θιW№ηKK«↶⊗⁺³⌕ηKK≔ⅈι ≔§⪪\-//|\³⁻ⅈιη»≔⌈KAθ⎚→‹θ!

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if all the dominoes fall, nothing if some remain. Explanation:

WS⊞υι≔⪫υ¶θ

Input the table as an array of strings and join them together.

≔v>^<η

Make a string of rotations for the starting domino characters. The string starts with the character for a clockwise rotation, then the one for no rotation, then an anticlockwise rotation, then a u-turn.

Pθ…θ⌈Eη⌕θι

Print the table and then up until the (last) occurrence of one the starting domino characters.

W№ηKK«

While the current character is present in the table of rotations...

↶⊗⁺³⌕ηKK

... pivot according to the position of the character in the table of rotations (annoyingly I have to spend an extra byte adding 3 instead of subtracting 1 because Charcoal can't pivot by negative amounts)...

≔ⅈι ≔§⪪\-//|\³⁻ⅈιη

... and, temporarily saving the current X-coordinate, erase the current character, moving in the current direction, then choose the list of valid characters (again listed in the order rotate clockwise, don't rotate, rotate anticlockwise) depending on whether the current direction is vertical or horizontal (detected via the change in X-coordinate, since Charcoal has no builtin to read the current direction).

»≔⌈KAθ⎚→‹θ!

Check that only spaces are left.

\$\endgroup\$
6
\$\begingroup\$

Java 10, 312 304 298 295 bytes

m->{int i=m.length,j,x=0,y=0,d=0,t;for(;i-->0;)for(j=m[i].length;j-->0;d=t<0?d:t+(m[y=i][x=j]=0))t="<>^v".indexOf(m[i][j]);try{for(;;t=m[y+=d/2*t][x+=d<2?t:0],m[y][x]=0,d=t>99?d<2?d:d/0:t>91?(d+3)%6-d%3*2:t>46?d+2&3:t>44&d>1?d:d/0)t=d%2*2-1;}finally{for(var r:m)for(var c:r)i+=c/33;return i<0;}}

-9 bytes thanks to @ceilingcat.

Input as a character matrix.

Try it online.

Explanation:

m->{                        // Method with char-matrix input & boolean return
  int i=m.length,           //  Index-integer `i`, starting at the amount of rows
      j,                    //  Index-integer `j`, uninitialized
      x=0,y=0,              //  Current `x,y`-coordinates, starting at 0,0
      d=0,                  //  Current direction, starting at 0
      t;                    //  Temp-integer
  for(;i-->0;)              //  Loop `i` over all rows:
    for(j=m[i].length;j-->0 //   Inner loop `j` over each cell:
        ;                   //     After every iteration:
         d=                 //      Set `d` to:
           t<0?             //       If index `t` is -1 (thus NOT our start position):
            d               //        Leave `d` as is
           :                //       Else (we've found out start position):
            t               //        Set `d` to `t`
             +(m[y=i]       //        Set `y` to `i`
                [x=j]       //        Set `x` to `j`
                     =0))   //        Empty this cell containing the starting character
      t="<>^v".indexOf(m[i][j])
                            //    Set `t` to the index of the current character in
                            //    "<>^v", or -1 if it's a different character
  try{for(;                 //  Loop indefinitely:
           ;                //    After every iteration:
            t=m[y+=d/2*t]   //     Adjust the `y`-coordinate based on the direction
               [x+=d<2?t:0],//     Do the same for the `x`-coordinate
                            //     And set `t` to the character of this new cell
            m[y][x]=0,      //     Then empty this cell
            d=              //     And change the direction to:
              t>99?         //      If the current character is '|':
                   d<2?     //       If the direction is left/right:
                       d    //        Leave the direction as is
                      :     //       Else (it's up/down instead)
                       d/0  //        Throw a division-by-zero error
              :t>91?        //      Else-if the character is '\':
                    (d+3)%6-d%3*2
                            //       Change the direction: 0→3; 1→2; 2→1; 3→0
              :t>46?        //      Else-if the character is '/':
                     d+2&3  //       Change the direction: 0→2; 1→3; 2→0; 3→1
              :t>44         //      Else-if the character is '-':
                   &d>1?    //       And the direction is up/down:
                        d   //        Leave the direction as is
              :             //      Else (the character is '-', but the direction is
                            //      left/right, OR the character is ' ' or an emptied
                            //      cell):
               d/0)         //       Throw a division-by-zero error
        t=d%2*2-1;}         //   Set `t` depending on `d`: 0→-1; 1→1; 2→-1; 3→1
  finally{                  //  After an error has occurred (either a manual 
                            //  division-by-zero, or ArrayIndexOutOfBoundsException):
    for(var r:m)            //   Loop over all rows of the matrix:
      for(var c:r)          //    Inner loop over all cells:
        i+=                 //     Increase `i` by:
           c/33;            //      The codepoint of the cell integer-divided by 33
    return i<0;}}           //   Return whether `i` is still -1
                            //   (`i` is -1 when we enter the finally, and will
                            //    remain that way if all cells are either a space or
                            //    emptied)
\$\endgroup\$
2
  • 2
    \$\begingroup\$ I do love those try { ... } finally { ... return ... } constructs! \$\endgroup\$
    – Neil
    Sep 21, 2020 at 10:16
  • \$\begingroup\$ @Neil Yeah, I don't use them to often in codegolf, but it certainly helps a lot here by catching both ArrayIndexOutOfBoundsExceptions if we go outside of the matrix after a direction change, or manually when we can't continue from the current cell onward. :) \$\endgroup\$ Sep 21, 2020 at 10:22
4
\$\begingroup\$

Python 3, 323 bytes

def f(m,e=enumerate,z='^v<>'):
 for a,r in e(m):
  for b,i in e(r):
   if i in z:x,y=b,a;c,d=[(0,-1),(0,1),(-1,0),(1,0)][z.index(i)]
 while 1:
  try:
   m[y][x]=' '
   if all(i==' 'for i in sum(m,[])):return 1
   x+=c;y+=d;n=m[y][x];assert (n!=' ')&(x>=0)&(y>=0)
  except:return 0
  if n=='/':c,d=d,c
  if n=='\\':c,d=-d,-c

Try it online!

Version showing each step

Quite simply moves through the dominoes, recording the current coordinates and direction, and making sure we haven't gone of the board/stopped knocking over dominoes/removed all dominoes.

Less golfed version:

def main(chars):
    for this_y, row in enumerate(chars):
        for this_x, char in enumerate(row):
            if char in '^v<>':
                x, y = this_x, this_y
                dx, dy = [(0, -1), (0, 1), (-1, 0), (1, 0)]['^v<>'.index(char)]
    while True:
        try:
            chars[y][x] = ' '
            if all(i == ' ' for i in sum(chars, [])):
                return True
            x += dx
            y += dy
            char = chars[y][x]
        except IndexError:
            return False
        if char == ' ':
            return False
        if x < 0 or y < 0:
            return False
        elif char == '/':
            dx, dy = dy, dx
        elif char == '\\':
            dx, dy = -dy, -dx
\$\endgroup\$

Your Answer

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

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