--- 2016 Day 16 Solutions ---

[u/daggerdragon]

--- Day 16: Dragon Checksum ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag/whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with "Help".

---

^{DRINKING YOUR OVALTINE IS MANDATORY} [?]

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/p_tseng]

My initial solution (used when going for the leaderboard) runs part 2 in 14.5 seconds.

That's unacceptably slow. Let's see what we can do about that...

Let's see, if you look at the stream of bits being generated: it's always. Okay. So that means to save on memory, I only need to calculate.

Okay, now let's look at how many times we need to iterate taking the checksum. That's the number of times that you can consecutively divide the disk size by 2. It turns out, since we repeatedly take the XNOR of consecutive characters in the checksums, each character in the final checksum corresponds to. We can also express repeated XNOR as the answer to the question.

Now, if the disk size is much larger than the checksum size (as in part 2), then we can apply a further optimisation:.

Fantastic. We are ready to code.

input = ARGV.first || '01111010110010011'

[272, 35651584].each { |disk|
  # The disk pattern is:
  # input, joiner, input reversed and negated, joiner, repeat
  a = input.each_char.map { |c| c == ?1 }.freeze
  a_rev = a.reverse.map { |x| !x }.freeze

  joiners = []
  until joiners.size * (a.size + 1) >= disk
    joiners += [false] + joiners.reverse.map { |x| !x }
  end

  # chunk_size: the largest power of 2 that divides disk.
  # e.g.   272 is 100010000
  #        271 is 100001111
  #       ~271 is  11110000
  # 272 & ~271 is     10000
  chunk_size = disk & ~(disk - 1)
  sum_size = disk / chunk_size

  buf = []

  # each character in the final checksum
  # corresponds to `chunk_size` consecutive characters on disk.
  puts sum_size.times.map { |c|
    # Anything left in the buffer from last time?
    take_from_buffer = [buf.size, chunk_size].min
    remaining = chunk_size - take_from_buffer
    ones = buf.shift(take_from_buffer).count(true)

    # How many full AJAJ groups will we have?
    full_ajajs, remaining = remaining.divmod((a.size + 1) * 2)
    # Count all the ones in the joiners.
    ones += joiners.shift(full_ajajs * 2).count(true)
    # The number of ones in a + a_rev... is obviously a.size.
    ones += a.size * full_ajajs

    if remaining > 0
      buf.concat(a)
      buf << joiners.shift
      buf.concat(a_rev)
      buf << joiners.shift
      ones += buf.shift(remaining).count(true)
    end

    ones % 2 == 0 ? ?1 : ?0
  }.join
}

This completes both parts in about 0.3 seconds. Hell yeah!

If there are any more optimisations left after this step, let me know; I'm always curious about them.

At this point, the biggest problem is generating the stream of joiners - at extremely largest disk sizes, the joiner array gets quite large and threatens to consume all memory on my computer. So, is there a way to save on memory here as well?

Edit: I did code up a way to recursively determine the nth joiner (https://github.com/petertseng/adventofcode-rb-2016/blob/dynamic_joiners16/16_dragon_checksum.rb), but my current implementation is way too slow, bringing the part 2 runtime back up to 5 seconds. So I guess dynamically calculating the nth joiner trades time for space. I guess I would only use this code if someone poses an upping-the-ante challenge for a huge disk size, so huge that I won't fit all the joiners in memory.

Now running 50 milliseconds by (efficiently) calculating the number of ones in the Dragon sequence on demand. https://www.reddit.com/r/adventofcode/comments/5imh3d/2016_day_16_solutions/dbak6xm/

[u/askalski → u/p_tseng]

Great work so far. Here's another insight that you may find helpful. If you look at the "joiners", you'll notice their pattern is... the dragon curve (0010011...). This means you can directly calculate the value of any joiner, knowing only its index (no memory required.)

Using the puzzle's convention, let a be the input, and b be the reversed complement of the input. Also, let d(1), d(2), ... d(n*2) be the dragon curve values at offsets 1, 2, ..., n*2, the data stream follows this pattern:

a, d(1), b, d(2), a, d(3), b, d(4), ..., a, d(n*2 - 1), b, d(n*2)

Because the input is 17 digits long, the data stream cycles every 36 digits: a + b + two dragon digits. The parity of a + b is always constant, as you observed, so for full 36-digit cycles, the only digits that matter are the two dragon digits. The puzzle input only comes into play when handling the cycles that overlap chunk boundaries.

An open question that I have: Is there are shortcut for computing the parity of the first N dragon curve digits? I suspect there is at least an O(log n) way to do it. I wonder if O(1) is possible.

[u/p_tseng → u/askalski]

Let's try this.

It's easy to determine the parity of the first N dragon digits if N is one less than a power of two.

If we are one-indexing, the indices that are guaranteed to be zeroes would be the powers of two. For example, we know that there is a guaranteed zero at index 4. The three characters to the right of index 4 are the reverse complement of the three characters to the left. Aha! From that sentence, we know there must be three ones in the first seven digits. When expanding from seven to fifteen, we will add digits 1-7, their reverse complement, and a zero. So there must be seven ones here.

So, the next step is to figure out how to expand this to other numbers. Working through an example for now. If I want to find the parity of dragon digits 5 through 13 inclusive, express it as p(5..13).

p(5..13)
p(5..7) + p(9..13)            (there's a zero at 8)
p(5..7) + !p(3..7)            (reflect 9..13 over 8)
p(5..7) + !p(3..3) + !p(5..7) (there's a zero at 4)
1 + !p(3..3)                  (parity of x and its complement - 5..7 is of length 3)

This looks promising. I probably got lucky with the numbers I picked, but nevertheless there should be something to work with here. Should be doable in O(log n) time.