Maddie
BAN USER4.1 is a good one.
data Tree a = Leaf a | Bin (Tree a) (Tree a)
data Circular a = Node a (Circular a) (Circular a)
-- pre-order traversal
--
-- .
-- / \
-- 0 .
-- / \
-- . .
-- / \ |\
-- 1 5 7 3
--
-- 0 <-> 1 <-> 5 <-> 7 <-> 3 <-> 0 <-> ...
--
toCircular :: Tree a -> Circular a
toCircular t =
let
go :: Tree a -> Circular a -> Circular a
go (Leaf a) n =
let
x =
Node a x n
in
x
go (Bin t1 t2) n =
let
x1 =
go t1 x2
x2 =
go t2 n
in
x1
in
go t (toCircular t)
-- view 8 . toCircular $ t
-- [0,1,5,7,3,0,1,5]
view :: Int -> Circular a -> [a]
view 0 _ =
[]
view n (Node a _ t2) =
a : view (n-1) t2
time O(2^n) since we enumerate all permutations of k picks from the lists.
space O(k)
range :: [[Int]] -> ((Int,Int),[Int])
range lss =
let
bounds xs =
let
a =
List.minimum xs
b =
List.maximum xs
in
(b-a,((b,a),xs))
pick =
fmap List.head . List.permutations
picks =
sequenceA . fmap pick $ lss
in
snd . List.minimumBy (comparing fst) . fmap bounds $
[ xs | xs <- picks ]
multiply :: [Int] -> [Int]
multiply xs =
-- [1,2,3]
let
accum y ys =
case ys of
[] ->
y : 1 : []
z : zs ->
z * y : z : zs
-- [1,1,2]
fromLeft =
List.reverse (List.drop 1 (foldl (flip accum) [] xs))
-- [6,3,1]
fromRight =
List.drop 1 (foldr accum [] xs)
in
-- fixed number (3) of traversals of xs => O(n)
List.zipWith (*) fromLeft fromRight
-- partition the string into pairs and singles.
-- n = 1 : 1
-- n = 2 : 2
-- n = 3 : 3
-- n = 4 : C(3) + C(2)
-- n = 5 : C(4) + C(3)
-- C(n) = C(n-1) + C(n-2)
-- "solving" the recurrence relation gives O(n^2)
--
codes :: [Int] -> [[Char]]
codes =
let
charOf x
| x >= 1 && x <= 26 =
['a'..'z'] List.!! (x-1)
| otherwise =
Prelude.error ("invalid input: " <> show x)
choice xs =
case xs of
[] ->
[[]]
[x] ->
[[charOf x]]
x : y : zs ->
fmap (charOf x:) (choice (y:zs)) <>
fmap ((charOf (10*x+y)):) (choice zs)
in
choice
deleteIndex :: Int -> [Char] -> [Char]
deleteIndex i xs =
List.take (i - 1) xs <> List.drop i xs
zeroPalindrome :: [Char] -> Bool
zeroPalindrome xs =
let
n =
length xs `div` 2
(as, bs) =
List.splitAt n xs
in
as == List.take n (List.reverse bs)
kCombination :: Int -> Int -> [[Int]]
kCombination k n =
fmap (List.take k) (List.permutations [0..n])
kPalindrome :: Int -> [Char] -> Bool
kPalindrome 0 xs =
zeroPalindrome xs
kPalindrome k xs =
let
delete indices s =
case indices of
[] ->
s
i : ixs ->
delete ixs (deleteIndex i s)
go =
List.any zeroPalindrome $
[ ys
| ys <- [ delete is xs
| is <- kCombination k (length xs)
]
]
in
-- C = C(0) + ... + C(k)
-- C(i) = (C(0) * i)!
-- C = O(k!) is what we need to improve
-- (there is no way to check a 0-palindrome in better than O(n))
kPalindrome (k-1) xs || go
-- instead of finding a palindrome, let's only check
-- that it exists. O(n)
kZeroPalindrome :: Int -> [Char] -> Bool
kZeroPalindrome k s =
let
n =
length s `div` 2
(as, bs) =
List.splitAt n s
diff (x:xs) (y:ys) =
if x == y then 0 else 2 +
diff xs ys
diff [] [] =
0
diff [] [_] =
0
diff [_] [] =
0
diff xs ys =
List.length xs + List.length ys
in
diff as (List.reverse bs) < k
- Maddie December 08, 2017