Optimaalinen painamisjärjestys hakusessa

Miten tämmöinen ratkaistaan: http://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslam en osannut itse.
Ilmianna
Jaa

24 Vastausta



nxn matriisille jossa vaikutusalue on 1 löytysi kaavakin.
https://en.wikipedia.org/wiki/Lights_Out_(game)

Pitää varmaan ottaa kynää ja paperia ja aloittaa helpoimmasta tehtävästä.
Sitten yrittää saada siirrettyä ohjelmakoodiksi.

Kattelin keskusteluosiota. Näyttäisi ratkasijoilla olleen hakualgoritmeja, jotka yrittävät hakea, muttei varmaa ratkaisua. En ole varma.

Myös tuo että yrittääkö löytää yleispätevää ratkaisua vai annettuun alkutilanteeseen räätälöityä ratkasua. Tämä jälkimmäinen oli kait ohjelmointiputkan ratkaisijoilla?

Jos lähtisi jostain kohtaa ja jatkaisi bitti kerrallaan tarvittaessa bitin kääntämistä (tietenkin vaikutusalueen levyisesti), jäisi aina kerroksen jälkeen alkukohtaan vaikutusalueen +1 pituinen sotku Esim. kierros = 120 ja vaikutusalue 7, saisi muut nolliksi ja alkuun tulisi 8 bittinen alue, jossa mahdollisesti ykkösiä.

Jos ajatellaan että on vaikka vain yksi ykkönen 12http://cs.gettysburg.edu/~tneller/fys187-4/hw2.pdf0 bittisessä renkaassa, kuinka nollaat kaikki bitit?

Meneekö matemaattisesti vaikeaksi vai onko kohtuullisen (matemaattisesti) helppo ratkasu?

pari linkkiä joissa saman tyyppinen ongelma, muttei ratkasuja
http://cs.gettysburg.edu/~tneller/fys187-4/hw2.pdf
http://stackoverflow.com/questions/35527681/finding-an-algorithm-that-can-find-the-shortest-way-to-solve-a-one-dimensional-v
Kommentoi
Ilmianna
Jaa
5 VASTAUSTA:
Testailin Excelin VBA:lla. Toimiva motivointi opiskeluun jos ei muuta ;)

Laitoin Excelin taulussa soluihin 12x10 helpomman näkyvyyden (jos visuaalisuudella tulis jotain ideoita) vuoksi ja sitten painikkeet makroille.

Tein niin että ohjelma kääntää alueen (rng=Range(A1:J12)) seitsemän peräkkäisen solun (solu=rng.cells(n)) arvoa yksitellen tarkistaen mennääkö yli 120 ja jos niin vähennetään 120 (for silmukan sisällä toinen käsin lisättävä muuttuja).

Huomasin että jos 120/7 tapauksessa on vain kaksi ykköstä ja ne ovat peräkkäin,
saa nollattua kaikki aloittamalla toisen ykkösen oikealta puolelta niin että se juuri nollaa tämän toisen ykkösen (toisen ykkösen paikka + 3). Sitten jatkaen oikealle päin painaen nappulaa vain jos juuri vaikutusalueen laidassa (painalluskohta -3) on ykkönen. Painalluksia tulee 34.
....
Jos ei tullut virheitä (mitä tosin epäilen) satunnaisesti kokeillen sain nollattua kaikki aloittamalla kohdasta 97 (vaikuttaa kohdasta 94 - 100) ja suorittamalla saman kuin yllä eli painamalla aina nappia jos painamiskohta -3 on 1 eli lamppu palaa. Painalluksia tuli 54.
Kommentoi
Ilmianna
Jaa
Ei ihan käsin lisättävä vaan indeksi = indeksi +1 for silmukan sisällä jotta sitä voi muuttaa silmukan saamiseksi. En keksinyt muuta.
Kommentoi
Ilmianna
Jaa
Painettavat nappula:
94,95,98,99,103,109,110,118,120,1,2,3,4,9,11,14,15,16,18,20,24,25,26,27,28,29,30,31,32,33,34,39,40,41,42,43,44,47,48,53,54,60,62,65,66,68,69,70,74,76,81,83,85,86

tai

1,2,3,4,9,11,14,15,16,18,20,24,25,26,27,28,29,30,31,32,33,34,39,40,41,42,43,44,47,48,53,54,60,62,65,66,68,69,70,74,76,81,83,85,86,94,95,98,99,103,109,110,118,120

Järjestyksellä ei pitäisi olla väliä.

Tuo näyttäisi olevan yksi ratkaisu. En osaa Modulaarista aritmetiikkaa. Eli esim miten sitä matriiseihin sovelletaan.
https://fi.wikipedia.org/wiki/Modulaarinen_aritmetiikka
Kommentoi
Ilmianna
Jaa
Nuo olivatkin 7-alueiden alkukohtia. Keskikohdat eli kytkimen kohdat olisivat
1,3,4,5,6,7,12,14,17,18,19,21,23,27,28,29,30,31,32,33,34,35,36,37,42,43,44,45,46,47,50,51,56,57,63,65,68,69,71,72,73,77,79,84,86,88,89,97,98,101,102,106,112,113

eli lisätty 3 ja yli 120 vähennetty 120 ts. 121 = 1 jne. VBA ohjelmassa käytinkin alkukohtaa yksinkertaisuuden vuoksi enkä keskikohtaa.
Kommentoi
Ilmianna
Jaa
Jos vain lamppu numero 1 palaa tarvitaa seuraava 103 painallusta

1,3,4,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,24,25,26,27,28,29,31,32,33,34,35,36,38,39,40,41,42,43,45,46,47,48,49,50,52,53,54,55,56,57,59,60,61,62,63,64,66,67,68,69,70,71,73,74,75,76,77,78,80,81,82,83,84,85,87,88,89,90,91,92,94,95,96,97,98,99,101,102,103,104,105,106,108,109,110,111,112,113,115,116,117,118,119,120

Laskin matriisilla ja testasin yksinkertaisella vba ohjelmalla, joka kääntää seitsemää lamppua (solua) painalluksella.
Kommentoi
Ilmianna
Jaa
+Lisää kommentti
Tuota jos lähtee lopusta alkuun ratkaisemaan.
Esim. bittejä (lamppuja) on 120 kpl ja kerralla kääntyy 7 bittiä.
Ennen viimeistä painallusta on 7 kpl ykkösiä. Ennen toiseksi viimeistä painallusta on joko 14 ykköstä peräkkäin tai kaksi seitsemän ryhmää tai kaksi seitsemän ryhmää osittain päällekkäin niin että päällekkäiset (leikkausjoukko) ovatkin nollia.

Pitää siis alkaa muodostamaan seitsemän ykkösen ryhmiä tai päällekkäisiä ryhmiä huomioiden leikkauksien käänteisyyden.

Pitäisi vielä kääntää algoritmiksi...
Ilmianna
Jaa
Luulen, että tämän voi tehdä yhtälöryhmällä. Siis merkitään x_i:llä nappulan numero i painalluksien lukumäärää. Tällöin lamppuun numero i vaikuttaa annetut painikkeet x_(i-n),...,x_(i+n). Saadaan lineaarinen yhtälöryhmä, joka ratkaistaan modulo 2, eli renkaassa Z/2Z. En vaan osaa koodata näin harrastelijana sitä. Jotain pseudoa.

for every case:
write matrix equation
solve matrix equation

Tuohon matriisiyhtälön ratkaisemiseen voisi koettaa Gaussin–Jordanin menetelmää jos se vaikka olisi tarpeeksi nopea. Tai sitten tehokkaampia juttuja jos alkaa kone piiputtamaan. http://math.stackexchange.com/questions/30330/fast-algorithm-for-solving-system-of-linear-equations

Hmm. Enää pitäisi opetella ohjelmoimaan.
Kommentoi
Ilmianna
Jaa
1 VASTAUS:
Minulla taas näin päin
Hmm. Enää pitäisi opetella laskemaan.

Jotain tyhmää systemaattista läpikäyntiä Pythonilla, vois kokeilla, katotaan nyt tuleeko mitään.
Kommentoi
Ilmianna
Jaa
+Lisää kommentti
Jos kytkimet olisivat vaikka n1...n120 ja vaikutus olisi 7 lamppua.
Painallusten määrät myös n1...n120

(n118+n119+n120+n1+n2+n3)%2 = 0
(n119+n120+n1+n2+n3+n4)%2 = 0
...
(n117+n118+n119+n120+n1+n2)%2 = 0

%2 tarkoittaa modulo 2

Kirjoitin matematemaatikon kommentin perusteella parhaimpani mukaan.
Mitenkä moduloa käsitellään yhtälöryhmässä. ja voiko tuota järjestellä ja yksinkertaistaa. Tuossa tosin kasasin yhteen summat.
Kommentoi
Ilmianna
Jaa
6 VASTAUSTA:
Puuttuu alkuarvot.
Kommentoi
Ilmianna
Jaa
Tuleeko tuohon nollan paikalle 1, jos alkuarvo on 1 ?.
(n118+n119+n120+n1+n2+n3+n4)%2 = 1

(n119+n120+n1+n2+n3+n4+n5)%2 = 0
Kommentoi
Ilmianna
Jaa
Siis minusta tuon matriisiesityksen pitäisi olla seuraavanlainen. Olkoon lamppuja n kpl. Nyt A on nxn-kerroinmatriisi, jossa alkio A_{i,j}=1 jos painikkeen i painallus vaihtaa myös lampun j tilan ja A_{i,j}=0 jos painikkeen i painallus ei vaihda lampun j tilaa. Siis jos vaikkapa lamppuja olisi 6 kpl ja vaikutusalue 1 lamppu suuntaansa, niin A olisi muotoa

110001
111000
011100
001110
000111
100011

eli vähän kuin yksikkömatriisi, jonka ykkösdiagonaali on paksunnettu ja valuu reunojen yli. Sitten B on lamppujen alkutilojen matriisi, esim. jos alkutilat olisivat 110001, niin saataisiin pystymatriisi

1
1
0
0
0
1

Sitten pitää ratkaista yhtälö Ax=B. Yksi vaihtoehto voisi olla laskea A^(-1)B, missä siis käänteismatriisi otetaan modulo 2, mutta en tiedä olisiko se liian hidasta noissa isoissa tapauksissa.
Kommentoi
Ilmianna
Jaa
Kysäisin myös matikkapalstalta. Tuli hieman liian vaikea vastaus minulle.

Nyt kokeilin vielä 120/7 tehtävään. Sain toimivat arvot. Laitoin Exceliin 120x120 matriisit, laskin determinantteja (Excel laskee tarpeeksi nopeasti 120x120 matriisin sisäänrakennetuilla funktiolla) ja otin mod 2:set determinanteista.
D oli -7 eli mod2 -> 1 (jakaja, lähinnä tarkistuksen vuoksi? koska ratkaisut ovat 0 tai 1)

Sijoitin alkuarvosarakkeen vuorotellen sarakkeisiin 1 - 120 (A-DP) ja laskin determinantit. Tutkin onko jaollinen kahdella (=mod(TRUNC(ROUNDUP(ABS(deternimanttiarvo),1),2) ei meinannut saada oikeita moduloita)

Determinantit annoin laskea taulukon solussa MDETERM() funktiolla, josta kopioin tulokset VBA:n silmukassa.

tulos sama kuin aiemmin
1,3,4,5,6,7,12,14,17,18,19,21,23,27,28,29,30,31,32,33,34,35,36,37,42,43,44,45,46,47,50,51,56,57,63,65,68,69,71,72,73,77,79,84,86,88,89,97,98,101,102,106,112,113

Ongelma olisi sitten "vain" sopiva optimointi.
Kommentoi
Ilmianna
Jaa
tulihantestattua kirjoitti:
Kysäisin myös matikkapalstalta. Tuli hieman liian vaikea vastaus minulle.

Nyt kokeilin vielä 120/7 tehtävään. Sain toimivat arvot. Laitoin Exceliin 120x120 matriisit, laskin determinantteja (Excel laskee tarpeeksi nopeasti 120x120 matriisin sisäänrakennetuilla funktiolla) ja otin mod 2:set determinanteista.
D oli -7 eli mod2 -> 1 (jakaja, lähinnä tarkistuksen vuoksi? koska ratkaisut ovat 0 tai 1)

Sijoitin alkuarvosarakkeen vuorotellen sarakkeisiin 1 - 120 (A-DP) ja laskin determinantit. Tutkin onko jaollinen kahdella (=mod(TRUNC(ROUNDUP(ABS(deternimanttiarvo),1),2) ei meinannut saada oikeita moduloita)

Determinantit annoin laskea taulukon solussa MDETERM() funktiolla, josta kopioin tulokset VBA:n silmukassa.

tulos sama kuin aiemmin
1,3,4,5,6,7,12,14,17,18,19,21,23,27,28,29,30,31,32,33,34,35,36,37,42,43,44,45,46,47,50,51,56,57,63,65,68,69,71,72,73,77,79,84,86,88,89,97,98,101,102,106,112,113

Ongelma olisi sitten "vain" sopiva optimointi.
Tarkoitin matriisilaskennan optimointia.
Kommentoi
Ilmianna
Jaa
matemaatikko kirjoitti:
Siis minusta tuon matriisiesityksen pitäisi olla seuraavanlainen. Olkoon lamppuja n kpl. Nyt A on nxn-kerroinmatriisi, jossa alkio A_{i,j}=1 jos painikkeen i painallus vaihtaa myös lampun j tilan ja A_{i,j}=0 jos painikkeen i painallus ei vaihda lampun j tilaa. Siis jos vaikkapa lamppuja olisi 6 kpl ja vaikutusalue 1 lamppu suuntaansa, niin A olisi muotoa

110001
111000
011100
001110
000111
100011

eli vähän kuin yksikkömatriisi, jonka ykkösdiagonaali on paksunnettu ja valuu reunojen yli. Sitten B on lamppujen alkutilojen matriisi, esim. jos alkutilat olisivat 110001, niin saataisiin pystymatriisi

1
1
0
0
0
1

Sitten pitää ratkaista yhtälö Ax=B. Yksi vaihtoehto voisi olla laskea A^(-1)B, missä siis käänteismatriisi otetaan modulo 2, mutta en tiedä olisiko se liian hidasta noissa isoissa tapauksissa.
Ei toimi tuo matriisin kääntö suoraan. Tehtävän voi ratkaista etsimällä annetulle vektoriavaruudelle kanta. Eli meillä on annettu tietyt vektorit, jotka vastaavat sitä, miten lamppujen tilat muuttuvat kun nappulaa painaa. Sitten näiden joukosta pitää etsiä minimaalinen joukko vektoreita, joiden lineaarikombinaationa saadaan annettu alkutila.
Kommentoi
Ilmianna
Jaa
+Lisää kommentti
Ei sittenkään toimi laskutapani aina. Determinantit voi mennä nollaksi, vaikka ratkaisu olisikin olemassa. Silloin kun ratkaisu on löytynyt, se on ollut oikea mitä olen testannut.

Ongelma on ilmeisesti siinä että deteriminantti pitäisi laskea eri tavalla.
Ei riitä modulo 2 ottaminen jälkikäteen.

Lisäksi laskin 120/7 H-tehtävän niin että koko vaikutusalue on seitsemän. Vastauksen oli sillä tulkinnalla oikein. Kuitenkin tehtävässä tarkoitetaan kumpaankin suuntaan 7 + painalluskohta (yht 15). Esim. siinä laskutapani antaa determinanteiksi nollan joten ei saa tulosta.

Huomasin virheen kun laajensin ohjelmaa laskemaan millä tahansa lamppumäärällä ja vaikutusalueella ja testasin tehtävillä. Heti B-tehtävässä tuli determinanteiksi 0, vaikka vastauksen (4 ja 5) sai esimerkkitehtävään (6 lamppua vaikutusalueella 2).
Ilmianna
Jaa
http://math.stackexchange.com/questions/169921/how-to-solve-system-of-linear-equations-of-xor-operation#
how can i solve this set of equations ? to get values of x,y,z ?
1=x⊕y⊕z
1=x⊕y⊕w
0=x⊕w⊕z
1=w⊕y⊕z
...

samantyyppinen ?
Ilmianna
Jaa
Eikö olisi helpompaa tehdä vaikka githubiin projekti tälle kuin keskustella täällä?
Ilmianna
Jaa
Yritin tehdä Pythonilla matriisiyhtälön ekasta ratkaisusta. Jostain syystä tämä ei toimi. Löytääkö joku bugin?

# Museon lamput.

# Museon lamput ratkeaa matriisiyhtälöllä yli Z/2Z:n. Matriisit voidaan tehdä Pythonissa listoilla.

# Sanotaan, että ensimmäinen indeksi kuvaa pystysuuntaa ja toinen vaakasuuntaa.

# Tämä funktio generoi wxn nollamatriisin
def generate_matrix(w, h):
return [[0 for x in range(w)] for y in range(h)]

# Nyt matriisin tulostus sujuu seuraavasti:

def print_matrix(A):
for row in range(0,len(A[0])):
line = ""
for col in range(0,len(A[0])):
line += str(A[row][col])
if col == len(A[0]):
line += "\n"
print(line)

# Alkeisrivioperaatio: Vaihda kaksi riviä keskenään.
def swap_rows(A,i,j):
for k in range(0,len(A[0])):
temp = A[k][i]
A[k][i] = A[k][j]
A[k][j] = temp
return A

# Alkeisrivioperaatio: Lisää riviin toinen rivi.
def mult_rows(A,i,j):
for k in range(0,len(A[0])):
A[k][j] += A[k][i]
A[k][j]= A[k][j] % 2
return A

# Kahden indeksin etäisyys toisistaan.
def dist(i,j,n):
d1 = max(i-j,j-i)
dist_beg = min(i,j)
dist_end = n-max(i,j)
d2 = dist_beg + dist_end
return min(d1,d2)

# Kerroinmatriisin alustus
def gen_coeff_matrix(n,effect_width):
A = generate_matrix(n,n)
for i in range(0,n):
for j in range(0,n):
print("indeksien "+str(i)+ " ja "+str(j)+"etäisyys on "+str(dist(i,j,n))+", ew="+str(effect_width))
if dist(i,j,n) <= effect_width:
A[i][j] = 1
print("A["+str(i)+"]["+str(j)+"]="+str(A[i][j]))
print(A)
return A

# Yksikkömatriisin alustus
def init_unit_matrix(n):
A = generate_matrix(n,n)
for i in range(0,n):
A[i][i] = 1
return A

# Matriisin käännös. Edetään sarakkeittain. Jos diagonaalilla on nolla, vaihdetaan rivit alhaalta jotta diagonaalille tulee nolla.
# Tämän jälkeen eliminoidaan muut rivit.
def inv(M):
n = len(M[0])
U = init_unit_matrix(n)
for column in range(0,n):
if M[column][column] == 0:
i = 1
while M[column+i][column+i] != 0:
++i
swap_rows(A,column,column+i)
swap_rows(U,column,column+i)
# Nyt diagonaalilla on varmasti ykkönen. Käytetään tätä eliminoimaan loput alkiot sarakkeelta.
for c in range(0,n):
if M[c][column] == 1:
if c != column:
mult_rows(M,c,column)
mult_rows(U,c,column)
return U

# Kerrotaan matriisi vektorilla.
def mult_matrix_vector(M,V):
print(str(len(M))+", "+str(len(V)))
result = [0 for x in range(0,len(V))]
summa = 0
for row in range(0,len(V)):
for i in range(0,len(V)):
# print(M[row][i])
# print(V[i])
summa += M[row][i] * V[i]
summa = summa % 2
result[row] = summa
return result

A = init_unit_matrix(5)
#print_matrix(A)
B = gen_coeff_matrix(6,1)
print("B="+str(B))
print_matrix(B)
print("-")
C = inv(B)
print_matrix(C)
print("-")
print_matrix(B)
D=[1,0,1,1,0,1]
print(mult_matrix_vector(C,D))
Kommentoi
Ilmianna
Jaa
2 VASTAUSTA:
Tuossa on 9 Funktiota, ja niissä ei ole virhettä.

Kukaan tai mikään ei vain kutsu yhtäkään noista funktioista, joten mitään ei voi tapahtua. Niiden olemassa olo on yhtä tyhjän kanssa, ellei niitä käytetä mihinkään.
Kommentoi
Ilmianna
Jaa
Niin. Tuossa meni sisennykset pieleen. Mutta riviltä A = init_unit_matrix(5) alkaen loput rivit alkavat ensimmäisestä sarakkeesa. Minun Python-tulkki osaa lukea tiedoston vaikka main puuttuu. Mulla tulostuu seuraavaa:

indeksien 0 ja 0etäisyys on 0, ew=1
A[0][0]=1
indeksien 0 ja 1etäisyys on 1, ew=1
A[0][1]=1
indeksien 0 ja 2etäisyys on 2, ew=1
indeksien 0 ja 3etäisyys on 3, ew=1
indeksien 0 ja 4etäisyys on 2, ew=1
indeksien 0 ja 5etäisyys on 1, ew=1
A[0][5]=1
indeksien 1 ja 0etäisyys on 1, ew=1
A[1][0]=1
indeksien 1 ja 1etäisyys on 0, ew=1
A[1][1]=1
indeksien 1 ja 2etäisyys on 1, ew=1
A[1][2]=1
indeksien 1 ja 3etäisyys on 2, ew=1
indeksien 1 ja 4etäisyys on 3, ew=1
indeksien 1 ja 5etäisyys on 2, ew=1
indeksien 2 ja 0etäisyys on 2, ew=1
indeksien 2 ja 1etäisyys on 1, ew=1
A[2][1]=1
indeksien 2 ja 2etäisyys on 0, ew=1
A[2][2]=1
indeksien 2 ja 3etäisyys on 1, ew=1
A[2][3]=1
indeksien 2 ja 4etäisyys on 2, ew=1
indeksien 2 ja 5etäisyys on 3, ew=1
indeksien 3 ja 0etäisyys on 3, ew=1
indeksien 3 ja 1etäisyys on 2, ew=1
indeksien 3 ja 2etäisyys on 1, ew=1
A[3][2]=1
indeksien 3 ja 3etäisyys on 0, ew=1
A[3][3]=1
indeksien 3 ja 4etäisyys on 1, ew=1
A[3][4]=1
indeksien 3 ja 5etäisyys on 2, ew=1
indeksien 4 ja 0etäisyys on 2, ew=1
indeksien 4 ja 1etäisyys on 3, ew=1
indeksien 4 ja 2etäisyys on 2, ew=1
indeksien 4 ja 3etäisyys on 1, ew=1
A[4][3]=1
indeksien 4 ja 4etäisyys on 0, ew=1
A[4][4]=1
indeksien 4 ja 5etäisyys on 1, ew=1
A[4][5]=1
indeksien 5 ja 0etäisyys on 1, ew=1
A[5][0]=1
indeksien 5 ja 1etäisyys on 2, ew=1
indeksien 5 ja 2etäisyys on 3, ew=1
indeksien 5 ja 3etäisyys on 2, ew=1
indeksien 5 ja 4etäisyys on 1, ew=1
A[5][4]=1
indeksien 5 ja 5etäisyys on 0, ew=1
A[5][5]=1
[[1, 1, 0, 0, 0, 1], [1, 1, 1, 0, 0, 0], [0, 1, 1, 1, 0, 0], [0, 0, 1, 1, 1, 0], [0, 0, 0, 1, 1, 1], [1, 0, 0, 0, 1, 1]]
B=[[1, 1, 0, 0, 0, 1], [1, 1, 1, 0, 0, 0], [0, 1, 1, 1, 0, 0], [0, 0, 1, 1, 1, 0], [0, 0, 0, 1, 1, 1], [1, 0, 0, 0, 1, 1]]
110001
111000
011100
001110
000111
100011
-
111110
100001
110000
100111
101101
010010
-
001101
101111
110110
111010
011000
000001
6, 6
[1, 1, 0, 1, 1, 1]
Kommentoi
Ilmianna
Jaa
+Lisää kommentti
Mun mielestä tuosta voi tehdä yhtälöryhmän modulo 2 ja sitten pitää minimoida tuntemattomien summa. Voisikohan joku integer linear programming -menetelmä toimia?
Ilmianna
Jaa
Aika hankala. Vissiin toimiva idea on osoitteessa https://math.stackexchange.com/questions/2569003/how-to-find-an-algorithm-to-shut-down-all-lamps-with-minimum-number-of-moves . Kunpa osaisin kääntää tuon ohjelmakoodiksi.
Ilmianna
Jaa

Vastaa alkuperäiseen viestiin

Optimaalinen painamisjärjestys hakusessa

Miten tämmöinen ratkaistaan: http://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslam en osannut itse.

5000 merkkiä jäljellä

Peruuta