diff options
| -rw-r--r-- | aoc-2020-gleam/src/aoc_2020_gleam.gleam | 2 | ||||
| -rw-r--r-- | aoc-2020-gleam/src/days/day07.gleam | 2 | ||||
| -rw-r--r-- | aoc-2020-gleam/src/days/day08.gleam | 158 | ||||
| -rw-r--r-- | aoc-2020-gleam/src/ext/listx.gleam | 12 | ||||
| -rw-r--r-- | aoc-2020-gleam/src/util/parser.gleam | 9 |
5 files changed, 179 insertions, 4 deletions
diff --git a/aoc-2020-gleam/src/aoc_2020_gleam.gleam b/aoc-2020-gleam/src/aoc_2020_gleam.gleam index a4f5902..25b59d7 100644 --- a/aoc-2020-gleam/src/aoc_2020_gleam.gleam +++ b/aoc-2020-gleam/src/aoc_2020_gleam.gleam @@ -7,6 +7,7 @@ import days/day04 import days/day05 import days/day06 import days/day07 +import days/day08 pub fn main() -> Nil { use day <- runner.with_day() @@ -18,6 +19,7 @@ pub fn main() -> Nil { 5 -> day05.run() 6 -> day06.run() 7 -> day07.run() + 8 -> day08.run() _ -> io.println("Day not found!") } } diff --git a/aoc-2020-gleam/src/days/day07.gleam b/aoc-2020-gleam/src/days/day07.gleam index 8569956..0b0a8e8 100644 --- a/aoc-2020-gleam/src/days/day07.gleam +++ b/aoc-2020-gleam/src/days/day07.gleam @@ -43,7 +43,7 @@ fn parse_graph(lines: List(String)) -> BagGraph { |> p.skip(p.then(p.literal("bag"), p.opt(p.literal("s")))) |> p.sep1(by: p.literal(", ")), else: p.literal("no other bags") - |> p.map(fun.constant([])), + |> p.replace(with: []), )) |> p.skip(p.literal(".")) diff --git a/aoc-2020-gleam/src/days/day08.gleam b/aoc-2020-gleam/src/days/day08.gleam new file mode 100644 index 0000000..0501162 --- /dev/null +++ b/aoc-2020-gleam/src/days/day08.gleam @@ -0,0 +1,158 @@ +import gleam/io +import gleam/list +import gleam/set.{Set} +import gleam/iterator.{Iterator} as iter +import gleam/option.{None, Option, Some} as opt +import ext/listx +import ext/resultx as resx +import util/input_util +import util/parser as p + +type Instr { + Acc(increment: Int) + Jmp(offset: Int) + Nop(unused: Int) +} + +type Program = + List(Instr) + +type Cpu { + Cpu(acc: Int, pc: Int) +} + +const initial_cpu = Cpu(acc: 0, pc: 0) + +type ExecutionResult { + InfiniteLoop(acc_before_second: Int) + Termination(acc_after: Int) +} + +fn parse_program(lines: List(String)) -> Program { + let argument_parser = + p.any(of: [ + p.replace(p.literal("+"), with: 1), + p.replace(p.literal("-"), with: -1), + ]) + |> p.then(p.int()) + |> p.map2(with: fn(sign, magnitude) { sign * magnitude }) + + let instr_parser = + p.any(of: [ + p.literal("acc ") + |> p.proceed(with: argument_parser) + |> p.map(with: Acc), + p.literal("jmp ") + |> p.proceed(with: argument_parser) + |> p.map(with: Jmp), + p.literal("nop ") + |> p.proceed(with: argument_parser) + |> p.map(with: Nop), + ]) + + lines + |> list.map(with: fn(line) { + line + |> p.parse_entire(with: instr_parser) + |> resx.assert_unwrap + }) +} + +fn fetch(from program: Program, with cpu: Cpu) -> Option(Instr) { + program + |> list.at(cpu.pc) + |> opt.from_result +} + +fn execute(instr: Instr, on cpu: Cpu) -> Cpu { + case instr { + Acc(increment) -> Cpu(cpu.acc + increment, cpu.pc + 1) + Jmp(offset) -> Cpu(cpu.acc, cpu.pc + offset) + Nop(_) -> Cpu(cpu.acc, cpu.pc + 1) + } +} + +fn execution_result_helper( + program: Program, + cpu: Cpu, + visited: Set(Int), +) -> ExecutionResult { + case set.contains(visited, cpu.pc), fetch(from: program, with: cpu) { + True, _ -> InfiniteLoop(acc_before_second: cpu.acc) + _, None -> Termination(acc_after: cpu.acc) + _, Some(instr) -> + execution_result_helper( + program, + execute(instr, on: cpu), + set.insert(visited, cpu.pc), + ) + } +} + +fn execution_result(program: Program) -> ExecutionResult { + execution_result_helper(program, initial_cpu, set.new()) +} + +fn halts(program: Program) -> Bool { + case execution_result(program) { + Termination(_) -> True + _ -> False + } +} + +fn all_program_mutations(of program: Program) -> Iterator(Program) { + let undo_corruption = fn(instr) { + case instr { + Nop(offset) -> Jmp(offset) + Jmp(unused) -> Nop(unused) + other -> other + } + } + + program + |> iter.from_list + |> iter.index + |> iter.flat_map(fn(elem) { + let #(index, instr) = elem + case instr { + Acc(_) -> iter.empty() + _ -> + program + |> listx.set(undo_corruption(instr), at: index) + |> iter.single + } + }) +} + +fn part1(lines: List(String)) -> Int { + assert InfiniteLoop(acc) = + lines + |> parse_program + |> execution_result + + acc +} + +fn part2(lines: List(String)) -> Int { + assert Termination(acc) = + lines + |> parse_program + |> all_program_mutations + |> iter.find(one_that: halts) + |> resx.assert_unwrap + |> execution_result + + acc +} + +pub fn run() -> Nil { + let test = input_util.read_lines("test08") + assert 5 = part1(test) + assert 8 = part2(test) + + let input = input_util.read_lines("day08") + io.debug(part1(input)) + io.debug(part2(input)) + + Nil +} diff --git a/aoc-2020-gleam/src/ext/listx.gleam b/aoc-2020-gleam/src/ext/listx.gleam index bead987..2d4f4b6 100644 --- a/aoc-2020-gleam/src/ext/listx.gleam +++ b/aoc-2020-gleam/src/ext/listx.gleam @@ -6,3 +6,15 @@ pub fn count(list: List(a), satisfying predicate: fn(a) -> Bool) -> Int { |> iter.from_list |> iterx.count(satisfying: predicate) } + +fn set_helper(list: List(a), value: a, index: Int, counter: Int) -> List(a) { + case list { + [] -> [] + [_, ..t] if counter == index -> [value, ..t] + [h, ..t] -> [h, ..set_helper(t, value, index, counter + 1)] + } +} + +pub fn set(list: List(a), value: a, at index: Int) -> List(a) { + set_helper(list, value, index, 0) +} diff --git a/aoc-2020-gleam/src/util/parser.gleam b/aoc-2020-gleam/src/util/parser.gleam index d5fa429..1ca2447 100644 --- a/aoc-2020-gleam/src/util/parser.gleam +++ b/aoc-2020-gleam/src/util/parser.gleam @@ -140,9 +140,12 @@ pub fn skip_ws(after parser: Parser(a)) -> Parser(a) { |> skip(ws0()) } +pub fn replace(parser: Parser(a), with value: b) -> Parser(b) { + map(parser, with: fun.constant(value)) +} + pub fn ignore(parser: Parser(a)) -> Parser(Nil) { - parser - |> map(fun.constant(Nil)) + replace(parser, with: Nil) } pub fn then(first: Parser(a), second: Parser(b)) -> Parser(#(a, b)) { @@ -162,7 +165,7 @@ pub fn skip(first: Parser(a), second: Parser(b)) -> Parser(a) { |> map(with: pair.first) } -pub fn proceed(first: Parser(a), second: Parser(b)) -> Parser(b) { +pub fn proceed(first: Parser(a), with second: Parser(b)) -> Parser(b) { first |> then(second) |> map(with: pair.second) |