Main.java

package com.tinymolly;

import java.awt.*;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Rose marker = new Rose(null, Rose.Color.Blue);
        Set<Rose> processed = new HashSet<>();
        Queue<Rose> inProcess = new LinkedList<>();
        int curGen = 1;
        inProcess.add(Rose.RoseMap.get("2001"));
        inProcess.add(Rose.RoseMap.get("0200"));
        inProcess.add(Rose.RoseMap.get("0010"));
        inProcess.add(marker); // this marks the start of next generation.

        Rose blue = Rose.RoseMap.get("2220");
        while (!inProcess.isEmpty() && !processed.contains(blue)) {
            Rose head = inProcess.poll();
            if(head == marker)
            {
                if (!inProcess.isEmpty()) {
                    curGen++;
                    inProcess.add(marker);
                }
            } else {
                processed.add(head);
                for (var rose : processed) {
                    List<Rose> added = rose.cross(head, curGen);
                    inProcess.addAll(added);
                }

//                System.out.println("With rose: " + head);
//                for (var rose : processed) {
//                    System.out.println(rose);
//                }
            }
        }

        for (var rose : processed) {
            System.out.println(rose);
        }
    }

    private static void printInProcess(Queue<Rose> inProcess) {
        for (var item : inProcess) {
            System.out.print(item.gene() + ", ");
        }
        System.out.println("\n");
    }
}

Rose.java

package com.tinymolly;

import java.util.*;

public class Rose {
    public String gene() {
        return this.gene;
    }

    enum Color {
        Red, Yellow, White, Pink, Blue, Orange, Purple, Black
    }

    private static final char C0 = '0';
    private static final char C1 = '1';
    private static final char C2 = '2';

    private static final int COUNT = 4;
    public static final Map<String, Rose> RoseMap = new HashMap<>();

    static {
        initMap();
    }

    private final String gene;
    private final Color color;

    private Rose parent1;
    private Rose parent2;
    private double p;
    private int generation = Integer.MAX_VALUE;

    Rose(String gene, Color color) {
        this.gene = gene;
        this.color = color;
    }

    private Rose(String gene, Color color, int generation, double p) {
        this.gene = gene;
        this.color = color;
        this.generation = generation;
        this.p = p;
    }

    Rose(String gene, Color color, int generation, Rose p1, Rose p2, double p) {
        this.gene = gene;
        this.color = color;
        this.generation = generation;
        this.parent1 = p1;
        this.parent2 = p2;
        this.p = p;
    }

    public boolean update(Rose p1, Rose p2, double p, int generation) {
        if (this.generation < generation ||
                this.generation == generation && this.p >= p) // use the one who has the higher possibility
            return false; // this has already been registered previously
//        if (p < 0.0625) return false; // this has too low chance to cross bread the flower with this path
        this.parent1 = p1;
        this.parent2 = p2;
        this.p = p;
        this.generation = generation;
        return true;
    }

    public List<Rose> cross(Rose another, int generation){
        List<Rose> updated = new ArrayList<>();
        // all results are saved in output.
        List<Tuple<String, Double>> output = new ArrayList<>();
        cross(0, this.gene.toCharArray(), another.gene.toCharArray(), 1, new char[4], output);

        Map<Color, Integer> seen = new HashMap<>();
        // add parents colors into seen color.
        seen.put(this.color, 1);
        seen.put(another.color, 1);

        // add all mix output flower color into seen color.
        for (Tuple<String, Double> item : output) {
            var rose = RoseMap.get(item.x);
            if (seen.containsKey(rose.color)) {
                int count = seen.get(rose.color);
                seen.put(rose.color, count + 1);
            } else {
                seen.put(rose.color, 1);
            }
        }

        for (Tuple<String, Double> item : output) {
            var rose = RoseMap.get(item.x);
            if (seen.getOrDefault(rose.color, 1) == 1) {
                // Only record the one that we can uniquely tell from others in breading
                if (rose.update(this, another, item.y, generation)) updated.add(rose);
            }
        }
        return updated;
    }

    public static void cross(int i, char[] g1, char[] g2, double p, char[] gene, List<Tuple<String, Double>> output) {
        if (i == COUNT) {
            String seq = String.valueOf(gene);
            output.add(new Tuple<>(seq, p));
            return;
        }
        char v1 = g1[i];
        char v2 = g2[i];
        if (v1 == v2) {
            if (v1 == C0 || v1 == C2) {
                // XX * XX or xx * xx
                gene[i] = v1;
                cross(i + 1, g1, g2, p, gene, output);
            } else // Xx * Xx
            {
                gene[i] = C0;
                cross(i + 1, g1, g2, p * 0.25, gene, output);

                gene[i] = C2;
                cross(i + 1, g1, g2, p * 0.25, gene, output);

                gene[i] = C1;
                cross(i + 1, g1, g2, p * 0.5, gene, output);
            }
        } else { // v1 != v2
            if (v1 == C1 || v2 == C1) // Xx * XX or Xx * xx
            {
                gene[i] = v1;
                cross(i + 1, g1, g2, p * 0.5, gene, output);

                gene[i] = v2;
                cross(i + 1, g1, g2, p * 0.5, gene, output);
            } else { // XX * xx
                gene[i] = C1;
                cross(i + 1, g1, g2, p, gene, output);
            }
        }
    }

    public static void initMap() {
        // rr
        RoseMap.put("0000", new Rose("0000", Color.White));
        RoseMap.put("0001", new Rose("0001", Color.White));
        RoseMap.put("0002", new Rose("0002", Color.White));
        RoseMap.put("0010" /*rryyWwss*/, new Rose("0010", Color.White, 0, 1));
        RoseMap.put("0011", new Rose("0011", Color.White));
        RoseMap.put("0012", new Rose("0012", Color.White));
        RoseMap.put("0020", new Rose("0020", Color.Purple));
        RoseMap.put("0021", new Rose("0021", Color.Purple));
        RoseMap.put("0022", new Rose("0022", Color.Purple));

        RoseMap.put("0100", new Rose("0100", Color.Yellow));
        RoseMap.put("0101", new Rose("0101", Color.Yellow));
        RoseMap.put("0102", new Rose("0102", Color.Yellow));
        RoseMap.put("0110", new Rose("0110", Color.White));
        RoseMap.put("0111", new Rose("0111", Color.White));
        RoseMap.put("0112", new Rose("0112", Color.White));
        RoseMap.put("0120", new Rose("0120", Color.Purple));
        RoseMap.put("0121", new Rose("0121", Color.Purple));
        RoseMap.put("0122", new Rose("0122", Color.Purple));

        RoseMap.put("0200" /*rrYYWWss*/, new Rose("0200", Color.Yellow, 0, 1));
        RoseMap.put("0201", new Rose("0201", Color.Yellow));
        RoseMap.put("0202", new Rose("0202", Color.Yellow));
        RoseMap.put("0210", new Rose("0210", Color.Yellow));
        RoseMap.put("0211", new Rose("0211", Color.Yellow));
        RoseMap.put("0212", new Rose("0212", Color.Yellow));
        RoseMap.put("0220", new Rose("0220", Color.White));
        RoseMap.put("0221", new Rose("0221", Color.White));
        RoseMap.put("0222", new Rose("0222", Color.White));

        // Rr
        RoseMap.put("1000", new Rose("1000", Color.Red));
        RoseMap.put("1001", new Rose("1001", Color.Pink));
        RoseMap.put("1002", new Rose("1002", Color.White));
        RoseMap.put("1010", new Rose("1010", Color.Red));
        RoseMap.put("1011", new Rose("1011", Color.Pink));
        RoseMap.put("1012", new Rose("1012", Color.White));
        RoseMap.put("1020", new Rose("1020", Color.Red));
        RoseMap.put("1021", new Rose("1021", Color.Pink));
        RoseMap.put("1022", new Rose("1022", Color.Purple));

        RoseMap.put("1100", new Rose("1100", Color.Orange));
        RoseMap.put("1101", new Rose("1101", Color.Yellow));
        RoseMap.put("1102", new Rose("1102", Color.Yellow));
        RoseMap.put("1110", new Rose("1110", Color.Red));
        RoseMap.put("1111", new Rose("1111", Color.Pink));
        RoseMap.put("1112", new Rose("1112", Color.White));
        RoseMap.put("1120", new Rose("1120", Color.Red));
        RoseMap.put("1121", new Rose("1121", Color.Pink));
        RoseMap.put("1122", new Rose("1122", Color.Purple));

        RoseMap.put("1200", new Rose("1200", Color.Orange));
        RoseMap.put("1201", new Rose("1201", Color.Yellow));
        RoseMap.put("1202", new Rose("1202", Color.Yellow));
        RoseMap.put("1210", new Rose("1210", Color.Orange));
        RoseMap.put("1211", new Rose("1211", Color.Yellow));
        RoseMap.put("1212", new Rose("1212", Color.Yellow));
        RoseMap.put("1220", new Rose("1220", Color.Red));
        RoseMap.put("1221", new Rose("1221", Color.Pink));
        RoseMap.put("1222", new Rose("1222", Color.White));

        // RR
        RoseMap.put("2000", new Rose("2000", Color.Black));
        RoseMap.put("2001" /*RRyyWWSs*/, new Rose("2001", Color.Red, 0, 1));
        RoseMap.put("2002", new Rose("2002", Color.Pink));
        RoseMap.put("2010", new Rose("2010", Color.Black));
        RoseMap.put("2011", new Rose("2011", Color.Red));
        RoseMap.put("2012", new Rose("2012", Color.Pink));
        RoseMap.put("2020", new Rose("2020", Color.Black));
        RoseMap.put("2021", new Rose("2021", Color.Red));
        RoseMap.put("2022", new Rose("2022", Color.Pink));

        RoseMap.put("2100", new Rose("2100", Color.Orange));
        RoseMap.put("2101", new Rose("2101", Color.Orange));
        RoseMap.put("2102", new Rose("2102", Color.Yellow));
        RoseMap.put("2110", new Rose("2110", Color.Red));
        RoseMap.put("2111", new Rose("2111", Color.Red));
        RoseMap.put("2112", new Rose("2112", Color.White));
        RoseMap.put("2120", new Rose("2120", Color.Black));
        RoseMap.put("2121", new Rose("2121", Color.Red));
        RoseMap.put("2122", new Rose("2122", Color.Purple));

        RoseMap.put("2200", new Rose("2200", Color.Orange));
        RoseMap.put("2201", new Rose("2201", Color.Orange));
        RoseMap.put("2202", new Rose("2202", Color.Yellow));
        RoseMap.put("2210", new Rose("2210", Color.Orange));
        RoseMap.put("2211", new Rose("2211", Color.Orange));
        RoseMap.put("2212", new Rose("2212", Color.Yellow));
        RoseMap.put("2220" /*RRYYwwss*/, new Rose("2220", Color.Blue));
        RoseMap.put("2221", new Rose("2221", Color.Red));
        RoseMap.put("2222", new Rose("2222", Color.White));
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Rose rose = (Rose) o;
        return Double.compare(rose.p, p) == 0 &&
                generation == rose.generation &&
                Objects.equals(gene, rose.gene) &&
                color == rose.color &&
                // the order of parents does not matter
                ((Objects.equals(parent1, rose.parent1) && Objects.equals(parent2, rose.parent2)) ||
                        (Objects.equals(parent2, rose.parent1) && Objects.equals(parent1, rose.parent2)));
    }

    @Override
    public int hashCode() {
        return Objects.hash(gene, color, parent1, parent2, p, generation);
    }

    @Override
    public String toString() {
        return "Rose{" +
                "gene='" + gene + '\'' +
                ", color=" + color +
                ", parent1=" + (parent1 == null ? parent1 : parent1.gene) +
                ", parent2=" + (parent2 == null ? parent2 : parent2.gene) +
                ", p=" + p +
                ", generation=" + generation +
                '}';
    }
}

RoseTest.java

package com.tinymolly;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

import static org.junit.jupiter.api.Assertions.*;

class RoseTest {

    @BeforeEach
    public void setup() {
        Rose.initMap();
    }

    @Test
    public void shouldCross() {
        List<Tuple<String, Double>> output = new ArrayList<>();
        Rose.cross(0, "1100".toCharArray(), "2002".toCharArray(), 1, new char[4], output);
        assertEquals(4, output.size());
        assertEquals(new Tuple<>("1101", 0.25), output.get(0));
        assertEquals(new Tuple<>("1001", 0.25), output.get(1));
        assertEquals(new Tuple<>("2101", 0.25), output.get(2));
        assertEquals(new Tuple<>("2001", 0.25), output.get(3));
    }

    @Test
    public void initRedCrossShouldReturnPinkAndBlack() {
        Rose rose = Rose.RoseMap.get("2001");
        rose.cross(rose, 1);

        Rose pink = Rose.RoseMap.get("2002");
        Rose black = Rose.RoseMap.get("2000");
        Rose red = Rose.RoseMap.get("2001");
        assertEquals(new Rose("2002", Rose.Color.Pink, 1, rose, rose, 0.25), pink);
        assertEquals(new Rose("2000", Rose.Color.Black, 1, rose, rose, 0.25), black);
        assertEquals(new Rose("2001", Rose.Color.Red, 0, null, null, 0), red);
    }
}

Tuple.java

package com.tinymolly;

import java.util.Objects;

public class Tuple<X, Y> {
    public final X x;
    public final Y y;
    public Tuple(X x, Y y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "Tuple{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Tuple<?, ?> tuple = (Tuple<?, ?>) o;
        return Objects.equals(x, tuple.x) &&
                Objects.equals(y, tuple.y);
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}