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

  • Amy ( lwhjp@lemmy.sdf.org ) deleted by creator
    link
    fedilink
    arrow-up
    8
    ·
    2 years ago

    Haskell

    This was quite fun! I got a bit distracted trying to rewrite safe in point-free style, but I think this version is the most readable. There’s probably a more monadic way of writing lessOne as 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) input
    
  • Gobbel2000 ( Gobbel2000@programming.dev ) 
    link
    fedilink
    English
    arrow-up
    5
    ·
    2 years ago

    Rust

    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!();
    
  • 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; i
  • Andy ( Andy@programming.dev ) 
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    2 years ago

    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 ;
    
  • Ananace ( ace@lemmy.ananace.dev ) 
    link
    fedilink
    arrow-up
    4
    ·
    2 years ago

    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));
    }
    
        • hades ( hades@lemm.ee ) 
          link
          fedilink
          arrow-up
          2
          ·
          2 years ago

          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.

            • hades ( hades@lemm.ee ) 
              link
              fedilink
              arrow-up
              3
              ·
              2 years ago

              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 call EvaluateLineSafe at 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.

  • janAkali ( janAkali@lemmy.one ) 
    link
    fedilink
    English
    arrow-up
    3
    ·
    2 years ago

    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
    

    Codeberg repo

  • ystael ( ystael@beehaw.org ) 
    link
    fedilink
    arrow-up
    3
    ·
    2 years ago

    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 "1 everywhere (you can interpret v"1 as “force the verb v to 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 data
    
  • wer2 ( wer2@lemm.ee ) 
    link
    fedilink
    arrow-up
    2
    ·
    2 years ago

    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))))
    
    
  • Nighed ( Nighed@feddit.uk ) 
    link
    fedilink
    English
    arrow-up
    2
    ·
    2 years ago

    #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;
    }
    

    }

    `

  • Deebster ( Deebster@programming.dev ) 
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    2 years ago

    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 wait edit: 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);
        }
    }
    
    
  • morrowind ( morrowind@lemmy.ml ) 
    link
    fedilink
    arrow-up
    1
    ·
    2 years ago

    Smalltalk

    Discovered a number of frustrations with this supposedly small and elegant language

    1. Smalltalk’s block based iteration has NO control flow
    2. blocks are very dissimilar to functions
    3. You cannot early return from blocks (leading to a lot of horrible nested ifs or boolean operations)
    4. 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
    5. 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 be nums[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    
        ].
    
  • hosaka ( hosaka@programming.dev ) 
    link
    fedilink
    arrow-up
    1
    ·
    2 years ago

    #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);