Coding scientific functions

Coding scientific functions#

These exercises are designed to refresh and in some cases challenge your python knowlege and problem solving skills. They are a mix of classic scientific coding problems and coding interview type questions found on sites such as HackerRank.

Note that the solutions to these exercises are in standard Python. If you have knowledge of scientific python libraries such as numpy or scipy and are confident in using them to complete the exercises then that is fine. However, don’t feel you need to overcomplicate your code. There are seperate exercises for numpy.

Even if you are confident in your basic python skills try to work through all of the questions.

In general the complexity of questions increases as you progress through the questions.

Some extra challenges relevant to algorithms

Aim to produce efficient solutions to problems i.e. those that require a minimal amount of memory, computations and run time. I have provided example solutions, but maybe you can do better!
Time your solutions to identify if you have improved run time.
Keep your solutions readable. Write good quality human readable code and give your functions PEP8 docstrings.
Test your problems with more than one data input - this can help identify weaknesses and errors in your code.
Add some defensive error checking and/or exception handling for function inputs.

Imports#

Exercise 1#

(source: hackerrank.com)

Given five positive integers, find the minimum and maximum values that can be calculated by summing exactly four of the five integers. Print the respective minimum and maximum values.

Example:

arr = [9, 3, 5, 7, 1]

output:

16
24

# your code here ...
arr = [9, 3, 5, 7, 1]

Exercise 2#

The inverse of a 2×2 matrix \(A = \begin{pmatrix} a & b\\ c & d \end{pmatrix}\) is given by

\[\begin{split}A^{-1} = \dfrac{1}{ad - bc} \begin{pmatrix} d & -b\\ -c & a \end{pmatrix}\end{split}\]

Task:

Code a function that, given a 2D array A = [[a,b],[c,d]], prints out the 2x2 inverse matrix.
Do not use the built in inversion functions.

Test data:

matrix = [[5.0, 2.0], [-7.0, -3.0]]
expected = [[3.0, 2.0], [-7.0, -5.0]] 

Hints:

How do I represent a matrix in standard python?
- For example the matrix \(A = \begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}\) would be list of lists a = [[1, 2], [3, 4]]

# your code here ...

Exercise 3#

A classic Markovian model for representing the steady state performance of queuing and service system is the M/M/1.

In the Markovian model “customers” arrive to the model following a Poisson process with rate parameter \(\lambda\) (e.g. an average of 5 arrivals per hour). The M/M/1 is a first come first served system with a single server. Service time is exponentially distributed with mean \(1/\mu\) i.e. customers are served at rate \(\mu\).

The equation for calculating the average waiting time to be served (\(W_q\)) in an M/M/1 queue is:

\[W_q = \dfrac{\lambda}{\mu\left(\mu-\lambda\right)}\]

While the probability that there are \(n\) customers in the system (\(P_n\)) is given by:

\[P_n = \left(1 - \dfrac{\lambda}{\mu}\right)\left(\dfrac{\lambda}{\mu}\right)^n\]

Example:

Given:

\[\lambda = 2 \textnormal{ per hour}\]

\[\mu = 3 \textnormal{ per hour}\]

Calculate \(W_q\) and \(P_0, P_1\)

\[W_q = \dfrac{2}{3\left(3 - 2\right)} = \dfrac{2}{3} \textnormal{ per hour}\]

\[P_0 = \left(1 - \dfrac{\lambda}{\mu}\right) = 1 - \dfrac{2}{3} = \dfrac{1}{3}\]

\[P_1 = \left(\dfrac{1}{3}\right)\left(\dfrac{2}{3}\right) = \dfrac{2}{9}\]

Task:

Code functions in python to calculate \(W_q\) and \(P_n\) for the M/M/1 queue model.

Test data:

arrival_rate = 2.0
service_rate = 3.0
expected_wq = 2/3
expected_p0 = 1/3
expected_p1 = 2/9
expected_p2 = 4/27

Hints:

Note that the word “lambda” is a special word in Python and should not be used as a variable name. When naming a variable options are to use _lambda or arrival_rate

# your code here...

Exercise 4#

(source: hackerrank.com)

A left rotation operation on an array shifts each of the array’s elements unit to the left.

Example 1

# original list
to_roll = [1, 2, 3, 4, 5]

#number of rotations/rolls left
n = 2

#call the function that rotates the array.
roll_left(to_roll, n)

output:

[3, 4, 5, 1, 2]

Note that the lowest index item moves to the highest index in a rotation. This is called a circular array.

Example 2:

# original list
to_roll = [1, 2, 3, 4, 5]

#number of rotations/rolls left
n = 8

# call the function that rotates the array.
roll_left(to_roll, n)

output:

[4, 5, 1, 2, 3]

Task:

Given an array of integers and a number, perform left rotations on the array.
Return the updated array and print to screen.

Test data

# test 1
to_roll = [1, 2, 3, 4, 5]
n = 7 
expected = [3, 4, 5, 1, 2]

# test 2
to_roll = [41, 73, 89, 7, 10, 1, 59, 58, 84, 77, 77, 97, 58, 1, 86, 58, 26, 
           10, 86, 51]
n = 10
expected = [77, 97, 58, 1, 86, 58, 26, 10, 86, 51, 41, 73, 89, 7, 10, 1, 59, 
            58, 84, 77]

# your code here ...

Exercise 5#

The Fibonacci numbers, denoted \(F_n\), form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is

\(F_{0}=0, F_{1}=1\)

and

\(F_{n}=F_{n-1}+F_{n-2}\) for \(n > 1\).

The beginning of the sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Task:

Code a function called fib(n).
The parameter n represents the Fibaonacci number that will be generated.
For example, the value when fib(50) returns 12_586_269_025

# your code here

Exercise 6#

(source hackerrank.com)

Given a 6x6 matrix \(A\)

An hourglass is a subset of values with indices falling in this pattern in \(A\)’s graphical representation:

a b c
  d 
e f g

In total, there are 16 hourglasses in \(A\). An hourglass sum is the sum of all the values it contains.

For example the first and second hour glasses in \(A\) are therefore.

1 1    1 1 0
      0
1 1    1 1 0

subset 1 total = 1+1+1+1+1+1+1 = 7

subset 2 total = 1+1+0+0+1+1+0 = 4

Task:

Code a function that accepts an matrix as a parameter (you can assume it is always 6x6)
The function must calculate all hourglass sums and return the maximum (int).

Test data

# expected answer = 19
matrix = [[1, 1, 1, 0, 0, 0],
          [0, 1, 0, 0, 0, 0],
          [1, 1, 1, 0, 0, 0],
          [0, 0, 2, 4, 4, 0],
          [0, 0, 0, 2, 0, 0],
          [0, 0, 1, 2, 4, 0]]


# expected answer = 13
matrix2 = [[1, 1, 1, 0, 0, 0],
           [0, 1, 0, 0, 0, 0],
           [1, 1, 1, 0, 0, 0],
           [0, 9, 2, -4, -4, 0],
           [0, 0, 0, -2, 0, 0],
           [0, 0, -1, -2, -4, 0]]

# your code here ...

Exercise 7#

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible.

Examples

Given the vector [3, 1, 8, 2, 5] the longest increasing subsequence is [1, 2, 5] and has length 3.
Given the vector [5, 2, 8, 6, 3, 6, 9, 5] the longest increasing subsequence is [2, 3, 6, 9] and has length 4

Task

Code a function that accepts a sequence as parameter. The function should return the length of the longest increasing subsequence.

Hints:

You are being asked to return the length not the actual subsequence.

# your code here ...

Exercise 8:#

(source: hackerrank.com)

A string is said to be a special string if either of two conditions is met:

All of the characters are the same, e.g. aaa.
All characters except the middle one are the same, e.g. aadaa.

A special substring is any substring of a string which meets one of those criteria. Given a string, determine how many special substrings can be formed from it.

Example

s = 'mnonopoo'

s contains the following 12 special substrings:

{'m', 'n', 'o', 'n', 'o', 'p', 'o', 'o', 'non', 'ono', 'opo', 'oo'}

Task:

Write a function called substr_count(s) that accepts a str parameter s and calculates the number of instances of a special string within it.
Use the example above and the test data below to test your function.
Extra Challenge: can you solve this problem efficiently with only one or two passes of s?

Test data

# expected answer = 7
# {'a', 's', 'a', 's', 'd', 'asa', 'sas'}
s = 'asasd'

# expected answer = 10
# {'a', 'b', 'c', 'b', 'a', 'b', 'a'. 'bcb', 'bab', 'aba'}
s = 'abcbaba'

# expected answer = 10
# {'a', 'a', 'a', 'a', 'aa', 'aa', 'aa', 'aaa', 'aaa', 'aaaa'}
s = 'aaaa'

# expected answer = 393074
# len(big_s) = 327308 (!)
f = open("big_special_str.txt", "r")
big_s = f.read()

I have provided the code below to download the instance of big s for you

RESPONSE_SUCCESS = 200
BIG_S_URL = 'https://raw.githubusercontent.com/health-data-science-OR/' \
            + 'hpdm139-datasets/main/big_special_str.txt'

def get_big_s():
    '''
    downloads large test problem
    
    Returns:
    -------
    str - if successful
    None - if unsuccessful
    '''
    response = requests.get(BIG_S_URL)

    if response.status_code == RESPONSE_SUCCESS:
        # return the string
        return response.text
    else:
        print('connection error for big s')
        return None

# test data
test_data = ['mnonopoo', 'asasd', 'abcbaba', 'aaaa', get_big_s()]
expected = [12, 7, 10, 10, 393074]

# your code here

Coding scientific functions

Contents

Coding scientific functions#

Imports#

Exercise 1#

Exercise 2#

Exercise 3#

Exercise 4#

Exercise 5#

Exercise 6#

Exercise 7#

Exercise 8:#