与えられた並べ替えを実現するあみだくじの生成
Posted feedbacks - Ruby
お題の例と同じ出力になります。 高さは極小にはなりますが、最小とは限らない気がします。
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 | def ins(pos, amida, n)
idx = amida.size
amida.reverse_each do |row|
break if row[pos,1] == '-' ||
pos-2 > 0 && row[pos-2,1] == '-' ||
pos+2 < row.size && row[pos+2,1] == '-'
idx -= 1
end
if idx == amida.size
amida.push(Array.new(n, '|').join(' '))
end
amida[idx][pos] = '-'
end
def make_amida(goal)
n = goal.size
amida = []
cur = Array.new(n) {|i| i}
puts cur.join(' ')
for i in 0...n
j = cur.index(goal[i])
while j > i
cur[j], cur[j-1] = cur[j-1], cur[j]
ins(2*j-1, amida, n)
j -= 1
end
end
puts amida
puts goal.join(' ')
end
make_amida [3, 5, 2, 4, 0, 1]
|
shiro
#4704()
Rating13/13=1.00
お題#4476を見て思いつきました。
0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。
与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：
一応、制約条件を示しておきます。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
[ reply ]