# The Classical Josephus Problem 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
``````

# Simplicity Programming Praxis 4: Sudoku Solution

Sudoku problems can be perceived as quite complex. Counter-intuitively and from a mathematical standpoint, the solution is actually quite simple. I wrote this solution a while back in Python by pulling together algorithms from a number of sources. But by translating it into Haskell again, I think its acheived a certain Zen-like simplicity and elegance. Or maybe its the homebrew talking.

``````import Data.List
import Data.Maybe

check :: Int -> Int -> Bool
check i j
| (f i)/9 == (f j)/9 = True
| mod (i-j) 9 == 0 = True
| (f i)/27 == (f j)/27 && (f \$ mod i 9)/3 == (f \$ mod j 9)/3 = True
| otherwise = False
where
f = fromIntegral

solve :: [Int] -> [Int]
solve s
| elem 0 s = solve \$ a ++ [n | n <- [1..9], elem n e == False] ++ b
| otherwise = s
where
a = take i s
b = drop (i + 1) s
i = fromJust \$ elemIndex 0 s
e = [s !! j | j <- [0..80], check i j]

main = print \$ solve [7,0,0,1,0,0,0,0,0,0,2,0,0,0,0,0,1,5,0,0,0,0,0,6,3,9,0,2,
0,0,0,1,8,0,0,0,0,4,0,0,9,0,0,7,0,0,0,0,7,5,0,0,0,3,0,7,8,5,0,0,0,0,0,
5,6,0,0,0,0,0,4,0,0,0,0,0,0,1,0,0,2]
``````

# Dirty Little Monad Never tried random numbers before in Haskell. Obviously it must involve a Monad, because randomness is considered so unpure. Found this great line somewhere, worth sharing here:

### Using Monads in Haskell is like drinking from the communal water bottle, but never letting your lips touch the bottle.

Programming Praxis 3: Bingo

Such a simple game, Bingo, but such an annoying problem in Haskell. I suppose most of my grief stems from the fact that I’m still thinking in imperative concepts. Eventually I figured out that I would need to use higher order functions (and/or tail recursion) in lieu of iteration. Then I spent the next week reviewing mind numbing concepts like filters, maps, folds, scans. All are incredibly powerful but eventually I didn’t need them. Everything reduced down to good old fashioned list comprehensions. Still my favourite Haskell feature.

Found that System.Random provided lots of handy functions. “randomRs” needs seeds, so I just used the count numbers. Not very random, but ok for these purposes. Since its a random generator, I couldn’t guarantee that all my needed numbers were picked. So I generated more than enough numbers over a range, removed duplicates with “nub” and took the right number.

The other interesting note is the use of Data.Maybe. When using “elemIndex“, it could throw an error, so the function will return a type “Maybe“, akin to a Null value in other languages. Used “fromJust” to strip the “Maybe” off and use the “Int“. Didn’t worry about the error because the pool always held all 75 numbers.

In main, printed just the two calculations. The first shows the average number of balls called to get to Bingo with only one card and 500 different pools. The second shows the average number calls used to get to Bingo with one pool and 500 different cards. Routine only takes a second to run in GHCi.

``` import System.Random import Data.List import Data.Maybe makePool :: Int -> [Int] makePool s = take 75 \$ nub \$ take (1000) \$ randomRs (1,75) (mkStdGen s) :: [Int] makeCard :: Int -> [Int] makeCard seed = (b ++ i ++ n ++ g ++ o) where b = take 5 \$ nub \$ take 20 \$ randomRs (1,15) (mkStdGen seed) :: [Int] i = take 5 \$ nub \$ take 20 \$ randomRs (16,30) (mkStdGen \$ sum b) :: [Int] n = take 5 \$ nub \$ take 20 \$ randomRs (31,45) (mkStdGen \$ sum i) :: [Int] g = take 5 \$ nub \$ take 20 \$ randomRs (46,60) (mkStdGen \$ sum n) :: [Int] o = take 5 \$ nub \$ take 20 \$ randomRs (61,75) (mkStdGen \$ sum g) :: [Int] filterCard :: [Int] -> [[Int]] filterCard card = [[card !! x | x <- r] | r <- ranges] where ranges = [[0..4],[5..9],[10,11,13,14],[15..19],[20..24], [0,5..20],[1,6..21],[2,7,17,22],[3,8..23],[4,9..24],[0,6,18,24],[4,8,16,20]] evaluate :: [Int] -> [Int] -> Int evaluate pool subcard = maximum [fromJust \$ elemIndex x pool | x <- subcard, elem x pool] bingoTest :: [Int] -> [Int] -> Int bingoTest pool card = minimum [evaluate pool x | x <- (filterCard card)] main = do print \$ 0.002 * fromIntegral (sum [bingoTest (makePool x) \$ makeCard 1 | x <- [1..500]]) print \$ 0.002 * fromIntegral (sum [bingoTest (makePool 1) \$ makeCard x | x <- [1..500]]) ```

# Basket Making 101 Praxis 2: Write a function that calculates the list of prime numbers using the Sieve of Eratosthenes.

Ummm, yeah. Done it a couple dozen times before over at Project Euler. Never hurts to review. I did manage to use more function composition this time around. Oh, and don’t forget to install module data.ordlist using Cabal.

``````
import Data.List.Ordered

primes :: Integer -> [Integer]
primes m = 2 : sieve [3,5..m]
where
sieve [] = []
sieve (p:xs) = p : sieve (minus xs [p*p, p*p+2*p..m])

main = do
putStrLn "Enter n: "
input <- getLine
putStrLn \$ "# of primes: " ++ (show . length . primes \$ read input)
``````

# Back to Functional Programming Purity Got the itch to start studying Haskell again. Best to scratch it. I’m a bit sick of gluing together bits of Javascript code that don’t look like they should be together in the same script, then wondering why in the world it works. Granted, I did enjoy coding everything in the cloud, and my ultimate hope is for the same treatment be given to Haskell.

I keep getting drawn to Haskell’s simplicity, consistency, structural elegance, and perfect typing system, even though it still causes me a great deal of mental strain to understand it. And I found that after being away from it for several months, even the simplest concepts have to be re-learned.

So I did two things. One, I began re-reading Haskell guides like “Real World Haskell” and “Learn you a Haskell for Great Good!“. There are tons of very helpful resources online.

The second thing I did is to give “Programming Praxis” a try. In the past I used Project Euler, but having solved 108+ problems, I’m getting tired of the same old, same old. I’m sure I’ll get to the same point with Praxis, but for now its giving me a change.

Praxis 1 – Create a RPN calculator:
Loved my HP 48sx+ calculator in Engineering. Sad day when it kak’d. Still have trouble using regular algebraic calculators. So this one was is right up my alley. Lots of sample code online, but I started noticing that most code used function composition, rather than using variables. Up until now I always avoided function composition, but it really does make things clearer.

``````
import Data.List

solveRPN :: String -> Float
solveRPN = head . foldl calcme [] . words
where
calcme (x:y:ys) "*" = (x * y):ys
calcme (x:y:ys) "+" = (x + y):ys
calcme (x:y:ys) "-" = (y - x):ys
calcme (x:y:ys) "/" = (y / x):ys
calcme xs numStr = read numStr:xs

main = do
putStrLn "Enter calculation: "
input <- getLine
putStrLn \$ "Result = " ++ (show \$ solveRPN input)
``````