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.

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 ())

My solution is here: https://gist.github.com/abailly/0f032e562f240f536b4317b682a22a59

Same idea than blaisepascal2014…

I had the same solution :D.

Mine is pretty much like the others.

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:

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

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!