Since tomorrow is the 4th of May, here's a little Star Wars themed post to prepare you mentally to all the bad jokes coming tomorrow.
During a session of the galactic senate all the senators are sitting in an
A sudden outbreak of JarJar flu (which lasts forever and causes the infected to speak like JarJar Binks) causes some of the senators to get infected.
Here's an example with a
6*6 grid where the
X are the infected senators, the corresponding list is :
After that the infection begins to spread step by step. Two senators are adjacent if they share a whole edge on the grid (i.e., top,bottom,right,left), which means we exclude diagonals.
We can conclude a senator can be adjacent to 2,3 or 4 other senators and claim the following rules for the infection :
- A senator that has been infected stays infected forever
- A senator is infected at a step if he was adjacent to 2 or more infected senator at the previous step
Here's an example with the previous grid which shows the 2 first steps of the infection :
After the nexts steps all the senate will be infected
Your code doesn't need to handle invalid inputs like a list greater than
n*n or coordinates that aren't distincts.
Your code will take as input a list of couples of integers (or a binary grid or any other format that suits your language) and an integer
n (which can be unnecessary if you use another format than a list) , for instance :
n being the side of the grid which means the grid will be a n*n grid, and the list of couples of integers being the coordinates of the cells of the initally infected senators.
The bottom left of the grid is [0,0] and the top right is [n-1,n-1]. The top left is [0,n-1].
Your code must output an integer :
-1 or a falsy value or an error if the whole grid will never be totally infected
or the minimum number of steps required to infect the whole grid
6 [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]] => 7 4 [[1,1][0,3][1,0][3,0][3,3]] => 9
Remember that this is code-golf, thus the shortest answer in bytes wins !