Day 13: Shuttle Search

This one was pretty easy for me. I just just had each bus loop until I could see the first value AFTER the earliest arrival time, then kept the 'best' answer from there.

#data = input_data.split('\n')
data = test_data.split('\n')

earliest_departure = int(data[0])

busses_raw = data[1].split(',')
busses = data[1].split(',')

while 'x' in busses:
    busses.remove('x')
    
busses = list(map(int, busses))

best_bus = None
best_bus_time = None
for bus in busses:
    time = 0
    while time < earliest_departure:
        time = time + bus
    if not best_bus_time or time < best_bus_time:
        best_bus = bus
        best_bus_time = time
    
print(earliest_departure)
print(busses)

print(best_bus)
print(best_bus_time)
print(best_bus_time - earliest_departure)

Figuring out how to do it in the first place was relatively simple. Figuring out how to get the computation done before the end of the month was trickier. I spend a while chasing a fancy mathematical solution, and that was definitely helpful, but it would have taken several hours to understand and implement. If I'm being honest, it's still a bit hard to understand why exactly it works, but here goes:

When I have bus A and B, and they have no offset, I KNOW that they sync up every A * B steps. If they have an offset, then that offset will be exactly the same every A * B steps.

I start with a group of synced busses. It starts empty (or with a ghost bus with an interval of 1).
For each bus, I move the synced bus group until the new bus is at the appropriate offset.
When I find that offset, I add that bus to the synced bus group, and increase the 'speed' of all the synced busses by that busses speed.
So after bus 1 it synced busses just has bus A in it
After bus 2 it is moving at speed A * B
After bus 3 it's moving at speed A * B * C
Etc...

Once all the busses are synced, I have the answer

data = input_data.split('\n')
#data = test_data_2.split('\n')

earliest_departure = int(data[0])

busses_raw = data[1].split(',')
busses = data[1].split(',')
busses_indicies = []

while 'x' in busses:
    busses.remove('x')

for bus in busses:
    busses_indicies.append(busses_raw.index(bus))
    
busses = list(map(int, busses))

synced_busses = 1
time = 0
for bus, index in zip(busses, busses_indicies):
    print(f'Syncing with {bus}, {index}')
    synced = False
    while not synced:
        time = time + synced_busses
        if (time + index) % bus == 0:
            synced = True
            print(f'Successfully synced at {time}')
            synced_busses = synced_busses * bus
    

• This one might be really difficult, depending on your approach

• For the love of god DO NOT BRUTE FORCE part B. My answer was on the order of 700 trillion

• There are fancy fancy mathy ways to solve it. I couldn't wrap my head around the equations after midnight though, but reading up on the concepts did help me eventually develop my solution

• If you don't go for a purely math solution, figuring out how to speed up your search is extremely important.

• Try breaking the problem up into smaller, more manageable portions. For example, can you solve the problem for just 2 busses at a time? And can you think of a way to treat 2 busses as 1 bus?

• All my busses were prime numbers. I have reason to believe that everyone else's will be as well. Knowing they were primes was sort of helpful, but looking at the prime factorization was mostly a dead end for me.

The first part was relatively straightforward: take the ceiling of the arrival time (first number) divided by the bus_id of each bus. From there, you just take the minimum of each of these ceilings to get the closest departure time.

import math
import sys

# Functions

def read_input():
    departure = int(sys.stdin.readline())
    busses    = [int(b) for b in sys.stdin.readline().strip().split(',') if b != 'x']

    return departure, busses

# Main Execution

def main():
    arrival, busses   = read_input()
    bus_departures    = [math.ceil(arrival / b) * b for b in busses]
    departure, bus_id = min(zip(bus_departures, busses))

    print((departure - arrival) * bus_id)

if __name__ == '__main__':
    main()

The second part took me a lot longer to understand conceptually, but turned out to be not a lot of code. The key here is to realize (as mentioned by others) that once a set of busses are synchronized, they will remain synchronized for the product of their ids. So the idea is to simply synchronize one bus at a time, keeping in mind the offset from the initial bus.

For instance, given 17,x,13,19, we would first try to synchronize 17 and 13 where 13 has an offset of 2 (its position in the input).

Start from 17, we initially count upwards by 17 until we reach 102. Here we can see that 102 + 2 is a multiple of 13, therefore we have found the synchronization point for these two numbers. From now on, these two busses will be synchronized every additional 17*13 timesteps. That is, at 102 + 17*13 = 323, bus 13 will be 2 timesteps away from bus 17
Therefore, our next increment should be 17*13 = 221 and we will use that find the synchronization point with the final bus, 19.

I had to work this out on paper a few times to confirm it works, but once I saw the pattern, the code was pretty straightforward. The multiplying of the increment (which works because the synchronization cycles) is what makes the search efficient (runs in milliseconds).

import sys

# Functions

def read_busses():
    _    = sys.stdin.readline()
    data = sys.stdin.readline().strip().split(',')
    return [(int(b), i) for i, b in enumerate(data) if b != 'x']

def find_next_timestamp(start, increment, bus_id, offset):
    while ((start + offset) % bus_id) != 0:
        start += increment
    return start

# Main Execution

def main():
    busses    = read_busses()
    timestamp = busses[0][0]
    increment = timestamp

    for bus_id, offset in busses[1:]:
        timestamp  = find_next_timestamp(timestamp, increment, bus_id, offset)
        increment *= bus_id

    print(timestamp)

if __name__ == '__main__':
    main()

def compute_p1(input)
  start = input.lines.first.to_i
  bus_list = input.lines[1].strip.split(',').reject { |b| b == 'x' }.map(&:to_i)
  soonest = bus_list.map { |bus_id|
    x = bus_id
    while x < start
      x += bus_id
    end
    [x, bus_id]
  }.sort.first

  return (soonest[1] * (soonest[0]-start))
end

I started by looking at the GCD/LCM of the bus ids, and quickly wrote a dumb brute force search (which was obviously too slow), played around with using various combinations of LCM and modulus to make the search faster (this is where I realized that all the bus ids were prime) and got stuck for a good while. Thinking about primes and modulus, plus some half-remembered college material, lead me (after walking away for a bit and coming back with fresh eyes) to Residue Number Systems and the Chinese Remainder Theorem, which provided the correct solution I'd been fumbling towards.

The key observation, as mentioned in the other posts, is that the times/solutions for each subset of buses ([bus1], [bus1, bus2], [bus1, bus2, bus3], etc) will repeat at intervals of their least common multiples (which, given that they're all prime, is just the product, though my solution leaves in the LCM call from an earlier version). This means that you can start at the first bus, and then search forward by steps of that bus's id until you find a match for the next bus, change your step size to the LCM of the solved bus ids, proceed until you find a match for the next, and so on until all the buses are solved.

def check(num, bus_list)
  bus_list.each_with_index.reject{ |b,i| b == 1 }.all? { |b,i| ((num+i) % b) == 0}
end

def compute_p2(input)
  bus_list = input.lines[1]
               .strip
               .split(',')
               .map { |x| x == 'x' ? 1 : x.to_i }
  working = []
  step = 1
  t = 0

  bus_list.each do |bus|
    # add the next bus to our working set
    working << bus

    # advance by steps until we find a time that fits all the buses in our set
    t += step until check(t, working)

    # change our step so that we only ever advance by the LCM of all our previous
    # buses, which ensures that every new step we take continues to satisfy the
    # constraints
    step = working[...-1].reduce(1,:lcm)
  end

  return t
end

=ARRAYFORMULA(
  INDEX(
   QUERY(
    SPLIT(
     FLATTEN(
      IF(
       REGEXMATCH(
        TEXT(TRANSPOSE(SEQUENCE(1,30,A1,1))/SPLIT(A2,",x",TRUE,TRUE),"0.###"),
        "[0-9]+\.[0-9]+"),,
        ROW(A3:A)-3&"|"&SPLIT(REGEXREPLACE(A2,"x",""),",",FALSE,TRUE))),"|"),
     "select Col1, Sum(Col1)*Sum(Col2) 
      where Col2 is not null 
      group by Col1
      order by Col1 asc 
      limit 1
      label Sum(Col1)*Sum(Col2) 'Part 1'",0),0,2))

function main()

    input = []
    open("Day13/input.txt") do fp
        input = readlines(fp)
    end

    current_time = parse(Int, input[1])
    bus_ids = tryparse.(Int, split(input[2], ','))

    # filter out out of service buses
    bus_ids = Array{Int}(bus_ids[bus_ids .!= nothing])

    earliest_times = earliest_time.(current_time, bus_ids)

    min_time, min_index = findmin(earliest_times)

    result_1 = (min_time - current_time) * bus_ids[min_index]

    println(result_1)

end

function earliest_time(current_time, bus_time)
    return Int(ceil(current_time / bus_time) * bus_time)
end

main()

I had originally sorted the bus IDs to get the biggest ones first, in the hope that would get a larger step size early on and lead to faster runtime. In the end it was actually a bit slower so I left them as is.

@@ -8,8 +8,14 @@ function main()
     current_time = parse(Int, input[1])
     bus_ids = tryparse.(Int, split(input[2], ','))
 
+    # Grab minute offsets
+    offsets = findall(bus_ids .!= nothing)
+
     # filter out out of service buses
-    bus_ids = Array{Int}(bus_ids[bus_ids .!= nothing])
+    bus_ids = Array{Int}(bus_ids[offsets])
+
+    # Adjust offset for indexing at 1
+    offsets = offsets .- 1
 
     earliest_times = earliest_time.(current_time, bus_ids)
 
@@ -19,8 +25,32 @@ function main()
 
     println(result_1)
 
+    # Credit to @PapaNachos on Tildes for their hints/code
+    not_found = true
+    step = 1
+    time = 1
+    constraint = 1
+    while not_found
+        not_found = false
+
+        # apply constraint
+        if mod(time + offsets[constraint], bus_ids[constraint]) != 0
+            time += step
+            not_found = true
+        end
+
+        # Check to see if we have applied all constraints, if not, add another and keep going
+        if !not_found && constraint < length(bus_ids)
+            step *= bus_ids[constraint]
+            constraint += 1
+            not_found = true
+        end
+    end
+    println(time)
+
 end