Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.

This is a Jupyter notebook. See How to use these notes.

# Count¶

## The problem¶

Suppose we have a sequence of things and we want to count how many times a given element occurs.

We'll represent sequences as python tuples.

### Some definitions¶

To make the code less dependent on the details of Python, we'll make and use the following definitions.

In [40]:
def isEmpty( s ):
"""Pre: s is a sequence represented by a tuple
Post: result is true if s is empty and false otherwise
"""
assert isinstance(s, tuple)
return s == ()

def empty():
"""Pre: true
Post: result is an empty sequence"""
return ()

def cons( x, s ) :
"""Pre: s is is a sequence represented by a tuple
Post: result is a sequence represented by a tuple with x as its first item and s as the rest.
"""
assert isinstance(s, tuple)
return (x,) + s

def first( s ) :
"""Pre: s is is a nonempty sequence represented by a tuple
Post: result the first item of the sequence
"""
assert isinstance(s, tuple) and s != ()
return s[0]

def rest( s ) :
"""Pre: s is is a nonempty sequence represented by a tuple
Post: result the first item of the sequence
"""
assert isinstance(s, tuple) and s != ()
fst, *rst = s
return tuple(rst)

def decons( s ) :
"""Pre: s is is a nonempty sequence represented by a tuple
Post: result is a pair consisting of the first items of s and a tuple of the rest of the items
"""
assert isinstance(s, tuple) and s != ()
fst, *rst = s
return fst, tuple(rst)

def split( s ) : # Split a sequence into two roughly equal parts.
"""Pre: s is is a sequence represented by a tuple
Post: result is a pair consisting of the first two tuples, which if catentated form the origninal tuple.
The two parts will be the same size or differ in size by one.
Consequence: If s is of size at least 2, the two tuples will each be smaller than s.
"""
assert isinstance(s, tuple)
l = len(s)
return s[0:l//2], s[l//2:]

def cat( s, t ) : # Concatenate two sequences
"""Pre: s and t are sequences represented by a tuple
Post: result is a tuple formed by concatenating s with t.
"""
assert isinstance(s, tuple) and isinstance(t, tuple)
return s+t



### A contract¶

We write a contract for a count function which count the number of times an item equal to x occurs in a sequence x

def best( s, x ):
"""
Pre: s is a sequence
Post: result == number of items in s equal to x
"""


## Problem analysis¶

### Alice's observation¶

[Put your problem analysis here.]

### We need a base case¶

[What is the base case?]

## Design¶

Based on the problem analysis, we can write a design in pseudocode. In this case the pseudocode will look a lot like Python, so you can take this step if you want or skip it if you don't.

[Put your pseudocode here]

## Analyze design¶

Before coding, you should check that your design will work. Here is a checklist

• Is every case allowed by the precondition covered?
• Does the code do the right thing (i.e. return a result allowed by the postcondition) in each case?
• Is there a variant function?

## Code¶

Complete the following function

In [18]:
    def count( s, x ):
"""
Pre: s is a sequence
Post: result == number of items in s equal to x
"""


## Analyze code¶

If you wrote pseudocode, check that your design is consistant with the pseudocode. If you didn't write pseudocode, use the checklist above to check your code.

## Test¶

Below are some tests. After you define the function, you can run these tests and compare the answers with expected answers above.

In [19]:
count( (), 0 ) # Expect 0

In [20]:
count( (0,), 0) # Expect 1

In [21]:
count( (1,), 0) # Expect 0

In [22]:
count( (1,2,0,1,2,3,0,1), 1) # Expect 3

In [23]:
count( (1,2,0,1,2,3,0,1), 0) # Expect 2


# My Solution¶

## Design¶

Here is my pseudocode, it's included here mostly as an illustration of the notation that I use for sequences when writing pseudocode

function $count\langle T\rangle( s : Seq\langle T\rangle, T x)$

pre $s$ is a sequence
post result is number of items in $s$ equal to $x$

if $s = [\,]$ then 0
elsif $s(0)=x$ then $1 + count( s[1,..] )$
else $count( s[1,..] )$ end if

## Analysis¶

• A sequence is either empty or not, so all cases are covered
• The code looks right for both cases.
• The variant function is the length of the sequence $s$!

## Code¶

And here is the Python 3 code

In [24]:
  def countMine( s, x ):
"""
Pre: s is a sequence
Post: result == number of items in s equal to x
"""
if isEmpty(s) : return 0
elif first(s) == x : return 1 + countMine( rest(s), x)
else:return countMine( rest(s), x)


## Test¶

In [25]:
countMine( (), 0 ) # Expect 0

Out[25]:
0
In [26]:
countMine( (0,), 0) # Expect 1

Out[26]:
1
In [27]:
countMine( (1,), 0) # Expect 0

Out[27]:
0
In [28]:
countMine( (1,2,0,1,2,3,0,1), 1) # Expect 3

Out[28]:
3
In [29]:
countMine( (1,2,0,1,2,3,0,1), 0) # Expect 2

Out[29]:
2