Contest: Algoritmo wang tiling
Volevo proporre un piccolo contest per un problema matematico/informatico/geometrico:
Tema:
Wang Tiling
Dato un set di wang tiles:
Composto da 16 tiles che possono essere combinati solo "Aperiodicamente"
Edit: davo per scontato fosse un argomento abbastanza conosciuto: I tile qui sopra riportati possono essere affiancati tra di loro solo rispettando l'adiacenza dei colori sui bordi (quindi un tile con triangolo blu a sinistra deve essere affiancato con un altro tile che ha triangolo blu a destra).
Rispettando queste regole non è possibile ottenere disposizioni periodiche. Ovvero non sarà mai possibile trovare intervalli all'interno dei quali i tile si ripetono.
Non do dimostrazioni della precedente affermazione, basti sapere che qualcuno l'ha dimostrato. (anche perchè dandovi
la dimostrazione risolvereste facilmente il problema)
Obiettivo:
Creare un applicazione che riceva come parametri:
-coordinate di un punto di partenza (due numeri interi)
-coordinate di un punto di arrivo (due numeri interi)
-tile di partenza (numero da 1 a 16)
L'applicazione deve restituire correttamente il tile che si trova nelle coordinate di arrivo. Per fare ciò sarà necessario rispettare le
regole di tiling: ovvero un quadrato potrà essere affiancato ad un altro quadrato, solo se i colori sui lati adiacenti combaciano.
Indipendentemente dal costo computazionale, il programma dovrà essere in grado di generare tutti i tile in una zona rettangolare
(ad esempio 100x200, e questi dovranno combaciare). Per riempire un area rettangolare è sufficiente cambiare il punto di arrivo
usando come input tutte le coppie di coordinate (X,Y) all'interno del rettangolo. Se il programma riempe correttamente questo
rettangolo allora è pronto per essere consegnato.
Ovviamente la richiesta minima è che venga restituito il tile corretto ad ogni input.(la funzione ritorna un intero) Nulla vi vieta di ritornare una tabella intera di tile, in tal caso però dovrete essere precisi ed indicare come interpretare questi dati. Quindi sarà compito vostro rendere accessibili questi dati.(se ritornate un array, da qualche parte dovrete pure ritornare la sua lunghezza ecc.)
Ovviamente una volta che il vostro algoritmo ritorna dei dati è semplicissimo visualizzarli con un'implementazione grafica. Questo tuttavia
non influirà molto sulla valutazione (usate librerie opensource crossplatform in modo da permettermi di compilarle
sulla mia macchina e sulla macchina di chiunque altro: SFML, irrlicht, Ogre, GLUT ecc. ). Ovviamente a parità di algoritmi vince la
miglior implementazione grafica.
Ecco alcuni esempi di combinazioni possibili:
(in aggiornamento)
Regole:
Le regole sono abbastanza semplici:
-termine ultimo per la consegna 25 maggio ore 23.59 (2 mesi abbondanti)
-Potete partecipare da soli o in gruppo (specificare tutti i componenti del gruppo)
-Non potete copiare codice e dovrete citare le fonti (libri, pagine web) che vi hanno aiutato
-Aprirò una seziona apposta per la consegna dove specificherò le modalità.
-Possibilmente utilizzate C/C++ per il programma. Accetto anche Java ma potrei ridurre la valutazione in tal caso. Occhio
Salvo nuovi avvisi queste sono le modalità di consegna:
-mandate tutto a me via mail / PM.
-come consegna minima dovrà essere presente il codice sorgente commentato.
-Applicazioni grafiche sono gradite ma non necessarie ( in tal caso usate librerie cross-platform
opensource cosicchè se voi aveste linux io possa compilare anche sotto windows).
-A fine contest TUTTO IL MATERIALE SARA' RESO PUBBLICO.
Chi volesse solo mostrare le applicazioni ma non il codice sorgente, non sarà considerato
un valido partecipante. Perchè il codice sorgente sarà reso pubblico?
1) Io sono un sostenitore dell'opensource.
2) Per testare i vari codici userò il debugger.
3) Chiunque può compilare in sicurezza senza dover temere i virus.
4) Potrete giudicare voi stessi i lavori e avrete la libertà di criticare le mie scelte
Valutazione:
-L'algoritmo verrà valutato in efficenza:
Quanto tempo viene impiegato per trovare il tile di arrivo?
-L'algoritmo dovrà essere corretto:
Verranno impostati parametri di ingresso totalmente casuali
Variando i dati in ingresso il tile restituito dovrà essere coerente con i tile precedentemente trovati
Il test di correttezza verrà fatto riempendo un area rettangolare di grandi dimensioni che comprenda sia le coordinate di partenza, sia quelle di arrivo.
-Applicazioni grafiche sono gradite:
In quanto facilitano la correzione da parte mia e danno in generale un impatto migliore al programma
A parità di algoritmi vince l'applicazione grafica migliore (dato che è soggettivo potrei chiedere
una votazione collettiva). Ritengo improbabile tale avvenimento.
-Commentate bene il codice.
- Se copiate codice gia esistente, penalizzo la valutazione.
-Se mi accorgo che avete copiato/basato il vostro lavoro su una fonte non citata, penalizzo la valutazione (penalità maggiore rispetto al punto precedente).
Ricompensa:
Edit: Nessuna. Solo onore ed il piacere di aver partecipato
Mi sembra tutto..
Tema:
Wang Tiling
Dato un set di wang tiles:
Composto da 16 tiles che possono essere combinati solo "Aperiodicamente"
Edit: davo per scontato fosse un argomento abbastanza conosciuto: I tile qui sopra riportati possono essere affiancati tra di loro solo rispettando l'adiacenza dei colori sui bordi (quindi un tile con triangolo blu a sinistra deve essere affiancato con un altro tile che ha triangolo blu a destra).
Rispettando queste regole non è possibile ottenere disposizioni periodiche. Ovvero non sarà mai possibile trovare intervalli all'interno dei quali i tile si ripetono.
Non do dimostrazioni della precedente affermazione, basti sapere che qualcuno l'ha dimostrato. (anche perchè dandovi
la dimostrazione risolvereste facilmente il problema)
Obiettivo:
Creare un applicazione che riceva come parametri:
-coordinate di un punto di partenza (due numeri interi)
-coordinate di un punto di arrivo (due numeri interi)
-tile di partenza (numero da 1 a 16)
L'applicazione deve restituire correttamente il tile che si trova nelle coordinate di arrivo. Per fare ciò sarà necessario rispettare le
regole di tiling: ovvero un quadrato potrà essere affiancato ad un altro quadrato, solo se i colori sui lati adiacenti combaciano.
Indipendentemente dal costo computazionale, il programma dovrà essere in grado di generare tutti i tile in una zona rettangolare
(ad esempio 100x200, e questi dovranno combaciare). Per riempire un area rettangolare è sufficiente cambiare il punto di arrivo
usando come input tutte le coppie di coordinate (X,Y) all'interno del rettangolo. Se il programma riempe correttamente questo
rettangolo allora è pronto per essere consegnato.
Ovviamente la richiesta minima è che venga restituito il tile corretto ad ogni input.(la funzione ritorna un intero) Nulla vi vieta di ritornare una tabella intera di tile, in tal caso però dovrete essere precisi ed indicare come interpretare questi dati. Quindi sarà compito vostro rendere accessibili questi dati.(se ritornate un array, da qualche parte dovrete pure ritornare la sua lunghezza ecc.)
Ovviamente una volta che il vostro algoritmo ritorna dei dati è semplicissimo visualizzarli con un'implementazione grafica. Questo tuttavia
non influirà molto sulla valutazione (usate librerie opensource crossplatform in modo da permettermi di compilarle
sulla mia macchina e sulla macchina di chiunque altro: SFML, irrlicht, Ogre, GLUT ecc. ). Ovviamente a parità di algoritmi vince la
miglior implementazione grafica.
Ecco alcuni esempi di combinazioni possibili:
(in aggiornamento)
Regole:
Le regole sono abbastanza semplici:
-termine ultimo per la consegna 25 maggio ore 23.59 (2 mesi abbondanti)
-Potete partecipare da soli o in gruppo (specificare tutti i componenti del gruppo)
-Non potete copiare codice e dovrete citare le fonti (libri, pagine web) che vi hanno aiutato
-Aprirò una seziona apposta per la consegna dove specificherò le modalità.
-Possibilmente utilizzate C/C++ per il programma. Accetto anche Java ma potrei ridurre la valutazione in tal caso. Occhio
Salvo nuovi avvisi queste sono le modalità di consegna:
-mandate tutto a me via mail / PM.
-come consegna minima dovrà essere presente il codice sorgente commentato.
-Applicazioni grafiche sono gradite ma non necessarie ( in tal caso usate librerie cross-platform
opensource cosicchè se voi aveste linux io possa compilare anche sotto windows).
-A fine contest TUTTO IL MATERIALE SARA' RESO PUBBLICO.
Chi volesse solo mostrare le applicazioni ma non il codice sorgente, non sarà considerato
un valido partecipante. Perchè il codice sorgente sarà reso pubblico?
1) Io sono un sostenitore dell'opensource.
2) Per testare i vari codici userò il debugger.
3) Chiunque può compilare in sicurezza senza dover temere i virus.
4) Potrete giudicare voi stessi i lavori e avrete la libertà di criticare le mie scelte
Valutazione:
-L'algoritmo verrà valutato in efficenza:
Quanto tempo viene impiegato per trovare il tile di arrivo?
-L'algoritmo dovrà essere corretto:
Verranno impostati parametri di ingresso totalmente casuali
Variando i dati in ingresso il tile restituito dovrà essere coerente con i tile precedentemente trovati
Il test di correttezza verrà fatto riempendo un area rettangolare di grandi dimensioni che comprenda sia le coordinate di partenza, sia quelle di arrivo.
-Applicazioni grafiche sono gradite:
In quanto facilitano la correzione da parte mia e danno in generale un impatto migliore al programma
A parità di algoritmi vince l'applicazione grafica migliore (dato che è soggettivo potrei chiedere
una votazione collettiva). Ritengo improbabile tale avvenimento.
-Commentate bene il codice.
- Se copiate codice gia esistente, penalizzo la valutazione.
-Se mi accorgo che avete copiato/basato il vostro lavoro su una fonte non citata, penalizzo la valutazione (penalità maggiore rispetto al punto precedente).
Ricompensa:
Edit: Nessuna. Solo onore ed il piacere di aver partecipato
Mi sembra tutto..
Risposte
Hai dimenticato alcune (parecchie) informazioni:
- cosa è un wang tile?
- che diamine vorrebbe dire "combinati solo aperiodicamente"?
- cosa deve fare l'applicazione?
- perché mai dovrei farla?
- perché mai dovrei mandarla a te?
- a che serve una valutazione?
Direi che... sì, hai dimenticato qualcosa d'altro:
- a che pro tutto questo?
- sei sicuro di essere nel posto giusto?
- mai pensato di noleggiare uno spazio web tutto tuo?
- cosa è un wang tile?
- che diamine vorrebbe dire "combinati solo aperiodicamente"?
- cosa deve fare l'applicazione?
- perché mai dovrei farla?
- perché mai dovrei mandarla a te?
- a che serve una valutazione?
Direi che... sì, hai dimenticato qualcosa d'altro:
- a che pro tutto questo?
- sei sicuro di essere nel posto giusto?
- mai pensato di noleggiare uno spazio web tutto tuo?
"Rggb":
Hai dimenticato alcune (parecchie) informazioni:
- cosa è un wang tile?
- che diamine vorrebbe dire "combinati solo aperiodicamente"?
- cosa deve fare l'applicazione?
- perché mai dovrei farla?
- perché mai dovrei mandarla a te?
- a che serve una valutazione?
Direi che... sì, hai dimenticato qualcosa d'altro:
- a che pro tutto questo?
- sei sicuro di essere nel posto giusto?
- mai pensato di noleggiare uno spazio web tutto tuo?
Rispondo in ordine:
-Un wang tile è un oggetto che può essere affiancato solo ad altri oggetti rispettando le corrispondenze dei colori sui bordi. Vista l'importanza che riveste in molte applicazioni informatiche do per scontato che sia conosciuto in un ambiente matematico.
-basta cercare il significato sul dizionario: vuol dire che non è possibile individuare nessun intervallo all'interno del quale si ripetono i tile nello stesso ordine.
-L'ho gia detto. L'applicazione deve restituire correttamente il tile che si trova nelle coordinate di arrivo. (basta conoscere le proprietà dei wang tiles per capire cosa vuol dire questa frase.
-per puro spirito competivo, ci sono un sacco di competizioni fatte solo per fare a gara. La tua domanda vale per tutte ovviamente, se vuoi partecipare sei libero di farlo.
-Semplicemente per il fatto che se posti il codice sul forum qualcuno potrebbe copiarlo e dire che è riuscito a risolvere il problema pure lui modificando il codice e magari piazzarsi meglio nella competizione. Infatti a fine competizione tutto sarà reso pubblico.
-ci dovrà essere un vincitore in un contest no?
-Solamente per gareggiare. Tralaltro l'argomento è molto istruttivo e necessita di iniziativa personale per trovare le fonti giuste (il web è sufficiente, ma ci sono anche alcuni libri che si possono trovare nelle bibliotece). Per questo motivo non voglio fornire indicazioni su dove trovare materiale utile.
-Siamo in un forum matematico, nella sottosezione informatica quindi penso di si.
-Non vedo un collegamento con questa discussione.
"DemoneRoss":
L'applicazione deve restituire correttamente il tile che si trova nelle coordinate di arrivo.
Forse ho frainteso qualcosa ma non mi sembra proprio che il tile nelle coordinate di arrivo sia ben definito. Diverse combinazione porterebbero potenzialmente a diversi tile di arrivo. Il primo tile in alto e a sinistra potrebbe essere ad esempio affiancato con il terzo e il quarto ed entrambi sarebbero accostamenti validi. Mi sono perso qualcosa? Non è importante l'unicità ma è sufficiente che esista una combinazione? Il problema non mi sembra ben definito e forse neanche particolarmente interessante. È abbastanza facile costruire combinazioni di wang tiles riga per riga e facendo ad ogni passo scelte casuali (forse facendo un po' di backtracking nel caso in cui si arrivi ad un punto morto).
Sicuramente non parteciperò a nessun contest 
. Ma mi incuriosiscono alcune cose, e se qualcuno fosse interessato:
1) Come dice apatriarca, il problema non è ben definito. Che cosa esattamente dovrebbe fare l'applicazione?
2) Disponendo questo particolare insieme (o parte di esso) per creare un pattern di riempimento? Hai provato e ne sei convinto, oppure lo puoi dimostrare?
. Ma mi incuriosiscono alcune cose, e se qualcuno fosse interessato:1) Come dice apatriarca, il problema non è ben definito. Che cosa esattamente dovrebbe fare l'applicazione?
"DemoneRoss":
Rispettando queste regole non è possibile ottenere disposizioni periodiche. Ovvero non sarà mai possibile trovare intervalli all'interno dei quali i tile si ripetono.
2) Disponendo questo particolare insieme (o parte di esso) per creare un pattern di riempimento? Hai provato e ne sei convinto, oppure lo puoi dimostrare?
Rggb, i Wang tiles sono stati (e sono) oggetti di parecchio studio e sono stati trovati degli insiemi che rispettano la proprietà esposta da DemoneRoss di avere solo tiling aperiodici. C'è quindi proprio una dimostrazione.
"apatriarca":
C'è quindi proprio una dimostrazione.
Appunto, ma non la volevo fare io: chiedevo se l'aveva fatta lui.
Partendo da un dato insieme:
A) si può creare un riempimento (tiling) periodico;
B) si può creare un riempimento cd. aperiodico;
C) non si può né (A) né (B).
Eventualmente si può trovare (D) sottoinsieme che crea riempimento (ovvero non si usano tutti gli elementi dell'insieme originale). Non mi sono messo a controllare qual è la situazione dell'insieme proposto, né l'ho confrontata con altre note, e nemmeno desidero farlo; quindi chiedo:
"Disponendo questo particolare insieme (o parte di esso) puoi creare un pattern di riempimento? Hai provato e ne sei convinto, oppure lo puoi dimostrare?"
L'unico modo per risolvere questo problema è vedere tutte le compinazioni, se il problema è di dicesione "esiste/non esiste" un modo è utilizzare il backtracking o comunque una tecnica di ricerca locale per confrontare tutti i lati.
PS: questo problema lo conoscevo con il nome "Square Tiling" o "Dominio Limitato" sarà di sicuro una variante o una sua riduzione.
PS: questo problema lo conoscevo con il nome "Square Tiling" o "Dominio Limitato" sarà di sicuro una variante o una sua riduzione.
"ham_burst":
L'unico modo per risolvere questo problema è vedere tutte le combinazioni, se il problema è di dicesione "esiste/non esiste" un modo è utilizzare il backtracking o comunque una tecnica di ricerca locale per confrontare tutti i lati.
PS: questo problema lo conoscevo con il nome "Square Tiling" o "Dominio Limitato" sarà di sicuro una variante o una sua riduzione.
Uno dei modi è cercare tutte le combinazioni, anche se è il meno efficiente può funzionare benone. Mi sembrava ben definito lo scopo dell'applicazione, cerco di rendere più comprensibile il primo post dunque
.Per quanto riguarda il lato matematico, io trovo che le dimostrazioni siano piuttosto complesse per questo problema (io le ho trovate difficili da capire, poi magari per qualche matematico sono semplici. Non sono nemmeno un matematico figuriamoci..
). Per fortuna il computer ci permette l'uso della forza bruta (anche se in questo caso non è strettamente necessaria).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo