# Inf2 - Introduction to Algorithms and Data Structures
# Python lab sheets, Sept-Oct 2019

# LAB SHEET 1: SOLUTIONS TO EXERCISES on pages 8 and 9


# Exercise 1

# even numbers from 6 to 132 inclusive:
[x for x in range(6,134) if x % 2 == 0]
# remember, range(6,134) includes 6 but excludes 134

# alternative, same answer:
[x*2 for x in range(6//2,134//2)]


# Exercise 2

# initial substrings, including empty string:
["python"[:n] for n in range(0,7)]

# final substrings:
["python"[m:] for m in range(0,7)]

# all substrings:
["python"[m:n] for m in range(0,7) for n in range(0,7) if m <= n]
# this works, but generates empty string multiple times
# trick to avoid this:
["python"[m:n] for m in range(0,7) for n in range(0,7) if m < max(n,1)]


# Exercise 3

[(x,y,z) for x in range(1,11) for y in range(1,11) for z in range(1,11)
         if x+y+z == 10]
# range(1,11) gives integers 1,...,10, but could equally use range(1,8) here


# Exercise 4

# first way (once again interpret 'between' as strict):
[x for x in range(1,1000) if x % 5 == 0]
# second way:
[x*5 for x in range(1,200)]

# first way involves ~1000 '%' operations, second way ~200 '*' operations,
# so second way is better (usually around 10 times faster on my machine)


# Exercise 5

# direct method:
[x for x in range(2,714) if 714 % x == 0]

# for a more scalable method, do something like:
import math
L = [x for x in range(2,math.ceil(math.sqrt(714))) if 714 % x == 0]
L + [714 // x for x in L]


# Exercise 6

# directly:
[p for p in range(2,1000) if [x for x in range(2,p) if p % x == 0] == []]

# or more scalably:
[p for p in range(2,1000)
   if [x for x in range(2,math.ceil(math.sqrt(p))+1) if p % x == 0] == []]


# END OF FILE