Advent of Code 2020 Solution Megathread - Day 4: Passport Processing

Day 4! I was worried as I was reading the first problem yesterday that I would have to optimize for any rational slope. I'm thankful he decided to take it easier than that for Day 3.

The Puzzle

In today’s puzzle, we're just trying to get through airport security, which is jam-packed because, obviously, Santa's magic keeps the North Pole COVID-free. It's classified as a hum-bug. 🥁 Anyways. The passport scanner is broken and we're doing a good deed by "fixing" it. And by "fixing," we mean "hacking it to let us through but also mostly fixing it."

Y'all. We are THIS close to validating YAML and I am here for it.

The Leaderboards

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

Ryan's Leaderboard: 224198-25048a19

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:06PM 12/12/2020 PST.

Language	Count
Python	8
JavaScript	3
Rust	2
Haskell	2
C#	1
Raku	1
COBOL	1
PHP	1
Ruby	1
Elixir	1
Go	1
C	1

Merry Coding!

Comments

[Erik Bäckman]

Still not doing these the day the come out but here's my Haskell solution.
Problems like these seem like work to me :P

{-# LANGUAGE LambdaCase #-}
module Day4 where

import Text.Parsec
import Text.Parsec.String
import Control.Monad (guard)
import Data.Maybe (mapMaybe, isJust)
import Data.List.Split hiding (sepBy, endBy, oneOf)
import qualified Data.Map as M
import Data.Map (Map)
import Data.List ((\\))
import Text.Read (readMaybe)
import Data.Char
import Data.Semigroup (All(All), getAll)

hush :: Either e a -> Maybe a
hush (Left _)  = Nothing
hush (Right a) = Just a

parse' :: Parser a -> String -> Maybe a
parse' p = hush . parse p ""

-- Part 1
parsePassport :: String -> Either ParseError (Map String String)
parsePassport = fmap M.fromList . parse' (kvp `sepEndBy` space)
  where
    kvp = (,) <$> manyTill anyChar (char ':')
              <*> many (noneOf "\n ")

hasRequiredFields :: Map String String -> Bool
hasRequiredFields m =  null $ ["byr", "ecl", "eyr", "hcl", "hgt", "iyr", "pid"] \\ M.keys m

validatePassports :: (Map String String -> Bool) -> String -> [Map String String]
validatePassports v = filter v . mapMaybe (hush . parsePassport) . splitOn "\n\n"

solveP1 :: String -> Int
solveP1 = length . validatePassports hasRequiredFields

-- Part 2
type Validation a = (a -> Maybe a)

within :: (Int, Int) -> Int -> Bool
within (min, max) i = i >= min && i <= max

year :: String -> Maybe Int
year s = parse' (4 `times` digit) s >>= readMaybe

yearBetween :: (Int, Int) -> String -> Maybe String
yearBetween r s = year s >>= \n -> guard (within r n) >> pure s

byr :: Validation String
byr = yearBetween (1929, 2020)

iyr :: Validation String
iyr = yearBetween (2010, 2020)

eyr :: Validation String
eyr = yearBetween (2020, 2030)

hgt :: Validation String
hgt = parse' (mappend <$> many1 digit <*> (try (string "cm") <|> try (string "in")))

hcl :: Validation String
hcl = parse' (mappend <$> string "#" <*> 6 `times` anyChar)

ecl :: Validation String
ecl s | s == "amb" = Just s
      | s == "blu" = Just s
      | s == "brn" = Just s
      | s == "gry" = Just s
      | s == "grn" = Just s
      | s == "hzl" = Just s
      | s == "oth" = Just s
      | otherwise  = Nothing

pid :: Validation String
pid s = guard (length s == 9 && isNumber s) >> pure s
  where isNumber = getAll . foldMap (All . isDigit)

validateFields :: Map String String -> Maybe (Map String String)
validateFields = M.traverseWithKey validateAtKey
  where
    validateAtKey = \case "byr" -> byr
                          "iyr" -> iyr
                          "eyr" -> eyr
                          "hgt" -> hgt
                          "hcl" -> hcl
                          "ecl" -> ecl
                          _     -> Just

solveP2 :: String -> Int
solveP2 = length . validatePassports (\x -> hasRequiredFields x &&
                                            isJust (validateFields x))

[Thibaut Patel]

My JavaScript walkthrough:

[readyready15728]

Ruby, part 2:

passports = File.read('04.txt').split /\n\n/

passports = passports.map do |passport|
  fields = passport.split(/\n/).join(' ').split ' '
  passport_hash = fields.map { |field| field.split ':' }.to_h
end

valid_count = 0

def all_required_fields?(passport)
  required_fields = ['byr', 'iyr', 'eyr', 'hgt', 'hcl', 'ecl', 'pid']
  required_count = 0

  required_fields.each do |field|
    required_count += 1 if passport.include? field
  end

  required_count == required_fields.length
end

def valid_birth_year?(passport)
  birth_year = passport['byr'].to_i
  1920 <= birth_year and birth_year <= 2002
end

def valid_issue_year?(passport)
  issue_year = passport['iyr'].to_i
  2010 <= issue_year and issue_year <= 2020
end

def valid_expiration_year?(passport)
  expiration_year = passport['eyr'].to_i
  2020 <= expiration_year and expiration_year <= 2030
end

def valid_height?(passport)
  match = /(?<number>\d+)(?<units>in|cm)/.match(passport['hgt'])
  return false unless match
  number = match.named_captures['number'].to_i
  units = match.named_captures['units']

  if units == 'in'
    59 <= number and number <= 76
  else
    150 <= number and number <= 193
  end
end

def valid_hair_color?(passport)
  /\A#[0-9a-f]{6}\z/.match passport['hcl']
end

def valid_eye_color?(passport)
  begin
    %q{amb blu brn gry grn hzl oth}.include? passport['ecl']
  rescue
    false
  end
end

def valid_passport_id?(passport)
  /\A[0-9]{9}\z/.match passport['pid']
end

def valid_passport?(passport)
  test_outcomes = [
    all_required_fields?(passport),
    valid_birth_year?(passport),
    valid_issue_year?(passport),
    valid_expiration_year?(passport),
    valid_height?(passport),
    valid_hair_color?(passport),
    valid_eye_color?(passport),
    valid_passport_id?(passport)
  ]

  test_outcomes.all?
end

passports.each do |passport|
  valid_count += 1 if valid_passport? passport
end

puts valid_count

[Mike Gasparelli]

This is a fun little thread. Since there's no C# representation, I figured I would share my solution. I have a little framework code that handles some stuff behind the scenes such as locating and reading the file, as well as validating the solving on the sample data returns the correct solution, so you won't see any of that in the code here:

Part 1

    public class Part1 : Puzzle<IEnumerable<Passport>, int>
    {
        public override int SampleAnswer => 2;

        public override IEnumerable<Passport> ParseInput(string rawInput)
        {
            return rawInput
                .Split(Environment.NewLine + Environment.NewLine)
                .Where(x => x.Length > 0)
                .Select(ParsePassport);
        }

        protected Passport ParsePassport(string chunk)
        {
            var keyValuePairs = chunk
                .Replace(Environment.NewLine, " ")
                .TrimEnd()
                .Split(' ')
                .Select(pair => new KeyValuePair<string, string>(pair[..3], pair[4..]));

            return new Passport(new Dictionary<string, string>(keyValuePairs));
        }

        public override int Solve(IEnumerable<Passport> input)
            => input.Count(p => p.IsValid());
    }

Part 2

    public class Part2 : Part1
    {
        public override int SampleAnswer => 2;

        public override IEnumerable<Passport> ParseInput(string rawInput)
        {
            return rawInput
                .Split(Environment.NewLine + Environment.NewLine)
                .Where(x => x.Length > 0)
                .Select(ParsePassport);
        }

        public override int Solve(IEnumerable<Passport> input)
            => input.Count(p => p.IsStrictValid());
    }

Passport

public class Passport
    {
        HashSet<string> mandatory = new() { "byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid" };
        string[] eyeColors = { "amb", "blu", "brn", "gry", "grn", "hzl", "oth" };
        Dictionary<string, string> fields = new();

        public Passport(Dictionary<string, string> fields)
        {
            this.fields = fields;
        }

        public bool IsValid()
            => mandatory.All(x => fields.ContainsKey(x));

        public bool IsStrictValid()
            => IsValid() && fields.All(f => IsFieldValid(f.Key, f.Value));

        bool IsFieldValid(string key, string value)
            => key switch
            {
                "byr" => IsYearValid(value, 1920, 2002),
                "iyr" => IsYearValid(value, 2010, 2020),
                "eyr" => IsYearValid(value, 2020, 2030),
                "hgt" => IsHeightValid(value),
                "hcl" => IsHairColorValid(value),
                "ecl" => IsEyeColorValid(value),
                "pid" => IsPidValid(value),
                _ => true
            };

        private bool IsPidValid(string value)
            => value.Length == 9
                && long.TryParse(value, out _);

        private bool IsEyeColorValid(string value)
            => eyeColors.Contains(value);

        private bool IsHairColorValid(string value)
            => value[0] == '#'
                && value.Length == 7
                && value
                    .ToLower()
                    .Skip(1)
                    .All(c => c >= '0' && c <= '9' || c>= 'a' && c <= 'z');

        private bool IsHeightValid(string value)
            => int.TryParse(value[..^2], out int iValue)
                && value[^2..] == "cm"
                    ? iValue >= 150 && iValue <= 193
                    : iValue >= 59 && iValue <= 76;

        bool IsYearValid(string value, int min, int max)
            => int.TryParse(value, out int iValue)
                && iValue >= min && iValue <= max;
    }

[Stefan Linke]

Warning this might be offensive to some :D
My Saturday was too long, so I created a code-golfed PHP version (for both parts)

<?$r=['byr):((19[2-9]\d|200[0-2]','iyr):((201\d|2020','eyr):((202\d|2030','hgt):(((?:1[5-8]\d|19[0-3])cm|(?:59|6\d|7[0-6])in','hcl):((#[\da-f]{6}','ecl):((amb|blu|brn|gry|grn|hzl|oth','pid):((\d{9}'];foreach(explode("

",file_get_contents('input'))as$p){$s=$t=1;for($i=0;$i<7;)if(!preg_match("/(?:^|\s)({$r[$i++]})(\s|$))?/",$p,$m))$s=$t=0;elseif(!($m[2]??0))$t=0;$x+=$s;$y+=$t;}echo"$x $y";

[Phantz]

would anyone be interested in a solution written entirely in C, without regex or hashtables

static char const* formats[] = {
    " byr:19%*2[0-9]%n", " byr:200%*1[0-2]%n",
    " iyr:201%*1[0-9]%n", " iyr:2020%n",
    " eyr:202%*1[0-9]%n", " eyr:2030%n",
    " hgt:1%*1[5-8]%*1[0-9]cm%n", " hgt:19%*1[0-3]cm%n",
        " hgt:59in%n", " hgt:6%*1[0-9]in%n", " hgt:7%*1[0-6]in%n",
    " hcl:#%*x%n",
    " ecl:amb%n", " ecl:blu%n", " ecl:brn%n", " ecl:gr%*1[yn]%n", " ecl:hzl%n", " ecl:oth%n",
    " pid:%*9[0-9]%n",
    " cid:%*s%n"
};

static bool is_valid(char const* s)
{
    size_t count = 0;
    for (int n = 0, prevn = -1; n != prevn && s[n] != '\0';)
    {
        prevn = n;
        for (size_t i = 0; i < sizeof formats / sizeof * formats; i++)
        {
            int _n = 0;
            sscanf(s + n, formats[i], &_n);
            if (_n != 0)
            {
                n += _n;
                count += 1;
                formats[i] = "";
                break;
            }
        }
    }
    return count >= 7;
}

The input s to is_valid should be a full passport string (what you get after splitting by double new lines). It does parsing + validation at once and eagerly exits if any field validation fails.

Yes, I know - very cursed. 'twas just for fun, and to prove a point ;)

[Stefan Linke]

Go again, a bit hacky with the very last element

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "regexp"
    "strconv"
    "strings"
)

var requiredAttributes = []string{"byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"}

func isValid(passport map[string]string) bool {
    for _, attribute := range requiredAttributes {
        if _, exists := passport[attribute]; !exists {
            return false
        }
    }

    return true
}

func exists(slice []string, val string) bool {
    for _, item := range slice {
        if item == val {
            return true
        }
    }
    return false
}

func validateRange(val string, lower, upper int) bool {
    num, err := strconv.Atoi(val)
    return err == nil && num >= lower && num <= upper
}

func isValidV2(passport map[string]string) bool {
    for attr, val := range passport {
        switch attr {
        case "byr":
            if !validateRange(val, 1920, 2002) {
                return false
            }
        case "iyr":
            if !validateRange(val, 2010, 2020) {
                return false
            }
        case "eyr":
            if !validateRange(val, 2020, 2030) {
                return false
            }

        case "hgt":
            if strings.HasSuffix(val, "cm") {
                if !validateRange(strings.TrimSuffix(val, "cm"), 150, 193) {
                    return false
                }
            } else if strings.HasSuffix(val, "in") {
                if !validateRange(strings.TrimSuffix(val, "in"), 59, 76) {
                    return false
                }
            } else {
                return false
            }

        case "hcl":
            if match, _ := regexp.MatchString("^#[0-9a-f]{6}$", val); !match {
                return false
            }

        case "ecl":
            eyeColors := []string{"amb", "blu", "brn", "gry", "grn", "hzl", "oth"}
            if !exists(eyeColors, val) {
                return false
            }

        case "pid":
            if match, _ := regexp.MatchString("^[0-9]{9}$", val); !match {
                return false
            }
        }
    }

    return true
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    passport := make(map[string]string, 8)

    numValid, numValidV2 := 0, 0
    for {
        var line string
        line, err := reader.ReadString('\n')
        if err == io.EOF {
            break
        }

        line = strings.TrimSpace(line)

        if len(line) == 0 {
            // passport complete
            if isValid(passport) {
                numValid++
                if isValidV2(passport) {
                    numValidV2++
                }
            }
            // reset passport
            passport = make(map[string]string, 8)
        } else {
            parts := strings.Split(line, " ")
            for _, part := range parts {
                attribute := strings.Split(part, ":")
                passport[attribute[0]] = attribute[1]
            }
        }
    }

    // last one is special snowflake, as file does not end with 2 newlines
    if isValid(passport) {
        numValid++
        if isValidV2(passport) {
            numValidV2++
        }
    }

    fmt.Println(numValid, numValidV2)
}

[Mustafa Haddara]

Reading all of these solutions, I'm glad I opted to avoid regexes in my answers! There are some messy hacks here ("1234567890abcdef".indexOf(c) stands out) and the types should probably all have been string? instead of string, which would have made this a little more concise, but I'm still pretty happy with how it turned out.

I am annoyed they decided to put multiple K:V pairs on the same line because it made the parsing a little messier but oh well.

import { SolveFunc } from './types';

export const solve: SolveFunc = (lines: string[]) => {
  const passports: Passport[] = parse_passports(lines);
  return passports.filter((p) => is_valid(p)).length.toString();
};

type Passport = {
  byr: string;
  iyr: string;
  eyr: string;
  hgt: string;
  hcl: string;
  ecl: string;
  pid: string;
  cid: string;
};

const parse_passports = (lines: string[]): Passport[] => {
  let p: Passport = make_blank_passport();
  const result = [p];
  for (let i = 0; i < lines.length; i++) {
    const line = lines[i];
    if (line.trim() === '') {
      p = make_blank_passport();
      result.push(p);
    }
    line.split(' ').map((chunk) => {
      const [k, v] = chunk.split(':');
      p[k] = v;
    });
  }
  return result;
};

const make_blank_passport = (): Passport => {
  return {
    byr: null,
    iyr: null,
    eyr: null,
    hgt: null,
    hcl: null,
    ecl: null,
    pid: null,
    cid: null,
  };
};

const is_valid = (p: Passport): boolean => {
  return (
    check_int(p.byr, 1920, 2002) &&
    check_int(p.iyr, 2010, 2020) &&
    check_int(p.eyr, 2020, 2030) &&
    check_height(p.hgt) &&
    check_hair_color(p.hcl) &&
    check_eye_color(p.ecl) &&
    check_passport_id(p.pid)
  );
};

const check_int = (strval, min, max) => {
  if (!strval) return false;
  const val = parseInt(strval);
  return min <= val && val <= max;
};

const check_height = (strval) => {
  if (!strval) return false;
  if (strval.endsWith('cm')) {
    const [h] = strval.split('cm');
    return check_int(h, 150, 193);
  } else if (strval.endsWith('in')) {
    const [h] = strval.split('in');
    return check_int(h, 59, 76);
  }
  return false;
};

const check_hair_color = (strval) => {
  if (!strval) return false;
  if (strval.startsWith('#') && strval.length === 7) {
    return strval.split('').filter((c) => '1234567890abcdef'.indexOf(c) < 0).length === 1;
  }
  return false;
};

const check_eye_color = (strval) => {
  if (!strval) return false;
  const accepted = ['amb', 'blu', 'brn', 'gry', 'grn', 'hzl', 'oth'];
  return accepted.indexOf(strval) >= 0;
};

const check_passport_id = (strval) => {
  if (!strval) return false;
  if (strval.length !== 9) return false;
  strval.split('').map((c) => parseInt(c));
  return true;
};

[Seth Etter]

Feels like it could have been cleaner, my first round was worse though! I refactored to use Result and the ? error propagation operator, which was fun.

use regex::Regex;
use anyhow::{anyhow, Result};

#[derive(Clone)]
struct Passport {
    byr: Option<String>,
    iyr: Option<String>,
    eyr: Option<String>,
    hgt: Option<String>,
    hcl: Option<String>,
    ecl: Option<String>,
    pid: Option<String>,
    cid: Option<String>,
}

impl Default for Passport {
    fn default() -> Self {
        Passport {
            byr: None, iyr: None, eyr: None, hgt: None,
            hcl: None, ecl: None, pid: None, cid: None,
        }
    }
}

fn main() {
    let input = std::fs::read_to_string("input.txt").unwrap();

    let passports: Vec<Passport> = input.trim().split("\n\n").map(parse_passport).collect();
    let num_valid = passports.into_iter().filter(|p| {
        // validate_passport(p).is_ok()
        match validate_passport(p) {
            Ok(_) => true,
            Err(e) => { println!("{}", e); false },
        }
    }).count();

    println!("Num Valid: {}", num_valid);
}

fn parse_passport(input: &str) -> Passport {
    let mut p: Passport = Passport::default();
    for entry in input.replace("\n", " ").split(" ") {
        let parts: Vec<&str> = entry.split(":").collect();
        let (label, value) = (parts[0], parts[1]);
        match label {
            "byr" => { p.byr = Some(value.to_owned()) },
            "iyr" => { p.iyr = Some(value.to_owned()) },
            "eyr" => { p.eyr = Some(value.to_owned()) },
            "hgt" => { p.hgt = Some(value.to_owned()) },
            "hcl" => { p.hcl = Some(value.to_owned()) },
            "ecl" => { p.ecl = Some(value.to_owned()) },
            "pid" => { p.pid = Some(value.to_owned()) },
            "cid" => { p.cid = Some(value.to_owned()) },
            _ => {},
        }
    }
    p
}

fn validate_passport(p: &Passport) -> Result<()> {
    check_year_range(p.clone().byr, 1920, 2002)?;
    check_year_range(p.clone().iyr, 2010, 2020)?;
    check_year_range(p.clone().eyr, 2020, 2030)?;
    check_height(p.clone().hgt)?;
    check_regex(p.clone().hcl, "#[0-9A-Fa-f]{6}")?;
    check_regex(p.clone().ecl, "^(amb|blu|brn|gry|grn|hzl|oth)$")?;
    check_regex(p.clone().pid, "^[0-9]{9}$")?;
    Ok(())
}

fn check_year_range(year_str: Option<String>, min: usize, max: usize) -> Result<()> {
    let year = year_str.ok_or(anyhow!("Missing value"))?.parse::<usize>()
        .map_err(|_e| anyhow!("Failed to parse year_str"))?;
    if year < min || year > max {
        return Err(anyhow!("Year out of range"));
    }
    Ok(())
}

fn check_height(height: Option<String>) -> Result<()> {
    let hgt = height.ok_or(anyhow!("Missing hgt"))?;

    let re = Regex::new(r"^([0-9]+)(cm|in)$").unwrap();
    let caps = re.captures(hgt.as_str()).ok_or(anyhow!("Invalid height format"))?;

    let num_str = caps.get(1).unwrap().as_str();
    let unit = caps.get(2).unwrap();

    let num = num_str.parse::<usize>().map_err(|_e| anyhow!("Failed to parse height value"))?;

    match unit.as_str() {
        "in" if num < 59 || num > 76 => { return Err(anyhow!("Height out of range")); },
        "cm" if num < 150 || num > 193 => { return Err(anyhow!("Height out of range")); },
        _ => {},
    }
    Ok(())
}

fn check_regex(field: Option<String>, re_str: &str) -> Result<()> {
    let re = Regex::new(re_str).unwrap();
    let val = field.ok_or(anyhow!("Field missing"))?;
    match re.is_match(val.as_str()) {
        true => Ok(()),
        false => Err(anyhow!(format!("Regex mismatch: {}, {}", re_str, val))),
    }
}

[Yuan Gao]

I went ahead and wrote a solution using PEG in Python (parsimonious library). Aside from the slightly compact PEG grammar, the rest of it is very readable

from parsimonious.grammar import Grammar, NodeVisitor
from parsimonious.exceptions import ParseError, IncompleteParseError, VisitationError

grammar = Grammar(r"""
    EXPR  = ITEM+
    ITEM  = (BYR / IYR / EYR / HGT / HCL / ECL / PID / CID) WHITE?
    WHITE =  ~r"[\s]+"

    BYR   = "byr:" NUMB
    IYR   = "iyr:" NUMB
    EYR   = "eyr:" NUMB
    HGT   = "hgt:" (HGTCM / HGTIN)
    HCL   = "hcl:" ~r"#[0-9a-f]{6}"
    ECL   = "ecl:" ("amb" / "blu" / "brn" / "gry" / "grn" / "hzl" / "oth") 
    PID   = "pid:" ~r"[0-9]{9}"
    CID   = "cid:" ~r"[0-9a-zA-Z]*"

    HGTCM = NUMB "cm"
    HGTIN = NUMB "in"

    NUMB  = ~r"[0-9]{2,4}"
""")

class PassportVisitor(NodeVisitor):
    def visit_EXPR(self, node, visited_children):
        assert not {"BYR", "IYR", "EYR", "HGT", "HCL", "ECL", "PID"}.difference(visited_children)

    def visit_ITEM(self, node, visited_children):
        return node.children[0].children[0].expr_name

    def visit_BYR(self, node, visited_children):
        assert 1920 <= visited_children[1] <= 2002

    def visit_IYR(self, node, visited_children):
        assert 2010 <= visited_children[1] <= 2020

    def visit_EYR(self, node, visited_children):
        assert 2020 <= visited_children[1] <= 2030

    def visit_HGTCM(self, node, visited_children):
        assert 150 <= visited_children[0] <= 193

    def visit_HGTIN(self, node, visited_children):
        assert 59 <= visited_children[0] <= 76

    def visit_NUMB(self, node, visited_children):
        return int(node.text)

    def generic_visit(self, node, visited_children):
        return visited_children or node

pv = PassportVisitor()
pv.grammar = grammar

data = open("input.txt").read().split("\n\n")
valid = 0
for entry in data:
    try:
        pv.parse(entry)
    except (ParseError, VisitationError, IncompleteParseError):
        continue
    else:
        valid += 1
print("Valid:", valid)