Topple some dominoes!

Question

Thanks to this question for some inspiration

In this challenge we will represent a line of dominoes as a string of |, / and \. You will be given a string of dominoes as input and you must determine what they look like when they have settled. Here are the rules for how dominoes fall over

• A standing domino, |, left of a left fallen domino, \, will become a left fallen domino as well.

• A standing domino, |, right of a right fallen domino, /, will become a right fallen domino as well.

• If a standing domino is between a left fallen \ and a right fallen / domino, it will remain standing.

These rules are applied repeatedly until the arrangement no longer changes.

Here is an example of how a single input might arrive at its conclusion

|||||||\/|||||||\||\|||/||||||\|||||

||||||\\//|||||\\|\\|||//||||\\|||||
|||||\\\///|||\\\\\\|||///||\\\|||||
||||\\\\////|\\\\\\\|||////\\\\|||||
|||\\\\\////|\\\\\\\|||////\\\\|||||
||\\\\\\////|\\\\\\\|||////\\\\|||||
|\\\\\\\////|\\\\\\\|||////\\\\|||||

\\\\\\\\////|\\\\\\\|||////\\\\|||||

Your task is to write code that finds and outputs the end result of a input. You may assume that the input is always valid and contains at least 2 characters.

This is code-golf so answers will be scored in bytes with fewer bytes being better.

Test cases

|||/||||  -> |||/////
|||\||||  -> \\\\||||
|/||||\|  -> |///\\\|
||/|||\|  -> ||//|\\|
||\|||/|  -> \\\|||//

Answer 1

Retina, 32 bytes

+`(/.\\)|(/)\||\|(\\)
$1$2$2$3$3

Try it online!

Explanation

The + tells Retina to run the replacement in a loop until it fails to change the string. Each replacement computes one step the falling dominoes. The replacement itself is really three replacements in one, but this ensures that they happen simultaneously:

(/.\\)...
$1

This just matches /|\ (as well as /\\ and /\\, but those don't matter) and reinserts it unchanged. The purpose of this is to skip over | with fallen dominoes on both sides, because this is shorter than ruling out those cases with separate lookarounds in the other two cases.

...(/)\|...
$2$2

This matches /| and turns it into //.

...\|(\\)
$3$3

This matches |\ and turns it into \\.

Answer 2

Python 2, 115 114 111 108 98 95 bytes

^{-1 byte thanks to ovs}

a=input()
for i in range(4)*len(a):a=a.replace('//|x||\ \\'[i::4],'/\/x|\/ \\'[3-i::4])
print a

Try it online!

Answer 3

V, 23 bytes

òÓ¯À<!|¨Ü©ü¨¯©|ÜÀ!/±±²²

Try it online!

Really, this is very similar to the retina answer, just that it looks uglier. Uses regex compression.

Hexdump:

00000000: f2d3 afc0 3c21 7ca8 dca9 fca8 afa9 7cdc  ....<!|.......|.
00000010: c021 2fb1 b1b2 b2                        .!/....

Explanation:

ò tells V to run until the string doesn't change. The rest is a compressed regex. Let's convert it into the vim equivalent...

:s/\v\/@<!\|(\\)|(\/)\|\\@!/\1\1\2\2/g

:s/                                     " Substitute...
   \v                                   " Turn on magic (use less escaping)
          \|                            " A bar
            (\\)                        " Followed by a captured backslash
       @<!                              " That is not preceded by
     \/                                 " A forward slash
                |                       " OR...
                 (\/)                   " A captured forward slash
                     \|                 " Followed by a bar
                       \\@!             " That is not followed by a backslash
                           /            " Replace this with
                            \1\1        " Pattern 1 twice (will be empty if we matched the second path)
                                \2\2    " Pattern 2 twice (will be empty if we matched the first path)
                                    /g  " Replace every match on this line

Answer 4

SNOBOL4 (CSNOBOL4), 117 115 112 111 bytes

	D =INPUT
S	D '/|\' ='_'	:S(S)
	E =D
	D '/|' ='//'
	D '|\' ='\\'
	D E	:F(S)
R	D '_' ='/|\'	:S(R)
	OUTPUT =D
END

Try it online!

Credit to Rod's python answer for the idea for the stopping condition with a second variable to see changes rather than testing D '/|' | '|\'.

	D =INPUT		;* read input
S	D '/|\' ='_'	:S(S)	;* replace '/|\' with '_', recursively
	E =D			;* set E to D, this is the while loop
	D '/|' ='//'		;* topple right
	D '|\' ='\\'		;* topple left
	D E	:F(S)		;* if D doesn't match E, goto S
R	D '_' ='/|\'	:S(R)	;* replace '_' with '/|\' (inverse of statement S)
	OUTPUT =D		;* output
END

Answer 5

Perl 5, 39 + 1 (-p) = 40 bytes

s%(?<!/)\|(\\)|(/)\|(?!\\)%$+$+%g&&redo

Try it online!

Answer 6

Haskell, 114 107 bytes

until=<<((==)=<<)$g
g s=t<$>zip3('|':s)s(tail s++"|")
t(l,'|',r)|l<'0',r/='\\'=l|r=='\\',l>'/'=r
t(_,e,_)=e

Try it online! The first line defines an anonymous function.

Explanation:

• until=<<((==)=<<)$g is a fix point function (see here for an explanation) which applies the function g to the input string until the result no longer changes.
• zip3('|':s)s(tail s++"|") creates for each domino, that is character in the string s, a triple with the pre- and succeeding domino, padding with | at the edges. E.g. /\| becomes [(|,/,\),(/,\,|),(\,|,|)] (ignoring escaping).
• Then the function t is applied to each of the triples to compute the new position of the centre piece of the triple.

Answer 7

Prolog (SWI), 132 bytes

+[]-->[].
+[47,124,92|T]-->"/|\\",+T.
+[47,47|T]-->"/|",+T.
+[92,92|T]-->"|\\",+T.
+[X|T]-->[X],+T.
X+Y:- +(N,X,[]),!,(X=N,Y=N;N+Y).

Try it online!

This program defines a predicate +/2 that is true if the second argument is the settled version of the first. Both arguments are lists of character codes.

Explanation

This solution uses a DCG to figure out what the next step is and then repeatedly calculates the next step until the next step is the same as the current step.

The DCG

+[]-->[].
+[47,124,92|T]-->"/|\\",+T.
+[47,47|T]-->"/|",+T.
+[92,92|T]-->"|\\",+T.
+[X|T]-->[X],+T.

These five lines of code define a DCG (Definite Clause Grammar) rule + that is used in the program to calculate a single step of dominoes toppling. DCGs in Prolog work by finding the first case of the rule whose right hand side matches the string and determining the argument of the rule on the left hand side through that process. If a case fails to match then it will backtrack and try a later case.

+[]-->[].

This line represents the base case of the + rule. It simply states that if there are no dominoes currently then in the next step there will still be no dominoes.

+[47,124,92|T]-->"/|\\",+T.

Since this program deals exclusively with lists of character codes it is important to note that the character codes for /, \, and | are 47, 92, and 124 respectively. This case of the + rule handles the /|\ string.

+[47,47|T]-->"/|",+T.

This case handles a right falling domino knocking over the domino the right of it. Since it comes after the case for handling /|\ it will not be used for that possibility.

+[92,92|T]-->"|\\",+T.

Handles the case for a left falling domino knocking over the domino to the left of it.

+[X|T]-->[X],+T.

This is the wildcard case. Since nothing else changes besides what is described above, so long as there is text left in the input string it will just copy it over to the output so long as it does not match any of the above cases.

The Predicate

X+Y:- +(N,X,[]),!,(X=N,Y=N;N+Y).

The main predicate takes two arguments, the first one is the initial domino setup, the second is the settled dominoes. Since this is Prolog the second can be undetermined and the program will calculate it. The predicate in and of itself is fairly simple +(N,X,[]) calls the DCG and calculates the next step of the dominoes storing it in N. (X=N,Y=N;N+Y) checks if the next step of the dominoes is the same as the current and if it is it sets Y to it since the dominoes must have settled and if it is not it recurses, calling the same predicate with the next step of the dominoes N instead of X.

Answer 8

APL (Dyalog), 36 bytes

({(↑∘1¨3 ¯3)⍳⊂⍵≠'/|\'}⊃'\/',2⊃⊢)⌺3⍣≡

Try it online!

-3 partially thanks to Cows Quack.

Feels so ungolfed...:(

Answer 9

face, 166 bytes

\|/,cm_/o>AvI[IIcP/+PP|m_/m*/Sl*Im1/11:~-_I|'|?_1-_P|?_1`I-III_|+II|'I.C:1-_I|?_C'|-_P|?_C_|'I-_I|`I?_!'I.C:!'|'|-III+II|'I:C_|-PPP+PPI'I?I~_I-PPP+PP|-**1?*~Sl*Iw*I*>

Takes input as a command line argument and outputs to STDOUT. This only works in commit 86494f6 and beyond due to a bugfix in that commit.

Wrapped for aesthetics:

\|/,cm_/o>AvI[IIcP/+PP|m_/m*/Sl*Im1/11:~-_I|'|?_1-_P|?_1`I
-III_|+II|'I.C:1-_I|?_C'|-_P|?_C_|'I-_I|`I?_!'I.C:!'|'|-III
+II|'I:C_|-PPP+PPI'I?I~_I-PPP+PP|-**1?*~Sl*Iw*I*>

And ungolfed / commented:

\|/,cm_/o>              ( setup )

AvI[II                  ( store input into I )
cP/+PP|m_/              ( store 92, ascii for \, into P, meaning prev char )
m*/Sl*Im1/11            ( store length of input into counter variable * )

( main loop: )
:~

    -_I|'|?_1           ( branch to 1 if the character is not \ )
    -_P|?_1             ( also branch to 1 if the previous character wasn't | )
    `I-III_|+II|'I      ( we have a sequence |\ so prev needs to be toppled )
    .C                  ( jump to C, the "continue" label at end of loop )

    :1
    -_I|?_C             ( branch to C if the character is not | )
    '|-_P|?_C           ( also branch to C if the previous character wasn't / )
    _|'I-_I|`I?_!       ( branch to ! if the next character isn't \ )
    'I.C:!              ( otherwise, skip the next \ and branch to continue )
    '|'|-III+II|'I      ( if all conditions hold we have /|| or /|/ so topple )

    :C
    _|                  ( reset pointer to source )
    -PPP+PPI            ( update prev variable )
    'I                  ( step through data )

?I~

_I-PPP+PP|-**1          ( reset input/prev and decrement counter )
?*~                     ( repeat main loop as many times as there are chars )

Sl*Iw*I*>               ( output final string to stdout )

There's a few subtle tricks in here that shave off a few extra bytes, such as

• the naming of the variables | and /, whose ASCII values are accessed via introspection later in the code

• the '| on the first line of the main loop, which is called there instead of on the second line in order to set the | pointer for use in the second section of the main loop

Answer 10

Perl 5, 52+1(-p) = 53 bytes

-6 bytes thanks to mik

Probably not the best possible for Perl, but it's what I could come up with.

0while(s/(?<!\/)\|(?=(\\))|(?<=(\/))\|(?!\\)/$1$2/g)

Explanation

while(
  s/
    (?<!\/)\|(?=(//)) # If there's a | that precedes a \ but doesn't follow a /, capture /
      | # Or
    (?<=(\/))\|(?!//)/ # If there's a | that follows a / doesn't precede a \, capture /
  /$1$2/ # Replace all | with capture group 1 or 2, as one of the two will always be empty
  g # Repeat as much as possible for this string
)

Try it online!

Answer 11

Clean, 98 bytes

import StdEnv
$['/|':t]=['//': $t]
$['|\\':t]=['\\\\': $t]
$[h:t]=[h: $t]
$e=e
f=until(\e=e== $e)$

Try it online!

Answer 12

Perl 5 -p, 44 bytes

1while s,(/)\|(?!\\)|(?<!/)\|(\\),$1$1$2$2,g

Try it online!

Explanation

1while s,                        ,        ,g   while anything found substitute globally
         (/)\|(?!\\)              $1$1         /| that is not followed by \ to //
                    |                          or
                     (?<!/)\|(\\)     $2$2     |\ that is not preceded by / to \\

Answer 13

Jelly, 32 bytes

i@€Ø2jḅ3ị“½jỊA!S’ḃ3¤Ɗ3ƤƊÐLịɗ“\|/

Try it online!

There's probably a much better way to do this.

Answer 14

Ruby, 83 bytes

Technically cheatable with 9.times, or even just 999.times but I don't feel like being cheap :)

Still has huge golfing potential. (Note: y while undone is far longer than x.size.times)

->x{x.size.times{x.gsub! /\/\|\\?|\|\\/,'/|\\'=>'/|\\','/|'=>'//','|\\'=>'\\\\'}
x}

Try it online!

Answer 15

R, 114 bytes

function(d){g=gsub
for(i in 1:nchar(d))d=g("/|","//",g("|\\","\\\\",g("/|\\","_",d,f=T),f=T),f=T)
g("_","/|\\",d)}

Try it online!

Returns an escaped string.

Answer 16

C (gcc), 183 bytes

D,i;f(char*S){char*s=malloc(-~strlen(S));for(D=1;D--;strcpy(S,s))for(strcpy(s,S),i=0;s[i];i++)s[i]>92&&(S[-~i]==92&&S[~-i]!=47&&(s[i]=92,D=1)||S[~-i]==47&&S[-~i]!=92&&(s[i]=47,D=1));}

Try it online!