109 Python Problems for CCPS 109
CCPS 109 Computer Science I Labs
Ilkka Kokkarinen
Chang School of Continuing Education
Ryerson University
Version of January 12, 2022
General requirements
This document contains speci0ications for the lab problems in the course CCPS 109 Computer
Science I, as taught by Ilkka Kokkarinen for Chang School of Continuing Education, Ryerson
University, Toronto, Canada. It contains 109 individual problems (plus 0ive bonus problems) for you
to choose your battles from. The problems are presented roughly in order of increasing complexity.
All problems are designed to allow solutions using only the core computation structures
introduced during the
enough practice problems at the excellent CodingBat Python interactive training site, or acquired
the equivalent knowledge from earlier studies. Except for a handful of problems that explicitly point
out the standard li
ary modules that are useful to solve them, no knowledge of any specialized
Python li
aries is required. Despite this, you are allowed to use anything in the Python 3
standard li
ary that you 0ind useful in constructing your program logic. In computer science and
all of programming, no problem should ever have to be solved twice!
Each co
ectly solved problem is worth the exact same one point to your course grade. Your
grade starts from the baseline of 40 points, by itself not quite enough to pass this course. Solving ten
problems makes your course grade reach 50 points, which co
esponds to the lowest possible
passing course grade of D minus. Solving 0ifty problems (yes, yes, for grownup realsies, those 0ifty
problems can be any 0ifty) takes you up to 90 points where the highest possible grade of A+ awaits.
You must implement all these functions in a single source code
allows you to run the tester109.py script at any time to validate the functions you have
completed so far, so you always know exactly where you are standing on this course. These tests are
executed in the same order that your functions appear inside the labs109.py 0ile.
Your functions may assume that the arguments given to them them are as promised in the
problem speci
whose value or type is invalid. Your functions must especially handle zero integers and empty lists
co
ectly whenever they can be legitimate argument values.
The test for each individual function should take at most a couple of seconds to complete
when executed on an off-the-shelf desktop from the past couple of years. If some test takes a minute
or more to complete, your code is too slow and its logic desperately needs to be streamlined. This is
usually achieved by shaving off one level of nesting from the structured loops, occasionally with the
aid of a set or a dict to remember the stuff that your function has seen and done so far. The
automated tester imposes a twenty second cutoff for each test to complete, after which the test is
forcefully terminated.
Silence is golden. None of your functions should print anything on the console, but return the
expected result silently. You can do some debugging outputs during the development, but remember
to comment all of them out before submission.
https:
github.com/ikokkari/PythonExamples
https:
github.com/ikokkari/PythonExamples
http:
www.scs.ryerson.ca/~ikokkari
https:
codingbat.com/python
http:
www.catb.org/~es
faqs/hacker-howto.html#believe2
https:
github.com/ikokkari/PythonProblems
lo
maste
tester109.py
http:
www.catb.org/~es
writings/taoup/html/ch11s09.html
This speci0ication document and the automated tester are released under GNU Public License
version 3 so that they can be adapted and distributed among all teachers and students of computer
science. The author compiled these problems over time from a gallimaufry of sources ranging from
the original lab and exam problems of his old Java version of this course to a multitude of
programming puzzle and code challenge sites such as LeetCode, CodeA
ey, Stack Exchange Code
Golf, and Wolfram Programming Challenges. Classic recreational mathematics (yes, that is a real
thing) columns by Martin Gardner and his spiritual disciples also inspired many problems.
The author has tried to dodge not just the Scylla of the well-worn problems that you can 0ind in
asically all textbooks and online problem collections, but also the Charybdis of pointless make-
work drudgery that doesn’t have any inherent meaning or purpose on its own, at least above the
lunt 0inger practice to provide billable “jobs for the boys” to maintain the illusion that The Machine
is still churning as intended. Some of these seemingly simple problems also touch the deeper issues
of computer science that you will encounter in your later undergraduate and graduate courses.
Occasionally these problems even relate to entirely separate 0ields of human endeavour, which
makes them have nontrivial worldview implications, both philosophical and practical.
This problem set also has an of0icial associated su
eddit
ccps109 for students to discuss the
individual problems and associated issues. This discussion should take place at the level of ideas, so
that no solution code should be posted or requested. Any issues with course management and the
course schedule in any particular semester should be kept out of this su
eddit to give a more
permanent and fundamental nature. Furthermore, no student should at any time be stuck with any
one problem. Once you embark on solving these problems, you should read ahead to 0ind at least
0ive problems that interest you. Keep them simmering on your mental back burner as you go about
your normal days. Then when you get on an actual keyboard, work on the problem where you feel
yourself being closest to a working solution.
The author wishes to thank past students Shu Zhu Su, Rimma Konoval, Mohammed Waqas,
Zhouqin He and Karel Tutsu for going above and beyond the call of duty in solving these problems
in ways that either revealed e
ors in the original problem speci0ications or the instructor's private
model solutions, or more fortunately, independently agreed with the instructor's private model
solution and by doing so massively raised the con0idence to the co
ectness of both. A legion of
individual students who pointed out ambiguities, e
ors and inconsistencies in particular problems
effectively acted as a giant Zamboni to plane the ice for all future students to skate over a little bit
easier. Members of that horde, you all know who you are. All remaining e
ors, ambiguities and
inconsistencies both logical and extracu
icular remain the sole responsibility of Ilkka Kokkarinen.
Report any and all such e
ors as discovered to XXXXXXXXXX.
https:
leetcode.com/problemset/all
http:
www.codea
ey.com/index/task_list
https:
codegolf.stackexchange.com
https:
codegolf.stackexchange.com
https:
challenges.wolfram.com
https:
en.wikipedia.org/wiki/Recreational_mathematics
https:
en.wikipedia.org/wiki/Recreational_mathematics
https:
www.reddit.com
ccps109
List of Problems
Ryerson letter grade 10
Ascending list 11
Rif0le shuf0le kerfuf0le 12
Even the odds 13
Cyclops numbers 14
Domino cycle 15
Colour trio 16
Count dominators 17
Beat the previous 18
Subsequent words 19
Taxi ℤum ℤum 20
Exact change only 21
Rooks on a rampage 22
Try a spatula 23
Words with given shape 24
Chirality 25
The card that wins the trick 26
Do you reach many, do you reach one? 27
Sevens rule, zeros drool 28
Fulcrum 29
Fail while daring greatly 30
All your fractions are belong to base 31
Recamán's sequence 32
Count the balls off the
ass monkey 33
Count growlers 34
Bulgarian solitaire 35
Scylla or Charybdis? 36
Longest arithmetic progression 37
Best one out of three 38
Collecting numbers 39
Count Troikanoff, I presume 40
Crack the crag 41
Three summers ago 42
Sum of two squares 43
Ca
y on Pythonista 44
As below, so above 45
Expand positive integer intervals 46
Collapse positive integer intervals 47
Prominently featured 48
Like a kid in a candy store, except without money 49
Dibs to dubs 50
Nearest smaller element 51
Interesting, intersecting 52
So shall you sow 53
That's enough of you! 54
Brussel's choice 55
Cornered cases 56
Count consecutive summers 57
McCulloch's second machine 58
That's enough for you! 59
Crab bucket list 60
What do you hear, what do you say? 61
Bishops on a binge 62
Dem’s some mighty tall words, pardner 63
Up for the count 64
Revorse the vewels 65
Everybody on the 0loor, come do the Scrooge Shuf0le 66
Rational lines of action 67
Ve
os regulares 68
Hippity hoppity, abolish loopity 69
Where no one can hear you bounce 70
Nearest polygonal number 71
Don’t wo
y, we will 0ix it in the post 72
Fractran interpreter 73
Permutation cycles 74
Whoever must play, cannot play 75
ztalloc ecneuqes 76
The solution solution 77
Reverse ascending sublists 78
Brangelin-o-matic for the people 79
Line with most points 80
Om nom nom 81
Autoco
ect for sausage 0ingers 82
Uambcsrlne the wrod 83
Substitution words 84
Manhattan skyline 85
Count overlapping disks 86
Ordinary cardinals 87
Count divisibles in range 88
Bridge hand shape 89
Milton Work point count 90
Never the twain shall meet 91
Bridge hand shorthand form 92
Points, schmoints 93
Bulls and cows 94
Frequency sort 95
Calling all units, B-and-E in progress 96
Lunatic multiplication 97
Distribution of abstract
idge hand shapes 98
Fibonacci sum 99
Wythoff a
ay 100
Rooks with friends 101
Possible words in Hangman 102
All
anches lead to Rome 103
Be there or be square 104
Flip of time 105
Bulgarian cycle 106
Square it out amongst yourselves 107
Sum of distinct cubes 108
Count maximal layers 109
Maximum checkers capture 110
Collatzy distance 111
Van Eck sequence 112
Tips and trips 113
Balanced ternary 114
Lords of Midnight 115
Optimal crag score 116
Painted into a corner 117
Go for the Grand: In0inite Fibonacci word 118
Bonus problem 110: Reverse the Rule 110 119
Bonus problem 111: Aye, eye, I 120
Bonus problem 112: Count domino tilings 121
Bonus problem 113: Invaders must die 122
Bonus problem 114: Stepping stones 123
Ryerson letter grade
def ryerson_letter_grade(pct):
Given the percentage grade, calculate and return the letter grade that would appear in the Ryerson
grades transcript, as de0ined on the page Ryerson Grade Scales. This letter grade should be returned
as a string that consists of the uppercase letter followed by the modi0ier '+' or '-', if there is one.
This function should work co
ectly for all values of pct from 0 to 150.
Same as all other programming problems that follow this problem, this can be solved in various
different ways. The simplest way to solve this problem would probably be to use an if-else ladder.
The 0ile labs109.py given in the repository ikokkari/PythonProblems already contains an
implementation of this function for you to run the tester script tester109.py to verify that
everything is hunky dory.
As you learn more Python and techniques to make it dance for you, you may think up other ways to
solve this problem. Some of these would be appropriate for actual productive tasks done in a
professional coding environment, whereas others are intended to be taken in jest as a kind of
conceptual performance art. A popular genre of recreational puzzles in all programming languages
is to solve some straightforward problem with an algorithmic equivalent of a needlessly
complicated Rube Goldberg machine, to demonstrate the universality and unity of all computation.
pct Expected result
45 'F'
62 'C-'
89 'A'
107 'A+'
https:
www.ryerson.ca
egistra
faculty/grading/gradescales_ugrad
https:
github.com/ikokkari/PythonProblems
lo
maste
labs109.py
https:
github.com/ikokkari/PythonProblems
https:
github.com/ikokkari/PythonProblems
lo
maste
tester109.py
https:
en.wikipedia.org/wiki/Rube_Goldberg_machine
Ascending list
def is_ascending(items):
Determine whether the sequence of items is strictly ascending so that each element is strictly
larger (not just merely equal to) than the element that precedes it. Return True if the list of
items is strictly ascending, and return False otherwise.
Note that the empty sequence is ascending, as is also every one-element sequence, so be careful that
your function returns the co
ect answers in these seemingly insigni0icant edge cases of this
problem. (If these sequences were not ascending, pray tell, what would be the two elements that
violate the requirement and make that particular sequence not be ascending?)
In the same spirit, note how every possible universal claim made about the elements of an empty
sequence is trivially true! For example, if items is the empty sequence, the two claims “All elements
of items are odd” and “All elements of items are even” are both equally true, as is also the claim
“All elements of items are colourless green ideas that sleep furiously.”
items Expected result
[] True
[-5, 10, 99, 123456] True
[2, 3, 3, 4, 5] False
[-99] True
[4, 5, 6, 7, 3, 7, 9] False
[1, 1, 1, 1] False
https:
en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously
Riffle shuffle kerfuffle
def riffle(items, out=True):
Given a list of items whose length is guaranteed to be even (note that “oddly” enough, zero is an
even number), create and return a list produced by performing a perfect rif
interleaving the items of the two halves of the list in an alternating fashion.
When performing a perfect rif0le shuf0le, also known as the Faro shuf0le, the list of items is split in
two equal sized halves, either conceptually or in actuality. The 0irst two elements of the result are
then the 0irst elements of those halves. The next two elements of the result are the second elements
of those halves, followed by the third elements of those halves, and so on up to the last elements of
those halves. The parameter out determines whether this function performs an out shuf0le or an in
shuf0le that determines which half of the deck the alternating card is 0irst taken from.
items out Expected result
[1, 2, 3, 4, 5, 6, 7, 8] True [1, 5, 2, 6, 3, 7, 4, 8]
[1, 2, 3, 4, 5, 6, 7, 8] False [5, 1, 6, 2, 7, 3, 8, 4]
[] True []
['bob', 'jack'] True ['bob', 'jack']
['bob', 'jack'] False ['jack', 'bob']
https:
en.wikipedia.org/wiki/Faro_shuffle
https:
en.wikipedia.org/wiki/Out_shuffle
https:
en.wikipedia.org/wiki/In_shuffle
https:
en.wikipedia.org/wiki/In_shuffle
Even the odds
def only_odd_digits(n):
Check that the given positive integer n contains only odd digits (1, 3, 5, 7 and 9) when it is written
out. Return True if this is the case, and False otherwise. Note that this question is not asking
whether the number n itself is odd or even. You therefore will have to look at every digit of the given
number before you can proclaim that the number contains no odd digits.
To extract the lowest digit of a positive integer n, use the expression n%10. To chop off the lowest
digit and keep the rest of the digits, use the expression n
10. Or, if you don't want to be this fancy,
you can 0irst convert the number into a string and work from there with string operations.
n Expected result
8 False
XXXXXXXXXXTrue
42 False
71358 False
0 False
Cyclops numbers
def is_cyclops(n):
A nonnegative integer is said to be a cyclops number if it consists of an odd number of digits so
that the middle (more poetically, the “eye”) digit is a zero, and all other digits of that number are
nonzero. This function should determine whether its parameter integer n is a cyclops number, and
eturn either True or False accordingly.
As an extra challenge, you can try to solve this problem using only loops, conditions and integer
arithmetic operations, without 0irst converting the integer into a string and working from there.
Dividing an integer by 10 with the integer division
effectively chops off its last digit, whereas the
emainder operator % can be used to extract that last digit. These operations allow us to iterate
through the digits of an integer one at the time from lowest to highest, almost as if that integer were
some kind of lazy sequence of digits.
Even better, this operation doesn't work merely for the familiar base ten, but it works for any base
y using that base as the divisor. Especially using two as the divisor instead of ten allows you to
iterate through the bits of the binary representation of any integer, which will come handy in
problems in your later courses that expect you to be able to manipulate these individual bits. (In
practice these division and remainder operations are often further condensed into equivalent but
faster bit shift and bitwise and operations.)
n Expected result
0 True
101 True
98053 True
XXXXXXXXXXFalse
1056 False
XXXXXXXXXXFalse
Domino cycle
def domino_cycle(tiles):
A single domino tile is represented as a two-tuple of its pip values, such as (2,5) or (6,6). This
function should determine whether the given list of tiles forms a cycle so that each tile in the list
ends with the exact same pip value that its successor tile starts with, the successor of the last tile
eing the 0irst tile of the list since this is supposed to be a cycle instead of a chain. Return True if
the given list of tiles forms such a cycle, and False otherwise.
tiles Expected result
[(3, 5), (5, 2), (2, 3)] True
[(4, 4)] True
[] True
[(2, 6)] False
[(5, 2), (2, 3), (4, 5)] False
[(4, 3), (3, 1)] False
Colour trio
def colour_trio(colours):
This problem was inspired by the Mathologer video “Secret of Row 10”. To start, assume the
existence of three values called “red”, “yellow” and “blue”. These names serve as colourful (heh)
mnemonics and could as well have been 0, 1, and 2, or “foo”, “bar” and “baz”; no connection to actual
physical colours is implied. Next, de0ine a rule to mix such colours so that mixing any colour with
itself gives that same colour, whereas mixing any two different colours always gives the third colour.
For example, mixing blue to blue gives that same blue, whereas mixing blue to yellow gives red,
same as mixing yellow to blue, or red to red.
Given the 0irst row of colours as a string of lowercase letters, this function should construct the
ows below the 0irst row one row at the time according to the following discipline. Each row is one
element shorter than the previous row. The i:th element of each row comes from mixing the colours
in positions i and i + 1 of the previous row. Rinse and repeat until only the singleton element of the
ottom row remains, returned as the 0inal answer. For example, starting from the 0irst row
'rybyr' leads to '
', which leads to 'yry', which leads to '
', which leads to 'b' for the
0inal answer, Regis. When the Python virtual machine laughingly goes '
', that will lead to
'y
', '
' , 'y
', and '
' for the 0inal answer 'y' for “Yes, please!”
(Today's 0ive-dollar power word to astonish your friends and coworkers is "quasigroup".)
colours Expected result
'y' 'y'
'
' 'b'
'rybyry' 'r'
'
y
' 'r'
'
yry
y
' 'y'
'y
yyry
' 'b'
https:
www.youtube.com/channel/UC1_uAIS3r8Vu6JjXWvastJg
https:
www.youtube.com/watch?v=9JN5f7_3YmQ&t=1457s
https:
en.wikipedia.org/wiki/Quasigroup
Count dominators
def count_dominators(items):
We shall de0ine an element of a list of items to be a dominator if every element to its right (not
just the one element that is immediately to its right) is strictly smaller than that element. By this
de0inition, the last item of the list is automatically a dominator. This function should count how
many elements in items are dominators, and return that count. For example, the dominators of the
list [42, 7, 12, 9, 13, 5] would be its elements 42, 13 and 5. The last element of the list is
trivially a dominator, regardless of its value, since nothing greater follows it.
Before starting to write code for this function, you should consult the parable of "Shlemiel the
painter" and think how this seemingly silly tale from a simpler time relates to today's computational
problems performed on lists, strings and other sequences. This problem will be the 0irst of many
that you will encounter during and after this course to illustrate the important principle of using
only one loop to achieve in a tiny fraction of time the same end result that Shlemiel achieves with
two nested loops. Your workload therefore increases only linearly with respect to the number of
items, whereas the total time of Shlemiel’s back-and-forth grows quadratically, that is, as a
function of the square of the number of items.
Trying to hide the inner loop of some Shlemiel algorithm inside a function call (and this includes
Python built-ins such as max and list slicing) and pretending that this somehow makes those inner
loops take a constant time will only summon the Gods of Compubook Headings to return with
tumult to claim their lion's share of execution time.
items Expected result
[42, 7, 12, 9, 2, 5] 4
[] 0
[99] 1
[42, 42, 42, 42] 1
ange(10**7) 1
ange(10**7, 0, XXXXXXXXXX
http:
wiki.c2.com/?ShlemielThePainte
http:
wiki.c2.com/?ShlemielThePainte
Beat the previous
def extract_increasing(digits):
Given a string of digits guaranteed to only contain ordinary integer digit characters 0 to 9, create
and return the list of increasing integers acquired from reading these digits in order from left to
ight. The 0irst integer in the result list is made up from the 0irst digit of the string. After that, each
element is an integer that consists of as many following consecutive digits as are needed to make
that integer strictly larger than the previous integer. The leftover digits at the end of the digit string
that do not form a suf0iciently large integer are ignored.
This problem can be solved with a single for-loop through the digits that looks at each digit
exactly once regardless of the position of that digit in the beginning, end or middle of the string.
Keep track of the cu
ent number (initially zero) and the previous number to beat (initially
equal to minus one). Each digit d is then processed by pinning it at the end of cu
ent number
with the assignment cu
ent=10*cu
ent+int(d).
digits Expected result
'600005' [6]
'045349' [0, 4, 5, 34]
'777 XXXXXXXXXX' [7, 77, 777, 7777, 77777, 777777]
'1 XXXXXXXXXX' [1, 2, 23, 33, 44, 445, 555, 566,
666]
'27182 XXXXXXXXXX
471352 XXXXXXXXXX
957496 XXXXXXXXXX
475945 XXXXXXXXXX
466391 XXXXXXXXXX
66 XXXXXXXXXX'
[2, 7, 18, 28, 182, 845, 904,
5235, 36028, 74713, 526624,
977572, XXXXXXXXXX, XXXXXXXXXX,
XXXXXXXXXX, XXXXXXXXXX, XXXXXXXXXX,
XXXXXXXXXX, XXXXXXXXXX,
XXXXXXXXXX, XXXXXXXXXX,
XXXXXXXXXX]
'1234' * 100 A list with 38 elements, the last one equal to
3 XXXXXXXXXX
'420' * 420 A list with 56 elements, the last one equal to
4204204204204 XXXXXXXXXX
XXXXXXXXXX
Subsequent words
def words_with_letters(words, letters):
This problem is an excuse to introduce some general discrete math terminology that helps make
many later problem speci0ications less convoluted and ambiguous. A substring of a string consists
of characters taken in order from consecutive positions. Contrast this with the similar concept of
subsequence of characters still taken in order, but not necessarily at consecutive positions. For
example, each of the 0ive strings '', 'e', 'put', 'ompu' and 'computer' is both a substring
and subsequence of the string 'computer', whereas 'cper' and 'out' are subsequences, but
not substrings.
Note how the empty string is always a substring of