The longest consecutive traversal possible (number of edges)

Question

A truck fleet dispatcher is trying to determine which routes are still accessible after heavy rains flood certain highways. During their trips, trucks must follow linear, ordered paths between 26 waypoints labeled A through Z; in other words, they must traverse waypoints in either standard or reverse alphabetical order.

The only data the dispatcher can use is the trip logbook, which contains a record of the recent successful trips. The logbook is represented as a list of strings, where each string (corresponding to one entry) has two characters corresponding to the trip origin and destination waypoints respectively.

If the logbook contains a record of a successful trip between two points, it can be assumed that the full path between those points is accessible. Note that logbook entries imply that both directions of the traversal are valid. For example, an entry of RP means that trucks can move along both R --> Q --> P and P --> Q --> R. Note that the trips A --> B and C -> D do not together imply that B -> C is usable. Entries can have the same character twice, such as C -> C, but this indicates no paths.

Given an array of logbook entries, your task is to write a function to return the length of the longest consecutive traversal possible; in other words, compute the maximum number of consecutive edges known to be safe. (In even more formal terms, compute the diameter of the largest tree on this graph.)

Example

For logbook = ["BG", "CA", "FI", "OK"], the output should be 8

Because we can get both from A to C and from B to G, we can thus get from A to G. Because we can get from F to I and access I from G, we can therefore traverse A --> I. This corresponds to a traversal length of 8 since 8 edges connect these 9 waypoints. O through K is a length 4 traversal. These two paths are disjoint, so no longer consecutive paths can be found and the answer is 8.

---

Guaranteed constraints:

1 ≤ logbook.length ≤ 100,

logbook[i].length = 2,

logbook[i][j] ∈ ['A'..'Z'].

---

Test Cases:

logbook: ["AZ"] Output:25

logbook: ["AB", "CD"] Output:1

logbook: ["BG", "CA", "FI", "OK"] Output: 8

logbook: ["KM", "SQ", "ON", "XM", "UK"] Output:13

logbook: ["XU", "WY", "ZD", "HH", "BK", "LG"] Output: 24

logbook: ["QR", "PC", "TK", "OE", "YQ", "IJ", "HB"] Output: 23

logbook: ["MG", "QQ", "JV", "IZ", "SQ", "PN", "TI", "NK"] Output: 19

logbook: ["II", "ZW", "CI", "DT", "IM", "II", "TR", "XO", "AL"] Output: 25

---

The input will always be an array of strings, each of which has exactly two characters corresponding to the trip origin and destination waypoints respectively. The characters will always be letters, in a consistent case of your choice. The input will never contain more than 100 pairs.

Your program should output the longest consecutive traversal possible (number of edges) given the input.

This is code-golf so the shortest code in bytes wins

Answer 1

APL (Dyalog Unicode), 17 bytes

≢⍉↑⊆⍨∨/≠/∨⍀⎕a∘.=⎕

Try it online!

Answer 2

APL (Dyalog Unicode), 39 bytes

{⌈/≢¨⊆⍨∊∨¨/{(⊂⍵){1 3 2≡⍋∊⍺[⍋⍺]⍵}¨⎕A}¨⍵}

Try it online!

-4 bytes thanks to ovs
-6 bytes thanks to following a similar approach to Jonah's J answer
-6 bytes thanks to a clever observation from ovs

Answer 3

J, ^{52 48 41 40 38 34} 29 bytes

3 :'>./#;._1#.~:/"1+./\a.=/y'

Try it online!

^{Based on ngn's beautiful insight.}

^{-5 thanks to Lynn for realizing an explicit verb would be shorter than a tacit one}

This is a corrected answer after the clarification that ABCD should return 1, not 3.

answer before clarification, ^{52 48 41 40} 38 bytes

[:>./[:<:@#;._1@OR a.(+/\*+/\.)@e."1]

Input is a matrix whose rows are the pairs of strings like AC. For example, let's assume our input is:

AC
EB

• a. ... e."1] - Is each ascii character an element of an input row? This returns a 0-1 matrix like:

                   A   C  at positions 65 and 67
                   v   v
    0 0 0 0 .... 0 1 0 1 0 0 ... 0
    0 0 0 0 .... 0 0 1 0 0 1 ... 0
                     ^     ^
                     B     E
  

• (+/\*+/\.) - Applies to each row from last step. We'll look at happens to the first row. Create scan sums from both directions:

    0 0 0 0 .... 0 1 1 2 ... 2 2 2  <-- +/\
    2 2 2 2 .... 2 2 1 1 ... 0 0 0  <-- +/\.
  

  and multiply them together *:

    0 0 0 0 .... 0 2 1 2 ... 0 0 0
  

• [:...OR Reduce resulting rows by OR:

    0 0 0 0 .... 0 1 1 1 1 1 ... 0
  

• [:<:@#;._1 Split on zeroes, and take the length of each resulting segment of ones, minus 1 <:@#.

• [:>./ Max

Try it online!

Answer 4

Haskell, 86 bytes

• -5 bytes thanks to kops for suggesting fst$span(`elem`y)[a..].
• +8 bytes to comply with the updated challenge rules.

f x|y<-do[a,b]<-x;[a..pred b]++[b..pred a]=maximum[length.fst$span(`elem`y)[a..]|a<-y]-1

Try it online!

The function f takes the logbook x as input (as a list of two-character strings) and returns the longest possible traversal.

How?

f x|                                -- f is the function that takes a logbook x
    y<-do[a,b]<-x;                  --   define y to be the concatenation for each "ab" in x
        [a..pred b]++[b..pred a]    --     of the two ranges [a..pred b] and [b..pred a] (one of which will be empty)
    =maximum[length.                -- f returns the maximum length
        fst$span(`elem`y)[a..]      --   of the longest range starting from a whose elements all belong to y
        |a<-y]                      --   where a is a character in y

Answer 5

R, 61 69 65 bytes

for(i in scan(,""))F[(j=utf8ToInt(i)*2):j[2]]=1;max(rle(F)$l)%/%2

Try it online!

Unfortunately, edits made to the task specification broke the original answer :(

On the brighter side, the changes needed to fix it were not so drastic.

Explanation

First, we use utf8ToInt to convert the characters to their byte values. Then, we fill the vector F with ones at the range of positions from start byte to end byte. R allows assigning to indices outside of existing range, and upon such assignment sets all preceding empty positions to NA. Finally, we take Run Length Encoding and return the length of the longest run. Conveniently, rle doesn't list all NA as a single long run, but rather as many runs of length 1.

In the original version, ranges such as AB CD became fused together:

...     A  B  C  D    ...
... 64 65 66 67 68 69 ...
... NA  1  1  1  1    ...

To resolve this, we simply multiply the range boundaries by 2, and thus gain a separator between adjacent routes when they don't overlap:

...      A       B       C       D  ...
... 129 130 131 132 133 134 135 136 ...
... NA   1   1   1  NA   1   1   1  ...

Finally, integer division by 2 gives the desired result.

Answer 6

Ruby, 79 71 bytes

->a{r=c=0
a.map{|i|r|=-1<<i.ord^-1<<i[1].ord}
(c+=1;r&=r*2)while r>0;c}

Try it online!

Ruby probably isnt' the best language for this bit twiddling approach, but I haven't seen it yet so it's worth posting. The idea is to take -1 and shift it to the left according to each letter, then XOR it with the other letter in the pair. It's best explained with an example (ignore 64 zeroes missing to the right.)

B ->    ...1111111100 
G ->    ...1110000000
XOR     ...0001111100

Thus there are 5 clear paths between B and G.

These are then combined by ORing together.

At the end of ["BG", "CA", "FI", "OK"] we have r=111100111111110 (plus 64 trailing zeroes).

To find the longest run of 1s, we now count the number of times r must be ANDed with r*2 until r becomes zero. Each time we perform this operation, the length of each group of 1's is reduced by one.

Answer 7

Charcoal, 16 bytes

ＩＬ⌈⪪⭆α⬤θ⊖ΣＥλ‹ιν1

Try it online! Link is to verbose version of code. Explanation: For each uppercase letter, compare it against all of the logs to see whether it precedes neither or both entries, resulting in a string of exclusions e.g. 00000000110000111111111111 for an input of BG, CA, FI, OK. Split that string on 1s and output the length of the longest string of 0s.

    α               Predefined uppercase alphabet
   ⭆                Map over characters and join
       θ            Log array input
      ⬤             All satisfy
           λ        Current log
          Ｅ         Map over elements
             ι      Outer character
            ‹       Less than
              ν     Inner character
         Σ          Summed
        ⊖           Decremented
   ⪪           1    Split on literal `1`
  ⌈                 Take the maximum (longest)
 Ｌ                  Take the length
Ｉ                   Cast to string
                    Implicitly print

Answer 8

Retina, 71 bytes

A`(.)\1
%O`.
%T`L`_L`.$
\B
-
¶

~`.+
.+¶26$*¶Y`\_`L¶[$&]¶_
L`_+
O^`
\G_

Try it online! Takes a newline-separated list, but the test suite takes a comma-separated list for convenience. Explanation:

A`(.)\1

Delete identical pairs, as they have nothing to contribute (other than crashes).

%O`.

Sort each pair of letters into order.

%T`L`_L`.$

Decrement the second of each pair, as the ranges are effectively half-open intervals.

\B
-

Insert a - between each pair of letters.

¶

Join all of the letter ranges together.

~`.+
.+¶26$*¶Y`\_`L¶[$&]¶_

Wrap the letter ranges in Retina code that replaces legal edges with _s, then evaluate that code.

L`_+

Keep only the runs of _s, discarding any remaining letters.

O^`

Sort the longest first.

\G_

Output its length.

Example of generated Retina code for the input BG, CA, FI, OK:

.+
26*
Y`\_`L
[B-FA-BF-HK-N]
_

Explanation:

.+
26*

Replace the ranges with 26 _s.

Y`\_`L

Cyclically transliterate the _s to uppercase letters.

[B-FA-BF-HK-N]
_

Replace all the legal edges with _s.

Answer 9

Haskell, 77 66 bytes

f l=maximum$scanl(\m c->sum[m+1|any(foldr1(/=).map(c>))l])0['A'..]

Try it online!

-11 bytes thanks to @xnor by reformulating as a scanl and informing me that ['A'..] is a finite list!

f computes for each character in effectively A..Z whether or not it is starting point of a traversable leg, and keeps track of the running count.

The magic is in the condition any(foldl1(/=).map(c>))l which makes use of the fact that x is comprised of length 2 strings. map(c>) asks whether each endpoint of the journey is beyond c and foldl1(/=) takes the xor of the results, so c satisfies this condition only when it is in the half-inclusive journey. If c satisfies this for any journey, our count will get incremented, otherwise reset to 0.

Answer 10

Jelly, 14 bytes

ØA<þ^/€€|/ṣ0ṀL

Try it online!

This steals the idea to check if a letter precedes neither or both bound to determine if it's in range from Neil's Charcoal answer. Go upvote them!

Explanation

ØA<þ^/€€|/ṣ0ṀL  Main Link; takes a list of pairs of characters
   þ            Make a product table
  <             using the < operator
ØA              between the entire uppercase alphabet
                and the input (gives a list of lists of pairs)
       €        For each sublist (corresponding to a input pair)
      €         For each pair (corresponding to each letter in the alphabet)
    ^/          Reduce by logical XOR (now a list of length-26 lists each being 0 or 1 depending on if the letter is in the range)
        |/      Reduce the entire thing by logical OR (now a length-26 list with 1 where the letter is in a range and 0 otherwise)
          ṣ0    Split at 0s
            Ṁ   Maximum
             L  Length

Answer 11

JavaScript (V8), 177 bytes

b=>Math.max(...b.map(t=>[...t].sort()).sort((w,x)=>(w[0]>x[0])-.5).reduce((r,x)=>x[0]<p[1]?(p[1]=(x[1]<p[1]?p:x)[1],r):[p=x,...r],p=[]).map(g=>(i=parseInt)(g[1],36)-i(g[0],36)))

Try it online!

Tried to do this without looking at any of the other answers' tricks. This can potentially be pretty heavily outgolfed.