Skip to content

Instantly share code, notes, and snippets.

@ConnorBaker
Last active May 25, 2020 19:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ConnorBaker/df5ac912ef4f68f0037687fd825361f0 to your computer and use it in GitHub Desktop.
Save ConnorBaker/df5ac912ef4f68f0037687fd825361f0 to your computer and use it in GitHub Desktop.
Solution to https://open.kattis.com/problems/substitution (fails second secret test case)
module Main where
import Prelude
import Control.Arrow
import Data.List.Split ( chunksOf )
import Data.Maybe ( fromJust )
import qualified Data.ByteString.Lazy.Char8 as C
import qualified Data.Vector.Unboxed as V
-- Zero index
parse :: [C.ByteString] -> [V.Vector Int]
parse =
map (V.fromList . map (flip (-) 1 . (fst . fromJust . C.readInt)) . C.words)
-- Vector's unsafeBackpermute does the heavy lifting for us
solve :: [V.Vector Int] -> Int
solve [ms, cs, ps] =
(length . takeWhile (/= cs) . iterate (V.unsafeBackpermute ps)) ms
solve _ = error "Malformed test case."
main :: IO ()
main =
C.interact
$ C.lines -- Each line is an element of the list
>>> drop 1 -- We don't need the number of test cases
>>> chunksOf 4 -- Each test case has four lines
>>> map
( drop 1 -- We don't need the first line of the test case
>>> parse -- Transform the input to data
>>> solve -- Manipulate the data
>>> show -- Transform back to text
>>> C.pack -- Transform to ByteString
)
>>> C.unlines -- Print each result on a different line
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment