Get dependencies Ids Algorithm

Question

I have this problem and I came out with a solution but what is the best way to solve this problem ? Thank you in advance.

Given an array of strings and an array of tasks you need to return a sorted array with tasks and dependencies tasks ids.

Example:

$inputs = ['A'];

$tasks = [
    ['id' => 1, 'type' => 'A', 'dependencies' => ['B']],
    ['id' => 2, 'type' => 'A', 'dependencies' => ['C']],
    ['id' => 3, 'type' => 'B', 'dependencies' => ['C']],
    ['id' => 4, 'type' => 'C', 'dependencies' => ['A', 'F']],
    ['id' => 5, 'type' => 'D', 'dependencies' => []],
    ['id' => 6, 'type' => 'D', 'dependencies' => ['F']],
    ['id' => 7, 'type' => 'E', 'dependencies' => ['D']],
    ['id' => 8, 'type' => 'F', 'dependencies' => []]
];

Expected output:

[1, 2, 3, 4, 8]

// Comments.
Id 1 of tasks['type'] = A  - [1]
Id 2 of tasks['type'] = A  - [1, 2]

Tasks id 1 has dependencies B then 
Id 3 of tasks['type'] = B  - [1, 2, 3]

Tasks id 3 has dependencies C then 
Id 4 of tasks['type'] = C  - [1, 2, 3, 4]

Tasks id 4 has dependencies A and F. Take F then 
Id 8 of tasks['type'] = F  - [1, 2, 3, 4, 8]

So far this is the solution I built, but I would like to know if I am in the right path.

print_r(getId($inputs, $tasks));

function getId($inputs, $tasks){
    $id   = [];
    $deps = [];
    $values = [];
    $result = [];

    foreach($inputs as $input){
        foreach($tasks as $task){
            if ($task['type'] == $input){
                $result[$task['id']] = $task['id'];

                foreach($task['dependencies'] as $dependencies){
                    if($dependencies != $input){
                        $deps[] = $dependencies;
                    }
                }
            }
            else
            {
                $values[$task['type']]['id'][] = $task['id'];
                $values[$task['type']]['deps'] = $task['dependencies'];
            }
        }

        foreach($deps as $d){
            if(count($values[$d]['deps']) > 0)
            {
                foreach($values[$d]['deps'] as $nDeps)
                {
                    if($nDeps != $input){
                        $result[] = $values[$nDeps]['id'];
                    }
                }
            }
        }
    }

    foreach( $result as $res){
        if (is_array($res)){
            foreach( $res as $r){
                $id[] = $r;
            }
        }
        else {
            $id[] = $res;
        }
    }

    return array_unique($id);
}

Your current solution doesn't print 3. Besides, the code is pretty verbose. There is scope to make it more concise. — mighty_dev
– mighty_dev, Commented Apr 22, 2021 at 19:03
Thank you for the comments nice_dev, I thought the same thing when finished but I don't know how to implemented. — Yiu Shong
– Yiu Shong, Commented Apr 22, 2021 at 19:15
Could you test this? sandbox.onlinephpfunctions.com/code/… — mighty_dev
– mighty_dev, Commented Apr 22, 2021 at 19:33

mighty_dev · Accepted Answer · 2021-04-23 10:56:09Z

Full Snippet:

<?php

function getId($inputs, $tasks){
   $types = [];
   $dependencies = [];
   foreach($tasks as $task){
       $types[$task['type']] =  $types[$task['type']] ?? [];
       $dependencies[$task['type']] = $dependencies[$task['type']] ?? [];
       $types[$task['type']][] = $task['id'];
       $dependencies[$task['type']] = array_unique(array_merge($dependencies[$task['type']],$task['dependencies']));
   }
   
   $res = [];
   $vis = [];
   foreach($inputs as $in){
       $queue = [];
       foreach($types[$in] as $id){
           if(!isset($vis[$id])){
               $vis[$id] = true;
               $queue[] = [$id , $in];
           }
       }
       while(count($queue) > 0){
           $d = array_shift($queue);
           $res[] = $d[0];
           $vis[$d[0]] = true;
           $type = $d[1];
           foreach($dependencies[$type] as $de_type){
               foreach($types[$de_type] as $id){
                   if(!isset($vis[$id])){
                       $vis[$id] = true;
                       $queue[] = [$id , $de_type];
                   }
               }
           }
       }
   }
   
   sort($res);
   return $res;
}

Step 1 : Dependency and type maps:

foreach($tasks as $task){
       $types[$task['type']] =  $types[$task['type']] ?? [];
       $dependencies[$task['type']] = $dependencies[$task['type']] ?? [];
       $types[$task['type']][] = $task['id'];
       $dependencies[$task['type']] = array_unique(array_merge($dependencies[$task['type']],$task['dependencies']));
}

Collect all types of tasks according to their type. This will be helpful in accumulating all tasks of a particular type.
Create a dependency map(associative array) as well by collecting all dependencies for a particular type. This involves merging of all tasks' dependencies which have the same type.

Step 2: Add those tasks whose types are requested in $inputs

$queue = [];
foreach($types[$in] as $id){
   if(!isset($vis[$id])){
       $vis[$id] = true;
       $queue[] = [$id , $in];
   }
}

The above snippet is to just add nodes/tasks in the queue(only those who haven't been added before)

Step 3: Loop over all dependencies

while(count($queue) > 0){
     $d = array_shift($queue);
     $res[] = $d[0];
     $vis[$d[0]] = true;
     $type = $d[1];
     foreach($dependencies[$type] as $de_type){
         foreach($types[$de_type] as $id){
             if(!isset($vis[$id])){
                 $vis[$id] = true;
                 $queue[] = [$id , $de_type];
             }
         }
     }
 }

Above snippet loops over each tasks one by one popping them out from the queue. Once a task is popped out, we loop over all it's type dependencies. The inner loop loops over those tasks which have the current type in iteration. This way, the whole dependency graph is visited and appended.

Collectives™ on Stack Overflow

Get dependencies Ids Algorithm

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related