Mercurial > repos > other > SevenLanguagesInSevenWeeks

annotate 7-Haskell/day2.hs @ 93:39084e2b8744

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add a function for word-aware text wrapping Potentially hugely inefficient because we iterate through the string character by character, but then splitting it first and iterating over words still needs to iterate over the string to know where to split.
author IBBoard <dev@ibboard.co.uk>
date Tue, 18 Jun 2019 21:05:00 +0100
parents 6f650dd96685
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
90
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
1 module Day2 where
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
2 -- We could just "import Data.List" and then use "sort", but let's do it by hand with an ugly O(n^2) approach
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
3 my_sort :: Ord a => [a] -> [a]
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
4 my_sort lst = my_sort' (<) lst []
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
5
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
6 -- my_sort' :: Ord a => [a] -> [a] -> [a]
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
7 -- my_sort' [] res = res
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
8 -- my_sort' (h:t) [] = my_sort' t [h]
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
9 -- my_sort' (h:t) (h_res:t_res)
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
10 -- | h < h_res = my_sort' t (h:h_res:t_res)
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
11 -- | otherwise = my_sort' t (h_res:my_sort' (h:[]) t_res)
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
12
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
13 my_sort' :: Ord a => (a -> a -> Bool) -> [a] -> [a] -> [a]
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
14 my_sort' cmp [] res = res
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
15 my_sort' cmp (h:t) [] = my_sort' cmp t [h]
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
16 my_sort' cmp (h:t) (h_res:t_res)
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
17 | cmp h h_res = my_sort' cmp t (h:h_res:t_res)
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
18 | otherwise = my_sort' cmp t (h_res:my_sort' cmp (h:[]) t_res)
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
19
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
20 parse_int :: String -> Int
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
21 parse_int str = parse_int' str 0
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
22
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
23 parse_int' :: String -> Int -> Int
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
24 parse_int' "" val = val
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
25 parse_int' (h:t) val
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
26 | fromEnum h >= 48 && fromEnum h <= 57 = parse_int' t (val * 10 + ((fromEnum h) - 48))
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
27 | otherwise = parse_int' t val
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
28
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
29 every_three :: Integer -> [Integer]
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
30 every_three = every_n 3
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
31
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
32 every_five :: Integer -> [Integer]
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
33 every_five = every_n 5
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
34
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
35 every_n :: Integer -> Integer -> [Integer]
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
36 every_n n x = [x, x + n ..]
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
37
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
38 -- Usage: every_m_n (every_five) 5 (every_three) 3
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
39 every_m_n :: (Integer -> [Integer]) -> Integer -> (Integer -> [Integer]) -> Integer -> [Integer]
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
40 every_m_n _m x _n y = zipWith (+) (_m x) (_n y)
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
41
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
42 halve :: Double -> Double
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
43 halve x = (/ 2) x -- It's ugly, but it's the "partially applied" version of "x / 2" - "(/ 2)" becomes an anonymous function that gets applied to x
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
44
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
45 new_line :: String -> String
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
46 new_line x = (++ "\n") x
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
47
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
48 -- Let's go Euclidean: https://en.wikipedia.org/wiki/Greatest_common_divisor#Euclid's_algorithm
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
49 my_gcd :: Integer -> Integer -> Integer
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
50 my_gcd a b
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
51 | a == b = a
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
52 | a > b = my_gcd (a - b) b
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
53 | otherwise = my_gcd a (b - a)
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
54
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
55 -- Wilson's theorem seems easiest: https://en.wikipedia.org/wiki/Wilson%27s_theorem
c27c87cd0f08 Add most of the Day 2 exercises for Haskell
IBBoard <dev@ibboard.co.uk>
parents:
diff changeset
56 primes :: [Integer]
92
6f650dd96685 Minor tweak to prime efficiency
IBBoard <dev@ibboard.co.uk>
parents: 91
diff changeset
57 -- Primes after 2 have to be odd (or else they're a multiple of 2!), so increment up the odd numbers
93
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
58 primes = 2 : [x | x <- [3, 5 ..], (mod ((product [1 .. x-1]) + 1) x) == 0]
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
59
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
60 break_lines :: String -> Int -> [String]
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
61 break_lines str len = break_lines' str "" "" len []
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
62
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
63 break_lines' :: String -> String -> String -> Int -> [String] -> [String]
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
64 break_lines' "" "" "" _ strings = strings
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
65 break_lines' "" next_word line len strings = break_lines' "" "" "" len (strings ++ [line ++ next_word])
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
66 break_lines' (char:rest) next_word line len strings
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
67 | char == ' ' && candidate_length == len = break_lines' rest "" "" len (strings ++ [line ++ next_word]) -- if we've got a space at the right place, add the word but not the space
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
68 | char == ' ' = break_lines' rest "" (line ++ next_word ++ " ") len strings -- else we've got a break so add the word and the space to the line
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
69 -- Then, for non-space characters…
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
70 | candidate_length < len = break_lines' rest (next_word ++ [char]) line len strings -- if we're not at the line length then add the character
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
71 | candidate_length == len && line /= "" = break_lines' rest (next_word ++ [char]) "" len (strings ++ [line]) -- if we've got a partial line and our next word is getting too long then add the line as-is
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
72 | length next_word == len = break_lines' rest ("-" ++ [char]) "" len (strings ++ [next_word]) -- if our candidate is more than our length and we've got a blank line then add our N characters of this word, and hyphenate the word
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
73 | otherwise = break_lines' rest (next_word ++ [char]) line len strings -- otherwise we're within limits and can keep going
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
74 where candidate_length = (length next_word + length line)
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
75
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
76 -- > break_lines "hello 1234567890123456789012345678901234567890123456789012345678901234567890123456789012345 lorem ipsum bibbety bobbety boo once upon a time there was a cat and it sat on a mat while the quick brown fox jumped over the lazy dog" 80
39084e2b8744 Add a function for word-aware text wrapping
IBBoard <dev@ibboard.co.uk>
parents: 92
diff changeset
77 -- ["hello ","12345678901234567890123456789012345678901234567890123456789012345678901234567890","-12345 lorem ipsum bibbety bobbety boo once upon a time there was a cat and it ","sat on a mat while the quick brown fox jumped over the lazy dog"]--