Mercurial > repos > other > SevenLanguagesInSevenWeeks

annotate 7-Haskell/day2.hs @ 92:6f650dd96685

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Minor tweak to prime efficiency
author IBBoard <dev@ibboard.co.uk>
date Mon, 17 Jun 2019 20:50:43 +0100
parents 075ff4e4feaf
children 39084e2b8744
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
6f650dd96685 Minor tweak to prime efficiency
IBBoard <dev@ibboard.co.uk>
parents: 91
diff changeset
58 primes = 2 : [x | x <- [3, 5 ..], (mod ((product [1 .. x-1]) + 1) x) == 0]