Ci sono numAgenti agenti che si muovono nello ‘spazio’ di dimesione x,y. Inizialmente sono posizionati in ordine inverso nella prima riga:
.9.8.7.6.5.4.3.2.1.0.
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
Ogni agente si muove di una posizione (anche in diagonale) per raggiungere lo stato finale:
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
.0.1.2.3.4.5.6.7.8.9.
La gestione degli spostamenti avviene tramite un opportuno monitor Spazio con i seguenti metodi:
void register(int n, int x, int y): ‘registra’ l’agente n nella posizione x,y. Questo metodo viene invocato una sola volta quando gli agenti vengono creati. Serve per inizializzare lo spazio nella configurazione iniziale.boolean move(int n, int x, int y, int dx, int dy): muove l’agente n dalla posizionex,yalla posizionex+dx, y+dy. Il valoridxedysono nel range [-1,1] in quanto gli agenti si spostano di una sola posizione. Se la posizione è occupata l’agente attende. Il metodo ritorna false nel caso l’agente n non sia nella posizionex,y.int getAgent(int x, int y): ritorna l’id dell’agente nella posizionex,y. Se la posizione è vuota ritorna -1. Questo metodo viene usato per stampare la situazione ed eseguire test.
Scopo della prova è implementare il monitor ‘Spazio’ come una classe Java il cui costruttore prende in input le dimenzioni x,y dello spazio di gioco (es. Spazio(10,10)) e con i tre metodi sopra descritti. Utilizzare il programma di test riportato qui sotto.
Programma di test
import java.util.HashSet;
import java.util.Set;
public class Test extends Thread {
private static final int numAgenti =10; // numero agenti
private static final int x=10, y=10; // dimensione spazio di gioco
private final int num; // id dell'agente
private final Spazio s; // monitor spazio di gioco
private int my_x,my_y;
// costruttore: salva id, monitor e posizione iniziale dell'agente
Test(int num, Spazio s) {
this.num = num;
this.s = s;
this.my_x = numAgenti -1 - num;
this.my_y = 0;
}
public void run() {
try {
code();
} catch (InterruptedException e) {
System.out.println("Agente numero "+num+" interrotto!!");
}
}
// codice dei thread
void code() throws InterruptedException {
int dx, dy, i, j, a;
if (num == numAgenti) {
// questo thread stampa solo la situazione e controlla interferenze
// vedere nel ramo 'else' per il codice degli agenti
boolean done = false;
Set <Integer>check = new HashSet <Integer>();
// attende che tutti gli agenti siano registrati
sleep(1000);
// controlla la registrazione
for (i=0;i<x;i++)
if (s.getAgent(i,0) != numAgenti-1-i) {
System.out.println("Errore: l'agente " + i + " non e' registrato correttamente");
System.exit(1);
}
// stampa e controlla la situazione ogni secondo
while(!done){
// stampa
check.clear(); // svuota l'insieme di id
synchronized(s) {
System.out.println("====");
for (j=0;j<y;j++) {
for (i=0;i<x;i++) {
a = s.getAgent(i,j);
if (a == -1)
System.out.print(". ");
else {
System.out.print("."+a);
if (check.contains(a)) {
System.out.println("Errore: l'agente " + a + "e' presente 2 volte!");
System.exit(1);
} else // lo aggiungiamo
check.add(a);
}
}
System.out.println(".");
// se tutti gli agenti sono sull'ultima linea
if (j+2 == y && check.isEmpty())
done = true;
}
}
// controlla che non ci siano overlap: tutti gli agenti devono essere presenti
if (check.size() != numAgenti) {
// manca qualche agente!
System.out.println("Errore: sono presenti solo gli agenti " + check);
System.exit(1);
}
// se tutti gli agenti sono sull'ultima riga controlla che siano nell'ordine
// giusto
if (done) {
for (i=0;i<x;i++)
if (s.getAgent(i,y-1) != i) {
System.out.println("Errore: l'agente " + i + " non e' posizionato correttamente");
System.exit(1);
}
} else
sleep(1000);
}
// se non siamo usciti prima il test e' superato
System.out.println("Tutti gli agenti sono posizionati correttamente");
} else {
// questo sono gli agenti
// si registra
s.register(num,my_x,my_y);
// il giocatore e' pronto attende che tutti si registrino
System.out.println("Agente numero "+num+" registrato!");
sleep(500);
// qui avvengono le mosse
while (my_y != y-1) {
sleep(1000); // si muovono tutti assieme ogni secondo
// calcola la mossa
dy = 1; // scende sempre di una posizione
if (num == my_x)
dx = 0; // posizione giusta, non si muove orizzontalmente
else {
dx = (num - my_x) / Math.abs(num - my_x); // -1,1 a seconda della necessita'
}
// prova a fare la mossa
if (!s.move(num,my_x,my_y,dx,dy)) {
System.out.println("Agente numero "+num+ ": la posizione non corrisponde!!");
System.exit(1);
}
// aggiorna la posizione
my_x += dx;
my_y += dy;
}
}
}
public static void main(String argv[]) throws InterruptedException {
int j;
Spazio s = new Spazio(x,y); // crea il monitor
// crea i thread dei vari colori/numeri
for (j=0; j<=numAgenti; j++) {
(new Test(j,s)).start();
}
}
}
Ho provato una soluzione per l’esercizio in questo modo:
(Non ho fatto nessun controllo sul fatto che si potessero muovere per più di una posizione ma ho fatto si che se mi trovo nella posizione 9,9 con 1,1 finisco in 0,0 anche se non so quanto sia giusto
public class Spazio { private int spazio[][];//matrice per le posizioni private int righe;//variabile dove salvo il numero di righe, non si sa mai private int colonne;//variabile dove salvo il numero di righe, non si sa mai public Spazio(int x, int y){ int i,j; this.spazio=new int[x][y];//inizializzo la matrice this.righe=x;//salvo le righe this.colonne=y;//salvo le colonne for(i=0;i<x;i++){ for(j=0;j<y;j++){ this.spazio[i][j]=-1;//pongo tutti gli elementi della matrice a -1 per rendere visibile che è vuota } } } void register(int n, int x, int y){ //‘registra’ l’agente n nella posizione x,y. // Questo metodo viene invocato una sola volta quando gli agenti vengono creati. // Serve per inizializzare lo spazio nella configurazione iniziale.*/ this.spazio[x][y]=n; } synchronized boolean move(int n, int x, int y, int dx, int dy){ // Il metodo è synchronized ovvero dentro un mutex, muove l'agente n da // x,y a x+dx,y+dy. Se la posizione è occupata attendo con una wait in // ciclo while, quando è possibile muovere eseguo una notify. Il metodo // ritorna false se l'agente n non si trova veramente nella posizione x,y // if( this.getAgent(x, y)!=n) return false; else{ while(this.getAgent((x+dx)%this.righe, (y+dy)%this.colonne)!=-1) try { wait(); } catch (InterruptedException ex) { System.out.println("ERRORE WAIT "); } notify(); this.spazio[x][y]=-1; this.spazio[(x+dx)%this.righe][(y+dy)%this.colonne]=n; return true; } } int getAgent(int x, int y){ /*Ritorna l’id dell’agente nella posizione x,y, -1 se è vuota*/ return this.spazio[x][y]; } }La mia soluzione.
Speriamo che anche l’ esame sia così! 😛
public class Spazio{ int[][] tabella; public Spazio(int x, int y){ int i,j; tabella=new int[x][y]; /* Inizializzo le celle a -1*/ for(i=0;i<x;i++) for(j=0;j<y;j++) tabella[i][j] = -1; } synchronized void register(int n, int x, int y){ tabella[x][y] = n; } synchronized boolean move(int n, int x, int y, int dx, int dy) throws InterruptedException{ if(n != tabella[x][y]) return false; // l' agente non è nella poszione n while(tabella[x+dx][y+dy] != -1) wait(); tabella[x][y] = -1; tabella[x+dx][y+dy] = n; notifyAll(); return true; } synchronized int getAgent(int x, int y){ return tabella[x][y]; // Posso restituire direttamente la cella } }@Andrea: OK non serviva che chiudessi il gioco modulo righe,colonne. Gli agenti non vanno mai fuori dai bordi
@Loris: OK ma commenta! Prendete l’abitudine di commentare sempre il codice via via che lo scrivete.
Dovrebbe essere tutto ok, sembra funzionare bene 🙂
public class Spazio { int matrice[][]; //matrice delle posizioni public Spazio(int x, int y){ matrice = new int[x][y]; for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { //inizializzo tutte le caselle a -1 (vuote) matrice[i][j] = -1; } } } /** ‘Registra’ l’agente n nella posizione x,y. * Questo metodo viene invocato una sola volta quando gli agenti vengono creati. * Serve per inizializzare lo spazio nella configurazione iniziale. */ void register(int n, int x, int y){ this.matrice[x][y] = n; } /** Muove l’agente n dalla posizione x,y alla posizione x+dx, y+dy. * Il valori dx e dy sono nel range [-1,1] in quanto gli agenti si spostano di una sola posizione. * Se la posizione è occupata l’agente attende. Il metodo ritorna false nel caso l’agente n non sia nella posizione x,y. * @throws InterruptedException */ synchronized boolean move(int n, int x, int y, int dx, int dy) throws InterruptedException{ if(dx < -1 || dx > 1 || dy < -1 || dy > 1 || matrice[x][y] != n){ return false; //se il passo è troppo lungo o l'agente n non corrisponda alle coordinate ritorno false } while(matrice[x+dx][y+dy] != -1){ //finché la casella su cui voglio muovermi è occupata, aspetto wait(); } matrice[x+dx][y+dy] = n; //mi sposto sulla nuova casella matrice[x][y] = -1; //svuoto la casella precedente notify(); return true; } /** Ritorna l’id dell’agente nella posizione x,y. * Se la posizione è vuota ritorna -1. * Questo metodo viene usato per stampare la situazione ed eseguire test. */ int getAgent(int x, int y){ return this.matrice[x][y]; //mi basta ritornare la casella (le vuote sono già a -1) } }Ecco anche la mia soluzione!
public class Spazio { /** Campi: * - board è lo spazio dove si muovono gli agenti * - sx e sy sono le dimensioni della board */ private int sx; private int sy; private int[][] board; /** Costruttore: * - La board è di dimensioni date, x e y; * - la board è inizialmente tutta a -1 (non c'è nessun agente). */ public Spazio(int x, int y) { this.sx = x; this.sy = y; board = new int[x][y]; for (int i = 0; i < sx; i++) { for (int j = 0; j < sy; j++) { board[i][j] = -1; } } } // Metodi */ /** Register: per registrare l'esistenza degli agenti sulla board */ public synchronized void register(int n, int x, int y) { board[x][y] = n; } /** * Move: muove l’agente n dalla posizione x,y alla posizione x+dx, y+dy. * - I valori dx e dy sono nel range [-1,1] in quanto gli agenti si spostano di * una sola posizione. - Se la posizione è occupata l’agente attende. * - Il metodo ritorna false nel caso l’agente n non sia nella posizione x,y. */ public synchronized boolean move(int n, int x, int y, int dx, int dy) throws InterruptedException { /** * Condizione di blocco: * - Se la posizione d'arrivo non è libera (c'è un agente, quindi c'è un numero >= 0), il thread attende; */ while (board[x + dx][y + dy] >= 0) { wait(); } // Quando la posizione d'arrivo si libera... board[x + dx][y + dy] = n; // ...riposiziono l'agente nella nuova casella if (board[x][y] == n) { //se l'agente era presente nella posizione precedente... board[x][y] = -1; //...lo "cancello" dalla board... notifyAll(); //..e notifico gli altri thread return true; } else { return false; //ritorno false se l'agente era nella posizione sbagliata } } /** * getAgent() ritorna l’id dell’agente nella posizione x,y. Se la posizione * è vuota ritorna -1. Questo metodo viene usato per stampare la situazione * ed eseguire test. */ public synchronized int getAgent(int x, int y) { int val; if (board[x][y] < 0) { val = -1; } else val = board[x][y]; return val; } }La mia soluzione è molto simile alle vostre, ho usato però notify() anziché notifyAll() come ha fatto anche Andrea. In questo caso quale dei due è più corretto?
public class Spazio { private int[][] matrix; // matrice che rappresenta lo spazio public Spazio(int w, int h) { this.matrix = new int[w][h]; // crea una matrice w x h for(int i = 0; i < w; i ++) for(int j = 0; j < h; j ++) matrix[i][j] = -1; // inizializza tutte le celle a -1 } /* * ‘registra’ l’agente n nella posizione x,y. Questo metodo viene * invocato una sola volta quando gli agenti vengono creati. Serve * per inizializzare lo spazio nella configurazione iniziale. */ public synchronized void register(int n, int x, int y) { this.matrix[x][y] = n; // l'agente n occupa la cella m[x][y] } /* * muove l’agente n dalla posizione x,y alla posizione x+dx, y+dy. * Il valori dx e dy sono nel range [-1,1] in quanto gli agenti si * spostano di una sola posizione. Se la posizione è occupata * l’agente attende. Il metodo ritorna false nel caso l’agente n * non sia nella posizione x,y. */ public synchronized boolean move(int n, int x, int y, int dx, int dy) { if(this.matrix[x][y] != n) // se l'agente non si trova nella cella m[x][y] return false; // operazione fallita else { while(this.matrix[x + dx][y + dy] != -1) { // finche' la cella m[x][y] e' occupata try { this.wait(); // l'agente aspetta } catch(InterruptedException e) { System.err.println("InterruptedException: " + e.getMessage()); } } this.matrix[x + dx][y + dy] = n; // sposta l'agente n nella nuova posizione this.matrix[x][y] = -1; // libera la posizione precedente this.notify(); // avvisa un'altro agente che puo' avanzare return true; // operazione riuscita } } /* * ritorna l’id dell’agente nella posizione x,y. Se la posizione è * vuota ritorna -1. Questo metodo viene usato per stampare la * situazione ed eseguire test. */ public synchronized int getAgent(int x, int y) { return this.matrix[x][y]; // restituisce il valore della cella m[x][y] } }@Roberta: la verifica della presenza dell’agente è meglio farla prima del wait. Inutile attendere per poi ritornare false
@Gabriele: OK
@Lorenzo: meglio usare notifyAll quando hai thread che attendono eventi differenti. notify potrebbe sbloccare un thread che si riblocca e magari altri che potrebbero procedere attendono inutilmente. Di fatto in java usi spesso notifyAll avendo un’unica coda di attesa. Usi notify quando in effetti è indifferente quale thread viene sbloccato (coda in cui i thread attendono tutti lo stesso evento).