読者です 読者をやめる 読者になる 読者になる

雀巽の日記帳

雀巽が綴る日常の記録

paiza learning を Haskell で解くよ!

Haskell で解くよ!Ruby でも解いたよ!!

paiza learning

パイザ・ラーニング は、オンラインでプログラミングしながら スキルアップできるプログラミング入門学習コンテンツです。 1本3分の動画レッスンと練習問題 で、効率よく学べます。

パイザ・ラーニング(プログラミング学習)

問題

長テーブルのうなぎ屋 (paizaランク B 相当)を解いてみました!

「うなぎ屋さんに来た人たちがある条件で椅子に座ったり、座らずに帰ったりします。最終的に何人座っていますか?」という問題です。

Haskell で解く!

こんな感じで書きました。

import Control.Applicative
import Control.Monad

type SeatCondition = (Int,Bool)

getLineInts :: IO [Int]
getLineInts = map (read :: String -> Int) . words <$> getLine

getLinesInts :: Int -> IO [[Int]]
getLinesInts n = replicateM n getLineInts

newSeatsCondition :: [SeatCondition] -> [Int] -> [SeatCondition]
newSeatsCondition seatsCondition group_info
  | or . map snd $ filter (\(i,_) -> i `elem` indexes) seatsCondition = seatsCondition
  | otherwise = map (\condition@(i,b) -> if i `elem` indexes then (i,True) else condition) seatsCondition
  where people_count = group_info !! 0
        position = group_info !! 1 - 1
        indexes = map (flip mod $ length seatsCondition) $ take people_count [position..]

lastSeatsCondition :: [SeatCondition] -> [[Int]] -> [SeatCondition]
lastSeatsCondition seatsCondition [] = seatsCondition
lastSeatsCondition seatsCondition (x:xs) = lastSeatsCondition (newSeatsCondition seatsCondition x) xs

main :: IO ()
main = do
  info <- getLineInts
  let capacity = info !! 0
  let group_count = info !! 1

  groups_info <- getLinesInts group_count
  let seatsCondition = take capacity $ zip [0..] $ repeat False
  print $ length . filter(\(_,b) -> b) $ lastSeatsCondition seatsCondition groups_info

ほぼ初めてのまともな Haskell プログラミングだったので、 Haskell っぽく書けているのか、関数型っぽく書けているのか、とても自信がないです(゚ー゚;A

Ruby でも解いた!

Ruby でも解いたというか、実は先に Ruby で解きました(ノ∀`)

capacity, group_count = gets.chomp.split("\s").map(&:to_i)
conditions = Array.new(capacity, false)

group_count.times do
  people_count, position = gets.chomp.split("\s").map(&:to_i)
  first = position - 1
  last = position + people_count - 2
  targets = (first..last).map { |i| i % capacity }

  unless targets.map { |target| conditions[target] }.reduce { |acc, b| acc || b }
    targets.each { |target| conditions[target] = true }
  end
end

puts conditions.reduce (0) { |acc, b| acc + (b ? 1 : 0) }

なんと、Haskell のほぼ半分の行数になっちゃいました。 Haskell 力が低すぎる……精進します!

競技プログラミングは興味があるにもかかわらず、重い腰がなかなか上がらず全然できていませんでした*1が、今日から色々やっていきます!とうとう蟻本も買ったしね(*´・ω・)b

コードレビュー待ってます(/-\*)

大先輩 Haskeller に解いていただいた

すごいH本読書会で色々教えていただいている、大先輩 Haskeller に解いていただきました。

main :: IO ()
main = interact $ show . longTable . map (map read . words) . lines
 
longTable :: [[Int]] -> Int
longTable ([n, _] : xs) = sum $ foldl update (replicate n 0) xs
  where
  update xs [a, b]
    | sum ys > 0 = xs
    | otherwise = take n $ drop (n-b+1) $ xs' ++ xs'
    where
    (ys, zs) = splitAt a $ take n $ drop (b-1) $ xs ++ xs
    xs' = replicate a 1 ++ zs

次元が違った……。

  1. interact 関数の存在
  2. longTable 関数の設計
  3. update 関数の設計

あたりがとても印象に残りました。interactに関してはただ知らなかっただけだけど、これはとても便利そう。試してみる。

longTable 関数で、引数の処理の仕方が最高にかっこいいなと思いました。 一括で取得して、パターンマッチで先頭を取得。凄い。思いつかなかった。 そして Haskell でカッコよく繰り返し処理するんであれば、確かに入力行数なんて情報はハナから不要ですよね。

update 関数の設計については目から鱗でした。リスト結合して、先頭 Drop するなんて思いつきもしなかった……。

道のりは長く険しいがとても楽しい。

*1:TopCoder で英語力の低さが露呈して死んでただけの可能性あり