aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--aoc-2020-gleam/manifest.toml4
-rw-r--r--aoc-2020-gleam/src/aoc_2020_gleam.gleam2
-rw-r--r--aoc-2020-gleam/src/days/day07.gleam80
-rw-r--r--aoc-2020-gleam/src/ext/iteratorx.gleam3
-rw-r--r--aoc-2020-gleam/src/ext/listx.gleam7
-rw-r--r--aoc-2020-gleam/src/util/graph.gleam35
-rw-r--r--aoc-2020-gleam/src/util/parser.gleam28
7 files changed, 138 insertions, 21 deletions
diff --git a/aoc-2020-gleam/manifest.toml b/aoc-2020-gleam/manifest.toml
index b1d3141..2b3dceb 100644
--- a/aoc-2020-gleam/manifest.toml
+++ b/aoc-2020-gleam/manifest.toml
@@ -2,8 +2,8 @@
# You typically do not need to edit this file
packages = [
- { name = "gleam_erlang", version = "0.17.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_erlang", source = "hex", outer_checksum = "BAAA84F5BCC4477E809BA3E03BB3009A3894A6544C1511626C44408E39DB2AE6" },
- { name = "gleam_stdlib", version = "0.26.0", build_tools = ["gleam"], requirements = [], otp_app = "gleam_stdlib", source = "hex", outer_checksum = "6221F9D7A08B6D6DBCDD567B2BB7C4B2A7BBF4C04C6110757BE04635143BDEC8" },
+ { name = "gleam_erlang", version = "0.18.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_erlang", source = "hex", outer_checksum = "14ABC93A7975369CCDDC0C4D9A34C0E0FE99CA3AD336BE6A17299EC0285B7107" },
+ { name = "gleam_stdlib", version = "0.26.1", build_tools = ["gleam"], requirements = [], otp_app = "gleam_stdlib", source = "hex", outer_checksum = "B17BBE8A78F3909D93BCC6C24F531673A7E328A61F24222EB1E58D0A7552B1FE" },
]
[requirements]
diff --git a/aoc-2020-gleam/src/aoc_2020_gleam.gleam b/aoc-2020-gleam/src/aoc_2020_gleam.gleam
index 5590629..a4f5902 100644
--- a/aoc-2020-gleam/src/aoc_2020_gleam.gleam
+++ b/aoc-2020-gleam/src/aoc_2020_gleam.gleam
@@ -6,6 +6,7 @@ import days/day03
import days/day04
import days/day05
import days/day06
+import days/day07
pub fn main() -> Nil {
use day <- runner.with_day()
@@ -16,6 +17,7 @@ pub fn main() -> Nil {
4 -> day04.run()
5 -> day05.run()
6 -> day06.run()
+ 7 -> day07.run()
_ -> io.println("Day not found!")
}
}
diff --git a/aoc-2020-gleam/src/days/day07.gleam b/aoc-2020-gleam/src/days/day07.gleam
new file mode 100644
index 0000000..eee817f
--- /dev/null
+++ b/aoc-2020-gleam/src/days/day07.gleam
@@ -0,0 +1,80 @@
+import gleam/io
+import gleam/list
+import gleam/function as fun
+import gleam/pair
+import gleam/iterator as iter
+import gleam/map.{Map}
+import ext/resultx as resx
+import ext/iteratorx as iterx
+import util/graph
+import util/input_util
+import util/parser as p
+
+const special_bag = "shiny gold"
+
+type BagEdge =
+ #(String, Int)
+
+type BagGraph =
+ Map(String, List(BagEdge))
+
+fn parse_graph(lines: List(String)) -> BagGraph {
+ let bag_type_parser =
+ [p.str1_until_ws(), p.ws_gc(), p.str1_until_ws()]
+ |> p.str_of_seq
+ |> p.labeled(with: "bag_type")
+
+ let line_parser =
+ bag_type_parser
+ |> p.then_skip(p.literal(" bags contain "))
+ |> p.then(p.or(
+ p.int()
+ |> p.then_skip(p.ws_gc())
+ |> p.then(bag_type_parser)
+ |> p.map(with: pair.swap)
+ |> p.then_skip(p.ws_gc())
+ |> p.then_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.then_skip(p.literal("."))
+
+ lines
+ |> list.map(with: fun.compose(
+ p.parse_entire(_, with: line_parser),
+ resx.force_unwrap,
+ ))
+ |> map.from_list
+}
+
+fn part1(lines: List(String)) -> Int {
+ let graph = parse_graph(lines)
+ let neighbours = fn(bag) {
+ graph
+ |> map.get(bag)
+ |> resx.force_unwrap
+ |> list.map(with: pair.first)
+ |> iter.from_list
+ }
+
+ graph
+ |> map.keys
+ |> iter.from_list
+ |> iter.filter(for: fn(bag) { bag != special_bag })
+ |> iterx.count(satisfying: fn(start) {
+ start
+ |> graph.dfs(with: neighbours)
+ |> iter.any(fn(bag) { bag == special_bag })
+ })
+}
+
+pub fn run() -> Nil {
+ let test = input_util.read_lines("test07")
+ assert 4 = part1(test)
+
+ let input = input_util.read_lines("day07")
+ io.debug(part1(input))
+
+ Nil
+}
diff --git a/aoc-2020-gleam/src/ext/iteratorx.gleam b/aoc-2020-gleam/src/ext/iteratorx.gleam
index 456c1d1..8e34351 100644
--- a/aoc-2020-gleam/src/ext/iteratorx.gleam
+++ b/aoc-2020-gleam/src/ext/iteratorx.gleam
@@ -3,8 +3,7 @@ import gleam/list
pub fn length(iterator: Iterator(a)) -> Int {
iterator
- |> iter.to_list
- |> list.length
+ |> iter.fold(from: 0, with: fn(c, _) { c + 1 })
}
pub fn count(iterator: Iterator(a), satisfying predicate: fn(a) -> Bool) -> Int {
diff --git a/aoc-2020-gleam/src/ext/listx.gleam b/aoc-2020-gleam/src/ext/listx.gleam
index d962515..bead987 100644
--- a/aoc-2020-gleam/src/ext/listx.gleam
+++ b/aoc-2020-gleam/src/ext/listx.gleam
@@ -1,7 +1,8 @@
-import gleam/list
+import gleam/iterator as iter
+import ext/iteratorx as iterx
pub fn count(list: List(a), satisfying predicate: fn(a) -> Bool) -> Int {
list
- |> list.filter(for: predicate)
- |> list.length
+ |> iter.from_list
+ |> iterx.count(satisfying: predicate)
}
diff --git a/aoc-2020-gleam/src/util/graph.gleam b/aoc-2020-gleam/src/util/graph.gleam
new file mode 100644
index 0000000..d9aa5aa
--- /dev/null
+++ b/aoc-2020-gleam/src/util/graph.gleam
@@ -0,0 +1,35 @@
+import gleam/list
+import gleam/iterator.{Iterator} as iter
+import gleam/set.{Set}
+
+fn dfs_helper(
+ neighbours: fn(a) -> Iterator(a),
+ stack stack: List(a),
+ visited visited: Set(a),
+ acc acc: List(a),
+) -> List(a) {
+ case stack {
+ [node, ..stack] ->
+ dfs_helper(
+ neighbours,
+ stack: node
+ |> neighbours
+ |> iter.filter(for: fn(n) { !set.contains(visited, n) })
+ |> iter.to_list
+ |> list.append(stack),
+ visited: visited
+ |> set.insert(node),
+ acc: [node, ..acc],
+ )
+ [] -> list.reverse(acc)
+ }
+}
+
+pub fn dfs(from start: a, with neighbours: fn(a) -> Iterator(a)) -> Iterator(a) {
+ iter.from_list(dfs_helper(
+ neighbours,
+ stack: [start],
+ visited: set.new(),
+ acc: [],
+ ))
+}
diff --git a/aoc-2020-gleam/src/util/parser.gleam b/aoc-2020-gleam/src/util/parser.gleam
index 59c6f62..66c20e3 100644
--- a/aoc-2020-gleam/src/util/parser.gleam
+++ b/aoc-2020-gleam/src/util/parser.gleam
@@ -9,7 +9,7 @@ import gleam/option.{None, Option, Some}
// Heavily inspired by https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/
-// TODO: - make distinction between atomic (int, string literal) and non-atomic (then, sequence)
+// TODO: - make distinction between atomic (int, string literal) and non-atomic (then, seq)
// parsers and only override error sources for atomic parsers
// - report where the error occured in the error struct
@@ -253,17 +253,17 @@ fn lift2(function: fn(a, b) -> c) -> fn(Parser(a), Parser(b)) -> Parser(c) {
}
}
-pub fn sequence(of parsers: List(Parser(a))) -> Parser(List(a)) {
+pub fn seq(of parsers: List(Parser(a))) -> Parser(List(a)) {
let prepend_parser = lift2(fn(x, xs) { [x, ..xs] })
case parsers {
[] -> succeeding(with: [])
[head, ..tail] ->
tail
- |> sequence
+ |> seq
|> prepend_parser(head, _)
}
|> labeled(
- with: "sequence(of: [" <> {
+ with: "seq(of: [" <> {
parsers
|> list.map(with: fn(p) { p.label })
|> string.join(", ")
@@ -271,9 +271,9 @@ pub fn sequence(of parsers: List(Parser(a))) -> Parser(List(a)) {
)
}
-pub fn str_of_sequence(of parsers: List(Parser(String))) -> Parser(String) {
+pub fn str_of_seq(of parsers: List(Parser(String))) -> Parser(String) {
parsers
- |> sequence
+ |> seq
|> map(with: string.concat)
}
@@ -314,21 +314,21 @@ pub fn str_of_many1(of parser: Parser(String)) -> Parser(String) {
|> map(with: string.concat)
}
-pub fn sep0(parser: Parser(a), by separator: Parser(b)) -> Parser(List(a)) {
+pub fn sep1(parser: Parser(a), by separator: Parser(b)) -> Parser(List(a)) {
parser
|> then(many0(of: drop_then(separator, parser)))
|> map2(with: fn(p, ps) { [p, ..ps] })
|> labeled(
- with: "sep0(" <> parser.label <> ", by: " <> separator.label <> ")",
+ with: "sep1(" <> parser.label <> ", by: " <> separator.label <> ")",
)
}
-pub fn sep1(parser: Parser(a), by separator: Parser(b)) -> Parser(List(a)) {
+pub fn sep0(parser: Parser(a), by separator: Parser(b)) -> Parser(List(a)) {
parser
- |> sep0(by: separator)
+ |> sep1(by: separator)
|> or(else: succeeding(with: []))
|> labeled(
- with: "sep1(" <> parser.label <> ", by: " <> separator.label <> ")",
+ with: "sep0(" <> parser.label <> ", by: " <> separator.label <> ")",
)
}
@@ -353,14 +353,14 @@ pub fn literal(expected: String) -> Parser(String) {
expected
|> string.to_graphemes
|> list.map(with: fn(eg) { gc_satisfying(fn(g) { g == eg }) })
- |> str_of_sequence
+ |> str_of_seq
|> labeled(with: q_d(expected))
}
pub fn str_of_len(parser: Parser(String), length: Int) -> Parser(String) {
parser
|> list.repeat(times: length)
- |> str_of_sequence
+ |> str_of_seq
|> labeled(
with: "str_of_len(" <> parser.label <> "," <> int.to_string(length) <> ")",
)
@@ -373,7 +373,7 @@ pub fn any_str_of_len(length: Int) -> Parser(String) {
pub fn repeat(parser: Parser(a), times times: Int) -> Parser(List(a)) {
parser
|> list.repeat(times: times)
- |> sequence
+ |> seq
|> labeled(
with: parser.label <> " |> repeat(times: " <> int.to_string(times) <> ")",
)
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-23 16:15:04 +0000