#9: http://pastebin.com/g7zP0KHp
#10: http://pastebin.com/0dGiX3qR

#11: http://pastebin.com/X7f21ngV | http://pastebin.com/LkQsLJtW | http://pastebin.com/F94StciK

Egy kis magyarázat:
Az első link az Welltype-os, de sajnos nagyon lassan futott. Elkapott az agyfasz, átírtam C++ra, viszont optimalizáltam deque-re. A második rész ezek után piece of cake volt.

Érdekesség veszi körül ezt a függvényt és a felhasználását:

Ki jön rá, hogy ez mit csinál, és miért jó az?

Tanulság:
Az AoC kiváló, hogy a nyelv problémáit (jelen esetben adatszerkezeteit) felderítsem.
Persze az őrület határából a C++ hozott vissza.

This post was edited by Jason89 on Dec 11 2016 01:12pm

A "&" jelen esetben konkatenál?

huh? nope... bitwise-and

és a << >>?

<< bit shift left
>> bit shift right

és mielőtt kérdeznéd
| bitwise or

engem érdekel a megoldás, de nem sikerült rájönnöm. bár sosem voltam jó bitműveletekből

A feladat szempontjából egy teljes szintet optimalizál. A már meglátogatott állapotokat célzott kiszűrni, amit a digest (kivonat) segítégével oldok meg. A digest-ek set-ben tárolódnak.
Na már most, ezt a két állapotot ekvivalensnek tekintjük:

és


Egy szintről egy bitminta készül, hogy mi van ott. A páros bitek a generátorok, a páratlan bitek a chip-ek. A fenti példa bitmintája:
0110
1001
(Az egyszerűség kedvéért, csak két szint van, és csak egy elem, azaz egy generátor és egy chip.)
A két bitminta teljesen különböző, mégis ekvivalens.
Mi lenne, ha inkább úgy számolnánk, hogy egy bit az "A" kacatjaiból? Tehát, ha van egy chip: 01; ha van egy generátor: 01; ha mindkettő: 11; ha egyiksincs: 00.
Ebből adódik a következő táblázat:

Vagyis ezt szeretnénk eljátszani az összes bit-párral.

Hogy is van a bitműveletek táblázata?

(Megj.: a táblázatot direkt jó sorrendben állítottam össze.)

Csak a chip-ek bitjei: x & 0b01_0101_0101 (0x155)
Csak a generátorok bitjei: x & 0b10_1010_1010 (0x2AA)

Megoldás: a páratlan bitet úgy állítom elő, hogy össze-és-elem az eredeti bitet a páros bittel (amit fel kell shift-eljek eggyel).

A páros biteket úgy állítom elő, hogy összevagyolom a chip bit-jét az eggyel le-shift-elt generátor bittel:
[code]ms | (gs >> 1)[/code]

Ezek után az eredményt össze kell vagy-olni, tehát bitenként egyesíteni.
[code](gs & (cs << 1)) | (cs | (gs >> 1))[/code]

Az egész szépségét az adja, hogy mind az 5 félére egyszerre csinálja meg. A part2 esetén mind a 7-re egyszerre.

Kiegészítés:

1.
Az, hogy egy bit-et használok kacatonként, az tulajdonképpen az 1-es alapú számrendszernek felel meg. Nagyjából.

2.
Azért jó ez, mert így a keresési térből nem csak az identikusakat (van ilyen magyar szó?) zárja ki, hanem az ekvivalenseket is. Enélkül a keresési tér még jobban felrobbanna.

3.
Ezeket miért nem rakta kód-ba?

[...]
A páros biteket úgy állítom elő, hogy összevagyolom a chip bit-jét az eggyel le-shift-elt generátor bittel:


Ezek után az eredményt össze kell vagy-olni, tehát bitenként egyesíteni.


Az egész szépségét az adja, hogy mind az 5 félére egyszerre csinálja meg. A part2 esetén mind a 7-re egyszerre.

This post was edited by Jason89 on Dec 11 2016 01:54pm

#12: http://pastebin.com/NXPdxLg2

Azért ez a mai sokkal üdítőbb volt.
Eddig ez a kedvenc feladatom.