-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathday_13.js
More file actions
82 lines (67 loc) · 1.9 KB
/
day_13.js
File metadata and controls
82 lines (67 loc) · 1.9 KB
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
'use strict'
const rawInput = []
// The actual input
rawInput[0] = require('./data/day_13')
// The 1-st example
rawInput[1] = `939
7,13,x,x,59,x,31,19`
// 7,13,x,x,59,x,31,19`
// The 2-nd example
rawInput[2] = ``
let input = rawInput[1].split('\n')
const time0 = input[0] * 1
let ids = input[1].split(',').map(s => s === 'x' ? 0 : s * 1)
// console.log(ids)
const q1 = () => {
const buses = ids.filter(Boolean)
const next = []
for (let i = 0, t; (t = buses[i]) !== undefined; ++i) {
while (t < time0) t += buses[i]
next.push([t - time0, i])
}
next.sort((a, b) => a[0] - b[0])
return next[0][0] * buses[next[0][1]]
}
console.log('Q1', q1())
// This solution worked with sample data, but never made it with real data.
// I tried some tricks to speed up this brute-force sh*t, but with no success.
// The right stuff is q22() below. It's amazing!
const q2 = () => {
let t = 0, found, t1, v
do {
for (let i = 0; (v = ids[i]) !== undefined; ++i) {
t1 = t + i
if (v !== 0 && (t1 % ids[i]) !== 0) {
t += 1
break
}
}
if (v === undefined) {
found = t
}
} while (found === undefined)
return found
}
// A working solution:
// Absolutely beautiful code by @augmented-warlock
// https://www.reddit.com/r/adventofcode/comments/kc4njx/2020_day_13_solutions/
const q22 = () => {
const buses = ids.map((id, seq) => id && { id, seq }).filter(Boolean)
let time = 0
let multiplier = buses[0].id
let unsatisfied = 1
let next
while (unsatisfied < buses.length) {
time += multiplier
next = buses[unsatisfied]
if ((time + next.seq) % next.id === 0) {
multiplier *= next.id
// The current bus will match all the further time values,
// because of its `id` is a factor in repetition and
// all this starts from the current initial match!
unsatisfied++
}
}
return time
}
console.log('\nQ2', q22())