Covid vaccination and the IBM Ponder This challenge
This is the 6th IBM Ponder This that I manage to solve: IBM Research | Ponder This | January 2021 Challenge. The challenge is copied/pasted below.
This seems to be a straightforward problem where a DFS or BFS should do it. However, the challenge is the following: how to mark that a certain cell has been visited or not? There are no limits of how many times you can go thru one cell when it is marked as 2 or 3. This is the part that required some heuristic, at least from my part. First, to mark a cell as visited we need to make sure that the cell position, the cell value and the cell direction are all the same. Second, for the heuristic, I made an assumption that the robot can visit the same cell (with the mark mentioned before) at most N times. In terms of the execution time, for N = 50, we'll have something that is really expensive, but doable:
- Loop to find the first B: 50^2
- Loop to find the second B: 50^2
- Loop for the validation whether the vaccination is doable: 50^2 * 50
Hence, total: 50^2 * 50^2 * 50^3 = 50^7, or < (2^6)^7, or < 2^42. This gets into or close to the trillions. Now, that will take a while, in the order of hours (maybe > 24h), but the problem clearly specifies that a solution exists, hence it becomes a game of cards (luck), and thankfully the solution pops up rather quickly for N=50 (within few minutes). Now I actually modified the code a bit to try the N=100, and even worse with 3 Bs, which would then be 100^6 * 100^3 = 100^9 which would be more like close to 2^56, clearly intractable. But it worked overnight (probably 12h to give me the answer), and that's why the "*" is there near my name. Code for N=50 is below, cheers, ACC.
CODE:
using System;
using System.Collections;
using System.Collections.Generic;
namespace IBMPonderThisJan2021
{
class Program
{
static void Main(string[] args)
{
int N = Int32.Parse(args[0]);
Process(N);
}
static void Process(int N)
{
bool foundSolution = false;
for (int r1 = 0; r1 < N; r1++)
{
if (foundSolution) break;
for (int c1 = 0; c1 < N; c1++)
{
if (foundSolution) break;
for (int r2 = 0; r2 < N; r2++)
{
if (foundSolution) break;
for (int c2 = 0; c2 < N; c2++)
{
if (foundSolution) break;
if (r2 == r1 && c2 == c1) continue;
int[][] grid = new int[N][];
for (int r = 0; r < N; r++) grid[r] = new int[N];
grid[r1][c1] = 3;
grid[r2][c2] = 3;
if (CovidVaccination(grid))
{
Console.WriteLine("Solution: [({0},{1}), ({2},{3})]", r1, c1, r2, c2);
PrintGrid(grid);
foundSolution = true;
break;
}
}
}
}
}
}
static void PrintGrid(int[][] grid)
{
for (int r = 0; r < grid.Length; r++)
{
for (int c = 0; c < grid[r].Length; c++)
{
Console.Write("{0} ", grid[r][c]);
}
Console.WriteLine();
}
Console.WriteLine();
}
static bool CovidVaccination(int[][] grid)
{
Hashtable visited = new Hashtable();
Queue queue = new Queue();
int direction = 0; //0 up, 1 right, 2 down, 3 left
int row = 0;
int col = 0;
QueueItem qi = new QueueItem(grid.Length, row, col, direction, grid[row][col]);
visited.Add(qi.key, 1);
queue.Enqueue(qi);
while (queue.Count > 0)
{
QueueItem currentItem = queue.Dequeue();
row = currentItem.row;
col = currentItem.col;
direction = currentItem.direction;
/* DEBUG
PrintGrid(grid);
Console.WriteLine("({0},{1})", row, col);
if (direction == 0) Console.WriteLine("UP");
if (direction == 1) Console.WriteLine("RIGHT");
if (direction == 2) Console.WriteLine("DOWN");
if (direction == 3) Console.WriteLine("LEFT");
Console.ReadLine();
*/
switch (currentItem.value)
{
case 0:
grid[row][col] = 1;
direction = (direction + 1) % 4;
break;
case 1:
grid[row][col] = 2;
direction--;
if (direction == -1) direction = 3;
break;
case 2:
break;
case 3:
direction--;
if (direction == -1) direction = 3;
break;
}
switch (direction)
{
case 0:
row--;
if (row < 0) row = grid.Length - 1;
break;
case 1:
col = (col + 1) % grid.Length;
break;
case 2:
row = (row + 1) % grid.Length;
break;
case 3:
col--;
if (col < 0) col = grid.Length - 1;
break;
}
QueueItem newItem = new QueueItem(grid.Length, row, col, direction, grid[row][col]);
if (!visited.ContainsKey(newItem.key))
{
visited.Add(newItem.key, 1);
queue.Enqueue(newItem);
}
else
{
int count = (int)visited[newItem.key];
if (count < grid.Length)
{
visited[newItem.key] = count + 1;
queue.Enqueue(newItem);
}
}
}
return AllVaccinatedTwice(grid);
}
static bool AllVaccinatedTwice(int[][] grid)
{
for (int r = 0; r < grid.Length; r++)
{
for (int c = 0; c < grid[0].Length; c++)
{
if (grid[r][c] < 2) return false;
}
}
return true;
}
}
public class QueueItem
{
public int N = 0;
public int row = 0;
public int col = 0;
public int direction = 0; //0 up, 1 right, 2 down, 3 left
public int value = 0;
public long key = 0;
public QueueItem(int N, int row, int col, int direction, int value)
{
this.N = N;
this.row = row;
this.col = col;
this.direction = direction;
this.value = value;
key = row * N + col + direction * 100100 + value * 1000000;
}
}
}
CHALLENGE:
A robot is distributing COVID-19 vaccines on an NxN grid. At the beginning, the robot is located at the (0,0) cell facing UP, and every cell in the grid is marked as having received zero doses of the vaccine. The robot's goal is to ensure that each cell on the grid gets two doses of vaccine by visiting each cell twice.
Unfortunately, the robot was attacked by anti-vaccine bots, causing its navigation system to malfunction. As a result, the robot now acts like this at every step:
- If the cell was vaccinated 0 times, it administers one dose (raising the cell's status from "0" to "1") and turns 90 degrees CLOCKWISE.
- If the cell was vaccinated 1 time, it administers one dose (raising the cell's status from "1" to "2") and turns 90 degrees COUNTERCLOCKWISE.
- If the cell was vaccinated 2 times, the robot does not change direction.
The robot then takes one step in the direction it is currently facing. If the step takes it out of the grid, it returns from the other side (i.e., coordinate arithmetic is modulo N).
Here is an example of how the robot acts on a 4x4 grid for the first few steps (the cell (0,0) is pictured at the top-left corner). The current cell is marked by square brackets; recall that the robot begins by facing upwards.[0] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 [0] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 [0] 0 0 0 0 0 0 0 0 0 0 1 1 0 0 [0] 1 0 0 0 0 0 0 0 0 0 0 [1] 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 2 1 0 [0] 1 1 0 0 0 0 0 0 0 0 0 0It can be seen already that for N=4, the robot cannot administer two doses to the whole grid. Luckily, some of the anti-vaccine bots remain and can be used to our benefit. We can change some cells of the grid to contain the value "B" and give the robot an additional rule:
- If the cell's status is "B", the robot avoids the anti-vaccine bots, administers no vaccine, and turns 90 degrees COUNTERCLOCKWISE.
The robot then takes one step as usual (the anti-vaccine bot cannot harm it).For example:
[0] B 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 [B] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 B 0 0 0 0 0 0 0 0 0 0 0 [0] 0 0We do not need the "B" cells to be vaccinated.
Your goal is to find a placement of two "B" cells that ensures the rest of the grid will reach "2" status eventually for N=50. Give your answer in the following format: [(a,b), (x,y)] where (a,b) are the coordinates of the first "B" cell and (x,y) are the coordinates of the second "B" cell.
A bonus '*' for finding a placement of at most three "B" cells that works for N=100. Give your answer in the format [(a,b), (x,y), (r,s)] or [(a,b), (x,y)].
A bonus '**' for finding the minimum N such that 2 "B" cells do not suffice for it.
Comments
Post a Comment