Eternity II: Masz ochotę na 2 miliony dolarów?
2008-11-20, Czwartek 22:12:57 +0100, autor Karol „Zal” Zalewski, licencja LPRCTKC
Wystarczy, że ułożysz kwadrat 16 na 16 z 256 puzzli Eternity II, a staniesz się szczęśliwym posiadaczem 2 milionów dolarów. Proste, prawda?
Tomasz Dobrowolski (doktorant, dawny Sferowicz i twórca MoonEdita) zainicjował akcję, której efektem jest nie tylko podjęcie wyzwania przez Katedrę Algorytmów i Modelowania Systemów (KAiMS) na WETI PG, ale również poniższa prezentacja multimedialna znajdująca się w nowym gmachu WETI.
A przy okazji, w tle, widać promocję Koła Naukowego "Sfera" ;-D Zainteresowanie studentów było na tyle duże, iż nawet późnym wieczorem przed planszą zbierały się spore ich grupy dyskutując nad tym "banalnym" problemem. Oczywiście, z samym problemem mogą również zmierzyć się studenci, o czym poczytać można na stronie Tomasza.
PS. Obecnie spotkania Sfery odbywają się w starym gmachu WETI w sali 245 we wtorki o godzinie 1800.
2008-11-21, Piątek 12:28:13 +0100
Eternity II — kult algo?
Zal napisał wczoraj, iż Katedra Algorytmów i Modelowania Systemów wzięła się za układanie Eternity II. Póki co, najbardziej widocznym efektem tych prób jest prezentacja w nowym gmachu, która przedstawia proces układania. Wygląda to intr[...]
2008-11-20, Czwartek 22:17:24 +0100
„Wystarczy” że się to ułoży czy trzeba to zrobić najszybciej lub w najmniejszej ilości ruchów ( wśród wszystkich osób startujących w konkursie)?
I z lenistwa poprosił bym Cie o napisanie jak złożony jest to problem, bo sam stanąłem na chwile przed prezentacją, wiem że każdy klocek można obrócić na 4 rożne sposoby… no i czy jest tylko jedno prawidłowe rozwiązanie czy jak?
2008-11-20, Czwartek 22:23:46 +0100
Z tego, co się orientuję to wystarczy je po prostu ułożyć. Nic więcej ;] Nadesłane rozwiązania, o ile w ogóle takowe są, będą przejrzane dopiero 31 grudnia tego roku. A sam konkurs trwa do 2010, o ile mnie pamięć nie myli.
A co do złożoności problemu – bardzo złożony (ale NP-zupełny). Samych kombinacji wspomnianych puzzli jest ponad 10^557.
Więcej info na angielskiej Wiki :]
2008-11-20, Czwartek 22:42:50 +0100
czyli nie mam szansy ułożyć tego ręcznie …?:> (żart )
2008-11-20, Czwartek 23:08:37 +0100
szanse masz zawsze ;)
2008-11-20, Czwartek 23:09:32 +0100
Tyle tylko, że tutaj nawet pratchettowa „szansa jedna na milion” (sprawdza się w 9 przypadkach na 10) nie ma zastosowania ;D
2008-11-20, Czwartek 23:35:13 +0100
A jakie jest prawdopodobieństwo ułożenia tych puzzli? Ile jest kombinacji?
2008-11-20, Czwartek 23:36:44 +0100
@skkf: Tak, jak zostało to zaznaczone na Wiki, przy zadanym ustawieniu początkowym puzzli, liczba kombinacji jest rzędu 10^557 ;]
2008-11-20, Czwartek 23:38:26 +0100
Chyba duuużo większe jest prawdopodobieństwo trafienia szóstki w totka, niż znalezienia metodą ‘na chama’ odp. kombinacji w rozsądnym czasie. Trzeba to jakoś sposobem.
2008-11-20, Czwartek 23:40:04 +0100
@q84_fH: Brute force nie przejdzie – jeżeli wykorzystać by całą dostępną obecnie moc obliczeniową to i tak nie zdąży się przed planowanym końcem Wszechświata ;D
Zdecydowanie lepiej pograć w ToTka, jeżeli ktoś ma zamiar robić to na chama. Z drugiej zaś strony – puzzle są tańsze ;]
2008-11-20, Czwartek 23:46:13 +0100
Najlepsza jest zmiana cyferek :) Tak swoją drogą, tam jest kropka, ona oddziela rozwinięcie dziesiętne czy przedział którejś potęgi 10ki? :)
2008-11-20, Czwartek 23:50:28 +0100
@Bartek: To jest zapisane w notacji naukowej, czyli 1,115 * 10557 ;]
2008-11-21, Piątek 00:06:54 +0100
trochę nie kumam.. Tam było dużo – kropka – ileśtam zer, o ile dobrze pamiętam. Żadnego „e”, ani 10tki do potęgi tam nie widziałem(może dobrze by było dodać? Z resztą zastanawialiśmy się nad tym ze znajomym w przerwie w wykładzie ;p.
2008-11-21, Piątek 00:09:19 +0100
@Bartek: Masz na myśli samą prezentację? :D Niestety, nie przyglądałem się jej, aż tak dokładnie, a twórcą nie jestem ;]
2008-11-21, Piątek 00:10:11 +0100
warto dodac, ze rozwiazan jest wiecej niz jedno – podobno!
2008-11-21, Piątek 00:10:41 +0100
Tak, prezentację, wydawało mi się to oczywiste… ;p
2008-11-21, Piątek 00:12:06 +0100
@Bartek: Częsty problem występujący podczas komunikacji ;D
@matekm: Ale z tego, co się mówi to nie są one zbyt gęsto rozłożone w zbiorze wszystkich możliwych ułożeń.
2008-11-21, Piątek 00:13:35 +0100
ta, na HDI o tym mówią, ale jak zmieniające się cyferki wspomniałem, to myślałem, że skumasz, że pod wizualizacją jest podana liczba sprawdzonych kombinacji i o nią pytam.
2008-11-21, Piątek 00:45:14 +0100
@Bartek: Tak – nacisk na słowo zmiana to jest to, czego nie zauważyłem ;D
2008-11-24, Poniedziałek 17:40:42 +0100
Mimo, że już załamywałam się tym, i trochę postałam tam nabijając się, to nie zauważyłam reklamy, więc słabo się staracie :p
2008-11-24, Poniedziałek 19:46:02 +0100
@katsu: Ja sam ją ledwo wyłapałem ;D I nawet nie wiedziałem, że się reklamujemy ;p