commit e27d180ed44afae12fb299507ea0ad0d4d098ad1
parent 8a3e03c5892f6dc3a9562f76a1cdf54404e65e17
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 9 Apr 2023 22:20:08 -0400
Fix existing days and amend day 12 solution
Diffstat:
21 files changed, 166 insertions(+), 155 deletions(-)
diff --git a/src/.gitignore b/src/.gitignore
@@ -1,2 +1,5 @@
target
Cargo.lock
+template
+compile_commands.json
+main
diff --git a/src/01/Cargo.toml b/src/01/Cargo.toml
@@ -4,4 +4,4 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
diff --git a/src/02/Cargo.toml b/src/02/Cargo.toml
@@ -4,4 +4,4 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
diff --git a/src/03/Cargo.toml b/src/03/Cargo.toml
@@ -4,4 +4,4 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
diff --git a/src/04/Cargo.toml b/src/04/Cargo.toml
@@ -4,4 +4,4 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
diff --git a/src/05/Cargo.toml b/src/05/Cargo.toml
@@ -4,4 +4,4 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
diff --git a/src/06/Cargo.toml b/src/06/Cargo.toml
@@ -4,6 +4,6 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
num-bigint = "0.4.3"
num-traits = "*"
diff --git a/src/07/Cargo.toml b/src/07/Cargo.toml
@@ -4,5 +4,5 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
diff --git a/src/08/Cargo.toml b/src/08/Cargo.toml
@@ -4,5 +4,5 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
diff --git a/src/08/src/main.rs b/src/08/src/main.rs
@@ -1,4 +1,5 @@
use std::collections::HashMap;
+use aoc::debugln;
fn code2bin(code: &str) -> u32 {
let alph = "abcdefg";
@@ -26,8 +27,7 @@ fn bits_set(bin: u32) -> u32 {
return cnt;
}
-fn decode_value(aoc: &mut aoc::Info,
- codes: &Vec<&str>, out_codes: &Vec<&str>) -> u32 {
+fn decode_value(codes: &Vec<&str>, out_codes: &Vec<&str>) -> u32 {
let len2code: HashMap<u32,u32> = HashMap::from([
(2, 1),
(3, 7),
@@ -76,26 +76,26 @@ fn decode_value(aoc: &mut aoc::Info,
for digit in 0..10 {
fit = true;
for cmp in 0..10 {
- aoc::debug!(aoc, "-- {} {} --\n", digit, cmp);
+ debugln!("-- {} {} --", digit, cmp);
let cmplen = overlaps[digit][cmp];
if digit == cmp && bits_set(code) != cmplen {
- aoc::debug!(aoc, "wrong length\n");
+ debugln!("wrong length");
fit = false;
break;
}
if mapping[cmp] == 0 { continue; }
if bits_set(code & mapping[cmp]) != cmplen {
- aoc::debug!(aoc, "wrong # of same bits: {:08b} & {:08b} != {}\n",
+ debugln!("wrong # of same bits: {:08b} & {:08b} != {}",
code, mapping[cmp], cmplen);
fit = false;
break;
}
- aoc::debug!(aoc, "{}: {:08b} {:08b}\n", cmplen, code, mapping[cmp]);
+ debugln!("{}: {:08b} {:08b}", cmplen, code, mapping[cmp]);
}
if fit == true {
- aoc::debug!(aoc, "add {:08b} => {}\n", code, digit);
+ debugln!("add {:08b} => {}", code, digit);
mapping[digit] = code;
break;
}
@@ -145,7 +145,7 @@ fn part2(aoc: &mut aoc::Info) {
.split(" ").collect();
let out_codes: Vec<&str> = line.split_once(" | ").unwrap().1
.split(" ").collect();
- sum += decode_value(aoc, &sig_codes, &out_codes);
+ sum += decode_value(&sig_codes, &out_codes);
}
aoc.answer = Some(format!("{}", sum));
diff --git a/src/09/Cargo.toml b/src/09/Cargo.toml
@@ -4,5 +4,5 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
diff --git a/src/09/src/main.rs b/src/09/src/main.rs
@@ -1,3 +1,5 @@
+use aoc::debugln;
+
#[derive(PartialEq,Eq)]
struct Pos {
x: i32,
@@ -78,9 +80,7 @@ fn part2(aoc: &mut aoc::Info) {
let mut basin_sizes: Vec<usize> = Vec::new();
for start in lowest {
- if aoc.debug {
- println!("START {} {}", start.x, start.y);
- }
+ debugln!("START {} {}", start.x, start.y);
let mut visited: Vec<Pos> = Vec::new();
let mut outer: Vec<Pos> = Vec::new();
@@ -108,9 +108,7 @@ fn part2(aoc: &mut aoc::Info) {
outer = new_outer;
}
- if aoc.debug {
- println!("VISITED COUNT: {}", visited.len());
- }
+ debugln!("VISITED COUNT: {}", visited.len());
basin_sizes.push(visited.len());
}
diff --git a/src/10/Cargo.toml b/src/10/Cargo.toml
@@ -4,6 +4,6 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
lazy_static = "*"
bimap = "*"
diff --git a/src/11/Cargo.toml b/src/11/Cargo.toml
@@ -4,5 +4,5 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
diff --git a/src/11/src/main.rs b/src/11/src/main.rs
@@ -15,16 +15,6 @@ const SURROUNDING: [Pos; 8] = [
Pos { x: 1, y: 1 }
];
-fn print_octos(octos: &Vec<Vec<u32>>) {
- for row in octos {
- for octo in row {
- print!("{}", octo);
- }
- println!();
- }
- println!();
-}
-
fn inc_check(flashed: &mut Vec<Pos>, octos: &mut Vec<Vec<u32>>, x: usize, y: usize) {
let pos = Pos { x: x as i32, y: y as i32 };
if flashed.contains(&pos) { return; }
@@ -72,7 +62,7 @@ fn part1(aoc: &mut aoc::Info) {
flashes += sim_step(&mut octos);
}
- println!("{}", flashes);
+ aoc.answer = Some(format!("{}", flashes));
aoc.solution = Some("1681");
}
diff --git a/src/12/Cargo.toml b/src/12/Cargo.toml
@@ -4,4 +4,4 @@ version = "0.1.0"
edition = "2021"
[dependencies]
-aoc = { path = "../../lib/aoc" }
+aoc = { path = "../common/aoc" }
diff --git a/src/12/src/main.rs b/src/12/src/main.rs
@@ -1,7 +1,5 @@
use std::collections::HashMap;
-
-/* assume no two big caves are next to each other
- * => otherwise infinite paths possible */
+use aoc::{debug, debugln};
#[derive(PartialEq,Clone)]
struct Node {
@@ -43,70 +41,48 @@ fn parse_input(input: &String) -> HashMap<String, Node> {
fn part1(aoc: &mut aoc::Info) {
let nodes = parse_input(&aoc.input);
- let mut path: Vec<&Node> = Vec::new();
- let mut adj_index = 0;
+ let mut path: Vec<NodeState> = Vec::new();
- path.push(nodes.get("start").unwrap());
+ let start_node = nodes.get("start").unwrap();
+ let start_state = NodeState {
+ node: &start_node,
+ index: 0
+ };
+ path.push(start_state);
- let mut paths: usize = 0;
- while path.len() > 0 {
- let current = path.last().unwrap().clone();
- if adj_index >= current.adj.len() {
- /* backtrack */
- path.pop();
- if path.len() == 0 { break; }
- let next = path.last().unwrap();
- adj_index = next.adj.iter().position(|x| *x == current.name).unwrap() + 1;
- } else {
- let adj = nodes.get(¤t.adj[adj_index]).unwrap();
- if adj.name == "end" {
- // for p in &path {
- // print!("{} -> ", p.name);
- // }
- // println!("end");
- paths += 1;
- adj_index += 1;
- } else if !path.contains(&adj) || !adj.small {
- path.push(adj);
- adj_index = 0;
- } else {
- adj_index += 1;
- }
- }
- }
+ /* depth first search of nodes with no recursing
+ * since two big caves can not be next to each other */
- println!("{}", paths);
-}
+ let mut pathcnt: usize = 0;
+ while path.len() > 0 {
+ let mut tail = path.last().unwrap().clone();
-fn self_paths<'a>(nodes: &'a HashMap<String,Node>,
- path: &'a Vec<NodeState<'a>>, cur: &'a Node) -> usize {
- let prevlen = path.len();
-
- let mut path: Vec<NodeState<'a>> = path.to_vec();
- path.push(NodeState { node: cur, index: 0 });
-
- let mut paths: usize = 0;
- while path.len() > prevlen {
- let current = path.last_mut().unwrap();
- if current.index < current.node.adj.len() {
- let adj: &Node = nodes.get(¤t.node.adj[current.index])
- .unwrap();
- current.index += 1;
- if adj == cur {
- paths += 1;
- } else if adj.name != "start" && adj.name != "end" {
- let count = path.iter().filter(|x| x.node == adj).count();
- if count <= 1 || !adj.small {
- path.push(NodeState { node: adj, index: 0 });
+ let mut next: Option<&Node> = None;
+ if tail.index < tail.node.adj.len() {
+ let adj = nodes.get(&tail.node.adj[tail.index]).unwrap();
+ if adj.name == "end" {
+ for p in &path {
+ debug!("{} -> ", p.node.name);
}
+ debugln!("end");
+ pathcnt += 1;
+ } else if !adj.small || path.iter().find(|x| x.node == adj).is_none() {
+ next = Some(&adj);
}
+ tail.index += 1;
+ path.last_mut().unwrap().clone_from(&tail);
} else {
- /* backtrack */
path.pop();
}
+
+ if next.is_some() {
+ let state = NodeState { node: next.unwrap(), index: 0 };
+ path.push(state);
+ }
}
- return paths;
+ aoc.answer = Some(format!("{}", pathcnt));
+ aoc.solution = Some("5457");
}
fn part2(aoc: &mut aoc::Info) {
@@ -114,37 +90,50 @@ fn part2(aoc: &mut aoc::Info) {
let mut path: Vec<NodeState> = Vec::new();
- path.push(NodeState { node: nodes.get("start").unwrap(), index: 0 });
+ let start_node = nodes.get("start").unwrap();
+ let start_state = NodeState { node: start_node, index: 0 };
+ path.push(start_state);
- let mut paths: usize = 0;
+ let mut double: Option<&Node> = None;
+ let mut pathcnt: usize = 0;
while path.len() > 0 {
- let current = path.last_mut().unwrap();
- if current.index < current.node.adj.len() {
- let adj: &Node = nodes.get(¤t.node.adj[current.index])
- .unwrap();
- current.index += 1;
+ let mut tail = path.last().unwrap().clone();
+
+ let mut next: Option<&Node> = None;
+ if tail.index < tail.node.adj.len() {
+ let adj = nodes.get(&tail.node.adj[tail.index]).unwrap();
if adj.name == "end" {
- let mut prod: usize = 1;
- for (i, p) in path.iter().enumerate() {
- aoc::debug!(aoc, "{} -> ", p.node.name);
- if i == 0 { continue; }
- prod += 1 + self_paths(&nodes, &path, p.node);
+ debug!("{} : ", double.is_some());
+ for p in &path {
+ debug!("{} -> ", p.node.name);
}
- paths += prod;
- aoc::debug!(aoc, "end\n");
+ debugln!("end");
+ pathcnt += 1;
} else if adj.name != "start" {
- let count = path.iter().filter(|x| x.node == adj).count();
- if count < 1 || !adj.small {
- path.push(NodeState { node: adj, index: 0 } );
+ let inpath = path.iter().find(|x| x.node == adj).is_some();
+ if !adj.small || !inpath || (inpath && double.is_none()) {
+ if adj.small && inpath {
+ double = Some(&adj);
+ }
+ next = Some(&adj);
}
}
+ tail.index += 1;
+ path.last_mut().unwrap().clone_from(&tail);
} else {
- /* backtrack */
+ if double.is_some() && tail.node == double.unwrap() {
+ double = None;
+ }
path.pop();
}
+
+ if next.is_some() {
+ let state = NodeState { node: next.unwrap(), index: 0 };
+ path.push(state);
+ }
}
- println!("{}", paths);
+ aoc.answer = Some(format!("{}", pathcnt));
}
fn main() {
diff --git a/src/12/test1 b/src/12/test1
@@ -0,0 +1,7 @@
+start-A
+start-b
+A-c
+A-b
+b-d
+A-end
+b-end
diff --git a/src/Makefile b/src/Makefile
@@ -0,0 +1,37 @@
+DAYS = $(shell seq 1 25 | xargs printf "%02i\n")
+
+all:: build run
+
+define make-day
+
+run:: $1/run
+
+build:: $1/main
+
+clean:: $1/clean
+
+.PHONY: $1/run $1/clean
+
+$1/main: $1/src/main.rs
+ cd $1 && cargo build && cp ./target/debug/day$1 main
+
+$1/run1: $1/main
+ @cd $1 && time ./main 1
+
+$1/run2: $1/main
+ @cd $1 && time ./main 2
+
+$1/run:
+ @echo "== day $1 =="
+ @echo -en "\npart 1: " && cd $1 && time ./main 1
+ @echo -en "\npart 2: " && cd $1 && time ./main 2
+ @echo ""
+
+$1/clean:
+ rm $1/main
+
+endef
+
+$(foreach day,$(DAYS),$(eval $(call make-day,$(day))))
+
+.PHONY: all build run clean
diff --git a/src/common/Cargo.toml b/src/common/Cargo.toml
diff --git a/src/common/aoc/src/lib.rs b/src/common/aoc/src/lib.rs
@@ -1,19 +1,9 @@
use std::env;
use std::fs;
use std::process::exit;
-
-#[derive(PartialEq, PartialOrd)]
-pub enum Loglvl {
- LogNone = 0,
- LogVerb,
- LogDebug,
- LogAll
-}
+use std::sync::atomic::{AtomicU8, Ordering};
pub struct Info {
- pub verbose: bool,
- pub debug: bool,
-
pub filename: String,
pub input: String,
pub part: u32,
@@ -22,45 +12,44 @@ pub struct Info {
pub answer: Option<String>,
}
-#[macro_export]
-macro_rules! die {
- ($( $arg:expr ),*) => {
- eprintln!($( $arg ), *);
- exit(1);
- }
+static DEBUG: AtomicU8 = AtomicU8::new(0);
+
+pub fn get_debug() -> u8 {
+ DEBUG.load(Ordering::Relaxed)
+}
+
+pub fn set_debug(lvl: u8) {
+ DEBUG.store(lvl, Ordering::Relaxed);
}
#[macro_export]
macro_rules! debug {
- ($aoc:expr, $( $arg:expr ),*) => {
- if $aoc.debug {
+ ($( $arg:expr ),*) => {
+ if aoc::get_debug() > 0 {
eprint!($( $arg ), *);
}
}
}
#[macro_export]
-macro_rules! verbose {
- ($aoc:expr, $( $arg:expr ),*) => {
- if $aoc.verbose {
- eprint!($( $arg ), *);
+macro_rules! debugln {
+ ($( $arg:expr ),*) => {
+ if aoc::get_debug() > 0 {
+ eprintln!($( $arg ), *);
}
}
}
-pub fn to_loglvl(val: u32) -> Loglvl {
- match val {
- 0 => return Loglvl::LogNone,
- 1 => return Loglvl::LogVerb,
- 2 => return Loglvl::LogAll,
- _ => panic!("Invalid log level {}", val)
+#[macro_export]
+macro_rules! err {
+ ($( $arg:expr ),*) => {
+ eprintln!($( $arg ), *);
+ exit(1);
}
}
pub fn run(part1: fn(info: &mut Info), part2: fn(info: &mut Info)) {
let mut info = Info {
- verbose: false,
- debug: false,
filename: "input".to_string(),
input: "".to_string(),
part: 0,
@@ -68,35 +57,33 @@ pub fn run(part1: fn(info: &mut Info), part2: fn(info: &mut Info)) {
answer: None,
};
- let input_file = env::var("AOCINPUT");
+ let input_file = env::var("AOC_INPUT");
if input_file.is_ok() {
info.filename = input_file.unwrap();
}
let content = fs::read_to_string(info.filename.clone());
if content.is_err() {
- die!("Failed to read from file: {}", info.filename);
+ err!("Failed to read from file: {}", info.filename);
}
info.input = content.unwrap();
- let debug = env::var("AOCDEBUG");
- if debug.is_ok() {
- let num = debug.unwrap().parse::<u32>().unwrap();
- let lvl = to_loglvl(num);
- info.verbose = lvl >= Loglvl::LogVerb;
- info.debug = lvl >= Loglvl::LogDebug;
+ let envvar = env::var("AOC_DEBUG");
+ if envvar.is_ok() {
+ let lvl = envvar.unwrap().parse::<u32>().unwrap();
+ set_debug(lvl as u8);
}
let args: Vec<String> = env::args().collect();
if args.len() > 1 {
let num = args[1].parse();
if num.is_err() {
- die!("Invalid part number: {}", args[1]);
+ err!("Invalid part number: {}", args[1]);
}
info.part = num.unwrap();
} else {
- die!("Usage: aoc run PART");
+ err!("Usage: aoc run PART");
}
if info.part == 1 {
@@ -104,7 +91,7 @@ pub fn run(part1: fn(info: &mut Info), part2: fn(info: &mut Info)) {
} else if info.part == 2 {
part2(&mut info);
} else {
- die!("No such part: {}", info.part);
+ err!("No such part: {}", info.part);
}
if info.answer.is_some() {
@@ -113,7 +100,7 @@ pub fn run(part1: fn(info: &mut Info), part2: fn(info: &mut Info)) {
if info.solution.is_some() {
let solution = info.solution.unwrap();
if answer != solution {
- die!("Incorrect solution!");
+ err!("Incorrect solution!");
}
}
}
