CS 151: Intro to Programming in Python

Problem Set 5: Histogram

Due: Monday, 28 October, 11:59 PM

Github Classroom Link: https://classroom.github.com/a/rGt0WBas

This is a problem set of 2 problems, the first of which has 3 parts.

Files:

1. Histogram

  • Update (only) this file:
    • Prob1.py
  • You will also need:
    • pgl.py

2. Magic Square

  • Update (only) this file:
    • Prob2.py

Resources on PGL (Portable Graphics Library):

Problem 1: Histogram

Create histogram, or bar chart, based on how many times some value occurs in a list.

Consider the first 16 digits of π: 

PI_DIGITS = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 5, 8, 9, 7, 9]

This would create histogram array as follows: 

HISTOGRAM = [0, 2, 1, 2, 1, 4, 1, 1, 1, 3]

We visualize the array as follows:

That is, there are zero 0s in PI_DIGITS, there are two 1s in PI_DIGITS,... there are three 9s in PI_DIGITS.

Problem 1a: create_histogram_array

Write a function over a list of integers that returns a new, distinct list of integers that corresponds to the histogram values.

create_histogram_array(x)[i] should be equal to the number of times i appears in x. 

create_histogram_array(data:list[int])->list[int]

It can be used as follows: 

>>> PI_DIGITS
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 5, 8, 9, 7, 9]
>>> create_histogram_array(PI_DIGITS)
[0, 2, 1, 2, 1, 4, 1, 1, 1, 3]

Problems:

Problem 1b: print_histogram

Write a function over a list of integers that prints a labelled history of asterisks representing the histogram array. It will have type: 

print_histogram(hist:list[int])->None

For each integer in hist print:

  1. The index, beginning with zero and increasing.
  2. A colon followed by a space ": ".
  3. A number of 'star' or 'asterisk' characters equal to the value hist[index].

It is most likely easier to see an example: 

>>> PI_DIGITS
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 5, 8, 9, 7, 9]
>>> create_histogram_array(PI_DIGITS)
[0, 2, 1, 2, 1, 4, 1, 1, 1, 3]
>>> h = create_histogram_array(PI_DIGITS) 
>>> print_histogram(h)
0: 
1: **
2: *
3: **
4: *
5: ****
6: *
7: *
8: *
9: ***

For example, '5: ****' represents that

  • The digit 5 appears 4 times in PI_DIGITS, and that
  • The value of h[5] is 4

Problem 1c: graph_histogram

Write a function that graphs the histogram in a PGL window of size width by height, probably in red on white: 

graph_histogram(hist:list[int], width:int, height:int)

For example, consider graph_histogram(create_histogram_array(PI_DIGITS),400,400). I have added an outline to make the image more clear, but you do not need to add an outline.

How I solved it

For 1a, I created a list of length max(data) + 1 of all zeros. I looped over data, and for each value, added one to the list index equal to the current value.

For 1b, I wrote a single list comprehension over the length of the histogram. I printed (the string representation of the index) plus (the formatting colon and space) plus (the histogram value times the asterisk character).

For 3b, I used my_rect. I calculated how wide each column would be, and how many pixels corresponded a histogram value of one (one of the asterisks from above). Then I looped over the histogram, adding rectangles displaced from the upperleft according to their index (from left) and histogram value less maximum value (from the top).

Problem 2: is_magic_square

The function is_magic_square will

  • Accept a list of lists of integers.
  • Return False the outer list and differs in length from any of the inner lists.
    • That is, in a list of 3 lists of integers, all of the lists of integers must be of length 3.
  • Return True if:
    • The sum of the rows, columns and diagonals are all equal.
  • Return False otherwise. 
is_magic_square(array:list[list[int]]) -> bool

The following depicts a magic square of size 3x3.

There is a famous 4x4 magic square in Melencolia I by Albrecht Dürer. Albrecht Dürer - Melencolia I (detail)