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.

About Brent

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 Control.Monad (void)
    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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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