Advent of Code

[steveO_O]

Das ist ziemlich cool. Danke!

[nezzcarth]

Und auch dieses Jahr gibt es wieder einen Advent of Code:
https://adventofcode.com/2021

[sls]

Ich hatte mir dieses Jahr vorgenommen, AoC zu nutzen um Bash-Scripting zu lernen. Ich glaube ich verwerfe das Vorhaben schnell wieder.

Part 1:

Code: Alles auswählen

#!/usr/bin/env bash

MEASUREMENTS=()
INCREASED=0

while read line
  do
    MEASUREMENTS+=($line)
  done < day1-input.txt

for (( i=2; i<=${#MEASUREMENTS[@]}; i++ ));
  do
    if [[ $MEASUREMENTS[$i] -gt $MEASUREMENTS[$i-1] ]]; then
      INCREASED=$((INCREASED + 1))
    fi
  done

echo $INCREASED

[__blackjack__]

Jo, Tag 1 ist ja wie immer ziemlich einfach. Das liess sich problemlos mit BASIC auf dem C64 lösen. Wobei Teil 2 Potential hat optimiert zu werden:

Code: Alles auswählen

10 TI$="000000":PRINT"READING INPUT...":DIM A(2000):OPEN 1,8,0,"INPUT01,S":N=0
20 INPUT#1,A(N):N=N+1:IF ST=0 THEN 20
30 CLOSE 1:PRINT N;"VALUES IN ";TI$:PRINT"PART 1..."
40 C=0:FOR I=0 TO N-2:IF A(I)<A(I+1) THEN C=C+1
50 NEXT:PRINT C;TI$
60 PRINT"PART 2...":C=0:FOR I=0 TO N-4
70 X=0:Y=0:FOR J=0 TO 2:K=I+J:X=X+A(K):Y=Y+A(K+1):NEXT:IF X<Y THEN C=C+1
80 NEXT:PRINT C;TI$

[__blackjack__]

@sls: Das läuft bei mir nicht solange ich die Indexzugriffe auf MEASUREMENTS nicht in geschweifte Klammern setze: ``${MEASUREMENTS[$i]}``. Meine Bash sagt da sonst Syntaxfehler.

Und dann kommt bei mir das falsche Ergebnis, weil die Schleife bei 2 statt bei 1 anfängt. Indizes fangen bei Bash-Arrays bei 0 an.

Dann hat die Bash den praktischen ``readarray``-Befehl.

Um 1 erhöhen geht ohne Zuweisung, mit ``++``.

Und Lesbarkeit wird IMHO überbewertet — weg mit dem ``if``, her mit dem ``&&``.

Code: Alles auswählen

#!/usr/bin/env bash

readarray MEASUREMENTS < input.txt

INCREASED=0
for (( i=1; i<=${#MEASUREMENTS[@]}; i++ )); do
    [[ ${MEASUREMENTS[i]} -gt ${MEASUREMENTS[i-1]} ]] && (( INCREASED++ ))
done

echo $INCREASED

[sls]

@sls: Das läuft bei mir nicht solange ich die Indexzugriffe auf MEASUREMENTS nicht in geschweifte Klammern setze: ``${MEASUREMENTS[$i]}``. Meine Bash sagt da sonst Syntaxfehler.

Und dann kommt bei mir das falsche Ergebnis, weil die Schleife bei 2 statt bei 1 anfängt. Indizes fangen bei Bash-Arrays bei 0 an.

Oh man, ich hatte das Bash-Skript in PyCharm geschrieben und ausgeführt, dabei hat er das auf meiner Kiste mit zsh ausgeführt. Komischerweise zählt er dort noch das newline mit und das `INCREASED` ist dann um eins zu hoch, selbst wenn ich beim korrekten Index 1 starte. Der Rest ist mega praktisch, danke dir!

Update: readarray wird von zsh nicht mal gefunden... Ein grund mehr wieder bash zu verwenden.
Update2: Newline wurde ebenfalls von Pycharm hinzugefügt. Trotzdem will ich zsh nicht mehr verwenden.

[__blackjack__]

Iiihk, ja das ``<=`` als Schleifenbedingung ist natürlich falsch, dass müsste nur ``<`` heissen. Sorry, das habe ich übersehen.

[nezzcarth]

@sls:
Zu deinem Shell-Skript hier noch meine "One-Liner" (spätestens beim zweiten wird es etwas absurd, aber nun gut … ):

Code: Alles auswählen

#!/bin/bash
FILE="day01.txt"
paste <(head -n -1 "$FILE") <(tail -n +2 "$FILE" ) | awk '$2>$1{print}' | wc -l
paste -d + <(head -n -2 "$FILE") <(tail -n +2 "$FILE" | head -n -1) <(tail -n +3 "$FILE") | bc >_day01.tmp && paste <(head -n -1 _day01.tmp) <(tail -n +2 _day01.tmp) | awk '$2>$1{print}' | wc -l && rm -f _day01.tmp 

(AWK wollte ich so minimal wie möglich verwenden; ansonsten könnte man natürlich auch da viel mehr direkt machen)

[sls]

Iiihk, ja das ``<=`` als Schleifenbedingung ist natürlich falsch, dass müsste nur ``<`` heissen. Sorry, das habe ich übersehen.

Alles gut, das war ja ein Fehler von mir

@nezzcarth:

Das beste was ich für Tag auf die Schnelle hinbekommen habe ist das (Part 2):

Code: Alles auswählen

#!/usr/bin/env bash

readarray MEASUREMENTS < day1.txt

for (( i=0; i+3<${#MEASUREMENTS[@]}; i++ )); do
  WINDOW1=$((${MEASUREMENTS[i]} + ${MEASUREMENTS[i+1]} + ${MEASUREMENTS[i+2]}))
  WINDOW2=$((${MEASUREMENTS[i+1]} + ${MEASUREMENTS[i+2]} + ${MEASUREMENTS[i+3]}))
  [[ ${WINDOW1} -lt ${WINDOW2} ]] && (( INCREASED++ ))
  done


echo $INCREASED

[Kebap]

Ich versuche mich derzeit auch am AoC 2021, weil ich das schöne Rätsel und Übung und Inspiration finde.
Zwar erwarte ich nicht, da innerhalb eines Monats fertig zu werden, aber darum geht es mir auch gar nicht.

Nur weiß ich noch nicht, wie ich dann hier Feedback zu meinen stümperhaften Ergebnissen erfragen kann.
Soll ich neue Threads pro Tag öffnen oder alles hier in den riesigen Thread einfügen, wo es ggf. untergeht?
Bis dato stelle ich alles bei Github online, weil ich die Versionierung mag und Zugriff von mehreren Orten:

https://github.com/Kebap/aoc2021

[Kebap]

Tag 6 brachte exponentielles Wachstum mit sich.
Meine naive Lösung für die erste Teilaufgabe ließ sich nicht ohne weiteres für größere Listen fortsetzen, da die Berechnungen exponentiell immer länger dauerten.
Stattdessen habe ich (weil es nicht gefragt war) einen Teil der Informationen fallen gelassen, und die Gegenstände in Masse bearbeitet, statt jedes einzeln in Reihenfolge.

[ThomasL]

Bei den Aufgaben kommt es manchmal auf einzelne Worte in der Aufgabenstellung an, die einen Hinweis auf die Art und Weise einer Lösung geben.

Bei dieser Aufgabe war es die erste Zeile im gegebenen Beispiel: "Initial state: 3,4,3,1,2" und zwar das Wort state.

Danach wurde man zwar durch die Art und Weise der Erklärung des Beispiels auf eine falsche Fährte geschickt (erstellen einer immer längeren Liste).

Anstatt für jeden einzelnen Fisch den Status nachzuhalten, reicht es die Anzahl der Fische pro State (Lebenstage) nachzuhalten. Wenn man das mal mit Pen & Paper macht, kommt das heraus. Und dann erkennt man,
dass dies einfachst durch eine Verschiebung der Werte nach links zu erreichen ist.

Code: Alles auswählen

   0 1 2 3 4 5 6 7 8
0:   1 1 2 1
1: 1 1 2 1
2: 1 2 1       1   1
3: 2 1       1 1 1 1

Hatte die Verschiebung zuerst selbst gecodet und mich dann an collections deque erinnert. Das ist auch mit eine der wichtigen Helferbibliotheken bei AoC jedes Jahr. Meine Lösung:

Code: Alles auswählen

from collections import deque

data = list(map(int, open('input.txt').read().split(',')))

def life(n):
    counts = deque([data.count(i) for i in range(9)])
    for _ in range(n):
        counts.rotate(-1)
        counts[6] += counts[8]
    return sum(counts)

print('Part1:', life(80))
print('Part2:', life(256))

[__blackjack__]

Ich hatte gleich Abstand von der länger werdenden Liste genommen, weil ich ja immer als erstes CBM BASIC V2 im Kopf habe, und da wäre das selbst ohne exponentielles Wachstum ja keine gute Idee gewesen. Hier der erste Lösungsansatz von mir:

Code: Alles auswählen

   10 TI$="000000":SF=7:DIM P(SF+1)
   20 OPEN 1,8,0,"INPUT06,S":PRINT"READING FISH..."
   30 GET#1,A$:IF ST<>0 THEN PRINT"READ ERROR":CLOSE 1:END
   40 I=VAL(A$):P(I)=P(I)+1:GET#1,A$:REM SKIP ","
   50 IF ST=0 THEN 30
   60 CLOSE 1:PRINT "READING TIME ";TI$:PRINT
   70 FOR D=1 TO 256:PRINT"{UP}DAY";D
   80 C=P(0):FOR I=0 TO SF:P(I)=P(I+1):NEXT:P(SF+1)=C:P(SF-1)=P(SF-1)+C
   90 IF D=80 THEN GOSUB 200
  100 NEXT:GOSUB 200:PRINT"TOTAL TIME ";TI$:END
  200 S=0:FOR I=0 TO SF+1:S=S+P(I):NEXT:PRINT S:PRINT:RETURN

Funktioniert eigentlich auch, wenn der begrenzte Wertebereich der Gleitkommazahlen nicht wäre, denn die 80 Tage-Marke gibt das noch exakt aus, aber nach 256 Tagen fallen 36 Fische ”hinten runter”:

Code: Alles auswählen

RUN
READING FISH...
READING TIME 000008
DAY 80
 353079
DAY 256
 1.60540013E+12

TOTAL TIME 000037

37 Sekunden Laufzeit inklusive einlesen der Daten von Diskette ist aber okay für den alten Rechner.

[ThomasL]

ist aber okay für den alten Rechner.

Was ist denn das für eine Hardware?

[__blackjack__]

Commodore 64, interpretiertes BASIC auf einer etwas unter 1 Mhz getakteten 8-Bit-CPU. Plus grottenlangsame Disk-I/O. Einlesen der 600 einstelligen Werte hat alleine schon 8 Sekunden gedauert.

Ich habe das mal zu GW-BASIC für den PC portiert, da gibt es auch einen Gleitkommatyp mit höherer Genauigkeit:

Code: Alles auswählen

10 SPAWN.FREQ=7:REM In days.
20 DIM POPULATION#(SPAWN.FREQ+1):REM Index=days till spawn, Value=# of fish.
30 OPEN "INPUT06.TXT" FOR INPUT AS #1
40 WHILE NOT EOF(1):INPUT #1,I:POPULATION#(I)=POPULATION#(I)+1:WEND:CLOSE #1
100 FOR DAY=1 TO 256
110   N#=POPULATION#(0)
120   FOR I=0 TO SPAWN.FREQ:POPULATION#(I)=POPULATION#(I+1):NEXT
130   POPULATION#(SPAWN.FREQ+1)=N#
140   POPULATION#(SPAWN.FREQ-1)=POPULATION#(SPAWN.FREQ-1)+N#
150   IF DAY=80 THEN GOSUB 500
160 NEXT:GOSUB 500:END
500 SUM#=0:FOR I=0 TO SPAWN.FREQ+1:SUM#=SUM#+POPULATION#(I):NEXT
510 PRINT SUM#:RETURN

[kbr]

Plus grottenlangsame Disk-I/O.

Da gab es doch den Fastloader – das meist raubkopierte Programm seiner Zeit.

[__blackjack__]

@kbr: Da gab es mehrere, aber die meisten Leute die ich kannte/kenne haben ein Steckmodul mit Fastloader (gehabt). In der Regel eine Final Cartridge 3 oder ein Action Replay 5 oder 6. Ich hatte damals ein Action Replay 6 und heute ein Retro Replay. Das Problem ist, dass die nur LOAD und SAVE beschleunigen, aber nicht was man so nach einem OPEN mit Dateien macht: GET#/INPUT#/PRINT#.

Da gibt es auch Lösungen für, für die man aber an die Hardware ran muss und im einfachsten Fall sowohl beim Rechner als auch im Laufwerk ROMs austauschen muss. Bei älteren Geräten waren die Bausteine nicht zwingend gesockelt und man musste mit dem Lötkolben ran. Bei einigen Lösungen kam dann noch Basteln und Löten von zusätzlichen Kabeln und RAM-Platinen für das Laufwerk dazu. Da wird das mit dem Raubkopieren zumindest mal aufwändiger.

Ich war dann jetzt doch mal motiviert auch auf dem C64 die exakte Lösung zu bekommen und habe die Zähler in zwei Teile aufgeteilt: alles über eine Million und alles unter einer Million:

Code: Alles auswählen

   10 TI$="000000":SF=7:DIM P(SF+1,1):OM=1E6
   20 OPEN 1,8,0,"INPUT06,S":PRINT"READING FISH..."
   30 GET#1,A$:IF ST<>0 THEN PRINT"READ ERROR":CLOSE 1:END
   40 I=VAL(A$):P(I,0)=P(I,0)+1:GET#1,A$:REM SKIP ","
   50 IF ST=0 THEN 30
   60 CLOSE 1:PRINT "READING TIME ";TI$:PRINT
   70 FOR D=1 TO 256:PRINT"{UP}DAY";D
   80 AL=P(0,0):AH=P(0,1):FOR I=0 TO SF:P(I,0)=P(I+1,0):P(I,1)=P(I+1,1):NEXT
   90 P(SF+1,0)=AL:P(SF+1,1)=AH
  100 BL=P(SF-1,0):BH=P(SF-1,1):GOSUB 300:P(SF-1,0)=AL:P(SF-1,1)=AH
  110 IF D=80 THEN GOSUB 200
  120 NEXT:GOSUB 200:PRINT"TOTAL TIME ";TI$:END
  200 AL=0:AH=0:FOR I=0 TO SF+1:BL=P(I,0):BH=P(I,1):GOSUB 300:NEXT
  210 PRINT AH;"MILLIONS +";AL:PRINT:RETURN
  300 AL=AL+BL:AH=AH+BH:IF AL>=OM THEN AL=AL-OM:AH=AH+1
  310 RETURN

Jetzt gehen keine Fische mehr verloren. Bei einer Laufzeit von rund 1½ Minuten:

Code: Alles auswählen

RUN
READING FISH...
READING TIME 000011
DAY 80
 0 MILLIONS + 353079
DAY 256
 1605400 MILLIONS + 130036

TOTAL TIME 000129

READY.

Und hier mal meine Python-Lösung:

Code: Alles auswählen

#!/usr/bin/env python3
from collections import Counter

import pytest
from more_itertools import iterate, nth

SPAWN_FREQUENCY = 7  # in days.

EXAMPLE_INPUT = "3,4,3,1,2"

EXAMPLE_DEVELOPMENT = """\
Initial state: 3,4,3,1,2
After  1 day:  2,3,2,0,1
After  2 days: 1,2,1,6,0,8
After  3 days: 0,1,0,5,6,7,8
After  4 days: 6,0,6,4,5,6,7,8,8
After  5 days: 5,6,5,3,4,5,6,7,7,8
After  6 days: 4,5,4,2,3,4,5,6,6,7
After  7 days: 3,4,3,1,2,3,4,5,5,6
After  8 days: 2,3,2,0,1,2,3,4,4,5
After  9 days: 1,2,1,6,0,1,2,3,3,4,8
After 10 days: 0,1,0,5,6,0,1,2,2,3,7,8
After 11 days: 6,0,6,4,5,6,0,1,1,2,6,7,8,8,8
After 12 days: 5,6,5,3,4,5,6,0,0,1,5,6,7,7,7,8,8
After 13 days: 4,5,4,2,3,4,5,6,6,0,4,5,6,6,6,7,7,8,8
After 14 days: 3,4,3,1,2,3,4,5,5,6,3,4,5,5,5,6,6,7,7,8
After 15 days: 2,3,2,0,1,2,3,4,4,5,2,3,4,4,4,5,5,6,6,7
After 16 days: 1,2,1,6,0,1,2,3,3,4,1,2,3,3,3,4,4,5,5,6,8
After 17 days: 0,1,0,5,6,0,1,2,2,3,0,1,2,2,2,3,3,4,4,5,7,8
After 18 days: 6,0,6,4,5,6,0,1,1,2,6,0,1,1,1,2,2,3,3,4,6,7,8,8,8,8
""".splitlines()


def parse_population(string):
    """
    Parse given `string` into a histogram of the population.

    Each index in the result represents the number of fish that spawn in the
    number of days represented by that index.  This way the exponential growth
    is kept in a fixed size data structure.

    >>> p = parse_population("")
    >>> p
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
    >>> len(p) == SPAWN_FREQUENCY + 2
    True
    >>> parse_population("4,2,4")
    [0, 0, 1, 0, 2, 0, 0, 0, 0]
    """
    histogram = Counter(map(int, string.split(",") if string.strip() else []))
    return [histogram[i] for i in range(SPAWN_FREQUENCY + 2)]


def do_one_day(population):
    creator_count = population[0]
    new_population = population[1:]
    new_population.append(creator_count)  # The new ones.
    new_population[SPAWN_FREQUENCY - 1] += creator_count  # The old ones.
    return new_population


def iter_days(population):
    return iterate(do_one_day, population)


def count_fish_after_period(population, day_count):
    return sum(nth(iter_days(population), day_count))


def main():
    population = parse_population(input())
    for day_count in [80, 256]:
        print(count_fish_after_period(population, day_count))


def _parse_example_development_line(line):
    description, colon, population_text = line.partition(":")
    assert colon == ":", line
    return description, parse_population(population_text)


def test_do_one_day():
    values = iter_days(parse_population(EXAMPLE_INPUT))
    expected_values = map(_parse_example_development_line, EXAMPLE_DEVELOPMENT)
    for value, (description, expected) in zip(values, expected_values):
        assert value == expected, description


@pytest.mark.parametrize(
    "day_count, expected", [(18, 26), (80, 5934), (256, 26_984_457_539)]
)
def test_count_fish_after_period(day_count, expected):
    assert (
        count_fish_after_period(parse_population(EXAMPLE_INPUT), day_count)
        == expected
    )


if __name__ == "__main__":
    main()

[__blackjack__]

Noch mal eine Tag 6 Lösung für den C64. In COMAL. So eine Mischung zwischen BASIC und Pascal und eine recht angenehme Art lesbar auf solchen Systemen zu programmieren. Ist so ähnlich interpretiert wie BASIC, also bei der Eingabe werden die Zeilen kompakter im Speicher abgelegt als es reiner Text wäre. Im Gegensatz zum Microsoft BASIC werden nicht nur Schlüsselworte zu 1 Byte Tokens, sondern auch Zahlen werden nicht als Text gespeichert. Namen werden in einer Namenstabelle geführt und in den Zeilendaten landet nur der Index in diese Tabelle, so dass obwohl Namen bis zu 79 Zeichen lang sein dürfen, jeder Name nur einmal diesen vollen Speicherplatz im Programm belegt, und das nachschlagen des Namens nicht zur Laufzeit des Programms passiert, sondern schon bei der Eingabe.

Neben den ganzen strukturierten Kontrollstrukturen wie IF … THEN … ELIF … ELSE … ENDIF und FOR, WHILE, REPEAT … UNTIL, … Schleifen, gibt es benannte Funktionen und Prozeduren. Mit lokalen Namensräumen. Und sowohl „pass by value“ als auch „pass by reference“-Argumente.

Weil Zeichenketten in COMAL nicht auf 255 Zeichen beschränkt sind wie bei BASIC, kann man hier einfach die komplette Datei in eine Zeichenkette einlesen. Und weil das COMAL-Steckmodul keinen eigenen Schnelllader mitbringt, kommt auch beim OPEN/get$() JiffyDOS zum Zug und das ist noch mal schneller als das BASIC-Programm mit RetroReplay-Steckmodul.

Code: Alles auswählen

0010 TIME 0
0020 sf#:=7 // spawn frequency
0030 DIM pop(0:sf#+1,0:1)
0040 
0050 PRINT "Reading fish...";
0060 read'fish
0070 PRINT TIME/60;"s"
0080 
0090 FOR d#:=1 TO 256 DO
0100   PRINT AT 0,1: "Day";d#;
0110   
0120   // Rotate pop(,) left.
0130   nl:=pop(0,0); nh:=pop(0,1)
0140   FOR i#:=0 TO sf# DO
0150     pop(i#,0):=pop(i#+1,0)
0160     pop(i#,1):=pop(i#+1,1)
0170   ENDFOR i#
0180   pop(sf#+1,0):=nl; pop(sf#+1,1):=nh
0190   
0200   add(nl,nh,pop(sf#-1,0),pop(sf#-1,1))
0210   pop(sf#-1,0):=nl; pop(sf#-1,1):=nh
0220   
0230   IF d#=80 THEN print'result
0240 ENDFOR d#
0250 print'result
0260 PRINT "Total";TIME/60;"s"
0270 END 
0280 
0290 PROC read'fish CLOSED
0300   IMPORT pop(,)
0310   DIM buf$ OF 1000
0320   OPEN FILE 2,"input06",READ
0330   INPUT FILE 2: buf$
0340   FOR i#:=1 TO LEN(buf$) STEP 2 DO
0350     pop(VAL(buf$(i#:i#)),0):+1
0360   ENDFOR i#
0370   CLOSE FILE 2
0380 ENDPROC read'fish
0390 
0400 PROC print'result CLOSED
0410   IMPORT sf#,pop(,),add
0420   sum'l:=0; sum'h:=0
0430   FOR i#:=0 TO sf#+1 DO
0440     add(sum'l,sum'h,pop(i#,0),pop(i#,1))
0450   ENDFOR i#
0460   
0470   PRINT "=";
0480   IF sum'h=0 THEN
0490     PRINT sum'l;
0500   ELSE 
0510     PRINT sum'h,
0520     PRINT USING "######": sum'l;
0530   ENDIF 
0540   PRINT "fish."
0550 ENDPROC print'result
0560 
0570 PROC add(REF al,REF ah,bl,bh) CLOSED
0580   al:=al+bl; ah:=ah+bh
0590   IF al>=1000000 THEN al:-1000000; ah:+1
0600 ENDPROC add

Das läuft in 44,67 Sekunden durch:

Code: Alles auswählen

run
Reading fish... 2.75 s
Day 80 = 353079 fish.
Day 256 = 1605400130036 fish.
Total 44.6666667 s

end at 0270

[Kebap]

Das sind echt tolle Lösungen und Stilmittel. Davon kann ich noch viel lernen. Bin leider noch meilenweit entfernt und kann vieles noch nicht annähernd so knapp und elegant formulieren.

Ich stelle mal meine Lösung für Tag 8 vor. Sie "funktioniert" schon, insofern sie das richtige Ergebnis liefert.
Trotz meiner Bedenken ob des komplizierten Codes geht das auch durchaus schnell innerhalb weniger Sekundenbruchteile.
Vermutlich ist die Aufgabe einfach so kompliziert. Musste echt lange überlegen, bis mir überhaupt ein Lösungsweg eingefallen ist.
Habe einige Stellen markiert, die ggf. beschleunigt werden könnten. Zum Glück habe ich das zurückgestellt, denn es war gar nicht nötig.

Wahrscheinlich würde es Sinn machen, die mega lange Funktion in viele Einzelteile aufzutrennen. Mir fehlt da nur das richtige Messer. Wie schneiden?
Es wäre hilfreich gewesen, diese dann einzeln testen zu können. So musste ich gelegentlich assert() oder print() einsprenkeln, um den richtigen Weg zu prüfen.

Auch ist mir keine sinnvolle Datenstruktur eingefallen, um die verschiedenen Ebenen und Benennungen rund ums Display einheitlich zusammenzufassen.
Daher habe ich mich für mega lange Variablen und ausführliche Kommentierung entschieden. Bin trotzdem selbst ein paar Mal durcheinander gekommen.

Code: Alles auswählen

# https://adventofcode.com/2021/day/8

from parse import parse # requires: pip install parse 
# from parse import *   # would yield: parse(), search(), findall(), and with_pattern() 

UNIQUE_DIGITS_LENGTHS = [2, 4, 3, 7] # for digits 1, 4, 7, or 8
UNIQUE_LENGTHS_TRANSLATIONS = {2: 1, 4: 4, 3: 7, 7: 8}
UNIQUE_SLOT_OCCURENCES_TRANSLATIONS = {4: "e", 6: "b", 9: "f"}
GENERAL_PATTERN_DECRYPTIONS = {
  "abcefg": 0,
  "cf": 1,
  "acdeg": 2,
  "acdfg": 3,
  "bcdf": 4,
  "abdfg": 5,
  "abdefg": 6,
  "acf": 7,
  "abcdefg": 8,
  "abcdfg": 9
} # Could remove patterns with unique length from here, they are handled otherwise already! 

DISPLAY = """
  0:      1:      2:      3:      4:
 aaaa    ....    aaaa    aaaa    ....
b    c  .    c  .    c  .    c  b    c
b    c  .    c  .    c  .    c  b    c
 ....    ....    dddd    dddd    dddd
e    f  .    f  e    .  .    f  .    f
e    f  .    f  e    .  .    f  .    f
 gggg    ....    gggg    gggg    ....

  5:      6:      7:      8:      9:
 aaaa    aaaa    aaaa    aaaa    aaaa
b    .  b    .  .    c  b    c  b    c
b    .  b    .  .    c  b    c  b    c
 dddd    dddd    ....    dddd    dddd
.    f  e    f  .    f  e    f  .    f
.    f  e    f  .    f  e    f  .    f
 gggg    gggg    ....    gggg    gggg
"""

PLAN = """
Skizze:
  A	
B		C
	D	
E		F
	G	

Zusammensetzung:
n	A	B	C	D	E	F	G	s	unique?
0	X	X	X		X	X	X	6	Set 6
1			X			X		2	WAHR
2	X		X	X	X		X	5	Set 5
3	X		X	X		X	X	5	Set 5
4		X	X	X		X		4	WAHR
5	X	X		X		X	X	5	Set 5
6	X	X		X	X	X	X	6	Set 6
7	X		X			X		3	WAHR
8	X	X	X	X	X	X	X	7	WAHR
9	X	X	X	X		X	X	6	Set 6
#	8	6	8	7	4	9	7		
u	2	1	2	2	1	1	2		

Legende:
Spalten:
- n: Zahlen 0-9
- A-G: Slots
- s: Summe der Slots für diese Zahl
- unique?: Ist s unique und Zahl damit in UNIQUE_DIGITS_LENGTH
Zeilen:
- 0-9: Zusammensetzung der Slots für diese Zahl
- #: Anzahl der Einsätze für diesen Slot
- u: Einsätze unique? Dann Slot darüber identifizierbar!

Zahlen:		
0  	?  	Set 6: C, D oder E fehlt
1	  OK	1, 4, 7, or 8: Unique über Länge erkannt
2	  ?	  Set 5: [B, E], [B, F] oder [C, E] fehlen
3	  ?	  Set 5: [B, E], [B, F] oder [C, E] fehlen
4	  OK	1, 4, 7, or 8: Unique über Länge erkannt
5	  ?	  Set 5: [B, E], [B, F] oder [C, E] fehlen
6	  ?	  Set 6: C, D oder E fehlt
7	  OK	1, 4, 7, or 8: Unique über Länge erkannt
8	  OK	1, 4, 7, or 8: Unique über Länge erkannt
9	  ?	  Set 6: C, D oder E fehlt

Slots:		
A	todo	noch ableiten über 1 und 7 (sind bekannt)
B	todo	B, E, F: unique über Häufigkeit erkannt
C	todo	noch ableiten über Set 5 (Rest bekannt)
D	todo	noch ableiten über Set 6 (Rest bald bekannt aus Set 5 und C)
E	todo	B, E, F: unique über Häufigkeit erkannt
F	todo	B, E, F: unique über Häufigkeit erkannt
G	todo	verbleibt als letztes, wenn obiges umgesetzt ist
Alle Slots erkannt? Dann kann auch alle Zahlen erkennen!
"""


def solve_display_8a(display):
  easy_digits_displayed = [d for d in display["outputs"] if len(d) in UNIQUE_DIGITS_LENGTHS]
  return len(easy_digits_displayed)    


def solve_display(display) -> int:
  """
  Review one display and return its output value translated into integer.
  """
  patterns = display["patterns"]
  outputs = display["outputs"]
  
  # For solving the display, I need to decrypt each pattern into a number 
  # Then: decryption("cdeg") == 4
  decryptions = dict()  

  # Maybe slot "e" in this display was called "B" in the general modell
  # Then: slot_translations["e"] == "B"
  slot_translations = dict()
  
  # When I have translated enough slots, I can translate signal patterns
  # Then pattern_translations["cdeg"] == "abef"
  # Where "abef" is the name the pattern would have in the general modell
  # And "cdeg" is the encrypted name the pattern has in the current display
  pattern_translations = dict()
  # Is this step even necessary or can't I immediately use decryptions at that time?

  # Remember or even decypher patterns via their (maybe unique) lengths
  set5 = list(p for p in patterns if len(p) == 5) # will be 3 different patterns
  set6 = list(p for p in patterns if len(p) == 6) # will be 3 different patterns
  for pattern in patterns:  
    # Is this a pattern that can already be identified by its unique length?
    if len(pattern) in UNIQUE_LENGTHS_TRANSLATIONS:
      decryptions[pattern] = UNIQUE_LENGTHS_TRANSLATIONS[len(pattern)]
      
  # Looking at each slot/signal/wire now.
  # How often (and for which patterns) is each slot used?
  slot_names = list("abcdefg")
  slot_usage = dict()
  for slot in slot_names:
    slot_usage[slot] = [p for p in patterns if slot in p]
  slot_usage_count = {k: len(v) for k, v in slot_usage.items()}
  # slot_usage_count has the following values once: 4, 6, 9, and twice: 7, 8 
  assert "".join(sorted(map(str, slot_usage_count.values()))) == "4677889", "unexpected slots"

  # The slots with unique number of occurrences can be identified immediately.
  # Where 4x used is called E in the general model, 6x used is B, 9x used is F.
  for slot, occurrences in slot_usage_count.items():
    if occurrences in UNIQUE_SLOT_OCCURENCES_TRANSLATIONS:
      slot_translations[slot] = UNIQUE_SLOT_OCCURENCES_TRANSLATIONS[occurrences]

  # We can identify the slot that is called A in the general model as well.
  # It is the slot that is used in number 7 but not used in number 1 and we know those.
  for p, n in decryptions.items():
    if n == 1: 
      slots_used_in_one = list(p)
    elif n == 7:
      slots_used_in_seven = list(p)
  assert not slots_used_in_one is None, "Pattern for number one not found"
  assert not slots_used_in_seven is None, "Pattern for number seven not found"
  # Find the slot that is used in 7 but not used in 1. It translates to A in general
  for slot in slots_used_in_seven:
    if not slot in slots_used_in_one:
      slot_translations[slot] = "a"
      break

  # Find slot C via set5 (which are the 3 patterns represented with exactly 5 slots)
  # Two of their slots are used in 2 of the 3 patterns. One slot I know as F, the other is C.
  slots_used_in_set5 = set5[0] + set5[1] + set5[2]
  slots_used_twice_in_set5 = list(s for s in set(slots_used_in_set5) 
                                  if slots_used_in_set5.count(s) == 2)  # O(n) ?
  for slot in slots_used_twice_in_set5:
    if not slot in slot_translations:
      slot_translations[slot] = "c"
      break
  
  # Find slot D via set6 (which are the 3 patterns represented with exactly 6 slots)
  # Three of their slots are used in 2 of the 3 patterns. One slot is still unknown. It is D.
  slots_used_in_set6 = set6[0] + set6[1] + set6[2]
  slots_used_twice_in_set6 = list(s for s in set(slots_used_in_set6) 
                                  if slots_used_in_set6.count(s) == 2)  # O(n) ?
  for slot in slots_used_twice_in_set6:
    if not slot in slot_translations:
      slot_translations[slot] = "d"
      break

  # Only one slot remains without a translation to its general name. It is G.
  for slot in slot_names:
    if not slot in slot_translations:
      slot_translations[slot] = "g"

  # All slots can now be translated to their general name. Great!
  # Now I can translate the slot name in the display

  # Decrypt all six remaining unknown numbers (with non-unique lengths).
  # This will use the now known slots, as all translations are known.
  for pattern in set5 + set6:
    if all(bool(slot in slot_translations) for slot in pattern):
      pattern_translation = "".join(sorted(slot_translations[slot] for slot in pattern))
      decryptions[pattern] = GENERAL_PATTERN_DECRYPTIONS[pattern_translation]
      pattern_translations[pattern] = pattern_translation

  # Finally I can decrypt the numbers shown in this display
  decrypted_output_numbers = tuple(decryptions.get(p, 0) for p in outputs)
  # The 0 here was a place holder during a time when some decryptions were unknown still!
  
  decrypted_value = int("".join(str(n) for n in decrypted_output_numbers))
  
  print(f"{decrypted_value:>4}", 
        outputs, 
        sep="\t")
  return decrypted_value


def solve(data):
  sum_of_output_values = sum(solve_display(d) for d in data)
  return f"{sum_of_output_values} is the sum of all output values."
   


def main():
  print(f"Solution of example data is:\n{solve(get_data(False))}\n")
  print(f"Solution of real data is:\n{solve(get_data(True))}\n")
  

def sanitize_data_of_today(data_from_file: list) -> list:
  displays = []
  for display in data_from_file:
    unique_patterns, output_values = parse("{} | {}", display)
    
    unique_patterns = unique_patterns.split(" ")
    # In each pattern, sort the letters alphabetically lexicographically
    unique_patterns = ["".join(sorted(s)) for s in unique_patterns]
    # Sort the patterns, the shortest first, then lexicographically
    unique_patterns.sort(key = lambda x: (len(x), x))
    
    output_values = output_values.split(" ")
    output_values = ["".join(sorted(s)) for s in output_values]
    
    displays.append({"patterns": unique_patterns, "outputs": output_values})
    
  return displays


def get_data(use_real_input = False) -> list:
  day = "day8"
  example_input = """
acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab | cdfeb fcadb cdfeb cdbaf
  """
  example_input = """
be cfbegad cbdgef fgaecd cgeb fdcge agebfd fecdb fabcd edb | fdgacbe cefdb cefbgd gcbe
edbfga begcd cbg gc gcadebf fbgde acbgfd abcde gfcbed gfec | fcgedb cgb dgebacf gc
fgaebd cg bdaec gdafb agbcfd gdcbef bgcad gfac gcb cdgabef | cg cg fdcagb cbg
fbegcd cbd adcefb dageb afcb bc aefdc ecdab fgdeca fcdbega | efabcd cedba gadfec cb
aecbfdg fbg gf bafeg dbefa fcge gcbea fcaegb dgceab fcbdga | gecf egdcabf bgf bfgea
fgeab ca afcebg bdacfeg cfaedg gcfdb baec bfadeg bafgc acf | gebdcfa ecba ca fadegcb
dbcfg fgd bdegcaf fgec aegbdf ecdfab fbedc dacgb gdcebf gf | cefg dcbef fcge gbcadfe
bdfegc cbegaf gecbf dfcage bdacg ed bedf ced adcbefg gebcd | ed bcgafe cdgba cbgef
egadfb cdbfeg cegd fecab cgb gbdefca cg fgcdab egfdb bfceg | gbdfcae bgc cg cgb
gcafb gcf dcaebfg ecagb gf abcdeg gaef cafbge fdbac fegbdc | fgae cfgab fg bagce
"""
  if not use_real_input:
    used_input = example_input
    
  else:
    with open(f"input_data/{day}.txt", "r") as input_file:
      used_input = input_file.read()
      
  used_input = used_input.strip().split("\n")
  return sanitize_data_of_today(used_input)

  
if __name__ == "__main__":
  main()

[narpfel]

Meine Lösung für 2021 Tag 8 war ein bisschen kürzer:

Code: Alles auswählen

E={1:2,4:4,7:3,8:7}
f=frozenset;D=[(map(f,(a:=l.split())[:10]),map(f,a[11:]))for l in open("i")]
q=Q=0
for P,d in D:
 l={k:[]for k in range(9)}
 for p in P:l[len(p)]+=[p]
 m={d:l[E[d]][0]for d in E}
 for p in l[6]:m[p>=m[4]|m[7]and 9or not p>=m[1]and 6or 0]=p
 for p in l[5]:m[p>=m[1]and 3or p<m[6]and 5or 2]=p
 m={m[k]:k for k in m};n="".join(str(m[i])for i in d);q+=sum(int(i)in E for i in n);Q+=int(n)
print(q,Q)

Aber Tipps für Datenstrukturen kann ich mit dem Code eher nicht mehr geben.