Szathmáry László honlapja @ DEIK

AoC2017, Day 12, Part 1 (Digital Plumber)

A rendszerünkön számos program fut, melyek csővezetékeken (pipes) keresztül kommunikálnak egymással. A legtöbb program nincs közvetlen kapcsolatban egymással, hanem az üzeneteket a csővezetékek hálózatán juttatják el egymáshoz.

Minden program rendelkezik egy egyedi azonosítóval (PID), ami egy egész szám.

Minden csővezeték kétirányú, vagyis ha pl. a 8-as azonosítóval rendelkező program képes üzenetet küldeni a 11-esnek, akkor ez fordítva is igaz: a 11-es is képes kommunikálni a 8-assal.

A feladat bemenete a feltérképezett csővezeték-hálózatot tartalmazza, vagyis mely program mely más programmal (vagy programokkal) van közvetlenül összekötve. A feladat az lesz, hogy állapítsuk meg, hogy hány program tartozik abba a csoportba, amelynek része a 0-s azonosítóval rendelkező program (más szóval: a 0-s program összesen hány programmal tud közvetve vagy közvetlenül kommunikálni [beleértve önmagát is]).

Tekintsük a következő bemenetet:

0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5

Ebben a példában a következő programok tartoznak a 0-s program csoportjába:

Maga a 0-s program (definíció szerint).
A 2-es program közvetlenül csatlakozik a 0-shoz.
A 3-as program, a 2-esen keresztül.
A 4-es program, a 2-esen keresztül.
Az 5-ös program a 6-oson, majd 4-esen, majd a 2-esen keresztül.
A 6-os program a 4-esen, majd a 2-esen keresztül.

A válasz: összesen 6 program tartozik a 0-s program csoportjába. A példában egyedül az 1-es nem tartozik ide, ami csak önmagával áll kapcsolatban.

A feladat bemenete innen tölthető le. A feladat eredeti kiírása itt olvasható el.

20180308a