2
\$\begingroup\$

Here is the problem statement:

Take a second to imagine that you are in a room with 100 chairs arranged in a circle. These chairs are numbered sequentially from One to One Hundred. At some point in time, the person in chair #1 will be told to leave the room. The person in chair #2 will be skipped, and the person in chair #3 will be told to leave. Next to go is person in chair #6. In other words, 1 person will be skipped initially, and then 2, 3, 4.. and so on. This pattern of skipping will keep going around the circle until there is only one person remaining- The survivor! Note that each chair is removed when the person leaves the room.

Please review my attempt below considering the following points:

  1. Correctness (I am getting the winner as # 31)
  2. Any chances for optimization

var myApp = angular.module('myApp',[]);

myApp.controller('MyCtrl', [ '$scope', '$interval', '$log', function($scope, $interval, $log){

  $scope.init = function(){
    $scope.people = [];
    $scope.logs = [];

    // get the 100 people/chair
    for(var i=1; i<=100; i++){
      $scope.people.push({ index: i });
    }
  };

  $scope.startFiring = function(){

    var fireIndex = 0, // for removing the person at this index
        skipCount = 0; // for incremental counting 

    if($scope.people.length >= 1){ // if start button clicked again
      $scope.gotWinner = false; // hide the winner
      $interval.cancel(fireInterval); // stop the interval
      $scope.init();
    }

    var fireInterval = $interval(function(){
      
      $scope.disableStartButton = true;

      if ($scope.people.length > 1) { // if more than 1 people
        $scope.logs.push({text: 'Firing #' + $scope.people[fireIndex].index}); // show the log
        
        $scope.people.splice(fireIndex, 1); // fire!
        
        // increment
        skipCount += 1;
        fireIndex += skipCount;

        //if fireIndex becomes greater than $scope.people.length, then set fireIndex to remainder from fireIndex / $scope.people.length
        if(fireIndex > $scope.people.length){
          fireIndex %= $scope.people.length;
        }

      } else {
        $interval.cancel(fireInterval); // stop the interval
        $scope.gotWinner = true; // show the winner
        $scope.disableStartButton = false;
      }
    }, 500); // every 1/2 sec.

  };

  $scope.init(); // intialize the chair/people when the view is loaded or start is clicked again

}]);
body{
  font-family: "HelveticaNeue-Light", "Helvetica Neue Light", "Helvetica Neue", Helvetica, Arial, "Lucida Grande", sans-serif;
}

span{
  display: inline-block;
  padding: 5px;
  margin: 4px;
  border-radius: 3px;
  background: #000000;
  color: #FFFFFF;
}
<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>JS Bin</title>
  </head>
  <body ng-app='myApp'>
    <div ng-controller="MyCtrl">
      <div>
        <span ng-repeat="person in people">{{person.index}}</span>
      </div>
      <button ng-click="startFiring()" ng-disabled="disableStartButton">Start!</button>
      <p ng-show="gotWinner">And the winner is.... # <strong>{{people[0].index}}!</strong></p>
      <p ng-show="logs.length !== 0">Logs:</p>
      <ul>
        <li ng-repeat="log in logs | orderBy:'-'">{{log.text}}</li>
      </ul>
    </div>
    <script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.5.0/angular.min.js"></script>
  </body>
</html>

\$\endgroup\$
  • \$\begingroup\$ The firing sequence you have described (1, 3, 6, 10, 15, …) is different from the typical "Josephus Problem". \$\endgroup\$ – 200_success Feb 14 '16 at 5:05
  • \$\begingroup\$ @200_success I have edited the title. However, the problem statement remains the same. \$\endgroup\$ – Rahul Desai Feb 14 '16 at 7:27
  • 1
    \$\begingroup\$ 31 is correct. The fiddle could be improved codewise but is correct. You can check it by using a smaller number for initialization (instead of 100 set 10. \$\endgroup\$ – Ivan Modric Feb 15 '16 at 9:54
1
\$\begingroup\$

Mathematical % simplification

Remember that $$a\ \%\ b == a \ \ if\ b > a$$

I don't know the math, but Python confirms:

>>> import random
>>> def random_ints():
    for _ in range(1000): yield random.randint(1, 100)
>>> all(a % b == a for a in random_ints() for b in random_ints() if b > a)
True

So:

    fireIndex += skipCount;

    //if fireIndex becomes greater than $scope.people.length, then set fireIndex to remainder from fireIndex / $scope.people.length
    if(fireIndex > $scope.people.length){
      fireIndex %= $scope.people.length;
    }

can be simplified to

fireIndex = (fireIndex + skipCount) % $scope.people.length

Comments

Some comments are good, but you should avoid writing comments next to obvious code:

  if ($scope.people.length > 1) { // if more than 1 people

It is already obvious from the code that you are checking if there are more than 1 people, the comment just doubles the effort required to change the code.

The below comment is very confusing instead:

if($scope.people.length >= 1){ // if start button clicked again

Probably you changed the code but not comment.

\$\endgroup\$
  • \$\begingroup\$ Thank you! What do you think about the correctness? Is 31 correct? \$\endgroup\$ – Rahul Desai Feb 14 '16 at 18:22

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.