4
\$\begingroup\$

I came through a question on Stack Overflow, which shows this array structure:

array (size=4)
  0 => 
    array (size=3)
      'id' => int 1
      'name' => string 'Anniversary' (length=11)
      'parent' => int 0
  1 => 
    array (size=3)
      'id' => int 12
      'name' => string 'New arrives' (length=11)
      'parent' => int 1
  2 => 
    array (size=3)
      'id' => int 13
      'name' => string 'Discount' (length=8)
      'parent' => int 12
  3 => 
    array (size=3)
      'id' => int 6
      'name' => string 'Birthday' (length=8)
      'parent' => int 0

and the required outcome needs to be the path for that list like shown below, implementation of adjacency list:

13 - Anniversary->New arrives->Discount
12 - Anniversary->New arrives
1 - Anniversary
6 - Birthday

I came to this solution:

$in = [
    ['id'=>1, 'name'=>'Anniversary', 'parent'=>0],
    ['id'=>12, 'name'=>'New arrives', 'parent'=>1],
    ['id'=>13, 'name'=>'Discount', 'parent'=>12 ],
    ['id'=>6, 'name'=>'Birthday', 'parent'=>0 ]
];  

function path($element, $input) {
    $return = $input[ array_search($element, array_column($input, 'id')) ];
    $str [] = $return ['name'];
    if($return ['parent'] != 0) {
        $str [] = path($return ['parent'], $input);
    }
    return implode('->', array_reverse($str));
}

var_dump(path(13,$in));

It gets the task done, but I want to know if any improvements can be made to optimize the approach to the problem.

\$\endgroup\$
  • 2
    \$\begingroup\$ That's some of the cleanest PHP I've ever seen, well done! \$\endgroup\$ – Phrancis Jun 25 '15 at 17:29
  • 1
    \$\begingroup\$ Maybe using the SPLDoubly linkedlist might help speed. Not sure. Just a brain bubble. php.net/manual/en/spl.datastructures.php \$\endgroup\$ – Pinoniq Jun 26 '15 at 21:50
2
\$\begingroup\$

Miscellaneous

The only thing that I could think of as general principle, since the code is pretty good, is that you don't test your inputs. What if the input array is empty ? What if the id does not match any id of the array ? If you want the code to be perfect, you need to test those cases.

One small other thing, the name of your variables could be a little bit more explicit. For example, return could be replaced by currentElement, str by elementNames etc etc.

Performance

Concerning performance, there's not a lot to optimize, though there's one thing you could avoid doing each time you enter into your function : getting the array of ids. I would define the function like this function path($element, $input, $ids = array()) . You will have to look if this array is empty (which should correspond to the first call), and if so, initialize it with array_column . You then perform your search as you did, get the next element (if it exists) and delete it from the array of ids before calling your function again. The advantages are : you don't have to compute the array of ids at each function call and since you delete the ids as you progress through your list, the search space gets smaller and smaller, making the final function calls pretty fast.

\$\endgroup\$
  • \$\begingroup\$ yes, you are absolutely right about making an array of $ids. Really helpful, i appreciate it \$\endgroup\$ – Viral Jun 30 '15 at 19:27
  • \$\begingroup\$ mind having a look here ? \$\endgroup\$ – Viral Jun 30 '15 at 21:12
3
\$\begingroup\$

Your code is really good, so there's not much to improve on, that I can see, but nonetheless:


You shouldn't have whitespace before, or inside your brackets unless required:

   $return = $input[ array_search($element, array_column($input, 'id')) ];
                    ^                                                  ^
   $str [] = $return ['name'];
       ^            ^
   if($return ['parent'] != 0) {
             ^
       $str [] = path($return ['parent'], $input);
           ^                 ^

All these lines above have unnecessary whitespace, however the line below is missing whitespace after the comma in path().

var_dump(path(13,$in));
                 ^

You really ought not to name your variables $return or $str, because the first is a system keyword, and the second is undescriptive & possibly confusing as it's really an array, not a string.


The implode string -> could also be -> with an extra space, or even a unicode long (or not long) rightwards arrow: , along with the extra space, visually output would be more readable, and better looking.

13 - Anniversary -> New arrives -> Discount // With added space
13 - Anniversary ⟶ New arrives ⟶ Discount // With added space and long rightwards arrow
\$\endgroup\$
  • \$\begingroup\$ arrow looks handsome, thanks, i appreciate your effort :) \$\endgroup\$ – Viral Jun 30 '15 at 19:16
  • \$\begingroup\$ mind having a look here ? \$\endgroup\$ – Viral Jun 30 '15 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.