Advent of Code 2019 Solution Megathread - Day 4: Secure Container

Oh hey! It's a problem related to my current job! Let's try to brute force some passwords like real l337 h4xx0rz.

Day 4 - The Problem

Man, the forces of the Holidays have a consistent problem with security. Every year we have to do some basic offensive security work... Santa's forgotten password, most of the obstacles in our assault on Easter Bunny Corp., cracking High Entropy Passwords, sneaking past lazy guards, or some other bad practice.

Part 1 seems complicated at first, but looking at the whole possibility set might shake some things loose.

Part 2 was mainly difficult for me due to the wording. However, once I figured out that there needs to be at least one number that appears exactly twice, then it was all downhill pedaling.

I was beginning to worry that this was going to be a tougher year with a steep ramp-up!

Ongoing Meta

Dev.to List of Leaderboards

• 120635-5c140b9a - provided by Linda Thompson

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Neat Statistics

I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?

Languages Seen On Day 03

• Python x 3
• Clojure x 2
• C++
• Haskell
• Javascript
• Kotlin
• PHP
• Scala
• Swift

Comments

[Jon Bristow]

Kotlin Solution

object Day04 {

    private fun has5DistinctNumbers(it: Int) = it.toString().toSet().size < 6

    private fun hasAllIncreasingDigits(it: Int) =
        it.toString()
            .map { it.toInt() }
            .windowed(2, 1)
            .all { (a, b) -> b >= a }

    private fun hasAtLeastOneDigitAppearingExactlyTwice(it: Int) =
        it.toString()
            .groupBy { it }
            .mapValues { (k, v) -> v.size }
            .any { (k, v) -> v == 2 }

    fun part1() =
        passwordRange.asSequence()
            .filter { hasAllIncreasingDigits(it) && has5DistinctNumbers(it) }
            .count()

    fun part2() =
        passwordRange.asSequence()
            .filter { hasAllIncreasingDigits(it) && hasAtLeastOneDigitAppearingExactlyTwice(it) }
            .count()

}

fun main() {
    println(Day04.part1())
    println(Day04.part2())
}

It's important to use Sequence here so that the map/filter/count function can happen per item instead of applying to the whole list for each operation.

[Farah Anjum]

Something about seeing so many greens <3
Waiting for someone to post a functional/not-very-imperative JS solution!

[Farah Anjum]

Where in part1() are you checking that 2 adjacent digits are the same?

[Jon Bristow]

Here’s my math/logic for n=3 that expands to a general case simply in my mind (if it doesn’t I can work on a more formal proof)

Given:

• a<=b<=c
• a==b OR b==c

Therefore:

• distinct(a,b,c) must be equal to (a,c) OR (a)
• aba is never a legal pattern

Explanation of the second therefore: By looking at a 4 digit number that is abca we see that since this implies c<=a<=b that this isn’t a legal string. We can also insert any number of digits (that follow the rules) between b and c and the contradiction with given #1 still occurs.

[Christopher Kruse]

Back again with more Clojure. Cool thing to point out on this one: the frequencies function. It takes as input a collection, and then returns a map of the values present in that collection, and the count of the times they appear. Made part two real easy.

repl.it: repl.it/@ballpointcarrot/AoC-Clojure
github: github.com/ballpointcarrot/AoC/blo...

(ns aoc2019.day4
  (:require [clojure.string :as st]))

(defn satisfies-criteria?
  "checks for increasing values, with a flag for
  at least one double."
  [num]
  (let [digits (st/split (str num) #"")
        pairs (->> digits
                   (map #(Integer/parseInt %))
                   (partition 2 1))]
    (and (some (fn [[a b]] (= a b)) pairs)
         (every? (fn [[a b]] (>= b a)) pairs))))


(defn p2019-04-part1
  [input]
  (let [[low-bound high-bound] (map #(Integer/parseInt %) (st/split input #"-"))
        all-values (range low-bound high-bound)]
    (->> all-values
         (filter satisfies-criteria?)
         (count))))

(defn explicit-double?
  [num]
  (let [digits (map #(Integer/parseInt %) (st/split (str num) #""))]
    (some (fn [[k v]] (= v 2)) (frequencies digits))))

(defn p2019-04-part2
  [input]
  (let [[low-bound high-bound] (map #(Integer/parseInt %) (st/split input #"-"))
        all-values (range low-bound high-bound)]
    (->> all-values
         (filter satisfies-criteria?)
         (filter explicit-double?)
         (count))))

(defn run
  "Runs the Day 4 solutions."
  []
  (let [input "108457-562041"]
    (println (str "Part 1: " (p2019-04-part1 input)))
    (println (str "Part 2: " (p2019-04-part2 input)))))

[Jon Bristow]

I had to write my own in kotlin! Their design philosophy states that GroupBy->MapValues(Count) is good enough, and I... kind of agree?

Still handy to do it in one step though.

[Christopher Kruse]

I'd agree that it's not strictly necessary, as (group-by identity "112233") would solve the same problem; however, if you give me a convenience function, I'll take it. :D

[Christopher Kruse]

Threw a Ruby solution together, just because it feels under-represented here. Ended up faster than the Clojure solution, probably because I'm doing the processing for the values as they're generated:

def valid_numbers(input, &block)
  num_start, num_end = input.split('-').map(&:to_i)
  valid = []
  num_start.upto(num_end) do |num|
    increasing = true
    num.digits.each_cons(2) { |a, b| increasing &&= (b <= a) }
    if increasing
      frequencies = num.digits.inject(Hash.new(0)) { |hash, val| hash[val] += 1; hash }
      valid << num if frequencies.values.any? block
    end
  end
  valid
end

def p2019_04_part1(input)
  nums = valid_numbers(input) { |v| v > 1 }
  nums.count
end

def p2019_04_part2(input)
  nums = valid_numbers(input) { |v| v == 2 }
  nums.count
end

[Linda Thompson]

JavaScript...thank goodness I got this one! Still struggling to work out day 3, the mapping ones always get me stuck...I'll get it soon, though!

Basically, I filled out all the digits in my input range, then checked through each number to see if it was in order & had at least one double. Tried to break the second I saw an out of order number, so it would be a bit faster. Thankfully each input number is small, so it ran pretty quickly!

const input = [165432, 707912];
const range = [];
const diff = input[1] - input[0];
const hopefuls = [];

for (let i = 0; i <= diff; i++) {
  range.push(input[0] + i);
}

range.forEach(val => {
  let possible = checkValidity(val);
  if (possible) {
    hopefuls.push(val);
  }
})

function checkValidity(num) {
  let div = num.toString().split('').map(el => {
    return parseInt(el, 10)
  });
  let double = false;
  let doubleCount = 0;
  let order = true;
  for (let j = 0; j < div.length - 1; j++) {
    if (div[j] > div[j+1]) {
      order = false;
      break;
    } else if (div[j] === div[j+1]) {
      if (div[j+2] === div[j] || div[j-1] === div[j]) {
        double = false;
      } else {
        double = true;
        doubleCount++;
      }
    }
  }
  if (doubleCount > 0 && order) {
    return true;
  } else {
    return false;
  }
}

let qtyOfHope = hopefuls.length;
console.log(qtyOfHope);

[Farah Anjum]

Here's mine. Lot of room for DRY-ing it and making it declarative:

const isNotDecreasing = (num) => {
    return JSON.stringify((num).toString().split('').sort()) == JSON.stringify((num).toString().split(''))
}
const hasAdjDuplicates = (num) => {
    let hasDup = false;
    const str = num.toString();
    for(var i = 1; i< str.length; i++){
        if(str[i] == str[i-1]) {
            hasDup = true;
            break;
        }
    }
    return hasDup;
} 


const hasAdjDuplicatesPart2 = (num) => {
    let hasDup = false;
    const str = num.toString();
    for (var i = 1; i < str.length; i++) {
        if (str[i] == str[i - 1] 
            && ((i -2 >= 0) ? str[i - 1] != str[i - 2] : true)
            && ((i + 1 < str.length ? str[i] != str[i + 1] : true ))
        ) {
            hasDup = true;
            break;
        }
    }
    return hasDup;
} 

const solve = (range) => {
    const l = range.split('-')[0], r = range.split('-')[1];
    let part1 = 0, part2 = 0;
    for(var i = l; i<= r; i++){
        if (isNotDecreasing(i) && hasAdjDuplicates(i)) part1+=1;
        if (isNotDecreasing(i) && hasAdjDuplicatesPart2(i)) part2+=1;
    }
    console.log(part1, part2);
    return;
}

solve('171309-643603');

[Neil Gall]

Back in the early 1990s in my CS degree we did a genetic algorithm polynomial solver in Prolog. My Prolog has become a bit rusty through disuse since then but I was hoping for a constraint solving problem to dust it off.

Later I might try again using one of my MiniKanren implementations (e.g. github.com/neilgall/KotlinKanren)

digit(0).
digit(1).
digit(2).
digit(3).
digit(4).
digit(5).
digit(6).
digit(7).
digit(8).
digit(9).

in_range(Min, Max, A, B, C, D, E, F) :-
     X = (((((A * 10 + B) * 10 + C) * 10) + D) * 10 + E) * 10 + F
   , Min =< X
   , X =< Max.

has_adjacent_digits_the_same(A, B, C, D, E, F) :-
      A == B
    ; B == C
    ; C == D
    ; D == E
    ; E == F.

adjacent_digits_not_in_larger_group(A, B, C, D, E, F) :-
              A == B, B \= C
    ; A \= B, B == C, C \= D
    ; B \= D, C == D, D \= E
    ; C \= E, D == E, E \= F
    ; D \= E, E == F.

has_no_decreasing_digits(A, B, C, D, E, F) :-
      A =< B
    , B =< C
    , C =< D
    , D =< E
    , E =< F.

solve_part1(Min, Max, A, B, C, D, E, F) :-
      digit(A)
    , digit(B)
    , digit(C)
    , digit(D)
    , digit(E)
    , digit(F)
    , has_adjacent_digits_the_same(A, B, C, D, E, F)
    , has_no_decreasing_digits(A, B, C, D, E, F)
    , in_range(Min, Max, A, B, C, D, E, F).

solve_part2(Min, Max, A, B, C, D, E, F) :-
      solve_part1(Min, Max, A, B, C, D, E, F)
    , adjacent_digits_not_in_larger_group(A, B, C, D, E, F).

part1(Min, Max, Count) :-
      setof([A, B, C, D, E, F], solve_part1(Min, Max, A, B, C, D, E, F), Set)
    , length(Set, Count).

part2(Min, Max, Count) :-
      setof([A, B, C, D, E, F], solve_part2(Min, Max, A, B, C, D, E, F), Set)
    , length(Set, Count).

[Stephanie Hope]

PHP again! I solved it within the first half hour but was too embarrassed by my code to post it here, so spent most of my evening figuring out how to make it look less bad, oops. And I overwrote my Part 1 code, so this is just Part 2:

$lower = 359282;
$upper = 820401;
$count = 0;

for ($i = $lower; $i <= $upper; $i++) {
    if (test_ascending(strval($i))) {
        if (test_exact_dup(strval($i))) {
            $count++;
        }
    }

}
echo $count;

function test_exact_dup($password)
{
    for ($i = 0; $i < 5; $i++) {
        $num = $password[$i];
        $count = substr_count($password, $num);
        if ($count == 2){
            return true;
        }
    }
    return false;
}

function test_ascending($password)
{
    for ($i = 0; $i < 5; $i++) {
        if ($password[$i] > $password[$i + 1]) {
            return false;
        }

    }
    return true;
}

I did take some inspiration from other solutions to make this improved version :)

[Jon Bristow]

These are fine instincts that will serve you well in future pull requests.

No shame in making sure all the corners are sharp and you replaced all the variables named x, fart, someKindaFunc, etc. (I must admit to editing my posted code after an elegant refactor reveals itself to me)

[Supriya Srivatsa]

Kotlin code, used groupBy for the double digit condition checks - github.com/sup95/AdventOfCode-19/b... :)

fun main() {
    var part1Result = 0
    var part2Result = 0

    for(i in 357253..892942) {
        val numAsCharArray = i.toString().map { it }
        if (isDigitsNonDecreasing(numAsCharArray)) {
            if(hasAtleastDouble(numAsCharArray)) part1Result++
            if(hasExactlyDouble(numAsCharArray)) part2Result++
        }
    }

    println(part1Result)    //530
    println(part2Result)    //324
}

fun hasAtleastDouble(numAsChar: List<Char>) : Boolean {
    return numAsChar.groupBy { it }.filter { it.value.size >= 2 }.isNotEmpty()
}

fun hasExactlyDouble(numAsChar: List<Char>) : Boolean {
    return numAsChar.groupBy { it }.filter { it.value.size == 2 }.isNotEmpty()
}

fun isDigitsNonDecreasing(numAsChar: List<Char>) : Boolean {
    return numAsChar == numAsChar.sorted()
}

[Jon Bristow]

Unsolicited code review:

filter(x).isEmpty() is equivalent to none(x)

filter(x).isNotEmpty() is equivalent to any(x)

filterNot(x).isEmpty() is equivalent to all(x)

filterNot(x).isNotEmpty() is equivalent to any(!x)

c.any{it == x} is equivalent to x in c

I find future me tends to remember what I was doing faster when I use the any/none/all functions. (They also short-circuit, but the readability boost to my productivity helps more than the loop optimization)

[Rizwan]

Swift Solution here. By reading the statement I felt easy but took almost same time as yesterday to solve this as well.

import Cocoa

let start: Int = 134792
let end: Int = 675810

extension BinaryInteger {
    var digits: [Int] {
        return String(describing: self).compactMap { Int(String($0)) }
    }
}

func partOne() {
    var count = 0
    for number in (start ... end) {
        let array = number.digits
        if array.sorted() == array {
            for pair in zip(array, array.dropFirst()) {
                if pair.0 == pair.1 {
                    count = count + 1
                    break;
                }
            }
        }
    }
    print(count)
}

func partTwo() {
    var total = 0
    for number in (start ... end) {
        let array = number.digits
        if array.sorted() == array {
            if (hasAtLeast2Pair(array)) {
                total += 1
            }
        }
    }
    print(total)
}

func hasAtLeast2Pair(_ array: Array<Int>) -> Bool {
    var count = 0
    var dict: [Int:Int] = [:]
    var dupe = false
    for pair in zip(array, array.dropFirst()) {
        if pair.0 == pair.1 {
            count += 1
            dict[pair.0] = count
        }
        else {
            if count == 1 {
                dupe = true
                break
            }
            count = 0
        }
    }
    if count == 1 {
        dupe = true
    }
    return dupe
}

partOne()
partTwo()

[Matt Ellen]

Regex to the rescue!

function passwordcount()
{
    let inputtext = document.querySelector('.puzzle-input').innerHTML;
    let pwrange = inputtext.split('-').map(v => parseInt(v, 10));
    let pwcount = 0;
    //let consecutivesame = /(11|22|33|44|55|66|77|88|99|00)/; /*for part 1*/
    let consecutivesame = /(([^1]|^)11([^1]|$)|([^2]|^)22([^2]|$)|([^3]|^)33([^3]|$)|([^4]|^)44([^4]|$)|([^5]|^)55([^5]|$)|([^6]|^)66([^6]|$)|([^7]|^)77([^7]|$)|([^8]|^)88([^8]|$)|([^9]|^)99([^9]|$)|([^0]|^)00([^0]|$))/;
    for(let i = pwrange[0]; i < pwrange[1]; i++)
    {
        let istr = i.toString();
        let iparts = istr.split('');
        let sortstr = iparts.sort().join('');
        if(sortstr == istr && consecutivesame.test(istr))
        {
            pwcount++;
        }
    }
    return pwcount;
}

Just to make it clear: ([^1]|^)11([^1]|$) says:

• ([^1] find anything other than 1 | or ^) the beginning of the string. The parentheses create a capture group that allows the use of | to mean "or".
• 11 find "11"
• ([^1] find anything other than 1 | or $) the end of the string.

Essentially this searches for "11" surrounded by anything that isn't a 1. Then I repeated it for the other digits.

[Shaurya]

Interesting, I used the same regex for my part 1 too

[Matt Ellen]

Nice solution. I've not used rust, but I hear it's really fast!

[Neil Gall]

Nice, although I wouldn't inflict that on my team-mates!

[Matt Ellen]

It is a bit of a monster.

I've being trying to think of a way to refine it, but then again I'm not likely to be asked to find numbers like that outside of AoC :D

[Jon Bristow]

Even I, someone who loves regexes so much that I made a regex that converted words to Pig Latin, find this hard to read!

It makes sense! I just worry that if I look away from it for too long it will have changed...

It’s still more readable than the regex that “matches a b c where a+b=c” (a,b,c being any rational number)

[Matt Ellen]

Wow. ._.

[Paweł Świątkowski]

Wow, nice solution.

[SavagePixie]

My JavaScript solution:

const checkAdjacent = number => number 
    .toString()
    .split('')
    .some((x, i, a) => x == a[i - 1])

const checkAdjacentTwo = number => number
    .toString()
    .split('')
    .some((x, i, a) => x == a[i - 1] && x != a[i - 2] && x != a[i + 1])

const checkNoDecrease = number => number 
    .toString()
    .split('')
    .every((x, i, a) => {
        const prev = a[i - 1] || 0
        return x >= prev
    })

const findCombinations = (from, to, adjChecker) => Array
    .from({ length: to - from + 1 }, (_, i) => from + i)
    .filter(x => adjChecker(x) && checkNoDecrease(x)).length


module.exports = input => {
    const [ from, to ] = input.split('-')
    const partOne = findCombinations(+from, +to, checkAdjacent)
    const partTwo = findCombinations(+from, +to, checkAdjacentTwo)
    return({ partOne, partTwo })
}

[Shaurya]

The first part was pretty easy and in the second part I was trying to construct a perfect regex initially so that didn't work out. One thing that stumped me a bit was that in rust string.split("") throws a "" at the beginning and the end.

I haven't completed Day 3 yet, gonna do that later. I figured out the logic for Day 3 but there's some problem with the implementation.

I've uploaded all my Advent of Code 2019 solutions in rust on a github repo : github.com/coolshaurya/advent_of_c...

Day 3 solution using Rust

extern crate regex;

#[macro_use]
extern crate lazy_static;

use regex::Regex;
use std::collections::HashMap;

lazy_static! {
    static ref RE1: Regex = Regex::new(r"11|22|33|44|55|66|77|88|99|00").unwrap();
}

fn process_input(raw: String) -> Vec<u32> {
    raw.split("-")
        .map(|val| val.parse::<u32>().unwrap())
        .collect::<Vec<u32>>()
}

fn is_valid_a(password: String) -> bool {
    RE1.is_match(&password) && password.split("").filter(|val| val.len() > 0).is_sorted()
}

fn is_valid_b(password: String) -> bool {
    let correct_digit_order: bool = password.split("").filter(|val| val.len() > 0).is_sorted();
    let mut  only_two_grouping: bool = false;
    let mut digit_frequency = HashMap::new();

    for digit in password.split("").filter(|val| val.len() > 0) {
        let count = digit_frequency.entry(digit).or_insert(0);
        *count += 1
    }

    for digit in digit_frequency.keys() {
        if digit_frequency.get(digit).unwrap() == &2 {
            only_two_grouping = true;
            break;
        }
    }

    correct_digit_order && only_two_grouping
}

fn part_a(input: Vec<u32>) -> u32 {
    let mut valid_passwords: Vec<u32> = vec![];

    for passw in input[0]..input[1] {
        if is_valid_a(passw.to_string()) {
            valid_passwords.push(passw);
        }
    }

    valid_passwords.len() as u32
}

fn part_b(input: Vec<u32>) -> u32 {
    let mut valid_passwords: Vec<u32> = vec![];

    for passw in input[0]..input[1] {
        if is_valid_b(passw.to_string()) {
            valid_passwords.push(passw);
        }
    }

    valid_passwords.len() as u32
}

[Einar Norðfjörð]

Haskell solution

module Main where

import           Data.List

splitWhen :: (Char -> Bool) -> String -> [String]
splitWhen p s =
  case dropWhile p s of
    "" -> []
    s' -> w : splitWhen p s''
      where (w, s'') = break p s'

toPair :: [a] -> (a, a)
toPair (x:y:xs) = (x, y)

isAscending :: String -> Bool
isAscending []       = True
isAscending [_]      = True
isAscending (x:y:xs) = x <= y && isAscending (y : xs)

hasAdjacentDigits :: String -> Bool
hasAdjacentDigits xs = any (> 1) (length <$> group xs)

hasAdjacentDigitsInGroups :: String -> Bool
hasAdjacentDigitsInGroups xs =
  let sequenceLengths = length <$> group xs
   in (any (== 2) sequenceLengths)

validate :: String -> Bool
validate xs = (isAscending xs) && (hasAdjacentDigits xs)

validatePart2 :: String -> Bool
validatePart2 xs = (isAscending xs) && (hasAdjacentDigitsInGroups xs)

main :: IO ()
main = do
  (from, to) <- getContents >>= pure . splitWhen (== '-') >>= pure . toPair
  putStrLn "Part 1"
  putStrLn "Test Cases:"
  print $
    length $
    filter (== True) $
    (validate . show) <$> [(read from :: Int) .. (read to :: Int)]
  putStr "\n\n"
  putStrLn "Part 2"
  print $
    length $
    filter (== True) $
    (validatePart2 . show) <$> [(read from :: Int) .. (read to :: Int)]

[Ali Spittel]

Brute force Python solution:

def check_ascending(n):
    return "".join(sorted(n)) == n


def check_repeat(n):
    for digit1, digit2 in zip(n, n[1:]):
        if digit1 == digit2:
            return True


def check_two_consecutive_digits(n):
    repeat_count = 0
    for n1, n2 in zip(n, n[1:]):
        if n1 == n2:
            repeat_count += 1
        else:
            if repeat_count == 1:
                return True
            repeat_count = 0
    return repeat_count == 1


p1_count = 0
p2_count = 0

for n in range(134792, 675811):
    n = str(n)
    if check_ascending(n):
        if check_repeat(n):
            p1_count += 1
        if check_two_consecutive_digits(n):
            p2_count += 1

print(f"Part 1: {p1_count}")
print(f"Part 2: {p2_count}")

For me, this was 100x easier than day 3.