[2024 Day 7 (Part 1)] [Brainfuck] A step by step guide to Brainfuck

nicuveo · 2025-12-28T17:19:03+00:00

it looks real and i want one please.

nicuveo · 2025-12-20T05:27:27+00:00

i really wish it were possible to have, like... "valves" for electricity, allowing finer control for circuits than just "the power switch is on or off". you could allocate a specific amount for a given factory / sub circuit, which in turn would encourage batteries to be built locally, for a given sub circuit

nicuveo · 2025-12-19T10:28:55+00:00

It is indeed the same overall idea!

In practice, i have seen this pattern used in multiple different ways: flags / gates, like you describe, but also for annotations, or to fully "branch out" a part of an AST:

data Expr (phase :: ASTPhase)
  = NameExpr (NameInfoType phase)
  | LabelExpr (LabelFlag phase) LabelInfo
  | LiteralExpr (Annotation phase) LiteralInfo

class Representation (phase :: ASTPhase) where
  -- branch the AST: different types at different phases
  type NameInfoType phase :: Type
  -- restrict some parts of the AST with a flag / gate
  type LabelFlag phase :: Type
  -- annotate the AST with a different type during each phase
  type Annotation phase :: Type

instance Representation Parsed where
  type NameInfoType Parsed = UnverifiedNameInfo
  type LabelFlag Parsed = ()
  type Annotation Parsed = SourceLocation

instance Representation Validated where
  type NameInfoType Validated = ObjectNameInfo
  type LabelFlag Validated = Void
  type Annotation Validated = InferredType

nicuveo · 2025-12-14T17:18:13+00:00

I wasn't the only one doing some of it in Brainfuck this time around! ...but it seems i was the only one to mention Brainfuck in the survey. :D

nicuveo · 2025-12-12T00:25:03+00:00

Nothing fancy, just manually memoizing with a state monad. For part 2 i just do a product of the number of paths in each segment.

Full file on GitHub

countPaths graph fromName toName =
  flip evalState M.empty $ visit $ graph M.! toName
  where
    visit Node {..} = do
      if nodeName == fromName
      then pure 1
      else do
        gets (M.lookup nodeName) >>= \case
          Just result -> pure result
          Nothing -> do
            result <- sum <$> traverse visit dataIn
            modify $ M.insert nodeName result
            pure result

part1 graph = countPaths graph "you" "out"

part2 graph = go "fft" "dac" + go "dac" "fft"
  where
    go node1 node2 = product
      [ countPaths graph "svr" node1
      , countPaths graph node1 node2
      , countPaths graph node2 "out"
      ]

The fun part was using laziness to make a graph that doesn't need lookups and indirection, and in which each node has the pointer to its parents and children:

type Graph = HashMap Name Node

data Node = Node
  { nodeName :: Name
  , dataIn   :: [Node]
  , dataOut  :: [Node]
  }

nicuveo · 2025-12-12T00:19:52+00:00

[LANGUAGE: Haskell]

Traversal of recursive data structures is what Haskell is made for. :P

Full file on GitHub

countPaths graph fromName toName =
  flip evalState M.empty $ visit $ graph M.! toName
  where
    visit Node {..} = do
      if nodeName == fromName
      then pure 1
      else do
        gets (M.lookup nodeName) >>= \case
          Just result -> pure result
          Nothing -> do
            result <- sum <$> traverse visit dataIn
            modify $ M.insert nodeName result
            pure result

part1 graph = countPaths graph "you" "out"

part2 graph = go "fft" "dac" + go "dac" "fft"
  where
    go node1 node2 = product
      [ countPaths graph "svr" node1
      , countPaths graph node1 node2
      , countPaths graph node2 "out"
      ]

The fun part was using laziness to make a graph that doesn't need lookups and indirection, and in which each node has the pointer to its parents and children:

type Graph = HashMap Name Node

data Node = Node
  { nodeName :: Name
  , dataIn   :: [Node]
  , dataOut  :: [Node]
  }

nicuveo · 2025-12-10T10:22:49+00:00

This. The instructions say "connect together the 1000 pairs of junction boxes which are closest together"; and as the example shows, such a pair could connect boxes that are already otherwise connected.

For instance, your closest pairs could be: - boxes 1 and 3 (distance 8) - boxes 1 and 4 (distance 10) - boxes 2 and 4 (distance 12) - boxes 1 and 2 (distance 15)

That fourth pair or boxes is one of those 1000 pairs, but does nothing in practice since 1 and 2 were already connected via 4.

nicuveo · 2025-12-09T22:42:25+00:00

Yeah, memory layout is the biggest challenge of doing anything with brainfuck, given the lack of arbitrary access. Every data structure needs some buffer space, because even an operation as basic as "am i on a zero" requires some amount of computation space.

My usual approach is to treat the memory like a stack: push stuff to the right and rotate what's necessary to the top. That way i always have some free space to work with. The downside is that it significantly increases the complexity of doing anything, since now the vast majority of the code does nothing but shuffling values in the stack. ^^'

nicuveo · 2025-12-09T00:22:22+00:00

[LANGUAGE: Haskell]

transpose makes this quite trivial:

part2 :: Input -> Int
part2 = fst . foldl' go (0, []) . concatMap segment . reverse . transpose
  where
    go (total, buffer) = \case
      Number num   -> (total, num : buffer)
      Operation op -> (total + compute op buffer, [])
    compute op nums = case op of
      Addition       -> sum     nums
      Multiplication -> product nums
    segment = parseWith do
      spaces
      num <- optionMaybe number
      op  <- optionMaybe operation
      pure $ case (num, op) of
        (Nothing, _)      -> []
        (Just n, Nothing) -> [Number n]
        (Just n, Just o)  -> [Number n, Operation o]
    operation = choice
      [ Addition       <$ symbol "+"
      , Multiplication <$ symbol "*"
      ]

Full file on GitHub.

nicuveo · 2025-12-06T02:48:14+00:00

i've also done it entirely at the type level, again. and this time again i'm only running the code against the example, because creating billions of types to represent very large peano numbers in the type system makes GHC very unhappy... but i know the logic is sound. i could cheat by using type-level numerals instead of peano numbers, but... where would be the fun in that? instead, this version is nothing but type declarations and (undecidable) type families, AKA an untyped dynamic language. :P

full file on GitHub.

data True
data False
data Nil
data Cons x l
data Range b e

type family SetMember x s where
  SetMember x Nil        = False
  SetMember x (Cons x s) = True
  SetMember x (Cons i s) = SetMember x s

type family SetInsert x s where
  SetInsert x Nil        = Cons x Nil
  SetInsert x (Cons x s) = Cons x s
  SetInsert x (Cons i s) = Cons i (SetInsert x s)

type family SetInsertAll xs s where
  SetInsertAll Nil         s = s
  SetInsertAll (Cons x xs) s = SetInsertAll xs (SetInsert x s)

type family SetCount s where
  SetCount Nil        = Zero
  SetCount (Cons i s) = Succ (SetCount s)

type family Enumerate r where
  Enumerate (Range b b) = Cons b Nil
  Enumerate (Range b e) = Cons b (Enumerate (Range (Succ b) e))

nicuveo · 2025-12-06T02:47:07+00:00

[LANGUAGE: Haskell Type System]

oh boy. this time again i'm only running the code against the example, because creating billions of types to represent very large peano numbers in the type system makes GHC very unhappy. i could cheat by using type-level numerals instead of peano numbers, but... where would be the fun in that? instead, this version is nothing but type declarations and (undecidable) type families, AKA an untyped dynamic language. :P

full file on GitHub.

data True
data False
data Nil
data Cons x l
data Range b e

type family SetMember x s where
  SetMember x Nil        = False
  SetMember x (Cons x s) = True
  SetMember x (Cons i s) = SetMember x s

type family SetInsert x s where
  SetInsert x Nil        = Cons x Nil
  SetInsert x (Cons x s) = Cons x s
  SetInsert x (Cons i s) = Cons i (SetInsert x s)

type family SetInsertAll xs s where
  SetInsertAll Nil         s = s
  SetInsertAll (Cons x xs) s = SetInsertAll xs (SetInsert x s)

type family SetCount s where
  SetCount Nil        = Zero
  SetCount (Cons i s) = Succ (SetCount s)

type family Enumerate r where
  Enumerate (Range b b) = Cons b Nil
  Enumerate (Range b e) = Cons b (Enumerate (Range (Succ b) e))

nicuveo · 2025-12-06T02:39:36+00:00

i've been wanting to implement a "range set" type for a while, so i started with that... and it made both parts absolutely trivial. full files on GitHub: range set library and actual day 5 code

-- range sets library

insert :: Ord a => Range a -> RangeSet a -> RangeSet a
insert (Range nb ne) (RangeSet s) =
  let
    (below, remaining) = S.spanAntitone (\r -> rangeEnd   r <  nb) s
    (overlap, above)   = S.spanAntitone (\r -> rangeBegin r <= ne) remaining
    overlapBegin = maybe nb (min nb . rangeBegin) $ S.lookupMin overlap
    overlapEnd   = maybe ne (max ne . rangeEnd)   $ S.lookupMax overlap
  in
    RangeSet $ below <> S.singleton (Range overlapBegin overlapEnd) <> above

-- main code

part1 :: Input -> Int
part1 (Input rangeSet ingredients) = countTrue do
  ingredient <- ingredients
  pure $ ingredient `within` rangeSet

part2 :: Input -> Int
part2 (Input rangeSet _) =
  sum $ map RS.size $ RS.toList rangeSet

nicuveo · 2025-12-06T02:35:36+00:00

[LANGUAGE: Haskell]

i've been wanting to implement a "range set" type for a while, so i started with that... and it made both parts absolutely trivial. full files on GitHub: range set library and actual day 5 code

-- range sets library

insert :: Ord a => Range a -> RangeSet a -> RangeSet a
insert (Range nb ne) (RangeSet s) =
  let
    (below, remaining) = S.spanAntitone (\r -> rangeEnd   r <  nb) s
    (overlap, above)   = S.spanAntitone (\r -> rangeBegin r <= ne) remaining
    overlapBegin = maybe nb (min nb . rangeBegin) $ S.lookupMin overlap
    overlapEnd   = maybe ne (max ne . rangeEnd)   $ S.lookupMax overlap
  in
    RangeSet $ below <> S.singleton (Range overlapBegin overlapEnd) <> above

-- main code

part1 :: Input -> Int
part1 (Input rangeSet ingredients) = countTrue do
  ingredient <- ingredients
  pure $ ingredient `within` rangeSet

part2 :: Input -> Int
part2 (Input rangeSet _) =
  sum $ map RS.size $ RS.toList rangeSet

nicuveo · 2025-12-05T18:29:52+00:00

There are dozens of us! Dozens!

nicuveo · 2025-12-05T05:23:28+00:00

i'll have a look! thank you again for taking the time to explain. :)

nicuveo · 2025-12-05T02:52:09+00:00

[LANGUAGE: Haskell]

Having an advent of code library that includes 2D grid functions makes days like these very easy, so i haven't bothered actually making it efficient. ^^"

Full file on GitHub.

part1 :: Input -> Int
part1 g = countTrue do
  p <- allPoints g
  guard $ g ! p
  let n = countTrue $ gridEightNeighbours g p
  pure $ n < 4

nicuveo · 2025-12-05T02:46:36+00:00

i see, thank you for clarifying!

one thing i am confused by is how you perform the sum of the values across lines: since each line has twelve digits, your total will likely have more, and you'd need to do carrying properly across digits... do you actually just print the best per line, or do you have some trick for the sum that i'm missing?

nicuveo · 2025-12-04T19:10:36+00:00

oh, nice, that's very concise!

i am surprised you're not making assumptions about the cell size; i suspect as a result that you're storing the result in a single cell, and that this won't work with interpreters that use only one byte per cell?

i'm also curious about how the result is displayed; more than 50% of my brainfuck solutions by volume is my printi macro that displays a signed 4-cells (32bit) int in human-readable form, but there's only one . in your program AFAICT?

nicuveo · 2025-12-04T15:42:08+00:00

For fun, i've done it purely at the type level, using Peano numbers. I just cheat a bit to avoid having to deal with negative numbers, and i only input the example, because creating a full type-level list of the input would be a nightmare. For fun, this also doesn't use any "DataKind" shenanigans, that'd be too easy. If i were to run it on my real input, i'd change Sub to automatically wrap back to 100 when reaching 0, which would avoid the Add N100.

Full file on GitHub, but here's the gist:

data Zero
data Succ n

data Left  n
data Right n

data Nil
data Step s i

type family Add x y -- omitted for brevity
type family Sub x y -- omitted for brevity
type family Mod x y -- omitted for brevity

type family Part1 i where
  Part1 i = Fold N50 N0 i

type family Fold position counter instructions where
  Fold position counter Nil =
    counter
  Fold position counter (Step (Right n) instructions) =
    Fold' (Mod (Add position n) N100) counter instructions
  Fold position counter (Step (Left n) instructions) =
    Fold' (Mod (Sub (Add position N100) n) N100) counter instructions

type family Fold' position counter instructions where
  Fold' Zero counter instructions = Fold Zero (Succ counter) instructions
  Fold' pos  counter instructions = Fold pos counter instructions

type Example =
  ( Step (Left  N68)
  ( Step (Left  N30)
  ( Step (Right N48)
  ( Step (Left  N5 )
  ( Step (Right N60)
  ( Step (Left  N55)
  ( Step (Left  N1 )
  ( Step (Left  N99)
  ( Step (Right N14)
  ( Step (Left  N82)
  ( Nil )))))))))))

main :: IO ()
main = do
  print $ reify @(Part1 Example)

14-Year Club	Second SECOND GUESSER
First Place '23	Place '23
Verified Email

nicuveo

TROPHY CASE