Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda Krenn94 » 18/09/2019, 21:46

veciorik ha scritto:L'OP si è dileguato 2 giorni dopo aver inserito il suo primo ed unico post, non avendo avuto quello che cercava urgentemente: un algoritmo per risolvere il suo problema.
Lo ha mascherato da gioco per scongiurare domande sui suoi tentativi di soluzione.
Naturalmente l'algoritmo può non trovare la sequenza richiesta se questa non esiste, perché gli interruttori sono generati casualmente.
Tanto per giocare:
Testo nascosto, fai click qui per vederlo
Un interruttore può essere rappresentato da una stringa di N bit, uno per lampadina. Così pure lo stato iniziale.
Gli interruttori operano in XOR sugli stati; poiché XOR è commutativo e associativo la sequenza cercata non è una sequenza ordinata ma un sottoinsieme.
L'algoritmo banale consiste nell'applicare allo stato iniziale gli interruttori prima uno alla volta, poi a due a due, poi a tre a tre, e via dicendo finché non si ottiene una stringa di bit tutti a zero.
Naturalmente l'algoritmo banale è ridondante e si può ottimizzare in vari modi, sia per ridurre il numero di operazioni che per limitare il consumo di memoria.
Ma questo oltrepassa i requisiti minimi.



Ciao, sono nuovo del forum e anche io mi sto imbattendo in questo stesso problema.
Frequento l'università di informatica e questo quesito è del corso di Algoritmi e Strutture dati e non so come risolverlo, qualcuno saprebbe una soluzione implementativa?
Per ora ho ipotizzato delle combinazioni di tasti in base allo stato iniziale restringendo l'analisi su 3 soli tasti (visto che 3 sono le lampadine che attivano quando un tasto è premuto). Ovvero la mia idea era analizzare in generale la soluzione e poi attuare la ricorsione nodo per nodo, ipotizzo qui di agire su un pulsante centrale (radice) che ha due figli (sx e dx). Se premo un pulsante cambia lo stato di tutti e 3

sx r dx cosa premere
0 0 0 nulla
0 0 1 dx+1 (ovvero non più a dx del destro attuale)
0 1 0 sx+r+dx
0 1 1 dx
1 0 0 sx+1
ecc...

Questo il testo del problema: http://lonati.di.unimi.it/algopig/1819/ ... iu2019.pdf
Krenn94
Starting Member
Starting Member
 
Messaggio: 1 di 2
Iscritto il: 18/09/2019, 21:35

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda veciorik » 12/10/2019, 22:02

@Krenn94

IMHO la sezione giusta per la tua richiesta è Informatica: apri lì un nuovo thread e metti un link a questo.


@gimasci99

ribadisco che IMHO il termine "gioco" è un po' riduttivo: tu stesso hai parlato di "problema", "algoritmo", "implementare", "inefficiente" con un tono serio, poco ludico.

I bottoni CITA e RISPONDI vanno bene entrambi per rispondere: si usa CITA per riportare le parole scritte da altri; in ambo i casi la risposta parte quando si preme "Invia".

Mi spiace di aver sospettato di te ma i tuoi interventi del 15-16 settembre e le tue visite erano invisibili.
Se, dopo aver premuto "Invia", non vedevi le tue risposte, forse erano nel limbo.
Io le ho viste solo oggi quando il sistema mi ha notificato il tuo secondo messaggio, quello datato 15/9 ore 9:43, dopo 27 giorni !!
"Dietro ogni problema c'è un'opportunità" - "Nelle prove naturali non si deve ricercare l'esattezza geometrica" - "Stimo più il trovar un vero, benché di cosa leggiera, che 'l disputar lungamente delle massime questioni senza conseguir verità nissuna" (Galileo Galilei)
Avatar utente
veciorik
Senior Member
Senior Member
 
Messaggio: 447 di 1135
Iscritto il: 07/03/2014, 23:42
Località: stra(VE)

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda gimasci99 » 15/10/2019, 15:38

@veciorik

IMHO la sezione giusta per la tua richiesta è Informatica: apri lì un nuovo thread e metti un link a questo.

ribadisco che IMHO il termine "gioco" è un po' riduttivo: tu stesso hai parlato di "problema", "algoritmo", "implementare", "inefficiente" con un tono serio, poco ludico.


provvedo a farlo immediatamente

I bottoni CITA e RISPONDI vanno bene entrambi per rispondere: si usa CITA per riportare le parole scritte da altri; in ambo i casi la risposta parte quando si preme "Invia".


Ok.

Mi spiace di aver sospettato di te ma i tuoi interventi del 15-16 settembre e le tue visite erano invisibili.
Se, dopo aver premuto "Invia", non vedevi le tue risposte, forse erano nel limbo.
Io le ho viste solo oggi quando il sistema mi ha notificato il tuo secondo messaggio, quello datato 15/9 ore 9:43, dopo 27 giorni !!


Il problema a quanto pare o è dell'aministratore che ha approvato in un sol colpo e solo oggi dopo più di un mese tutti i miei post oppure si era bloccato qualcosa sul forum. Ad ogni modo speriamo che questa risposta non arrivi tra un altro mese altrimenti non avrebbe senso postare. Grazie cmq.
gimasci99
Starting Member
Starting Member
 
Messaggio: 8 di 26
Iscritto il: 13/09/2019, 14:27

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda axpgn » 15/10/2019, 15:42

@gimasci99
L'invito di veciorik a postare nella sezione di Informatica non era rivolto a te ma a Krenn94 :wink:
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14277 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda veciorik » 15/10/2019, 20:56

axpgn ha scritto:@gimasci99
L'invito di veciorik a postare nella sezione di Informatica non era rivolto a te ma a Krenn94 :wink:


Confermo.

Se le risposte che ti abbiamo dato qui ti hanno soddisfatto, fermati qui.

Se vuoi approfondire, provaci qui !
Forse possiamo farcela, con spirito ludico, senza impegno.
Se non riusciamo a farlo, vai a Informatica.
"Dietro ogni problema c'è un'opportunità" - "Nelle prove naturali non si deve ricercare l'esattezza geometrica" - "Stimo più il trovar un vero, benché di cosa leggiera, che 'l disputar lungamente delle massime questioni senza conseguir verità nissuna" (Galileo Galilei)
Avatar utente
veciorik
Senior Member
Senior Member
 
Messaggio: 448 di 1135
Iscritto il: 07/03/2014, 23:42
Località: stra(VE)

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda axpgn » 15/10/2019, 21:01

È già andato ... in Informatica :D
axpgn
Cannot live without
Cannot live without
 
Messaggio: 14287 di 40640
Iscritto il: 20/11/2013, 22:03

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda gimasci99 » 28/10/2019, 19:41

@Bokonon
Volevo ringraziarti per avermi dato la dritta giusta sulla soluzione dell'algoritmo.
Ho eleganemente risolto implementando l'algoritmo di eliminazione di Gauss.
Determino anche i casi in cui il sistema non ammette soluzioni o è inconsistente, ecc.
gimasci99
Starting Member
Starting Member
 
Messaggio: 11 di 26
Iscritto il: 13/09/2019, 14:27

Re: Gioco delle N lampadine tutte spente (come fare?)

Messaggioda Bokonon » 28/10/2019, 19:49

gimasci99 ha scritto:@Bokonon
Volevo ringraziarti per avermi dato la dritta giusta sulla soluzione dell'algoritmo.
Ho eleganemente risolto implementando l'algoritmo di eliminazione di Gauss.
Determino anche i casi in cui il sistema non ammette soluzioni o è inconsistente, ecc.

Ottimo!
Felice di aver dato una mano
Avatar utente
Bokonon
Cannot live without
Cannot live without
 
Messaggio: 1725 di 5942
Iscritto il: 25/05/2018, 20:22

Precedente

Torna a Giochi matematici

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite