I don't know about those theorems. It's a prime factorisation problem (and evidently all bus numbers are prime numbers, so that makes it even easier). My Ruby solution is general purpose (so also non-prime busses) but π€·
require'prime'require'benchmark'source='input.txt'timestamp,schedule_line=File.readlines(source)schedule=schedule_line.split(',').map{|x|x.chomp}busses=schedule.each_with_index.map{|bus,offset|bus!='x'?[bus.to_i,offset]:nil}.compactcurrent_timestamp=0# This is unnecessary because all bus numbers are prime numbers, but this more# general solution works for busses that are non-prime!## In this exercise, the result is an array with one element: the first bus number:# [7]timestamp_factors=busses.shift.first.prime_division.map(&:first)Benchmark.bmdo|x|x.reportdobusses.eachdo|(bus,offset)|# The first bus will depart at t + 0 every t = bus * i. In fact, for any bus it's# true that once you find a valid t where t + offset = bus * i, the next# valid t for that bus is (t + bus).## So you can skip all the ts inbetween.skip_factor=timestamp_factors.inject(&:*)# Find the next t for which [t + offset = bus * i].loopdominutes_to_departure=bus-(current_timestamp%bus)breakifminutes_to_departure==offset%buscurrent_timestamp+=skip_factorend# If all busses are prime numbers (they are in AoC), the prime-only# solution would be:## timestamp_factors.push(bus)## The general purpose solution looks like this:timestamp_factors.push(*bus.prime_division.map(&:first))timestamp_factors.uniq!endendendputscurrent_timestamp
Thanks for this. I was really stuck on this; came on here and saw folks mentioning a new theory (which bummed me out). I had been trying to figure something out with LCM, and your solution showed me what I'd been missing. Here's the core of mine:
current_timestamp=ids.first.firstids.each_with_indexdo|(bus_id,offset),index|nextifindex==0# At this point, we start off with a t that's valid for bus 1# Second iteration will add the period (bus 1's cycle) to t until it finds a valid t# Subsequent iterations will add the period (LCM of already found numbers)# Why does this work? Because the cycle repeats over the period.# So, if we've found a t that has b2 and b1 at certain positions,# Then using a period of lcm(b1, b2) will have them in the same positions again. (LCM == coinciding cycles)# So we just need to do this until we find where position(b3) = position(b2) + offset# Then update our period and go again for the next bus.period=ids[0..index-1].reduce(1){|acc,(id,_)|acc.lcm(id)}loopdodifference=bus_id-(current_timestamp%bus_id)breakifdifference==(offset%bus_id)current_timestamp+=periodendendpcurrent_timestamp
No way I could figure out part 2 without googling. I was playing around with least common divisor + gcd + clever looping. Finally googling around I found the chinese remainder theorem.
rust rust rust :)
usestd::usize::MAX;usestd::collections::HashMap;#[aoc(day13,part1)]fnbus_wait_time(input:&(usize,HashMap<usize,usize>))->usize{lettime=input.0;letbusses=&input.1;letmutmin_time=MAX;letmutbest_bus_id=0;for(&i,bus)inbusses.iter(){letr=time%*bus;letwaiting=*bus+time-r;ifwaiting<min_time{min_time=waiting;best_bus_id=i;}}busses[&best_bus_id]*(min_time-time)}#[aoc(day13,part2)]fnmagic_timestamp(input:&(usize,HashMap<usize,usize>))->usize{letmutbuses:Vec<(usize,usize)>=input.1.iter().map(|(&pos,&id)|(pos,id)).collect();buses.sort_by(|a,b|a.0.partial_cmp(&b.0).unwrap());letmuttimestamp=0;letmutinc=buses[0].1;for&(i,bus)in&buses[1..]{// friggin CRT sieve garbage see: https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Computationwhile(timestamp+i)%bus!=0{timestamp+=inc;}// adjust for the next moduloinc*=bus;}timestamp}
I'm a Staff Software Engineer at Cisco. I specialize in Python and Go, building functional, practical, and maintainable web systems leveraging Kubernetes and the cloud. Blog opinions are my own.
I feel really, really proud of myself for coming up with a fast algorithm for this pretty much on my own with no cheating. The only thing I'll say is that I saw other people commenting about prime numbers, which led me down the right track. I've got it commented in part two down in the code, but essentially, if you try to get each bus to fall into step incrementally, and you multiply your timestep by each found bus's ID, you can keep pace with the complexity of the problem for an arbitrary number of input busses. It's because, since the inputs are prime, they would only coincide on a number where they are multiplied together, and the same relationship applies even if you shift the second one by one.
As I write this, I know it doesn't make any sense, but just take a look at the code and see if that helps at all.
Woohoo!
#include "Day13.h"
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
/// Day 13: Shuttle Search////// Plan your trip based on regularly timed intersecting shuttle departures./// A simple bus schedule for a fleet of busses.typedefstruct{intearliest;///< The earliest possible timestep you could departint*ids;///< List of Bus ID's (which are also their frequencies)intcount;///< The number of busses}BusSchedule;/// Parse the input file:/// First line is just the earliest timestep we could leave./// Second line consists of integer bus ID's separated by commasBusScheduleparse(constchar*filename){FILE*fp;fp=fopen(filename,"r");if(fp==NULL){printf("Couldn't open file.\n");exit(EXIT_FAILURE);}BusScheduleschedule={0};fscanf(fp,"%d\n",&schedule.earliest);charline[255]={0};fscanf(fp,"%s",line);fclose(fp);// Count and allocate the ID'sintcount=0;for(inti=0;line[i];i++){if(line[i]==',')count++;}count++;schedule.ids=(int*)malloc(sizeof(int)*count);// Split, parse, and store them.inti=0;char*token=strtok(line,",");while(token!=NULL){schedule.ids[i]=atoi(token);token=strtok(NULL,",");i++;}schedule.count=count;returnschedule;}voidfree_bus_schedule(BusSchedule*schedule){free(schedule->ids);// Don't free schedule because it's on the stack}/// What is the ID of the bus who leaves soonest after you get there/// multiplied by the amount of minutes you'll be waiting for it?intpart1(constchar*filename){BusScheduleschedule=parse(filename);intbest_bus_id=0;intbest_wait_time=INT_MAX;for(inti=0;i<schedule.count;i++){if(schedule.ids[i]==0)continue;intwait=schedule.ids[i]-(schedule.earliest%schedule.ids[i]);if(wait<best_wait_time){best_wait_time=wait;best_bus_id=schedule.ids[i];}}free_bus_schedule(&schedule);returnbest_bus_id*best_wait_time;}/// A bus schedule for the contest to see who can calculate the timestep/// where the first bus ID leaves and every subsequent nth bus leaves/// on the subsequent nth timestep. X's don't matter.typedefstruct{int*ids;///< List of the bus id'sint*offsets;///< List of time offsets (i.e. bus `i` should leave at time `t + i`)intcount;///< Number of busses (that we care about, not X's)}ContestBusSchedule;/// Parse the input file (same format as part 1) into a ContestBusSchedule.ContestBusScheduleparse2(constchar*filename){FILE*fp;fp=fopen(filename,"r");if(fp==NULL){printf("Couldn't open file.\n");exit(EXIT_FAILURE);}ContestBusScheduleschedule={0};charnonsense[25];fgets(nonsense,25,fp);charline[255]={0};fscanf(fp,"%s",line);fclose(fp);// Count and allocate the ID'sintcount=0;for(inti=0;line[i];i++){if(line[i]==','&&line[i-1]!='x')count++;}count++;schedule.count=count;schedule.ids=(int*)malloc(sizeof(int)*count);schedule.offsets=(int*)malloc(sizeof(int)*count);// Split, parse, and store them.inti=0;intoffset=0;char*token=strtok(line,",");while(token!=NULL){if(*token=='x'){token=strtok(NULL,",");offset++;continue;}schedule.ids[i]=atoi(token);schedule.offsets[i]=offset;token=strtok(NULL,",");offset++;i++;}returnschedule;}/// Find the earliest time `t` that satisfies the requirements discussed/// above in the `ContestBusSchedule`.////// The trick is that for every [0..i] subset of the numbers, their intersection/// repeats every (PRODUCT(numbers[0..i])) minutes. So my algorithm/// is to roll it up:/// Start by finding the intersection of the first two numbers where/// bus 0 departs at t and bus 1 departs at t + 1. From then on,/// a timestep of bus0 * bus1 will guarantee that all times conform/// to the same relationship between bus0 and bus1. Then you can look for/// an instance where bus2 appears at t + 2. Then adjust timestep to/// bus0 * bus1 * bus2.////// Lather, rinse, repeat, continuously growing your timestep so that/// you're always only really looking for one more number to line up/// which should be pretty quick.////// You're only guaranteed the earliest `t` because all numbers in the/// input file are prime. Otherwise, it could happen a multiple of one of/// the non-prime buses earlier.longpart2(constchar*filename){ContestBusScheduleschedule=parse2(filename);longstep=schedule.ids[0];intsearch_idx=1;for(longt=step;t<LONG_MAX;t+=step){boolsuccess=true;for(inti=0;i<=search_idx;i++){if((t+schedule.offsets[i])%schedule.ids[i]!=0){success=false;break;}}if(success&&search_idx==schedule.count-1)returnt;if(success){step*=schedule.ids[search_idx];search_idx++;}}return-1;}/// Run both parts.intday13(){printf("====== Day 13 ======\n");printf("Part 1: %d\n",part1("data/day13.txt"));printf("Part 2: %ld\n",part2("data/day13.txt"));returnEXIT_SUCCESS;}
More efficient if list of buses was ordered from highest to lowest, the iterator would be the necessary remainder of the first bus, the increment would be the first bus and the first element of the list wouldn't be iterated
OK, I just discovered AoC, more than a month late... This one had me stumped, I took it from the hints that it should be brute-forceable, but it just took too long. Then I saw this video that inspired me to try to construct a solution one bus id by one, and once I did that modulo the product of all the bus id's, it was correct! In Odin (which I am trying to learn for this occasion): [edit: after modification, the modulo on the endresult is no longer needed]
package day13
import "core:os"
import "core:strings"
import "core:strconv"
import "core:fmt"
main:: proc() {
file,_:= os.read_entire_file("day13.txt");
lines:= strings.split(string(file),"\n");
timestamp:= strconv.atoi(lines[0]);
buses:= strings.split(lines[1],",");
lowest,id,nreq,prod:= 999999999,0,0,1;
for bus in buses do if bus[0] != 'x' {
nreq+= 1;
i:= strconv.atoi(bus);
prod*= i;
wait:= i-timestamp%i;
if wait < lowest do lowest,id= wait,i;
}
fmt.println(lowest*id);
reqs:= make(map[int]int,nreq);
for bus,min in buses do if bus[0] != 'x' do reqs[min]= strconv.atoi(bus);
time,step:= 0,1;
for min,id in reqs {
for id-time%id != (min == 0 ? id : min%id) do time+= step;
//fmt.println(id,min,step,time);
step*= id;
}
fmt.println(time);
}
I admit I tried to brute force part 2 at first, then had to think about it. The solution was quite neat in the end and runs in 4 milliseconds.
usestd::fs::File;usestd::io::prelude::*;useparser::*;// --- file readfnread_file(filename:&str)->std::io::Result<String>{letmutfile=File::open(filename)?;letmutcontents=String::new();file.read_to_string(&mutcontents)?;Ok(contents)}// -- modeltypeTimestamp=i64;typeBusID=i64;structInput{estimate:Timestamp,bus_ids:Vec<Option<BusID>>}implFrom<&str>forInput{fnfrom(s:&str)->Self{letbus_id=either(match_literal("x").means(None),integer.map(Option::Some));letbus_ids=bus_id.sep_by(match_literal(","));letinput=pair(whitespace_wrap(integer),bus_ids,|estimate,bus_ids|Input{estimate,bus_ids});input.parse(s).unwrap().1}}// --- problemsimplInput{fnnext_bus_departing(&self)->Option<(BusID,Timestamp)>{self.bus_ids.iter().filter_map(|maybe_id|*maybe_id).map(|id|(id,id-(self.estimate%id))).min_by_key(|(_id,wait_time)|*wait_time)}fnbus_ids_with_departure_offsets(&self)->implIterator<Item=(BusID,Timestamp)>+'_{// find the valid bus IDs and pair them with their position in the // list, which equates to the departure offset in minutesself.bus_ids.iter().enumerate().filter_map(|(index,maybe_id)|maybe_id.map(|id|(id,indexasTimestamp)))}fnfind_first_aligned_timestamp(&self,after:Timestamp)->Timestamp{// for each bus, find a new base timestamp after the current timestamp at which// the bus leaves (subject to its indexed departure offset), and a repetition period// which is true for all buses examined so far// (the period is a product of all bus ids, which passes all tests and finds// the right answer, but technically it should only count common factors once each;// this is possibly a deliberate design of the input data to make the problem// easier - thay do all seem to be primes)self.bus_ids_with_departure_offsets().fold((after,1),|(base_timestamp,period),(bus_id,offset)|(0..).find_map(|i|{lettimestamp=base_timestamp+i*period;if(timestamp+offset)%bus_id==0{Some((timestamp,period*bus_id))}else{None}}).unwrap()).0}}fnpart1(input:&Input)->Option<i64>{input.next_bus_departing().map(|(id,wait)|id*wait)}fnpart2(input:&Input)->Timestamp{input.find_first_aligned_timestamp(100000000000000)}fnmain(){letinput=Input::from(read_file("./input.txt").unwrap().as_str());println!("part1 {:?}",part1(&input));println!("part2 {:?}",part2(&input));}#[cfg(test)]modtests{usesuper::*;#[test]fntest_parser(){letinput=Input::from("939\n7,13,x,x,59,x,31,19");assert_eq!(input.estimate,939);assert_eq!(input.bus_ids,vec![Some(7),Some(13),None,None,Some(59),None,Some(31),Some(19)]);}#[test]fntest_next_bus_departing(){letinput=Input::from("939\n7,13,x,x,59,x,31,19");assert_eq!(input.next_bus_departing(),Some((59,5)));}#[test]fntest_find_first_aligned_timestamp_1(){letinput=Input::from("939\n7,13,x,x,59,x,31,19");assert_eq!(input.find_first_aligned_timestamp(1000000),1068781);}#[test]fntest_find_first_aligned_timestamp_2(){letinput=Input::from("0\n17,x,13,19");assert_eq!(input.find_first_aligned_timestamp(0),3417);}#[test]fntest_find_first_aligned_timestamp_3(){letinput=Input::from("0\n67,7,59,61");assert_eq!(input.find_first_aligned_timestamp(0),754018);}#[test]fntest_find_first_aligned_timestamp_4(){letinput=Input::from("0\n67,x,7,59,61");assert_eq!(input.find_first_aligned_timestamp(0),779210);}#[test]fntest_find_first_aligned_timestamp_5(){letinput=Input::from("0\n67,7,x,59,61");assert_eq!(input.find_first_aligned_timestamp(0),1261476);}#[test]fntest_find_first_aligned_timestamp_6(){letinput=Input::from("0\n1789,37,47,1889");assert_eq!(input.find_first_aligned_timestamp(0),1202161486);}}
Only going to post my part 1 solution here, as I cheated and read through the thread in order to figure out part 2. Looking back, the brute force solution would have taken quite a while to show up; glad I didn't just "set and forget."
Well today's AOC 2020 was interesting, initally I thought it was going to be very straightforward, but that turned out not to be the case. Part 1 I could just do by force, but I got very stuck on part 2, as it was going to take a very long time :-) So after some pointers on reddit I ended up learning a new bit of number theory to make it work, utlizing a extended GCD from stack overflow.
Once I knew about that, it was a lot easier, not to mention quicker:
I don't know about those theorems. It's a prime factorisation problem (and evidently all bus numbers are prime numbers, so that makes it even easier). My Ruby solution is general purpose (so also non-prime busses) but π€·
Thanks for this. I was really stuck on this; came on here and saw folks mentioning a new theory (which bummed me out). I had been trying to figure something out with LCM, and your solution showed me what I'd been missing. Here's the core of mine:
No way I could figure out part 2 without googling. I was playing around with least common divisor + gcd + clever looping. Finally googling around I found the chinese remainder theorem.
rust rust rust :)
Man, this turned out really concise. Also, thank you for letting me shamelessly steal your logic for part 2 :D
I feel really, really proud of myself for coming up with a fast algorithm for this pretty much on my own with no cheating. The only thing I'll say is that I saw other people commenting about prime numbers, which led me down the right track. I've got it commented in part two down in the code, but essentially, if you try to get each bus to fall into step incrementally, and you multiply your timestep by each found bus's ID, you can keep pace with the complexity of the problem for an arbitrary number of input busses. It's because, since the inputs are prime, they would only coincide on a number where they are multiplied together, and the same relationship applies even if you shift the second one by one.
As I write this, I know it doesn't make any sense, but just take a look at the code and see if that helps at all.
Woohoo!
I worked out the algorithm on my own with no googling too. We should get extra stars!
Solution of Part 2 in Python
More efficient if list of buses was ordered from highest to lowest, the iterator would be the necessary remainder of the first bus, the increment would be the first bus and the first element of the list wouldn't be iterated
OK, I just discovered AoC, more than a month late... This one had me stumped, I took it from the hints that it should be brute-forceable, but it just took too long. Then I saw this video that inspired me to try to construct a solution one bus id by one, and once I did that modulo the product of all the bus id's, it was correct! In Odin (which I am trying to learn for this occasion): [edit: after modification, the modulo on the endresult is no longer needed]
Staying true to COBOL
I admit I tried to brute force part 2 at first, then had to think about it. The solution was quite neat in the end and runs in 4 milliseconds.
Only going to post my part 1 solution here, as I cheated and read through the thread in order to figure out part 2. Looking back, the brute force solution would have taken quite a while to show up; glad I didn't just "set and forget."
Anyway, part 1 in Rust. As always, on Github.
Well today's AOC 2020 was interesting, initally I thought it was going to be very straightforward, but that turned out not to be the case. Part 1 I could just do by force, but I got very stuck on part 2, as it was going to take a very long time :-) So after some pointers on reddit I ended up learning a new bit of number theory to make it work, utlizing a extended GCD from stack overflow.
Once I knew about that, it was a lot easier, not to mention quicker: