Quartermeter Push Obstacles

Computer Science Level 5

Brilli the ant is going from point $A=(0,0)$ to point $B=(10,10)$ on a grid. It can either move one unit up or one unit to the right in one move, along the grid lines. The perimeter of the area in which it can move is given in the figure by a quarter circle of radius 10 centred at point $C=(10,0)$ . Along the way it encounters small bead obstacles which can be moved by a unit distance along the direction in which it is moving. So if it is moving from $(2,1)$ to $(2,2)$ and if there is an obstacle at $(2,2)$ , then the obstacle moves to $(2,3)$ and Brilli moves to $(2,2)$ . There are three obstacles in total, at $(2,2)$ , $(4,4)$ and $(7,7)$ . The obstacles too are not allowed to cross the perimeter but move along the perimeter, just like Brilli. Find the number of possible paths such that Brilli can reach its destination from point A to point B.

The answer is 44961.

2 solutions

Siva Bathula
Sep 8, 2016

Relevant wiki: Dynamic Programming

The problem is very much similar to the one posted here : Quartermeterpath with added constraint of movable obstacles.

        void QuartermeterObstacles()
        {
            HashSet<string> Obstacles = new HashSet<string>();
            Obstacles.Add("2:2");
            Obstacles.Add("4:4");
            Obstacles.Add("7:7");

            Action<int, int, HashSet<string>> Move = null;
            int xMax = 10, yMax = 10, xmaxSq = xMax * xMax;
            int ForwardPaths = 0;
            Move = delegate (int x, int y, HashSet<string> obstacles)
            {
                if (x > xMax) return;
                if (y > yMax) return;

                int dSquared = (xMax - x) * (xMax - x) + (y * y);
                if (dSquared > xmaxSq) return;

                if (x == xMax && y == yMax)
                {
                    ForwardPaths += 1;
                    return;
                }

                if (x < xMax)
                {
                    string oKey = (x + 1) + ":" + y;
                    if (obstacles.Contains(oKey))
                    {
                        HashSet<string> oNext = new HashSet<string>(obstacles);
                        if (x + 1 < xMax)
                        {
                            oNext.Remove(oKey);
                            int osq = ((xMax - x - 2) * (xMax - x - 2)) + (y * y);
                            if (osq <= xmaxSq)
                            {
                                oNext.Add((x + 2) + ":" + y);
                                Move(x + 1, y, oNext);
                            }
                        }
                    }
                    else Move(x + 1, y, obstacles);
                }
                if (y < yMax)
                {
                    string oKey = x + ":" + (y + 1);
                    if (obstacles.Contains(oKey))
                    {
                        HashSet<string> oNext = new HashSet<string>(obstacles);
                        if (y + 1 < yMax)
                        {
                            oNext.Remove(oKey);
                            int osq = ((xMax - x) * (xMax - x)) + ((y + 2) * (y + 2));
                            if (osq <= xmaxSq)
                            {
                                oNext.Add(x + ":" + (y + 2));
                                Move(x, y + 1, oNext);
                            }
                        }
                    }
                    else Move(x, y + 1, obstacles);
                }
            };
            Move(0, 0, Obstacles);
        }

Do You happen to have a "profile" on Brilliant Slack? I would like to ask You one simple question, but I would rather do that in some kind of private chat.

Milan Milanic - 4 years, 8 months ago

I actually dont have a squared account, I am assuming Slack is available for Squared users only. What is it anyway?

Siva Bathula - 4 years, 8 months ago

I do not have squared account either, but I do have slack. So I think having a squared account is not a necessary for slack. Of course, if You would prefer e-mail conversation or via some other network, I don't have anything against it. It is related to one of my problems on Brilliant, to its solution. So we can even discuss it in solution section of that problem.

Milan Milanic - 4 years, 8 months ago

@Milan Milanic – Could you link it here, I will see if I can help, wish I could turn on slack for my account, dont seem to find it anywhere.

Siva Bathula - 4 years, 8 months ago

@Siva Bathula – Here's the link to the problem. In the solution section I will at-mention You and ask You the question.

Milan Milanic - 4 years, 8 months ago

Laurent Shorts
Feb 13, 2017

Python code:

def outside(p):
    [x,y] = p
    if x < 0 or y < 0 or x > 10 or y > 10:
        return True
    if (10-x)**2 + y**2 > 100:
        return True
    return False

def moveRight(t):
    return [t[0] + 1, t[1]]
def moveUp(t):
    return [t[0], t[1] + 1]

def ways(pos, obsts):
    if outside(pos):
        return 0
    for obs in obsts:
        if outside(obs):
            return 0

    if pos == [10, 10]:
        return 1

    # moving right
    posR = moveRight(pos)
    obstsR = obsts[:]
    for i in xrange(len(obsts)):
        if obstsR[i] == posR:
            obstsR[i] = moveRight(obstsR[i])

    # moving up
    posU = moveUp(pos)
    obstsU = obsts[:]
    for i in xrange(len(obsts)):
        if obstsU[i] == posU:
            obstsU[i] = moveUp(obstsU[i])

    return ways(posR, obstsR) + ways(posU, obstsU)



POS = [0,0]
OBSTS = [ [2,2], [4,4], [7,7] ]
print ways(POS, OBSTS)

Quartermeter Push Obstacles

The answer is 44961.

2 solutions

0 pending reports