"Alchemical Groups": Advent of Code using Group Theory (free groups, g...

Hi all! If you don’t already know, Advent of Code is in full swing this year! If you’re participating and using Haskell, you’re welcome to join us at glguy ’s semi-official Haskell Leaderboard (join code 43100-84040706 )! There are also Haskellers on freenode ##adventofcode, and also #adventofcode on the Functional Programming slack.

My daily reflections are online, where I talk about how I approach each problem and what insight purely typed Functional Programming gives us for each problem.

Every once in a while I’ll find a challenge that I think can be pulled out as a short blog post, so I’ll bring them onto the blog for a more long-term sort of longevity!

In this one, I’ll talk about using group theory to solve the Day 5 challenge. Spoilers for those who have not solved it yet!

Part 1

dabAcCaCBAcCcaDA  The first 'cC' is removed.
dabAaCBAcCcaDA    This creates 'Aa', which is removed.
dabCBAcCcaDA      Either 'cC' or 'Cc' are removed (the result is the same).
dabCBAcaDA        No further actions can be taken.

Now, I feel like this problem might have been deliberately written to obscure this fact, but what it is describing is exactly the behavior of a Free Group , from group theory!

A fully reacted polymer is an element of the free group generated by the set of 26 letters of the alphabet, . Basically, we can talk about interpeting the string dabAcCaCBAcCcaDA as d <> a <> b <> A <> c <> C <> a <> C <> B <> etc. , where <> is the group action (“mappend”, in Haskell-speak) and A stands for “ a inverse”.

We can use Data.Group.Free from the free-algebras library, which offers a free group type FreeGroupL , to let us write:

import qualified Data.Group.Free as FG

interpret :: [Char] -> FG.FreeGroupL Char
interpret = foldMap inject          -- that's `foldMap` from Data.Foldable

where inject :: Char -> FreeGroupL Char takes a Char and turns it into the element of our free group. We can do this by using the library’s returnFree and invert (from the Group typeclass):

import           Data.Algebra.Free
import           Data.Char
import           Data.Group

inject :: Char -> FG.FreeGroupL Char
inject c
    | isAlpha c && isLower c = returnFree c
    | isAlpha c && isUpper c = invert $ returnFree (toLower c)
    | otherwise              = mempty       -- group identity element

The question is essentially asking for the length of the Tietze list representation of the final result. We can get this using FG.toList , and so our entire part 1 is just:

day05a :: [Char] -> Int
day05a = length . FG.toList . foldMap inject

Was this problem actually deliberately written to obscure the fact that we have a group action? We can’t say for sure, but it definitely seems to paint an “imperative”, step-by-step picture. Most implementations might scan the list for things to replace, and iterate over things until there is no more change. The problem is also written to maybe imply the fact that ordering of reduction of different items across the string might matter (is it left to right, or right to left?).

However, we know that ordering of reduction can’t matter, because we have a group action <> , which we know from group theory is, by definition, associative. Knowing that we have a group, we can immediately throw away any thought of caring about things like sequential, imperative order, and the complications that might come from it.

I think that these useful properties about the reduction process are not obvious from an initial reading. Being able to recognize that we have a group is the key to unlocking all of these insights, for free !

Part 2

Even though the problem again seems to be written to obscure this fact, we can see that Part 2 is basically describing a group homomorphism . That is, it talks about functions that map (the free group on the 26 letters of the alphabet) to (the free group on the letters of the alphabet excluding some cleaned letter).

Luckily, the free group comes equipped with a handy function create group homomorphisms “for free”:

foldMapFree
    :: Group b
    => (a -> b)
    -> (FreeGroupL a -> b)     -- the group homomorphism

That is, given any a -> b for a group b , we get a guaranteed group homormohpsim from FreeGroupL a to b . We can write a function from the generators of our group (in this case, Char ), and it’ll give us a group homomorphism on the free group on our generators.

We can use this to write our group homomorphism

foldMapFree
    :: (Char -> FreeGroupL Char)  -- map letters to letters-minus-some-letter
    -> FreeGroupL Char
    -> FreeGroupL Char

(Note that this type signature looks a lot like =<< , for monads. Coincidence?)

We can now create a “cleaned” version of our reaction by using:

clean
    :: Char                                     -- ^ given a letter to clean
    -> (FreeGroupL Char -> FreeGroupL Char)     -- ^ return a group homomorphism
clean c = foldMapFree $ \d ->
        if d == c
          then mempty
          else returnFree d

And so that’s part 2! We just need clean and this next function:

day05b :: String -> Int
day05b (foldMap inject -> polymer) =
    = minimum [ length $ FG.toList (clean c polymer)
              | c <- ['a' .. 'z']
              ]

Basically, we find the minimum of all of the possible “cleaned” lengths.

The best part about this, I think, is that we actually introduced a large optimization , completely by accident , thanks to group theory.

Because we recognize that this is a group homomorphism, we know the properties of group homomorphisms apply. Namely, the most important one: “Aggregating, then cleaning” is the same as “cleaning, then aggregating”.

That’s because all group homomorphisms necessarily obey the law:

f x <> f y == f (x <> y)

This means that we are free to either “clean first, then aggregate”, or “aggregate first, then clean”.

What’s in a Group?

Now, I don’t know about you, but I definitely feel that this choice we have is definitely not obvious just from reading the problem immediately. Indeed, it seems like the problem might be written to obscure this choice from us: it’s implying that “cleaning, then reacting” is the only correct way, and “reacing, then cleaning” is not something that is even mentioned.

But, thanks to group theory, we know that these are equivalent, so we can substitute which ever version is more efficient!

This is, I believe, at the heart of what people say is the advantage of “using monoids”, “using monads”, “using functors”, etc. in Haskell. That’s because if we state our programs in terms of monoids, monads, groups, functors, etc., then we get the entire body of group theory (or monad theory, or functor theory, etc.) to help us make program reductions that aren’t immediately obviously legal but that have already been proven to be equivalent by mathematicians. We hijack their work!

We get program optimizations and reductions and substitutions for free, by “stealing” from the large body of such things that mathematicians have spent centuries collecting.