-- http://jaced.com/2005/05/31/the-u2-riddle/

data U2 = Adam | Bono | Edge | Larry

pace Adam = 5
pace Bono = 1
pace Edge = 2
pace Larry = 10

-- 1. people on starting side
-- 2. people on ending side (for convenience)
-- 3. flash light on starting side
-- 4. remaining time
data State = State [U2] [U2] Bool Int
initial = State [Adam, Bono, Edge, Larry] [] True 17

move :: State -> State
-- start to end
move (State (a++[x]++b++[y]++c) z True t)
  | nt >= 0
  = State (a++b++c) (x:y:z) False nt
  where nt = t - max (pace x) (pace y)
-- end to start
move (State xs (a++[x]++b) False t)
  | nt >= 0
  = State (x:xs) (a++b) True nt
  where nt = t - pace x

-- if p:ps is a path and q=move p, then q:p:ps is a path
type Path = [State]
extend :: Path -> Path
extend a@(State [] _ _ _ : _) = reverse a
extend a@(b@(State (_:_) _ _ _) : _) = extend (move b : a)

main = extend [initial]