Dragon iterators

Saturday 17 December 2016

Advent of Code is running again this year, and I love it. It reveals a new two-part Santa-themed puzzle each day for the first 25 days in December. The puzzles are algorithmically slanted, and the second part is only revealed after you’ve solved the first part. The second part often requires you to refactor your code, or deal with growing computational costs.

I’ve long been fascinated with Python’s iteration tools, so Day 16: Dragon Checksum was especially fun.

Here’s an adapted version of the first part of the directions:

You’ll need to use a modified dragon curve. Start with an appropriate initial string of 0’s and 1’s. Then, for as long as you need, repeat the following steps:

  • Call the data you have at this point, A.
  • Make a copy of A; call this copy B.
  • Reverse the order of the characters in B.
  • In B, replace all instances of 0 with 1 and all 1’s with 0.
  • The resulting data is A, then a single 0, then B.

For example, after a single step of this process,

  • 1 becomes 100.
  • 0 becomes 001.
  • 11111 becomes 11111000000.
  • 111100001010 becomes 1111000010100101011110000.

We have a few options for how to produce these strings. My first version took an initial seed, and a number of steps to iterate:

ZERO_ONE = str.maketrans("01", "10")

def reverse01(s):
    """Reverse a string, and swap 0 and 1."""
    return s.translate(ZERO_ONE)[::-1]

def dragon_iterative(seed, steps):
    d = seed
    for _ in range(steps):
        d = d + "0" + reverse01(d)
    return d

(BTW, I also wrote tests as I went, but I’ll omit those for brevity. The truly curious I’m sure can find the full code on GitHub.) This is a simple iterative function.

The problem statement sounds like it would lend itself well to recursion, so let’s try that too:

def dragon_recursive(seed, steps):
    if steps == 0:
        return seed
        d = dragon_recursive(seed, steps-1)
        return d + "0" + reverse01(d)

Both of these functions have the same downside: they produce complete strings. One thing I know about Advent of Code is that they love to give you problems that can be brute-forced, but then turn up the dials high enough that you need a cleverer algorithm.

I don’t know if this will be needed, but let’s try writing a recursive generator that doesn’t create the entire string before returning. This was tricky to write. In addition to the seed and the steps, we’ll track whether we are going forward (for the first half of a step), or backward for the second half:

def dragon_gen(seed, steps, reverse=False):
    if reverse:
        if steps == 0:
            yield from reverse01(seed)
            yield from dragon_gen(seed, steps-1, reverse=not reverse)
            yield "1"
            yield from dragon_gen(seed, steps-1, reverse=reverse)
        if steps == 0:
            yield from seed
            yield from dragon_gen(seed, steps-1, reverse=reverse)
            yield "0"
            yield from dragon_gen(seed, steps-1, reverse=not reverse)

If you are still using Python 2, the “yield from” may be new to you: it yields all the values from an iterable. This function works, but feels unwieldy. There may be a way to fold the similar lines together more nicely, but maybe not.

In any case, all of these function still have a common problem: they require the caller to specify the number of steps to execute. The actual Advent of Code problem instead tells us how many characters of result we need. There’s a simple way to calculate how many steps to run based on the length of the seed and the desired length of the result. But more interesting is an infinite dragon generator:

def dragon_infinite(seed):
    """Generate characters of dragon forever."""
    yield from seed
    for steps in itertools.count():
        yield "0"
        yield from dragon_gen(seed, steps, reverse=True)

This relies on the fact that the first part of an N-step dragon string is the N-1-step dragon string. Each time around the for-loop, we’ve produced a dragon string for a particular number of steps. To extend it, we just have to output the “0”, and then a reverse version of the string we’ve already produced. It’s a little surprising that this only calls dragon_gen with reverse=True, but discovering that is part of the fun of these sorts of exercises.

Now we can write dragon_finite, to give us a result string of a desired length:

def dragon_finite(seed, length):
    return "".join(itertools.islice(dragon_infinite(seed), length))

The second part of the puzzle involved a checksum over the result, which I wrote in a simple way. It meant that although I had written generators which could produce the dragon string a character at a time, I was using them to create a complete string before computing the checksum. I could have continued down this path and written a checksum function that didn’t need a complete string, but this is as far as I got.

One other implementation I didn’t tackle: a function that could produce the Nth character in the dragon string, given the seed and N, but without generating the entire sequence.


A very naïve implementation (close to your first idea) takes ~14 seconds on my machine to solve part 2.
Yes, unfortunately the target length in second part was too low. :-\
Quoting the creator of AoC:

For each star, I have some pretty naive Perl code on a 2.5ghz that can complete in under 30sec.
It may well be that the creator of AoC has a different idea of "naive". I know I have written solutions to the puzzles that have taken too long. And one of the puzzles this year specifically is designed to need strings larger than memory.
I took a lil time to poke around an Nth character generator, mostly scribbling on paper to get a feel for how it behaves and I found some interesting stuff.

If you ignore the inserting a 0 step, start with a seed of just 0 and run it by hand you end up with 01010101010101...

If we then say that "a" is the negation of "A" and start with a seed of "abc" this extends the pattern to abcCBAabcCBAabcCBA...

As for the inserted 0's, they fall between each seed sized block and it turns out their values just follow the dragon curve turns and there's a simple direct calculation for the Nth element of that.

Combined that makes figuring the the Nth element of this is relatively easy.

Why this happens involves various things about dragon curves and gray code that I'm going to leave as an exercise for the reader, however this might be helpful http://oeis.org/A005811

Add a comment:

Ignore this:
Leave this empty:
Name is required. Either email or web are required. Email won't be displayed and I won't spam you. Your web site won't be indexed by search engines.
Don't put anything here:
Leave this empty:
Comment text is Markdown.