My favorites | Sign in
Project Home Wiki Issues Source
READ-ONLY: This project has been archived. For more information see this post.
Search
for
  Advanced search   Search tips   Subscriptions
Issue 12: After implementing binary heap, acceptance tests no longer pass
1 person starred this issue and may be notified of changes. Back to list
Status:  Fixed
Owner:  J.Wes.Pickens
Closed:  Feb 2012


 
Project Member Reported by J.Wes.Pickens, Feb 14, 2012
The most obvious example is as follows...

input:

50 0

expected output:

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

actual output:

1 2 4 8 16 32 33 17 34 35 9 18 36 37 19 38 39 41 44 45 3 6 12 24 25 13 26 27 23 22 21 20 29 30 46 5 15 14 28 31 11 40 42 48 7 43 10 49 47 50
Feb 14, 2012
Project Member #1 J.Wes.Pickens
My initial suspicion is that the binary heap is not always keeping the lowest value at the root as it should be.
Feb 14, 2012
Project Member #2 J.Wes.Pickens
The failure is indicated by the following unit test...

        def test_solve3 (self) :
                r = StringIO.StringIO("5 0\n")
                w = StringIO.StringIO()
                pfd_solve(r, w)
                self.assert_(w.getvalue() == "1 2 3 4 5\n")

...which fails with the following...

FAIL: test_solve3 (__main__.TestPFD)
-------------------------------------------------
Traceback (most recent call last):
  File "TestPFD.py", line 176, in test_solve3
    self.assert_(w.getvalue() == "1 2 3 4 5\n")
AssertionError: False is not true
Status: Started
Feb 14, 2012
Project Member #3 J.Wes.Pickens
With the above unit test, the actual value being returned is...

1 2 4 3 5

Feb 14, 2012
Project Member #4 J.Wes.Pickens
It looks like it's a problem with the binHeapRemoveFirst function.

The noDependencies list starts out correct...

[1, 2, 3, 4, 5]

Then, after removing 1...

[2, 4, 3, 5]

...which is okay, but then after removing 2...

[4, 5, 3]

Clearly, 3 did not move to the root as it should have.  Then after removing 4...

[3, 5]

It's okay now, but the damage has already been done since 4 came out before 3.

Feb 14, 2012
Project Member #5 J.Wes.Pickens
I think my down-heap algorithm still isn't correct.  I'm swapping with the first child I find which is lower, but I should be swapping with the lowest child.
Feb 14, 2012
Project Member #6 J.Wes.Pickens
Re-wrote binHeapRemoveFirst.  All unit tests now passing...

TestPFD.py
....................
----------------------------------------------------------------------
Ran 20 tests in 0.004s

OK

Feb 14, 2012
Project Member #7 J.Wes.Pickens
Also passes acceptance tests.
Feb 14, 2012
Project Member #8 J.Wes.Pickens
(No comment was entered for this change.)
Status: Fixed

Powered by Google Project Hosting