Day 6: Wait for It


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)
  • Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    11
    ·
    edit-2
    11 months ago

    Today was easy enough that I felt confident enough to hammer out a solution in Uiua, so read and enjoy (or try it out live):

    {"Time:      7  15   30"
     "Distance:  9  40  200"}
    StoInt ← /(+ ×10) ▽×⊃(≥0)(≤9). -@0
    Count ← (
      ⊙⊢√-×4:×.⍘⊟.           # Determinant, and time
      +1-⊃(+10⌊÷2-)(-1⌈÷2+) # Diff of sanitised roots
    )
    ≡(↘1⊐⊜∘≠@\s.)
    ⊃(/×≡Count⍉∵StoInt)(Count⍉≡(StoInt⊐/⊂))
    
  • Gobbel2000@feddit.de
    link
    fedilink
    arrow-up
    8
    ·
    11 months ago

    Rust

    I went with solving the quadratic equation, so part 2 was just a trivial change in parsing. It was a bit janky to find the integer that is strictly larger than a floating point number, but it all worked out.

      • moriquende@lemmy.world
        link
        fedilink
        arrow-up
        1
        ·
        edit-2
        11 months ago

        In Python when using numpy to find the roots, sometimes you get a numeric artifact like 30.99999999999, which breaks this. Make sure to limit the significant digits to a sane amount like 5 with rounding to prevent that.

    • Black616Angel@feddit.de
      link
      fedilink
      arrow-up
      2
      ·
      11 months ago

      I wanted to try the easy approach first and see how slow it was. Didn’t even take a second for part 2. So I just skipped the mathematical solution entirely.

  • cacheson@kbin.social
    link
    fedilink
    arrow-up
    6
    ·
    11 months ago

    Nim

    Hey, waitaminute, this isn’t a programming puzzle. This is algebra homework!

    Part 2 only required a trivial change to the parsing, the rest of the code still worked. I kept the data as singleton arrays to keep it compatible.

  • Leo Uino@lemmy.sdf.org
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    11 months ago

    Haskell

    This problem has a nice closed form solution, but brute force also works.

    (My keyboard broke during part two. Yet another day off the bottom of the leaderboard…)

    import Control.Monad
    import Data.Bifunctor
    import Data.List
    
    readInput :: String -> [(Int, Int)]
    readInput = map (\[t, d] -> (read t, read d)) . tail . transpose . map words . lines
    
    -- Quadratic formula
    wins :: (Int, Int) -> Int
    wins (t, d) =
      let c = fromIntegral t / 2 :: Double
          h = sqrt (fromIntegral $ t * t - 4 * d) / 2
       in ceiling (c + h) - floor (c - h) - 1
    
    main = do
      input <- readInput <$> readFile "input06"
      print $ product . map wins $ input
      print $ wins . join bimap (read . concatMap show) . unzip $ input
    
  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    11 months ago

    Dart Solution

    I decided to use the quadratic formula to solve part 1 which slowed me down while I struggled to remember how it went, but meant that part 2 was a one line change.

    This year really is a roller coaster…

    int countGoodDistances(int time, int targetDistance) {
      var det = sqrt(time * time - 4 * targetDistance);
      return (((time + det) / 2).ceil() - 1) -
          (max(((time - det) / 2).floor(), 0) + 1) +
          1;
    }
    
    solve(List> data, [param]) {
      var distances = data.first
          .indices()
          .map((ix) => countGoodDistances(data[0][ix], data[1][ix]));
      return distances.reduce((s, t) => s * t);
    }
    
    getNums(l) => l.split(RegExp(r'\s+')).skip(1);
    
    part1(List lines) =>
        solve([for (var l in lines) getNums(l).map(int.parse).toList()]);
    
    part2(List lines) => solve([
          for (var l in lines) [int.parse(getNums(l).join(''))]
        ]);
    
  • anonymouse@sh.itjust.works
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    11 months ago

    Rust

    Feedback welcome! Feel like I’m getting the hand of Rust more and more.

    use regex::Regex;
    pub fn part_1(input: &str) {
        let lines: Vec<&str> = input.lines().collect();
        let time_data = number_string_to_vec(lines[0]);
        let distance_data = number_string_to_vec(lines[1]);
    
        // Zip time and distance into a single iterator
        let data_iterator = time_data.iter().zip(distance_data.iter());
    
        let mut total_possible_wins = 1;
        for (time, dist_req) in data_iterator {
            total_possible_wins *= calc_possible_wins(*time, *dist_req)
        }
        println!("part possible wins: {:?}", total_possible_wins);
    }
    
    pub fn part_2(input: &str) {
        let lines: Vec<&str> = input.lines().collect();
        let time_data = number_string_to_vec(&lines[0].replace(" ", ""));
        let distance_data = number_string_to_vec(&lines[1].replace(" ", ""));
    
        let total_possible_wins = calc_possible_wins(time_data[0], distance_data[0]);
        println!("part 2 possible wins: {:?}", total_possible_wins);
    }
    
    pub fn calc_possible_wins(time: u64, dist_req: u64) -> u64 {
        let mut ways_to_win: u64 = 0;
    
        // Second half is a mirror of the first half, so only calculate first part
        for push_time in 1..=time / 2 {
            // If a push_time crosses threshold the following ones will too so break loop
            if push_time * (time - push_time) > dist_req {
                // There are (time+1) options (including 0).
                // Subtract twice the minimum required push time, also removing the longest push times
                ways_to_win += time + 1 - 2 * push_time;
                break;
            }
        }
        ways_to_win
    }
    
    fn number_string_to_vec(input: &str) -> Vec {
        let regex_number = Regex::new(r"\d+").unwrap();
        let numbers: Vec = regex_number
            .find_iter(input)
            .filter_map(|m| m.as_str().parse().ok())
            .collect();
        numbers
    }
    
    
    • hades@lemm.ee
      link
      fedilink
      arrow-up
      2
      ·
      11 months ago

      Somewhere on the way you seem to have converted ampersands to HTML entities :)

    • Walnut356@programming.dev
      link
      fedilink
      arrow-up
      1
      ·
      edit-2
      11 months ago

      I’m no rust expert, but:

      you can use into_iter() instead of iter() to get owned data (if you’re not going to use the original container again). With into_iter() you dont have to deref the values every time which is nice.

      Also it’s small potatoes, but calling input.lines().collect() allocates a vector (that isnt ever used again) when lines() returns an iterator that you can use directly. You can instead pass lines.next().unwrap() into your functions directly.

      Strings have a method called split_whitespace() (also a split_ascii_whitespace()) that returns an iterator over tokens separated by any amount of whitespace. You can then call .collect() with a String turbofish (i’d type it out but lemmy’s markdown is killing me) on that iterator. Iirc that ends up being faster because replacing characters with an empty character requires you to shift all the following characters backward each time.

      Overall really clean code though. One of my favorite parts of using rust (and pain points of going back to other languages) is the crazy amount of helper functions for common operations on basic types.

      Edit: oh yeah, also strings have a .parse() method to converts it to a number e.g. data.parse() where the parse takes a turbo fish of the numeric type. As always, turbofishes arent required if rust already knows the type of the variable it’s being assigned to.

      • anonymouse@sh.itjust.works
        link
        fedilink
        arrow-up
        1
        ·
        11 months ago

        Thanks for making some time to check my code, really appreciated! the split_whitespace is super useful, for some reason I expected it to just split on single spaces, so I was messing with trim() stuff the whole time :D. Could immediately apply this feedback to the Challenge of today! I’ve now created a general function I can use for these situations every time:

            input.split_whitespace()
                .map(|m| m.parse().expect("can't parse string to int"))
                .collect()
        }
        

        Thanks again!

  • vole@lemmy.world
    link
    fedilink
    English
    arrow-up
    3
    ·
    edit-2
    11 months ago

    Raku

    I spent a lot more time than necessary optimizing the count-ways-to-beat function, but I’m happy with the result. This is my first time using the | operator to flatten a list into function arguments.

    edit: unfortunately, the lemmy web page is unable to properly display the source code in a code block. It doesn’t display text enclosed in pointy brackets <>, perhaps it looks too much like HTML. View code on github.

    Code
    use v6;
    
    sub MAIN($input) {
        my $file = open $input;
    
        grammar Records {
            token TOP {  "\n"  "\n"* }
            token times { "Time:" \s* +%\s+ }
            token distances { "Distance:" \s* +%\s+ }
            token num { \d+ }
        }
    
        my $records = Records.parse($file.slurp);
    
        my $part-one-solution = 1;
        for $records».Int Z $records».Int -> $record {
            $part-one-solution *= count-ways-to-beat(|$record);
        }
        say "part 1: $part-one-solution";
    
        my $kerned-time = $records.join.Int;
        my $kerned-distance = $records.join.Int;
        my $part-two-solution = count-ways-to-beat($kerned-time, $kerned-distance);
        say "part 2: $part-two-solution";
    }
    
    sub count-ways-to-beat($time, $record-distance) {
        # time = button + go
        # distance = go * button
        # 0 = go^2 - time * go + distance
        # go = (time +/- sqrt(time**2 - 4*distance))/2
    
        # don't think too hard:
        # if odd t then t/2 = x.5,
        #   so sqrt(t**2-4*d)/2 = 2.3 => result = 4
        #   and sqrt(t**2-4*d)/2 = 2.5 => result = 6
        #   therefore result = 2 * (sqrt(t**2-4*d)/2 + 1/2).floor
        # even t then t/2 = x.0
        #   so sqrt(t^2-4*d)/2 = 2.x => result = 4 + 1(shared) = 5
        #   therefore result = 2 * (sqrt(t^2-4*d)/2).floor + 1
        # therefore result = 2 * ((sqrt(t**2-4*d)+t%2)/2).floor + 1 - t%2
        # Note: sqrt produces a Num, so perhaps the result could be off by 1 or 2,
        #       but it solved my AoC inputs correctly 😃.
    
        my $required-distance = $record-distance + 1;
        return 2 * ((sqrt($time**2 - 4*$required-distance) + $time%2)/2).floor + 1 - $time%2;
    }
    
  • UlrikHD@programming.dev
    link
    fedilink
    arrow-up
    3
    ·
    edit-2
    11 months ago

    A nice change of pace from the previous puzzles, more maths and less parsing

    Python
    import math
    import re
    
    
    def create_table(filename: str) -> list[tuple[int, int]]:
        with open('day6.txt', 'r', encoding='utf-8') as file:
            times: list[str] = re.findall(r'\d+', file.readline())
            distances: list[str] = re.findall(r'\d+', file.readline())
        table: list[tuple[int, int]] = []
        for t, d in zip(times, distances):
            table.append((int(t), int(d)))
        return table
    
    
    def get_possible_times_num(table_entry: tuple[int, int]) -> int:
        t, d = table_entry
        l_border: int = math.ceil(0.5 * (t - math.sqrt(t**2 -4 * d)) + 0.0000000000001)  # Add small num to ensure you round up on whole numbers
        r_border: int = math.floor(0.5*(math.sqrt(t**2 - 4 * d) + t) - 0.0000000000001)  # Subtract small num to ensure you round down on whole numbers
        return r_border - l_border + 1
    
    
    def puzzle1() -> int:
        table: list[tuple[int, int]] = create_table('day6.txt')
        possibilities: int = 1
        for e in table:
            possibilities *= get_possible_times_num(e)
        return possibilities
    
    
    def create_table_2(filename: str) -> tuple[int, int]:
        with open('day6.txt', 'r', encoding='utf-8') as file:
            t: str = re.search(r'\d+', file.readline().replace(' ', '')).group(0)
            d: str = re.search(r'\d+', file.readline().replace(' ', '')).group(0)
        return int(t), int(d)
    
    
    def puzzle2() -> int:
        t, d = create_table_2('day6.txt')
        return get_possible_times_num((t, d))
    
    
    if __name__ == '__main__':
        print(puzzle1())
        print(puzzle2())
    
  • capitalpb@programming.dev
    link
    fedilink
    English
    arrow-up
    3
    ·
    11 months ago

    A nice simple one today. And only a half second delay for part two instead of half an hour. What a treat. I could probably have nicer input parsing, but that seems to be the theme this year, so that will become a big focus of my next round through these I’m guessing. The algorithm here to get the winning possibilities could also probably be improved upon by figuring out what the number of seconds for the current record is, and only looping from there until hitting a number that doesn’t win, as opposed to brute-forcing the whole loop.

    https://github.com/capitalpb/advent_of_code_2023/blob/main/src/solvers/day06.rs

    #[derive(Debug)]
    struct Race {
        time: u64,
        distance: u64,
    }
    
    impl Race {
        fn possible_ways_to_win(&amp;self) -> usize {
            (0..=self.time)
                .filter(|time| time * (self.time - time) > self.distance)
                .count()
        }
    }
    
    pub struct Day06;
    
    impl Solver for Day06 {
        fn star_one(&amp;self, input: &amp;str) -> String {
            let mut race_data = input
                .lines()
                .map(|line| {
                    line.split_once(':')
                        .unwrap()
                        .1
                        .split_ascii_whitespace()
                        .filter_map(|number| number.parse::().ok())
                        .collect::>()
                })
                .collect::>();
    
            let times = race_data.pop().unwrap();
            let distances = race_data.pop().unwrap();
    
            let races = distances
                .into_iter()
                .zip(times)
                .map(|(time, distance)| Race { time, distance })
                .collect::>();
    
            races
                .iter()
                .map(|race| race.possible_ways_to_win())
                .fold(1, |acc, count| acc * count)
                .to_string()
        }
    
        fn star_two(&amp;self, input: &amp;str) -> String {
            let race_data = input
                .lines()
                .map(|line| {
                    line.split_once(':')
                        .unwrap()
                        .1
                        .replace(" ", "")
                        .parse::()
                        .unwrap()
                })
                .collect::>();
    
            let race = Race {
                time: race_data[0],
                distance: race_data[1],
            };
    
            race.possible_ways_to_win().to_string()
        }
    }
    
  • sjmulder@lemmy.sdf.org
    link
    fedilink
    arrow-up
    3
    ·
    edit-2
    11 months ago

    C

    Brute forced it, runs in 60 ms or so. Only shortcut is quitting the loop when the distance drops below the record. I didn’t bother with the closed form solution here because a) it ran so fast and b) I was concerned about floats, rounding and off-by-one errors. Will probably implement it later!

    GitHub link

    Edit: implemented the closed form solution. Feels dirty copying a formula without really understanding it…

    GitHub link (closed form)

  • cvttsd2si@programming.dev
    link
    fedilink
    arrow-up
    3
    ·
    edit-2
    11 months ago

    Scala3

    // math.floor(i) == i if i.isWhole, but we want i-1
    def hardFloor(d: Double): Long = (math.floor(math.nextAfter(d, Double.NegativeInfinity))).toLong
    def hardCeil(d: Double): Long = (math.ceil(math.nextAfter(d, Double.PositiveInfinity))).toLong
    
    def wins(t: Long, d: Long): Long =
        val det = math.sqrt(t*t/4.0 - d)
        val high = hardFloor(t/2.0 + det)
        val low = hardCeil(t/2.0 - det)
        (low to high).size
    
    def task1(a: List[String]): Long = 
        def readLongs(s: String) = s.split(raw"\s+").drop(1).map(_.toLong)
        a match
            case List(s"Time: $time", s"Distance: $dist") => readLongs(time).zip(readLongs(dist)).map(wins).product
            case _ => 0L
    
    def task2(a: List[String]): Long =
        def readLong(s: String) = s.replaceAll(raw"\s+", "").toLong
        a match
            case List(s"Time: $time", s"Distance: $dist") => wins(readLong(time), readLong(dist))
            case _ => 0L
    
  • janAkali@lemmy.one
    link
    fedilink
    English
    arrow-up
    2
    ·
    edit-2
    11 months ago

    Nim

    Today’s puzzle was too easy. I solved it with bruteforce in 20 minutes, but that’s boring. So here’s the optimized solution with quadratic formula.

    Total runtime: 0.008 ms
    Puzzle rating: Too Easy 5/10
    Code: day_06/solution.nim

  • Ananace@lemmy.ananace.dev
    link
    fedilink
    arrow-up
    2
    ·
    11 months ago

    Well, this one ended up being a really nice and terse solution when done naïvely, here with a trimmed snippet from my simple solution;

    Ruby
    puts "Part 1:", @races.map do |race|
      (0..race[:time]).count { |press_dur| press_dur * (race[:time] - press_dur) > race[:distance] }
    end.inject(:*)
    
    full_race_time = @races.map { |r| r[:time].to_s }.join.to_i
    full_race_dist = @races.map { |r| r[:distance].to_s }.join.to_i
    
    puts "Part 2:", (0..full_race_time).count { |press_dur| press_dur * (full_race_time - press_dur) > full_race_dist }
    
  • Ategon@programming.devOPM
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    11 months ago

    [JavaScript] Relatively easy one today

    Paste

    Part 1
    function part1(input) {
      const split = input.split("\n");
      const times = split[0].match(/\d+/g).map((x) => parseInt(x));
      const distances = split[1].match(/\d+/g).map((x) => parseInt(x));
    
      let sum = 0;
    
      for (let i = 0; i &lt; times.length; i++) {
        const time = times[i];
        const recordDistance = distances[i];
    
        let count = 0;
    
        for (let j = 0; j &lt; time; j++) {
          const timePressed = j;
          const remainingTime = time - j;
    
          const travelledDistance = timePressed * remainingTime;
    
          if (travelledDistance > recordDistance) {
            count++;
          }
        }
    
        if (sum == 0) {
          sum = count;
        } else {
          sum = sum * count;
        }
      }
    
      return sum;
    }
    
    Part 2
    function part2(input) {
      const split = input.split("\n");
      const time = parseInt(split[0].split(":")[1].replace(/\s/g, ""));
      const recordDistance = parseInt(split[1].split(":")[1].replace(/\s/g, ""));
    
      let count = 0;
    
      for (let j = 0; j &lt; time; j++) {
        const timePressed = j;
        const remainingTime = time - j;
    
        const travelledDistance = timePressed * remainingTime;
    
        if (travelledDistance > recordDistance) {
          count++;
        }
      }
    
      return count;
    }
    

    Was a bit late with posting the solution thread and solving this since I ended up napping until 2am, if anyone notices theres no solution thread and its after the leaderboard has been filled (can check from the stats page if 100 people are done) feel free to start one up (I just copy paste the text in each of them)

  • abclop99@beehaw.org
    link
    fedilink
    arrow-up
    2
    ·
    11 months ago

    Rust:

    For part 2, all I did was edit the input and change i32 to i64.

    spoiler
    use std::fs;
    use std::path::PathBuf;
    
    use clap::Parser;
    
    #[derive(Parser)]
    #[command(author, version, about, long_about = None)]
    struct Cli {
        input_file: PathBuf,
    }
    
    fn main() {
        // Parse CLI arguments
        let cli = Cli::parse();
    
        // Read file
        let input_text = fs::read_to_string(&amp;cli.input_file)
            .expect(format!("File \"{}\" not found", cli.input_file.display()).as_str());
    
        let input_lines: Vec&lt;&amp;str> = input_text.lines().collect();
    
        let times: Vec = input_lines[0]
            .split_ascii_whitespace()
            .skip(1)
            .map(|s| s.parse().unwrap())
            .collect();
    
        let distances: Vec = input_lines[1]
            .split_ascii_whitespace()
            .skip(1)
            .map(|s| s.parse().unwrap())
            .collect();
    
        println!("{:?}", times);
        println!("{:?}", distances);
    
        let mut product: i64 = 1;
    
        for (time, distance) in times.iter().zip(distances) {
            let mut n = 0;
            for b in 0..*time {
                if time * b - b * b > distance {
                    n += 1;
                }
            }
    
            product *= n;
        }
    
        println!("{}", product)
    }