RCOの中途採用コーディング試験の過去の出題例1

RCO_pastexam1.hs

module Main where

{-
https://www.rco.recruit.co.jp/career/engineer/entry/pastexam

例題:1 「相手の思考を推理する」過程をプログラムで表現してください。
※こちらは回答例がございません。予めご了承ください。

問題内容
A,B,Cの3人が1〜5の5枚のカードを使ってインディアンポーカーをします。

3人は、ランダムに1枚のカードを引いて額にかざします。 相手のカードは見えますが、自分のカードは見えません。

この状態で、A->B->Cの順番に、自分が1番大きい(MAX)、自分は2番目に大きい(MID)自分が1番小さい(MIN)、わからない(?)、を答えます。

一人でも答えがわかった場合、そこで終了となります。｢わからない｣と答えた場合、回答権が次の人に移ります。 
Cもわからない場合、再度Aに回答権が移ります。3人ともウソを言ったり、適当に答えてはいけません。

例1) ｢A=1 B=4 C=5｣だった場合、｢A => MIN｣で終了します。 
例2) ｢A=1 B=2 C=4｣だった場合、｢A => ?, B => MID｣で終了します。 
Bは｢Aがわからないなら、自分は5ではない｣と考えるからです。


以上を踏まえて、

引数で｢A=1 B=4 C=5｣で実行すると｢A =>MIN｣を出力 
引数で｢A=1 B=2 C=4｣で実行すると｢A =>?, B =>MID｣

を出力するようなコマンドラインのプログラムを作成してください。

なお、人数やカードの枚数がパラメーター化されていて、さまざまなケースがシミュレーションできるコードが望ましいです。

前提
* 制限時間は１時間半
* 今回のケースでは、「全員がわからない（無限ループ）」という結果にはなりません。
-}

import Control.Monad
import Data.Foldable
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
import Data.List
import Data.Map (Map)
import qualified Data.Map as Map
import Data.Monoid
import Data.Ord
import Data.Sequence (Seq, (|>))
import Data.List.Split
import System.Environment 

type Card = Int
type Player = String
type State = Map Player Card

-- | 何番目に小さいか: 0, 1, ..
type Rank = Int

type Answer = Maybe Rank

simulate
  :: IntSet   -- ^ カードの集合
  -> State    -- ^ 実際のカードの割当
  -> [Player] -- ^ ターンのリスト (無限リストでも良い)
  -> [(Player, Answer)]
simulate cards state turns =
  go turns (Map.mapWithKey (\p _ -> initialPossibleCardsForPlayer state p) state) mempty
  where
    go :: [Player]           -- ^ (将来の)ターンのリスト (無限リストでも良い)
       -> Map Player IntSet  -- ^ 各プレイヤーにとってあり得る「自分のカードの集合」
       -> Seq Player         -- ^ 過去のターンで答えられなかったプレイヤーの列
       -> [(Player, Answer)]
    go [] _ _ = []
    go (p : ps) pcs hist =
      case answer p [Map.insert p c state | c <- IntSet.toList (pcs Map.! p)]  of
        Just r -> [(p, Just r)]
        Nothing -> (p, Nothing) : go ps (Map.mapWithKey (filterPossibleCards (hist |> p)) pcs) (hist |> p)
 
    -- ある状態が与えられたときに、プレイヤーにとって可能な自分のカードの集合
    initialPossibleCardsForPlayer :: State -> Player -> IntSet
    initialPossibleCardsForPlayer state p = cards `IntSet.difference` used
      where
        used = IntSet.delete (state Map.! p) $ IntSet.fromList $ Map.elems state

    -- 過去に hist のプレイヤーがこの順で答えられなかったときに p の可能なカード集合 cs を絞り込む
    filterPossibleCards :: Seq Player -> Player -> IntSet -> IntSet
    filterPossibleCards hist p cs = IntSet.filter f cs
      where
        -- 仮に p のカードが c だったと仮定して、これまで回答できなかったという結果と合致しているか
        f c = simulate cards (Map.insert p c state) (toList hist) == [(p, Nothing) | p <- toList hist]

answer :: Player -> [State] -> Answer
answer p ss =
  if IntSet.size ranks == 1 then
    Just (head $ IntSet.toList ranks)
  else
    Nothing
  where
    ranks = IntSet.fromList [rank p s | s <- ss]

rank :: Player -> State -> Rank
rank p s = head [r1 | (r1,(p1,_)) <- zip [0..] (sortBy (comparing snd) (Map.toList s)), p1==p]

sample1, sample2 :: [(Player, Answer)]
sample1 = simulate (IntSet.fromList [1..5]) (Map.fromList [("A",1),("B",4),("C",5)]) (cycle ["A","B","C"])
sample2 = simulate (IntSet.fromList [1..5]) (Map.fromList [("A",1),("B",2),("C",4)]) (cycle ["A","B","C"])

test1, test2 :: Bool
test1 = sample1 == [("A", Just 0)]
test2 = sample2 == [("A", Nothing), ("B", Just 1)]

main :: IO ()
main = do
  args <- getArgs
  let xs = [(name, read val) | arg <- args, let [name,val] = splitOn "=" arg]
      players = map fst xs
      state = Map.fromList xs
      cards = IntSet.fromList [1..5]
      turns = cycle players
  forM_ (simulate cards state turns) $ \(p,ans) -> do
    let s = case ans of
              Nothing -> "?" 
              Just 0 -> "MIN"
              Just 1 -> "MID"
              Just 2 -> "MAX"
              Just _ -> error "should not happen"
    putStrLn $ p ++ "=>" ++ s
    
{-
* 知識論理の基本的な応用だと思うのだけれど、そういう解き方は思いつかず、ナイーブにシミュレータを再帰的に呼び出してしまった。
* 小規模な問題なのでやらなかったけど、メモ化した方が良いかも。
* これCoqやAgdaで満たすべき性質を定義するにはどうしたら良いかな?
-}