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?

Oldest comments (64)

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()
}

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.

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!

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);
            }
        }
    }
}

Jon Bristow • Dec 2 '18

I lost about 10 minutes to my son stalling getting into bed.

Kotlin Solution

Answer 1

Once again a fairly straightforward opener. Just run through, do some simple frequency checking and spit back the results. I think this is technically O(n²⁾ but it moved fast enough for me. (And in a more lazy language, it ends up being closer to O(n) anyway)

fun String.frequencies(): Map<Char, Int> =
        groupBy { it }.mapValues { (_, v) -> v.count() }

fun answer1(input: List<String>) =
    input.map {
        val freqs = it.frequencies()
        freqs.anyValue(2::equals) to freqs.anyValue(3::equals)
    }
        .unzip().toList()
        .map { bs -> bs.count { it } }
        .fold(1, Int::times)

Answer 2

As Ryan said, this is just Hamming distance with the added wrinkle that you need to throw away the differences while counting them. Lots of optimization room here, but once again, we shave off just under half the possibilities by only doing unique combinations and going from a raw n^2 to (n*(n+1))/2.

At around 10 ms (calculated by shuffling my input 1000 times), I don't think there's an easy way to make this noticeably faster at this point without a more esoteric method.

fun <A, B> List<A>.cartesian(transform: (A, A) -> B): Sequence<B> {
    return init.asSequence().mapIndexed { i, a ->
        drop(i + 1).asSequence().map { b ->
            transform(a, b)
        }
    }.flatten()
}

fun <A> Pair<A, A>.same() = first == second
fun <A> Pair<A, A>.different() = first != second

fun answer2(input: List<String>) =
    input.cartesian { s1, s2 ->
        s1.zip(s2)
    }.find { // find short circuits on Sequence
        it.count(Pair<Char, Char>::different) == 1
    }?.filter {
        it.same()
    }?.joinToString("") { it.first.toString() }

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!

Ben Halpern • Dec 2 '18

We need better cover images 😂

Ryan Palo • Dec 2 '18

I was kind of hoping that the magical resizing was an automated resizing thing that happens and not one of you guys fixing it for me. I can actually put a background on it and scale it. What are the optimal dimensions? Is the white text on black ok or should I come up with something more fancy? I have very little aesthetic skill, so I’d appreciate any suggestions you or anyone else has.

Ali Spittel • Dec 2 '18

Ryan, do you want me to design something? The only hard part is that I probably won't be up at midnight most nights to add specifics. Do you have any design software? If so, I can transfer you a file! We could also use Canva.

Ryan Palo • Dec 2 '18

That would be amazing! I have a Figma account, but that’s it. I’ve never heard of Canva and pretty sure I don’t have any design software, but if you tell me the best way to handle it, I’ll happily do whatever you suggest. I’m happy to learn.

Ali Spittel • Dec 2 '18

Cool -- sending you a DM via /connect!

Harriet • Dec 2 '18

Part 1 in Ruby:

have_two_letters = 0
have_three_letters = 0

File.open('./input.txt', 'r').each do |str|
  freq = str.split('').group_by(&:itself).map {|k,v| [v.size, k] }.to_h
  have_two_letters += 1 if freq[2]
  have_three_letters += 1 if freq[3]
end

puts have_three_letters * have_two_letters

I enjoyed playing around with the one liner

str.split('').group_by(&:itself).map {|k,v| [v.size, k] }.to_h

which produces a frequency chart something like this:

{1=>"j", 4=>"f", 2=>"s"}

i.e. there are exactly 2 occurrences of the letter s in str

Part 2 in Ruby

lines = File.read('./input.txt').split("\n");

def get_shared_letters(str1, str2)
  differences = 0
  same_letters = nil
  str1.split('').each_with_index do |letter, i|
    if letter != str2[i]
      differences += 1 
      same_letters = str1.dup
      same_letters.slice!(i)
    end
  end

  differences === 1 ? same_letters : nil
end

lines.each_with_index do |str1, i1|
  lines.each_with_index do |str2, i2|
    next if i2 === i1

    shared = get_shared_letters str1, str2
    puts shared if shared
  end
end

Not happy about the double loop through the input file... but also can't think of a way to avoid it! It occurred to me that sorting the list first might improve the chances of finding a match earlier in the loop since all similar strings would be together, but thinking about it, perhaps there's equal chance that the similar strings would end up being sorted to the bottom of the list and it wouldn't help at all :/

Another thought - many of the input strings are v. similar, maybe they could be grouped into sets early on (e.g. based on the first 4 chars or something) and then you only look for similar strings in the same set?

Going to read into hamming distances now!

Bjarne Magnussen • Dec 2 '18

I am using Advent of Code to learn Golang, and here is the solution I came up with. Suggestions for improvements are always welcome!

Part 1:

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

// readLines reads a whole file into memory
// and returns a slice of its lines.
func readLines(path string) ([]string, error) {
    file, err := os.Open(path)
    if err != nil {
        return nil, err
    }
    defer file.Close()

    var lines []string
    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        lines = append(lines, scanner.Text())
    }
    return lines, scanner.Err()
}

func main() {
    boxes, err := readLines("input")
    if err != nil {
        panic(err)
    }

    var twos, threes int
    for _, box := range boxes {
        // Iterate through each box letter-by-letter and check if letters appear
        // two or three times:
        two, three := false, false
        for _, letter := range box {
            if !two && strings.Count(box, string(letter)) == 2 {
                twos++
                two = true
            } else if !three && strings.Count(box, string(letter)) == 3 {
                threes++
                three = true
            }
            if two && three {
                // We already found the maximum number of appearing letters we count
                break
            }
        }
    }
    checksum := twos * threes
    fmt.Printf("Checksum is: %d\n", checksum)
}

Part 2:

package main

import (
    "bufio"
    "fmt"
    "os"
)

// readLines reads a whole file into memory
// and returns a slice of its lines.
func readLines(path string) ([]string, error) {
    file, err := os.Open(path)
    if err != nil {
        return nil, err
    }
    defer file.Close()

    var lines []string
    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        lines = append(lines, scanner.Text())
    }
    return lines, scanner.Err()
}

func findSimilar(boxes []string) string {
    // For each box name we remove the i'th element and store the rest of the
    // name inside a map:
    visited := make(map[int]map[string]bool)
    for _, box := range boxes {
        // Go through each  box:
        for i := range box {
            // Remove i'th character from box name:
            subname := box[:i] + box[i+1:]
            // Check if we have already visited a similar box name:
            _, ok := visited[i][subname]
            if !ok {
                // If we have never encountered a similar box name, add it:
                _, ok := visited[i]
                if !ok {
                    sub := make(map[string]bool)
                    visited[i] = sub
                }
                visited[i][subname] = true
            } else {
                // We have encounter a similar box name, return it:
                return subname
            }
        }
    }
    return ""
}

func main() {
    boxes, err := readLines("input")
    if err != nil {
        panic(err)
    }
    subname := findSimilar(boxes)
    fmt.Println(subname)
}

My idea was to use a dictionary and store the subnames and see if we encounter one we have already visited. Since there should only be one match we can immediately return it. I learned a lot about using maps in Golang!

I am also using Python that I have more experience with to cross check solutions. I have tried to implement it with readability in mind, not performance.

Part 1:

with open('input') as f:
    boxes = f.readlines()

twos, threes = 0, 0
for box in boxes:
    twos += any([box.count(letter) == 2 for letter in set(box)])
    threes += any([box.count(letter) == 3 for letter in set(box)])
checksum = twos * threes

print('Checksum {}'.format(checksum))

Part 2:

with open('input') as f:
    boxes = f.readlines()


def closest_boxes():
    visited = {}
    for box in boxes:
        for i in range(len(box)):
            if i not in visited:
                visited[i] = set()
            subname = box[0:i] + box[i+1:]
            if subname in visited[i]:
                return subname
            else:
                visited[i].add(subname)


print(closest_boxes())

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

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.

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 😎

Mustafa Haddara • Dec 2 '18 • Edited

Hosting my solutions on my github...

MustafaHaddara / advent-of-code-2018

Code for https://adventofcode.com/2018/

advent-of-code-2018

Code for adventofcode.com/2018/

I'm trying to learn Julia so I'm using AoC to force myself to learn.

View on GitHub

I'm pretty sure part 2 has to be O(n²⁾ but you can cut down on the total number of iterations by only looking forward...here's my solution (implemented in Julia)

function inventory_management_diff(input)
    word_idx = 0
    while word_idx < length(input)
        word_idx += 1
        word1 = input[word_idx]

        for word2 in input[word_idx+1:end]
            ch_diff = one_char_diff(word1, word2)
            if ch_diff != nothing
                return string(word1[1:ch_diff-1], word1[ch_diff+1:end])
            end
        end
    end
end

function one_char_diff(word1, word2)
    found_diff = nothing
    ch_idx = 0
    while ch_idx < length(word1)
        ch_idx += 1
        if word1[ch_idx] != word2[ch_idx]
            if found_diff == nothing
                found_diff = ch_idx
            else
                return nothing
            end
        end
    end
    return found_diff
end

function main()
    filename = ARGS[1]  # julia arrays are 1-indexed!
    input = split(read(filename, String))
    test_input = ["abcde","fghij","klmno","pqrst","fguij","axcye","wvxyz"]

    println(inventory_management_diff(input))
end

main()

Julia's a weird language...it's so close to python that I forget it does weird things like "Arrays are 1-indexed", and it spells None/null as nothing

Ryan Palo • Dec 2 '18

I agree that Julia is weird, but I actually love it because it adds some functional stuff that I miss in python like the pipe operator!

jess unrein • Dec 2 '18

My solutions for part 1

Python

def checksum(inputs):
    ids = inputs.read().splitlines()
    twos = 0
    threes = 0
    for row in ids:
        seen = {}
        for letter in row:
            seen[letter] = seen.get(letter, 0) + 1
        if 2 in seen.values():
            twos += 1
        if 3 in seen.values():
            threes += 1

    return twos * threes

checksum(open('input.txt', 'r'))

package main

import (
    "strings"
    "io/ioutil"
)

func containsVal(m map[string]int, v int)(bool) {
    for _, x := range m{
        if x == v {
            return true
        }
    }
    return false
}

func checksum(x string)(int) {
    two := 0
    three := 0
    ids := strings.Split(x, "\n")
    for i := 0; i < len(ids); i++ {
        counter := make( map[string]int )
        s := strings.Split(ids[i], "")
        for _, l := range s {
            counter[l]++
        }
        if containsVal(counter, 2) {
            two++
        }
        if containsVal(counter, 3) {
            three++
        }
    }
    return two * three
}

func main() {
    f, err := ioutil.ReadFile("input.txt")
    if err != nil {
        panic(err)
    }
    checksum(string(f))
}

Benchmark difference

`python3 2_1.py` 100 times
real    0m4.744s
user    0m3.129s
sys 0m0.967s

`go run 2_1.go` 100 times
real    0m37.649s
user    0m28.807s
sys 0m14.105s

go build

`./2_1` 100 times
real    0m0.709s
user    0m0.327s
sys 0m0.280s

Shritesh Bhattarai • Dec 2 '18 • Edited

Rust
Part 1

use std::collections::HashMap;

fn contains_repeats(input: &str) -> (bool, bool) {
    let mut count = HashMap::new();

    input.chars().for_each(|c| {
        let n = count.entry(c).or_insert(0);
        *n += 1;
    });

    let two = count.iter().any(|(_, &v)| v == 2);
    let three = count.iter().any(|(_, &v)| v == 3);

    (two, three)
}

pub fn checksum(input: &[&str]) -> usize {
    let (twos, threes): (Vec<_>, Vec<_>) = input.iter().map(|&s| contains_repeats(s)).unzip();
    let two = twos.iter().filter(|&x| *x).count();
    let three = threes.iter().filter(|&x| *x).count();

    two * three
}

Part 2
~~I'm still searching for a nice iterator adapter to replace the nested loop.~~ I finally used the itertools crate and it's AMAZING!!!

use itertools::Itertools;

fn hamming(input1: &str, input2: &str) -> usize {
    input1
        .chars()
        .zip(input2.chars())
        .filter(|(a, b)| a != b)
        .count()
}

fn common(input1: &str, input2: &str) -> String {
    input1
        .chars()
        .zip(input2.chars())
        .filter_map(|(a, b)| match a == b {
            true => Some(a),
            false => None,
        })
        .collect()
}

pub fn find_common(input: &[&str]) -> String {
    input
        .iter()
        .tuple_combinations()
        .find_map(|(first, second)| match hamming(first, second) {
            1 => Some(common(first, second)),
            _ => None,
        })
        .unwrap()
}

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.

Matt Morgis • Dec 2 '18 • Edited

Node.js

Common async generator. Read the file in chunk by chunk and yield each product ID based on new lines.

// Generator
// "abcdef\n+bababc\n" yields -> abcdef -> bababc
async function* streamToProdctId(stream) {
  let previous = "";
  for await (const chunk of stream) {
    previous += chunk;
    let eolIndex;
    while ((eolIndex = previous.indexOf("\n")) >= 0) {
      // productId excludes the EOL
      const productId = previous.slice(0, eolIndex);
      yield productId;
      previous = previous.slice(eolIndex + 1);
    }
  }
  if (previous.length > 0) {
    yield previous;
  }
}

Part 1 was fun with some ES6 array -> Set -> Map to get the value counts

// ['b', 'a', 'b', 'a', 'b', 'c'] returns Map {3 => 'b', 2 => 'a', 1 => 'c}
const count = array => {
  return new Map(
    [...new Set(array)].map(x => [array.filter(y => y === x).length, x])
  );
};

const checksum = async stream => {
  let idsWith2MatchingLetters = 0;
  let idsWith3MatchingLetters = 0;
  for await (const productId of streamToProductId(stream)) {
    const valueCounts = count([...productId]);
    if (valueCounts.has(2)) {
      idsWith2MatchingLetters++;
    }
    if (valueCounts.has(3)) {
      idsWith3MatchingLetters++;
    }
  }
  return idsWith2MatchingLetters * idsWith3MatchingLetters;
};

Part 2 got interesting. I needed to generate all pairs for every product ID. I made my Hamming Distance function also return the common letters. Then tied it all together by running each pair through the Hamming Distance function and getting the lowest.

const generatePairs = array => {
  return array.reduce(
    (acc, _, i1) => [
      ...acc,
      ...new Array(array.length - 1 - i1)
        .fill(0)
        .map((v, i2) => [array[i1], array[i1 + 1 + i2]])
    ],
    []
  );
};

const hammingDistance = (stringOne, stringTwo) => {
  let distance = 0;
  let commonLetters = "";
  for (let i = 0; i < stringOne.length; i++) {
    if (stringOne[i] !== stringTwo[i]) {
      distance += 1;
    } else {
      commonLetters = commonLetters.concat(stringOne[i]);
    }
  }
  return [distance, commonLetters];
};

const findLowestPairAndRemoveDifferences = pairs => {
  let lowestDistance = Infinity;
  let lowestPair;
  pairs.forEach(pair => {
    const [distance, commonLetters] = hammingDistance(...pair);
    if (distance < lowestDistance) {
      lowestDistance = distance;
      lowestPair = commonLetters;
    }
  });
  return lowestPair;
};

const productIds = async stream => {
  const ids = [];
  for await (const productId of streamToProductId(stream)) {
    ids.push(productId);
  }
  return ids;
};

const findCommon = async stream => {
  return findLowestPairAndRemoveDifferences(
    generatePairs(await productIds(stream))
  );
};

Putting it all together:

const productIdStream = () => {
  return fs.createReadStream(__dirname + "/input.txt", {
    encoding: "utf-8",
    highWaterMark: 256
  });
};

const main = async () => {
  try {
    const part1 = await checksum(productIdStream());
    console.log({part1});
    const part2 = await findCommon(productIdStream());
    console.log({part2});
  } catch (e) {
    console.log(e.message);
    process.exit(-1);
  }
};

Full code here: github.com/MattMorgis/Advent-Of-Co...

Ryan Palo • Dec 2 '18

Making hamming distance return common letters is a slick way to go. I was looking at the duplication between the hamming distance and common letters functionality in my solution and was a little bummed about it, but I couldn't figure out a good way to do it.

I like this!

View full discussion (66 comments)

DEV Community

AoC Day 2: Inventory Management System

Oldest comments (64)

Part 1

Part 2

Kotlin Solution

Answer 1

Answer 2

Part 1 in Ruby:

Part 2 in Ruby

MustafaHaddara / advent-of-code-2018

Code for https://adventofcode.com/2018/

advent-of-code-2018

Node.js

Read next

Coding in 2024 = Dead? The Best Language to Learn is English? 🤔☠️

Open Source AI Glasses: Would you wear them?

Teams, Slack, Discord. What's better?

Meme Monday