Daily Coding Day Two Eighty Three

, ,

This problem was asked by Google.

A regular number in mathematics is defined as one which evenly divides some power of 60. Equivalently, we can say that a regular number is one whose only prime divisors are 2, 3, and 5.

These numbers have had many applications, from helping ancient Babylonians keep time to tuning instruments according to the diatonic scale.

Given an integer N, write a program that returns, in order, the first N regular numbers.

I definitely did not get this one on my first go. After a few cracks I came up with this passable solution in swift. I didn’t think about a heap- so I guess I kind of suck?
After a bit of Googling (ironic) I was there. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import Foundation

func generateRegularNumbers(_ n: Int) -> [Int] {
    let factors = [2, 3, 5]
    var result: [Int] = []
    var heap = Set<Int>()
    var minHeap = Heap<Int>(sort: <)
    
    minHeap.insert(1)
    heap.insert(1)
    
    while result.count < n {
        let smallest = minHeap.remove()!
        result.append(smallest)
        
        for factor in factors {
            let next = smallest * factor
            if !heap.contains(next) {
                heap.insert(next)
                minHeap.insert(next)
            }
        }
    }
    
    return result
}

// Harken back to College Days Heap Implementation
struct Heap<T> {
    var elements: [T] = []
    let sort: (T, T) -> Bool
    
    init(sort: @escaping (T, T) -> Bool) {
        self.sort = sort
    }
    
    var isEmpty: Bool { elements.isEmpty }
    
    // Teenage Mutating Ninja Swift Funcs
    mutating func insert(_ value: T) {
        elements.append(value)
        siftUp(from: elements.count - 1)
    }
    
    // Teenage Mutating Ninja Swift Funcs
    mutating func remove() -> T? {
        guard !elements.isEmpty else { return nil }
        elements.swapAt(0, elements.count - 1)
        let value = elements.removeLast()
        siftDown(from: 0)
        return value
    }
    
    // Recluse Teenage Mutating Ninja Swift Funcs
    private mutating func siftUp(from index: Int) {
        var child = index
        var parent = (child - 1) / 2
        while child > 0 && sort(elements[child], elements[parent]) {
            elements.swapAt(child, parent)
            child = parent
            parent = (child - 1) / 2
        }
    }
    
    private mutating func siftDown(from index: Int) {
        var parent = index
        while true {
            let left = 2 * parent + 1
            let right = 2 * parent + 2
            var candidate = parent
            
            if left < elements.count && sort(elements[left], elements[candidate]) {
                candidate = left
            }
            if right < elements.count && sort(elements[right], elements[candidate]) {
                candidate = right
            }
            if candidate == parent { return }
            
            elements.swapAt(parent, candidate)
            parent = candidate
        }
    }
}

// Example Usage:
print(generateRegularNumbers(15))