Een kleurendoolhof bestaat uit

• $$m \times n$$ gekleurde cirkels die gerangschikt zijn in een rechthoekig rooster met $$m$$ rijen en $$n$$ kolommen ($$m, n \geq 2$$)

• een kleurenpatroon dat gevormd wordt door een reeks kleuren die achtereenvolgens moet doorlopen worden, waarbij na de laatste kleur terug de eerste kleur volgt

Hieronder staat bijvoorbeeld een kleurendoolhof met een $$5 \times 5$$ rooster van gekleurde cirkels. Het kleurenpatroon geeft in dit geval aan dat je eerst een oranje cirkel moet bezoeken, gevolgd door een groene cirkel, dan weer een oranje cirkel, een groene cirkel, enzoverder.

Een route door het rooster van een kleurendoolhof begint bij een gekleurde cirkel in het rooster en loopt telkens verder naar één van de naburige cirkels ten noorden (N), oosten (E), zuiden (S) of westen (W) van de cirkel. Een route kan meerdere keren langs dezelfde cirkel van het rooster lopen.

De opdracht bestaat erin om de uitweg door het kleurendoolhof te vinden: de kortste route die de onderste rij van het rooster verbindt met de bovenste rij. Daarbij moet de kleur van de eerste cirkel langs de route (op de onderste rij) overeenkomen met de eerste kleur van het kleurenpatroon. De kleur van elke volgende cirkel langs de route moet overeenkomen met de volgende kleur van het kleurenpatroon, waarbij na de laatste kleur terug de eerste kleur van het patroon volgt. Het kleurenpatroon hoeft niet per se volledig tot op het einde afgelopen te worden.

Elk kleurendoolhof is zo opgesteld dat er altijd één uitweg is. Dit is bijvoorbeeld de uitweg door het kleurendoolhof dat we hierboven als voorbeeld gebruikt hebben:

Opgave

We stellen een kleur voor als een hoofdletter (String). Dezelfde kleur wordt steeds voorgesteld als dezelfde hoofdletter. Verschillende kleuren wordt steeds voorgesteld als verschillende hoofdletters.

We stellen een reeks kleuren (en dus ook een kleurenpatroon) voor als een string (String) met hoofdletters die corresponderen met de opeenvolgende kleuren in de reeks.

We stellen een rooster met gekleurde cirkels voor als de reeks kleuren van de cirkels in het rooster, waarbij een rij cirkels van links naar rechts doorlopen wordt en de rijen van boven naar onder doorlopen worden.

Door de rijen (resp. kolommen) van een rooster van boven naar onder (resp. van links naar rechts) te nummeren vanaf 0, kunnen we de positie van een cirkel in het rooster voorstellen als een reeks $$[r, k]$$ (Array), waarbij $$r$$ (Number) het rijnummer en $$k$$ (Number) het kolomnummer aanduidt.

Een route door een kleurendoolhof kunnen we dan voorstellen als een reeks (Array) met posities (Array) van de opeenvolgende cirkels waar de route langs loopt.

Definieer een klasse Doolhof waarmee kleurendoolhoven kunnen voorgesteld worden. Bij het aanmaken van een kleurendoolhof (Doolhof) moet drie argumenten doorgegeven worden: i) het aantal rijen (Number) van het rooster, ii) het rooster met gekleurde cirkels (String) en iii) het kleurenpatroon (String). Daarbij mag ervan uitgegaan worden dat de argumenten een geldig kleurendoolhof met een unieke uitweg beschrijven, zonder dat dit expliciet moet gecontroleerd worden.

Op een kleurendoolhof $$\mathcal{M}$$ (Doolhof) moet je minstens de volgende methoden kunnen aanroepen:

• Een methode kleur waaraan twee natuurlijke getallen $$r$$ (Number) en $$k$$ (Number) moeten doorgegeven worden. De methode moet de kleur (String) van de cirkel op positie $$[r, k]$$ in het rooster van $$\mathcal{M}$$ teruggeven. De methode mag ervan uitgaan dat de argumenten een positie binnen het rooster aanduiden, zonder dat dit expliciet moet gecontroleerd worden.

• Een methode route waaraan twee argumenten moeten doorgegeven worden: i) de positie $$[r, k]$$ (Array) van een cirkel in het rooster van $$\mathcal{M}$$ en ii) een string (String) met hoofdletters die richtingen aanduiden: noord (N), oost (E), zuid (S) of west (W). De methode moet de route (Array) door het rooster van $$\mathcal{M}$$ teruggeven die begint bij de cirkel op positie $$[r, k]$$ en telkens in de volgende richting loopt naar een naburige gekleurde cirkel. De methode mag ervan uitgaan dat de argumenten een geldige route door het rooster aanduiden, zonder dat dit expliciet moet gecontroleerd worden.

• Een methode weergave waaraan een route (Array) door het rooster van $$\mathcal{M}$$ moet doorgegeven worden. De methode mag ervan uitgaan dat het argument een geldige route door het rooster vormt, zonder dat dit expliciet moet gecontroleerd worden. De methode moet een stringvoorstelling (String) van het rooster teruggeven, waarvan elke regel correspondeert met een rij van gekleurde cirkels. De opeenvolgende cirkels van een rij worden elk voorgesteld door één karakter, met telkens één spatie tussen die karakters. Een cirkel die op de route ligt, wordt voorgesteld door de kleur van de cirkel. Een cirkel die niet op de route ligt, wordt voorgesteld door een punt (.).

• Een methode uitweg waaraan geen argumenten moeten doorgegeven worden. De methode moet de uitweg (Array) doorheen het rooster van $$\mathcal{M}$$ teruggeven.

  Tip

  De uitweg door een kleurendoolhof kan je vinden met breedte-eerst zoeken¹:

  • bepaal de collectie $$\mathcal{R}_1$$ van alle routes met lengte 1 die starten bij een cirkel op de onderste rij van het rooster waarvan de kleur correspondeert met de eerste kleur van het kleurenpatroon

  • herhaal zolang geen enkele route van $$\mathcal{R}_i$$ ($$i = 1, 2, \ldots$$) eindigt op de bovenste rij van het rooster:

  • bepaal de collectie $$\mathcal{R}_{i+1}$$ van routes met lengte $$i+1$$ door elke route met lengte $$i$$ van $$\mathcal{R}_{i}$$ uit te breiden langs elk van de vier mogelijke richtingen die uitkomt bij een cirkel met de $$(i + 1)$$-de kleur van het kleurenpatroon (waarbij we tellen vanaf 1 en na de laatste kleur van het patroon verdergaan met tellen vanaf de eerste kleur)

  • de uitweg is de route van $$\mathcal{R}_{i+1}$$ die eindigt op de bovenste rij van het rooster

Voorbeeld

> let doolhof = new Doolhof(5, "BOROYORBGRBOGOYYGBYGRORBR", "OG")
> doolhof.kleur(4, 1)
"O"
> doolhof.kleur(3, 1)
"G"
> doolhof.kleur(2, 1)
"O"
> doolhof.kleur(2, 2)
"G"
> doolhof.route([4, 1], "NNEE")
[[4, 1], [3, 1], [2, 1], [2, 2], [2, 3]]
> console.log(doolhof.weergave(doolhof.route([4, 1], "NNEE")))
. . . . .
. . . . .
. O G O .
. G . . .
. O . . .
> doolhof.uitweg()
[[4, 1], [3, 1], [2, 1], [2, 2], [2, 3], [1, 3], [0, 3]]
> console.log(doolhof.weergave(doolhof.uitweg()))
. . . O .
. . . G .
. O G O .
. G . . .
. O . . .

> doolhof = new Doolhof(10, "OBYRPORROBRYPPPPGYPRRGOOPOYYYGBOPPGOPBRYYOBRPGRGGPGYBORBRRBGPOPRGPOBRYYORYBRBROYRRRRBOBRBPYOROGRGYOGOYOYBGORROBBBYPGYGOYROBOYBGGGBROYRBBBYRGBPGYGGRPYOOROYBOGBRP", "BRYYO")
> doolhof.route([9, 10], "NWSWNNWNWNESSWSWWNNNNEEENWSWNNEEEEEENN")
[(9, 10), (8, 10), (8, 9), (9, 9), (9, 8), (8, 8), (7, 8), (7, 7), (6, 7), (6, 6), (5, 6), (5, 7), (6, 7), (7, 7), (7, 6), (8, 6), (8, 5), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (4, 5), (4, 6), (4, 7), (3, 7), (3, 6), (4, 6), (4, 5), (3, 5), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10), (2, 11), (1, 11), (0, 11)]
> doolhof.uitweg()
[(9, 10), (8, 10), (8, 9), (9, 9), (9, 8), (8, 8), (7, 8), (7, 7), (6, 7), (6, 6), (5, 6), (5, 7), (6, 7), (7, 7), (7, 6), (8, 6), (8, 5), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (4, 5), (4, 6), (4, 7), (3, 7), (3, 6), (4, 6), (4, 5), (3, 5), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10), (2, 11), (1, 11), (0, 11)]
> console.log(doolhof.weergave(doolhof.uitweg()))
. . . . . . . . . . . Y . . . .
. . . . . . . . . . . Y . . . .
. . . . . B R Y Y O B R . . . .
. . . . . O R B . . . . . . . .
. . . . R Y Y O . . . . . . . .
. . . . B . B R . . . . . . . .
. . . . O . O Y . . . . . . . .
. . . . Y . O Y R . . . . . . .
. . . . Y R B . B Y R . . . . .
. . . . . . . . O Y B . . . . .

Het eerste deel van dit voorbeeld werkt met het kleurendoolhof uit de inleiding. Hieronder zie je de grafische voorstelling van het kleurendoolhof uit in het tweede deel, met een $$10 \times 16$$ rooster en een patroon met 5 kleuren (blauw — rood — geel (2x) — oranje). Klik hier om de unieke uitweg door dit kleurendoolhof weer te gevenKlik hier om de unieke uitweg door dit kleurendoolhof te verbergen.