Don’t complicate your code

A friend sent me a link to a blog post that discusses solutions to the Josephus problem in Perl, Ruby, and Python. Ouch! Those implementations hurt.

The Josephus problem is a simple discrete math puzzle:

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?


I think that the simplest way to solve this puzzle is to keep track of all alive soldiers and start eliminating every k-th solidier until we are left with just one soldier. In Haskell, I would implement this as follows:

survivor :: Int -> [a] -> a 
survivor k soldiers = killnext k soldiers 
    where killnext l (x:xs) | Pre.null xs = x 
                            | l == 1 = killnext k xs 
                            | otherwise = killnext (l-1) (xs++[x])

 main = do 
    args <- getArgs 
    let k = read (args!!1) :: Int 
        n = read (args!!2) :: Int 
    print $ survivor k [1..n]

Note that I am using Haskell’s lists to keep track of the alive soldiers. List append ++ is O(n2); which slows down the algorithm. The execution time (on my low power netbook) is (k is 3 in all experiments):

 _n_ time (in s) 
------ --------------- 
4       0.00 
40      0.01 
400     0.02 
4000    1.19 
8000    6.04 

So, it is better to replace list by a data structure that has O(1) append. I chose Data.Sequence.

survivor :: Int -> [a] -> a
survivor k soldiers = viewnext k (Seq.fromList soldiers) 
    where viewnext l list = killnext l (Seq.viewl list) 
          killnext l (x:<xs) | Seq.null xs = x 
                                | l == 1 = viewnext k xs 
                                | otherwise = viewnext (l-1) (xs|>x) 

The implementation is almost the same as before. The main difference is that I had to add a viewnext accessor function to peek at the left element of the sequence. The execution time with this implementation is (as before k is 3 in all experiments):

 _n_ time (in s)
----- ---------------
4      0.01 
40     0.01 
400    0.01 
4000   0.02 
8000   0.03 
16000  0.05 

Much better. A simple solution to a simple puzzle.

Advertisements

4 thoughts on “Don’t complicate your code

  1. Hi,

    nice clear and simple implementation.

    I can’t compile the second implemention using Sequences. This is what i tried:

    
    import System.Environment
    import Data.Sequence ((> [a] -> a
    survivor' k soldiers = viewnext k (Seq.fromList soldiers)
      where
        viewnext l list    = killnext l (Seq.viewl list)
        killnext l (x:x)
    main = do
        args <- getArgs
        let k = read (args!!0) :: Int
            n = read (args!!1) :: Int
        print $ survivor' k [1..n]
    

    Note: i changed

    
      let k = read (args!!1) :: Int
          n = read (args!!2) :: Int
    

    to

    
        let k = read (args!!0) :: Int
            n = read (args!!1) :: Int
    

    I suppose the problem is the pattern match at (x:<xs).

    Chris

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s