Discussion on: Advent of Code 2020 Solution Megathread - Day 13: Shuttle Search

[pepa65]

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