# Second Sage Lecture¶

## Lists¶

range(from=0, to, step=1)


• [ ) interval notation
• inclusive from the left and exclusive from the right
• Also 0-based indexing!
In [1]:
range(5, 10)

Out[1]:
[5, 6, 7, 8, 9]
In [2]:
[1, 2, 3][0] == 1

Out[2]:
True

## List comprehension¶

[ f(x) for x in ___ ]
In [3]:
[n for n in range(10)]

Out[3]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [4]:
[n^2 for n in range(1,11)]

Out[4]:
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

### Selection¶

[ f(x) for x in ___ if g(x) ]


• f(x) is the result
• g(x) is a boolean function (condition) ### either/or values
[ f1(x) if g(x) else f2(x) for x in ___ ]

Every element will appear in the list, but some with f1(x) values, others with f2(x) values (depending in g(x))

In [5]:
print range(1,21)
[ 3*x+1 if x%2==1 else x//2 for x in range(1,21) ]

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Out[5]:
[4, 1, 10, 2, 16, 3, 22, 4, 28, 5, 34, 6, 40, 7, 46, 8, 52, 9, 58, 10]

### multiple for¶

Means cross product or Descartes product.

[(i,j) for i in ___ for j in ___ ]



Goes through (i, j) pairs in the cross product.

Not the same as:

[[(i,j) for i in ___ ] for j in ___ ]



Because that is a list-of-lists!

In [6]:
print([ (i, j) for i in range(5) for j in range(5) ] )
print
print([[ (i, j) for i in range(5)] for j in range(5) ] )

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4)]

[[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)], [(0, 1), (1, 1), (2, 1), (3, 1), (4, 1)], [(0, 2), (1, 2), (2, 2), (3, 2), (4, 2)], [(0, 3), (1, 3), (2, 3), (3, 3), (4, 3)], [(0, 4), (1, 4), (2, 4), (3, 4), (4, 4)]]


## Functions¶

inline:

f(x) = x^2



declaration:

def f(x):
return x^2


• Mind the colon and the identation!
• The identation decides where to end the function.
• The return is not necessarily the last line, but nothing is executed after that!
In [7]:
x=var('x')
f(x)=x^2
def g(x):
return x^2
def h(x):
return x^2
print('ooh!')

print(f(3), g(3))
print(diff(f,x,1))
print(diff(g(x),x,1))

(9, 9)
x |--> 2*x
2*x


There is a difference between inline and declared functions.

• inline functions can contain only one expression
• inline functions are mathematically funcitions
• declared functions are functions in the programming sense
In [8]:
f?


## Condition¶

inline:

f1(x) if g(x) else f2(x)



programming:

if g(x):
f1(x)
else:
f2(x)



Mind the colon and the identation! The else part is optional.

In [9]:
def parity(a):
if a%2 == 0:
return "even"
else:
return "odd"
return 0
print(parity(6))

even


If you miss the return then the result is a unique None value. You cannot miss the return in inline functions.

In [10]:
def parity2(a):
if a%2 == 0:
return "even"
else:
print "odd"
'ooh'
print(parity2(5))

odd
None

In [11]:
def gcd(a,b):
if (b == 0):
return a
return gcd(b, a%b)
print(gcd(50,15))

5

In [12]:
def factorial(n):
if n==0:
return 1
return n*factorial(n-1)
factorial(10)

Out[12]:
3628800
In [13]:
def factorial2(x):
return x*factorial2(x-1)
factorial2(10)

---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-13-35a00d34a177> in <module>()
1 def factorial2(x):
2     return x*factorial2(x-Integer(1))
----> 3 factorial2(Integer(10))

<ipython-input-13-35a00d34a177> in factorial2(x)
1 def factorial2(x):
----> 2     return x*factorial2(x-Integer(1))
3 factorial2(Integer(10))

... last 1 frames repeated, from the frame below ...

<ipython-input-13-35a00d34a177> in factorial2(x)
1 def factorial2(x):
----> 2     return x*factorial2(x-Integer(1))
3 factorial2(Integer(10))

RuntimeError: maximum recursion depth exceeded while calling a Python object

## Tower of Hanoi¶

The puzzle was invented by the French mathematician Édouard Lucas in 1883. There is a story about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it, surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks in accordance with the immutable rules of Brahma since that time. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle is completed, the world will end.

https://en.wikipedia.org/wiki/Tower_of_Hanoi

In [14]:
A = [5, 4, 3, 2, 1]
B = []
C = []
def move(n, source, target, auxiliary):
if n > 0:
# move n - 1 disks from source to auxiliary, so they are out of the way
move(n - 1, source, auxiliary, target)
# move the nth disk from source to target
target.append(source.pop())
# Display our progress
print(A, B, C)
# move the n - 1 disks that we left on auxiliary onto target
move(n - 1, auxiliary, target, source)
# initiate call from source A to target C with auxiliary B
move(5, A, C, B)

([5, 4, 3, 2], [], [1])
([5, 4, 3], [2], [1])
([5, 4, 3], [2, 1], [])
([5, 4], [2, 1], [3])
([5, 4, 1], [2], [3])
([5, 4, 1], [], [3, 2])
([5, 4], [], [3, 2, 1])
([5], [4], [3, 2, 1])
([5], [4, 1], [3, 2])
([5, 2], [4, 1], [3])
([5, 2, 1], [4], [3])
([5, 2, 1], [4, 3], [])
([5, 2], [4, 3], [1])
([5], [4, 3, 2], [1])
([5], [4, 3, 2, 1], [])
([], [4, 3, 2, 1], [5])
([1], [4, 3, 2], [5])
([1], [4, 3], [5, 2])
([], [4, 3], [5, 2, 1])
([3], [4], [5, 2, 1])
([3], [4, 1], [5, 2])
([3, 2], [4, 1], [5])
([3, 2, 1], [4], [5])
([3, 2, 1], [], [5, 4])
([3, 2], [], [5, 4, 1])
([3], [2], [5, 4, 1])
([3], [2, 1], [5, 4])
([], [2, 1], [5, 4, 3])
([1], [2], [5, 4, 3])
([1], [], [5, 4, 3, 2])
([], [], [5, 4, 3, 2, 1])