Day 21 - Advent of Code 2022

Mix.install([:kino, :benchee])

:ok

Links

• Advent of Code (AoC)
• AoC Puzzle Input
• tylerj GitHub - Code
• tylerj GitHub - Livebook

Prompt

--- Day 21: Monkey Math ---

The monkeys are back! You're worried they're going to try to steal your stuff again, but it seems like they're just holding their ground and making various monkey noises at you.

Eventually, one of the elephants realizes you don't speak monkey and comes over to interpret. As it turns out, they overheard you talking about trying to find the grove; they can show you a shortcut if you answer their riddle.

Each monkey is given a job: either to yell a specific number or to yell the result of a math operation. All of the number-yelling monkeys know their number from the start; however, the math operation monkeys need to wait for two other monkeys to yell a number, and those two other monkeys might also be waiting on other monkeys.

Your job is to work out the number the monkey named root will yell before the monkeys figure it out themselves.

For example:

root: pppw + sjmn
dbpl: 5
cczh: sllz + lgvd
zczc: 2
ptdq: humn - dvpt
dvpt: 3
lfqf: 4
humn: 5
ljgn: 2
sjmn: drzm * dbpl
sllz: 4
pppw: cczh / lfqf
lgvd: ljgn * ptdq
drzm: hmdt - zczc
hmdt: 32

Each line contains the name of a monkey, a colon, and then the job of that monkey:

• A lone number means the monkey's job is simply to yell that number.
• A job like aaaa + bbbb means the monkey waits for monkeys aaaa and bbbb to yell each of their numbers; the monkey then yells the sum of those two numbers.
• aaaa - bbbb means the monkey yells aaaa's number minus bbbb's number.
• Job aaaa * bbbb will yell aaaa's number multiplied by bbbb's number.
• Job aaaa / bbbb will yell aaaa's number divided by bbbb's number.

So, in the above example, monkey drzm has to wait for monkeys hmdt and zczc to yell their numbers. Fortunately, both hmdt and zczc have jobs that involve simply yelling a single number, so they do this immediately: 32 and 2. Monkey drzm can then yell its number by finding 32 minus 2: 30.

Then, monkey sjmn has one of its numbers (30, from monkey drzm), and already has its other number, 5, from dbpl. This allows it to yell its own number by finding 30 multiplied by 5: 150.

This process continues until root yells a number: 152.

However, your actual situation involves considerably more monkeys. What number will the monkey named root yell?

To begin, get your puzzle input.

--- Part Two ---

Due to some kind of monkey-elephant-human mistranslation, you seem to have misunderstood a few key details about the riddle.

First, you got the wrong job for the monkey named root; specifically, you got the wrong math operation. The correct operation for monkey root should be =, which means that it still listens for two numbers (from the same two monkeys as before), but now checks that the two numbers match.

Second, you got the wrong monkey for the job starting with humn:. It isn't a monkey - it's you. Actually, you got the job wrong, too: you need to figure out what number you need to yell so that root's equality check passes. (The number that appears after humn: in your input is now irrelevant.)

In the above example, the number you need to yell to pass root's equality test is 301. (This causes root to get the same number, 150, from both of its monkeys.)

What number do you yell to pass root's equality test?

Although it hasn't changed, you can still get your puzzle input.

Input

input = Kino.Input.textarea("Please paste your input file:")

input = input |> Kino.Input.read()

"jqtt: tnwg * mbnq\nvsww: jmrn + twmm\nppws: qtfb * rdsp\nljqm: 14\nbsvb: tbqb - fqqm\nwfpq: hgdp * ddvm\njhtm: 2\nslnm: rrtr * lhwh\nlgzs: jtrw * dfmw\nrmwf: pmsv - llsm\nprzw: bqwv + ghcz\nrqwg: 6\npsrl: 4\njddv: plnt * gcfc\nvtbv: rwmn + zcwm\nhgtf: qrlv + brzm\nhhlf: 2\nqnwv: vhwb + thlf\nsbwr: ppws * rlvq\ncpld: gwmj + rhcd\nnnmv: gjsm * jrpf\nltft: rfvj * cttp\nsjzd: 2\nfnnl: rpmq * zgms\nthmv: 3\nslsp: 5\nqnhh: crqv + hdgl\nlzmd: 2\ncfjz: 18\nnftb: 3\nwndb: ztgl * cwnt\nbjbh: hhnq + wchj\nhcsl: sbtp + wrnf\nwljw: wrmd / ffct\nfctr: 2\nwnmz: 17\nmhfl: 3\ncrfw: sdvt * gvrz\nvqdv: 3\nzswr: 4\ntbgc: hqzm * qtsc\nbcmz: jqbf + vchc\nfltj: jlgw / prsv\npnbd: 2\nvqcc: 3\npdhb: 11\nmssc: hjbb * zzsf\nfbcp: pfhh + fhbm\nqjlj: 2\nbwmp: gwqd + zttp\nqqnm: fftd * mbst\nrmwh: tcnh - pcmh\nssrc: 2\ntlhm: tjfv + zpsf\nrnbd: jjvt + hmzp\ngbwn: cvlv + djwh\npfpd: 4\nnfvs: cpmc + vzhf\nssts: 3\nhvbh: 3\nfnwt: shzp * thgj\nbwjj: wfnf * dtqb\ndvll: 1\nrjtf: 3\ngtrh: lcqd + prrn\npbqm: 1\nnlrm: 5\ndftz: mzng * tncp\nrlsl: ppmh / pvnb\nhhgf: dwnr * qbrj\nlddg: tbzq * ncwd\npclv: qqnt - gcqz\nblhb: rnzq + mhqz\ndrnr: zlhg + mvcq\nhgwl: jqtl + wzsr\nzswf: blqr * lvsb\nfdbt: pwfs * gnhq\nfwlm: 1\nwpzv: 3\ncdwp: gfhs + wtbp\nhzch: fdbd + nrth\npdsl: 3\nphql: hbmw * wrlt\nztvt: 1\nfgfp: 13\nwfjt: 3\nwrmd: fhrp * jrdr\ncldc: fmgr + cdjg\nvfvb: zlgm - stzg\nqfrh: hbhc * gnhc\njrdr: 2\nfcdv: 3\nhjjp: cvmd * qnjb\nftmr: qtbj + gnfr\ngqfw: 3\nzgzh: phsj + jzrn\ncqvn: 7\nbbhr: jdbt * ccrh\nvrvs: 5\nrlvz: pwvl * lczp\nsmhn: 2\nrzhg: 6\nqbmc: 3\nwtvv: 4\nnqnb: 4\nzshh: ngfn + ljqm\nrpph: hbwt * fwfh\nlqqw: grqf * jwfc\njwgt: lwjj * fsfh\nwqmw: 4\nnzjs: 2\ngcvc: 2\npwvl: 16\ngwqd: 10\nprrn: 4\nbtrp: 5\nmpjh: 2\nfbcl: 2\nmwbr: 2\nlcgw: zpmm + lwfw\ndlsw: 1\nvwtr: rgsj / vfcg\nvhjq: wrvz * dmzh\nmdvc: 5\nsldj: 5\nfwpv: 11\npvqb: qwdt + srzd\nptqg: 12\nchzc: 2\nvfsz: 3\nhjlt: mrgj * ffdp\nmvtd: 5\njldc: dvvw * zbwz\nbsft: 2\nsvsd: 9\nqcbl: fztd * cpld\nhjzq: 3\nctmh: 2\ncnss: 2\nzqrj: mhhq * fjfc\njsgj: 5\nqrmb: 7\nnszq: rdhf * zstr\nmgsm: 5\nzmhz: cglq * cttz\nmsjt: 3\nczrh: cvbr / djtb\nlslt: grfq / hsgj\nnfcm: 3\nncsj: 14\nvgjt: 3\nldzh: 4\nlzdj: 8\nglrq: 5\ncjjr: 11\ndnwc: 8\npldf: vcdj * chzc\nrfwr: rqcp * qpwg\nzblf: 2\nswbp: wggc + qcnf\nhcjq: jfft * hhll\nfjlz: vjdq + dzsp\nzswq: wbmt + scrh\ntzrc: fflf + mpbq\nzsjl: jmdd * mpwj\ntmwj: 4\njfvd: 3\njqzf: 2\nhtzv: tlps + sjjp\ngmwm: 7\nqbrj: 2\ncmdr: lswp * lljh\nrtpp: 1\nqrdg: slst + bbrq\nhqzm: 2\nvdsw: 3\nhzhv: 6\nhumn: 927\ndzsp: 5\nlpsb: 5\njqcq: 5\nmvcq: 12\ncfhv: 2\nqrrf: vqvn - wprq\nmznq: sfjb * hvtd\nbzfw: 4\nnctp: 4\nbzjg: hcnm + jtbm\ngppp: fnfn * qqnm\nghzf: szlh * bgcc\nrfls: gjnf / hffp\nnfjz: 4\npqzg: 4\nfrhd: twtc * rrmn\nmvds: 1\nhqlh: pwvn * qtvf\nwfgr: twsv * tntz\nmfsl: dlsw + hlmh\nlzlf: szvt + qwcz\ncgwz: 14\nwvjb: 4\nhsnr: 4\ndhdl: hmcr * lscn\nqmwp: cbdg * mplg\njfft: qjfq + vzpv\ntttw: 6\nqcsp: 12\ncmtc: qtrv * fcfl\nzttp: jnbr * sldj\ncnrm: 3\nmqtj: nhhv * bsdz\ntwmm: mhbm * ltwj\nvphb: fcdv * wgpg\nrcpt: 2\nsglw: wplj + ffmd\ngwqw: pntz - dwzg\nbwdq: 3\ngjdr: mpqg + qsvs\nmgtw: ddgp + cqlr\ncgzf: 4\nvmpw: btrp + wlhb\ncvbn: 4\njcsn: lntg * tmqv\npgdh: frmz + sqth\nfqbc: lgzs + zttz\nllpw: 8\nhbnz: 12\nzdll: 19\npbnr: 5\npzcv: 1\nwlwl: 2\nljcq: 6\nvwgp: 8\nthlf: 2\nmzqq: pgdh + rmch\ndhrn: 5\njbrv: mttw * rjhz\npbgz: 2\ntmnw: dfdq - ljmt\nssqj: 6\nsplf: nlzg / jvrb\npflc: 2\nssmt: rlwg + rppv\ngpwh: 3\nnncw: 11\nggzr: sqvs * ctcq\nvjcm: 2\nzdlm: nsrp - nptq\npwfb: 3\nglpb: 5\nccrm: ztzh * mjjv\ntpnw: smdm + zblf\nmnmm: 2\nprnd: mwvp / lddf\nchfq: sbzg * qqcw\ngtcw: drhz + hmqm\nlpwm: 4\nlnpt: lpcg - gvrg\nbmsr: cqrt + mqst\nhbsb: lztz * tmll\nvcrf: 4\nsjwd: 3\nmjdq: fcvf * ghzf\ndpng: qjvl * htzv\nlvsb: 4\nmsmz: zbvr * ndpr\ngzgd: jtvv + djmv\nftsd: 2\ntjfh: 2\njggn: cqsq * szrw\nvjzc: 5\ncvqj: fwlm + qpdm\nngzd: jdvr + hzld\ngdzl: 3\nsvvl: hcsl + tqvn\nldqv: ncqc * pvcl\nfgqr: nwsb - glnr\nrzmw: 4\nrzlb: 5\nmvtf: 7\ntsbg: tshn * lspr\nglmh: 4\nmwjj: lfgq + wqqz\nrmnq: vmpw + vwtr\nlfsd: 3\nwdnd: 2\njfps: 2\nwzmg: jznb + ntth\nlmnv: wmwb * hlgs\nzghz: scnm + jgpj\nwgjp: slnt + wccg\ncmnb: 2\ngjnf: jzzv * cfrs\nlfwr: cwht + bmsr\nqqcw: 2\nhmzn: gwjs * tqfv\nvvjt: ftmz + bzmt\nvdvv: 2\nwnmv: 4\nvgnz: 3\nfmgr: 4\nsqvc: dzzd + jrhp\njsgr: znft * lhcl\nlfcf: 5\ndhhr: rmwf + ffjt\nrcbh: tvdm + wccm\nlntg: cqpv / gghf\nvqqr: dgct + vnjw\ntjsp: 2\npnjw: 18\npvfm: 2\ntzsj: 2\nrcnm: 2\nzt" <> ...

Solution

defmodule Day21 do
  defdelegate parse(input), to: __MODULE__.Input

  def part1(input) do
    input
    |> parse()
    |> solve("root")
    |> trunc()
  end

  def part2(input) do
    input
    |> parse()
    |> Map.update!("root", fn {_, a, b} ->
      {:==, a, b}
    end)
    |> search(1, 0)
  end

  def solve(map, key) when is_binary(key), do: solve(map, map[key])
  def solve(_, num) when is_integer(num), do: num

  def solve(map, {:==, a, b}) do
    a = solve(map, a) |> trunc()
    b = solve(map, b) |> trunc()

    {a - b, a, b}
  end

  def solve(map, {op, a, b}),
    do: apply(Kernel, op, [solve(map, a), solve(map, b)])

  def search(map, base, exponent) do
    value = base * 10 ** exponent

    map
    |> Map.put("humn", value)
    |> solve("root")
    # |> then(fn {diff, _, _} = res ->
    #   IO.puts("DIFF: #{diff}, VALUE: #{value}")
    #   res
    # end)
    |> handle_result(map, base, exponent)
  end

  def handle_result({0, _, _}, _map, base, exp), do: base * 10 ** exp

  def handle_result({diff, _, _}, map, 1, 0) when diff < 0 do
    map
    |> Map.update!("root", fn {:==, a, b} -> {:==, b, a} end)
    |> search(1, 0)
  end

  def handle_result({diff, _, _}, map, 1, exp) when diff > 0 do
    search(map, 1, exp + 1)
  end

  def handle_result(_, map, 1, exp) do
    search(map, 2, exp - 1)
  end

  def handle_result({diff, _, _}, map, base, exp) when diff > 0 do
    search(map, base + 1, exp)
  end

  def handle_result(_, map, base, exp) do
    search(map, (base - 1) * 10 + 1, exp - 1)
  end

  defmodule Input do
    def parse(input) when is_binary(input) do
      input
      |> String.split("\n", trim: true)
      |> parse()
    end

    def parse(input) when is_list(input) do
      input
      |> Stream.map(&parse_line/1)
      |> Enum.into(%{})
    end

    def parse_line(line) do
      line
      |> String.split([": ", " "], trim: true)
      |> then(fn
        [name, number] -> {name, String.to_integer(number)}
        [name, a, op, b] -> {name, {String.to_atom(op), a, b}}
      end)
    end
  end
end

{:module, Day21, <<70, 79, 82, 49, 0, 0, 17, ...>>,
 {:module, Day21.Input, <<70, 79, 82, ...>>, {:parse_line, 1}}}

However, your actual situation involves considerably more monkeys. What number will the monkey named root yell?

Your puzzle answer was 110181395003396.

Day21.part1(input)

110181395003396

What number do you yell to pass root's equality test?

Your puzzle answer was 3721298272959.

NOTE: I initially manually performed a search, using this function and passing a value to manually set as humn, until I arrived at the correct answer. This involved starting with a random number like 1, and then increasing it significantly until it got closer to causing the two sides of this equation to match.

I just kept adding a zero to the end until the difference between the two numbers became negative (I went too far).

Then, I backed up (removed the last zero) and began increasing the most significant digit until it became too big (the difference was negative again).

I kept doing this until finally, while increasing the ones digit, I found the correct number that caused both sides of the equation to match.

I have since seen this referred to as a Hill climbing algorithm.

I was then able to replicate that process via the search/3 and handle_result/4 functions implemented above.

Day21.part2(input)

3721298272959

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, you should return to your Advent calendar and try another puzzle.

If you still want to see it, you can get your puzzle input.

Tests

ExUnit.start(auto_run: false)

defmodule Day21Test do
  use ExUnit.Case, async: false

  setup_all do
    [
      input:
        "root: pppw + sjmn\ndbpl: 5\ncczh: sllz + lgvd\nzczc: 2\nptdq: humn - dvpt\ndvpt: 3\nlfqf: 4\nhumn: 5\nljgn: 2\nsjmn: drzm * dbpl\nsllz: 4\npppw: cczh / lfqf\nlgvd: ljgn * ptdq\ndrzm: hmdt - zczc\nhmdt: 32"
    ]
  end

  describe "part1" do
    test "returns expected value", %{input: input} do
      assert Day21.part1(input) == 152
    end
  end

  describe "part2" do
    test "returns expected value", %{input: input} do
      assert Day21.part2(input) == 301
    end
  end
end

ExUnit.run()

..
Finished in 0.00 seconds (0.00s async, 0.00s sync)
2 tests, 0 failures

Randomized with seed 259734

%{excluded: 0, failures: 0, skipped: 0, total: 2}

Benchmarking

# https://github.com/bencheeorg/benchee

Benchee.run(%{
  "Part 1" => fn -> Day21.part1(input) end,
  "Part 2" => fn -> Day21.part2(input) end
})

nil

Operating System: macOS
CPU Information: Apple M1 Pro
Number of Available Cores: 10
Available memory: 16 GB
Elixir 1.14.2
Erlang 25.1.2

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 ns
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 14 s

Benchmarking Part 1 ...
Benchmarking Part 2 ...

Name             ips        average  deviation         median         99th %
Part 1        232.30        4.30 ms     ±2.44%        4.28 ms        4.51 ms
Part 2         36.91       27.09 ms     ±0.81%       27.09 ms       27.65 ms

Comparison: 
Part 1        232.30
Part 2         36.91 - 6.29x slower +22.79 ms

nil