Advent of Code

[Dennis89]

Guten Morgen und danke für euren Input.

Das mit `count` ist interessant, habe ich allerdings noch nicht in Code versucht umzusetzen.

@__blackjack__ Das Suchen nach den X-Koordinaten ist nicht das Problem. Aber das Suchen in alle Richtungen. Um das zu verdeutlichen, hier mal mein Ansatz bzw. der Punkt an dem ich aufgehört habe, weil ich das Rätsel mit so nicht lösen will, weil das Mist ist.

Code: Alles auswählen

import re
from collections import defaultdict


EXAMPLE_LINES = """\
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX""".splitlines()

DELTA = [x for x in range(-4, 5) if x != 0]


def parse_input(lines):
    line_to_x = defaultdict(list)
    for line_number, line in enumerate(lines):
        for match in re.finditer("X", line):
            line_to_x[line_number].append(int(match.start()))
    return line_to_x

def count_xmas(x_coordinates, lines):
    max_row_length = len(lines[0])
    words_inline = []
    words_vertical = []
    words_diagonal = []
    for row, columns in x_coordinates.items():
        for column in columns:
            for delta in DELTA:
                if column >= 3:
                    words_inline.append(lines[row][column + delta])
                elif delta > 0:
                    words_inline.append(lines[row][column + delta])
                if row >= 3:
                    words_vertical.append(lines[row + delta][column])
                elif delta > 0:
                    words_vertical.append(lines[row + delta][column])
                if column > 3 and row > 3 and column + 4 <= max_row_length:
                    words_diagonal.append(lines[row + delta][column + delta])
                # Und so weiter für die anderen Randfälle und oben sind
                # auch nicht alle abgedeckt.
                # Da wird man doch verrückt.



def main():
    puzzle_input = EXAMPLE_LINES
    x_coordinates = parse_input(puzzle_input)
    print(count_xmas(x_coordinates, puzzle_input))


if __name__ == '__main__':
    main()

Hatte noch überlegt, das ich `slicing` anstatt das delta aufzusummieren, aber das haut bei den Diagonalen nicht hin und auch sonst wirds nicht übersichtlicher.

Grüße
Dennis

[nezzcarth]

Code: Alles auswählen

Aber das Suchen in alle Richtungen. 

Wenn man sich das 2D-Grid denkt, lassen sich die Richtungen durch 8 Offsets für die xy-Koordination beschreiben, die man ausschreiben oder auch automatisch generieren lassen kann. Und dann kann man soweit in jede Richtung suchen, wie es das Suchwort eben erfordert.

[Dennis89]

Danke für deine Antwort.

Das habe ich mit `DELTA` gemacht, die Werte darin auf `row`, `column` oder auf beide addiert, ergeben die neuen Koordinaten für alle Richtungen. Nur sieht das, so wie ich das mache, nicht sonderlich elegant aus.

Grüße
Dennis

[__blackjack__]

@Dennis89: Dein Delta beschreibt aber nicht einfach nur die Richtung, unabhängig von der Länge des Wortes.

Bei mir sehen die Deltawerte so aus:

Code: Alles auswählen

In [355]: DIRECTIONS
Out[355]: [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

Für jede der 8 Richtungen was man auf x und y addieren muss um *einen* Schritt in diese Richtung zu gehen. Dann eine Schleife über die Buchstaben und am Ende der Schleife addiert man die beiden Werte auf x und y um im nächsten Schleifendurchlauf für den nächsten Buchstaben an der passenden Stelle zu prüfen.

[Dennis89]

Danke für deine Antwort.

Ich wollte mit meinem Delta beschreiben wo ich hin will. Im besten Fall 4 Schritte.

Dann eine Schleife über die Buchstaben und am Ende der Schleife addiert man die beiden Werte auf x und y um im nächsten Schleifendurchlauf für den nächsten Buchstaben an der passenden Stelle zu prüfen.

Entweder man kann mich bald einliefern oder ich weiß auch nicht was los ist. Ich lese den Abschnitt seit 13Uhr immer wieder und ich blicke es beim besten Willen nicht.

Eine Schleife über welche Buchstaben? Die gefundenen "X"'s? Wenn ja, dann ein Schritt in jede Richtung und dann geht die Schleife über die Buchstaben weiter, obwohl ich noch gar nicht alle Schritte, um ein mögliches Wort zu finden, gemacht habe?

Ich stelle mir vor ich gehe von einem "X" einen Schritt nach rechts und da ist ein "M", was mache ich dann jetzt damit, wenn mein nächster Schritt nicht ist, das ich schaue was rechts neben dem "M" steht?
Ich muss dann irgendwie das "M" mit Koordinaten zugehörig zum "X" abspeichern und dann irgendwie wieder von "M" die DELTA's durchgehen, wobei ich da ja nur ein Schritt in die RIchtung gehen will, in der ich das "M" gefunden habe.

Der Ansatz mit deinen DELTA's ist bei mir so und haut natürlich nicht hin, weil ich entweder `*_step` erhöhen müsste, bis ich durch 4 Buchstaben durch bin oder es eben so machen, wie du es beschreibst und ich aber nicht verstehe.

Code: Alles auswählen

def looking_for_symbol(lines, lines_to_x):
    for row, column in lines_to_x.items():
        for row_step, column_step in DELTA:
            try:
                letter = lines[row + row_step][column + column_step]
            except IndexError:
                pass
    return

Komme mir gerade schon bisschen doof vor und bin in meiner Denkweise gefangen.

Grüße
Dennis

[__blackjack__]

@Dennis89: Eine Schleife über die Buchstaben des Wortes. So ganz grob:

Code: Alles auswählen

x, y = x_position
for character in "XMAS":
    if data[y][x] != character:
        return False

    x += delta_x
    y += delta_y

return True

Da fehlt noch die Prüfung ob `x` und `y` noch innerhalb der Daten sind. Und das macht man dann in einer Schleife über die 8 Delta-Paare für die jeweiligen Richtungen.

[nezzcarth]

Das habe ich mit `DELTA` gemacht, die Werte darin auf `row`, `column` oder auf beide addiert, ergeben die neuen Koordinaten für alle Richtungen.

Meiner Meinung nach machst du etwas anderes. Und du benutzt ja auch irgendwie den mehrzeiligen String als Grid und suchst mit RegEx direkt die Koordinaten aus, was einerseits ausgeklügelt ist, meiner Meinung nach aber auch fehleranfällig. Dadurch, dass gutes Python so elegant aussehen kann, entsteht finde ich manchmal ein gewisser Druck. Aber es kann durchaus sinnvoll sein, sich auf die "imperativen Grundlagen", die auch in traditionellen Programmiersprachen schon gegangen wären, zu besinnen.

Bei mir ist das Grid eine 2D-Datenstruktur (verschachtelte Liste oder Dict mit x,y-Koordinaten-Tupel als Key), in das der gesamte Input geladen wird. Das geht man von oben nach unten und rechts nach links Buchstabe für Buchstabe durch. Findet man ein "X", startet man ausgehend von der aktuellen Position eine Suche. Und da kommen dann die Offsets in's Spiel, die __blackjack__ beschrieben hat: Addiert man sie zu x,y, kann man so schrittweise und systematisch in eine Richtung gehen. Entspricht der Buchstabe an der aktuellen Position des Suchcursors dem gesuchten Buchstaben, geht man weiter zum nächsten Buchstaben, indem man das Offset wieder addiert, erreicht man das Ende, hat man das Wort gefunden: True. Entspricht der Buchstabe nicht dem gesuchten, bricht man ab (False). In beiden Fällen geht es danach mit der nächsten Richtung weiter. Sind alle Richtungen abgeklappert, geht man zurück zum X und sucht von da aus nach dem nächsten X. Das wäre m.M.n. so ein "klassischer imperativer" Algorithmus, wie er auch schon in den 80ern mit z.B. Basic oder Pascal möglich gewesen wäre. Danach kann man dann immer noch gucken, wie man das mit itertools etc. aufhübschen kann.

[Dennis89]

Danke für eure Erklärungen, habe es mittlerweile kapiert. Puuh..

@nezzcarth Genau das ist mein Anspruch, vorallem bei Rätsel, bei denen es um nichts geht. Ich möchte lernen und viel routinierter eleganten Code zu schreiben. Der Druck übt vielleicht Python etwas aus, weil es möglich ist, aber viel mehr ist es bei mir dieses Forum

Das ist aber positiv gemeint. Mich fasziniert es einfach immer wieder, was, mit welchen Gedankengänge und mit welchen Sprachmittel ihr Lösungen in Code umsetzt. Mir ist zwar bewusst, das ich als Hobbytippse da nicht hin komme, aber ich kann mich in kleinen Stücken wenigstens etwas nähern.

Naja den ersten Teil habe ich, als ich Teil zwei gelesen habe, dachte ich mir, das ist ja easy. Muss nur meine Funktionen etwas allgemeingültiger schreiben. Gesagt, getan und gemerkt, das ich das Muster suchen soll und nicht nur "MAS" diagonal geschrieben. An dem Stand bin ich jetzt. Hier mal der Code, damit ihr seht was aus euren Erklärungen geworden ist.
Den zweiten Teil einfach ignorieren.

Code: Alles auswählen

#!/usr/bin/env python
import re
from collections import defaultdict
from pathlib import Path

INPUT_FILE = Path(__file__).parent / "input04.txt"

PUZZLE_INPUT = """\
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX""".splitlines()

DELTA_1 = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
DELTA_2 = [(-1, 1), (1, 1), (-1, 1), (-1, -1)]
SEARCH_WORD_1 = "XMAS"
SEARCH_WORD_2 = "MAS"


def parse_input(lines, letter):
    lines_to_letter = defaultdict(list)
    for line_number, line in enumerate(lines):
        for match in re.finditer(letter, line):
            lines_to_letter[line_number].append(int(match.start()))
    return lines_to_letter


def is_word_around(lines, x_position, delta_x, delta_y, search_word):
    row, column = x_position
    for letter in search_word:
        try:
            if lines[row][column] != letter:
                return False
            row += delta_x
            column += delta_y
            if (row < 0 or column < 0) and letter != search_word[-1]:
                return False
        except IndexError:
            return False
    return True


def count_words(lines, lines_to_letter, search_word, delta):
    words_counter = []
    for row, columns in lines_to_letter.items():
        for column in columns:
            words_counter.extend(
                is_word_around(lines, (row, column), delta_x, delta_y, search_word)
                for delta_x, delta_y in delta
            )
    return sum(words_counter)


def main():
    puzzle_input = PUZZLE_INPUT
    # puzzle_input = INPUT_FILE.read_text(encoding="UTF-8").splitlines()
    lines_to_x = parse_input(puzzle_input, "X")
    print(count_words(puzzle_input, lines_to_x, SEARCH_WORD_1, DELTA_1))
    lines_to_a = parse_input(puzzle_input, "M")
    print(count_words(puzzle_input, lines_to_a, SEARCH_WORD_2, DELTA_2))


if __name__ == "__main__":
    main()

Grüße
Dennis

P.S. im Gegensatz zu der Aussage, einer Seite weiter vorne, finde ich nicht dass der zweite Teil leichter ist.

[narpfel]

@Dennis89: Vielleicht noch als Inspiration ein Teil meiner Lösung. Ich habe mal das drinnen gelassen, was ich hier geschrieben habe.

Code: Alles auswählen

def count_xmas(lines):
    return sum(
        line.count("XMAS") + line.count("SAMX")
        for line in ...
    )


def part_1(lines):
    return count_xmas(lines) + sum(map(count_xmas, rotate_45_degrees(lines)))


def count_x_mas(lines):
    ...
    
    return sum(
        lines[y].startswith(("MAS", "SAM"), x - 1)
        and ...[x].startswith(("MAS", "SAM"), y - 1)
        for y, x in ...
    )


def part_2(lines):
    return sum(map(count_x_mas, rotate_45_degrees(lines)))

[__blackjack__]

@Dennis89: `is_word_around()` geht ein bisschen einfacher weil man sich das zweite ``if`` und damit insbesondere den ``and``-Teil sparen kann, wenn man die erste Teilbedingung in das erste ``if`` einbaut:

Code: Alles auswählen

def is_word_around(lines, start_position, delta_x, delta_y, search_word):
    row, column = start_position
    for letter in search_word:
        try:
            if row < 0 or column < 0 or lines[row][column] != letter:
                return False

            row += delta_x
            column += delta_y
        except IndexError:
            return False
    return True

[Dennis89]

Guten Morgen,

danke für eure Antworten.

@narpfel Das mit `count` ist fast wesentlich einfacher. Aber das drehen der Matrix um 45° Wie haut dass denn hin? In meinem Kopf habe ich dann unterschiedlich lange Reihen. Wenn ich bei lines[0][0] starte, den Wert in meine neue Matrix schreibe und dann gehe ich weiter und nehme lines[1][1] und setze ich neben den vorherigen Wert und so weiter für jeden Buchstaben, dann werden meine neuen Reihen immer kürzer.

@__blackjack__ Ach man ja, das hätte ich auch sehen können.

Ich will das Thema hier eigentlich nicht mit meinen Problemen zumüllen, falls das jemand stört, gebt bitte Bescheid, dann eröffne ich ein neues.

Grüße
Dennis

[Dennis89]

Nicht sonderlich schön, aber Part 1 von Tag 6 habe ich wenigstens geschafft:

Code: Alles auswählen

#!/usr/bin/env python
from pathlib import Path

INPUT_FILE = Path(__file__).parent / "input06.txt"

PUZZLE_INPUT = """\
....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...""".splitlines()

DIRECTIONS = [
    (-1, 0),
    (0, 1),
    (1, 0),
    (0, -1),
]

def get_start_position(guard_map):
    for row, places in enumerate(guard_map):
        column = places.find("^")
        if column != -1:
            return row, column


def count_visited_places(start_position, guard_map):
    visit_places = 1
    y, x = start_position
    already_visited = [(y, x)]
    while True:
        for (delta_y, delta_x) in DIRECTIONS:
            while True:
                y += delta_y
                x += delta_x
                try:
                    if y < 0 or x < 0:
                        return visit_places
                    if guard_map[y][x] == "#":
                        y -= delta_y
                        x -= delta_x
                        break
                    if (y, x) not in already_visited:
                        visit_places += 1
                        already_visited.append((y, x))
                except IndexError:
                    return visit_places


def main():
    guard_map = PUZZLE_INPUT
    #guard_map = INPUT_FILE.read_text(encoding="UTF-8").splitlines()
    print(count_visited_places(get_start_position(guard_map), guard_map))

    
if __name__ == '__main__':
    main()

Grüße
Dennis

[nezzcarth]

Die gestrige Aufgabe war auch wieder schön mit komplexen Zahlen lösbar, aber natürlich auch ohne gut.

[__blackjack__]

@Dennis89: Das wäre ein bisschen effizienter wenn `already_visited` ein `set()` ist. Und `visit_places` wird immer genau dann um 1 erhöht wenn ein neues Element in `already_visited` eingefügt wird — als eigentlich zählst Du da noch mal parallel die Länge davon mit, die man da auch abfragen könnte. Und mit `itertools.cycle()` könnte man sich die äusserste ``while True``-Schleife sparen.

Ungetestet:

Code: Alles auswählen

def count_visited_places(start_position, guard_map):
    y, x = start_position
    already_visited = {start_position}
    for delta_y, delta_x in cycle(DIRECTIONS):
        while True:
            y += delta_y
            x += delta_x
            try:
                if y < 0 or x < 0:
                    return len(already_visited)
                if guard_map[y][x] == "#":
                    y -= delta_y
                    x -= delta_x
                    break
                already_visited.add((y, x))
            except IndexError:
                return len(already_visited)

Bei mir sah das ähnlich aus nach Teil 1. Für Teil 2 habe ich das ein bisschen erweitert. Da wird nicht mehr die Anzahl zurück gegeben, sondern die besuchten Positionen, und die Info ob es einen Kreis gibt oder nicht. Und ich habe da ein paar eigene Datentypen für die Position, die Karte, den Guard. Und Aufzählungstypen für die Kartenfelder und die Richtung. Ich markiere auch die Besuche auf der Karte, so dass man die in eine Zeichenkette für Doctests ausgeben kann:

Code: Alles auswählen

def move_guard(map_, guard):
    r"""
    >>> guard, lab_map = Map.parse(EXAMPLE_LINES)
    >>> visited_positions, is_cycle = move_guard(lab_map, guard)
    >>> len(visited_positions)
    41
    >>> is_cycle
    False
    >>> print(f":\n{lab_map:X}")
    :
    ....#.....
    ....XXXXX#
    ....X...X.
    ..#.X...X.
    ..XXXXX#X.
    ..X.X.X.X.
    .#XXXXXXX.
    .XXXXXXX#.
    #XXXXXXX..
    ......#X..
    >>> guard, lab_map = Map.parse(EXAMPLE_LINES)
    >>> lab_map[guard.position + Direction.WEST.value] = CellType.EXTRA_OBSTACLE
    >>> _, is_cycle = move_guard(lab_map, guard)
    >>> is_cycle
    True
    >>> print(f":\n{lab_map}")
    :
    ....#.....
    ....+---+#
    ....|...|.
    ..#.|...|.
    ....|..#|.
    ....|...|.
    .#.O+---+.
    ........#.
    #.........
    ......#...
    """
    ...

@nezzcarth: Ich bastel mir dafür immer eine eigene Klasse. Nicht selten kommt da ja noch eine Methode wie ``def distance_to(self, other):`` mit der Manhatten-Distanz oder etwas in der Richtung dazu.

Code: Alles auswählen

@frozen
class Point:
    x = field()
    y = field()

    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

[nezzcarth]

@__blackjack__: Ich wechsel da immer etwas, abhängig von den Anforderungen der Aufgabe. Die Variante mit den komplexen Zahlen wähle ich häufig dann, wenn Drehungen um 90° gefordert sind. Vorwärtungsbewegung und Drehung ließen sich so gestern durch einfache Rechenoperationen umsetzen ohne dass man irgendwas zusätzlich machen muss. Das finde ich schon schick – und doppelt, weil Python das nativ beherrscht

[Dennis89]

@__blackjack__ Danke für die Verbesserung. Ich habe zusätzlich noch den `try/except` Block verkleinert:

Code: Alles auswählen

            try:
                if guard_map[y][x] == "#":
                    y -= delta_y
                    x -= delta_x
                    break
            except IndexError:
                return len(already_visited)

Mehr gehört da ja eigentlich nicht rein.

Den Teil mit "eigenen Datentypen" die du da gemacht hast, habe ich einfach mal überlesen
Den Code würde ich aber schon gerne sehen.

Wie man so etwas mit komplexen Zahlen lösen kann ist mir bis jetzt auch noch so absolut gar nicht klar.

Grüße
Dennis

[nezzcarth]

Wie man so etwas mit komplexen Zahlen lösen kann ist mir bis jetzt auch noch so absolut gar nicht klar.

Hier mal eine gekürzte Lösung nur für Part 1:

Code: Alles auswählen

#!/usr/bin/env python3
import fileinput

GUARD = "^"
OBSTRUCTION = "#"


def get_data():
    grid = {}
    startpos = None
    for line in fileinput.input():
        line = line.strip()
        for x, char in enumerate(line):
            y = fileinput.lineno() - 1
            grid[complex(x, y)] = char
            if char == GUARD:
                startpos = complex(x, y)
    return grid, startpos


def get_guard_positions(grid, guard):
    seen = set()
    direction = -1j
    while True:
        seen.add(guard)
        new_position = guard + direction
        if new_position not in grid:
            return seen
        if grid[new_position] == OBSTRUCTION:
            direction *= 1j
        else:
            guard = new_position


def main():
    grid, guard = get_data()
    positions = get_guard_positions(grid, guard)
    print("Part 1:", len(positions))


if __name__ == "__main__":
    main()

Wie gesagt: Muss man so nicht machen (sollte man vielleicht auch nicht); aber ich mag es.

[Dennis89]

Danke für das Beispiel, da muss man auch erst mal drauf kommen

[narpfel]

Heute war mal wieder ein Problem, bei dem man was parsen musste. Und ein paar Rechnungen waren auch dabei. Ergo: Prolog eignet sich super.

Code: Alles auswählen

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

:- use_module(library(clpfd)).
:- use_module(library(dcg/basics)).
:- use_module(library(pure_input)).

machine(machine(Ax, Ay, Bx, By, Px, Py)) -->
    "Button A: X+", integer(Ax), ", Y+", integer(Ay), eol,
    "Button B: X+", integer(Bx), ", Y+", integer(By), eol,
    "Prize: X=", integer(Px), ", Y=", integer(Py), eol.

machines([Machine | Machines]) --> machine(Machine), eol, machines(Machines).
machines([]) --> eos.

cost(Offset, machine(Ax, Ay, Bx, By, Px, Py), Cost) :-
    [N, M] ins 0..sup,
    N * Ax + M * Bx #= Offset + Px,
    N * Ay + M * By #= Offset + Py,
    Cost #= 3 * N + M,
    labeling([min(Cost)], [Cost]).
cost(_, _, 0).

solve(Offset, Machines, Cost) :-
    maplist(cost(Offset), Machines, Costs),
    sum_list(Costs, Cost).

main :-
    phrase_from_file(machines(Machines), input),
    solve(0, Machines, Part1),
    write(Part1), nl,
    solve(10000000000000, Machines, Part2),
    write(Part2), nl.