Game of Life arrowslits

26

Background

This challenge is in honor of apsillers, who won the Not as simple as it looks category in Best of PPCG 2016 with their challenge Can my 4-note music box play that song? Congratulations!

On their "About Me" page, this user has a really neat simulator for the Game of Life cellular automaton. (Seriously, go check it out.) On the other hand, the word aspillera is Spanish for "arrowslit". In light of these facts, this challenge is about arrowslits in Game of Life.

Game of Life arrowslits

In GoL, we will represent an arrow by a glider, and a wall by a sequence of blocks. A single glider approaches the wall from above, and tries to fly through a gap in the wall (the arrowslit). Your task is to check whether the glider passes through the arrowslit or crashes into the wall.

Input

Your input is a grid of bits, which represents a GoL configuration. You can take it in any reasonable format (multiline string of any two distict printable ASCII characters, list of strings, 2D array of integers, 2D array of booleans etc). For clarity, I will use multiline strings of the characters .# in the following.

The input is guaranteed to have several properties. First, its height is 2N for some N ≥ 6, and its width is at least 2N+2. The input will be all .s, except that somewhere on the top three rows is a glider, and on the two middle rows there is a wall of blocks. The glider will be heading southwest or southeast, and its position is such that if the walls are removed, it will not pass through a side edge before reaching the bottom edge (but it may reach a corner of the grid). The glider is initially separated from the left and right edges by at least one step of .s. It can be in any phase.

The wall consists of blocks, which are separated by one column of .s, except in one place, where they will be separated by at least two columns of .s. Like the glider, the leftmost and rightmost blocks are also separated from the edges by one step of .s. There will always be at least one block on the left edge and one block on the right edge.

Here is an example of a valid input grid:

....#......................
..#.#......................
...##......................
...........................
...........................
...........................
.##.##............##.##.##.
.##.##............##.##.##.
...........................
...........................
...........................
...........................
...........................
...........................

Output

As stated, your task is to determine whether the glider crashes into the wall or makes it through to the south edge. For the purposes of this challenge, a crash occurs if the configuration no longer consists of a single glider and the wall of blocks, regardless of what happens later in the simulation. The following diagrams show the smallest gaps that a southeast glider can go through without crashing in the two distinct phases (the condition for southwest gliders is symmetric).

...#...........
.#.#...........
..##...........
...............
...............
##...........##
##...........##

...#...........
....#..........
..###..........
...............
...............
##...........##
##...........##

If the glider flies through the wall, you shall output a truthy value, and otherwise a falsy value. For the example above, the correct output is falsy, since the glider will crash into the left part of the wall.

For the purposes of this challenge, you can assume that if you simulate GoL on the input for 2*(height - 3) steps, the glider is on the bottom row in the expected position and the wall is intact, then the output is truthy.

Rules and scoring

You can write a full program or a function. The lowest byte count wins.

Test cases

I have collected the test cases into a GitHub repository, since they are quite large. Here are links to the individual files:

Zgarb

Posted 2017-03-07T15:46:47.437

Reputation: 39 083

Is there any reason for including the empty rows below the wall in the input? – Martin Ender – 2017-03-07T15:54:15.170

@MartinEnder They make solutions where you actually simulate GoL on the input more feasible (at least I hope so). – Zgarb – 2017-03-07T15:58:24.203

The glider will always start on the top row? – Rod – 2017-03-07T16:05:16.857

@Rod Yes, it will be on the top row heading southwest or southeast. – Zgarb – 2017-03-07T16:06:09.540

Another game of life :P – Christopher – 2017-03-07T16:18:38.023

Thanks for the interesting challenge! I'm honored. :) – apsillers – 2017-03-08T17:40:14.703

Answers

15

Python 2, 142 136 135 bytes

-6 bytes thanks to ElPedro
-1 byte thanks to TuukkaX

p=input()
z=p[2].index(1)
m=(p[1][z]-p[1][z+1]<1)*2-1
k=i=0
for b in p[3:]:x=p[2][::m].index(1)+i;k|=1in b[::m][x-2:x+8];i+=1
print 1-k

Try it online! or Verify all test cases

Checking orientation (east/west):

west_east
Using z=p[2].index(1) to get the first square on 3rd row (represented by the red square), and then m=(p[1][z]-p[1][z+1]<1)*2-1 to subtract the value on the right (green) from the one on the left (blue), this way all the 4 gliders states that are going to southwest result in 1 (top row in the image), while the ones going to southeast result in 0 or -1.
Then convert : 1 -> -1 and 0,-1 -> 1 to be used on parameter to reverse the lists when dealing with west ones. This way the gliders going southwest are threated the same as the one going southeast.

Glider movement

gliding
This is the movement that the glider going southeast do, it has a "ladder" pattern, and the leftmost block on 3rd line is constant to every pattern. Using it as starting point, the surrounding 3 blocks on left and right, and the middle 4 blocks are checked for the presence of 1s (that would be the wall).
arrowslits
arrowslits_path

Rod

Posted 2017-03-07T15:46:47.437

Reputation: 17 588

I think you can lose 4 bytes by setting a variable i to 0 outside the for loop then adding 1 to it it each pass and so get rid of enumerate. Seems to work when I tried it with your TIO. +1 for a cool answer whether I am right or wrong. – ElPedro – 2017-03-07T21:02:11.363

Nice! You can save a byte by removing the whitespace from 1 in. +1. – Yytsi – 2017-03-08T00:15:34.960

2

+1 for "weast"

– JungHwan Min – 2017-03-08T03:24:51.053

4

Octave , 123 122 108 bytes

Thanks to @LuisMendo saved 2 bytes

B=A=input("");B(1:3,:)=0;do;until nnz((A=A&(s=conv2(A,(m=-1:1)|m','same'))>1&s<4|~A&s==3)-B)-5;any(A(end,:))

Try it online!

Or

Verify all test cases

Thanks to Rod preparing test cases.

B=A=input("");
B(1:3,:)=0;
do
until nnz((A=A&(s=conv2(A,(m=-1:1)|m','same'))>1&s<4|~A&s==3)-B)-5
any(A(end,:))

Previous answer:

B=A=input("");
B(1:3,:)=0;
while nnz(A~=B)==5
    s=conv2(A,(m=-1:1)|m','same');
    x=~A;
    A&=~A|~(s<2|s>3);
    A|=x&s==3;
end;
any(A(end,:))

First extract wall pattern as variable B.
Do GoL simulation until the wall pattern and the simulated pattern have more/less than 5 different cells.
If the glider has received the last row the function returns true.

rahnema1

Posted 2017-03-07T15:46:47.437

Reputation: 5 435

1until the wall pattern and the simulated pattern have more/less than 5 different cells. That's clever! – Luis Mendo – 2017-03-08T10:35:51.177

@LuisMendo Thanks, saved a byted – rahnema1 – 2017-03-08T10:57:42.570

3

Retina, 101 93 91 bytes

Byte count assumes ISO 8859-1 encoding.

O$#^`.(?=(.*¶)*(?<=#_.\2.+##.(.*¶)\D+))
$#1
¶(?>_(_)*#+_+¶_+¶(?<1>_+¶)*)(?>(?<-1>.)+)_{11}

Try it online!

Certainly not optimal yet.

Martin Ender

Posted 2017-03-07T15:46:47.437

Reputation: 184 808