Advent of Code

[__blackjack__]

Aaah, hatte ich noch gar nicht nachgeschaut. Weiss gar nicht mit welchem Rechner/System ich das dieses Jahr angehen will. Bin halbwegs sattelfest in CP/M auf Intel 8080, aber PDP-11 ist auch irgendwie interessant. Da aber noch kein Betriebssystem angeschaut. Vielleicht am Wochenende mal Unix installieren und dann vielleicht einen nativen C-Compiler in den Fingern haben‽

[nezzcarth]

Emulierst du diese Systeme mit SIMH oder wie ist da die Herangehensweise?

[__blackjack__]

CP/M mit z80pack, weil man den Altair/IMSAI da so schön grafisch hat. PDP würde ich mit simh machen.

[Kebap]

Traditionellerweise löse ich die ersten 2-3 Tage per Excel, einfach weils am schnellsten geht, die Daten manuell herum zu schubsen, statt eine sattelfeste automatische Lösung zu programmieren.

Diesmal hab ich Tag 1 pflichtgemäßg per Python versucht, und immerhin den ersten Teil auch geschafft, nur beim zweiten bekomme ich die Info, dass meine Antwort zu hoch gegriffen sei. Ich fand noch nicht alle Gründe. Einen Schnitzer hatte ich schon ausgebaut, dass die Position 100 fälschlich doppelt berechnet wurde. Bin jetzt schon ein paar Dutzend Zeilen manuell durchgegangen, aber die Logik scheint soweit erstmal stichfest. Was habe ich noch übersehen?

Code: Alles auswählen

import os
from dataclasses import dataclass

@dataclass
class Instruction:
  direction: str
  length: int
  text: str


def parse_data_01(data):
  instructions = []
  for line in data.split("\n"):
    first_char = line[0]
    if first_char == "R":
      direction = +1
    elif first_char == "L":
      direction = -1
    else:
      raise ValueError("Direction must be coded as L or R, but found: {first_char}.")

    other_chars = line[1:]
    length = int(other_chars)
    instructions.append(Instruction(direction, length, line))

  return instructions


def solve_01(data):
  zeroes_hit = 0
  zeroes_passed = 0
  position = 50

  print(f"- The dial starts by pointing at {position}.")

  instructions = parse_data_01(data)
  for i in instructions:
    position = (position + (i.direction * i.length))

    while position < 0:
      zeroes_passed += 1
      position += + 100

    while position > 100:
      zeroes_passed += 1
      position -= 100

    if position in (0, 100):
      position = 0
      zeroes_hit += 1
      zeroes_passed += 1

    print(f"- The dial is rotated {i.text} to point at {position}.")

  print(f"- Hit position 0 a total of {zeroes_hit} times.")
  print(f"- Passed position 0 a total of {zeroes_passed} times.")

if __name__ == "__main__":
  folder = "C:/data/py/26-aoc2025"
  number = "01"
  file_path = os.path.join(folder, f"{number}.txt")

  with open(file_path) as f:
    data = f.read().strip()

  solve_01(data)

Das i hab ich extra so unerwartet abgekürzt benannt, um die Stammuser hier zu grüßen.

[Manul]

Einen Schnitzer hatte ich schon ausgebaut, dass die Position 100 fälschlich doppelt berechnet wurde. Bin jetzt schon ein paar Dutzend Zeilen manuell durchgegangen, aber die Logik scheint soweit erstmal stichfest. Was habe ich noch übersehen?

Es gibt noch eine weitere Position, die in Deinem Code manchmal (etwa in der Hälfte der Fälle) doppelt gezählt wird.

Ich hatte erst den gleichen Fehler beim 2. Teil gemacht, daher hab ich das schnell gefunden.

[__blackjack__]

@Kebap: Das ``position > 100`` ist komisch. Sollte das nicht >99 sein und den Fall ``if position == 100`` kann man sich dann sparen‽

[narpfel]

Teil 1 in ging in Bash noch relativ einfach als Einzeiler:

Code: Alles auswählen

n=50; < input tr LR -+ | while read line; do ((n = (n $line + 100) % 100)); echo $n; done | grep -c '^0$'

Oder gegolft sogar unter 80 Zeichen:

Code: Alles auswählen

n=50;tr LR -+<i|while read l;do((n=(n$l+100)%100));echo $n;done|grep -c '^0$'

Aber für Teil 2 hab’ ich mehrere Zeilen gebraucht:

Code: Alles auswählen

n=50
part_2=0
while read line; do
    ((step = line < 0 ? -1 : 1))
    ((step_count = line < 0 ? -line : line))
    for ((i = 0; i < step_count; ++i)); do
        ((n = (n + step + 100) % 100, n == 0 && ++part_2))
    done
done < <(tr LR -+ < input)
echo $part_2

Dass in der `for`-Schleife alles in einer arithmetic expansion gemacht wird, ist eine Performanceoptimierung. Bash ist sehr geeignet für sowas, nur 100x langsamer als der selbe Algorithmus in Python umgesetzt.

[narpfel]

Heute gingen beide Teile sehr schön als Basheinzeiler.

[Kebap]

Einen Schnitzer hatte ich schon ausgebaut, dass die Position 100 fälschlich doppelt berechnet wurde. Bin jetzt schon ein paar Dutzend Zeilen manuell durchgegangen, aber die Logik scheint soweit erstmal stichfest. Was habe ich noch übersehen?

Es gibt noch eine weitere Position, die in Deinem Code manchmal (etwa in der Hälfte der Fälle) doppelt gezählt wird.

Ich hatte erst den gleichen Fehler beim 2. Teil gemacht, daher hab ich das schnell gefunden.

Hmm, ich habe nun ein Beispiel isolieren können, das fälschlich doppelt gezählt wird.
Tatsächlich an derselben Position, die ich bereits repariert wähnte:

Code: Alles auswählen

- The dial starts by pointing at 50.
- The dial is rotated R50 to point at 0.
- Passed zero: 2 times. 
- Hit zero: 1 time.

Irgendwie hab ich gerade einen Knoten im Kopf, wie ich das am besten löse, ohne zu viel zu verlieren.
Habe den Vorschlag von __blackjack__ umgesetzt, aber das brachte keine Besserung.


edit: Habe jetzt meinen letzten Entwurf mit den While-Schleifen weggeworfen, die jede Drehung einzeln summieren.
Statt dessen benutze ich nun die Kraft der Division, um direkt die richtige Anzahl der Hunderterübergänge zu errechnen:

Code: Alles auswählen

    zeroes_passed += abs(position // 100)
    position = position % 100
    zeroes_hit += (position == 0)

Damit konnte ich meine Antwort erneut deutlich reduzieren, doch oh je, sie ist immer noch zu hoch..

edit: Sie ist zu HOCH, obwohl mir jetzt wieder Fälle aufgefallen sind, die ich gar nicht richtig mitzähle:

Code: Alles auswählen

- The dial starts by pointing at 1.
- The dial is rotated L1  to point at 0.        Passed 0: 0 times. Hit 0: 1 times.

Sollte doch auch 1x passed sein. Hmrgl.

[Manul]

Hmm, ich habe nun ein Beispiel isolieren können, das fälschlich doppelt gezählt wird.
Tatsächlich an derselben Position, die ich bereits repariert wähnte:

Code: Alles auswählen

- The dial starts by pointing at 50.
- The dial is rotated R50 to point at 0.
- Passed zero: 2 times. 
- Hit zero: 1 time.

Die war auch schon repariert. Zumindest tritt das mit Deinem oben geposteten Code nicht auf.

Irgendwie hab ich gerade einen Knoten im Kopf, wie ich das am besten löse, ohne zu viel zu verlieren.
Habe den Vorschlag von __blackjack__ umgesetzt, aber das brachte keine Besserung.

Das hat im Gegenteil wahrscheinlich den Fehler eingeführt. Ich mag was übersehen, aber ich halte den Vorschlag mit ">99" ausnahmsweise für nicht hilfreich.

Code: Alles auswählen

    zeroes_passed += abs(position // 100)
    position = position % 100
    zeroes_hit += (position == 0)

[...]

Code: Alles auswählen

- The dial starts by pointing at 1.
- The dial is rotated L1  to point at 0.        Passed 0: 0 times. Hit 0: 1 times.

[...]
Sollte doch auch 1x passed sein. Hmrgl.

Warum sollte es das? Wenn Du die drei Zeilen oben im Kopf mit der Endposition durchgehst, sollte klar werden, dass "zeroes_passed" hier nicht hochgezählt wird.

[snafu]

Tag 1 in Rust, aber erstmal nur für die Beispiele aus Part 1:

Code: Alles auswählen

fn parse_steps(instruction: &str) -> i32 {
    instruction.trim_start_matches("R")
               .replace("L", "-")
               .parse()
               .unwrap()
}

fn find_path(start: i32, instructions: Vec<&str>) -> impl Iterator<Item = i32> {
    instructions.into_iter().map(parse_steps)
                .scan(start, |position, steps| {
                    *position = (*position + steps).rem_euclid(100);
                    dbg!(&position);
                    Some(*position)
                })
}

fn main() {
    let instructions = vec!["L68", "L30", "R48", "L5", "R60", "L55", "L1", "L99", "R14", "L82"];
    let zeros = find_path(50, instructions).filter(|n| *n == 0);
    dbg!(zeros.count());
}

Das Lesen aus dem Dateianhang baue ich noch ein. Bin gespannt, ob mir da mein Parser zum Verhängnis wird.

Jedenfalls ist das ein schönes Anwendungsbeispiel für die scan()-Methode, finde ich.

[Kebap]

Warum sollte es das? Wenn Du die drei Zeilen oben im Kopf mit der Endposition durchgehst, sollte klar werden, dass "zeroes_passed" hier nicht hochgezählt wird.

Stimmt, ich habe da die Begriffe ein bisschen verschmiert. Also bei mir war "zeroes_passed" eher so gedacht, dass es die Antwort auf Frage B ist, also eigentlich zeroes_passed_or_hit

[snafu]

Teil 1 ist gelöst, Teil 2 (übersprungene Nullen zählen) krieg ich noch nicht hin. Ich habe mir div_floor() selbst geschrieben, da Rust in der stabilen Version dies noch nicht unterstützt. IMHO ist dies der richtige Ansatz. Muss ich mir die Tage nochmal genauer angucken, warum er dabei zu viele Nullen zählt...

Code: Alles auswählen

use std::fs::read_to_string;

fn instruction_to_int(instruction: &str) -> i32 {
    instruction
        .trim_start_matches("R")
        .replacen("L", "-", 1)
        .parse()
        .unwrap()
}

fn div_floor(a: i32, b: i32) -> i32 {
    (a as f32 / b as f32).floor() as i32
}

fn find_path(
    start: i32,
    instructions: impl Iterator<Item = i32>,
) -> impl Iterator<Item = (i32, i32)> {
    let state = (start, 0);
    instructions.scan(state, |(pos, null_hits), steps| {
        let shift = *pos + steps;
        *pos = shift.rem_euclid(100);
        *null_hits += div_floor(shift, 100).abs();
        Some((*pos, *null_hits))
    })
}

fn main() {
    let input = read_to_string("input.txt").unwrap();
    let instructions = input.lines().map(instruction_to_int);
    let path = find_path(50, instructions);
    //dbg!(path.last().unwrap());
    let zeros = path.filter(|(pos, _)| *pos == 0);
    dbg!(zeros.count());
}

Das Auslesen der Zeilen kann man effizienter umsetzen, ist für die Aufgabe aber nicht entscheidend und war mir dafür zu viel Boilerplate.

[narpfel]

@snafu: Ist `div_floor` nicht das gleiche wie `div_euclid` für nichtnegative `rhs`?

[snafu]

Nun mit div_euclid():

Code: Alles auswählen

use std::fs::read_to_string;

fn instruction_to_int(instruction: &str) -> i32 {
    instruction
        .trim_start_matches("R")
        .replacen("L", "-", 1)
        .parse()
        .unwrap()
}

fn find_path(
    start: i32,
    instructions: impl Iterator<Item = i32>,
) -> impl Iterator<Item = (i32, i32)> {
    let state = (start, 0);
    instructions.scan(state, |(pos, hits_zero), steps| {
        let next_pos = *pos + steps;
        *hits_zero += next_pos.div_euclid(100).abs();
        if next_pos == 0 {
            *hits_zero += 1;
        }
        if next_pos < 0 && *pos == 0 {
            *hits_zero -= 1;
        }
        *pos = next_pos.rem_euclid(100);
        Some((*pos, *hits_zero))
    })
}

fn main() {
    let input = read_to_string("input.txt").unwrap();
    let instructions = input.lines().map(instruction_to_int);
    let path = find_path(50, instructions);
    //dbg!(Vec::from_iter(path));
    dbg!(path.last().unwrap());
}

Trotzdem krieg ich's nicht gebacken, den zweiten Teil des Rätsels zu lösen. Für den Beispiel-Input klappt es, aber für die Textdatei leider nicht.

[__blackjack__]

Ich hatte da auch ein Problem und bin das dann systematisch angegangen. Also wenn die kompletten Umdrehungen abgefrühstückt sind, welchen Wertebereich hat man vor dem drehen und welchen danach und welche ”Klassen” gibt es da. Und dann habe ich alle Möglichkeiten von vor und nach dem drehen aufgeschrieben, und mir überlegt in welchen Fällen man den Zähler erhöhen muss, und in welchen nicht. So hatte ich dann den Fall gefunden, den ich nicht berücksichtigt hatte.

[grubenfox]

Probleme beim zweiten Teil hatte ich auch, dann eher unsystematisch verschiedenes probiert und das ganze dann erst mal ein paar Tage ruhen lassen... gestern Abend hatte ich mir dann noch vier weitere Testfälle ausgedacht:

Code: Alles auswählen

    assert links(start=5,anzahl_schritte=5) == (0,1) # neuer Start: 0, gezählte Nuller: 1 
    assert links(start=5,anzahl_schritte=6) == (99,1)
    assert links(start=5,anzahl_schritte=105) == (0,2)
    assert links(start=5,anzahl_schritte=100) == (5,1)

als die dann fehlerfrei durchliefen stimmte dann auch das Endergebnis

[snafu]

Jetzt hab ich's auch. Ich mache in jedem Fall die Division durch 100 und addiere den absoluten Wert davon auf meine Null-Treffer. Der Sonderfall ist, wenn ich NICHT auf der Null stehe und durch eine Linksdrehung entweder auf der Null oder links davon lande. Dann zähle ich noch einen Treffer dazu.

Diese Beschreibung bezieht sich auf Rust und Sprachen, in denen sich die Ganzzahl-Division ähnlich verhält. Bei Python muss man den Test für den Sonderfall anpassen, denn da kommt z. B. für -5 / 100 etwas anderes raus als in Rust.

[__blackjack__]

@snafu: Ich habe das durch 100 teilen/modulo einfach gemacht *bevor* ich überhaupt "L" oder "R" angeschaut habe, um die Anzahl der vollen Umdrehungen zu bekommen und die Restdistanz egal in welche Richtung.

[nezzcarth]

Für meinen Ansatz benötige ich Modulo bzw. 'divmod' nur für eine Richtung. Ich zähle zudem endet-auf-Null/passiert-Null getrennt und rechne das dann für die Antwort auf Teil 2 zusammen.

Ich hatte Teil 1 zwar noch tagesaktuell geschafft, mich aber relativ schwer getan, insb. gemessen an üblichen AoC-Tag-1-Aufgaben. Insofern ist es natürlich interessant zu hören, dass es auch anderen scheinbar nicht ganz leicht fiel