셔틀 검색

코드 출현 2020 13일차

2부 시뮬레이터 사용해 보기

작업: X에 대해 풀기 여기서...

1 부

X = Product of two numbers: Id of the next bus to arrive, and the minutes between earliest departure time and that bus's arrival time 

2 부

X = Earliest timestamp where all buses arrive within minutes of one another

예시 입력

939
7,13,x,x,59,x,31,19

나타내는

가장 빠른 출발 시간

각 버스의 도착 시간 간격으로 배가되는 버스 ID 목록(예: 7은 7분마다 도착하는 버스 ID 7임)

1 부

가장 빨리 도착하는 버스를 식별하기 위한 방정식 공식화

내 퍼즐 입력을 위해 수동으로 풀기

알고리즘으로 해결하기

가장 빨리 도착하는 버스를 식별하기 위한 방정식 공식화

이 퍼즐은 다음과 같은 유용한 다이어그램을 제공합니다.

time   bus 7   bus 13  bus 59  bus 31  bus 19
929      .       .       .       .       .
930      .       .       .       D       .
931      D       .       .       .       D
932      .       .       .       .       .
933      .       .       .       .       .
934      .       .       .       .       .
935      .       .       .       .       .
936      .       D       .       .       .
937      .       .       .       .       .
938      D       .       .       .       .
939*     .       .       .       .       .
940      .       .       .       .       .
941      .       .       .       .       .
942      .       .       .       .       .
943      .       .       .       .       .
944**    .       .       D       .       .
945      D       .       .       .       .
946      .       .       .       .       .
947      .       .       .       .       .
948      .       .       .       .       .
949      .       D       .       .       .

이것이 나에게 보여주는 것:

Using 939 as a baseline

For Bus ID 7:
Last departure was 938
1 minute ago
The remainder after 939/7 = 1 -> 939 - 1 = 938

For Bus ID 13:
Last departure was 936
3 minutes ago
The remainder after 939/13 = 3 -> 939 - 3 = 936

For Bus ID 31:
Last departure was 930
9 minutes ago
The remainder after 939/31 = 9 -> 939 - 9 = 930

For Bus ID 19:
Last departure was 931
8 minutes ago
The remainder after 939/19 = 8 -> 939 - 8 = 931

확인됨:

  Earliest departure time 
- (Earliest departure time modulo Bus ID)
-----------------------------------------
Bus ID's just-missed departure time

이제 각 버스의 다음 출발 시간을 어떻게 결정합니까?

Using 939 as a baseline

For Bus ID 7:
Next departure is 945
6 minute from now
(7 - The remainder after 939/7) = 6

For Bus ID 13:
Next departure is 949
10 minutes from now
(13 - The remainder after 939/13) = 10

For Bus ID 59:
Next departure is 944
5 minutes from now
(59 - The remainder after 939/59) = 5

확인됨:

  Bus ID
- (Earliest departure time modulo Bus ID)
--------------------------------------
Bus ID's next departure time

내 퍼즐 입력을 위해 수동으로 풀기

입력에 버스 ID가 10개 미만이었기 때문에 브라우저의 콘솔을 사용하여 이러한 각 방정식을 수행하고 각 버스 ID를 서브빙했습니다

.

역시나 바라던대로 정답을 맞췄네요

알고리즘으로 해결

Process the input:
Split the input at the new line character to create an array of two elements
Convert the first element into a number
Split the second element at the comma character to create an array of elements
  Filter out all 'x' elements
Convert each remaining element into a number

Determine which bus arrives soonest:
For each number
  Update an accumulating 2-element array - starting from an array with two elements that are both the earliest departure time - according to the following steps:
    If the number generated from subtracting (the remainder after dividing the earliest departure time by the bus ID) from the bus ID is less than the current number stored as the second element in the accumulating array
      Updated the accumulating array such that the first item is the bus ID and the second item is the result of the equation above

Calculate the product of bus ID and minutes spent waiting:
For each number in the 2-element array
  Accumulate the product of each number

Return the product

다음은 해당 알고리즘의 시각화입니다.

2 부

나는 x 가 결국 역할을 할 것이라는 것을 알고 있었습니다!

이어진 여정:

지침을 읽고, 다시 읽고, 이해했습니다

이 퍼즐을 풀 수 있고 100억 번 이상 실행되지 않는 알고리즘을 만드는 데 어디서부터 시작해야 할지 모르겠다는 것을 깨달았습니다

.

자주 사용하는 JavaScript 솔버인 NullDev

를 사용했습니다.

their solution이 배열 반복자 함수

내부의 단순while 루프라는 사실을 알고 기뻐했습니다.

작동 방식을 이해하기로 했습니다

.

NullDev의 알고리즘을 활용하는 시뮬레이터를 구축할 기회를 잡았습니다...작동 방식을 시각화할 수 있었습니다

.

조립하고 작동 방식을 확인하고 그 우아함에 감탄했습니다

Here is the simulator using NullDev's algorithm for Part 2


내 입력에서 실행되는 시뮬레이터를 보지 않기로 선택했습니다.

자랑스럽게 얻은 골드 스타 하나와 함께 이 퍼즐을 남겼습니다.

그리고 내 시뮬레이터 벨트에 또 하나의 노치가 있습니다.