{-
  Copyright (C) 2008 Dmitry Negoda, http://ndv.mywebcommunity.org
  
  This file is part of Book of Programming Problems (http://ndv.mywebcommunity.org/problems).
  It is free software; you can redistribute it and/or modify
  it with no limits.	This software is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of	MERCHANTABILITY or 
  FITNESS FOR A PARTICULAR PURPOSE.
-}
{- A 'motley' number is a number with different digits. Find the longest chains of motley numbers such that each 
successive number is twice as large as the preceding.
Usage: load ghci, load Solution.hs either in ghci command line or in ghci prompt using :l command. In ghci
prompt, input "printmotley k" where k is the number of digits. It will create the file with name "output.txt" and
write all numbers there.
-}

module Solution where

import IO
import Char
import CPUTime

ismotley [] = True
ismotley (d:n) = if d `elem` n then False else ismotley n

-- increment the least significant digit of the number by 0 or 1
incLast any 0 = any
incLast [] c = [c]
incLast (n:tail) c = (n+c : tail)

-- multiply the number by 2
double [] = []
double (d:tail) = (d*2 `mod` 10) : incLast (double tail) (d*2 `div` 10)

fstd d = d `div` 10 -- first digit of a number 0 .. 99
sndd d = d `mod` 10 -- second digit of a number 0 .. 99

-- generate triple-motley numbers and check for each if it is quadruple-montly.
-- return all quadruple-montly numbers
-- given a number prev, we've got 4 cases to the next two digits: 0..24, 25..49, 50..74, 75..99
-- each case will generate different carry bits when multiplied by 2 two times
motleyRec prev  0    0 = if ismotley (double (double (double prev))) then [prev] else []
motleyRec prev  0    n = []
motleyRec prev (k+1) startFromDigits = 
	foldr (++) [] [
		(if isTriplemotley prev (fstd d) (sndd d `div` 5) 0 then motleyRec ((fstd d):prev) k ((sndd d)*10) else []) ++
		(if isTriplemotley prev (fstd d) (sndd d `div` 5) 1 then motleyRec ((fstd d):prev) k ((sndd d)*10+25) else [])
		| d <- [startFromDigits,(startFromDigits+5)  .. (startFromDigits+20)]]
	where 
		isTriplemotley prev d c1 c2 = 
			not (d `elem` prev) && 
			not (d2 `elem` prev2) &&
			not ((2*d2 `mod` 10 + c2) `elem` (incLast (double prev2) (d2*2 `div` 10)))
			where 
				d2 = d*2 `mod` 10 + c1
				prev2 = incLast (double prev) (d*2 `div` 10)

-- generate quadruple-motley numbers with a specified length
motley 1 = [[1]]
motley (k+1) = motleyRec [1] k 0

numberToString [] = ""
numberToString (d:tail) = (numberToString tail) ++ [Char.chr(d+48)]

printmotley k = do
	writeFile "output.txt" ""
	t <- CPUTime.getCPUTime
	mapM (\n -> appendFile "output.txt" ((numberToString n)++"\n")) (motley k)
	t1 <- CPUTime.getCPUTime
	putStrLn ("time elapsed: " ++ (show ((t1 - t) `div` 1000000000000)))
	return ()