33

As a professor of Awesomeness at the prestigious Ad Hoc University (other questions in this series), I decided to assign my students this puzzle. Unfortunately, they were all unable to get it! I want to post it here to see if any puzzlers can get it.

Here we go:

Suppose I've defined an operation that takes in a 5x5 grid of booleans (or 1s and 0s) and outputs a number which represents its score. Here are some examples:

grid 1 = 5 + 7 = 12

grid 2 = 3 + 6 = 9

grid 3 = 3 + 0 = 3

grid 4 = $\infty$

grid 5 = 6 + 4 = 10

grid 6 = $\infty$

Your job is to tell me how I score my grids!

Note: all the information of the puzzle is in the blockquote; nothing outside the blockquote is relevant!

Voldemort's Wrath
  • 3,114
  • 2
  • 12
  • 46

2 Answers2

22

You score your grids by

Running them on a 5x5 Game of Life!

The score is calculated from two pieces:

The time until the pattern becomes stable, plus the number of cells alive at the end

StephenTG
  • 3,565
  • 1
  • 21
  • 27
  • 1
    This is a really nice observation and may very well be strongly connected to the answer :) However, how do you define 'time' here? When I use the link you provided, the fourth grid in particular takes a LOT of iterations to do what you say... – Stiv Aug 17 '20 at 14:40
  • 1
    Time = iterations. Are you testing on a 5x5 grid, or just putting the patterns on a larger one? – StephenTG Aug 17 '20 at 14:43
  • 1
    Ah, that might well be what's making the difference! In which case I withdraw my doubt and commend you again on spotting this connection! – Stiv Aug 17 '20 at 14:45
  • 3
    Yeah, the second example gave me the idea, but my first test on a larger grid didn't match up. But I realized that thing might pan out differently if things couldn't expand past the borders – StephenTG Aug 17 '20 at 14:46
  • 1
    :) :) :) :) I need emojis on stackexchange to show my expressions – Aakash Mathur Aug 17 '20 at 14:49
  • 1
    Awesome! This is correct... You get an A+ in the class :):) – Voldemort's Wrath Aug 17 '20 at 16:41
  • 5
    OMG! I thought it was related to the game of life and even figured it might be related to number of iterations to reach stability. So I ran it on a game of life simulator on a large grid and couldn't see any answers emerging. DAMN I was so close!!! I even spent 2 hours looking at cool game of life videos after this question... – Dmitry Kamenetsky Aug 18 '20 at 07:44
  • 1
    @DmitryKamenetsky — I’m glad my puzzle allowed you to learn some cool things about the Game of Life!! – Voldemort's Wrath Aug 20 '20 at 12:10
22

As the answer from @StephenTG states, the secret is to

interpret the grids as cells in Conway's Game of Life (a thought I'd had, and intended to investigate further this evening)

Specifically,

it is run on a finite 5x5 grid where all cells outside the 5x5 area are considered to be permanently 'dead' (one common alternative is to run it on a toroidally-connected grid, but this is ruled out because several of the patterns shown would have different behaviour on such a grid).

Implementing the necessary calculations in Excel:

Game of Life in excel based on puzzle

We can see that, as also stated in @StephenTG's answer,

Taking $N$ as the generation where a stable configuration is reached, and $K$ as the number of live cells in that stable configuration, the final answer adds $N + K$. For starting grids that reach no stable configuration, $N = \infty$

Higher finite scores are possible. For example,

I was able to quickly construct grids which score $13 + 4 = 17$ and $3 + 16 = 19$

Glider in corner of 5x5 grid

Pattern which degenerates to 4 2x2 blocks in 3 generations

... and revisiting it a little later, some minor tweaks improve this:

$27 + 6 = 33$
Glider-block collision in 5x5 grid

Later, I finally got round to doing an exhaustive computer search for better solutions. The most relevant part of the output

shows both the longest-lived starting state, and also the highest-scoring (subsequent generations are left as an exercise for the reader):

 State 257296 : 39 + 0 = 39
         []
       []
 [][]  [][]
 [][][]

New best score: 39 + 0 = 39


State 12366675 : 34 + 6 = 40
 [][]    []
   []  [][]
     [][]
 []    [][]
 [][]  []
 New best score: 34 + 6 = 40


Search Time: 35.3581088 seconds
 Showing 48 states with best score (40):
Steve
  • 3,865
  • 11
  • 34