FilesExpand file tree

main

/

optional.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

100 lines (73 loc) · 3.12 KB

main

/

optional.py

Copy path

Top

File metadata and controls

• Code
• Blame

100 lines (73 loc) · 3.12 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

############################

# Optional Challenges

def nth_generalized_number(n, zeroth, first):

"""

Context:

The Fibonacci sequence is a member in a family of sequences defined by a recurrence.

Another sequence is the Lucas Sequence, where its numbers are defined by the following:

L_i = L_{i - 1} + L_{i - 2}

nth_lucas_number(0) = 2

nth_lucas_number(1) = 1

nth_lucas_number(2) = 3

nth_lucas_number(5) = 11

nth_lucas_number(8) = 47

Task:

Abstract over your nth_fibonacci_number function to define this `nth_generalized_number`. Modify the accepted arguments to change the initial numbers

"""

raise NotImplementedError()

def fast_nth_generalized_number(n, zeroth, first, cache={}):

"""

Context:

Looking closely at the `nth_generalized_number`, we see that we might end up

repeating a lot of work. Draw out a call tree of `nth_generalized_number`(5) to convince yourself of this.

One way to optimize this is to use a "cache" so that we can reuse already-computed values.

Task:

Modify your `nth_generalized_number` to accept a cache value

Hint: think about what you've learned in SWC and how you can efficiently "look up" values

"""

raise NotImplementedError()

def two_sum(in_arr, target_value):

"""

Task:

given an array of integers and a target value, return the indices corresponding to the integers that sum

to the target value.

If there is more than one solution you may return any valid set of indices. If there are no pairs satisfying this,

return a None

"""

raise NotImplementedError()

def test_fibonacci_generalized():

# Test unoptimized

assert nth_generalized_number(8, 0, 1) == 21

assert nth_generalized_number(10, 0, 1) == 55

# Test Optimized

assert fast_nth_generalized_number(8, 0, 1) == 21

assert fast_nth_generalized_number(10, 0, 1) == 55

def test_lucas_generalized():

# Test unoptimized

assert nth_generalized_number(8, 2, 1) == 47

assert nth_generalized_number(10, 2, 1) == 123

# Test Optimized

assert fast_nth_generalized_number(8, 2, 1) == 47

assert fast_nth_generalized_number(10, 2, 1) == 123

def test_mixed():

"""

Task:

can you identify WHY the second call fails even though we've established that our code from before was correct?

How do you change the function to make it correct?

Hint:

try smaller `n` and print the cache. In the future we will introduce debuggers, which will make your lives

easier

"""

assert fast_nth_generalized_number(10, 0, 1) == 55

assert fast_nth_generalized_number(10, 2, 1) == 123

def test_two_sum():

assert sorted(two_sum([2, 7, 11, 15], 9)) == [0, 1]

assert sorted(two_sum([3, 2, 4], 6)) == [1, 2]

assert sorted(two_sum([3, 3], 6)) == [0, 1]

assert sorted(two_sum([-1, 5, 1], 0)) == [0, 2]

assert sorted(two_sum([-1, 5, 1], 100)) is None # Do you know why we do an `is None` instead of `== None` ?

if __name__ == "__main__":

test_fibonacci_generalized()

test_lucas_generalized()

test_mixed()

test_two_sum()