トップ «前の日記(02/09) 最新 次の日記(02/12)» 編集

hossy online - といぼっくす

ゲームの感想日記、たまにIT・プログラミングの話


02/11

_ [プログラミング] 5×5のマス目に6個の○を 回転・裏返しありの場合

02/07のエントリで、回転がありの場合はとツッコミを頂きましたもので、もう少し続けてみます。前のエントリのコメントと内容が被っています。

5×5のマス目に6個の○を次の条件を満たすように書きます。

条件:各行・各列に少なくとも1個は○を書く。同じマスには2個以上の○を書くことはできない。

このとき、6個の○を書く方法は全部で何通りありますか。

この問題に条件を付け加えます。

回転あり - 問題

この4通りは回転してみると同じです。これらをあわせて1通りと数えたときに、答えはどうなるでしょう。

●□□●□ □□□□● ●□□□□ □□□□●
□●□□□ □□□●□ □●□□□ ●□□●□
□□●□□ □□●□□ □□●□□ □□●□□
□□□●□ □●□□● □□□●□ □●□□□
□□□□● ●□□□□ □●□□● ●□□□□

回転あり - プログラミングで その1

前回最初に作ったごり押しプログラムに変更を加えました。rubyです。

def g(a)
  b = []
  a.each do |i|
    x, y = yield(i%5, i/5, 4 - i%5, 4 - i/5)  # left, top, right, bottom
    b << y*5 + x
  end
  (a <=> b.sort) <= 0
end
 
def f(a, d, s)
  r = 0
  s.upto(24) do |i|
    a[d] = i
    x = {}
    y = {}
    0.upto(d) do |j|
      x[a[j] / 5] = true
      y[a[j] % 5] = true
    end
    if (x.size >= d) && (y.size >= d)
      if (d == 5)
        next unless g(a){|l, t, r, b| [t, r]}
        next unless g(a){|l, t, r, b| [r, b]}
        next unless g(a){|l, t, r, b| [b, l]}
        r += 1
      else
        r += f(a, d+1, i+1)
      end
    end
  end
  r
end
a = [0]*6
puts f(a, 0, 0)

正解かもしれない配置が見つかったときに、その配置を回転してみた3通りがについて以前に出てきていないかを調べます。left, top, right, bottomをそれぞれから数えて何番目かを示すとき、(left, top) を回転させると (top, right), (right, bottom), (bottom, left)。その回転したものとの大小関係を確かめて、問題なければ g(a) が true を返します。

回転あり - プログラミングで その2

この問題なら、もっと簡単に解く事が出来ます。

90度単位で回転を行うとき、だいたいの配置は4回動かしてはじめて元に戻ります。ですので、前回の答えを4で割ったものがだいたいの答えになります。

だいたいというのは、一部だけ2回動かして元に戻るものがあるためです。点対称。

□□●□□
□●□□□
●□□□●
□□□●□
□□●□□
 
□□●□□
□□□●□
●□□□●
□●□□□
□□●□□

4で割ると割りすぎになります。2回動かすと戻るなら、2で割るのが正しい。そこで、4で割る前にこのようなケースを見つけると2個分と数えておきます。

点対称な配置は、左上から数えるかわりに右下から数えることで簡単に得られます。位置を24から引き算して、反転して、元と同じなら点対称。そうして書き直したものがこちら。

def f(a, d, s)
  r = 0
  s.upto(24) do |i|
    a[d] = i
    x = {}
    y = {}
    0.upto(d) do |j|
      x[a[j] / 5] = true
      y[a[j] % 5] = true
    end
    if (x.size >= d) && (y.size >= d)
      if (d == 5)
        r += 1
        r += 1 if a.reverse.map{|x| 24-x} == a
      else
        r += f(a, d+1, i+1)
      end
    end
  end
  r
end
a = [0]*6
puts f(a, 0, 0) / 4

回転あり - 手で

点対称な場合の数は、全て書き出すことができる程度です。

□□●□□ □★□□□ ★□□□□ □□●□□
□★□□□ □□●□□ □□●□□ ★□□□□
●□□□● ●□□□● □●□●□ □●□●□
□□□★□ □□●□□ □□●□□ □□□□★
□□●□□ □□□★□ □□□□★ □□●□□
 
□□●□□ □□□★□ □□□□★ □□●□□
□□□★□ □□●□□ □□●□□ □□□□★
●□□□● ●□□□● □●□●□ □●□●□
□★□□□ □□●□□ □□●□□ ★□□□□
□□●□□ □★□□□ ★□□□□ □□●□□

●4つで中心軸を通る菱形を作り、残り★2個を配置すると、回転を意識しなかった時の8通り分という事が分かります。ですので正解は「(4200+8)/4 = 1052(反転)となります。

回転・裏返しあり - 問題

更に裏から見た場合も同じと考えます。この8通りが同じと数えたときにはどうなるでしょう。

●□□●□ □□□□● ●□□□□ □□□□●
□●□□□ □□□●□ □●□□□ ●□□●□
□□●□□ □□●□□ □□●□□ □□●□□
□□□●□ □●□□● □□□●□ □●□□□
□□□□● ●□□□□ □●□□● ●□□□□
 
□□□□● ●□□□□ □●□□● ●□□□□
□□□●□ □●□□● □□□●□ □●□□□
□□●□□ □□●□□ □□●□□ □□●□□
□●□□□ □□□●□ □●□□□ ●□□●□
●□□●□ □□□□● ●□□□□ □□□□●

回転あり - プログラミングで

最初のコードに4行追加です。

        next unless g(a){|l, t, r, b| [t, r]}
        next unless g(a){|l, t, r, b| [r, b]}
        next unless g(a){|l, t, r, b| [b, l]}
        next unless g(a){|l, t, r, b| [t, l]}  # 追加
        next unless g(a){|l, t, r, b| [r, t]}  # 追加
        next unless g(a){|l, t, r, b| [b, r]}  # 追加
        next unless g(a){|l, t, r, b| [l, b]}  # 追加

これがしたかったために、最初のコードは長くなっていたのでした。

答えは「561(反転)だそうです。

回転・裏返しあり - 手で?

手で解こうとしました。しかし、場合分けが大変で力尽きました(汗)。どなたか頑張ってください…

本日のツッコミ(全2件) [ツッコミを入れる]
_ すいきょー (02/16 22:45)

よんだー!リクエストに応えてくれてありがとうござました。<br><br>そう、その「+8」とかが詐欺っぽくてつまずいたおぼえがあります…

_ sljhkktqdh (01/29 13:39)

y2UMH6 <a href="http://zrqjinbzowlp.com/">zrqjinbzowlp</a>, [url=http://zlpqdndvndww.com/]zlpqdndvndww[/url], [link=http://cstlgdyognqt.com/]cstlgdyognqt[/link], http://pbykoljzrqen.com/