[Advent of Code 2024] Day 12: Garden Groups

この記事は、[mae616 Advent of Code Advent Calendar 2024](https://qiita.com/advent-calendar/2024/mae616) の12日目の記事です。

https://qiita.com/advent-calendar/2024/mae616

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

------

前の日: [[Advent of Code 2024] Day 11: Plutonian Pebbles](https://qiita.com/mae616/items/b6f4c5331188937ea314)
次の日: [[Advent of Code 2024] Day 13: Claw Contraption](https://qiita.com/mae616/items/aa4619b1b71d52ba2df4)

# 今日のお題

https://adventofcode.com/

https://adventofcode.com/2024/day/12

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

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

> 食べ物はたくさんあるので、歴史学者たちは食べながら探しています。
>
> 複雑に配置された庭の区画の近くで座ろうとした時、エルフたちが手を貸してくれないかと頼んできました。彼らは各庭の区画に囲いを設置したいのですが、<INS>必要な囲いの量やその費用がわかりません</INS>。彼らはあなたに庭の区画の地図（あなたのパズルの入力）を渡してきました。
>
> 各庭の区画は、1種類の植物しか育てておらず、その植物の種類は地図上の1文字で示されています。同じ種類の植物が複数の区画で育っていて、しかもそれらの区画が隣接している（横または縦に）場合、それらは1つの『地域』を形成します。

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

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/435274/213f79df-886a-9509-3e0a-2772f049ccf0.png" width=600>

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

# 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` が周囲の長さになります。

囲いの価格は、その『地域』の<INS>面積</INS>と<INS>周囲の長さ</INS>を掛け合わせて求めます。
上記の例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` です。
>
> あなたの地図上のすべての地域の囲いの総価格はいくらですか？

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

## 解いたコード
```js: ./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"));
```
周囲の長さの計算が今までやったことがなかったので、戸惑っちゃいましたね٩( ᐛ )و

https://github.com/mae616/adventOfCode2024/tree/main/day12_1

下記で実行できます。
```zsh: 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` になります。
> 
> 新しい合計価格はいくらですか？

## 解いたコード
```js: ./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://github.com/mae616/adventOfCode2024/tree/main/day12_2

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

---

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

では、また明日。