Advent of Code

[nezzcarth]

@narpfel:
Das automatische Erzeugen der Sonderfälle war auch schnell umgesetzt. Für die B-Note. Oder so.

[Manul]

Ich hätte bei den Sonderfällen (wenn ich drauf gekommen wäre) wahrscheinlich das Gefühl gehabt, noch drüber nachdenken zu müssen, ob ich direkt aneinandergereihte extra bedenken muss (eher nicht). Ich hab's dann auch eher hemdsärmlig mit diesem Konstrukt gelöst:

Code: Alles auswählen

WORDS_TO_DIGITS = {
  'zero':   '0ero',
  'one':    '1ne',
  'two':    '2wo',
  'three':  '3hree',
  'four':   '4our',
  'five':   '5ive',
  'six':    '6ix',
  'seven':  '7even',
  'eight':  '8ight',
  'nine':   '9ine'
}

Sooft ersetzen, bis sich nichts mehr tut, und dann den Einzeiler aus Teil 1 drauf loslassen. Das Konstrukt hätte man (für die B-Note ) natürlich auch noch programmatisch erzeugen können.

[ThomasL]

Nachdem mein erster Code für Teil 2 glücklicherweise für die Beispieldaten schon ein falsches Ergebnis ausgab, konnte ich durch Anpassung der Liste pairs das Problem schnell lösen.

Code: Alles auswählen

# Part 1
summe = lambda f : sum(int(f'{num[0]}{num[-1]}') 
                        for num in [''.join(ch for ch in line if ch.isdigit()) 
                                    for line in f])
print(f'Part 1: {summe(open("input.txt"))}')

# Part 2
pairs = [('one','o1e'), ('two','t2o'), ('three','t3e'), ('four','4'), ('five','5e'), ('six','6'), ('seven','7n'), ('eight','8'), ('nine','9')]
    
numbers = []
for line in open("input.txt"):
    for k, v in pairs:
        line = line.replace(k, v)
    numbers.append(line)

print(f'Part 2: {summe(numbers)}')

[snafu]

Iiih, in Aufgabenteil zwei von Tag 1 2023 ist eine kleine Falle drin, in die ich getappt bin, die in den Testdaten nicht vorkam, in meinen persönlichen Eingabedaten aber schon. In den Testdaten ist aber trotzdem ein Hinweis.

Geht mir gerade ähnlich. Ich weiß nicht, was passieren soll, wenn in einer Zeile nur eine anstatt zwei Ziffern enthalten sind.

[snafu]

Habe mittlerweile auch beide Parts gelöst. Den Lookahead-Trick nutze ich dabei mit re.finditer(). Somit spare ich mir die quadratische Laufzeit bei den Textersetzungen.

Code: Alles auswählen

import re

INPUT_PATH = "input1.txt"

DIGIT_WORDS = (
    "one two three four five six seven eight nine"
).split()

WORD_MAP = {
    word: str(i) for i, word
    in enumerate(DIGIT_WORDS, 1)
}

TOKEN_PATTERN = re.compile(
    rf"(\d)|(?=({'|'.join(DIGIT_WORDS)}))"
)


def get_digit_chars(line):
    matches = TOKEN_PATTERN.finditer(line)
    return [
        m.group(1) if m.group(1)
        else WORD_MAP[m.group(2)]
        for m in matches
    ]


def parse_number(line):
    digits = get_digit_chars(line)
    return int(digits[0] + digits[-1])


def main():
    with open(INPUT_PATH) as stream:
        numbers = [
            parse_number(line)
            for line in stream
        ]
    print(sum(numbers))


if __name__ == "__main__":
    main()

[Manul]

Heute bin ich in Teil 1 darüber gestolpert daß ich die Aufgabenstellung zu flüchtig gelesen hatte. Witzigerweise hat der Code, den ich daraufhin zum Debuggen eingebaut habe, dann fast automatisch die Lösung für Teil 2 geliefert.

[grubenfox]

Iiih, in Aufgabenteil zwei von Tag 1 2023 ist eine kleine Falle drin, in die ich getappt bin, die in den Testdaten nicht vorkam, in meinen persönlichen Eingabedaten aber schon. In den Testdaten ist aber trotzdem ein Hinweis.

Geht mir gerade ähnlich. Ich weiß nicht, was passieren soll, wenn in einer Zeile nur eine anstatt zwei Ziffern enthalten sind.

Da hing ich auch kurz, aber da war das letzte Beispiel aus dem ersten Teil die (Auf-)lösung.

Habe mittlerweile auch beide Parts gelöst. Den Lookahead-Trick nutze ich dabei mit re.finditer(). Somit spare ich mir die quadratische Laufzeit bei den Textersetzungen.

Was haben es die Leute eigentlich alle mit regulären Ausdrücken und Textersetzungen? Es war doch nur einfaches suchen angesagt...

Code: Alles auswählen

TRANSFORM2 ={
'one' : 1,
'two' : 2,
'three' : 3,
'four' : 4,
'five' : 5,
'six' : 6,
'seven' : 7,
'eight' : 8,
'nine' : 9,
'1' : 1,
'2' : 2,
'3' : 3,
'4' : 4,
'5' : 5,
'6' : 6,
'7' : 7,
'8' : 8,
'9' : 9,
}

def wert(zeichenkette, transform):
    pos = len(zeichenkette)+1
    zehner = 0
    for k,v in transform.items():
        try:
            if zeichenkette.index(k) < pos:
                pos = zeichenkette.index(k)
                zehner = v
        except ValueError:
                pass
    pos = -1
    einer = 0
    for k,v in transform.items():
        if zeichenkette.rfind(k) > pos:
            pos = zeichenkette.rfind(k)
            einer = v

    return 10*zehner+einer

def main():
    with open('aoc_2023_01a.txt') as datei:
        summe = 0
        for zeile in datei:
            summe += wert5(zeile, TRANSFORM2)

    print('Ergebnis Stufe 2:', summe)


if __name__ == "__main__":
    main()

[snafu]

Hab bei Tag 2 nun auch beide Parts durch. Ich fand den heutigen Tag sogar leichter als den Tag 1, insbesondere den zweiten Teil. Die in Python naheliegende Datenstruktur pro Spiel machte die Lösung recht simpel. Nur beim Parsen musste ich erst ein bisschen überlegen. Weniger über die benötige Methode, sondern vielmehr wegen der Struktur der Schleifen. Das Parsen der Game ID konnte ich weglassen, weil das auch mit enumerate() ging. Dann ist mir aufgefallen, dass ich pro Spiel ja eigentlich nur ein Dict brauche und so ist der Code dann schon etwas zusammengeschrumpft. Mit dieser Erkenntnis war dann wie gesagt auch Part 2 nicht mehr wirklich schwer.

[snafu]

Iiih, in Aufgabenteil zwei von Tag 1 2023 ist eine kleine Falle drin, in die ich getappt bin, die in den Testdaten nicht vorkam, in meinen persönlichen Eingabedaten aber schon. In den Testdaten ist aber trotzdem ein Hinweis.

Geht mir gerade ähnlich. Ich weiß nicht, was passieren soll, wenn in einer Zeile nur eine anstatt zwei Ziffern enthalten sind.

Da hing ich auch kurz, aber da war das letzte Beispiel aus dem ersten Teil die (Auf-)lösung.

Mir ist nach dem Posten aufgefallen, dass ich diese Frage "versehentlich" schon durch Lösen von Part 1 beantwortet hatte. Das konnte ich somit als Ursache für die Abweichung ausschließen.

Habe mittlerweile auch beide Parts gelöst. Den Lookahead-Trick nutze ich dabei mit re.finditer(). Somit spare ich mir die quadratische Laufzeit bei den Textersetzungen.

Was haben es die Leute eigentlich alle mit regulären Ausdrücken und Textersetzungen? Es war doch nur einfaches suchen angesagt...

Dein Code beantwortet das IMHO ganz gut. Lieber ein knackiger regulärer Ausdruck als zig Mal den selben Text zu durchsuchen und dazu viel mehr Zeilen Quelltext zu benötigen. Prinzipiell lässt sich jedes Regex-Problem auch mit Boardmitteln lösen und niemand ist gezwungen, reguläre Ausdrücke zu verwenden. Wenn man im Lesen und Formulieren dieser Ausdrücke aber einigermaßen geübt ist, greift man gerne danach (sofern es einen sichtbaren Vorteil mit sich bringt).

BTW: Kann es sein, dass du gerade im Studium bist oder irgendeinen Informatik-Grundkurs belegst? Dieses ``x*10 + einer`` erinnert stark an meine damalige Zeit dort und ich vermute, da wird sich in den Jahren nicht so viel verändert haben.

BTW2: Warum nutzt man List Comprehensions und sum()? Geht doch in Pascal oder Basic auch ganz wunderbar...

[__blackjack__]

Insbesondere ist der reguläre Ausdruck, zumindest wenn man `regex` benutzt, ja auch total einfach und verständlich.

Code: Alles auswählen

#!/usr/bin/env python3
# AoC 2023, day 1
import sys

import regex as re

TEST_LINES_A = """\
1abc2
pqr3stu8vwx
a1b2c3d4e5f
treb7uchet
""".splitlines()

TEST_LINES_B = """\
two1nine
eightwothree
abcone2threexyz
xtwone3four
4nineeightseven2
zoneight234
7pqrstsixteen
""".splitlines()

DIGIT_RE = re.compile(r"\d|one|two|three|four|five|six|seven|eight|nine")
WORD_TO_DIGIT = {
    word: str(value) for value, word in enumerate(DIGIT_RE.pattern.split("|"))
}


def get_number_a(line):
    """
    >>> list(map(get_number_a, TEST_LINES_A))
    [12, 38, 15, 77]
    """
    digits = [character for character in line if character.isdigit()]
    return int(digits[0] + digits[-1])


def get_digit(text):
    return WORD_TO_DIGIT.get(text, text)


def get_number_b(line):
    """
    >>> list(map(get_number_b, TEST_LINES_B))
    [29, 83, 13, 24, 42, 14, 76]
    """
    digits = DIGIT_RE.findall(line, overlapped=True)
    return int(get_digit(digits[0]) + get_digit(digits[-1]))


def main():
    lines = list(sys.stdin)
    for get_number in [get_number_a, get_number_b]:
        print(sum(map(get_number, lines)))


if __name__ == "__main__":
    main()

[kbr]

Ich werfe hier mal im Nachgang für Tag 1 Teil 2 eine Lösung in den Raum, die ohne Reguläre Ausdrücke auskommt und mit weißem Gürtel zu bewältigen ist. Von oben nach unten quick und dirty runtergeschrieben sowie ohne Laufzeitoptimierung bedarf es nur `.startswith()`:

Code: Alles auswählen

import itertools

patterns = [
'one',
'two',
'three',
'four',
'five',
'six',
'seven',
'eight',
'nine'
]
rpatterns = [p[::-1] for p in patterns]
digits = list(map(str, range(1, 10)))
patterns += digits
str_to_num = {s: n for s, n in zip(patterns + rpatterns, itertools.cycle(list(range(1, 10))))}
rpatterns += digits

def find_first(line, patterns=patterns):
    while line:
        for p in patterns:
            if line.startswith(p):
                return str_to_num[p]
        line = line[1:]
    raise ValueError("no pattern found")

def find_last(line):
    line = line[::-1]
    return find_first(line, rpatterns)

fname = "input.txt"

with open(fname) as fobj:
    summe = 0
    for line in fobj:
        line = line.strip()
        first = find_first(line)
        last = find_last(line)
        summe += int(f"{first}{last}")

print(summe)
 

[snafu]

@kbr: Auch wenn das bei heutigen Rechnern und angesichts der wenigen Daten keinen spürbaren Unterschied macht, aber deine Lösung ist ziemlich suboptimal. Allein schon das ständige Umkopieren des nahezu kompletten Strings, nur um ein Zeichen vorzurücken, stellt auch bei Quick & Dirty Code in meinen Augen ein absolutes NoGo dar.

[kbr]

@snafu: Mit so einer Antwort hatte ich gerechnet – deswegen ja auch der Hinweis auf quick and dirty und nicht zuletzt auch der Laufteit. Diese ist mit ca. 6 ms auf meinem Rechner zur Lösung der Aufgabe schnell genug und der Code geht auch nicht irgendwo in Production. Natürlich kann man versuchen dies aus sportlicher Hinsicht noch auf Höchstleistung zu trimmen. Macht ebenfalls Freude und nicht zuletzt dazu lädt AoC ja auch ein. Also viel Spaß!

[grubenfox]

Wenn man im Lesen und Formulieren dieser Ausdrücke aber einigermaßen geübt ist, greift man gerne danach (sofern es einen sichtbaren Vorteil mit sich bringt).

Betonung auf "Wenn"... und mit den Resten einer Erkältung im Kopf war mir gestern erst recht nicht nach Codeoptimierung.

[Dennis89]

Wie sieht denn eure Datenstruktur für Tag 2 aus?
Ich habe die entweder viel zu kompliziert gewählt oder ich habe sie viel zu kompliziert benutzt. Sicher kann ich nur sagen, ich habe ein großes Chaos erzeugt.
Vielleicht am Schluss auch etwas daran geschuldet, das ich fertig werden wollte. Ich denke, auf einem leeren Blatt anfangen, wäre für eine ordentliche Lösung sicherlich das sinnvollste. Aber heute werde ich nicht mehr viel am PC sein und morgen gehts ja schon weiter.

Gelöst habe ich es, aber ganz und gar nicht schön.


VORSICHT LÖSUNG TAG 2:

Code: Alles auswählen

from pathlib import Path
from functools import reduce
import re


INPUT = Path('/home/dennis/AoC/2023/Day2/input.txt')
MAX_CUBES = {
    'red': 12,
    'green': 13,
    'blue': 14
}


def parse_input(game):
    id_separated = [item.strip() for item in game.split(':')]
    color_with_numbers = []
    for game_round in id_separated[1].split(';'):
        color_with_numbers.extend(
            {color.strip().replace(',', ''): int(number)}
            for number, color in zip(
                re.findall(r'\d+', game_round.strip()),
                re.findall(r'\D+', game_round.strip())
                )
        )
    return {int(id_separated[0].replace('Game ', '')): color_with_numbers}


def get_min_cubes(game):
    biggest_number = {}
    for cubes in game.values():
        for pair in cubes:
            for color, number in pair.items():
                if color in biggest_number and biggest_number[color] < number:
                    biggest_number[color] = number
                elif color not in biggest_number:
                    biggest_number[color] = number
    return biggest_number


def get_sum_of_powers_produces(games):
    powers_produces = []
    for game in games:
        if game:
            color_to_fewest_number = get_min_cubes(game)
            powers_produces.append(reduce(lambda x, y: x * y, list(color_to_fewest_number.values())))
    return sum(powers_produces)


def get_sum_of_possible_games(games):
    id_of_impossible_games = []
    for game in games:
        for game_id, cubes in game.items():
            for color_to_number in cubes:
                for color, number in color_to_number.items():
                    if (
                            number > MAX_CUBES[color]
                            and game_id not in id_of_impossible_games
                    ):
                        id_of_impossible_games.append(game_id)
    for game in games:
        for impossible_games in id_of_impossible_games:
            game.pop(impossible_games, None)
    possible_games = []
    for game in games:
        possible_games.extend(iter(game.keys()))
    return sum(possible_games)


def main():
    games = [parse_input(game) for game in INPUT.read_text(encoding='UTF-8').splitlines()]
    print(get_sum_of_powers_produces(games))
    print(get_sum_of_possible_games(games))


if __name__ == '__main__':
    main()

Grüße
Dennis

[Manul]

Wie sieht denn eure Datenstruktur für Tag 2 aus?

Je Beispiel ein (default)dict Farbe->Anzahl, je Spiel eine Liste der Beispiele, für alle Spiele ein (default)dict ID->Liste. Letzteres hätte, wie @snafu schrieb, auch eine Liste sein können, wenn man vorher überprüft hätte, daß im Input alle IDs in der richtigen Reihenfolge und ohne Lücken stehen.

Meine Gesamtlösung sieht so aus:

Code: Alles auswählen

#!/usr/bin/python3

import fileinput

from collections import defaultdict
from functools import reduce
from operator import mul

def read_input():
  games = defaultdict(list)

  for line in fileinput.input():
    game, samples = line.strip().split(":")
    game = int(game.split()[1])

    samples = samples.split(";")

    for sample in samples:
      balls = defaultdict(int)
      for color in sample.split(","):
        number, color = color.strip().split()
        balls[color] = int(number)
      games[game].append(balls)

  return games

def main():
  games = read_input()

  # part 1
   available = {
    "red":    12,
    "green":  13,
    "blue":   14
  }

  sum_of_IDs = 0

  # part 2
  powers = defaultdict(int)

  for ID, game in games.items():
    possible = True
    needed = defaultdict(int)
    for sample in game:
      possible &= all(sample[color] <= available[color] for color in available)
      for color in available:
        needed[color] = max(needed[color],sample[color])
    sum_of_IDs += ID * possible
    powers[ID] = reduce(mul, needed.values())

  print(sum_of_IDs)

  print(sum(powers.values()))

if __name__ == "__main__":
  main()

[__blackjack__]

@Dennis89: Ich habe zwei Klassen, eine `Cubes`-Klasse mit den Attributen `red`, `green`, und `blue` die jeweils die Anzahl der Würfel speichern und eine `Game`-Klasse mit den Attributen `id` und `rounds`, wobei letzteres eine Liste mit `Cubes`-Objekten ist.

Die `Cubes`-Objekte sind iterierbar und liefert die Zahlen für `red`, `green`, und `blue`. `Game`-Objekte sind auch iterierbar und liefern die `Cube`-Objekte aus `rounds`.

`Cubes` kann man mit ``<=`` vergleichen ob das komponentenweise für die beiden Objekte gilt. Es gibt ein `power`-Property, welches das Produkt der Komponenten liefert. Da habe ich übrigens `math.prod()` statt `reduce()` verwendet. Und eine `get_max()`-Methode die ein `Cubes`-Objekt liefert mit einem komponentenweisen Maximum, von dem Objekt selbst und einem anderen `Cubes`-Objekt.

`Game`-Objekte haben eine `is_possible()`-Methode, der man ein `Cubes` geben kann was den Beutelinhalt von dem Spiel repräsentiert. Und eine `get_minimal_bag()`-Methode die ein `Cubes`-Objekt liefert was den kleinsten Beutelinhalt repräsentiert, den man für dieses Spiel braucht.

Beide Klassen haben dann noch eine Klassenmethode `parse()` um einen Text in so ein Objekt zu wandeln.

Was dann ohne die Klassen noch übrig bleibt:

Code: Alles auswählen

#!/usr/bin/env python3
import sys
from functools import reduce
from math import prod

from attr import attrib, attrs, fields
from parse import parse

EXAMPLE_LINES = """\
Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green
""".splitlines()

BAG_CONTENT = "12 red, 13 green, 14 blue"

...

def parse_lines(lines):
    return map(Game.parse, lines)


def sum_possible_games(games):
    """
    >>> sum_possible_games(parse_lines(EXAMPLE_LINES))
    8
    """
    bag = Cubes.parse(BAG_CONTENT)
    return sum(game.id for game in games if game.is_possible(bag))


def sum_power_of_games(games):
    """
    >>> sum_power_of_games(parse_lines(EXAMPLE_LINES))
    2286
    """
    return sum(game.get_minimal_bag().power for game in games)


def main():
    games = list(parse_lines(sys.stdin))
    print(sum_possible_games(games))
    print(sum_power_of_games(games))


if __name__ == "__main__":
    main()

Die beteiligten Methoden sind eigentlich alles simple Einzeiler, abgesehen vom parsen.

Und hier die Komplettlösung — in BASIC (Laufzeit 3½ Minuten):

Code: Alles auswählen

   10 TI$="000000":R1=0:R2=0
  100 OPEN 1,8,2,"INPUT02,S"
  110 IF ST<>0 THEN 900
  120 FOR I=1 TO LEN("GAME "):GET#1,C$:NEXT
  130 GOSUB 1000:ID=N
  140 PRINT ID:PRINT"{UP}";
  150 R=0:G=0:B=0:V=-1
  160 RM=0:GM=0:BM=0
  170 GET#1,C$:GOSUB 1000:GET#1,C$
  180 IF C$="R" THEN R=N:GOTO 210
  190 IF C$="G" THEN G=N:GOTO 210
  200 IF C$="B" THEN B=N
  210 GET#1,C$:IF C$>="A" AND C$<="Z" THEN 210
  220 IF C$="," THEN 170
  230 REM PRINT:PRINT">"R;G;B
  240 IF V THEN V=R<=12 AND G<=13 AND B<=14
  250 IF RM<R THEN RM=R
  260 IF GM<G THEN GM=G
  270 IF BM<B THEN BM=B
  280 IF C$=";" THEN 170
  290 IF V THEN R1=R1+ID
  300 R2=R2+RM*GM*BM
  310 GOTO 110
  900 CLOSE 1
  910 PRINT:PRINT R1,R2,TI$
  920 END
 1000 N=0
 1010 GET#1,C$
 1020 IF C$<"0" OR C$>"9" THEN RETURN
 1030 N=N*10+VAL(C$)
 1040 GOTO 1010

[narpfel]

Ich habe `collections.Counter` benutzt, damit bekommt man den <=-Operator for free und ein Indexzugriff auf einen nicht vorhandenen Wert liefert 0.

[Dennis89]

Danke für eure Antworten und Erklärungen.

Da habe ich wider genügend Stoff zum durcharbeiten, sollte mich die Langeweile mal überkommen.


Grüße
Dennis

[kbr]

Ich habe es mal prozedural "ohne alles" umgesetzt. Die Verwendung von "math.prod" bringt im Vergleich zur ausgeschriebenen Schleife keinen merklichen Laufzeitvorteil. Letztenendes ging es bei Tag 2 aber um das Parsen. Hier die Variante für Teil 2:

Code: Alles auswählen

fname = "input.txt"


def get_gamenumber_and_cubesets(line):
    parts = line.split(":")
    _, game = parts[0].split()
    game_number = int(game)
    cubesets = parts[-1]
    return game_number, cubesets


def get_grabbed_cubes(grab):
    d = {}
    parts = grab.split(",")
    for part in parts:
        num, color = part.split()
        d[color] = int(num)
    return d


def get_setpower_from_cubesets(cubesets):
    max_d = {}
    grabs = cubesets.split(";")
    for grab in grabs:
        d = get_grabbed_cubes(grab)
        for color in d:
            m = max_d.get(color, 0)
            if m < d[color]:
                max_d[color] = d[color]
    set_power = 1
    for value in max_d.values():
        set_power *= value
    return set_power


with open(fname) as fobj:
    game_sum = 0
    for line in fobj:
        line = line.strip()
        game_number, cubesets = get_gamenumber_and_cubesets(line)
        set_power = get_setpower_from_cubesets(cubesets)
        game_sum += set_power

print(game_sum)