Advent of Code Day 6

[nezzcarth]

Hallo

BlackJack hatte ja auf die Advent of Code Aufgabensammlung hingewiesen.
Meine Lösung kommt mir (abgesehen davon, dass sie etwas aufwändiger ist, als notwendig wäre, um das Ergebnis zu berechnen), an ein paar Stellen etwas seltsam vor. Beispielsweise habe ich bisher noch nie das "for … else" Konstrukt verwendet; hier erschien es mir sinnvoll, aber ist es das wirklich? Für das grid habe ich ein set gewählt, aus dem Items gelöscht oder in es hinzugefügt werden (für Teil 2 dann ein defaultdict). Da bin ich mir auch etwas unsicher, ob das nicht zu sehr "zurecht gefummelt" ist. Über Kommentare oder Vorschläge würde ich mich freuen:

(Python 3)

Code: Alles auswählen

from collections import namedtuple
import fileinput
import re


Corner = namedtuple('Corner', 'x y')


def turn_on(grid, first_corner, second_corner):
    for i in range(first_corner.x, second_corner.x + 1):
        for j in range(first_corner.y, second_corner.y + 1):
            grid.add((i, j))
    return grid


def turn_off(grid, first_corner, second_corner):
    for i in range(first_corner.x, second_corner.x + 1):
        for j in range(first_corner.y, second_corner.y + 1):
            try:
                grid.remove((i, j))
            except:
                pass
    return grid


def toggle(grid, first_corner, second_corner):
    for i in range(first_corner.x, second_corner.x + 1):
        for j in range(first_corner.y, second_corner.y + 1):
            try:
                grid.remove((i, j))
            except KeyError:
                grid.add((i, j))
    return grid


ACTIONS = {
    re.compile(r'\s*toggle'):toggle,
    re.compile(r'\s*turn\s+on'): turn_on,
    re.compile(r'\s*turn\s+off'): turn_off,
}


VALUES = re.compile(r'\s*(?P<x1>[0-9]+)\s*,\s*(?P<y1>[0-9]+)\s*through\s*(?P<x2>[0-9]+)\s*,(?P<y2>\s*[0-9]+)$')


def main():
    grid = set()
    for line in fileinput.input():
        line = line.strip()
        for predicate, action in ACTIONS.items():
            if re.match(predicate, line):
                break
        else:
            print('Error:', line)
        values = re.search(VALUES, line)
        try:
            first_corner = Corner(*map(int, values.group('x1', 'y1')))
            second_corner = Corner(*map(int, values.group('x2', 'y2')))
        except AttributeError:
            pass
        grid = action(grid, first_corner, second_corner)
    print('Total:', len(grid))


if __name__ == '__main__':
    main()

Edit:
Die Aufgabenstellung ist, eine zeilenbasierte Steuerungsdatei einzulesen und anhand der Informationen Lichter in einem 1000x1000 Raster an oder auszuschalten. Das Schema ist: (toggle|turn on|turn off) x1,y1 through x2,y2 Die Koordinaten geben zwei Eckten eines Rechtecks an.

[BlackJack]

@nezzcarth: `Corner` ist IMHO etwas kurz gedacht, denn eigentlich hat man die Dinger ja *immer* paarweise für ein Rechteck — das habe ich als Datenstruktur für die Koordinaten implementiert.

Eine Million Listenelemente (+ 1000 Listen für die Zeilen) sprengen ja nicht gerade den Speicher. Und wenn man das nicht mit Listen sondern mit Numpy-Arrays macht, dann spart man sich Python-Schleifen — Operationen auf rechteckigen Teilbereichen eines 2D-Arrays sind damit supereinfach zu programmieren. Hier meine Lösung für beide Aufgabenteile:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from __future__ import absolute_import, division, print_function
from collections import namedtuple
from functools import partial
import numpy as np


class Rectangle(namedtuple('_Rectangle', 'x_1 y_1 x_2 y_2')):

    def as_slices(self):
        return (slice(self.y_1, self.y_2 + 1), slice(self.x_1, self.x_2 + 1))


class AbstractGrid(object):

    DTYPE = None

    def __init__(self, size):
        self.lights = np.zeros((size, size), dtype=self.DTYPE)

    def get_brightness(self):
        return self.lights.sum()


class BinaryGrid(AbstractGrid):

    DTYPE = bool

    def switch(self, state, rectangle):
        self.lights[rectangle.as_slices()] = state

    def toggle(self, rectangle):
        slices = rectangle.as_slices()
        self.lights[slices] = ~self.lights[slices]


class DimmerGrid(AbstractGrid):

    DTYPE = int

    def change(self, value, rectangle):
        slices = rectangle.as_slices()
        self.lights[slices] = (self.lights[slices] + value).clip(0)


def parse_coordinate(string):
    return tuple(map(int, string.split(',')))


def parse_instructions(lines):
    for line in lines:
        parts = line.split()
        yield (
            'turn_' + parts[1] if parts[0] == 'turn' else parts[0],
            Rectangle(
                *(parse_coordinate(parts[-3]) + parse_coordinate(parts[-1]))
            ),
        )


def main():
    puzzles = [
        (
            BinaryGrid,
            {
                'turn_on': ('switch', True),
                'turn_off': ('switch', False),
                'toggle': ('toggle',),
            }
        ),
        (
            DimmerGrid,
            {
                'turn_on': ('change', 1),
                'turn_off': ('change', -1),
                'toggle': ('change', 2),
            }
        ),
    ]

    with open('input.txt') as lines:
        instructions = list(parse_instructions(lines))

    for grid_type, command_mapping in puzzles:
        grid = grid_type(1000)
        command2func = dict(
            (command, partial(getattr(grid, v[0]), *v[1:]))
            for command, v in command_mapping.iteritems()
        )
        for command, rectangle in instructions:
            command2func[command](rectangle)

        print(grid.get_brightness())


if __name__ == '__main__':
    main()

[nezzcarth]

@BlackJack: Danke für die Alternativlösung (und natürlich die Sache mit den Ecken, da hätte ich auch selbst merken können ); da sind wieder so einige Dinge bei, auf die ich niemals gekommen wäre... Interessant fand ich, dass du auf Regular-Expressions verzichtet hast. Ich war hier unsicher, ob das hier angemessen ist, oder einfache Stringoperationen genügen. Beide Teilaufgaben gleichzeitig zu berücksichtigen, ist natürlich optimal. Allerdings sieht die Lösung -- finde ich -- dafür auch etwas komplexer aus.

Mit numpy, das gewissermaßen zu den erweiterten Standardbibliotheken gehört, habe ich mich ehrlich gesagt noch nie so richtig beschäftigt, weil es bisher immer auch irgendwie ohne ging.

[kbr]

Hier mein Ansatz, der etwas anders aussah:

Code: Alles auswählen

import re

re_area = re.compile(r'(\d+)')
dimension = 1000


class Light:

    def __init__(self):
        self.is_on = False

    def turn_on(self):
        self.is_on = True

    def turn_off(self):
        self.is_on = False

    def toggle(self):
        self.is_on = not self.is_on


def count_lights(array):
    return sum(light.is_on for light in (row for row in array))


def handle_command(array, command, x1, y1, x2, y2):
    for y in range(y1, y2+1):
        for x in range(x1, x2+1):
            getattr(array[y][x], command)()


def switch_lights(array, info):
    area = list(map(int, re_area.findall(info)))
    if info.startswith('turn on'):
        command = 'turn_on'
    elif info.startswith('turn off'):
        command = 'turn_off'
    else:
        command = 'toggle'
    handle_command(array, command, *area)


def main(data):
    array = [[Light() for x in range(dimension)] for y in range(dimension)]
    for info in data:
        switch_lights(array, info)
    print('Lights on:', count_lights(array))


if __name__ == '__main__':
    with open('day06.inp') as f:
        data = f.readlines()
    main(data)

Für Teil 2 braucht nur die Light-Klasse und die Auswertung angepasst zu werden. Eine Million Light-Objekte werden sicher langsamer laufen als eine numpy-basierte Lösung - aber ich mag Objekte

[nezzcarth]

aber ich mag Objekte

@kbr: Ich ja nicht so Aber ich finde deine Lösung ist gut lesbar. Die Lösung mit "starts_with" hab' ich nicht gewählt mir das nicht robust genug erscheint (auch wenn es für die Daten zugegebenermaßen egal ist).

So am Rande: Gibt es einen bestimmten Grund dafür, dass die Datei nicht in main sondern im vorherigen if-Block ausgelesen wird?

[kbr]

Gibt es einen bestimmten Grund dafür, dass die Datei nicht in main sondern im vorherigen if-Block ausgelesen wird?

Wenn main Daten erhält sollte es egal sein, aus welcher Quelle diese kommen, solange sie das korrekte Format haben. Erst dann ergibt das if __name__ == '__main__' Konstrukt einen Sinn. Für diese Aufgabe ist das natürlich völlig irrelevant, ich habe es aber dennoch so gehalten.

[BlackJack]

@kbr: Das ist jetzt irgendwie kein Grund auf Modulebene eine Variable zu haben. Das ist ja der Grund für `main()` → Keine Variablen und kein Code auf Modulebene der da nicht hingehört.

[kbr]

@kbr: Das ist jetzt irgendwie kein Grund auf Modulebene eine Variable zu haben. Das ist ja der Grund für `main()` → Keine Variablen und kein Code auf Modulebene der da nicht hingehört.

@BlackJack: Da sehe ich jetzt irgendwie kein Problem. Tatsächlich ist der "if __name__ == '__main__'" Abschnitt auch geeignet um Modultests zu enthalten (wenn pytest oder Unittest nicht zur Anwendung kommen). Das mag nicht jedermanns Stil sein (und wäre bei umfangreichen Projekten auch nicht der meine), aber in dem Sinne kannst Du den dortigen Code als Test verstehen, der zufällig die Aufgabe löst. Vielleicht stört Dich ja, dass die aufgerufene Funktion "main" heißt - bei größeren Projekten eben der Einstiegspunkt, dem kein anderer Code vorangestellt sein sollte.

[BlackJack]

@kbr: Mich stört das `data` was eine modulglobale *Variable* ist und dementsprechend zu Problemen führen kann. Mindestens zu Verwirrungen beim lesen und/oder Warnungen von statischer Codeanalyse wenn irgendwo der generische Name innerhalb einer Funktion und Methode noch mal verwendet wird und damit den Namen auf Modulebene ”verdeckt”. Je mehr Namen man da definiert um so grösser die Wahrscheinlichkeit das man mit lokalen Namen durcheinander kommt oder irgendwann auch mal nach eine Codeänderung auf die globalen Daten zugreift ohne das gleich zu realisieren.

Wenn man Testcode schreibt, kann man den auch in eine Funktion stecken. Hätte zusätzlich den Vorteil das der dann bei entsprechender Namenswahl auch automatisch von Werkzeugen wie `nose` oder `py.test` gefunden werden kann.

[kbr]

@BlackJack: Sicherlich lässt sich Testcode in Funktionen (z.B. innerhalb des if-Blocks) unterbringen, auf diese Weise kann auch 'data' eingelesen werden ohne global definiert zu sein. Diese Mühe hatte ich mir für die kleine Anwendung gespart.

Einen Vorteil bezüglich pytest sehe ich nicht, setzt pytest neben geeigneten Funktionsnamen standardmäßig auch geeignete Datei- und Verzeichnisnamen voraus; für ein späteres Refactoring mag hingegen eine entsprechende Namenswahl von Nutzen sein.

[BlackJack]

Ui, das ist ja fast wie Weihnachten: Gerade eben den Monitor angeschaltet an dem der C64 hängt und geschaut ob der über Nacht das richtige Ergebnis ausgerechnet hat und *er hat*! Das Parsen der Eingabedaten habe ich vor dem schlafen gehen noch ”gesehen” — hat ca. eine halbe Minute gedauert, aber dann kam der quälend langsame Zeilenzähler für Aufgabenteil A und da bin ich dann ins Bett.

Die Lösung ist in C geschrieben, eher einfach als effizient, also da lässt sich sicher noch etwas mehr Geschwindigkeit heraus holen ohne auf Assembler zurück zu greifen. Für Teil A brauchte der C64 1½ Stunden (5400 Sekunden) und für Teil B etwas mehr als 2 Stunden (7349 Sekunden).

So, jetzt aber erst einmal die Aufgabe von gestern lösen und die von heute anschauen…

[BlackJack]

Die C-Lösung für den C64 ist jetzt auf 35 Sekunden für das Parsen und aufbereiten der Daten und ca. 1½ Stunden für beide Aufgabenteile runter. Es werden jetzt nur noch die Kommandos ausgewertet die tatsächlich für eine Zeile verwenden werden und nicht mehr alle 300 für jede der 1000 Zeilen und ich ermittle vorher bei welchen Zeilen sich nichts an der Menge der Kommandos ändert, so dass man dort einfach den zuletzt berechneten Wert addieren kann. Mehr bekomme ich da vom Algorithmus her wohl auch nicht hin. Ab hier hilft nur noch die meist benutzten Codeteile von Hand in Assembler neu zu schreiben.

Weil Weihnachten ist und alte Hardware zu Weihnachten aufbauen so einen Spass macht, habe ich jetzt auch einen Atari 130XE in Betrieb genommen, aber da habe ich noch Probleme mit der Datenübertragung. Der hat auch einen 6502-kompatiblen Prozessor, ist aber höher getaktet als der im C64. 1,77 Mhz vs. knapp unter einem Megahertz.

[chpo7234]

Wie schön, dass hier die Lösungen ausgetauscht werden! Wirklich interessant zu sehen, wie andere das gelöst haben. Schade nur, dass es so wenige Threads über die anderen Aufgaben gab Mich würden auch Lösungsvorschläge zu den restlichen Aufgaben interessieren..

Ich habe das Gitter mittels Klasse erstellt und für jede einzelne Lampe einen Dictionary-Eintrag mit den Koordinaten als Key hinterlassen. Zum Beispiel grid["x100y200"]=2. Jede Status-Änderung einer Lampe sowie das Zählen der Lampen/Helligkeit musste ich somit mittels doppelter Schleife durchführen. Eine Schleife für die x-Koordinaten, die zweite für die y-Koordinaten. Das nächste Mal werde ich dann aber auch Numpy für Matrizen verwenden..

Die Text-Auswertung habe ich mittels String-Splitting erledigt. An dieser Stelle sollte ich mich auch mehr mit regular Expressions beschäftigen..

Lieben Gruß

[BlackJack]

@chpo7234: Warum so eine komische Zeichenkette als Schlüssel? Ein Tupel mit den Koordinaten wäre weniger aufwändig. Für das zählen bräuchte man bei Deinem Ansatz nur eine einfache Schleife. Die Koordinaten sind dafür ja egal, also braucht man nur einmal eine Schleife über alle Werte.

Da die ”Matrix” komplett besetzt ist, sehe ich allerdings keinen Vorteil von einem Wörterbuch über verschachtelte Listen. Eher im Gegenteil — das scheint mir umständlicher zu sein.

Was die anderen Lösungen angeht: Mach einfach ein Thema auf für Tage/Lösungen die Dich interessieren.

[/me]

Ich habe das Gitter mittels Klasse erstellt und für jede einzelne Lampe einen Dictionary-Eintrag mit den Koordinaten als Key hinterlassen. Zum Beispiel grid["x100y200"]=2.

Das sieht mir übermäßig kompliziert aus. Ich habe einfach eine Liste mit 1 Mio. Elementen verwendet und dann die jeweilige Position ausgerechnet (1000 * x + y).

[BlackJack]

@/me: Die Position selbst ausrechnen ist aber auch nicht wirklich „Hochsprache“. Das kenne ich aus BASIC und Assembler auf dem C64 und bei dynamisch angelegten mehrdimensionalen Arrays in C, weil es halt nicht anders geht.

[BlackJack]

Die Schaltfunktionen sind nun in 6510-Assembler geschrieben, wobei da auch noch Luft für Verbesserungen ist, und nun braucht alles zusammen knapp über 20 Minuten (20m15s): day06.c, switching.h, und switching.s.