1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
{-
--- Day 6: Tuning Trouble ---
The preparations are finally complete; you and the Elves leave camp on foot and begin to make
your way toward the star fruit grove.
As you move through the dense undergrowth, one of the Elves gives you a handheld device. He
says that it has many fancy features, but the most important one to set up right now is the
communication system.
However, because he's heard you have significant experience dealing with signal-based systems,
he convinced the other Elves that it would be okay to give you their one malfunctioning device
- surely you'll have no problem fixing it.
As if inspired by comedic timing, the device emits a few colorful sparks.
To be able to communicate with the Elves, the device needs to lock on to their signal. The
signal is a series of seemingly-random characters that the device receives one at a time.
To fix the communication system, you need to add a subroutine to the device that detects a
start-of-packet marker in the datastream. In the protocol being used by the Elves, the start
of a packet is indicated by a sequence of four characters that are all different.
The device will send your subroutine a datastream buffer (your puzzle input); your subroutine
needs to identify the first position where the four most recently received characters were all
different. Specifically, it needs to report the number of characters from the beginning of the
buffer to the end of the first such four-character marker.
For example, suppose you receive the following datastream buffer:
```
mjqjpqmgbljsphdztnvjfqwrcgsmlb
```
After the first three characters (mjq) have been received, there haven't been enough characters
received yet to find the marker. The first time a marker could occur is after the fourth
character is received, making the most recent four characters mjqj. Because j is repeated, this
isn't a marker.
The first time a marker appears is after the seventh character arrives. Once it does, the last
four characters received are jpqm, which are all different. In this case, your subroutine
should report the value 7, because the first start-of-packet marker is complete after 7
characters have been processed.
Here are a few more examples:
bvwbjplbgvbhsrlpgdmjqwftvncz: first marker after character 5
nppdvjthqldpwncqszvftbrmjlhg: first marker after character 6
nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg: first marker after character 10
zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw: first marker after character 11
How many characters need to be processed before the first start-of-packet marker is detected?
--- Part Two ---
Your device's communication system is correctly detecting packets, but still isn't working. It
looks like it also needs to look for messages.
A start-of-message marker is just like a start-of-packet marker, except it consists of 14
distinct characters rather than 4.
Here are the first positions of start-of-message markers for all of the above examples:
mjqjpqmgbljsphdztnvjfqwrcgsmlb: first marker after character 19
bvwbjplbgvbhsrlpgdmjqwftvncz: first marker after character 23
nppdvjthqldpwncqszvftbrmjlhg: first marker after character 23
nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg: first marker after character 29
zcfzfwzzqfrljwzlrfnpqdbhtmscgvjw: first marker after character 26
How many characters need to be processed before the first start-of-message marker is detected?
-}
{-# LANGUAGE DerivingStrategies #-}
{-# OPTIONS_GHC -Wno-unrecognised-pragmas #-}
{-# HLINT ignore "Use ordNub" #-}
{-# OPTIONS_GHC -Wno-unsafe #-}
module Main (main) where
import Data.ByteString.Lazy (ByteString)
import Data.Discrimination (Grouping, nub)
import Data.List (findIndex, length)
import Options.Applicative (Parser, ParserInfo, argument, execParser, fullDesc, help, helper, info, metavar, str)
import Relude hiding (ByteString, elem, empty, filter, fromList, length, null, optional, readFile, splitAt)
import Text.Parsec (ParseError, parse, (<?>))
import Text.Parsec.ByteString.Lazy (GenParser)
import Text.Parsec.Char (anyChar, string)
import Text.Parsec.Combinator (eof, many1)
import Text.Parsec.Prim (parsecMap, try)
type Opts :: Type
newtype Opts = Opts {_filename :: Text} deriving stock (Show)
parseInput :: FilePath -> ByteString -> Either ParseError String
parseInput = parse $ many1 anyChar <* (eol <|> eof)
where
eol :: GenParser t st ()
eol =
parsecMap
(const ())
( try (string "\n\r")
<|> try (string "\r\n")
<|> string "\n"
<|> string "\r"
<?> "end of line"
)
window :: Int -> [a] -> [[a]]
window n xs =
if n > length xs
then []
else take n xs : window n (drop 1 xs)
allunique :: Grouping a => [a] -> Bool
allunique xs = nub xs == xs
run :: Int -> String -> Maybe Int
run nchars = findIndex allunique . window nchars
runPart1 :: String -> Int
runPart1 xs = case run nchars xs of
Nothing -> error "Failure"
Just res -> nchars + res
where
nchars :: Int
nchars = 4
runPart2 :: String -> Int
runPart2 xs = case run nchars xs of
Nothing -> error "Failure"
Just res -> nchars + res
where
nchars :: Int
nchars = 14
main :: IO ()
main = do
fileName <- toString . _filename <$> execParser opts
rawInput <- readFileLBS fileName
case parseInput fileName rawInput of
Left e -> do
putTextLn "Error parsing input:"
print e
Right r -> do
print $ runPart1 r
print $ runPart2 r
where
opts :: ParserInfo Opts
opts = info (helper <*> options) fullDesc
options :: Parser Opts
options = Opts <$> filename
filename :: Parser Text
filename = argument str $ metavar "filename" <> help "Input file"
|
