Advent of Code

[kbr]

Schaut bei mir ein wenig anders aus:

Code: Alles auswählen

def decode_instruction(code):
    pm, opc = divmod(code, 100)
    a, b = divmod(pm, 100)
    b, c = divmod(b, 10)
    return [a, b, c], opc

[__blackjack__]

Jetzt ist mir mein Code definitiv peinlich.

Edit: Ein einzelner Schritt meines Prozessors:

Code: Alles auswählen

    def do_step(self):
        value = self.memory[self.instruction_pointer]
        value, opcode = divmod(value, 100)

        instruction = self.opcode_to_instruction.get(opcode)
        if instruction is None:
            raise ValueError(
                f"illegal opcode {opcode} at {self.instruction_pointer}"
            )

        parameter_modes = [
            ParameterMode(int(digit)) for digit in str(value).zfill(3)
        ]
        if instruction.execute(
            self, *parameter_modes[::-1][: instruction.length - 1]
        ):
            self.instruction_pointer += instruction.length

[nezzcarth]

Eine Frage an die Informatiker: Ich habe vor einiger Zeit mal etwas über Quadtrees gelesen. Wäre Tag 24.2 vielleicht eine (gute) Anwendung für so etwas? Ich weiß noch nicht genau, wie ich das rekursive Grid darstelle, aber es wird wohl auf eine Art Baum bzw. Graph hinaus laufen.

[ThomasL]

Du denkst da etwas zu komplex. Eine Liste mit 220 Listen á 25 Integer (oder Boolean) reicht völlig aus.
ebene[110] ist Level 0, das äußere Grid ist +1, das innere -1, etc.
Viel Spaß.
(Wenn du absolut keine Lösung findest poste ich gerne Code.)

[ThomasL]

Habe bei Advent of Code 2019 42 Sterne bis heute erreicht, die restlichen 7 werde ich die nächsten Wochen nacharbeiten.
Es hat viel Spaß gemacht, insbesondere die heutige Tag 25 Teil 1 war die Krönung imho.

[nezzcarth]

Du denkst da etwas zu komplex. Eine Liste mit 220 Listen á 25 Integer (oder Boolean) reicht völlig aus.
ebene[110] ist Level 0, das äußere Grid ist +1, das innere -1, etc.
Viel Spaß.
(Wenn du absolut keine Lösung findest poste ich gerne Code.)

Na ja, für mich ist das Teil des Spaßes, mit verschieden (ggf. auch etwas überzogenen) Ansätzen zu experimentieren. Insofern passt das schon; aber danke

[__blackjack__]

Ich bin seit Tag 14 mehr oder weniger raus gewesen. Danach nur noch 4 sehr verteilte Sterne erarbeitet. Insgesamt 29.

[__blackjack__]

Auch die Ereignisse in diesem bewegten Pandemie-Jahr konnten nicht verhindern, dass wir dem Weihnachtsmann wieder bei der Erfüllung seiner Mission helfen dürfen. Unter der altbekannten URL geht es am 1. Dezember um 6 Uhr Mitteleuropäischer Zeit los: https://adventofcode.com/

[nezzcarth]

In Python ist heutige Aufgabe zwar in ein paar Minuten erledigt, aber meistens konnte man zumindest den ersten Tag (oft sogar die ersten paar Tage) auch in einer Zeile mit gängigen Kommandozeilentools lösen. Dieses Jahr sehe ich dafür keinen echten Ansatzpunkt ...

Für Teil 1 habe ich noch was halbwegs funktionierendes gefunden. Für Teil 2 ist das aber nicht praktikabel:

Code: Alles auswählen

$ parallel -a day01.txt -a day01.txt echo | awk '$1 + $2 == 2020 {print $1 * $2 ; exit}'               

Schade.

[narpfel]

@nezzcarth: Mit einem kleinen Trick ist Teil 2 mit deiner Lösung sogar schneller als Teil 1:

Code: Alles auswählen

» time parallel -a input -a input echo | awk '$1 + $2 == 2020 {print $1 * $2; exit}'
1013211
parallel -a input -a input echo  8,10s user 2,73s system 244% cpu 4,424 total
awk '$1 + $2 == 2020 {print $1 * $2; exit}'  0,02s user 0,01s system 0% cpu 4,424 total
» time parallel -a input -a input -a input echo | awk '$1 + $2 + $3 == 2020 {print $1 * $2 * $3; exit}'
13891280
parallel -a input -a input -a input echo  3,07s user 1,11s system 231% cpu 1,802 total
awk '$1 + $2 + $3 == 2020 {print $1 * $2 * $3; exit}'  0,01s user 0,00s system 0% cpu 1,798 total

[nezzcarth]

Tatsache! Das numerisch zu sortieren habe ich dann natürlich nicht mehr versucht … Bei mir ist zwar Teil 2 trotzdem noch langsamer, aber geht nun in wenigen Sekunden. Wie schön. Danke für den Tipp.

[__blackjack__]

Boah ist das alles schnell. Bei mir hat der C64 für den zweiten Teil 4 Stunden, 44 Minuten, und 40 Sekunden gebraucht. In BASIC.

Der erste Teil war in einer Minute und sechs Sekunden durch.

Code: Alles auswählen

   10 PRINT"READ EXPENSES...":DIM E(200):FOR I=1 TO 200:READ E(I):NEXT
  100 TI$="000000":FOR I=1 TO 199:FOR J=I+1 TO 200
  110 IF E(I)+E(J)=2020 THEN PRINT E(I)*E(J):GOTO 200
  120 NEXT:NEXT:PRINT"ERROR PART 1!"
  200 PRINT"PART 1: "TI$:TI$="000000"
  210 FOR I=1 TO 198:FOR J=I+1 TO 199:FOR K=J+1 TO 200
  220 IF E(I)+E(J)+E(K)=2020 THEN PRINT E(I)*E(J)*E(K):GOTO 300
  230 NEXT:NEXT:NEXT:PRINT"ERROR PART 2!"
  300 PRINT"PART 2: "TI$:END
 9000 DATA 1889,1974,1983,1590,1530,1402,1731,1935,1404,1763,1733,1234,1706,633
 9010 DATA 1524,880,1970,1815,1766,1587,1329,1386,1769,1709,1816,1672,75,1874
 9020 DATA 1957,1241,1656,1290,1501,1456,1945,1375,1580,1738,1581,1704,1317,1651
 9030 DATA 1971,1614,1668,1694,1862,562,1497,1460,1768,1797,1828,728,1826,1519
 9040 DATA 1343,1850,1676,1932,1794,1295,1669,1995,1838,1253,1209,1288,1443,1436
 9050 DATA 1788,1732,1289,74,1659,1264,1533,1938,1401,1748,1445,1941,1924,1807
 9060 DATA 1772,1761,1805,1658,927,1294,1643,1308,1472,1822,1332,1220,1947,1352
 9070 DATA 1782,1851,1789,1551,1490,1690,1989,1052,1340,1437,1378,1316,1835,1967
 9080 DATA 1885,1487,1452,1480,1943,1760,1897,1632,1354,1843,1698,1467,1625,1421
 9090 DATA 1482,1275,1341,1422,1586,1283,1686,1640,1987,1603,1131,1777,1864,1529
 9100 DATA 1858,1665,1326,1804,1285,1449,1866,1762,1708,1699,1622,1774,1993,1796
 9110 DATA 1825,1786,1518,1726,1577,1545,1494,1756,1611,2005,1888,1930,1538,1744
 9120 DATA 894,1537,1513,1650,1898,1719,1615,1646,1758,1495,1717,1670,1759,1865
 9130 DATA 1793,1484,1702,1861,1330,1767,1549,1536,717,2007,1902,1583,1682,1374
 9140 DATA 1892,1839,1771,1624

[snafu]

Tatsache! Das numerisch zu sortieren habe ich dann natürlich nicht mehr versucht … Bei mir ist zwar Teil 2 trotzdem noch langsamer, aber geht nun in wenigen Sekunden. Wie schön. Danke für den Tipp.

Wir reden von Tag 1? Also bei mir liefen beide Teile in weniger als 1 Sekunde durch. Eigentlich musste man nur eine Funktion basteln, die als Parameter die Anzahl der Elemente pro Kombination (hier: 2 oder 3) annimmt. Den Rest haben ein bekanntes Builtin, sowie etwas aus dem itertools-Modul und etwas relativ neues aus dem math-Modul für mich erledigt.

[nezzcarth]

@snafu: Ja, Tag 1, genau. Allerdings ging es mir bei der Aussage nur um die gezeigte Lösung mit GNU Parallel, das ja das kartesische Produkt erzeugt; also viel mehr, als nötig wäre.
Ich habe die Aufgabe vorher in Python gelöst und da war die Geschwindigkeit, wie du schon meintest, kein Thema (allerdings mittels umstrittenem Ex-Builtin aus dem functools-Modul )

[snafu]

@nezzcarth: Okay, hatte mich schon gewundert.

Tag 2 ist auch erledigt. Der zweite Teil war sehr exklusiv.

[ThomasL]

Tag 1 und 2 sind ja immer zum warm laufen. Mich würde interessieren, ob meine Lösungen noch optimiert werden könnten.

Code: Alles auswählen

# Tag 1 mit Python 3.7
with open('input.txt', 'r') as file:
    data = {int(number) for number in file}

# Part 1
print({entry * (2020 - entry) for entry in data if (2020 - entry) in data})

# Part 2
print({entry1 * entry2 * (2020 - entry1 - entry2) 
       for entry1 in data for entry2 in data 
       if (2020 - entry1 - entry2) in data})

Code: Alles auswählen

# Tag 1 mit Python 3.8
with open('input.txt', 'r') as file:
    data = {int(number) for number in file}

# Part 1
print({entry * difference for entry in data if (difference := 2020 - entry) in data})

# Part 2
print({entry1 * entry2 * difference 
       for entry1 in data for entry2 in data 
       if (difference := 2020 - entry1 - entry2) in data})

Code: Alles auswählen

# Tag 2
from collections import defaultdict

with open('input.txt') as file:
    data = [line.replace('-', ' ').replace(': ', ' ').strip().split() for line in file]

# Part 1
def policy1(minu, maxu, letter, password):
    counts = defaultdict(int)
    for char in password:
        counts[char] += 1
    return int(minu) <= counts[letter] <= int(maxu)

print(sum(policy1(*line) for line in data))

# Part 2
def policy2(minu, maxu, letter, password):
    rule1 = password[int(minu) - 1] == letter
    rule2 = password[int(maxu) - 1] == letter
    return (rule1 and not rule2) or (not rule1 and rule2)

print(sum(policy2(*line) for line in data))

[DasIch]

Tag 2 in io:

Code: Alles auswählen

SledPasswordPolicy := Object clone do(
	lowerBound ::= nil
	upperBound ::= nil
	letter ::= nil

	fromString := method(string, 
		parts := string split
		range := parts at(0) split("-")
		SledPasswordPolicy clone
			setLowerBound(range at(0) asNumber)
			setUpperBound(range at(1) asNumber)
			setLetter(parts at(1))
	)

	isValid := method(password,
		count := password occurrencesOfSeq(letter)
		count >= lowerBound and count <= upperBound
	)
)

// We could define this as a proper operator but it would only affect files not parsed
// by the interpreter, yet. So it wouldn't have any impact on this file :(
true xor := method(right, right not)
false xor := method(right, right)

TobogganPasswordPolicy := Object clone do(
	firstPosition ::= nil
	secondPosition ::= nil
	letter ::= nil

	fromString := method(string, 
		parts := string split
		range := parts at(0) split("-")
		TobogganPasswordPolicy clone
			setFirstPosition(range at(0) asNumber)
			setSecondPosition(range at(1) asNumber)
			setLetter(parts at(1))
	)

	isValid := method(password,
		matchAtFirstPosition := password at(firstPosition - 1) asCharacter == letter
		matchAtSecondPosition := password at(secondPosition - 1) asCharacter == letter
		matchAtFirstPosition xor(matchAtSecondPosition)
	)
)



file := File clone openForUpdating("day02.input")
lines := file readLines
file close

validSledPasswords := 0
validTobogganPasswords := 0

lines foreach(line,
	parts := line split(": ")
	sledPasswordPolicy := SledPasswordPolicy fromString(parts at(0))
	tobogganPasswordPolicy := TobogganPasswordPolicy fromString(parts at(0))
	password := parts at(1)
	(sledPasswordPolicy isValid(password) or tobogganPasswordPolicy isValid(password)) ifTrue(line println)
	sledPasswordPolicy isValid(password) ifTrue(
		validSledPasswords = validSledPasswords + 1
	)
	tobogganPasswordPolicy isValid(password) ifTrue(
		validTobogganPasswords = validTobogganPasswords + 1
	)
)
"Valid Sled Rental Passwords: " print
validSledPasswords println

"Valid Toboggan Passwords: " print
validTobogganPasswords println

[__blackjack__]

Auch Tag 2 ging noch problemlos in BASIC auf dem C64:

Code: Alles auswählen

   10 TI$="000000":OPEN 2,8,2,"INPUT02,S,R":LN=1:CA=0:CB=0
   20 IF ST<>0 THEN 9000
   30 A=0:REM READ NUMBER A
   40 GET#2,C$:IF C$="-" THEN 60
   50 A=A*10+VAL(C$):GOTO 40
   60 B=0:REM READ NUMBER B
   70 GET#2,C$:IF C$=" " THEN 90
   80 B=B*10+VAL(C$):GOTO 70
   90 REM READ LETTER, SKIP ": ", READ PASSWORD
  100 GET#2,L$:GET#2,C$:GET#2,C$:INPUT#2,PW$
  110 PRINT LN:PRINT"{UP}";:LN=LN+1
 1000 REM SLED RULES
 1010 C=0:FOR I=1 TO LEN(PW$):IF MID$(PW$,I,1)=L$ THEN C=C+1
 1020 NEXT:IF A<=C AND C<=B THEN CA=CA+1
 2000 REM TOBOGGAN RULES
 2010 A$=MID$(PW$,A,1):B$=MID$(PW$,B,1)
 2020 IF A$=L$ AND B$<>L$ OR A$<>L$ AND B$=L$ THEN CB=CB+1
 8990 GOTO 20
 9000 CLOSE 2:PRINT:PRINT CA,CB,TI$

Ca. 5½ Minuten — der Datendurchsatz bei der Floppy ist unterirdisch.

[snafu]

@ThomasL
Der Ansatz für Tag 1 lässt sich noch verbessern, wenn man nicht über ein Set geht, sondern den jeweiligen Generator an next() übergibt. Dann steigt man nämlich bei der Fundstelle aus und macht nicht bis zum Ende weiter.

Tag 2 hätte bzw habe ich mit der count()-Methode auf Zeichenketten gelöst und nichts händisch durchgezählt. Die Bedingung für den zweiten Teil lässt sich auch mittels XOR-Operator ausdrücken, dann muss man dessen Logik nicht nachbauen.

Die Varianten hatte ich ja schon auf Twitter gezeigt, wobei deins am Tag 1 (wie schon besprochen) eine bessere Laufzeit hat, jedoch halt nicht so flexibel ist bei Größenänderungen der gewünschten Kombinationen.

[narpfel]

Tag 1 in Prolog:

Code: Alles auswählen

#!/usr/bin/env -S swipl -g main -t halt

read_input(Filename, Expenses) :-
    open(Filename, read, Input),
    read_string(Input, "", "\n", _, String),
    split_string(String, "\n", "", Lines),
    maplist(number_string, Expenses, Lines).

part1(Expenses, Solution) :-
    select(A, Expenses, Rest),
    select(B, Rest, _),
    2020 is A + B,
    Solution is A * B.

part2(Expenses, Solution) :-
    select(A, Expenses, Rest),
    select(B, Rest, Rest2),
    select(C, Rest2, _),
    2020 is A + B + C,
    Solution is A * B * C.

main :-
    read_input(input, Expenses),
    sort(Expenses, SortedExpenses),
    part1(SortedExpenses, Part1),
    write(Part1), nl,
    part2(SortedExpenses, Part2),
    write(Part2), nl.