Dnia Mon, 13 May 2013 02:20:56 +0200, bartekltg napisał(a):

>
> PS. jeśli post pojawi się dwa razy, wszytko wina aioe:)

Pojawilo :-)

Polecam serwer neostrady, jest otwarty dla wszystkich od pewnego czasu i
stabilny.

--
pozdro
R.e.m.e.K

do góry

W dniu sobota, 11 maja 2013 12:28:04 UTC+2 użytkownik bartekltg napisał:

> W skrócie, parzysta liczba 'kliknięć' w pole jest redukowana
> do zera.
Bym to ujął trochę inaczej. Parzysta ilość kliknięć w dane pole
powoduje, że pola na które kliknięcie ma wpływ, przyjmują wartości takie
jak w stanie początkowym.


> Kolejność klikania też nie ma znaczenie.
Jasne, takie ma właściwości xor.


> Możesz więc klikną raz lub w ogole. Stąd też wiadomo,
> że kliknięć nie będzie więcej niż pol szachownicy.
Jasne.


> Zapisz kliknięcia jako wektor v.
Rozumiem, że mamy wektor zero-jedynkowy o rozmiarze
n*m. Jak wektor ma jedynkę, to było kliknięcie, a jak zero to
kliknięcia nie było. Wektor v jest rozwiązaniem.


> Wtedy stan danego pola możesz opisać jakio w = A*v
> gdzie A to niezbyt gęsta macierz (mniej niż 5*n*m elementów).
> Oba wektory mają długość m*n, maciesrz siłą rzeczy (m*n)x(m*n).
> Wszytko dzieje się modulo 2.
Nie wiem co to za macierz A. Na razie widzę tak:
v[n*m] - kolumnowy zero-jedynkowy wektor kliknięć
x[n*m] - wierszowy zero-jedynkowy wektor wpływu kliknięcia
b[n*m] - kolumnowy zero-jedynkowy stan początkowy
i - wektor jedynkowy
b = (v*x*i) .modulo 2
Szukamy wektora zero-jedynkowego v. Siłowe sprawdzenie ma
złożoność (n*m)^2. Szybsze zaproponowałem kilka postów
wyżej z rekurencją i zapamiętywaniem ile razy było zapamiętane
dane pole i w którym wywołaniu rekurencyjnym - nie jestem
pewny na 100% czy zadziała.


> Konfiguracja zapalająca czy konfiguracja gasząca to to samo,
> więc szykamy v, takiego, że w to nasz stan początkowy i
> w = A*v
Jasne, poza macierzą A.


> Po pierwsze, da się rozwiązać, kiedy w siedzi w przestrzeni rozpiętej
> przez kolumny A (jest a obrazie A, dość trywialny wniosek).
> Ponieważ obraz A będzie duży, łatwiej do algorytmu wyznaczyć kojądro*)
> i sprawdzać, czy aby nasza oczekiwana konfiguracja sie z nim nie
> przecina (iloczynem skalarnym).
Jak to sie rozwiązuje i co to za macierz A?

Pozdrawiam

do góry

bartekltg <b...@g...com> wrote:
> W dniu 2013-05-12 23:01, Vax pisze:
>> W dniu 2013-05-12 22:51, bartekltg pisze:
>>
>>>> Rozpatrywanie tego algorytmu jest mało sensowne, ale skoro chcesz:
>>>> mamy 2^(m*n) prób. W każdej musimy wygenerować tablicę opisującą
>>>> stan lampek. Jeśli rzeczywiście będziemy budować ją od początku,
>>>> wykonamy O(m*n) operacji. Ale nie musimy tego robić, wystarczy, że
>>>> naniesiemy poprawki. Jeśli różnił się jeden bit, poprawka jest w 5
>>>> miejscach. Super.
>>
>> tablica 5 x 100 - z dowolnej kombinacji masz 500 innych "różnych o jeden
>> bit", ale czymże to jest wobec 2^500...
>
> Jesteś jedyną osobą, która w ogole wspomina o czymś takim!
> Czyżbyś sugerował, że "mój" alg tyle działa? Czyli jednak nie
> załapałeś;>
>
> Opisany prze zemnie algorytm ma cześć 'wykładniczą'
> 2^l, gdzie l jest co najwyżej 5.

Dla 5 x 100 l=0 ;)

do góry

Vax <...@i...nie.ma> wrote:
> 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).

Ale to nie musi to być rozwiązanie optymalne - gdy takiego szukasz, to musisz
przejrzeć wszystkie :(
Chyba, że null-space jest pusta.

Każda metoda ma swój techniczny zakres stosowalności.
Twoja jest dobra dla wąskich macierzy, ale co zrobisz dla 40 x 40?
Ja w pari-gp (czyli tak sobie optymalnym narzędziu) mam wynik poniżej 1 sekundy.

do góry

W dniu 2013-05-13 11:54, Miroslaw Kwasniak pisze:
> bartekltg <b...@g...com> wrote:
>> W dniu 2013-05-12 23:01, Vax pisze:
>>> W dniu 2013-05-12 22:51, bartekltg pisze:
>>>
>>>>> Rozpatrywanie tego algorytmu jest mało sensowne, ale skoro chcesz:
>>>>> mamy 2^(m*n) prób. W każdej musimy wygenerować tablicę opisującą
>>>>> stan lampek. Jeśli rzeczywiście będziemy budować ją od początku,
>>>>> wykonamy O(m*n) operacji. Ale nie musimy tego robić, wystarczy, że
>>>>> naniesiemy poprawki. Jeśli różnił się jeden bit, poprawka jest w 5
>>>>> miejscach. Super.
>>>
>>> tablica 5 x 100 - z dowolnej kombinacji masz 500 innych "różnych o jeden
>>> bit", ale czymże to jest wobec 2^500...
>>
>> Jesteś jedyną osobą, która w ogole wspomina o czymś takim!
>> Czyżbyś sugerował, że "mój" alg tyle działa? Czyli jednak nie
>> załapałeś;>
>>
>> Opisany prze zemnie algorytm ma cześć 'wykładniczą'
>> 2^l, gdzie l jest co najwyżej 5.
>
> Dla 5 x 100 l=0 ;)

n = 100;
m = 5;
Nn = DiagonalMatrix[ConstantArray[1/2, n]] +
DiagonalMatrix[ConstantArray[1, n - 1], 1] +
DiagonalMatrix[ConstantArray[1, n - 1], -1];
M = DiagonalMatrix[ConstantArray[1/2, m]] +
DiagonalMatrix[ConstantArray[1, m - 1], 1] +
DiagonalMatrix[ConstantArray[1, m - 1], -1];

A = KroneckerProduct[M, IdentityMatrix[n]] +
KroneckerProduct[IdentityMatrix[m], Nn];

m*n - MatrixRank[A, Modulus -> 2]

Out[310]= 0

Zgadza się:)

Masz jakiś sprytniejszy pomysł na liczenie tego?


Odpaliłem wczoraj wieczorem bardzo niewydajną maszynkę,
która zrobiła tabelkę:
http://www.sendspace.com/file/xl0izd

Przy okazji, zna ktoś sprawniejszą maszynkę do takich
działań? Lapack dla ciał Z_p ;)

pzdr
bartekltg

do góry

W dniu 2013-05-13 13:07, Miroslaw Kwasniak pisze:
> Vax <...@i...nie.ma> wrote:
>> 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).
>
> Ale to nie musi to być rozwiązanie optymalne - gdy takiego szukasz, to musisz
przejrzeć wszystkie :(
> Chyba, że null-space jest pusta.
>
> Każda metoda ma swój techniczny zakres stosowalności.
> Twoja jest dobra dla wąskich macierzy, ale co zrobisz dla 40 x 40?
> Ja w pari-gp (czyli tak sobie optymalnym narzędziu) mam wynik poniżej 1 sekundy.


Hehe, spryciarz;> A dla 39x39?

Potem gorszy jest 61x61.

pzdr
bartekltg

do góry

W dniu 2013-05-13 13:07, Miroslaw Kwasniak pisze:
> Vax <...@i...nie.ma> wrote:
>> 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).
>
> Ale to nie musi to być rozwiązanie optymalne - gdy takiego szukasz, to musisz
przejrzeć wszystkie :(
> Chyba, że null-space jest pusta.
>
> Każda metoda ma swój techniczny zakres stosowalności.
> Twoja jest dobra dla wąskich macierzy, ale co zrobisz dla 40 x 40?
> Ja w pari-gp (czyli tak sobie optymalnym narzędziu) mam wynik poniżej 1 sekundy.


Hehe, spryciarz;> A dla 39x39?

Potem gorszy jest 61x61.

pzdr
bartekltg

do góry

W dniu 2013-05-13 11:54, Miroslaw Kwasniak pisze:
> bartekltg <b...@g...com> wrote:
>> W dniu 2013-05-12 23:01, Vax pisze:
>>> W dniu 2013-05-12 22:51, bartekltg pisze:
>>>
>>>>> Rozpatrywanie tego algorytmu jest mało sensowne, ale skoro chcesz:
>>>>> mamy 2^(m*n) prób. W każdej musimy wygenerować tablicę opisującą
>>>>> stan lampek. Jeśli rzeczywiście będziemy budować ją od początku,
>>>>> wykonamy O(m*n) operacji. Ale nie musimy tego robić, wystarczy, że
>>>>> naniesiemy poprawki. Jeśli różnił się jeden bit, poprawka jest w 5
>>>>> miejscach. Super.
>>>
>>> tablica 5 x 100 - z dowolnej kombinacji masz 500 innych "różnych o jeden
>>> bit", ale czymże to jest wobec 2^500...
>>
>> Jesteś jedyną osobą, która w ogole wspomina o czymś takim!
>> Czyżbyś sugerował, że "mój" alg tyle działa? Czyli jednak nie
>> załapałeś;>
>>
>> Opisany prze zemnie algorytm ma cześć 'wykładniczą'
>> 2^l, gdzie l jest co najwyżej 5.
>
> Dla 5 x 100 l=0 ;)

n = 100;
m = 5;
Nn = DiagonalMatrix[ConstantArray[1/2, n]] +
DiagonalMatrix[ConstantArray[1, n - 1], 1] +
DiagonalMatrix[ConstantArray[1, n - 1], -1];
M = DiagonalMatrix[ConstantArray[1/2, m]] +
DiagonalMatrix[ConstantArray[1, m - 1], 1] +
DiagonalMatrix[ConstantArray[1, m - 1], -1];

A = KroneckerProduct[M, IdentityMatrix[n]] +
KroneckerProduct[IdentityMatrix[m], Nn];

m*n - MatrixRank[A, Modulus -> 2]

Out[310]= 0

Zgadza się:)

Masz jakiś sprytniejszy pomysł na liczenie tego?


Odpaliłem wczoraj wieczorem bardzo niewydajną maszynkę,
która zrobiła tabelkę:
http://www.sendspace.com/file/xl0izd

Przy okazji, zna ktoś sprawniejszą maszynkę do takich
działań? Lapack dla ciał Z_p

pzdr
bartekltg

do góry

W dniu 2013-05-13 10:58, M.M. pisze:

>> Zapisz kliknięcia jako wektor v.
> Rozumiem, że mamy wektor zero-jedynkowy o rozmiarze
> n*m. Jak wektor ma jedynkę, to było kliknięcie, a jak zero to
> kliknięcia nie było. Wektor v jest rozwiązaniem.

Tak.


>> Wtedy stan danego pola możesz opisać jakio w = A*v
>> gdzie A to niezbyt gęsta macierz (mniej niż 5*n*m elementów).
>> Oba wektory mają długość m*n, maciesrz siłą rzeczy (m*n)x(m*n).
>> Wszytko dzieje się modulo 2.
> Nie wiem co to za macierz A. Na razie widzę tak:


Bo to było w poprzednich postach (ten jest już o nieco czym innym:)),
w szczególności tym Message-ID: <kml6fm$7ev$1@node1.news.atman.pl>


W skrócie, macierz wiążąca kliknięcie z zapaleniem.
Bardzo podobna do dyskretnego laplasjanu, tylko wszędzie
ma jedynki.


pzdr
bartekltg

do góry

W dniu 2013-05-13 10:14, R.e.m.e.K pisze:
> Dnia Mon, 13 May 2013 02:20:56 +0200, bartekltg napisał(a):
>
>>
>> PS. jeśli post pojawi się dwa razy, wszytko wina aioe:)
>
> Pojawilo :-)
>
> Polecam serwer neostrady, jest otwarty dla wszystkich od pewnego czasu i
> stabilny.

Mam nawet podpiętego w thunderbirdzie, ale tylko dwie grupy,
widać coś było nie tak.

Próbowałem wygooglać, czy da się zmusić thunderbirda do czytania
na raz z kilku serwerów, ale nic nie znalazłem (hamster chyba zdechl).

pzdr
bartekltg

do góry