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>

asked Feb 14, 2016 at 4:07
\$\endgroup\$
3
  • \$\begingroup\$ The firing sequence you have described (1, 3, 6, 10, 15, ...) is different from the typical "Josephus Problem". \$\endgroup\$ Commented Feb 14, 2016 at 5:05
  • \$\begingroup\$ @200_success I have edited the title. However, the problem statement remains the same. \$\endgroup\$ Commented Feb 14, 2016 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\$ Commented Feb 15, 2016 at 9:54

1 Answer 1

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.

answered Feb 14, 2016 at 11:26
\$\endgroup\$
1
  • \$\begingroup\$ Thank you! What do you think about the correctness? Is 31 correct? \$\endgroup\$ Commented Feb 14, 2016 at 18:22

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.