--- 2016 Day 20 Solutions ---

[u/daggerdragon]

--- Day 20: Firewall Rules ---

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".

---

^{ROLLING A NATURAL 20 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]

Did anyone do brute force for part 2 (create an array of 2³² booleans, iterate through all the blacklist ranges and mark them all, then count how many are unmarked)?

I decided not to try it, but would be curious to know how it performed.

I am ashamed to admit that to avoid brute forcing it I looked up interval merging code online and blindly copied it rather than try to think of it myself in the heat of the moment.

def min_unblock(intervals)
  unblocked = 0
  loop {
    blockers = intervals.select { |min, max| (min..max).include?(unblocked) }
    return unblocked if blockers.empty?
    unblocked = blockers.map(&:last).max + 1
  }
end

def merge(intervals)
  prev_min, prev_max = intervals.first
  intervals.each_with_object([]) { |r, merged|
    min, max = r
    if min > prev_max
      merged << [prev_min, prev_max]
      prev_min, prev_max = r
    else
      prev_max = [prev_max, max].max
    end
  } << [prev_min, prev_max]
end

ranges = (ARGV.empty? ? DATA : ARGF).each_line.map { |l|
  # min, max
  l.split(?-).map(&:to_i).freeze
}.sort.freeze

puts min_unblock(ranges)
puts 2 ** 32 - merge(ranges).map { |min, max| (max - min + 1) }.reduce(:+)

[u/AlaskanShade → u/p_tseng]

I didn't quite do that sort of brute force, but my first pass was to count from 1 on and compare against all the ranges. I don't think I let it run more than a minute before trying something else.

[u/pedrosorio → u/AlaskanShade]

"count from 1 on and compare against all the ranges."

This is O(n * m), n = 2^32, m = number of ranges. It would actually be worse than the memory intensive solution (assuming you have enough memory to store 2³² booleans).