この記事は、mae616 Advent of Code Advent Calendar 2024 の12日目の記事です。

このアドベントカレンダーは皆勤賞のQiitaくんのぬいぐるみに惹かれて挑戦している大変ゆるい挑戦のものです。そんな感じで読んでいただければ幸いです。

前の日: [Advent of Code 2024] Day 11: Plutonian Pebbles
次の日: [Advent of Code 2024] Day 13: Claw Contraption

今日のお題

12日目の物語

■ 12日目: 庭のグループ
『庭師』とその『広大な農場』の近くで主任歴史学者を探してみてます。

『庭師』と『広大な農場』は、Advent of Code 2023と繋がってるみたいですね。

食べ物はたくさんあるので、歴史学者たちは食べながら探しています。

複雑に配置された庭の区画の近くで座ろうとした時、エルフたちが手を貸してくれないかと頼んできました。彼らは各庭の区画に囲いを設置したいのですが、必要な囲いの量やその費用がわかりません。彼らはあなたに庭の区画の地図（あなたのパズルの入力）を渡してきました。

各庭の区画は、1種類の植物しか育てておらず、その植物の種類は地図上の1文字で示されています。同じ種類の植物が複数の区画で育っていて、しかもそれらの区画が隣接している（横または縦に）場合、それらは1つの『地域』を形成します。

今日も graph 問題なのかな٩( ᐛ )و
ちなみにまた、画像生成AIでエルフを生成しました ꉂꉂ( ᐛ )

かわいいですね。
いってみましょう٩( ᐛ )و

1問目

例1:
AAAA
BBCD
BBCC
EEEC
この4x4の配置には、5種類の異なる植物（A, B, C, D, E）が育っている庭の区画が含まれており、それぞれが自分の『地域』にグループ化されています。

この例の場合、各地域の周囲を視覚的に示すために、- と | を使って区画の辺を示すと、上記の地図では各『地域』の周囲の長さが次のように測定されます：
+-+-+-+-+
|A A A A|
+-+-+-+-+     +-+
              |D|
+-+-+   +-+   +-+
|B B|   |C|
+   +   + +-+
|B B|   |C C|
+-+-+   +-+ +
          |C|
+-+-+-+   +-+
|E E E|
+-+-+-+

うーん。まあ要は、例えば

🌽🌽🌽🌽
🍆🍆🥕🥒
🍆🍆🥕🥕
🥬🥬🥬🥕

A...🌽(とうもろこし)
B...🍆(なす)
C...🥕(にんじん)
D...🥒(きゅうり)
E...🥬(キャベツ)
を育ててる庭のある区画があって、育ててる植物ごとに囲いをつけたい。

A: 🌽(とうもろこし) の『地域』は下記になる。

🌽🌽🌽🌽
❓❓❓❓
❓❓❓❓
❓❓❓❓

B: 🍆(なす) の『地域』は下記になる。

❓❓❓❓
🍆🍆❓❓
🍆🍆❓❓
❓❓❓❓

C: 🥕(にんじん) の『地域』は下記になる。

❓❓❓❓
❓❓🥕❓
❓❓🥕🥕
❓❓❓🥕

D: 🥒(きゅうり) の『地域』は下記になる。

❓❓❓❓
❓❓❓🥒
❓❓❓❓
❓❓❓❓

E: 🥬(キャベツ) の『地域』は下記になる。

❓❓❓❓
❓❓❓❓
❓❓❓❓
🥬🥬🥬❓

それぞれの『地域』の形から囲いをつけるとしたら下記の形になる。

+-+-+-+-+
|🌽🌽🌽🌽|
+-+-+-+-+     +-+
              |🥒|
+-+-+   +-+   +-+
|🍆🍆|   |🥕|
+   +   + +-+
|🍆🍆|   |🥕🥕|
+-+-+   +-+ +
          |🥕|
+-+-+-+   +-+
|🥬🥬🥬|
+-+-+-+

同じ種類の植物は複数の別々の『地域』に現れることがあり、『地域』は他の『地域』の中に含まれることさえあります。
例2:
OOOOO
OXOXO
OOOOO
OXOXO
OOOOO

下記みたいな感じでしょうかね。

🌽🌽🌽🌽🌽
🌽🥕🌽🥕🌽
🌽🌽🌽🌽🌽
🌽🥕🌽🥕🌽
🌽🌽🌽🌽🌽

4つの🥕( X ) の『地域』は面積 1 で周囲の長さは 4 (辺 1 * 4) です。
🌽( O ) の『地域』は、外周の長さが 20 (辺 5 * 4)
↓外周

+-+-+-+-+-+
|🌽🌽🌽🌽🌽|
+        　+
|🌽🥕🌽🥕🌽|
+        　+
|🌽🌽🌽🌽🌽|
+        　+
|🌽🥕🌽🥕🌽|
+        　+
|🌽🌽🌽🌽🌽|
+-+-+-+-+-+

外周の長さ 20 に、4つの🥕( X ) の『地域』(周囲の長さは 4 )が加わり、20 + (4 * 4) = の 36 が周囲の長さになります。

囲いの価格は、その『地域』の面積と周囲の長さを掛け合わせて求めます。
上記の例2では、整理すると、

🌽( O ) の『地域』の周囲の長さは 36
🥕( X ) の『地域』の周囲の長さは 4
🌽( O ) の『地域』の面積は？
→ 🌽( O ) の文字数を数えると 21 です
🥕( X ) の『地域』の面積は？
→ 1つの 🥕( X ) の『地域』の文字数を数えると 1 です

21 * 36 = 756 (🌽: O の面積 * 周囲の長さ) 1 * 4 = 4 (🥕: X の面積 * 周囲の長さ)
756 + 4 + 4 + 4 + 4 = (🥕( X ) の『地域』は 4 つ) の 772 が総価格になります。

例1に戻りましょうか。

例1:

AAAA
BBCD
BBCC
EEEC

+-+-+-+-+
|A A A A|
+-+-+-+-+     +-+
              |D|
+-+-+   +-+   +-+
|B B|   |C|
+   +   + +-+
|B B|   |C C|
+-+-+   +-+ +
          |C|
+-+-+-+   +-+
|E E E|
+-+-+-+

なので、

地域Aは、価格が 4 (面積) * 10 (周囲の長さ) = 40
地域Bは、価格が 4 (面積) * 8 (周囲の長さ) = 32
地域Cは、価格が 4 (面積) * 10 (周囲の長さ) = 40
地域Dは、価格が 1 (面積) * 4 (周囲の長さ) = 4
地域Eは、価格が 3 (面積) * 8 (周囲の長さ) = 24

40 + 32 + 40 + 4 + 24 = の総価格は 140 になります。

例3(大きな例)です。

RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE

これには次のものが含まれます：

R植物の地域、価格は 12 * 18 = 216
I植物の地域、価格は 4 * 8 = 32
C植物の地域、価格は 14 * 28 = 392
F植物の地域、価格は 10 * 18 = 180
V植物の地域、価格は 13 * 20 = 260
J植物の地域、価格は 11 * 20 = 220
C植物の地域、価格は 1 * 4 = 4
E植物の地域、価格は 13 * 18 = 234
I植物の地域、価格は 14 * 22 = 308
M植物の地域、価格は 5 * 12 = 60
S植物の地域、価格は 3 * 8 = 24

したがって、総価格は 1930 です。

あなたの地図上のすべての地域の囲いの総価格はいくらですか？

やってみましょう٩( ᐛ )و

解いたコード

./day12_1

function main(input) {
  const args = input.split("\n");

  const graph = [];
  for (let i = 0; i < args.length; i++) {
    if (args[i] === "") continue;
    graph.push(args[i].split(""));
  }

  const H = graph.length;
  const W = graph[0].length;

  const move = [
    { x: -1, y: 0 }, // left
    { x: 0, y: -1 }, // up
    { x: 1, y: 0 }, // right
    { x: 0, y: 1 }, // down
  ];

  let sum = 0;

  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      if (graph[y][x] === ".") continue;

      let outer = 0;
      let area = 0;
      let target = graph[y][x];
      const visited = new Set();
      (function search(cx, cy) {
        if (graph[cy][cx] !== target) {
          if (!visited.has(`${cx},${cy}`)) outer++;
          return;
        }

        visited.add(`${cx},${cy}`);
        area++;
        graph[cy][cx] = ".";

        for (const m of move) {
          const nx = cx + m.x;
          const ny = cy + m.y;

          if (nx < 0 || nx >= W || ny < 0 || ny >= H) {
            outer++;
            continue;
          }
          search(nx, ny);
        }
      })(x, y);
      sum += area * outer;
    }
  }
  console.log(sum);
}

main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));

周囲の長さの計算が今までやったことがなかったので、戸惑っちゃいましたね٩( ᐛ )و

下記で実行できます。

zsh

$ cd day12_1
$ node main.js

2問目

「"すごい大量に囲いを買うから割引してあげるよ"て感じで、計算方法が変わります」ってことみたいですね。
周囲の長さが変わって、囲いの直線部分はその長さに関係なく1辺としてカウントされるそうです。
なので、

例1:

AAAA
BBCD
BBCC
EEEC

+-+-+-+-+
|A A A A|
+-+-+-+-+     +-+
              |D|
+-+-+   +-+   +-+
|B B|   |C|
+   +   + +-+
|B B|   |C C|
+-+-+   +-+ +
          |C|
+-+-+-+   +-+
|E E E|
+-+-+-+

A の周囲の辺の数は、4 (直線が 4 つ)になり、それぞれの計算は...

地域Aは、価格が 4 (面積) * 4 (周囲の辺の数) = 16
地域Bは、価格が 4 (面積) * 4 (周囲の辺の数) = 16
地域Cは、価格が 4 (面積) * 8 (周囲の辺の数) = 32
地域Dは、価格が 1 (面積) * 4 (周囲の辺の数) = 4
地域Eは、価格が 3 (面積) * 4 (周囲の辺の数) = 12

となり、総価格は 80 になります。

例2:

OOOOO
OXOXO
OOOOO
OXOXO
OOOOO

は、

地域Oは、価格が 21 (面積) * (4 + 4 * 4) (周囲の辺の数) = 420
地域Xの1つは、価格が 1 (面積) * 4 (周囲の辺の数) = 4

84 + 4 * 4 = の 436 です。

この例では:
EEEEE
EXXXX
EEEEE
EXXXX
EEEEE
E字型の領域は面積 17、辺の数 12 で価格は 204 です。
X型植物が満ちた2つの領域を含めると、この地図の合計価格は 236 になります。

例3(大きな例):
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
では、新しい合計価格は 1206 になります。

新しい合計価格はいくらですか？

解いたコード

./day12_2/main.js

function main(input) {
  const args = input.split("\n");

  const graph = [];
  for (let i = 0; i < args.length; i++) {
    if (args[i] === "") continue;
    graph.push(args[i].split(""));
  }

  const H = graph.length;
  const W = graph[0].length;

  const move = [
    { label: "left", x: -1, y: 0 },
    { label: "up", x: 0, y: -1 },
    { label: "right", x: 1, y: 0 },
    { label: "down", x: 0, y: 1 },
  ];

  let sum = 0;

  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      if (graph[y][x] === ".") continue;

      let area = 0;
      let target = graph[y][x];
      const visited = new Set();
      const side = new Map();
      (function search(cx, cy, label) {
        if (graph[cy][cx] !== target) {
          if (label !== null && !visited.has(`${cx},${cy}`)) {
            saveOuter(label, side, cx, cy);
          }
          return;
        }

        visited.add(`${cx},${cy}`);
        area++;
        graph[cy][cx] = ".";

        for (const m of move) {
          const nx = cx + m.x;
          const ny = cy + m.y;

          if (nx < 0 || nx >= W || ny < 0 || ny >= H) {
            saveOuter(m.label, side, nx, ny);
            continue;
          }
          search(nx, ny, m.label);
        }
      })(x, y);
      const outer = countOuter(side);
      sum += area * outer;
    }
  }
  console.log(sum);
}
function saveOuter(label, side, x, y) {
  if (label === "up" || label === "down") {
    if (side.has(label)) {
      side.get(label).add(`${y}:${x}`);
    } else {
      side.set(label, new Set([`${y}:${x}`]));
    }
  } else {
    if (side.has(label)) {
      side.get(label).add(`${x}:${y}`);
    } else {
      side.set(label, new Set([`${x}:${y}`]));
    }
  }
}

function countOuter(side) {
  let outer = 0;
  for (const set of side.keys()) {
    const array = Array.from(side.get(set));
    array.sort((a, b) => {
      const [i, j] = a.split(":");
      const [k, l] = b.split(":");
      if (i === k) {
        return Number(j) - Number(l);
      } else {
        return Number(i) - Number(k);
      }
    });

    const temp = [];
    for (const current of array) {
      const [i, j] = current.split(":");
      if (!check(temp, Number(i), Number(j))) {
        outer++;
      }
      temp.push(current);
    }
  }
  return outer;
}

function check(ary, i, j) {
  const search = [`${i}:${j - 1}`, `${i}:${j + 1}`];
  for (const s of search) {
    if (ary.includes(s)) {
      return true;
    }
  }
  return false;
}
main(require("fs").readFileSync("./input/puzzle.txt", "utf8"));

今日は終わり٩( ᐛ )و
お疲れさまです。

今日の海外の人
https://www.reddit.com/r/adventofcode/
すごい難しいなと思ったのですが、どうも仲間がいるようです٩( ᐛ )و

では、また明日。