Skip to main content
replaced http://stackoverflow.com/ with https://stackoverflow.com/
Source Link

Now the fun part... we sleep for a bit with the help of catastrophic backtrackingcatastrophic backtracking. There is an exponential amount of ways to split up a match of (a+)+ between repetitions of the group. Because the b causes the match to fail, the engine will backtrack and try every single one of those combinations before deciding that (a+)+b can't match. For the twenty as at the end that takes something like half a second.

Now the fun part... we sleep for a bit with the help of catastrophic backtracking. There is an exponential amount of ways to split up a match of (a+)+ between repetitions of the group. Because the b causes the match to fail, the engine will backtrack and try every single one of those combinations before deciding that (a+)+b can't match. For the twenty as at the end that takes something like half a second.

Now the fun part... we sleep for a bit with the help of catastrophic backtracking. There is an exponential amount of ways to split up a match of (a+)+ between repetitions of the group. Because the b causes the match to fail, the engine will backtrack and try every single one of those combinations before deciding that (a+)+b can't match. For the twenty as at the end that takes something like half a second.

added 28 characters in body
Source Link
Martin Ender
  • 197.2k
  • 67
  • 447
  • 975

Explanation

^.{0,79}$
$0 

We start by appending a space if the input contains fewer than 80 characters. This is so that a / at the right end does not have to be treated separately.

:`^
<ESC>c

Now we prepend <ESC>c to the string, which is the ANSI escape code for clearing the terminal. So every time the string is printed it will do so at the top of the terminal. The :` instructs Retina to print out the result of this substitution, i.e. the initial configuration.

(`/ | \\
__

(` begins a loop. Since there is no matching ), the loop is assumed to go until the last stage of the program. Each iteration will simulate one step of the dominoes falling and then "sleep" a bit. This first stage replaces / and \ next to a space into __. This automatically handles the / \ case correctly, because matches cannot overlap and are searched for from left to right. So the /<sp> would be matched and turned into __ such that the \ can't be matched, and we get the correct __\.

/\|(?!\\)
//a

This turns /| into // provided there's no \ next to it. We append an a such that this new / doesn't mess with the next stage (which shouldn't "know" about this change yet).

(?<!/)\|\\
\\

The opposite situation: turn |\ into \\ provided there's no / next to it. We don't need to put an a here, because we're done with this step of the simulation.

Now the sleeping part...

$
aaaaa

Appends 5 more as to the end of the code.

a
aaaa

Turns each a into 4 as, so we get 20 as at the end.

(a+)+b|a
<empty>

Now the fun part... we sleep for a bit with the help of catastrophic backtracking. There is an exponential amount of ways to split up a match of (a+)+ between repetitions of the group. Because the b causes the match to fail, the engine will backtrack and try every single one of those combinations before deciding that (a+)+b can't match. For the twenty as at the end that takes something like half a second.

At the same time, we allow the regex to match a single a, but only after doing the backtracking. When that matches, we replace it with an empty string, removing all the as we inserted for one reason or another from the string.

That leaves printing the string at the end of the loop iteration. Here it comes in handy that I haven't fixed the printing behaviour of loops in Retina yet. Currently, there is only one flag for each stage, which says "print" or "don't print". The default is "don't print" except for the last stage in the program, which defaults to "print". But the stage is looped, so that means it actually prints the current string on each iteration. Normally, that is really annoying, and you almost always need to include an additional empty stage at the end if you only want the final result, but here it lets me save four bytes.

Explanation

^.{0,79}$
$0 

We start by appending a space if the input contains fewer than 80 characters. This is so that a / at the right end does not have to be treated separately.

:`^
<ESC>c

Now we prepend <ESC>c to the string, which is the ANSI escape code for clearing the terminal. So every time the string is printed it will do so at the top of the terminal. The :` instructs Retina to print out the result of this substitution, i.e. the initial configuration.

(`/ | \\
__

(` begins a loop. Since there is no matching ), the loop is assumed to go until the last stage of the program. Each iteration will simulate one step of the dominoes falling and then "sleep" a bit. This first stage replaces / and \ next to a space into __. This automatically handles the / \ case correctly, because matches cannot overlap and are searched for from left to right. So the /<sp> would be matched and turned into __ such that the \ can't be matched, and we get the correct __\.

/\|(?!\\)
//a

This turns /| into // provided there's no \ next to it. We append an a such that this new / doesn't mess with the next stage (which shouldn't "know" about this change yet).

(?<!/)\|\\
\\

The opposite situation: turn |\ into \\ provided there's no / next to it. We don't need to put an a here, because we're done with this step of the simulation.

Now the sleeping part...

$
aaaaa

Appends 5 more as to the end of the code.

a
aaaa

Turns each a into 4 as, so we get 20 as at the end.

(a+)+b|a
<empty>

Now the fun part... we sleep for a bit with the help of catastrophic backtracking. There is an exponential amount of ways to split up a match of (a+)+ between repetitions of the group. Because the b causes the match to fail, the engine will backtrack and try every single one of those combinations before deciding that (a+)+b can't match. For the twenty as at the end that takes something like half a second.

At the same time, we allow the regex to match a single a, but only after doing the backtracking. When that matches, we replace it with an empty string, removing all the as we inserted for one reason or another from the string.

That leaves printing the string at the end of the loop iteration. Here it comes in handy that I haven't fixed the printing behaviour of loops in Retina yet. Currently, there is only one flag for each stage, which says "print" or "don't print". The default is "don't print" except for the last stage in the program, which defaults to "print". But the stage is looped, so that means it actually prints the current string on each iteration. Normally, that is really annoying, and you almost always need to include an additional empty stage at the end if you only want the final result, but here it lets me save four bytes.

added 28 characters in body
Source Link
Martin Ender
  • 197.2k
  • 67
  • 447
  • 975

Retina, 87 8686 85 bytes

Thanks to Dennis for saving 1 byte.

:`$
<ESC>[A
^.{0,79}$
$0 
:`^
<ESC>c
(`/ | \\
__
/\|(?!\\)
//a
(?<!/)\|\\
\\
$
aaaaa
a
aaaa
(a+)+b|a
<empty>

<ESC> should be replaced by the actual control character (0x1B). <empty> represents an empty trailing line. You can then run the above code from a single file with the -s flag.

The code requires a terminal which supports ANSI escape codes. I can't suppress the line feed in Retina's output so I need to moveclear the cursor back upentire console with <ESC>[A<ESC>c to print on the same line againeach time. I've tested the code in bash using Mono to run Retina.

Retina, 87 86 bytes

:`$
<ESC>[A
^.{0,79}$
$0 
(`/ | \\
__
/\|(?!\\)
//a
(?<!/)\|\\
\\
$
aaaaa
a
aaaa
(a+)+b|a
<empty>

<ESC> should be replaced by the actual control character (0x1B). <empty> represents an empty trailing line. You can then run the above code from a single file with the -s flag.

The code requires a terminal which supports ANSI escape codes. I can't suppress the line feed in Retina's output so I need to move the cursor back up with <ESC>[A to print on the same line again. I've tested the code in bash using Mono to run Retina.

Retina, 87 86 85 bytes

Thanks to Dennis for saving 1 byte.

^.{0,79}$
$0 
:`^
<ESC>c
(`/ | \\
__
/\|(?!\\)
//a
(?<!/)\|\\
\\
$
aaaaa
a
aaaa
(a+)+b|a
<empty>

<ESC> should be replaced by the actual control character (0x1B). <empty> represents an empty trailing line. You can then run the above code from a single file with the -s flag.

The code requires a terminal which supports ANSI escape codes. I can't suppress the line feed in Retina's output so I need to clear the entire console with <ESC>c each time. I've tested the code in bash using Mono to run Retina.

Post Undeleted by Martin Ender
Post Deleted by Martin Ender
deleted 2 characters in body
Source Link
Martin Ender
  • 197.2k
  • 67
  • 447
  • 975
Loading
Source Link
Martin Ender
  • 197.2k
  • 67
  • 447
  • 975
Loading