Longest spell to cast from pages of spellbook

Question

While practicing for a school coding challenge, I came across this problem. My code got the right answers but exceeded the time limited. Any tips for how to reduce the time complexity?

https://pctc.cuttle.org/index.php?action=user_question&grq_id=946

Problem

Details

My code:

x = int(input())
c,a,mx,ct,og,mx = 0,0,0,[0],[0]*x,0
for i in range(x):
    og[i] = int(input())
#copying input into list
for i in range(len(og)):
    t = og.copy()
    #copy across into temp
    j,c = i,0
    while t[j]!= -1:
        #-1 is a marker for when the loop has already visited a page
        temp = t[j]
        t[j] = -1
        j = temp-1
        c+=1
    if c >= mx:
        #only append to list if greater than prev
        mx = c
        ct.append(c)
print(mx)
print(ct.count(mx))

Sadly I don't have access to the testcases.

Answer 1

obscure code

c, a, mx, ct, og, mx = 0, 0, 0, [0], [0] * x, 0

Uggh, this is terrible in so many ways. Please don't write code like that.

Find a classmate. Show them this one line of code, or all the code up to a given line of code, and ask them to say out loud what the code does. If they cannot offer a cogent explanation related to the Business Domain (here, wizardry), then go back and write new code. Repeat, until your partner is able to convince you that they understand the technical idea you were trying to convey in the source code.

The problem statement introduced two variables:

• n pages, and
• page index i (one-origin, like Fortran, different from python's zero-origin)

You get those variables for free. The others, you're going to have to work for.

Perhaps og denotes "original grimoire"? If so, spell that out for us, with a longer identifier or at least with a # comment.

c,a,mx,ct,og,mx = ...

This code is so obscure that not even you can read it, as we see mx being introduced twice.

No one you show this code to knows what c, a, mx, or ct mean. And neither will you in a month or two. You owe it to the Gentle Reader to explain what's going on, in sufficient detail that a maintenance engineer could maintain this code (fix a bug, refactor, speed up, add a feature) without needing to have a conversation with you.

The tuple unpack (the , comma notation) that you're using here does not aid clear exposition. If you really want to zero a bunch of variables in one line (not necessarily a good approach to follow) then at least say so clearly:

c = a = mx = 0

Now, as I'm parsing out the sequence of several variables, at least I needn't juggle a few values to match up -- "is this variable being set to a single-valued list? Is it being set to a bunch of zeros? Or is it being set to a scalar?" The line does just one thing, it sets stuff to zero.

be boring

x = int(input())

This is valid python syntax.

It's unclear how this line of code relates to the Problem Statement. It would have been clearer if you either (A.) adopted the contest's notation of n, or (B.) explained the "change of variables" to the Gentle Reader, who after all has just finished reading the contest's explanatory material. Writing code offers lots of room for creativity, but that doesn't mean you should make up new names for things that already have a name.

Prefer: n = int(input())

already visited graph nodes

        # -1 is a marker for when the loop has already visited a page
        t[j] = -1

That is a helpful comment, and I thank you for it. Please continue to write such comments.

Or, write code which explains what the English sentence explains. Rather than using an obscure magic number for this sentinel, we could explicitly name it:

VISITED = -1
...
        t[j] = VISITED

Rather than overwrite the t vector, it might be more convenient to use this familiar idiom:

seen = set()
...
        seen.add(j)

and then we can ask if k in seen: to find out if node k has already been visited.

algorithm

cycles

We are given a graph, and asked to find cycles in it, as well as paths which lead to a cycle. In particular, we care about finding longer and longer paths, with size bounded by n. The contest refers to path length as "spell length".

By the pigeonhole principle there must be at least one cycle, of length n or smaller. Consider this brief example:

• 1: 2
• 2: 3
• 3: 1

              2 --> 3 --> 1
              ^           |
              |           |
              +-----------+

Page 1 takes us to page 2, and we soon are back at a visited page. Max path length through a cycle is 3, and there are three such paths or "spells", depending on where we start.

Consider this larger graph:

  1 --> 2 --> 3 --> 4 --> 5 <-- 6 <-- 7 <-- 8 <-- 9
              ^           |
              |           |
              +-----------+

Starting on either pages 1 or 2 will take us to page 3 and hence the cycle. But it would be best to start on page 9, which brings us to the cycle via page 5. Once having exhausted the cycle, we're done.

There's more than one way to do cycle detection. Some ways use more memory than others. For example the seen set recommended above uses O(n) memory. In contrast Floyd's tortoise and hare approach uses O(1) memory, at the cost of maybe taking a little longer to complete, though still with maximum of O(n) time complexity, even shorter if cycle lengths are << n.

For any given node, you want to identify

• whether it is a cycle node (part of a cycle), and
• what that cycle length is.

Then the problem boils down to finding longest tail (e.g. 9 above) that leads into a longish cycle. Let's see, how could we do that?

reverse links

The problem has inconveniently given us the forward link from a given node to its successor node. So 9 leads us down into a cycle. But we might have first (wastefully!) tested 6 and 7 before that.

If we had the reverse link from a given node to its predecessor, we could start at the cycle and efficiently chase back from 5 to 6 and eventually 9. (We would also have to explore the 3 --> 2 --> 1 path -- them's the breaks.)

memory

The contest explains that n is bounded by 3e5, and our datastructures must fit within a fixed memory budget. Now, python lists have a lot of things going for them; they are certainly flexible and convenient. But there's a lot of pointers in there, n of them, in fact. On a 64-bit machine, suppose it takes about 8 bytes to store an int value. When we stick it in a list, that costs another 8 bytes for the list to point to the integer object.

Flexibility is all well and good, but we'll never store a str nor a float object, since the contest uses strictly int page numbers. An array lets us efficiently allocate storage for n integers, saving a ton of storage for all those pointers:

from array import array

rev_link = array("I", range(n))
assert rev_link.itemsize == 4  # each element is a 32-bit unsigned integer

Since 3e5 is less than four billion, we're confident each page number will fit within that allocation. Also, the allowed memory budget turns out to be pretty generous; we can allocate a little more than two hundred bytes per input node.

Iterate through the page numbers, recording reverse links, at O(n) cost. A node (e.g. 5) can have in-degree greater than one, so we're probably back to using n containers, such as lists, for this.

longest path

Now it's just a matter of doing a DFS outward from each cycle, in search of long paths.

Choose a cycle node. Use simple DFS, Kruskal, Borůvka, or Prim to find paths leading outward, away from the cycle. Identify the longest path(s) and report them.

memoize

Record “longest path from here” at each node. For cycle nodes that’s the length of the cycle. DFS will track its outbound path lengths and record max path length at each node it visits. Notice that if there are C cycles to process, we could compute C max() assignments per node.

Answer 2

One thing that these kinds of sites like to do is generate huge inputs that are trivial when viewed from the right angle.

One "huge" input would be an array such that a[n] = n. This corresponds to the 6 entry in your example array, and it immediately links to itself. The result is that each such page has a maximum value of 1.

This is not a great example for them, because you can solve it so directly. However, it does consume a lot of memory, and might be a good attack against languages that do static allocation.

Another example would be a long series of array entries that each refer to a predecessor or successor. That is, a[n] = n-1 or a[n] = n+1. For a "naive" program that attempts to compute the run of each array entry without reference to any work that has been done before, the time cost is going to be equally huge. I suspect this is the attack that is causing your test cases to fail.

You can address this by taking a "dynamic programming" approach. First pick a mechanism to indicate that you have not computed a value for a "page." Since each page has a minimum "spell length" of 1 in the case where it directly links to itself, the value 0 seems to be a good indicator. So initialize a parallel array:

NOT_COMPUTED_YET = 0
max_links_from_node = [NOT_COMPUTED_YET] * N

With this done, you can compute your answers, but as part of your computation you should pass the values through this new array:

if max_links_from_node[i] == NOT_COMPUTED_YET:
    ...
else:
    ...  + max_links_from_node[i]

One other thing to watch out for is recursion. Using this approach makes it very tempting to write a recursive solution. And in fact, that may work. But recursion trades looping for stack frames, and stack frames are surprisingly expensive (because the possible number of them is usually much, much lower than the possible number of entries in a list, e.g.). So if you choose to write a recursive solution, don't be surprised if it fails one test case due to stack overflow. And don't lose hope - it is fairly easy to switch from a recursive solution to one where you manage the "stack" yourself.

Answer 3

I think J_H's answer does a great job at detailing the style issues in your code, but I think there hasn't been a good and simple explanation of how to improve the algorithm yet, so here are my two cents.

The problem

The main issue with your approach is that you end up retracing the same path a lot of times. Let's say you have a simple spellbook that is just a single loop (1->2->3->4->1). You start from 1, go through all 4 pages and come back to 1, spell length is 4; then you start from 2, go through all 4 pages again and come back to 2, spell length is 4... You repeat this for every page, when you had all the information you needed at the end of the first loop! It's not a big deal when there are 4 pages, but since books can contain up to 300,000 pages this can end up taking a very long time.

Since you may end up going through all n pages for each of the n spell lengths you are trying to compute, we can say that your algorithm has a complexity of \$O(n^2)\$. We can do better.

Solving loops all at once

Looking at the previous example the solution is simple: when we complete a loop we set the spell length of each page of the loop to the length of the loop itself.

There is just one thing we need to be careful with: where does the loop start?

Managing chains leading to loops

Let's look at this other example spellbook: 1->2->3->4->2. Here we have a loop containing pages [2,3,4], and page 1 pointing to this loop. If we start counting from 1 we will get a spell length of 4 pages, but the loop itself only has a length of 3. Here we should set 4 as the spell length of page 1 and 3 as the spell length of all other pages.

A simple way to manage this situation is to keep a list of the pages you went through for the current spell. You will know which page started the loop (the one you tried to visit twice) so you know that all pages before this one are outside the loop. You can still set the spell length for all of them, but you should set decreasing lengths for the starting chain and equal lengths for the loop.

In code, this would be something like:

# visited_pages is the list of pages encountered during this spell
# loop_trigger is the page that we attempted to read twice
length = len(visited_pages)
loop_started = False
for page in visited_pages:
  spell_lengths[page] = length
  if page == loop_trigger:
    loop_started = True
  if not loop_started:
    length -= 1

Better loop detection

Your method of detecting a loop is based on copying the spellbook and modifying the copy. This can be an expensive operation when the spellbook gets large, but a better solution (as already noted by J_H) can be implemented using a set of pages seen. Add each page you visit to the set and check if you have already visited a page with if page in pages_seen:. That's simple and efficient.

Note: you may be tempted to use the list of visited pages also to check if you have already seen a particular page, but it is a bad idea. Checking if an element is in a list is \$O(n)\$, while checking if it is in a set is \$O(1)\$ (with lists you have to compare the page with every element of the list, while sets use hash magic to tell you the answer straight away).

One more optimisation: reuse partial values

There is one last thing we can improve, and this has been suggested in aghast's answer. If at any point we read a page for which we already know the spell length, we can stop looking and simply add the length of that spell to the number of pages we have visited in the current run. This will only happen for chains outside a cycle (because there can be no such thing as a partially-visited cycle), so you can adapt the previous code by setting loop_trigger to None in this case and adding the right value to length.

The final result

If you implement all this you will have an algorithm that never looks at the same page twice: in each run you compute the length of all pages you visit and future runs don't recompute any of the values seen in previous runs. This is \$O(n)\$ and should be able to tackle any test case without running out of time.

P.S.: Memory limits

You don't really have to worry about memory limits. Doing a very rough calculation each integer can be stored in 32 bits (4 bytes) and we will store up to 300K of them in each list of numbers, for a total of 1.2MB. The 64MB limit allows us to keep in memory enough of these lists that there will never be an issue.

Answer 4

This review is for coding style and good coding practices; it does not improve the speed.

Layout

The layout could use some improvements.

Making an assignment to 6 variables on one line is error-prone and hard to understand, especially when assigning different values.

You made an assignment to the same variable twice: mx.

Variable a is not needed and can be removed.

Perhaps a few lines would be better:

c, mx = 0, 0
ct = [0]
og = [0] * x

Adding blank lines after the for loops would improve readability.

Documentation

You should add documentation at the top of the file to summarize the purpose of the code, including expected input and typical output.

Input

You should add text for each input prompt to guide the user.

x = int(input('How many numbers? '))

og[i] = int(input('Next number? '))

While it is good that you cast the input to int, consider adding more input checking just in case the user accidentally enters a letter or a number that is out of range. The pyinputplus module is great for that.

Note: if the input is known to be good, for example, if you post your code into a site that automatically runs your code as part of a programming challenge, then there is no need for input checking. It would likely slow your code down.

Output

When I run the code, it is hard to distinguish the input from the output. Add some information to the print-out:

print(f'mx = {mx}')
print(f'count = {ct.count(mx)}')

Naming

Most variables do not have meaningful names. There is no penalty for having longer variable names. At a minimum, add a comment for each variable.

Whitespace

The PEP 8 style guide recommends:

• Space after comma: j, c = i, 0
• Space around assignment operators: c += 1
• Space around comparison operators: t[j] != -1

Simpler

There is not need to calculate the len of og since you already know it is x. Change:

for i in range(len(og)):

to:

for i in range(x):