marco.r
14-05-2009, 19:28
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
24 40
########################################
##########################.....#########
##########################.....#########
###############....#######-----#########
##############..........#......#########
##############....#...........##########
##############....#####......###########
###############.......##################
#######.......###......#################
######..........###.....################
#####.....###...#####....###############
#####....####....#####....##############
####.....####....######...##############
####....#####....######...##############
####....#####....#####....##############
####....######...####.....##############
####.....#####...###.....###############
####.....#####....#.....################
####.....######........#################
####=====#######....####################
########################################
########################################
########################################
########################################
= Output =
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.
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
24 40
########################################
##########################.....#########
##########################.....#########
###############....#######-----#########
##############..........#......#########
##############....#...........##########
##############....#####......###########
###############.......##################
#######.......###......#################
######..........###.....################
#####.....###...#####....###############
#####....####....#####....##############
####.....####....######...##############
####....#####....######...##############
####....#####....#####....##############
####....######...####.....##############
####.....#####...###.....###############
####.....#####....#.....################
####.....######........#################
####=====#######....####################
########################################
########################################
########################################
########################################
= Output =
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.