Hashable

Part of the Object Oriented Programming section of Coddy's Swift journey. Lesson 40 of 57.

Hashable lets values be stored in a Set or used as Dictionary keys. A hash is a number computed from the value, used to find it quickly. Structs and enums whose properties are all Hashable get it by declaring the conformance:

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

Hashable values make good dictionary keys, for example to count occurrences of structured values:

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 builds on Equatable. When == compares only some properties, the hash must use the same properties, which is done in hash(into:). Otherwise two equal values could get different hashes and a set would keep both:

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:

The rule to remember: values that are equal must have equal hashes. Hash values change between program runs, so never store or print them; use them only through sets and dictionaries.

// equal values -> equal hashes (required)
// different values -> usually different hashes
func hash(into hasher: inout Hasher) {
    hasher.combine(id)          // exactly the properties that == compares
}

Challenge

Easy

A robot on a grid moves U, D, L, R one step at a time from (0, 0). Make Position (x, y) Hashable and complete explore(_:), which returns three lines: visited 5 cells (the number of distinct positions including the start), revisits 2 (moves that landed on an already visited cell) and most visited (0, 0) x3 (the cell entered the most times, counting the start as one visit; the first one to reach that count wins ties).

The supplied code reads one line of moves and prints each returned line.

Your code goes in Position.swift and Functions.swift. main.swift holds the supplied input/output code and cannot be edited.

Try it yourself

// 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) }