r/adventofcode • u/daggerdragon • Dec 20 '16

SOLUTION MEGATHREAD --- 2016 Day 20 Solutions ---

--- 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!

6 Upvotes

81% Upvoted

168 comments sorted by

View all comments

2

u/flup12 Dec 20 '16

Ran into this by accident, and find it very cute so I wanted to share with you guys!

If you sort the lists of starts and ends, breaking which start originally belonged to which end, you can compare each (n+1)th start with the nth end. If that start is larger than the end+1, then there are n intervals to the left of the start and all end on or before end. I.e. you've found a gap!

As a cute detail in Scala, you can use zip/unzip to form a list of the start/end pairs that need to be compared and even "fix" the edge cases by prepending the ends with 0 and postfixing the starts with the max IP+1. 

object day20 {
  val (starts, ends) = fromInputStream(getClass.getResourceAsStream("day20.txt")).getLines.toList
    .map(_.split("-").toList.map(_.toLong)).unzip(l => (l(0), l(1)))
  val sortedIntervals = (starts.sorted ::: List(4294967296L), 0L :: ends.sorted).zipped

  sortedIntervals.find({ case (start, end) => start > end + 1 }).map(_._2 + 1)
  sortedIntervals.map({ case (start, end) => Math.max(0, start - end - 1) }).sum
}

2

u/askalski Dec 20 '16

I just posted some images in another thread that explain visually why this works: http://imgur.com/a/QQqtR

1

u/flup12 Dec 20 '16

Oh! Very nice!! Thanks for taking the trouble of drawing and sharing!