Sorting an array into a 'histogram'

Question

I am a fairly new software Engineering student, so my knowledge is limited. I have been given a task to sort an array, which in this case is a set of lottery numbers to give a graph like output in the console, I could do this using a whole bunch of match statements but feel there must be a better way.

this is the exact brief given:

---

Suppose that the following declaration defines the number of times that each of the national lottery balls (1 ..49) has been drawn over a given period.

  var lottery = Array(23,16,18,19,26,13,22,    /*  1 ..  7 */
                20,14,22,18,21,15,17,    /*  8 .. 14 */
                24,15,18,20,13,14,20,    /* 15 .. 21 */
                18,22,20,16,19,11,20,    /* 22 .. 28 */
                16,28,22,20,15,17,17,    /* 29 .. 35 */
                21,21,19,20,14,22,25,    /* 36 .. 42 */
                19,17,26,18,20,23,12);   /* 43 .. 49 */

write a program to print a histogram showing the information graphically using stars like so:

1 (23) | **********************
2 (16) | ************

and so on..

---

any hints/ advice on how to accomplish this would be appreciated as it has stumped me thus far. I am not asking for an exact solution just some guidance on what methods i could use to accomplish them as it is likely I have not come across them. Thank you and have a good day.

---

Edit - the first way I completed the task.

object lottery {
  def main(args: Array[String]): Unit = {

    var lotteryIndex = 1

    var lottery = Array(23,16,18,19,26,13,22,    /*  1 ..  7 */
                    20,14,22,18,21,15,17,    /*  8 .. 14 */
                    24,15,18,20,13,14,20,    /* 15 .. 21 */
                    18,22,20,16,19,11,20,    /* 22 .. 28 */
                    16,28,22,20,15,17,17,    /* 29 .. 35 */
                    21,21,19,20,14,22,25,    /* 36 .. 42 */
                    19,17,26,18,20,23,12);   /* 43 .. 49 */

    scala.util.Sorting.quickSort(lottery)

    var i = 1

    while(i < lottery.length){
      if(lottery(i) != lottery(i-1)){
        print("\n" + lotteryIndex + " (" + lottery(i) + ")  |  " + "*")
        i += 1
        lotteryIndex += 1
      }else{
        print("*")
        i += 1
      }
    }
  }
}

Answer 1

This is fairly straightforward. Each value in the array is the frequency count of the index, so you need to be able to create a string of asterisks ('*') whose length is the same as the frequency count. This can be achieved any number of ways, but perhaps the simplest is to define a function as follows:

def ast(fc: Int) = "*" * fc

Where fc is the frequency count and the number of asterisks required. So, for example, if fc is 5, the result of this expression will be "*****".

Next we need a function that creates a line of output, given a ball number (bn) and the corresponding frequency count (fc):

def line(bn: Int, fc: Int) = f"$bn%2d ($fc%2d) | ${ast(fc)}%s"

Let's explain what's happening here. The f prefix to the string tells Scala that it contains string formatting information and must be interpolated. (Refer to this explanation for further information.)

Whenever a $ is encountered, whatever follows is treated as an expression that needs to converted to a string in the output. If the expression isn't a simple one such as just a variable or value name (if it's a function call, for example), then the expression must be wrapped inside braces (e.g. ${...}). If a % follows the expression, then it identifies the format of the expression in a manner similar to the C language std::printf function.

So: $bn%2d converts the integer value bn into a two-digit decimal string; $fc%2d converts the integer value fc into a two-digit decimal string; and ${ast(fc)}%s calls the function ast passing fc as an argument, and then inserts the resulting string into the output. (The %s is redundant in this latter case.)

(Note: One of the comments on your original question specifies a format of %2s. While this correctly formats the output to two characters, it doesn't check that the argument type is integer, and is, therefore, not recommended.)

Now we need to iterate through the array to call this latter function for each member of the array...

Firstly, note that we need the index as well as the value (the ball number is the array index + 1, since arrays are 0-based). The first step is to convert lottery from an Array[Int] into an Array[(Int, Int)] via the zipWithIndex method. This takes each index-value pair in the lottery array, and combines them into a tuple (with the value first, then the index), placing the result in another array.

We can then map each tuple value in the result to a line of output as follows:

val lines = lottery.zipWithIndex.map {
  case (fc, idx) => line(idx + 1, fc)
}

The above is a way of breaking open the tuple using a partial function. If you don't mind using tuple access members, this can also be achieved more tersely (but also more obfuscatedly) using:

val lines = lottery.zipWithIndex.map(p => line(p._2 + 1, p._1))

where p is a tuple of array index and frequency count. Choose whichever method you prefer.

Finally, we can iterate on the result to print out each line of the result:

lines.foreach(println)

This latter is a shorthand for:

lines.foreach(l => println(l))

So, putting this all together, we end up with the following:

object Lottery
extends App {

  // Lottery data
  val lottery = Array(23,16,18,19,26,13,22,    /*  1 ..  7 */
                      20,14,22,18,21,15,17,    /*  8 .. 14 */
                      24,15,18,20,13,14,20,    /* 15 .. 21 */
                      18,22,20,16,19,11,20,    /* 22 .. 28 */
                      16,28,22,20,15,17,17,    /* 29 .. 35 */
                      21,21,19,20,14,22,25,    /* 36 .. 42 */
                      19,17,26,18,20,23,12)    /* 43 .. 49 */

  // Get a string of asterisks of the required length.
  def ast(fc: Int) = "*" * fc

  // Get a line of the histogram from a ball number and frequency count.
  def line(bn: Int, fc: Int) = f"$bn%2d ($fc%2d) | ${ast(fc)}%s"

  // Get each line of output for the histogram.
  val lines = lottery.zipWithIndex.map {
    case (fc, idx) => line(idx + 1, fc)
  }

  // Print each line of the histogram
  lines.foreach(println)
}

Note that we haven't sorted the histogram (the code as it stands matches the output specified in your brief). If you need to have balls listed in descending order of frequency count, simply sort the zipped array using the frequency count:

val lines = lottery.zipWithIndex.sortBy(-_._1).map {
  case (fc, idx) => line(idx + 1, fc)
}

sortBy takes a function used as the sort value. Here, we take the frequency count and make it negative to reverse the order of the sort (if you want it sorted in ascending order of frequency count, remove the - sign).

Note that we must sort the array after zipping with the index, otherwise we'll lose the ball number association.

Some further observations:

• In Scala, the use of var is heavily discouraged. Prefer val instead. (It's possible to write code that never uses var at all.)
• objects (other than package objects) should typically have a capital first letter by convention.
• Extending scala.App allows the object's constructor to become the main method of the program, and simplifies matters.

Unsorted output (which matches your brief):

1 (23) | ***********************
2 (16) | ****************
3 (18) | ******************
4 (19) | *******************
5 (26) | **************************
...

Sorted output:

30 (28) | ****************************
 5 (26) | **************************
45 (26) | **************************
42 (25) | *************************
15 (24) | ************************
...

UPDATE

In response to your comment about needing a frequency count of the frequency counts (if I understand you correctly), here's how you would do that:

To get the frequency of each value, there are (again) many ways to do this. In this particular case, I'm going to use a foldLeft operation.

You can think of foldLeft as an accumulation operation: the first argument identifies a zero value—the initial value of the accumulator—while the second is a function which is applied to each member of the container (the Array). This latter function itself takes two arguments: the current accumulator value, and the value of the current element, and it returns a new accumulator value.

In this case, I'm going to use foldLeft to build an associative array (a SortedMap, which keeps its keys sorted in ascending order) that links each frequency count to the number of times that it occurs. (In this SortedMap, the _key_s are the frequency counts, and the value associated with each key is the frequency of that frequency count.)

Here's what that looks like (I've broken it down into a number of steps to make it more comprehensible):

// Required import.
import scala.collection.immutable.SortedMap

// Our initial, empty map, which reports a frequency of zero if a key is not present.
// Note that a `SortedMap` keeps its keys sorted.
val zero = SortedMap.empty[Int, Int].withDefaultValue(0)

// Iterate through the frequency counts (`fc`) in the `lottery` array. `fm` is the current
// status of our map.
val freq = lottery.foldLeft(zero) {(fm, fc) =>

  // Determine the new count for this frequency count.
  val newCount = fm(fc) + 1

  // Create an association from the frequency count to this new count.
  val assoc = fc -> newCount

  // Add this association to the map, resulting in a new map. Any existing association
  // will be replaced.
  fm + assoc
}

If you've followed that, here's a terser version:

val freq = lottery.foldLeft(SortedMap.empty[Int, Int].withDefaultValue(0)) {(fm, fc) =>
  fm + (fc -> (fm(fc) + 1))
}

Now all that remains is to create the histogram lines and print them:

val lines = freq.map {
  case (k, v) => line(k, v)
}

lines.foreach(println)

(Note: The definition of the arguments for the line method need tweaking in light of the changes, but the behavior is identical.)

Output:

11 ( 1) | *
12 ( 1) | *
13 ( 2) | **
14 ( 3) | ***
15 ( 3) | ***
16 ( 3) | ***
17 ( 4) | ****
18 ( 5) | *****
19 ( 4) | ****
20 ( 8) | ********
21 ( 3) | ***
22 ( 5) | *****
23 ( 2) | **
24 ( 1) | *
25 ( 1) | *
26 ( 2) | **
28 ( 1) | *