loading...
Cover image for Advent of Code 2019 Solution Megathread - Day 4: Secure Container

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

jbristow profile image Jon Bristow Updated on ・2 min read

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

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

Discussion

pic
Editor guide
Collapse
mellen profile image
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.

Collapse
neilgall profile image
Neil Gall

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

Collapse
jbristow profile image
Jon Bristow Author

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)

Thread Thread
mellen profile image
Matt Ellen

Wow. ._.

Collapse
mellen profile image
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

Collapse
katafrakt profile image
Paweł Świątkowski

Wow, nice solution.

Collapse
coolshaurya profile image
Shaurya Shubham

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

Collapse
mellen profile image
Matt Ellen

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

Collapse
jbristow profile image
Jon Bristow Author

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.

Collapse
farahanjum profile image
Farah Anjum

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

Collapse
jbristow profile image
Jon Bristow Author

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.

Collapse
farahanjum profile image
Farah Anjum

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

Collapse
ballpointcarrot profile image
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)))))
Collapse
jbristow profile image
Jon Bristow Author

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.

Collapse
ballpointcarrot profile image
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

Collapse
ballpointcarrot profile image
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

Collapse
savagepixie profile image
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 })
}
Collapse
rtran profile image
Ray Tran ☁️

Here's my Python solution. I went for brute force, but looking forward to seeing how others solved it.

from collections import defaultdict

def check_rules(num):
    repeat_counts = defaultdict(int)
    decreases = False

    for i in range(len(num)):
        if i > 0 and num[i] == num[i - 1]:
            repeat_counts[num[i]] += 1
        if i > 0 and num[i] < num[i - 1]:
            decreases = True
    return repeat_counts, decreases 

nums = map(str, range(123257, 647016))

# part 1
num_pw_candidates_part1 = 0
for num in nums:
    repeat_counts, decreases = check_rules(num)
    if len(repeat_counts) > 0 and not decreases:
        num_pw_candidates_part1 += 1    
print(num_pw_candidates_part1)

# part 2
num_pw_candidates_part2 = 0
for num in nums:
    repeat_counts, decreases = check_rules(num)
    has_adjacent = 1 in repeat_counts.values()
    if has_adjacent and not decreases:
        num_pw_candidates_part2 += 1
print(num_pw_candidates_part2)
Collapse
aspittel profile image
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.

Collapse
rizzu26 profile image
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()

Collapse
coolshaurya profile image
Shaurya Shubham

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
}
Collapse
fossheim profile image
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)
Collapse
rpalo profile image
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());
}
Collapse
nordfjord profile image
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)]
Collapse
yordiverkroost profile image
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
Collapse
lindakatcodes profile image
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);
Collapse
farahanjum profile image
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');
Collapse
neilgall profile image
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).
Collapse
maxart2501 profile image
Massimo Artizzu

My solution in JavaScript, with some regex magic.

const start = 123257;
const end = 647015;

function isMonotone(pwd) {
  return pwd.split('').every((digit, index) => index === 0 || digit >= pwd[index - 1]);
}
function hasGroupOfTwo(pwd) { // For part 1
  return /(\d)\1/.test(pwd);
}
function hasGroupOfOnlyTwo(pwd) { // For part 2
  return (pwd.match(/(\d)\1+/g) || []).map(sequence => sequence.length).includes(2);
}
function isCandidate(pwd) {
  return hasGroupOfTwo(pwd) && isMonotone(pwd);
}

let validCount = 0;
for (let pwd = start; pwd <= end; pwd++) {
  validCount += isCandidate(String(pwd));
}

console.log(validCount);

For the second part, replace hasGroupOfTwo with hasGroupOfOnlyTwo in isCandidate.

Check out my solutions at github.com/MaxArt2501/advent-of-co...

Collapse
mustafahaddara profile image
Mustafa Haddara

Part 2 solution

#!/usr/bin/env ruby

def find_valid_passwords(min, max)
    total = 0
    current = min
    while current <= max
        str = current.to_s
        if has_exactly_two_adjacent(str) && digits_increasing(str)
            total += 1
        end
        current += 1
    end
    return total
end


def has_exactly_two_adjacent(str)
    10.times do |n|
        double = n.to_s * 2
        triple = n.to_s * 3
        if str.include?(double) && !str.include?(triple)
            return true
        end
    end
    return false
end

def digits_increasing(str)
    last_val = nil
    str.split('').each do |c|
        val = c.to_i
        if last_val != nil && last_val > val
            return false
        end
        last_val = val
    end
    return true
end


if __FILE__ == $0
    positions = []
    File.open(ARGV[0], "r") do |file_handle|
        file_handle.each_line do |line|
            range = line.split('-')
            puts find_valid_passwords(range[0].to_i, range[1].to_i)
        end
      end
end

not a fan of my has_exactly_two_adjacent method but, hey, it works ¯\_(ツ)_/¯

my part 1's has_two_adjacent method was a lot nicer:

def has_two_adjacent(str)
    last_c = nil
    str.split('').each do |c|
        if last_c != nil && last_c == c
            return true
        end
        last_c = c
    end
    return false
end
Collapse
smh30 profile image
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 :)

Collapse
jbristow profile image
Jon Bristow Author

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)

Collapse
supriyasrivatsa profile image
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()
}
Collapse
jbristow profile image
Jon Bristow Author

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)

Collapse
katafrakt profile image
Paweł Świątkowski

I wrote my solution in Zig this time. Funny experiment. Code is a bit ugly and for sure suboptimal, as it usually happens when you try out a language for the first time:

const assert = @import("std").debug.assert;
const warn = @import("std").debug.warn;

fn numToDigits(num: i32) [6]i32 {
    var array: [6]i32 = undefined;
    var value: i32 = num;

    for (array) |*item| {
        const digit = @mod(value, 10);
        item.* = digit;
        value = @divFloor(value, 10);
    }
    return array;
}

test "numToDigits" {
    const num: i32 = 321456;
    const re = numToDigits(num);
    assert(re[0] == 6);
    assert(re[3] == 1);
}

fn isOk(digits: [6]i32) bool {
    var adjacent = false;
    var nonIncreasing = true; // since we're going opposite direction, condition changes
    var lastDigit = digits[0];
    var idx = @intCast(i32, 1);
    while(idx < 6) {
        var currentDigit = digits[@intCast(usize, idx)];
        if (currentDigit > lastDigit) {
            nonIncreasing = false;
        }
        if (currentDigit == lastDigit) {
            adjacent = true;
        }

        idx += 1;
        lastDigit = currentDigit;
    }

    return (adjacent and nonIncreasing);
}

test "isOK" {
    assert(isOk(numToDigits(111111)));
    assert(!isOk(numToDigits(223450)));
    assert(!isOk(numToDigits(123789)));
}

fn hasAdjacent2(digits: [6]i32) bool {
    var lastDigit = digits[1];
    var lastButOneDigit = digits[0];
    var idx = @intCast(i32, 2);
    var adjacent2 = lastDigit == lastButOneDigit;

    while (idx < 6) {
        var currentDigit = digits[@intCast(usize, idx)];
        if (adjacent2 and currentDigit != lastDigit) {
            return true;
        } else if (adjacent2) {
            adjacent2 = false;
        } else {
            adjacent2 = currentDigit == lastDigit and currentDigit != lastButOneDigit;
        }
        idx += 1;
        lastButOneDigit = lastDigit;
        lastDigit = currentDigit;
    }

    return adjacent2;
}

test "hasAdjacent2" {
    assert(hasAdjacent2(numToDigits(112233)));
    assert(!hasAdjacent2(numToDigits(123444)));
    assert(!hasAdjacent2(numToDigits(444321)));
    assert(!hasAdjacent2(numToDigits(444444)));
    assert(hasAdjacent2(numToDigits(444322)));
    assert(hasAdjacent2(numToDigits(443222)));
    assert(hasAdjacent2(numToDigits(111122)));
    assert(hasAdjacent2(numToDigits(112222)));
}

pub fn main() void {
    var current: i32 = 278384;
    const limit: i32 = 824795;
    var count = @intCast(i32, 0);
    var count2 = @intCast(i32, 0);

    while(current <= limit) {
        if (isOk(numToDigits(current))) {
            count += 1;
            if(hasAdjacent2(numToDigits(current))) count2 += 1;
        }
        current += 1;
    }

    warn("{}\n", count);
    warn("{}\n", count2);
}
Collapse
whatapalaver profile image
Angela Wolff

Here's my Ruby attempt for part 1
I was trying to avoid iterating through every number but it seems a little complex

class Password

  attr_accessor :start_code, :end_code
  LENGTH = 6

  def initialize(start_code, end_code)
    @start_code = start_code
    @end_code = end_code
  end

  def valid_options
    valid_options = []
    current_value = next_valid_option(start_code)
    while current_value <= end_code
      valid_options << current_value
      current_value = next_valid_option(current_value + 1)
    end
    valid_options
  end

  def next_valid_option(code)
    possible = next_increaser_option(code)
    while possible.digits.uniq.length == LENGTH
      possible = next_increaser_option(possible + 1)
    end
    possible
  end

  def next_increaser_option(code)
    digits = code.to_s.chars.map(&:to_i)
    output_digits = []
    digits.each_with_index do |digit, index|
      if index.zero? || digit >= output_digits[index - 1] 
        output_digits << digit
      else
        multiplier = digits.length - index
        multiplier.times {output_digits << output_digits[index-1]}
        break
      end
    end
    output_digits.join.to_i
  end


  part1 = Password.new(307237,769058)
  part1_output = part1.valid_options
  puts part1_output.count

end
Collapse
fiddlerpianist profile image
fiddlerpianist

This time I went to bed early and woke up at 4am to do the problem. Oddly, I think that will work better for me! And I found this problem much easier than Day 3.

I had the same issue with the wording of Part Two, so thank you for the interpretive hint.

I have a tendency to write very low-level implementations (without including libs)...partly because I'm not all that familiar with what's available in the Python ecosystem, and partly because I kind of like controlling the nitty gritty!

# Part One: How many passwords meet the required criteria?
def determineIfCriteriaMetPartOne(num):
    digits = [int(x) for x in str(num)]
    #print (digits)
    if len(digits) != 6:
        return False

    foundDoubleDigit = False
    previousDigit = -1
    for i in digits:
        if i < previousDigit:
            return False
        if i == previousDigit:
            foundDoubleDigit = True
        previousDigit = i

    #if foundDoubleDigit:
        #print (num)
    return foundDoubleDigit

# Part Two: How many passwords meet the required criteria?
def determineIfCriteriaMetPartTwo(num):
    digits = [int(x) for x in str(num)]
    #print (digits)
    if len(digits) != 6:
        return False

    repeatedDigitCount = 1
    foundDoubleDigit = False
    previousDigit = -1
    for i in digits:
        if i < previousDigit:
            return False
        elif i == previousDigit:
            repeatedDigitCount += 1
        elif i > previousDigit:
            # we found an exact sequence of 2. Mark it, then reset
            if repeatedDigitCount == 2:
                foundDoubleDigit = True
            repeatedDigitCount = 1
        previousDigit = i

    # In case the double digit is at the end
    if repeatedDigitCount == 2:
        foundDoubleDigit = True

    return foundDoubleDigit

# These were unique to the instance of my puzzle
myGivenLowNUmber = 128392
myGivenHighNumber = 643281

counter = 0
for i in range(128392, 643281 + 1):
    if determineIfCriteriaMetPartOne(i):
        counter += 1
print ("Part One: %i" % counter)

counter = 0
for i in range(128392, 643281 + 1):
    if determineIfCriteriaMetPartTwo(i):
        counter += 1
print ("Part Two: %i" % counter)
Collapse
auerbachstefan profile image
auerbachstefan

here is my python solution (basically a one-liner):

part1:

input = [int(i) for i in open('input.txt', 'r').read().split('-')]
res = sum([sum([s[i] > s[i + 1] for i in range(len(s) - 1)]) == 0 and len(set([x for x in s]))<=5
    for s in [str(i) for i in range(input[0], input[1] + 1)]])
print(res)

part2:

input = [int(i) for i in open('input.txt', 'r').read().split('-')]
res = sum([sum([s[i] > s[i + 1] for i in range(len(s) - 1)]) == 0 and 2 in [s.count(c) for c in s]
    for s in [str(i) for i in range(input[0], input[1] + 1)]])
print(res)
Collapse
auerbachstefan profile image
auerbachstefan

a bit shorter:

i = [int(x) for x in open('input.txt', 'r').read().split('-')]
res = sum( [ s == ''.join(sorted(s)) and len(set(s))<=5
    for s in [str(c) for c in range(i[0], i[1] + 1)]])
print(res)

i = [int(x) for x in open('input.txt', 'r').read().split('-')]
res = sum([s == ''.join(sorted(s)) and 2 in [s.count(c) for c in s]
    for s in [str(c) for c in range(i[0], i[1] + 1)]])
print(res)
Collapse
bretthancox profile image
bretthancox

Solution in Clojure:

Day 4

Collapse
thibpat profile image
Thibaut Patel

A javascript walkthrough:

Collapse
richymueller profile image
RichyMueller

COBOL zOS Solution

Variables

01 ADVENT-OF-CODE.

05 AOC-COUNTER PIC 9(6).

05 AOC-CANDIDAT PIC 9(6) VALUE 0.

01 AOC REDEFINES ADVENT-OF-CODE.

05 S1 PIC 9(1).

05 S2 PIC 9(1).

05 S3 PIC 9(1).

05 S4 PIC 9(1).

05 S5 PIC 9(1).

05 S6 PIC 9(1).

Section for the problem

  PERFORM UNTIL AOC-COUNTER > 732736                        

     EVALUATE TRUE                                          
  • A PAIR IN MY NUMBER ? WHEN S1 = S2 WHEN S2 = S3 WHEN S3 = S4 WHEN S4 = S5 WHEN S5 = S6
  • DIGITS INCREASING OR CONSTANT ?

    IF S6 >= S5 AND

    S5 >= S4 AND

    S4 >= S3 AND

    S3 >= S2 AND

    S2 >= S1

    ADD 1 TO AOC-CANDIDAT

    DISPLAY MY-SERVICE-NAME ' C : ' AOC-COUNTER

    END-IF

    WHEN OTHER

    CONTINUE

    END-EVALUATE

    ADD 1 TO AOC-COUNTER

    END-PERFORM

    DISPLAY MY-SERVICE-NAME ' CANDIDAT: ' AOC-CANDIDAT