From 952c486fe2bf7011ac38601b1c3eccdda23cc9d0 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Fri, 9 Dec 2022 21:09:46 +0100 Subject: Day 6 --- Day6/CHANGELOG.md | 5 ++++ Day6/Day6.cabal | 34 ++++++++++++++++++++++ Day6/app/Main.hs | 87 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ Day6/input | 1 + 4 files changed, 127 insertions(+) create mode 100644 Day6/CHANGELOG.md create mode 100644 Day6/Day6.cabal create mode 100644 Day6/app/Main.hs create mode 100644 Day6/input diff --git a/Day6/CHANGELOG.md b/Day6/CHANGELOG.md new file mode 100644 index 0000000..e2b0ec7 --- /dev/null +++ b/Day6/CHANGELOG.md @@ -0,0 +1,5 @@ +# Revision history for Day6 + +## 0.1.0.0 -- YYYY-mm-dd + +* First version. Released on an unsuspecting world. diff --git a/Day6/Day6.cabal b/Day6/Day6.cabal new file mode 100644 index 0000000..aebdd52 --- /dev/null +++ b/Day6/Day6.cabal @@ -0,0 +1,34 @@ +cabal-version: 2.4 +name: Day6 +version: 0.1.0.0 + +-- A short (one-line) description of the package. +-- synopsis: + +-- A longer description of the package. +-- description: + +-- A URL where users can report bugs. +-- bug-reports: + +-- The license under which the package is released. +-- license: +author: Andreas Grois +maintainer: andi@grois.info + +-- A copyright notice. +-- copyright: +-- category: +extra-source-files: CHANGELOG.md + +executable Day6 + main-is: Main.hs + + -- Modules included in this executable, other than Main. + -- other-modules: + + -- LANGUAGE extensions used by modules in this package. + -- other-extensions: + build-depends: base ^>=4.16.3.0 + hs-source-dirs: app + default-language: Haskell2010 diff --git a/Day6/app/Main.hs b/Day6/app/Main.hs new file mode 100644 index 0000000..a8c90f9 --- /dev/null +++ b/Day6/app/Main.hs @@ -0,0 +1,87 @@ +module Main (main) where + +import System.Environment ( getArgs ) + +main :: IO () +main = getArgs >>= readFile . head >>= print . solveDay6 + +solveDay6 :: String -> String +solveDay6 = formatResults . (=<<) solveDay6Actual . parseDay6Input + +newtype RadioSignal = RadioSignal String + +-- Rather trivial: Any string of at least 14 characters is valid input (for part 2). +parseDay6Input :: String -> Either String RadioSignal +parseDay6Input (a:b:c:d:e:f:g:h:i:j:k:l:m:n:es) = Right $ RadioSignal (a:b:c:d:e:f:g:h:i:j:k:l:m:n:es) +parseDay6Input _ = Left "Insufficient input. Need at least 14 characters." + +-- Without knowing the part 2 prompt, I started out with a hardcoded buffer size. Left in for reference. Part 2 below is generic in buffer size. +data RingBufferFour a = RingBufferFour { + buffer :: (a,a,a,a), + position :: Int +} + +makeRingBufferFour :: (a,a,a,a) -> RingBufferFour a +makeRingBufferFour b = RingBufferFour { buffer = b, position = 0} + +pushRingBufferFour :: RingBufferFour a -> a -> RingBufferFour a +pushRingBufferFour RingBufferFour { buffer = (a,b,c,d), position = 0 } e = RingBufferFour { buffer = (e,b,c,d), position = 1} +pushRingBufferFour RingBufferFour { buffer = (a,b,c,d), position = 1 } e = RingBufferFour { buffer = (a,e,c,d), position = 2} +pushRingBufferFour RingBufferFour { buffer = (a,b,c,d), position = 2 } e = RingBufferFour { buffer = (a,b,e,d), position = 3} +pushRingBufferFour RingBufferFour { buffer = (a,b,c,d), position = 3 } e = RingBufferFour { buffer = (a,b,c,e), position = 0} +pushRingBufferFour _ _ = error "Index out of bounds in RingBufferFour. Should be impossible." + +solveDay6Actual :: RadioSignal -> Either String (Int, Int) +solveDay6Actual s = solveDay6Part1 s >>= (\firstResult -> fmap (\x -> (firstResult,x)) (solveDay6Part2 s)) + +data StartOfPacketSearch = StartOfPacketSearch { + ringBuffer :: RingBufferFour Char, + index :: Int, + remainingData :: String +} + +solveDay6Part1 :: RadioSignal -> Either String Int +solveDay6Part1 = findStartOfPacketMarker . initializeStartOfPacketSearch + +initializeStartOfPacketSearch :: RadioSignal -> StartOfPacketSearch -- this cannot fail +initializeStartOfPacketSearch (RadioSignal (a:b:c:d:es)) = StartOfPacketSearch { ringBuffer = makeRingBufferFour (a,b,c,d), index = 4, remainingData = es } + +findStartOfPacketMarker :: StartOfPacketSearch -> Either String Int +findStartOfPacketMarker s | isFinished s = Right (index s) + where isFinished StartOfPacketSearch { ringBuffer = RingBufferFour {buffer = (a,b,c,d)} } = a /= b && a /= c && a /= d && b /= c && b /= d && c /= d +findStartOfPacketMarker StartOfPacketSearch { remainingData = [] } = Left "Search for Start-of-Packet Marker did not complete." +findStartOfPacketMarker StartOfPacketSearch { ringBuffer = r, index = i, remainingData = (c:cs)} = + findStartOfPacketMarker StartOfPacketSearch { ringBuffer = pushRingBufferFour r c, index = i+1, remainingData = cs } + +newtype RingBufferN a = RingBufferN [a] + +makeRingBufferN :: [a] -> RingBufferN a +makeRingBufferN = RingBufferN + +pushRingBufferN :: RingBufferN a -> a -> RingBufferN a +pushRingBufferN (RingBufferN (a:as)) = RingBufferN . (++) as . return + +data StartOfMessageSearch = StartOfMessageSearch { + mRingBuffer :: RingBufferN Char, + mIndex :: Int, + mRemainingData :: String +} + +solveDay6Part2 :: RadioSignal -> Either String Int +solveDay6Part2 = findStartOfMessageMarker . initializeStartOfMessageSearch + +initializeStartOfMessageSearch :: RadioSignal -> StartOfMessageSearch -- can't fail either. RadioSignal already checked for validity. +initializeStartOfMessageSearch (RadioSignal s) = StartOfMessageSearch { mRingBuffer = makeRingBufferN $ take 14 s, mIndex = 14, mRemainingData = drop 14 s } + +findStartOfMessageMarker :: StartOfMessageSearch -> Either String Int +findStartOfMessageMarker s | isFinished s = Right (mIndex s) + where isFinished StartOfMessageSearch { mRingBuffer = RingBufferN as } = allUnique as + allUnique (a:as) = (a `notElem` as) && allUnique as + allUnique [] = True +findStartOfMessageMarker StartOfMessageSearch { mRemainingData = [] } = Left "Search for Start-of-Message Marker did not complete." +findStartOfMessageMarker StartOfMessageSearch { mRingBuffer = r, mIndex = i, mRemainingData = (c:cs)} = + findStartOfMessageMarker StartOfMessageSearch { mRingBuffer = pushRingBufferN r c, mIndex = i+1, mRemainingData = cs } + +formatResults :: Either String (Int, Int) -> String +formatResults (Left x) = x +formatResults (Right (a,b)) = "Part 1: " ++ show a ++ ", Part 2: " ++ show b \ No newline at end of file diff --git a/Day6/input b/Day6/input new file mode 100644 index 0000000..534b221 --- /dev/null +++ b/Day6/input @@ -0,0 +1 @@ +srjsssgppnssqzszmzjmjdmmqwqcwqccslsjswjssgbsgsnggqtqnnjznndtndnhddfldfdsfswsjsjjptjpttlwlccpnpgngcncnscncsnnwrwmwggsgdgssvbsstzsstqqrjqqlsqlsqscschhclhccznzcnnzzqppjbpjjqzzbwbqqzdqdjjqtjtbtgtqgtgdgwwsjjbwjjzssrsvsttgqtgglgplgpllcrcncssbrbgrbrllsqlsltthshrrnddwzdzdbbrppdvdqvvpvdvdsslbbmnbnjjrdrnntzzftzftttrsshpspvvrzzqzwzhzszbzjjwqwvqqglgflfwfrfprpddfvdffhzztwtppwwwztzsznzmnnbvbbtqqdhqdqdfffnjnmnlmljmlmnlnddzbbdgdqdnqqtjjtnthttvwwtrwwwgffqcfchfcfwcczhhgjhghpgpwgwffhghzghhtftntnnmlnmlmddqbbfwbfwbwvvfssrggptpltpllbcbzczzlccjgcgvcczjzvvvdtvdvqdqwdqdvdjvddjfdjjqmmfgfsftfzfwzwzfftmfmmqdqccjqcqwwflwlccpssvzzzbnbjnbjjgtgpttbwbrbwrwvrrwccgrgrvvpjvvznvvhddtdldpldppmlplltdllhqhpqhqqbpptgpgjgqjgjffvfdvdttsrsllhzlzrrdrnrjrddqbbjrrvrsstgsttjqjhjbhhnmndmmnrmnnrggmtgmmhshjjfqjjtqtstpstppggtzzrsrwwqffvzvzvqqggqsqtstszttpvtvvvddcncvncvchhnsnpsnnlmnnmqnqjjfwfccmwmbwbswbswwghhzrrptptbbjbtjjgdjgjrgrwgwlglblbnlnbbwnnpbnbmbtmtvvhjjlwlhhszslldwlwdllhjhghqghhqpplhhtjhhnhqhlhjhmmlhlmmrpptvvcczfcccwgcccpgpspdpccfhchffbjbzzwppfbbstbtltpllcssnnctnnqcqhhclhccvlvlffnjjwbwfbfttwvvdvnnnsrstrtmtfthtzzcvzvhzzpmpfpmmmwggdbdqdbbjnbbdqbbrnnnprrwbbcwbbpjjprjjzzvwwvrrthhqvhvnhhzmzszrszsjssclcjjbhjbhjbhjbjhhzbbzttnrnssrbrjbrjjmsmffdlflfzfbzzmtztdthdhldhlddnccgbbmtbbsbzsbzzcsszpzfffprfpfzfrzzhvhffsmmqtjwgjbzhnmrslrmgfjpqcllcgsjdhrshqtlgmqqtfmswfzwtnrswtzdjzclcfmltqgdhcsgvzrdltgfbtqclpppvbqnbqmlhmdbsjbwbdllzpnrwfhmnlgvdwsdjsznnhqzhwntjvcpzdrfwmwwdrttdvzspmbmqggmlmsvwgcjgpvcmplqwfjgpghnfpbctnfhcgngcbdmzhlpcnjpmczzsgfgrdftrzgvmmpdmgcrpcdrjsgczpfjnwpdjpntdngdjwctvcbsjmfwvtsrlhvpswppmfwrwzsbsgbjvljzqjjldmnqnmwsmqnmhmqhhttppbpqlvdcvdbhmbnjzztjrdjdzlvmbdrghtftwdpcwwblsjbgnzwtpztmtmnrpsvzfzncqmrvhcbqcvqvnlngdcllrqlbhjttnmjmhfhdzmjmplcfdqpmwblzsnmpczwcnggcwdvgnjcrrtmpwwqdqpvtbzpdbfnbfcfllntqjlslcsznjvzvsbntrtzwhcbtdmbmwttvhdvdtvrcmprcrrjlgsqddrsmwsrbtbpjrmlbrnsdrjfhjnqjtgjmhzjbjnprvmhtjcdbztwqmrlfflfmcslshtwmwhgvbdslgjhzjlglhllsdphlzngjfwfrlwpnqfhghnqhzhgrszbcwjvlrtmshntszsqplvfbccjwctgtfmqgqjdlgdbwhgvctqtcgfdwvqdwqzddmsbrpftzpqztgzbnplvhftmgpdthnrdhqbltbrmhpcqsfccmqzwmrbnbgbjspslwpjhdqspssqdtnssmjmvzwwfstgzzjrmfczdlznwqpdhbsjqddvffcgfhfdqdrlwcsgcsszdtpqbbsthpwbhdfzmgmcdggfcwcmzfjnfbzbccjhvwhbwfslnqnrwhgrwtlnmrmncnjtbjbdlmqsczppgbcmsdrwlrpjbgrmnhqqfhhsdhmdmpvvpjrnzsvzctmqhpzcvcjfgtlfvqvnvlnprmgrsvrrvtjfndqfsvqdsfbcwlbglmfhfhcfgqdfmclnzhdtppgzzsqgjqncqrbdhlhdjqwjpmbdnfmgdgwbwmnlngnmrhcgqwzvmbjzdvsspjwwdtpnvpftdlqlzfgtscfczsvbrtrqqpgqlvmrtddqplbzsswbgpdzpqfvqpqbndblghmdhmnctdnjbgglmrlvmrmsfgntfdwvqcvvlvbcnwrctvjqhmnsjqccwltbfqpqpmwsfvmnnfqmlmlcchqcdtbvqwcpptvfwrwtbdrlsgnwpmjgnwlprzqjlwqmtmjglbrzlgfbsghwqdmwhrcmfwdmzmflsbngtgndftdpzsqvgqdsfdhplmfcmwpbtvcdmpghmfwqjvhdhfpmbrqpvnbhlftgdtprlztrgnlcldfpjqjqdfrvqtcnzrtjcgzgsslzghlnfhwwjwzdsmpsczclrfmnqjvfmvsqpntsnnnlrfswqtrppzhqgjzlzvrrbhhfhchhvgztpgctcsgssvttszsrdwzwrbmwmspgqhmmfnzqqdbmnbltdmrsvqgddltwczbbjcmplncspgqgmzrndhttsrbvqbpbvhshfqrpqgmmdbhmmtccjcmntmpqhrvhnfnlqqbctsnfzjbphhqwmztgbhqqlbctbsfcszbggzrlcdhwddtjgtqhppzgjsqcddwjsngjrcdflmgwgfnzhjtcwgbqvpwmpgcpdwvqgswwfzcnjgmdpffmqczmsqgpthpmsjlwnrcbzrfshvwftzllwrmfccmlpjnmpjdfpcvjgjpznllmqjwpcflgqgdljtbbjvjlvhhmtvzfnjfnnwrvtlfdbhqphrjghtmlsrplqscsnvjvqdslsbsfzzrjfmchplzgjgdqvzhfphvsjfvnqlgmjfzhrdlmmvfntnzdvrnwqshsmtjnqmwzgpbbzszrsqcvlzjwnmgjhmfqrbvgmfqpswctmvpfcghvdqgstglmzvpfhzfzvhqqdmvrvrttlpwwhqgddzqlrvvdffqtznvlfgjhhmvbmtzjqnnhqzrtbzpqcwpngrdcndcgzwhzgtfwbmwbrpvvczczhwcqwsqzqbqvqftcswtcbzdbpccjhtwbpnwlwwwqwscptlwshrdbmmdcgrmpnnwgjwzszwwdwctfspbfqvdjqtrflshrqlbfgpnrmbszwjpcdzbggphgplcgvwljprzmtncsvfwqchttndhpnzmtdvtjqtcsddtqvcmztmjgwqvjhflrjjtnvfpjrnlvzvwvrpbhrzslmrqqzqhnzqnvtqppmncddphbwwsjczmphsrlltzndtqjgdlqgpnlfcvwntstmrgcrjzmmllpwldnwmwzpvzctmhszspcvtgnqthszzsmtdnzwtfddfctpjhscbqgwfpqmzpvqrzvtbrdjzrqprdgbpmzzfbgqcvcdtsfrffcpqwtvdwvtcqlcsdrzntgrhrspznndslmnvptlphpdqgbblfhmgbpmmfwqzlhvzshhpzgfjldqclngbcbrmmnqqvqmwdnjsglsggqfgjldqfbsqgtrwmpdffqlcwwlfhlpqfgwtssnjwzhgvtwqzmhmgwzwmcggmpmrzqrcsmflqsrbnzvdmjcdbnscstqrqhvddsbjpzwsvzswqhcqmgzlvfcnzjrrffzphmrvdbhqbrwpsfqvfqwhqhcgfvfsfttzcdsrjgjwcgvhllszmplmvgczqsbfldnbvrnqccbprjjdwhmqpdjjrnfdlhzdvlfmrldjlqclbjrrtjfsflphzdcdpfpr -- cgit v1.2.3