| 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 |
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
Feb 14, 2012
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
With the above unit test, the actual value being returned is... 1 2 4 3 5
Feb 14, 2012
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
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
Re-wrote binHeapRemoveFirst. All unit tests now passing... TestPFD.py .................... ---------------------------------------------------------------------- Ran 20 tests in 0.004s OK
Feb 14, 2012
Also passes acceptance tests.
Feb 14, 2012
(No comment was entered for this change.)
Status:
Fixed
|