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

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 }
  .compact

current_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.bm do |x|
  x.report do
    busses.each do |(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].
      loop do
        minutes_to_departure = bus - (current_timestamp % bus)
        break if minutes_to_departure == offset % bus
        current_timestamp += skip_factor
      end

      # 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!
    end
  end
end

puts current_timestamp

const fs = require("fs");
let data = fs.readFileSync("input.txt", "utf8").split("\n")
let num = Number(data[0]);
let busnumbers = data[1].split(",").filter(e => e != "x").map(e => Number(e));
const dospecial = i => {
    let specialnum = busnumbers.map(e => {
        if (((num + i) % e) == 0) {
            return e * ((num + i) - num);
        }
    }).filter(e => e)
    return specialnum;
}
for (let i = 0; true; i++) {
    let specialnum = dospecial(i)
    if (specialnum.length) {
        console.log(specialnum[0])
        break;
    }
}

use std::usize::MAX;
use std::collections::HashMap;

#[aoc(day13, part1)]
fn bus_wait_time(input: &(usize, HashMap<usize, usize>)) -> usize {
    let time = input.0;
    let busses = &input.1;
    let mut min_time = MAX;
    let mut best_bus_id = 0;
    for (&i, bus) in busses.iter() {
        let r = time % *bus;
        let waiting = *bus + time - r;
        if waiting < min_time {
            min_time = waiting;
            best_bus_id = i;
        }
    }
    busses[&best_bus_id] * (min_time - time)
}

#[aoc(day13, part2)]
fn magic_timestamp(input: &(usize, HashMap<usize, usize>)) -> usize {
    let mut buses:Vec<(usize, usize)> = input.1.iter().map(|(&pos, &id)| (pos, id)).collect();
    buses.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
    let mut timestamp = 0;
    let mut inc = buses[0].1;
    for &(i, bus) in &buses[1..] {
        // friggin CRT sieve garbage see: https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Computation
        while (timestamp + i) % bus != 0 {
            timestamp += inc;
        }
        // adjust for the next modulo
        inc *= bus;
    }
    timestamp
}

def part2(buses):
    mods = {}
    for idx, bus in enumerate(buses):
        if bus != 'x':
            mods[bus] = -idx % bus

    iterator = 0
    increment = 1
    for bus in mods.keys():
        while iterator % bus != mods[bus]:
            iterator += increment
        increment *= bus

    return iterator

#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.
typedef struct {
  int earliest;   ///< The earliest possible timestep you could depart
  int* ids;       ///< List of Bus ID's (which are also their frequencies)
  int count;      ///< 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 commas
BusSchedule parse(const char* filename) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open file.\n");
    exit(EXIT_FAILURE);
  }

  BusSchedule schedule = {0};
  fscanf(fp, "%d\n", &schedule.earliest);

  char line[255] = {0};
  fscanf(fp, "%s", line);
  fclose(fp);

  // Count and allocate the ID's
  int count = 0;
  for (int i = 0; line[i]; i++) {
    if (line[i] == ',') count++;
  }
  count++;
  schedule.ids = (int*)malloc(sizeof(int) * count);

  // Split, parse, and store them.
  int i = 0;
  char* token = strtok(line, ",");
  while (token != NULL) {
    schedule.ids[i] = atoi(token);
    token = strtok(NULL, ",");
    i++;
  }
  schedule.count = count;
  return schedule;
}

void free_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?
int part1(const char* filename) {
  BusSchedule schedule = parse(filename);

  int best_bus_id = 0;
  int best_wait_time = INT_MAX;

  for (int i = 0; i < schedule.count; i++) {
    if (schedule.ids[i] == 0) continue;
    int wait =  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);
  return best_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.
typedef struct {
  int* ids;       ///< List of the bus id's
  int* offsets;   ///< List of time offsets (i.e. bus `i` should leave at time `t + i`)
  int count;      ///< Number of busses (that we care about, not X's)
} ContestBusSchedule;

/// Parse the input file (same format as part 1) into a ContestBusSchedule.
ContestBusSchedule parse2(const char* filename) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open file.\n");
    exit(EXIT_FAILURE);
  }

  ContestBusSchedule schedule = {0};
  char nonsense[25];
  fgets(nonsense, 25, fp);

  char line[255] = {0};
  fscanf(fp, "%s", line);
  fclose(fp);

  // Count and allocate the ID's
  int count = 0;
  for (int i = 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.
  int i = 0;
  int offset = 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++;
  }

  return schedule;
}

/// 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.
long part2(const char* filename) {
  ContestBusSchedule schedule = parse2(filename);

  long step = schedule.ids[0];
  int search_idx = 1;
  for (long t = step; t < LONG_MAX; t += step) {
    bool success = true;
    for (int i = 0; i <= search_idx; i++) {
      if ((t + schedule.offsets[i]) % schedule.ids[i] != 0) {
        success = false;
        break;
      }
    }
    if (success && search_idx == schedule.count - 1) return t;
    if (success) {
      step *= schedule.ids[search_idx];
      search_idx++;
    }
  }
  return -1;
}

/// Run both parts.
int day13() {
  printf("====== Day 13 ======\n");
  printf("Part 1: %d\n", part1("data/day13.txt"));
  printf("Part 2: %ld\n", part2("data/day13.txt"));
  return EXIT_SUCCESS;
}

use aoc_runner_derive::{aoc, aoc_generator};

#[derive(Debug, Clone)]
struct Bus {
    interval: u128,
    last_pickup: u128,
}

#[derive(Clone)]
struct Timetable {
    depart: usize,
    buses: Vec<Option<Bus>>,
}

impl Bus {
    fn new(interval: u128) -> Bus {
        Bus {
            interval,
            last_pickup: 0,
        }
    }
}
impl Iterator for Bus {
    type Item = u128;
    fn next(&mut self) -> Option<u128> {
        self.last_pickup += self.interval as u128;
        Some(self.last_pickup)
    }
}

#[aoc_generator(day13)]
fn parse_input_day13(input: &str) -> Timetable {
    let lines: Vec<&str> = input.lines().collect();
    let approximate_departure = str::parse(lines.get(0).unwrap());
    let buses = lines.get(1).unwrap().split(",");
    Timetable {
        depart: approximate_departure.unwrap(),
        buses: buses
            .map(|b| {
                match b {
                    "x" => {
                        // Skip out-of-service buses
                        None
                    }
                    _ => Some(Bus::new(str::parse(b).unwrap())),
                }
            })
            .collect(),
    }
}

#[aoc(day13, part1)]
fn find_next_bus(root_input: &Timetable) -> u128 {
    let input = root_input.clone();
    let next_bus = input
        .buses
        .iter()
        .filter_map(|b| match b.as_ref() {
            None => None,
            Some(bus) => Some(Bus {
                interval: bus.interval,
                last_pickup: bus
                    .clone()
                    .take_while(|t| *t < input.depart as u128 + bus.interval)
                    .last()
                    .unwrap(),
            }),
        })
        .min_by(|bus1, bus2| bus1.last_pickup.cmp(&bus2.last_pickup))
        .unwrap();

    println!("{:?}", next_bus);
    next_bus.interval as u128 * (next_bus.last_pickup - input.depart as u128)
}

use std::fs::File;
use std::io::prelude::*;
use parser::*;

// --- file read

fn read_file(filename: &str) -> std::io::Result<String> {
    let mut file = File::open(filename)?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    Ok(contents)
}

// -- model

type Timestamp = i64;
type BusID = i64;

struct Input {
    estimate: Timestamp,
    bus_ids: Vec<Option<BusID>>
}

impl From<&str> for Input {
    fn from(s: &str) -> Self {
        let bus_id = either(
            match_literal("x").means(None),
            integer.map(Option::Some)
        );

        let bus_ids = bus_id.sep_by(match_literal(","));

        let input = pair(whitespace_wrap(integer), bus_ids,
            |estimate, bus_ids| Input { estimate, bus_ids }
        );

        input.parse(s).unwrap().1
    }
}

// --- problems

impl Input {
    fn next_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)
    }

    fn bus_ids_with_departure_offsets(&self) -> impl Iterator<Item = (BusID, Timestamp)> + '_ {

        // find the valid bus IDs and pair them with their position in the 
        // list, which equates to the departure offset in minutes

        self.bus_ids.iter()
            .enumerate()
            .filter_map(|(index, maybe_id)| maybe_id.map(|id| (id, index as Timestamp) ))        
    }

    fn find_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| {
                    let timestamp = base_timestamp + i * period;
                    if (timestamp + offset) % bus_id == 0 {
                        Some( (timestamp, period * bus_id) )
                    } else {
                        None
                    }
                }).unwrap()
        ).0
    }
}

fn part1(input: &Input) -> Option<i64> {
    input.next_bus_departing().map(|(id, wait)| id * wait)
}

fn part2(input: &Input) -> Timestamp {
    input.find_first_aligned_timestamp(100000000000000)
}

fn main() {
    let input = Input::from(read_file("./input.txt").unwrap().as_str());
    println!("part1 {:?}", part1(&input));
    println!("part2 {:?}", part2(&input));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_parser() {
        let input = 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]
    fn test_next_bus_departing() {
        let input = Input::from("939\n7,13,x,x,59,x,31,19");
        assert_eq!(input.next_bus_departing(), Some((59, 5)));        
    }

    #[test]
    fn test_find_first_aligned_timestamp_1() {
        let input = Input::from("939\n7,13,x,x,59,x,31,19");
        assert_eq!(input.find_first_aligned_timestamp(1000000), 1068781);        
    }

    #[test]
    fn test_find_first_aligned_timestamp_2() {
        let input = Input::from("0\n17,x,13,19");
        assert_eq!(input.find_first_aligned_timestamp(0), 3417);        
    }

    #[test]
    fn test_find_first_aligned_timestamp_3() {
        let input = Input::from("0\n67,7,59,61");
        assert_eq!(input.find_first_aligned_timestamp(0), 754018);        
    }

    #[test]
    fn test_find_first_aligned_timestamp_4() {
        let input = Input::from("0\n67,x,7,59,61");
        assert_eq!(input.find_first_aligned_timestamp(0), 779210);        
    }

    #[test]
    fn test_find_first_aligned_timestamp_5() {
        let input = Input::from("0\n67,7,x,59,61");
        assert_eq!(input.find_first_aligned_timestamp(0), 1261476);        
    }

    #[test]
    fn test_find_first_aligned_timestamp_6() {
        let input = Input::from("0\n1789,37,47,1889");
        assert_eq!(input.find_first_aligned_timestamp(0), 1202161486);        
    }
}

-- IDs paired with offsets
parse :: String -> Integer -> [(Integer,Integer)]
parse [] _ = []
parse xs offset 
    | head xs == 'x' = parse (tail xs) (offset+1)
    | head xs == ',' = parse (tail xs) offset
    | otherwise = let (n,xs') = span isDigit xs
                  in (read n :: Integer, offset) : parse xs' (offset + 1)
task1 ts = head . filter isJust . concatMap (\(ts, ids) -> map (check ts) ids)
  where
    check ts' id | ts' `mod` id == 0 = Just ((ts' - ts) * id)
                 | otherwise        = Nothing

-- Chinese Remainder Gaussian
-- https://en.wikipedia.org/wiki/Chinese_remainder_theorem
crt :: [Integer] -> Integer -> [Integer] -> Integer
crt diffs mprod ids = let ins = zip diffs ids
                       in foldr (\(x,y) r -> r + aux x y) 0 ins `mod` mprod
    where
      aux x y = let f = (mprod `div` y) `inv` y
                in ((x * mprod) `div` y) * f
      -- Modular multiplicative inverse
      -- https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
      a `inv` m = let (_, i, _) = gcd' a m in i `mod` m
      -- Extended Euclidean Algorithm
      -- stack overflow 
      -- (https://stackoverflow.com/questions/35529211/chinese-remainder-theorem-haskell)
      gcd' 0 b = (b, 0, 1)
      gcd' a b = (g, t - (b `div` a) * s, s)
          where (g, s, t) = gcd' (b `mod` a) a
main = do
  [timestamp, ids] <- readFile "day13_input" <&> lines
  let ts = read timestamp :: Integer
      ids' = parse ids 0
      ids'' = map fst ids'
  putStrLn ("Part 1: " ++ show (fromJust $ task1 ts (zip [ts, ts+1..] (repeat ids''))))
  putStrLn ("Part 2: " ++ show (crt (map (uncurry (-)) ids') (product ids'') ids''))

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

       IDENTIFICATION DIVISION.
       PROGRAM-ID. AOC-2020-13-2.
       AUTHOR ANNA KOSIERADZKA.

       ENVIRONMENT DIVISION.
       INPUT-OUTPUT SECTION.
       FILE-CONTROL.
           SELECT INPUTFILE ASSIGN TO "d13.input"
           ORGANIZATION IS LINE SEQUENTIAL.

       DATA DIVISION.
       FILE SECTION.
         FD INPUTFILE
         RECORD IS VARYING IN SIZE FROM 1 to 200
         DEPENDING ON REC-LEN.
         01 INPUTRECORD PIC X(200).

       WORKING-STORAGE SECTION.
         01 REC-LEN PIC 9(2) COMP.
         01 WS-BUSES PIC 9(5) OCCURS 1 TO 99 DEPENDING ON LEN.
         01 WS-REMAINDERS PIC S9(5) OCCURS 1 TO 99 DEPENDING ON LEN.
         01 WS-BUFFER PIC X(5).
         01 WS-I PIC S9(5).
         01 WS-M PIC S9(5).
         77 LEN PIC 99 VALUE 99.
         77 WS-QUOTIENT PIC S9(20).
         77 WS-MOD PIC S9(20).
         77 N PIC 9(20).
         77 A PIC 9(20).
         77 N1 PIC 9(20).
         77 A1 PIC 9(20).
         77 RESULT PIC 9(20).

       LOCAL-STORAGE SECTION.
         01 STRING-PTR UNSIGNED-INT VALUE 1.
         01 I UNSIGNED-INT VALUE 0.
         01 J UNSIGNED-INT VALUE 1.

       PROCEDURE DIVISION.
       001-MAIN.
           OPEN INPUT INPUTFILE.
           PERFORM 002-READ.
           CLOSE INPUTFILE.
           PERFORM 003-FIND-TIMESTAMP.
           DISPLAY RESULT.
           STOP RUN.

       002-READ.
           READ INPUTFILE
           END-READ.
           READ INPUTFILE 
           END-READ.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > 99
             MOVE 0 TO WS-BUFFER
             UNSTRING INPUTRECORD DELIMITED BY ',' INTO WS-BUFFER
             WITH POINTER STRING-PTR
             COMPUTE WS-I = FUNCTION NUMVAL(WS-BUFFER)
             IF NOT WS-I = 0 THEN 
               MOVE WS-I TO WS-BUSES(J)
               COMPUTE WS-M = WS-I - I + 1
               DIVIDE WS-M BY WS-I GIVING WS-QUOTIENT REMAINDER WS-M
               IF WS-M < 0 THEN 
                 ADD WS-I TO WS-M 
               END-IF
               COMPUTE WS-REMAINDERS(J) = WS-M
               ADD 1 TO J
             END-IF
           END-PERFORM.
           COMPUTE LEN = J - 1.

       003-FIND-TIMESTAMP.
           MOVE WS-BUSES(1) TO N.
           MOVE WS-REMAINDERS(1) TO A.
           PERFORM VARYING I FROM 2 BY 1 UNTIL I > LEN
              MOVE WS-BUSES(I) TO N1
              MOVE WS-REMAINDERS(I) TO A1
              MOVE 0 TO WS-MOD
              MOVE 1 TO WS-QUOTIENT
              PERFORM UNTIL WS-MOD = A1
                 COMPUTE A = A + N
                 DIVIDE A BY N1 GIVING WS-QUOTIENT REMAINDER WS-MOD
              END-PERFORM
              COMPUTE N = N * N1
           END-PERFORM.
           COMPUTE RESULT = A.