11 votes

Day 13: Shuttle Search

Today's problem description: https://adventofcode.com/2020/day/13


Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

6 comments

  1. PapaNachos
    (edited )
    Link
    I'm just going to post part A for now, I'm still wrapping my head around the math for part B. This might take a bit. Edit: After ramming my head against it for a while, I finally figured it out. I...

    I'm just going to post part A for now, I'm still wrapping my head around the math for part B. This might take a bit.

    Edit: After ramming my head against it for a while, I finally figured it out. I ALMOST had to turn off the eurobeat to help myself concentrate, but thankfully that wasn't necessary.

    Day 13 Part A – Python

    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)
    
    Day 13 Part B – Python

    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
        
    
    Tips and Commentary
    • 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.

    5 votes
  2. pnutzh4x0r
    Link
    Python Repo Link Part 1 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...

    Python

    Repo Link

    Part 1

    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()
    
    Part 2

    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()
    
    4 votes
  3. Crespyl
    Link
    Ruby Like many others, part 2 took me a lot longer than part 1. Part 1 def compute_p1(input) start = input.lines.first.to_i bus_list = input.lines[1].strip.split(',').reject { |b| b == 'x'...

    Ruby

    Like many others, part 2 took me a lot longer than part 1.

    Part 1
    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
    
    Part 2 This puzzle reminded me straight away of 2019's [day 16](https://adventofcode.com/2019/day/16) and [day 22](https://adventofcode.com/2019/day/22), which also both involved enormous numbers.

    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
    
    4 votes
  4. tomf
    (edited )
    Link
    I'm not sure about part 2... but here's part 1 in Sheets! Part 1 =ARRAYFORMULA( INDEX( QUERY( SPLIT( FLATTEN( IF( REGEXMATCH( TEXT(TRANSPOSE(SEQUENCE(1,30,A1,1))/SPLIT(A2,",x",TRUE,TRUE),"0.###"),...

    I'm not sure about part 2... but here's part 1 in Sheets!

    Part 1
    =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))
    

    I was late starting tonight but made ~7000, which is within 2k of my best and well under my average.

    ok, Part 2 is done -- but Google Sheets cannot do the math. The result Sheets spits out is 1,118,684,865,113,060 where the proper answer is 1,118,684,865,113,056. However, even posting this proper answer into Sheets, it'll change it to 1,118,684,865,113,050 after formatting it. When you check the difference between the formatted correct answer and the answer it spits out, it says there's a difference of 7, when in fact there should be a difference of 4.

    3 votes
  5. spit-evil-olive-tips
    Link
    Part 1 import sys def parse_input(input_path): routes = [] with open(input_path) as input_file: lines = input_file.readlines() initial_timestamp = int(lines[0]) for route in lines[1].split(','):...
    Part 1
    import sys
    
    
    def parse_input(input_path):
        routes = []
        with open(input_path) as input_file:
            lines = input_file.readlines()
            initial_timestamp = int(lines[0])
            for route in lines[1].split(','):
                try:
                    routes.append(int(route))
                except ValueError:
                    pass
    
        return initial_timestamp, routes
    
    
    def main():
        initial_timestamp, routes = parse_input(sys.argv[1])
    
        for route in routes:
            quotient, remainder = divmod(initial_timestamp, route)
            wait_time = route - remainder
            print(f'{route} -> {wait_time} ({route * wait_time})')
    
    
    if __name__ == '__main__':
        main()
    
    Part 2

    I came up with an OK-ish algorithm for this...take the slowest bus (every 971 minutes in my case) and only consider multiples of that. Still not fast enough normally. However, it parallelizes very well, so I threw Python's multiprocessing at it.

    I ended up running it on my 16-core desktop as well as SCPing the script to my 12-core home server, and working them both until I got an answer. It took...about an hour? I wasn't paying very close attention.

    import multiprocessing
    import operator
    import sys
    import time
    
    
    def parse_input(input_path):
        routes = {}
        with open(input_path) as input_file:
            lines = input_file.readlines()
            for index, route in enumerate(lines[1].split(',')):
                try:
                    routes[index] = int(route)
                except ValueError:
                    pass
    
        return routes
    
    
    def evaluate(routes, start, end):
        start_time = time.perf_counter_ns()
    
        slowest_route, slowest_frequency = max(routes.items(), key=operator.itemgetter(1))
    
        current = (start // slowest_frequency) * slowest_frequency
        while current < end:
            current += slowest_frequency
    
            base = current - slowest_route
            success = True
            for route, frequency in routes.items():
                target = base + route
                if target % frequency != 0:
                    success = False
                    break
    
            if success:
                return base
    
        end_time = time.perf_counter_ns()
        duration = (end_time - start_time) / 1_000_000_000
        print(f'{start}: {duration:0.9f}')
    
    
    def main():
        routes = parse_input(sys.argv[1])
        start = int(sys.argv[2])
        end = int(sys.argv[3])
        chunk_size = (end - start) // 10000
    
        futures = []
        pool = multiprocessing.Pool()
        for chunk_start in range(start, end, chunk_size):
            future = pool.apply_async(evaluate, (routes, chunk_start, chunk_start + chunk_size))
            futures.append(future)
    
        for future in futures:
            result = future.get()
            if result:
                print(result)
                break
    
    
    if __name__ == '__main__':
        main()
    
    3 votes
  6. Gyrfalcon
    Link
    Language: Julia Repository This one was a doozy. Part 1 was not bad but part 2 I tried several things that did not work. I looked at it as linear algebra, as a linear optimization problem, as...

    This one was a doozy. Part 1 was not bad but part 2 I tried several things that did not work. I looked at it as linear algebra, as a linear optimization problem, as something I could do recursively with a simpler method, and eventually got close based on hints from @PapaNachos, and then just had to look at a solution to get over the last hump. My final solution is pretty speedy (mean time of 380.573 μs over 10,000 samples) but wow I would not have gotten there on my own.

    Part 1
    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()
    
    Part 2 diff

    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
    
    2 votes