Ryan Palo

Posted on Dec 2, 2018

AoC Day 2: Inventory Management System

#adventofcode #discuss

OK, the first day was awesome, I'm super excited about all of the solutions people posted. And I'm learning a lot! We've got a solid 20 people on the DEV leaderboard, which means there are still spots for 180 more -- use code 224198-25048a19 to join!

On to Day 2!

Day 2 of Advent of Code, and I'm pretty sure that Google is tired of me asking it questions every 15 seconds about "How Do I Do X in Rust."

Today's challenge involves an inventory system. Boxes have IDs that are a jumble of letters, and we've got a warehouse full of boxes to check. The first part asks us to analyze the frequency of letters in each ID. The second part gets into Hamming Distances, which are a familiar sight after mentoring on Exercism.

I got both parts working, and even part 2 ran pretty fast, but I'm not algorithmically happy with the double-loop (O(n^2)) runtime. Did anybody come up with anything tricky to do it more efficiently?

I'm going to post my solution in the comments like the rest of the cool kids.

How'd everybody else do?

Top comments (66)

Ali Spittel • Dec 2 '18

Python solutions!

part 1

from collections import Counter

with open('input.txt', 'r') as f:
    twice = 0
    thrice = 0
    for line in f:
        counts = Counter(line).values()
        if 2 in counts:
            twice += 1
        if 3 in counts:
            thrice += 1
    print(twice * thrice)

part 2 -- this one feels clunky to me.

with open('input.txt', 'r') as f:
    boxes = [box.strip() for box in f]

def check_differences(box1, box2):
    difference_idx = -1
    for idx, letter in enumerate(box1):
        if letter != box2[idx]:
            if difference_idx < 0:
                difference_idx = idx
            else:
                return False
    return box1[0:difference_idx] + box1[difference_idx+1:]


def find_one_difference(boxes):
    for idx, box in enumerate(boxes):
        for box2 in boxes[idx+1:]:
            diff = check_differences(box, box2)
            if diff:
                return diff

print(find_one_difference(boxes))

Dane Hillard • Dec 2 '18

My part one ended up looking super similar!

#!/usr/bin/env python

from collections import Counter


if __name__ == '__main__':
    box_ids_with_two_duplicate_letters = 0
    box_ids_with_three_duplicate_letters = 0
    with open('1-input.txt') as box_file:
        for box_id in box_file:
            fingerprint = Counter(box_id)
            if 2 in fingerprint.values():
                box_ids_with_two_duplicate_letters += 1
            if 3 in fingerprint.values():
                box_ids_with_three_duplicate_letters += 1

    print(box_ids_with_two_duplicate_letters * box_ids_with_three_duplicate_letters)

I ended up using zip to help with the comparison if the strings in part 2:

#!/usr/bin/env python

from collections import Counter


def find_similar_box_ids(all_box_ids):
    for box_id_1 in all_box_ids:
        for box_id_2 in all_box_ids:
            # This is kind of a naive Levenshtein distance!
            letter_pairs = zip(box_id_1, box_id_2)
            duplicates = list(filter(lambda pair: pair[0] == pair[1], letter_pairs))
            if len(duplicates) == len(box_id_1) - 1:
                return ''.join(pair[0] for pair in duplicates)


if __name__ == '__main__':
    with open('2-input.txt') as box_file:
        all_box_ids = box_file.read().splitlines()
    print(find_similar_box_ids(all_box_ids))

Ali Spittel • Dec 2 '18

Nice! Definitely think that's the easiest way to do number 1. Zip also makes sense for the second, though not using it allowed me to do the early return!

Dane Hillard • Dec 2 '18

True!

Ryan Palo • Dec 2 '18

10 points for the variable name “thrice!”

Jon Bristow • Dec 2 '18

As a lispy thinker, my brain wants to tell you to make those for loops into comprehensions, but my work brain is telling me that my coworkers would have me drawn and quartered to make your "find-one-difference" a one-liner!

Kudos on how neat this looks. I find python and ruby to be difficult to make look "clean" when I write it.

Ryan Palo • Dec 2 '18

Part 1

You can probably see my Python shining through as I implemented a custom Counter struct to help me out.

use std::collections::HashMap;

// Part 1

/// A histogram of the characters in a string.
struct Counter {
    letters: HashMap<char, usize>,
}

impl Counter {
    pub fn new(word: &str) -> Self {
        let mut letters = HashMap::new();
        for letter in word.chars() {
            let current_reference = letters.entry(letter).or_insert(0);
            *current_reference += 1;
        }
        Self { letters }
    }

    pub fn count_value(&self, number: usize) -> usize {
        self.letters.values().filter(|count| **count == number).count()
    }
}

/// Calculates a checksum for id strings.
/// 
/// The checksum is the number of id's with at least one set of exactly
/// two of a letter times the number of id's with at least one set of
/// exactly three of a letter.  If it has more than one
pub fn checksum(text: &str) -> usize {
    let mut twos = 0;
    let mut threes = 0;
    text.lines()
        .map(|id| Counter::new(id))
        .for_each(|counter| {
            if counter.count_value(2) != 0 {
                twos += 1;
            }
            if counter.count_value(3) != 0 {
                threes += 1;
            }
        });
    twos * threes
}

Part 2

Double for loop boooooooo! But it works and it's fast enough for now. I'm pretty happy with the mileage I got out of Iterators for this part.

// Part 2

/// Finds the letters that are shared between the two prototype fabric
/// box ids.
/// 
/// These ids are the only two that differ from each other by exactly
/// one letter.
pub fn prototype_ids_common_letters(text: &str) -> String {
    let ids: Vec<&str> = text.lines().collect();
    for (i, s1) in ids.iter().enumerate() {
        for s2 in ids.iter().skip(i) {
            if hamming_distance(s1, s2) == 1 {
                return common_letters(s1, s2);
            }
        }
    }
    String::new()
}

/// Calculates the "Hamming Distance" between two strings
/// 
/// Hamming distance is the number of characters who are different
/// between the two strings when the corresponding indices are compared
/// in each string
fn hamming_distance(s1: &str, s2: &str) -> usize {
    s1.chars().zip(s2.chars())
        .filter(|(c1, c2)| c1 != c2)
        .count()
}

/// Returns the letters that are the same (and in the same place)
/// between the two strings
fn common_letters(s1: &str, s2: &str) -> String {
    s1.chars().zip(s2.chars())
        .filter(|(c1, c2)| c1 == c2)
        .map(|(c1, _c2)| c1)
        .collect()
}

Christopher Kruse • Dec 3 '18

This is very well documented and clear, easy-to-read code. This also makes me want to jump into Rust again (I've only hobbied around with it here and there).

Ryan Palo • Dec 3 '18

Thanks! That really encouraging!

Shritesh Bhattarai • Dec 2 '18

I love how you've used enumerate and skip together in your nested for loop. I struggled to find a clean solution like this.

Ryan Palo • Dec 2 '18

Thanks! Yeah, I originally had a very manual nested for-loop set up, but after I got the tests passing, I decided to make an effort to do everything I could with iterators instead :) I've decided that the iterator module in Rust is where most of the magic that I'm missing from Python and Ruby lives.

Shritesh Bhattarai • Dec 2 '18

This was still bothering me, but I found the Itertools crate and the tuple_combinations method. Check out my updated solution in the thread. Itertools makes iterators even more powerful.

Carly Ho 🌈 • Dec 2 '18

PHP

Ended up learning about a bunch of useful array functions like array_values, array_count_values and array_diff_assoc for this one!

Part 1:

$list = file_get_contents($argv[1]);
$boxes = explode("\n", trim($list));
$twos = 0;
$threes = 0;
foreach ($boxes as $box) {
    $letters = str_split($box);
    $values = array_values(array_count_values($letters));
    if (in_array(2, $values)) {
        $twos++;
    }
    if (in_array(3, $values)) {
        $threes++;
    }
}
echo $twos*$threes;
die(1);

Part 2:

<?php
$list = file_get_contents($argv[1]);
$boxes = explode("\n", rtrim($list));
foreach ($boxes as $i=>$box) {
    if ($i != count($boxes)-1) {
        for ($j = $i+1; $j < count($boxes); $j++) {
            $one = str_split($box);
            $two = str_split($boxes[$j]);
            if (count(array_diff_assoc($one, $two)) == 1) {
                echo join("", array_intersect_assoc($one, $two));
                die(1);
            }
        }
    }
}

Ian Kirker • Dec 3 '18

I’m trying to use a broader range of languages than I do usually, so I figured I’d try not to use one I’d already used before through the days. I use bash all the time, so I thought I’d get it out of the way early.

This was not one of my better decisions, but worked fine!

Part 1 uses regular expressions; I could have used an associative array like some other people in the thread, but for some reason I went here first. The sort function wasn’t necessary, but helped with debugging.

#!/bin/bash

twos=0
threes=0

function sort_str () {
    # Bubble Sort ^_^
    local sl="$1"
    changed=1
    while [[ "$changed" -eq 1 ]]; do
        changed=0
        for i in $(seq 1 $(( ${#sl} - 1 ))); do
            if [[ ${sl:$(( i - 1 )):1} > ${sl:$i:1} ]]; then
                echo "${sl:$(( i - 1 )):1} > ${sl:$i:1}" >>sort_progress
                changed=1
                if [[ $i -eq 1 ]]; then
                    sl=${sl:1:1}${sl:0:1}${sl:2}
                else
                    sl=${sl:0:$(( i - 1 ))}${sl:$i:1}${sl:$((i-1)):1}${sl:$i+1}
                fi
            fi
        done
    done
    echo $sl
}

re_2_str=""
re_3_str=""
for a in a b c d e f g h i j k l m n o p q r s t u v w x y z; do
    re_2_str+="^[^$a]*$a[^$a]*$a[^$a]*$|"
    re_3_str+="^[^$a]*$a[^$a]*$a[^$a]*$a[^$a]*$|"
done
re_2_str="(${re_2_str%|})"
re_3_str="(${re_3_str%|})"


while read line
do
    echo -n "$line: $(sort_str $line): "
    if [[ "$line" =~ $re_2_str ]]; then
        twos=$(( twos + 1 ))
        echo -n "2 "
    fi
    if [[ "$line" =~ $re_3_str ]]; then
        threes=$(( threes + 1 ))
        echo -n "3 "
    fi
    echo
done <2.1.input

echo "Twos: $twos"
echo "Threes: $threes"
echo "x: $(( twos * threes ))"

Part 2 uses the same double for loop lamented elsewhere, but it gets the job done.

#!/bin/bash

while read line
do
    while read comp_line
    do
        same_string=""
        ndiffs=0
        for i in $(seq 0 $(( ${#line} - 1 )) )
        do
            if [[ "${line:$i:1}" == "${comp_line:$i:1}" ]]; then
                same_string+=${line:$i:1}
            else
                ndiffs=$(( ndiffs+1 ))
            fi
        done
        if [[ "$ndiffs" -eq 1 ]]; then
            echo "$line: $comp_line: $same_string"
            exit
        fi
    done <2.2.input
done <2.2.input

Neither of these is what I’d call “fast”.

Ryan Palo • Dec 3 '18

Woah, nice! It's always really cool to see bigger things done with Bash :)

P.S. Depending on your Bash version, you can save yourself some typing with {a..z}.

Ian Kirker • Dec 3 '18

Oh yes, good call, I missed that compaction.

Pavel Gurkov • Dec 3 '18 • Edited

Clojure (inefficient part 2)

Part 1:

(->>
    (utils/read-file (str utils/resources-path "day2.txt"))
    (map frequencies)
    (map vals)
    (map (juxt (fn [coll] (some #(= 2 %) coll))
               (fn [coll] (some #(= 3 %) coll))))
    (reduce
      (fn [acc [_2 _3]]
        (-> acc
            (update :2 #(+ (if _2 1 0) %))
            (update :3 #(+ (if _3 1 0) %))))
      {:2 0 :3 0})
    ((fn [coll] (* (:2 coll) (:3 coll)))))

Part 2:

(->>
    (utils/read-file (str utils/resources-path "day2.txt"))
    (map #(map-indexed (fn [idx itm] [idx itm]) %))
    (map set)
    ((fn [coll] (combinatorics/combinations coll 2)))
    (map (fn [[f s]] {:diff (clj-set/difference f s) :orig [f s]}))
    (filter #(= (count (:diff %)) 1))
    ((fn [[{:keys [diff orig]}]]
       (apply str (map second (sort-by first (clj-set/difference (first orig) diff)))))))

Christopher Kruse • Dec 3 '18

I like the threaded use of update here in part 1 - my method used a transient map and returned a persistent copy at the end:

(ns aoc.aoc2)

(defn reduce-twos-threes
  "check the given frequency map n for twos or threes matches, and update
   the memo map to indicate if the string has a match. Used for a reducer."
  [memo n]
  (let [t-memo (transient memo)]
    (if (some (fn [[k v]] (= v 2)) n) 
      (assoc! t-memo :twos (inc (:twos t-memo))))
    (if (some (fn [[k v]] (= v 3)) n) 
      (assoc! t-memo :threes (inc (:threes t-memo))))
    (persistent! t-memo)))

(defn checksum [input]
  (let [sum-maps (map frequencies input)
        twos-threes (reduce reduce-twos-threes {:twos 0 :threes 0} sum-maps)]
    (* (:twos twos-threes) (:threes twos-threes))))

Pavel Gurkov • Dec 3 '18

Nice one. Is definitely faster than mine.

Anderson. J • Dec 3 '18 • Edited

Javascript lazy solution
I don't have much time to solve the challenges :( So I'm just trying to get the stars.

part 1


let twoAppears = 0;
let threeAppears = 0;

for(ID of input) {
  const letters = new Set(ID.split(''));
  let twoAppearing = false;
  let threeAppearing = false;

  for(letter of letters) {
    const length = ID.match(new RegExp(letter, 'g')).length;

    switch (length) {
      case 2:
        if(!twoAppearing) {
          twoAppears++;
          twoAppearing = true;
        }
        break;
      case 3:
      if(!threeAppearing) {
        threeAppears++;
        threeAppearing = true;
      }
      break;
    }
  }
}

console.log(twoAppears * threeAppears);

Part 2


function getCommonLetters(string1, string2) {
  let commonLetters = [];

  for(let i=0; i<string1.length; i++) {
    if(string1[i] === string2[i] && string1[i] !== '\r') {
      commonLetters.push(string1[i]);
    }
  }
  return commonLetters;
}

let mostOcurrencies = [0, 0];
for(let i=0; i<input.length; i+=1) {
  for(let j=i+1; j<input.length; j+=1) {
    commonLetters = getCommonLetters(input[i], input[j]);
    if(commonLetters.length >= 1 && commonLetters.length > mostOcurrencies[0]) {
      mostOcurrencies[0] = commonLetters.length;
      mostOcurrencies[1] = commonLetters;
    }
  }
}

console.log(mostOcurrencies[1].join().replace(/,/g,''))

Linda Thompson • Dec 2 '18 • Edited

Thanks for hosting the private leaderboard! Never been on a leaderboard before lol so that'll be fun. :)

I am curious - how is everyone posting their code? Is there a code tag on here, like there is on Slack? Is everyone sharing screenshots? I haven't posted a whole lot on here yet, so I'm not sure of the best way to share code.

I'm using JS this year, so here's my day 2 solutions: not the prettiest / most succinct, but they work!

Part 1:

let countDouble = 0;
let countTriple = 0;

for (let i = 0; i < input.length; i++) {
    let label = input[i].split('');
    let letterCount = {};

    label.reduce((letters, letter) => {
        if (letter in letterCount) {
            letterCount[letter]++;
        } else {
            letterCount[letter] = 1;
        }
        return letters;
    }, 0);

    let checkCounts = Object.values(letterCount);
    if (checkCounts.includes(2)) {
        countDouble++;
    }
    if (checkCounts.includes(3)) {
        countTriple++;
    }
}

let checksum = countDouble * countTriple;
console.log(checksum);

Part 2:

for (let i = 0; i < input.length; i++) {
    let root = input[i];

    for (let j = i+1; j < input.length; j++) {
        let currName = input[j];

        if (compareNames(root, currName)) {
            return;
        }
    }
}

function compareNames(first, second) {
    let differences = 0;
    let locations = [];
    for (let k = 0; k < first.length; k++) {
        if (first[k] === second[k]) {
            continue;
        } else {
            differences++;
            locations.push(k);
        }
    }

    if (differences === 1) {
        const letterArray = first.split('');
        const removeLetter = letterArray.splice(locations[0], 1);
        const matchingLetters = letterArray.join('');
        console.log(`same letters: ${matchingLetters}`);
        return true;
    } else {
        return false;
    }

    differences = 0;
    locations = [];
}

Neil Gall • Dec 2 '18

There's an enhanced form of markdown for code blocks: triple backticks for start and end, and if you immediately follow the opening backticks with the language you get syntax highlighting. Difficult to show raw markdown in markdown unfortunately.

Linda Thompson • Dec 2 '18

Excellent, thank you! Much better than screenshots. :)

Neil Gall • Dec 2 '18

Enjoyed this one. My Kotlin solution:

package adventofcode2018.day2

import java.io.File

fun repeatCounts(s: String): Set<Int> =
    s.groupBy { it }.values.map { it.size }.toSet()

fun difference(s1: String, s2: String): Int = 
    s1.zip(s2, { x, y -> if (x == y) 0 else 1 }).sum()

fun common(s1: String, s2: String): String =
    s1.zip(s2, { x, y -> if (x == y) x.toString() else "" }).joinToString(separator="")

fun <T> pairs(xs: Collection<T>): List<Pair<T, T>> = when {
    xs.isEmpty() -> listOf() 
    else -> {
        val head = xs.first()
        val tail = xs.drop(1)
        (tail.map { head to it }) + pairs(tail)
    }
}

fun main(args: Array<String>) {
    val file = if (args.isEmpty()) "input.txt" else args[0]
    val input = File(file).readLines().map(String::trim)

    // Part 1
    val counts = input.map(::repeatCounts)
    val numPairs = counts.filter { s -> s.contains(2) }.size
    val numTriples = counts.filter { s -> s.contains(3) }.size
    println("Part 1 checksum: ${numPairs * numTriples}")

    // Part 2
    val differentByOnePairs = pairs(input).filter { (x, y) -> difference(x, y) == 1 }
    println(differentByOnePairs.map { (x, y) -> common(x, y) })
}

Jon Bristow • Dec 2 '18

Were you also annoyed that Kotlin has .groupBy but not .frequencies?

Have you thought about looking into Sequence? You could make your pairs function lazily? Using List means you're materializing the entirety of your double for-loop right away.

Neil Gall • Dec 2 '18 • Edited

The lack of frequencies didn't bother me - it's easy to add. And yes, I've been thinking for the rest of the day that I should use lazy sequences. In this case the execution time remains O(N²) but as you say the memory footprint becomes more like constant. Definitely a good practice when you can't find a better algorithm.

Ryan Will • Dec 4 '18

A little late, to the party. I tried really hard to think of a solution to part 2 that only involved iterating the list once, but no luck. Here is my solution in Elixir.

Part one:

 def part_1() do
  %{"3" => total_3, "2" => total_2} =
    AOC.read_input("2018/day_2"      
    |> Enum.reduce(%{"2" => 0, "3" => 0}, fn id, acc ->
        counts =
          String.split(id, "", trim: true)
          |> Enum.reduce(%{}, &Map.update(&2, &1, 1, fn val -> val + 1 end))
          |> Enum.reduce(%{"2" => 0, "3" => 0}, fn
            {_, 2}, count ->
              Map.update!(count, "2", fn _ -> 1 end)

            {_, 3}, count ->
              Map.update!(count, "3", fn _ -> 1 end)

            _, count ->
              count
          end)

        %{acc | "2" => acc["2"] + counts["2"], "3" => acc["3"] + counts["3"]}
      end)

    total_2 * total_3
end

Part 2:

def part_2() do
  AOC.read_input("2018/day_2")
  |> traverse_list()
end

def traverse_list([head | tail]) do
  traverse_list(head, tail, tail)
end

def traverse_list(_, [], [head | tail]) do
  traverse_list(head, tail, tail)
end

def traverse_list(compare, [current | tail] = remaining, rest_list)
    when length(remaining) > 0 do
  case compare_strings(compare, current) do
    :notfound ->
      traverse_list(compare, tail, rest_list)

    common_chars ->
      common_chars
  end
end

def compare_strings(s1, s2) do
  s1 = String.split(s1, "", trim: true)
  s2 = String.split(s2, "", trim: true)
  zipped = Enum.zip(s1, s2)

  case Enum.reduce(zipped, %{misses: 0, common: ""}, fn
    {s, s}, acc ->
      %{acc | common: acc.common <> s}

     _, acc ->
       %{acc | misses: acc.misses + 1}
  end) do
    %{misses: 1, common: common} ->
      common

    _ ->
      :notfound
  end
end

Phil Nash • Dec 2 '18 • Edited

So this was a pain. I also ended up with a double loop (O(n²⁾⁾ and couldn't think of anything better.

One thing I discovered during part two was that Crystal has Levenshtein distance as part of the standard library. It might have been a bit heavy going for what I needed, but it did the trick!

require "levenshtein"

class FabricBox
  getter id

  @letter_map : Hash(String, Int32)

  def initialize(@id : String)
    @letter_map = @id.split("").reduce(Hash(String, Int32).new(default_value: 0)) do |acc, letter|
      acc[letter] = acc[letter] + 1
      acc
    end
  end

  def has_exactly?(letters : Int32) : Bool
    @letter_map.values.any? { |count| count == letters }
  end
end

class FabricBoxCollection
  getter boxes
  @boxes : Array(FabricBox)

  def initialize(ids : Array(String))
    @boxes = ids.map { |id| FabricBox.new(id) }
  end

  def checksum
    @boxes.count { |box| box.has_exactly? 2 } * @boxes.count { |box| box.has_exactly? 3 }
  end

  def find_close_id
    @boxes.each do |box_i|
      @boxes.each do |box_j|
        if Levenshtein.distance(box_i.id, box_j.id) == 1
          characters_i = box_i.id.split("")
          characters_j = box_j.id.split("")
          char_pairs = characters_i.zip(characters_j)
          return char_pairs.reduce("") do |acc, (char_i, char_j)|
            acc += char_i if char_i == char_j
            acc
          end
        end
      end
    end
  end
end

puts "--- Day 2: Inventory Management System ---"
input = File.read_lines("./02/input.txt")
collection = FabricBoxCollection.new(input)
puts "Checksum: #{collection.checksum}"
puts "Common letters: #{collection.find_close_id}"

Bring on day 3!

Ryan Palo • Dec 2 '18

High five for a beefy standard library! That’s awesome 😎

Lasse Schultebraucks • Dec 2 '18

from collections import defaultdict
from difflib import SequenceMatcher

from operator import itemgetter


def similar(a, b):
    return SequenceMatcher(None, a, b).ratio()


def main():
    part_one()
    part_two()


def part_one():
    with open('input.txt', 'r') as input_file:
        lines = [line for line in input_file]

    word_twice_count = 0
    word_three_times_count = 0

    for line in lines:
        word_count_dic = defaultdict(int)
        has_char_twice = False
        has_char_three_times = False
        for char in line:
            word_count_dic[char] += 1
        for key in word_count_dic.keys():
            if word_count_dic[key] == 2:
                has_char_twice = True
            elif word_count_dic[key] == 3:
                has_char_three_times = True

        if has_char_twice:
            word_twice_count += 1
        if has_char_three_times:
            word_three_times_count += 1

    checksum = word_twice_count * word_three_times_count

    print 'checksum is ' + str(checksum)


def part_two():
    with open('input.txt', 'r') as input_file:
        lines = [line for line in input_file]

    similarity_strings = [(line, comparing_line, similar(line, comparing_line))
                          for line in lines for comparing_line in lines
                          if line is not comparing_line]

    most_similair_strings = max(similarity_strings, key=itemgetter(2))

    result_word = ''.join([char_word_one
                           for char_word_one, char_word_two in zip(most_similair_strings[0], most_similair_strings[1])
                           if char_word_one == char_word_two])

    print result_word


if __name__ == '__main__':
    main()

My solution with Python, not sure about the second part, not the most fastest solution I think regarding of performance.

Ryan Palo • Dec 2 '18

Nice! Don’t forget about collections.Counter for part 1! I didn’t know about difflib though. Cool!

Lasse Schultebraucks • Dec 2 '18

Thanks for the hint! Will do that later!

Lasse Schultebraucks • Dec 2 '18

def part_one():
    word_twice_count = 0
    word_three_times_count = 0

    with open('input.txt', 'r') as input_file:
        for line in input_file:
            line_counter = Counter(line)
            if 2 in line_counter.values():
                word_twice_count += 1
            if 3 in line_counter.values():
                word_three_times_count += 1

    checksum = word_twice_count * word_three_times_count

    print 'checksum is ' + str(checksum)

My edited solution for part one with collections Counter

roeekl • Dec 3 '18

Part 1: C# + LINQ = one-liner

return (input.Count(id => id.GroupBy(c => c).Any(group => group.Count() == 2)) *
                   input.Count(id => id.GroupBy(c => c).Any(group => group.Count() == 3)))

Part 2

for (int i = 0; i < input[0].Length; i++)
            {
                var commonIds = input.Select(id => id.Remove(i, 1)).GroupBy(id => id).FirstOrDefault(group => group.Count() > 1);
                if (commonIds != null)
                {
                    return commonIds.First();
                }
            }

Florian Rohrer • Dec 2 '18

Part 1

from collections import Counter

with open("input.txt") as f:
    ids = [Counter(l.strip()) for l in f]

count2 = 0
count3 = 0
for c in ids:
    if 2 in c.values(): count2 += 1
    if 3 in c.values(): count3 += 1

print(count2 * count3)

Part 2

from editdistance import eval as dist
from itertools import product

with open("input.txt") as f:
    ids = [l.strip() for l in f]

for a, b in product(ids, ids):
    d = dist(a, b)
    if d == 1:
        print(a, b)
        break

And from the output, I just copied and pasted the necessary characters that matched. That was faster than comming up with a custom method to do so.

Ryan Palo • Dec 2 '18

Nice! Did you implement editdistance yourself, or is that an external library?

Florian Rohrer • Dec 2 '18

It is external. I found it via a quick google search. The edit distance measures how many operations - insertion, deletion or substitution - it takes to get from one string to the other. Since all the strings in the puzzle input have the same length, insertion and deletion do not come into play and it works out perfectly.

Ryan Palo • Dec 2 '18

Ok that’s cool, just checking. Neat!

Dylan Paulus • Dec 2 '18 • Edited

Terrible C++ solution for part 1 !

#include <iostream>
#include <fstream>
#include <list>
#include <map>

std::list<std::string> read_file(std::string filename)
{
  auto lines = std::list<std::string>();
  std::ifstream file(filename);

  for (std::string line; std::getline(file, line);)
  {
    lines.push_back(line);
  }

  file.close();

  return lines;
}

class WordCounter
{
public:
  static std::map<char, int> CalculateLine(const std::string line)
  {
    auto map = std::map<char, int>();

    if (line.length() == 0)
    {
      return map;
    }

    for (int i = 0; i < line.length(); i++)
    {
      std::map<char, int>::iterator it = map.find(line[i]);

      if (it != map.end())
      {
        it->second = it->second + 1;
      }
      else
      {
        map.insert(std::pair<char, int>(line[i], 1));
      }
    }

    return map;
  }

  static const std::pair<int, int> Sum(std::map<char, int> map)
  {
    int twos = 0;
    int threes = 0;

    for (auto line = map.begin(); line != map.end(); line++)
    {
      if (line->second == 2)
      {
        twos = 1;
      }
      else if (line->second == 3)
      {
        threes = 1;
      }
    }

    return std::pair<int, int>(twos, threes);
  }
};

int main()
{
  auto input = read_file("./input.txt");
  int two = 0;
  int three = 0;

  for (auto i = input.begin(); i != input.end(); i++)
  {
    auto letterMap = WordCounter::CalculateLine(*i);
    auto calculated = WordCounter::Sum(letterMap);

    two += calculated.first;
    three += calculated.second;
  }

  std::cout << two * three << std::endl;

  return 0;
}

Ryan Palo • Dec 3 '18

Terrible is better than never finished! And this looks pretty good to me, not knowing C++ if that makes you feel better 😄

Paula Gearon • Dec 3 '18

I did my solutions at midnight last night, but I was surviving on very little sleep at the time, so the resulting code was below standard. I tried again this morning and felt better about it.

For anyone reading this, I'm still using the simple lines function from Day 1 which reads a file into a sequence of strings.

Part 1

This was my solution last night:

(defn nums [s]
  (let [cs (->> s
                (group-by identity)
                vals
                (map count))]
    [(some #(= 2 %) cs) (some #(= 3 %) cs)]))

(defn star
  [input-file]
  (let [tt (->> (lines input-file)
                (map nums))]
    (* (count (filter first tt)) (count (filter second tt)))))

This is embarrassing code. I totally forgot about the frequencies function, which is why I used group-by followed by count. But the 2 filter operations in the final calculation meant that the results of the map get processed twice.

My morning attempt fixed these:

(defn counts [[two-count three-count] s]
  (let [cs (-> s frequencies vals)]
    [(if (some #(= 2 %) cs) (inc two-count) two-count)
     (if (some #(= 3 %) cs) (inc three-count) three-count)]))

(defn star
  [input-file]
  (let [[two-count three-count] (->> (lines input-file) (reduce counts [0 0]))]
    (* two-count three-count)))

This time I accumulated the 2/3 count values while processing the list, so it only goes through it once.

Part 2

Since each element needs to be compared to every other element, I can't see any way around the O(n² ) complexity. Of course, each element should only be compared to the ones after it, so as to avoid comparing each one twice (since comparing A/B has the same result as comparing B/A).

When doing list processing, the only ways I know to refer to everything following an element are by using indexes (yuck) or with a loop. Unfortunately, I got fixated on the loop construct, and nested it:

(defn close [a b]
  (let [sim (filter identity (map #(when (= %1 %2) %1) a b))]
    (when (= (count sim) (dec (count a))) sim)))

(defn cmp-close [ll]
  (loop [[f & fr] ll]
    (when (seq fr)
      (or
        (loop [[s & sr] fr]
          (when s
            (or (close f s)
                (recur sr))))
        (recur fr)))))

(defn star2
  [input-file]
  (let [ll (lines input-file)]
    (apply str (cmp-close ll))))

The other way you can tell that I wrote this on very little sleep was the use of ridiculously terse var names.

On reflection this morning, I realized that the inner loop should have been a some operation. This does a predicate test and terminates processing early, which is what I was doing manually with the inner loop.

Also, my close function has several issues. First is the name! I was thinking of "A is close to B", but when I saw it again this morning I realized that it's the same function name for closing a resource. Something else that bothers me is that it processes the entirety of each string before returning, when a false result can usuall terminate early. Finally, a minor issue is that the anonymous function #(when (= %1 %2) %1) would be more idiomatic to use a singleton set on %1 to compare to %2.

(defn nearly= [left right]
  (let [same (filter identity (map #(#{%1} %2) left right))]
    (when (= (count same) (dec (count left))) (apply str same))))

(defn compare-lines [ll]
  (loop [[line & xlines] ll]
    (when (seq line)
      (or
       (some (partial nearly= line) xlines)
       (recur xlines)))))

(defn star2
  [input-file]
  (compare-lines (lines input-file)))

The nearly= function now returns a string, rather than the array of characters, but hasn't changed much. I was still unsatisfied with it not terminating the test early, so I rewrote it to be faster. However, the resulting code lacks any kind of elegance, and I'm not convinced that it's worth the effort:

(defn nearly= [left right]
  (loop [[l & xl] left [r & xr] right diffs 0]
    (if (nil? l)
      (apply str (filter identity (map #(#{%1} %2) left right)))
      (if (not= l r)
        (when (zero? diffs)
          (recur xl xr 1))
        (recur xl xr diffs)))))

Hopefully I'll get some sleep before attempting day 3. 😊

View full discussion (66 comments)

DEV Community

AoC Day 2: Inventory Management System

Top comments (66)

Part 1

Part 2

Part 1

Part 2

Read next

What's Your Favorite IT Quote or Rule? And How Does It Influence Your Work?

If John Wick was a programmer, what language would he use?

What Makes Ruby Easy to Learn & Use?

Destructuring props in React