Skip to content

Instantly share code, notes, and snippets.

@mizuhara
Created November 9, 2018 13:19
Show Gist options
  • Save mizuhara/b3a8d4451529c31a21c1b2dd412d642b to your computer and use it in GitHub Desktop.
Save mizuhara/b3a8d4451529c31a21c1b2dd412d642b to your computer and use it in GitHub Desktop.
require 'minitest/autorun'
class Room
attr_reader :room_number
def initialize(room_number, x, y, side_length)
@room_number = room_number
@x, @y, @side_length = x, y, side_length
end
def pos
{
lt: [ @x, @y ],
lb: [ @x, @y - @side_length ],
rt: [ @x + @side_length, @y ],
rb: [ @x + @side_length, @y - @side_length ]
}
end
def neighbor?(other)
if room_number == other.room_number
false
else
my_pos, other_pos = pos, other.pos
left, right = [ my_pos, other_pos ].sort_by { |e| e[:lt][0] }
bottom, top = [ my_pos, other_pos ].sort_by { |e| e[:lb][1] }
horizontal_neighbor?(left, right, bottom, top) || vertical_neigbor?(left, right, bottom, top)
end
end
private
def horizontal_neighbor?(left, right, bottom, top)
left[:rt][0] == right[:lt][0] && top[:lb][1] < bottom[:lt][1]
end
def vertical_neigbor?(left, right, bottom, top)
bottom[:lt][1] == top[:lb][1] && right[:lt][0] < left[:rt][0]
end
end
class House
def initialize
@rooms = [ Room.new(1, 0, 0, 1) ]
@minw, @maxw, @minh, @maxh = 0, 1, -1, 0
end
def add(d, n)
next_room_number = @rooms.size + 1
room_numbers = [ *next_room_number...(next_room_number + n) ]
room_numbers.each.with_index do |rn, i|
@rooms << Room.new(rn, *build_space(d, n, i))
end
update(d, n)
end
def neighboring_rooms(room_number)
if room = @rooms[room_number - 1]
@rooms
.select { |r| room.neighbor?(r) }
.map { |r| r.room_number }
.join(?,)
end
end
private
def side_length(d, n)
case d
when ?N, ?S
Rational(@maxw - @minw, n)
when ?E, ?W
Rational(@maxh - @minh, n)
end
end
def build_space(d, n, i)
sl = side_length(d, n)
case d
when ?N
[ @minw + i * sl, @maxh + sl, sl ]
when ?S
[ @minw + i * sl, @minh, sl ]
when ?E
[ @maxw, @maxh - i * sl, sl ]
when ?W
[ @minw - sl, @maxh -i * sl, sl ]
end
end
def update(d, n)
sl = side_length(d, n)
case d
when ?N
@maxh += sl
when ?S
@minh -= sl
when ?E
@maxw += sl
when ?W
@minw -= sl
end
end
end
def solve(src)
str, room_number = src.split(?/)
house = House.new
str.scan(/([NSEW])([0-9])/).each { |d, n| house.add(d, n.to_i) }
house.neighboring_rooms(room_number.to_i)
end
class SolveTest < MiniTest::Test
def test_solve
assert_equal '1,7,12,13,14', solve('N7N4E5/8')
assert_equal '2', solve('E1/1')
assert_equal '1,4,6', solve('N6/5')
assert_equal '1,2,4', solve('W5/3')
assert_equal '2,3,4', solve('S1N2/1')
assert_equal '4,5,10,12', solve('E7E6/11')
assert_equal '4,5,6,9,11', solve('W7W3/10')
assert_equal '1,4,6', solve('N1E4N1/5')
assert_equal '1,7,9', solve('N4E5S8/8')
assert_equal '1,10,16,17', solve('S7E3N6/9')
assert_equal '1,17,24,26', solve('N9E7S9/25')
assert_equal '2,3,6,8', solve('E1N2W2S3/1')
assert_equal '2,3,4,5,8,9,11,12', solve('E2N3W3S4/1')
assert_equal '2,6,8', solve('E4E8S8N8/7')
assert_equal '8,16', solve('W6W7W7E8/15')
assert_equal '1,2,17,18,19,23,24', solve('E2N9E7S5E7/3')
assert_equal '2,15,17,27,28', solve('E2N9E7S5E7/16')
assert_equal '1,2,17,19,25,26,27,28,29', solve('E8S7E2N2N9/20')
assert_equal '1,17,19', solve('N9S9N8W4W5/18')
assert_equal '18,19,24,26', solve('S3E9N8N6S5/25')
assert_equal '1,6,16,23,24', solve('S4N9W6S2N8/15')
assert_equal '1,8,13', solve('W5E3N4S7N7S6/7')
assert_equal '1,2,12,17,19,20,21,22,28,29,30,31', solve('N7S3N4W3N9W9/16')
assert_equal '1,27,28,29,36,37,38,39', solve('S9W8S7E2E4N9/26')
assert_equal '1,20,30,31,32,33,34', solve('W6W2S9E4N9E6/19')
assert_equal '2,3,4,5,6,7,8,10,11,26,27,28,33,34,35,36', solve('W7W1W2W6W7S6N9/9')
assert_equal '2,4,7,32,34', solve('E2E3E4E5E6E7N7/33')
assert_equal '1,32,34,41,42', solve('N8E3W8N8S8S9N5/33')
assert_equal '1,12,17,25,26,27', solve('S4S6W4N3E6N8S7/16')
assert_equal '1,6,13,18,19,20,21,22,23,24,25,30,31,32,33,34', solve('W5N4E3S1N3S8W9/14')
assert_equal '5,6,8,9', solve('N1E1N1E1N1E1N1E1/7')
assert_equal '1,3,4,7,8,9', solve('N1E1W1S1N1E1W1S1/5')
assert_equal '1,5,8,13,17', solve('N2E2W2S2N2E2W2S2/9')
assert_equal '9,14,37', solve('E2S4S1W5N5E8E9W6/36')
assert_equal '1,32,34,45,46', solve('E4S8E5S6E4W9N3W8/33')
assert_equal '8,9,23,26,27', solve('E6W7E7W4N9N3E6N9/22')
assert_equal '1,49,51', solve('E9E7E3S8S3S6W3S6N9/50')
assert_equal '25,26,27,28,29,31,32,33,35,36,37,38,43,44,45,46', solve('N6N6E3W8W5W1W3N9S7/30')
assert_equal '39,48', solve('S9N2E4N5E6S5S6W8W9/47')
assert_equal '1,33,35', solve('N9E7E7E6W8N6N4E1S1E8/34')
assert_equal '1,16,43,48,49,51,54,55,56,57', solve('W6S8E9S5W5S8E5E1N3N8/50')
assert_equal '1,21,30,32,37,38,39', solve('W6W9E5E6S5S8N7W2N6N9/31')
assert_equal '16,17,18,41,43', solve('N6S5N7W7S7W4N6W5S9W3S5/42')
assert_equal '34,35,36,42,50,52,53,54', solve('S9W5N2W9W4E3N8W7N3W7W8/49')
assert_equal '4,5,31,33,46', solve('W5N9E7E4W9E7W6E4S7S2E7/32')
assert_equal '32,33,34,35,36,37,38,39,40,41,52,53,57,58,59,60,61,62,63,64,65', solve('E4W7E4S7E8W9N1E9W1N2W8S5/51')
assert_equal '20,21,25,27,48', solve('N7E6E4S5S6N7N8E2S6N9N5W5/26')
assert_equal '1,50,52,69,70', solve('N9N5N8E7N7N3N8S7N5W5S7E6/51')
assert_equal '24,25,26,37,74,76', solve('N9N5N8E7N7N3N8S7N5W5S7E6/75')
assert_equal '36,42,54,56', solve('N1E1N6W3W6N4N7W2S5N5E1E9S8/55')
assert_equal '48,49,50,76,78,90,91,92,93', solve('S9E8E7N5S7S9E6N9W9W5E3N8E9/77')
assert_equal '77,91,93', solve('S9E8E7N5S7S9E6N9W9W5E3N8E9/92')
assert_equal '21,22,28,30,43', solve('W5N7W4E5E8S9E5E7S7N8E8N9E8/29')
assert_equal '66,68,83,85', solve('W5N7W4E5E8S9E5E7S7N8E8N9E8/67')
assert_equal '38,39,59,61', solve('S7E9W7W5S8S3W4E7W4S9N4N8E8E7/60')
assert_equal '74,75,82,84,95', solve('W6E8E8W8W6N8N9S9W4S9S8N9S2E6/83')
assert_equal '1,21,23,71', solve('E7W4E4S4N4E6W3E7W4W7E5W8E4N5W7/22')
assert_equal '43,55,57,65', solve('W8S9N8S8N3W5E5N9E3N8S6W2S8E9E5/56')
assert_equal '84,85,98,100', solve('N8E3N7W3S7S6E9S8N5S7W8E2N9E6N7E7/99')
assert_equal '57,82,95,97', solve('W3W6S8W9E8N9W6E6N1S4E6S7S7W8S5N8/96')
assert_equal '38,39,51,53,67,68', solve('E6E7N6E9W8E6W7E8W8E5W7W9S6E9S7N5S6/52')
assert_equal '91,96,101', solve('N7N6S2W8S8W5N9S7N6S6W9E3E8W5N4W6N4/95')
assert_equal '2,12,22,24,90', solve('E6W4E4N9S6S8E6E3W5W4E9E6W9S5N7N9E4S4/23')
assert_equal '46,50,52,81,82', solve('W2N4W7E4E1W5W8E6S4E2N2N7E3W8E1E6W9N3/51')
assert_equal '86,87,99,101', solve('S8E9W9E7E8W8E8W4W6W6W9W8E5W9S3S8S4E9/100')
assert_equal '110,111,119,121', solve('W9W5N7E6W8W6W9S1E8S9W6S8S7N9W6S8E3S8/120')
assert_equal '41,42,43,44,59,60,61,62,63,64,76,77,78,79', solve('S1W1N4S8S1S3W3W4E7N7N4S4N1S9N6S6S5E1W8/49')
assert_equal '10,11,12,18,77,79,101,102', solve('S4W4E6N3N6W9N3N5S9N7S8N4W4E7W6S8W2E8S3/78')
assert_equal '86,88,96,105,106', solve('S4W4E6N3N6W9N3N5S9N7S8N4W4E7W6S8W2E8S3/87')
assert_equal '110,111,119,121', solve('W9W5N7E6W8W6W9S1E8S9W6S8S7N9W6S8E3S8E9/120')
assert_equal '72,73,74,75,76,86,92,93,94,95,96,101,102,103,104', solve('E6E2W4W3E2W8E6W5E8S4S6E1W2N5W4S9N9S2S9E8/87')
assert_equal '55,56,57,73,75,81,82', solve('N4W7S3S4W7S5N4N4N9S9E6N7S6S8N9W9N8E9E7S6/74')
assert_equal '74,75,77,82,83,84', solve('N5S4S1W2W1W2W5W6N7W3W8E1S9W9N1W8W1S2W2W6/78')
assert_equal '53,69,86,88', solve('N9S9S3S6N6S7N8W4E9W7E3N5W8S9E9E9W6N3N9N7/87')
assert_equal '73,90,104,124,140,141', solve('N5E5S5W5N6E6S6W6N7E7S7W7N8E8S8W8N9E9S9W9/105')
assert_equal '73,74,78,113,120,122,123,124,131,132,133,134', solve('N9S9S3S6N6S7N8W4E9W7E3N5W8S9E9E9W6N3N9W8/119')
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment