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

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

[Neil Gall]

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

[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. ._.

[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

[Paweł Świątkowski]

Wow, nice solution.

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

[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]

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.

[Farah Anjum]

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

[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

[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 })
}

[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

[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()

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

[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
}

[Sarah]

It's not as good as I wanted it to be, am pretty sure it was possible to solve in a nicer way with regex. But had to do it quickly between meetings so 🤷‍♀️ Am satisfied though

matches = 0

for number in range(min, max + 1):
    is_increasing = True
    has_double = False

    previous = []

    for character in str(number):
        if len(previous) > 0:
            if character < previous[-1]:
                is_increasing = False
                break
            if previous.count(character) > 0:
                has_double = True

        previous.append(character)

    if is_increasing and has_double and 2 in Counter(previous).values():
        matches += 1


print(matches)

[Ryan Palo]

My motto for today is: it's not stupid if it works. I didn't feel like fighting with Rust over "whose characters belong to whom" and "you can't borrow that" and "don't add strings together". Don't judge me.

/// Day 4: Secure Container
/// 
/// Crack the password to a Venus fuel container

fn generate_passwords() -> Vec<usize> {
    let mut results: Vec<usize> = Vec::new();

    for a in 1..=6 {
        for b in 0..=9 {
            for c in 0..=9 {
                for d in 0..=9 {
                    for e in 0..=9 {
                        for f in 0..=9 {
                            let num = a * 100000 + b * 10000 + c * 1000 + d * 100 + e * 10 + f;
                            if num < 134792 || num > 675810 {
                                continue;
                            }

                            if a != b && b != c && c != d && d != e && e != f {
                                continue;
                            }

                            if a > b || b > c || c > d || d > e || e > f {
                                continue;
                            }

                            results.push(num);
                        }
                    }
                }
            }
        }
    }

    results
}

fn generate_passwords2() -> Vec<usize> {
    let mut results: Vec<usize> = Vec::new();

    for a in 1..=6 {
        for b in 0..=9 {
            for c in 0..=9 {
                for d in 0..=9 {
                    for e in 0..=9 {
                        for f in 0..=9 {
                            let num = a * 100000 + b * 10000 + c * 1000 + d * 100 + e * 10 + f;
                            if num < 134792 || num > 675810 {
                                continue;
                            }

                            if !((a == b && b != c) ||
                                 (b == c && a != b && c != d) ||
                                 (c == d && b != c && d != e) ||
                                 (d == e && c != d && e != f) ||
                                 (e == f && d != e)) {
                                continue;
                            }

                            if a > b || b > c || c > d || d > e || e > f {
                                continue;
                            }

                            results.push(num);
                        }
                    }
                }
            }
        }
    }

    results
}

pub fn run() {
    let candidates = generate_passwords();
    println!("There are {} possible passwords.", candidates.len());
    let candidates2 = generate_passwords2();
    println!("For round 2, there are {} possible passwords.", candidates2.len());
}

[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)]

[Yordi Verkroost]

My solutions in Elixir. I'm just posting the final solution for part two since that essentially contains the solution for part one as well. A very nice day to use the power of pattern-matching!

defmodule Aoc19.Day4b do
  @moduledoc false

  def start do
    {lower, upper} = read()

    check(lower, upper, 0)
  end

  defp check(current, upper, count) when current <= upper do
    with :ok <- adjacent?(current),
         :ok <- increasing?(current) do
      check(current + 1, upper, count + 1)
    else
      _ -> check(current + 1, upper, count)
    end
  end

  defp check(_, _, count), do: count

  defp increasing?(current) do
    current
    |> Integer.to_string()
    |> String.graphemes()
    |> is_increasing?()
  end

  defp is_increasing?([]), do: :ok
  defp is_increasing?([_]), do: :ok

  defp is_increasing?([h1, h2 | rest]) when h1 <= h2 do
    is_increasing?([h2 | rest])
  end

  defp is_increasing?(_), do: :error

  defp adjacent?(current) do
    current
    |> Integer.to_string()
    |> String.graphemes()
    |> is_adjacent?()
  end

  defp is_adjacent?([]), do: :error

  defp is_adjacent?([h1, h1, h1 | rest]) do
    rest = skip(h1, rest)
    is_adjacent?(rest)
  end

  defp is_adjacent?([h1, h1 | _rest]), do: :ok
  defp is_adjacent?([_h1 | rest]), do: is_adjacent?(rest)

  defp skip(h, [h | rest]), do: skip(h, rest) 
  defp skip(_h, rest), do: rest

  defp read, do: {231_832, 767_346}
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).