AoCG2021 Day 24: Is the bus company cheating?

Question

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]

Answer 1

Pari/GP, 45 bytes

a->i=1;iferr(chinese([Mod(i--,b)|b<-a])',e,1)

Try it online!

Taking holes as 1.

Tries applying the Chinese remainder theorem built-in. If it throws an error, the bus company is cheating.

Answer 2

Jelly, 8 bytes

P+€TọµẠƇ

Try it online!

Outputs an empty list for falsy.

P        Product
 +€      Foreach, added to
   T     0...input length
    ọ    Number of times each divides each - 0 for falsy
     µẠƇ Filter by all truthy

Answer 3

Wolfram Language (Mathematica), 42 38 37 bytes

Head@ChineseRemainder[i=0;i++&/@#,#]&

Try it online!

Input holes as 1. Returns Integer for truthy, and ChineseRemainder for falsy.

Another built-in. ChineseRemainder returns unevaluated if impossible (an integer if possible), so checking the head collapses these into two fixed values.

---

Slightly less boring (43 bytes):

Sum[Mod[j--,],{,i=0;#},{,j=i++;GCD[,#]}]<1&

Try it online!

Input holes as 1 or -1. Same approach as Neil's Charcoal answer.

Answer 4

Charcoal, 23 bytes

⬤θ⬤θ⬤…·²ι∨∨﹪ιν﹪λν¬﹪⁻κμν

Try it online! Link is to verbose version of code. Accepts -1 as a hole. Outputs a Charcoal boolean, i.e. - for possible, nothing for impossible. Explanation: Any factor common to two of the elements must also divide the difference in their indices, otherwise the application of the Chinese Remainder Theorem would fail at that point.

 θ                      Input array
⬤                       All elements satisfy
   θ                    Input array
  ⬤                     All elements satisfy
     …·                 Inclusive range
       ²                From literal integer `2`
        ι               To outer value
    ⬤                   All elements satisfy
             ν          Potential factor
           ﹪            Does not divide
            ι           Outer value
          ∨             Logical Or
                ν       Potential factor
              ﹪         Does not divide
                ν       Inner value
         ∨              Logical Or
                      ν Potential factor
                 ¬﹪     Divides
                    κ   Outer index
                   ⁻    Minus
                     μ  Inner index
                        Implicitly print

Answer 5

JavaScript (Node.js), 56 bytes

a=>eval("for(i=1+a.join``;a.some(n=>++x%n,x=i--)*i;);i")

Try it online!

Use 0 for a hole. Too slow for most testcases.

Simple idea:

for t := (large enough number) domnto 0 do
    if (t is valid) then return true
return false

Although \$\prod a_i\$ would be large enough. Calculating the product is a bit longer than just concat them.

---

JavaScript, 62 bytes

a=>a.some(o=(t,i)=>(g=j=>j&&(t%j?o:o[j]??=i%j)-i%j|g(j-1))(t))

Use hole for a hole. A faster version.

---

JavaScript (Node.js), 65 bytes

a=>a.some((x,i)=>a.some(g=(y,j,_,z=x)=>z%y?g(z%y,j,a,y):(i-j)%y))

Try it online!

Use hole for a hole. The fast version in polynomial time complexity.

Answer 6

Haskell, 65 52 bytes

f l=or[all(==0)$zipWith mod[t..]l|t<-[0..product l]]

Try it Online!

Uses 1 for a hole.

-13 bytes thanks to xnor

Answer 7

TypeScript Types, 332 bytes

//@ts-ignore
type a<T,N=[],U=`${T}`>=U extends`${N["length"]}`?N:a<T,[...N,0]>;type b<A,B>=A extends[...B,...infer X]?b<X,B>:A;type c<A,B>=[]extends A|B?Exclude<A|B,[]>:c<B,b<A,B>>;type M<T,X={[K in keyof T]:[a<T[K]>,a<K>]}[number],Y=X>=0 extends(X extends X?Y extends Y?b<X[1],c<X[0],Y[0]>>extends b<Y[1],c<X[0],Y[0]>>?1:0:0:0)?0:1

Represents holes with 1s.

Try It Online!

Ungolfed / Explanation

I suspect this just applies the Chinese Remainder Theorem, but I haven't looked into it.

// Convert a number literal or a string literal representing a number to a `Nat`
type NumOrStrNumToNat<T, N=[], U=`${T}`> = U extends `${N["length"]}` ? N : NumOrStrNumToNat<T, [...N, 0]>

type ModNat<A, B> = A extends [...B, ...infer X] ? ModNat<X, B> : A

// Calculate the GCD of two `Nat`s using the Euclidean algorithm
type GcdNat<A, B> = [] extends A | B ? Exclude<A | B, []> : GcdNat<B, ModNat<A, B>>

type Main<
  T,
  // Convert an e.g. T of [1,5,3] to [Nat(1), Nat(0)] | [Nat(5), Nat(1)] | [Nat(3), Nat(1)]
  X = { [K in keyof T]: [NumOrStrNumToNat<T[K]>, NumOrStrNumToNat<K>] }[number],
  Y = X
> =
  // Return 0 if any of the following return 0
  0 extends (
    // Map over X cross Y
    X extends X ? Y extends Y ?
      // Return 1 if X[1] and Y[1] are equal modulo the GCD of X[0] and Y[0]
      ModNat<X[1], GcdNat<X[0], Y[0]>> extends ModNat<Y[1], GcdNat<X[0], Y[0]>> ? 1 : 0
    : 0 : 0
  ) ? 0 : 1

Answer 8

Vyxal, 8 bytes

Π'?ẏ+?ḊA

Try it Online!

Outputs an empty list as falsy and a list with items as truthy, taking holes as 1.

Π        # Absolute value of product
 '       # Range 1...n filtered by
  ?ẏ+    # Add 0...input length to that
      ḊA # All divisible by
     ?   # Input   

Answer 9

05AB1E, 9 bytes

PLʒ∞<+IÖP

Port of @emanresuA's Vyxal answer, also taking 1 as holes and outputting an empty list for falsey.

Try it online or verify all test cases (uses a find_first .Δ instead of filter ʒ to speed the test suite up).

Explanation:

P         # Take the product of the (implicit) input-list
 L        # Pop and push a list in the range [1,product(innput)]
  ʒ       # Filter this list by:
   ∞      #  Push an infinite positive list: [1,2,3,...]
    <     #  Decrease each by 1: [0,1,2,...]
     +    #  Add the current integer to it: [y,y+1,y+2,...]
      IÖ  #  Check if the first input amount of values are divisible by the input-values
          #  at the same positions (it'll transform the list into the smallest of the
          #  two, causing the infinite list to shrink to the input-size)
        P #  Check if all are truthy by taking the product
          # (after which the filtered list is output implicitly)

Answer 10

Python3, 88 bytes

lambda L,t=1:t>lcm(*L)or any((t-i)%b for i,b in enumerate(L))*f(L,t+1)
from math import*

Attempt This Online!

Uses 1s as holes. Returns 0 (falsy) if possible, and 1 (truthy) if impossible.

Some test cases cannot be completed due to memory limit with recursion. The iterative version however can finish and gives the correct results: Attempt This Online!

This is a bruteforce search for all numbers t between 1 and the LCM (least common multiple) of all bus IDs. If we find a t that has the correct remainders when divided by all bus IDs b: (t-i) % b == 0 then the bus schedule is possible.