Per completezza, si rimanda al primo post del sito per ulteriori informazioni.

Si ricorda che dello stesso esercizio possono esistere più varianti.

Esercizio 1

Siano a un array di numeri, ordinato in senso crescente, e k un numero. Si scriva una funzione JS cerca(a, k, i, j), che, con un numero OTTIMO di operazioni di accesso ad a, restituisca true se k occorre nell’array a in una posizione compresa tra gli indici i e j, con 0<=i<j<a.length (indici i e j inclusi), e false altrimenti.

ESEMPI:

cerca([-21,22,23,45,67], 0, 0, 4) -> false

cerca([-21,22,23,45,67], -21, 0, 4) -> true

cerca([], -21, 0, 4) -> false

function cerca(a,k,i,j) {
  if (i < 0 || j < 0 || j >= a.length)
    return false;

  if (i >= j)
    return false;

  let middle = Math.floor((i+j)/2);
  
  if (a[middle] == k)
    return true;
  else {
    if (a[middle] > k)
      return cerca(a,k,i,middle-1);
    else // a[middle] < k
      return cerca(a,k,middle+1,j);
  }
}

Esercizio 2

Sia a un array di numeri interi distinti >=0, ordinato in senso crescente. Si scriva una funzione JS cercaId(a), che, con un numero OTTIMO di operazioni di accesso ad a, restituisce l’indice i tale che a[i]==i, se esiste, e -1 altrimenti. Si assuma che, se tale indice esiste, allora e' l’unico a verificare la condizione.

ESEMPI:

cercaId([-1,0,1,2,4]) -> 4

cercaId([-21,22,23,45,67]) -> -1

cercaId([0,2,3,4,5]) -> 0

function cercaId(a) {
  let left = 0;
  let right = a.length-1;
  let middle;

  while (left <= right) {
    middle = Math.floor((left+right)/2)

    if (a[middle] == middle)
      return middle;
    
    if (a[middle] < middle)
        left = middle + 1;
    else if (a[middle] > middle)
        right = middle - 1;
  }
  return -1;
}

Esercizio 3

Si scriva una funzione JS isAntisymmetric(m), con m una matrice quadrata (rappresentata come array di array). La funzione verifica se m è antisimmetrica, restituendo true se antisimmetrica e false altrimenti. Una matrice è antisimmetrica rispetto alla prima diagonale se gli elementi della diagonale sono tutti 0 e gli elementi della colonna c e riga r sono opposti in segno a quelli delle colonna r e riga c, per tutti gli indici r e c (con r diverso da c). Se la matrice in input non è quadrata, la funzione deve lanciare un’eccezione di tipo MatrixError. La classe MatrixError va definita in modo appropriato. ESEMPI:

isAntisymmetric([[0,2,-1],[-2,0,-4],[1,4,0]]) -> true

isAntisymmetric([[1,2,-1],[-2,0,-4],[1,4,0]]) -> false

isAntisymmetric([[1]]) -> false

isAntisymmetric([[0]]) -> true

isAntisymmetric([[0,2,-1],[-2,0,-4],[1,0]]) -> lancia MatrixError

class MatrixError extends Error {
  ;
}

function isAntisymmetric(m) {
  if (m.some((row) => row.length != m.length))
    throw new MatrixError("Matrice non quadrata");

  let i = 0, j;

  while (i < m.length) {
    j = 0;
    while (j < m[0].length) {
      if (i == j)
        if (m[i][j] != 0)
          return false;

      else {
        if (m[i][j] != -m[j][i])
          return false;
      }

      j++;

      if (j == m[0].length)
        i++;
    }
  }
  return true;
}

Esercizio 4 - TS

Si scriva una classe AnyMatrix che rappresenta una matrice rettangolare rxc (rappresentata come array di array) che contiene elementi omogenei, di qualsiasi tipo (stringhe, numeri, oggetti, ecc.). La classe deve offrire: Costruttore (che costruisce una matrice avente almeno dimensione 1x1), che prende anche un valore v con cui inizializzare il contenuto della matrice. Metodo setAll(dati: T[][]): boolean che, preso un array di array di dimensione pxq, usa i valori contenuti nel parametro dati come valori da assegnare a questa matrice. Se le dimensioni di dati e di questa matrice non coincidono, il metodo restituisce false; altrimenti, true. Metodo transpose() che restituisce una nuova AnyMatrix, trasposta di questa matrice.

NOTA: il metodo toString() vi e' gia' fornito. Non lo modificate. NOTA: nei test che faremo, useremo solo oggetti per cui esiste una rappresentazione sensata come stringa.

Esempi: Sia m una AnyMatrix di stringhe (inizializzata con il carattere che vi pare).

m.setAll([[“p”, “i”, “p”],[“qui”, “quo”, “qua”],[“super”, “qui”, “va”],[“qua”, “va”, “qua”]]) -> true

m.toString() -> 4x3:

|p,i,p|

|qui,quo,qua|

|super,qui,va|

|qua,va,qua|

m.transpose().toString() -> 3x4:

|p,qui,super,qua|

|i,quo,qui,va|

|p,qua,va,qua|

m.setAll([[“p”, “i”],[“qui”, “quo”],[“super”, “qui”],[“qua”, “va”]]) -> false

class AnyMatrix<T> {
  r: number;
  c: number;
  A: T[][];

  constructor(r: number = 1, c: number = 1, v: T) {
    this.r = r
    this.c = c
    this.A = []
    for (let i = 0; i < r; i++) {
      this.A[i] = []
      for (let j = 0; j < c; j++) {
        this.A[i][j] = v;
      }
    }
  }

  setAll(dati: T[][]): boolean {
    let colonnePrimaRiga = dati[0];
    if (this.A.some((row) => row.length != colonnePrimaRiga.length))
      return false;

    if (this.A.length != dati.length) // matrici con un numero di righe diverse
      return false;

    let i = 0, j;
    while (i < this.r) {
      j = 0;
      while (j < this.c) {
        this.A[i][j] = dati[i][j];

        j++;

        if (j == this.A[0].length)
          i++;
      }
    }
    return true;
  }

  transpose(): AnyMatrix<T> {
    let newMatrix = new AnyMatrix(this.r, this.c, this.A[0][0]);
    for (let i = 0; i < this.r; i++) {
      for (let j = 0; j < this.c; j++) {
        newMatrix.A[i][j] = this.A[j][i]
      }
    }
    return newMatrix;
  }

  toString(): string {
    return `${this.r}x${this.c}:\n|${this.A.join("|\n|")}|`
  }
}

let m = new AnyMatrix(4, 3, "");
console.log(m.setAll([["p", "i", "p"], ["qui", "quo", "qua"], ["super", "qui", "va"], ["qua", "va", "qua"]]), m.toString(), m.setAll([["p", "i"], ["qui", "quo"], ["super", "qui"], ["qua", "va"]]))

Esercizio 5 - TS

Si scriva in TypeScript una classe Pila che rappresenti, prevedibilmente, una pila. La pila deve poter gestire elementi omogenei, di qualsiasi tipo (stringhe, numeri, oggetti, ecc.). Potete implementare la pila con la struttura dati che preferite. Oltre a un costruttore, dovranno essere implementati i seguenti metodi:

p.push(el) - inserisce in cima alla pila p l’elemento el, e restituisce il numero di elementi presenti nella pila dopo l’inserimento

p.pop() - estrae l’elemento in cima alla pila, e lo restituisce. Se la pila e' vuota, restituisce null

p.top() - restituisce, senza rimuoverlo, l’elemento in cima alla pila. Se la pila e' vuota, restituisce null

p.size() - restituisce il numero di elementi presenti nella pila p

p. reset() - elimina tutti gli elementi dalla pila p, e restituisce 0

p.merge(p1) - sia p1 una pila non vuota, e dello stesso tipo di p. Il metodo inserisce tutti gli elementi in p1 (a partire da quello in cime) in cima a p, e restituisce il numero degli elementi complessivi di p dopo l’operazione di merge

p.print() - restituisce una stringa contenente la rappresentazione in stringa degli elementi in p (tutti gli elementi della coda sulla stessa riga, separati da virgola, senza spazi), a partire da quello in cima. NOTA: nei test che faremo, useremo solo oggetti per cui esiste una rappresentazione sensata come stringa.

ESEMPI: Sia p una nuova Pila di stringhe

p.pop() -> null

p.push(“ciao”) -> 1

p.push(“come”) -> 2

p.push(“va”) -> 3

p.push(“oggi”) -> 4

p.print() -> “oggi,va,come,ciao”

p.size() -> 4

p.top() -> “oggi”

p.print() -> “oggi,va,come,ciao”

Sia p1 una nuova Pila di stringhe

p1.push(“oggi”) -> 1

p1.push(“bene”) -> 2

p1.print() -> “bene,oggi”

p.merge(p1) -> 6

p.print() -> “oggi,bene,oggi,va,come,ciao”

class Pila<T> {
  pila: T[];

  constructor() {
    this.pila = [];
  }

  push(elem: T): number {
    return this.pila.unshift(elem);
  }

  pop(): T | null {
    return this.pila.length > 0 ? this.pila.shift()! : null;
  }

  size(): number {
    return this.pila.length;
  }

  top(): T | null {
    if (this.pila.length != 0)
      return this.pila[0];

    return null;
  }

  reset(): number {
    this.pila = [];
    return 0;
  }

  merge(p1: Pila<T>) {
    for (let i = 0; i < p1.size(); i++) {
      this.push(p1.pila[i])
    }
    return this.size();
  }

  print(): string {
    return this.pila.toString();
  }
}

Esercizio 6

Il quadrato di un grafo orientato G = (V, E) e' il grafo G2 = (V, E2) tale che (x, y) ∈ E2 se e solo se ∃u : (x, u) ∈ E ∧ (u, y) ∈ E. In altre parole, se esiste un percorso di due archi fra i nodi x e y. Scrivere una funzione JS quadratoG(G) con G un grafo rappresentato mediante una matrice di adiacenza. La funzione restituisce la matrice di adiacenza del grafo G2. Nota: assumete che la matrice di adiacenza passata come argomento sia quadrata, e che rappresenti una matrice di adiacenza di un grafo orientato.

ESEMPI:

quadratoG([[0,1,0,0],[0,0,1,1],[1,0,0,0],[0,0,0,0]])->[ [ 0, 0, 1, 1 ], [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 0, 0 ] ]

quadratoG([[0,1,1,0],[0,0,0,0],[0,1,0,1],[0,0,1,0]])->[ [ 0, 1, 0, 1 ], [ 0, 0, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 1, 0, 1 ] ]

function quadratoG(G) {
    let res = [];

    for (let i = 0; i < G.length; i++) {
      res[i] = [];
      for (let j = 0; j < G[0].length; j++) {
        let sum = 0;
        for (let k = 0; k < G[0].length; k++) {
          sum += G[i][k] * G[k][j];
        }
        res[i][j] = sum;
      }
    }
    return res;
  }

Esercizio 7

Scrivere una funzione JS floyd(i), dove i e' un numero naturale (>=0). Il triangolo di Floyd è un triangolo rettangolo che contiene numeri naturali, definito riempiendo le righe del triangolo con numeri consecutivi e partendo da 1 nell’angolo in alto a sinistra. Ecco, come esempio, le prime righe del triangolo di Floyd:

1

2 3

4 5 6

7 8 9 10

11 12 13 14 15

La funzione floyd(i) restituisce la riga i-esima del triangolo di Floyd, memorizzata in un array (le righe del triangolo si contano a partire da 0).

ESEMPI:

floyd(0) -> [1]

floyd(4) -> [11,12,13,14,15]

function floyd(i) {
  let arr = [1];

  if (i == 0)
    return arr;

  for (let j = 1; j <= i; j++) {
    arr[0] = arr[arr.length - 1] + 1;

    for (var k = 1; k < arr.length; k++) {
      arr[k] = arr[k - 1] + 1;
    }

    arr.push(arr[arr.length - 1] + 1)
  }

  return arr;
}

Esercizio 8 - TS

Si deve scrivere una classe TicTacToe che simuli il classico gioco del “tris”.

Il gioco si svolge su una tabella di dimensione 3x3, ed e' giocato da due giocatori. A turno, i giocatori scelgono una cella vuota e vi disegnano il proprio simbolo (di solito un giocatore ha come simbolo una “X” e l’avversario un cerchio “O” ). Vince il giocatore che riesce a disporre tre dei propri simboli in linea retta orizzontale, verticale o diagonale. Se la griglia viene riempita senza che nessuno dei giocatori sia riuscito a completare una linea retta (orizzontale, verticale o diagonale) di tre simboli, il gioco finisce in parità. [da Wikipedia]

Decidete liberamente quale struttura dati utilizzare per implementare la 9 caselle del gioco. La mossa “crocetta” e' rappresentata con “X” (lettera X maiuscola) e la mossa “cerchio” con “O” (lettera O maiuscola).

La classe, oltre al costruttore, deve fornire i seguenti metodi: move(i,j), che esegue una mossa sulla tabella, con 0<=i,j<=2, in posizione (i,j). Se l’ultima mossa giocata e' stata una crocetta, allora verra' inserito un cerchio in posizione (i,j); altrimenti una crocetta. La prima mossa di una partita e' sempre una crocetta, ed e' sempre una mossa valida (si vedano i casi descritti in seguito). Si considerino inoltre i seguenti casi: Se non e' possibile effettuare una mossa in posizione (i,j) perche' la cella e' gia' occupata, o perche' gli indici non sono corretti, allora viene restituito un oggetto avente due proprieta': res, il cui valore e' la stringa “no”, e last che contiene la stringa che rappresenta la mossa che si e' appena tentato di giocare. Se la mossa e' legale, allora viene giocata. Se la mossa porta a vincere una partita (c’e' un tris), viene restituito un oggetto avente due proprieta': res, il cui valore e' la stringa “tris”, e last che contiene la stringa che rappresenta la mossa che si e' appena giocata.
Se invece la mossa porta a riempire la tabella (senza “tris”), viene restituito un oggetto avente due proprieta': res, il cui valore e' la stringa “patta”, e last che contiene la stringa che rappresenta la mossa che si e' appena giocata. reset() che resetta il contenuto della tabella, e quindi inizia una nuova partita; il metodo restituisce sempre true.

Suggerimento: tenete opportunamente traccia dello “stato” del gioco, dove lo stato e' semplicemente l’ultima mossa che e' stata giocata o che si e' provato a giocare (crocetta o cerchio). Lo stato puo' quindi assumere valori “X” oppure “O” (la lettera O maiuscola).

ESEMPI:

Sia t un oggetto della classe TicTacToe.

t.move(0,0) -> {res: “ok”, last:“X”}

t.move(2,2) -> {res: “ok”, last:“O”}

t.move(0,0) -> {res: “no”, last:“X”}

t.move(0,0) -> {res: “no”, last:“X”}

t.move(2,2) -> {res: “no”, last:“X”}

t.move(1,1) -> {res: “ok”, last:“X”}

t.move(0,2) -> {res: “ok”, last:“O”}

t.move(1,0) -> {res: “ok”, last:“X”}

t.move(1,2) -> {res: “tris”, last:“O”}

t.reset() -> true;

interface esito {
  res: string;
  last: string;
}

class TicTacToe {
  grid: string[][];
  currentMove: string;

  constructor() {
    this.grid = [];

    for (let i = 0; i < 3; i++) {
      this.grid[i] = [];
      for (let j = 0; j < 3; j++) {
        this.grid[i][j] = "";
      }
    }

    this.currentMove = "X";
  }

  move(i: number, j: number): esito {

    // NB: la prima mossa è sempre una crocetta

    if ((i < 0 || i > 2) || (j > 2 || j < 0) || (this.grid[i][j] != ''))
      return { res: "no", last: this.currentMove }

    this.grid[i][j] = this.currentMove;

    // controllo riga
    let rowSum = 0;
    for (let col = 0; col < 3; col++) {
      if (this.grid[i][col] == this.currentMove)
        rowSum++;
    }

    if (rowSum == 3)
      return { res: "tris", last: this.currentMove }

    // controllo colonna
    let colSum = 0;
    for (let row = 0; row < 3; row++) {
      if (this.grid[row][j] == this.currentMove)
        colSum++;
    }

    if (colSum == 3)
      return { res: "tris", last: this.currentMove }

    // diagonale principale
    if (i == j) {
      let diagSum = 0;
      for (let k = 0; k < 3; k++) {
        if (this.grid[k][k] == this.currentMove)
          diagSum++;
      }

      if (diagSum == 3)
        return { res: "tris", last: this.currentMove }
    }

    // diagonale secondaria
    if (i + j == 2) {
      let diagSum = 0;
      for (let k = 0; k < 3; k++) {
        if (this.grid[2 - k][k] == this.currentMove)
          diagSum++;
      }

      if (diagSum == 3)
        return { res: "tris", last: this.currentMove }
    }

    for (let row = 0; row < 3; row++) {
      for (let col = 0; col < 3; col++) {
        if (this.grid[row][col] == "") {
          let prevMove = this.currentMove;

          if (this.currentMove == "X")
            this.currentMove = "O"
          else
            this.currentMove = "X";

          return { res: "ok", last: prevMove }
        }
      }
    }

    return { res: "patta", last: this.currentMove }
  }

  reset() {
    this.grid.forEach((row: string[]) => row.fill(""));
    this.currentMove = "X"
    return true;
  }
}

let ttt = new TicTacToe();

console.log(ttt.move(0, 0)) // -> { res: "ok", last: "X" }
console.log(ttt.grid)
console.log(ttt.move(2, 2)) // -> { res: "ok", last: "O" }
console.log(ttt.grid)
console.log(ttt.move(0, 0)) //-> { res: "no", last: "X" }
console.log(ttt.grid)
console.log(ttt.move(0, 0))  //-> { res: "no", last: "X" }
console.log(ttt.grid)
console.log(ttt.move(2, 2)) //-> { res: "no", last: "X" }
console.log(ttt.grid)
console.log(ttt.move(1, 1)) //-> { res: "ok", last: "X" }
console.log(ttt.grid)
console.log(ttt.move(0, 2)) //-> { res: "ok", last: "O" }
console.log(ttt.grid)
console.log(ttt.move(1, 0)) //-> { res: "ok", last: "X" }
console.log(ttt.grid)
console.log(ttt.move(1, 2)) //-> { res: "tris", last: "O" }
console.log(ttt.grid)