Day 2: Red-Nosed Reports
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://blocks.programming.dev if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/22323136
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Haskell
This was quite fun! I got a bit distracted trying to rewrite
safein point-free style, but I think this version is the most readable. There’s probably a more monadic way of writinglessOneas well, but I can’t immediately see it.safe xs = any gradual [diffs, negate <$> diffs] where diffs = zipWith (-) (drop 1 xs) xs gradual = all (`elem` [1 .. 3]) lessOne [] = [] lessOne (x : xs) = xs : map (x :) (lessOne xs) main = do input :: [[Int]] <- map (map read . words) . lines <$> readFile "input02" print . length $ filter safe input print . length $ filter (any safe . lessOne) inputRust
The function is_sorted_by on Iterators turned out helpful for compactly finding if a report is safe. In part 2 I simply tried the same with each element removed, since all reports are very short.
fn parse(input: String) -> Vec> { input.lines() .map(|l| l.split_whitespace().map(|w| w.parse().unwrap()).collect()) .collect() } fn is_safe(report: impl DoubleEndedIterator + Clone) -> bool { let safety = |a: &i32, b: &i32| (1..=3).contains(&(b - a)); report.clone().is_sorted_by(safety) || report.rev().is_sorted_by(safety) } fn part1(input: String) { let reports = parse(input); let safe = reports.iter().filter(|r| is_safe(r.iter().copied())).count(); println!("{safe}"); } fn is_safe2(report: &[i32]) -> bool { (0..report.len()).any(|i| { // Try with each element removed is_safe(report.iter().enumerate().filter(|(j, _)| *j != i).map(|(_, n)| *n)) }) } fn part2(input: String) { let reports = parse(input); let safe = reports.iter().filter(|r| is_safe2(r)).count(); println!("{safe}"); } util::aoc_main!();is_sorted_byis new to me, could be very useful.deleted by creator
C
First went through the input in one pass, number by number, but unfortunately that wouldn’t fly for part 2.
Code
#include "common.h" static int issafe(int *lvs, int n, int skip) { int safe=1, asc=0,prev=0, ns=0,i; for (i=0; safe && i 0) safe = safe && lvs[i] != prev && lvs[i] > prev-4 && lvs[i] < prev+4; if (i-ns == 1) asc = lvs[i] > prev; if (i-ns > 1) safe = safe && (lvs[i] > prev) == asc; prev = lvs[i]; } return safe; } int main(int argc, const char **argv) { char buf[64], *rest, *tok; int p1=0,p2=0, lvs[16],n=0, i; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); while ((rest = fgets(buf, sizeof(buf), stdin))) { for (n=0; (tok = strsep(&rest, " ")); n++) { assert(n < (int)LEN(lvs)); lvs[n] = (int)strtol(tok, NULL, 10); } for (i=-1; iWhat is this coding style? The function type, name and open brace placement made me think GNU at first, but the code in the body doesn’t look like GCS at all.
BSD more or less. Mostly K&R except for function declarations.
Factor
: get-input ( -- reports ) "vocab:aoc-2024/02/input.txt" utf8 file-lines [ split-words [ string>number ] map ] map ; : slanted? ( report -- ? ) { [ [ > ] monotonic? ] [ [ < ] monotonic? ] } || ; : gradual? ( report -- ? ) [ - abs 1 3 between? ] monotonic? ; : safe? ( report -- ? ) { [ slanted? ] [ gradual? ] } && ; : part1 ( -- n ) get-input [ safe? ] count ; : fuzzy-reports ( report -- reports ) dup length [ remove-nth-of ] with map ; : tolerable? ( report -- ? ) { [ safe? ] [ fuzzy-reports [ safe? ] any? ] } || ; : part2 ( -- n ) get-input [ tolerable? ] count ;Quite the interesting language choice. It’s so clean. I love it!
Of course I ended up with a off-by-one error for the second part, so things took a bit longer than they really should’ve.
But either way, behold, messy C#:
C#
int[][] reports = new int[0][]; public void Input(IEnumerable lines) { reports = lines.Select(l => l.Split(' ').Select(p => int.Parse(p)).ToArray()).ToArray(); } public void Part1() { int safeCount = reports.Where(report => CheckReport(report)).Count(); Console.WriteLine($"Safe: {safeCount}"); } public void Part2() { int safeCount = reports.Where(report => { if (CheckReport(report)) return true; for (int i = 0; i < report.Length; ++i) if (CheckReport(report.Where((_, j) => j != i))) return true; return false; }).Count(); Console.WriteLine($"Safe: {safeCount}"); } bool CheckReport(IEnumerable report) { var diffs = report.SkipLast(1).Zip(report.Skip(1)).Select(v => v.Second - v.First); return diffs.All(v => Math.Abs(v) <= 3) && (diffs.All(v => v > 0) || diffs.All(v => v < 0)); }deleted by creator
I don’t think your solution is O(N^3). Can you explain your reasoning?
deleted by creator
It’s not as simple as that. You can have 20 nested for loops with complexity of O(1) if all of them only ever finish one iteration.
Or you can have one for loop that iterates 2^N times.
deleted by creator
It’s O(n).
If you look at each of the levels of all reports, you will access it a constant number of times: at most twice in each call to
EvaluateLineSafe, and you will callEvaluateLineSafeat most six times for each report.It really depends on what your parameter n is. If the only relevant size is the number of records (let’s say that is n), then this solution takes time in O(n), because it loops over records only once at a time. This ignores the length of records by considering it constant.
If we also consider the maximum length of records (let’s call it m), then your solution, and most others I’ve seen in this thread, has a time complexity in O(n * m^2) for part 2.
Nim
Got correct answer for part 1 on first try, but website rejected it. Wasted some time debugging and trying different methods. Only to have the same answer accepted minutes later. =(
proc isSafe(report: seq[int]): bool = let diffs = collect: for i, n in report.toOpenArray(1, report.high): n - report[i] (diffs.allIt(it > 0) or diffs.allIt(it < 0)) and diffs.allIt(it.abs in 1..3) proc solve(input: string): AOCSolution[int, int] = let lines = input.splitLines() var reports: seq[seq[int]] for line in lines: reports.add line.split(' ').map(parseInt) for report in reports: if report.isSafe(): inc result.part1 inc result.part2 else: for t in 0..report.high: var mReport = report mReport.delete t if mReport.isSafe(): inc result.part2 break
J
There is probably a way to write this more point-free. You can definitely see here the friction involved in the way J wants to regard lists as arrays: short rows of the input matrix are zero padded, so you have to snip off the padding before you process each row, and that means you can’t lift some of the operations back up to the parent matrix because it will re-introduce the padding as it reshapes the result; this accounts for a lot of the
"1everywhere (you can interpretv"1as “force the verbvto operate on rank 1 subarrays of the argument”).data_file_name =: '2.data' data =: > 0 ". each cutopen toJ fread data_file_name NB. {. take, i. index of; this removes trailing zeros remove_padding =: {.~ i.&0 NB. }. behead, }: curtail; this computes successive differences diff =: }. - }: NB. a b in_range y == a <: y <: b in_range =: 4 : '(((0 { x) & <:) * (<: & (1 { x))) y' NB. a row is safe if either all successive differences are in [1..3] or all in [_3.._1] NB. +. or ranges =: 2 2 $ 1 3 _3 _1 row_safe =: (+./"1) @: (*/"1) @: (ranges & (in_range"1 _)) @: diff @: remove_padding result1 =: +/ safe"1 data NB. x delete y is y without the xth element delete =: 4 : '(x {. y) , ((>: x) }. y)'"0 _ modified_row =: 3 : 'y , (i.#y) delete y' modified_row_safe =: 3 : '+./"1 row_safe"1 modified_row"1 y' result2 =: +/ modified_row_safe datadeleted by creator
Lisp
Part 1
(defun p1-process-line (line) (mapcar #'parse-integer (str:words line))) (defun line-direction-p (line) "make sure the line always goes in the same direction" (loop for x in line for y in (cdr line) count (> x y) into dec count (< x y) into inc when (and (> dec 0 ) (> inc 0)) return nil when (= x y) return nil finally (return t))) (defun line-in-range-p (line) "makes sure the delta is within 3" (loop for x in line for y in (cdr line) for delta = (abs (- x y)) when (or (> delta 3) ) return nil finally (return t))) (defun test-line-p (line) (and (line-in-range-p line) (line-direction-p line))) (defun run-p1 (file) (let ((data (read-file file #'p1-process-line))) (apply #'+ (mapcar (lambda (line) (if (test-line-p line) 1 0)) data))))Part 2
(defun test-line-p2 (line) (or (test-line-p (cdr line)) (test-line-p (cdr (reverse line))) (loop for back on line collect (car back) into front when (test-line-p (concatenate 'list front (cddr back))) return t finally (return nil) ))) (defun run-p2 (file) (let ((data (read-file file #'p1-process-line))) (loop for line in data count (test-line-p2 line))))#Rust
initially, for part two I was trying to ignore a bad pair not a bad value - read the question!
Only installed Rust on Sunday, day 1 was a mess, today was more controlled. Need to look at some of the rust solutions for std library methods I don’t know about.
very focussed on getting it to actually compile/work over making it short or nice!
long!
`
pub mod task_2 {
pub fn task_1(input: &str) -> i32{ let mut valid_count = 0; let reports = process_input(input); for report in reports{ let valid = is_report_valid(report); if valid{ valid_count += 1; } } println!("Valid count: {}", valid_count); valid_count } pub fn task_2(input: &str) -> i32{ let mut valid_count = 0; let reports = process_input(input); for report in reports{ let mut valid = is_report_valid(report.clone()); if !valid { for position_to_delete in 0..report.len() { let mut updated_report = report.clone(); updated_report.remove(position_to_delete); valid = is_report_valid(updated_report); if valid { break; } } } if valid{ valid_count += 1; } } println!("Valid count: {}", valid_count); valid_count } fn is_report_valid(report:Vec) -> bool{ let mut increasing = false; let mut decreasing = false; let mut valid = true; for position in 1..report.len(){ if report[position-1] > report[position] { decreasing = true; } else if report[position-1] < report[position] { increasing = true; } else { valid = false; break; } if (report[position-1] - report[position]).abs() > 3 { valid = false; break; } if increasing && decreasing { valid = false; break; } } return valid; } pub fn process_input(input: &str) -> Vec>{ let mut reports: Vec> = Vec::new(); for report_string in input.split("\n"){ let mut report: Vec = Vec::new(); for value in report_string.split_whitespace() { report.push(value.parse::().unwrap()); } reports.push(report); } return reports; }}
`
I forgot that this started yesterday, so I’m already behind. I quite like my solution for part one,
but part two will have to waitedit: part 2 was a lot simpler than I thought after a night’s sleep.Rust
use color_eyre::eyre; use std::{fs, num, str::FromStr}; #[derive(Debug, PartialEq, Eq)] struct Report(Vec); impl FromStr for Report { type Err = num::ParseIntError; fn from_str(s: &str) -> Result { let v: Result, _> = s .split_whitespace() .map(|num| num.parse::()) .collect(); Ok(Report(v?)) } } impl Report { fn is_safe(&self) -> bool { let ascending = self.0[1] > self.0[0]; let (low, high) = if ascending { (1, 3) } else { (-3, -1) }; self.0.windows(2).all(|w| { let a = w[0]; let b = w[1]; b >= a + low && b <= a + high }) } fn is_dampsafe(&self) -> bool { if self.is_safe() { return true; } for i in 0..self.0.len() { let damped = { let mut v = self.0.clone(); v.remove(i); Self(v) }; if damped.is_safe() { return true; } } false } } fn main() -> eyre::Result<()> { color_eyre::install()?; let part1 = part1("d02/input.txt")?; let part2 = part2("d02/input.txt")?; println!("Part 1: {part1}\nPart 2: {part2}"); Ok(()) } fn part1(filepath: &str) -> eyre::Result { let mut num_safe = 0; for l in fs::read_to_string(filepath)?.lines() { if Report::from_str(l)?.is_safe() { num_safe += 1; } } Ok(num_safe) } fn part2(filepath: &str) -> eyre::Result { let mut num_safe = 0; for l in fs::read_to_string(filepath)?.lines() { if Report::from_str(l)?.is_dampsafe() { num_safe += 1; } } Ok(num_safe) }Tests
#[cfg(test)] mod tests { use super::*; #[test] fn sample_part1() { assert_eq!(part1("test.txt").unwrap(), 2); } #[test] fn sample_part2() { assert_eq!(part2("test.txt").unwrap(), 4); } }Smalltalk
Discovered a number of frustrations with this supposedly small and elegant language
- Smalltalk’s block based iteration has NO control flow
- blocks are very dissimilar to functions
- You cannot early return from blocks (leading to a lot of horrible nested ifs or boolean operations)
- Smalltalk’s messages (~functions) cannot take multiple arguments, instead it has these sort of combined messages, so instead of a function with three arguments, you would send 3 combined messages with one argument. This is fine until you try to chain messages with arguments, as smalltalk will interpret them as a combined message and fail, forcing you to either break into lots of temp variables, or do lisp-like parenthesis nesting, both of which I hate
- Smalltalk’s order of operations, while nice and simple, is also quite frustrating at times, similar to #4, forcing you to break into lots of temp variables, or do lisp-like parenthesis nesting. For instance
(nums at: i) - (nums at: i+1)which would benums[i] - nums[i+1]in most languages
Part 1
day2p1: input ^ (input lines collect: [ :l | l substrings collect: [ :s | s asInteger ]]) count: [ :nums | (nums = nums sorted or: nums = nums sorted reverse) and: [ (1 to: nums size-1) allSatisfy: [ :i | ((nums at: i) - (nums at: i+1)) abs between: 1 and: 3 ] ] ]Part 2
day2p2: input | temp | ^ (input lines collect: [ :l | (l substrings collect: [ :s | s asInteger ]) asOrderedCollection ]) count: [ :nums | (self day2p2helper: nums) or: [ ((1 to: nums size) anySatisfy: [ :i | temp := nums copy. temp removeAt: i. self day2p2helper: temp ]) or: [(self day2p2helper: nums reversed) or: [ (1 to: nums size) anySatisfy: [ :i | temp := nums reversed. temp removeAt: i. self day2p2helper: temp ] ]]] . ]day2p2helper: nums ^ (1 to: nums size - 1) allSatisfy: [ :i | ((nums at: i+1) - (nums at: i)) between: 1 and: 3 ].#Zig
const std = @import("std"); const List = std.ArrayList; const splitScalar = std.mem.splitScalar; const parseInt = std.fmt.parseInt; const print = std.debug.print; const concat = std.mem.concat; var gpa = std.heap.GeneralPurposeAllocator(.{}){}; const alloc = gpa.allocator(); const Answer = struct { safe: u32, tolerated: u32, }; pub fn isSafe(levels: []i32) bool { if (levels.len == 0) { return false; } // slide window in pairs, advancing by one var it = std.mem.window(i32, levels, 2, 1); const first = it.first(); const decreasing = first[0] - first[1] > 0; it.reset(); // rewind the iterator while (it.next()) |slice| { const lhs: i32 = slice[0]; const rhs: i32 = slice[1]; if (decreasing) { if (lhs <= rhs) return false; if (lhs - rhs < 1 or lhs - rhs > 3) return false; } else { if (rhs <= lhs) return false; if (rhs - lhs < 1 or rhs - lhs > 3) return false; } } return true; } pub fn solve(input: []const u8) !Answer { var rows = splitScalar(u8, input, '\n'); // PART 1 // determine how many reports are safe var safe_reports: u32 = 0; var tolerated_reports: u32 = 0; var unsafe_reports = List([]i32).init(alloc); defer unsafe_reports.deinit(); while (rows.next()) |row| { var levels = splitScalar(u8, row, ' '); var report = List(i32).init(alloc); defer report.deinit(); while (levels.next()) |level| { const value = parseInt(i32, level, 10) catch continue; report.append(value) catch continue; } if (isSafe(report.items)) { safe_reports += 1; } else { try unsafe_reports.append(try alloc.dupe(i32, report.items)); } } // PART 2 // determine how many unsafe reports can be tolerated for (unsafe_reports.items) |report| { var index: usize = 0; while (index < report.len) : (index += 1) { // mutate report by removing one level const mutated_report = concat( alloc, i32, &[_][]const i32{ report[0..index], report[index + 1 ..] }, ) catch report; defer alloc.free(mutated_report); if (isSafe(mutated_report)) { tolerated_reports += 1; break; } } } return Answer{ .safe = safe_reports, .tolerated = safe_reports + tolerated_reports }; } pub fn main() !void { const answer = try solve(@embedFile("input.txt")); print("Part 1: {d}\n", .{answer.safe}); print("Part 2: {d}\n", .{answer.tolerated}); } test "test input" { const answer = try solve(@embedFile("test.txt")); try std.testing.expectEqual(2, answer.safe); try std.testing.expectEqual(4, answer.tolerated);Rust
Turned out alright, I am looking forward to seeing what 2d coordinate grid code I can cannibalize from last year’s solutions 😄
I think that repo is private
I realized after I posted 😅 thanks for pointing it out! I will go make it public











