Radio station hopping

Question

Introduction

You are listening to a car radio. You are pressing seek up/down, moving you to the next frequency some radio station broadcasts on, to avoid all this pointless music and listen to all the ads, or vice versa. If you try to go below the lowest frequency radio can handle, it jumps to the highest (and vice versa). Possible frequency range of a car radio is about 80-110 MHz with 2 decimals of precision.

But there is a tendency of these broadcasts to have your radio jump to another frequency, where signal of that radio station is stronger. So, suppose this radio station A broadcasts at 99, 100 and 101 MHz with 100 MHz having the strongest signal at your place. The moment you reach 101 MHz, radio will jump to 100 MHz.

Because of that, you can get trapped. Suppose there is one extra radio station B, broadcasting only at 102 MHz. The moment you are stuck at the station A, you can never listen to station B again - if you try going with frequency down, you will hit 99 and jump to 100, if you go up you reach 101 and jump to 100 again... never escaping that trap and radio station.

But if there is yet another station C at 99.5 and 98.5 MHz with latter being the strongest, you can listen to all 3 radios again - starting from B you get down to A, then down to C, then pressing down loops you back again to the highest frequency and station B.

So, you start wondering - given a list of radio stations, can I listen to all radio stations at least once if I start at the correct frequency? And will I be able to endlessly cycle through all of them, or listen to all just once before getting cut off some stations?

Your task:

Get a list of radio stations, along with a designation of which has the strongest signal, in any reasonable format (1). Return one of three options to distinguish whether you can cycle through all stations indefinitely, you can cycle through all stations once or you cannot reach all stations from any starting point. Again in any reasonable format (2). Standard loophole rules apply.

(1) Test cases have different radio stations separated by semicolon. For each radio station, the strongest broadcast for the station is first, other entries separated by comma. You can pick anything else as your input format, along with any reasonable extra information you would like - for example number of radio stations, number of channels each station broadcasts at etc. Two stations won't share frequency. Frequencies can be assumed to be in typical car-like frequency range of say 80.00 to 110.00 MHz (or 8000 to 11000 if you prefer working with integers).

(2) Test cases have output as 1 - cycle all, 2 - cycle once, 3 - cannot reach all stations even once. You can return anything reasonable to distinguish these three options, as long as you return/print the value. For example, another possible output might be T meaning cycle all is true, FT meaning cycle all is false, cycle once is true, and FF meaning cycle all and cycle once are both false (= you can't reach all stations even once). Limitation: You must return everything in the same way, eg if your code outputs "cycle all" by crashing due to recursion depth, your "cycle once" and "cannot cycle" must also output by crashing.

Test cases:

input: 102; 100, 99, 101 output: 2

input: 102; 100, 99, 101; 98.5, 99.5 output: 1

input: 100, 99, 101; 103, 102, 104 output: 3

input: 100, 99, 101; 103, 102, 104; 101.5, 99.5, 103.5 output: 1

input: 100, 99; 99.5, 100.5; 102, 103; 102.5, 101.5 output: 3

May the shortest code win.

Answer 1

JavaScript (ES10),  179  155 bytes

Expects an array of arrays of frequencies, with the strongest broadcast in first position for each station.

Returns \$1\$ for cycle once, \$0\$ for cycle all, or \$3\$ if there's no solution at all.

a=>a.some(h=A=>a[(g=([x],C=q=>a.find(d=>d.includes(b[(b.indexOf(x)+q)%n])))=>!g[x]&&g(C(g[x]=1))-~g(C(n-1)))(A)],b=a.flat().sort(),n=b.length)|2*a.every(h)

Try it online!

How?

We first create an array b[] holding all frequencies sorted in lexicographical order. It means that the 80-99Mhz range will be put after the 100-110MHz range. But because the frequencies are wrapping around anyway, it doesn't matter. We also put the total number of frequencies in n.

b = a.flat().sort(), n = b.length

The helper function C takes a direction q and returns the sub-list corresponding to the station that is reached by moving towards q from the current leading frequency x.

C = q => a.find(d => d.includes(b[(b.indexOf(x) + q) % n]))

The callback function h takes the sub-list A of a station and walks through all connected stations, keeping track of the count (let's call it N). We use q = 1 to seek up and q = n - 1 to seek down. We eventually test a[N] to figure out whether all stations were reached.

h = A => a[(g = ([x], C = ...) => !g[x] && g(C(g[x] = 1)) - ~g(C(n - 1)))(A)]

This uses the helper function C described above and another recursive function g whose underlying object is also used to keep track of the stations that were already reached, using the leading frequency as the key.

We invoke h twice: once within a some() to detect cycle once and once within an every() to detect cycle all.

Answer 2

Jelly, 58 36 bytes

;þ`Ḣ)ẎṢṪ€i@€FṢ$µṙⱮØ-Zị@QċþQæ*LẠ€Ạ;ẸƊ

Try it online!

A monadic link that takes as it’s argument a list of lists and returns [0,0] if it’s not possible to reach every station, [0, 1] if each can be reached once and [1, 1] if they can be cycled through indefinitely.

Explanation

    )                                  | For each radio station:
;þ`                                    | - Concatenate each frequency to each of the other frequencies, as a list of lists
   Ḣ                                   | - Head - i.e. each frequency paired with the main frequency for the station
     Ẏ                                 | Join lists together
      Ṣ                                | Sort (so now in frequency order)
       Ṫ€                              | Tail of each (i.e. just the main frequency)
         i@€  $                        | For each, index of the station in the list generated by taking the original input and:      
            F                          | - Flattening it and
             Ṣ                         | - Sorting it
               µ                       | Start a new monadic chain
                ṙⱮØ-                   | Rotate by each if -1 and 1
                    Z                  | Transpose
                     ị@                | Take only the main stations (which are
                       Q               | - The unique values)
                        ċþQ            | Generate an adjacency matrix
                           æ*L         | Matrix to the power of the length(number of stations)
                              Ạ€       | Check wherher rows are all true
                                   Ɗ   | Following as a monad:
                                Ạ      | - All
                                 ;     | - Concatenated to
                                  Ẹ    |- Any

Answer 3

J, ^{85 81} 78 bytes

[:~.#=[:+/@((]+.+./ .*)^:_"_ 1[:=#\)>+./@e."1/~/:~@;(]/:~e.#[:|:_1 1|."{[){.&>

Try it online!

the idea

Let n be the number of the stations.

• Create an adjacency matrix representing connections between stations.
• For each starting station create an n item vector with a single 1 in the starting station's position, and 0 elsewhere, to encode the starting position as a vector.
• For each starting vector, iteratively multiply by the adjacency matrix n times, collecting intermediate results. The final vector represents which stations you can visit from the starting vector.
• Sum that final vector. This is the number of stations you can visit from that starting station.
• Check if that sum is equal to n. If it is, all stations can be visited.
• Now we have n final sums, each of which will be 0 (you can't visit all stations from that starting station) or 1 (you can). Uniquify that 0-1 list. Then note:
  • A single 1 means every starting station returned 1, meaning any station can be visited (via some number of hops) from any other. This is case 1.
  • A single 0 means you cannot visit all stations from any starting point. Case 3.
  • Both a 0 and 1 means it's possible to visit all stations from some starting point, but not from all. Case 2.