CODEWITHSUNDEEP
recursionpascalfreepascalbacktracking
Jean Francois Clout
Jean Francois Clout

Reputation: 135

Backtracking in Pascal: finding maximal weighted branch

I've been learning Pascal (using the Free Pascal compiler) for a week now, and came across a seemingly easy exercise. Given a structure as shown below, find the maximal weighted branch:

    1
   4 9
  7 0 2
 4 8 6 3

A branch is any sequence of numbers, starting from the top (in this case: 1), when for every number the branch can expand either down-left or down-right. For example, the branch 1-4-0 can expand into either 1-4-0-8 or 1-4-0-6. All branches must start from the top and end at the bottom.

In this example, the maximal branch is 1-4-7-8, which gives us 20. In order to solve this question, I tried to use backtracking. The triangular structure was stored in an array of type 'triangle':

type triangle = array[1..MAX_NUM_OF_ROWS, 1..MAX_NUM_OF_ROWS] of integer;

Here's my implementation: 

function findAux(data: triangle; dim: integer; i: integer; j:integer) : integer;
begin
if i = dim then
    findAux := data[i][j]
else
    if findAux(data, dim, i + 1, j + 1) > findAux(data, dim, i + 1, j) then
        findAux := data[i+1][j+1] + findAux(data, dim, i + 1, j + 1);
    else
        findAux := data[i+1][j] + findAux(data, dim, i + 1, j);
end;

function find_heaviest_path(data: triangle; dim: integer) : integer;
begin
    find_heaviest_path := findAux(data, dim, 1, 1);
end;

As you can see, I've used an auxiliary function. Unfortunately, it doesn't seem to give the right result. For the structure seen above, the result I get is 27, which is 7 points off. What am I missing? How does the implementation look overall? I should add that the maximal number of rows is 100, for this exercise. If clarification is needed, please don't hesitate to ask.

Upvotes: 5

Views: 613

Answers (1)

lurker
lurker

Reputation: 58254

Your findAux is adding the wrong value to the recursively obtained result. As an aside, you can neaten the code a bit using some local variables. A corrected version of findAux:

uses math;

...

function findAux(data: triangle; dim: integer; i: integer; j:integer) : integer;
var
    left, right: integer;
begin
    if i = dim then
        findAux := data[i][j]
    else begin
        left := findAux(data, dim, i + 1, j);
        right := findAux(data, dim, i + 1, j + 1);
        findAux := data[i][j] + Max(left, right);
    end;
end;

Upvotes: 3

Related Questions