FuzzyLife

TCO10 Qual 2 · 2010-04-11 · by Nickolas

TCO10 Qual 2 · 2010-04-11 · by Nickolas · Greedy, Simulation

Show categories

Class Name: FuzzyLife

Return Type: int

Method Name: survivingCells

Arg Types: (vector<string>)

Problem Statement

The Game of Life is a simulation which takes an initial state and shows its evolution over time. The simulation takes place on an infinite 2-dimensional grid of cells, where each cell is either live or dead. Each cell has exactly 8 neighbors (2 horizontal, 2 vertical, and 4 diagonal). Once the initial layout of live and dead cells is known, the evolution of the grid happens step by step. On each step, the state of the cells changes in the following way:

Each live cell with less than 2 or more than 3 live neighbors becomes dead.
Each dead cell with exactly 3 live neighbors becomes live.
All other cells remain the same.

All cells change their states simultaneously, so for each cell, the number of live neighbors is calculated before any changes are performed.
You are given a String[] grid which describes the initial layout of cells on a rectangular section of the grid. Unlike the classic game, in which the initial states of all the cells are known, grid contains cells of three types: live, dead and unknown, denoted by '1' (one), '0' (zero) and '?', respectively. The j-th character of the i-th element of grid describes the cell at row i, column j of the rectangular section. No cell will have more than one neighbor of type '?'. All cells outside of the area described by grid are initially dead.
Your task is to replace the unknown cells in the initial layout with live or dead cells in such a way that the total number of live cells after one step is maximized. Return the maximal possible number of live cells after one step.

Constraints

grid will contain between 2 and 50 elements, inclusive.
Each element of grid will contain between 2 and 50 characters, inclusive.
All elements of grid will contain the same number of characters.
Each character in grid will be '0', '1' or '?'.
No cell will have more than one neighboring cell of type '?'.

Examples

{"011",
 "0?1",
 "100"}
Returns: 5

There is only one unknown cell on the board, and two choices of filling it: 011 011 011 011 001 -> 001 or 011 -> 101 100 000 100 010 The first choice produces 3 live cells, and the second one produces 5 live cells.

{"101",
 "0?0",
 "101"}
Returns: 4

Again only one unknown cell and two choices: 101 000 101 010 000 -> 000 or 010 -> 101 101 000 101 010

{"?11",
 "100",
 "100"}
Returns: 5

{"11",
 "11"}
Returns: 4

It is possible to have no unknown cells.

{"111",
 "1?1",
 "111"}
Returns: 8

The number of live cells doesn't depend on the choice of the unknown cell. Remember that the cells outside of the described part of the grid can turn live as well.

{"0110",
 "?00?",
 "0110"}
Returns: 6

beehive

{"0?10",
 "1001",
 "0101",
 "00?0"}
Returns: 7

loaf

10)

{"?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?111?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001",
 "10000000000000000000000000000000000000000000000001",
 "?111?11?11?11?11?11?11?11?11?11?11?11?11?11?11?11?",
 "10000000000000000000000000000000000000000000000001"}
Returns: 2546

presumably max test (2546)

12)

{"00100",
 "01010",
 "10?01",
 "01010",
 "00100"}
Returns: 12

Choosing '0' as the value of an unknown cell is sometimes better.

13)

{"10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01", "00100100100100100100100100100100100100100100100100", "10010010010010010010010010010010010010010010010010", "01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01?01"}
Returns: 2320

result is an almost solid square

14)

{"00100100100100",
 "01001?10010010",
 "10?10001001001",
 "00100100100100",
 "01001010010010",
 "1?0100?10?10?1",
 "01001010010010",
 "00100100100100",
 "10?100?10?1001",
 "01001010010010",
 "00100100100100"}
Returns: 111

choose all 0

15)

{"?1110",
 "100?1",
 "00001",
 "?0010"}
Returns: 11

choose 0

16)

{"110",
 "1?1",
 "011"}
Returns: 6

choose 0

18)

{"111111",
"000000",
"0?00?0"}
Returns: 12

choose all 0

Submissions are judged against all 134 archived test cases, of which 14 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FuzzyLife with a public method int survivingCells(vector<string> grid) · 134 test cases · 2 s / 256 MB per case