Learning Python with Advent of Code Walkthroughs
Dazbo's Advent of Code solutions, written in Python
Advent of Code 2022 - Day 19
Useful Links
Concepts and Packages Demonstrated
Page Navigation
Problem Intro
We would like to collect geodes. In order to do so, we need:
- Geode-cracking robots, to release the geodes
- Obsidian-collecting robots
- Clay-collecting robots
- Ore-collecting robots; we start with one of these.
Timings:
- Each robot can collect one of its corresponding resource per minute.
- Our robot factory can assemble any robot from its requisite ingrediens in one minute. The resources are consumed at the beginning of any fabrication minute.
Our input contains blueprints for robot types. The input data looks like this:
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.
Part 1
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. Calculate the sum of he quality levels of all the blueprints in your input data.
Essentially, this problem is about calculating all the possible orders in which we can build robots in each blueprint, to determine the maximum number of geodes that can be obtained from each blueprint.
We can do this using a BFS to determine all possible states that can be achieved in the 24 minutes we’ve been given. With each minute that passes, we flood fill to the possible states in the next minutes.
First, I’ll create an Enum type for the mineral types. This is to make the code a bit more readable, to avoid any str typos, and to facilitate autocompletion.
class MineralType(Enum):
""" Enumerate mineral / robot types """
ORE = "ore"
CLAY = "clay"
OBSIDIAN = "obsidian"
GEODE = "geode"
Then I create a Blueprint class. It is simply a dataclass that stores our blueprint ID, and a dict that stores the material cost to build a given robot. This is a nested dictionary.
@dataclass(frozen=True)
class Blueprint():
""" Store blueprint ID, with a dict for each robot type, that in turn contains a nested dict
of all mineral costs for that robot. """
id: int
costs: dict # { "ore": {"ore": 4}, "obsidian": {"ore": 3, clay: 14}, ...}
def get_max_cost(self, mineral: MineralType):
""" Return the maximum cost of a given mineral type for all robots in this blueprint. """
# If this robot does not contain a given mineral in the blueprint, return 0 for this mineral
return max([self.costs[MineralType.ORE.value].get(mineral.value, 0),
self.costs[MineralType.CLAY.value].get(mineral.value, 0),
self.costs[MineralType.OBSIDIAN.value].get(mineral.value, 0),
self.costs[MineralType.GEODE.value].get(mineral.value, 0)])
The interesting thing to note about this class is the get_max_cost() method. This looks at each bot type in turn, and then determines the maximum rate we can consume the specified mineral. (I sometimes refer to this as spend rate later.) I.e. because bots consume these minerals at different rates, and we want the rate that is highest. I use this later in optimising the solution.
Now we can read in the input data:
def parse_data(data: list[str]) -> list[Blueprint]:
""" Read the input and return a list of Blueprint """
pattern = re.compile(r"Each (\w+) robot costs (\d+) (\w+)(?: and (\d+) (\w+))*.")
blueprints = []
for line in data:
blueprint_id = int(line.split(":")[0].split()[-1])
costs = {}
for matches in pattern.findall(line):
robot = matches[0]
minerals = {}
for i in range(2, len(matches) + 1, 2):
if matches[i]: # if not empty
minerals[matches[i]] = int(matches[i-1])
costs[robot] = minerals
blueprints.append(Blueprint(blueprint_id, costs))
return blueprints
- Getting the ID is trivial. We just split the current line at the
:, then all the words before the:by space, and return the last value. This is the ID. Convert it to anint. - For the robots and their costs, we’re using regex.
- A given robot either costs
x something, or it costsx something and y something-else. So, in the regex, I’ve made theand y something-elsean optional group. Also, I’m using(?: whatever)to define this optional group as a non-capturing group. That means that this repeating group doesn’t itself get returned as a match. (But groups inside it do.) - We then grab each subsequent pair of matches to build our
dictofK:Vpairs, whereKis the mineral required, andVis integer amount.
- A given robot either costs
The rest of the solution is simply a BFS. It works by popping the current state off the frontier, checking if we’ve used up all our time, and if we haven’t, it adds all possible next states on to our frontier. Those next states can only be from the following:
- Do not build any robot; simply accumulate resources with the robots we have.
- Build an ore robot.
- Build a clay robot.
- Build an obsidian robot.
- Build a geode robot.
In each case, the subsequent state needs to:
- Decrease the time by 1.
- Increment the respective robot, where applicable.
- Decrement resources that were used to build a robot, if applicable.
- Increment the mineral levels, by a number equivalent to the number of robots of that type.
We’ll need to track these states, so I’ve created a State class:
@dataclass(frozen=True)
class State():
t_remaining: int
ore: int = 0
clay: int = 0
obsidian: int = 0
geode: int = 0
ore_r: int = 1
clay_r: int = 0
obsidian_r: int = 0
geode_r: int = 0
At last, we’re ready to implement the actual BFS. (Recall that I explain how BFS works here.)
def bfs(blueprint: Blueprint, state: State):
best = 0
frontier = deque([state])
explored = set()
max_ore_cost = blueprint.get_max_cost(MineralType.ORE)
max_clay_cost = blueprint.get_max_cost(MineralType.CLAY)
max_obsidian_cost = blueprint.get_max_cost(MineralType.OBSIDIAN)
while frontier:
state = frontier.popleft() # popleft for BFS; pop for DFS
best = max(best, state.geode)
if state.t_remaining == 0:
continue
# Optimise state space by throwing away robots we can't use
# E.g. if the highest per minute ore cost is 4, then there's no point having more than 4 ore robots.
ore_r = min(state.ore_r, max_ore_cost)
clay_r = min(state.clay_r, max_clay_cost)
obs_r = min(state.obsidian_r, max_obsidian_cost)
# optimise state space by throwing away resources we can't possibly spend in the time we have left.
# E.g. if t=10 and max ore cost is 4, then we can only spend a max of 40 ore.
# So if we have more than 40, throw it away.
# Of course, we can't throw away any geodes!
ore = min(state.ore, state.t_remaining * max_ore_cost - ore_r*(state.t_remaining-1))
clay = min(state.clay, state.t_remaining * max_clay_cost - clay_r*(state.t_remaining-1))
obs = min(state.obsidian, state.t_remaining * max_obsidian_cost - obs_r*(state.t_remaining-1))
# If our optimisations are applicable, amend our state to reflect the optimised state.
# Thus, fewer overall states to explore.
state = State(state.t_remaining,
ore, clay, obs, state.geode,
ore_r, clay_r, obs_r, state.geode_r)
if state in explored:
continue
explored.add(state)
# Now add each possible next state to the frontier...
# 1st option: Don't make any robots; just accumulate.
# New mineral levels are simply old levels + number of each robot type
frontier.append(State(state.t_remaining-1,
ore+ore_r,
clay+clay_r,
obs+obs_r,
state.geode+state.geode_r,
ore_r, clay_r, obs_r, state.geode_r))
# Remaining options: build one of each bot, if we can
if ore >= blueprint.costs[MineralType.ORE.value].get(MineralType.ORE.value, 0):
# build ore robot
frontier.append(State(state.t_remaining-1,
ore-blueprint.costs[MineralType.ORE.value][MineralType.ORE.value]+ore_r,
clay+clay_r,
obs+obs_r,
state.geode+state.geode_r,
ore_r+1, clay_r, obs_r, state.geode_r))
if ore >= blueprint.costs[MineralType.CLAY.value][MineralType.ORE.value]:
# build clay robot
frontier.append(State(state.t_remaining-1,
ore-blueprint.costs[MineralType.CLAY.value][MineralType.ORE.value]+ore_r,
clay+clay_r,
obs+obs_r,
state.geode+state.geode_r,
ore_r, clay_r+1, obs_r, state.geode_r))
if (ore >= blueprint.costs[MineralType.OBSIDIAN.value][MineralType.ORE.value]
and clay>=blueprint.costs[MineralType.OBSIDIAN.value][MineralType.CLAY.value]):
# build obsidian robot
frontier.append(State(state.t_remaining-1,
ore-blueprint.costs[MineralType.OBSIDIAN.value][MineralType.ORE.value]+ore_r,
clay-blueprint.costs[MineralType.OBSIDIAN.value][MineralType.CLAY.value]+clay_r,
obs+obs_r,
state.geode+state.geode_r,
ore_r, clay_r, obs_r+1, state.geode_r))
if (ore >= blueprint.costs[MineralType.GEODE.value][MineralType.ORE.value]
and obs>=blueprint.costs[MineralType.GEODE.value][MineralType.OBSIDIAN.value]):
# build geode robot
frontier.append(State(state.t_remaining-1,
ore-blueprint.costs[MineralType.GEODE.value][MineralType.ORE.value]+ore_r,
clay+clay_r,
obs-blueprint.costs[MineralType.GEODE.value][MineralType.OBSIDIAN.value]+obs_r,
state.geode+state.geode_r,
ore_r, clay_r, obs_r, state.geode_r+1))
return best
Note that I’ve included a couple of optimisations to reduce the solution space. I.e. to reduce the total number of valid states that can explored.
- If the number of any type of robot exceeds the maximum per minute spend rate of its corresponding mineral, then there’s no point in having that many robots. So, amend our state by reducing the number of this type of robot to match the maximum spend rate for this mineral.
- If we have more of a mineral than we can possibly spend in the time that is remaining, then there’s no point in having this excess mineral. So, amend our state by reducing the mineral amount to match the maximum we could theoretically spend in the time remaining.
With each state we explore, we get the current number of geodes, and check if it’s the most geodes so far. If it is, we store it. Ultimately, we return this number. So now we have a maximum number of geodes that we can obtain in 24 minutes, per blueprint. We can therefore calculate our quality levels for each blueprint, and provide the answer to Part 1:
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
blueprints = parse_data(data)
quality_level = 0
geode_product = 1
for blueprint in blueprints:
print(blueprint)
geodes = bfs(blueprint, State(24))
quality_level += geodes * blueprint.id
print(f"Part 1={quality_level}")
Part 2
We’re told we now have more time. We now have 32 minutes instead of 24.
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?
We don’t care about quality level anymore.
Basically, we can just run the same BFS as we did before, but with a longer timer. Because we’ve got more time, the solution space is a lot larger, so it takes a lot longer to complete the BFS for each blueprint. Fortunately, we only have to do this for the first three blueprints.
Very little code needs to change. All I’ve done is added a check to find out if the current blueprint is in the first three, and if it is, I’ve run a BFS with 32:
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
blueprints = parse_data(data)
quality_level = 0
geode_product = 1
for blueprint in blueprints:
print(blueprint)
geodes = bfs(blueprint, State(24))
quality_level += geodes * blueprint.id
if blueprint.id <= 3: # First three blueprints; they start at 1
geodes = bfs(blueprint, State(32)) # These take a while!
geode_product *= geodes
print(f"Part 1={quality_level}")
print(f"Part 2={geode_product}")
Results
The final code looks like this:
from dataclasses import dataclass
from enum import Enum
from pathlib import Path
from collections import deque
import re
import time
SCRIPT_DIR = Path(__file__).parent
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
class MineralType(Enum):
""" Enumerate mineral / robot types """
ORE = "ore"
CLAY = "clay"
OBSIDIAN = "obsidian"
GEODE = "geode"
@dataclass(frozen=True)
class Blueprint():
""" Store blueprint ID, with a dict for each robot type, that in turn contains a nested dict
of all mineral costs for that robot. """
id: int
costs: dict # { "ore": {"ore": 4}, "obsidian": {"ore": 3, clay: 14}, ...}
def get_max_cost(self, mineral: MineralType):
""" Return the maximum cost of a given mineral type for all robots in this blueprint. """
# If this robot does not contain a given mineral in the blueprint, return 0 for this mineral
return max([self.costs[MineralType.ORE.value].get(mineral.value, 0),
self.costs[MineralType.CLAY.value].get(mineral.value, 0),
self.costs[MineralType.OBSIDIAN.value].get(mineral.value, 0),
self.costs[MineralType.GEODE.value].get(mineral.value, 0)])
@dataclass(frozen=True)
class State():
t_remaining: int
ore: int = 0
clay: int = 0
obsidian: int = 0
geode: int = 0
ore_r: int = 1
clay_r: int = 0
obsidian_r: int = 0
geode_r: int = 0
def bfs(blueprint: Blueprint, state: State):
best = 0
frontier = deque([state])
explored = set()
max_ore_cost = blueprint.get_max_cost(MineralType.ORE)
max_clay_cost = blueprint.get_max_cost(MineralType.CLAY)
max_obsidian_cost = blueprint.get_max_cost(MineralType.OBSIDIAN)
while frontier:
state = frontier.popleft() # popleft for BFS; pop for DFS
best = max(best, state.geode)
if state.t_remaining == 0:
continue
# Optimise state space by throwing away robots we can't use
# E.g. if the highest per minute ore cost is 4, then there's no point having more than 4 ore robots.
ore_r = min(state.ore_r, max_ore_cost)
clay_r = min(state.clay_r, max_clay_cost)
obs_r = min(state.obsidian_r, max_obsidian_cost)
# optimise state space by throwing away resources we can't possibly spend in the time we have left.
# E.g. if t=10 and max ore cost is 4, then we can only spend a max of 40 ore.
# So if we have more than 40, throw it away.
# Of course, we can't throw away any geodes!
ore = min(state.ore, state.t_remaining * max_ore_cost - ore_r*(state.t_remaining-1))
clay = min(state.clay, state.t_remaining * max_clay_cost - clay_r*(state.t_remaining-1))
obs = min(state.obsidian, state.t_remaining * max_obsidian_cost - obs_r*(state.t_remaining-1))
# If our optimisations are applicable, amend our state to reflect the optimised state.
# Thus, fewer overall states to explore.
state = State(state.t_remaining,
ore, clay, obs, state.geode,
ore_r, clay_r, obs_r, state.geode_r)
if state in explored:
continue
explored.add(state)
# Now add each possible next state to the frontier...
# 1st option: Don't make any robots; just accumulate.
# New mineral levels are simply old levels + number of each robot type
frontier.append(State(state.t_remaining-1,
ore+ore_r,
clay+clay_r,
obs+obs_r,
state.geode+state.geode_r,
ore_r, clay_r, obs_r, state.geode_r))
# Remaining options: build one of each bot, if we can
if ore >= blueprint.costs[MineralType.ORE.value].get(MineralType.ORE.value, 0):
# build ore robot
frontier.append(State(state.t_remaining-1,
ore-blueprint.costs[MineralType.ORE.value][MineralType.ORE.value]+ore_r,
clay+clay_r,
obs+obs_r,
state.geode+state.geode_r,
ore_r+1, clay_r, obs_r, state.geode_r))
if ore >= blueprint.costs[MineralType.CLAY.value][MineralType.ORE.value]:
# build clay robot
frontier.append(State(state.t_remaining-1,
ore-blueprint.costs[MineralType.CLAY.value][MineralType.ORE.value]+ore_r,
clay+clay_r,
obs+obs_r,
state.geode+state.geode_r,
ore_r, clay_r+1, obs_r, state.geode_r))
if (ore >= blueprint.costs[MineralType.OBSIDIAN.value][MineralType.ORE.value]
and clay>=blueprint.costs[MineralType.OBSIDIAN.value][MineralType.CLAY.value]):
# build obsidian robot
frontier.append(State(state.t_remaining-1,
ore-blueprint.costs[MineralType.OBSIDIAN.value][MineralType.ORE.value]+ore_r,
clay-blueprint.costs[MineralType.OBSIDIAN.value][MineralType.CLAY.value]+clay_r,
obs+obs_r,
state.geode+state.geode_r,
ore_r, clay_r, obs_r+1, state.geode_r))
if (ore >= blueprint.costs[MineralType.GEODE.value][MineralType.ORE.value]
and obs>=blueprint.costs[MineralType.GEODE.value][MineralType.OBSIDIAN.value]):
# build geode robot
frontier.append(State(state.t_remaining-1,
ore-blueprint.costs[MineralType.GEODE.value][MineralType.ORE.value]+ore_r,
clay+clay_r,
obs-blueprint.costs[MineralType.GEODE.value][MineralType.OBSIDIAN.value]+obs_r,
state.geode+state.geode_r,
ore_r, clay_r, obs_r, state.geode_r+1))
return best
def parse_data(data: list[str]) -> list[Blueprint]:
""" Read the input and return a list of Blueprint """
pattern = re.compile(r"Each (\w+) robot costs (\d+) (\w+)(?: and (\d+) (\w+))*.")
blueprints = []
for line in data:
blueprint_id = int(line.split(":")[0].split()[-1])
costs = {}
for matches in pattern.findall(line):
robot = matches[0]
minerals = {}
for i in range(2, len(matches) + 1, 2):
if matches[i]: # if not empty
minerals[matches[i]] = int(matches[i-1])
costs[robot] = minerals
# costs = costs.set(robot, minerals)
# costs = frozendict({k:v for k,v in costs.items()})
blueprints.append(Blueprint(blueprint_id, costs))
return blueprints
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
blueprints = parse_data(data)
quality_level = 0
geode_product = 1
for blueprint in blueprints:
print(blueprint)
geodes = bfs(blueprint, State(24))
quality_level += geodes * blueprint.id
if blueprint.id <= 3: # First three blueprints; they start at 1
geodes = bfs(blueprint, State(32)) # These take a while!
geode_product *= geodes
print(f"Part 1={quality_level}")
print(f"Part 2={geode_product}")
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
Output:
Blueprint(id=1, costs={'ore': {'ore': 3}, 'clay': {'ore': 3}, 'obsidian': {'ore': 3, 'clay': 15}, 'geode': {'ore': 2, 'obsidian': 8}})
Blueprint(id=2, costs={'ore': {'ore': 2}, 'clay': {'ore': 3}, 'obsidian': {'ore': 3, 'clay': 17}, 'geode': {'ore': 3, 'obsidian': 10}})
Blueprint(id=3, costs={'ore': {'ore': 2}, 'clay': {'ore': 2}, 'obsidian': {'ore': 2, 'clay': 20}, 'geode': {'ore': 2, 'obsidian': 14}})
Blueprint(id=4, costs={'ore': {'ore': 4}, 'clay': {'ore': 4}, 'obsidian': {'ore': 3, 'clay': 14}, 'geode': {'ore': 4, 'obsidian': 15}})
Blueprint(id=5, costs={'ore': {'ore': 2}, 'clay': {'ore': 3}, 'obsidian': {'ore': 3, 'clay': 13}, 'geode': {'ore': 3, 'obsidian': 15}})
Blueprint(id=6, costs={'ore': {'ore': 2}, 'clay': {'ore': 2}, 'obsidian': {'ore': 2, 'clay': 15}, 'geode': {'ore': 2, 'obsidian': 7}})
Blueprint(id=7, costs={'ore': {'ore': 3}, 'clay': {'ore': 3}, 'obsidian': {'ore': 3, 'clay': 9}, 'geode': {'ore': 3, 'obsidian': 7}})
Blueprint(id=8, costs={'ore': {'ore': 4}, 'clay': {'ore': 2}, 'obsidian': {'ore': 2, 'clay': 16}, 'geode': {'ore': 2, 'obsidian': 8}})
Blueprint(id=9, costs={'ore': {'ore': 2}, 'clay': {'ore': 4}, 'obsidian': {'ore': 4, 'clay': 20}, 'geode': {'ore': 4, 'obsidian': 18}})
Blueprint(id=10, costs={'ore': {'ore': 3}, 'clay': {'ore': 3}, 'obsidian': {'ore': 2, 'clay': 11}, 'geode': {'ore': 2, 'obsidian': 19}})
Blueprint(id=11, costs={'ore': {'ore': 4}, 'clay': {'ore': 4}, 'obsidian': {'ore': 2, 'clay': 7}, 'geode': {'ore': 3, 'obsidian': 10}})
Blueprint(id=12, costs={'ore': {'ore': 2}, 'clay': {'ore': 3}, 'obsidian': {'ore': 3, 'clay': 11}, 'geode': {'ore': 2, 'obsidian': 16}})
Blueprint(id=13, costs={'ore': {'ore': 3}, 'clay': {'ore': 4}, 'obsidian': {'ore': 4, 'clay': 16}, 'geode': {'ore': 3, 'obsidian': 15}})
Blueprint(id=14, costs={'ore': {'ore': 4}, 'clay': {'ore': 3}, 'obsidian': {'ore': 4, 'clay': 18}, 'geode': {'ore': 3, 'obsidian': 13}})
Blueprint(id=15, costs={'ore': {'ore': 2}, 'clay': {'ore': 3}, 'obsidian': {'ore': 3, 'clay': 13}, 'geode': {'ore': 2, 'obsidian': 20}})
Blueprint(id=16, costs={'ore': {'ore': 3}, 'clay': {'ore': 4}, 'obsidian': {'ore': 4, 'clay': 14}, 'geode': {'ore': 4, 'obsidian': 10}})
Blueprint(id=17, costs={'ore': {'ore': 4}, 'clay': {'ore': 3}, 'obsidian': {'ore': 2, 'clay': 17}, 'geode': {'ore': 3, 'obsidian': 16}})
Blueprint(id=18, costs={'ore': {'ore': 2}, 'clay': {'ore': 4}, 'obsidian': {'ore': 3, 'clay': 20}, 'geode': {'ore': 2, 'obsidian': 17}})
Blueprint(id=19, costs={'ore': {'ore': 2}, 'clay': {'ore': 4}, 'obsidian': {'ore': 2, 'clay': 16}, 'geode': {'ore': 4, 'obsidian': 12}})
Blueprint(id=20, costs={'ore': {'ore': 3}, 'clay': {'ore': 3}, 'obsidian': {'ore': 3, 'clay': 16}, 'geode': {'ore': 3, 'obsidian': 20}})
Blueprint(id=21, costs={'ore': {'ore': 3}, 'clay': {'ore': 4}, 'obsidian': {'ore': 4, 'clay': 18}, 'geode': {'ore': 4, 'obsidian': 12}})
Blueprint(id=22, costs={'ore': {'ore': 3}, 'clay': {'ore': 4}, 'obsidian': {'ore': 3, 'clay': 13}, 'geode': {'ore': 3, 'obsidian': 19}})
Blueprint(id=23, costs={'ore': {'ore': 3}, 'clay': {'ore': 4}, 'obsidian': {'ore': 4, 'clay': 18}, 'geode': {'ore': 3, 'obsidian': 8}})
Blueprint(id=24, costs={'ore': {'ore': 4}, 'clay': {'ore': 3}, 'obsidian': {'ore': 2, 'clay': 13}, 'geode': {'ore': 2, 'obsidian': 9}})
Blueprint(id=25, costs={'ore': {'ore': 4}, 'clay': {'ore': 4}, 'obsidian': {'ore': 4, 'clay': 5}, 'geode': {'ore': 3, 'obsidian': 15}})
Blueprint(id=26, costs={'ore': {'ore': 4}, 'clay': {'ore': 4}, 'obsidian': {'ore': 2, 'clay': 15}, 'geode': {'ore': 3, 'obsidian': 16}})
Blueprint(id=27, costs={'ore': {'ore': 3}, 'clay': {'ore': 4}, 'obsidian': {'ore': 4, 'clay': 20}, 'geode': {'ore': 4, 'obsidian': 16}})
Blueprint(id=28, costs={'ore': {'ore': 4}, 'clay': {'ore': 3}, 'obsidian': {'ore': 4, 'clay': 8}, 'geode': {'ore': 2, 'obsidian': 8}})
Blueprint(id=29, costs={'ore': {'ore': 4}, 'clay': {'ore': 4}, 'obsidian': {'ore': 2, 'clay': 14}, 'geode': {'ore': 4, 'obsidian': 19}})
Blueprint(id=30, costs={'ore': {'ore': 3}, 'clay': {'ore': 4}, 'obsidian': {'ore': 3, 'clay': 10}, 'geode': {'ore': 2, 'obsidian': 7}})
Part 1=1177
Part 2=62744
Execution time: 261.0272 seconds
This is pretty slow. Over 4 minutes. But it works. It probably needs some more work!