@narpfel:
Das automatische Erzeugen der Sonderfälle war auch schnell umgesetzt. Für die B-Note. Oder so.
Advent of Code
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:
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.
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'
}
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)}')
Ich bin Pazifist und greife niemanden an, auch nicht mit Worten.
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
Geht mir gerade ähnlich. Ich weiß nicht, was passieren soll, wenn in einer Zeile nur eine anstatt zwei Ziffern enthalten sind.__blackjack__ hat geschrieben: ↑Freitag 1. Dezember 2023, 11:05 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.
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()
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.
Da hing ich auch kurz, aber da war das letzte Beispiel aus dem ersten Teil die (Auf-)lösung.snafu hat geschrieben: ↑Samstag 2. Dezember 2023, 06:26Geht mir gerade ähnlich. Ich weiß nicht, was passieren soll, wenn in einer Zeile nur eine anstatt zwei Ziffern enthalten sind.__blackjack__ hat geschrieben: ↑Freitag 1. Dezember 2023, 11:05 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.
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()
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.
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.grubenfox hat geschrieben: ↑Samstag 2. Dezember 2023, 12:00Da hing ich auch kurz, aber da war das letzte Beispiel aus dem ersten Teil die (Auf-)lösung.snafu hat geschrieben: ↑Samstag 2. Dezember 2023, 06:26Geht mir gerade ähnlich. Ich weiß nicht, was passieren soll, wenn in einer Zeile nur eine anstatt zwei Ziffern enthalten sind.__blackjack__ hat geschrieben: ↑Freitag 1. Dezember 2023, 11:05 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.
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...
Zuletzt geändert von snafu am Samstag 2. Dezember 2023, 12:25, insgesamt 1-mal geändert.
- __blackjack__
- User
- Beiträge: 13214
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
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()
“There will always be things we wish to say in our programs that in all known languages can only be said poorly.” — Alan J. Perlis
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)
@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.
@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ß!
Betonung auf "Wenn"... und mit den Resten einer Erkältung im Kopf war mir gestern erst recht nicht nach Codeoptimierung.
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:
Grüße
Dennis
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()
Dennis
"When I got the music, I got a place to go" [Rancid, 1993]
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__
- User
- Beiträge: 13214
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
@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:
Die beteiligten Methoden sind eigentlich alles simple Einzeiler, abgesehen vom parsen.
Und hier die Komplettlösung — in BASIC (Laufzeit 3½ Minuten):
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()
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
“There will always be things we wish to say in our programs that in all known languages can only be said poorly.” — Alan J. Perlis
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)