Seuraa 
Viestejä926
Liittynyt19.3.2005

Tällainen tehtävä löytyi netistä https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=muslam :

Museossa on pyöreitä näyttelyhuoneita, joiden seinillä riippuu tasavälein lamppuja. Ne lamput, joiden kohdalla on taideteos, on sytytetty. Museon sulkeuduttua kaikki lamput täytyy sammuttaa. Sähkökeskuksen vian vuoksi lamppujen kytkimet eivät kuitenkaan toimi oikein. Tietyn lampun kytkimen painaminen vaikuttaa myös sen vieressä oleviin lamppuihin. Mikä on nopein tapa sammuttaa huoneiden lamput?

Tehtävä

Tiedossa on huoneen lamppujen määrä ja kytkimen painalluksen vaikutusalue. Pyöreässä huoneessa lamput muodostavat jatkuvan ketjun, koska ensimmäinen lamppu on viimeisen vieressä. Kytkin muuttaa paitsi sen kohdalla olevan lampun tilaa, myös kytkimen vasemmalla ja oikealla puolella olevien lamppujen tilaa tiettyyn lamppuun asti. Kaikkien vaikutusalueen lamppujen tilat muuttuvat päinvastaisiksi.

Museon huoneessa A on kuusi lamppua ja kytkimien vaikutusalue on kaksi lamppua kumpaankin suuntaan. Huoneessa palavat lamput 1 ja 2 voidaan sammuttaa kahdella kytkimenpainalluksella: ensin painetaan kytkintä 4, sitten kytkintä 5.

Tämän huoneen lamppujen tila voidaan ilmoittaa lyhyesti 110000. Numero 1 tarkoittaa siis sytytettyä lamppua.

Vahtimestarin laatima luettelo museon muiden huoneiden lampuista on osoitteessa https://www.ohjelmointiputka.net/tiedostot/muslam.txt

Miten tuollainen tehtävä ratkaistaan? Yritin käyttää Sagea ja kunnan Z/2Z lineaarialgebraa ja joitain tapauksia sain ratkaistua:

input = '101011011000010000010101100101111101011110100111010011000000100010100110101100000000100110010100010010110111000000010110'
m = 7
d = len(input)
F = GF(2)

L_init = vector(F,input)
M = matrix(F,d,d)
for i in range(d):
for j in range(-m,m+1):
M[i,(i+j) % d] = 1
I = M.solve_right(L_init)
K = M.right_kernel();
m = min([len((I+k).nonzero_positions()) for k in K])
print (m)

Tulostaa 46 jonkun ajan päästä mutta koodi on joissain tapauksissa liian hidas:

input ='1110111111101000100110011001100110100000001010001100011110110011111100000101000010101101100111001000100110110101111000110101101000010000100110111101001001011010110100100111011000110001101011110100110011010111110101010100'
m = 27
d = len(input)
F = GF(2)
L_init = vector(F,input)
M = matrix(F,d,d)
for i in range(d):
for j in range(-m,m+1):
M[i,(i+j) % d] = 1
I = M.solve_right(L_init)
K = M.right_kernel();
m = min([len((I+k).nonzero_positions()) for k in K])
print (m)

Tämä ei tulosta mitään läppärilläni. Eli millainen olisi nopeampi algoritmi? Veikkaisin, että kielen vaihtaminen vaikka C++:aan ei nopeuttaisi ohjelmaa tarpeeksi, enkä edes osaa tarpeeksi C++:aa.

Kommentit (13)

Eusa
Seuraa 
Viestejä15631
Liittynyt16.2.2011

Varmaankin pitää huoneessa A painaa ensin 4, sitten 3.

Haettu lopputilanne on sellainen, jossa palavat peräkkäin pariton määrä lamppuja 2 × vaikutusalue +1.

Tuota kannattaa mielestäni lähestyä niin, että pyrkii ajamaan päällä olevat lamput yhteen läjään. Kyseessä on Rubikin kuution tapainen ongelma ja erilaisiin aluetilanteisiin löytyy painallussarjakuvioita, joilla ykköset järjestetään toiseen reunaan...

Hienorakennevakio suoraan vapausasteista: 1 / (1+2¹+3²+5³+1/2¹*3²/5³) = 1 / 137,036

pöhl
Seuraa 
Viestejä926
Liittynyt19.3.2005

Eusa kirjoitti:
Tuota kannattaa mielestäni lähestyä niin, että pyrkii ajamaan päällä olevat lamput yhteen läjään.

En usko, että tuo toimii aina optimaalisesti. Minusta tätä voi ajatella kahden alkion kunnassa. Jokainen kytkimen painallus on vektori. Tehtävä on ekvivalentti sen kanssa, virittääkö tietyt vektorit annetun lamppujen alkutilavektorin. Gaussin algoritmi voisi toimia, mutta luulen, että se on jo implementoitu noihin Sagen funktioihin. 

Eusa
Seuraa 
Viestejä15631
Liittynyt16.2.2011

pöhl kirjoitti:
Eusa kirjoitti:
Tuota kannattaa mielestäni lähestyä niin, että pyrkii ajamaan päällä olevat lamput yhteen läjään.

En usko, että tuo toimii aina optimaalisesti. Minusta tätä voi ajatella kahden alkion kunnassa. Jokainen kytkimen painallus on vektori. Tehtävä on ekvivalentti sen kanssa, virittääkö tietyt vektorit annetun lamppujen alkutilavektorin. Gaussin algoritmi voisi toimia, mutta luulen, että se on jo implementoitu noihin Sagen funktioihin. 


No joo, kun vaikutusalue on riittävän pieni tai alkuasetelma suotuisa, voi noita loppusammutusryhmiä muodostaa useitakin...

Hienorakennevakio suoraan vapausasteista: 1 / (1+2¹+3²+5³+1/2¹*3²/5³) = 1 / 137,036

Eusa
Seuraa 
Viestejä15631
Liittynyt16.2.2011

Koodaukseen tuntuisi silti kokeilukelpoiselta quick sort -algoritmin hyödyntäminen, kun vain ensin saa konvertoitua ongelman indeksitaulukoksi...

Hienorakennevakio suoraan vapausasteista: 1 / (1+2¹+3²+5³+1/2¹*3²/5³) = 1 / 137,036

pöhl
Seuraa 
Viestejä926
Liittynyt19.3.2005

Luulenpa, että tuo antamani koodi ei toimi optimaalisesti. Rivin m = min([len((I+k).nonzero_positions()) for k in K]) perusteella arvioisin, että koodi etsii useita ratkaisuja ja valitsee niistä minimaalisen. Ehkä tämän voi sittenkin ratkaista jotenkin sopivasti Gaussin-Jordanin algoritmilla, jos etsii vain parasta ratkaisua eikä kaikkea. Pitäisi opetella paremmin ohjelmointia tai Sagea jotta voisin testata.

Lyde19
Seuraa 
Viestejä3885
Liittynyt7.7.2013

Kaverillani oli kylpyhuoneessa kaksi ovea ja katkaisijat molempien ovien vieressä. Sähköt oli jotenkin maagisesti saatu kytkettyä niin että valot sai kyllä päälle molemmista kytkimistä mutta sen jälkeen sammui vain kiertämällä sulake irti.

pöhl
Seuraa 
Viestejä926
Liittynyt19.3.2005

Taas tuli uusi idea. Entä jos lamppujen tiloja ajattelisi verkon solmuina ja painalluksia särminä, joiden paino on yksi. Tällöin tehtävä on ekvivalentti sen kanssa, miten annetusta solmusta pääsee tiettyyn solmuun lyhintä reittiä pitkin. Silloin Dijkstran algoritmi ratkaisisi ongelman. Onko näin? Pitäisi vaan opetella toteuttamaan tuo verkko ja Dijkstran algoritmi. Vai pitääko Dijkstrassa ladata koko verkko ensin muistiin, joka ei ole tässä tapauksessa mahdollista? Vai voiko sitä verkkoa laajentaa aina pala kerrallaan?

Retromake
Seuraa 
Viestejä48
Liittynyt1.12.2017

Ainakin osa lampputehtävistä näyttäisi ratkeavan metodilla, joka perustuu Eusan ideaan samantilaisten lamppujen ajamisesta yhteen jonoon. 

Kuljetaan lamppukehää suuntaa vaihtamatta ja aloitetaan sammutus kohdasta, jossa katkaisijan  vaikutusalueen viimeisin positio (kulkusuunnassa) osuu lampun kohdalle, jossa on valo. Painetaan vaikutusalueen keskimmäistä katkaisijaa. Siirretään vaikutusalueen loppupositiota aina seuraavan päällä olevan lampun kohdalle ja painetaan taas keskimmäistä katkaisijaa. Näin jatkaen taakse  muodostuu jono sammutettuja lamppuja, ja kun kehä on kierretty, suotuisassa tapauksessa kaikki lamput ovat sammuksissa. Menetelmällä voi ratkaista mm. 220 lampun tehtävän, jota pöhl käytti esimerkissään. 

Tehtäväsarjassa on muutama tapaus, joka ei ratkea näin, vaan lamppuja jää päälle viimeisen  vaikutusalueen sisään. Lopputilan käsittelyssä houkuttelee brute-force -tekniikka, mutta  kombinatoriikassa tulee nopeasti seinä vastaan.

Yleispätevä ratkaisu pitäisi löytyä lineaarialgebran menetelmin. Kun lampputehtävässä on n lamppua, muodostetaan lineaarinen yhtälöryhmä, jossa on n yhtälöä ja n tuntematonta, ja käsitellään se matriisimuodossa

Ax = b, jossa b on lamppujen alkutilaa kuvaava pystyvektori,  x on ratkaisuvektori (painettavat katkaisimet) ja A on matriisi, jonka riville i on kuvattu katkaisijan i painalluksen aiheuttama valojen tilamuutos lähtötilasta.

Ratkaistessa redusoidaan matriisi [A|b] Gauss-Jordan -menetelmällä. Jos A on invertoituva, päädytään muotoon [I|c] jolloin ratkaisu x = c. Jos A ei ole invertoituva, päädytään muotoon [rref(A) | P]. Tällöin ratkaisuja on äärettömästi tai ei yhtään.

Koska lamppujen tilat voivat olla vain 0 tai 1, on laskettava modulo 2, tai bittimatriiseja käytettäessä XOR operaattorilla.

pöhl
Seuraa 
Viestejä926
Liittynyt19.3.2005

Tähän näyttäisi olevan joku ratkaisu, joka tuottaa optimaalisen painallussarjan osoitteessa https://ask.sagemath.org/question/39335/how-to-find-a-minimum-number-of-... , tuo nimimerkin dan_fulea ratkaisu kohdassa final solution. Mutta kun koetin ajaa sitä omalla koneellani, sain vastaukseksi virheilmoituksen TypeError: unable to find a common ring for all elements. Onkohan minulla väärä versio Sagesta vai onkohan tuo nimimerkki pistänyt väärän version vastaukseen?

Retromake
Seuraa 
Viestejä48
Liittynyt1.12.2017

Onkohan Sagea mahdollista käyttää ns. debugger -moodissa, eli tilassa, jossa ohjelman lähdekoodia voi tarkastella 
ajoaikana? Ominaisuudesta olisi hyötyä virhetilanteita tutkittaessa. 
Jos tehtävää ohjelmoi lineaarialgebraan tukeutuen, voi epäilyttää riittääkö läppärin teho, kun matriiseista suurin on
kooltaan 2107 x 2107. Testissäni osoittautui, että tämä ei ole ongelma, redusointiin kului vain 30 sekuntia. Jatko 
olikin jo pulmallisempaa. Muutamassa tapauksessa redusoidun matriisin ydin (kernel) jäi hyvin suureksi, esim. 1002:n lampun kehässä vapaiden muuttujien lukumääräksi jää 166, eli vapaiden muuttujien arvojen kombinaatioita on 2^166.
Hain ratkaisua metodilla, jossa valitaan kernel-rivien numeroita vastaavilta redusoidun matriisin sarakkeilta  sellainen, joka löydettyyn erityisratkaisuun summattuna sisältää vähiten ykkösarvoja. Tämä sarake merkitään
käsitellyksi, ja proseduuria toistetaan kunnes saavutettu parannus ei enää ylitä asetettua kynnysarvoa. Kynnysarvo
kannattaa asettaa hieman pienemmäksi kuin nolla, jolloin prosessissa sallitaan hetkellinen tilan heikkeneminen.
Tällä tavoin päädyin kaikissa tapauksissa samaan tulokseen kuin viittaamasi Sagemath -sivuston mukaan oli saatu.
Käyttämäni metodi ei välttämättä silti hae optimaalista ratkaisua, en ainakaan pysty todistamaan, että se hakisi.

Suosituimmat

Uusimmat

Uusimmat

Suosituimmat