Colab Ideas

Here I liste ideas of exercises and active sessions, to be implemented in colab, adding tags to specify the concepts explored by the exercise or activity. When implemented, I add a link to the Python Notebook(s) implementing the idea of exercise.

1 Parrot: Extend the functionalities of a function implementing a parrot.

1.1 Temas vistos sin aprofondizaje

while,
break,
Programas Interactivos,

1.2 Objetivos de aprendizaje

En su solucion, el alumno debe demostrar su capacidad a

usar los operadores booleanos and y or;
usar structuras if, elif y else;
usar varias operaciones sobre strings (que puede encontrar con help(str)).
usar la funcion help

1.3 Instructions

Consider the following basic program:

string = input("kwak! ")
while True
  if string.upper() == "HOLA!":
    print("Holi!")
  elif string == "Holi":
    print("Hola!")
  elif string ==""
    break
  else:
    print(string+"!")
print("Ciao!")

Check the documentation of the str data structure (execute help(str) in a code cell)

Para evaluar su rendimiento en la actividad, preguntense si usaron cada una de las funciones siguientes:

[ ] or (e.g. string = “hola”= or string =“holi”=)
[ ] + (e.g. =string+”!”=)
[ ] string.upper() (e.g. print(string.upper())
[ ] string.casefold()
[ ] string.beginswith() o string.endswith()
[ ] and (e.g. string.startswith("Hey!") and string.endswith("!"))

2 Scalable recipe: Given your favorite recipe, program a function scaling the ingredients (cleverly: no half eggs) for the amount of serving requested

3 Shell Drawing: Using Turtle and For loops, draw series of triangle, up to form a shell

4 ROT13 Code: implement rot13(string), which adds 13 modulo 26 to each alphabetic letter of a string.

5 Cesar Code: implement cesar(string,shift), which adds shift modulo 26 to each alphabetic letter of a string.

6 Bible Code: implement rot13(string,shifts), which adds shift[i%len(shift)] modulo 26 to the ith letter of a string.

7 Cipher Bomb Cesar: implement decipherCesar(cipher,dictionary), which returns the strings which words match a maximum of those in the dictionary while coding to cipher via some cesar code

8 Cipher Bomb Bible: implement decipherBible(cipher,dictionary,lenght), which returns the strings which words match a maximum of those in the dictionary while coding to cipher via some bible code of lenght at most length

9 Hanoi Tower Puzzle: implement a function giving the sequence of moves solving the Hanoi puzzle (Bonus: use a library which animates the discs)

10 Hanoi Diagram: draw the diagram of all states of a Hanoi puzzle of $n$ disks

11 Disk Pile Puzzle: implement a function giving the sequence of moves solving the Disk Pile puzzle (variant of Hanoi with some disks of same size)

12 Cheese Tower Puzzle: variant of the Hanoi tower where each disk can support at most the double of its weight

I always tell student that in the Hanoi puzzle, one cannot put a large disk on top of a smaller one because it would break, an argument which would not hold in practice if the difference of size is small enough. An interesting variant is one where the rule is about the (cumulated) weight that each disc can support (like a camembert cheese can support another one, but not a whole pile of them).

12.0.1 How many moves are required to move a tower of $n$ disks if allowing a disk to support at most the double of its weight, and the weights of the disks are a linear sequence (e.g. $1,2,3,4,\ldots$)?

ANSWER: none, a tower of height more than $6$ cannot exist!
PROOF:
- Solve $∑_i=1^n-1 i > 2n$
- $\frac{n(n-1)}{2} > 2n$
- $n-1>4$
- $n>5$

12.0.2 How many moves are required to move a Hanoi tower of $n$ disks if allowing a disk to support at most the double of its weight, and the weights of the disks are a quadratic sequence (e.g. $1,4,9,16,25,36,49,64,81\ldots$)?

ANSWER: none, a tower of height more than $6$ cannot exist:
PROOF:
- $1+4+9+16+25+36+49=140 > 2*64 =128$

12.0.3 How many moves are required to move a tower of $n$ disks if allowing a disk to support at most the double of its weight, and the weights of the disks are an exponential sequence (e.g. $1,2,4,8,16,32,64,128,256\ldots$)?

Of course, the exponential sequence is the smaller one for which such cumulative rule could work:
- $∑_i=1^n-1 2^i > 2*2^n = 2ⁿ⁺¹$
Yet such a Cheese tower requires less moves than a Hanoi Tower for $n>=3$:

The recursive formula (and algorithm) is C(n) = 2*C(n-1)+1 if n>4 and from the array above otherwise.
The proof of optimality resides in the observation that,
- given the rule that a disc can support at most $2$ times its weight (summed over all discs it supports)
- any peg with such an inversion is frozen and cannot support any more disc.

n	1	2	3	4	5	6	7	8	…
H(n)	1	3	7	15	31	63	127	255	…
C(n)	1	3	5	10	<=21	<=43	<=87	<=175	…

(when one disc supports a disc larger than it, it is the double and it can’t support ANY other disc)
- Hence this trick can be used only for the top discs and not the bottom ones (which once inverted could not support any more discs).
- The code to check such solution is at

https://colab.research.google.com/drive/1RnQFlUfL6iptEmHExkwft2iDigIAjRYD?usp=sharing

12.1 Cheese Tower Puzzle Diagram

13 Selenite Tower Puzzle: variant of the Hanoi tower where one inserts and removes disks from the middle of the tower

13.1 Selenite Tower Puzzle Diagram

14 Operations on IMDB Graph: recover the IMDB graph and runs a graph algoritm on it.

jyby/ColabIdeas