DEV Community

Cover image for Advent of Code 2020 Solution Megathread - Day 2: Password Philosophy
Ryan Palo
Ryan Palo

Posted on • Edited on

Advent of Code 2020 Solution Megathread - Day 2: Password Philosophy

With Day 1 in the books, hopefully you’re starting to get into the swing of things. I know that I definitely didn’t spend a few hours fiddling with my AoC tooling yesterday. That would be obsessive and overkill. 😐

The Puzzle

Today’s puzzle involves passwords and security policies. Each listing has a password alongside the security policy in place for it, but some passwords aren’t compliant! It’s our job to analyze the passwords and sort things out.

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19
Enter fullscreen mode Exit fullscreen mode

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 03:05PM 12/12/2020 PST.

Language Count
Python 5
C 2
Rust 2
JavaScript 2
C# 1
Raku 1
PHP 1
Scratch 1
Elixir 1
Haskell 1
COBOL 1
Ruby 1

Merry Coding!

Top comments (23)

Collapse
 
galoisgirl profile image
Anna

COBOL (second one is on my GitHub):

   IDENTIFICATION DIVISION.
   PROGRAM-ID. AOC-2020-02-1.
   AUTHOR. ANNA KOSIERADZKA.

   ENVIRONMENT DIVISION.
   INPUT-OUTPUT SECTION.
   FILE-CONTROL.
       SELECT INPUTFILE ASSIGN TO "d2.input"
       ORGANIZATION IS LINE SEQUENTIAL.

   DATA DIVISION.
   FILE SECTION.
     FD INPUTFILE
     RECORD IS VARYING IN SIZE FROM 8 to 50
     DEPENDING ON REC-LEN.
     01 INPUTRECORD PIC X(50).
   WORKING-STORAGE SECTION.
     01 FILE-STATUS PIC 9 VALUE 0.
     01 REC-LEN  PIC 9(2) COMP.
     01 WS-MIN PIC 9(4).
     01 WS-MAX PIC 9(4).
     01 WS-CHAR PIC A.
     01 WS-STRING-EMPTY PIC X.
     01 WS-PASSWORD PIC A(50).
     01 WS-SUBSTR-1 PIC X(5). 
     01 WS-CHAR-COUNT PIC 9(2).

   LOCAL-STORAGE SECTION.
     01 CORRECT-ROWS UNSIGNED-INT VALUE 0.

   PROCEDURE DIVISION.
   001-MAIN.
        OPEN INPUT INPUTFILE.
        PERFORM 002-READ UNTIL FILE-STATUS = 1.
        CLOSE INPUTFILE.
        DISPLAY CORRECT-ROWS.
        STOP RUN.

   002-READ.
        READ INPUTFILE
            AT END MOVE 1 TO FILE-STATUS
            NOT AT END PERFORM 003-PROCESS-RECORD
        END-READ.

   003-PROCESS-RECORD.
       MOVE 0 TO WS-CHAR-COUNT.
       UNSTRING INPUTRECORD DELIMITED BY SPACE OR "-" OR ":" INTO 
           WS-MIN
           WS-MAX
           WS-CHAR
           WS-STRING-EMPTY
           WS-PASSWORD.
       INSPECT WS-PASSWORD TALLYING WS-CHAR-COUNT FOR ALL WS-CHAR.
       IF WS-CHAR-COUNT >= WS-MIN AND WS-CHAR-COUNT <= WS-MAX THEN 
          ADD 1 TO CORRECT-ROWS
       END-IF.
Enter fullscreen mode Exit fullscreen mode
Collapse
 
patryk profile image
Patryk Woziński • Edited

IMO you’re a real hipster using Cobol! Great job! :)

Collapse
 
galoisgirl profile image
Anna

Thanks! Gotta stay busy in the pandemic somehow. :)

Thread Thread
 
patryk profile image
Patryk Woziński

May I ask you - have you used Cobol before? Or it's just your pandemic-advent challenge? :D

Thread Thread
 
galoisgirl profile image
Anna • Edited

I started in the spring and wrote a couple things like FizzBuzz: github.com/GaloisGirl/Coding/tree/...
Then I had a bit of a life, and now I'm having a second wave of COBOL.

Collapse
 
rpalo profile image
Ryan Palo

Ooh boy it's a little early in the season to already be stumped by an off-by-one bug. 1-BASED INDICES RYAN! 1-BASED! IT'S RIGHT THERE IN THE PROMPT!

Also, I started a little parsing module to help me with some of the repetitive tedia.

Day2.h:

/// Day 2: Password Philosophy 
/// 
/// Find the passwords that aren't compliant.

#include <stdlib.h>
#include <stdint.h>

/// A Policied Password is a password that is accompanied by a policy
/// consisting of two positive integers and a letter.  These components
/// can be used to validate the password.
typedef struct {
  int a;
  int b;
  char letter;
  char password[30];
} PoliciedPassword;

/// Part 1 calculates how many valid passwords there are.
/// A password is valid if the # of occurrences of 'letter' is between
/// 'a' and 'b,' inclusive.
///
/// passes: the list of policied passwords to check
/// count: the number of passwords to check
int part1(PoliciedPassword** passes, size_t count);

/// Part 2 calculates how many valid passwords there are.
/// A password is valid of either the 'a' index or 'b' index character 
/// (1-based!) is equal to 'letter,' but not both.
int part2(PoliciedPassword** passes, size_t count);

/// day2 runs both parts in sequence and outputs their results.
int day2();
Enter fullscreen mode Exit fullscreen mode

Day2.c:

/// Day 2: Password Philosophy 
/// 
/// Find the passwords that aren't compliant.

#include "Day2.h"
#include "parsing.h"

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/// Parse the input file,
static PoliciedPassword** parse(size_t* lines) {
  FILE* fp;
  fp = fopen("data/day2.txt", "r");
  if (fp == NULL) {
    printf("Couldn't open input file.\n");
    exit(EXIT_FAILURE);
  }

  *lines = count_lines(fp);

  PoliciedPassword** passes = malloc(sizeof(PoliciedPassword*) * *lines);

  for (size_t i = 0; i < *lines; i++) {
    PoliciedPassword* p = malloc(sizeof(PoliciedPassword));
    fscanf(fp, "%d-%d %c: %s\n", &p->a, &p->b, &p->letter, p->password);
    passes[i] = p;
  }

  fclose(fp);
  return passes;
}

static void freePoliciedPasswordList(PoliciedPassword** passes, size_t count) {
  for (size_t i = 0; i < count; i++) {
    free(passes[i]);
    passes[i] = NULL;
  }
  free(passes);
}

int part1(PoliciedPassword** passes, size_t count) {
  size_t valid = 0;

  for (size_t i = 0; i < count; i++) {
    PoliciedPassword* p = passes[i];
    uint8_t matches = 0;
    for (size_t j = 0; p->password[j]; j++) {
      if (p->password[j] == p->letter) matches++;
    }
    if (p->a <= matches && matches <= p->b) valid++;
  }
  return valid;
}

int part2(PoliciedPassword** passes, size_t count) {
  size_t valid = 0;

  for (size_t i = 0; i < count; i++) {
    PoliciedPassword* p = passes[i];
    int matches = 0;
    if (p->password[p->a - 1] == p->letter) matches++;
    if (p->password[p->b - 1] == p->letter) matches++;
    if (matches == 1) valid++;
  }
  return valid;
}

int day2() {
  size_t count;
  PoliciedPassword** passes = parse(&count);
  printf("====== Day 2 ======\n");
  printf("Part 1: %d\n", part1(passes, count));
  printf("Part 2: %d\n", part2(passes, count));
  freePoliciedPasswordList(passes, count);
  return EXIT_SUCCESS;
}
Enter fullscreen mode Exit fullscreen mode

parsing.h:

#ifndef AOC2020_PARSING_H
#define AOC2020_PARSING_H

#include <stdio.h>
#include <stdlib.h>

/// Counts the number of newline characters in a text file.
/// Assumes no newline at the end of the last line (so adds +1 more)
size_t count_lines(FILE* fp);

#endif
Enter fullscreen mode Exit fullscreen mode

parsing.c:

#include "parsing.h"

#include <stdlib.h>
#include <stdio.h>

size_t count_lines(FILE* fp) {
  size_t lines = 0;
  while (!feof(fp)) {
    if (getc(fp) == '\n') lines++;
  }

  rewind(fp);
  return lines + 1;
}
Enter fullscreen mode Exit fullscreen mode

Also a little tooling to help generate the daily files:

bin/newday:

#!/usr/bin/env bash

# newday: Creates a new day of files for the Advent of Code Challenge
#
# Date:   12/2/2020
# Author: Ryan Palo

function usage() {
  echo "usage: newday NUMBER"
  echo
  echo "    NUMBER: The number of the day to create.  Will be inserted"
  echo "            into the templates and used for filenames."
}

function help() {
  echo "newday: Creates a new day of files for the Advent of Code challenge."
  echo
  usage
  echo
}

function make_day() {
  day="$1"
  echo "Creating Day ${day}." >&2
  sed "s/{X}/$day/g" "templates/DayX.c" > "src/Day${day}.c"
  sed "s/{X}/$day/g" "templates/DayX.h" > "src/Day${day}.h"
  sed "s/{X}/$day/g" "templates/TestDayX.c" > "test/TestDay${day}.c"
  sed "s/{X}/$day/g" 'templates/main.c' > 'src/main.c'
  touch "data/day${day}.txt"
  echo "Complete." >&2
}

function main() {
  if [[ "$#" -ne 1 ]]; then
    usage
    exit 1
  fi

  if [[ "$1" == '-h' ]]; then
    help
    exit 0
  fi

  if ! [[ "$1" =~ [:digit:]+ ]]; then
    echo "Input must be a number"
    exit 1
  fi

  make_day "$1"
}

main "$@"
Enter fullscreen mode Exit fullscreen mode
Collapse
 
patryk profile image
Patryk Woziński • Edited

Hi guys!
The second day was awesome. I've really enjoyed the task. :) I'm still learning Elixir, but I think my solution was not that bad. :) Of course, I did it in Elixir.

This time I've split the day into two modules - one per part. The full solution is on my GitHub repository.

The first part of the day looks like:

defmodule AdventOfCode.Day2Part1 do
  @pattern ~r/(?<min>\d*)-(?<max>\d*)\s(?<char>\w):\s*(?<password>\w*)/

  def calculate(file_path) do
    file_path
    |> File.stream!()
    |> Stream.map(&String.replace(&1, "\n", ""))
    |> Stream.map(fn line ->
      Regex.named_captures(@pattern, line)
    end)
    |> Stream.filter(fn %{"char" => char, "min" => min, "max" => max, "password" => password} ->
      occurrences =
        password
        |> String.graphemes()
        |> Enum.count(&(&1 == char))

      occurrences >= String.to_integer(min) and occurrences <= String.to_integer(max)
    end)
    |> Enum.count()
  end
end
Enter fullscreen mode Exit fullscreen mode

The second part of the day looks like:

defmodule AdventOfCode.Day2Part2 do
  @pattern ~r/(?<x>\d*)-(?<y>\d*)\s(?<char>\w):\s*(?<password>\w*)/

  def calculate(file_path) do
    file_path
    |> File.stream!()
    |> Stream.map(&String.replace(&1, "\n", ""))
    |> Stream.map(fn line ->
      Regex.named_captures(@pattern, line)
    end)
    |> Stream.filter(fn %{"char" => char, "x" => x, "y" => y, "password" => password} ->
      at_position?(char, x, password) != at_position?(char, y, password)
    end)
    |> Enum.count()
  end

  defp at_position?(char, position, password) do
    String.at(password, String.to_integer(position) - 1) == char
  end
end
Enter fullscreen mode Exit fullscreen mode
Collapse
 
ballpointcarrot profile image
Christopher Kruse

Rust solution for Day 2. Felt happy and clever at the inclusion of the XOR for part 2.

Full repo on Github.

use aoc_runner_derive::{aoc, aoc_generator};
use regex::Regex;

struct PasswordChallenge {
    password: String,
    min: usize,
    max: usize,
    search_char: char,
}

#[aoc_generator(day2)]
fn parse_input_day1(input: &str) -> Vec<PasswordChallenge> {
    input.lines().map(|v| parse_line(v)).collect()
}

fn parse_line(line: &str) -> PasswordChallenge {
    let pattern = Regex::new(r"^(\d+)-(\d+)\s(\w):\s(\w+)$").expect("couldn't create Regex");
    let captures = pattern.captures(line).unwrap();

    PasswordChallenge {
        min: str::parse(captures.get(1).unwrap().as_str()).unwrap(),
        max: str::parse(captures.get(2).unwrap().as_str()).unwrap(),
        search_char: (captures.get(3).unwrap().as_str()).chars().next().unwrap(),
        password: String::from(captures.get(4).unwrap().as_str()),
    }
}

#[aoc(day2, part1)]
fn valid_password_count(input: &Vec<PasswordChallenge>) -> usize {
    input
        .iter()
        .filter(|challenge| is_valid_password_by_char_count(challenge))
        .count()
}

fn is_valid_password_by_char_count(challenge: &PasswordChallenge) -> bool {
    let pw_chars_count = challenge
        .password
        .chars()
        .filter(|ch| ch == &challenge.search_char)
        .count();

    challenge.min <= pw_chars_count && challenge.max >= pw_chars_count
}

#[aoc(day2, part2)]
fn valid_password_positions(input: &Vec<PasswordChallenge>) -> usize {
    input
        .iter()
        .filter(|challenge| is_valid_password_by_pos(challenge))
        .count()
}

fn is_valid_password_by_pos(challenge: &PasswordChallenge) -> bool {
    challenge.password.char_indices().fold(false, |memo, (idx, ch)| {
        if idx == challenge.min-1 || idx == challenge.max-1 {
            memo ^ (ch == challenge.search_char)
        } else {
            memo
        }
    })
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
patryk profile image
Patryk Woziński

Rust looks intriguing! I hope that one day I will find time to learn this language. :D

Collapse
 
karaajc profile image
Kara Carrell

Hey Y'all!! This time, I actually brought the input.txt file in as it was, and again, made a ruby solution that im sure could be a bit more refactored, but i got to play with regex! so that was fun...
Here's my full code, and here's a snippet of what i did to solve it:

class PasswordChecker

  attr_reader :parse_passwords, :check_passwords

  def initialize(passwords)
    @passwords = passwords
    @parsed_passwords = parse_passwords
  end

  def parse_passwords
    parsed = @passwords.map do |item|
      item_split = item.match(/(^\d*)-(\d*) (\w): (\w*)/)
      {
        min: item_split[1].to_i,
        max: item_split[2].to_i,
        letter: item_split[3],
        password: item_split[4]
      }
    end
    parsed
  end

  def validate_password_frequency(log)
    # puts "rules are minimum #{log[:min]} and max #{log[:max]}"
    # puts "there are #{log[:password].count(log[:letter])} letter #{log[:letter]}'s"
    log[:password].count(log[:letter]).to_i.between?(log[:min],log[:max])
  end

  def validate_password_accuracy(log)
    return false unless log[:password].include?(log[:letter])
    return false if log[:password][log[:min] - 1] == log[:letter] && log[:password][log[:max] - 1] == log[:letter]

    # puts "rules are letter #{log[:letter]} must be at position #{log[:min]} and then at position #{log[:max]}"
    # puts "there's a #{log[:password][log[:min] - 1]} at position #{log[:min]} and a #{log[:password][log[:max] - 1]} at position #{log[:max]}"
    log[:password][log[:min] - 1] == log[:letter] || log[:password][log[:max] - 1] == log[:letter]
  end

  def check_passwords(way="frequency")
    @parsed_passwords.map do |log|
        if way == "accuracy"
          validate_password_accuracy(log)
        else
          validate_password_frequency(log)
        end
    end.count(true)
  end

end
Enter fullscreen mode Exit fullscreen mode
Collapse
 
aspittel profile image
Ali Spittel

Mine!

def check_count_in_range(password, letter, start, stop):
    return password.count(letter) >= start and password.count(letter) <= stop


def check_indexes(password, letter, start, stop):
    return (password[start] == letter or password[stop] == letter) and (password[start] != password[stop])


with open('input.txt') as file:
    letters = [num.split(": ") for num in file]
    part1_tally = 0
    part2_tally = 0
    for policy, password in letters:
        length, letter = policy.split(" ")
        start, stop = length.split("-")
        start, stop = int(start), int(stop)

        # part 1
        if check_count_in_range(password, letter, start, stop): part1_tally += 1

        # part 2
        if check_indexes(password, letter, start - 1, stop - 1): part2_tally += 1


    print("Part 1", part1_tally)
    print("Part 2", part2_tally)
Enter fullscreen mode Exit fullscreen mode
Collapse
 
neilgall profile image
Neil Gall

Using AoC to brush up my Rust this year.

I adapted Bodil's parser combinators into a little parser module, as I suspect there'll be much more parsing to come.

And then the solution is:


mod parser;

use std::fs::File;
use std::io::prelude::*;
use std::ops::Range;
use parser::*;


// ---- model

#[derive(Debug, Eq, PartialEq)]
struct Password {
    position1: usize,
    position2: usize,
    character: char,
    password: String
}

// ---- model parser

fn password(input: &str) -> ParseResult<Password> {
    let pos1p = first(integer, string("-"));
    let pos2p = first(integer, whitespace);
    let charp = first(letter, string(": "));
    let passp = one_or_more(letter);
    let parser = map(seq(pos1p, seq(pos2p, seq(charp, passp))), |(n1, (n2, (c, p)))| Password {
        position1: n1 as usize,
        position2: n2 as usize,
        character: c,
        password: p.into_iter().collect()
    });
    parser.parse(input)
}

// --- input file

fn read_file(filename: &str) -> std::io::Result<String> {
    let mut file = File::open(filename)?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    Ok(contents)
}

fn parse_input(input: &str) -> ParseResult<Vec<Password>> {
    let p = one_or_more(first(password, whitespace));
    p.parse(input)
}


// --- problem

impl Password {
    fn part1_is_valid(&self) -> bool {
        let n = self.password.chars().filter(|c| c == &self.character).count();
        self.position1 <= n && n <= self.position2
    }

    fn part2_is_valid(&self) -> bool {
        let c1 = self.password.chars().nth(self.position1 - 1) == Some(self.character);
        let c2 = self.password.chars().nth(self.position2 - 1) == Some(self.character);
        (c1 || c2) && !(c1 && c2)
    }
}

fn part1(passwords: &Vec<Password>) -> usize {
    passwords.iter().filter(|p| p.part1_is_valid()).count()
}

fn part2(passwords: &Vec<Password>) -> usize {
    passwords.iter().filter(|p| p.part2_is_valid()).count()
}

fn main() {
    let input = read_file("../input.txt").unwrap();
    let (_, passwords) = parse_input(&input).unwrap();
    println!("part1 {}", part1(&passwords));
    println!("part2 {}", part2(&passwords));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_parse_passwords() {
        let (rest, passwords) = parse_input("1-3 a: abcde\n1-3 b: cdefg\n2-9 c: ccccccccc").unwrap();
        assert_eq!(rest, "");
        assert_eq!(passwords,
            vec![
                Password { position1: 1, position2: 3, character: 'a', password: String::from("abcde") },
                Password { position1: 1, position2: 3, character: 'b', password: String::from("cdefg") },
                Password { position1: 2, position2: 9, character: 'c', password: String::from("ccccccccc") }
            ]
        );
    }

    #[test]
    fn test_part1_is_valid_1() {
        let p = Password { position1: 1, position2: 3, character: 'a', password: String::from("abcde") };
        assert_eq!(p.part1_is_valid(), true);
    }

    #[test]
    fn test_part1_is_valid_2() {
        let p = Password { position1: 1, position2: 3, character: 'b', password: String::from("cdefg") };
        assert_eq!(p.part1_is_valid(), false);
    }

    #[test]
    fn test_part1_is_valid_3() {
        let p = Password { position1: 2, position2: 9, character: 'c', password: String::from("ccccccccc") };
        assert_eq!(p.part1_is_valid(), true);
    }

    #[test]
    fn test_part2_is_valid_1() {
        let p = Password { position1: 1, position2: 3, character: 'a', password: String::from("abcde") };
        assert_eq!(p.part2_is_valid(), true);
    }

    #[test]
    fn test_part2_is_valid_2() {
        let p = Password { position1: 1, position2: 3, character: 'b', password: String::from("cdefg") };
        assert_eq!(p.part2_is_valid(), false);
    }

    #[test]
    fn test_part2_is_valid_3() {
        let p = Password { position1: 2, position2: 9, character: 'c', password: String::from("ccccccccc") };
        assert_eq!(p.part2_is_valid(), false);
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
clothierdroid profile image
David Clothier • Edited

SQL (0 lines of code huehue)

Get this table naming 'day2'

table

2.1. Solution

SELECT COUNT(*) FROM 
(
SELECT
   letra
 , pass
 , nmin
 , nmax
 ,(LENGTH(pass) - LENGTH(REPLACE(pass, letra, ''))) AS times
FROM
   day2
HAVING
   times BETWEEN nmin AND nmax
) puzzle_answer
Enter fullscreen mode Exit fullscreen mode

2.2. Solution

SELECT COUNT(*) 
FROM   day2 
WHERE  LOCATE(letra, pass, nmin) = nmin
       XOR LOCATE(letra, pass, nmax) = nmax 
Enter fullscreen mode Exit fullscreen mode
Collapse
 
benwtrent profile image
Benjamin Trent • Edited

My Rust solution for Day 2. Also using an XOR :). Great minds think alike.

#[derive(Debug, Eq, PartialEq)]
pub struct PasswordPolicy {
    character: char,
    min: usize,
    max: usize,
} 

impl From<&String> for PasswordPolicy {
    fn from(s: &String) -> Self {
        let spaces:Vec<&str> = s.split(" ").collect();
        let character:char = spaces[1].chars().next().unwrap();
        let vec:Vec<usize> = spaces[0].split("-").map(|i| i.parse().unwrap()).collect();
        PasswordPolicy {
            character,
            min: vec[0],
            max: vec[1]
        }
    }
}


impl PasswordPolicy {

    pub fn satisfied_1(&self, password: &str) -> bool {
        let ct = password.chars().filter(|c| *c == self.character).count();
        (self.min - 1) < ct && ct < (self.max + 1)
    }

    pub fn satisfied_2(&self, password: &str) -> bool {
        let mut ans = false;
        for (i, c) in password.chars().enumerate() {
            if (i + 1) == self.min  || (i + 1) == self.max {
                ans ^= self.character == c;
            }
        }
        ans
    }
}

#[aoc_generator(day2)]
fn input_to_vec(input: &str) -> Vec<(PasswordPolicy, String)> {
    input.lines().map(|i| {
        let splt = i.split(": ").map(|s| String::from(s)).collect::<Vec<String>>();
        (PasswordPolicy::from(&splt[0]), splt[1].to_string())
    }).collect()
}

#[aoc(day2, part1)]
fn valid_password_count(input: &Vec<(PasswordPolicy, String)>) -> usize {
    input.iter().filter(|(policy, password)| policy.satisfied_1(password.as_str())).count()
}

#[aoc(day2, part2)]
fn valid_password_count2(input: &Vec<(PasswordPolicy, String)>) -> usize {
    input.iter().filter(|(policy, password)| policy.satisfied_2(password.as_str())).count()
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
pihentagy profile image
pihentagy • Edited

Short and hopefully non-cryptic python. Ideas to improve?

def explode(line):
    policy, password = line.split(': ',1)
    nums, letter = policy.split()
    a, b = map(int, nums.split('-'))
    return a,b , letter, password

def compliant(line):
    min, max, letter, password = explode(line)
    return min <= password.count(letter) <= max

def compliant2(line):
    p1, p2, letter, password = explode(line)
    return (password[p1-1] == letter) != (password[p2-1] == letter)

print(sum(1 for _ in filter(compliant, open('input2'))))
print(sum(1 for _ in filter(compliant2, open('input2'))))
Enter fullscreen mode Exit fullscreen mode