The Classical Josephus Problem

OLYMPUS DIGITAL CAMERA

This is another one taken from Programming Praxis #5 – Flavius Josephus, has a historical context which can be found here. For this exercise, write a function j that takes two values n & m that returns a list of n people, numbered from 0 to n-1, in the order in which they are executed, every mth person in turn, with the sole survivor as the last person in the list. What is the value of j (41,3)? In what position did Josephus survive?

Built a recursive routine that executes each soldier and creates a smaller and smaller live soldier list. Used Debug.Trace to list each one executed, rather than build an execution list.


import Debug.Trace

execute :: [Int] -> Int -> Int -> [Int]
execute [a] _ _ = [a]
execute soldiers inc pos = trace (show v) $ execute [x | x <- soldiers, x /= soldiers !! pos] inc newPos
	where
		newPos
			| (pos + inc) >= length soldiers = pos + inc - length soldiers
			| otherwise = pos + inc - 1
		v = (soldiers, inc, pos, newPos)

main = print $ j 41 3
	where
		j numSoldiers inc = execute [1..numSoldiers] inc $ inc - 1
About these ads

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