Day 3: Rucksack Reorganization

[3]

tjf

December 3, 2022

Link

As you can tell, I love Python generators! Part 1 #!/usr/bin/env pypy3 import string import sys def main(): rucksacks = ((set(r[:(len(r) - 1) // 2]), set(r[(len(r) - 1) // 2:-1])) for r in...

As you can tell, I love Python generators!

Part 1

#!/usr/bin/env pypy3

import string
import sys

def main():
    rucksacks = ((set(r[:(len(r) - 1) // 2]), set(r[(len(r) - 1) // 2:-1]))
                 for r in sys.stdin)
    priorities = (string.ascii_letters.index(next(iter(set.intersection(*r)))) + 1
                  for r in rucksacks)
    print(sum(priorities))

if __name__ == '__main__':
    main()

Part 2

#!/usr/bin/env pypy3

import string
import sys

def group_sacks(rucksacks, size):
    for i in range(0, len(rucksacks), size):
        yield rucksacks[i:i + size]

def main():
    groups = group_sacks([set(r[:-1]) for r in sys.stdin], 3)
    priorities = (string.ascii_letters.index(next(iter(set.intersection(*r)))) + 1
                  for r in groups)
    print(sum(priorities))

if __name__ == '__main__':
    main()

7 votes

[2]
primordial-soup
December 3, 2022
Link Parent
ooh, string.ascii_letters is nice here, i'm going to steal that :)

ooh, string.ascii_letters is nice here, i'm going to steal that :)

4 votes
1. tjf
  December 3, 2022
  Link Parent
  My first instinct was to use ord() and subtract ascii values, but this worked out cleaner I think.
  
  My first instinct was to use ord() and subtract ascii values, but this worked out cleaner I think.
  
  4 votes

[2]

bhrgunatha

December 3, 2022 (edited December 3, 2022)

Link

Part 1 Really straightforward with sets (define (part-01 input) (for/sum ([l (in-list input)]) (priority (set-first (set-intersect (string->set (substring l 0 (/ (string-length l) 2)))...

Part 1

Really straightforward with sets

(define (part-01 input)
  (for/sum ([l (in-list input)])
    (priority
     (set-first (set-intersect
                 (string->set (substring l 0 (/ (string-length l) 2)))
                 (string->set (substring l (/ (string-length l) 2))))))))

(define string->set
  (compose1 list->set string->list))

(define (priority c)
  (define is (char->integer c))
  (if (char-upper-case? c)
      (- is 38)
      (- is 96)))

I love Racket's sequences in this case (and sorry for putting this on its own line but for some reason tildes can't format it correctly in-line):

in-slice make this trivial.

Part 2:

Part 2

(define (part-02 input)
  (for/sum ([g (in-slice 3 (in-list input))])
    (priority
     (set-first (apply set-intersect (map string->set g))))))

Speedrun

First attempt part 1: ~50% elapsed time:

Instead of using converting both halves of the rucksack to sets, just convert the first half of the rucksack to a set and find the first member of that set in the second half of the rucksack

(define (part-01 input)
  (for/sum ([l (in-list input)])
    (priority
     (string-intersect/2 (substring l 0 (/ (string-length l) 2))
                         (substring l (/ (string-length l) 2))))))

(define (string-intersect/2 s1 s2)
  (define seen (for/set ([c (in-string s1)]) c))
  (for/first ([c (in-string s2)]
              #:when (set-member? seen c))
    c))

For part 2 ~66% elapsed time:

convert the 1^st rucksack to a set
make a set of characters in the 2^nd rucksack that are members of the set from 1.
find the first character in the 3^rd rucksack in the set from 2.

(define (part-02 input)
  (for/sum ([g (in-slice 3 (in-list input))])
    (priority (apply string-intersect/3 g))))

(define (string-intersect/3 s1 s2 s3)
  (define seen (for/set ([c (in-string s1)]) c))
  (define badges (for/set ([c (in-string s2)]
                           #:when (set-member? seen c)) c))
  (for/first ([c (in-string s3)]
              #:when (set-member? badges c))
    c))

5 votes

thorondir

December 5, 2022

Link Parent

Ah, sets make a lot of sense, didn't think of them. I went about it in a rather... procedural way, which felt dirty, but worked. xD Part 1 ;; sanitize-input gets called before part-1 (define...

Ah, sets make a lot of sense, didn't think of them.

I went about it in a rather... procedural way, which felt dirty, but worked. xD

Part 1

;; sanitize-input gets called before part-1
(define (sanitize-input raw-input)
  (for/list ([l (string-split raw-input "\n")])
    (define strlen (string-length l))
    (list ; return halves independently
     (string->list (substring l 0 (/ strlen 2)))
     (string->list (substring l (/ strlen 2))))))

(define (char-mapper c)
  (if (char-lower-case? c)
      (- (char->integer c) (sub1 (char->integer #\a)))
      (+ 26 (- (char->integer c) (sub1 (char->integer #\A)) ))))

(define (calculate-priority priorities)
  (for/fold ([acc 0])
            ([c priorities])
    (+ acc (char-mapper c))))

(define (part-1 input)
  (define duplicates
    (for/list ([backpack input])
      (define h (make-hash))
      (for ([c (first backpack)])
        (hash-set! h c 1))
      (for/last ([c (second backpack)]
                 #:when (hash-has-key? h c))
        c)))

  (calculate-priority duplicates))

And part 2 also makes use of hash-maps a lot.

Part 2

; each backpack gets a hash where the characters are mapped to 1
(define (map-backpack backpack)
  (define h (make-hash))
  (map (lambda (c) (hash-set! h c 1)) (append (first backpack) (second backpack)))
  h)

; calculate the union of the hashes by combining the values with +
; which means that the key that has a value of 3 is the badge we're looking for
(define (compare-backpack-maps backpack-maps)
  (apply hash-union! backpack-maps #:combine +)
  (define combined (first backpack-maps))
  (for/last ([k (in-hash-keys combined)]
             #:when (= (hash-ref combined k) 3))
    k))

; split the backpacks into groups of three
; calculate the badge for the current group
; recursively calculate the badge for the next group
(define (process-backpacks backpacks)
  (cond [(< (length backpacks) 3) empty]
        [else (define-values
                (current-group other-groups)
                (split-at backpacks 3))
              (cons
               (compare-backpack-maps
                (for/list ([b current-group])
                  (map-backpack b)))
               
               (process-backpacks other-groups))]))


;; part 2
(define small-answer-2 70)

(define (part-2 input)
  (define badges (process-backpacks input))
  (calculate-priority badges))

2 votes

primordial-soup

December 3, 2022 (edited December 3, 2022)

Link

Part 1, in Python-ish

(ls
 > fe((divide, 2)
      | fe(set) | (reduce, and_) | one
      | string.ascii_letters.index | X + 1)
 | sum)

Python code generated from the above

from functools import reduce
from more_itertools import divide
from more_itertools import one
from operator import and_
from pipetools import X
from pipetools import foreach
import string
import sys
from pyp import pypprint
fe = foreach
lines = [x.rstrip('\n') for x in sys.stdin]
ls = lines
output = ls > fe((divide, 2) | fe(set) | (reduce, and_) | one | string.ascii_letters.index | X + 1) | sum
if output is not None:
    pypprint(output)

Part 2, in Python-ish

(ls > p
 | (chunked, X, 3)
 | fe(fe(set) | (reduce, and_) | one
      | string.ascii_letters.index | X + 1)
 | sum)

Python code generated from the above

from functools import reduce
from more_itertools import chunked
from more_itertools import one
from operator import and_
from pipetools import X
from pipetools import foreach
from pipetools import pipe
import string
import sys
from pyp import pypprint
p = pipe
fe = foreach
lines = [x.rstrip('\n') for x in sys.stdin]
ls = lines
output = ls > p | (chunked, X, 3) | fe(fe(set) | (reduce, and_) | one | string.ascii_letters.index | X + 1) | sum
if output is not None:
    pypprint(output)

edit: replaced λ c: ord(c) - (ord("a") if c.islower() else ord("A") - 26) + 1 with string.ascii_letters.index | X + 1.

4 votes

jzimbel

December 3, 2022

Link

Elixir Both parts Pretty straightforward. I converted the appropriate strings or substrings to sets of characters, and then used set intersection to find the common character. defmodule...

Elixir

Both parts

Pretty straightforward. I converted the appropriate strings or substrings to sets of characters, and then used set intersection to find the common character.

defmodule AdventOfCode.Solution.Year2022.Day03 do
  def part1(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(&find_duplicate/1)
    |> Enum.map(&priority/1)
    |> Enum.sum()
  end

  def part2(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.chunk_every(3)
    |> Enum.map(&find_badge/1)
    |> Enum.map(&priority/1)
    |> Enum.sum()
  end

  defp find_duplicate(sack) do
    compartment_size = div(byte_size(sack), 2)

    sack
    |> String.to_charlist()
    |> Enum.split(compartment_size)
    |> then(fn {l, r} -> MapSet.intersection(MapSet.new(l), MapSet.new(r)) end)
    |> Enum.at(0)
  end

  defp find_badge(group) do
    group
    |> Enum.map(&(&1 |> String.to_charlist() |> MapSet.new()))
    |> Enum.reduce(&MapSet.intersection/2)
    |> Enum.at(0)
  end

  for {item, pri} <- Enum.with_index(Enum.concat(?a..?z, ?A..?Z), 1) do
    defp priority(unquote(item)), do: unquote(pri)
  end
end

4 votes

[2]

akk

December 3, 2022

Link

More swift! Parts 1 and 2 import Foundation // Source: https://www.hackingwithswift.com/example-code/language/how-to-split-an-array-into-chunks extension Array { func chunked(into size: Int) ->...

More swift!

Parts 1 and 2

import Foundation

// Source: https://www.hackingwithswift.com/example-code/language/how-to-split-an-array-into-chunks
extension Array {
    func chunked(into size: Int) -> [[Element]] {
        return stride(from: 0, to: count, by: size).map {
            Array(self[$0 ..< Swift.min($0 + size, count)])
        }
    }
}

func checkPriority(for item: String.Element) -> Int {
    if item.isUppercase {
        return Int(item.asciiValue!) - 64 + 26
    } else {
        return Int(item.asciiValue!) - 96
    }
}

func partOne(_ input: [String]) {
    var totalPriority: Int = 0

    for line in input {
        let sacks = Array(line).chunked(into: line.count / 2).map { Set($0) }
        guard let uniqueCompartment = sacks[0].intersection(sacks[1]).first else {  break }
        totalPriority += checkPriority(for: uniqueCompartment)
    }
    print(totalPriority)
}


func partTwo(_ input: [String]) {
    let sackGroups = input.chunked(into: 3)
    var totalPriority: Int = 0
    for group in sackGroups {
        let sackSet = group.map { Set($0) }
        guard let uniqueItem = sackSet[0].intersection(sackSet[1].intersection(sackSet[2])).first else {
            break }
        totalPriority += checkPriority(for: uniqueItem)
    }
    print(totalPriority)
}

var puzzleInput: [String] = []

while let line = readLine() {
    puzzleInput.append(line)
}

partOne(puzzleInput)
partTwo(puzzleInput)

4 votes

kari
December 3, 2022
Link Parent
Wow, Swift seems a lot like Rust

Wow, Swift seems a lot like Rust

2 votes

[5]

Toric

December 3, 2022 (edited December 3, 2022)

Link

I really wish rusts HashSet implentation allowed finding the intersection of more than one other hashset at a time... Driver mod part1; mod part2; mod utilities; fn main() { let _input =...

I really wish rusts HashSet implentation allowed finding the intersection of more than one other hashset at a time...

Driver

mod part1;
mod part2;
mod utilities;

fn main() {
    let _input = include_str!("./input.txt");
    let _structured_input = utilities::parse(_input);

    println!("Part One");
    println!("Result: {}", part1::part1(&_structured_input));

    println!("Part Two");
    println!("Result: {}", part2::part2(&_structured_input));
}

utilites

use std::collections::HashSet;
#[derive(Debug, PartialEq, Eq)]
pub struct Rucksack(pub HashSet<char>, pub HashSet<char>);

pub fn parse(input: &str) -> Vec<Rucksack> {
    input
        .lines()
        .map(|line| {
            let (first, second) = line.split_at(line.len() / 2);
            Rucksack(first.chars().collect(), second.chars().collect())
        })
        .collect()
}

pub fn find_char_score(input: &char) -> usize {
    if input.is_uppercase() {
        *input as usize - 38
    } else {
        *input as usize - 96
    }
}

Part 1

use crate::utilities::*;

pub fn part1(input: &[Rucksack]) -> usize {
    input
        .iter()
        .map(|rucksack| rucksack.0.intersection(&rucksack.1).next().unwrap())
        .map(find_char_score)
        .sum()
}

Part 2

use crate::utilities::*;
use std::collections::HashSet;

struct Group(HashSet<char>, HashSet<char>, HashSet<char>);

pub fn part2(input: &[Rucksack]) -> usize {
    seperate_groups(input)
        .iter()
        .map(|group| {
            //manual implementation of intersection because doing chained intersections is annoying...
            group
                .0
                .iter()
                .filter(|c| group.1.contains(c))
                .filter(|c| group.2.contains(c))
                .next()
                .unwrap()
        })
        .map(find_char_score)
        .sum()
}

fn seperate_groups(input: &[Rucksack]) -> Vec<Group> {
    let mut output: Vec<Group> = Vec::new();
    for group in input.chunks_exact(3) {
        output.push(Group(
            group[0].0.union(&group[0].1).copied().collect(),
            group[1].0.union(&group[1].1).copied().collect(),
            group[2].0.union(&group[2].1).copied().collect(),
        ));
    }
    output
}

3 votes

bhrgunatha
December 3, 2022
Link Parent
I remember an exercise to extend mergesort to multiple arrays. Many people used a priority queue, but my approach was much like mergesort itself, recursively break down the arrays into 2 halves....

intersection of more than one other hashset at a time

I remember an exercise to extend mergesort to multiple arrays. Many people used a priority queue, but my approach was much like mergesort itself, recursively break down the arrays into 2 halves. When one half was a single array or 2 arrays, use mergesort and return the result back up the stack.

I think it would work for set intersection too.

1 vote
[3]
DataWraith
December 3, 2022
Link Parent
I thought this would be nicely doable using reduce, but it turns out that that solution is far from elegant. Reduce multiple HashSets use std::collections::HashSet; fn main() { let a =...
I really wish rusts HashSet implentation allowed finding the intersection of more than one other hashset at a time...

I thought this would be nicely doable using reduce, but it turns out that that solution is far from elegant.
Reduce multiple HashSets

use std::collections::HashSet; fn main() { let a = HashSet::from([1, 2, 3]); let b = HashSet::from([1, 3, 4]); let c = HashSet::from([1, 4, 5]); let d = HashSet::from([1, 2, 7]); println!("{:?}", [a, b, c, d].into_iter().reduce(|a, b| a.intersection(&b).map(|x| *x).collect())); }
1 vote
1. Liru
  December 3, 2022
  Link Parent
  It's actually not that bad; no type wrasslin', no weird methods or anything like that. (One thing I'd change is using copied() instead of map(|x| *x), but it's practically the same thing.)
  
  It's actually not that bad; no type wrasslin', no weird methods or anything like that. (One thing I'd change is using copied() instead of map(|x| *x), but it's practically the same thing.)
  
  2 votes
2. Toric
  December 4, 2022
  Link Parent
  thats actually pretty clever...
  
  thats actually pretty clever...
  
  1 vote

asterisk

December 3, 2022

Link

Python import string from collections import Counter from functools import reduce from operator import and_ insert = open("input.txt").read().split() def reorganization(length: int, count: int =...

Python

import string
from collections import Counter
from functools import reduce
from operator import and_

insert = open("input.txt").read().split()


def reorganization(length: int, count: int = 1) -> int:
    priorities: int = 0

    for line in range(0, len(insert) - count + 1, count):
        parts = list()

        for n in range(count):
            l = len(insert[line + n]) // length

            for div in range(0, len(insert[line + n]), l):
                parts.append(Counter(insert[line + n][div : div + l]))

        item = list(reduce(and_, parts).elements())[0]
        priorities += string.ascii_letters.index(item) + 1

    return priorities


print(reorganization(2))  # Part One: 7889
print(reorganization(1, 3))  # Part Two: 2825

3 votes

Crespyl

December 4, 2022

Link

Sets! Clojure (both parts) (defn priority [ch] (+ 1 (str/index-of "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" ch))) (defn parse-line [line] (let [len (count line) split (/ len 2)...

Sets!

Clojure (both parts)

(defn priority [ch]
  (+ 1 (str/index-of
        "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
        ch)))

(defn parse-line [line]
  (let [len (count line)
        split (/ len 2)
        compartment-1 (subs line 0 split)
        compartment-2 (subs line split)]
    (map set [compartment-1 compartment-2])))

(defn shared-item [sack]
  (let [c1 (first sack)
        c2 (second sack)]
    (clojure.set/intersection c1 c2)))

(defn part-1 [input]
  (let [sacks (map parse-line input)]
    (->> sacks
        (map shared-item)
        (map first)
        (map priority)
        (reduce +))
    ))

(defn part-2 [input]
  (let [sacks (map set input)]
    (->> sacks
         (partition 3)
         (map #(apply clojure.set/intersection %))
         (map first)
         (map priority)
         (reduce +))))

3 votes

balooga

December 4, 2022

Link

Here's my TypeScript solution type InputData = [string, string][]; function formatInput(input: string): InputData { return input.split('\n').map(e => [e.slice(0, e.length / 2), e.slice(e.length /...

Here's my TypeScript solution

type InputData = [string, string][];

function formatInput(input: string): InputData {
  return input.split('\n').map(e => [e.slice(0, e.length / 2), e.slice(e.length / 2, e.length)]);
}

export function run(input: string): string[] {
  const data = formatInput(input);

  const priorities = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';

Part 1

  const getSumOfPriorities = (rucksacks: InputData): number => {
    let sum = 0;
    for (const rucksack of rucksacks) {
      for (let i = 0; i < rucksack[0].length; i++) {
        if (rucksack[1].includes(rucksack[0][i])) {
          sum += priorities.indexOf(rucksack[0][i]) + 1;
          break;
        }
      }
    }
    return sum;
  };

Part 2

  const getSumOfBadgePriorities = (rucksacks: InputData): number => {
    let sum = 0;
    for (let i = 0; i < rucksacks.length; i += 3) {
      const group = [rucksacks[i], rucksacks[i + 1], rucksacks[i + 2]].sort((a, b) => a[0].length - b[0].length);
      for (let j = 0; j < group[0][0].length * 2; j++) {
        const item = `${group[0][0]}${group[0][1]}`.charAt(j);
        if (`${group[1][0]}${group[1][1]}`.includes(item) && `${group[2][0]}${group[2][1]}`.includes(item)) {
          sum += priorities.indexOf(item) + 1;
          break;
        }
      }
    }
    return sum;
  };

  return [`${getSumOfPriorities(data)}`, `${getSumOfBadgePriorities(data)}`];
}

3 votes

tomf

December 3, 2022 (edited December 3, 2022)

Link

These are both very similar. Another nice one for the sheetheads out there. Minor details in each. 7117/9122 Part 1 Basically, this is splitting the cell in half and adding L or R to each side...

These are both very similar. Another nice one for the sheetheads out there. Minor details in each. 7117/9122

Part 1

Basically, this is splitting the cell in half and adding L or R to each side along with the row number. From there I split by the diamond and flatten it. Once I have stuff like 2|L|p I run UNIQUE on it so each group is cleansed of its dupes. Then I split again by the pipe and run the first QUERY. The second QUERY is a quick and dirty cleanup.

Lastly, the VLOOKUP uses CODE for the letters, since VLOOKUP is case agnostic. CODE, as you guessed it, gives me the unicode map value.. and the rest is the VLOOKUP.

The SEQUENCEs at the end are generating code tables to convert the codes to the 1-52 values. I was doing it straight CODE(..)-x but that doesn't work as nicely for this.

=ARRAYFORMULA(
  IF(C2=FALSE,,
   SUM(
    IFERROR(
     VLOOKUP(
      CODE(
       QUERY(
        QUERY(
         UNIQUE(
          SPLIT(
           FLATTEN(
            IF(ISBLANK(A2:A),,
             SPLIT(
              REGEXREPLACE(LEFT(A2:A,LEN(A2:A)/2),"(.)",ROW(A2:A)&"|L|$1💎")&
              REGEXREPLACE(RIGHT(A2:A,LEN(A2:A)/2),"(.)",ROW(A2:A)&"|R|$1💎"),
              "💎",TRUE,FALSE))),
           "|")),
         "select Col1, Col3, Count(Col1)
          where Col3 is not null
          group by Col1, Col3
          label Count(Col1) ''"),
        "select Col2
         where Col3 = 2")),
      {{SEQUENCE(26,1,97);
        SEQUENCE(26,1,65)},
       SEQUENCE(52)},
      2,FALSE)))))

Part 2

More of this trash, but this time instead of L and R for sets, I have `ROUNDUP((ROW(A2:A)-1)/3)` to get sets of three (1,2,3 round down to 1.. etc)

Nothing crazy, just longer than I want it to be.

=ARRAYFORMULA(
  IF(C2=FALSE,,
   SUM(
    IFERROR(
     VLOOKUP(
      CODE(
       QUERY(
        QUERY(
         UNIQUE(
          IFERROR(
           SPLIT(
            FLATTEN(
             IF(ISBLANK(A2:A),,
              ROW(A2:A)&"|"&ROUNDUP((ROW(A2:A)-1)/3)&"|"&
              SPLIT(
               REGEXREPLACE(A2:A,"(.)","$1|"),
               "|"))),
            "|"))),
          "select Col2, Col3, Count(Col1)
           where Col3 is not null
           group by Col2, Col3 label Count(Col1) ''"),
        "select Col1, Col2
         where Col3 >= 3")),
      {{SEQUENCE(26,1,97);
        SEQUENCE(26,1,65)},
       SEQUENCE(52)},
      2,FALSE)))))

2 votes

MeckiSpaghetti

December 3, 2022 (edited December 3, 2022)

Link

Ruby Part 1 sum = File .read("input.txt") .split("\n") .map{ |l| [l[...l.size/2], l[l.size/2..]] } .map{ |a, b| a.chars & b.chars } .flatten .map{ |a| (a.ord-38) % 58 } .sum p sum Part 2 sum =...

Ruby

Part 1

sum = File
         .read("input.txt")
         .split("\n")
         .map{ |l| [l[...l.size/2], l[l.size/2..]] }
         .map{ |a, b| a.chars & b.chars }
         .flatten 
         .map{ |a| (a.ord-38) % 58 }
         .sum
         
p sum

Part 2

sum = File
         .read("input.txt")
         .split("\n")
         .each_slice(3)
         .map{ |a, b, c| a.chars & b.chars & c.chars }
         .flatten 
         .map{ |a| (a.ord-38) % 58 }
         .sum
         
p sum

2 votes

Crestwave

December 3, 2022

Link

Neat one. Part 1 #!/usr/bin/awk -f { split("", items) types = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" len = length($0) for (i = 1; i <= len; ++i) { c = substr($0, i, 1) if (i < len...

Neat one.

Part 1

#!/usr/bin/awk -f
{
	split("", items)
	types = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
	len = length($0)

	for (i = 1; i <= len; ++i) {
		c = substr($0, i, 1)
		if (i < len / 2 + 1) {
			items[c] = 1
		} else if (items[c]) {
			sum += match(types, c)
			next
		}
	}
}

END { print(sum) }

Part 2

#!/usr/bin/awk -f
{
	group = ((NR - 1) % 3) + 1
	types = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
	len = length($0)

	if (group == 1)
		split("", items)

	for (i = 1; i <= len; ++i) {
		c = substr($0, i, 1)
		if (items[c] == group - 1) {
			items[c] = group
			if (group == 3)
				sum += match(types, c)
		}
	}
}

END { print(sum) }

2 votes

Gyrfalcon

December 3, 2022

Link

Happy with how this turned out, though I think I learned that I need to find a more elegant way to interact with Python's Set, especially given how handy I find it in general. Parts 1 and 2 import...

Happy with how this turned out, though I think I learned that I need to find a more elegant way to interact with Python's Set, especially given how handy I find it in general.

Parts 1 and 2

import os
from typing import Tuple
from string import ascii_lowercase, ascii_uppercase
from aoc2022.common import load_file

current_dir = os.path.realpath(os.path.dirname(__file__))
INPUT_FILE = "/".join([current_dir, "input.txt"])
TEST_FILE_1 = "/".join([current_dir, "test1.txt"])
TEST_RESULTS_1 = (157, 70)

priorities = {
    character: priority + 1 for priority, character in enumerate(ascii_lowercase)
}
priorities.update(
    {character: priority + 27 for priority, character in enumerate(ascii_uppercase)}
)


def compartment_commonality(rucksack: str) -> str:
    compartment_1 = set(rucksack[: len(rucksack) // 2])
    compartment_2 = set(rucksack[len(rucksack) // 2 :])
    return compartment_1.intersection(compartment_2).pop()


def generate_groups(rucksacks: list[str]) -> list[list[str]]:
    grouped = []
    for idx in range(0, len(rucksacks), 3):
        grouped.append(rucksacks[idx : idx + 3])

    return grouped


def find_badge(rucksacks: list[str]) -> str:
    sets = [set(rucksack) for rucksack in rucksacks]
    return sets[0].intersection(*sets).pop()


def main(filepath: str) -> Tuple[int, int]:
    rucksacks = load_file.load_cleaned_lines(filepath)
    common_items = map(compartment_commonality, rucksacks)

    groups = generate_groups(rucksacks)
    badges = map(find_badge, groups)

    return (
        sum((priorities[item] for item in common_items)),
        sum((priorities[badge] for badge in badges)),
    )


if __name__ == "__main__":
    part1, part2 = main(INPUT_FILE)

    print(part1)
    print(part2)

2 votes

kari

December 3, 2022

Link

I enjoyed today! Nim (both parts) I think there's a better way for me to get the single item left after the intersections than popping, but I can't figure it out import std/[sets, sequtils,...

I enjoyed today!

Nim (both parts)

I think there's a better way for me to get the single item left after the intersections than popping, but I can't figure it out

import std/[sets, sequtils, strutils]

proc getPriority(item: char): int =
  # We want a-z to be 1-26
  # and A-Z to be 27-52
  if item.isLowerAscii():
    return ord(item) - 96 # ord('a') == 97
  else:
    return ord(item) - 38 # ord('A') == 65

  # Just in case, but everything *should* be upper or lowercase letters
  return 0

proc day03*() =
  var
    prioritySumP1 = 0
    prioritySumP2 = 0

  var rucksacks = lines("inputs/day03.in").toSeq()
  for line in rucksacks:
    let midPoint = int(line.len / 2)
    let compartmentOne = line[0 ..< midPoint].toHashSet()
    let compartmentTwo = line[midPoint .. ^1].toHashSet()
    # easy way to get the one mismatched item
    var itemSet = (compartmentOne * compartmentTwo)
    let item = itemSet.pop()

    prioritySumP1 += getPriority(item)

  while rucksacks.len() > 0:
    let rucksackOne = rucksacks.pop().toHashSet()
    let rucksackTwo = rucksacks.pop().toHashSet()
    let rucksackThree = rucksacks.pop().toHashSet()

    var itemSet = (rucksackOne * rucksackTwo * rucksackThree)
    let item = itemSet.pop()

    prioritySumP2 += getPriority(item)

  echo "Part 1: " & $prioritySumP1
  echo "Part 2: " & $prioritySumP2

2 votes

[4]

soks_n_sandals

December 3, 2022

Link

I found today to be quite difficult with bash. Would love some feedback if anyone has any, particularly on how to make these faster. Part 1+2 Part 1: we split the line into two even sections,...

I found today to be quite difficult with bash. Would love some feedback if anyone has any, particularly on how to make these faster.

Part 1+2

Part 1: we split the line into two even sections, separate each character, with a newline, sort it. We compare the sorted lines. Then, we convert the letter to a number with printf and add it on to our sum.

Part 2: the same, except we don't split the line into two sections and we do two comparisons of the sorted lines.

#!/usr/bin/env bash

file=day3.dat
part=2
str=$(echo {a..z} | tr -d ' ')
sum=0

if [[ ${part} -eq 1 ]]; then
# /////////////////////////////////////////////////////////////////////////////
#part 1 ~3.5s // 8252

while read -r line || [[ -n ${line} ]]; do
# /////////////////////////////////////////////////////////////////////////////
# echo ${line:0:${#line}/2} === ${line:${#line}/2}
#   -- get the string into an array
firstArr=$(fold -w1<<<${line:0:${#line}/2}) #fold works here bc sort needs newlines
secondArr=$(fold -w1<<<${line:${#line}/2}) #could use sed 's/./&\n/g'<<<$sring

firstArrSortUniq=$(sort -u <<<$firstArr)
secondArrSortUniq=$(sort -u <<<$secondArr)

# commonLetter=$(comm -1 -2 <(echo "$firstArrSortUniq") <(echo "$secondArrSortUniq"))
commonLetter=$(grep -o "$firstArrSortUniq" <<< "$secondArrSortUniq")

if [[  $str =~ "$commonLetter" ]]; then
    upCase=$(tr [:lower:] [:upper:]<<<$commonLetter)
    val=$(printf "%d" "'$upCase")
    ((val = val - 64))
    (( sum = val + sum))
else
    val=$(printf "%d" "'$commonLetter")
    ((val = val - 38))
    (( sum = val + sum))
fi

done < $file
echo Part A: $sum
# /////////////////////////////////////////////////////////////////////////////
fi

if [[ ${part} -eq 2 ]]; then
# /////////////////////////////////////////////////////////////////////////////
#part 2 2.26s // 2828
wholeFile=($(cat $file))
i=0
while [[ $i -lt ${#wholeFile[@]} ]]; do

    firstArr=$(fold -w1<<<${wholeFile[$i]}) #fold works here bc sort needs newlines
    firstArrSortUniq=$(sort -u <<<$firstArr)
    secondArr=$(fold -w1<<<${wholeFile[$i+1]}) #fold works here bc sort needs newlines
    secondArrSortUniq=$(sort -u <<<$secondArr)
    thirdArr=$(fold -w1<<<${wholeFile[$i+2]}) #fold works here bc sort needs newlines
    thirdArrSortUniq=$(sort -u <<<$thirdArr)

    commonLetter1=$(grep -o "$firstArrSortUniq" <<< "$secondArrSortUniq")
    commonLetter2=$(grep -o "$thirdArrSortUniq" <<< "$commonLetter1") #can also use comm command here: comm -1 -2 <($firstArrSortUniq) <$(secondArrSortUniq)

    if [[  $str =~ "$commonLetter2" ]]; then
        upCase=$(tr [:lower:] [:upper:]<<<$commonLetter2)
        val=$(printf "%d" "'$upCase")
        ((val = val - 64))
        (( sum = val + sum))
    else
        val=$(printf "%d" "'$commonLetter2")
        ((val = val - 38))
        (( sum = val + sum))
    fi


    ((i = i + 3))
done
echo Part A: $sum

# /////////////////////////////////////////////////////////////////////////////
fi

2 votes

[3]
Crestwave
December 4, 2022 (edited December 4, 2022)
Link Parent
Have you read the Pure Bash Bible? Although external commands may be fast at processing data, it is significantly more efficient to use builtins for small changes because you avoid the fork and...
Have you read the Pure Bash Bible? Although external commands may be fast at processing data, it is significantly more efficient to use builtins for small changes because you avoid the fork and startup time. Especially when you would otherwise use command substitution and piping, as those are already costly by themselves.

Some examples of simple substitutions you could make are printf -v str %s {a..z} instead of str=$(echo {a..z} | tr -d ' ' and upCase=${commonLetter^} instead of upCase=$(tr [:lower:] [:upper:]<<<$commonLetter).

Beyond that, you can get creative with Bash's builtins and solve them in a completely different way. This may be a bit too arcane, but here's how I would solve it:
Part 1

#!/usr/bin/env bash while read -r line; do a=${line::${#line}/2} b=${line:${#line}/2} c=${a//["${a//["$b"]}"]} c=${c::1} printf -v val %d "'$c" # alternatively, use a [[ $c =~ [[:lower:]] ]] check (( val -= (val >= 97 ? 96 : 38))) (( sum += val )) done <"$1" printf '%s\n' "$sum"
Part 2

#!/usr/bin/env bash mapfile -t lines <"$1" for (( i = 0; i < ${#lines[@]}; i += 3 )); do a=${lines[i]} b=${lines[i+1]} c=${lines[i+2]} d=${a//["${a//["$b"]}"]} d=${c//["${c//["$d"]}"]} d=${d::1} printf -v val %d "'$d" (( val -= (val >= 97 ? 96 : 38))) (( sum += val )) done printf '%s\n' "$sum"
Both of these execute in ~0.010s on my machine. But if you want a more straightforward way to find the common letters, you can use Bash's associative arrays to do something like my AWK solution.

EDIT - One easier method for part 1:
Part 1

#!/usr/bin/env bash while read -r line; do a=${line::${#line}/2} b=${line:${#line}/2} [[ $a =~ [$b] ]] c=${BASH_REMATCH[0]} printf -v val %d "'$c" (( val -= (val >= 97 ? 96 : 38))) (( sum += val )) done <"$1" printf '%s\n' "$sum"
3 votes
1. [2]
  soks_n_sandals
  December 4, 2022
  Link Parent
  Thank you very much for taking the time to write these up. They run ~0.05s on my system, so about 100x faster than my solutions! I'd never seen that github page. It helped me find this resource...
  
  Thank you very much for taking the time to write these up. They run ~0.05s on my system, so about 100x faster than my solutions! I'd never seen that github page. It helped me find this resource too, so thanks for that!
  
  I've broken out the assignment used in Part 1 to help myself understand them. I'm wondering why the expansion of ["$b"] with brackets works, but leaving the brackets off doesn't?
  
  see this snippet
  
  a=${line::${#line}/2} b=${line:${#line}/2} # ${string//substring/replacement} # Replace all matches of $substring with $replacement. c=${a//[$b]/+} #no replacement, so we just delete. The bracket is a builtin to expand the variable. d=${a//$b} #doesn't work echo $c echo $d echo good substitution $c echo failed substitution $d ------------ good substitution ++gJ+RGJ failed substitution ttgJtRGJ
  
  I'll note that your second solution to Part 1 is 0.009s on my system, so an even better speedup. Thanks again for giving me these tips.
  
  1 vote
  1. Crestwave
    December 5, 2022
    Link Parent
    No problem, Bash is always fun to hack on. The brackets denote a regex character class (e.g., [0-9]) that matches any character in $b.
    
    No problem, Bash is always fun to hack on. The brackets denote a regex character class (e.g., [0-9]) that matches any character in $b.
    
    2 votes

vord

December 5, 2022

Link

Late to the party, saved them for the workday. Feeling much better than Day 2. I abstracted better, so part 2 was not nearly as painful. Typescript (both parts) import * as fs from...

Late to the party, saved them for the workday. Feeling much better than Day 2. I abstracted better, so part 2 was not nearly as painful.

Typescript (both parts)

import * as fs from 'node:fs/promises';

function allEqual(array: string[]): boolean {
	return array.every(a => { if (a == array[0]) {
								return  true;
							} }
						);
};

function findBadItemType(pack: number[][]): number {
	// 0 is left pack, 1 is right pack
	for (let item of pack[0]) {
		if (pack[1].includes(item)) {
			return item;
		}
	}
	//If no bad items are found, return 0
	return 0;
};

function convertPriority(pack: string): number[][] {
	let left_side: number[] = [];
	let right_side: number[] = [];
	
	for (let x=0; x < pack.length; x++) {
		let priority = pack.charCodeAt(x);

		// A charCode = 65, but priority = 27
		// a charCode = 97, but priority = 1

		if (priority < 97) {
			priority = priority - 38;
		} else {
			priority = priority - 96;
		};

		if (x < pack.length/2){
			left_side.push(priority);
		} else {
			right_side.push(priority);
		}
	}

	return [left_side,right_side];
};

function isInAll(x: number, array1: number[], array2: number[]): boolean {
	if(array1.includes(x) && array2.includes(x)){
		return true;
	}
	return false;
};

function groupElves(packs: number[][][]): number[] {
	let groups: number[] = [];
	
	for (let group = 0;group < packs.length-2; group += 3) {
		let elf_1: number[] = packs[group].flat();
		let elf_2: number[] = packs[group+1].flat();
		let elf_3: number[] = packs[group+2].flat();

		// Default null to -1
		let badge: number = elf_1.find(element => isInAll(element, elf_2,elf_3)) ?? -1;
		groups.push(badge);
	};
	return groups;
};

async function main(): Promise<void> {
	const file = await fs.readFile("input/day3","utf-8");

	let rucksacks = file.split("\n");
	
	let converted_rucksacks: number[][][] =
				rucksacks.map((pack: string,index: number): number[][] =>
									convertPriority(pack));
	
	// Part 1
	let bad_items: number[] =
		converted_rucksacks.map((pack: number[][], index: number): number =>
							findBadItemType(pack));
	
	let total_bad_priorities: number = 
				bad_items.reduce((total: number, item: number) => total + item,0);

	// Part 2
	let elf_groups: number[] = groupElves(converted_rucksacks);

	let total_badge_priorities: number = 
				elf_groups.reduce((total: number, item: number) => total + item,0);

	console.log("Total Bad Priorities: ",total_bad_priorities);
	console.log("Total Badge Priorities: ",total_badge_priorities);
};

await main();

1 vote

whispersilk

December 6, 2022

Link

I'm using Rust this year, and trying to keep it std-only throughout the month. I had a lot of fun using a bitset for this one. Part 1 use std::error::Error; use std::fs::File; use std::io::Read;...

I'm using Rust this year, and trying to keep it std-only throughout the month.

I had a lot of fun using a bitset for this one.

Part 1

use std::error::Error;
use std::fs::File;
use std::io::Read;

fn main() -> Result<(), Box<dyn Error>> {
	let mut file = File::open("input_3.txt")?;
	let mut contents = String::new();
	file.read_to_string(&mut contents)?;
	let total_overlap_priority = contents.lines().fold(0, |acc, line| {
		let line_len = line.len();
		let first = &line[0..line_len / 2];
		let second = &line[line_len / 2..];
		let first_set = first.chars().fold(0, |acc, x| acc | priority(x));
		let second_set = second.chars().fold(0, |acc, x| acc | priority(x));
		let overlap = first_set & second_set;
		acc + overlap_priority(overlap)
	});
	println!("{total_overlap_priority}");
	Ok(())
}

// Returns a u64 with the Xth bit set, where X is the char's priority
fn priority(c: char) -> u64 {
	if c >= 'A' && c <= 'Z' {
		1 << (26 + (c as u8 - 'A' as u8))
	} else if c >= 'a' && c <= 'z' {
		 1 << (c as u8 - 'a' as u8)
	} else {
		0
	}
}

fn overlap_priority(overlap: u64) -> u64 {
	assert!(overlap & overlap - 1 == 0);
	let mut n = overlap;
	let mut priority = 1;
	while n > 1 {
		priority += 1;
		n = n >> 1;
	}
	priority
}

Part 2

use std::error::Error;
use std::fs::File;
use std::io::Read;

fn main() -> Result<(), Box<dyn Error>> {
	let mut file = File::open("input_3.txt")?;
	let mut contents = String::new();
	file.read_to_string(&mut contents)?;
	let mut inventory_sets = contents.lines()
		.map(|line| line.chars().fold(0, |acc, x| acc | priority(x)))
		.peekable();
	let mut badge_sum = 0;
	while inventory_sets.peek().is_some() {
		let first = inventory_sets.next().unwrap();
		let second = inventory_sets.next().unwrap();
		let third = inventory_sets.next().unwrap();
		let overlap = first & second & third;
		badge_sum += overlap_priority(overlap);
	}
	println!("{badge_sum}");
	Ok(())
}

// Returns a u64 with the Xth bit set, where X is the char's priority
fn priority(c: char) -> u64 {
	if c >= 'A' && c <= 'Z' {
		1 << (26 + (c as u8 - 'A' as u8))
	} else if c >= 'a' && c <= 'z' {
		 1 << (c as u8 - 'a' as u8)
	} else {
		0
	}
}

fn overlap_priority(overlap: u64) -> u64 {
	assert!(overlap & overlap - 1 == 0);
	let mut n = overlap;
	let mut priority = 1;
	while n > 1 {
		priority += 1;
		n = n >> 1;
	}
	priority
}

1 vote

Today's problem description: https://adventofcode.com/2022/day/3

28 comments