CODEWITHSUNDEEP
python-3.xlistsequencegraph-theorytraversal
Ailurophile
Ailurophile

Reputation: 3005

How to calculate the longest consecutive traversal possible in Python

Context

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, the 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.)

I'm trying to return the length of the longest consecutive traversal possible; in other words, computing the maximum number of consecutive edges known to be safe.

def maximumTraversal(log):
    length = []
    for i in log:
        length.append(abs(ord(i[0]) - ord(i[1])))
    return max(length)

the log 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.

I'm able to find the traversal/length in both directions.

log = ["BG", "CA", "FI", "OK"]
maximumTraversal(log)

This returns

5

The Expected output for logbook = ["BG", "CA", "FI", "OK"], 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.

I'm unable to find the possible consecutive traversal of the above condition? How can I do that?

Upvotes: 1

Views: 485

Answers (1)

John Kugelman
John Kugelman

Reputation: 361605

You can store the information you need in 25 bits, one for each edge. The first bit is for AB, the second for BC, the third for CD, etc.

A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Iterate over each log entry and set the corresponding bits to 1. This will naturally handle overlapping log entries without issue.

Here's what each step would look like for the logbook ["BG", "CA", "FI", "OK"]:

[]
A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

["BG"]
A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z
 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

["BG", "CA"]
A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z
 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

["BG", "CA", "FI"]
A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z
 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

["BG", "CA", "FI", "OK"]
A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y-Z
 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0

When the dust settles you can find the longest consecutive traversal by finding the longest run of adjacent 1s.

Upvotes: 1

Related Questions