Hashable

Fa parte della sezione Programmazione orientata agli oggetti del percorso Swift di Coddy. Lezione 40 di 57.

Hashable consente di archiviare i valori in un Set o di usarli come chiavi di un Dictionary. Un hash è un numero calcolato a partire dal valore, usato per trovarlo rapidamente. Le struct e gli enum le cui proprietà sono tutte Hashable ottengono questa funzionalità dichiarandone la conformità:

struct Point: Hashable {
    let x: Int, y: Int
}

var visited: Set<Point> = []
visited.insert(Point(x: 0, y: 0))
visited.insert(Point(x: 1, y: 0))
visited.insert(Point(x: 0, y: 0))
print(visited.count)
print(visited.contains(Point(x: 1, y: 0)))

Output:

2
true

I valori hashable sono ottime chiavi di dizionario, ad esempio per contare le occorrenze di valori strutturati:

struct Pair: Hashable {
    let from: String, to: String
}

let trips = [Pair(from: "A", to: "B"), Pair(from: "B", to: "C"), Pair(from: "A", to: "B")]
var counts: [Pair: Int] = [:]
for t in trips { counts[t, default: 0] += 1 }
print(counts[Pair(from: "A", to: "B")]!)

Output:

Hashable si basa su Equatable. Quando == confronta solo alcune proprietà, l’hash deve usare le stesse proprietà, operazione che viene eseguita in hash(into:). Altrimenti due valori uguali potrebbero avere hash diversi e un set li conserverebbe entrambi:

struct User: Hashable {
    let id: Int
    var name: String

    static func == (lhs: User, rhs: User) -> Bool { lhs.id == rhs.id }
    func hash(into hasher: inout Hasher) { hasher.combine(id) }
}

let users: Set<User> = [User(id: 1, name: "Ada"), User(id: 1, name: "Ada L."), User(id: 2, name: "Bo")]
print(users.count)

Output:

La regola da ricordare: i valori uguali devono avere hash uguali. I valori hash cambiano tra un’esecuzione del programma e l’altra, quindi non memorizzarli né stamparli mai; usali solo tramite set e dizionari.

// valori uguali -> hash uguali (obbligatorio)
// valori diversi -> di solito hash diversi
func hash(into hasher: inout Hasher) {
    hasher.combine(id)          // esattamente le proprietà che == confronta
}

Sfida

Facile

Un robot su una griglia si sposta di un passo alla volta da (0, 0) con U, D, L, R. Rendi Position (x, y) Hashable e completa explore(_:), che restituisce tre righe: visited 5 cells (il numero di posizioni distinte, inclusa quella iniziale), revisits 2 (gli spostamenti che sono terminati su una casella già visitata) e most visited (0, 0) x3 (la casella in cui si è entrati più volte, contando la posizione iniziale come una visita; in caso di parità, vince la prima a raggiungere quel conteggio).

Il codice fornito legge una riga di spostamenti e stampa ogni riga restituita.

Il tuo codice va in Position.swift e Functions.swift. main.swift contiene il codice fornito per input/output e non può essere modificato.

Provalo tu

// Supplied input/output code: keep it as it is
var input: [String] = []
while let line = readLine() { input.append(line) }
for line in explore(input[0]) { print(line) }