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