Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

20個のカラーボックスで作る本棚は何通り?『プログラマ脳を鍛える数学パズル』キャンペーンクイズの解答

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2015/10/28 08:00

 10月20日にCodeZine上で出題した『プログラマ脳を鍛える数学パズル』のキャンペーンクイズ「カラーボックスで作る本棚」の解答を紹介します。独自の回答を応募いただいた皆さん、ありがとうございました。正解した方の中から3名に、本書をプレゼントいたします。

 翔泳社では10月13日(火)に『プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問』を刊行、それを記念してCodeZine上でオリジナル問題を出題しました。

→「プログラミング、楽しめてますか? 『プログラマ脳を鍛える数学パズル』がもらえるクイズキャンペーン開催

 回答を応募いただいた皆さん、お待たせしました。この場で回答を発表いたします。ソースコードは解答例であり、すべての回答についてきちんと精査しますのでご安心ください。

 今回、正解者の中から3名の方に本書をプレゼントします、どうぞお楽しみに。また、正解したのに抽選に外れてしまった方には翔泳社のオンラインショップ「SEshop」で使用できる20%オフクーポンをお送りします。当選の発表・プレゼントの送付については個別にご連絡いたします。

解答とソースコード例:カラーボックスで作る本棚

 まずは問題を振り返っておきましょう。

カラーボックスで作る本棚

 手軽で便利な家具として人気のカラーボックスは、さまざまな種類が販売されています。今回は3段のカラーボックス(縦90cm、横60cm)を複数組み合わせて本棚を作ることを考えます(カラーボックスは横に倒すことで、雑誌など大きな本も入れられるようになります)。

 上下左右に並べて配置して、見た目がスッキリするように「全体として長方形」になるようにします。例えば、5個のカラーボックスを使うと、下記左図のような8パターンが考えられます(下記右図のような配置は「全体として長方形」になっていないのでNGです)。

 上記の条件において、20個のカラーボックスを使った場合、その配置が何パターンあるかを求めてください。

※個々のカラーボックスは区別せず、配置のパターン数のみを考えてください。また、置く場所には充分な広さと高さがあるものとします。

カラーボックスで作る本棚
OKな例、NGな例

解答

 答えは610通りです。

 すべて並べ終わったときの配置が「全体として長方形」になる必要がありますので、最初に全体の長方形の形を決めてしまいます。長方形の形が決まると、その中にカラーボックスを配置していきます。左上から右下に向けて、縦か横のカラーボックスを配置していき、置けなくなると探索終了です。

 カラーボックスの数が固定なので、長方形の面積は自動的に決まります。このため、長方形の縦の長さを決めると、横の長さも決まります。あとはカラーボックスを配置したかどうかを記録すれば探索できます。カラーボックスは90cm×60cmなので、3×2のサイズだと考えることができます。

 下のソースコードでは、1次元の配列(box)でカラーボックスを配置した位置を表現しています(配置した位置に「1」をセット、まだ配置していない位置に「0」をセット)。

 この配列に対して、「縦に置いた場合(2×3)、横に置いた場合(3×2)の位置に「1」をセットして、次の位置に置けるかを調べる」ということを繰り返します。Rubyでは、以下のように書くことができます。

ソースコード:カラーボックスで作る本棚
# カラーボックスの個数
N = 20
# 長方形の面積
S = N * 2 * 3

# 設定できる高さを配列にセット
height = (2..(S-1)).to_a.select{|i| (S / i) * i == S}

def bookshelf(box, w, h, x, y)
  if x >= w then
    # 一行を埋めた場合、次の行に移動
    return bookshelf(box, w, h, 0, y + 1)
  end
  if y >= h then
    # すべて埋まっていた場合1、空きがあった場合0を返す
    return box.count(0) == 0 ? 1 : 0
  end
  cnt = 0
  if box[x + y * w] == 0 then  # 現在の位置が空いている場合
    # 縦に配置
    if (x + 2 <= w) && (y + 3 <= h) then
      if (box[x + y * w, 2] == [0, 0]) && 
         (box[x + (y + 1) * w, 2] == [0, 0]) &&
         (box[x + (y + 2) * w, 2] == [0, 0]) then
        3.times{|hh| 2.times{|ww| box[x + ww + (y + hh) * w] = 1}}
        cnt += bookshelf(box, w, h, x + 2, y)
        3.times{|hh| 2.times{|ww| box[x + ww + (y + hh) * w] = 0}}
      end
    end
    # 横に配置
    if (x + 3 <= w) && (y + 2 <= h) then
      if (box[x + y * w, 3] == [0, 0, 0]) &&
         (box[x + (y + 1) * w, 3] == [0, 0, 0]) then
        2.times{|hh| 3.times{|ww| box[x + ww + (y + hh) * w] = 1}}
        cnt += bookshelf(box, w, h, x + 3, y)
        2.times{|hh| 3.times{|ww| box[x + ww + (y + hh) * w] = 0}}
      end
    end
  else  # 現在の位置が埋まっている場合、次の位置に移動
    cnt += bookshelf(box, w, h, x + 1, y)
  end
  cnt
end

cnt = 0
height.each{|h|
  # 高さから幅を決定
  w = S / h
  # 初期状態から探索開始
  cnt += bookshelf([0] * w * h, w, h, 0, 0)
}
puts cnt

 パズルを解くときに、左上から右下に探索する手法はいろいろ考えられます。シンプルに実装するために有効な再帰の使い方だけでなく、境界の判定などさまざまな方法が書籍の中で登場しますので、ぜひ読んでみてください。

プログラマ脳を鍛える数学パズル

 Amazon  SEshop  その他

プログラマ脳を鍛える数学パズル
シンプルで高速なコードが書けるようになる70問

著者:増井敏克
出版社:翔泳社
発売日:2015年10月13日(火)
定価:2,580円(税別)

目次

  • 第1章 入門編 ★ プログラムを作って問題を解いてみよう
  • 第2章 初級編 ★★ アルゴリズムの効果を実感しよう
  • 第3章 中級編 ★★★ 工夫して高速な処理を実現しよう
  • 第4章 上級編 ★★★★ 視点を変えて高速化を目指してみよう

 



  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • 渡部 拓也(ワタナベ タクヤ)

     翔泳社マーケティング広報課。MarkeZine、CodeZine、EnterpriseZine、Biz/Zine、ほかにて翔泳社の本の紹介記事や著者インタビュー、たまにそれ以外も執筆しています。 Twitter@tiktakbeam

バックナンバー

連載:翔泳社 新刊紹介

もっと読む

All contents copyright © 2005-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5