## Google CodeJam 2011 Problem A. Bot Trust Published on: 12 May 2011

### Solution Analysis

Lets list some important things about the problem:

• The buttons need to be pressed in order.
• The Robots can move simultaneously (However given above condition they will never press buttons simultaneously)
• Robots begin at position 1

We could do a brute-force solution where we store all the moves for each robot. Then at any given point it is trivial to say what the robot should do next. However we could just accumulate time for the robot, and when it's his turn to press the button we could go 'back' in time, and move him appropriately. Lets look at some code

class Robot {
int m_currPos;
int m_accumulatedSeconds;

public:
Robot() : m_currPos(1), m_accumulatedSeconds(0) {} ;
int moveMe(int position) {
int requiredSeconds = abs(position - m_currPos) + 1 - m_accumulatedSeconds;
m_accumulatedSeconds = 0;
m_currPos = position;
return requiredSeconds > 0 ? requiredSeconds : 1;
}

int accumulateSeconds(int seconds){
m_accumulatedSeconds+=seconds;
}
};


So each Robot has two states - his current position and how much time he has accumulated since his last move. The key insight here is that the robot moves only when he needs to press the button. Otherwise we can just keep accumulating seconds. This saves us from needing to know each Robot's next move! We can defer the decision to move till we know where we need to move. Another nice thing about making this Robot class is that we can have more than two Robots, and our solution would work perfectly well.

Lets examine the logic in the MoveMe method a little in detail. Required seconds basically calculates how many seconds its going to take the Robot to press the button. abs(position - m_currPos) calcuates the number of seconds it requries to move and + 1 is for pressing the button. We then subtract the accumulated seconds the robot has, since he would have been moving towards the button in those seconds. We then reset the state of the robot as having no accumulated seconds and set his currenet position. We then return the total number of seconds it took to press the button so that other robots can accumulate time. Note that the minimum amount of time we return is 1 since it always takes at least 1 second to press the button, even if the robot was already at the required position.

Now lets look at the Game class which controls the movement of these robots

class Game {
public:
int move(Robot& rMove, Robot& rAccumulate, int pos)
{
int secs = rMove.moveMe(pos);
rAccumulate.accumulateSeconds(secs);
return secs;
}

int start(const string& moves) {
istringstream in(moves);
int nextPos, temp, totalSeconds=0;
char cNextRobot;
Robot ro, rb;

in >> temp;
while(! in.eof()) {
in>>cNextRobot>>nextPos;
if(cNextRobot == 'O')
totalSeconds += this->move(ro , rb, nextPos);
else
totalSeconds += this->move(rb , ro, nextPos);
}