AoC 2022 D19: Not Enough Minerals

| Problem statement | Source code | Tags: Dynamic programming

← Previous Back to AoC Index Next →

Part 1

This is very similar to day 16. We also want to explore a decision space and maximize the output, where the score of each decision is dependent on how early we made it. Let's start by defining the states of our space.

data State = State
  { ore :: Int,
    clay :: Int,
    obsidian :: Int,
    geode :: Int,
    oreBots :: Int,
    clayBots :: Int,
    obsidianBots :: Int,
    time :: Int
  }
  deriving (Show)

initState :: State
initState =
  State
    { ore = 0,
      clay = 0,
      obsidian = 0,
      geode = 0,
      oreBots = 1,
      clayBots = 0,
      obsidianBots = 0,
      time = 0
    }

Note that I don't keep track of geodeBots in the state, because they don't affect state transitions. Each time we build a geode bot, we can immediately add the geodes it will produce to the score.

I see some people basing their state transitions on "what should I do the next minute?", but the key observation is that most of these recursion steps result in nothing happening because we don't have enough resources to build anything. Instead, like day 16 (where we directly decide which valve to open next, not which valve to go to next), we can base our state transitions on "what should I build next?" This way, we can skip over all the states where we just wait for resources to accumulate.

I use a DFS, like day 16. For each state, we try building each type of bot. If no bot can be built (probably because not enough time left to gather enough resources), then the only choice is to sit and wait for the remaining time to elapse.

bestOutput :: Int -> Blueprint -> Int
bestOutput t bp = go 0 [initState]
  where
    go :: Int -> [State] -> Int
    go best [] = best
    go best (st : stk)
      -- If can't build any bots, tally the score.
      | null nextStates = go (max best (geode st)) stk
      | otherwise = go best stk'
      where
        nextStates =
          [ buildBot t bp st bot
            | bot <- [Ore, Clay, Obsidian, Geode],
              canBuildBot t bp st bot
          ]
        stk' = nextStates ++ stk

The core logic is in the canBuildBot and buildBot functions. The most important part about state transitioning is figuring out how long it will take to build the next bot, which includes gathering the resources and actually building the bot. For example, if we have 2 ores and 2 ore bots, and we need 7 ores, then we need 5 more ores, which is going to take 3 minutes to mine (ceiling division), and then another minute to build a bot. When building obsidian and geode bots, we need two resources to be simultaneously available.

timeToMeetReq :: Int -> Int -> Int -> Int
timeToMeetReq req cur rate
  | short <= 0 = 0
  | otherwise = ceilDiv short rate
  where
    short = req - cur

timeToBuildBot :: BotType -> Blueprint -> State -> Int
timeToBuildBot Ore bp st = timeToMeetReq (oreReq bp) (ore st) (oreBots st) + 1
timeToBuildBot Clay bp st = timeToMeetReq (clayReq bp) (ore st) (oreBots st) + 1
timeToBuildBot Obsidian bp st =
  let (oreSpent, claySpent) = obsidianReq bp
      durOre = timeToMeetReq oreSpent (ore st) (oreBots st) + 1
      durClay = timeToMeetReq claySpent (clay st) (clayBots st) + 1
   in max durOre durClay
timeToBuildBot Geode bp st =
  let (oreSpent, obsidianSpent) = geodeReq bp
      durOre = timeToMeetReq oreSpent (ore st) (oreBots st) + 1
      durObsidian = timeToMeetReq obsidianSpent (obsidian st) (obsidianBots st) + 1
   in max durOre durObsidian

How do we know if we can and should build a bot? This is the most important bit because edge pruning happens here. For part 1 I didn't do any aggressive pruning, so there are only 3 conditions:

1. We can't build a bot if we have no bots producing its required resources. For example, we can't build an obsidian bot if we have no clay bots, because we will never be able to gather the required clay. This prevents division by zero in the timeToBuildBot function.
2. We can't build a bot if we don't have enough time to gather the required resources and build the bot, including if the bot is finished right at the time limit, since it can't mine more things.
3. (Optimization) We don't need to build more bots than the maximum required resources for a bot, since we can only build one bot per minute. For example, if we need 4 clays per obsidian bot, then we don't need more than 4 clay bots, because we can't spend more than 4 clays per minute. For ores, we take the maximum of all ore requirements.

canBuildBot :: Int -> Blueprint -> State -> BotType -> Bool
canBuildBot t bp st ty = hasBot && hasTime && needsMore
  where
    hasBot = case ty of
      Ore -> True
      Clay -> True
      Obsidian -> clayBots st > 0
      Geode -> obsidianBots st > 0
    hasTime = timeToBuildBot ty bp st + time st < t
    maxOreReq = maximum [oreReq bp, clayReq bp, fst (obsidianReq bp), fst (geodeReq bp)]
    needsMore = case ty of
      Ore -> oreBots st < maxOreReq
      Clay -> clayBots st < snd (obsidianReq bp)
      Obsidian -> obsidianBots st < snd (geodeReq bp)
      Geode -> True

Now for actually building the bot. We first run the state forward by the time it takes to build the bot. Then we subtract the resources we spent to build the bot, and add the new bot to the state. As stated before, if we build a geode bot, we can immediately add the geodes it will produce to the score, so we don't need to keep track of geode bots in the state.

buildBot :: Int -> Blueprint -> State -> BotType -> State
buildBot t bp st ty = case ty of
  Ore -> st' {oreBots = oreBots st' + 1, ore = ore st' - oreReq bp}
  Clay -> st' {clayBots = clayBots st' + 1, ore = ore st' - clayReq bp}
  Obsidian ->
    let (oreSpent, claySpent) = obsidianReq bp
     in st'
          { obsidianBots = obsidianBots st' + 1,
            ore = ore st' - oreSpent,
            clay = clay st' - claySpent
          }
  Geode ->
    let (oreSpent, obsidianSpent) = geodeReq bp
     in st'
          { obsidian = obsidian st' - obsidianSpent,
            ore = ore st' - oreSpent,
            geode = geode st' + t - time st' -- Immediately mine all geodes
          }
  where
    dur = timeToBuildBot ty bp st
    -- Run the state forward for dur minutes, not building any bots.
    st' =
      st
        { ore = ore st + oreBots st * dur,
          clay = clay st + clayBots st * dur,
          obsidian = obsidian st + obsidianBots st * dur,
          time = time st + dur
        }

Performance is okay: it runs in ~350ms.

Part 2

Because the state space grows exponentially with time, adding another 8 minutes to the time limit roughly means multiplying the runtime by $4^8 = 65536$! In reality, because of the "no more bots than necessary" pruning, we actually don't explore that many states after a given time point. Also because the number of blueprints went from 30 to 3, the actual runtime is about 41s, a 130x increase. However, I believe I can do better than 40s.

I just implemented a single pruning condition: if we can't do better than the current best by building a geode bot every minute, then we can stop exploring this branch. With t minutes left, we can build at most t - 1 geode bots, each producing 1, 2, ..., t - 1 geodes, so the maximum number of geodes we can produce is t * (t - 1) / 2. If this plus the current geodes is less than the best score, then we can stop exploring this branch.

geodesLeftUpperBound :: Int -> State -> Int
geodesLeftUpperBound t st =
  let timeLeft = t - time st
   in timeLeft * (timeLeft - 1) `div` 2

Now we add this single condition to the DFS:

go best (st : stk)
  -- If can never beat the best, skip this branch.
  | geode st + geodesLeftUpperBound t st <= best = go best stk
  -- If can't build any bots, tally the score.
  | null nextStates = go (max best (geode st)) stk
  | otherwise = go best stk'

And 🔥🔥🔥 part 2's runtime drops to 40ms (1000x speedup), and part 1's drops to 82ms! I guess this is the beauty of edge pruning.

(Note: I tagged this one as "dynamic programming", because DFS on a state space with memoization is just DP. At this point I just think DP is an extremely uninformative branding.)

← Previous Back to AoC Index Next →