Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Folgende BASIC Lösung für Tag 2 braucht 3½ Minuten auf einem VIC-20 und auch am zweiten Tag kommt man noch mit dem bisschen Original-RAM aus:

Code: Alles auswählen

   10 TI$="000000":R1=0:R2=0:OPEN 2,8,2,"INPUT02,S"
   20 IF ST<>0 THEN CLOSE 2:GOTO 500
   30 INPUT#2,L$
   40 A=ASC(MID$(L$,1,1))-65
   50 B=ASC(MID$(L$,3,1))-88
   60 GOSUB 700:R1=R1+O
   70 GOSUB 600:R2=R2+O:GOTO 20
  500 PRINT R1,R2:PRINT TI$:END
  600 ON B GOTO 630,640
  610 B=A-1:IF B<0 THEN B=2
  620 GOTO 700
  630 B=A:GOTO 700
  640 B=A+1:IF B=3 THEN B=0
  700 O=B+1
  710 IF A=B THEN O=O+3:RETURN
  720 IF A=0 AND B=1 OR A=1 AND B=2 OR A=2 AND B=0 THEN O=O+6
  730 RETURN
Wie man sieht ist es eigentlich recht einfach das in *einem* Programm zu lösen. Für den zweiten Teil muss man ja eigentlich nur den eigenen Move entsprechend anpassen (hier ab Zeile 600) und kann dann die gleiche Unterroutine zur Bewertung (hier ab Zeile 700) verwenden. Hätte fast „aufrufen“ geschrieben, aber es gibt hier nur eine Unterroutine mit zwei Einsprungspunkten (600 und 700). Nehmt das ihr komischen „strukturierten“ Programmiersprachen. 😜
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
narpfel
User
Beiträge: 643
Registriert: Freitag 20. Oktober 2017, 16:10

Meine dumme gegolfte Lösung ist 141 Zeichen lang. :cry:

Code: Alles auswählen

print(sum({"A X":4+3j,"A Y":8+4j,"A Z":3+8j,"B X":1+1j,"B Y":5+5j,"B Z":9+9j,"C X":7+2j,"C Y":2+6j,"C Z":6+7j}[l.strip()]for l in open("i")))
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

narpfel hat geschrieben: Freitag 2. Dezember 2022, 18:35 Meine dumme gegolfte Lösung ist 141 Zeichen lang. :cry:
Die Idee mit den komplexen Zahlen finde ich aber exzellent! :) Bei mir in AWK sind es hingegen nur stumpfe Look-Up-Tabellen geworden.
Benutzeravatar
Dennis89
User
Beiträge: 1124
Registriert: Freitag 11. Dezember 2020, 15:13

Hallo,

bin gerade an Teil 1, leider ist mein Ergebnis zu hoch.
Ich habe zum Beispiel ein Rucksack mit diesem Tascheninhalt:

Code: Alles auswählen

['GRRjbVjmJ', 'ZlgMRzzrN']
In der ersten Tasche sind zwei "R" und in der zweiten eins. Muss ich das irgendwie besonders behandeln?

Mein aktueller Stand ist dieser:

Code: Alles auswählen

#!/usr/bin/env python3
import string
from pathlib import Path

ITEMS_FILE = Path(r"C:\Users\Dennis\Documents\items.txt")


def read_file(file):
    with open(file, encoding="UTF-8") as items_file:
        return [line.strip("\n") for line in items_file]


def split_in_two_compartments(rucksacks):
    return [
        [compartments[: len(compartments) // 2], compartments[len(compartments) // 2 :]]
        for compartments in rucksacks
    ]


def find_common_items(rucksacks):
    common_items = []
    for rucksack in rucksacks:
        for item in rucksack[0]:
            if item in rucksack[1]:
                common_items.append(item)
    return common_items


def calculate_priority(items):
    priority = []
    for item in items:
        if item.islower():
            priority.append(string.ascii_lowercase.find(item) + 1)
        else:
            priority.append(string.ascii_uppercase.find(item) + 27)
    return sum(priority)


def main():
    rucksacks = read_file(ITEMS_FILE)
    rucksacks_with_split_compartments = split_in_two_compartments(rucksacks)
    common_items = find_common_items(rucksacks_with_split_compartments)
    print(calculate_priority(common_items))


if __name__ == "__main__":
    main()
Danke und Grüße
Dennis
"When I got the music, I got a place to go" [Rancid, 1993]
Benutzeravatar
sparrow
User
Beiträge: 4165
Registriert: Freitag 17. April 2009, 10:28

@Dennis89: Es ist explizit nach dem Buchstaben gefragt, der in beiden "compartments" des Rocksacks vorkommt. Also keine Sonderbehandlung.
Benutzeravatar
Whitie
User
Beiträge: 216
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Ich hab das mit Set's gelöst.
Benutzeravatar
Dennis89
User
Beiträge: 1124
Registriert: Freitag 11. Dezember 2020, 15:13

Danke für die schnelle Antwort.
"R" kommt in beiden compartments vor und ist im ganzen Rucksack aber 3 mal enthalten. So wie ich aktuell suche wird mir "R" zwei mal in die Liste der gleichen Teile hinzugefügt. Finde ich auch logisch, da ja jedes Teil nur einmal im Rucksack sein soll, also müssen aus dem zwei "R" 's raus. Wenn ich das bis hier hin richtig verstanden habe, muss ich mein Fehler wo anders suchen.

An welcher Stelle hast du ein Set benutzt? Beim auflisten der gleichen Teile kann ich das ja nicht nehmen, es ist a bestimmt so, dass das "R" zum Beispiel in einem anderen Rucksack auch zwei mal drin ist.

Grüße
Dennis
"When I got the music, I got a place to go" [Rancid, 1993]
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@Dennis89: Da würde ich an jeder Stelle `set()`\s benutzen. Sozusagen. Die ganze Aufgabe schreit ja förmlich „Mengenoperationen“. Man sucht ja den Gegenstandstyp der in beiden Rucksachfächern vorkommt. Also die Schnittmenge — die genau ein Element enthält für jeden Rucksack.

Mal so am Rande: Ich habe gerade noch einen Fehler in meiner BASIC-Lösung entdeckt der ”zufällig” keinen Einfluss auf das Ergebnis hat. Und zwar scheint die Eingabe zu garantieren, das jede Elfengruppe zusammen *alle* Gegenstandstypen haben. Aus dem Aufgabentext wird das IMHO nicht wirklich klar. Ist aber praktisch, weil es sonst meine Lösung etwas komplexer machen würde. 😉
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
sparrow
User
Beiträge: 4165
Registriert: Freitag 17. April 2009, 10:28

@Dennis89: Es wird nach dem Teil gesucht, dass in beiden "compartments" enthalten ist. Wie oft wird nirgends gefragt. Dafür also eine Liste aufzubauen ist unnötig.
Was ist sowohl in 'GRRjbVjmJ' als auch in 'ZlgMRzzrN': R
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Na dann hau ich mal meine Lösung für Tag 3 raus.
Verbesserungsvorschläge sind erwünscht.

Code: Alles auswählen

def calc(value):
    prio = ord(value) - 96
    if prio < 0: prio += 58
    return prio

def priority(sacks):
    packs = list(map(set, sacks))
    return calc((set.intersection(*packs)).pop())

data = open("input.txt").read().split("\n")[:-1]
mid = lambda x: len(x) // 2
data1 = [[pack[:mid(pack)], pack[mid(pack):]] for pack in data]
data2 = [data[i:i+3] for i in range(0, len(data), 3)]

print("Part 1:", sum(map(priority, data1)))
print("Part 2:", sum(map(priority, data2)))
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
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@ThomasL: Das `mid` eine Lambdafunktion ist, statt gleich der Index macht nicht so wirklich Sinn. Und das erste `split()` ist ”falsch”. Genau für diesen Anwendungszweck gibt es die `splitlines()`-Methode. Man muss nix wegwerfen am Ende der Liste und das funktioniert egal ob die letzte Zeile mit einem "\n" endet oder nicht.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

Dennis89 hat geschrieben: Samstag 3. Dezember 2022, 17:29 An welcher Stelle hast du ein Set benutzt? Beim auflisten der gleichen Teile kann ich das ja nicht nehmen, es ist a bestimmt so, dass das "R" zum Beispiel in einem anderen Rucksack auch zwei mal drin ist.
Hier mal mein Ansatz mit Mengen:

Code: Alles auswählen

#!/usr/bin/env python3
import fileinput
from string import ascii_letters
from itertools import cycle

PRIOS = {char: i for i, char in enumerate(ascii_letters, 1)}


def iter_rucksacks():
    for rucksack in fileinput.input():
        rucksack = rucksack.rstrip()
        if rucksack:
            if len(rucksack) % 2:
                raise ValueError
            size = len(rucksack) // 2
            yield set(rucksack[:size]), set(rucksack[size:])


def main():
    sums = 0
    group_sums = 0
    for i, rucksack in zip(cycle(range(3)), iter_rucksacks()):
        left, right = rucksack
        common = left & right
        sums += sum(PRIOS[item] for item in common)
        if i == 0:
            group_badges = left | right
        else:
            group_badges &= left | right
        if len(group_badges) == 1:
            group_sums += PRIOS[group_badges.pop()]
    print(sums)
    print(group_sums)


if __name__ == "__main__":
    main()

Zuletzt geändert von nezzcarth am Samstag 3. Dezember 2022, 18:48, insgesamt 3-mal geändert.
narpfel
User
Beiträge: 643
Registriert: Freitag 20. Oktober 2017, 16:10

Verbesserungsvorschläge: Die Lösungen hier finde ich bis jetzt alle zu lang und zu leserlich, so wäre es schöner (231 Zeichen):

Code: Alles auswählen

from string import ascii_letters as A
B=set(A).intersection
from more_itertools import chunked as C
r=list(map(str.strip,open("i")))
print(sum(A.find(B(*C(t,len(t)//2)).pop())+1for t in r),sum(A.find(B(*g).pop())+1for g in C(r,3)))
Benutzeravatar
Dennis89
User
Beiträge: 1124
Registriert: Freitag 11. Dezember 2020, 15:13

Danke für eure Hilfe.
Ohne eure Ansätze angeschaut zu haben, habe ich jetzt den ersten Teil mit Set und '&'-Operator hinbekommen.

Part 2 wird mir heute nicht mehr reichen, wenn ich das habe schaue ich mir eure Lösungen an.

Grüße
Dennis
"When I got the music, I got a place to go" [Rancid, 1993]
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@narpfel: Ist länger als Deins, aber sicherlich nicht lesbarer und läuft in 6m53s auf dem VIC-20:

Code: Alles auswählen

   10 TI$="000000":R1=0:R2=0:DIM P(255),C(52),C2(52)
   20 P=1:FOR I=ASC("A") TO ASC("Z"):P(I)=P:P=P+1:NEXT
   30 FOR I=ASC("A") TO ASC("Z"):P(I)=P:P=P+1:NEXT
   40 FOR I=1 TO 52:C2(I)=1:NEXT
  100 OPEN 2,8,2,"INPUT03,S":LC=0
  110 IF ST<> 0 THEN CLOSE 2:GOTO 999
  120 FOR I=1 TO 52:C(I)=0:NEXT
  130 INPUT#2,L$:L=LEN(L$):M=L/2:LC=LC+1
  140 FOR I=1 TO M
  150 C(P(ASC(MID$(L$,I,1))))=1
  160 NEXT:FOR I=M+1 TO L
  170 P=P(ASC(MID$(L$,I,1)))
  180 IF C(P) THEN R1=R1+P:GOTO 200
  190 NEXT:STOP
  200 FOR I=M+1 TO L
  210 C(P(ASC(MID$(L$,I,1))))=1:NEXT
  220 FOR I=1 TO 52:C2(I)=C2(I) AND C(I):NEXT
  230 IF LC<>3 THEN 110
  240 FOR I=1 TO 52:IF C2(I) THEN R2=R2+I
  250 C2(I)=1:NEXT:LC=0:GOTO 110
  999 PRINT R1,R2:PRINT TI$
Nach GW-BASIC portiert ca 5m auf einem 8088er-PC, also kaum schneller, und das trotz mehr als 4× die Taktrate und schnellerem Dateizugriff:

Code: Alles auswählen

10 T1!=TIMER:DEFINT A-Z:R1=0:R2=0:DIM P(255),C(52),C2(52)
20 P=1:FOR I=ASC("a") TO ASC("z"):P(I)=P:P=P+1:NEXT
30 FOR I=ASC("A") TO ASC("Z"):P(I)=P:P=P+1:NEXT
40 FOR I=1 TO 52:C2(I)=1:NEXT:DEF FN P(I)=P(ASC(MID$(L$,I,1)))
50 OPEN "input03.txt" FOR INPUT AS #1:LC=0
60 WHILE NOT EOF(1):LINE INPUT#1,L$:LC=LC+1:L=LEN(L$):M=L\2
70 FOR I=1 TO 52:C(I)=0:NEXT:FOR I=1 TO M:C(FN P(I))=1:NEXT
80 FOR I=M+1 TO L:P=FN P(I):IF C(P) THEN R1=R1+P:GOTO 100
90 NEXT:STOP:REM No common item error.
100 FOR I=M+1 TO L:C(FN P(I))=1:NEXT
110 FOR I=1 TO 52:C2(I)=C2(I) AND C(I):NEXT:IF LC<>3 THEN 135
120 FOR I=1 TO 52:IF C2(I) THEN R2=R2+I
130 C2(I)=1:NEXT:LC=0
135 WEND:CLOSE 1
140 PRINT R1,R2:PRINT"In";TIMER-T1!;"seconds."
Bei der 1m18s die der QBasic-Port läuft weiss man dann schon eher warum man 1983 so schweineviel Geld ausgegeben hat im Vergleich zum VIC-20 — wenn man auf QBasic nicht noch fast 10 Jahre hätte warten müssen:

Code: Alles auswählen

DECLARE FUNCTION GetPrio% (s AS STRING, i AS INTEGER)
DECLARE SUB InitItemSet (s() AS INTEGER, value AS INTEGER)
DECLARE SUB TickItems (s() AS INTEGER, L AS STRING, a AS INTEGER, b AS INTEGER)

t1 = TIMER
DIM SHARED Byte2Prio(255) AS INTEGER
DIM items(52) AS INTEGER, groupItems(52) AS INTEGER
DIM r1 AS INTEGER, r2 AS INTEGER, p AS INTEGER, lc AS INTEGER
DIM i AS INTEGER, length AS INTEGER, middle AS INTEGER

' Init lookup table ASCII code -> priority.
p = 1
FOR i = ASC("a") TO ASC("z"): Byte2Prio(i) = p: p = p + 1: NEXT
FOR i = ASC("A") TO ASC("Z"): Byte2Prio(i) = p: p = p + 1: NEXT

r1 = 0: r2 = 0: lc = 0
InitItemSet groupItems(), 1
OPEN "input03.txt" FOR INPUT AS #1
DO WHILE NOT EOF(1)
  LINE INPUT #1, L$: length = LEN(L$): middle = length \ 2
  ' Part 1
  InitItemSet items(), 0
  TickItems items(), L$, 1, middle
  FOR i = middle + 1 TO length
    p = GetPrio(L$, i): IF items(p) THEN r1 = r1 + p: EXIT FOR
  NEXT

  ' Part 2
  TickItems items(), L$, middle + 1, length
  FOR i = 1 TO 52: groupItems(i) = groupItems(i) AND items(i): NEXT
  lc = lc + 1
  IF lc = 3 THEN ' Group complete.
    lc = 0
    FOR i = 1 TO 52
      IF groupItems(i) THEN r2 = r2 + i: EXIT FOR
    NEXT
    InitItemSet groupItems(), 1
  END IF
LOOP
CLOSE 1: PRINT r1, r2: PRINT "In"; TIMER - t1; "seconds."

FUNCTION GetPrio% (s AS STRING, i AS INTEGER)
  GetPrio = Byte2Prio(ASC(MID$(s, i, 1)))
END FUNCTION

SUB InitItemSet (s() AS INTEGER, value AS INTEGER)
  DIM i AS INTEGER
  FOR i = 1 TO 52: s(i) = value: NEXT
END SUB

SUB TickItems (s() AS INTEGER, L AS STRING, a AS INTEGER, b AS INTEGER)
  DIM i AS INTEGER
  FOR i = a TO b: s(GetPrio(L, i)) = 1: NEXT
END SUB
In diesem strukturierteren Quelltext war mir übrigens erst aufgefallen, das ich die ”angefangene” Menge `items`/`C()` aus dem ersten Teil in Teil 2 einfach vervollständigen kann, statt das nochmal komplett neu zu machen. Liess sich wie man sieht auch einfach auf die beiden vorherigen Varianten zurück portieren.

So wirklich schnell wurde es dann aber erst mit einer Pascal-Lösung: 2,8s, also mehr als 100mal schneller als GW-BASIC:

Code: Alles auswählen

type
  TPrio = 1..52;
  TItems = set of TPrio;

const
  AllItems = [Low(TPrio)..High(TPrio)];

var
  charToPrioTable: array[0..255] of TPrio;
  r1, r2: Word;
  f: Text;
  lineCount: Byte;
  line: String;
  middle: Byte;
  items, groupItems: TItems;
  prio: TPrio;
  i: Byte;

procedure Init;
var
  i: Byte;
  p: TPrio;
begin
  FillChar(charToPrioTable, SizeOf(charToPrioTable), 0);
  p := 1;
  for i := Ord('a') to Ord('z') do
    begin
      charToPrioTable[i] := p;
      Inc(p);
    end;
  for i := Ord('A') to Ord('Z') do
    begin
      charToPrioTable[i] := p;
      Inc(p);
    end;
end;

function CharToPrio(c: Char): TPrio;
begin
  CharToPrio := charToPrioTable[Ord(c)];
end;

procedure IncludeItems(var items: TItems; const line: String; i, j: Byte);
begin
  for i := i to j do Include(items, CharToPrio(line[i]));
end;

begin
  Init;
  Assign(f, 'input03.txt');
  Reset(f);
  r1 := 0; r2 := 0; lineCount := 0; groupItems := AllItems;
  while not Eof(f) do
    begin
      ReadLn(f, line);
      middle := Length(line) DIV 2;
      items := [];
      { Part 1 }
      IncludeItems(items, line, 1, middle);
      for i := middle + 1 to Length(line) do
        begin
          prio := CharToPrio(line[i]);
          if prio in items then
            begin
              Inc(r1, prio);
              Break;
            end;
        end;

      { Part 2 }
      IncludeItems(items, line, middle + 1, Length(line));
      groupItems := groupItems * items;
      Inc(lineCount);
      if lineCount = 3 then
        begin
          lineCount := 0;
          for prio := Low(TPrio) to High(TPrio) do
            begin
              if prio in groupItems then
                begin
                  Inc(r2, prio);
                  Break;
                end;
            end;
        groupItems := AllItems;
        end;
    end;
  Close(f);
  WriteLn(r1, ' ', r2);
end.
An der Lösung fand ich interessant, dass Pascal einen Mengentyp hat.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

@__blackjack__: Was für ein Pascal ist das? All die Jahre wusste ich nicht, dass man "program ..." am Anfang weglassen kann ... Free Pascal übersetzt das anstandslos... :shock:
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

__blackjack__ hat geschrieben: Samstag 3. Dezember 2022, 18:18 @ThomasL: Das `mid` eine Lambdafunktion ist, statt gleich der Index macht nicht so wirklich Sinn.
Hi __blackjack__, danke für den Hinweis auf .splitlines(), irgendwie hatte ich die nicht mehr auf dem Schirm.

Aber den ersten Hinweis verstehe ich nicht.

Code: Alles auswählen

mid = lambda x: len(x) // 2
data1 = [[pack[:mid(pack)], pack[mid(pack):]] for pack in data]
pack ist ja immer ein unterschiedlich langer (gerade Anzahl) String. mid berechnet die Länge der Hälfte. Wie meinst du das mit Index?
Danke im Voraus.
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
Benutzeravatar
sparrow
User
Beiträge: 4165
Registriert: Freitag 17. April 2009, 10:28

@ThomasL:

Code: Alles auswählen

mid = lambda x: len(x) // 2
data1 = [[pack[:mid(pack)], pack[mid(pack):]] for pack in data]
wird zu:

Code: Alles auswählen

mid = len(pack) // 2
data1 = [[pack[:mid], pack[mid:]] for pack in data]
Die Lambdafunktion ist unnötig. Sowohl was die Lesbarkeit betrifft als auch vor dem Hintergrund, dass du sie 2 Mal aufrufst und damit 2 Mal die Mitte des Strings bestimmst.

Edit: Der Code ist ungetestet und ich habe das len vergessen :ugeek:
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

@sparrow:

Das kann doch so nicht funktionieren. pack ist erstens außerhalb der list comprehension nicht definiert und innerhalb hat es immer eine andere Länge.
Ich verstehe euch nicht.
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
Benutzeravatar
sparrow
User
Beiträge: 4165
Registriert: Freitag 17. April 2009, 10:28

@ThomasL: Sorry, da war ich wohl gesten etwas müde und habe die Comprehension an der Stelle übersehen

Ich persönlich würde an der Stelle keine LC verwenden. Für mich macht das den Code nicht wirklich schöner zu lesen. Aber das ist vielleicht persönliche Ansicht.

Trotzdem braucht es kein lambda und die doppelte Berechnung des Wertes:

Code: Alles auswählen

data1 = [
    [pack[:mid], pack[mid:]] for pack in data
    for mid in (len(pack) // 2,)
]
Antworten