13
\$\begingroup\$

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 so the shortest code in bytes wins

\$\endgroup\$
2

11 Answers 11

14
+500
\$\begingroup\$

APL (Dyalog Unicode), 17 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
6
  • \$\begingroup\$ There are two pairs of parentheses: The operators and \ bind to their operands which shortens (+\⍣¯1) to +\⍣¯1, and (⊢,⌽¨)⍵ is the same as ⍵,⌽¨⍵. 53 bytes (I've taken the TIO template from one of Adám's answer and I think the Unicode version is the preferred one.) \$\endgroup\$
    – ovs
    Apr 14, 2021 at 17:55
  • \$\begingroup\$ @ovs thanks for the golfs, and thanks for the template! i'll keep that bookmarked and i'll use the unicode one if it's preferred \$\endgroup\$
    – hyper-neutrino
    Apr 14, 2021 at 20:23
  • \$\begingroup\$ @hyper-neutrino After a lot of head banging I found a different approach in J. I suspect you could save by 10+ bytes by using something similar in APL. \$\endgroup\$
    – Jonah
    Apr 15, 2021 at 13:11
  • 1
    \$\begingroup\$ Ugh, although I just noticed that both of our solutions fail the test case 'AB' 'CD' which was added by the OP in the comments, and is supposed to return 1, not 3. \$\endgroup\$
    – Jonah
    Apr 15, 2021 at 13:51
  • \$\begingroup\$ After all values are either 0 or 1, so 0≠ is the same as , and (⊢⊆⊢) can be shortened to ⊆⍨. 39 bytes (There was another extra pair of parenthesis) \$\endgroup\$
    – ovs
    Apr 16, 2021 at 18:04
5
\$\begingroup\$

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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Thanks for the comments under my post; I think I've managed to save a significant amount of bytes by following a mostly similar approach to yours! Unfortunately, it does seem that this question's clarifications now invalidate this answer, though I suspect you might be able to just subtract one from the upper bound of each range? I'm not exactly sure how well that would work in J. \$\endgroup\$
    – hyper-neutrino
    Apr 15, 2021 at 18:56
  • 1
    \$\begingroup\$ Indeed. I only noticed after finishing. I have an idea for solving the clarified problem which I'm going to attempt tonight. \$\endgroup\$
    – Jonah
    Apr 15, 2021 at 20:37
  • 1
    \$\begingroup\$ This has enough [:s that you're better off writing an explicit 3 :'>./#;._1#.~:/"1+./\a.=/y'. \$\endgroup\$
    – Lynn
    Apr 21, 2021 at 0:14
  • \$\begingroup\$ @Lynn Well-spotted! Thanks. \$\endgroup\$
    – Jonah
    Apr 21, 2021 at 0:17
4
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ [a..until(`notElem`y)succ a] can be shortened to fst.span(`elem`y)$[a..]. Try it online (I also added the other test cases) \$\endgroup\$
    – kops
    Apr 14, 2021 at 20:41
  • \$\begingroup\$ @kops Amazing, thanks! (actually, the code you linked can be shortened to 78 bytes with a trivial change) \$\endgroup\$
    – Delfad0r
    Apr 14, 2021 at 20:45
  • \$\begingroup\$ Clarifications to the challenge have unfortunately invalidated this answer now. AB CD should give 1, since A -> B and C -> D are the only two edges that can be traversed, and B and C are not connected in this example. \$\endgroup\$
    – hyper-neutrino
    Apr 15, 2021 at 18:53
  • 1
    \$\begingroup\$ @hyper-neutrino Fixed, at the cost of 8 bytes :( \$\endgroup\$
    – Delfad0r
    Apr 15, 2021 at 20:41
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Cool approach, nice one \$\endgroup\$
    – rak1507
    Apr 14, 2021 at 22:15
2
\$\begingroup\$

Charcoal, 16 bytes

IL⌈⪪⭆α⬤θ⊖ΣEλ‹ιν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
          E         Map over elements
             ι      Outer character
            ‹       Less than
              ν     Inner character
         Σ          Summed
        ⊖           Decremented
   ⪪           1    Split on literal `1`
  ⌈                 Take the maximum (longest)
 L                  Take the length
I                   Cast to string
                    Implicitly print
\$\endgroup\$
2
  • \$\begingroup\$ Clarifications to the challenge have unfortunately invalidated this answer now. AB CD should give 1, since A -> B and C -> D are the only two edges that can be traversed, and B and C are not connected in this example. \$\endgroup\$
    – hyper-neutrino
    Apr 15, 2021 at 18:53
  • \$\begingroup\$ @hyper-neutrino That's great news! \$\endgroup\$
    – Neil
    Apr 15, 2021 at 19:12
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Clarifications to the challenge have unfortunately invalidated this answer now. AB CD should give 1, since A -> B and C -> D are the only two edges that can be traversed, and B and C are not connected in this example. \$\endgroup\$
    – hyper-neutrino
    Apr 15, 2021 at 18:54
  • \$\begingroup\$ @hyper-neutrino Ugh, that sucks; I may have to delete this answer. \$\endgroup\$
    – Neil
    Apr 15, 2021 at 19:14
  • \$\begingroup\$ @hyper-neutrino Well, I came up with a fix, but at what cost... \$\endgroup\$
    – Neil
    Apr 15, 2021 at 19:29
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.