DEV Community

Christopher Nilsson
Christopher Nilsson

Posted on • Edited on

Advent of Code: 2020 Day 04

#adventofcode #python

SPOILER ALERT
This is a post with my solutions and learnings from the puzzle. Don't continue
reading if you haven't tried the puzzle on your own yet.

If you want to do the puzzle, visit adventofcode.com/2020/day/4.

My programming language of choice is python and all examples below are in python.

Key learnings

  • Debugging and testing

Todays puzzle has a number of specific requirements to follow. The key learning I took away from it too handle edge cases, follow specification and having a systematic way of debugging. A good practice would to create tests for the edge cases to ensure everything works as expected.

Puzzle

The challenge is to validate data for a thousand passport.

Example input for two passports:

ecl:gry pid:860033327 eyr:2020 hcl:#fffffd
byr:1937 iyr:2017 cid:147 hgt:183cm

iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884
hcl:#cfa07d byr:1929
Enter fullscreen mode Exit fullscreen mode

They fields are defined as:

  • byr (Birth Year)
  • iyr (Issue Year)
  • eyr (Expiration Year)
  • hgt (Height)
  • hcl (Hair Color)
  • ecl (Eye Color)
  • pid (Passport ID)
  • cid (Country ID)

Part 1

All fields except for Country ID (cid) are mandatory.
Validate that all mandatory fields are present.

Parse input

First step is to save the input in a local file and parse it in python:

# Open the input file
inputfile = open('04.input', 'r')

# Parse lines
data = [x.strip() for x in inputfile.readlines()]
Enter fullscreen mode Exit fullscreen mode

Solution 

def part1(data):
    valid_passport_count = 0
    required_fields = ['byr' ,'iyr' ,'eyr' ,'hgt' ,'hcl' ,'ecl' ,'pid']

    # Variable to track number of required fields for current passport
    current = 0
    for line in data:
        if line == '':                              # Empty line indicates new passport
            if current == len(required_fields):
                valid_passport_count += 1
            current = 0
            continue

        for field in line.split():
            key, val = field.split(':')
            if key in required_fields:
                current += 1

    return valid_passport_count

print "Solution part 1: %d" % part1(data)
Enter fullscreen mode Exit fullscreen mode

Part 2

The second part adds validation for each field. The requirements are:

  • byr (Birth Year) - four digits; at least 1920 and at most 2002.
  • iyr (Issue Year) - four digits; at least 2010 and at most 2020.
  • eyr (Expiration Year) - four digits; at least 2020 and at most 2030.
  • hgt (Height) - a number followed by either cm or in:
    • If cm, the number must be at least 150 and at most 193.
    • If in, the number must be at least 59 and at most 76.
  • hcl (Hair Color) - a # followed by exactly six characters 0-9 or a-f.
  • ecl (Eye Color) - exactly one of: amb blu brn gry grn hzl oth.
  • pid (Passport ID) - a nine-digit number, including leading zeroes.
  • cid (Country ID) - ignored, missing or not.

My Solution

This part will have as many variations of solutions as there are developers. The important part is to read carufully the requirements and test against edge-cases. I did my testing continuously by printing relevant variables while coding. The solution below is therefore not the whole "solution" as I see the process as important as the final code.

def valid(passport):
    # Validate mandatory fields
    fields = ['byr' ,'iyr' ,'eyr' ,'hgt' ,'hcl' ,'ecl' ,'pid']
    for f in fields:
        if(f not in passport):
            return False

    # Validate numerical
    if not ( 1920 <= int(passport['byr']) <= 2002):
        return False
    if not ( 2010 <= int(passport['iyr']) <= 2020):
        return False
    if not ( 2020 <= int(passport['eyr']) <= 2030):
        return False

    # Validate Height
    if 'cm' in passport['hgt'] and not (150 <= int(passport['hgt'][:-2]) <=193):
        return False
    elif 'in' in passport['hgt'] and not (59 <= int(passport['hgt'][:-2]) <= 76):
        return False
    if 'cm' not in passport['hgt'] and 'in' not in passport['hgt']:
        return False

    # Validate strings/enums
    if  passport['ecl'] not in ['amb', 'blu', 'brn','gry','grn','hzl','oth']:
        return False
    if re.match(r'^\#[0-9a-f]{6}$', passport['hcl']) is None:
        return False
    if re.match(r'^\d{9}$', passport['pid']) is None:
        return False

    return True

def part2(data):
    valid_passport_count = 0
    current = {}
    for line in data:
        if line == '':
            if valid(current):
                valid_passport_count += 1
            current = {}
            continue

        for field in line.split():
            field,val = field.split(':')
            current[field] = val
    return valid_passport_count
Enter fullscreen mode Exit fullscreen mode

Comments

One edge-case I missed was the passport-id with 9 digits. I forgot to add start and end notation on the regex. A 10-digit passport-id was valid as it did in fact contain a 9-digit number. This off by one error was hard for me to find. The lesson learned is to test edge-cases.

Though it is not practical in a "competition" environment. Therefore I tested by using print continuously to track what got passed and what didn't.

Thanks for reading!

I hope these solutions were helpful for you. Just ask if anything was hard to grasp.

Complete code can be found at: github.com/cNille/AdventOfCode/blob/master/2020/04.py

Top comments (10)

Collapse
 
neilgall profile image
Neil Gall •

I re-used and extended the parser combinators I wrote for day 2 (see, that investment is paying off already!) but I'm not entirely happy with my solution. My instinct was Parse don't validate but with AoC you never know what's coming in part 2. The bit about cheating the system in the initial description made me think the second part might have to deal with the invalid records in some way. So I kept the PasswordData as a simple HashMap for maximum flexibility. Now I know the full requirements I might come back later and implement a proper parse-don't-validate approach.

use std::collections::HashMap;
use std::fs::File;
use std::io::prelude::*;
use std::ops::RangeInclusive;
use std::str::Chars;

mod parser;
use parser::*;

// --- model

struct PassportData(HashMap<String, String>);

enum Height {
    CM(usize),
    IN(usize)
}

fn parse_height(input: &str) -> ParseResult<Height> {
    let p = or(
        map(seq(integer, string("cm")), |(h, _)| Height::CM(h as usize)),
        map(seq(integer, string("in")), |(h, _)| Height::IN(h as usize))
    );
    p.parse(input)
}

fn height_string_is_valid(s: &str) -> bool {
    if let Ok((_, height)) = parse_height(s) {
        match height {
            Height::CM(h) => (150..=193).contains(&h),
            Height::IN(h) => (59..=76).contains(&h)
        }
    } else {
        false
    }
}

fn has_n_digits(mut chars: Chars, n: usize, radix: u32) -> bool {
    (0..n).all(|_|
        chars.next().map(|c| c.is_digit(radix)).unwrap_or(false)
    ) && chars.next().is_none()
}

fn is_valid_hair_color(s: &str) -> bool {
    let mut chars = s.chars();
    chars.next() == Some('#') && has_n_digits(chars, 6, 16)
}

fn is_valid_eye_color(s: &str) -> bool {
    vec!["amb", "blu", "brn", "gry", "grn", "hzl", "oth"].contains(&s)
}

impl PassportData {
    fn new(data: Vec<(String,String)>) -> Self {
        PassportData(data.iter().cloned().collect())
    }

    fn contains_required_fields(&self) -> bool {
        vec!["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"]
            .into_iter()
            .all(|key| self.0.contains_key(key))
    }

    fn all_fields_are_valid(&self) -> bool {
        self.birth_year_is_valid()
        && self.issue_year_is_valid()
        && self.expiration_year_is_valid()
        && self.height_is_valid()
        && self.hair_color_is_valid()
        && self.eye_color_is_valid()
        && self.passport_id_is_valid()
    }

    fn year_is_valid(&self, key: &str, valid_range: RangeInclusive<usize>) -> bool {
        if let Some(s) = self.0.get(key) {
            if let Ok(byr) = s.parse::<usize>() {
                return valid_range.contains(&byr)
            }
        }
        false
    }

    fn birth_year_is_valid(&self) -> bool {
        self.year_is_valid("byr", 1920..=2002)
    }

    fn issue_year_is_valid(&self) -> bool {
        self.year_is_valid("iyr", 2010..=2020)
    }

    fn expiration_year_is_valid(&self) -> bool {
        self.year_is_valid("eyr", 2020..=2030)
    }

    fn height_is_valid(&self) -> bool {
        if let Some(s) = self.0.get("hgt") {
            height_string_is_valid(s)
        } else {
            false
        }
    }

    fn hair_color_is_valid(&self) -> bool {
        if let Some(s) = self.0.get("hcl") {
            is_valid_hair_color(s)
        } else {
            false
        }
    }

    fn eye_color_is_valid(&self) -> bool {
        if let Some(s) = self.0.get("ecl") {
            is_valid_eye_color(s)
        } else {
            false
        }
    }

    fn passport_id_is_valid(&self) -> bool {
        if let Some(s) = self.0.get("pid") {
            has_n_digits(s.chars(), 9, 10)
        } else {
            false
        }
    }
}

// --- 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) -> Vec<PassportData> {
    let tag = map(one_or_more(letter), |ls| ls.iter().collect());
    let value = map(one_or_more(non_whitespace), |cs| cs.iter().collect());
    let item = between(tag, string(":"), value);
    let passport = map(one_or_more(first(item, whitespace)), PassportData::new);

    input.split("\n\n")
        .map(|inp| passport.parse(inp).unwrap().1)
        .collect()
}


// --- problems

fn part1(data: &Vec<PassportData>) -> usize {
    data.iter().filter(|p| p.contains_required_fields()).count()
}

fn part2(data: &Vec<PassportData>) -> usize {
    data.iter().filter(|p| p.all_fields_are_valid()).count()
}

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

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

    fn sample_input() -> &'static str {
"ecl:gry pid:860033327 eyr:2020 hcl:#fffffd
byr:1937 iyr:2017 cid:147 hgt:183cm

iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884
hcl:#cfa07d byr:1929

hcl:#ae17e1 iyr:2013
eyr:2024
ecl:brn pid:760753108 byr:1931
hgt:179cm

hcl:#cfa07d eyr:2025 pid:166559648
iyr:2011 ecl:brn hgt:59in"
    }

    #[test]
    fn test_parse_input() {
        let data = parse_input(sample_input());
        assert_eq!(data.len(), 4);

        vec![
            ("ecl", "gry"),
            ("pid", "860033327"),
            ("eyr", "2020"),
            ("hcl", "#fffffd"),
            ("byr", "1937"),
            ("iyr", "2017"),
            ("cid", "147"),
            ("hgt", "183cm")
        ].into_iter().for_each(|(k,v)| {
            assert_eq!(data[0].0.get(k), Some(&String::from(v)));
        });
    }

    #[test]
    fn test_has_required_fields() {
        let data = parse_input(sample_input());
        assert_eq!(data[0].contains_required_fields(), true);
        assert_eq!(data[1].contains_required_fields(), false);
        assert_eq!(data[2].contains_required_fields(), true);
        assert_eq!(data[3].contains_required_fields(), false);
    }

    #[test]
    fn test_invalid_passports() {
        let data = parse_input("eyr:1972 cid:100
hcl:#18171d ecl:amb hgt:170 pid:186cm iyr:2018 byr:1926

iyr:2019
hcl:#602927 eyr:1967 hgt:170cm
ecl:grn pid:012533040 byr:1946

hcl:dab227 iyr:2012
ecl:brn hgt:182cm pid:021572410 eyr:2020 byr:1992 cid:277

hgt:59cm ecl:zzz
eyr:2038 hcl:74454a iyr:2023
pid:3556412378 byr:2007");

        data.iter().for_each(|p| {
            assert_eq!(p.all_fields_are_valid(), false)
        });
    }

    #[test]
    fn test_valid_passports() {
        let data = parse_input("pid:087499704 hgt:74in ecl:grn iyr:2012 eyr:2030 byr:1980
hcl:#623a2f

eyr:2029 ecl:blu cid:129 byr:1989
iyr:2014 pid:896056539 hcl:#a97842 hgt:165cm

hcl:#888785
hgt:164cm byr:2001 iyr:2015 cid:88
pid:545766238 ecl:hzl
eyr:2022

iyr:2010 hgt:158cm hcl:#b6652a ecl:blu byr:1944 eyr:2021 pid:093154719");

        data.iter().for_each(|p| {
            assert_eq!(p.all_fields_are_valid(), true)
        });
    }

    #[test]
    fn test_height_validation() {
        assert_eq!(height_string_is_valid("60in"), true);
        assert_eq!(height_string_is_valid("190cm"), true);
        assert_eq!(height_string_is_valid("190in"), false);
        assert_eq!(height_string_is_valid("190"), false);
    }

    #[test]
    fn test_hair_color_validation() {
        assert_eq!(is_valid_hair_color("#123abc"), true);
        assert_eq!(is_valid_hair_color("#123abz"), false);
        assert_eq!(is_valid_hair_color("#123"), false);
        assert_eq!(is_valid_hair_color("123abc"), false);
        assert_eq!(is_valid_hair_color("#123abcd"), false);
    }

    #[test]
    fn test_eye_color_validation() {
        assert_eq!(is_valid_eye_color("brn"), true);
        assert_eq!(is_valid_eye_color("wat"), false);
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
cnille profile image
Christopher Nilsson •

I'm guessing this is rust? I'm impressed by your structure! It's clear to understand the code and nice that you have tests! Hopefully I'll learn to add more tests as well some day 🙏 haha

Collapse
 
neilgall profile image
Neil Gall •

Thanks. Yes, it's Rust. I like to approach these problems as if I was producing production code. That's the only type worth practicing, right? :-)

Collapse
 
sergiogragera profile image
Sergio Gragera • • Edited

Only with regex

import re


def is_valid(credentials):
    regex = {
        'byr': r'^(19[2-9][0-9]|200[0-2])$',
        'iyr': r'^(201[0-9]|2020)$',
        'eyr': r'^(202[0-9]|2030)$',
        'hgt': r'^((1[5-8][0-9]|19[0-3])cm|(59|6[0-9]|7[0-6])in)$',
        'hcl': r'^#[0-9a-f]{6}$',
        'ecl': r'^(amb|blu|brn|gry|grn|hzl|oth)$',
        'pid': r'^\d{9}$'}
    if regex.keys() <= credentials.keys():
        for key in credentials:
            if key != 'cid':
                comp = re.compile(regex[key])
                if not comp.match(credentials[key]):
                    return False
        return True
    return False


def part2(file):
    valid_credentials = 0
    credentials = {}
    for line in file:
        line_withou_break = line.replace('\n', '')
        if len(line_withou_break) > 0:
            pairs = line_withou_break.split(' ')
            for pair in pairs:
                key, value = pair.split(':')
                credentials[key] = value
        else:
            valid_credentials += 1 if is_valid(credentials) else 0
            credentials = {}
    return valid_credentials
Enter fullscreen mode Exit fullscreen mode
Collapse
 
cnille profile image
Christopher Nilsson •

Really clean solution! Thanks for sharing! 🦄

Collapse
 
gubesch profile image
Christian Gubesch •

Hello Christopher,
I just wanted to let you know that in your section with validate height you would run into some edge cases with the last if statement.

For example for my quiz input this solution wouldn't work.

You should consider the if elif and append an else at the end to catch all remaining cases.

    # Validate Height
    if 'cm' in passport['hgt']:
            return False
    elif 'in' in passport['hgt']:
            return False
    else:
            return False
Enter fullscreen mode Exit fullscreen mode

If you want to highlight your python code here on dev.to just write python after the three backticks ;)

Cheers,
Christian

Collapse
 
cnille profile image
Christopher Nilsson •

Thanks for the tip on highlighting! :D

An else wouldn't let the flow through to validate the Validate strings/enums, so would have to reorder the code then. Could you share what the case is in your input that I don't catch? :)

Collapse
 
gubesch profile image
Christian Gubesch •

Hello Christopher,
I can only tell that your solution is off by 1 compared to mine at my input file.

I use this code right here:

def isValidPuzzle2(self):
        attributes = vars(self)
        if len(attributes) == 8 or (len(attributes) == 7 and "cid" not in attributes):
            if not (1920 <= int(self.byr) <= 2002):
                return False
            if not (2010 <= int(self.iyr) <= 2020):
                return False
            if not (2020 <= int(self.eyr) <= 2030):
                return False
            if "cm" in self.hgt:
                if not 150 <= int(self.hgt[:-2]) <= 193:
                    return False
            elif "in" in self.hgt:
                if not 59 <= int(self.hgt[0:-2]) <= 76:
                    return False
            else:
                return False
            patternHairColor = re.compile("^#[a-f0-9]{6}$")
            if not patternHairColor.match(self.hcl):
                return False
            eyeColors = ["amb","blu","brn","gry","grn","hzl","oth"]
            if self.ecl not in eyeColors:
                return False
            patternPid = re.compile("^\d{9}$")
            if not patternPid.match(self.pid):
                return False
            return True
        else:
            return False
Enter fullscreen mode Exit fullscreen mode

My console output:

PS C:\Users\christian.gubesch\Documents\DEV\AdventOfCode\Python\Day4> python.exe .\day4_devto.py
Solution part 1: 241
Solution part 2: 185
PS C:\Users\christian.gubesch\Documents\DEV\AdventOfCode\Python\Day4> python.exe .\day4.py      
Puzzle 1: 242
Puzzle 2: 186
Enter fullscreen mode Exit fullscreen mode

Maybe I have time tomorrow to find the specific case for you.

Cheers ;)

Collapse
 
limjinsun profile image
Jin Lim • • Edited

If anyone interested in Ruby solutions, here is my 2 cents. I like the simplicity of Ruby.

file = File.open('puzzle_input.txt')
data = file.readlines

arr = []
result = []

data.each_with_index { |line, index|
  arr << line.strip

  if line.length == 1 
    result << arr.join(' ').strip
    arr.clear
  end

  if index == data.size - 1
    result << arr.join(' ').strip
    arr.clear
  end
}

result_hash = result.map{ |data| 
  data.split(' ').each_with_object({}){ |item, hash| 
    content = item.split(':')
    hash[content.first] = content.last
  }
}

valid_count = 0

def valid?(hash)
  hash.key?('hcl') && hash.key?('hgt') && hash.key?('pid') && hash.key?('byr') && hash.key?('eyr') && hash.key?('iyr') && hash.key?('ecl')
end

def check_values(hash)
  return false unless hash['byr'].to_i >= 1920 && hash['byr'].to_i <= 2002
  return false unless hash['iyr'].to_i >= 2010 && hash['iyr'].to_i <= 2020
  return false unless hash['eyr'].to_i >= 2020 && hash['eyr'].to_i <= 2030

  if hash['hgt'].match(/\d+in$/).nil? && hash['hgt'].match(/\d+cm$/).nil?
   return false
  else
    if !hash['hgt'].match(/\d+in$/).nil? 
      return false unless hash['hgt'].match(/\d+/).to_s.to_i >= 59 && hash['hgt'].match(/\d+/).to_s.to_i <= 76
    elsif !hash['hgt'].match(/\d+cm$/).nil? 
      return false unless hash['hgt'].match(/\d+/).to_s.to_i >= 150 && hash['hgt'].match(/\d+/).to_s.to_i <= 193
    end
  end

  return false unless hash['hcl'] == hash['hcl'].match(/#[\d|a-f]+/).to_s
  return false unless %w[amb blu brn gry grn hzl oth].any? { |e| e == hash['ecl'] }
  return false unless hash['pid'] == hash['pid'].match(/\d{9}/).to_s

  return true
end

result_hash.each { |hash| 
  if valid?(hash)
    if check_values(hash)
      valid_count += 1
    end
  end
}

puts valid_count

file.close
Enter fullscreen mode Exit fullscreen mode
Collapse
 
andrewharpin profile image
Andrew Harpin •

There's a flaw in your part 1, it assumes the last entry is invalid.

There is no new line at the EOF, so the last entry is not evaluated by your code.

Read next

dazevedo profile image

Implementing a Perceptron from Scratch in Python

Daniel Azevedo -

qianl15 profile image

How to build a crashproof customer service agent in <80 lines with Swarm 💪🐝

Qian Li -

sopralapanca profile image

A Guide to Unsupervised Image Segmentation using Normalized Cuts (NCut) in Python

Giacomo -

scofieldidehen profile image

Build a Secure Python Password Generator Using Secret Lib

Scofield Idehen -