How to reassign values with recursion?

Question

Given a hierarchy (like an outline) where each level is represented by an integer (e.g., the first level is 0, the second level is 1, and at any point you can start a new point at an earlier level), I want to reassign integers so that numbers are not skipped but at the same time respecting the original relationships. I've represented the input as an array:

$stuff = array(0,1,2,2,4,1,9,9,10,3,8,4);

And the desired output (when represented as an array) is:

$stuff = array(0,1,2,2,3,1,2,2,3,2,3,3);

The rules are:

If the given value is the same as the nearest prior value, then the output value should be the same as the nearest prior's output value
If the given value is higher (i.e., deeper) than the nearest prior value, then the output value should be one greater than the nearest prior's output value
If the given value is lower (i.e., shallower) than the nearest prior value, then find the nearest prior value that is less than the given value and the output value should be one greater than that value.

The only way I've thought to do this is through recursion. And I can get it to work for all but the last case in my aforementioned input array. If I change the last case in my input array to a '5' rather than a '4' then it works.

Here is what I am trying:

<?php

$input = array(0,1,2,2,4,1,9,9,10,3,8,4);
$debug = false;
for ($i =0; $i < count($input); $i++) {
    if ($debug) {
        echo '<hr />Old level: '.$input[$i];
        $newLevel = newLevel($input,$i,$input[$i],$debug);
        echo '<br />New level: '.$newLevel.'<br /><br /><br /><hr />';
    }
    else {
        echo 'Old level: '.$input[$i].'; New level: '.newLevel($input,$i,$input[$i],$debug).'<br />';
    }
}

function newLevel($input, $index,$origValue,$debug) {
    if ($index == 0) return 0;
    else {
        if ($input[$index] > $input[$index-1]) {
            if ($debug) echo '<br />Orig value: '.$origValue.' in else/if';
            return newLevel($input,$index-1,$origValue,$debug)+1;
        }
        elseif ($input[$index] == $input[$index-1]) {
            if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif1';
            return newLevel($input,$index-1,$origValue,$debug);
        }
        elseif ($input[$index] < $input[$index-1]) {
            for ($i = $index-2; $i >= 0; $i--) {
                if ($input[$index] == $input[$i]) {
                    if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif2/for/if';
                    return newLevel($input,$i,$origValue,$debug);
                }
                elseif ($input[$index] == ($input[$i] + 1)) {
                    if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif2/for/elseif';
                    return newLevel($input,$i,$origValue,$debug);
                }
            }
                die ("Error with going to outer level -- should never hit this.");
        }
    }
}

?>

This is the output I want:

Old level: 0; New level: 0
Old level: 1; New level: 1
Old level: 2; New level: 2
Old level: 2; New level: 2
Old level: 4; New level: 3
Old level: 1; New level: 1
Old level: 9; New level: 2
Old level: 9; New level: 2
Old level: 10; New level: 3
Old level: 3; New level: 2
Old level: 8; New level: 3
Old level: 4; New level: 3

But the output I am getting has a "2" for the new level of the last line. Any help is greatly appreciated it.

I'm fairly certain the last case can be decomposed to min(prior_new_level, current_old_level) — Stuart Wakefield
– Stuart Wakefield, Commented May 17, 2013 at 23:53

slashingweapon · Accepted Answer · 2013-05-17 23:30:27Z

3

Actually, you don't need recursion at all. You did a good job of explaining your algorithm without using recursion, so your code shouldn't need it either.

Here is my version of your algorithm, without the recursion.

$original = array(0,1,2,2,4,1,9,9,10,3,8,4);
$revised = array();

foreach($original as $index=>$value) {
    $output = 0;
    $previous = false;

    if ($index > 0)
        $previous = $original[$index-1];

    if ($previous === false) 
        $output = 0;
    else if ($value == $previous)
        $output = $revised[$index-1];
    else if ($value > $previous)
        $output = $revised[$index-1] + 1;
    else {
        $output = 1; // worst case scenario
        for($rindex = $index-1; $rindex >= 0; $rindex--) {
            if ($value > $original[$rindex]) {
                $output = $revised[$rindex]+1;
                break;
            }
        }
    }

    $revised[] = $output;
}

echo "\n";
print_r($original);
print_r($revised);

answered May 17, 2013 at 23:30

slashingweapon

11.4k4 gold badges33 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Buttle Butkus Over a year ago

This looks right at first glance. +1 for answering yet another recursion question (although this one isn't really recursion).

user2379780 Over a year ago

+1 for an answer that works. But the reason I wanted to find a recursive solution is that I need to be able to do this in a language that does not allow variables to be reassigned after instantiation (because the language doesn't allow side effects). My plan was to figure this out in PHP because that is my stronger language and then port it to the other language. Best laid plans... If you can help figure out the recursive solution, I'd greatly appreciate it.

slashingweapon Over a year ago

Using recursion doesn't solve your immutability problem. You can only figure out one element of your answer at a time, and you have to either extend an existing array by one, or assign the value to a previously-allocated element. In Java, you might initialize your output array with int[] revised = new int[original.length];, then assign the new values with revised[index] = output;. I guarantee you that every language will have some kind of construct that supports what you need to do here.

user2379780 Over a year ago

Thanks, I will give it a whirl. (I've never had a doubt that there is some way to do this; just having problems figuring it out.) I will also accept your answer. Again, thanks for the help.

Collectives™ on Stack Overflow

How to reassign values with recursion?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related