←⌂ / ←/devlog

16 — 1337

algs 1337 euler

Created: 07 May 2026, Modified: 13 May 2026

WIP - this devlog is unfinished

Introduction

I don’t know if it is a good idea to make a devlog about this, but I’m having a go. If I end up abandoning I will add a note to the start that it’s abandoned.

[I guess to have some kind of objective for this devlog, I will try to do the first 10 problems of each of the sites leetcode.com and projecteuler.net, in alternating order. Then if I want to continue this, I could do a pt 2 covering the next 20, and so on.]

The idea is I aspire to one day maybe get a job in programming, so I maybe should make a leetcode.com account and familiarise myself with the kind of problems you get in job interviews.

I actually didn’t need to create an account, you can connect with GitHub. It gave me the same username as on my GitHub account (leetcode.com/u/plu5).

(but you have to confirm your email before it lets you run or submit anything)

I created already on the 5th a repository algs where I uploaded old things I did and where I can put leetcode.com stuff in the subfolder 1337, and projecteuler.net stuff in the subfolder euler.

Relevant past experience

In the past decade, I have read the books:

  1. Structure and Interpretation of Computer Programs (1996?)
  2. Introduction to Algorithms 3e (2009)
  3. Programming Interviews Exposed 4e (2018)
    • It uses Java, which I don’t like, but a friend of my dad’s who converted from plumbing to programming recommended it, so I felt it was my duty to read it all.
  4. Cracking the Coding Interview 6e (2015)

3 is the only one I finished (because of that sense of duty I mentioned).

I attempted to participate in Advent of Code 2024 (1.5 years ago), woke up at night every night to try to get a good time, and had my ego crushed after a few days of manifest inadequacy. I massively overestimated my ability compared to the mean and underestimated what it takes.

Competitive programming is its own skill, there are people who do just that, and are incredibly good at it. If you come from ordinary open source programming it can be a bit of a shock. It’s not completely separate from ordinary programming, but normally we don’t optimise for time to write code and submit. I noticed in Advent of Code experienced people will detect straight away “ah, it’s an X problem”, because it boils down to a limited set of types of problems, and once you have done them a million times you have established code patterns you whip out, people have their own Advent of Code libraries.

And the classification to types of problems is something I find incredibly interesting.

It would be cool to 100% Advent of Code like others have done, but stop, this devlog is meant to be about leetcode.com problems.

Decisions before tackling the first problem

Languages available: C++, Java, Python3, Python, JavaScript, TypeScript, C#, C, Go, Kotlin, Swift, Rust, Ruby, PHP, Dart, Scala, Elixir, Erlang, Racket. Is this by order of popularity?

In the absence of Elisp (I’m sure a lot of employers are hiring in that language), I will choose good old Python3.

Python 3.14.
Most libraries are already imported automatically for your convenience, such as array, bisect, collections. If you need more libraries, you can import it yourself.
For Map/TreeMap data structure, you may use sortedcontainers library.

On the site the function needs to be in a class called Solution, but in my files I am just going to write my functions top level, to avoid having to instantiate the class and avoid the extra level of indentation. I would like to be able to return to my files for reference when I need to implement something similar so it needs to be structured somewhat generically.

LC1: Two Sum

Problem 1 is to return the indices of two different elements in an array of integers that add up to a given number. And we need to assume that there will only be one solution (only two elements that would add up to it).

The naïve solution is O(n²); to check each number against every other number.

def twoSum(nums, target):
    for i, a in enumerate(nums):
        for j, b in enumerate(nums):
            if i != j and a + b == target:
                return [i, j]


if __name__ == '__main__':
    def v(x, expected):
        assert x == expected, x

    v(twoSum([2, 7, 11, 15], 9), [0, 1])
    v(twoSum([3, 2, 4], 6),      [1, 2])
    v(twoSum([3, 3], 6),         [0, 1])
    print("Tests passed")

The little v utility function is to see the return value in case of failure, otherwise Python assert doesn’t tell us. (The , x after the assert is to put that value in the body of the AssertionError that will be raised). Avoid the common mistake of using assert with parentheses that I totally didn’t fall for, thanks Evgeni Sergeev.

Can you come up with an algorithm that is less than O(n²) time complexity?

I remember from the books that usually the way to reduce time complexity is trading it for space. Iterating the list just once and storing something in a cache. Actually we could even iterate it more than just once, so long as it’s less than 2 nested loops; having 2+ loops for example that are not nested reduces to just O(n), same as having just one loop (in reality we would prefer the solution with just one loop I guess, but the time complexity is the same).

How could it be useful in this problem though? The idea that immediately comes to me is in the first iteration discard of numbers that are clearly unsuitable, like numbers greater than the target. But this doesn’t really help much, because O((n-c)²) still reduces to O(n²).

Another idea is to sort the list. But then what?

Another observation: For every number we can subtract it from the target to find what it would need to be added to.

Say we have a sorted list [2, 7, 11, 15] and the target 9. Upon seeing 2, we do 9-2 = 7, add this result to a list of numbers we’re looking for. We also need to store the index so that we would know what index to give at the end. lookingfor = {7: 0}, i.e. the number at index 0 is looking for 7 to complete the addition to reach the target. Each subsequent iteration we can look up in this map if the current number is in lookingfor, and if yes, return the index that was looking for it and the current index. If not, add what the current iteration is looking for: lookingfor[currentnumber-target] = currentindex (but only if it’s >0. or just return straight away at the start if the currentnumber > target, as it’s never going to be one of the numbers we’re searching for in that case).

The problem with that is the indices will no longer be correct after we sort the list (or they may be correct by accident or if the list is already sorted, but obviously we can’t count on that).

The same approach (though with continue instead of return if currentnumber > target) without sorting the list works for the examples. So I submitted it, but it did not pass all the test cases.

def twoSumFail(nums, target):
    """Failed attempt at a O(n) solution"""
    lookingfor = {}
    for i, a in enumerate(nums):
        if a > target:
            continue
        r = lookingfor.get(a, None)
        if r is None:
            lookingfor[target-a] = i
        else:
            return [r, i]


if __name__ == '__main__':
    def v(funcs, args, expected):
        for f in funcs:
            res = f(*args)
            assert res == expected, f'{res} != {expected} ({f.__name__})'

    funcs = [y for x, y in globals().items() if x.startswith('twoSum')]
    v(funcs, ([2, 7, 11, 15], 9), [0, 1])
    v(funcs, ([3, 2, 4], 6),      [1, 2])
    v(funcs, ([3, 3], 6),         [0, 1])
    print("Tests passed")

Do you like my new and improved testing facility? Good old Python introspection! I modified it to run the asserts of the test cases on all functions whose name starts with ‘twoSum’, and the AssertionError message to tell us both the expected and real return value, and the name of the function that returned it. (I omitted the definition of the previous function twoSum, but I’ll be keeping all working solutions in the file.)

It looks like all the submissions, including failed ones, get assigned an ID and stored on a webpage (although I can’t see that from private browser, not sure if another registered user can) and you can see them on your progress page and even leave little notes.

It fails on input [-3,4,3,90], 0.

I forgot to consider negative numbers. We shouldn’t be skipping numbers that are greater than the target. Ok, and if I just get rid of that check, it’s fine? Apparently.

def twoSum2(nums, target):
    lookingfor = {}
    for i, a in enumerate(nums):
        r = lookingfor.get(a, None)
        if r is None:
            lookingfor[target-a] = i
        else:
            return [r, i]

Runtime is the best possible, but space complexity could be improved:

20.69MB
Beats 8.55%

Time complexity O(n), space complexity O(n). As opposed to our previous solution, which was time O(n²) and space O(1) (constant). Would it actually be O(1) or just 0? The first solution doesn’t even assign any variables (I guess it does; the arguments). Well look, it’s irrelevant.

Not sure how to reduce space complexity while keeping time O(n). My only idea is to store each number as is and look up the result of the subtraction, but this won’t change the complexity of either time or space.

I gave up and looked at the hints and the editorial, and neither mention there existing a solution O(n) in time and better than O(n) in space. Maybe the percentage refers to percentage out of all algorithms, including time O(n²) ones?

This gives me Shenzhen I/O flashbacks. Maybe I should have mentioned that in relevant past experience. Only if we get to implement our own variant of solitaire.

Looking at the editorial,

  1. the standard way of writing this algorithm looks to be indeed to store the numbers and associated indices as is, and look up the result of the subtraction.
  2. I should have checked the existence of an element in the dictionary with in instead of using .get().
  3. return [] at the end so that we always return a list, even if the elements are not found (though we were told to assume one will always be found). Which is not really necessary in Python, but is in for example C++ where you’d return {} if your return type is a vector.
def twoSumStandard(nums, target):
    """Time: O(n), space: O(n)"""
    seen = {}
    for i, a in enumerate(nums):
        b = target - a
        if b in seen:
            return [seen[b], i]
        seen[a] = i
    return []

I am wondering if there is a solution that uses sorting. I guess it cannot have better space complexity than O(n), because we necessarily have to keep track of the original indices.

projecteuler.net

For this site, to be able to register we have to solve a problem first. “Let none but enquiring minds enter”.

In addition to a captcha. “Let none but human minds enter”.

I won’t cover it because they probably don’t want you to, but I guess I can write down what it was at least: the sum of odd squares in the first 128000 square numbers.

Just after I did it and finished the registration form, my internet went down. So I then had to do it again and it was the same question except a different number of square numbers.

Eu1: Multiples of 3 or 5

It looks like the questions on this site we only put in the answer, not the algorithm. Which does simplify it, as just writing an algorithm that will work is far easier than to write one with the lowest time and space complexity possible. In this sense it kind of resembles Advent of Code.

The first question is the sum of all multiples of 3 or 5 in 1000. Algorithmically, this is very similar to the question with the squares that we have to do to be able to register.

#!/usr/bin/env python3
# 2026-05-08 05:10
def multiplesOf3Or5(upTo):
    sum = 0
    for n in range(1, upTo):
        if n % 3 == 0 or n % 5 == 0:
            sum += n
    return sum


if __name__ == '__main__':
    def v(funcs, args, expected=None):
        for f in funcs:
            res = f(*args)
            if expected is not None:
                assert res == expected, f'{res} != {expected} ({f.__name__})'
            print(f'{f.__name__}{args} -> {res}')

    funcs = [y for x, y in globals().items() if x.startswith('multiplesOf3Or5')]
    v(funcs, (10,), 23)
    v(funcs, (1000,))

My testing facility has improved a tad; now expected is optional, and the function, arguments, and result get printed for each call.

This can be reduced to just one line:

def multiplesOf3Or5OneLiner(upTo):
    return sum(n for n in range(1, upTo) if n % 3 == 0 or n % 5 == 0)

This is considered a brute-force solution, because we’re checking every possible number up to the limit.

To solve it by hand we could sum the arithmetic series for the multiples of 3 and the one for the multiples of 5, and subtract the multiples of 3×5 (to avoid double-counting).

The sum of the sequence of the first n terms of an arithmetic series:
Sₙ = (n/2)(a₁+aₙ)

Where n is the biggest multiple, a₁ is the first element of the series, and aₙ the last (n times the number whose multiples we’re obtaining).

(// is euclidean division where we take just the quotient and throw away the remainder. i.e. division where we through away the fractional part.)

166833+99500-33165 = 233168.

Generalising the calculation of n and aₙ that we did above, we did in each case n=999//d and aₙ=n×d, where d is the difference between each element in the series. Since d in our case is the same as the first element, the arithmetic sum formula reduces to (n/2)(d+aₙ) ⇒ (n/2)(d+n×d), where n=999//d.

def multiplesOf3Or5ArithmeticSeries(upTo):
    def sumSeries(d, maximum):
        n = maximum // d
        return int((n / 2) * (d + n * d))

    max = upTo - 1
    return sumSeries(3, max) + sumSeries(5, max) - sumSeries(15, max)

I added the int() as otherwise the result is a float (233168.0).

The same thing derived algebraically from the formula for the kth element of an arithmetic series:
aₖ = a₁+(k-1)d

 aₖ = a₁+(k-1)d ⇒
 aₙ = a₁+(n-1)d

 Since we have a₁=d,
 aₙ = d+(n-1)d ⇔
 aₙ = d+d×n-d ⇔
 aₙ = d×n

 From the sum formula:
 Sₙ = (n/2)(a₁+aₙ) ⇒
 Sₙ = (n/2)(d+d×n)

cf on the connected discussion thread:

Euler rules on sharing solutions

Solving the problem rewards me with this piece of sad news:

Please do not deprive others of going through the same process by publishing your solution outside of Project Euler. Members found to be spoiling problems beyond the first one-hundred problems will have their accounts locked.

Further information on the about page.

Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.

…

the rule about sharing solutions outside of Project Euler does not apply to the first one-hundred problems, as long as any discussion clearly aims to instruct methods, not just provide answers, and does not directly threaten to undermine the enjoyment of solving later problems.

…

It’s very polite of you to ask. That is not a courtesy normally shown to us. Either that, or we get asked and then they do what they want anyway. As you said, the concern of the Project Euler team, who have invested so much of there time and energy in crafting beautiful problems, is having the problems ruined by allowing solutions to be publicly accessible. So as long as you understand our concerns and you are responsible about how your solutions are accessed then it’s up to you. Generally we accept that the first one hundred or so problems have for some time now openly discussed in blogs, videos, and so on. Closing the stable door on that long gone horse is a fools errand.
—euler, 2016

Not sure there was even a point to share what I did so far because it’s nothing new or interesting. Like I said at the start, there is not much point to this devlog, is there. It’s not really “dev”.

It’s not impossible to make it interesting: I found this cool project by Jared Krinke (HN, log) where he solves each one of the first 100 problems using a different programming language for each problem, and he mostly avoided common languages. Apparently setting up a toolchain to run each one was a problem in itself. These days some can be run in the browser, and I guess you could technically make a compiler/emulator for all of them that could run in the browser, hence his (possibly joke) followup project idea to “implement a compiler and/or interpreter for 100 different programming languages”.

Euler maths barrier

According to eru on HN (part of the same thread I linked above) (Jan 2025), this PDF, generatingfunctionology by Herbert S. Wilf (1990/1994), demonstrates techniques that allow you to solve Project Euler problems without a computer.

Eg where they ask you to add up the first few billion even terms of the Fibonacci numbers and similar; you can just derive a simple closed formula and evaluate that by hand.

xzyyyz, also on the same thread:

The coding and designs skills are completely secondary to the math. The algorithms (except for computational number theory, computation geometry) are completely secondary. So it is knowledge of math that is barrier.
I keep learning math (and, sometimes, relatively new development in math) by solving problems. To start, I would recommend reading G.H. Hardy & E.M. Wright “An Introduction to the Theory of Numbers”.

abecedarius:

Really it’s fine to just start. At some point you may get stuck and want to learn more math, but when I did the first ~45 I certainly had not read generatingfunctionology or Hardy and Wright.

LC2: Add Two Numbers

From now on, I am only going to look at SlicedPotatoes’ French translations of the problems instead of the original English on leetcode.com, because I prefer to read in French. I hope no misunderstandings will arise from this.

Two linked lists each representing a positive whole number, with each node representing a digit, stored in inverse order. Get the sum as a linked list.

Function taking 2 arguments: l1 and l2, each of type ListNode, which has properties val and next.

This is complicating our test mechanism (read: my stubbornness to not test directly on the site); we first need to write a way to initialise these linked lists, as well as a way to compare two linked lists to be able to check if we got the right linked list as output for our function.

class N:
    def __init__(self, *args):
        n = self
        for i in range(len(args)):
            n.val = args[i]
            n.next = N(args[i+1]) if i+1 < len(args) else None
            n = n.next

    def __repr__(self):
        values = []
        n = self
        while n:
            values.append(str(n.val))
            n = n.next
        return "N(" + ', '.join(values) + ")"

    def __eq__(self, other):
        if type(other) is not N:
            return False
        n1 = self
        n2 = other
        while n1 and n2:
            if n1.val != n2.val:
                return False
            n1 = n1.next
            n2 = n2.next
            if n1 and not n2 or n2 and not n1:
                return False
        return True

The repr is to get useful errors, like:

AssertionError: N(8, 9, 9, 9) != N(8, 9, 9, 9, 0, 0, 0, 1) (addTwoNumbers)

My first effort passes the first two examples, but fails the third one (see error above):

def addTwoNumbers(l1, l2):
    n1 = l1
    n2 = l2
    res = nres = N(0)  // res to keep track of the root
    carry = 0
    while n1 and n2:
        nres.val = (n1.val + n2.val + carry) % 10
        carry = (n1.val + n2.val + carry - nres.val) // 10
        n1 = n1.next
        n2 = n2.next
        nres.next = N(0) if n1 and n2 else None
        nres = nres.next
    return res


if __name__ == '__main__':
    def v(funcs, args, expected):
        for f in funcs:
            res = f(*args)
            assert res == expected, f'{res} != {expected} ({f.__name__})'

    funcs = [y for x, y in globals().items() if x.startswith('addTwoNumbers')]
    v(funcs, (N(2, 4, 3), N(5, 6, 4)), N(7, 0, 8))
    v(funcs, (N(0), N(0)), N(0))
    v(funcs, (N(*[9]*7), N(*[9]*4)), N(8, 9, 9, 9, 0, 0, 0, 1))
    print("Tests passed")

The problem is not taking into account the situation where the number of digits in each number differs. It’s also not taking into account the situation where we may need to open another digit.

I really should have thought it through before programming. For the next problems I will try to force myself to write through planning the algorithm before being allowed to write anything.

How to handle inputs with a different number of digits? We know that they are in inverse order, so it will be like this:

 l1 3 2 1
 l2 5 4

For adding 123+45. This is already aligned the way we need for the addition; the ones place with the ones place (the 3 with the 5) and the tens place with the tens place (the 2 with the 4). Once we’re past the tens place, what should be done? Add the 1 with just the carry (which will be 0 in this case).

Two problems:

And the number of digits could be even further off:

 l1 4 3 2 1
 l2 6 5

So the loop shouldn’t assume there is always a node to get the value of, or even the next of.

Next, we need to consider the problem of needing to open another digit. This will happen when we still have a carry left after the last addition.

 l1 9
 l2 9

After this addition, nres.val = 8 and carry = 1. We need to open a digit for the carry.

 res 8 1

def addTwoNumbers(l1, l2):
    n1 = l1
    n2 = l2
    res = nres = N(0)
    carry = 0
    while n1 or n2 or carry:
        val1 = n1.val if n1 else 0
        val2 = n2.val if n2 else 0
        nres.val = (val1 + val2 + carry) % 10
        carry = (val1 + val2 + carry - nres.val) // 10
        n1 = n1.next if n1 else None
        n2 = n2.next if n2 else None
        nres.next = N(0) if n1 or n2 or carry else None
        nres = nres.next
    return res

All the examples pass now.

In the real one, N has to be changed to ListNode.

Accepted
1569 / 1569 testcases passed
± submitted at May 10, 2026 04:10
Runtime
0ms
Beats 100.00%
Memory
19.32MB
Beats 41.73%

It’s a flat loop over the digits, so I guess runtime complexity is O(n). I’m not sure how to think about space complexity, we just store a new linked list, and surely that’s unavoidable. Unless we overwrite one of the existing linked lists?

[The editorial says it’s O(max(n,m)) time complexity where n and m are the lengths of l1 and l2, and O(1) space complexity because the answer doesn’t count for space complexity. Good to note for future.]

Interestingly, SlicedPotatoes says that he initially tried to extract the numbers from the linked lists and add them directly, which was not viable because they can contain up to 100 digits, resulting in a bigger number than can be stored in even an unsigned long long (which is only up to 18446744073709551615).

[In Python, that approach is possible. There are several solutions that use it in the comments by converting the digits to a string and concatenating them, then int(s[::-1]) to convert to a number (the [::-1] reverses s). This works for absurdly large numbers. It was previously only limited by hardware, but they introduced a limit of 4300 digits in 2022] [In this discussion about this change, Oscar Benjamin gives an algorithm parse_int that converts a string to a number an order of magnitude faster than Python, taken from the book Modern Computer Arithmetic p39]

Another interesting thing he did is create a “fake” node -1 at the head of res, create new nodes as needed while going through the loop, then at the end return res.next. That’s what the editorial does too. I thought it would save us 1 line but it doesn’t, because each iteration (1) you have to create the new node in a separate variable (if you create the node directly in nres, it’s not going to be connected), (2) set nres.next to it, (3) set nres to it. As opposed to our current algorithm which, each iteration, does (1) save the val in the node already created, (2) create a new node if needed, (3) set nres to it. So it’s the exact same number of lines (8 inside the loop).

def addTwoNumbersDummy(l1, l2):
    n1 = l1
    n2 = l2
    res = nres = N(0)  # "dummy head"
    carry = 0
    while n1 or n2 or carry:
        val1 = n1.val if n1 else 0
        val2 = n2.val if n2 else 0
        new = N((val1 + val2 + carry) % 10)
        carry = (val1 + val2 + carry - new.val) // 10
        n1 = n1.next if n1 else None
        n2 = n2.next if n2 else None
        nres.next = new
        nres = nres.next
    return res.next

There is a followup, which I am only now noticing in the editorial, as I only read SlicedPotatoes’ translation of the description which didn’t include it. It’s to do the same problem, but this time with the digits not being stored in inverse order.

How are you supposed to do the followup, are you supposed to submit it in the same place? As surely it would be different results for the same inputs. Maybe It’s just a question an interviewer might ask and expect us to explain what you would need to do differently in that case, without having to really implement it.

 l1 1 2
 l2 3

Would be 12+3. We need to add the 2 and 3, and 1 to the carry (0 in this case). When constructing the new number, we will have to start from the tens place somehow. We can’t set the 1 from the 5.

 res 1 -> 5

Since an addition of a lower digit can affect the higher ones (and this can cascade), maybe this means we necessarily need another data structure.

Plus, we have to align the places. So we probably first have to go all the way to the end of each linked list, storing the nodes in a data structure, and only then start the addition.

How to create the resulting linked list?

Maybe it’d be easier to just write an algorithm that reverses the order of a linked list, apply our previous algorithm to add the two numbers, then reverse the result.

How to reverse the order of a linked list?

Maybe there is a clever way that doesn’t necessitate storing all the elements in another data structure?

Note

After this point I make a tonne of mistakes. You might want to skip it, or else get some popcorn and watch how badly someone can confuse themselves with ASCII diagrams.

 n 1 -> 2 -> 3

I can imagine reversing the direction and storing the original in a variable:

This will have reversed the 1 and the 2, but also gotten rid of the link to 3, which is now inaccessible.

 n 1 <- 2   3

I can imagine storing temp.next in a variable too, but there will be the same problem for the next element if there was another element 4.

Let’s imagine the solution that involves another data structure, then.

def reverseLinkedList(n):
    nodes = []
    while n:
        nodes.append(n)
        n = n.next
    for i in reversed(range(len(nodes))):
        nodes[i].next = nodes[i-1] if i-1 >= 0 else None
    return nodes[-1]

def rAddTwoNumbers(l1, l2):
    """addTwoNumbers with opposite order of digits"""
    return reverseLinkedList(
        addTwoNumbers(reverseLinkedList(l1), reverseLinkedList(l2)))

What is the time complexity? I think still O(max(n,m)), because we don’t have nested loops, it’s still just looping over all the digits of l1 and all the digits of l2, even if we loop each thrice (O(3n) reduces to O(n)). We also loop another time for reversing the result, and the result might be more digits, but it’s not an order of magnitude difference.

Space now probably also becomes O(max(n,m)) because of having to store the nodes.

Which would mean it’s actually the same as the other order of digits in terms of time complexity, and only worse in space complexity.

The editorial doesn’t cover this, it just leaves the question open ended.

I looked up “reversing a linked list”, and saw in the description field of a result that it’s possible to reverse a linked list without adding all the nodes to another structure, using 3 pointers.

Let’s reconsider this.

 n 1 -> 2 -> 3

  prev  n   next
   1 <- 2    3

  prev  n   next
   1 <- 2 <- 3

How to make this work for 4 elements, with still only 3 variables? If we followed the same steps, we would lose the reference to the 4th one. I guess before next.next = n, something has to store next.next.

 n 1 -> 2 -> 3 -> 4

  prev  n   next
   1 <- 2    3 -> 4

What if we repeat the same steps?

             n
       prev next
   1 <- 2 <- 3    4

No, it’s not good. next didn’t move. We lost 4.

Let’s go back to the previous state.

  prev  n   next
   1 <- 2    3 -> 4

We can advance prev, because 1 is already connected.

       prev
        n   next
   1 <- 2    3 -> 4

If we connect next, we would lose 4. So advance n and next first.

       prev  n   next
   1 <- 2    3 -> 4

Now we can connect n to prev.

       prev  n   next
   1 <- 2 <- 3    4

If we had another element after the 4, we would lose it if we were to simply connect next to n first. So before doing any such connection, we need to advance prev, n, and next, then connect n to prev. Stop when next is None.

At the beginning, when we receive a list like this:

 n 1 -> 2 -> 3 -> 4

We need to set up our pointers first:

Then, repeatedly:

  prev  n   next
   1 -> 2 -> 3 -> 4   set up

       prev  n   next
   1 <- 2    3 -> 4   1st iteration

            prev  n  (next = None)
   1 <- 2 <- 3    4   2nd iteration

No, this is broken, we can’t go into another iteration after this, as next = n.next will fail. We need to rather do the n.next = prev at the end of each loop rather than at the beginning. Which means that the first one needs to happen outside the loop, unfortunately. (Alternatively, do the last n.next = prev outside of the loop, at the end)

So a set up like this:

Then, repeatedly (while next):

  prev  n   next
   1 <- 2    3 -> 4   set up

       prev  n   next
   1 <- 2 <- 3    4   1st iteration

            prev  n  (next = None)
   1 <- 2 <- 3 <- 4   2nd iteration

I forgot to consider the situation where we have less than 3 items on the list. In the set up, we can’t assume that .next of anything is non-None.

What do we return? If the loop was entered, n should be the new head, but if it was not, it would be prev. I guess we could do:

I wrote this (potentially wrong):

def reverseLinkedListThreePointers(n):
    """bad and broken"""
    prev = n
    n = n.next
    next = n.next if n else None
    if n is not None:
        n.next = prev
    while next:
        prev = prev.next
        n = n.next
        next = next.next
        n.next = prev
    return n if n is not None else prev

but I can’t get it working properly. It could be something wrong with my N implementation or test mechanism. When I call it with the usual:

    funcs = [y for x, y in globals().items()
             if x.startswith('reverseLinkedList')]
    v(funcs, (N(2, 4, 3),), N(3, 4, 2))

it gets just N(2) as its input. My previous function, reverseLinkedList, gets N(2, 4, 3) just fine. When I call it myself with reverseLinkedListThreePointers(N(2, 4, 3)) it gets N(2, 4, 3) as it should, but if I try to print the result, my program gets stuck in an infinite loop. It could be a problem with my N.__repr__ implementation, which indeed could get stuck in a loop because it doesn’t account for cycles. If there are cycles, it means our algorithm is broken. This also doesn’t explain why when it’s called with v it only gets N(2) instead of the full N(2, 4, 3). We’re relying on N.__repr__ to tell us what it is, but still, I don’t see why it would be different. Is it because it’s passed by reference? It gets called after reverseLinkedList with a reference to the same node, after the list has already been reversed?

Let’s first modify repr to be able to detect cycles. This is the method currently:

    def __repr__(self):
        values = []
        n = self
        while n:
            values.append(str(n.val))
            n = n.next
        return "N(" + ', '.join(values) + ")"

Instead of storing the values we can store the nodes, then if a node was seen before, we know we have a cycle. Then at the end instead of ', '.join(values) we could do ', '.join(str(n.val) for n in nodes). And indicate in the return string when there is a cycle.

    def __repr__(self):
        nodes = []
        n = self
        cycle = None
        while n:
            if n in nodes:
                cycle = n
                break
            nodes.append(n)
            n = n.next
        vals = ', '.join(str(n.val) for n in nodes)
        vals += f", cycles to {cycle.val}" if cycle is not None else ""
        return f"N({vals})"

print(reverseLinkedListThreePointers(N(2, 4, 3))) results in:

N(2, 4, cycles to 2)

The input is 2,4,3 and it’s supposed to return 3,4,2.

Just before the if, n is 4,3, pre is 2,4,3, and next is 3. Up to here, it’s as expected. After the if n is not None: n.next = prev though (and still before the loop), n and pre get cycles:

n N(4, 2, cycles to 4)
prev N(2, 4, cycles to 2)
next N(3)

  prev  n   next
   2 ?? 4    3

I am very confused. Are they pointing to each other?

I think that the ASCII representation of the nodes led us astray. It visualises connections as just one connection, but each node has its own next. So yes, they can point to each other. To change from this:

  prev  n   next
   2 -> 4 -> 3

to this:

  prev  n   next
   2 <- 4    3

it is not sufficient to do n.next = prev, we also have to change prev.next to None. Otherwise, we get this:

  prev  n   next
   2 -> 4    3
     <-

Does the entire algorithm has to be considered with this in mind? I think it may only be a problem for the first one, because the first node’s next doesn’t get set, since in the reversed version it doesn’t have a node after it.

Or maybe not, because I end up with n being just 2 without a next, and prev and next somehow both None.

preif n N(4, 3) prev N(2, 4, 3) next N(3)
preloop n N(4, 2) prev N(2) next N(3)
iteration n N(4, 2) prev N(2) next N(3)
end iteration n N(2) prev None next None
postloop n N(2) prev None next None

The 2 not having a next is normal. The prev being None should not happen. And 3 should have a next.

To make this less confusing I’m going to use the input 1,2,3.

preif n N(2, 3) prev N(1, 2, 3) next N(3)
preloop n N(2, 1) prev N(1) next N(3)
iteration n N(2, 1) prev N(1) next N(3)
end iteration n N(1) prev None next None
postloop n N(1) prev None next None

  prev  n   next
   1 <- 2    3    preloop

   n              (pre = None, next = None)
   1 <- 2    3    end iteration

Where did pre and next disappear to, and why did n go backwards?

Oh… I think I was looking at the diagrams linearly and always assumed next is going to make it go to the left → and obviously it’s not the case, it goes to the thing it is connected to. That is, the thing next was set to.

I think the algorithm would still work, just instead of advancing the pointers with prev = prev.next, n = n.next, next = next.next, I need to be doing prev = n, n = next, next = next.next (that one stays the same). Apart from the start, where we do need to do n = n.next. That’s when we first set the pointers.

def reverseLinkedListThreePointers(n):
    prev = n
    n = n.next
    next = n.next if n else None
    if n is not None:
        n.next = prev
        prev.next = None
    while next:
        prev = n
        n = next
        next = next.next
        n.next = prev
    return n if n is not None else prev

Only two lines changed, the first two lines inside the loop.

Summary of the bugs:

  1. At the beginning to change the direction of the connection between the first two nodes, other than n.next = prev we have to do prev.next = None, otherwise nothing changes the next of the first node (which becomes the last) and we get a cycle.
  2. To advance prev and n inside the loop, instead of prev = prev.next and n = n.next we must do prev = n et n = next. Otherwise we end up changing directions, because we changed their nexts.

There is another issue, though not inside the algorithm itself, and it’s with my test mechanism. The nodes are passed by reference. I have two different linked list reversal functions called with the same inputs, and by the time this one gets called the former head of the list has no next.

    def v(funcs, args, expected):
        for f in funcs:
            res = f(*args)
            assert res == expected, f'{res} != {expected} ({f.__name__})'

Changing f(*args) to f(*copy(args)) does not resolve it. f(*deepcopy(args)) does.

It finally works now.

This reversing algorithm is still the same time complexity as the previous one, because it has to go through all the elements. The space complexity has reduced to O(1), because it’s just 3, regardless of the number of elements.

Eu2:

TODO

!! remember to write through planning the alg before being allowed to program

—— In other news ——

emacs-doentry: delete-selection-mode yank

Bug (sort of) in doentry-mode where if you have delete-selection-mode on and a selection and yank, it doesn’t replace the selection. In other modes it works. First suspect was of course that I need to do something in doentry-mode-yank given that we have that function instead of yank, but I got derailed because testing with M-x yank and M-: yank didn’t work either, which I reasoned means something more fundamental is broken. I even tested in other modes and thought that in other modes it does work when invoked with M-x and M-:, but I can’t reproduce this now, it seems like yank only replaces when invoked with the hotkey. I’m not really sure why that would be, to be honest, but it seems to be the case across all modes.

The most useful resource I found is this SE question from 2016. Which also links to bug#21275 in cc-mode which is excellent and a wholesome exchange.

Thanks for taking the trouble to report this bug, and thanks even more for making your report so clear and well structured.
—Alan Mackenzie

It was just a matter of adding the following in the define-derived-mode:

(put 'doentry-mode-yank 'delete-selection t)

Commit beed10f

Improve this page / Leave a message.
■
←⌂ / ←15 — Encryption and JavaScript /

Linked discussion