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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
#!/usr/bin/env ruby
class KnotHash
def initialize(text)
@list = (0...256).to_a
@skip = 0
@ptr = 0
@input = text.chars.map(&:ord) + [17,31,73,47,23]
end
def run(rounds = 64)
rounds.times do
@input.each do |len|
reverse_sublist!(len)
end
end
return self
end
def compress
p = 0
out = []
16.times do
out << @list[p...p+16].inject(:^)
p += 16
end
return out
end
def hexdigest
dense = self.compress
hex = dense.map { |i| "%02x" % i }
return hex.join
end
def bindigest
dense = self.compress
hex = dense.map { |i| "%08b" % i }
return hex.join
end
def to_a
return @list
end
def to_s
l = @list.dup
l[@ptr] = "[#{l[@ptr]}]"
return "#{l.join(' ')} skip = #{@skip}"
end
private
def reverse_sublist!(len)
if @ptr + len > @list.length then
reverse_wrapping_sublist!(len)
else
reverse_contained_sublist!(len)
end
inc_ptr!(len)
end
def reverse_wrapping_sublist!(len)
dbl = @list.dup + @list.dup
sublist = dbl[@ptr...@ptr+len].reverse
(@ptr...@ptr+len).each do |i|
@list[i % @list.length] = sublist[i-@ptr]
end
end
def reverse_contained_sublist!(len)
sublist = @list[@ptr...@ptr+len].reverse
(@ptr...@ptr+len).each do |i|
@list[i] = sublist[i-@ptr]
end
end
def inc_ptr!(len)
@ptr += len
@ptr += @skip
@ptr = @ptr % @list.length
@skip += 1
end
end
input = gets.chomp
grid = []
(0..127).each do |r|
hash = KnotHash.new("#{input}-#{r}").run
grid << hash.bindigest.chars.map{|c|c == '1'}
end
def find_first_used(grid)
(0..127).each do |r|
(0..127).each do |c|
return [r,c] if grid[r][c]
end
end
return nil
end
def mark_off_region(grid, start)
coords = [start]
loop do
break if coords.empty?
row, col = coords.shift
next unless grid[row][col]
grid[row][col] = false
coords << [row-1, col] if row > 0
coords << [row+1, col] if row < 127
coords << [row, col-1] if col > 0
coords << [row, col+1] if col < 127
end
end
regions = 0
loop do
f = find_first_used(grid)
break if f.nil?
regions += 1
mark_off_region(grid, f)
end
puts regions
|
