Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@sparrow: Du nutzt ernsthaft eine for-Schleife zur Deklaration einer Variable innerhalb einer LC?
Wenn es Dir um Optimierung geht, das Erzeugen eines Tuples und das Initialisieren einere for-Schleife braucht auch Zeit.

Code: Alles auswählen

def split_in_half(pack):
    mid = len(pack) // 2
    return pack[:mid], pack[mid:]

data1 = [split_in_half(pack) for pack in data]
Benutzeravatar
sparrow
User
Beiträge: 4164
Registriert: Freitag 17. April 2009, 10:28

@Sirius3: Nein, das war zur Demonstration, dass das theoretisch geht. Ich schrieb, dass ich an der Stelle die LC in der Form nicht verwenden würde.
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

@Sparrow: Ok, diese Konstruktion ist mir neu. Mal schauen ob ich mir das so angewöhnen kann. Edit: Laut @Sirius wohl besser doch nicht. lol

Hier mein Code für Tag 4. Habe ich auch wieder mit Hilfe von Sets gelöst.

Code: Alles auswählen

raw = [line.replace('-',',').strip() for line in open("input.txt").readlines()]
data = [list(map(int, pair.split(','))) for pair in raw]

def evaluate(condition, a, b, x, y):
    range_a_b = set(range(a, b+1))
    range_x_y = set(range(x, y+1))
    same = range_a_b.intersection(range_x_y)
    return condition(same, range_a_b, range_x_y)

contain = lambda s, ab, xy : s == ab or s == xy
overlap = lambda s, ab, xy : len(s) > 0

print('Part 1:', sum(evaluate(contain, *pair) for pair in data))
print('Part 2:', sum(evaluate(overlap, *pair) for pair in data))
Zuletzt geändert von ThomasL am Sonntag 4. Dezember 2022, 11:16, insgesamt 1-mal geändert.
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: 4164
Registriert: Freitag 17. April 2009, 10:28

@ThomasL: Nein, du solltest das wie Sirius3 lösen und das nicht in eine LC mit lambda-Funktion stecken, sondern aus der lambda-Funktion eine richtige Funktion machen.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

@ThomasL: wenn du eine Lambda-Funktion an einen Bezeichner bindest, dann ist es keine anonyme Funktion mehr. Dann kannst du stattdessen auch direkt eine "normale" Funktion verwenden.

Hier meine Lösung für Tag 4, Teil 1. Im Gegensatz zu @narpfel leserlich und beliebig lang :)

Code: Alles auswählen

fname = "input.txt"
# fname = "test.txt"


def get_section_set(section):
    lower, upper = map(int, section.split('-'))
    return set(range(lower, upper + 1))


def sections_total_overlap(sections):
    s1, s2 = sections.split(",")
    s1 = get_section_set(s1)
    s2 = get_section_set(s2)
    return s1 <= s2 or s2 <= s1


with open(fname) as fobj:
    print(sum(sections_total_overlap(sections) for sections in fobj))
Für Teil 2 bedarf es lediglich einer kleinen Änderung.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Interessant wie vorherige Aufgaben folgende Aufgaben beeinflussen — ich habe das nicht mit Mengen gelöst sondern mit konstantem Speicherverbrauch pro Aufgabe/Aufgabenpaar. Die Tests sind ja einfach nur ein paar Vergleiche von den Start- und Endpunkten. Aber bei moderner Hardware und Aufgaben die maximal 100 Abschnitte (zumindest in meinen Eingabedaten) umfassen können, kann man ja ein bisschen mit Speicher rumsauen. 🤓
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

Die Tage 3 und 4 waren aus meiner Sicht Aufgaben die sich mittels Python sehr gut mit Sets lösen lassen. Überhaupt betrachte ich die Aufgaben, wenn ich sie denn mache, gerne aus der Python-Perspektive: finde eine lesbare pythonische Lösung ohne irgendwelche mikro-Optimierungen. Sozusagen KISS inklusive brute force bis es nicht mehr anders geht.

Wer dagegen gelegentlich gerne auch seinen VC20 anwerfen möchte, hat möglicherweise andere Präferenzen 8)
Benutzeravatar
Dennis89
User
Beiträge: 1124
Registriert: Freitag 11. Dezember 2020, 15:13

Bei Tag 4 bin ich dieses mal zwar selbst auf 'set' gekommen (ist auch nicht schwer, wenn man es mir am Tag davor deutlich gesagt hat), aber ich muss sagen für mich als nicht Programmierer bringen die Aufgaben meinen Kopf schon zum qualmen. Schöner Code entsteht dabei im ersten Schuss auch nicht. Umso mehr bin ich von euren kompakten Lösungen begeistert und versuche so viel wie möglich davon mit zu nehmen 👍
"When I got the music, I got a place to go" [Rancid, 1993]
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

Ich habe Gesamtlösungen mit beiden Ansätzen (mit/ohne sets). Hier mal die ohne sets, der Abwechselung halber ;):

Code: Alles auswählen

#!/usr/bin/env python3
import fileinput
from itertools import tee


def iter_pairs():
    for line in fileinput.input():
        line = line.rstrip()
        if line:
            left, right = line.split(",")
            left, right = [list(map(int, item.split("-"))) for item in (left, right)]
            left, right = sorted((left, right))
            yield left, right


def contains(first, second):
    return first[0] <= second[0] and first[1] >= second[1]


def overlaps(first, second):
    return first[1] > second[0] or first[1] == second[0]


def main():
    part1, part2 = tee(iter_pairs(), 2)
    overlapping = sum(overlaps(left, right) for left, right in part2)
    contained = sum(
        contains(left, right) or contains(right, left) for left, right in part1
    )
    print("Fully contained:", contained)
    print("Overlapping:", overlapping)


if __name__ == "__main__":
    main()
Mir ist es immer wichtig, "komplette" Skripte zu schreiben.
Benutzeravatar
grubenfox
User
Beiträge: 413
Registriert: Freitag 2. Dezember 2022, 15:49

Ich habe mir meinen Python-Stil durch langjährige Nicht-nutzung von Python voll völlig versaut... zu "kompletten" Skripten kann ich mich hier jedenfalls nicht durchringen... Hauptsache die Skripte machen das was sie sollen.
Wobei... die Initialisierung von stapel9000 bzw. stapel9001 mit neun leeren Listen in einer Liste hätte ich gerne sinngemäß so geschrieben: stapel9000 = [ []*9,] Ich meine da gab es früher (bei Python2) mal einen Trick um das hin zu bekommen. Täuscht mich da meine Erinnerung oder habe ich nur die passende Schreibweise vergessen oder geht das unter Python3 nicht mehr?

P.S. Kann ich hier im Forum bei meinen Einstellungen irgendwo einstellen das TABs als nur vier Leerzeichen dargestellt werden sollen?

Code: Alles auswählen

#!/usr/bin/env python3
datei = open(r'2022_puzzle05.txt')

stapel9000 = [[],[],[],[],[],[],[],[],[],]
stapel9001 = [[],[],[],[],[],[],[],[],[],]
for zeile in datei:
	if zeile.find('[') == -1:
		break
	for index in range(9):
		element = zeile[index*4:(index+1)*4]
		# print('stapel', (index+1), element)
		if element.find('[')>-1:
			stapel9000[index].append(element.strip('\n[ ]'))
			stapel9001[index].append(element.strip('\n[ ]'))
print(stapel9000)
print('Aufbau der Stapel fertig! Nun beginnt die Arbeit...')


for zeile in datei:
	zeile = zeile.strip()
	if zeile.find('move')>-1:
		anzahl = int(zeile.split(' from ')[0].split('move ')[1])
		von = int(zeile.split(' from ')[1].split(' to ')[0])-1
		nach =  int(zeile.split(' from ')[1].split(' to ')[1])-1
		# print('Anzahl:', anzahl)
		# print('Von:', von+1)
		# print('nach:', nach+1)
		for schritt in range(anzahl):
			element = stapel9000[von].pop(0)
			stapel9000[nach].insert(0, element)

		element = stapel9001[von][:anzahl]
		stapel9001[von] = stapel9001[von][anzahl:]
		element.extend(stapel9001[nach])
		stapel9001[nach] = element

# print(stapel9000)
print('CrateMover9000: ', end='')
for stack in stapel9000:
	print(stack[0],end='')
print()


# print(stapel9001)
print('CrateMover9001: ', end='')
for stack in stapel9001:
	print(stack[0],end='')
print()
Benutzeravatar
Whitie
User
Beiträge: 216
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Je komplexer die Aufgaben werden, desto uneleganter wird mein Code :D Ich hatte das Gefühl, nach den Set's wollte man uns heute das Modul "collections" näherbringen.

Code: Alles auswählen

from collections import defaultdict, deque, namedtuple
from pathlib import Path


TEST = """\
    [D]    
[N] [C]    
[Z] [M] [P]
 1   2   3 

move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2
"""
Move = namedtuple('Move', 'count from_stack to_stack')


def get_input():
    with Path('input.txt').open() as fp:
        return fp.read().rstrip()


def get_chunks(it, n, same_size=True):
    chunks = []
    for i in range(0, len(it), n):
        chunk = it[i:i+n]
        if len(chunk) != n and same_size:
            break
        chunks.append(chunk)
    return chunks


def parse_stacks(raw):
    stacks = defaultdict(deque)
    for line in list(reversed(raw.splitlines()))[1:]:
        for i, stack in enumerate(get_chunks(line, 4, False), start=1):
            if stack.strip():
                stacks[i].append(stack[1])
    return stacks


def parse_moves(raw):
    moves = []
    for line in raw.splitlines():
        if line.strip():
            parts = line.split()
            moves.append(
                Move(int(parts[1]), int(parts[3]), int(parts[5]))
            )
    return moves


def do_move(move, stacks):
    for _ in range(move.count):
        crate = stacks[move.from_stack].pop()
        stacks[move.to_stack].append(crate)
    return stacks


def do_moves(move, stacks):
    from_stack = list(stacks[move.from_stack])
    crates = from_stack[-move.count:]
    stacks[move.to_stack].extend(crates)
    stacks[move.from_stack] = deque(from_stack[:-move.count])
    return stacks


def main():
    inp = get_input()
    # inp = TEST
    raw_stacks, raw_moves = inp.split('\n\n')
    stacks = parse_stacks(raw_stacks)
    moves = parse_moves(raw_moves)
    for move in moves:
        stacks = do_move(move, stacks)
    print('Part 1')
    print(''.join([stacks[x][-1] for x in sorted(stacks.keys())]))
    print('Part 2')
    stacks = parse_stacks(raw_stacks)
    for move in moves:
        stacks = do_moves(move, stacks)
    print(''.join([stacks[x][-1] for x in sorted(stacks.keys())]))


if __name__ == '__main__':
    main()
Leider musste ich für Teil 2 meinen schönen deque Code wieder aufweichen, da die sich nicht slicen lassen :D

Viele Grüße
Whitie
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@grubenfox: das mit den Tabs ist kein Problem, da man eh immer mit 4 Leerzeichen pro Ebene einrückt und keine Tabs verwendet.
`[[]*9]` erzeugt eine Liste und packt die 9mal in eine Liste. Mit `[[] for _ in range(9)]` werden neune unabhängige Listen erzeugt.
Dateien, die man öffnet, sollte man auch wieder schließen, am besten, indem man das with-Statement benutzt.
Statt `find` solltest Du hier immer den in-Operator verwenden.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

Tag 5, für alle, die es interessiert: hier eine Lösung aus der Kategorie beliebig lang und (hoffentlich) lesbar. Diesmal inklusive Walrösser :)

Code: Alles auswählen

import collections
import re
import string


fname = "input.txt"
# fname = "test.txt"


IS_CRATE_MOVER_9000 = False  # part 1: True / part 2: False
RE_STACK = re.compile(r"[A-Z]")
RE_MOVE = re.compile(r"move (\d+) from (\d+) to (\d+)")


def get_stacks(fobj):
    stacks = collections.defaultdict(list)
    while (line := next(fobj)) and '[' in line:
        for mo in RE_STACK.finditer(line):
            stacks[(mo.start() + 3) // 4].append(mo.group(0))
    for stack in stacks.values():
        stack.reverse()
    return stacks


def move_crates(stacks, fobj, is_crate_mover_9000):
    for line in fobj:
        if mo := RE_MOVE.match(line):
            amount, source, target = map(int, mo.groups())
            crates = stacks[source][-amount:]
            if is_crate_mover_9000:
                crates.reverse()
            stacks[target].extend(crates)
            del stacks[source][-amount:]


def get_top_crates(stacks):
    return ''.join(stacks[key][-1] for key in sorted(stacks.keys()) if stacks[key])


with open(fname) as fobj:
    stacks = get_stacks(fobj)
    move_crates(stacks, fobj, IS_CRATE_MOVER_9000)
    print(get_top_crates(stacks))
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

kbr hat geschrieben: Montag 5. Dezember 2022, 14:52 hier eine Lösung aus der Kategorie beliebig lang und (hoffentlich) lesbar.
Hier meine Lösung aus der Kategorie "beliebig lang und möglicherweise leicht over-engineered": ;)

Code: Alles auswählen

#!/usr/bin/env python3
import re
import fileinput
from itertools import takewhile, tee
from collections import namedtuple
from copy import copy

Move = namedtuple("Move", ["amount", "source", "goal"])

STACK_PATTERN = re.compile(r"(?:\[(\w)\]\s?|\s{3}\s?)")
MOVE_PATTERN = re.compile(
    r"^move (?P<amount>\d+) from (?P<source>\d+) to (?P<goal>\d+)$"
)


def parse_stacks(lines):
    stacks = dict()
    for line in takewhile(lambda x: len(x.strip()), lines):
        line = line.rstrip("\n")
        matches = re.findall(STACK_PATTERN, line)
        for i, match in enumerate(matches, 1):
            if match:
                stacks.setdefault(i, list())
                stacks[i].append(match)
    stacks = {i: stack[::-1] for i, stack in stacks.items()}
    return stacks


def iter_parse_moves(lines):
    for line in lines:
        line = line.strip()
        matched = re.match(MOVE_PATTERN, line)
        if matched:
            items = {key: int(value) for key, value in matched.groupdict().items()}
            yield Move(**items)


def rearrange(stacks, move, invert=False):
    crates = stacks[move.source][-move.amount :]
    if invert:
        crates = crates[::-1]
    stacks[move.goal].extend(crates)
    stacks[move.source] = stacks[move.source][: -move.amount]
    return stacks


def main():
    lines = fileinput.input()
    part1_stacks = parse_stacks(lines)
    part2_stacks = copy(part1_stacks)
    part1_moves, part2_moves = tee(iter_parse_moves(lines), 2)

    for stacks, invert, moves in zip(
        (part1_stacks, part2_stacks), (True, False), (part1_moves, part2_moves)
    ):
        for move in moves:
            stacks = rearrange(stacks, move, invert=invert)
        result = []
        for item in sorted(stacks):
            result.append(stacks[item][-1])
        print("".join(result))


if __name__ == "__main__":
    main()
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@kbr: Also der VIC-20 (oder deutsch VC-20) beeinflusst natürlich wie ich über die Problemlösung nachdenke, aber auch so hätte ich in Python keine Mengen genommen, und das sehe ich in diesem Fall auch nicht als Mikrooptimierung sondern ich gehe da in Python auch mit Lesbarkeit im Hinterkopf dran, also das man das am besten ”vorlesen” kann, wie es dort steht. Und das ganze in relativ vielen kleinen Funktionen/Methoden. Ich sehe da bei Tag 4 eine Funktion die eine Zeile in zwei Assignment-Objekte parst. Und dabei auf eine Klassenmethode zurückgreift, die ein `Assignment` parst, und eine Funktion die viele Zeilen parst und die einfach nur `parse_line()` mit `map()` auf die übergebenen Zeilen anwendet.

Das Assignment könnte den ``in``-Operator überladen um zu schauen ob ein Abschnitt enthalten ist, und zwei Testmethoden die jeweils prüfen ob ein Assignment komplett in einem anderen Assignment enthalten ist, und ob das Assignment sich mit einem anderen Assignment überlappt.

Dann noch pro Aufgabenteil eine Funktion die Assignment-Paare bekommt und jeweils zählt bei wie vielen die Bedingung des Aufgabenteils zutrifft. Beides nicht direkt in der `main()` weil beides testbar sein sollte, also noch zwei Testfälle um das Beispiel aus den Teilaufgaben zu prüfen. Ist für meine Begriffe noch KISS. :-)

Aber hier jetzt erst einmal das was auf dem VIC-20 in 2m52s die beiden Teilergebnisse für Tag 4 ausspuckt:

Code: Alles auswählen

   10 TI$="000000":R1=0:R2=0
   20 OPEN 2,8,2,"INPUT04,S"
   30 IF ST<>0 THEN CLOSE 2:PRINT R1,R2,TI$:END
   40 INPUT#2,A$,B$:GOSUB 500:A=S:B=E
   50 A$=B$:GOSUB 500:C=S:D=E
   60 FA=A>=C AND A<=D
   70 FB=B>=C AND B<=D
   80 FC=C>=A AND C<=B
   90 FD=D>=A AND D<=B
  100 IF FA AND FB OR FC AND FD THEN R1=R1+1
  200 IF FA OR FB OR FC OR FD THEN R2=R2+1
  400 GOTO 30
  500 FOR I=1 TO LEN(A$)-1
  510 IF MID$(A$,I,1)="-" THEN 530
  520 NEXT:STOP:REM NO '-' FOUND
  530 S=VAL(MID$(A$,1,I))
  540 E=VAL(MID$(A$,I+1))
  550 RETURN
Das ist sogar halbwegs verständlich wenn man die Bedeutung der Variablen entziffert hat. Der VIC-20 verhilft hier unfreiwillig zu verständlicherem Code gegenüber dem C64 obwohl es das gleiche BASIC ist. Aber auf dem VIC-20 ist der Ausschnitt den man gleichzeitig vom Programm sehen kann mit 22×23 Zeilen so winzig, dass ich deutlich weniger in die Zeilen packe als auf dem C64. Bei der GW-BASIC-Portierung sieht man das, wie das Programm an Länge verliert und an Breite gewinnt:

Code: Alles auswählen

10 DEFINT A-Z:T1!=TIMER:R1=0:R2=0:DEF FN C(N,S,E)=N>=S AND N<=E
20 OPEN "input04.txt" FOR INPUT AS #1
30 WHILE NOT EOF(1):INPUT#1,A$,B$:GOSUB 500:A=S:B=E:A$=B$:GOSUB 500:C=S:D=E
40 FA=FN C(A,C,D):FB=FN C(B,C,D):FC=FN C(C,A,B):FD=FN C(D,A,B)
50 IF FA AND FB OR FC AND FD THEN R1=R1+1
60 IF FA OR FB OR FC OR FD THEN R2=R2+1
499 WEND:CLOSE 1:PRINT R1,R2:PRINT"In";TIMER-T1!;"seconds.":END
500 I=INSTR(A$,"-"):IF I=0 THEN PRINT"Error: '-' not found in ";A$:END
510 S=VAL(MID$(A$,1,I)):E=VAL(MID$(A$,I+1)):RETURN
In QBasic geht das Programm dann schon in den lesbaren Zustand über und man sieht auch im Ansatz wo die Klasse Sinn machen würde, weil ich dort einen Typ für `Assignment` definiert habe, weil das ja zweimal die gleiche Datenstruktur ist, und das beim Parsen und beim Test ob ein Abschnitt im `Assignment` enthalten ist Argumente zusammenfasst:

Code: Alles auswählen

TYPE Assignment
  startSection AS INTEGER
  endSection AS INTEGER
END TYPE

t1 = TIMER
DIM r1 AS INTEGER, r2 AS INTEGER
DIM a1 AS Assignment, a2 AS Assignment
DIM a, b, c, d AS INTEGER

r1 = 0: r2 = 0
OPEN "input04.txt" FOR INPUT AS #1
DO WHILE NOT EOF(1)
  INPUT #1, a$, b$
  ParseAssignment a$, a1: ParseAssignment b$, a2
  a = Contains(a2, a1.startSection): b = Contains(a2, a1.endSection)
  c = Contains(a1, a2.startSection): d = Contains(a1, a2.endSection)
  IF a AND b OR c AND d THEN r1 = r1 + 1
  IF a OR b OR c OR d THEN r2 = r2 + 1
LOOP
CLOSE 1: PRINT r1, r2: PRINT "In"; TIMER - t1; "seconds."

FUNCTION Contains% (a AS Assignment, section AS INTEGER)
  Contains = section >= a.startSection AND section <= a.endSection
END FUNCTION

SUB ParseAssignment (s AS STRING, a AS Assignment)
  DIM i AS INTEGER
  i = INSTR(s, "-")
  IF i = 0 THEN PRINT "Error: '-' not found in "; s: END
  a.startSection = VAL(MID$(s, 1, i))
  a.endSection = VAL(MID$(s, i + 1))
END SUB
Und damit man das wirklich mal in OOP sieht, habe ich es noch in Pascal implementiert (mein Informatik-Lehrer wäre wahrscheinlich sehr glücklich):

Code: Alles auswählen

type
  TSection = Byte;
  TAssignment = object
      startSection, endSection: TSection;
      procedure InitFromStr(const s: String);
      function Contains(section: TSection): Boolean;
      function IsEnclosedIn(const other: TAssignment): Boolean;
      function Overlaps(const other: TAssignment): Boolean;
    end;

var
  r1, r2: Word;
  f: Text;
  line: String;
  a1, a2: TAssignment;

procedure TAssignment.InitFromStr(const s: String);
var
  i: Byte;
  code: Integer;
begin
  i := Pos('-', s);
  if i = 0 then Halt(1);
  Val(Copy(s, 1, i - 1), startSection, code);
  if code > 0 then Halt(1);
  Val(Copy(s, i + 1, Length(s)), endSection, code);
  if code > 0 then Halt(1);
end;

function TAssignment.Contains(section: TSection): Boolean;
begin
  Contains := (section >= startSection) and (section <= endSection);
end;

function TAssignment.IsEnclosedIn(const other: TAssignment): Boolean;
begin
  IsEnclosedIn := (startSection >= other.startSection)
                  and (endSection <= other.endSection);
end;

function TAssignment.Overlaps(const other: TAssignment): Boolean;
begin
  Overlaps := Self.Contains(other.startSection)
              or Self.Contains(other.endSection)
              or other.Contains(Self.startSection)
              or other.Contains(Self.endSection);
end;

procedure ParseLine(const line: String; var a1, a2: TAssignment);
var
  i: Byte;
begin
  i := Pos(',', line);
  if i = 0 then Halt(1);
  a1.InitFromStr(Copy(line, 1, i - 1));
  a2.InitFromStr(Copy(line, i + 1, Length(line)));
end;

begin
  r1 := 0; r2 := 0;
  Assign(f, 'input04.txt');
  Reset(f);
  while not Eof(f) do begin
    ReadLn(f, line);
    ParseLine(line, a1, a2);
    if a1.IsEnclosedIn(a2) or a2.IsEnclosedIn(a1) then Inc(r1);
    if a1.Overlaps(a2) then Inc(r2);
  end;
  Close(f);
  WriteLn(r1, ' ', r2);
end.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
Dennis89
User
Beiträge: 1124
Registriert: Freitag 11. Dezember 2020, 15:13

Die Aufgabe heute konnte ich auch wieder lösen. Gestern kam ich nicht von alleine drauf.

Code: Alles auswählen

#!/usr/bin/env python3
from pathlib import Path
from more_itertools import windowed, all_unique

CHARACTERS = Path.home() / "Dokumente/characters.txt"


def read_input_file(file):
    return file.read_text(encoding="UTF-8")


def looking_for_start(characters, group):
    potential_start_characters = windowed(characters, group)
    for start_character in potential_start_characters:
        if all_unique(start_character):
            return start_character


def looking_for_index(start_character, characters, group):
    return characters.find("".join(start_character)) + group


def main():
    characters = read_input_file(CHARACTERS)
    first_start_character = looking_for_start(characters, 4)
    print(looking_for_index(first_start_character, characters, 4))
    first_message_character = looking_for_start(characters, 14)
    print(looking_for_index(first_message_character, characters, 14))


if __name__ == "__main__":
    main()
Grüße
Dennis
"When I got the music, I got a place to go" [Rancid, 1993]
Benutzeravatar
Whitie
User
Beiträge: 216
Registriert: Sonntag 4. Juni 2006, 12:39
Wohnort: Schulzendorf

Heute kam mir das etwas komisch vor, dass ich für Teil 2 nur eine Zahl ändern musste. Hat aber funktioniert ;-)

Code: Alles auswählen

from collections import deque
from pathlib import Path


TEST = """\
mjqjpqmgbljsphdztnvjfqwrcgsmlb
"""


def get_input():
    with Path('input.txt').open() as fp:
        return fp.read().rstrip()


def get_marker_position(inp, marker_length):
    stack = deque(maxlen=marker_length)
    for pos, char in enumerate(inp, start=1):
        stack.append(char)
        if len(stack) == marker_length and len(set(stack)) == marker_length:
            return pos
    raise ValueError('No marker found')


def main():
    inp = get_input()
    # inp = TEST
    print('Part 1')
    print(get_marker_position(inp, 4))
    print('Part 2')
    print(get_marker_position(inp, 14))


if __name__ == '__main__':
    main()
Grüße
Whitie
Manul
User
Beiträge: 52
Registriert: Samstag 13. Februar 2021, 16:00

Heute fand ich auch recht schnell zu lösen: Die eigentliche Suche ist bei mir ein Einzeiler, wobei ich sogar unnötigerweise alle Indizes der Marker suche. Einen Reiz von Advent of Code finde ich ja auch immer, zu versuchen, die Eingabedaten für den ersten Teil schon so zu strukturieren, daß man sich für den zweiten Teil alle Möglichkeiten offen lässt, obwohl man die Aufgabenstellung noch gar nicht kennt. Da kann man natürlich auch mal komplett daneben liegen - so bin ich gestern in die gleiche deque-Falle wie @whitie getappt.

Meine Lösung für heute:

Code: Alles auswählen

#!/usr/bin/python3

import fileinput

def find_markers(signal,length):
  return [i for i in range(length,len(signal)) if len(set(signal[i-length:i])) == length]

def main():
  signal = fileinput.input().readline().strip()

  packets = find_markers(signal,4)
  print(packets[0])

  messages = find_markers(signal,14)
  print(messages[0])

if __name__ == "__main__":
  main()
Und, weil schon erwähnt, für gestern:

Code: Alles auswählen

#!/usr/bin/python3

import fileinput
import re
from collections import deque
from more_itertools import chunked

MOVE = re.compile("move (\d+) from (\d+) to (\d+)")

def read_stacks(f):
  stacks = []
  for line in f:
    items = [ item[1] for item in chunked(line, 4) ]
    if items[0] != "1":
      if len(stacks) < len(items):
        stacks.extend([ deque() for _ in range(len(items)-len(stacks)) ])
      for stack,item in zip(stacks,items):
        if item != " ":
          stack.appendleft(item)
    else:
      assert len(stacks) == int(line.split()[-1])
      f.readline()
      return stacks

def read_moves(f):
  return [ tuple(map(int,MOVE.match(line).groups())) for line in f ]

def move_crates(stacks,number,origin,destination):
  for _ in range(number):
    stacks[destination-1].append(stacks[origin-1].pop())

def move_crates_9001(stacks,number,origin,destination):
  stacks[destination-1].extend(stacks[origin-1][-number:])
  del stacks[origin-1][-number:]

def part1(stacks,moves):
  stacks = [stack.copy() for stack in stacks]
  for number,origin,destination in moves:
    move_crates(stacks,number,origin,destination)
  return "".join(stack[-1] for stack in stacks)

def part2(stacks,moves):
  stacks = [list(stack) for stack in stacks]
  for number,origin,destination in moves:
    move_crates_9001(stacks,number,origin,destination)
  return "".join(stack[-1] for stack in stacks)

def main():
  with fileinput.input() as f:
    stacks = read_stacks(f)
    moves = read_moves(f)
  print(part1(stacks, moves))
  print(part2(stacks, moves))

if __name__ == "__main__":
  main()
Benutzeravatar
grubenfox
User
Beiträge: 413
Registriert: Freitag 2. Dezember 2022, 15:49

Heute habe ich es mal hübscher gemacht:

Code: Alles auswählen

#!/usr/bin/env python3

LAENGE_SOP = 4 # Start Of Packet
LAENGE_SOM = 14 # Start Of Message

def suche_signal(nachricht, signallenge):
    for index in range(len(nachricht)):
        signal = nachricht[index:index+signallenge]
        if len(set(signal)) == signallenge:
            return(index + signallenge)

testnachricht01 = 'mjqjpqmgbljsphdztnvjfqwrcgsmlb' # 7 

if __name__ == '__main__':
    nachricht = open('2022_puzzle06.txt').read()

    print(suche_signal(testnachricht01, LAENGE_SOP))
    print('##########################')
    print(suche_signal(nachricht, LAENGE_SOP))
    print(suche_signal(nachricht, LAENGE_SOM))
Wobei ich hier dann auch mal mit dem golfen angefangen habe.... eine Zeile für die erste Teilaufgaben (82 Zeichen) und beim zweiten Teil dann 85 Zeichen

Code: Alles auswählen

n=open('i').read();print([i for i in range(4,len(n)) if len(set(n[i-4:i]))==4][0])
n=open('i').read();print([i for i in range(14,len(n)) if len(set(n[i-14:i]))==14][0])
Manul
User
Beiträge: 52
Registriert: Samstag 13. Februar 2021, 16:00

Spielt noch jemand? Heute fand ich recht knifflig - und habe keine Lösung gefunden, die für Teil 1 und Teil 2 gleichermaßen funktioniert.
Antworten