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.

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?]

Your solution¶

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

    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.

count( (), 0 ) # Expect 0

count( (0,), 0) # Expect 1

count( (1,), 0) # Expect 0

count( (1,2,0,1,2,3,0,1), 1) # Expect 3

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

  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¶

countMine( (), 0 ) # Expect 0

0

countMine( (0,), 0) # Expect 1

1

countMine( (1,), 0) # Expect 0

0

countMine( (1,2,0,1,2,3,0,1), 1) # Expect 3

3

countMine( (1,2,0,1,2,3,0,1), 0) # Expect 2

2