Advent of Code 2021 day 13

    The complexity in day 13 came from an unexpected place.

    I continued my trend of created possibly too many data types, with explicit data types for everything I could think of (emphasising the "parse, don't validate" mantra). I use V2 from linear for representing points, and have bespoke data types for both folds and the axis of a fold.

    type Coord = V2 Int
    type Sheet = S.Set Coord
    data Axis = X | Y
      deriving (Eq, Ord, Show)
    data Fold = Fold Axis Int
      deriving (Eq, Ord, Show)

    Parsing the input file has some wrinkles that may be worth noting, specifically how to parse values of type Axis, which have no parameters. Using attoparsec:

    inputP = (,) <$> sheetP <* many1 endOfLine <*> foldsP
    sheetP = S.fromList <$> dotP `sepBy` endOfLine
    dotP = V2 <$> decimal <* "," <*> decimal
    foldsP = foldP `sepBy` endOfLine
    foldP = Fold <$> ("fold along " *> axisP) <* "=" <*> decimal
    axisP = ("x" *> pure X) <|> ("y" *> pure Y)

    Note the use of pure to generate Axis values.

    Folding a sheet involves partitioning the sheet into the two halves, transforming the dots in the right or bottom half, then merging the two results.

    There's some duplicated code here. I could possibly DRY it up only doing a fold in one dimension, and handling the other by transposing the points before and after that fold. But I think this solution is simple enough.

    doFold :: Sheet -> Fold -> Sheet
    doFold sheet (Fold X i) = S.union left foldedRight
      where (left, right) = S.partition ((<= i) . getX) sheet
            foldedRight = foldDot right
            foldDot (V2 x y) = V2 (i - (x - i)) y
    doFold sheet (Fold Y i) = S.union top foldedBottom
      where (top, bottom) = S.partition ((<= i) . getY) sheet
            foldedBottom = foldDot bottom
            foldDot (V2 x y) = V2 x (i - (y - i))

    After that, all that's left is to display the final values. I've got OverloadedLists turned on by default in my Cabal file, which means I need a few explicit type allocations here. That took me too long to work out and solve!

    showSheet :: Sheet -> String
    showSheet sheet = unlines [ concat [showPoint (V2 x y) | x <- ([0..maxX] :: [Int]) 
                                       ] | y <- ([0..maxY] :: [Int]) ]
      where showPoint here = if here `S.member` sheet then "█" else " "
            maxX = S.findMax $ getX sheet
            maxY = S.findMax $ getY sheet


    You can get the code from my locally-hosed Git repo, or from Gitlab.

    Neil Smith

    Read more posts by this author.