Solution of code fails on passing tests

Programming Python
1

Could anybody help me with my solution of Dominoes exam (section Python)? In Pycharm, everything works well but when I try to submit, 7 from 13 tests are not passed. My I understood something wrong? Or using importing “copy” is not allowed? I understand that my code is cumbersome due to frequent use of deepcopy, but it should not influence the functionality.


from copy import deepcopy

def search_number_twin(number, dominoes_list, solution_list, alternate_list):
    _dominoes_list = deepcopy(dominoes_list)

    found = False
    next_element = []
    for element in _dominoes_list:
        for side in range(2):
            if element[side] == number:
                if found == False:
                    found = True
                    next_element = deepcopy(element)
                    if side == 1:
                        next_element.reverse()
                    dominoes_list.remove(element)
                else:
                    new_alternate = [deepcopy(solution_list)]
                    new_element = deepcopy(element) 
                    if side == 1:
                        new_element.reverse()
                    new_alternate[0].append(new_element)
                    new_dominoes_alternate = deepcopy(_dominoes_list)
                    new_dominoes_alternate.remove(element)
                    new_alternate.append(new_dominoes_alternate)
                    alternate_list.append(new_alternate)

    return next_element

def can_chain(dominoes):

    if dominoes == []:
        return []

    exists = True
    dominoes_list = []
    last_element = list(dominoes[0])
    another_last_element = deepcopy(last_element)
    another_last_element.reverse()
    solution_list = [last_element]
    dominoes.remove(dominoes[0])
    for domino in dominoes:
        dominoes_list.append(list(domino))
    alternate_list = [[[another_last_element], deepcopy(dominoes_list)]]

    while dominoes_list != []:
        next_element = search_number_twin(last_element[1], dominoes_list, solution_list, alternate_list)
        if next_element != []:
            last_element = deepcopy(next_element)
            solution_list.append(deepcopy(next_element))
        elif len(alternate_list) > 0:
            solution_list = alternate_list[len(alternate_list) - 1][0]
            last_element = solution_list[len(solution_list) - 1]
            dominoes_list = alternate_list[len(alternate_list) - 1][1]
            alternate_list.remove(alternate_list[len(alternate_list) - 1])
        else:
            print("Solution does not exist.")
            exists = False
            break

    if exists:
        solution = []
        for element in solution_list:
            solution.append(tuple(element))

        return solution
2

When you say it “doesn’t work”, what exactly does the test output?

3

Hi @smota-git :wave:

When I run your code, I am getting test failures that seem to indicate you are not removing some dominos when you should (in some scenarios).

For example the test case:

input_dominoes = [(1, 2), (3, 1), (2, 3)]
output_chain = can_chain(input_dominoes)
self.assert_correct_chain(input_dominoes, output_chain)

Throws the following error:

AssertionError: Lists differ: [(1, 3), (2, 3)] != [(1, 2), (1, 3), (2, 3)]

First differing element 0:
(1, 3)
(1, 2)

Second list contains 1 additional elements.
First extra element 2:
(2, 3)

- [(1, 3), (2, 3)]
+ [(1, 2), (1, 3), (2, 3)]
?      ++++++++
 : Dominoes used in the output must be the same as the ones given in the input

Note that the second list (the output from your code) is longer than the expected result. Somehow, your code is not outputting the same chain as what the tests expect.

It would be helpful if we could see the test output from PyCharm as well as the test failures you are getting when you submit. That way we can drill down on the details of what might be going wrong. :smile:

4

Hi, @BethanyG,

when I submit in exercism, one of 7 unsuccesfull test cases returns the same answer as you got. This makes me confused in 2 ways:

  1. In Pycharm installed on my computer, in case of the input being [(1, 2), (3, 1), (2, 3)], my code returns the chain [(1, 2), (2, 3), (3, 1)]. More concretely, the Pycharm output is

" [(1, 2), (2, 3), (3, 1)]

Process finished with exit code 0 "

which differs from the chain produced by my code in exercism. Maybe importing “deepcopy” from modul “copy” does not work in exercism?
2) As I understand, exercism expects my code to produce in this case [(1, 3), (2, 3)]. But this contradicts the Instructions which want me to produce a connected chain of dominoes from given set of dominoes. Or do I understand something wrong? Especially, let me highlight this sentence from Instructions:

" For example given the stones [2|1] , [2|3] and [1|3] you should compute something like [1|2] [2|3] [3|1] or [3|2] [2|1] [1|3] or [1|3] [3|2] [2|1] etc, where the first and last numbers are the same."

So, in given case, the lists differ, but I don’t understand the solution which the exercism wants me to produce. Although the input contains 3 dominoes, there should be only 2 dominoes in output?? And how to explain the disagreement with the sentence in Instructions?

Thank you for your help.

5

Hi, @IsaacG,

one of the test cases I discussed with @BethanyG as you can see. More concretely, for the intput [(1, 2), (3, 1), (2, 3)], the output should be [(1, 3), (2, 3)] but my code (surprisingly for me) produces [(1, 2), (1, 3), (2, 3)] (which differs from result [(1, 2), (2, 3), (3, 1)] produced in Pycharm installed on my computer). This you can see in the output of the test:

AssertionError: Lists differ: [(1, 3), (2, 3)] != [(1, 2), (1, 3), (2, 3)]

Neglecting the problem of disagreement of what my code produces on different machines, I don’t understand the disagreement between the Instructions and what the code should produce. Or do I understand something wrong?

6

It would help if you could copy/paste the exact/full test failure output.

8

Some examples:

CODE RUN:
input_dominoes = [(1, 2), (3, 1), (2, 3)]
output_chain = can_chain(input_dominoes)
self.assert_correct_chain(input_dominoes, output_chain)

TEST FAILURE:
AssertionError: Lists differ: [(1, 3), (2, 3)] != [(1, 2), (1, 3), (2, 3)]

First differing element 0:
(1, 3)
(1, 2)

Second list contains 1 additional elements.
First extra element 2:
(2, 3)

- [(1, 3), (2, 3)]
+ [(1, 2), (1, 3), (2, 3)]
?      ++++++++
 : Dominoes used in the output must be the same as the ones given in the input

CODE RUN:
input_dominoes = [
    (1, 2),
    (5, 3),
    (3, 1),
    (1, 2),
    (2, 4),
    (1, 6),
    (2, 3),
    (3, 4),
    (5, 6),
]
output_chain = can_chain(input_dominoes)
self.assert_correct_chain(input_dominoes, output_chain)

TEST FAILURE:
AssertionError: Lists differ: [(1, 2), (1, 3), (1, 6), (2, 3), (2, 4), (3, 4), (3, 5), (5, 6)] != [(1, 2), (1, 2), (1, 3), (1, 6), (2, 3), (2, 4), (3, 4), (3, 5), (5, 6)]

First differing element 1:
(1, 3)
(1, 2)

Second list contains 1 additional elements.
First extra element 8:
(5, 6)

- [(1, 2), (1, 3), (1, 6), (2, 3), (2, 4), (3, 4), (3, 5), (5, 6)]
+ [(1, 2), (1, 2), (1, 3), (1, 6), (2, 3), (2, 4), (3, 4), (3, 5), (5, 6)]
?              ++++++++
 : Dominoes used in the output must be the same as the ones given in the input
9

In the last case, the lists differ as well (and my code is in disagreement with what produces my Pycharm), but neglecting the differences, the “official” solution also contradicts the Instructions (the presented solution does not create chain). Do I understand something in Instructions bad?

10

Your code contains:

def can_chain(dominoes):
    ....
    dominoes.remove(dominoes[0])
    ...

The test runs:

output_chain = can_chain(input_dominoes)
self.assert_correct_chain(input_dominoes, output_chain)

Since your code does dominoes.remove(dominoes[0]) this means the input_dominoes used on those two lines of the unit test are different values. Could that be part of the issue?

How are you running local tests in PyCharm? Are you using pytest?

11

Thank you for your idea - that was the problem. I was changing the input data during the calculation and I did not know that the test does not make its own copy of input_data before the execution starts. Now it works properly. I submitted my solution now and I asked another question - it is connected with frequent use of deepcopy in my code and possible improvements. Do you want to deal with it or you have not time? If you have time, we can continue this discussion in this thread or we can close it and continue on the place where I asked for mentoring the submitted solution. What do you prefer?

To your last question - in Pycharm, I execute the code separately, i.e. I am not using any tests and just only verify the functionality by using different input values. That is why I did not see there any problems.

12

If you’re working locally, you really, really should be running the unit tests. If you’re not running the tests, it’s really, really difficult to assess if your solution works or not – you are not testing your code against the same requirements that the platform and everyone else is using. You might think, “my code does X, so it works” but the exercise actually requires Y. Running the tests locally is easy. See the “working locally” docs.

Either works. If you requested a code review, the people on this thread may not see it. The first mentor to accept the code review is the last person that can see your question. Whomever picks up your request hopefully answers the question for you so you may not even have that question anymore.

13

Here is my code after last revision:

from copy import deepcopy

def search_number_twin(number, dominoes_list, solution_list, alternate_list):
    _dominoes_list = deepcopy(dominoes_list)

    found = False
    next_element = []
    for element in _dominoes_list:
        for side in range(2):
            if element[side] == number:
                if not found:
                    found = True
                    next_element = deepcopy(element)
                    if side == 1:
                        next_element.reverse()
                    dominoes_list.remove(element)
                else:
                    new_alternate = [deepcopy(solution_list)]
                    new_element = deepcopy(element)
                    if side == 1:
                        new_element.reverse()
                    new_alternate[0].append(new_element)
                    new_dominoes_alternate = deepcopy(_dominoes_list)
                    new_dominoes_alternate.remove(element)
                    new_alternate.append(new_dominoes_alternate)
                    alternate_list.append(new_alternate)

    return next_element

def can_chain(dominoes):

    wc_dominoes = deepcopy(dominoes)

    if wc_dominoes == []:
        return []

    exists = True
    dominoes_list = []
    last_element = list(wc_dominoes[0])
    another_last_element = deepcopy(last_element)
    another_last_element.reverse()
    solution_list = [last_element]
    wc_dominoes.remove(wc_dominoes[0])
    for domino in wc_dominoes:
        dominoes_list.append(list(domino))
    alternate_list = [[[another_last_element], deepcopy(dominoes_list)]]

    while dominoes_list != []:
        next_element = search_number_twin(last_element[1], dominoes_list, solution_list, alternate_list)
        if next_element != []:
            last_element = deepcopy(next_element)
            solution_list.append(deepcopy(next_element))
        elif len(alternate_list) > 0:
            last_alternate_position = len(alternate_list) - 1
            solution_list = alternate_list[last_alternate_position][0]
            last_element = solution_list[len(solution_list) - 1]
            dominoes_list = alternate_list[last_alternate_position][1]
            alternate_list.remove(alternate_list[last_alternate_position])
        else:
            print("Solution does not exist.")
            exists = False
            break

    if exists:

        if solution_list[0][0] != solution_list[-1][1]:
            print("Solution does not exist.")
            return     
        
        solution = []
        for element in solution_list:
            solution.append(tuple(element))

        return solution

Somebody already mentored this, but if you don’t mind, we can discuss it here as well. This works well, but I am interested in your opinion on such a kind of architecture of an algorithm (especially frequent use of deepcopy). Do you think is it sufficient to solve python tasks in this way or is it always better for building algorithms to avoid using such a frequent use of deepcopy?

14

deepcopy is just a function. It would be more helpful to available runtime complexity and memory cost of an approach rather than the specific method calls used.

In terms of the actual deepcopy use, it does seem like it is being used as awful lot. Without analyzing things closely, I do wonder if it’s actually needed as much as it is being used.

15

Ok, thank you.