[Rust]Summe eines Vec mit Wahrheitswerten

[narpfel]

Nor do you need a fancy computer; every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.

Da kann man noch ein bisschen was rausholen. Zum Beispiel hiermit.

[__blackjack__]

@Dennis89: Wie gesagt, es werden da über 129 Millionen Schleifendurchläufe zu viel gemacht — bei dem einen Beispiel. Und wahrscheinlich sind selbst die 2048 Möglichkeiten nicht nötig wenn man nicht `itertools,product()` verwendet, sondern die Operationen selbst rekursiv aufzählt und abbricht sobald das Zwischenergebnis grösser als das gesuchte Ziel ist, denn weitere Operationen machen das Zwischenergebnis ja nur *noch* grösser. Das könnte für Aufgabenteil 2 interessant bis wirklich wichtig werden in Rust, weil dort Zwischenergebnisse wahrscheinlich auch die 64 Bit sprengen können.

[Dennis89]

Guten Morgen und danke euch.

`iproduct` hatte ich tatsächlich auch gesehen, bin aber davon ausgegangen, dass das nicht das richtige ist. Zum einen gibt mir das eine Tuple zurück, die ich nicht mit meinen Werte "zippen" kann und zum anderen hat das im Vergleich zu `itertools.product` für Python, kein `repeat`-Argument. Dann muss ich den Vec, der die Funktionen enthält, so oft kopieren und an `iproduct` übergeben, bis mein Ergebnis die gewünschte Länge hat?
Ich denke dass ich das sicherlich so nicht machen muss, was anderes fällt mir nur nicht ein.

Die Schleife würde so aussehen:

Code: Alles auswählen

for operations in  iproduct!(multible_operations.clone(), multible_operations)
    {
        let mut values = values.iter();
        let mut result: u64 = *values.next().unwrap();
        for (operation, value) in operations.zip(values) {
            let result_: u64 = operation(&result, value);
            result = result_;
        }
        if result == *target {
            return true;
        }
    }

`operations` ist jetzt eine Tuple vom Typ `(fn(&u64, &u64) -> u64, fn(&u64, &u64) -> u64)` Das ist gut wenn `values` 3 Werte hat, aber bei 4 ist das eine Operation zu wenig usw. Irgendwie muss ich mein `length` wieder mit ins Spiel bringen. Ich verstehe nur nicht wie man das in Rust macht.

Und dann natürlich noch das Problem:

Code: Alles auswählen

error[E0599]: `(fn(&u64, &u64) -> u64, ...)` is not an iterator
  --> src/main.rs:42:46
   |
42 |         for (operation, value) in operations.zip(values) {
   |                                              ^^^ `(fn(&u64, &u64) -> u64, ...)` is not an iterator
   |

Ich weiß das man über Tuples so nicht iterieren kann, da sie unterschiedliche Typen enthalten können. Das was `iproduct` zurückgibt, macht für mich keinen Sinn bzw. ich verstehe gar nicht wie ich damit umgehen muss.

@__blackjack__ Das mit der Rekursion habe ich noch im Hinterkopf (und ich mag rekursive Aufrufe immer noch nicht), ich wollte erst mal die Python-Lösung nachbauen, weil ich weiß das es funktioniert und ich mich auf Rust konzentrieren kann und nicht noch Fehler in meinen eigenen Gedanken suchen muss. Man könnte in die Schleife noch eine Abfrage einbauen, die die Größe des Ergebnisses prüft und bei Bedarf abbricht.(?) Je nach dem wie weit ich damit diese Woche komme, versuche ich das mit der Rekursion evtl. noch


Grüße
Dennis

[narpfel]

und zum anderen hat das im Vergleich zu `itertools.product` für Python, kein `repeat`-Argument.

Ah, du musst die Länge vom Ergebnis dynamisch festlegen. Dafür gibt es `multi_cartesian_product`.

Spoiler: So würde ich deinen Code mit minimalen Änderungen kompilierbar machen https://godbolt.org/z/h9dEas3db und so würde ich das mit ein paar mehr Änderungen schreiben: https://godbolt.org/z/h5shT7oWG (Das `fold` kann gerne auch durch eine explizite Schleife ersetzt werden, so wie in deinem Code.)

[Kebap]

So große Zahlen versteh ich nicht. Hab mir das übersetzt:

Code: Alles auswählen

s = 10989.60064
print(f"{s} s")
m = s / 60
print(f"{m} min")
h = m / 60
print(f"{h} h")
-->
10989.60064 s
183.16001066666666 min
3.0526668444444445 h

Geduld ist schön ausgedrückt, habe die Laufzeit gemessen:

Code: Alles auswählen

10989.60064s runtime

[__blackjack__]

@Kebap: Hm, ich habe diese Aufgabe jetzt gerade in GW-BASIC auf einem Rechner mit etwas unter 10 Mhz Prozessortakt laufen. Die Laufzeit wird am Ende auch in Sekunden ausgegeben. Mal schauen wie gross *diese* Zahl wird.

[snafu]

Ich arbeite nun doch die Rust Doku mithilfe des online verfügbaren Buches durch. Mein Eindruck von Rust ist nun gar nicht mehr so "kryptisch". Wobei ich für den Anfang bei ``Option``s lieber meine Fallunterscheidungen via ``match`` hinschreibe, anstatt alles zwingend über verkettete Methoden auszudrücken.

Gefällt mir jedenfalls ganz gut bisher, auch dass der Compiler bei so vielen Dingen aufpasst. Vielleicht setze ich das tatsächlich für ein Projekt ein.

[Dennis89]

Danke für die weiter Hilfe!

Der aktuelle Stand:

Code: Alles auswählen

use itertools::Itertools;
use std::error::Error;
use std::fs::read_to_string;
use std::iter::repeat_n;
use std::time::Instant;

type Operations = [fn(&u64, &u64) -> u64; 2];

fn add(a: &u64, b: &u64) -> u64 {
    a + b
}

fn multiply(a: &u64, b: &u64) -> u64 {
    a * b
}

fn parse_lines<'a>(
    lines: impl Iterator<Item = &'a str>,
) -> Result<Vec<(u64, Vec<u64>)>, Box<dyn Error>> {
    lines
        .map(|line| {
            let (target, operands) = line.split_once(": ").ok_or("No colon in line")?;
            let operands = operands
                .split(' ')
                .map(|operand| operand.parse())
                .collect::<Result<Vec<_>, _>>()?;
            Ok((target.parse()?, operands))
        })
        .collect()
}

fn check_calibration(target: &u64, values: &[u64], operations: &Operations) -> bool {
    for operations in repeat_n(operations, values.len() - 1).multi_cartesian_product() {
        let mut values = values.iter();
        let mut result: u64 = *values.next().unwrap();
        for (operation, value) in operations.iter().zip_eq(values) {
            let result_: u64 = operation(&result, value);
            result = result_;
            if result > *target {
                break;
            }
        }
        if result == *target {
            return true;
        }
    }
    false
}

fn sum_solvable_calibrations(calibrations: &Vec<(u64, Vec<u64>)>, operations: &Operations) -> u64 {
    let mut solvable: Vec<u64> = Vec::new();
    for (target, values) in calibrations {
        if check_calibration(target, values, operations) {
            solvable.push(*target);
        };
    }
    solvable.iter().sum()
}

fn main() {
    let input =
        read_to_string("/home/dennis/PycharmProjects/AdventofCode/2024/Day07/input07.txt").unwrap();
    let calibrations_result = parse_lines(input.lines());
    let calibrations = match calibrations_result {
        Ok(values) => values,
        Err(error) => panic!("Error: {error:?}"),
    };
    let operations: Operations = [add, multiply];
    let start = Instant::now();
    let sum_ = sum_solvable_calibrations(&calibrations, &operations);
    println!("{:?}", sum_);
    println!("{:.5?} runtime", start.elapsed());
}

Die Laufzeit vereinbart sich wesentlich besser mit meiner Geduld:

Code: Alles auswählen

56.29204ms runtime

Ich habe gleich mal etwas angefangen, den Code anzupassen, dass die Funktionen für Aufgabeteil 2 auch verwendet werden können, nur durch den festgelegten Typ `Operations` kann ich nicht einfach eine 3. Funktion verwenden. Da muss ich noch schauen, ob und wie ich das mache.

Deine zweite Lösung muss ich jetzt aber erst aber auch noch durcharbeiten.
Was mir gleich aufgefallen ist, ich aber nicht verstehe. Wieso `use itertools::Itertools as _;` ? Also wieso das Umbenennen? Mich verwirrt das, weil die Unterstriche auch in `.collect::<Result<Vec<_>, _>>()?;` verwendet werden. Sind das jetzt Itertools-Typen? Ne, oder?

@snafu

[narpfel]

nur durch den festgelegten Typ `Operations` kann ich nicht einfach eine 3. Funktion verwenden. Da muss ich noch schauen, ob und wie ich das mache.

Zwei Möglichkeiten: Du übergibst nicht ein Array mit konstanter Länge, sondern einen Wert mit einem Typ, dessen Länge dynamisch festgelegt werden kann. Oder du schreibst die Funktion so, dass sie mit Arrays beliebiger Länge aufgerufen werden kann. Stichwort const generics.

Wieso `use itertools::Itertools as _;` ? Also wieso das Umbenennen?

Man kann Methoden aus Traits nur aufrufen, wenn der Trait importiert ist. Ich will den Trait selbst aber nicht benutzen, sondern nur Methoden daraus. Also benenne ich den Trait beim Import um, damit ich weniger Namen im globalen Scope habe. Manchmal hat man den Fall, dass man Methoden aus zwei verschiedenen Traits mit dem gleichen Namen benutzen will. `std::fmt::Write` und `std::io::Write` zum Beispiel, da muss man mindestens einen umbenennen. Irgendwann hab ich mir mal angewöhnt, das immer zu machen, wenn ich einen Trait nur wegen seiner Methoden importiere.

Mich verwirrt das, weil die Unterstriche auch in `.collect::<Result<Vec<_>, _>>()?;` verwendet werden. Sind das jetzt Itertools-Typen? Ne, oder?

Nein, der Unterstrich wird in Rust quasi gleich benutzt wie in Python: „Da muss an der Stelle syntaktisch ein Name stehen, aber ich will den nicht hinschreiben.“, z. B. in einer `for`-Schleife:

Code: Alles auswählen

for _ in 0..10 {
    println!("hello world");
}

In einer Typannotation bedeutet er, dass der Typ inferiert werden soll. Ich könnte `.collect::<Result<Vec<u64>, Box<dyn std::error::Error>>>()` schreiben, aber sowohl das `u64` als auch das `Box<dyn std::error::Error>` ist eindeutig durch den Rest der Funktion bestimmt, also muss ich das nicht schreiben. Und man kann nicht `.collect::<Result<Vec>>()` schreiben, weil es nicht erlaubt ist, Typparameter einfach wegzulassen.

Code: Alles auswählen

            let result_: u64 = operation(&result, value);
            result = result_;

Warum schreibst du das so? Warum nicht direkt `result = operation(&result, value);`?

Ansonsten sind da noch ein paar Typannotationen, die man eigentlich nicht schreiben würde. Gibt es einen Grund, warum du die an ein paar Stellen schreibst, an anderen Stellen aber nicht?

[Dennis89]

Danke für die Antwort.

Ich habe zu

Code: Alles auswählen

type Operations = Box<[fn(&u64, &u64) -> u64]>;

gewechselt.

Die eigentliche Bedeutung des Unterstrichs, in der Typannotation, war mir grundsätzlich bewusst. Ich war mir aber nicht sicher bzw. verwirrt ob sich das jetzt geändert hat, weil der Name `_` ja plötzlich an `Itertools` gebunden wurde, durch das umbenennen.

Warum schreibst du das so? Warum nicht direkt `result = operation(&result, value);`?

Da hatte ich in vorherigen Versuchen wohl noch einen Fehler drin. Da gab es Fehlermeldungen mit ausgeliehen Werten. Habe das gerade angepasst.

Gibt es einen Grund, warum du die an ein paar Stellen schreibst, an anderen Stellen aber nicht?

Wenn ich Fehlermeldungen hatte, die sich auf Typen bezogen und ich die nicht gleich verstanden habe, dann habe ich mir den Typ dazu geschrieben um einen besseren Überblick zu haben. Ich denke daher kommt die Inkonsistenz.


Grüße
Dennis

[narpfel]

weil der Name `_` ja plötzlich an `Itertools` gebunden wurde, durch das umbenennen.

`_` ist kein normaler Identifier: Wenn es in einer `use`-Deklaration als Target benutzt wird, ist das importierte Item danach unter keinem Namen erreichbar. Wenn man `let _ = ...` schreibt, wird der Wert nicht gemovet, es wird keine Variable mit dem Namen `_` angelegt: https://godbolt.org/z/PefGcWa94

Code: Alles auswählen

type Operations = Box<[fn(&u64, &u64) -> u64]>;

Warum `Box`? Wäre ein Slice nicht einfacher?

[Dennis89]

Ah danke, jetzt wird es klarer!

Warum `Box`? Wäre ein Slice nicht einfacher?

Finde ich komplizierter, weil ich das nur hinbekommen habe, wegen den Hilfen des Compilers:

Code: Alles auswählen

type Operations = [fn(&u64, &u64) -> u64];


fn main() {
    let operations: &Operations = &[add, multiply];
}

Wieso ich hier jetzt zwei mal `&` benötige, begreife ich nicht. Ich werde mir das Kapitel im Buch noch mal durchlesen. Bis vor kurzem dachte ich, dass ich das begriffen habe, wann "etwas" ein Objekt nur ausgeliehen bekommt und/oder wann es ihm gehören soll. Nur jetzt beim erstellen des Objekts leuchtet mir das nicht ein. Daher habe ich `Box` verwendet. Heißt aber nicht, das ich es nicht gerne verstehen würde, weil klar, der Code sieht schöner aus.


Grüße
Dennis

[__blackjack__]

Schade das ich heute kein Home Office hatte, da hätte ich immer mal wieder die blinkenden LEDs vom Altair-Emulator anschauen können, während der 11 Stunden und 51 Minuten damit beschäftigt war Aufgabenteil 1 zu lösen, mit folgendem BASIC-Programm unter CP/M mit MBASIC:

Code: Alles auswählen

10 DEFINT A-Z:DIM V#(12):R1#=0
20 OPEN "I",#1,"INPUT.TXT"
30 WHILE NOT EOF(1):LINE INPUT #1,L$:PRINT L$
40 I=INSTR(L$,":"):IF I=0 THEN PRINT"missing ':'":CLOSE 1:END
50 T#=VAL(LEFT$(L$,I)):N=0:I=I+2
60 J=INSTR(I,L$," "):IF J=0 THEN 80
70 N=N+1:V#(N)=VAL(MID$(L$,I,J-I)):I=J+1:GOTO 60
80 N=N+1:V#(N)=VAL(MID$(L$,I))
90 FOR I=0 TO 2^(N-1)-1:X#=V#(1):M=1:FOR J=2 TO N
100 IF I AND M THEN X#=X#+V#(J) ELSE X#=X#*V#(J)
110 M=M+M:NEXT:IF X#=T# THEN R1#=R1#+T#:I=2^(N-1)
120 NEXT:WEND:CLOSE 1:PRINT R1#:SYSTEM

[Dennis89]

Wenn du das mit dem gleichen Algorithmus auf Teil 2 erweiterst, dann reicht ein Tag bestimmt nicht mehr aus.

[__blackjack__]

@Dennis89: Nachdem ich mich zu lange mit FORTRAN aufgehalten habe und wie ich damit die originale Eingabedatei verarbeiten könnte, habe ich den BASIC-Compiler von Microsoft mal auf das Programm losgelassen. Das kompilierte Programm braucht nur noch etwas mehr als 2½ Stunden.

Nächster geplanter Schritt: Das umschreiben, dass es eine Datei schreibt wo für jede EIngabezeile gespeichert wird ob sie das Kriterium von Aufgabenteil 1 erfüllt. Denn die brauche ich für Teil 2 ja nicht mehr zu testen. Und dann mal schauen ob der Rest in sinnvoller Rechenzeit machbar ist,.

[snafu]

Allmählich werde ich warm mit Rust.

OOP finde ich herausfordernd, weil ich dort nicht immer Referenzen oder Iteratoren durchreichen will, sondern auch mal Werte in einem Vektor behalten möchte. Man könnte dann stumpf alles klonen, was in den Vektor gehen soll. Aber viel spannender ist ja das Thema Referenzen in Verbindung mit dem für mich völlig Konzept der Lifetimes. Man muss sich in dem Zusammenhang fragen, an welcher sinnvollen Stelle man die Originale seiner Objekte behält und wo man Referenzen darauf einsetzt. In Python kümmert sich der GC auf globaler Ebene darum und kommt auch mit komplexeren Abhängigkeiten klar. In Rust muss ich da selber ein Auge drauf haben.

Und ansonsten ist mir aufgefallen, dass nicht jeder Tipp des Compilers bei einer Fehlermeldung wirklich hilfreich ist. Rust gibt da häufig einen konkreten Typen als Vorschlag an. Wenn ich z. B. eine Methode schreiben möchte, die einen Iterator liefern soll, der seine Elemente auf eine bestimmte Funktion mappt, dann schlägt der Compiler eine komplizierte Typangabe vor. Da kann man aber einfach die passende Abstraktion (Trait = Verhalten) einsetzen. Ein Beispiel: Wenn ich die Rückgabe von Vec::chunks() an ``Spam::new`` übergeben möchte (also jeweils die einzelnen Chunks) und der Aufrufer somit einen neuen Iterator mit ``Spam```-Instanzen erhalten soll, dann schlägt der Compiler in Verbindung mit der map()-Methode folgendes vor: ``Map<Chunks<'_, Item>, for<'a> fn(&'a [Item]) -> Spam>``. Dies konnte ich stattdessen ersetzen durch: ``impl Iterator<Item = Spam>``. Letzteres ist natürlich wesentlich lesbarer und leichter zu merken. Im Grunde einfach ein Interface wie ich das in Java auch gemacht hätte, oder ein abstrakter Typ in Python aus ``collections.abc``. Da hatte mich der Rust-Compiler quasi erst auf eine falsche Fährte gelockt, aber das sind wahrscheinlich die typischen Anfängerfehler, die man beim Einstieg in eine neue Sprache macht.