|
|||||||
|
|
|
 |
|
|
Strumenti |
14-05-2009, 18:28
|
#1 |
|
Senior Member
Iscritto dal: Dec 2005
Città: Istanbul
Messaggi: 1817
|
[Contest 14?] Corsa delle macchine
Voglio proporre un contest un po' alternativo, nel senso che stavolta la speranza e' che diventi una gara tra algoritmi piu' che una mostra di microottimizzazioni.
La sfida si ispira alle corse di macchine che penso piu' di qualcuno avra' giocato con penna e foglio a quadri quand'era piccolo, anche se ho apportato qualche modifica per rendere (almeno in teoria) relativamente semplice l'implementazione della struttura di base. Il regolamento e' relativamente lungo, perche' ho cercato di essere il piu' rigoroso possibile, non escludo pero' bug :P = Goal = Muovere la vettura dalla griglia di partenza fino al traguardo nel piu' breve tempo possibile = Descrizione del mondo = Il mondo e' costituito da una griglia rettangolare di celle Ogni griglia puo' essere di uno tra i quattro seguenti tipi Partenza: posizione dalla quale la vettura puo' partire Asfalto: cella che puo' essere percorsa dall'auto Erba: cella nella quale la macchina non puo' procedere, pena l'eliminazione Traguardo: cella che l'auto deve raggiungere per concludere l'esecuzione = Movimento della vettura = Il tempo scorre in modo discreto. Ad ogni turno la vettura puo' decidere di variare la propria velocita' ed aggiorna la propria posizione sulla griglia. La vettura puo' controllare indipendentemente due velocita', quella lungo l'asse x e quella lungo l'asse y. La velocita' e' espressa in caselle/turno, ed e' un valore intero. Se ad un dato istante la velocita' lungo un asse e' V, la velocita' lungo lo stesso asse al turno successivo puo' essere uno tra i tre valori [V-1,V,V+1]. = Collisioni = Le caselle di partenza, di arrivo e di asfalto sono considerate sgombre. La casella d'erba NON e' sgombra. La vettura puo' procedere solo su caselle sgombre. Nel caso che uno spostamento che coinvolga diverse celle, tutte le caselle per cui passa il segmento S che va da P1=(x1,y1) a P2=(x2,y2), devono essere sgombre. Il segmento parte dal centro della casella, per cui in pratica per ogni casella (x,y) tale che min(x1,x2) <= x <= max(x1,x2) min(y1,y2) <= y <= max(y1,y2) distanza( (x,y), S ) <= 1/2 tale casella deve essere sgombra ( distanza( (x,y) , S ) e' definita come min_{ (x',y') \in S } max( abs(x-x'), abs(y-y') ), = Condizione iniziale = L'utente puo' scegliere di partire da una qualsiasi delle caselle di partenza, con velocita' uguali a 0 = Condizione finale = La corsa finisce quando in un dato istante la macchina passa attraverso una delle caselle del traguardo, ovvero quando viene fatta una mossa _valida_ tra (x1,y1) a (x2,y2) per la quale esiste una casella di traguardo (xt,yt) tale che distanza( (xt,yt), S ) <= 1/2 = Obiettivo = Data una certa configurazione, trovare la sequenza di movimenti della macchina che permettano di ottenere una traiettoria completa tra partenza e arrivo nel minore numero di passi possibile. = Input = In input da console viene fornita la mappa della pista nel seguente formato: La prima riga contiene due interi separati da uno spazio rappresentanti rispettivamente il numero di righe <nrighe> e il numero di colonne <ncolonne> della mappa Seguono <nrighe> righe ognuna composta di <ncolonne> caratteri e terminata da un ritorno a capo, Ogni carattere avra' uno dei seguenti significati - (meno) : partenza = (uguale) : arrivo . (punto) : asfalto # (cancelletto) : erba (ostacolo) Esempio di input Codice:
24 40 ######################################## ##########################.....######### ##########################.....######### ###############....#######-----######### ##############..........#......######### ##############....#...........########## ##############....#####......########### ###############.......################## #######.......###......################# ######..........###.....################ #####.....###...#####....############### #####....####....#####....############## ####.....####....######...############## ####....#####....######...############## ####....#####....#####....############## ####....######...####.....############## ####.....#####...###.....############### ####.....#####....#.....################ ####.....######........################# ####=====#######....#################### ######################################## ######################################## ######################################## ######################################## L'output del programma dovra' essere nel seguente formato: ogni riga deve contenere le coordinate <x> e <y> dell'auto ad ogni istante successivo. Conseguentemente, se il percorso consta di n passi, l'output sara' composto di n+1 righe Per fare qualche prova per ora potete usare la pista sopra disegnata, provvedero' ad proporne di molto piu' corpose.
__________________
One of the conclusions that we reached was that the "object" need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele |
|
|
|
14-05-2009, 18:29
|
#2 |
|
Senior Member
Iscritto dal: Dec 2005
Città: Istanbul
Messaggi: 1817
|
Allego un esempio di percorso valido, non necessariamente il migliore, per la pista segnata sopra.
__________________
One of the conclusions that we reached was that the "object" need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele |
|
|
|
|
14-05-2009, 18:31
|
#3 |
|
Senior Member
Iscritto dal: Dec 2005
Città: Istanbul
Messaggi: 1817
|
Ovviamente avevo dimenticato l'allegato
__________________
One of the conclusions that we reached was that the "object" need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele |
|
|
|
|
14-05-2009, 18:34
|
#4 |
|
Senior Member
Iscritto dal: Dec 2005
Città: Istanbul
Messaggi: 1817
|
Infine, per chi vuole divertirsi a creare tracciati, allego un paio di script python che permettono di convertire una immagine bitmap in tracciato.
Nell'immagine di partenza il colore bianco viene convertito in partenza, il nero in traguardo, il grigio (128,128,128) in asfalto, e tutto il resto in erba. L'estensione va rinominata in .py
__________________
One of the conclusions that we reached was that the "object" need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele |
|
|
|
|
15-05-2009, 21:10
|
#5 |
|
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3692
|
Iscritto.
Ho un'idea. Mi manca un pezzo ancora pero'.
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. |
|
|
|
|
16-05-2009, 22:31
|
#6 |
|
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3692
|
Ho dei dubbi sulla validazione.
Se ho un pezzo Codice:
###. ###. ##.. ##.. E altri esempi simili. Come interpretare la regola correttamente? Altra domanda. Se DOPO aver passato il traguardo, sempre nella stessa mossa finale l'auto mi si schianta va bene lo stesso? Insomma una vittoria postuma... PS: Se mi lasciate da solo spezzo le braccine a tutti...
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. Ultima modifica di gugoXX : 16-05-2009 alle 23:00. |
|
|
|
|
16-05-2009, 22:59
|
#7 | ||
|
Senior Member
Iscritto dal: Dec 2005
Città: Istanbul
Messaggi: 1817
|
Quote:
 , inizialmente temevo nessuno se lo filasse 'sto contest :P. Per rispondere alla tua domanda: non e' una mossa ammessa. Nel caso in questione la retta che congiunge i centri delle due caselle passa giusto per l'angolo di una casella # per cui la distanza risulta essere giusto 1/2. La regola dice che ogni casella la cui distanza (del centro) dalla retta sia minore o uguale a 1/2 deve essere sgombra. Piu' semplicemente, la regola in questione dice in termini matematici che qualsiasi casella che viene anche solo toccata dalla retta deve essere sgombra. Spero di essermi chiarito un po' meglio Quote:
__________________
One of the conclusions that we reached was that the "object" need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele |
||
|
|
|
|
16-05-2009, 23:04
|
#8 | |
|
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3692
|
Grazie. (Nooo devo rifare il pezzo piu' brutto) Vabbe'.
Forse hai perso questo: Quote:
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. |
|
|
|
|
|
16-05-2009, 23:10
|
#9 |
|
Senior Member
Iscritto dal: Dec 2005
Città: Istanbul
Messaggi: 1817
|
giusto per fare un paio di esempi:
le caselle grigie sono quelle che devono essere libere
__________________
One of the conclusions that we reached was that the "object" need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele |
|
|
|
|
16-05-2009, 23:10
|
#10 |
|
Senior Member
Iscritto dal: Dec 2005
Città: Istanbul
Messaggi: 1817
|
esempio due (uff...perche' solo 1 attach ?
).
__________________
One of the conclusions that we reached was that the "object" need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele |
|
|
|
|
16-05-2009, 23:11
|
#11 | ||
|
Senior Member
Iscritto dal: Dec 2005
Città: Istanbul
Messaggi: 1817
|
Quote:
Per l'altra domanda: Quote:
Ovvero la casella di arrivo nel momento in cui si passa il traguardo deve essere sgombra.
__________________
One of the conclusions that we reached was that the "object" need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele |
||
|
|
|
|
16-05-2009, 23:44
|
#12 | |
|
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3692
|
Quote:
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. |
|
|
|
|
|
17-05-2009, 00:16
|
#13 |
|
Senior Member
Iscritto dal: Dec 2005
Città: Istanbul
Messaggi: 1817
|
Esatto.
Inizialmente volevo lasciare spazio dietro, solo che quando ho fatto a mano la soluzione di esempio l'ho fatta partendo dal traguardo, per cui a posteriori ho scambiato partenza e arrivo , ecco il motivo per cui non c'e' spazio  Comunque arriveranno delle piste piu' divertenti e soprattutto piu' grandi :P
__________________
One of the conclusions that we reached was that the "object" need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele Ultima modifica di marco.r : 17-05-2009 alle 01:10. |
|
|
|
|
17-05-2009, 13:45
|
#14 |
|
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3692
|
 Errore
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. |
|
|
|
|
17-05-2009, 16:03
|
#15 |
|
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3692
|
Mi ci voleva una birra.
E' lento, ma ho fiducia che funzioni. Eccolo al lavoro sull'esempio. 29 passi, compresi inizio e fine (In lanciata, spero che valga anche se dopo c'e' un muro!!) Codice:
Time - 5999ms Steps - 29 ######################################## ##########################.....######### ##########################.....######### ###############....#######@----######### ##############...@@.@...#.@....######### ##############...@#....@.@....########## ##############....#####......########### ###############..@....################## #######.......###.@.@..################# ######..@..@.@..###...@.################ #####.@...###.@.#####..@.############### #####....####....#####....############## ####.@...####.@..######@..############## ####....#####....######...############## ####....#####....#####....############## ####@...######@..####..@..############## ####.....#####...###.....############### ####.....#####.@..#...@.################ ####.....######..@..@..################# ####@====#######....#################### ######################################## ######################################## ######################################## ########################################
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. |
|
|
|
|
18-05-2009, 07:51
|
#16 |
|
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3692
|
Folgorazione notturna, scrivo, rifattorizzo e si scende.
Ho un QuadCore a 2.7GHz ora, e ovviamente ho rifattorizzato in modo da poter iniettare il parellismo, cosa che ho puntualmente fatto. Leggendo il codice intermendio mi sono accorto che beneficerei dei 64bit. Mannaggia, avessi voglia di reinstallare metterei Windows7 a 64bit. Codice:
Time - 408ms Steps - 29 ######################################## ##########################.....######### ##########################.....######### ###############....#######@----######### ##############...@@.@...#.@....######### ##############...@#....@.@....########## ##############....#####......########### ###############..@....################## #######.......###.@.@..################# ######...@.@.@..###...@.################ #####..@..###.@.#####....############### #####....####....#####.@..############## ####..@..####.@..######...############## ####....#####....######...############## ####....#####....#####.@..############## ####.@..######@..####.....############## ####.....#####...###..@..############### ####.....#####.@..#..@..################ ####.....######..@.@...################# ####@====#######....#################### ######################################## ######################################## ######################################## ########################################
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. Ultima modifica di gugoXX : 18-05-2009 alle 07:55. |
|
|
|
|
18-05-2009, 08:47
|
#17 |
|
Senior Member
Iscritto dal: Feb 2003
Città: Stockholm (SE)
Messaggi: 1343
|
hai provato anche con altri tracciati?
PS: se vuoi te lo testo sul mio sistema (2x dual core con win vista 64 bit) |
|
|
|
|
18-05-2009, 09:10
|
#19 | |
|
Senior Member
Iscritto dal: Jul 2002
Città: Reggio Calabria -> London
Messaggi: 12112
|
Quote:
veramente il suo primo step è correttamente il + corto.. 
__________________
|
|
|
|
|
|
18-05-2009, 09:13
|
#20 | |
|
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3692
|
Quote:
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. |
|
|
|
|
|
|
| Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 11:13.
