Created
          March 16, 2016 19:36 
        
      - 
      
 - 
        
Save bdkosher/322c84d6b675ab4bf428 to your computer and use it in GitHub Desktop.  
    Groovy-based solution to the generalized Josephus problem
  
        
  
    
      This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
      Learn more about bidirectional Unicode characters
    
  
  
    
  | /* | |
| "Flavius Josephus was a roman historian of Jewish origin. During the Jewish-Roman wars of the first century AD, he was in a cave with fellow soldiers, | |
| 40 men in all, surrounded by enemy Roman troops. They decided to commit suicide by standing in a ring and counting off each third man. Each man so | |
| designated was to commit suicide...Josephus, not wanting to die, managed to place himself in the position of the last survivor. | |
| In the general version of the problem, there are n soldiers numbered from 1 to n and each k-th soldier will be eliminated. The count starts from the | |
| first soldier. What is the number of the last survivor?" | |
| */ | |
| int solveJosephusProblem(int n = 40, int k = 3) { | |
| def soldiers = [] + ((1..n) as List) | |
| int deathIndex = 0 | |
| while (soldiers.size() > 1) { | |
| int unluckySoldier = soldiers.removeAt(deathIndex) | |
| println "Killed soldier ${unluckySoldier}. Now ${soldiers.size()} remain." | |
| deathIndex = (deathIndex + k) % soldiers.size() | |
| } | |
| soldiers[0] | |
| } | |
| println solveJosephusProblem() | 
  
    Sign up for free
    to join this conversation on GitHub.
    Already have an account?
    Sign in to comment