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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- 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
[Language: Lean4]
This one was straightforward, especially since Lean’s Floats are 64bits. There is one interesting piece in the solution though, and that’s the function that combines two integers, which I wrote because I want to use the same parse function for both parts. This
combineNumbers
function is interesting, because it needs a proof of termination to make the Lean4 compiler happy. Or, in other words, the compiler needs to be told that if n is larger than 0, n/10 is a strictly smaller integer than n. That proof actually exists in Lean’s standard library, but the compiler doesn’t find it by itself. Supplying it is as easy as invoking thesimp
tactic with that proof, and a proof that n is larger than 0.As with the previous days, I won’t post the full source here, just the relevant parts. The full solution is on github, including the main function of the program, that loads the input file and runs the solution.
Solution
structure Race where timeLimit : Nat recordDistance : Nat deriving Repr private def parseLine (header : String) (input : String) : Except String (List Nat) := do if not $ input.startsWith header then throw s!"Unexpected line header: {header}, {input}" let input := input.drop header.length |> String.trim let numbers := input.split Char.isWhitespace |> List.map String.trim |> List.filter (not ∘ String.isEmpty) numbers.mapM $ Option.toExcept s!"Failed to parse input line: Not a number {input}" ∘ String.toNat? def parse (input : String) : Except String (List Race) := do let lines := input.splitOn "\n" |> List.map String.trim |> List.filter (not ∘ String.isEmpty) let (times, distances) ← match lines with | [times, distances] => let times ← parseLine "Time:" times let distances ← parseLine "Distance:" distances pure (times, distances) | _ => throw "Failed to parse: there should be exactly 2 lines of input" if times.length != distances.length then throw "Input lines need to have the same number of, well, numbers." let pairs := times.zip distances if pairs = [] then throw "Input does not have at least one race." return pairs.map $ uncurry Race.mk -- okay, part 1 is a quadratic equation. Simple as can be -- s = v * tMoving -- s = tPressed * (tLimit - tPressed) -- (tPressed - tLimit) * tPressed + s = 0 -- tPressed² - tPressed * tLimit + s = 0 -- tPressed := tLimit / 2 ± √(tLimit² / 4 - s) -- beware: We need to _beat_ the record, so s here is the record + 1 -- Inclusive! This is the smallest number that can win, and the largest number that can win private def Race.timeRangeToWin (input : Race) : (Nat × Nat) := let tLimit := input.timeLimit.toFloat let sRecord := input.recordDistance.toFloat let tlimitHalf := 0.5 * tLimit let theRoot := (tlimitHalf^2 - sRecord - 1.0).sqrt let lowerBound := tlimitHalf - theRoot let upperBound := tlimitHalf + theRoot let lowerBound := lowerBound.ceil.toUInt64.toNat let upperBound := upperBound.floor.toUInt64.toNat (lowerBound,upperBound) def part1 (input : List Race) : Nat := let limits := input.map Race.timeRangeToWin let counts := limits.map $ λ p ↦ p.snd - p.fst + 1 -- inclusive range counts.foldl (· * ·) 1 -- part2 is the same thing, but here we need to be careful. -- namely, careful about the precision of Float. Which luckily is enough, as confirmed by pen&paper -- but _barely_ enough. -- If Lean's Float were an actual C float and not a C double, this would not work. -- we need to concatenate the numbers again (because I don't want to make a separate parse for part2) private def combineNumbers (left : Nat) (right : Nat) : Nat := let rec countDigits := λ (s : Nat) (n : Nat) ↦ if p : n > 0 then have : n > n / 10 := by simp[p, Nat.div_lt_self] countDigits (s+1) (n/10) else s let d := if right = 0 then 1 else countDigits 0 right left * (10^d) + right def part2 (input : List Race) : Nat := let timeLimits := input.map Race.timeLimit let timeLimit := timeLimits.foldl combineNumbers 0 let records := input.map Race.recordDistance let record := records.foldl combineNumbers 0 let limits := Race.timeRangeToWin $ {timeLimit := timeLimit, recordDistance := record} limits.snd - limits.fst + 1 -- inclusive range open DayPart instance : Parse ⟨6, by simp⟩ (ι := List Race) where parse := parse instance : Part ⟨6, _⟩ Parts.One (ι := List Race) (ρ := Nat) where run := some ∘ part1 instance : Part ⟨6, _⟩ Parts.Two (ι := List Race) (ρ := Nat) where run := some ∘ part2
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.
Hi there! Looks like you linked to a Lemmy community using a URL instead of its name, which doesn’t work well for people on different instances. Try fixing it like this: !nim@programming.dev
[JavaScript] Relatively easy one today
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 < times.length; i++) { const time = times[i]; const recordDistance = distances[i]; let count = 0; for (let j = 0; j < 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 < 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)
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!
Should you be using
SCNi64
instead ofPRIi64
insscanf
?
Not sure if it’s the most optimal, but I figured it’s probably quicker to calculate the first point when you start winning, and then reverse it to get the last point when you’ll last win. Subtracting the two to get the total number of ways to win.
Takes about 3 seconds to run on the real input
Python Solution
class Race: def __init__(self, time, distance): self.time = time self.distance = distance def get_win(self, start, stop, step): for i in range(start, stop, step): if (self.time - i) * i > self.distance: return i def get_winners(self): return ( self.get_win(0, self.time, 1), self.get_win(self.time, 0, -1), ) race = Race(71530, 940200) winners = race.get_winners() print(winners[1] - winners[0] + 1)
Crystal
# part 1 times = input[0][5..].split.map &.to_i dists = input[1][9..].split.map &.to_i prod = 1 times.each_with_index do |time, i| start, last = find_poss(time, dists[i]) prod *= last - start + 1 end puts prod # part 2 time = input[0][5..].chars.reject!(' ').join.to_i64 dist = input[1][9..].chars.reject!(' ').join.to_i64 start, last = find_poss(time, dist) puts last - start + 1 def find_poss(time, dist) start = 0 last = 0 (1...time).each do |acc_time| if (time-acc_time)*acc_time > dist start = acc_time break end end (1...time).reverse_each do |acc_time| if (time-acc_time)*acc_time > dist last = acc_time break end end {start, last} end
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
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 }
I’m no rust expert, but:
you can use
into_iter()
instead ofiter()
to get owned data (if you’re not going to use the original container again). Withinto_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) whenlines()
returns an iterator that you can use directly. You can instead passlines.next().unwrap()
into your functions directly.Strings have a method called
split_whitespace()
(also asplit_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.Somewhere on the way you seem to have converted ampersands to HTML entities :)
It’s caused by lemmy code blocks. They don’t handle
&
correctly. See.Ah. Never noticed that before :)
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
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.nimC++
Yesterday, I decided to code in Tcl. That program is still running, i will go back to the day 5 post once it finishes :)
Today was super simple. My first attempt worked in both cases, where the hardest part was really switching my ints to long longs. Part 1 worked on first compile and part 2 I had to compile twice after I realized the data type needs. Still, that change was made by search and replace.
I guess today was meant to be a real time race to get first answer? This is like day 1 stuff! Still, I have kids and a job so I did not get to stay up until the problem was posted.
I used C++ because I thought something intense may be coming on the part 2 problem, and I was burned yesterday. It looks like I spent another fast language on nothing! I think I’ll keep zig in the hole for the next number cruncher.
Oh, and yes my TCL program is still running…
My solutions can be found here:
// File: day-6a.cpp // Purpose: Solution to part of day 6 of advent of code in C++ // https://adventofcode.com/2023/day/6 // Author: Robert Lowe // Date: 6 December 2023 #include <iostream> #include <vector> #include <string> #include <sstream> std::vector<int> parse_line() { std::string line; std::size_t index; int num; std::vector<int> result; // set up the stream std::getline(std::cin, line); index = line.find(':'); std::istringstream is(line.substr(index+1)); while(is>>num) { result.push_back(num); } return result; } int count_wins(int t, int d) { int count=0; for(int i=1; i<t; i++) { if(t*i-i*i > d) { count++; } } return count; } int main() { std::vector<int> time; std::vector<int> dist; int product=1; // get the times and distances time = parse_line(); dist = parse_line(); // count the total number of wins for(auto titr=time.begin(), ditr=dist.begin(); titr!=time.end(); titr++, ditr++) { product *= count_wins(*titr, *ditr); } std::cout << product << std::endl; }
// File: day-6b.cpp // Purpose: Solution to part 2 of day 6 of advent of code in C++ // https://adventofcode.com/2023/day/6 // Author: Robert Lowe // Date: 6 December 2023 #include <iostream> #include <vector> #include <string> #include <sstream> #include <algorithm> #include <cctype> std::vector<long long> parse_line() { std::string line; std::size_t index; long long num; std::vector<long long> result; // set up the stream std::getline(std::cin, line); line.erase(std::remove_if(line.begin(), line.end(), isspace), line.end()); index = line.find(':'); std::istringstream is(line.substr(index+1)); while(is>>num) { result.push_back(num); } return result; } long long count_wins(long long t, long long d) { long long count=0; for(long long i=1; i<t; i++) { if(t*i-i*i > d) { count++; } } return count; } int main() { std::vector<long long> time; std::vector<long long> dist; long long product=1; // get the times and distances time = parse_line(); dist = parse_line(); // count the total number of wins for(auto titr=time.begin(), ditr=dist.begin(); titr!=time.end(); titr++, ditr++) { product *= count_wins(*titr, *ditr); } std::cout << product << std::endl; }
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.
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.
Factor on github (with comments and imports):
I didn’t use any math smarts.
: input>data ( -- races ) "vocab:aoc-2023/day06/input.txt" utf8 file-lines [ ": " split harvest rest [ string>number ] map ] map first2 zip ; : go ( press-ms total-time -- distance ) over - * ; : beats-record? ( press-ms race -- ? ) [ first go ] [ last ] bi > ; : ways-to-beat ( race -- n ) dup first [1..b) [ over beats-record? ] map [ ] count nip ; : part1 ( -- ) input>data [ ways-to-beat ] map-product . ; : input>big-race ( -- race ) "vocab:aoc-2023/day06/input.txt" utf8 file-lines [ ":" split1 nip " " without string>number ] map ; : part2 ( -- ) input>big-race ways-to-beat . ;
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(&self) -> usize { (0..=self.time) .filter(|time| time * (self.time - time) > self.distance) .count() } } pub struct Day06; impl Solver for Day06 { fn star_one(&self, input: &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(&self, input: &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() } }
That was so much better than yesterday. Went with algebra but looks like brute force would have worked.
python
import re import argparse import math # i feel doing this with equations is probably the # "fast" way. # we can re-arange stuff so we only need to find the point # the line crosses the 0 line # distance is speed * (time less time holding the button (which is equal to speed)): # -> d = v * (t - v) # -> v^2 -vt +d = 0 # -> y=0 @ v = t +- sqrt( t^2 - 4d) / 2 def get_cross_points(time:int, distance:int) -> list | None: pre_root = time**2 - (4 * distance) if pre_root < 0: # no solutions return None if pre_root == 0: # one solution return [(float(time)/2)] sqroot = math.sqrt(pre_root) v1 = (float(time) + sqroot)/2 v2 = (float(time) - sqroot)/2 return [v1,v2] def float_pair_to_int_pair(a:float,b:float): # if floats are equal to int value, then we need to add one to value # as we are looking for values above 0 point if a > b: # lower a and up b if a == int(a): a -= 1 if b == int(b): b += 1 return [math.floor(a),math.ceil(b)] if a < b: if a == int(a): a += 1 if b == int(b): b -= 1 return [math.floor(b),math.ceil(a)] def main(line_list: list): time_section,distance_section = line_list if (args.part == 1): time_list = filter(None , re.split(' +',time_section.split(':')[1])) distance_list = filter(None , re.split(' +',distance_section.split(':')[1])) games = list(zip(time_list,distance_list)) if (args.part == 2): games = [ [time_section.replace(' ','').split(':')[1],distance_section.replace(' ','').split(':')[1]] ] print (games) total = 1 for t,d in games: cross = get_cross_points(int(t),int(d)) cross_int = float_pair_to_int_pair(*cross) print (cross_int) total *= cross_int[0] - cross_int[1] +1 print(f"total: {total}") if __name__ == "__main__": parser = argparse.ArgumentParser(description="day 6 solver") parser.add_argument("-input",type=str) parser.add_argument("-part",type=int) args = parser.parse_args() filename = args.input if filename == None: parser.print_help() exit(1) file = open(filename,'r') main([line.rstrip('\n') for line in file.readlines()]) file.close()