W dniu 2013-05-12 00:31, bartekltg pisze:

pozwolę sobie to pominąć, gdyż:

>> do zapisania każdej serii "kliknięć" to mi zazwyczaj wystarczy INT o
>> długości tylu bitów, ile pól liczy krótszy z boków, i nawet nie muszę
>> mieć w pamięci miejsca na całą kopię tablicy wejściowej
>
> Oczywista oczywistość. Tylko pamiętaj, żę jeden 64 bitowy int starcza
> na m=n <=8. Mało.

nie rozumiesz, że 64-bitowy int wystarcza mi na zapamiętanie każdej
_sensownej_ kombinacji klików na tablicy N x M gdzie:
( M <= 64 ) OR ( N <= 64 )

ergo, nie załapałeś jeszcze, jak ma działać algorytm "logiczny" (w
odróżnieniu od "matematycznego"), zatem jeszcze za wcześnie, by się o
niego spierać :) Absolutnie bez urazy, jak chcesz, mogę potem opisać
ideę sposobu i wyjaśnić zastosowane skróty.

do góry

W dniu 2013-05-12 01:59, M.M. pisze:

[...]

> Mozna troche przerobic Twoje spostrzezenie. Kazdy klik pewne pola zapala a
> inne gasi. Niech to bedzie klik x. Wiec klik x determinuje kliki ktore
> musza zgasic to co on zapalil. Jesli kolejnosc jest niewazna, to klik x
> moze determinowac je jako kliki w nastepnej kolejnosci. Wiec kazde pole moze
> miec zapamietany numer+1 rekurencyjnego wywolania w ktorym zostalo zapalone
> lub jeden jesli bylo dane w ukladzie poczatkowym. Algorytm w kazdym
> kroku musi zgasic dowolne pole o najmniejszym numrze. To na pewno zmniejszy
> breanch-faktor.

W skrócie, to wyszedłem z takiego założenia:
1. działa to jak XOR, czyli jest naprzemienne
2. skoro kolejność nie ma znaczenia, to ja ją (na swoje potrzeby)
uporządkuję np. od góry, do dołu
3. po wykonaniu wszystkich klików pierwszego wiersza już do niego nie
wracam, zatem w wierszu drugim MUSZĘ ustawić pożądany stan wiersza
pierwszego, klikając POD polami (i TYLKO POD nimi), które mają ów stan
niewłaściwy. W kolejnym wierszu już takiej szansy nie będzie, więc nie
zostanie spełniony warunek zadania.

np. gdy pierwszy rząd po testowym klikaniu wygląda tak:
11010001 to muszę kliknąć pod nim: --x-xxx- (gdzie "x" to click, a "-"
jego brak, nie chcę używać 0/1 żeby się komuś clicki i stany nie myliły :)),
rząd 1 wówczas wygląda już tak: 11111111,
nastąpiły zmiany w rzędzie 2 oraz 3, ale tu już iteracyjnie powtarzamy
aż do ostatniego, po czym badamy, czy on też przyjął postać 11111111.

> Pozostaje kwestia czy mozna jakos uniknac spamietywania?

Trzymając się dalej tablicy np. 8 x 1024, musimy wykonać najwyżej 256
iteracji, od 00000000(bin) do 11111111(bin), czyli np. zwykłą pętlą od 0
do 255 sobie polecieć. Licznik pętli ma już sam z siebie na sobie
zapisane wszystkie układy "klików" do przetestowania.
Gdy kombinacja dla pierwszego wiersza jest dobra, to mamy sukces (i
możemy prościutko odtworzyć wszystkie pola wymagające kliknięcia).

> Algorytm z spamietywaniem jest prosty Jesli docieramy do ukladu ktory byl
> wczesniej, to wnioskujemy ze zaczyna sie petlic. Ale takie podejscie
> wymagaloby sporo pamieci.

Tu, poza tablicą wejściową, masz licznik + 2 bufory o rozmiarze
krótszego boku każdy, wszystko na bitach. Nazwa pliku zajmie więcej
pamięci ;)

> Moze wystarczy zapamietac z kazdym polem, ze juz bylo raz zapalone i potem
> zgaszone? Intuicja podpowiada, ze nie ma sensu zapalac danego pola dwa razy.
> Nie wiem czy moja intuicja sie nie myli, ale jesli to prawda, to algortym
> moze przerwac przeszukiwanie danej galezi, jesli nie da sie zgasic jakiegos
> pola bez zapalania tych pol, ktore juz wczesniej byly zgaszone.

Jeszcze raz: iteracyjnie XOR-ujesz licznik z pierwszym rzędem i drugim,
pamiętając, że XOR w rzędzie klikniętym to nie zwykły XOR, ale również
odwrócenie sąsiadujących bitów.
Tak swoją drogą, to znalezienie nieiteracyjnego algorytmu (lub formuły),
które dla danego ciągu bitów zwróca ciąg z którym wystarczy RAZ wykonać
"zwykły XOR" (czyli: 0001 => 0011, 0010 => 0111, 0011 => 0100 itd.) to
też fajna rozrywka, ale to takie "podzadanie" w zadaniu raczej :)
Kontynuując:
Po wykonaniu testowanej serii klików na pierwszym rzędzie (pamiętaj,
pierwszy wiersz zmienia się "nieco magicznie", drugi to już zwykły XOR,
poprzez negację wiersza pierwszego otrzymujemy mapę kliknięć do
wykonania na następnym wierszu. I tak z każdym kolejnym wierszem aż do
ostatniego. I albo się udało (po "magicznym XOR" mam same jedynki), albo
przechodzimy do kolejnej kombinacji kliknięć w pierwszy rząd.

do góry

W dniu 2013-05-12 15:31, Vax pisze:
> W dniu 2013-05-12 00:31, bartekltg pisze:
>
> pozwolę sobie to pominąć, gdyż:
>
>>> do zapisania każdej serii "kliknięć" to mi zazwyczaj wystarczy INT o
>>> długości tylu bitów, ile pól liczy krótszy z boków, i nawet nie muszę
>>> mieć w pamięci miejsca na całą kopię tablicy wejściowej
>>
>> Oczywista oczywistość. Tylko pamiętaj, żę jeden 64 bitowy int starcza
>> na m=n <=8. Mało.
>
> nie rozumiesz, że 64-bitowy int wystarcza mi na zapamiętanie każdej
> _sensownej_ kombinacji klików na tablicy N x M gdzie:
> ( M <= 64 ) OR ( N <= 64 )

Nie ja nie rozumiem, tylko Ty masz nieporządek.
Deklarowałeś złożność 2^n. (n<=m) a to nie może być osiagniete,
jeśli pamiętasz jedną linię. Wtedy masz m*2^n (m>=n)
Tylko tyle;)

> ergo, nie załapałeś jeszcze, jak ma działać algorytm "logiczny" (w
> odróżnieniu od "matematycznego"), zatem jeszcze za wcześnie, by się o
> niego spierać :) Absolutnie bez urazy, jak chcesz, mogę potem opisać
> ideę sposobu i wyjaśnić zastosowane skróty.

Zalapalem, ale pisać nie bronię:)

Twój alg jest prosty i rzeczywiśćei łątwo go się optymalizuje sprzętowo,
ale pisałem to wszytko po to, byś zobaczył, gdzie bardziej
zaawansowany algorytm zyskuje przewagę.
Wyciąłeś to, więc zakładam, że załapałeś.

pzdr
bartekltg

do góry

W dniu 2013-05-12 16:44, bartekltg pisze:

> Nie ja nie rozumiem, tylko Ty masz nieporządek.
> Deklarowałeś złożność 2^n. (n<=m) a to nie może być osiagniete,
> jeśli pamiętasz jedną linię. Wtedy masz m*2^n (m>=n)
> Tylko tyle;)

Właśnie gdy pamiętam jedną linię jest osiągnięte.
Cała "iteracja wewnętrzna" to nie szukanie rozwiązania, ale jego test.

W "klasycznej" metodzie, gdzie szukasz kombinacji kliknięć po całej
tablicy, musisz te kliknięcia tak czy siak "zrzutować" na tablicę
wejściową by sprawdzić, czy tablica ma wymagany stan (same jedynki, lub
same zera, jak tam założysz).
Zauważ, że iteracyjne przetworzenie rzędów jest odpowiednikiem
iteracyjnego sprawdzenia "sekwencji klików" (i dużo szybsze niż test
przeciętnej sekwencji N*M potencjalnych klików).

Jako, że czasochłonność testu jest zależna od rozmiaru danych (w jednym
wypadku od liczby bitów na każdy bok, w drugim od ich iloczynu) koszt
testu pominąłem, istotne, że ja mam do przetestowania np. 16 kombinacji
zamiast np. 65536 (i to zapewne przy większym koszcie testu w druim
przypadku).

> Zalapalem, ale pisać nie bronię:)

w sąsiedniej gałęzi wątku wyłuszczyłem, mam nadzieję, że wystarczająco?

> Twój alg jest prosty i rzeczywiśćei łątwo go się optymalizuje sprzętowo,
> ale pisałem to wszytko po to, byś zobaczył, gdzie bardziej
> zaawansowany algorytm zyskuje przewagę.

"Pominąłeś koszty operacji macierzowych" ;)

> Wyciąłeś to, więc zakładam, że załapałeś.

załapałem, wiem o czym piszesz, ale jestem zwolennikiem wstępnego
upraszczania problemów na drodze logicznej, a to był akurat dobry
przykład :)

do góry

On Fri, 10 May 2013 20:15:52 +0200, Vax <...@i...nie.ma> wrote:

>W dniu 2013-05-09 14:15, bartekltg pisze:
>> Hmm, dopiero co by?a poprzednia edycja, albo obsuwa,
>> albo robi? co pó? roku;-)
>
>to mo?e kto? si? podejmie oszacowa? z?o?ono?? obliczeniow? takiego problemu:
>
>Mamy prostok?tn? tablic? M x N z dwustanowymi komórkami. Prze??czenie
>wskazanej komórki powoduje automatyczne prze??czenie komórek
>s?siaduj?cych od góry, do?u, z lewej i prawej (o ile takie wyst?puj?).
>Modelem mo?e by? szachownica zape?niona bierkami z reversi, ruch posiada
>dwie fazy - odwracasz wybran? bierk?, a nast?pnie jej najbli?szych
>s?siadów (poza tymi po przek?tnych).
>
>Nale?y dla zastanego stanu (w szczególnym przypadku wszystkie komórki w
>stanie "0") odnale?? sekwencj? ruchów, która wszystkie komórki
>doprowadzi do stanu "1" lub stwierdzi?, ?e taka sekwencja nie istnieje.
>
>Chyba nie za trudne? ;)

Problem jest niekompletnie zdefiniowany i jako taki nie moze byc
rozwiazany

A.L.

do góry

W dniu 2013-05-12 18:23, A.L. pisze:

>
> Problem jest niekompletnie zdefiniowany i jako taki nie moze byc
> rozwiazany

http://en.wikipedia.org/wiki/Lights_Out_%28game%29
i odnośniki 2-4.


O, właśnie, Ty będziesz wiedział. Znalezienie jakiegokolwiek
rozwiązania jest wielomianowe, ale aby znaleźć rozwiązanie
optymalne trzeba rozwiązać jeszcze jeden prolbem. Obierajac
go z otoczki:

Mamy zero-jedynkowy wektor X długości L oraz k wektorów y_j
(tej samej długości).

Teraz bierzemy podzbiór {y_j} i wszytko (x i wybrane y_j) xorujemy
po współrzędnych (dadajemy modulo 2).

Problemem jest znalezienie podzbioru {y_j}, który da minimalną
liczbę jedynek (minimalną normę wektora, ponieważ 0-1, wszytko
jedno jaką).

Śmierdzi mi to NP-trudnym (tzn znlazłem jedynie algorytm wykladniczy
względem k:), ale pewności nie mam (dość podobne do dyskretnego
programowania liniowego, ale jednak zdecydowanie nie to samo).

Wiesz coś o takim problemie? Sformułowanie wygląda tak, jakby
było znane;)

pzdr
bartekltg

do góry

On Sun, 12 May 2013 18:40:50 +0200, bartekltg <b...@g...com>
wrote:

>W dniu 2013-05-12 18:23, A.L. pisze:
>
>>
>> Problem jest niekompletnie zdefiniowany i jako taki nie moze byc
>> rozwiazany
>
>http://en.wikipedia.org/wiki/Lights_Out_%28game%29
>i odno?niki 2-4.
>

W poscie tutaj nie bylo napisane czy zmiana stany propaguje sie czy
tez jest ograniczona do najblizszych sasiadow

A.L.

do góry

W dniu 2013-05-12 17:14, Vax pisze:
> W dniu 2013-05-12 16:44, bartekltg pisze:
>
>> Nie ja nie rozumiem, tylko Ty masz nieporządek.
>> Deklarowałeś złożność 2^n. (n<=m) a to nie może być osiagniete,
>> jeśli pamiętasz jedną linię. Wtedy masz m*2^n (m>=n)
>> Tylko tyle;)
>
> Właśnie gdy pamiętam jedną linię jest osiągnięte.
> Cała "iteracja wewnętrzna" to nie szukanie rozwiązania, ale jego test.

Nie, pomyśl, ile operacji musisz wykonać, aby znaleźć rozwiązanie
optymalne. Musisz wygenerować _wszystkie_ kombinacje linii
początkowej, i musisz je przetestować (a także zliczyć kliknięcia).
Kandydatów jest 2^n, a dla każdego wykonujesz m operacji (m>=n)


> Jako, że czasochłonność testu jest zależna od rozmiaru danych (w jednym
> wypadku od liczby bitów na każdy bok, w drugim od ich iloczynu) koszt
> testu pominąłem, istotne, że ja mam do przetestowania np. 16 kombinacji
> zamiast np. 65536 (i to zapewne przy większym koszcie testu w druim
> przypadku).

Ale z czym Ty dyskutujesz? Jeśli min (m,n) =4 to opisamy
przezemnie algorytm musi wykonać <=16 testów, bo na 4
wektory 'zerowe'.


>> Zalapalem, ale pisać nie bronię:)
>
> w sąsiedniej gałęzi wątku wyłuszczyłem, mam nadzieję, że wystarczająco?
>
>> Twój alg jest prosty i rzeczywiśćei łątwo go się optymalizuje sprzętowo,
>> ale pisałem to wszytko po to, byś zobaczył, gdzie bardziej
>> zaawansowany algorytm zyskuje przewagę.
>
> "Pominąłeś koszty operacji macierzowych" ;)

Nie. Z nich bierze się owo O((n*m)^3)


>
>> Wyciąłeś to, więc zakładam, że załapałeś.
>
> załapałem, wiem o czym piszesz, ale jestem zwolennikiem wstępnego

No nie wiem, uwaga o przeszukiwaniu kazdej kombinacji na całej
tablicy kliknięć sugeruje, że nawet nie przeczytałeś dokładnie:/


pzdr
bartekltg

do góry

On Sun, 12 May 2013 19:24:10 +0200, bartekltg <b...@g...com>
wrote:

>W dniu 2013-05-12 17:14, Vax pisze:
>> W dniu 2013-05-12 16:44, bartekltg pisze:
>>
>>> Nie ja nie rozumiem, tylko Ty masz nieporz?dek.
>>> Deklarowa?e? z?o?no?? 2^n. (n<=m) a to nie mo?e by? osiagniete,
>>> je?li pami?tasz jedn? lini?. Wtedy masz m*2^n (m>=n)
>>> Tylko tyle;)
>>
>> W?a?nie gdy pami?tam jedn? lini? jest osi?gni?te.
>> Ca?a "iteracja wewn?trzna" to nie szukanie rozwi?zania, ale jego test.
>
>Nie, pomy?l, ile operacji musisz wykona?, aby znale?? rozwi?zanie
>optymalne. Musisz wygenerowa? _wszystkie_ kombinacje linii
>pocz?tkowej, i musisz je przetestowa? (a tak?e zliczy? klikni?cia).
>Kandydatów jest 2^n, a dla ka?dego wykonujesz m operacji (m>=n)

Czyli przeliczyc wszystkie mozliwe kombinacje?...

A.L.

do góry

W dniu 2013-05-12 19:48, A.L. pisze:
> On Sun, 12 May 2013 19:24:10 +0200, bartekltg <b...@g...com>
> wrote:
>
>> W dniu 2013-05-12 17:14, Vax pisze:
>>> W dniu 2013-05-12 16:44, bartekltg pisze:
>>>
>>>> Nie ja nie rozumiem, tylko Ty masz nieporz?dek.
>>>> Deklarowa?e? z?o?no?? 2^n. (n<=m) a to nie mo?e by? osiagniete,
>>>> je?li pami?tasz jedn? lini?. Wtedy masz m*2^n (m>=n)
>>>> Tylko tyle;)
>>>
>>> W?a?nie gdy pami?tam jedn? lini? jest osi?gni?te.
>>> Ca?a "iteracja wewn?trzna" to nie szukanie rozwi?zania, ale jego test.
>>
>> Nie, pomy?l, ile operacji musisz wykona?, aby znale?? rozwi?zanie
>> optymalne. Musisz wygenerowa? _wszystkie_ kombinacje linii
>> pocz?tkowej, i musisz je przetestowa? (a tak?e zliczy? klikni?cia).
>> Kandydatów jest 2^n, a dla ka?dego wykonujesz m operacji (m>=n)
>
> Czyli przeliczyc wszystkie mozliwe kombinacje?...

Wszystkie kombinacje pierwszej linii.
W algorytmie podanym przez Vaxa. Często da się szybciej,
czasem dużo szybciej.

pzdr
bartekltg

do góry