SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

翔泳社 新刊紹介(AD)

ボウリングの点数をコードで計算するには? パズルを解いて使えるアルゴリズムを身につけよう

  • X ポスト
  • このエントリーをはてなブックマークに追加

 コードやアルゴリズムの勉強をするとき、ただテキストを読むだけでは長続きしません。できれば楽しく習得したいという方は、パズルを解いてスキルアップができる『プログラマを育てる脳トレパズル』はいかがでしょうか。今回は本書から2問紹介しますので、ぜひ挑戦してみてください。

  • X ポスト
  • このエントリーをはてなブックマークに追加

本記事は『プログラマを育てる脳トレパズル 遊んでおぼえるPythonプログラミング&アルゴリズム』の「Q01 ボウリングの点数を計算しよう」と「Q11 効率のよいファミリーレストラン」を抜粋したものです。掲載にあたり一部を編集しています。

回答のコードはPythonで記載していますが、本書の読者特典としてRubyとJavaScriptでの回答も提供しています(SHOEISHA iDへの会員登録が必要です)。

書籍本文に誤りがあったため、該当部分「解説:ボウリングの点数を計算しよう」を修正しました(2021年1月4日)。

出題:ボウリングの点数を計算しよう

 東京オリンピックの追加種目の候補に挙がりながら、落選してしまったボウリング。それでも若い人から年配の人まで、幅広く楽しめるゲームとして人気です。ボウリングでは次のようなスコアがつけられます。

ボウリングのスコア

 ご存じの通り、「×」のマークに塗りつぶされているのは「ストライク」、「/」のマークに塗りつぶされているのは「スペア」といいます。ストライクの場合、次の2投分の点数を、スペアの場合は次の1投分の点数を加算できます。また、「G」は「ガーター」、「-」は「ミス(ピンに当たらなかった)」を意味し、いずれも0点です。

 なお、10フレーム目はストライクやスペアがあれば3回投げられますが、それ以外は2回だけ投げられます。10フレーム目では倒れたピンの数だけがカウントされるため、ストライクが3つの場合は30点です。つまり、すべてストライクの場合は次のようになり、最高点は300点です。

ボウリングの最高点

 上記の例の場合、次のような2次元のリスト(配列)で各フレームでの点数が与えられるものとします。

例1:[[6, 4], [8, 0], [10], [2, 7], [5, 5], [3, 4], [10], [9, 1], [1, 2], [7, 1]]
例2:[[1, 8], [9, 1], [7, 2], [10], [0, 0], [9, 1], [3, 6], [8, 0], [5, 4], [10, 8, 1]]
例3:[[10], [10], [10], [10], [10], [10], [10], [10], [10], [10, 10, 10]]

問題

 次のリストが与えられたとき、その点数を求めてください。

[[9, 1], [8, 2], [10], [5, 0], [3, 6], [4, 2], [7, 3], [6, 3], [10], [9, 1, 9]]

考え方

 前のフレームから処理すると、次のフレームの点数がわからないと計算できません。そこで、逆にリストの後ろから計算してみましょう。前のフレームで使うピンの数を変数に入れておくと、簡単な足し算で計算できます。

答えと解説はこちら

出題:効率のよいファミリーレストラン

 客の人数に合わせてテーブルを動かすファミリーレストランを考えます。例えば、1人客や2人組の客に4人掛けのテーブルを使わせると、残りの席がムダになります。そこで、2人掛けテーブルを組み合わせて、できるだけ効率よくテーブルを配置していきます。

 店内にある2人掛けテーブルの数と、店内にいる客の人数がわかっているとき、テーブルの組み合わせ方として考えられるものが何通りあるかを考えます。このとき、どの客がどのテーブルのどこに座っているかは区別せず、テーブルの位置も区別しないものとします。

 つまり、以下のような配置はいずれも同じ(1通り)とします。

テーブルの配置

 なお、相席になることはないものとし、1人客でも2人掛けのテーブルを使い、3人客の場合は2人掛けのテーブルを2つ使います。また、空席のテーブルができないように配置します。

 例えば、テーブルが3つ、客が5人の場合、次の4通りが考えられます。

テーブルの配置例

問題

 テーブルが50個、客が80人の場合、考えられる配置(グループの人数)が何通りあるか求めてください。

考え方

 どの客がどのテーブルのどこに座っているかは区別しないので、配置が決まるのは各グループの人数だけです。つまり、グループの人数を少ない方から順に配置していき、すべての客を配置すれば完了です。2人掛けのテーブルなので、テーブルの数の2倍よりも多くの客が残っていると配置できません。

ヒント

 グループの人数が着席するのに必要なテーブルの数を1つの式で表現することを考えましょう。規則性としては、1人と2人は1個、3人と4人は2個、5人と6人は3個、というように増えていきます。

答えと解説はこちら

解説:ボウリングの点数を計算しよう

答え

 137点

STEP1

 ストライクやスペアのときは、次のフレームで倒したピンの数がないと計算できないため、後ろのフレームから順に処理することを考えます。このとき、前のフレームで計算するために必要なのは、次のフレームで倒したピンの数です。ただし、ストライクが続いた場合は、2つ後のフレームの値も必要になることがあります。

 ここで、ストライクの場合も「次の2つの投球で倒したピンの数がわかればいい」ということに注目します。つまり、用意するのは次の2つの投球で倒したピンの数を保持する変数2つだけです。

Point

 計算に必要なのは現在のフレームで倒したピンの数と、その後の投球で倒したピンの数ですが、その後の投球で倒した数は最大2つ保持すればOKです。

STEP2

 10フレーム目も特殊な処理が必要で、ストライクやスペアにかかわらず、そのフレーム内で倒したピンの合計本数が10フレーム目での得点です。

 その他のフレームでは、ストライクは次の2投球、スペアは次の1投球を加算すると、次のようなプログラムで実装できます。

def calc(score):
    result, next1, next2 = 0, 0, 0
    while len(score) > 0:
        frame = score.pop(-1) # 最後のフレームを取り出し
        total = sum(frame)
        if len(frame) == 3: # 10フレーム目でスペアやストライク
            result += total
            next1, next2, _ = frame 
        elif len(frame) == 1: # ストライクのとき
            result += 10 + next1 + next2
            next1, next2 = 10, next1
        elif total == 10: # スペアのとき
            result += 10 + next1
            next1, next2 = frame
        else:
            result += total
            next1, next2 = frame

    return result
print(calc([
    [9, 1], [8, 2], [10], [5, 0], [3, 6],
    [4, 2], [7, 3], [6, 3], [10], [9, 1, 9]
]))

解説:効率のよいファミリーレストラン

答え

 588,394通り

STEP1

 グループの人数を少ない方から順に配置するため、残っているテーブル数と客の人数に加えて、直前に配置した客の人数を引数とした関数を作成します。

 テーブルに配置する人数(グループの人数)を直前に配置した人数から順に配置してみて、再帰的に探索します。このとき、人数からテーブルの数を求める式を考えます。

 ヒントに書いたように、人数が偶数のときはその人数を2で割って計算できます。奇数のときは人数に1を足して、2で割ると計算できます。そこで、人数に1を足して、2で割った商を使います(偶数のときも商は変わらない)。

STEP2

 残っているテーブル数と客数がちょうど0になれば配置終了ですが、テーブルの数が足りなくなったり、残っている客がいなくなったりすると配置失敗です。

Point

 同じテーブル数、人数が何度も発生するのでメモ化が必要ですが、キャッシュのサイズに注意。テーブルが50、人数が80なので1000くらいでは不足して時間がかかってしまいます。単純計算で4000以上を指定する必要があります。

from functools import lru_cache

@lru_cache(maxsize=5000)
def search(table, n, pre):
    if (table == 0) and (n == 0):
        # テーブル数と客数がともに0になれば終了
        return 1
    if (table <= 0) or (n <= 0) or (table * 2 < n):
        # いずれかが0になったり、テーブルの2倍を超えるとNG
        return 0

    cnt = 0
    for i in range(pre, n + 1):
        # 配置する人数(グループの人数)でチェック
        cnt += search(table - (i + 1) // 2, n - i, i)

    return cnt

# 最初はグループの人数を1人からスタート
print(search(50, 80, 1))
プログラマを育てる脳トレパズル

Amazon SEshop その他


プログラマを育てる脳トレパズル
遊んでおぼえるPythonプログラミング&アルゴリズム

著者:増井敏克
発売日:2020年12月22日(火)
定価:1,800円+税

 

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
翔泳社 新刊紹介連載記事一覧

もっと読む

この記事の著者

増井 敏克(マスイ トシカツ)

増井技術士事務所 代表。技術士(情報工学部門)、テクニカルエンジニア(ネットワーク、情報セキュリティ)、その他情報処理技術者試験に多数合格。 ITエンジニアのための実務スキル評価サービス「CodeIQ」にて、情報セキュリティやアルゴリズムに関する問題を多数出題している。 また、ビジネス数学検定1級に合格し、...

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

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

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

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

【AD】本記事の内容は記事掲載開始時点のものです 企画・制作 株式会社翔泳社

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/13320 2021/01/04 10:35

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング