3
\$\begingroup\$

At a job interview, I was asked to code the following algorithm:

Given are three robots which advance across a 1km lane at a different pace respectively. Each pace made by a robot is of a random distance. All three robots stop once one of them is one pace away from reaching 1km. Once they stop, the robots' steps nearest to the middle of the lane are compared, and depending whose step throughout the journey was closest to the middle while exceeding it, a winner is declared. The winner robot's color is then printed out.

It took me a while to wrap my head around this quirky task, but I emerged with this solution:

var robot = function(color) {
    this.color = color;

    this.d1 = 0;
    this.robo1 = 0;
    this.a1 = [];
    while (this.robo1 < 1000 && this.d1 != -1) {

        // all robots begin at 0
        this.robo1 = this.robo1 + this.d1;

        // add starting point to array 
        this.a1.push(this.robo1);

        // generate new deltas
        this.d1 = Math.floor(Math.random() * 100);

        // check if adding delta to new robos would exceed 1000
        // to determine whether the next iteration 
        this.d1 = (this.d1 + this.robo1 > 1000) ? -1 : this.d1;

    }
    // log all arrays
    console.log(this.a1);

    // determine which element of a1 is closest to half of path
    console.log('smallest distance for a1:');
    this.smallestDistanceFromMiddle = 1000; // setting initial state

    this.cleanedA1 = [...this.a1];
    this.cleanedA1 = this.a1.filter(item => item > 500); // ###
    //console.log('cleanedA1 is \t' + this.cleanedA1);

    this.cleanedA1.forEach((index, item) => {
        this.iteratedValue = Math.abs(500 - this.cleanedA1[item]);
        this.smallestDistanceFromMiddle = this.iteratedValue < this.smallestDistanceFromMiddle ? this.iteratedValue : this.smallestDistanceFromMiddle;
        //console.log(iteratedValue);
    });
    console.log(this.smallestDistanceFromMiddle);
    return this.smallestDistanceFromMiddle;
}


let robot1 = new robot('red');
let robot2 = new robot('purple');
let robot3 = new robot('blue');


console.log("the robots' smallest distance to the middle is:");
console.log(robot1.color, robot1.smallestDistanceFromMiddle + '\n' +
    robot2.color, robot2.smallestDistanceFromMiddle + '\n' +
    robot3.color, robot3.smallestDistanceFromMiddle + '\n');

let nearestRobot = Math.min(robot1.smallestDistanceFromMiddle, robot2.smallestDistanceFromMiddle, robot3.smallestDistanceFromMiddle);

switch (nearestRobot) {
    case robot1.smallestDistanceFromMiddle:
        console.log(robot1.color, 'robot wins! \n');
        break;
    case robot2.smallestDistanceFromMiddle:
        console.log(robot2.color, 'robot wins! \n');
        break;
    case robot3.smallestDistanceFromMiddle:
        console.log(robot3.color, 'robot wins! \n');
        break;
    default:
        console.log('no robots defined');
}

Nevertheless, I feel like there is a more eloquent, easy on the eyes solution and I would very dearly appreciate improvement feedback.

\$\endgroup\$
7
  • 3
    \$\begingroup\$ I would send the spec back for clarification. If each pace is a random distance (and according to what distribution?), how can you know when a robot is one pace from the end? \$\endgroup\$ Oct 31 '17 at 10:41
  • \$\begingroup\$ That was a concern I had as well... what I ended up doing was generate a new d1 at the very end of the loop (see above) and see if the new distance when added to the current position on the lane would surpass 1km. Hope this provides some clarification. \$\endgroup\$
    – gnzg
    Oct 31 '17 at 11:39
  • \$\begingroup\$ Is there a range for each pace? You are using Math.random() * 100 in the code. Is there a requirement that each pace would be no more than 100m? \$\endgroup\$
    – Alex.S
    Oct 31 '17 at 13:34
  • \$\begingroup\$ There is no explicit requirement for that, only that each pace is of a random distance. The Math.random() * 100 is just an arbitrary choice I made. \$\endgroup\$
    – gnzg
    Oct 31 '17 at 14:21
  • 3
    \$\begingroup\$ Your code is not what they are looking for. Understanding the problem is about random numbers and that doing a long string of random things to pick one of 3 equally favoured random events is the same as picking a random item from 3. You have missed the point of the test console.log("Robot "+ ( ["red", "green", "blue"])[Math.random() * 3 |0] + " wins!"); was all that is needed. \$\endgroup\$
    – Blindman67
    Oct 31 '17 at 14:44
1
\$\begingroup\$

You did not model the race correctly. The specification says:

All three robots stop once one of them is one pace away from reaching 1km.

In your code, each robot runs the whole distance. The effect is that if you have one fast robot with a constant pace of 90 and one slow robot with a constant pace of 1, your code will make the slow robot win.

But at the time the race is over (after 12 steps), and at this point the slow robot is nowhere near the middle.

(Oh, there's one thing. When the paces are random, how can I know in advance whether the robot is one pace away? That gets complicated, but it is possible.)

Following the specification by the letter, the race has to be simulated very closely to the wording. That is, all robots start at the start, and in each step, each of them advances by its own pace.

Here is how I modeled the race:

'use strict';

class Robot {
    constructor(color, pace) {
        this.color = color;
        this.pace = pace;
        this.position = 0;
    }

    advance(distance) {
        this.position += distance;
    }
}

class Race {
    constructor(distance, robots) {
        this.distance = distance;
        this.middle = distance / 2;
        this.robots = robots;
        this.over = false;
        this.minMiddleDistance = this.middle;
        this.bestRobot = robots[0]; // Technically, it's a tie.
    }

    step() {
        // Calculate the robot's paces for this step in advance,
        // before actually advancing the robot's positions,
        // to satisfy the "one pace away from reaching" requirement
        // in combination with the "each pace is random" requirement.
        const paces = this.robots.map(robot => robot.pace());

        const raceLength = this.distance;
        this.over = this.robots.some((robot, i) => robot.position + paces[i] >= raceLength);
        if (this.over) {
            return;
        }

        this.robots.forEach((robot, i) => {
            robot.advance(paces[i]);
            const middleDistance = Math.abs(robot.position - this.middle);
            if (middleDistance < this.minMiddleDistance) {
                this.minMiddleDistance = middleDistance;
                this.bestRobot = robot;
            }
        })
    }
}

function rnd100() {
    return (100 * Math.random()) | 0; // only integer steps
}

// The specification does not say how each robot's pace is determined.
// The lambda functions in the following code can easily be replaced
// with rnd100 or any other number generator.
const robots = [
    new Robot('red', () => 90),
    new Robot('green', () => 7),
    new Robot('blue', () => 45)
];

const race = new Race(1000, robots);
while (!race.over) {
    race.step();
}
console.log('The winner is ' + race.bestRobot.color + ' with a distance of ' + race.minMiddleDistance + '.');

// Blue wins.
// The red robot crosses the finishing line after ceil(1000/90) == 12 steps.
// After 6 steps, the red robot was closest to the 500 mark, at 540.
// After 11 steps, the blue robot was at 11*45 == 495.
// The green robot is too slow to be a competitor.

I made the Robot class pretty small because the robot should not be involved in calculating the outcome of the race. Who knows, maybe one of them would try to cheat?

All the calculations happen in the Race class, which coordinates the robots.

\$\endgroup\$
2
  • \$\begingroup\$ Oops, I overlooked a tiny part of the specification: "while exceeding it". Therefore, it is wrong to use Math.abs for determining the winner. \$\endgroup\$ Jun 7 '18 at 22:04
  • \$\begingroup\$ I fixed it by slightly changing the if condition inside the forEach function to this: const middleDistance = robot.position - this.middle; and to establish minMiddleDistance: if (middleDistance > 0 && middleDistance < this.minMiddleDistance) Full code: repl.it/repls/ExternalFatalDemands \$\endgroup\$
    – gnzg
    Jun 9 '18 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.