AoC Day 2: Inventory Management System

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?

Comments

[Ben Mulford]

Here's my C# .Net solution:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Day2Part1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] inputTxt = File.ReadAllLines(@"C:\Users\Ben\Desktop\adventOfCode2018\Day 2\input.txt");
            List<int> TwoMatchList = new List<int>();// List of id's to find box in the input array
            List<int> ThreeMatchList = new List<int>();// list of id's to find box in the input array
            foreach (string boxID in inputTxt)
            {
                int id = Array.IndexOf(inputTxt, boxID);
                var distinctLetters = boxID.Select(x => x).Distinct().ToList();
                foreach (char letter in distinctLetters)
                {
                    var matches = boxID.Where(x => x == letter).ToList();
                    switch (matches.Count)
                    {
                        case 2:
                            //if there's exactly 2, and it's not already in the list then add it to the TwoMatchList
                            if (!TwoMatchList.Contains(id))
                            {
                                TwoMatchList.Add(id);
                            }
                            break;
                        case 3:
                            //if there's exactly 3, and it's not already in the list then add it to the ThreeMatchList
                            if (!ThreeMatchList.Contains(id))
                            {
                                ThreeMatchList.Add(id);
                            }
                            break;
                        default:
                            //don't add to any list
                            break;
                    }//end switch
                }//end foreach letter
            }//end foreach boxID
            int checksum = TwoMatchList.Count * ThreeMatchList.Count;
            Console.WriteLine("Number of boxes with exactly two matching letters {0}", TwoMatchList.Count);
            Console.WriteLine("Number of boxes with exactly three matching letters {0}", ThreeMatchList.Count);
            Console.WriteLine("Checksum: {0}", checksum);
            Console.WriteLine();


            Console.WriteLine("Now for part two!");

            //empty Dictionary to hold any boxes we find and the index of the letter that's different
            Dictionary<string, int> savedIDsAndIndexes = new Dictionary<string, int>();

            //empty string to hold the answer
            string answer = "";

            //Loop through to test and find correct boxes ==>> this could be a foreach loop
            for (int i = 0; i < inputTxt.Length; i++)
            {
                string boxID = inputTxt[i];
                for (int j = inputTxt.Length - 1; j >= 0; j--)
                {
                    List<int> mismatchIndexes = new List<int>();
                    string testBoxID = inputTxt[j];
                    for (int k = 0; k < boxID.Length; k++)
                    {
                        if (boxID[k] != testBoxID[k])
                        {
                            mismatchIndexes.Add(k);
                        }
                    }
                    if (mismatchIndexes.Count == 1)
                    {
                        savedIDsAndIndexes.Add(boxID, mismatchIndexes.First());
                    }
                }
            }

            Console.WriteLine("number of correct boxes found: {0}", savedIDsAndIndexes.Count);

            answer = savedIDsAndIndexes.Keys.First().Substring(0, savedIDsAndIndexes.Values.First())
                + savedIDsAndIndexes.Keys.First().Substring(savedIDsAndIndexes.Values.First() + 1);

            Console.WriteLine("here are the ids:");
            foreach (var id in savedIDsAndIndexes)
            {
                Console.WriteLine(id.Key);
            }

            Console.WriteLine("The common characters are:\n{0}", answer);

            Console.WriteLine("saved index: {0}", savedIDsAndIndexes.Values.First());
        }
    }
}

[Pablo Olmos de Aguilera Corradini]

A bit late to the party, here are my solutions on Ruby:

Part 1:

twos = 0
threes = 0

File.open('day-02_input.txt').each_line do |line|
  counter = {}

  line.each_char do |char|
    next if line.count(char) <= 1

    counter[char] = line.count(char)
  end

  twos += 1 if counter.value? 2
  threes += 1 if counter.value? 3
end

puts twos * threes

Part 2:

boxes = []

File.open('day-02_input.txt').each_line { |box| boxes << box.chomp! }

def find_distance pair, distance = 0
  pair[0].each_char.with_index do |char, index|
    distance += 1 if char != pair[1][index]
  end
  distance
end

boxes.combination(2).each do |pair|
  next unless find_distance(pair) == 1

  str = ''

  pair[0].chars.each_with_index do |_, i|
    str << pair[0][i] if pair[0][i] == pair[1][i]
  end
  puts str
end

I learnt about the combination method :)

[Josh Wisenbaker]

I'm not super thrilled with my Day 2 code, but I haven't really had the time to tweak it with everything going on at work currently.

Swift Solutions
Part 1

This one was fairly simple. Just count how many times each letter appears in each String and act appropriately. I do like the fact that a Swift String type is really an Array of Characters.

// Part 1: Find the checksums
func calculateChecksum(_ idCodes: [String]) -> Int {
    var doubles = 0
    var triples = 0

    idCodes.map { (boxID) in
        var doubleTrue = false
        var tripleTrue = false
        for char in boxID {
            let count = boxID.filter { $0 == char }.count
            if count == 2 {
                doubleTrue = true
            }
            if count == 3 {
                tripleTrue = true
            }
        }
        doubles += doubleTrue ? 1 : 0
        triples += tripleTrue ? 1 : 0
    }
    return doubles * triples
}

let checksum = calculateChecksum(boxIDs)
print("Boxes checksum is: \(checksum)")

Part 2
This one feels clunky, if I get a chance I'll revisit it.

I break on the first hit for a solution to short circuit everything and return the answer, this can help a lot with so many Characters to test.

I use zip(_:_:) with a filter and count to quickly test how many differences there are in the same positions. When I see two strings that differ by one character in the same position I move to the next step.

In the second part I cast the Arrays into Set types so that I can use the Collection Algebra features to quickly find the actual character to remove by subtracting one collection from the other. With that done I can just remove it from the source Array and return what's left.

// Part 2: Box finder
func findTheBoxes(_ idCodes: [String]) -> String {
    var result = ""
    var differceCount = 0

    for boxID in idCodes {
        if differceCount == 1 {
            break
        }
        for code in idCodes {
            differceCount = zip(boxID, code).filter{$0 != $1}.count
            if differceCount == 1 {
                let diff = Set(boxID).subtracting(code)
                if let charToRemove = diff.first {
                    result = boxID
                    if let foo = result.index(of: charToRemove) {
                        result.remove(at: foo)
                        break
                    }
                }
            }
        }
    }
    return result
}

let theBoxes = findTheBoxes(boxIDs)
print("Matching box ID is: \(theBoxes)")

Normally I would import Foundation here so that I could just use NSOrderedSet and skip a few steps. I wanted to try and keep it all in the Swift Standard Library though, so I didn't!

[Ryan Will]

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

[roeekl]

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

[Tiago Romero]

My solution in JavaScript / Node 11, using the readline interface:

readLines.js

const fs = require('fs');
const readline = require('readline');

const readLines = (file, onLine) => {
    const reader = readline.createInterface({
        input: fs.createReadStream(file),
        crlfDelay: Infinity
    });

    reader.on('line', onLine);

    return new Promise(resolve => reader.on('close', resolve));
};

const readFile = async file => {
    const lines = [];
    await readLines(file, line => lines.push(line));  
    return lines;
}

module.exports = {
    readLines,
    readFile
};

02a.js

const { readFile } = require('./readLines');

(async () => {
    const lines = await readFile('02-input.txt');

    let twoLettersCount = 0;
    let threeLettersCount = 0;
    for (let line of lines) {
        const frequencyMap = {};
        for (const char of line.split('')) {
            frequencyMap[char] = (frequencyMap[char] || 0) + 1;
        }
        const hasTwoLetters = Object.values(frequencyMap).some(frequency => frequency === 2);
        const hasThreeLetters = Object.values(frequencyMap).some(frequency => frequency === 3);

        twoLettersCount += +hasTwoLetters;
        threeLettersCount += +hasThreeLetters;
    };

    const checksum = twoLettersCount * threeLettersCount;
    console.log(`The checksum is ${checksum}`);
})();

02b.js

const { readFile } = require('./readLines');

// Compares two strings to see if they differ by one char and which one 
function compare(string1, string2) {
    const length = string1.length;
    let differentChars = 0;
    let differIndex;
    for (let i = 0; i < length; i++) {
        if (string1.charAt(i) !== string2.charAt(i)) {
            differentChars++;            
            differIndex = differentChars === 1 ? i : undefined;
        }
    }

    return {
        differByOneChar: differentChars === 1,
        differIndex
    };
}

// Compare each strings to every other string 
// and get the common letters in case the differByOneChar is true
function getCommonLetters(ids) {
    const idsCount = ids.length;
    for (let i = 0; i < idsCount; i++) {
        const id = ids[i];
        for (let j = i + 1; j < idsCount; j++) {
            const { differByOneChar, differIndex } = compare(id, ids[j]);
            if (differByOneChar) {
                return id.slice(0, differIndex) + id.slice(differIndex + 1);
            }
        }
    }
}

(async () => {
    const lines = await readFile('02-input.txt');

    const commonLetters = getCommonLetters(lines);
    console.log(`The common letters are ${commonLetters}`);
})();

[Stevie Oberg]

This one was difficult for me, but I eventually got it! I'm also not happy about that double for loop in part 2, but I think I sped it up by removing the elements as I compared them?

github.com/stevieoberg/advent-of-c...

[Ben Lovy]

Late to the party!

Still digging F#, but I'm definitely hindered by my lack of familiarity with what's available in .NET

namespace Day2
open Microsoft.FSharp.Collections

module util =
    type FreqMap = Map<char, int>

    let getBoxIds fileName =
      let lines = System.IO.File.ReadLines(fileName)
      lines |> Seq.toList

    let tickFreq c (freqs: FreqMap) =
      match (freqs.TryFind c) with
      | Some x -> Map.add c (x + 1) freqs
      | None -> Map.add c 1 freqs

    let rec goGetFreqs (freqs: FreqMap) boxId =
      let len = String.length boxId
      if len = 1 then
        tickFreq boxId.[0] freqs
      else
        goGetFreqs (tickFreq boxId.[0] freqs) boxId.[1..len - 1]

    let getFreqs boxId = goGetFreqs (new Map<char, int> (Seq.empty)) boxId

    let countOfFreq num (freqMap: FreqMap) =
      freqMap
        |> Map.filter (fun _ v -> v = num)
        |> Map.toList
        |> List.length

module part1 =
  let getTwosAndThrees boxId =
    let freqs = util.getFreqs boxId
    let twos = util.countOfFreq 2 freqs
    let threes = util.countOfFreq 3 freqs
    (twos, threes)

  let rec getTotals twos threes l =
    match l with
    | [] -> (twos, threes)
    | (two, three)::tail ->
      let newTwos = if two > 0 then twos + 1 else twos
      let newThrees = if three > 0 then threes + 1 else threes
      getTotals newTwos newThrees tail

  let execute fileName =
    let boxIds = util.getBoxIds fileName
    let twosAndThrees = List.map (fun bid -> getTwosAndThrees bid) boxIds
    let (twos, threes) = getTotals 0 0 twosAndThrees
    twos * threes

module part2 =
  let checkTwo id id' =
    let s = (Seq.map2 (fun c c' -> 
      if c <> c' then
        '!'
      else
        c) id id')
          |> Seq.filter (fun c -> c <> '!')
          |> Seq.toArray
          |> System.String

    if (String.length id) - 1 = String.length s then
      Some s
    else
      None

  let findWinner boxIds =
    List.map (fun id ->
      List.map (fun id' ->
        if id = id' then
          None
        else
          checkTwo id id') boxIds) boxIds
            |> List.map (List.filter (fun el -> el.IsSome))
            |> List.filter (fun el -> List.length el > 0)
            |> List.concat
            |> List.distinct

  let execute fileName =
    let boxIds = util.getBoxIds fileName
    findWinner boxIds

[Ian Kirker]

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]

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]

Oh yes, good call, I missed that compaction.

[Anderson. J]

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,''))