pattern.rb

#encoding: Windows-31J
#  3行5列のマスを塗っていくパターンは
#  ある列がそれより左の列の1行目が塗られている場合のみ塗れるので、
#  ・1列目だけ塗るパターン
#  ■
#  □
#  □
#  
#  ・２列めまで塗るパターン
#  ■■
#  □□
#  □□
#  
#  ...
#  
#  ・５列目まで塗るパターン
#  ■■■■■
#  □□□□□
#  □□□□□
#  
#  の５パターンある。
#
#
#  また、各列を塗るパターンは「何行目まで塗るか？」なので、
#  ■
#  □
#  □
#  
#  ■
#  ■
#  □
#  
#  ■
#  ■
#  ■
#  の３通りある。
#  すると、最初の５パターンそれぞれについて
#  　(1列を塗るパターン) ^ (使用する列数)
#   = 3                  ^  (使用する列数)
#  が各パターン毎の塗り方になるので、
#  ・１列目だけ・・・3^1 = 3
#  ・２列目まで・・・3^2 = 9
#  ・３列目まで・・・3^3 = 27
#  ・４列目まで・・・3^4 = 81
#  ・５列目まで・・・3^5 = 243
#  となって、全体のパターン数はこれらの和になるので、
#  初項3、公比3の等比数列の和がパターン数になる。
#  よって、
#  　パターン数 = (初項 * (1 - 公比^5))/(1 - 公比)
#               = (3 * (1 - 3^5))/(1 - 3)
#               = 363通り
#  になる。
#  
#  一般化すると、n行m列の場合
#  　パターン数 = (n * (1 - n^m)) / (1 - n)
#  になる。


#プログラム上の各列のパターン
# 最左列は0以外のパターン
# それ移行の列は左の列が0じゃないときのみ1,2,3
# 0のときは0のみ
# 
# 0    1    2    3
#□   ■   ■   ■
#□   □   ■   ■
#□   □   □   ■

ROW = 3
COL = 5

def each_pattern(cols)
  if cols.size == COL
    yield cols
  else
    if cols.size == 0 #最左列目はゼロ個はなし
      (1 .. ROW).each do |pattern|
        each_pattern(cols.dup << pattern) do |result|
          yield result if result
        end
      end
    else
      (0 .. ROW).each do |pattern|
        if pattern == 0 or cols.last > 0
          each_pattern(cols.dup << pattern) do |result|
            yield result if result
          end
        end
      end
    end
  end
end

def num_to_col(num)
  cols = Array.new(ROW, '□')
  (0 ... num).each do |i|
    cols[i] = '■'
  end
  cols
end

def pattern_to_s(pattern)
  pattern.map {|num|
    num_to_col(num)
  }.transpose.map(&:join).join("\n")
end

results = []
each_pattern([]) do |result|
  results << result
end
puts "総パターン数:#{results.size}"
group_by_painted_count = results.inject(Hash.new) do |acc, r|
  acc[r.inject(&:+)] ||= []
  acc[r.inject(&:+)] << r
  acc
end

group_by_painted_count.keys.each do |count|
  patterns = group_by_painted_count[count]
  puts "#{count}個塗る(#{patterns.size}パターン)-------------------------------------------"
  patterns.each do |pattern|
    puts "pattern:#{pattern.join(' ')}"
    puts pattern_to_s(pattern)
    puts ""
  end
end