Ez tetszik:) Bar baromi regen volt, megis mintha remlene, hogy a szabaly a szeleken is illeszkedest kert. Aztan tevedhetek. (Ertsd: ha ugy volt, akkor nem kibovitette, hanem szukitette a szabalyokat, aminek a kirakas megfelel.)
Befértem a 3x3-as részletek véletlenszerű azonosításával 0...3,6*10^11 tartományba, ami 42GB-os adatblokkokat jelent. Ez még mindig messze van a szekvenciális azonosítás <12GB-os blokkjaitól, de ezzel már lehet játszogatni. Kicsi trükkel 36GB is elég lehet... alakul. :)
Legközelebb akkor próbálkozom, ha lesz legalább 200GB RAM-om.
Oda már be tudok pakolni két 2^40 bites táblát némi trükközéssel (mROT transzfer vagy 256GB+).
Kb. 1000-szeres gyorsulás érhető el a táblák közti átjárásnál, de minimális kombó átlapolással számolni kell (0,1% alatt tartható 5x5C, 4x3MClue0 esetén is).
Szia! Szinte már senki nem foglalkozik az EternityII-vel, még a legnagyobb fórum (Yahoo/Eternity_two) is régen kihalt. Az általam ír kód assemblyben készült és kb. ötven alkalommal írtam meg újra és újra. :) Ugyanis mikor az aktuális ötletről kiderült, hogy halott ügy, akkor kidobtam az egészet a kukába. Aztán mikor elég új ötlet gyűlt össze, akkor újraírtam, ugyanis kb. 20 sor a hot spot, az meg a fejemben van. Jelenleg már hónapok óta nem programoztam a témával kapcsolatban. Persze állandóan jönnek újabb és újabb ötletek, de azokról mindig kiderül még a tervezési fázisban, hogy nem elég hatékonyak. Egyébként szívesen segítek, de a "netről letölthető program" kategóriában nem tudok. Olyanokat sosem próbáltam.
Én magam is foglalkoztam a problémával. Még 2010-ben írtam c-ben egy programot, ami backtrack nélkül brute force-olt viszonylag gyenge 35.000 másodpercenkénti próbálkozással. Középről indulva spirálba helyezte fel az elemeket, amíg tudta. Utána kezdte elölről. Kb 5 perc alatt 100 elemet tud így felrakni.
A kérdésem az lenne, hogy melyik a legjobb netről letölthető program, amit tudnék futtatni? Esetleg van még olyan project, ami számítógépek között elosztva dolgozik? (BOINC)
Fekete Ákos: a te megoldásod mennyire "open source"?
Egy kis szemléltető ábra, hogy a két szomszédos szín (2*5 bit) helyetti két szomszédos puzzle+orientáció (2*10 bit) adatra való átállás milyen hatással volt a "sötét zónára".
Az első esetben kb. 115 MB adattal dolgozik a kereső, a másodikban 17GB.
Szerintem logikus a következő lépés, megpróbálkozok a két szomszédos négyes (2*40 bit) kombinációval.
Az adatokkal persze trükközni kell, de előzetes számítások alapján elegendő lehet 128GB RAM.
Sikerült további 10%-kal növelni a lerakási sebességet. Ráadásul mindezt úgy értem el, hogy a soron következő pozícióba lerakható puzzle kiválasztása szigorúbb feltételekkel szűrt listából történik. Ez a feleslegesen bejárandó zsákutcák számát csökkenti, ami szintén sebességnövelő tényező. Megspóroltam az index tábla olvasást, cserébe 4GB memóriát esznek az adatok. Alakul... :D
Öröm látni, hogy még van valaki aki rajtam kívül is foglalkozik a témával. :)
A linken a megoldások nem valódiak, több egyforma elemet is tartalmaznak.
Szvsz. a 6x6-os táblán a 115 milliárd kombinációt a mostani algoritmusom kb. 1 óra alatt bejárná.
Legalábbis 4 éve 2 óra kellett hozzá és azóta még egy kicsit tudtam csiszolni rajta.
A sebességre lentebb lesz még célzás...
Jelenleg 1-1 bittel reprezentálom az adatokat és a back-track algoritmust csak a visszakonvertálásra használom.
A lényeg, hogy a bitmátrixból próbálom kiszűrni az adott helyekre nem lerakható kombinációkat.
A teljes táblát 3x3-as, 3x2-es és 2x3-as csoportokra osztottam fel, így kaptam egy 14x14-es, 14x15-ös és egy 15x14-es táblákat.
Az általad említett 895-ös hozzászólásban látszó képnek megfelelően így nézett ki 2015.02.27-én a 3x3-as tábla:
Ez a 895-ös hozzászólásban látható 1x1-es "kombinációkból" generált állapothoz képest a jelenlegi állapot kb. 15%-kal kevesebb bejegyzést tartalmaz ( ennyi bit lett már nullázva a mátrixban ). Érdekes módon, mikor visszaskálázom az adatokat 1x1-esre, tehát a "895"-ös elrendezésre, akkor még mindig ugyanott vagyok. :) Szeretnék legalább egy puzzle-t kiiktatni valahonnan a triviális eseteken kívül. Azt nem hiszem, hogy valaha is eljutnék a tábla bármely részén ( legvalószínűbb, hogy a bal alsó negyedben a két clue puzzle közti átlón ) egy "összeomlásig". Legalábbis a 3x3-as elemekkel ( kb. 100 milliárd bejegyzés / cella ) biztosan nem lehetséges, de tesztek alapján a 4x4-es sem lenne elég. Talán az 5x5-ös elrendezés (12x12-es tábla). Megjegyzem, hogy a 3x3-as esetén kb. 1 óra a számítási igény a legtöbb cellánál ( mindig, mind a 100 milliárd bejegyzést szépen sorban elő kell állítani, hogy az 1 bit alapján el tudjam dönteni, kell-e még foglalkozni vele vagy sem ). Jelenleg 34,5GB RAM-ot foglal a program és egy 4TB-os merevlemezt. 4x4-es tábla esetén a RAM igényt ezen a szinten lehetne tartani, viszont minden cellához kellene abból a merevlemezből úgy 2-2000 darab ami azt is jelenti, hogy egy cella feldolgozási ideje kb. 390 nap lenne.
A 3x2-es és 2x3-as táblákról csak annyit említenék, hogy ezeket a jóval kisebb méret miatt már majdnem direktbe (átlagosan kb. 15ns alatt) tudom ide-oda konvertálgatni, ami egy érdekes lehetőséget nyitott 5x4-es illetve 4x5-ös méretű szűrőablakok alkalmazásához. Az ablak lehetne nagyobb is, de így kb. 0,2-1,5 óra / cella a szűrőrutin sebessége ami még emberinek tekinthető. Mivel 2x210/420 cellám van, így kb. egy hét alatt fut egy kört a szűrő a mátrixon. Sajna minden körben egyre kevesebb és kevesebb kombináció esik ki ( most, hogy már 15% kibukott, kb. 0,1% / kör a tempó és egyre rosszabb lesz... :( ).
A Clue1-re visszatérve: én előállítottam az összes lehetséges módot [természetesen nem tároltam el őket :) ], és azon az elven dolgoztam, amit a 895ös hozzászólás bal oldali képe mutat. Mindig azt a pozíciót raktam le az összes lehetőségével, ahol ez a legkevesebb. Így minimalizálni tudtam az előállított állapotok számát.
Ezzel a módszerrel 39 gép használatával 483 óra alatt állítottam elő a 115.071.633.408 megoldást. Igen, 1 géppel több mint 2 év lett volna.. :)
A nagy kirakóra ez azért nem az igazi, mert ha az első néhány választás nem jó, akkor egy örökkévalóság, mire visszamegy addig a döntésig, és elindul más irányba.
Amúgy az alábbi oldalt találtam, elvileg ők kapták meg a részeredményért járó jutalmat is:
Figyi, ezt az egesz feladvanyt matematikusok raktak ossze, tehat eselytelen, hogy ennek a belso torvenyszeruseginek ismereteben (vagy anelkul) kitalalt bejarassal lefusson. Ket lehetoseged van:
1. kizarsz bizonyos tipusu megoldasokat (en egy idoben azt akartam volna - ha lett volna idom foglalkozni vele - beepiteni, hogy a darabok felsorolasa az elofordulasuk sorrendjeben van, marmint a szabalyismertetoben vagy hol volt, ez mar eleg jo korlatozast adott volna backtrack-re -- de csak akkor mukodik, ha ott mar feleslegesnek tartottak a tovabbi random-ot, amit nem hiszek, de akkor meg semmi strategia nincs ra, ez egy halovany esely lett volna)
2. ahogy tudtommal az elsot megcsinaltak: kezzel kiraktak egy "valoszinu" reszt, es csak a maradekot kereste'k gepi erovel -- ez meg nyilvan csak akkor mukodik, ha jo a megsejtesedVan egy harmadik esely, hogy nem akarsz szisztematikusan menni, hanem veletlenszeruen allitasz elo sorozatokat, aztan vagy beletalalsz az elejen, vagy nem.
Nyilvan lehet egy csomo elofeldolgozast csinalni, amig a tarhely birja, pl. 2x2-esek vagy 4x4-esek teljes listaja es utana azokat osszehozni. De hidd el, ugy alkottak meg a feladatot, hogy ezek a kitalalhato strategiak tutira NE birkozzanak meg vele. Ezert is csak az 1. szerintibe oltem volna ne'mi energiat, amugy nem hiszem hogy okosabb vagyok azoknal, akik ezt ki_szamoltak_, hogy egy nyereseges uzlet lesz.
Latom mar kicsit lecsengett az Eternity orulet es a forum is pihen. :) Mivel mar nem lehet penzt nyerni a dologgal, arra gondoltam megkerdem: nincs meg valakinek az osszes hint? Az 1-es es 2-es clue puzzle-t kiraktam, es be is kuldtem, de a 3-ast es 4-est nem lehetett itthon beszerezni es mar a oldal sem el ahova a megoldasokat be lehetne kuldeni... Nincs meg valakinek a 3-as es 4-es hint puzzle szama es orientacioja?
