这是一个每年 12 月举办的编程活动，每天都会开放一个程序设计题，不过只有一个样例，而且没有任何语言和时间复杂度的限制，只要算对答案就可以了。每道题有两个部分，附带圣诞节主题的小剧情。总体来说活动性质偏娱乐，所以难度不算太高。可以用它来熟悉一些新语言，我用的是 JavaScript。

传送门：https://adventofcode.com/

今年一共放出了 12 道题目，没做出来的题目有第九天和第十天的 Part 2，以及最后一天所有部分。可以看到后面会逐渐开始上强度。

Day 1: Secret Entrance

Part 1

求最终值为 0 的次数，比较简单。L 代表减，R 代表加，对最终结果求模判断一下就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => [item.slice(0, 1), Number(item.slice(1))]);

let curr = 50;
const ans = data.reduce((acc, item) => {
  curr = (((item[0] === "L" ? curr - item[1] : curr + item[1]) % 100) + 100) % 100;
  return curr === 0 ? acc + 1 : acc;
}, 0);

console.log(ans);
// 1154

Part 2

求转动过程中经过刻度 0 的总次数。

稍微转换了下思路，每经过一个 100 的倍数，都相当于经过一次 0 刻度，计算完之后再取模，转换成最终所在的刻度

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
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => [item.slice(0, 1), Number(item.slice(1))]);

let curr = 50;
const ans = data.reduce((acc, item) => {
  if (item[0] === "L") {
    if (curr === 0) {
      curr -= item[1];
      acc += -Math.trunc(curr / 100);
    } else {
      curr -= item[1];
      if (curr <= 0) acc += 1 - Math.trunc(curr / 100);
    }
  } else {
    curr += item[1];
    acc += Math.trunc(curr / 100);
  }
  curr = ((curr % 100) + 100) % 100;
  return acc;
}, 0);

console.log(ans);
// 6819

Day 2: Gift Shop

Part 1

重复两次的字符串组成的数字被视为无效数字，求出区间内无效数字之和。

首先奇数长度的数字肯定是有效的，字符串重复两次怎么都是偶数嘛。对于偶数长度的数字，只要判断前半段字符串和后半段是否相等就可以了。这样的判断对于奇数同样有效，所以可以省掉判断奇偶的步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split(",")
  .map(item => item.split("-").map(value => Number(value)));

const ans = data.reduce((acc, item) => {
  let sum = 0;
  for (let i = item[0]; i <= item[1]; i++) {
    const s = i.toString();
    const halfLength = Math.floor(s.length / 2);
    if (s.slice(0, halfLength) === s.slice(halfLength)) {
      sum += i;
    }
  }
  return acc + sum;
}, 0);

console.log(ans);
// 13108371860

Part 2

这下不强制要求重复两次了，只要能被一个重复字符串拼接出来都被视为无效数字。枚举一下子字符串长度就可以了

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
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split(",")
  .map(item => item.split("-").map(value => Number(value)));

const isValid = (s, l) => {
  if (s.length % l !== 0) return false;
  for (let i = 0; i < s.length; i += l) {
    if (s.slice(i, i + l) !== s.slice(0, l)) {
      return false;
    }
  }
  return true;
};

const ans = data.reduce((acc, item) => {
  let sum = 0;
  for (let i = item[0]; i <= item[1]; i++) {
    const s = i.toString();
    for (let j = 1; j <= Math.floor(s.length / 2); j++) {
      if (!isValid(s, j)) continue;
      sum += i;
      break;
    }
  }
  return acc + sum;
}, 0);

console.log(ans);
// 22471660255

Day 3: Lobby

Part 1

找到两个字符拼接成的最大两位数，不能变换顺序，对每个这样的两位数求和。

算是一个贪心吧，找到前 n - 1 个字符中最大的一个，保留最后一个防止取不到个位数，同样大取序列较小的。个位数就从这个序列之后的部分中取最大。

1
2
3
4
5
6
7
8
9
10
const data = require("fs").readFileSync("1.txt", "utf-8").split("\n");

const ans = data.reduce((acc, item) => {
  const a = Math.max(...item.slice(0, -1));
  const b = Math.max(...item.slice(item.indexOf(a) + 1));
  return acc + a * 10 + b;
}, 0);

console.log(ans);
// 17316

Part 2

同样的要求，不过现在变成 12 个字符了。

乍一看很唬人，其实是同样的策略，不过需要注意一下边界条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const data = require("fs").readFileSync("1.txt", "utf-8").split("\n");

const ans = data.reduce((acc, item) => {
  let sum = 0, pos = 0;
  for (let i = 1; i <= 12; i++) {
    const subItem = i !== 12 ? item.slice(pos, i - 12) : item.slice(pos);
    const value = Math.max(...subItem);
    pos += subItem.indexOf(value) + 1;
    sum = sum * 10 + value;
  }
  return acc + sum;
}, 0);

console.log(ans);
// 171741365473332

Day 4: Printing Department

Part 1

暴力穷举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => [".", ...item, "."]);

const width = data[0].length;
const height = data.length;

data.unshift(Array(width).fill("."));
data.push(Array(width).fill("."));

let ans = 0;
const dir = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];

for (let i = 1; i <= height; i++) {
  for (let j = 1; j <= width - 2; j++) {
    if (data[i][j] === ".") continue;
    const num = dir.reduce((acc, item) => (data[i + item[0]][j + item[1]] === "@" ? acc + 1 : acc), 0);
    ans += num < 4;
  }
}

console.log(ans);
// 1419

Part 2

跟 Part 1 一样，套一层循环就好了

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
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => [".", ...item, "."]);

const width = data[0].length;
const height = data.length;

data.unshift(Array(width).fill("."));
data.push(Array(width).fill("."));

let ans = 0, sum;
const dir = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];

do {
  sum = 0;
  const x = [];
  for (let i = 1; i <= height; i++) {
    for (let j = 1; j <= width - 2; j++) {
      if (data[i][j] === ".") continue;
      const num = dir.reduce((acc, item) => (data[i + item[0]][j + item[1]] === "@" ? acc + 1 : acc), 0);
      if (num >= 4) continue;
      sum++;
      x.push([i, j]);
    }
  }
  ans += sum;
  x.forEach(item => (data[item[0]][item[1]] = "."));
} while (sum !== 0);

console.log(ans);
// 8739

Day 5: Cafeteria

Part 1

找给定数据中不在有效区间内的数据总量。

一开始想直接用集合，结果爆栈了，然后想到只要枚举所有区间就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const fs = require("fs");

const data = fs
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => item.split("-").map(value => Number(value)));

const question = fs
  .readFileSync("2.txt", "utf-8")
  .split("\n")
  .map(item => Number(item));

const ans = question.reduce((acc, value) => (data.some(item => value >= item[0] && value <= item[1]) ? acc + 1 : acc), 0);
console.log(ans);
// 607

Part 2

求区间内有效数据的总量

其实就是合并区间的问题，直接上双重循环，有交集就合并，否则直接下一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const fs = require("fs");

const data = fs
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => item.split("-").map(value => Number(value)));

let ans = 0;
for (let i = 0; i < data.length; i++) {
  for (let j = i + 1; j < data.length; j++) {
    if (data[j][0] > data[i][1] || data[j][1] < data[i][0]) continue;
    data[i][0] = Math.min(data[i][0], data[j][0]);
    data[i][1] = Math.max(data[i][1], data[j][1]);
    data.splice(j, 1);
    j = i;
  }
  ans += data[i][1] - data[i][0] + 1;
}

console.log(ans);
// 342433357244012

Day 6: Trash Compactor

Part 1

这一天的题目挺有意思的。

这一部分让我们竖着算，虽然有点反直觉，不过调一调还是能写出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map((item, index) =>
    item
      .split(" ")
      .filter(value => value !== "")
      .map(value => (index === 4 ? value : Number(value)))
  );

let ans = 0;
for (let i in data[0]) {
  ans += data[4][i] === "+" 
    ? data[0][i] + data[1][i] + data[2][i] + data[3][i]
    : data[0][i] * data[1][i] * data[2][i] * data[3][i];
}

console.log(ans);
// 4309240495780

Part 2

仍然是竖着算，不过要精确到每一位了。只好自己把竖式掰成横的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const raw = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => [...item]);

const data = [];
for (let i in raw[0]) {
  if (raw[4][i] !== " ") data.push([raw[4][i], []]);
  let num = 0;
  for (let j = 0; j < 4; j++) {
    if (raw[j][i] === " ") continue;
    num = num * 10 + Number(raw[j][i]);
  }
  num !== 0 && data.at(-1)[1].push(num);
}

const ans = data.reduce(
  (acc, item) => acc + (item[0] === "+" ? item[1].reduce((acc, item) => acc + item, 0) : item[1].reduce((acc, item) => acc * item, 1)),
  0
);
console.log(ans);
// 9170286552289

Day 7: Laboratories

Part 1

用集合模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const data = require("fs").readFileSync("1.txt", "utf-8").split("\n");

let ans = 0;
const st = new Set().add(data[0].indexOf("S"));
for (let i = 2; i < data.length; i += 2) {
  st.forEach(index => {
    if (data[i][index] === ".") return;
    st.add(index + 1);
    st.add(index - 1);
    st.delete(index);
    ans++;
  });
}

console.log(ans);
// 1585

Part 2

直接 dfs 时间复杂度会拉到指数级，需要配合记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const data = require("fs").readFileSync("1.txt", "utf-8").split("\n");

const d = {};
const dfs = (pos, layer) => {
  if (layer >= data.length) return 1;
  if (d[`${layer}-${pos}`]) return d[`${layer}-${pos}`];
  d[`${layer}-${pos}`] = data[layer][pos] === "." ? dfs(pos, layer + 2) : dfs(pos - 1, layer + 2) + dfs(pos + 1, layer + 2);
  return d[`${layer}-${pos}`];
};

const ans = dfs(data[0].indexOf("S"), 2);

console.log(ans);
// 16716444407407

Day 8: Playground

Part 1

存储每个接线盒之间的距离并排序，然后使用并查集

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
let data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => item.split(",").map(value => Number(value)));

let d = {};
const size = data.length
for (let i = 0; i < size; i++) {
  for (let j = i + 1; j < size; j++) {
    d[`${i}-${j}`] = Math.hypot(data[i][0] - data[j][0], data[i][1] - data[j][1], data[i][2] - data[j][2]);
  }
}

d = Object.entries(d)
  .sort((a, b) => a[1] - b[1])
  .map(item => [item[0].split("-").map(value => Number(value)), item[1]]);

class Unionfind {
  constructor(n) {
    this.p = Array.from({ length: n }, (_, index) => index);
  }
  query(x) {
    return this.p[x] == x ? x : (this.p[x] = this.query(this.p[x]));
  }
  merge(x, y) {
    this.p[this.query(x)] = this.query(y);
  }
}

const uf = new Unionfind(size);
for (let i = 0; i < 1000; i++) {
  const [a, b] = d[i][0];
  uf.merge(a, b);
}

let cnt = Array(size).fill(0);
for (let i = 0; i < size; i++) {
  cnt[uf.query(i)]++;
}

cnt = cnt.sort((a, b) => b - a)
console.log(cnt[0] * cnt[1] * cnt[2])
// 153328

Part 2

继续按照原来的方式连线直到所有接线盒都在一个集合内

有一个坑点是如果两个盒本来就在一个集合内，则不需要累加到答案中

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
let data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => item.split(",").map(value => Number(value)));

let d = {};
const size = data.length;

for (let i = 0; i < size; i++) {
  for (let j = i + 1; j < size; j++) {
    d[`${i}-${j}`] = Math.hypot(data[i][0] - data[j][0], data[i][1] - data[j][1], data[i][2] - data[j][2]);
  }
}

d = Object.entries(d)
  .sort((a, b) => a[1] - b[1])
  .map(item => [item[0].split("-").map(value => Number(value)), item[1]]);

class Unionfind {
  constructor(n) {
    this.p = Array.from({ length: n }, (_, index) => index);
  }
  query(x) {
    return this.p[x] == x ? x : (this.p[x] = this.query(this.p[x]));
  }
  merge(x, y) {
    this.p[this.query(x)] = this.query(y);
  }
}

let ans;
const cnt = Array(size).fill(1);
const uf = new Unionfind(size);
for (let i = 0; ; i++) {
  const [a, b] = d[i][0];
  if (uf.query(a) === uf.query(b)) continue;

  const num = cnt[uf.query(a)] + cnt[uf.query(b)];
  uf.merge(a, b);
  cnt[uf.query(a)] = num;

  if (i >= 1000 && num >= size) {
    ans = data[a][0] * data[b][0];
    break;
  }
}

console.log(ans);
// 6095621910

Day 9: Movie Theater

Part 1

穷举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => item.split(",").map(value => Number(value)));

let ans = 0;
for (let i = 0; i < data.length; i++) {
  for (let j = i + 1; j < data.length; j++) {
    ans = Math.max(ans, Math.abs((data[i][0] - data[j][0] + 1) * (data[i][1] - data[j][1] + 1)))
  }
}

console.log(ans);
// 4774877510

Day 10: Factory

Part 1

注意到最优解法每个按钮最多只按一次，故使用位运算

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
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => [
    item
      .slice(1, item.indexOf("]"))
      .split("")
      .map(value => Number(value === "#")),
    item
      .slice(item.indexOf("("), item.lastIndexOf(")") + 1)
      .split(" ")
      .map(value =>
        value
          .slice(1, -1)
          .split(",")
          .map(v => Number(v))
      ),
  ]);

const ans = data.reduce((acc, item) => {
  let minn = Infinity;
  const [target, btns] = item;
  for (let i = 0; i < 1 << btns.length; i++) {
    const tmp = Array(target.length).fill(0);
    let cnt = 0;
    for (let j = 0; j < btns.length; j++) {
      if (((i >> j) & 1) === 0) continue;
      for (let k = 0; k < btns[j].length; k++) {
        tmp[btns[j][k]] ^= 1;
      }
      cnt++;
    }
    if (!tmp.some((item, index) => item !== target[index])) {
      minn = Math.min(cnt, minn);
    }
  }
  return acc + minn;
}, 0);

console.log(ans);
// 438

Day 11: Reactor

Part 1

因为是 DAG，所以直接搜索就可以。代码跟第七天 Part 2 差不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => [item.slice(0, 3), item.slice(5).split(" ")]);

const d = {};

const dfs = p => {
  if (p === "out") return 1;
  if (d[p]) return d[p];

  d[p] = 0;
  const idx = data.findIndex(item => item[0] === p);

  data[idx][1].forEach(item => {
    d[p] += dfs(item);
  });
  return d[p];
};

const ans = dfs("you");

console.log(ans);
// 758

Part 2

要求路径必须经过两个中间点。对是否经过这两点进行状态压缩，通过 mask 进行状态传递

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
const data = require("fs")
  .readFileSync("1.txt", "utf-8")
  .split("\n")
  .map(item => [item.slice(0, 3), item.slice(5).split(" ")]);

const d = {};

const dfs = (p, mask) => {
  if (p === "out") return mask === 3 ? 1 : 0;

  d[p] ??= Array(4).fill(undefined);
  if (d[p][mask] !== undefined) return d[p][mask];

  d[p][mask] = 0;
  const idx = data.findIndex(item => item[0] === p);
  
  data[idx][1].forEach(item => {
    if (item === "dac") d[p][mask] += dfs(item, mask | 1);
    else if (item === "fft") d[p][mask] += dfs(item, mask | 2);
    else d[p][mask] += dfs(item, mask);
  });
  return d[p][mask];
};

const ans = dfs("svr", 0);
console.log(ans);
// 490695961032000

总结

这次活动总的来说学到了不少新东西，不过最大的收获倒不是巩固了算法知识，而是对 JavaScript 这个语言更加熟悉了。了解了浅拷贝的逆天机制，函数传参直接影响原变量的精妙设计，还有两个相同数组不一定取等的神秘构思。也算是理解为什么那么多人讨厌 JavaScript。不过好的一面也是存在的，比如说各种方便的现成函数，简单易用的数据结构等等。有种又爱又恨的感觉。

没做出来的题目，以后有时间的话可能会补。不过按照我的性格大概率没机会就是了（笑