davecom / classiccomputerscienceproblemsinpython Goto Github PK

The constructor of the Graph class has [] as the default value for the vertices parameter. However, this implementation would fail the following test code.

class TestGraph(unittest.TestCase):
    def setUp(self):
        self.graph = Graph()

    def test_add_vertex(self):
        self.assertEqual(self.graph.vertex_count, 0)

    def test_remove_vertex(self):
        self.graph.add_vertex('A')
        self.graph.add_vertex('B')
        self.graph.add_vertex('C')
        self.assertEqual(self.graph.vertex_count, 3)

The reason for this issue is explained in detail in the following link:

Mutable Default Arguments - Python Guide

I'm trying to follow your logic in the generic algorithms chapter but I get the following error on send_more_money2.py:
`Generation 0 Best 0.2 Avg 0.0003496131148208891
Traceback (most recent call last):

File "", line 1, in
runfile('/datos/Scripts/Gitea/Classic_problems/Chapter_5__Genetic_algorithms/send_more_money2.py', wdir='/datos/Scripts/Gitea/Classic_problems/Chapter_5__Genetic_algorithms')

File "/datos/Scripts/Python/venv/lib/python3.7/site-packages/spyder_kernels/customize/spydercustomize.py", line 827, in runfile
execfile(filename, namespace)

File "/datos/Scripts/Python/venv/lib/python3.7/site-packages/spyder_kernels/customize/spydercustomize.py", line 110, in execfile
exec(compile(f.read(), filename, 'exec'), namespace)

File "/datos/Scripts/Gitea/Classic_problems/Chapter_5__Genetic_algorithms/send_more_money2.py", line 87, in
result: SendMoreMoney2 = ga.run()

File "/datos/Scripts/Gitea/Classic_problems/Chapter_5__Genetic_algorithms/genetic_algorithm.py", line 86, in run
highest: C = max(self._population, key=self._fitness_key)

File "/datos/Scripts/Gitea/Classic_problems/Chapter_5__Genetic_algorithms/send_more_money2.py", line 22, in fitness
s: int = self.letters.index("S")

ValueError: 'S' is not in list`

My solutions are not converging to the ones you described in chapter 5. I got the above error, with random letters, every time I run the code.

Any suggestions?

P.S.: Great book!

line 20 in file fib2.py should return 1 when n <=2

ATM it returns n

Great book. Favourite book currently.

I hand typed and then copy pasted the code from the dna search problem 2.1.1 and got

False
False

as my answers, not # true # false as commented.

Then I cut and pasted the code and got the same response. I can see that the codon acg is in the gene so I suspect a bug.

Massive noob so probably my fault. Happy to learn.

In the word_search.py (chapter 3)
columns: range = range(col, col + length + 1) and
rows: range = range(row, row + length + 1)
should be
columns: range = range(col, col + length)
rows: range = range(row, row + length)

The original code (regularly but not always) throws the following error when generating a 7x7 grid:

IndexError Traceback (most recent call last)
in
19 for index, letter in enumerate(word):
20 (row, col) = (grid_locations[index].row, grid_locations[index].column)
---> 21 grid[row][col] = letter
22 display_grid(grid)

IndexError: list assignment index out of rang

While solving the problem in missionaries.py using generic_search.py from Chapter 2, I found out that there are duplicate instances of MCState in Node::explored.

This is probably a problem where instances with the same value are not recognized as the same instance and are, therefore, duplicated in the set.

Hello there,
I think, you should modify the type hints, since the xdist and ydist are both integer, so sum of them is going to be integer too, right?

fib5.py in Chapter 1 uses the variable name "next", which is a builtin name and is best avoided in Python. Although less readable, I suggest renaming the variables to something like this:

def fib5(n: int) -> int:
    if n == 0: return n  # special case
    lst: int = 0  # initially set to fib(0)
    next: int = 1  # initially set to fib(1)
    for _ in range(1, n):
        lst, nxt = nxt, lst + nxt
    return nxt

The generate_domain function in word_search.py is buggy when finding possible locations down the diagonal to the left. For example, a 6x6 grid like the one below fails to find the lower left diagonal location of the word PYTHON:

word = 'PYTHON'
grid = [['P', 'Y', 'T', 'H', 'O', 'N'],
        ['A', 'B', 'C', 'D', 'E', 'F'],
        ['G', 'H', 'I', 'J', 'K', 'L'],
        ['M', 'N', 'O', 'P', 'Q', 'R'],
        ['S', 'T', 'U', 'V', 'W', 'X'],
        ['Y', 'Z', 'A', 'B', 'C', 'D']]

In the code that you provided, the gene sequence is not explicitly sorted, so the binary search algorithm will not work correctly on this gene sequence.

Hi, first of all thanks for your great book.
You could just save the nucleotide inside a dictionary, instead of iterating on each one.

NUCLEOTIDES_MAP = {
    'A': 0b00,
    'C': 0b01,
    'G': 0b10,
    'T': 0b11,
}
RMAP = {v: k for k, v in NUCLEOTIDES_MAP.items()}

Dear Sir,

Are there any solutions to the exercises?

In Chapter2/generic_search.py class Queue was defined as follows.

class Queue(Generic[T]):
    def __init__(self) -> None:
        self._container: Deque[T] = Deque()

I think that class Quene should be defined as follows.
I use collections.deque instead of typing.Deque.

from collections import deque

class Queue(Generic[T]):
    def __init__(self) -> None:
        self._container: Deque[T] = deque()

In Chapter2/generic_search.py, if an object is used in Set or Dict, shouldn't it implement its own __hash__?

For example:
generic_search.py

def bfs(initial: T, goal_test: Callable[[T], bool], successors: Callable[[T], List[T]]) -> Optional[Node[T]]:
    ...
    # explored is where we've been
    explored: Set[T] = {initial}

missionaries.py

class MCState:
    ...

I don't see MCState implement its __hash__, which means by default, all objects will compare unequal except with themselves?

Hello there,
Python str.join method accepts any kind of iterable object so, you could use a generator expression here. However, it is not a big different.

        output += "".join(c.value for c in row) + "\n"