Problem Statement
Cube roll is played on a horizontal row of cells. Cells are numbered consecutively, increasing from left to right. The row is infinitely long, so all integers, including negative ones, are valid cell numbers. Certain cells contain holes, and they are given in the int[] holePos. Initially, a cube is placed at cell initPos. The objective of the game is to move the cube to cell goalPos using the least possible number of turns. On each turn, the player will choose a direction (left or right) and roll the cube in that direction by x number of cells, where x is a perfect square (1, 4, 9, 16, …). If at any time during the roll, the cube lands on a cell containing a hole, the cube will fall into the hole. Once the cube falls into a hole, it can never be moved again.
Tutorial
At first glance, I thought it’s a dynamic problem. But since the holes are arbitrary, defining states isn’t easy. The problem can be solved using BFS and modular arithmetic. The fun and challenging part is coming up with modular arithmetic equation and solving it. The problem is split into a bounded and unbounded case. Bounded is were your left and right hole exits, and simple BFS traversal can solve this. But in the unbounded case, we need some understanding of modular arithmetic. So let’s consider the distance between initialPos and goalPos d. Then equation for d is \(a^2 - b^2 = d. a,b \epsilon \, Z\). After we try out some values of a and b, we find that modular cost is 4. Detailed explanation can be found here Link
Code
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class CubeRoll {
int firstLefMost, firstRightMost;
public boolean doesSolutionExists(int initpos, int goalPos, int[] holePos)
{
int n = holePos.length;
for(int i = 0; i < n ; i++)
if(initpos <= holePos[i] && holePos[i] <= goalPos)
return false;
return true;
}
public void setFirstLefMost(int initpos, int[] holePos)
{
firstLefMost = 0;
for(int i = 0 ; i < holePos.length; i++)
if(holePos[i] < initpos && holePos[i] > firstLefMost)
firstLefMost = holePos[i];
}
public void setFirstRightMost(int goalPos, int[] holePos)
{
firstRightMost = 100005;
for(int i = 0; i < holePos.length ; i++)
if(holePos[i] > goalPos && holePos[i] < firstRightMost)
firstRightMost = holePos[i];
}
public int getMinimumSteps(int initPos, int goalPos, int[] holePos) {
if(initPos > goalPos)
{
int tmp = initPos;
initPos = goalPos;
goalPos = tmp;
}
if(!doesSolutionExists(initPos, goalPos, holePos))
return -1;
setFirstLefMost(initPos, holePos);
setFirstRightMost(goalPos, holePos);
if(firstLefMost > 0 && firstRightMost < 100005)
return doBFS(initPos, goalPos, holePos);
else
{
int dist = Math.abs(goalPos - initPos) ;
firstLefMost = 0;
firstRightMost = dist + 2;
int res = doBFS(1, dist + 1, holePos);
if(dist % 4 != 2) // Min Trick is this a*a - b*b = d -> a*a - b*b = d mod 4
return min(res, 2);
return min(res, 3);
}
}
private int doBFS(int initPos, int goalPos, int[] holePos) {
Queue<Integer> Q = new LinkedList<>();
Q.offer(initPos);
int[] dist = new int[firstRightMost + 1];
Arrays.fill(dist, 10000000);
dist[initPos] = 0;
while(!Q.isEmpty())
{
int aux = Q.poll();
if(aux == goalPos)
return dist[aux];
for(int i = 1 ; i * i + aux < firstRightMost; i++) //i <= firstRightMost/i &&
{
if(dist[aux + i * i ] > dist[aux ] + 1)
{
dist[aux + i*i] = dist[aux] + 1;
Q.offer(aux + i * i);
}
}
for(int i = 1; i*i + firstLefMost < aux ; i++) // i <= aux/i &&
{
if(dist[aux - i * i ] > dist[aux] + 1){
dist[aux - i *i ] = dist[aux] + 1;
Q.offer( aux - i *i );
}
}
}
return -1;
}
}