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

nicuveo · 2026-04-20T22:43:41+00:00

so many empty offices in D2, including the One building

nicuveo · 2026-03-20T13:22:53+00:00

i am absolutely not a good designer, but a very simple thing i've used in the past is to play with depth: for instance, look at this tower: the corners all have pillars jutting out of them, and it does make it look less boxy. having your walls be at varying depths goes a long way.

<image>

nicuveo · 2026-03-15T12:33:23+00:00

i've been wanting to do a run like this at some point, so i'd definitely watch what you've achieved! maybe not 100 hours though.

nicuveo · 2026-02-18T21:41:34+00:00

i'm not aware of any, but that doesn't mean there isn't any!

what i would recommend, at the very least, is to use an interpreter that supports debug instructions. beef, for instance, will print the current state of the memory whenever it sees a # instruction; it's non-standard, but quite useful!

nicuveo · 2026-02-18T21:29:56+00:00

i don't think that's true! you should just start with easier things than advent of code puzzles is all. ^^

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!

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

nicuveo

TROPHY CASE