7
\$\begingroup\$

Conway's Game of Life is a cellular automaton "played" on an infinite grid, filled with cells that are either alive or dead. Once given an initial state, the board evolves indefinitely according to the following rules:

  • Any live cell with 2 or 3 living neighbours lives to the next state
  • Any dead cell with exactly 3 living neighbours becomes a living cell
  • Any other cell becomes a dead cell

The Challenge

Given a state of the game, find the previous state.

Rules

  • All inputs are assumed to have a preceding state, that is, your code need not handle Gardens of Eden.
  • There will be multiple solutions, output any of them.
  • You may take input in any reasonable format. Standard I/O Rules apply.

Test cases

> input
: output

> [(2, 2)]
: [(1, 1), (2, 2), (3, 3)]
> [(2, 2), (2, 4), (3, 3), (3, 4), (4, 3)]
: [(1, 3), (2, 4), (3, 2), (3, 3), (3, 4)]
> [(2, 2), (2, 3), (2, 4)]
: [(1, 3), (2, 3), (3, 3)]
> [(2, 2), (2, 3), (2, 4), (3, 2), (3, 4), (4, 2), (4, 3), (4, 4)]
: [(1, 3), (2, 3), (3, 2), (3, 4), (4, 3), (5, 3)]
> [(3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (5, 2), (5, 3), (5, 4)]
: [(2, 2), (2, 5), (3, 5), (4, 2), (4, 3), (5, 3), (5, 4)]
> [(2, 4), (2, 5), (4, 2), (4, 5), (5, 2), (5, 3), (5, 4)]
: [(2, 4), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 4), (5, 3)]
> [(1, 13), (1, 14), (1, 19), (1, 20), (2, 13), (2, 19), (3, 8), (3, 9), (3, 15), (3, 21), (3, 29), (3, 30), (4, 7), (4, 9), (4, 14), (4, 15), (4, 20), (4, 21), (4, 26), (4, 27), (4, 30), (5, 3), (5, 4), (5, 6), (5, 9), (5, 11), (5, 12), (5, 15), (5, 17), (5, 18), (5, 21), (5, 23), (5, 24), (5, 27), (5, 29), (6, 3), (6, 5), (6, 6), (6, 8), (6, 11), (6, 12), (6, 14), (6, 17), (6, 18), (6, 20), (6, 23), (6, 24), (6, 26), (6, 29), (6, 30), (7, 8), (7, 9), (7, 14), (7, 15), (7, 20), (7, 21), (7, 26), (7, 27), (7, 31), (8, 4), (8, 5), (8, 7), (8, 10), (8, 11), (8, 13), (8, 16), (8, 17), (8, 19), (8, 22), (8, 23), (8, 25), (8, 28), (8, 29), (8, 32), (9, 4), (9, 6), (9, 7), (9, 10), (9, 12), (9, 13), (9, 16), (9, 18), (9, 19), (9, 22), (9, 24), (9, 25), (9, 28), (9, 30), (9, 31), (9, 32), (10, 8), (10, 9), (10, 14), (10, 15), (10, 20), (10, 21), (10, 26), (10, 27), (11, 5), (11, 6), (11, 9), (11, 11), (11, 12), (11, 15), (11, 17), (11, 18), (11, 21), (11, 23), (11, 24), (11, 27), (11, 29), (11, 30), (12, 5), (12, 6), (12, 8), (12, 11), (12, 12), (12, 14), (12, 17), (12, 18), (12, 20), (12, 23), (12, 24), (12, 26), (12, 29), (12, 30), (13, 8), (13, 9), (13, 14), (13, 15), (13, 20), (13, 21), (13, 26), (13, 27), (13, 33), (13, 34), (14, 3), (14, 4), (14, 5), (14, 7), (14, 10), (14, 11), (14, 13), (14, 16), (14, 17), (14, 19), (14, 22), (14, 23), (14, 25), (14, 28), (14, 29), (14, 31), (14, 34), (15, 1), (15, 4), (15, 6), (15, 7), (15, 10), (15, 12), (15, 13), (15, 16), (15, 18), (15, 19), (15, 22), (15, 24), (15, 25), (15, 28), (15, 30), (15, 31), (15, 32), (16, 1), (16, 2), (16, 8), (16, 9), (16, 14), (16, 15), (16, 20), (16, 21), (16, 26), (16, 27), (17, 5), (17, 6), (17, 9), (17, 11), (17, 12), (17, 15), (17, 17), (17, 18), (17, 21), (17, 23), (17, 24), (17, 27), (17, 29), (17, 30), (18, 5), (18, 6), (18, 8), (18, 11), (18, 12), (18, 14), (18, 17), (18, 18), (18, 20), (18, 23), (18, 24), (18, 26), (18, 29), (18, 30), (19, 8), (19, 9), (19, 14), (19, 15), (19, 20), (19, 21), (19, 26), (19, 27), (20, 3), (20, 4), (20, 5), (20, 7), (20, 10), (20, 11), (20, 13), (20, 16), (20, 17), (20, 19), (20, 22), (20, 23), (20, 25), (20, 28), (20, 29), (20, 31), (21, 3), (21, 6), (21, 7), (21, 10), (21, 12), (21, 13), (21, 16), (21, 18), (21, 19), (21, 22), (21, 24), (21, 25), (21, 28), (21, 30), (21, 31), (22, 4), (22, 8), (22, 9), (22, 14), (22, 15), (22, 20), (22, 21), (22, 26), (22, 27), (23, 5), (23, 6), (23, 9), (23, 11), (23, 12), (23, 15), (23, 17), (23, 18), (23, 21), (23, 23), (23, 24), (23, 27), (23, 29), (23, 30), (23, 32), (24, 6), (24, 8), (24, 11), (24, 12), (24, 14), (24, 17), (24, 18), (24, 20), (24, 23), (24, 24), (24, 26), (24, 29), (24, 31), (24, 32), (25, 5), (25, 8), (25, 9), (25, 14), (25, 15), (25, 20), (25, 21), (25, 26), (25, 28), (26, 5), (26, 6), (26, 14), (26, 20), (26, 26), (26, 27), (27, 16), (27, 22), (28, 15), (28, 16), (28, 21), (28, 22)]
: [(1, 13), (1, 14), (1, 19), (1, 20), (2, 13), (2, 19), (3, 8), (3, 9), (3, 15), (3, 21), (3, 29), (3, 30), (4, 7), (4, 9), (4, 14), (4, 15), (4, 20), (4, 21), (4, 26), (4, 27), (4, 30), (5, 3), (5, 4), (5, 6), (5, 9), (5, 11), (5, 12), (5, 15), (5, 17), (5, 18), (5, 21), (5, 23), (5, 24), (5, 27), (5, 29), (6, 3), (6, 5), (6, 6), (6, 8), (6, 11), (6, 12), (6, 14), (6, 17), (6, 18), (6, 20), (6, 23), (6, 24), (6, 26), (6, 29), (6, 30), (7, 8), (7, 9), (7, 14), (7, 15), (7, 20), (7, 21), (7, 26), (7, 27), (7, 31), (8, 4), (8, 5), (8, 7), (8, 10), (8, 11), (8, 13), (8, 16), (8, 17), (8, 19), (8, 22), (8, 23), (8, 25), (8, 28), (8, 29), (8, 32), (9, 4), (9, 6), (9, 7), (9, 10), (9, 12), (9, 13), (9, 16), (9, 18), (9, 19), (9, 22), (9, 24), (9, 25), (9, 28), (9, 30), (9, 31), (9, 32), (10, 8), (10, 9), (10, 14), (10, 15), (10, 20), (10, 21), (10, 26), (10, 27), (11, 5), (11, 6), (11, 9), (11, 11), (11, 12), (11, 15), (11, 17), (11, 18), (11, 21), (11, 23), (11, 24), (11, 27), (11, 29), (11, 30), (12, 5), (12, 6), (12, 8), (12, 11), (12, 12), (12, 14), (12, 17), (12, 18), (12, 20), (12, 23), (12, 24), (12, 26), (12, 29), (12, 30), (13, 8), (13, 9), (13, 14), (13, 15), (13, 20), (13, 21), (13, 26), (13, 27), (13, 33), (13, 34), (14, 3), (14, 4), (14, 5), (14, 7), (14, 10), (14, 11), (14, 13), (14, 16), (14, 17), (14, 19), (14, 22), (14, 23), (14, 25), (14, 28), (14, 29), (14, 31), (14, 34), (15, 1), (15, 4), (15, 6), (15, 7), (15, 10), (15, 12), (15, 13), (15, 16), (15, 18), (15, 19), (15, 22), (15, 24), (15, 25), (15, 28), (15, 30), (15, 31), (15, 32), (16, 1), (16, 2), (16, 8), (16, 9), (16, 14), (16, 15), (16, 20), (16, 21), (16, 26), (16, 27), (17, 5), (17, 6), (17, 9), (17, 11), (17, 12), (17, 15), (17, 17), (17, 18), (17, 21), (17, 23), (17, 24), (17, 27), (17, 29), (17, 30), (18, 5), (18, 6), (18, 8), (18, 11), (18, 12), (18, 14), (18, 17), (18, 18), (18, 20), (18, 23), (18, 24), (18, 26), (18, 29), (18, 30), (19, 8), (19, 9), (19, 14), (19, 15), (19, 20), (19, 21), (19, 26), (19, 27), (20, 3), (20, 4), (20, 5), (20, 7), (20, 10), (20, 11), (20, 13), (20, 16), (20, 17), (20, 19), (20, 22), (20, 23), (20, 25), (20, 28), (20, 29), (20, 31), (21, 3), (21, 6), (21, 7), (21, 10), (21, 12), (21, 13), (21, 16), (21, 18), (21, 19), (21, 22), (21, 24), (21, 25), (21, 28), (21, 30), (21, 31), (22, 4), (22, 8), (22, 9), (22, 14), (22, 15), (22, 20), (22, 21), (22, 26), (22, 27), (23, 5), (23, 6), (23, 9), (23, 11), (23, 12), (23, 15), (23, 17), (23, 18), (23, 21), (23, 23), (23, 24), (23, 27), (23, 29), (23, 30), (23, 32), (24, 6), (24, 8), (24, 11), (24, 12), (24, 14), (24, 17), (24, 18), (24, 20), (24, 23), (24, 24), (24, 26), (24, 29), (24, 31), (24, 32), (25, 5), (25, 8), (25, 9), (25, 14), (25, 15), (25, 20), (25, 21), (25, 26), (25, 28), (26, 5), (26, 6), (26, 14), (26, 20), (26, 26), (26, 27), (27, 16), (27, 22), (28, 15), (28, 16), (28, 21), (28, 22)]

Visualize test cases (possible output followed by input)

  
  
  

This is , shortest answer in bytes wins.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ Is it possible that input is non-negative but output must have negative axis? \$\endgroup\$
    – l4m2
    Jul 13 at 17:13
  • 1
    \$\begingroup\$ @l4m2 you may assume both input and output will be in the first quadrant \$\endgroup\$
    – c--
    Jul 13 at 17:19

1 Answer 1

Reset to default
2
\$\begingroup\$

JavaScript (Node.js), 232 bytes

f=(x,u=[],i=0,j=0,...L)=>u.find(g=([x,y])=>(t[[k%3+x-1,(k/3|0)%3+y-1]]+=[k%9==4],++k%9?t[[x,y]].length%5-3:g(v)),k=t=[])||Object.keys(t).filter(i=>t[i][22]&&!t[i][28]).sort()!=x.sort()+''?f(x,...L,u,i+1,j,u,i,j+1,[...u,[i,j]],i,j):u

Nothing to Try it online!

f=(x,u=[],i=0,j=0,...L)=>                       // Init case
u.find(g=v=>(                                   // [i,j] exist?
  t[[k%3+v[0]-1,(k/3|0)%3+v[1]-1]]+=[k%9==4],   // neighbors +=5('false'), self +=4('true')
  ++k%9?t[[x,y]].length%5-3:g(v)                // Repeat 9 times then return if dup
),k=t=[])||
Object.keys(t).filter(                          // 0    5   10   15   20   25 28
  i=>t[i][22]&&!t[i][28]                        // undefinedfalsefalsefalsetrue
                                                // falsefalsetrue | falsefalsefalse | falsefalsefalsetrue
).sort()!=x.sort()+''?
f(x,...L,u,i+1,j,u,i,j+1,[...u,[i,j]],i,j)      // Try next, push with next [i,j] and version with [i,j] pushed
:u
Improve this answer
\$\endgroup\$

Your Answer

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

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