Class 36 — Wednesday April 28

Remembering what you know

Guns and violence — Do not mix well together — Need to do something

---

Look both ways

• Back or ahead

---

Agenda

• Problem solving

• Traveling Salesperson Problem (TSP)

---

Project

• Support TSP heuristics.

• In the below Wikipedia figure, the red dots represent city locations and the tour of edges connecting them is the least length of all tours.

---

Downloads

• Tester run.py

• Module line.py

• Module tex.py

• Module just.py

• Module check.py

• Module inv.py

• Module bit.py

• Module sim.py

• Module exc.py

---

Module line.py

• Defines a single function y(). The function has three numeric parameters, m, x, and b.

• The function returns the value of the expression m ⋅ x + b.

• The built-in tester for the module should produce the following output.

y( 3, 5, 7): 22

y( 5, 7, 3): 38

y( 7, 3, 5): 26

---

Module tex.py

• The module defines a single function words(). The function has a single string parameter s.

• The function returns the number of words in s.

• The built-in tester for the module should produce the following output.

words( "The cow mooed and mooed" ): 5

words( "All things must pass" ): 4

words( "I have a dream that one day" ): 7

---

Module just.py

• Defines a single function one(). The function has four logical (True / False) parameters w, x, y, and z.

• The function returns whether exactly one of parameters w, x, y, and z is equal to True.

• A list whose elements are the values of w, x, y, and z could prove helpful.

• The built-in tester for the module should produce the following output.

one( True, False, False, False): True

one( False, False, True, True): False

one( False, False, True, False): True

one( False, True, False, False): True

one( False, False, False, False): False

---

Module check.py

• Defines a single function in_order(). The function has a list of integers parameter x.

• The function returns whether the values in x are arranged in numeric order.

• The built-in tester for the module should produce the following output.

in_order( [1] ): True

in_order( [2, 5, 4] ): False

in_order( [5, 6, 8, 8] ): True

in_order( [7, 7, 1, 7, 9] ): False

---

Module inv.py

• Defines a single function erse(). The function has one dataset parameterd. The cell values ind` are all numeric.

• The function returns a new dataset. The values in the new dataset are the additive inverses of the values in d; that is if an individual cell in d has value v, then the corresponding cell in the new dataset has value -v.

• The built-in tester makes uses of datasets d1 and d2.

d1 = [ [ 3, 1, -4 ], [ 1, 5 ], [ -9, -2], [ -6 ] ]

d2 = [ [ 1 ], [ 0 ], [-1 ] ]

• The built-in tester for the module should produce the following output.

erse( d1 ): [[-3, -1, 4], [-1, -5], [9, 2], [6]]

erse( d2 ): [[-1], [0], [1]]

---

Module bit.py

• Defines a single function ter(). The function has two integers parameter n and k.

• The function returns a new list with n elements. Each element is a random value between 0 and k-1.

• Your code may not make use of the random module seed() function.

• The built-in tester for the module should produce the following output.

ter( 5, 2 ): [1, 0, 1, 0, 1]

ter( 8, 10 ): [4, 1, 4, 8, 0, 6, 1, 9]

---

Module sim.py

• Defines a single function metric(). The function has one dictionary parameterd`.

• The function returns True or False depending whether d is a symmetric dictionary.

• A dictionary is symmetric if for every mapping k to v in the dictionary, then there is also a mapping of v to k in the dictionary.

• Recommendation: Loop on the keys in d. Suppose key k maps to value v.

• If v is not in d.keys(), then there is a missing mapping for dictionary d to be symmetric.

• If instead d[ v ] is not equal to k, then there is a missing mapping for dictionary d to be symmetric.

• If there are no missing mappings, d is symmetric.

• The built-in tester for the module should produce the following output.

metric( {1: 2, 2: 3, 3: 1} ): False

metric( {1: 2, 2: 1, 3: 4, 4: 3} ): True

metric( {1: 2, 2: 5} ): False

---

Module exc.py

• The module efines a single function lusive(). The function has has two list parameterxandy`.

• The function returns a new list whose elements are all of the elements of x that are not in y, followed by all of the elements of y that are not in x.

• The built-in tester for the module should produce the following output.

lusive( [3, 5, 9], [2, 5, 3, 5, 8, 8] ): [9, 2, 8, 8]

lusive( [9, 7, 3, 2], [2, 3, 7] ): [9]

lusive( [3], [1, 4] ): [3, 1, 4]

lusive( [], [1, 2, 3] ): [1, 2, 3]

lusive( [1, 2], [1, 2] ): []

 

---

🦆 © 2022 Jim Cohoon

Resources from previous semesters are available.