From f80e7668102bec6e1ff0597a965eceecda6d2756 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Thu, 15 Dec 2016 11:25:28 +0000 Subject: [PATCH] Added acknowledgement in comment --- advent11a.hs | 15 ++++++--------- advent11h.hs | 15 ++++++--------- advent11p.hs | 9 ++++++--- 3 files changed, 18 insertions(+), 21 deletions(-) diff --git a/advent11a.hs b/advent11a.hs index 5a62ab1..6eb5156 100644 --- a/advent11a.hs +++ b/advent11a.hs @@ -1,3 +1,9 @@ +-- Using the idea of canonical representation of buildings from +-- https://andars.github.io/aoc_day11.html by Andrew Foote, +-- plus my extension of represening the pairs as an integer. + +-- This version is A* search, using a list for the agenda. + import Data.List (subsequences, (\\), sort, sortOn, nub, findIndices) import Data.Ord (comparing) import Data.Char (isDigit) @@ -5,7 +11,6 @@ import Data.Char (isDigit) data Item = Generator String | Microchip String deriving (Show, Eq) type Floor = [Item] data Building = Building Int [Floor] deriving (Show, Eq) --- data CBuilding = CBuilding Int [(Int, Int)] deriving (Show, Eq) data CBuilding = CBuilding Int Integer deriving (Show, Eq) data Agendum = Agendum {current :: Building, trail :: [CBuilding], cost :: Int} @@ -54,7 +59,6 @@ buildingTest = Building 0 [ []] canonical :: Building -> CBuilding --- canonical (Building f floors) = CBuilding f (sort pairs) canonical (Building f floors) = CBuilding f (read $ filter (isDigit) $ show $ sort pairs) where names = nub $ map (\(Generator n) -> n) $ filter (isGenerator) $ concat floors floorOf (Generator g) = head (findIndices @@ -75,11 +79,6 @@ main = do part1 :: IO () part1 = print $ length $ trail $ aStar (initAgenda building1) [] --- part1 = print $ length $ trail $ --- aStar [Agendum {current = building1, trail=[], cost = estimateCost building1}] [] - --- part2 :: IO () --- part2 = print $ length $ init $ extractJust $ aStar [[building2]] [] part2 :: IO () part2 = print $ length $ trail $aStar (initAgenda building2) [] @@ -99,7 +98,6 @@ aStar (currentAgendum:agenda) closed = reached = current currentAgendum creached = canonical reached newAgenda = - -- sortBy (\t1 t2 -> (cost t1) `compare` (cost t2)) $ sortOn (cost) $ agenda ++ (candidates currentAgendum closed) @@ -110,7 +108,6 @@ candidates agendum closed = newCandidates candidate = current agendum previous = trail agendum succs = legalSuccessors $ successors candidate - -- nonloops = (succs \\ previous) \\ closed excludable = previous ++ closed nonloops = filter (\s -> not $ (canonical s) `elem` excludable) succs newCandidates = map (\n -> makeAgendum n) nonloops diff --git a/advent11h.hs b/advent11h.hs index 860c765..ae6e566 100644 --- a/advent11h.hs +++ b/advent11h.hs @@ -1,3 +1,9 @@ +-- Using the idea of canonical representation of buildings from +-- https://andars.github.io/aoc_day11.html by Andrew Foote, +-- plus my extension of represening the pairs as an integer. + +-- This version is hillclimbing search, using a list for the agenda. + import Data.List (subsequences, (\\), sort, sortOn, nub, findIndices) import Data.Ord (comparing) import Data.Char (isDigit) @@ -5,7 +11,6 @@ import Data.Char (isDigit) data Item = Generator String | Microchip String deriving (Show, Eq) type Floor = [Item] data Building = Building Int [Floor] deriving (Show, Eq) --- data CBuilding = CBuilding Int [(Int, Int)] deriving (Show, Eq) data CBuilding = CBuilding Int Integer deriving (Show, Eq) data Agendum = Agendum {current :: Building, trail :: [CBuilding], cost :: Int} @@ -54,7 +59,6 @@ buildingTest = Building 0 [ []] canonical :: Building -> CBuilding --- canonical (Building f floors) = CBuilding f (sort pairs) canonical (Building f floors) = CBuilding f (read $ filter (isDigit) $ show $ sort pairs) where names = nub $ map (\(Generator n) -> n) $ filter (isGenerator) $ concat floors floorOf (Generator g) = head (findIndices @@ -75,11 +79,6 @@ main = do part1 :: IO () part1 = print $ length $ trail $ hillClimb (initAgenda building1) [] --- part1 = print $ length $ trail $ --- aStar [Agendum {current = building1, trail=[], cost = estimateCost building1}] [] - --- part2 :: IO () --- part2 = print $ length $ init $ extractJust $ aStar [[building2]] [] part2 :: IO () part2 = print $ length $ trail $ hillClimb (initAgenda building2) [] @@ -98,7 +97,6 @@ hillClimb (currentAgendum:agenda) closed = reached = current currentAgendum creached = canonical reached newAgenda = - -- sortBy (\t1 t2 -> (cost t1) `compare` (cost t2)) $ sortOn (cost) $ agenda ++ (candidates currentAgendum closed) @@ -109,7 +107,6 @@ candidates agendum closed = newCandidates candidate = current agendum previous = trail agendum succs = legalSuccessors $ successors candidate - -- nonloops = (succs \\ previous) \\ closed excludable = previous ++ closed nonloops = filter (\s -> not $ (canonical s) `elem` excludable) succs newCandidates = map (\n -> makeAgendum n) nonloops diff --git a/advent11p.hs b/advent11p.hs index 24955b9..cdcf030 100644 --- a/advent11p.hs +++ b/advent11p.hs @@ -1,3 +1,9 @@ +-- Using the idea of canonical representation of buildings from +-- https://andars.github.io/aoc_day11.html by Andrew Foote, +-- plus my extension of represening the pairs as an integer. + +-- This version is A* search, using a priority queue for the agenda. + import Data.List (subsequences, (\\), sort, sortOn, nub, findIndices) import Data.Ord (comparing) import Data.Char (isDigit) @@ -7,7 +13,6 @@ import qualified Data.PQueue.Prio.Min as P data Item = Generator String | Microchip String deriving (Show, Eq) type Floor = [Item] data Building = Building Int [Floor] deriving (Show, Eq) --- data CBuilding = CBuilding Int [(Int, Int)] deriving (Show, Eq) data CBuilding = CBuilding Int Integer deriving (Show, Eq) data Agendum = Agendum {current :: Building, trail :: [CBuilding], cost :: Int} type Agenda = P.MinPQueue Int Agendum @@ -106,8 +111,6 @@ candidates agendum closed = newCandidates candidate = current agendum previous = trail agendum succs = legalSuccessors $ successors candidate - -- excludable = previous ++ closed - -- nonloops = filter (\s -> not $ (canonical s) `elem` excludable) succs nonloops = filter (\s -> not $ (canonical s) `elem` closed) succs newCandidates = map (\a -> (cost a, a)) $ map (\n -> makeAgendum n) nonloops makeAgendum new = Agendum {current = new, -- 2.34.1