Skip to content

Latest commit

 

History

History
414 lines (319 loc) · 16.1 KB

19.md

File metadata and controls

414 lines (319 loc) · 16.1 KB

Day 19: Not Enough Minerals

Your scans show that the lava did indeed form obsidian!

The wind has changed direction enough to stop sending lava droplets toward you, so you and the elephants exit the cave. As you do, you notice a collection of geodes around the pond. Perhaps you could use the obsidian to create some geode-cracking robots and break them open?

To collect the obsidian from the bottom of the pond, you'll need waterproof obsidian-collecting robots. Fortunately, there is an abundant amount of clay nearby that you can use to make them waterproof.

In order to harvest the clay, you'll need special-purpose clay-collecting robots. To make any type of robot, you'll need ore, which is also plentiful but in the opposite direction from the clay.

Collecting ore requires ore-collecting robots with big drills. Fortunately, you have exactly one ore-collecting robot in your pack that you can use to kickstart the whole operation.

Each robot can collect 1 of its resource type per minute. It also takes one minute for the robot factory (also conveniently from your pack) to construct any type of robot, although it consumes the necessary resources available when construction begins.

The robot factory has many blueprints (your puzzle input) you can choose from, but once you've configured it with a blueprint, you can't change it. You'll need to work out which blueprint is best.

For example:

Blueprint 1:
  Each ore robot costs 4 ore.
  Each clay robot costs 2 ore.
  Each obsidian robot costs 3 ore and 14 clay.
  Each geode robot costs 2 ore and 7 obsidian.

Blueprint 2:
  Each ore robot costs 2 ore.
  Each clay robot costs 3 ore.
  Each obsidian robot costs 3 ore and 8 clay.
  Each geode robot costs 3 ore and 12 obsidian.

(Blueprints have been line-wrapped here for legibility. The robot factory's actual assortment of blueprints are provided one blueprint per line.)

The elephants are starting to look hungry, so you shouldn't take too long; you need to figure out which blueprint would maximize the number of opened geodes after 24 minutes by figuring out which robots to build and when to build them.

Using blueprint 1 in the example above, the largest number of geodes you could open in 24 minutes is 9. One way to achieve that is:

== Minute 1 ==
1 ore-collecting robot collects 1 ore; you now have 1 ore.

== Minute 2 ==
1 ore-collecting robot collects 1 ore; you now have 2 ore.

== Minute 3 ==
Spend 2 ore to start building a clay-collecting robot.
1 ore-collecting robot collects 1 ore; you now have 1 ore.
The new clay-collecting robot is ready; you now have 1 of them.

== Minute 4 ==
1 ore-collecting robot collects 1 ore; you now have 2 ore.
1 clay-collecting robot collects 1 clay; you now have 1 clay.

== Minute 5 ==
Spend 2 ore to start building a clay-collecting robot.
1 ore-collecting robot collects 1 ore; you now have 1 ore.
1 clay-collecting robot collects 1 clay; you now have 2 clay.
The new clay-collecting robot is ready; you now have 2 of them.

== Minute 6 ==
1 ore-collecting robot collects 1 ore; you now have 2 ore.
2 clay-collecting robots collect 2 clay; you now have 4 clay.

== Minute 7 ==
Spend 2 ore to start building a clay-collecting robot.
1 ore-collecting robot collects 1 ore; you now have 1 ore.
2 clay-collecting robots collect 2 clay; you now have 6 clay.
The new clay-collecting robot is ready; you now have 3 of them.

== Minute 8 ==
1 ore-collecting robot collects 1 ore; you now have 2 ore.
3 clay-collecting robots collect 3 clay; you now have 9 clay.

== Minute 9 ==
1 ore-collecting robot collects 1 ore; you now have 3 ore.
3 clay-collecting robots collect 3 clay; you now have 12 clay.

== Minute 10 ==
1 ore-collecting robot collects 1 ore; you now have 4 ore.
3 clay-collecting robots collect 3 clay; you now have 15 clay.

== Minute 11 ==
Spend 3 ore and 14 clay to start building an obsidian-collecting robot.
1 ore-collecting robot collects 1 ore; you now have 2 ore.
3 clay-collecting robots collect 3 clay; you now have 4 clay.
The new obsidian-collecting robot is ready; you now have 1 of them.

== Minute 12 ==
Spend 2 ore to start building a clay-collecting robot.
1 ore-collecting robot collects 1 ore; you now have 1 ore.
3 clay-collecting robots collect 3 clay; you now have 7 clay.
1 obsidian-collecting robot collects 1 obsidian; you now have 1 obsidian.
The new clay-collecting robot is ready; you now have 4 of them.

== Minute 13 ==
1 ore-collecting robot collects 1 ore; you now have 2 ore.
4 clay-collecting robots collect 4 clay; you now have 11 clay.
1 obsidian-collecting robot collects 1 obsidian; you now have 2 obsidian.

== Minute 14 ==
1 ore-collecting robot collects 1 ore; you now have 3 ore.
4 clay-collecting robots collect 4 clay; you now have 15 clay.
1 obsidian-collecting robot collects 1 obsidian; you now have 3 obsidian.

== Minute 15 ==
Spend 3 ore and 14 clay to start building an obsidian-collecting robot.
1 ore-collecting robot collects 1 ore; you now have 1 ore.
4 clay-collecting robots collect 4 clay; you now have 5 clay.
1 obsidian-collecting robot collects 1 obsidian; you now have 4 obsidian.
The new obsidian-collecting robot is ready; you now have 2 of them.

== Minute 16 ==
1 ore-collecting robot collects 1 ore; you now have 2 ore.
4 clay-collecting robots collect 4 clay; you now have 9 clay.
2 obsidian-collecting robots collect 2 obsidian; you now have 6 obsidian.

== Minute 17 ==
1 ore-collecting robot collects 1 ore; you now have 3 ore.
4 clay-collecting robots collect 4 clay; you now have 13 clay.
2 obsidian-collecting robots collect 2 obsidian; you now have 8 obsidian.

== Minute 18 ==
Spend 2 ore and 7 obsidian to start building a geode-cracking robot.
1 ore-collecting robot collects 1 ore; you now have 2 ore.
4 clay-collecting robots collect 4 clay; you now have 17 clay.
2 obsidian-collecting robots collect 2 obsidian; you now have 3 obsidian.
The new geode-cracking robot is ready; you now have 1 of them.

== Minute 19 ==
1 ore-collecting robot collects 1 ore; you now have 3 ore.
4 clay-collecting robots collect 4 clay; you now have 21 clay.
2 obsidian-collecting robots collect 2 obsidian; you now have 5 obsidian.
1 geode-cracking robot cracks 1 geode; you now have 1 open geode.

== Minute 20 ==
1 ore-collecting robot collects 1 ore; you now have 4 ore.
4 clay-collecting robots collect 4 clay; you now have 25 clay.
2 obsidian-collecting robots collect 2 obsidian; you now have 7 obsidian.
1 geode-cracking robot cracks 1 geode; you now have 2 open geodes.

== Minute 21 ==
Spend 2 ore and 7 obsidian to start building a geode-cracking robot.
1 ore-collecting robot collects 1 ore; you now have 3 ore.
4 clay-collecting robots collect 4 clay; you now have 29 clay.
2 obsidian-collecting robots collect 2 obsidian; you now have 2 obsidian.
1 geode-cracking robot cracks 1 geode; you now have 3 open geodes.
The new geode-cracking robot is ready; you now have 2 of them.

== Minute 22 ==
1 ore-collecting robot collects 1 ore; you now have 4 ore.
4 clay-collecting robots collect 4 clay; you now have 33 clay.
2 obsidian-collecting robots collect 2 obsidian; you now have 4 obsidian.
2 geode-cracking robots crack 2 geodes; you now have 5 open geodes.

== Minute 23 ==
1 ore-collecting robot collects 1 ore; you now have 5 ore.
4 clay-collecting robots collect 4 clay; you now have 37 clay.
2 obsidian-collecting robots collect 2 obsidian; you now have 6 obsidian.
2 geode-cracking robots crack 2 geodes; you now have 7 open geodes.

== Minute 24 ==
1 ore-collecting robot collects 1 ore; you now have 6 ore.
4 clay-collecting robots collect 4 clay; you now have 41 clay.
2 obsidian-collecting robots collect 2 obsidian; you now have 8 obsidian.
2 geode-cracking robots crack 2 geodes; you now have 9 open geodes.

However, by using blueprint 2 in the example above, you could do even better: the largest number of geodes you could open in 24 minutes is 12.

Determine the quality level of each blueprint by multiplying that blueprint's ID number with the largest number of geodes that can be opened in 24 minutes using that blueprint. In this example, the first blueprint has ID 1 and can open 9 geodes, so its quality level is 9. The second blueprint has ID 2 and can open 12 geodes, so its quality level is 24. Finally, if you add up the quality levels of all of the blueprints in the list, you get 33.

Determine the quality level of each blueprint using the largest number of geodes it could produce in 24 minutes. What do you get if you add up the quality level of all of the blueprints in your list?

Your puzzle answer was 1115.

Part Two

While you were choosing the best blueprint, the elephants found some food on their own, so you're not in as much of a hurry; you figure you probably have 32 minutes before the wind changes direction again and you'll need to get out of range of the erupting volcano.

Unfortunately, one of the elephants ate most of your blueprint list! Now, only the first three blueprints in your list are intact.

In 32 minutes, the largest number of geodes blueprint 1 (from the example above) can open is 56.

However, blueprint 2 from the example above is still better; using it, the largest number of geodes you could open in 32 minutes is 62.

You no longer have enough blueprints to worry about quality levels. Instead, for each of the first three blueprints, determine the largest number of geodes you could open; then, multiply these three values together.

Don't worry about quality levels; instead, just determine the largest number of geodes you could open using each of the first three blueprints. What do you get if you multiply these numbers together?

Your puzzle answer was 25056.

Solution

We'll solve this in Python using Linear Programming, and then again in Typescript using DFS with some heuristics.

Python Integer Programming - Code

See the Python setup in README and intro of this in 2020 day 21.

Formulation

Indices
  • $t\in T$ - a specific time interval
  • $Type = {Ore, Clay, Obsidian}$ - Set of types available
  • $j\in Type$
  • $i\in Type$
Parameters
  • T - number of minutes to run the blueprint
  • $c_ij$ - How many js you need to build i, where $i\in Type$ and $j\in Type$. This is determined based on blueprint.
Variables

$$ \begin{flalign} & \text{Ore}_{t} = \text{Amount of ores available at time t}. & \end{flalign} $$

  • Similar variables exist for $\text{Clay}_t$, $\text{Obsidian}_t$, $\text{Geode}_t$.

$$ \begin{flalign} & \text{OreRobot}_{t} = \text{Number of ore robots you have at time t}. & \end{flalign} $$

  • Similar variables exist for $\text{ClayRobot}_t$, $\text{ObsidianRobot}_t$, and $\text{GeodeRobot}_t$.

$$ \begin{flalign} & \text{OreRobotBuilt}_{t} = \left\lbrace\matrix{1&\text{if an ore robot was built at time t} \cr 0&\text{otherwise}}\right. & \end{flalign} $$

  • Similar variables exist for $\text{ClayRobotBuilt}_t$, $\text{ObsidianRobotBuilt}_t$, and $\text{GeodeRobotBuilt}_t$.
Objective

$$ \begin{flalign} & \max{z} = \text{Geode}_T. & \end{flalign} $$

Maximize the number of geode resources available at the end, which is t = T.

Constraints
  1. Ores at time t is equal to ores t - 1 plus number of ore robots at t - 1 minus all the ores used at time t.

$$ \forall_t \text{Ore}t = \text{Ore}{t-1} + \text{OreRobot}{t-1} - c{ore,ore}\times\text{OreRobotBuilt}{t} - c{clay,ore}\times\text{ClayRobotBuilt}t - c{obsidian,ore}\times\text{ObsidianRobotBuilt}t - c{geode,ore}\times\text{GeodeRobotBuilt}_t $$

  1. Ores built at time t is equal to ores built at t - 1 + robots built at t - 1.

$$ \forall_t \space\space\space\space\space\space\space \text{OreRobot}t = \text{OreRobot}{t-1} + \text{OreRobotBuilt}_{t-1} $$

  1. One robot can be built per time t.

$$ \forall_t \space\space\space\space\space\space\space \text{OreRobotBuilt}_t + \text{ClayRobotBuilt}_t + \text{ObsidianRobotBuilt}_t + \text{GeodeRobotBuilt}_t <= 1 $$

Code

The code can be found here.

Typescript Solution - Code

The solution is a depth-first search (DFS) with some heuristics that eliminate some of the search space for us.

Here's a few interfaces to guide us there.

interface Cost {
  ore: number;
  clay: number;
  obsidian: number;
}

interface Blueprint {
  oreRobot: Cost;
  clayRobot: Cost;
  obsidianRobot: Cost;
  geodeRobot: Cost;
}

interface State {
  resourcesAvailable: {
    ore: number;
    clay: number;
    obsidian: number;
    geode: number;
  };
  robots: {
    ore: number;
    clay: number;
    obsidian: number;
    geode: number;
  };
}

Heuristic 1: Branch and bound

Don't explore a path if the maximum potential geode we could get from this path is less than our current known maximum. This is called Branch and bound, where we relax the resources constraints. We assume we have infinite resources (or that building geodes takes no resources) and that we can build a geode every single minute.

We have an estimate (or bound) that starts off pretty bad because of how optimistic it is, and then once we start to get actual readings on what the actual maximum is, we can test that estimate (or bound) with our current known maximum. See OneNote -> Math -> LP-IP -> Discrete Optimization Coursera Course -> Branch/Bound for more examples of this.

Here's a function that takes the current state and time remaining to determine the maximum possible geodes.

/**
 * Given there are N minutes left, what's the max number of geodes can you make
 * if you have infinite resources? It's the sum of
 *    * number of geodes you already have
 *    * number of geode robots you have * timeRemaining
 *        - E.g., if you have two robots and 5 remaining minutes, you'll make 10 geodes.
 *    * (timeRemaining-1) + (timeRemaining-2) + .. + 1
 *             = (timeRemaining) * (timeRemaining - 1) / 2
 *        - This is assuming you have infinite resources and you can build a
 *        geode every minute. If you have 2 miutes left, you can build a robot
 *        at t=2, and that robot can create 1 geode.
 *        - If you have 3 minutes left, you build a robot#1 at t=3, which would
 *        collect 2 geodes before time ran out. You build robot #2 at t=2, which
 *        would collect 1 geode.
 *        - With 4 minute left, you'd end up with 3 + 2 + 1 = 6 geode.
 *        - With N minute left, you'd end up with (N-1) + (N-2) + .. + 1 =
 *          N(N-1)/2 geodes.
 */
function potentialGeodes({
  timeRemaining,
  ...state
}: State & { timeRemaining: number }) {
  const futurePotential =
    timeRemaining <= 1 ? 0 : (timeRemaining * (timeRemaining - 1)) / 2;
  return (
    state.resourcesAvailable.geode +
    state.robots.geode * timeRemaining +
    futurePotential
  );
}

Heuristic 2

Say your blueprint says you need 1 ore to build ore robot, 2 for clay, 3 for obsidian, and 4 for geode. These robots don't need any other resources to build them.

If you already have 5 ores and 1 ore robot, there's no point exploring a path that doesn't build any robots where you just collect more ores. There's nothing to gain from hogging more ores. You can build any robot you want right now.

This heuristic eliminates paths that only collect resources if you have ample resources. And ample resource is defined as when you have enough resources to build any robot you want.

/**
 * If you have enough resources to build any robot, don't bother with collecting
 * more resources (causing this function to return false). You should instead be
 * building bots + collecting resources at the same time.
 */
function addMoreResources(state: State, blueprint: Blueprint): boolean {
  const { ore, clay, obsidian } = state.resourcesAvailable;
  const { oreRobot, clayRobot, obsidianRobot, geodeRobot } = blueprint;
  if (
    ore <
    Math.max(oreRobot.ore, clayRobot.ore, obsidianRobot.ore, geodeRobot.ore)
  ) {
    return true;
  } else if (
    clay <
    Math.max(oreRobot.clay, clayRobot.clay, obsidianRobot.clay, geodeRobot.clay)
  ) {
    return true;
  } else if (
    obsidian <
    Math.max(
      oreRobot.obsidian,
      clayRobot.obsidian,
      obsidianRobot.obsidian,
      geodeRobot.obsidian
    )
  ) {
    return true;
  }
  return false;
}

Code

Code can be found here.