Rep-string: Difference between revisions
Content added Content deleted
m (→{{header|Haskell}}: Applied Hlint to first version.) |
|||
Line 1,331: | Line 1,331: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
<lang haskell>import Data.List ( |
<lang haskell>import Data.List (inits, maximumBy) |
||
import Data.Maybe (fromMaybe) |
|||
repstring :: String -> Maybe String |
repstring :: String -> Maybe String |
||
Line 1,337: | Line 1,338: | ||
repstring [] = Nothing |
repstring [] = Nothing |
||
-- strings with only one character are not rep strings |
-- strings with only one character are not rep strings |
||
repstring |
repstring [_] = Nothing |
||
repstring xs |
repstring xs |
||
| any (`notElem` "01") xs = Nothing |
|||
| otherwise = longest xs |
|||
where |
|||
-- length of the original string |
|||
lxs = length xs |
|||
-- half that length |
|||
lq2 = lxs `quot` 2 |
|||
-- make a string of same length using repetitions of a part |
|||
-- of the original string, and also return the substring used |
|||
subrepeat x = (x, take lxs $ concat $ repeat x) |
|||
-- check if a repeated string matches the original string |
|||
sndValid (_, ys) = ys == xs |
|||
-- make all possible strings out of repetitions of parts of |
|||
-- the original string, which have max. length lq2 |
|||
possible = map subrepeat . take lq2 . tail . inits |
|||
-- filter only valid possibilities, and return the substrings |
|||
-- used for building them |
|||
valid = map fst . filter sndValid . possible |
|||
-- see which string is longer |
|||
compLength a b = compare (length a) (length b) |
|||
-- get the longest substring that, repeated, builds a string |
|||
-- that matches the original string |
|||
longest ys = case valid ys of |
|||
[] -> Nothing |
|||
zs -> Just $ maximumBy compLength zs |
|||
main :: IO () |
main :: IO () |
||
main = |
main = |
||
mapM_ processIO examples |
|||
where |
|||
examples = |
|||
[ "1001110011", |
|||
"1010101010", "1111111111", "0100101101", "0100100", |
|||
"1110111011", |
|||
"0010010010", |
|||
⚫ | |||
"1010101010", |
|||
"1111111111", |
|||
"0100101101", |
|||
⚫ | |||
"0100100", |
|||
"101", |
|||
"11", |
|||
"00", |
|||
"1" |
|||
] |
|||
⚫ | |||
processIO xs = do |
|||
putStr (xs <> ": ") |
|||
⚫ | |||
{{Out}} |
{{Out}} |
||
<pre>1001110011: 10011 |
<pre>1001110011: 10011 |