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

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

SpitOut

Si scriva una funzione spitOut(a,p) che, dati come argomenti un array a e una funzione p, stampi tramite console.log() tutti gli elementi e di a tali che l’invocazione di p(e) restituisca true o un valore che viene promosso a true Esempi:

spitOut([12,7,14,0,561],e=>(e%3==0)) → stampa 12, 0, 561

spitOut(“la”,“vispa”,“teresa”,“solea”],e=>e.indexOf(“s”)) → stampa la, vispa, teresa

spitOut([31,3.1415, 1.4142, 7],e=>e==Math.round(e)) → stampa 31, 7

function spitOut(a, p) {
  let arr = []
  for (let i in a) {
    if (p(a[i]))
      arr.push(a[i]);
  }
  return arr.join(', ')
}

// oppure

function spitOut2(a, p) {
  a = a.filter((elem) => p(elem));
  console.log(a.join(', '));
}

SpitOut.ts

Si risolva l’esercizio SpitOut precedente, scrivendo però codice in TypeScript con tutti i tipi pienamente annotati. Attenzione: risolvete l’esercizio indicando tutti i tipi, senza usare il tipo any Suggerimento: si ripassino in particolare i tipi generici (generics)

function spitOut<T>(a: Array<T>, p: (e: T) => boolean | number): void {
    a = a.filter((elem) => p(elem));
    console.log(...a);
}

function spitOut2<T>(a: Array<T>, p: (e: T) => T | number | boolean) {
    let arr: Array<T> = [];
    for (let i = 0; i < a.length; i++) {
        if (p(a[i]))
            arr.push(a[i]);
    }
    return arr.join(', ');
}

Crocette

Si consideri una matrice A di m×n interi, ciascuno dei quali può essere 0 o 1, rappresentata come un array di m righe (ogni riga è un array di n interi). All’interno di A, una posizione (x,y) si dice contenere una “crocetta” se la cella (x,y) vale 1, come anche quelle subito sopra, sotto, a destra e a sinistra, mentre le quattro celle poste in diagonale valgono 0. Si scriva una funzione crocette(A) che, ricevuta una matrice come descritto sopra, restituisca un array di tutte le coordinate (x,y) in A che contengono crocette, in cui ogni coordinata è rappresentata come un vettore di due elementi [x, y]. L’origine è (0,0) e corrisponde all’angolo in alto a sinistra; l’asse Y va verso il basso. Esempi

Sia A:

A =[[ 1,0,0,1,1 ],
    [ 0,1,0,1,0 ],
    [ 1,1,1,1,1 ],	
    [ 0,1,0,1,0 ],
    [ 1,1,1,1,1 ],
    [ 0,1,0,1,1 ]]

allora, crocette(A) → [[1,2],[3,2],[1,4]]

function crocette(A) {
  let coords = [];

  // il -1 è per evitare di scandire inutilmente il bordo della matrice
  for (let row = 1; row < A.length - 1; row++) {
    for (let col = 1; col < A[0].length - 1; col++) {
      // controllo se in posizione (row,col) ho 1 e pure subito sopra, sotto, a destra e a sinistra. Sfrutto l'AND cortocircuitato
      if (A[row][col] == 1 && (A[row-1][col] + A[row+1][col] + A[row][col-1] + A[row][col+1] == 4)) {
        // controllo che le quattro celle poste in diagonale valgano 0
        if (A[row-1][col-1] + A[row+1][col+1] + A[row-1][col+1] + A[row+1][col-1] == 0)
          coords.push([col,row])
      }
    }
  }
  return coords;
}

Crocettex

Si scriva una funzione crocettex che si comporti esattamente come crocette dell’esercizio precedente, ma che in più verifichi che la matrice ricevuta come argomento abbia il formato corretto, e in caso contrario lanci le seguenti eccezioni:

  • TooSmallException - se la matrice è più piccola di 3x3
  • InvalidFormatException - se la matrice ha righe di lunghezza diversa
  • BadContentException - se la matrice contiene qualunque valore diverso da 0 e 1

Le eccezioni vanno realizzate come oggetti di tipo diverso; gli oggetti lanciati possono contenere ulteriori informazioni di dettaglio, a vostra discrezione.


class TooSmallException extends Error {
  ;
}

class InvalidFormatException extends Error {
  ;
}

class BadContentException extends Error {
  ;
}

function crocettex(A) {
  if (A.length < 3 || A.some((row) => row.length < 3))
    throw new TooSmallException("Matrice più piccola della dimensione 3x3!")

  /* A[0].length = lunghezza prima riga */
  if (A.some((row) => row.length != A[0].length))
    throw new InvalidFormatException("La matrice contiene righe di lunghezza diversa!");

  if (A.some((row) => row.find((elem) => elem != 0 && elem != 1) != undefined))
    throw new BadContentException("La matrice contiene un valore diverso da 0 e da 1!")

  return crocette(A);
}


let tooSmallA = [[1, 2], [1, 2]]

let InvalidA = [[1, 0, 0, 1, 1],
                [0, 1, 0, 1, 0],
                [1, 1, 1, 1, 1],
                [0, 1, 0, 1],
                [1, 1, 1, 1, 1],
                [0, 1, 0, 1, 1]]

let BadA = [[1, 0, 0, 1, 1],
            [0, 1, 0, 1, 0],
            [1, 1, 1, 1, 1],
            [0, 1, 0, 2, 0],
            [1, 1, 1, 1, 1],
            [0, 1, 0, 1, 1]]

MultiSet

Si scriva una classe MultiSet che implementi un multiinsieme (ovvero, un insieme che può contenere più volte lo stesso elemento). La classe deve implementare i seguenti metodi:

  • add(e) - inserisce l’elemento e nel multiinsieme
  • remove(e) - rimuove un elemento e dal multiinsieme; lancia un’eccezione NoSuchElementException se e non è presente nel multiinsieme
  • size() - restituisce il numero di elementi contenuti nel multiinsieme (si implementi come una proprietà di sola lettura)
  • union(S) - restituisce un nuovo multiinsieme contenente l’unione del multiinsieme con l’altro multiinsieme S (si usi il metodo add)
  • diff(S) - restituisce un nuovo multiinsieme contenente la differenza fra il multiinsieme e l’altro multiinsieme S (si usi il metodo remove)
class NoSuchElementException extends Error {
  ;
}

class MultiSet {
  constructor() {
    this.multiinsieme = [];
  }

  static n_elem = 0;

  add(e) {
    this.multiinsieme.push(e);
  }

  remove(e) {
    if (!this.multiinsieme.includes(e))
      throw new NoSuchElementException(`elemento ${e} non presente nel multiinsieme.`);

    // se ho più occorrenze di e elimino la prima scorrendo in ordine crescente dall'indice 0
    this.multiinsieme.splice(this.multiinsieme.indexOf(e), 1);
  }

  get size() {
    return this.multiinsieme.length;
  }

  union(S) {
    let m = new MultiSet();
    m.multiinsieme = new Array([...this.multiinsieme])
    for (let i in S.multiinsieme)
      m.add(S.multiinsieme[i]);

    return m;
  }

  diff(S) {
    let a = [...this.multiinsieme]
    let b = [...S.multiinsieme];
    let res = [];

    for (let i in a) {
      if (b.includes(a[i]))
        b.splice(b.indexOf(a[i], 1)); // levo una occorrenza dell'elem a[i]
      else
        res.push(a[i]);
    }
    return res;
  }
}

MultiSet.ts

Si ripeta l’esercizio MultiSet, scrivendo però il codice in TypeScript. Come già in SpitOut.ts, si abbia cura di dichiarare correttamente tutti i tipi dei metodi e delle proprietà, usando dove necessario i generics. Si ricordi che anche le eccezioni lanciate andranno opportunamente adattate.

class MultiSet<T> {
  multiinsieme: Array<T>;
  constructor() {
      this.multiinsieme = [];
  }

  add(e: T) {
      this.multiinsieme.push(e);
  }

  remove(e: T) {
      if (!this.multiinsieme.includes(e))
          throw new NoSuchElementException(`elemento ${e} non presente nel multiinsieme.`);

      // se ho più occorrenze di e elimino la prima scorrendo in ordine crescente dall'indice 0
      this.multiinsieme.splice(this.multiinsieme.indexOf(e), 1);
  }

  get size() {
      return this.multiinsieme.length;
  }

  union(S : MultiSet<T>) {
      let m = new MultiSet();
      m.multiinsieme = new Array([...this.multiinsieme])
      for (let i in S.multiinsieme)
        m.add(S.multiinsieme[i]);
  
      return m;
    }

  diff(S : MultiSet<T>) {
      let a : Array<T> = [...this.multiinsieme]
      let b : Array<T> = [...S.multiinsieme];
      let res : Array<T> = [];

      for (let i in a) {
          if (b.includes(a[i]))
              b.splice(b.indexOf(a[i], 1)); // levo una occorrenza dell'elem a[i]
          else
              res.push(a[i]);
      }

      let resMS = new MultiSet();
      resMS.multiinsieme = res;
      return resMS;
  }
}

reverse2

Il metodo reverse() chiamato su un array a, modifica a invertendo l’ordine dei suoi elementi. Si aggiunga un metodo reverse2() a tutti gli array del vostro programma, che chiamato su un array a, restituisca un nuovo array contenente gli stessi elementi di a, in ordine inverso.

Attenzione: per questo esercizio, non potete usare reverse() per definire reverse2(). Variante: svolgete l’esercizio su una sola riga, senza chiamare nessun metodo predefinito degli array.

Array.prototype.reverse2 = function() {
  let arr = [];

  for (let i = 0; i < this.length; i++) {
    arr.unshift(this[i]);
  }

  return arr;
}

// variante one-liner

Array.prototype.reverse3 = function() {
  if (this.length == 0)
    return [];
  let [a, ...b] = this
  return [...b.reverse3(), a]
}

GroupAnagrams

Si scriva una funzione groupAnagrams(a) che, dato un array di stringhe a, raggruppi tutte le stringhe in a che sono anagrammi l’una dell’altra, e restituisca un array contenente i vari gruppi (rappresentati a loro volta come array di stringhe). L’ordine del risultato non è rilevante. Esempi:

groupAnagrams([“scarabeo”, “arabo”, “noob, “arabesco”, “bono”]) → [ [ ‘scarabeo’, ‘arabesco’ ], [ ‘arabo’ ], [ ‘noob’, ‘bono’ ] ]

groupAnagrams([]) → []

function groupAnagrams(a) {
  if (a.length == 0)
    return [];

  let map = {};

  for (let elem of a) {
    let str = [...elem].sort().join('');

    if (str in map) {
      if (!map[str].includes(elem))
        map[str].push(elem);
    } else {
      map[str] = [];
      map[str].push(elem);
    }
  }

  return Object.values(map);
}

GroupAnagrams*

Si scriva una versione di groupAnagrams(), dall’esercizio precedente, implementata come generatore. Esempi:

var x=groupAnagrams([“scarabeo”, “arabo”, “noob, “arabesco”, “bono”])

x.next().value → [‘scarabeo’, ‘arabesco’]

x.next().value → [‘arabo’]

x.next().value → [‘noob’, ‘bono’]

x.next().value → undefined

function* groupAnagramsGen(a) {
  if (a.length == 0)
    return [];

  let map = {};

  for (let elem of a) {
    let str = [...elem].sort().join('');
    /* console.log(elem,str) */
    if (str in map) {
      if (!map[str].includes(elem))
        map[str].push(elem);
    } else {
      map[str] = [];
      map[str].push(elem);
    }
  }

  for (let elem of Object.values(map)) {
    yield elem;
  }
}

Malomostro

Si modifichi il Platform Game sviluppato a lezione, aggiungendo un nuovo tipo di Actor, detto Malomostro (rappresentato da una “M” nella mappa del livello), che abbia un comportamento simile a quello della lava a scorrimento orizzontale – ma con la differenza che, anziché cambiare direzione solo quando incontra un muro, ha una probabilità di cambiare direzione in maniera spontanea in qualunque momento. La grafica del Malomostro è a vostra discrezione. Suggerimento: è sensato che il Malomostro abbia, ad ogni update() una probabilità dell’1% di cambiare direzione.

// TO ADD, preferibilmente con un link a repl.it con una demo

Complex.ts

Si definisca in TypeScript una classe Complex che rappresenta i numeri complessi (a+bi), con le relative operazioni. La classe deve implementare:

  • Un costruttore con due argomenti (parte reale e parte immaginaria, ciascuna delle quali può essere un numero reale, oppure un numero razionale come definito nella classe Rational vista a lezione)
  • Un costruttore con un argomento, che può essere un numero o un Rational (nel qual caso, si assume che l’argomento sia la parte reale e che la parte immaginaria sia 0i), oppure un Complex (nel qual caso, il costruttore restituisce lo stesso valore dell’argomento)
  • Le operazioni di somma e moltiplicazione fra Complex, definite come (a,b)+(c,d) = (a+c,b+d) e (a,b)∙(c,d) = (ac-bd,bc+ad)
  • Opportune funzioni di accesso che consentano di recuperare le proprietà a (parte reale) e bi (parte immaginaria), nonché le corrispondenti proprietà r (modulo) e phi (angolo), ricordando che per un Complex z, si ha z = a+bi = r(cos(phi) + i sin(phi)) Si curi di definire in maniera rigorosa tutti i tipi coinvolti.
class Complex {
  real: number;
  imaginary: number;

  constructor(a: Rational | number | Complex, b?: Rational | number) {
      // a -> parte reale
      // b -> parte immaginaria

      // caso Rational
      if (a instanceof Rational && !b) { // 1 solo argomento di tipo Rational
          this.real = Number(a.toString());
          this.imaginary = 0;
      } else if (a instanceof Rational && b) { // 2 argomenti (il primo Rational), di cui il secondo va identificato il tipo
          this.real = Number(a.toString());

          if (typeof b == 'number') // 2nd arg è un numero
              this.imaginary = b;
          else if (b instanceof Rational) // 2nd arg è un Rational
              this.imaginary = Number(b.toString())
      }

      // caso numero
      else if (typeof a == 'number' && !b) {
          this.real = a;
          this.imaginary = 0;
      } else if (typeof a == 'number' && b) {
          this.real = a;

          if (typeof b == 'number')
              this.imaginary = b;
          else if (b instanceof Rational)
              this.imaginary = Number(b.toString());
      }

      // caso Complex
      else if (a instanceof Complex) {
          this.real = a.real;
          this.imaginary = a.imaginary;
      }
  }

  sum(c: Complex): Complex {
      return new Complex(this.real + c.real, this.imaginary + c.imaginary);
  }

  mul(c: Complex) {
      return new Complex((this.real * c.real) - (this.imaginary * c.imaginary), (this.imaginary * c.real) + (this.real * c.imaginary))
  }

  get a(): Rational | number {
      return this.real;
  }

  get b(): Rational | number {
      return this.imaginary;
  }

  // Modulo
  get r(): number {
      return Math.sqrt(this.real ** 2 + this.imaginary ** 2);
  }

  // Angolo
  get phi(): number {
      if (this.real > 0) {
          return Math.atan(this.imaginary / this.real)
      } else if (this.real < 0) {
          return Math.atan(this.real / this.imaginary) + Math.PI;
      }
  }
}

Single

Si scriva una funzione single(a) che, dato come argomento un array a di interi di lunghezza dispari n, ordinato in ordine crescente e in cui tutti gli elementi tranne uno appaiono esattamente due volte, restituisca il valore dell’unico elemento “single” che appare una sola volta. Attenzione: dovete risolvere questo problema in O(log n). Esempi:

single([3,3,5,5,7,10,10,12,12]) → 7

single([1,2,2,5,5,8,8]) → 1

single([1,1,4,4,5,5,9,9,12,12,15,18,18]) → 15

function single(a, left = 0, right = a.length - 1) {
  if (right - left == 1)
    return a[0]

  if (right - left == 3)
    if (a[0] == a[1])
      return a[2]
    else if (a[1] == a[2])
      return a[0];

  centre = Math.round((left + right) / 2);
  if ((a[centre] == a[centre + 1])) {
    return single(a, centre + 2, right);
  } else if ((a[centre] == a[centre - 1])) {
    return single(a, left, centre - 2);
  } else
    return a[centre];
}