Längste Serie

Teil des Abschnitts Logik & Kontrollfluss der Swift-Journey von Coddy — Lektion 35 von 56.

Ein Streak ist eine Folge von aufeinanderfolgenden Tagen, an denen eine Gewohnheit als erledigt markiert wurde. Für die Tage [1, 2, 3, 5, 6] ist der längste Streak 3 (Tage 1-3).

Sobald Sie eine sortierte Liste von Tagen haben, ist die Berechnung ein einfacher linearer Scan: Vergleichen Sie jeden Tag mit dem vorherigen, verlängern Sie die aktuelle Folge, wenn sie aufeinanderfolgend sind, andernfalls setzen Sie sie zurück.

func longestStreak(_ days: [Int]) -> Int {
    let sorted = days.sorted()
    var best = 0
    var run = 0
    var prev: Int? = nil
    for d in sorted {
        if let p = prev, d == p + 1 {
            run += 1
        } else {
            run = 1
        }
        if run > best { best = run }
        prev = d
    }
    return best
}

Das Muster, „aktuelle Sequenz verfolgen + bisheriger Bestwert“, tritt in vielen Problemen immer wieder auf. Erkenne es einmal und es gehört dir für immer.

Aufgabe

Mittel

Lies eine einzelne Eingabezeile ein: eine durch Kommas getrennte Liste von habit:day-Einträgen. Erstelle dasselbe Dictionary wie in der vorherigen Lektion und berechne dann für jede Gewohnheit die längste Serie aufeinanderfolgender Tage über die Woche hinweg.

Gib die Gewohnheiten in alphabetischer Reihenfolge aus, eine pro Zeile, im Format:

<habit>: streak=<n>

Für die Eingabe read:1,read:2,read:3,read:5,workout:2,workout:4 lautet die Ausgabe:

read: streak=3
workout: streak=1

Spickzettel

Längste Serie – linearer Scan, der den aktuellen Durchlauf und den bisherigen Bestwert verfolgt:

func longestStreak(_ days: [Int]) -> Int {
    let sorted = days.sorted()
    var best = 0, run = 0
    var prev: Int? = nil
    for d in sorted {
        if let p = prev, d == p + 1 { run += 1 } else { run = 1 }
        if run > best { best = run }
        prev = d
    }
    return best
}

Tage sind aufeinanderfolgend, wenn jeder dem vorherigen plus eins entspricht. Setzen Sie run bei einer Lücke auf 1 zurück; aktualisieren Sie best bei jeder Iteration.

Probier es selbst

var habits: [String: [Int]] = [:]
let ops = readLine()!.components(separatedBy: ",")
for op in ops {
    let parts = op.components(separatedBy: ":")
    let day = Int(parts[1])!
    if !(habits[parts[0], default: []].contains(day)) {
        habits[parts[0], default: []].append(day)
    }
}

// TODO: Längste Serie pro Gewohnheit, sortiert nach Name ausgeben als 'name: streak=n'