-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathday10hints.html
203 lines (192 loc) · 14.4 KB
/
day10hints.html
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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
<!DOCTYPE html>
<html lang="en-us">
<head>
<title>2020\day10hints.nim</title>
<link rel="icon" href="data:image/svg+xml,<svg xmlns=%22http://www.w3.org/2000/svg%22 viewBox=%220 0 100 100%22><text y=%22.9em%22 font-size=%2280%22>🐳</text></svg>">
<meta content="text/html; charset=utf-8" http-equiv="content-type">
<meta content="width=device-width, initial-scale=1" name="viewport">
<link rel='stylesheet' href='https://unpkg.com/normalize.css/'>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/kognise/water.css@latest/dist/dark.min.css">
<link rel='stylesheet' href='https://cdn.jsdelivr.net/gh/pietroppeter/nimib/assets/androidstudio.css'>
<style>
.nb-box {
display: flex;
align-items: center;
justify-content: space-between;
}
.nb-small {
font-size: 0.8rem;
}
button.nb-small {
float: right;
padding: 2px;
padding-right: 5px;
padding-left: 5px;
}
section#source {
display:none
}
</style>
<script async defer data-domain="pietroppeter.github.io/adventofnim" src="https://plausible.io/js/plausible.js"></script>
<style>
a {
text-decoration: none;
color: #009900;
}
a:hover {
color: #99ff99;
}
em {
color: #ffffff;
font-style: normal;
text-shadow: 0 0 5px #ffffff;
}
em.star {
font-style: normal;
color: #ffff66;
text-shadow: 0 0 5px #ffff66;
}
</style>
</head>
<body>
<header>
<div class="nb-box">
<span><a href="..">🏡</a></span>
<span><code>2020\day10hints.nim</code></span>
<span><a href="https://github.com/pietroppeter/adventofnim"><svg aria-hidden="true" width="1.2em" height="1.2em" style="vertical-align: middle; fill: #fff" preserveAspectRatio="xMidYMid meet" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M8 0C3.58 0 0 3.58 0 8c0 3.54 2.29 6.53 5.47 7.59.4.07.55-.17.55-.38 0-.19-.01-.82-.01-1.49-2.01.37-2.53-.49-2.69-.94-.09-.23-.48-.94-.82-1.13-.28-.15-.68-.52-.01-.53.63-.01 1.08.58 1.23.82.72 1.21 1.87.87 2.33.66.07-.52.28-.87.51-1.07-1.78-.2-3.64-.89-3.64-3.95 0-.87.31-1.59.82-2.15-.08-.2-.36-1.02.08-2.12 0 0 .67-.21 2.2.82.64-.18 1.32-.27 2-.27.68 0 1.36.09 2 .27 1.53-1.04 2.2-.82 2.2-.82.44 1.1.16 1.92.08 2.12.51.56.82 1.27.82 2.15 0 3.07-1.87 3.75-3.65 3.95.29.25.54.73.54 1.48 0 1.07-.01 1.93-.01 2.2 0 .21.15.46.55.38A8.013 8.013 0 0016 8c0-4.42-3.58-8-8-8z"></path></svg></a></span>
</div>
<hr>
</header><main>
<h1>2020, Day 10, Part 2 - Hints</h1>
<p>My background being in mathematics, I do suffer a bit parse-heavy days, while I enjoy thoroughly days like today.
Below a sequence of micro-hints to help those who have the reciprocal suffering.
Following them all the way should result in something similar to my implementation,
but you might want to stop earlier and come up with your own version.</p>
<h2>Problem</h2>
<p>You have to implement a function <code>solve2</code> that counts all possible arrangements of a sequence of integers according to the constraints:</p>
<ul>
<li>start with 0</li>
<li>any subsequent element should have a difference with the previous that is either 1, 2 or 3</li>
<li>end with max element of the sequence + 3</li>
</ul>
<h2>(Advent of) Hints</h2>
<p>I am not really using <a href="https://nim-lang.org/">nim</a> notation in the hints and they should be agnostic with respect to the programming language.</p>
<details><summary>Hint 1</summary><p><p>Sort your input if you haven't already (you should have in part1) and realize there are no duplicates</p>
</p></details>
<details><summary>Hint 2</summary><p><p>Is there a way to split the problem from a big sequence into several subsequences?</p>
</p></details>
<details><summary>Hint 3</summary><p><p>In particular, are there elements in the sequence that <strong>cannot</strong> be skipped in any configuration (e.g. every configuration must contain them)?</p>
</p></details>
<details><summary>Hint 4</summary><p><p>I mean in the sequences <code>[0 3 4]</code> or <code>[0 1 4]</code> (or <code>[0 2 5]</code> or <code>[0 3 5]</code>) can I ever skip the middle element? How many configurations do those have?</p>
</p></details>
<details><summary>Hint 5</summary><p><p>yep, those sequences only have one conifguration possible</p>
</p></details>
<details><summary>Hint 6</summary><p><p>realize that you can in fact split your problem whenever you have an element that has a difference of <code>3</code> with either the preceding or subsequent element</p>
</p></details>
<details><summary>Hint 7</summary><p><p>in particular realize that the absolute values of the elements do not really matter, only their differences 🤯!</p>
</p></details>
<details><summary>Hint 8</summary><p><p>implement a <code>diff</code> function (output of the above sequences would be <code>(3 1)</code>, <code>(1 3)</code>, <code>(2 3)</code>, <code>(3 2)</code>; note that I changed the syle of parentheses: <code>[]</code> for original sequence and <code>()</code> for its differences.</p>
</p></details>
<details><summary>Hint 9</summary><p><p>the new function we need to implement we call it <code>numArr</code> and computs number of possible arrangements given the differences of a (sub)sequence (it assumes first and last elements <strong>must</strong> be in the sequence)</p>
</p></details>
<details><summary>Hint 10</summary><p><p>previous hints imply that <code>numArr (s 3 t) = numArr(s)*numArr(t)</code> where <code>s</code> and <code>t</code> are subsequence 😲</p>
</p></details>
<details><summary>Hint 11</summary><p><p>now you are starting to realize that you will use recursion 🐢🐢🐢</p>
</p></details>
<details><summary>Hint 12</summary><p><p>manually compute the result over all possible difference sequences of length 2 and 3 (without a <code>3</code> difference)</p>
</p></details>
<details><summary>Hint 13</summary><p><p>is there another difference configuration that will result in stuff you cannot skip, can you see it?</p>
</p></details>
<details><summary>Hint 14</summary><p><p><code>numArr (s 2 2 t) = ?</code></p>
</p></details>
<details><summary>Hint 15</summary><p><p><code>numArr (s 2 2 t) = numArr(s)*numArr(t)</code></p>
</p></details>
<details><summary>Hint 16</summary><p><p>you are almost there but not yet: now you can split problem from a big sequence into a subsequence for some special cases, how do I reduce the computation for a sequence that has none of this special cases? I need to be able to reduce the length of the sequence!</p>
</p></details>
<details><summary>Hint 17</summary><p><p>to count the number of arrangements start counting those which contain the second element (remember the first must be included) and then count those who do not</p>
</p></details>
<details><summary>Hint 18</summary><p><p>try with this sequence <code>(1 1 1 1)</code>, you can think of it as <code>[0 1 2 3 4]</code></p>
</p></details>
<details><summary>Hint 19</summary><p><p><code>numArr (x y s) = ?</code> where <code>x</code>, <code>y</code> are single differences and <code>s</code> is a subsequence</p>
</p></details>
<details><summary>Hint 20</summary><p><p>correct! <code>numArr (x y s) = numArr (y s) + numArr (x+y s)</code> 💪</p>
</p></details>
<details><summary>Hint 21</summary><p><p>(note that having excluded the special cases when one of the difference is <code>3</code> or two subsequent <code>2</code>s, now <code>x + y <= 3</code>)</p>
</p></details>
<details><summary>Hint 22</summary><p><p>that's about it, you can implement a recursion using this, trying to take care first of the special cases (short lengths, diff sequences containg <code>3</code> or two <code>2</code>s)</p>
</p></details>
<details><summary>Hint 23</summary><p><p>(optional) ok, you want more? what does speed up recursion in case you need to recompute previously computed results?</p>
</p></details>
<details><summary>Hint 24</summary><p><p>that's right: <a href="https://en.wikipedia.org/wiki/Memoization">memoization</a>!</p>
</p></details>
<details><summary>Hint 25</summary><p><p>I am out of hints and you can just go and see my <a href="https://github.com/pietroppeter/adventofnim/blob/master/2020/day10.nim">implementation</a>! Hope you enjoyed!</p>
</p></details>
</main>
<footer>
<hr>
<div class="nb-box">
<span><span class="nb-small">made with <a href="https://pietroppeter.github.io/nimib/">nimib 🐳</a></span></span>
<span></span>
<span><button class="nb-small" id="show" onclick="toggleSourceDisplay()">Show Source</button></span>
</div>
</footer>
<section id="source">
<pre><code class="nim hljs"><span class="hljs-keyword">import</span> nimib, nimoji, markdown
nbInit
<span class="hljs-keyword">var</span> hint = <span class="hljs-number">1</span>
<span class="hljs-keyword">template</span> nbxHint(details: <span class="hljs-built_in">string</span>) =
nbText: <span class="hljs-string">"<details><summary>Hint "</span> & $hint & <span class="hljs-string">"</summary><p>"</span> & details.emojize.markdown & <span class="hljs-string">"</p></details>"</span>
inc hint
nbText: <span class="hljs-string">"""# 2020, Day 10, Part 2 - Hints
My background being in mathematics, I do suffer a bit parse-heavy days, while I enjoy thoroughly days like today.
Below a sequence of micro-hints to help those who have the reciprocal suffering.
Following them all the way should result in something similar to my implementation,
but you might want to stop earlier and come up with your own version.
## Problem
You have to implement a function `solve2` that counts all possible arrangements of a sequence of integers according to the constraints:
* start with 0
* any subsequent element should have a difference with the previous that is either 1, 2 or 3
* end with max element of the sequence + 3
## (Advent of) Hints
I am not really using [nim](https://nim-lang.org/) notation in the hints and they should be agnostic with respect to the programming language.
"""</span>
nbxHint: <span class="hljs-string">"Sort your input if you haven't already (you should have in part1) and realize there are no duplicates"</span>
nbxHint: <span class="hljs-string">"Is there a way to split the problem from a big sequence into several subsequences?"</span>
nbxHint: <span class="hljs-string">"In particular, are there elements in the sequence that **cannot** be skipped in any configuration (e.g. every configuration must contain them)?"</span>
nbxHint: <span class="hljs-string">"I mean in the sequences `[0 3 4]` or `[0 1 4]` (or `[0 2 5]` or `[0 3 5]`) can I ever skip the middle element? How many configurations do those have?"</span>
nbxHint: <span class="hljs-string">"yep, those sequences only have one conifguration possible"</span>
nbxHint: <span class="hljs-string">"realize that you can in fact split your problem whenever you have an element that has a difference of `3` with either the preceding or subsequent element"</span>
nbxHint: <span class="hljs-string">"in particular realize that the absolute values of the elements do not really matter, only their differences :exploding_head:!"</span>
nbxHint: <span class="hljs-string">"implement a `diff` function (output of the above sequences would be `(3 1)`, `(1 3)`, `(2 3)`, `(3 2)`; note that I changed the syle of parentheses: `[]` for original sequence and `()` for its differences."</span>
nbxHint: <span class="hljs-string">"the new function we need to implement we call it `numArr` and computs number of possible arrangements given the differences of a (sub)sequence (it assumes first and last elements **must** be in the sequence)"</span>
nbxHint: <span class="hljs-string">"previous hints imply that `numArr (s 3 t) = numArr(s)*numArr(t)` where `s` and `t` are subsequence :astonished:"</span>
nbxHint: <span class="hljs-string">"now you are starting to realize that you will use recursion :turtle::turtle::turtle:"</span>
nbxHint: <span class="hljs-string">"manually compute the result over all possible difference sequences of length 2 and 3 (without a `3` difference)"</span>
nbxHint: <span class="hljs-string">"is there another difference configuration that will result in stuff you cannot skip, can you see it?"</span>
nbxHint: <span class="hljs-string">"`numArr (s 2 2 t) = ?`"</span>
nbxHint: <span class="hljs-string">"`numArr (s 2 2 t) = numArr(s)*numArr(t)`"</span>
nbxHint: <span class="hljs-string">"you are almost there but not yet: now you can split problem from a big sequence into a subsequence for some special cases, how do I reduce the computation for a sequence that has none of this special cases? I need to be able to reduce the length of the sequence!"</span>
nbxHint: <span class="hljs-string">"to count the number of arrangements start counting those which contain the second element (remember the first must be included) and then count those who do not"</span>
nbxHint: <span class="hljs-string">"try with this sequence `(1 1 1 1)`, you can think of it as `[0 1 2 3 4]`"</span>
nbxHint: <span class="hljs-string">"`numArr (x y s) = ?` where `x`, `y` are single differences and `s` is a subsequence"</span>
nbxHint: <span class="hljs-string">"correct! `numArr (x y s) = numArr (y s) + numArr (x+y s)` :muscle:"</span>
nbxHint: <span class="hljs-string">"(note that having excluded the special cases when one of the difference is `3` or two subsequent `2`s, now `x + y <= 3`)"</span>
nbxHint: <span class="hljs-string">"that's about it, you can implement a recursion using this, trying to take care first of the special cases (short lengths, diff sequences containg `3` or two `2`s)"</span>
nbxHint: <span class="hljs-string">"(optional) ok, you want more? what does speed up recursion in case you need to recompute previously computed results?"</span>
nbxHint: <span class="hljs-string">"that's right: [memoization](https://en.wikipedia.org/wiki/Memoization)!"</span>
nbxHint: <span class="hljs-string">"I am out of hints and you can just go and see my [implementation](https://github.com/pietroppeter/adventofnim/blob/master/2020/day10.nim)! Hope you enjoyed!"</span>
nbSave</code></pre>
</section><script>
function toggleSourceDisplay() {
var btn = document.getElementById("show")
var source = document.getElementById("source");
if (btn.innerHTML=="Show Source") {
btn.innerHTML = "Hide Source";
source.style.display = "block";
} else {
btn.innerHTML = "Show Source";
source.style.display = "none";
}
}
</script></body>
</html>