+U Maxout!

Recursive Depth-First-Search with a tracking Set

Posted on In , Disqus:

Inspired by a StackOverflow(SOF) question, this post is a refreshment on DFS and key points to take care before coding a recursive DFS.

The Problem Statement

I have the following lists: Animals Food Cat Fish Dog Pork Beef I would like to allocate food to the animals in as many different ways as possible like:

Each different animal and food combination will be stored in a map.

(Cat eats Fish, Dog eats Pork)

(Cat eats Fish, Dog eats Beef)

(Cat eats Pork, Dog eats Fish)

(Cat eats Pork, Dog eats Beef)

(Cat eats Beef, Dog eats Fish)

(Cat eats Beef, Dog eats Pork)

Finally all the maps will be put in a set and returned. I am trying to use recursive function for the same and the following is how I tried it.. but am not able to get it right it right, so please help me to make it.

It intends to keep the method fingerprint ("will return Set object") and the incomplete code has no global tracking table as usual.

The method fingerprint provide by problem statement.

private static Set<Map<Animal, Food>> eats(List<Animal> animal, List<Food> food);

The original SFO link is http://stackoverflow.com/questions/43702227/java-recursive-food-allocation/43719930#43719930

Solution and Description

Solution Codes

DFS: Depth First Search. For DFS, we define the machine friendly rephrasing of problem space and lunch the search until termination condition is satisfied.

import java.util.*;
import java.util.stream.Collectors;

public class SFO_Recursive {
    public enum Animal {
        CAT, DOG ;
    }
    public enum Food {
        FISH, BEEF, PORK ;
    }

    private static Set<Map<Animal, Food>> eats(List<Animal> animal, List<Food> food) {
        Set<Map<Animal,Food>> fleet = new HashSet();
        for (Animal a: animal){
            for (Food f: food){
                // Take a step with (a, f)
                List<Food> food_left = food.stream().filter(x -> !x.equals(f)).collect(Collectors.toList());
                List<Animal> animal_left = animal.stream().filter(x -> !x.equals(a)).collect(Collectors.toList());
                if (animal_left.isEmpty() || food_left.isEmpty()){
                    // Terminal state
                    fleet.add(new HashMap<Animal, Food>(){{put(a,f);}});
                }else {
                    eats(animal_left, food_left).stream().forEach(s -> {s.put(a, f); fleet.add(s); });
                }
            }
        }
        return fleet;
    }

    public static void main(String[] args){
        SFO_Recursive.eats(
            Arrays.asList(Animal.CAT, Animal.DOG),
            Arrays.asList(Food.BEEF, Food.FISH, Food.PORK)
        ).stream().forEach(System.out::println);
    }
}

The output of above codes: 

{CAT=BEEF, DOG=PORK}
{CAT=PORK, DOG=BEEF}
{CAT=BEEF, DOG=FISH}
{CAT=FISH, DOG=BEEF}
{CAT=FISH, DOG=PORK}
{CAT=PORK, DOG=FISH}

Key Points in DFS before Coding

In worst case, the time complexity is \(O(|V| + |E|)\). V and E are vertex and edge sets. For recursive Depth-First-Search coding, besides the initial state and problem space representation, there are two key things to take care (before starting programming):

  • Terminal State Evaluation
    • Test condition to determine whether current state is a temrinal one
    • Any additional tests to judge if it is an effective result to retrun
    • How to pack up the data to return
  • The reduce step: How to apply current step to a partial result from (future) terminal state(s)
    • Let's assume the rest data are already processed by future states and we have time machine to get back to "now"
    • Here the key is to add (animal, food) pair into an existing Set
      • For each element of Set, the new pair can be appended into the element (Map)
      • The hashCode algorithms of Map, Map Entries are reliable to directly add new pair without additional restriction check.

If we have to keep the method fingerprint to return Set with inputs of two Lists. The terminal condition is the obvious empty list in either parameter to stop the search. To apply current step to a Set, we can loop all the Maps and just add the combination of new Animal obj and new Food obj to each one but rely on Set class to check whether unique Map is added. Without global tracking table, we can remove consumed elements from Animal and Food Lists to send the information to next state.

About Java hashCode() Algorithms

Java test equality, "==", by hashCode(). Map calculate hashCode as \(\sum{_{k,v\ in\ map}} (hashCode(k)\) ^ \(hashCode(v))\). Every enum value has an unique hashCode by default. Therefore, it is okay to directly add Map elements.

The simplified formula in other format: Map.hashCode() = \(\sum (entry.key.hashCode()\) ^ \(entry.val.hashCode())\)

Another Example from SFO

I confess the AI of SFO is effective as I recommend another DFS algorithm related topic. The original question on codereview.stackexchange.com is on Link.

It is about to walk full paths from a start directory and search for files only with restrictions of min and max Depth.

In this problem, the original code has mixed min depth check and max depth. Usually DFS check the max depth at first of code block, because it is (part of) Terminal State test. The recursion needs to know whether to terminate current approach direction at beginning for most cases. In other words, first sub-problem is whether to cut this search branch.

With a simple correction, here is the working program. Change happens in 3rd line.

def atDirList4(startDir, maxDepth=sys.maxsize, minDepth=0, curDepth=0):
    ret = []
    if curDepth < maxDepth:
        for item in os.listdir(startDir):
            fullItem = os.path.join(startDir, item)
            try:
                if os.path.isfile(fullItem) and curDepth >= minDepth:
                    ret.append(fullItem)
                elif os.path.isdir(fullItem) and curDepth + 1 <= maxDepth:
                    ret.extend(atDirList4(fullItem, maxDepth, minDepth, curDepth + 1))
            except OSError:
                continue
    return ret

References

My original answer on StackOverflow: http://stackoverflow.com/a/43719930/230100

DFS Definition on Wikipedia: https://en.wikipedia.org/wiki/Depth-first_search

Change Log

  • May 18, 2017: render equations with MaxthJax format.
  • May 03, 2017: add Python DFS example.