hatebyte
BAN USERSwift solution.
Use sets as hash map to collect horizontal and vertical X groups.
Recursively find and merge sets that intersect.
extension CGPoint:Hashable {
public var hashValue: Int {
return "\(x),\(y)".hashValue
}
}
var sea =
"00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "0000000000000000000X000000000000000"
+ "000000000000000000XXX00000000000000"
+ "000XX00000000000000X000000000000000"
+ "000XXXX0000000000000000000000000000"
+ "0000000X000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "000000000000000000000X0000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
+ "00000000000000000000000000000000000"
func numIslands(sea:String, width:Int, height:Int)->Int {
var hXs:[Set<CGPoint>] = []
var vXs:[Set<CGPoint>] = []
var xset = Set<CGPoint>()
var yset = Set<CGPoint>()
for i in 0..<sea.characters.count {
var y = i / width
var x = i % width
if x == 0 {
xset = Set<CGPoint>()
}
if Array(sea.characters)[i] == "0" {
if let _ = xset.first {
hXs.append(xset)
}
xset = Set<CGPoint>()
} else {
xset.insert(CGPointMake(CGFloat(x), CGFloat(y)))
}
y = i % height
x = (i / height)
let j = (width * y) + x
if j == 0 {
yset = Set<CGPoint>()
}
if Array(sea.characters)[j] == "0" {
if let _ = yset.first {
vXs.append(yset)
}
yset = Set<CGPoint>()
} else {
yset.insert(CGPointMake(CGFloat(x), CGFloat(y)))
}
}
if let _ = xset.first { hXs.append(xset) }
if let _ = yset.first { vXs.append(yset) }
let all = vXs + hXs
return mergeSets(all, results: []).count
}
extension Array {
var decompose:(Element, [Element])? {
return isEmpty ? nil : (self[0], Array(self[1..<count]))
}
}
func mergeSets(sets:[Set<CGPoint>], results:[Set<CGPoint>])->[Set<CGPoint>] {
if sets.count == 0 { return results + sets }
if let (head, tail) = sets.decompose {
var matches:[Set<CGPoint>] = []
var mresults = results
var t = tail
for i in 0..<tail.count {
let s = tail[i]
if head.intersect(s).count > 0 {
matches.append(head.union(s))
t.removeAtIndex(i)
break
}
}
if matches.count == 0 { mresults.append(head) }
return mergeSets(t + matches, results: mresults )
}
return []
}
let i = numIslands(sea, width: 35, height: 18)
print(i) // 4
Swift example
var list = [1,2,3,10,25,26,30,31,32,33]
func printRanges(arr:[Int]) {
let results:[[Int]] = []
let divide = list.reduce(results) { t, i in
var mt = t
if var sl = t.last, l = sl.last {
if l - i == -1 {
sl.append(i)
mt.removeLast()
mt.append(sl)
} else {
mt.append([i])
}
return mt
} else {
mt.append([i])
return mt
}
}
let statement = divide.reduce("") { t, n in
var s = t
if n.count > 1 {
s = t + "\(n[0])-\(n[n.count - 1])"
} else {
s = t + "\(n[0])"
}
guard let l = divide.last where l == n else {
s = s + ", "
return s
}
return s
}
print(statement)
}
printRanges(list)
Repjaynebackus, Applications Developer at Achieve Internet
I am Jayne And I am working as a Record center clerk in a company. Also I'm doing a ...
Swift
nfactorial(5) // 153
// I did read the problem wrong. Need new glasses. Thanks!
- hatebyte August 15, 2016