DEV Community

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

Ryan Palo on December 13, 2020

Yesterday was a cool one. I usually enjoy the simulation puzzles. Although I did have some brain farts when it came to rotating things on a discr...

Read full post

Derk-Jan Karrenbeld • Dec 13 '20

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

Shalvah • Dec 14 '20

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.first

ids.each_with_index do |(bus_id, offset), index|
  next if index == 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) }
  loop do
    difference = bus_id - (current_timestamp % bus_id)
    break if difference == (offset % bus_id)
    current_timestamp += period
  end
end

p current_timestamp

Kudos Beluga • Dec 13 '20 • Edited

Part 1 JS solution, (maybe) Part 2 coming soon (This Chinese remainder theorem thing sounds complicated for a 7th grader and looking at other comments brute force for part 2 doesn't seem like an option)

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

Benjamin Trent • Dec 13 '20 • Edited

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 :)

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
}

Christopher Kruse • Dec 14 '20

Man, this turned out really concise. Also, thank you for letting me shamelessly steal your logic for part 2 :D

Seoane8 • Dec 13 '20

Solution of Part 2 in Python

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

Seoane8 • Dec 13 '20

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

Ryan Palo • Dec 14 '20

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

Neil Gall • Dec 14 '20

I worked out the algorithm on my own with no googling too. We should get extra stars!

Christopher Kruse • Dec 14 '20

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.

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

Neil Gall • Dec 13 '20

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.

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

Benedict Gaster • Dec 13 '20

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:

-- 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''))

pepa65 • Jan 21 '21 • Edited

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

Anna • Dec 13 '20

Staying true to COBOL

       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.