20180402:TP:Go:PlayingAround

Introduction

This week practical session is here to push a little bit our Go exploration. We'll play with slices and map.

As explain last week, the expected architecture should look like:

• YourGIT/
  • go
    • src
      • tutorial20180402/
        • memo_fibo/ (first exercise)
        • merge_sort/ (second exercise)
        • test_merge_sort/ (second exercise)
        • eratosthenes/ (third exercise)
        • word_count (fourth exercise)

Memoization of Fibonacci

• Path: tutorial20180402/memo_fibo/

Our goal here is to play a little bit with one possible approach of the Fibonacci sequence: memoization.

Memoization consist of remembering values to avoid recomputing it, it's very useful in the presence of a recursive function that reuse very often already computed results. For a simple Fibonacci function, remembering the last two ranks is enough, but we want something more advanced: in a series of call to Fibonacci, we want to avoid recomputing what has been computed before.

Concretely, all you need is to keep an array containing the computed ranks. Something like this:

Fibo(n, memo):
  if n is not in memo:
    a = Fibo(n - 1, memo)
    b = Fibo(n - 2, memo)
    memo[n] = a + b
  return memo[n]

Complete the following code:

package main
 
import "fmt"
 
func MemoFibo(n int, memo []int) int {
        // FIX ME
}
 
func Fibo(n int) (r int) {
	p := 1
	r = 1
	for i := 1; i < n; i++ {
		r += p
		p = r - p
	}
	return
}
 
const (
	size = 50
)
 
func main() {
	for i := 0; i < size; i++ {
		fmt.Printf("fibo(%d) = %d\n", i, Fibo(i))
	}
	memo := make([]int, size)
	memo[0], memo[1] = 1, 1
	for i := 2; i < len(memo); i++ {
		memo[i] = -1
	}
	for i := 0; i < size; i++ {
		fmt.Printf("fibo(%d) = %d\n", i, MemoFibo(i, memo))
	}
}

Merge Sort

• Path: tutorial20180402/merge_sort and tutorial20180402/test_merge_sort

The goal here is to implement a merge-sort in a separate package and then test it in separate main package.

In the first path (merge_sort) create your package merge_sort with the completed code from:

package merge_sort
 
func Merge(a, b []int) (l []int) {
        // FIX ME
}
 
func MergeSort(l []int) []int {
        // FIX ME
}

Remember, the merge sort algorithm is pretty simple:

Merge(a, b): merges into a single sorted array the two sorted array a and b and returns it

MergeSort(l):
  if len(l) < 2: return l
  a = MergeSort of the first half of l
  b = MergeSort of the second half of l
  return Merge(a, b)

Now we can test our code, in the directory test_merge_sort create you main package (name your file as you which):

package main
 
import (
	"fmt"
	"math/rand"
	"tutorial20180402/merge_sort"
)
 
func sorted_fill(l []int) {
	for i, _ := range l {
		l[i] = i
	}
}
 
func rev_fill(l []int) {
	j := len(l) - 1
	for i, _ := range l {
		l[i] = j - i
	}
}
 
func main() {
	l := make([]int, 256)
	sorted_fill(l)
	fmt.Println("Array:")
	fmt.Println("  ", l)
	l = merge_sort.MergeSort(l)
	fmt.Println("Array:")
	fmt.Println("  ", l)
 
	rev_fill(l)
	fmt.Println("Array:")
	fmt.Println("  ", l)
	l = merge_sort.MergeSort(l)
	fmt.Println("Array:")
	fmt.Println("  ", l)
 
	l = rand.Perm(len(l))
	fmt.Println("Array:")
	fmt.Println("  ", l)
	l = merge_sort.MergeSort(l)
	fmt.Println("Array:")
	fmt.Println("  ", l)
}

• Complete your merge_sort package and test it using the provided main
• (bonus) Extend the main in order to take the array length as parameter

Sieve of Eratosthenes

• Path: tutorial20180402/eratosthenes/

This is just another basic algorithm training exercise !

• Complete the following code:

package main
 
import "fmt"
 
/* Eratosthenes(n) returns the list of prime numbers inferior or equal to n */
func Eratosthenes(n int) (prime []int) {
        // FIX ME
}
 
func main() {
	prime := Eratosthenes(100000)
	fmt.Println(prime)
}

Going Further

The sieve of Eratosthenes is the best method to compute the list of the first prime numbers, but with large value, building the list of n first integer is too large for the computer's memory. A possible solution is to use a map (a hash table) containing only the interesting values: non-prime numbers superior to the current in the computation.

Here is a possible algorithm:

CleverEratosthenes(n):
  primes = [ 2 ] // initial lists of prime numbers
  non_primes = empty map
  i = 3
  while i <= n:
    while i <= n and i is in non_primes:
      delete non_primes[i] // don't need to keep already seen values
      i += 2 // skip even numbers
    if i > n: return primes
    j = i
    while i * j <= n:
      add (i*j) to non_primes
      j++
    i++
  return primes

With this you should be able to go a little bit further than with previous version. As you can see, non_prines is more a set than a map, but go doesn't provide set. The go documentation describes a possible set implementation using maps (see [1]).

• Replace you sieve implementation and test it with a bigger bounds.

Counting Words

• Path: tutorial20180402/word_count

Counting with a hash map

• Write the following function:

/*
   WordCount(words) build a map of each distinct words appearing in the string
   slice words and attach the number of occurrences of each words.
*/
func WordCount(words []string) (wc map[string]int)

Open a file and split it

In order to test our code, we need a text already split into words. In order to do that, we'll load the content of a file and split it on spaces. You'all need the following function (look for them in the doc … ):

• os.Open(fname)
• ioutils.ReadAll(reader)
• strings.Fields(str)

Read carefully the docs and use the Go classic comma ok idiom.

• Write the following function:

/*
   LoadFile(fname) opens the file fname, reads the content and split it into
   words.
*/
func LoadFile(fname string) (words []string)

Going further (bonus)

The function strings.Fields(str) split our string on space characters but it doesn't handle punctuation signs. Try to enhance your loading code using punctuation.

Testing

• Complete the following code:

package main
 
import (
	"fmt"
	"io/ioutil"
	"os"
	"strings"
)
 
func WordCount(words []string) (wc map[string]int) {
	/* FIX ME */
}
 
func LoadFile(fname string) (words []string) {
	/* FIX ME */
}
 
func main() {
	if len(os.Args) < 2 {
		panic("Missing argument")
	}
	wc := WordCount(LoadFile(os.Args[1]))
	fmt.Println(wc)
}