Advent of Code

[bords0]

Nachtrag: Zuerst ging es mir genau so

[Manul]

Heute scheitere ich mal wieder: Wenn ich meinen Code mit den Beispieldaten laufen lasse, liefert er für die ersten 11 fallenden Felsen die korrekten Ergebnisse, für Teil 1 aber einen deutlich zu niedrigen Wert. Mit meinen echten Eingangsdaten dann wiederum einen zu hohen.

Sieht jemand auf Anhieb, wo mein Fehler liegt, oder kann mal mit seinem Code vergleichen, ab welchem Felsen Abweichungen auftreten, damit ich zumindest weiß, wo ich debuggen muß? Das wäre super nett, vielen Dank im voraus!

Mein Code (nicht PEP-konform mit 2 statt 4 Leerzeichen eingerückt, sorry):

Code: Alles auswählen

#!/usr/bin/python3

import fileinput
from itertools import cycle
from collections import UserDict

from P import P

DEBUG = 0

ROCKS = """####

.#.
###
.#.

..#
..#
###

#
#
#
#

##
##"""

ROCK = "#"
FALLING = "@"
EMPTY = "."
WALL = "|"
FLOOR = "-"
CORNER = "+"

class Rock(UserDict):
  
  def __init__(self,pattern):
    super().__init__()
    for y,line in enumerate(reversed(pattern.split("\n"))):
      for x,char in enumerate(line):
        self[P(x,y)] = char == ROCK
    self.width = max(key.x for key in self.keys())+1
    self.height = max(key.y for key in self.keys())+1

  def bottom(self,x):
    return min(key.y for key in self.keys() if key.x == x)

  def top(self,x):
    return max(key.y for key in self.keys() if key.x == x)

  def left(self,y):
    return min(key.x for key in self.keys() if key.y == y)

  def right(self,y):
    return max(key.x for key in self.keys() if key.y == y)

  def __repr__(self):
    lines = []
    for y in range(self.height):
      lines.append("".join("#" if self[P(x,y)] else "." for x in range(self.width)))
    return "\n".join(reversed(lines))

class Cave(UserDict):

  def __init__(self,width=7):
    super().__init__()
    self.width = width
    self.height = 0
    self.falling_rock = None
    self.position = None

  def __getitem__(self,key):
    try:
      if self.falling_rock is not None and self.falling_rock[key-self.position]:
        return FALLING
    except KeyError:
      pass
    try:
      return self.data[key]
    except KeyError:
      if key.x == -1 or key.x == self.width:
        return CORNER if key.y == -1 else WALL
      elif key.y == -1:
        return FLOOR
      else:
        return EMPTY

  def add_rock(self,rocks,jets):
    if DEBUG: print("adding rock")
    self.falling_rock = rock = next(rocks)
    self.position = position = P(2,self.height+3)
    if DEBUG: print(self)
    while True:
      jet = next(jets)
      # move sidewards
      if DEBUG >= 2: print("pushing","left" if jet == "<" else "right")
      direction = -1 if jet == "<" else 1
      edge = rock.left if jet == "<" else rock.right
      if not any(self[P(position.x+edge(y)+direction,position.y+y)] != EMPTY for y in range(rock.height)):
        self.position = position = P(position.x+direction,position.y)
      if DEBUG >= 2: print(self)
      # try to fall down
      if not any(self[P(position.x+x,position.y+rock.bottom(x)-1)] != EMPTY for x in range(rock.width)):
        if DEBUG >= 2: print("falling")
        self.position = position = P(position.x,position.y-1)
        if DEBUG >= 2: print(self)
      else:
        if DEBUG >= 2: print("landed")
        for x in range(rock.width):
          for y in range(rock.height):
            if rock[P(x,y)]:
              self[P(position.x+x,position.y+y)] = ROCK
        self.height = max(self.height,position.y+rock.height)
        self.falling_rock = None
        if DEBUG >= 2: print(self)
        break

  def __repr__(self):
    lines = []
    maxy = self.height+3
    if self.falling_rock is not None:
      maxy += self.falling_rock.height
    for y in range(-1,maxy):
      lines.append("".join(self[P(x,y)] for x in range(-1,self.width+1)))
    return "\n".join(reversed(lines))

def parse_rocks():
  rocks = []
  for pattern in ROCKS.split("\n\n"):
    rocks.append(Rock(pattern))
  return rocks

def part1(rocks,jets):
  cave = Cave()
  rocks = cycle(rocks)
  jets = cycle(jets)
  for _ in range(2022):
    cave.add_rock(rocks,jets)
  print(cave)
  return cave.height

def main():
  rocks = parse_rocks()
  jets = fileinput.FileInput().readline().strip()

  print(part1(rocks,jets))

if __name__ == "__main__":
  main()

Und die (ungünstig benamste) Helferklasse für addierbare 2-dimensionale Punkte:

Code: Alles auswählen

class P(tuple):

  def __new__(self,x,y):
    return tuple.__new__(P,(x,y))

  def __add__(self, other):

    return P(self.x+other.x,self.y+other.y)

  def __sub__(self, other):

    return P(self.x-other.x,self.y-other.y)

  def __mul__(self, integer):

    return P(self.x*integer,self.y*integer)

  __rmul__ = __mul__

  @property
  def x(self):

    return self[0]

  @property
  def y(self):

    return self[1]

[Manul]

Ich hab's jetzt doch selbst gefunden: Die Kollisionserkennung für meine Rock-Klasse war defekt, weil ich die mental wohl mit meiner Cave-Klasse verwechselt habe. Jetzt geht's.

Ist sonst noch jemand dabei? Ich bin dieses Jahr relativ oft daran gescheitert, dass die naive Lösung spätestens mit den echten Eingabedaten zu viele Ressourcen verbraucht und mir zum Optimieren die pfiffige Idee gefehlt hat. Meine "Lösung" für den 19. braucht sogar mit den Beispieldaten länger, als ich bisher gewillt war, sie laufen zu lassen. Entsprechend fehlen mir derzeit noch 2,5 Tage.

Hier meine Lösung für den 17., falls sie jemanden interessiert:

Code: Alles auswählen

#!/usr/bin/python3

import fileinput
from more_itertools import pairwise
from collections import UserDict

from P import P

DEBUG = 0

ROCKS = """####

.#.
###
.#.

..#
..#
###

#
#
#
#

##
##"""

ROCK = "#"
FALLING = "@"
EMPTY = "."
WALL = "|"
FLOOR = "-"
CORNER = "+"

class Cycle:
  def __init__(self,data):
    self.position = -1
    self.data = data

  def __iter__(self):
    return self

  def __next__(self):
    self.position = (self.position + 1) % len(self)
    return self.data[self.position]

  def __len__(self):
    return len(self.data)

class Rock(UserDict):
  
  def __init__(self,pattern):
    super().__init__()
    for y,line in enumerate(reversed(pattern.split("\n"))):
      for x,char in enumerate(line):
        self[P(x,y)] = char == ROCK
    self.width = max(key.x for key in self.keys())+1
    self.height = max(key.y for key in self.keys())+1

  def bottom(self,x):
    return min(key.y for key in self.keys() if self[key] and key.x == x)

  def top(self,x):
    return max(key.y for key in self.keys() if self[key] and key.x == x)

  def left(self,y):
    return min(key.x for key in self.keys() if self[key] and key.y == y)

  def right(self,y):
    return max(key.x for key in self.keys() if self[key] and key.y == y)

  def __repr__(self):
    lines = []
    for y in range(self.height):
      lines.append("".join("#" if self[P(x,y)] else "." for x in range(self.width)))
    return "\n".join(reversed(lines))

class Cave(UserDict):

  def __init__(self,width=7):
    super().__init__()
    self.width = width
    self.height = 0
    self.falling_rock = None
    self.position = None

  def __getitem__(self,key):
    try:
      if self.falling_rock is not None and self.falling_rock[key-self.position]:
        return FALLING
    except KeyError:
      pass
    try:
      return self.data[key]
    except KeyError:
      if key.x == -1 or key.x == self.width:
        return CORNER if key.y == -1 else WALL
      elif key.y == -1:
        return FLOOR
      else:
        return EMPTY

  def top_shape(self):
    tops = [max((key.y for key in self.keys() if key.x == x),default=0) for x in range(self.width)]
    start = min(tops)
    top_shape = set(key-P(0,start) for key in self.keys() if key.y >= start)
    return top_shape

  def add_rock(self,rocks,jets):
    if DEBUG: print("adding rock")
    self.falling_rock = rock = next(rocks)
    self.position = position = P(2,self.height+3)
    if DEBUG: print(self)
    while True:
      jet = next(jets)
      # move sidewards
      if DEBUG >= 2: print("pushing","left" if jet == "<" else "right")
      direction = -1 if jet == "<" else 1
      edge = rock.left if jet == "<" else rock.right
      if not any(self[P(position.x+edge(y)+direction,position.y+y)] != EMPTY for y in range(rock.height)):
        self.position = position = P(position.x+direction,position.y)
      if DEBUG >= 2: print(self)
      # try to fall down
      if not any(self[P(position.x+x,position.y+rock.bottom(x)-1)] != EMPTY for x in range(rock.width)):
        if DEBUG >= 2: print("falling")
        self.position = position = P(position.x,position.y-1)
        if DEBUG >= 2: print(self)
      else:
        if DEBUG >= 2: print("landed")
        for x in range(rock.width):
          for y in range(rock.height):
            if rock[P(x,y)]:
              self[P(position.x+x,position.y+y)] = ROCK
        self.height = max(self.height,position.y+rock.height)
        self.falling_rock = None
        if DEBUG >= 2: print(self)
        break

  def __repr__(self):
    lines = []
    maxy = self.height+3
    if self.falling_rock is not None:
      maxy += self.falling_rock.height
    for y in range(-1,maxy):
      lines.append("".join(self[P(x,y)] for x in range(-1,self.width+1)))
    return "\n".join(reversed(lines))

def parse_rocks():
  rocks = []
  for pattern in ROCKS.split("\n\n"):
    rocks.append(Rock(pattern))
  return rocks

def part1(rocks,jets):
  cave = Cave()
  rocks = Cycle(rocks)
  jets = Cycle(jets)
  for _ in range(2022):
    cave.add_rock(rocks,jets)
  print(cave)
  return cave.height

def part2(rocks,jets):
  cave = Cave()
  rocks = Cycle(rocks)
  jets = Cycle(jets)
  top_shapes = {}
  fallen = 0
  while True:
    cave.add_rock(rocks,jets)
    fallen += 1
    top_shape = cave.top_shape()
    top_shape.add((rocks.position,jets.position))
    top_shape = tuple(top_shape)
    if top_shape in top_shapes.keys():
      height_before,fallen_before = top_shapes[top_shape]
      height_gain = cave.height - height_before
      period = fallen - fallen_before
      moves_left = 1000000000000 - fallen
      periods = moves_left // period
      for _ in range(moves_left % period):
        cave.add_rock(rocks,jets)
      print(cave)
      return cave.height + periods * height_gain
    else:
      top_shapes[top_shape] = (cave.height,fallen)
  return cave.height

def main():
  rocks = parse_rocks()
  jets = fileinput.FileInput().readline().strip()

  print(part1(rocks,jets))
  print(part2(rocks,jets))

if __name__ == "__main__":
  main()

[__blackjack__]

@Manul: Ich hänge massiv hinterher. Irgendwie verzettel ich mich gerne in anderen Problemen — was ich aber auch interessant finde. Wegen dem Vergleich vom BASIC auf dem VIC-20 mit GW-BASIC auf einem 4,77 Mhz IBM-XT-kompatiblen und weil nezzcarth fragte welches Pascal da die PROGRAM-Zeile nicht brauchte, habe ich alle Versionen von Turbo-Pascal installiert, die ich in die Finger bekommen konnte um mal die Entwicklung von dieser Pascal-Implementierung zu verfolgen. Und so bin ich dann darauf gekommen mal zu schauen was damals noch so an Software von CP/M nach DOS gekommen ist. Zuletzt habe ich mir Digital Research's CBASIC-Compiler angeschaut, der ja mit GW-BASIC konkurriert haben muss. Dabei ist der Code deutlich schneller, eben weil kompiliert (nativ, unter CP/M war es noch Bytecode), und die Sprache geht schon in Richtung QBasic — Funktionen mit lokalen Variablen, keine Zeilennummern nötig (aber möglich). Man kann mehr Speicher benutzen — Programm und Daten haben jeweils ihr eigenes 64 KiB-Segment — und man kann das Programm in Overlays aufteilen falls das noch nicht ausreichen sollte.

Das witzigste bei Zeilennummern/Labels in CBASIC ist, das auch Dezimalbrüche als Zeilennummern möglich sind. Wenn zwischen Zeile 22 und 23 etwas eingefügt werden muss, kann man das einfach in Zeile 22.5 schreiben.

@nezzcarth: Turbo Pascal ist die ”etwas” verspätete Antwort. Gab's was besseres für DOS? (Ich kenne nur das. ) Bis Turbo Pascal 5 war es ja sowieso egal was der PROGRAM name war. Der wurde bis dahin ja für nichts verwendet. Ab Turbo Pascal 5 kann man über den UNIT/PROGRAM Namen explizit auf die Namen, die dort existieren zugreifen um Mehrdeutigkeiten aufzulösen. Ab Version 5 darf der Name, wenn er denn angegeben wird, nicht gleich einem Bezeichner in der Übersetzungseinheit sein.

Lustigerweise behauptet die Online-Hilfe auch in Turbo Pascal 7 immer noch „The program heading specifies the program's name and parameters; it is purely decorative and has no meaning to the program itself.“

Da FreePascal als freier ”Klon” von Turbo-Pascal/Delphi startete, ist es nicht verwunderlich, das der auch ohne PROGRAM auskommt.

[nezzcarth]

@__blackjack__: Vielen Dank für die aufwendige Antwort. Ich kenne im Wesentlichen nur Turbo Pascal 7 und Free Pascal und wusste bisher nur einfach nicht, dass man das weglassen kann. So, wie mir Pascal vermittelt wurde, hätte das glaube ich auch nicht gut ins didaktische Konzept gepasst, dass man da irgendwas weg lässt und die formale Ordnung stört

[__blackjack__]

@nezzcarth: Ich habe Turbo Pascal mit Version 5 kennengelernt. Es muss was ab 5.5 gewesen sein, weil der Lehrer der die Computer-AG angeboten hatte, bei mir für den Erstkontakt mit OOP verantwortlich war. Wenig überzeugend übrigens, das habe ich viel später erst mit Java wieder entdeckt.

Ich frage mich ja manchmal wie pragmatisch Wirth war in solchen Sachen, denn Turbo Pascal wäre sicher nicht so erfolgreich gewesen wenn sich Borland an alle formalen Vorgaben gehalten hätte. Dann wäre die Sprache IMHO eher unbenutzbar gewesen, über den reinen Lehrbetrieb hinaus.

Bei so Sachen wie POINTER, ABSOLUTE, das gelegentliche ignorieren von Dimensionen bei Arraytypen, die Mem/MemW/MemL-Arrays, CSeg/DSeg/SSeg, ASM (und INLINE), PChar, Break, Continue, Exit, … haben sich Puristen sicher die Fussnägel aufgerollt.

Ich, und wohl auch viele andere, hätten die Sprache aber sicher nicht so interessant gefunden wenn man da nicht sehr einfach hätte ”ausbrechen” können, und an den gesamten Speicher, auch ausserhalb des eigenen Programms, und an die Register von der Hardware käme. Man will doch an den Registern der Sound- und Grafikkarte herumspielen, und Spiele starten und dort im Speicher herum hacken können, wie man das vom C64 gewohnt war.

[__blackjack__]

Kleine ”Vorwarnung”: Auch dieses Jahr gibt es wieder einen Advent of Code.

[Dennis89]

Erste Aufgabe von 2022 und meine aller ersten Humpelversuche mit Rust:

Code: Alles auswählen

use std::{
    fs::File,
    io::{prelude::*, BufReader},
    path::Path,
};


fn read_lines(filepath: impl AsRef<Path>) -> Vec<String> {
    let file_content = File::open(filepath).expect("File not found");
    let buffer = BufReader::new(file_content);
    buffer.lines()
        .map(|l| l.expect("Can't read"))
        .collect()
}
fn main() {
    let lines = read_lines("/home/dennis/AoC/input.txt");
    let mut privous_deep = 0;
    let mut counter = 0;
    for line in lines {
        let line: i32 = line.parse().unwrap();
        if privous_deep > 0 {
            if line > privous_deep {
                counter  += 1;
            };
	};
	privous_deep = line;
    };
    println!("{}", counter);
}

Wobei ich ehrlicherweise sagen muss, dass ich das 'map(|l|...' noch mal nachlesen muss.
Nach dem ich hier die ersten 6 Kapitel gelesen habe, dachte ich, ich sei bereit für eine kleine Aufgabe. Habe mich getäuscht

Grüße
Dennis

[__blackjack__]

Das war Tag 1 in 2021. Tag 1 in 2022 war was mit Kalorien addieren.

[Dennis89]

Das ist der Beweis, der Smilie mit dem explodierenden Kopd war ernst gemeint

[__blackjack__]

Iiih, in Aufgabenteil zwei von Tag 1 2023 ist eine kleine Falle drin, in die ich getappt bin, die in den Testdaten nicht vorkam, in meinen persönlichen Eingabedaten aber schon. In den Testdaten ist aber trotzdem ein Hinweis.

[Dennis89]

Puuh, ich dachte der 1. Tag wäre mal leicht gewesen. Ich habe das Problem in Teil 2 auch erkannt und mit mein aktueller Code.

Code: Alles auswählen

from pathlib import Path
import re

INPUT = Path('/home/dennis/AoC/2023/Day1/input.txt')
STRING_TO_DIGIT = {
    'one': '1',
    'two': '2',
    'three': '3',
    'four': '4',
    'five': '5',
    'six': '6',
    'seven': '7',
    'eight': '8',
    'nine': '9'
}

def replace_words(text):
    for word, digit in STRING_TO_DIGIT.items():
        text = re.sub(word, digit, text)
    return text
def find_digit(text):
    text = replace_words(text)
    return "".join(digit for digit in text if digit.isdigit())

def split_digits(digits):
    return int("".join([digits[0], digits[-1]]))

def main():
    lines = INPUT.read_text(encoding='UTF-8').splitlines()
    digits = list(map(find_digit, lines))
    print(sum(list(map(split_digits, digits))))

if __name__ == '__main__':
    main()

scheitert daran auch.

Wie könnte ich dass denn lösen?
Ich will jetzt eigentlich nicht jemanden der hier mitliest und selbst rätseln will, den Spass nehmen.

Bitte an die die es noch nicht haben, nicht weiter lesen.


Ich umschreibe es auch nur grob. Wenn ich ein Wort ersetze, dann kann sein ich verliere eine andere Zahl, da dieser plötzlich ein Buchstabe fehlt.
Gibts ein Hinweis, was ich da anwenden könnte?

Grüße und Danke
Dennis

[Manul]

Iiih, in Aufgabenteil zwei von Tag 1 2023 ist eine kleine Falle drin, in die ich getappt bin, die in den Testdaten nicht vorkam, in meinen persönlichen Eingabedaten aber schon. In den Testdaten ist aber trotzdem ein Hinweis.

Falls wir beide die gleiche Falle meinen: Ich hatte den Hinweis bemerkt und die Falle umgangen, hatte aber gar nicht überprüft, ob sie in meinen Eingabedaten überhaupt vorkommt. Das habe ich auf Deinen Tip hin jetzt nachgeholt: Sie kommt auch bei mir sogar mehrfach vor. Also Obacht!

[Manul]

Ich umschreibe es auch nur grob. Wenn ich ein Wort ersetze, dann kann sein ich verliere eine andere Zahl, da dieser plötzlich ein Buchstabe fehlt.
Gibts ein Hinweis, was ich da anwenden könnte?

Dann sorg doch beim Ersetzen einfach dafür, daß der Buchstabe nicht fehlt.

[__blackjack__]

@Dennis89: Ich habe einen regulären Ausdrücke nur zum erkennen verwendet — dann auch gleich für die normalen Ziffern. Und der Lösungsansatz für das Problem was ich hatte war nicht das `re`-Modul aus der Standardbibliothek zu nehmen, sondern das `regex`-Modul. Das ist grundsätzlich kompatibel zum `re`-Modul, kann aber ein bisschen mehr.

@Manul: Wenn ich nicht faul gewesen wäre und gleich mit einer BASIC-Lösung für den VIC-20 angefangen hätte, wäre ich auch nicht in die Falle getappt, denn da müsste man diese ”Optimierung” in der Suche die im normalen `re`-Modul enthalten ist, ja extra manuell machen.

[Dennis89]

Danke für den Tipp, ich denke ich habe das bisschen mehr gefunden, das mir gefehlt hat. Tag 1 ist auf jeden Fall gelöst.

VORSICHT LÖSUNG:

Ja ich hätte dann den 1. Teil auch mit 'regex' machen können, habs jetzt aber mal den Code so gelassen, wie er zur Lösung verwendet wurde.
Ich könnte mir vorstellen, dass das was ich da mit 'text_and_digits' mache,sicherlich etwas eleganter geht.

Auf jeden Fall hier meine Lösung:

Code: Alles auswählen

from pathlib import Path
import regex as re

INPUT = Path('/home/dennis/AoC/2023/Day1/input.txt')
STRING_TO_DIGIT = {
    'one': '1',
    'two': '2',
    'three': '3',
    'four': '4',
    'five': '5',
    'six': '6',
    'seven': '7',
    'eight': '8',
    'nine': '9'
}

PATTERN = '|'.join(STRING_TO_DIGIT.keys())

def replace_words(text):
    text_and_digits = re.findall(f'\d|{PATTERN}', text, overlapped=True)
    text_and_digits = "".join(text_and_digits)
    for word, digit in STRING_TO_DIGIT.items():
        text_and_digits = re.sub(word, digit, text_and_digits)
    return text_and_digits

def find_digit(text):
    text = replace_words(text)
    return "".join(digit for digit in text if digit.isdigit())

def split_digits(digits):
    return int("".join([digits[0], digits[-1]]))

def main():
    lines = INPUT.read_text(encoding='UTF-8').splitlines()
    digits = list(map(find_digit, lines))
    print(sum(list(map(split_digits, digits))))

if __name__ == '__main__':
    main()

Grüße
Dennis

[narpfel]

Das `re`-Modul selbst kann das auch, zumindest so ähnlich:

Code: Alles auswählen

>>> digits = dict(one="1", two="2")
>>> pattern = re.compile(f"(?=({'|'.join(digits)}))")
>>> pattern.sub(lambda match: digits[match[1]], "twone")
'2tw1one'

Der Trick ist, das Pattern in eine lookahead assertion zu stecken, damit ein erfolgreicher Match nichts konsumiert.

[nezzcarth]

Etwas erfahreneren Programmierenden widerstrebt es zwar, aber die wenigen möglichen Sonderfälle sind mit Stift und Papier tatsächlich schnell gefunden und lassen sich dann einfach in einem Vorverarbeitungsschritt abhandeln, ganz ohne alternatives Regex-Modul und schwarzen Gürtel in RegEx. Ich glaube, die Schwierigkeit ist hier vielleicht eher die psychologische Hürde weil das natürlich als eher unschick gilt

[narpfel]

@nezzcarth: Stift und Papier gibt mir Flashbacks zum Würfel von letztem Jahr, dann doch lieber schwarze Regexmagie.

[derElch]

Nach dem ich zunächst zwar das Testbeispiel von ohne Probleme geschafft habe, war natürlich das gesamte falsch
Wobei es bei mir nicht Spezialfall sondern die Wiederholung die ich nicht berücksichtigt hatte

Ich beschränke meinen Code auf das Suchen der Zahlen:

Code: Alles auswählen

def get_numbers(text: str) -> list[str]:
    line_with_numbers = list(text)
    for pattern in NUMER_TRANSLATOR.keys():
        match = text.find(pattern)
        if match == -1:
            continue
        line_with_numbers[match] = NUMER_TRANSLATOR[pattern]
        match = text.rfind(pattern)
        line_with_numbers[match] = NUMER_TRANSLATOR[pattern]

    calibration_regex = re.compile(r'\d')
    numbers = re.findall(calibration_regex, "".join(line_with_numbers))
    return numbers

Der Rest wurde schon in den vorigen Posts behandelt.