どう書く

オフラインリアルタイムどう書くE19の回答

More than 1 year has passed since last update.

1時間ほど。
再帰で、残りのカードから次の候補を選んでいます。

e19.rb
def solve_impl( back, index, remain, candidate )
  return [ candidate, ] if index >= back.length
  m = back[index]
  prev = ((index % (back.length/2)) == 0) ? 0 : candidate[index-1]
  ret = []
  remain[m].select { |k, v| k >= prev and v > 0 }.keys.each { |num|
    remain[m][num] -= 1
    ret += solve_impl( back, index+1, remain, candidate + [num] )
    remain[m][num] += 1
  }
  ret
end

def solve( input )
  back = input.gsub(',', '')
  remain = (1..(back.length/2)).each_with_object(Hash.new{|h,k| h[k]={}}) { |i, h |
    mark = i.odd? ? 'o' : 'x'
    h[mark][i] = 2
  }
  solve_impl( back, 0, remain, [] ).map { |l| l.join(',') }.join('|')
end

def test( id, input, expected )
  actual = solve( input )
  if expected != actual
    puts '[%s] NG: input = %s, expected = %s, actual = %s' % [ id, input, expected, actual, ]
    exit 1
  else
    puts '[%s] OK' % [ id, ]
  end
end

test( 0, "xxoxo,oooxo", "2,2,3,4,5,1,1,3,4,5")
test( 1, "ooxxo,ooxxo", "1,1,2,2,5,3,3,4,4,5|3,3,4,4,5,1,1,2,2,5")
test( 2, "oxoxo,oxoxo", "1,2,3,4,5,1,2,3,4,5")
test( 3, "ooxoxx,oxxoxo", "1,3,4,5,6,6,1,2,2,3,4,5")
test( 4, "ooxxxx,ooxxoo", "1,1,2,2,6,6,3,3,4,4,5,5|3,3,4,4,6,6,1,1,2,2,5,5")
test( 5, "oxoxox,oxoxox", "1,2,3,4,5,6,1,2,3,4,5,6")
test( 6, "oxoxxxo,oxoxooo", "1,2,3,4,6,6,7,1,2,3,4,5,5,7")
test( 7, "oxooxxx,oxxoooo", "1,2,3,3,4,6,6,1,2,4,5,5,7,7")
test( 8, "oxoxxxo,oxoooxo", "1,2,3,4,4,6,7,1,2,3,5,5,6,7")
test( 9, "oxoxooox,oxoxoxxx", "1,2,3,4,5,7,7,8,1,2,3,4,5,6,6,8")
test( 10, "ooxoxxox,ooxxxoox", "3,3,4,5,6,6,7,8,1,1,2,2,4,5,7,8")
test( 11, "oxoxxxxx,oxoxoooo", "1,2,3,4,6,6,8,8,1,2,3,4,5,5,7,7")
test( 12, "oxoxooxxo,oxooxxoxo", "1,2,5,6,7,7,8,8,9,1,2,3,3,4,4,5,6,9")
test( 13, "oxoooooxo,oxxxoxxxo", "1,2,3,3,5,7,7,8,9,1,2,4,4,5,6,6,8,9")
test( 14, "oxoxoxxox,oxoxooxoo", "1,2,3,4,5,6,6,7,8,1,2,3,4,5,7,8,9,9")
test( 15, "oooxxxxoxo,xxooooxoxx", "1,1,3,4,4,6,6,7,8,9,2,2,3,5,5,7,8,9,10,10")
test( 16, "ooooxxxoxx,xxooxxxooo", "1,1,5,5,6,8,8,9,10,10,2,2,3,3,4,4,6,7,7,9")
test( 17, "xoxxoxxoxo,ooxoooxoxx", "2,3,4,4,5,6,6,7,8,9,1,1,2,3,5,7,8,9,10,10")
test( 18, "oxooxxoooxo,oxxxoxooxxo", "1,2,3,3,4,4,5,5,7,8,11,1,2,6,6,7,8,9,9,10,10,11")
test( 19, "oooxxxxoxoo,xxooooxooxx", "1,1,3,4,4,6,6,7,8,11,11,2,2,3,5,5,7,8,9,9,10,10")
test( 20, "ooooxxoxoxo,oxxxxooxoxo", "1,3,3,5,6,6,7,8,9,10,11,1,2,2,4,4,5,7,8,9,10,11")
test( 21, "ooooxoxooxox,xxoxxoxoxxox", "1,1,3,5,6,7,8,9,9,10,11,12,2,2,3,4,4,5,6,7,8,10,11,12")
test( 22, "ooxxoooooxox,ooxxoxxxxxox", "1,1,2,2,5,7,7,9,9,10,11,12,3,3,4,4,5,6,6,8,8,10,11,12|3,3,4,4,5,7,7,9,9,10,11,12,1,1,2,2,5,6,6,8,8,10,11,12")
test( 23, "xoxoxxooxoxx,ooxoxoxooxxo", "2,3,4,5,6,6,7,7,8,11,12,12,1,1,2,3,4,5,8,9,9,10,10,11|2,3,4,5,6,8,9,9,10,11,12,12,1,1,2,3,4,5,6,7,7,8,10,11")
test( 24, "oooooooooooo,xxxxxxxxxxxx", "1,1,3,3,5,5,7,7,9,9,11,11,2,2,4,4,6,6,8,8,10,10,12,12")

他の方の回答を見て、
片面決まれば残りは一通りしかないことに気づいて修正したバージョン。
テストは省略。

e19_2.rb
def solve_impl( back, index, remain, candidate )
  if index >= back[0].length
    r = remain.values.flat_map { |h| h.flat_map { |k, v| [k] * v } }.sort
    return [] if back[1] != r.map{ |i| i.odd? ? 'o' : 'x' }.join
    return [ (candidate + r).join(','), ]
  end
  m = back[0][index]
  prev = (index == 0) ? 0 : candidate[index-1]
  ret = []
  remain[m].select { |k, v| k >= prev and v > 0 }.keys.each { |num|
    remain[m][num] -= 1
    ret += solve_impl( back, index+1, remain, candidate + [num] )
    remain[m][num] += 1
  }
  ret
end

def solve( input )
  back = input.split(',')
  remain = (1..(back[0].length)).each_with_object(Hash.new{|h,k| h[k]={}}) { |i, h |
    mark = i.odd? ? 'o' : 'x'
    h[mark][i] = 2
  }
  solve_impl( back, 0, remain, [] ).join('|')
end