this repo has no description
tulkdan.dev
1* Reverse Polish Notation Calculator
2
3[[https://en.wikipedia.org/wiki/Reverse_Polish_notation][Link for the wikipedia for the explanation]]
4
5#+begin_src haskell
6 import Data.List
7#+end_src
8
9#+RESULTS:
10
11#+begin_src haskell
12 :{
13 solveRPN :: String -> Float
14 solveRPN = head . foldl foldingFunction [] . words
15 where foldingFunction (x:y:ys) "*" = (x * y):ys
16 foldingFunction (x:y:ys) "+" = (x + y):ys
17 foldingFunction (x:y:ys) "-" = (y - x):ys
18 foldingFunction (x:y:ys) "/" = (y / x):ys
19 foldingFunction (x:y:ys) "^" = (y ** x):ys
20 foldingFunction (x:xs) "ln" = log x:xs
21 foldingFunction xs "sum" = [sum xs]
22 foldingFunction xs numberString = read numberString:xs
23 :}
24
25 solveRPN "10 10 10 10 sum 4 /"
26#+end_src
27
28#+RESULTS:
29: Prelude Data.List> 10.0
30
31* Heathrow to London
32
33Your plane just landed in England and you rent a car.
34You have a meeting really soon and you have to get fro Heathrow Airport to London as fast as you can (but safely!).
35
36There are two main roads going from Heathrow to London and there's a number of regional roads crossing them.
37It takes you a fixed amount of time to travel from one crossroads to another.
38It's up to you to find the optimal path to take so that you get to London as fast as you can!
39You start on the lest side and can either cross to the other main road or go forward.
40
41Our job is to make a program that takes input that represents a road system and print out what the shortert path across it is.
42Here's what the input would look like for this care:
43
44#+begin_example
45 50
46 10
47 30
48 5
49 90
50 20
51 40
52 2
53 25
54 10
55 8
56 0
57#+end_example
58
59To mentally parse the input file, read it in threes and mentally split the road system into sections.
60Each section is comprised of a road A, road B and a crossing road.
61To have it neatly fit into threes, we say that there's a last crossing section that takes 0 minutes to drive over.
62That's because we don't care where we arrive in London, as long as we're in London.
63
64To get the best path we do this: first we see what the best path to the next crossroads on main road A is.
65The two options are going directly forward or starting at the opposite road, going forward and then crossing over.
66We remember the cost and the path. We use the same method to see what the best path to the next crossroads on main road B is and remember that.
67Then, we see if the path to the next crossroads on A is cheaper if we go prom the previous A crossroads or if we to from the previous B crossroads and then cross over.
68We remember the cheaper path and then we to the same for the crossroads opposite of it.
69We do this for every section until we reach the end.
70Once we've reachead the end, the cheapest of the two paths that we have is our optimal path!
71
72So in essence, we keep one shortest path on the road A and one path on the B road and when we reach the end, the shorter of those two ir our path.
73
74#+begin_src haskell
75 :{
76 data Section = Section { getA :: Int, getB :: Int, getC :: Int } deriving (Show)
77 type RoadSystem = [Section]
78
79 heathrowToLondon :: RoadSystem
80 heathrowToLondon = [Section 50 10 30, Section 5 90 20, Section 40 2 25, Section 10 8 0]
81
82 data Label = A | B | C deriving (Show)
83 type Path = [(Label, Int)]
84
85 roadStep :: (Path, Path) -> Section -> (Path, Path)
86 roadStep (pathA, pathB) (Section a b c) =
87 let priceA = sum $ map snd pathA
88 priceB = sum $ map snd pathB
89 forwardPriceToA = priceA + a
90 crossPriceToA = priceB + b + c
91 forwardPriceToB = priceB + b
92 crossPriceToB = priceA + a + c
93 newPathToA = if forwardPriceToA <= crossPriceToA
94 then (A,a):pathA
95 else (C,c):(B,b):pathB
96 newPathToB = if forwardPriceToB <= crossPriceToB
97 then (B,b):pathB
98 else (C,c):(A,a):pathA
99
100 in (newPathToA, newPathToB)
101
102
103 optimalPath :: RoadSystem -> Path
104 optimalPath roadSystem =
105 let (bestAPath, bestBPath) = foldl roadStep ([], []) roadSystem
106 in if sum (map snd bestAPath) <= sum (map snd bestBPath)
107 then reverse bestAPath
108 else reverse bestBPath
109
110 resolveProblem :: RoadSystem
111 resolveProblem roadSystem =
112 let path = optimalPath roadSystem
113 pathString = concat $ map (show . fst) path
114 pathPrice = sum $ map snd path
115 putStrLn $ "The best path to take is: " ++ pathString
116 putStrLn $ "The price is: " ++ pathPrice
117 :}
118
119 resolveProblem heathrowToLondon
120#+end_src
121
122#+RESULTS:
123: Prelude Data.List>
124: <interactive>:208:1-14: error:
125: Variable not in scope: resolveProblem :: RoadSystem -> t