Esercizi di Linguaggi di Programmazione

Define the following functions in Scala:

1. is_palindrome: string → bool that checks if the string given as input is palindrome, a string is palindrome when the represented sentence can be read the same way in either directions in spite of spaces, punctual and letter cases, e.g., detartrated, "Do geese see God?", "Rise to vote, sir.", ...;
2. is_an_anagram : string → string list → boolean that given a dictionary of strings, checks if the input string is an anagram of one or more of the strings in the dictionary;
3. factors: int → int list that given a number calculates all its prime factors;
4. is_proper: int → boolean that given a number calculates if it is a perfect number or not, where a perfect number is a positive integer equal to the sum of its proper positive divisors (excluding itself), e.g., 6 is a perfect number since 1, 2 and 3 are the proper divisors of 6 and 6 is equal to 1+2+3;

Write the following functions by using list comprehensions:

• squared_numbers that removes all non-numbers from a polymorphic list and returns the resulting list of squared numbers, e.g., squared_numbers(1 :: "hello" :: 100 :: 3.14 :: ('a'::10::Nil) :: 'c' :: (5,7,'a') :: Nil) should return List(1, 10000, 9.8596, List(100), (25,49)). Note that it recursively applies to substructures.
• intersect that given two generic lists, returns a new list that is the intersection of the two lists (e.g., intersect(List(1,2,3,4,5), List(4,5,6,7,8)) should return List(4,5)).
• symmetric_difference that given two lists, returns a new list that is the symmetric difference of the two lists. For example symmetric_difference(List(1,2,3,4,5), List(4,5,6,7,8)) should return List(1,2,3,6,7,8).

To reverse the order of the characters in a string is quite trivial but when the length of the string grows trivial could means extremely slow. To decompose the input string in shorter strings and to join back the inverted strings in order to keep the algorithm working always on a short input is a good idea to fast the process.

Write a master-slave distributed system where:

• a server process (MasterProcess) provides a service called long_reverse_string() that given a very large string (≥ 1000 characters) returns the reversed string;
• the service long_reversed_string() decomposes the input w into 10 strings w⁰, ..., w⁹ with the following lengths (# represents the operator length of a string, and n=#w%10): #w⁰=...=#wⁿ=#w/10+1 e #wⁿ⁺¹=...=#w⁹=#w/10 and forwards to 10 distinct actors (SlaveProcess) to reverse the 10 substrings w⁰, ..., w⁹ (service reverse_string()) and joins the 10 results.
• the client process (ClientProcess) just ask for the service on a given string.

When done with the exercise try to relax the constraint on the number of substrings from ten to a generic M passed as an input to the long_reversed_string service.

Note, Scala supports the actor model in a way really similar to Erlang look at the documentation to see the difference and learn how to implement the exercise.

A monoid is an algebraic structure consisting of a set together with a single associative binary operation and an identity element. E.g., the set of booleans with the or operator is a monoid whose identity is false.

A group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity and invertibility. E.g., the set Z (the integers with sign) with the + operator is a group but with the * is not since inverting the operation break the closure property.

A ring is an algebraic structure consisting of a set together with two binary operations (usually called addition and multiplication), where each operation combines two elements to form a third element. To qualify as a ring, the set together with its two operations must satisfy certain conditions, namely, the set must be an abelian (i.e., commutative) group under addition and a monoid under multiplication such that multiplication distributes over addition.

Write the Monoid, Group and Ring classess implementing the monoids, groups and rings algebraic structures respectively. Each class must be parametric on the algebraic sort, in the sense that the operations and the sets are not a priori defined and they should implement operations to check the properties characterizing the algebraic structure.

Test your implementation with the following examples (S is the set, add=additive operation, mul=multiplicative operation, i=identity):

Monoids

• S = {True, False} add = or i = False
• S = Zn={0,1,...,n-1} add = + where a+b=(a+b)%n i = 0

Groups

• S = {True, False}, add = or, i = False
• S = Z, add = +, i = 0
• S = Z4 = {0, 1, 2, 3}, add = * where a*b=(a*b)%4, i = 1
• S = {a}*, add: {a}*×{a}* --> {a}* where x1·x2 is x1 if #x1 > #x2, x2 otherwise, i = the empty string

Rings

• S = {0} add = + where 0+0=0 mul = * where 0*0=0 i = 0
• S = Z add = + mul = * i = 0
• S = Z4 = {0,1,2,3} add = + where a+b=(a+b)%4 mul = * where a*b=(a*b)%4 i = 0

Note property checks on infinite sets should be on a finite subset.

A KeWord In Context (KWIC) index is a simple index for a list of lines or titles. This assignment involves creating a KWIC index for an input list of titles stored in a file. Here's a small example. For the input file:

[02:34]cazzola@hymir:~/lp/scala>cat kwic.txt
My Big Fat Greek Wedding
One Flew Over the Cuckoo's Nest
Star Wars: Revenge of the Sith
Everything You Always Wanted To Know About Sex But Were Too Afraid To Ask
Borat: Cultural Learnings of America for Make Benefit Glorious Nation of Kazakhstan

your program should produce the output:

[02:36]cazzola@hymir:~/lp/scala>scala KWIC kwic.txt
   4 ed To Know About Sex But Were Too Afraid To Ask                           
   4                    Everything You Always Wanted To Know About Sex But Were
   5      Borat: Cultural Learnings of America for Make Benefit Glorious Nation
   4  About Sex But Were Too Afraid To Ask                                     
   5 ral Learnings of America for Make Benefit Glorious Nation of Kazakhstan   
   1                                My Big Fat Greek Wedding                   
   5                                   Borat: Cultural Learnings of America for
   2                 One Flew Over the Cuckoo's Nest                           
   5                            Borat: Cultural Learnings of America for Make B
   4                                   Everything You Always Wanted To Know Abo
   1                            My Big Fat Greek Wedding                       
   2                               One Flew Over the Cuckoo's Nest             
   5 nings of America for Make Benefit Glorious Nation of Kazakhstan           
   1                        My Big Fat Greek Wedding                           
   5 r Make Benefit Glorious Nation of Kazakhstan                              
   4   Everything You Always Wanted To Know About Sex But Were Too Afraid To As
   5                   Borat: Cultural Learnings of America for Make Benefit Gl
   5 Cultural Learnings of America for Make Benefit Glorious Nation of Kazakhst
   1                                   My Big Fat Greek Wedding                
   5 America for Make Benefit Glorious Nation of Kazakhstan                    
   2        One Flew Over the Cuckoo's Nest                                    
   2                                   One Flew Over the Cuckoo's Nest         
   3                        Star Wars: Revenge of the Sith                     
   4 g You Always Wanted To Know About Sex But Were Too Afraid To Ask          
   3         Star Wars: Revenge of the Sith                                    
   3                                   Star Wars: Revenge of the Sith          
   4 Wanted To Know About Sex But Were Too Afraid To Ask                       
   4             Everything You Always Wanted To Know About Sex But Were Too Af
   3                              Star Wars: Revenge of the Sith               
   1                  My Big Fat Greek Wedding                                 
   4 ways Wanted To Know About Sex But Were Too Afraid To Ask                  
   4                        Everything You Always Wanted To Know About Sex But

As you can see, each title is listed for each word (omitting some minor words). The titles are arranged so that the word being indexed is shown in a column on the page. The position the lines have in the input file is shown on the left in the result.

Your solution should follow the following rules:

• The input is just a series of titles, one per line. Any leading or trailing spaces should be removed. Internal spaces should be retained (trimmed to one).
• A word is a maximal sequence of non-blank characters.
• The output line is at most 79 characters wide.
  • The number is 4 characters wide, right-justified.
  • There is a space after the number.
  • The key word starts at position 40 (numbering from 1).
  • If the part of the title left of the keyword is longer than 33, trim it (on the left) to 33.
  • If the part of the keyword and the part to the right is longer than 40, trim it to 40.
• Each title appears in the output once for each word that isn't minor. Any article, conjunction and preposition is minor, e.g., and, to, and the words are minor words.
• If a title has a repeated word, it should be listed for each repetition.
• Sorting should be case-insensitive.

Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:

Every even integer greater than 2 is a Goldbach number, i.e., a number that can be expressed as the sum of two primes.

Expressing a given even number as a sum of two primes is called a Goldbach partition of the number. For example,

04 = 2 +  2           6 = 3 +  3           8 = 3 +  5

10 = 7 +  3          12 = 5 +  7          14 = 3 + 11

16 = 5 + 11          18 = 7 + 11          20 = 7 + 13

Write the following functions:

• goldbach(n) that returns a Goldbach partition for n
• goldbach_list(n,m) that returns a list of Goldbach partitions for the even numbers in the range (n,m).

You have to write a class Matrix to represent and manipulate integer matrices. The class should be parametric on its dimensions and will provide the operations of matrix equivalence, matrix copy, matrix addition, scalar-matrix multiplication, matrix-matrix multiplication, matrix transposition, and matrix norm -- the "size" of a matrix. Override the appropriate operators and raise the appropriate exceptions.

The following gives the semantics of such operations.

Let aij denote the i,j-th element of matrix A, located at row i, column j. Using this notation, the matrix operations listed above may be defined precisely as follows:

• matrix equivalence A ≃ B where A in Zm×n, B in Zp×q when m = p and n = q and bij = aij for i = 1,...,m j = 1,...,n;
• matrix copy B = A where A, B in Zm×n (bij = aij for i = 1,...,m j = 1,...,n);
• matrix addition C = A + B where A, B, C in Zm×n (cij = aij + bij for i = 1,...,m j = 1,...,n);
• scalar-matrix multiplication B = aA where A, B in Zm×n, a in Z (bij = a·aij for i = 1,...,m j = 1,...,n);
• matrix-matrix multiplication C = A·B where A in Zm×p, B in Zp×n, C in Zm×n (cij = Σk=1, ..., p aik·bkj for i = 1,...,m j = 1,...,n);
• matrix transposition B = AT where A in Zm×n, B in Zn×m (bji = aij for i = 1,...,m j = 1,...,n);
• matrix norm (matrix 1-norm) a = ‖A‖ where a in Z, A in Zm×n (a = maxj Σi | aij | for i = 1,...,m j = 1,...,n).

Note that in each case we state the proper matrix dimensions for the operation to be valid. For example, when multiplying two matrices A and B, the number of columns of A must match the number of rows of B.

As you probably know, vi is a modal text editor: it operates in either insert mode (where typed text becomes part of the document) or normal mode (where keystrokes are interpreted as commands that control the edit session). Ex is a line editor that serves as the foundation for the screen editor vi. Ex commands work on the current line or on a range of lines in a file.

Syntax of Ex commands

:[address] command [options]

In our exercise we are going to implement a simplified version of the line editor Ex used by VI.

In particular you have to implement a class editor representing a line of text with the following operations defined on it:

• x which deletes the character under the cursor (does nothing if no characters are present) and move the cursor on the character on the right if present otherwise back of one;
• dw which deletes from the character under the cursor (included) to the next space (excluded) or to the end of the line and moves the cursor on the character on the right if any or backwards otherwise;
• i which adds a character c after the character under the cursor and moves the cursor under c
• iw which adds a word w followed by a blank space after the character under the cursor and moves the cursor under the blank space;
• l which moves the cursor n (1 as default, i.e., when nothing is specified) characters on the right from the current position (it does nothing when at the end of the text or it moves less if it is close to the end);
• h which moves the cursor n (1 as default, i.e., when nothing is specified) character on the left from the current position (it does nothing when at the beginning of the text or it moves less if it is close to the beginning).

Clearly all the above operations are methods invokable on instances of the editor class. Each instance should have clear where the cursor is after each computation.

As you can imagine to debug the editor class is not easy. In particular it is difficult to find out which operation has changed the text and where the cursor is in any moment. To this respect write a trait debug (to be applied to the editor class) that, when you print the line of text prints also who has performed the operation and where the cursor is.

Moreover, any (usable) editor should have a mechanism to undo and redo the actions carried out on the text and our line editor cannot do an exception to this rule.

On the other side undo/redo operations are normally orthogonal to the text editing actions and they are separately implemented. We are going to adopt the same approach to their implementation by defining a UndoRedo trait.

The UndoRedo trait will add to the editor class two operations:

• u which undoes the effects of the last executed command (ctrlr included) at every call (this means that two consecutive calls will undo the effects of the last two executed commands);
• ctrlr which redoes the effects of the last undone command at every call (consecutive calls have a behavior similar to the undo case).

Note that every pair of calls u → ctrlr will leave the text unchanged. A call to ctrlr method after any other editing command (i.e., any method different from u) has no effect.

The undo/redo model to implement is linear, i.e., if you edit the text after an undo operation you lose the possibility to redo all the changes to it and a successive undo do not restore this possibility.