・0 pv・2 min read
5人の海賊と100枚の金貨を雑に解く
論理クイズ
有名な問題である海賊と金貨
が再帰で簡単に書けそうなので解いてみる
過半数で可決と、過半数では否決の2パターンあるので両方に対応したい
ー 可決するための数を求める関数を少しいじるだけで対応させる
再帰
5人組での最適解は4人組での最適解を見て考え、4人組での最適解は3人組での ... というような線形再帰的な考えが自然だが、「金貨5枚と100人の海賊」のように最初の何人かがどうあがいても否決されてしまう場合に無駄な計算をさせたくなかったので末尾再帰で考えることにした
import Data.List ( sortOn, unfoldr )
import Data.Bifunctor ( Bifunctor(first, bimap) )
import Data.Ord ( Down(Down) )
type Gold = Int
-- ランク1がボス2が次のボス ...
type Rank = Int
type Pirate = (Gold, Rank)
-- 配分を考える
shareStep :: Gold -> [Pirate] -> [Pirate]
shareStep g [] = [(g, 1)]
shareStep g pirates =
(g - golds, 1):(proponents ++ opponents)
where
-- 安い順に並び替え、過半数をとれるように分割
(cheapers, highers) = splitAt (majorityNum (length pirates)) $ sortOn fst pirates
proponents = map (bimap (\x -> if x >= g then x else succ x) succ) cheapers -- +1金貨で買収して位を下げる
opponents = map (\(_, r) -> (0, succ r)) highers -- 金貨没収して位を下げる
golds = sum $ map fst proponents
-- 過半数+1で可決にする
majorityNum :: Int -> Int
majorityNum len = len `div` 2 + len `mod` 2
-- majorityNum len = len `div` 2 こうすれば過半数可決の方になる
-- 末尾再帰で考える
share :: Gold -> Int -> [Pirate] -> [Pirate]
share g n pirates
-- マイナスになったら終わる
| any (\x -> fst x < 0) pirates = share g (n-1) []
-- 基底
| length pirates == n = pirates
| otherwise = share g n (shareStep g pirates)
-- 回答
solve :: Gold -> Int -> [Pirate]
solve g n = sortOn snd $ share g n []
print $ solve 100 5[(97,1),(0,2),(1,3),(0,4),(2,5)]
感想
過半数で可決の方だとただ"0", "1"が交互になるだけだけど、過半数では否決される方だとなかなか面白い規則が見られる
いろいろ変えて動かしてみてね