Miten tämmöinen ratkaistaan: http://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslam en osannut itse.
Optimaalinen painamisjärjestys hakusessa
Osaamaton
24381
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 24
Vanhimmat
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
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.
Ei ihan käsin lisättävä vaan indeksi = indeksi 1 for silmukan sisällä jotta sitä voi muuttaa silmukan saamiseksi. En keksinyt muuta.
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
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.
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.
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...
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.
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.
Jos+kytkimet+olisivat+vaikka+n1...n120+ja+vaikutus+olisi+7+lamppua.
Puuttuu alkuarvot.
Tuleeko+tuohon+nollan+paikalle+1,+jos+alkuarvo+on+1+?.
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.
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.
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.
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).
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 ?
Eikö olisi helpompaa tehdä vaikka githubiin projekti tälle kuin keskustella täällä?
Yritin+tehdä+Pythonilla+matriisiyhtälön+ekasta+ratkaisusta.+Jostain+syystä+tämä+ei+toimi.+Löytääkö+joku+bugin?
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.
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]
Mun mielestä tuosta voi tehdä yhtälöryhmän modulo 2 ja sitten pitää minimoida tuntemattomien summa. Voisikohan joku integer linear programming -menetelmä toimia?
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.