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
|
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Advent of Code 2022\n",
"#### Day 6: Tuning Trouble\n",
"\n",
"You're parsing a buffer of characters, looking for a \"marker\": the index of the first character where the previous $n$ characters are all unique.\n",
"\n",
"**Part 1.** What if $n = 4$, for the \"start of packet\" marker?\n",
"\n",
"**Part 2.** What if $n = 14$, for the \"start of message\" marker?"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"(require racket\n",
" advent-of-code\n",
" (only-in algorithms sliding))\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"##### Parts 1 and 2\n",
"\n",
"`(sliding xs n)` returns all the overlapping sublists of `xs` that are `n` elements wide. This turns this problem into a simple `for` comprehension, just looking for the first sublist with no duplicates (which means its length after deduplication doesn't change).\n",
"\n",
"The solution to part 1 and part 2 is the same, just differing in how wide the window is."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<code>1042</code>"
],
"text/plain": [
"1042"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(define buffer (fetch-aoc-input (find-session) 2022 6))\n",
"\n",
"(define (find-marker data type)\n",
" (define n\n",
" (match type\n",
" ['start-of-packet 4]\n",
" ['start-of-message 14]))\n",
" (for/first ([chunk (in-list (sliding (string->list data) n))]\n",
" [i (in-naturals n)]\n",
" #:when (= n (~> chunk remove-duplicates length)))\n",
" i))\n",
"\n",
"(find-marker buffer 'start-of-packet)\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<code>2980</code>"
],
"text/plain": [
"2980"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(find-marker buffer 'start-of-message)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Racket (trusted)",
"language": "racket",
"name": "racket-trusted"
},
"language_info": {
"codemirror_mode": "scheme",
"file_extension": ".rkt",
"mimetype": "text/x-racket",
"name": "racket",
"pygments_lexer": "racket",
"version": "8.7"
},
"orig_nbformat": 4,
"vscode": {
"interpreter": {
"hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}
|
