From 5108ae09e37ff6c71a9d791ef70897c4b6791c42 Mon Sep 17 00:00:00 2001 From: HJ Date: Sun, 3 Dec 2023 01:59:44 -0500 Subject: day 3 complete --- aoc2023/src/day3/.gitignore | 1 + aoc2023/src/day3/solve.gleam | 192 ++++++++++++++++++++++++++++++++++++++ aoc2023/test/day3/day3_test.gleam | 66 +++++++++++++ 3 files changed, 259 insertions(+) create mode 100644 aoc2023/src/day3/.gitignore create mode 100644 aoc2023/src/day3/solve.gleam create mode 100644 aoc2023/test/day3/day3_test.gleam (limited to 'aoc2023') diff --git a/aoc2023/src/day3/.gitignore b/aoc2023/src/day3/.gitignore new file mode 100644 index 0000000..ae40cea --- /dev/null +++ b/aoc2023/src/day3/.gitignore @@ -0,0 +1 @@ +input.txt \ No newline at end of file diff --git a/aoc2023/src/day3/solve.gleam b/aoc2023/src/day3/solve.gleam new file mode 100644 index 0000000..5df337d --- /dev/null +++ b/aoc2023/src/day3/solve.gleam @@ -0,0 +1,192 @@ +import adglent.{First, Second} +import gleam/io +import gleam/dict.{type Dict} +import gleam/string +import gleam/list +import gleam/int +import gleam/order.{Eq} +import gleam/result + +type Coord { + Coord(x: Int, y: Int) +} + +type Symbol { + Number(Int) + Gear + OtherSymbol + Empty +} + +type Board = + Dict(Coord, Symbol) + +fn to_symbol(c: String) -> Symbol { + case int.parse(c), c { + Ok(n), _ -> Number(n) + Error(Nil), "." -> Empty + Error(Nil), "*" -> Gear + _, _ -> OtherSymbol + } +} + +fn to_board(input: String) -> Board { + { + use y, r <- list.index_map(string.split(input, "\n")) + use x, c <- list.index_map(string.to_graphemes(r)) + #(Coord(x, y), to_symbol(c)) + } + |> list.flatten() + |> dict.from_list() +} + +fn find_all_numbers(b: Board) { + b + |> dict.filter(fn(_, v) { + case v { + Number(_) -> True + _ -> False + } + }) + |> dict.to_list() + |> list.sort(fn(a, b) { + let #(Coord(x_a, y_a), _) = a + let #(Coord(x_b, y_b), _) = b + case int.compare(y_a, y_b) { + Eq -> int.compare(x_a, x_b) + other -> other + } + }) +} + +fn group_parts(ns, acc) { + case ns, acc { + [], _ -> acc + [#(Coord(x, y) as c, Number(n)), ..t], [ + #([Coord(x0, y0), ..] as cs, n0), + ..acc_rest + ] if y == y0 -> + case { x - 1 == x0 } { + True -> group_parts(t, [#([c, ..cs], n0 * 10 + n), ..acc_rest]) + False -> group_parts(t, [#([c], n), ..acc]) + } + [#(coord, Number(n)), ..t], _ -> group_parts(t, [#([coord], n), ..acc]) + } +} + +fn all_neighbors(c: Coord) -> List(Coord) { + let Coord(x, y) = c + use dx <- list.flat_map([-1, 0, 1]) + use dy <- list.filter_map([-1, 0, 1]) + case dx, dy { + 0, 0 -> Error(Nil) + _, _ -> Ok(Coord(x + dx, y + dy)) + } +} + +fn check_part_neighbors( + part: #(List(Coord), Int), + board: Board, +) -> Result(Int, Nil) { + let #(coords, n) = part + + let neighbors = + coords + |> list.flat_map(all_neighbors) + |> list.unique() + + case + list.any( + neighbors, + fn(c) { + let content = dict.get(board, c) + content == Ok(OtherSymbol) || content == Ok(Gear) + }, + ) + { + True -> Ok(n) + False -> Error(Nil) + } +} + +pub fn part1(input: String) { + let board = to_board(input) + + board + |> find_all_numbers + |> group_parts([]) + |> list.map(check_part_neighbors(_, board)) + |> result.values + |> int.sum +} + +fn find_gears(b: Board) { + dict.filter(b, fn(_, v) { v == Gear }) + |> dict.keys +} + +fn to_part_with_neighbors(part: #(List(Coord), Int)) { + let #(coords, n) = part + + let neighbors = + coords + |> list.flat_map(all_neighbors) + |> list.unique + |> list.filter(fn(c) { !list.contains(coords, c) }) + + #(neighbors, n) +} + +fn find_parts_near_gear(gear: Coord, parts: List(#(List(Coord), Int))) { + parts + |> list.filter_map(fn(part) { + let #(neighbors, n) = part + case list.contains(neighbors, gear) { + True -> Ok(n) + False -> Error(Nil) + } + }) +} + +fn keep_gears_near_two_parts(sets_of_parts: List(List(Int))) { + list.filter_map( + sets_of_parts, + fn(ps) { + case ps { + [p1, p2] -> Ok(p1 * p2) + _ -> Error(Nil) + } + }, + ) +} + +pub fn part2(input: String) { + let board = to_board(input) + + let parts = + board + |> find_all_numbers + |> group_parts([]) + |> list.map(to_part_with_neighbors) + + board + |> find_gears + |> list.map(find_parts_near_gear(_, parts)) + |> keep_gears_near_two_parts + |> int.sum +} + +pub fn main() { + let assert Ok(part) = adglent.get_part() + let assert Ok(input) = adglent.get_input("3") + case part { + First -> + part1(input) + |> adglent.inspect + |> io.println + Second -> + part2(input) + |> adglent.inspect + |> io.println + } +} diff --git a/aoc2023/test/day3/day3_test.gleam b/aoc2023/test/day3/day3_test.gleam new file mode 100644 index 0000000..30e17a9 --- /dev/null +++ b/aoc2023/test/day3/day3_test.gleam @@ -0,0 +1,66 @@ +import gleam/list +import showtime/tests/should +import adglent.{type Example, Example} +import day3/solve + +type Problem1AnswerType = + Int + +type Problem2AnswerType = + Int + +/// Add examples for part 1 here: +/// ```gleam +///const part1_examples: List(Example(Problem1AnswerType)) = [Example("some input", "")] +/// ``` +const part1_examples: List(Example(Problem1AnswerType)) = [ + Example( + "467..114.. +...*...... +..35..633. +......#... +617*...... +.....+.58. +..592..... +......755. +...$.*.... +.664.598..", + 4361, + ), +] + +/// Add examples for part 2 here: +/// ```gleam +///const part2_examples: List(Example(Problem2AnswerType)) = [Example("some input", "")] +/// ``` +const part2_examples: List(Example(Problem2AnswerType)) = [ + Example( + "467..114.. +...*...... +..35..633. +......#... +617*...... +.....+.58. +..592..... +......755. +...$.*.... +.664.598..", + 467_835, + ), +] + +pub fn part1_test() { + part1_examples + |> should.not_equal([]) + use example <- list.map(part1_examples) + solve.part1(example.input) + |> should.equal(example.answer) +} + +pub fn part2_test() { + part2_examples + |> should.not_equal([]) + use example <- list.map(part2_examples) + solve.part2(example.input) + |> should.equal(example.answer) +} -- cgit v1.2.3 From 05f0ca3e2c25fedbb9f924c6b79a839d087e04c8 Mon Sep 17 00:00:00 2001 From: HJ Date: Sun, 3 Dec 2023 02:15:48 -0500 Subject: day 3 complete --- aoc2023/src/day3/solve.gleam | 63 +++++++++++++++++--------------------------- 1 file changed, 24 insertions(+), 39 deletions(-) (limited to 'aoc2023') diff --git a/aoc2023/src/day3/solve.gleam b/aoc2023/src/day3/solve.gleam index 5df337d..9e0cd0d 100644 --- a/aoc2023/src/day3/solve.gleam +++ b/aoc2023/src/day3/solve.gleam @@ -11,10 +11,14 @@ type Coord { Coord(x: Int, y: Int) } +type PartKind { + Gear + SomethingElse +} + type Symbol { Number(Int) - Gear - OtherSymbol + Part(PartKind) Empty } @@ -25,8 +29,8 @@ fn to_symbol(c: String) -> Symbol { case int.parse(c), c { Ok(n), _ -> Number(n) Error(Nil), "." -> Empty - Error(Nil), "*" -> Gear - _, _ -> OtherSymbol + Error(Nil), "*" -> Part(Gear) + _, _ -> Part(SomethingElse) } } @@ -40,7 +44,7 @@ fn to_board(input: String) -> Board { |> dict.from_list() } -fn find_all_numbers(b: Board) { +fn find_all_parts(b: Board) { b |> dict.filter(fn(_, v) { case v { @@ -90,41 +94,25 @@ fn check_part_neighbors( ) -> Result(Int, Nil) { let #(coords, n) = part - let neighbors = - coords - |> list.flat_map(all_neighbors) - |> list.unique() - - case - list.any( - neighbors, - fn(c) { - let content = dict.get(board, c) - content == Ok(OtherSymbol) || content == Ok(Gear) - }, - ) - { - True -> Ok(n) - False -> Error(Nil) - } + coords + |> list.flat_map(all_neighbors) + |> list.unique() + |> list.map(dict.get(board, _)) + |> result.all() + |> result.replace(n) } pub fn part1(input: String) { let board = to_board(input) board - |> find_all_numbers + |> find_all_parts |> group_parts([]) |> list.map(check_part_neighbors(_, board)) |> result.values |> int.sum } -fn find_gears(b: Board) { - dict.filter(b, fn(_, v) { v == Gear }) - |> dict.keys -} - fn to_part_with_neighbors(part: #(List(Coord), Int)) { let #(coords, n) = part @@ -149,15 +137,11 @@ fn find_parts_near_gear(gear: Coord, parts: List(#(List(Coord), Int))) { } fn keep_gears_near_two_parts(sets_of_parts: List(List(Int))) { - list.filter_map( - sets_of_parts, - fn(ps) { - case ps { - [p1, p2] -> Ok(p1 * p2) - _ -> Error(Nil) - } - }, - ) + use ps <- list.filter_map(sets_of_parts) + case ps { + [p1, p2] -> Ok(p1 * p2) + _ -> Error(Nil) + } } pub fn part2(input: String) { @@ -165,12 +149,13 @@ pub fn part2(input: String) { let parts = board - |> find_all_numbers + |> find_all_parts |> group_parts([]) |> list.map(to_part_with_neighbors) board - |> find_gears + |> dict.filter(fn(_, v) { v == Part(Gear) }) + |> dict.keys |> list.map(find_parts_near_gear(_, parts)) |> keep_gears_near_two_parts |> int.sum -- cgit v1.2.3 From 9f0516bbc9a6f9f7128cbf8fd8774949ea32064b Mon Sep 17 00:00:00 2001 From: HJ Date: Sun, 3 Dec 2023 04:01:34 -0500 Subject: day 3 type changes --- aoc2023/src/day3/solve.gleam | 150 ++++++++++++++++++++++--------------------- 1 file changed, 78 insertions(+), 72 deletions(-) (limited to 'aoc2023') diff --git a/aoc2023/src/day3/solve.gleam b/aoc2023/src/day3/solve.gleam index 9e0cd0d..21acd26 100644 --- a/aoc2023/src/day3/solve.gleam +++ b/aoc2023/src/day3/solve.gleam @@ -4,33 +4,41 @@ import gleam/dict.{type Dict} import gleam/string import gleam/list import gleam/int -import gleam/order.{Eq} +import gleam/order.{type Order, Eq} import gleam/result type Coord { Coord(x: Int, y: Int) } -type PartKind { +type SymbolKind { Gear SomethingElse } type Symbol { Number(Int) - Part(PartKind) + Symbol(SymbolKind) Empty } type Board = Dict(Coord, Symbol) +type Cell { + Cell(coord: Coord, symbol: Symbol) +} + +type Part { + Part(coords: List(Coord), part_number: Int) +} + fn to_symbol(c: String) -> Symbol { case int.parse(c), c { Ok(n), _ -> Number(n) - Error(Nil), "." -> Empty - Error(Nil), "*" -> Part(Gear) - _, _ -> Part(SomethingElse) + _, "." -> Empty + _, "*" -> Symbol(Gear) + _, _ -> Symbol(SomethingElse) } } @@ -44,7 +52,14 @@ fn to_board(input: String) -> Board { |> dict.from_list() } -fn find_all_parts(b: Board) { +fn cell_compare(a: Cell, b: Cell) -> Order { + case int.compare(a.coord.y, b.coord.y) { + Eq -> int.compare(a.coord.x, b.coord.x) + other -> other + } +} + +fn find_all_part_digits(b: Board) -> List(Cell) { b |> dict.filter(fn(_, v) { case v { @@ -53,112 +68,103 @@ fn find_all_parts(b: Board) { } }) |> dict.to_list() - |> list.sort(fn(a, b) { - let #(Coord(x_a, y_a), _) = a - let #(Coord(x_b, y_b), _) = b - case int.compare(y_a, y_b) { - Eq -> int.compare(x_a, x_b) - other -> other - } - }) + |> list.map(fn(tup) { Cell(tup.0, tup.1) }) + |> list.sort(cell_compare) +} + +fn to_parts(cells: List(Cell)) -> List(Part) { + do_parts(cells, []) } -fn group_parts(ns, acc) { - case ns, acc { - [], _ -> acc - [#(Coord(x, y) as c, Number(n)), ..t], [ - #([Coord(x0, y0), ..] as cs, n0), - ..acc_rest - ] if y == y0 -> - case { x - 1 == x0 } { - True -> group_parts(t, [#([c, ..cs], n0 * 10 + n), ..acc_rest]) - False -> group_parts(t, [#([c], n), ..acc]) +fn do_parts(cells: List(Cell), parts: List(Part)) -> List(Part) { + case cells { + [] -> parts + [Cell(next, Number(n)), ..t] -> { + case parts { + [] -> do_parts(t, [Part([next], n), ..parts]) + [Part([prev, ..] as coords, n0), ..rest_parts] -> + case { next.x - prev.x }, { next.y - prev.y } { + 1, 0 -> + do_parts(t, [Part([next, ..coords], n0 * 10 + n), ..rest_parts]) + _, _ -> do_parts(t, [Part([next], n), ..parts]) + } } - [#(coord, Number(n)), ..t], _ -> group_parts(t, [#([coord], n), ..acc]) + } } } fn all_neighbors(c: Coord) -> List(Coord) { - let Coord(x, y) = c use dx <- list.flat_map([-1, 0, 1]) use dy <- list.filter_map([-1, 0, 1]) case dx, dy { 0, 0 -> Error(Nil) - _, _ -> Ok(Coord(x + dx, y + dy)) + _, _ -> Ok(Coord(c.x + dx, c.y + dy)) } } -fn check_part_neighbors( - part: #(List(Coord), Int), - board: Board, -) -> Result(Int, Nil) { - let #(coords, n) = part +fn check_part_neighbors(part: Part, board: Board) -> Result(Int, Nil) { + let neighbors = + part.coords + |> list.flat_map(all_neighbors) + |> list.unique() - coords - |> list.flat_map(all_neighbors) - |> list.unique() - |> list.map(dict.get(board, _)) - |> result.all() - |> result.replace(n) + let sym = [Ok(Symbol(Gear)), Ok(Symbol(SomethingElse))] + case list.any(neighbors, fn(c) { list.contains(sym, dict.get(board, c)) }) { + True -> Ok(part.part_number) + False -> Error(Nil) + } } -pub fn part1(input: String) { +pub fn part1(input: String) -> Int { let board = to_board(input) board - |> find_all_parts - |> group_parts([]) + |> find_all_part_digits + |> to_parts + |> io.debug |> list.map(check_part_neighbors(_, board)) + |> io.debug |> result.values |> int.sum } -fn to_part_with_neighbors(part: #(List(Coord), Int)) { - let #(coords, n) = part - - let neighbors = - coords - |> list.flat_map(all_neighbors) - |> list.unique - |> list.filter(fn(c) { !list.contains(coords, c) }) - - #(neighbors, n) +fn to_part_with_neighbors(part: Part) -> Part { + part.coords + |> list.flat_map(all_neighbors) + |> list.unique + |> Part(part.part_number) } -fn find_parts_near_gear(gear: Coord, parts: List(#(List(Coord), Int))) { - parts - |> list.filter_map(fn(part) { - let #(neighbors, n) = part - case list.contains(neighbors, gear) { - True -> Ok(n) - False -> Error(Nil) - } - }) +fn find_part_numbers_near_gear(gear: Coord, parts: List(Part)) -> List(Int) { + use part <- list.filter_map(parts) + case list.contains(part.coords, gear) { + True -> Ok(part.part_number) + False -> Error(Nil) + } } -fn keep_gears_near_two_parts(sets_of_parts: List(List(Int))) { - use ps <- list.filter_map(sets_of_parts) +fn to_sum_of_gear_ratios(adjacent_parts: List(List(Int))) -> Int { + use acc, ps <- list.fold(adjacent_parts, 0) case ps { - [p1, p2] -> Ok(p1 * p2) - _ -> Error(Nil) + [p1, p2] -> acc + p1 * p2 + _ -> acc } } -pub fn part2(input: String) { +pub fn part2(input: String) -> Int { let board = to_board(input) let parts = board - |> find_all_parts - |> group_parts([]) + |> find_all_part_digits + |> to_parts |> list.map(to_part_with_neighbors) board - |> dict.filter(fn(_, v) { v == Part(Gear) }) + |> dict.filter(fn(_, v) { v == Symbol(Gear) }) |> dict.keys - |> list.map(find_parts_near_gear(_, parts)) - |> keep_gears_near_two_parts - |> int.sum + |> list.map(find_part_numbers_near_gear(_, parts)) + |> to_sum_of_gear_ratios } pub fn main() { -- cgit v1.2.3 From 8a521c9df766b733f03d357340f74935c65f7de7 Mon Sep 17 00:00:00 2001 From: HJ Date: Sun, 3 Dec 2023 10:30:08 -0500 Subject: day 3 revisions --- aoc2023/src/day3/solve.gleam | 13 ++++--------- 1 file changed, 4 insertions(+), 9 deletions(-) (limited to 'aoc2023') diff --git a/aoc2023/src/day3/solve.gleam b/aoc2023/src/day3/solve.gleam index 21acd26..fa16bb8 100644 --- a/aoc2023/src/day3/solve.gleam +++ b/aoc2023/src/day3/solve.gleam @@ -5,7 +5,6 @@ import gleam/string import gleam/list import gleam/int import gleam/order.{type Order, Eq} -import gleam/result type Coord { Coord(x: Int, y: Int) @@ -102,7 +101,7 @@ fn all_neighbors(c: Coord) -> List(Coord) { } } -fn check_part_neighbors(part: Part, board: Board) -> Result(Int, Nil) { +fn sum_valid_parts(acc: Int, part: Part, board: Board) -> Int { let neighbors = part.coords |> list.flat_map(all_neighbors) @@ -110,8 +109,8 @@ fn check_part_neighbors(part: Part, board: Board) -> Result(Int, Nil) { let sym = [Ok(Symbol(Gear)), Ok(Symbol(SomethingElse))] case list.any(neighbors, fn(c) { list.contains(sym, dict.get(board, c)) }) { - True -> Ok(part.part_number) - False -> Error(Nil) + True -> acc + part.part_number + False -> acc } } @@ -121,11 +120,7 @@ pub fn part1(input: String) -> Int { board |> find_all_part_digits |> to_parts - |> io.debug - |> list.map(check_part_neighbors(_, board)) - |> io.debug - |> result.values - |> int.sum + |> list.fold(0, fn(acc, p) { sum_valid_parts(acc, p, board) }) } fn to_part_with_neighbors(part: Part) -> Part { -- cgit v1.2.3