Generating balls and box combinations depending on set rules

Question

I am working on a project in which I have three box (as of now) and each box will have some color of balls, so I am storing the input in a Map of String and List of String as shown below:

Map<String, List<String>> boxBallMap = new LinkedHashMap<String, List<String>>();

Data in the above map can be like this. Below is one possible input combination and each box won't have same color balls, so two blues is not possible in box1 as an input:

{box1=[blue, red, orange]}
{box2=[blue, red, orange]}
{box3=[blue, red, orange]}

Basis on the above input, I need to return a mapping which will be List<Map<String, String>>, so for above input below mapping would be returned as an output (this is one possible output combination which follows the below rules):

[{box1=blue, box2=red, box3=orange}, 
{box1=red, box2=orange, box3=blue}, 
{box1=orange, box2=blue, box3=red}]

Some rules:

1. In each row, boxes should have an alternate colors of ball. If you see above, each row has an alternate color of balls for each box - meaning blue for box1, red for box2, orange for box3 in the first row.

2. I cannot have same color of balls in each row, so the below combination is not possible as it has same color of balls for two boxes in one row:

   {box1=blue, box2=blue, box3=orange}
   

3. In the next row, I won't use those balls for the box which have been used in the earlier rows, so the second row cannot have blue for box1 as it was already used in the first row by box1.

Below is the code I have so far which works fine on some input combinations but somehow doesn't work on some of the input combinations:

public static List<Map<String, String>> generateMappings(Map<String, List<String>> input) {
    List<Map<String, String>> output = new ArrayList<Map<String, String>>();
    // find all boxes
    List<String> boxes = new ArrayList<String>(input.keySet());

    // find all colors
    Set<String> distinctColors = new LinkedHashSet<String>();
    for(List<String> e : input.values()) {
        for(String color : e) {
            if(! distinctColors.contains(color)) {
                distinctColors.add(color);  
            }
        }
    }
    List<String> colors = new ArrayList<String>(distinctColors);

    int colorIndex = 0;
    for(int i = 0; i < colors.size(); i++) {
        Map<String, String> row = new LinkedHashMap<String, String>();
        output.add(row);
        colorIndex = i;
        for(int j = 0; j < colors.size(); j++) {
            int boxIndex = j;
            if(boxIndex >= boxes.size()) {
                boxIndex = 0;
            }
            String box = boxes.get(boxIndex);
            List<String> boxColors = input.get(box);
            if(colorIndex >= colors.size()) {
                colorIndex = 0;
            }
            String color = colors.get(colorIndex++);
            // a combination is generated only if the actual
            // colors does exist in the actual box
            if(boxColors.contains(color)) {
                row.put(box, color);    
            }
        }
    }

    return output;
}

Sample Unit Test

Map<String, List<String>> input = new LinkedHashMap<>();
input.put("box1", Arrays.asList("blue", "red", "orange"));
input.put("box2", Arrays.asList("blue", "red", "orange"));
input.put("box3", Arrays.asList("blue", "red", "orange"));

List<Map<String, String>> output = create(input);
for(Map<String, String> e : output) {
    System.out.println(e);  
}

And

Map<String, List<String>> input = new LinkedHashMap<>();
input.put("box1", Arrays.asList("blue", "red", "orange"));
input.put("box2", Arrays.asList("blue", "red", "orange"));
input.put("box3", Collections.<String>emptyList());

List<Map<String, String>> output = create(input);
for(Map<String, String> e : output) {
    System.out.println(e);  
}

And

Map<String, List<String>> input = new LinkedHashMap<>();
input.put("box1", Arrays.asList("blue", "red", "orange"));
input.put("box2", Arrays.asList("blue", "red"));
input.put("box3", Arrays.asList("blue", "red", "orange"));

List<Map<String, String>> output = create(input);
for(Map<String, String> e : output) {
    System.out.println(e);  
}

Is there any better way of solving this algorithm?

Answer 1

First of all, save some manual checking work and make your test self-checking with JUnit and Google Guava:

import static com.google.common.collect.Lists.newArrayList;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
import com.google.common.collect.ImmutableMap;

...

@Test
public void test1() {
    final Map<String, List<String>> input = new LinkedHashMap<>();
    input.put("box1", Arrays.asList("blue", "red", "orange"));
    input.put("box2", Arrays.asList("blue", "red", "orange"));
    input.put("box3", Arrays.asList("blue", "red", "orange"));

    final List<Map<String, String>> output = Generator.generateMappings(input);

    final List<Map<String, String>> expected = newArrayList();
    expected.add(ImmutableMap.of("box1", "blue", "box2", "red", "box3", "orange"));
    expected.add(ImmutableMap.of("box1", "red", "box2", "orange", "box3", "blue"));
    expected.add(ImmutableMap.of("box1", "orange", "box2", "blue", "box3", "red"));

    assertEquals(expected, output);
}

@Test
public void test2() throws Exception {
    final Map<String, List<String>> input = new LinkedHashMap<>();
    input.put("box1", Arrays.asList("blue", "red", "orange"));
    input.put("box2", Arrays.asList("blue", "red", "orange"));
    input.put("box3", Collections.<String> emptyList());

    final List<Map<String, String>> output = Generator.generateMappings(input);

    final List<Map<String, String>> expected = newArrayList();
    expected.add(ImmutableMap.of("box1", "blue", "box2", "red"));
    expected.add(ImmutableMap.of("box1", "red", "box2", "orange"));
    expected.add(ImmutableMap.of("box1", "orange", "box2", "blue"));

    assertEquals(expected, output);
}

@Test
public void test3() throws Exception {
    final Map<String, List<String>> input = new LinkedHashMap<>();
    input.put("box1", Arrays.asList("blue", "red", "orange"));
    input.put("box2", Arrays.asList("blue", "red"));
    input.put("box3", Arrays.asList("blue", "red", "orange"));

    final List<Map<String, String>> output = Generator.generateMappings(input);

    final List<Map<String, String>> expected = newArrayList();
    expected.add(ImmutableMap.of("box1", "blue", "box2", "red", "box3", "orange"));
    expected.add(ImmutableMap.of("box1", "red", "box3", "blue"));
    expected.add(ImmutableMap.of("box1", "orange", "box2", "blue", "box3", "red"));

    assertEquals(expected, output);
}

Then make it a little bit more readable with extracted out methods and new* factory methods:

import static com.google.common.collect.Lists.newArrayList;
import static com.google.common.collect.Maps.newLinkedHashMap;

...

public static List<Map<String, String>> generateMappings(
        Map<String, List<String>> input) {
    final List<Map<String, String>> output = newArrayList();
    final List<String> boxes = getAllBoxes(input);
    final List<String> colors = getAllColors(input);

    int colorIndex = 0;
    for (int i = 0; i < colors.size(); i++) {
        ...
    }
    return output;
}

private static List<String> getAllBoxes(
        Map<String, List<String>> input) {
    return newArrayList(input.keySet());
}

private static List<String> getAllColors(
        Map<String, List<String>> input) {
    final Set<String> distinctColors = new LinkedHashSet<String>();
    for (final List<String> e: input.values()) {
        for (final String color: e) {
            if (!distinctColors.contains(color)) {
                distinctColors.add(color);
            }
        }
    }
    final List<String> colors = newArrayList(distinctColors);
    return colors;
}

Note that it made the comments superfluous so I removed them.

I don't completely understand the requirements nor the code but maybe I'm just too tired. Anyway, I'd suggest you another approach: Generate every possible row (invalid ones too) and decide with one or more Rule classes whether a row is valid or not.

Pseudocode:

public interface Rule {
    boolean isValidRow(row, acceptedRows);
}

public class AndRule implements Rule {
    List<Rule> rules;

    public AndRule(Rule rules...) {
        this.rules = newArrayList(rules);
    }

    public boolean isValidRow(row, acceptedRows) {
        for (Rule rule: rules) {
            if (!rule.isValidRow(row, acceptedRows)) {
                return false;
            }
        }
        return true;
    }
}

Usage:

Rule mainRule = new AndRule(rule1, rule2, rule3);

List<Map<String, String>> output = newArrayList();
// maybe you need nested loops here, but an Iterator would be better
for (...) { 
    Map<String, String> row = createNextRow(...);
    if (mainRule.isValidRow(row, output)) {
        output.add(row);
    }
}