Soluzioni collezione esercizi Scala - Programmazione Funzionale e Parallela

Soluzioni di alcuni esercizi

Si riportano alcune soluzioni di esercizi proposti durante il corso.

Esercizio 20 - LSList (funzioni di ordine superiore su liste - sottosequenza più lunga)

LSList.scala:

object LSList {
    def longestSublist[T](p:T=>Boolean)(l:List[T]):List[T] = {
        val vuota = List[T]()
        val (curr,max) = l.foldLeft((vuota,vuota))(
            (acc,x) => {
                val (curr,max) = acc
                if (p(x)) (x::curr, max)
                else (vuota, if (curr.size > max.size) curr else max)
            }
        )
        (if (curr.size > max.size) curr else max).reverse
    }
}

LSListMain.scala:

object LSListMain extends App {
    val s1 = LSList.longestSublist((_:Int)>0)(List(-4,5,3,6,0,3,4,-1))
    println(s1 + " (corretto: "+List(5,3,6)+")")

    val s2 = LSList.longestSublist((_:Int)>=0)(List(1,-4,5,3,6,-1,3,4,1,6))
    println(s2 + " (corretto: "+List(3,4,1,6)+")")

    val s3 = LSList.longestSublist((_:Int)<0)(List(1,2,3))
    println(s3 + " (corretto: "+Nil+")")
}

Esercizio 23 (estensione del linguaggio con nuovi costrutti)

E23.scala:

object E23 {
    def profila[T](body: =>T):(T,Long) = {
        val start = System.nanoTime
        val v = body                        // il body passato come parametro per nome viene valutato qui
        val t = System.nanoTime - start
        (v,t)
    }
}

E23Main.scala:

import E23._

object E23Main extends App {
    val (v,t) = profila {
        println("Valutazione espressione...")
        (1 to 1000000).map(_.toLong).sum
    }

    println("Valore prodotto: "+v)
    println("Tempo richiesto: "+t*1E-9+" secondi")
}

Esercizio 24 (funzioni su liste di oggetti - data analytics)

E24.scala:

object E24 {

    // Query 1: estrarre tutti gli studenti con età compresa tra 20 e 24 anni (inclusi) che hanno sostenuto l'esame di "PFP"

    // con metodi delle collezioni
    def query1(l:List[Studente]) =
        l.filter(s => s.età >= 20 && s.età <= 24 && (s.esami contains "PFP"))

    // con for comprehension
    def query1_bis(l:List[Studente]) =
        for (s <- l ; if (s.età >= 20 && s.età <= 24 && (s.esami contains "PFP"))) yield s

    // Query 2: estrarre tutti gli studenti con età strettamente inferiore a 24 anni che hanno sostenuto almeno due esami

    // con metodi delle collezioni
    def query2(l:List[Studente]) =
        l.filter(s => s.età <= 24 && s.esami.size >= 2)    

    // con for comprehension
    def query2_bis(l:List[Studente]) =
        for (s <- l ; if (s.età <= 24 && s.esami.size >= 2)) yield s
}

E24Main.scala:

case class Studente(nome:String, età:Int, esami:List[String])

object E24Main extends App {
    val q = List(
                 Studente("Marco",   23, List("PFP","SC")), 
                 Studente("Laura",   19, List("SC", "FI1", "PFP")), 
                 Studente("Stefano", 23, List("SC", "FI1")), 
                 Studente("Marco",   25, List("SC", "FI1", "FI2")), 
                 Studente("Paola",   22, List("SC", "PFP"))
            )

    println(E24.query1(q))
    println(E24.query1_bis(q))
    println(E24.query2(q))
    println(E24.query2_bis(q))
}

Esercizio 25 (classe per numeri razionali)

Rational.scala:

// ni e di sono variabili di istanza private
// ai fini dell'esercizio poteva andare bene anche omettere `private val`
case class Rational(private val ni:Int, private val di:Int) {

    // metodi ausiliari
    private def sgn(x:Int,y:Int) = if (x*y < 0) "-" else ""
    private def mcd(x:Int,y:Int):Int = if (y==0) x else mcd(y,x%y)

    // variabili di istanza pubbliche
    val n = ni/mcd(ni, di)
    val d = di/mcd(ni, di)

    // toString
    override def toString = sgn(n,d)+Math.abs(n)+"/"+Math.abs(d)

    // operatori aritmetici
    def +(r:Rational) = Rational(n*r.d+r.n*d, d*r.d)
    def -(r:Rational) = Rational(n*r.d-r.n*d, d*r.d)
    def *(r:Rational) = Rational(n*r.n, d*r.d)
    def /(r:Rational) = Rational(n*r.d, d*r.n)

    // operatori relazionali
    // non usiamo il == di default generato da case class perché userebbe anche ni e di
    // il metodo != è automaticamente derivato come !equals
    override def equals(that:Any) = that match {
        case r:Rational => n == r.n && d == r.d
        case _ => false
    }

    // a volerlo fare bene, Rational dovrebbe implementare il trait Ordered[Rational]
    // e ridefinire il metodo compare, ma non ne abbiamo parlato a lezione
    // https://www.scala-lang.org/api/current/scala/math/Ordered.html;
    // ai fini dell'esercizio va bene comunque la seguente soluzione
    def <(r:Rational) = n*r.d < d*r.n
}

E25Main.scala:

object E25Main extends App {
    val r1 = Rational(2, 7)
    val r2 = Rational(8, 6)
    val r3 = Rational(4, 14)
    println(r1+r2)  // stampa 34/21
    println(r1-r2)  // stampa -22/21
    println(r1*r2)  // stampa 8/21
    println(r1/r2)  // stampa 3/14
    println(r1==r3) // stampa true
    println(r1!=r3) // stampa false
    println(r1!=r2) // stampa true
    println(r1<r2)  // stampa true
    println(r2<r1)  // stampa false
}

Esercizio 26 (disegno di una griglia n x n - grafica 2D)

Model2D.scala:

object Model2D {

    def getGrid(n:Int) = {
        val step  = 1.0/(n-1)
        val horiz = (0 to n-1).map(y => Line(0.0, y*step, 1.0, y*step)).toList  // linee orizzontali
        val vert  = (0 to n-1).map(x => Line(x*step, 0.0, x*step, 1.0)).toList  // linee verticali
        horiz ::: vert                                                          // concatenazione delle liste
    }

    def main(args:Array[String]) {
        println("Displaying 20x20 grid...")
        Frame2D.display(Model2D.getGrid(3), 500, 500)
    }
}

Esercizio 27 (disegno di un Mandala toroidale - grafica 2D)

Model2D.scala:

object Model2D {

    def getToroidalMandala(numPetals:Int) = {
        def rad(i:Int) = 2.0*math.Pi*i/numPetals
        (0 to numPetals-1).map(i => Circle(0.5+math.cos(rad(i))*0.25, 0.5+math.sin(rad(i))*0.25, 0.25)).toList
    }

    def main(args:Array[String]) {
        println("Displaying Toroidal Mandala...")
        Frame2D.display(Model2D.getToroidalMandala(24), 500, 500)
    }
}

oppure, usando for comprehension:

object Model2D {

    def getToroidalMandala(numPetals:Int) = {
        val l = for {
            i <- 0 to numPetals-1
            rad = 2.0*math.Pi*i/numPetals
            x   = 0.5+math.cos(rad)*0.25
            y   = 0.5+math.sin(rad)*0.25
        } yield Circle(x, y, 0.25)

        l.toList
    }

    def main(args:Array[String]) {
        println("Displaying Toroidal Mandala...")
        Frame2D.display(Model2D.getToroidalMandala(24), 500, 500)
    }
}

Esercizio 28 (cifrario di Cesare - metodi implicit)

E28.scala:

import scala.language.implicitConversions

class MyString(s:String) {
    def rot(k:Int):String = {
        def f(c:Char):Char = {
            val m = 'Z' - 'A' + 1 // dimensione dell'alfabeto
            if (c >= 'A' && c <= 'Z') ('A' + (k + c - 'A') % m).toChar
            else if (c >= 'a' && c <= 'z') ('a' + (k + c - 'a') % m).toChar
            else c
        }
        s.map(f)
    }
}

object E28 {
    implicit def string2MyString(s:String) = new MyString(s)
}

E28Main.scala:

import E28._

object E28Main extends App {
    def p(s:String, r:String, k:Int) = 
        println("\"" + s + "\" -> \"" + s.rot(k)  + "\" (corretto: \""+ r + "\")")
    val (s1, r1, k1) = ("Zorro", "Apssp", 1)
    val (s2, r2, k2) = ("Apssp", "Zorro", 26-1)
    val (s3, r3, k3) = ("Hello World!", "Uryyb Jbeyq!", 13)
    val (s4, r4, k4) = ("Uryyb Jbeyq!", "Hello World!", 26-13)
    p(s1, r1, k1)
    p(s2, r2, k2)
    p(s3, r3, k3)
    p(s4, r4, k4)
}

Esercizio 29 (operazioni su alberi binari - classi)

E29.scala:

sealed abstract class BinTree {
    def sum:Int = this match {
        case T(l,e,r) => e + l.sum + r.sum 
        case E() => 0
    }
}

// albero non vuoto
case class T(l:BinTree, e:Int, r:BinTree) extends BinTree 

// albero vuoto
case class E() extends BinTree

E29Main.scala:

object E29Main extends App {
    val t1 = T(E(), 10, E())
    val t2 = T(E(), 5, E())
    val t3 = T(t1, 7, t2)
    val t4 = T(t3, 2, E())
    println(t1.sum + " (corretto: 10)")
    println(t2.sum + " (corretto: 5)")
    println(t3.sum + " (corretto: 22)")
    println(t4.sum + " (corretto: 24)")
}

Esercizio 30 (map su alberi binari - classi)

E30.scala:

sealed abstract class BinTree {
    def map(f:Int=>Int):BinTree = this match {
        case E() => E()
        case T(l,e,r) => T(l.map(f),f(e),r.map(f))
    }
}

// albero non vuoto
case class T(l:BinTree, e:Int, r:BinTree) extends BinTree

// albero vuoto
case class E() extends BinTree

E30Main.scala:

object E30Main extends App {
    val t1 = T(E(), 10, E())
    val t2 = T(E(), 5, E())
    val t3 = T(t1, 7, t2)
    val t4 = T(t3, 2, E())
    val t = t4.map(_*2)
    println(t + " (corretto: T(T(T(E(),20,E()),14,T(E(),10,E())),4,E()))")
}

Esercizio 31 (elemento più frequente in una sequenza - collezioni, classe `Option`)

E31.scala:

object E31 {
    def piùFrequente[T](s:Seq[T]):Option[(T,Int)] =
        if (s.isEmpty) None
        else {
            val (x,l) = s.groupBy(identity).maxBy(_._2.size)
            Some((x,l.size))
        }
}

E31Main.scala:

object E31Main extends App {
    val s1 = Seq(1,2,4,2,1,1,5,2,4,2,5)
    val t1 = E31.piùFrequente(s1) getOrElse "errore"
    println(t1 + " (corretto: (1,3))")

    val s2 = Seq()
    val t2 = E31.piùFrequente(s2) getOrElse "errore"
    println(t2 + " (corretto: errore)")

    val s3 = Vector("uno", "due", "uno")
    val t3 = E31.piùFrequente(s3) getOrElse "errore"
    println(t3 + " (corretto: (uno,2))")
}

Esercizio 35 - `MyRed` (replica metodo reduce - ricorsione su liste)

MyRed.scala:

import scala.language.implicitConversions

class MyList[T](l:List[T]) {
    def myReduce(f:(T,T)=>T):Option[T] = l match {
        case Nil    => None
        case h::Nil => Some(h)
        case h::t   => {
            def aux(q:List[T], acc:T):T =
                if (q.isEmpty) acc
                else aux(q.tail, f(acc, q.head))
            Some(aux(t, h))
        }
    }
}

object MyRed {
    implicit def list2MyList[T](l:List[T]) = new MyList(l)
}

MyRedMain.scala:

import MyRed._

object MyRedMain extends App {
    val l = List.range(1,1000000)

    val v1 = l.myReduce(_+_)
    println("Test 1: "+v1+" (corretto: " + Some(l.reduce(_+_)) + ")")

    val v2 = List(1).myReduce(_+_)
    println("Test 2: "+v2+" (corretto: " + Some(List(1).reduce(_+_)) + ")")

    val v3 = List[Int]().myReduce(_+_)
    println("Test 3 "+v3+" (corretto: " + None + ")")
}

Esercizio 36 - `PCoin` (numero di resti possibili - parallelismo su liste)

PCoin.scala:

object PCoin {
    // versione sequenziale
    def countChange(amount:Int, coins:List[Int]):Int =
        if (amount == 0) 1
        else if (coins.isEmpty || amount < 0) 0
        else countChange(amount - coins.head, coins.tail) + countChange(amount, coins.tail)

    // versione parallela
    def countChangePar(amount:Int, coins:List[Int], maxThreads:Int = Runtime.getRuntime().availableProcessors()):Int =
        if (amount == 0) 1
        else if (coins.isEmpty || amount < 0) 0
        else if (maxThreads < 2) countChange(amount, coins)
        else {
            val (a,b) = Par.par { countChangePar(amount - coins.head, coins.tail, maxThreads/2) }
                                { countChangePar(amount, coins.tail, maxThreads/2)              }
            a+b
        }
}

PCoinMain.scala:

object PCoinMain extends App {
    val coins = List(10,100,1,2,5,20,10,50,1,200,100,5,20,10,10,5,1,20,50,1,5,200,2,50,20,1,1,2,5,200,100)
    val a1 = 899
    println("Versione sequenziale...")
    val (v1, t1)   = Prof.profila { PCoin.countChange    (a1, coins) }
    println("Versione parallela...")
    val (vp1, tp1) = Prof.profila { PCoin.countChangePar (a1, coins) }
    println("Test: " + vp1 + " (corretto: " + v1 + " - tempo seq: "+t1*1E-9+" sec - tempo par: "+tp1*1E-9+" sec)")
}

Par.scala:

object Par {
    def par[A,B](a: =>A)(b: =>B):(A,B) = {
        var resA:Option[A] = None
        val r = new Runnable {
            def run() = resA = Some(a)
        }
        val t = new Thread(r)
        t.start()
        val resB = b
        t.join()
        (resA.get, resB)
    }
}

Prof.scala

object Prof {
    def profila[T](body: =>T):(T,Long) = {
        val start = System.nanoTime
        val v = body                        // il body passato come parametro per nome viene valutato qui
        val t = System.nanoTime - start
        (v,t)
    }
}

Esercizio 37 - `IsRot` (uguaglianza a meno di rotazioni - operazioni su sequenze)

IsRot.scala:

import scala.language.implicitConversions

class MySeq[T](l:Seq[T]) {
    def isRot(m:Seq[T]):Option[Int] = {
        val res = for {
            i <- 0 until m.size
            (a,b) = m splitAt i
            if (l == b ++ a)
        } yield i
        if (res.isEmpty) None else Some(res.head)
    }
}

object IsRot {
    implicit def seq2MySeq[T](l:Seq[T]) = new MySeq(l)
}

IsRotMain.scala`

import IsRot._

object IsRotMain extends App {
    val l1:Seq[Char] = "Hello world"
    val m1:Seq[Char] = "orldHello w"
    val r1:Option[Int] = l1.isRot(m1)
    val c1 = Some(4)
    println("Test 1: " + r1 + " (corretto: " + c1 + ")")

    val l2:Seq[Int] = List(0,1,2,3,4,5,6,7,8,9)
    val m2:Seq[Int] = List(3,4,5,6,7,8,9,0,1,2)
    val r2:Option[Int] = l2.isRot(m2)
    val c2 = Some(7)
    println("Test 2: " + r2 + " (corretto: " + c2 + ")")

    val l3:Seq[String] = List("one", "two")
    val m3:Seq[String] = List("Two", "one")
    val r3:Option[Int] = l3.isRot(m3)
    val c3 = None
    println("Test 3: " + r3 + " (corretto: " + c3 + ")")

    val l4:Seq[Boolean] = List(true, false, false)
    val m4:Seq[Boolean] = List(true, false, false)
    val r4:Option[Int] = l4.isRot(m4)
    val c4 = Some(0)
    println("Test 4: " + r4 + " (corretto: " + c4 + ")")

    val l5:Seq[Boolean] = List(true, false, false)
    val m5:Seq[Boolean] = List(true)
    val r5:Option[Int] = l5.isRot(m5)
    val c5 = None
    println("Test 5: " + r5 + " (corretto: " + c5 + ")")

    val l6:Seq[Short] = List(1,2,1,2)
    val m6:Seq[Short] = List(2,1,2,1)
    val r6:Option[Int] = l6.isRot(m6)
    val c6 = None
    println("Test 6: " + r6 + " (corretto: " + c6 + ")")
}

Esercizio 38 - `PIsRot` (uguaglianza a meno di rotazioni - parallelismo su sequenze)

PIsRot.scala:

import scala.language.implicitConversions

class MySeqPar[T](l:Seq[T]) {
    private def isRotInRange(m:Seq[T], min:Int, max:Int):Option[Int] = {
        val res = for {
            i <- min until max
            (a,b) = m splitAt i
            if (l == b ++ a)
        } yield i
        if (res.isEmpty) None else Some(res.head)
    }

    def isRotPar(m:Seq[T]):Option[Int] = {
        def aux(min:Int, max:Int, t:Int):Option[Int] = {
            if (t < 2) isRotInRange(m, min, max)
            else if (min >= max) None
            else {
                val mid = (min+max)/2
                val (rl, rr) = Par.par { aux(min, mid, t/2) }
                                       { aux(mid, max, t/2) }
                if (rl == None) rr else rl
            }
        }
        aux(0, m.size, PIsRot.NUM_CORES)
    }
}

object PIsRot {
    lazy val NUM_CORES = Runtime.getRuntime().availableProcessors()
    implicit def seq2MySeqPar[T](l:Seq[T]) = new MySeqPar(l)
}

PIsRotMain.scala:

import IsRot._
import PIsRot._

object PIsRotMain extends App {
    val l1:Seq[Char] = "Hello world"
    val m1:Seq[Char] = "orldHello w"
    val r1:Option[Int] = l1.isRotPar(m1)
    val c1 = Some(4)
    println("Test 1: " + r1 + " (corretto: " + c1 + ")")

    val l2:Seq[Int] = List(0,1,2,3,4,5,6,7,8,9)
    val m2:Seq[Int] = List(3,4,5,6,7,8,9,0,1,2)
    val r2:Option[Int] = l2.isRotPar(m2)
    val c2 = Some(7)
    println("Test 2: " + r2 + " (corretto: " + c2 + ")")

    val l3:Seq[String] = List("one", "two")
    val m3:Seq[String] = List("Two", "one")
    val r3:Option[Int] = l3.isRotPar(m3)
    val c3 = None
    println("Test 3: " + r3 + " (corretto: " + c3 + ")")

    val l4:Seq[Boolean] = List(true, false, false)
    val m4:Seq[Boolean] = List(true, false, false)
    val r4:Option[Int] = l4.isRotPar(m4)
    val c4 = Some(0)
    println("Test 4: " + r4 + " (corretto: " + c4 + ")")

    val l5:Seq[Boolean] = List(true, false, false)
    val m5:Seq[Boolean] = List(true)
    val r5:Option[Int] = l5.isRotPar(m5)
    val c5 = None
    println("Test 5: " + r5 + " (corretto: " + c5 + ")")

    val l6:Seq[Short] = List(1,2,1,2)
    val m6:Seq[Short] = List(2,1,2,1)
    val r6:Option[Int] = l6.isRotPar(m6)
    val c6 = Some(1)
    println("Test 6: " + r6 + " (corretto: " + c6 + ")")

    val n = 20000
    val l = (0 to n).toVector
    val (a,b) = l splitAt 2*l.size/3
    val m = b ++ a
    println("Versione sequenziale...")
    val (v, t)   = Prof.profila { l.isRot(m) }
    println("Versione parallela...")
    val (vp, tp) = Prof.profila { l.isRotPar(m) }
    println("Test 7: " + vp + " (corretto: " + v + " - tempo seq: "+t*1E-9+" sec - tempo par: "+tp*1E-9+" sec)")
}

Usare inoltre i moduli Par.scala, Prof.scala e IsPar.scala definiti negli eserciti PCoin e IsPar.

Esercizio 39 - `veq32` (uguaglianza di array di int - vettorizzazione)

veq32.c

#include <immintrin.h>
#include "veq32.h"

// ---------------------------------------------------------------------
// veq32
// ---------------------------------------------------------------------
// versione vettorizzata

int veq32(const int* a, int na, const int* b, int nb) {
    int i;
    if (na != nb) return 0;
    for (i=0; i+3<na; i+=4) {
        __m128i va = _mm_loadu_si128((const __m128i*)(a+i));
        __m128i vb = _mm_loadu_si128((const __m128i*)(b+i));
        __m128i vres = _mm_cmpeq_epi32(va, vb);
        if (!_mm_test_all_ones(vres)) return 0;
    }
    for (; i<na; ++i)
        if (a[i] != b[i]) return 0;
    return 1;
}


// ---------------------------------------------------------------------
// veq32_seq
// ---------------------------------------------------------------------
// versione sequenziale

int veq32_seq(const int* a, int na, const int* b, int nb) {
    int i;
    if (na != nb) return 0;
    for (i=0; i<na; ++i)
        if (a[i] != b[i]) return 0;
    return 1;
}

Esercizio 40 - vpal32 (verifica array palindromo - vettorizzazione)

vpal32.c

#include <immintrin.h>
#include "vpal32.h"


// ---------------------------------------------------------------------
// vpal32
// ---------------------------------------------------------------------
// SSE version

int vpal32(const int* v, int n) {
    int i;
    for (i=0; i+3<n/2; i+=4) {
        __m128i va = _mm_loadu_si128((const __m128i*)(v+i));
        __m128i vb = _mm_loadu_si128((const __m128i*)(v+n-4-i));
        va = _mm_shuffle_epi32(va, 0x1B); // 0x1B è 00 01 10 11 in base 2 e consente di rovesciare l'ordine dei 4 int in va
        va = _mm_cmpeq_epi32(va, vb);
        if (!_mm_test_all_ones(va)) return 0;
    }
    for (; i<n/2; ++i)
        if (v[i] != v[n-1-i]) return 0;
    return 1;
}


// ---------------------------------------------------------------------
// vpal32_seq
// ---------------------------------------------------------------------
// sequential version

int vpal32_seq(const int* v, int n) {
    int i;
    for (i=0; i<n/2; ++i)
        if (v[i] != v[n-1-i]) return 0;
    return 1;
}

Programmazione Funzionale e Parallela

Corso di Laurea in Ingegneria Informatica e Automatica - A.A. 2021-2022