Part of Advent of Code Golf 2021 event. See the linked meta post for details.
Related to AoC2020 Day 13, Part 2.
Why Bubbler isn't posting this; Why Riker isn't posting this
A shuttle bus service runs between the sea port (where you are) to the airport (where you need to go). Each bus has an ID number that also indicates how often the bus leaves for the airport - more precisely, the number of minutes between the departure of two consecutive buses of that ID. Every bus departed at the same time some time in the past at the timestamp of zero.
The shuttle company is running a contest: one gold coin for anyone that can find the earliest timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs at that subsequent minute.
The list of bus IDs looks like this:
7,13,x,x,59,x,31,19
where x
means "don't care". So the objective here is to find the timestamp t
where:
- Bus 7 departs at
t
. - Bus 13 departs at
t+1
. - Bus 59 departs at
t+4
. - Bus 31 departs at
t+6
. - Bus 19 departs at
t+7
.
The earliest timestamp t
for this list is 1068781.
However, you suspect that the company won't want to give out any gold coins, because sometimes the list looks like this:
7,7
which is obviously impossible - Bus 7 cannot depart at t
and t+1
for any t
.
Given the list of Bus IDs, determine if you can earn a gold coin or not.
Input: The list of bus IDs, possibly with some holes. A bus ID is always positive. A hole can be represented using any value that is not a positive integer (e.g. 0, -1, "x"
); alternatively, you may represent holes by 1
, since they have the same effect (a 1
can always go anywhere). The list is guaranteed to be non-empty.
Output: A value representing the answer. You can choose to
- output truthy/falsy using your language's convention (swapping is allowed), or
- use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.
Standard code-golf rules apply. The shortest code in bytes wins.
Test cases
The test cases use 0 for the holes in the list.
Truthy:
[7, 13, 0, 0, 59, 0, 31, 19]
[1, 2, 3, 4, 5]
[0]
[999]
[1, 3, 5, 7, 9, 11, 13, 15]
Falsey:
[7, 7]
[3, 1, 4, 1, 5, 9, 2]
[4, 0, 4]
[1, 2, 3, 4, 5]
, if bus 1 departs at t+0, shouldn't bus 1 also departs at t+1? \$\endgroup\$1
s as holes. \$\endgroup\$