Skip to content

Instantly share code, notes, and snippets.

@takuma-saito
Created October 17, 2020 15:26
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save takuma-saito/5f9c9adb9968d49acb41d7e7302f2954 to your computer and use it in GitHub Desktop.
Save takuma-saito/5f9c9adb9968d49acb41d7e7302f2954 to your computer and use it in GitHub Desktop.
0 0 2 21 2 23 15 18
4 22 24 17 12 4 11 19
3 3 11 15 5 12 6 8
18 23 6 12 18 24 15 11
9 7 19 18 16 18 14 18
2 17 10 6 5 7 20 7
5 24 5 24 18 0 1 3
24 21 6 8 21 23 18 13
12 7 11 4 22 22 17 6
15 24 2 1 9 8 16 20
11 23 15 9 17 6 24 4
23 21 3 4 8 17 22 17
6 6 22 16 2 5 8 1
11 10 17 2 8 18 14 10
7 11 24 3 13 10 15 7
20 20 3 1 9 7 10 6
2 13 20 9 19 8 16 12
22 15 16 14 14 11 12 5
13 12 3 6 4 12 8 15
4 21 8 18 17 13 5 1
9 14 15 19 15 4 4 2
16 6 16 4 11 16 3 17
3 15 15 3 15 14 8 21
22 19 16 24 0 19 8 22
WIDTH = 8
def each_path(board, visited, i, j)
dead_end = true
[{dx: 1, dy: 0},
{dx: -1, dy: 0},
{dx: 0, dy: -1},
{dx: 0, dy: 1}].each do |direction|
new_j, new_i = direction[:dx]+j, direction[:dy]+i
next if new_j < 0 ||
new_i < 0 ||
new_j >= WIDTH ||
new_i >= WIDTH ||
!visited[(v = board[new_i*WIDTH+new_j])].nil?
dead_end = false
visited[v] = true
each_path(board, visited, new_i, new_j) { |*args| yield(*args) }
visited.delete v
end
yield(visited, i, j, dead_end)
end
def search_longest_path(board)
min_visited, max_visited = [], []
(0...5).each do |i|
(0...5).each do |j|
each_path(board, {}, i, j) do |visited, i, j, dead_end|
max_visited = visited.dup if visited.length > max_visited.length
min_visited = visited.dup if min_visited.empty? || (dead_end && visited.length < min_visited.length)
end
puts "progress: #{i} #{j} #{max_visited.size} #{min_visited.size}"
end
end
[min_visited.keys, max_visited.keys]
end
board = $stdin.read.scan(/\d+/).map(&:to_i)
fail if board.size != 64
min, max = search_longest_path(board)
puts "min: #{min.length} #{min.join(" => ")}"
puts "max: #{max.length} #{max.join(" => ")}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment