Skip to content

Instantly share code, notes, and snippets.

@makenowjust
Created March 26, 2019 13:50
Show Gist options
  • Save makenowjust/bd167bf3e27d7c5fa6348360f679d02c to your computer and use it in GitHub Desktop.
Save makenowjust/bd167bf3e27d7c5fa6348360f679d02c to your computer and use it in GitHub Desktop.
def solve
hs = [
[5, 3, 1, 2, 4],
[2, 5, 1, 4, 3],
[0, 0, 0, 0, 0],
]
queue = [[]]
checks = {}
checks[hs.map{|h| h.join(',')}.join('|')] = true
ps_size = nil
count = 0
until queue.empty?
ps = queue.shift
hs1 = hs.map(&:dup)
ps.each do |(a1, a2, b1, b2)|
hs1[a1][a2], hs1[b1][b2] = hs1[b1][b2], hs1[a1][a2]
end
if hs1.select { |h| h == [5, 4, 3, 2, 1] }.size == 2
p ps
break
end
# 28手まで
next if ps.size == 28
if ps_size != ps.size
p [ps.size, count]
count = 0
end
ps_size = ps.size
count += 1
ns = hs1.map { |h| h.index(0) }
hs1.each_with_index do |h, i|
n = ns[i]
next unless n
a1, a2 = i, n
[1, 2].each do |d|
j = (i + d) % hs.size
m = ns[j]&.pred || 4
b1, b2 = j, m
hs1[a1][a2], hs1[b1][b2] = hs1[b1][b2], hs1[a1][a2]
error = hs1.each_with_index.map do |h, k|
e = ns[k]&.pred || 4
h.each_with_index.map { |x, f| f > e || (5 - f) == x ? 0 : e - f }.sum
end.sum
key = hs1.map{|h| h.join(',')}.join('|')
unless checks[key] || ps.size + error > 28
queue.push(ps + [[a1, a2, b1, b2]])
end
checks[key] = true
hs1[a1][a2], hs1[b1][b2] = hs1[b1][b2], hs1[a1][a2]
end
end
end
end
solve
BOARD = []
6.times do |i|
BOARD[i] = []
6.times do |j|
BOARD[i][j] = 0
end
end
WANT = [[1, 1, 1, 3, 3, 3],
[1, 0, 0, 0, 0, 3],
[6, 6, 0, 0, 7, 7],
[5, 6, 0, 0, 7, 2],
[5, 0, 0, 0, 0, 2],
[5, 4, 4, 4, 2, 2]]
DIFF = [[0, 1],
[1, 0],
[0, -1],
[-1, 0]]
def solve
qs = [
{
pos: [0, 0],
pat: [[1, 1, 1],
[1, 0, 0]],
},
{
pos: [4, 0],
pat: [[0, 2],
[0, 2],
[2, 2]],
},
{
pos: [1, 1],
pat: [[3, 3, 3],
[0, 0, 3]],
},
{
pos: [0, 2],
pat: [[4, 4, 4]],
},
{
pos: [0, 3],
pat: [[5],
[5],
[5]],
},
{
pos: [1, 3],
pat: [[6, 6],
[0, 6]],
},
{
pos: [4, 3],
pat: [[7, 7],
[7, 0]],
},
]
board = BOARD.map(&:dup)
checks = {}
qs.each do |q|
qx, qy = q[:pos]
q[:pat].each_with_index do |t, py|
t.each_with_index do |n, px|
board[qy + py][qx + px] = n
end
end
end
key = board.map { |line| line.join(',') }.join('|')
checks[key] = true
queue = [[qs, []]]
ans_size = nil
until queue.empty?
qs, ans = queue.shift
board = BOARD.map(&:dup)
qs.each do |q|
qx, qy = q[:pos]
q[:pat].each_with_index do |t, py|
t.each_with_index do |n, px|
board[qy + py][qx + px] = n unless n.zero?
end
end
end
if board == WANT
pp ans
break
end
unless ans_size == ans.size
ans_size = ans.size
pp ans_size
end
qs.each_with_index do |q, k|
qx, qy = q[:pos]
pat = q[:pat]
sx, sy = pat[0].size, pat.size
pat.each_with_index do |t, py|
t.each_with_index do |n, px|
board[qy + py][qx + px] = 0 unless n.zero?
end
end
DIFF.each do |(dx, dy)|
bx, by = qx + dx, qy + dy
# p [k, [dx, dy], [bx, by]]
if bx < 0 || by < 0 || bx + sx > board[0].size || by + sy > board.size
# p ['範囲外']
next
end
can_place = true
pat.each_with_index do |t, py|
break unless can_place
t.each_with_index do |n, px|
m = board.dig by + py, bx + px
next if n.zero?
next if m.zero?
# p ['既にある', [bx, + px, by + py], n, m]
can_place = false
break
end
end
next unless can_place
pat.each_with_index do |t, py|
t.each_with_index do |n, px|
board[by + py][bx + px] = n unless n.zero?
end
end
key = board.map { |line| line.join(',') }.join('|')
unless checks[key]
checks[key] = true
new_qs = qs.dup
new_q = q.dup
new_q[:pos] = [bx, by]
new_qs[k] = new_q
queue.push [new_qs, ans + [[k + 1, [dx, dy]]]]
else
# p ['探索済']
end
pat.each_with_index do |t, py|
t.each_with_index do |n, px|
board[by + py][bx + px] = 0 unless n.zero?
end
end
end
pat.each_with_index do |t, py|
t.each_with_index do |n, px|
board[qy + py][qx + px] = n unless n.zero?
end
end
end
end
end
solve
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment