February 2021 - Challenge
A set of people is placed on the positive, non-zero values of an NxN grid. Our goal is to vaccinate all the people in the grid against COVID-19. Every person has a subset of "trusted neighbors". Once all of a person's trusted neighbors are vaccinated, that person will get vaccinated as well. (If the set of trusted neighbors is empty, that person is already convinced and gets vaccinated without further convincing.)
To carry out this task as efficiently as possible, we need to find the minimum set of people that must be directly convinced to start a chain reaction that will convince all others.
We can represent the trust relationship as a four-digit binary number. The digit '1' indicates trust, the digit '0' indicates no trust. The neighbors are those people at the four points connected to a given person on the grid, from the above neighbor and clockwise, i.e., the above, right, below, and left neighbors. A point on the edge of the grid has fewer than four neighbors.
For example, the trust relationship 1001 for the point (2,3) means that this grid point trusts its upper neighbor (2,4) and left neighbor (1,3). Once those points are vaccinated, in the next time step (2,3) will also become vaccinated.
As another example, for the point (1,N) the meaning of 1111 is that only the right neighbor (2,N) and the lower neighbor (1,N-1) are counted as trusted neighbors; the upper and left neighbors (1,N+1) and (0,N) are not included in the grid and so do not count (so 1111 is equivalent to 0110 in this case).
To represent the board in a compact fashion, we convert a point's binary number trust relationship to hexadecimal and use that hexadecimal digit to represent that point. So 0101 is represented by '5', 1111 is represented by 'f', etc.
An example of a 3x3 grid is:
381 79c 26c
Here the point (1,2) has the trust relationship '7', i.e., 0111, meaning it depends on (2,2) (right) and (1,1) (down), but not on (1,3) above (since it is 0) nor on (0,2) to the left (because even though it's defined as a trusted neighbor, it's outside the grid). It can be seen that since (1,1) is "2", i.e., it depends only on its non-existing neighbor (1,0), making its set of trusted neighbors essentially empty, therefore it will get vaccinated by itself, but (2,2) will not; convincing (1,2) to vaccinate directly will start a chain reaction ending in the vaccination of all points. So for this grid, the set [(1,2)] suffices to ensure full vaccination.
Your goal: Find a minimal set for ensuring eventual full vaccination of the following 12x12 grid:
0a8301b11b01 1bda41b24d78 37c09e8d5998 60473283d3b8 13279043d9bc 371bf4c021c1 1d122e800ee1 5bc967265d88 5f1998f5915d 628dff094034 39effbe6ecc8 2c440c20e0a0
A bonus '*' will be given for finding a 12x12 grid with a minimal set of size exactly 42.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
31/01/2021 @ 12:00 PM EST
Solution:
04/03/2021 @ 12:00 PM EST
List Updated:
03/03/2021 @ 12:00 PM EST
People who answered correctly:
*Bertram Felgenhauer (1/2/2021 3:27 PM IDT)
*Alper Halbutogullari (1/2/2021 5:56 PM IDT)
Daniel Chong Jyh Tar (1/2/2021 6:20 PM IDT)
*Guillaume Escamocher (1/2/2021 8:45 PM IDT)
*Gary M. Gerken (2/2/2021 10:25 AM IDT)
*Sanandan Swaminathan (2/2/2021 11:40 AM IDT)
*Walter Sebastian Gisler (2/2/2021 2:41 PM IDT)
*Paul Shaw (3/2/2021 12:06 AM IDT)
*Uoti Urpala (3/2/2021 2:54 AM IDT)
*Eden Saig (3/2/2021 3:09 AM IDT)
*Paul Revenant (3/2/2021 3:50 PM IDT)
Reda Kebbaj (3/2/2021 6:14 PM IDT)
*Luca Pintori (3/2/2021 6:39 PM IDT)
*Ilya Tarygin (3/2/2021 7:20 PM IDT)
*Dominik Reichl (3/2/2021 8:24 PM IDT)
*Giuliano Bertoletti (3/2/2021 9:54 PM IDT)
Dieter Beckerle (4/2/2021 12:33 AM IDT)
*Chuck Carroll (4/2/2021 10:12 AM IDT)
*Willem Hendriks (4/2/2021 1:50 PM IDT)
*Andreas Stiller (5/2/2021 2:40 AM IDT)
*Harald Bögeholz (5/2/2021 7:11 AM IDT)
*Dan Dima (5/2/2021 1:37 PM IDT)
*Yasodhar Patnaik (5/2/2021 8:43 PM IDT)
*Glauber Guarinello (5/2/2021 9:25 PM IDT)
*Florian Fischer (6/2/2021 12:21 AM IDT)
*Karl D’Souza (6/2/2021 12:25 AM IDT)
Andrew Mullins (6/2/2021 10:34 PM IDT)
*Latchezar Christov (6/2/2021 10:48 PM IDT)
Alex Fleischer (6/2/2021 11:01 PM IDT)
*Kai Guttmann (7/2/2021 3:15 AM IDT)
Graham Hemsley (7/2/2021 12:49 PM IDT)
*Joaquim Neves Carrapa (7/2/2021 8:29 PM IDT)
*Christopher Marks (7/2/2021 8:51 PM IDT)
*Amos Guler (7/2/2021 10:38 PM IDT)
*Thomas Pircher (7/2/2021 10:51 PM IDT)
*Glauber Guarinello (7/2/2021 11:19 PM IDT)
*Nicolas Lopez (8/2/2021 7:46 PM IDT)
*Hans Kodde (8/2/2021 11:01 PM IDT)
*Pål Hermunn Johansen (9/2/2021 4:15 PM IDT)
*Kamil Jarosz (9/2/2021 7:05 PM IDT)
Thomas Egense (9/2/2021 11:44 PM IDT)
*Victor Chang (10/2/2021 8:34 AM IDT)
*Hu Shuai (13/2/2021 2:47 PM IDT)
*Lorenz Reichel (13/2/2021 8:46 PM IDT)
Soonho You (14/2/2021 3:51 AM IDT)
*Simeon Krastnikov (15/2/2021 6:56 AM IDT)
Ilya Tarygin (15/2/2021 2:21 PM IDT)
*Vladimir Volevich (15/2/2021 4:45 PM IDT)
*Phil Proudman (15/2/2021 6:52 PM IDT)
*Fei Xie (15/2/2021 7:21 PM IDT)
*Cynthia Beauchemin (15/2/2021 10:09 PM IDT)
*James Muir (16/2/2021 5:10 AM IDT)
*Matthews, Aaron (16/2/2021 7:05 AM IDT)
Daniel Bitin (16/2/2021 9:19 AM IDT)
*David Greer (16/2/2021 1:27 PM IDT)
*Marco Bellocchi (16/2/2021 3:22 PM IDT)
*Nyles Heise (17/2/2021 7:51 AM IDT)
*Bert Dobbelaere (20/2/2021 4:36 PM IDT)
Egil Støren (22/2/2021 4:29 PM IDT)
*Tamir Ganor & Shouky Dan (25/2/2021 9:55 AM IDT)
*Chris Shannon (27/2/2021 1:47 AM IDT)
*Motty Porat (27/2/2021 9:21 PM IDT)
Todd Will (27/2/2021 10:41 PM IDT)
*Oscar Volpatti (28/2/2021 6:41 AM IDT)
Egil Støren (22/2/2021 4:29 PM IDT)
*Tamir Ganor & Shouky Dan (25/2/2021 9:55 AM IDT)
*Chris Shannon (27/2/2021 1:47 AM IDT)
*Motty Porat (27/2/2021 9:21 PM IDT)
Todd Will (27/2/2021 10:41 PM IDT)
*Oscar Volpatti (28/2/2021 6:41 AM IDT)
Arne Vik (28/2/2021 3:04 PM IDT)
Steven Langerwerf & Susan Brommer (28/2/2021 3:45 PM IDT)
*Andy Greig (only the "*" part) (28/2/2021 7:15 PM IDT)
*Zhou Hangbo (only the "*" part) (28/2/2021 7:43 PM IDT)
*Fabio Filatrella (28/2/2021 9:09 PM IDT)
*Clement Heyd (only the "*" part)(28/2/2021 11:39 PM IDT)
Reiner Martin (1/3/2021 1:03 AM IDT)
*Radu-Alexandru Todor (1/3/2021 2:54 AM IDT)
*Dezhi Zhao (1/3/2021 4:49 AM IDT)
*Filippos Christou (only the "*" part) (1/3/2021 2:41 PM IDT)
*Muralidhar Seshadri (1/3/2021 6:18 PM IDT)
Dipto Thakurta (1/3/2021 6:34 PM IDT)
*Alexander Strasser (2/3/2021 12:17 AM IDT)
*Kang Jin Cho (2/3/2021 7:45 PM IDT)
*Vromen, Tomer (2/3/2021 10:54 PM IDT)
Li Li (3/3/2021 2:23 AM IDT)