Competitive programming in Haskell: summer series

Now that this weird and crazy semester is finally over, I’d like to get back to doing some blogging (among other things). I’m going to return to my series on competitive programming in Haskell (previous posts here: basic setup; code style and moral absolutes; Scanner; ByteString; primes and factoring; modular arithmetic 1; modular arithmetic 2), but following a more hands-on approach: each Tuesday and Friday, I will post a link to a problem (or two), and invite you to try solving it. The following Tuesday or Friday, I will explain my solution (as well as link to another problem for the next post). Sometimes I may develop a topic over several posts; sometimes I may just post random problems that I like.

To kick things off, here’s an easy-ish problem with an elegant Haskell solution:

I invite you to try solving it, and to post your questions, comments, and solutions here! (Fair warning: don’t look at the comments before you’ve solved it if you don’t want spoilers!) On Tuesday I will post my solution with commentary, and another problem for you to try.

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in competitive programming, haskell and tagged , , , . Bookmark the permalink.

6 Responses to Competitive programming in Haskell: summer series

1. blaisepascal2014 says:

I don’t know if it’s elegant, but the core of my solution, for each line, does

words >>> map read >>> foldl insert (Empty :: Tree Int) >>> fmap (const ())

2. Arnaud Bailly says:

My solution is here: https://gist.github.com/abailly/0f032e562f240f536b4317b682a22a59
Same idea than blaisepascal2014…

3. Ryan Yates says:

I had the same solution :D.

4. Globules says:

Mine is pretty much like the others.

```{-# LANGUAGE DeriveFunctor #-}

import Data.List (foldl', group, sort)

data Tree a = Nil | Node (Tree a) a (Tree a)
deriving (Eq, Functor, Ord, Show)

mkTree :: Ord a => [a] -> Tree a
mkTree = foldl' insert Nil

insert :: Ord a => Tree a -> a -> Tree a
insert Nil x = Node Nil x Nil
insert (Node l y r) x | x   y = Node l y (insert r x)

numShapes :: [Tree a] -> Int
numShapes = length . group . sort . map void
```
5. Cool problem! My solution is more explicit. I turned lists to trees per usual, but then I realized that binary trees represent magmas, so to transform them to shapes, you need a magma morphism:

```compress :: Tree -> String
compress Root = "."
compress (Node _ l r) = "(" ++ compress l ++ compress r ++ ")"```

I then inserted the stringified shapes into a Set and applied size.

6. Connor Baker says:

Here’s my solution (with error handling): https://gist.github.com/ConnorBaker/4d1f0166e748a4518718822d7730cfd5

It seems like there’s a fairly typical solution for this kind of problem. I wonder what other designs (like Bartosz’s above) might look like?

Thanks for the problem Brent!

This site uses Akismet to reduce spam. Learn how your comment data is processed.