-- a module to solve the josephus problem
-- as discussed in week 9 lectures 
-- comp1711 unsw
-- richard buckland
-- 5/5/5

module Joe where

import Ring (Ring, Elt,
             newRing, current, deleteCurrent,
             rotate, size)
{-
-- ring interface

newRing       :: [Elt] -> Ring
current       :: Ring -> Elt
deleteCurrent :: Ring -> Ring
rotate        :: Ring -> Int -> Ring
size          :: Ring -> Int
-}

------------------------------------------

-- solve Joesephus problem
-- given ring of elts and an interval
-- cast out elts repeatedly until
-- there's one left
--
-- because deleteCurrent also effectively does a
-- rotate 1 we only need to advance by (interval-1)
-- after each deletion.
solve :: [Elt] -> Int -> Elt
solve elts interval = simulate (newRing elts) (interval-1)


-- solve the josephus problem by simulation - ie
-- iterate the josephus process on a ring.
-- rotate, zap, rotate, zap, .. till only one left
simulate :: Ring -> Int -> Elt
simulate ring rotations
  | finished  = (current ring)
  | otherwise = simulate smallerRing rotations
  where
     smallerRing = deleteCurrent (rotate ring rotations)
     finished    = (size ring) == 1