Find potentional sponsor for every animal

Question

This is a programming challenge in Czeck. My translation follows.

Does anyone know what the time complexity of my code is?

Input: The first line contains 2 integers: the number of animals 1 ≤N ≤100 and the number of their potential sponsors 1 ≤M ≤200. The following are N lines with information about each animal: the unique integer ID of the nth animal 0 ≤In <N and its one-word name. Animal names are also unique. Behind them are M lines with information about potential sponsors. Each line begins with the first name of the m-th sponsor and the number of animals 1 ≤Pm≤N, one of which is one willing to sponsor. The Pm ID of these animals follows. The first name of each sponsor is always unique.

Output: On the first line, write Yes, if all the animals find a sponsor, No otherwise. For all the animals for which you have found a sponsor, write the name of the animal on a separate line and the name of his sponsor separated by a space. Sort the rows in ascending alphabetical order by name animal. The task can have more than one correct solution, write any of them.

Example:

input:

7 8
1 cow
0 elephant
3 pig
2 gorilla
5 rhinoceros
6 tapir
4 kangaroo
Celestin 3 0 1 3
Hubert 2 4 5
Emma 2 4 6
Felix 1 6
Bert 4 0 1 2 6
Anna 5 0 2 3 4 5
Denis 1 6
Gustav 1 6

Output:

No
gorilla Bert
kangaroo Emma
elephant Celestina
pig Anna
rhinoceros Hubert
tapir Felix

Code:

import java.util.*;

class Animals
{
    //S is number of sponsors, A is number of animals 
    static int S = 0;
    static int A = 0;
 
    //DFS
    boolean bpm(boolean bpGraph[][], int u, boolean seen[], int matchR[]){
        for (int v = 0; v < A; v++){
            //does the sponsor want to sponsor this animal?
            if (bpGraph[u][v] && !seen[v])
            {
                seen[v] = true;
                if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR)){
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
 
    // returns an array of which sponsor sponsors what animal
    int[] maxBPM(boolean bpGraph[][])
    {
        int matchR[] = new int[A];
 
        for(int i = 0; i < A; ++i)
            matchR[i] = -1;
 
        for (int a = 0; a < S; a++){
            //indicate that no animal have been seen yet
            boolean seen[] =new boolean[A];
            for(int i = 0; i < A; ++i)
                seen[i] = false;
 
            //find if animal "a" can get sponsor
            bpm(bpGraph, a, seen, matchR);
        }
        return matchR;
    }
 
    public static void main (String[] args){
        //input
        Scanner scn = new Scanner(System.in);
        List<Animal> animalsID = new ArrayList<>();
        System.out.println("Input: ");

        A = scn.nextInt();
        S = scn.nextInt();
        scn.nextLine();

        boolean bpGraph[][] = new boolean[S][A];
        
        //load animals
        for (int i = 0; i < A; i++) { 
            int id = scn.nextInt();
            String name = scn.next();
            scn.nextLine();
            animalsID.add(new Animal(id, name));
        }

        //load sponsors
        String namesSponsors[] = new String[S];
        for (int i = 0; i < S; i++) {
            namesSponsors[i] = scn.next();
            int numberCanSponsor = scn.nextInt();
            for (int j = 0; j < numberCanSponsor; j++) {
                bpGraph[i][scn.nextInt()] = true;
            }
            scn.nextLine();
        }

        //BPM
        Animals a = new Animals();
        int[] result = a.maxBPM(bpGraph);

        //output
        System.out.println("\Output:");
        boolean allAnimalsAreSponsored = true;
        for (int i : result) {
            if (i == -1){
                allAnimalsAreSponsored = false;
            }
        }
        
        if (allAnimalsAreSponsored){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }

        for (int i = 0; i < A; i++) {
            if (result[i] != -1){
                for (Animal animal : animalsID) {
                    if (animal.getId() == i) {
                        System.out.print(animal.getName() + " ");
                    }
                }

                System.out.println(namesSponsors[result[i]]);
            }
        }
    }
}

public class Animal {
    private int id;
    private String name;

    Animal(int id, String name){
        this.id = id;
        this.name = name;
    }

    int getId(){
        return id;
    }

    String getName(){
        return name;
    }
}

I'm a beginner, so the code looks awful. But I tried to make some comments.

Do you have any suggestions on how to simplify the script?

Answer 1

My Java is rusty so I spent (a lot of!) time brushing up on some OpenJDK 16 topics. Starting with your existing program,

• Animals is not really a good representation of a class. It's non-reentrant, since S and A are statics, so it will be difficult to test.
• Your variable names S, A, v, u etc. are very difficult to understand and shouldn't be so abbreviated. Prefer instead something like nSponsors etc.
• If I understand your algorithm correctly, you're assuming that the animal IDs are contiguous integers starting at 0. This does seem to be guaranteed by the specification but you haven't included it in your translation.
• You have a class for Animal but not for Sponsor - this seems inconsistent.
• Overall your main does way too much, and needs to be split out into multiple separate methods and classes.
• There are some places where this program can make use of Java streams - for example, you can write a parser for animals like

    private static final Collector<Animal, ?, Map<Integer, Animal>>
        mapCollector = Collectors.toUnmodifiableMap(v -> v.id, v -> v);

    public static Map<Integer, Animal> parseAll(Scanner in, int n) {
        /* Parse n animals from n lines of the input stream.
           Validate that each line is well-formed and that the IDs are unique.
         */
        return Stream
            .generate(() -> parse(in))
            .limit(n)
            .collect(mapCollector);
    }

and so on.

• Add some Jupiter unit tests. This program should be testable and tested and it doesn't currently seem like either is true.
• It will be a challenge, but I encourage you to attempt a custom Spliterator implementation of your algorithm. Spliterators are a simple but powerful concept - choose an algorithm that can be segmented, and then tell Java how to segment it and let it run on multiple cores. The basic class signature can look like

public class Solver implements Spliterator<Solution> {
    protected final List<List<Sponsor>> sponsorOptions;

    @Override
    public int characteristics() {
        return DISTINCT | NONNULL | IMMUTABLE;
    }

    @Override
    public long estimateSize() {
        /* For each animal: combinations with no repetition, with some
           simplifying assumptions like: All sponsors are available for
           selection at a given animal, regardless of previous selections.
           This is an upper bound.
         */
        long upper = sponsorOptions.stream()
            .mapToLong(Collection::size)
            .reduce(1, (x, y) -> x*y);
        return upper;
    }

    @Override
    public boolean tryAdvance(Consumer<? super Solution> consumer) {
        // Call consumer() with the next possible solution value and return true
    }

    @Override
    public Spliterator<Solution> trySplit() {
        // Reduce the search space of this instance by half, and return the second half in a new instance of this class
    }
}

When I used your sample input problem and wrote a (brute-force, not Ford-Fulkerson) implementation, it shows how the Java reference StreamSupport segments your search space:

Split at depth 0, 4 -> 2, 2
Split at depth 0, 2 -> 1, 1
Split at depth 0, 2 -> 1, 1
Split at depth 1, 3 -> 1, 2
Split at depth 1, 3 -> 1, 2
Split at depth 1, 3 -> 1, 2
Split at depth 2, 3 -> 1, 2
Split at depth 1, 3 -> 1, 2
Split at depth 2, 3 -> 1, 2
Split at depth 1, 2 -> 1, 1
Split at depth 1, 2 -> 1, 1
Split at depth 1, 2 -> 1, 1
Split at depth 2, 3 -> 1, 2
Split at depth 2, 2 -> 1, 1
Split at depth 2, 3 -> 1, 2
Split at depth 2, 3 -> 1, 2
Split at depth 2, 2 -> 1, 1
Split at depth 2, 2 -> 1, 1
Split at depth 2, 2 -> 1, 1
Split at depth 2, 3 -> 1, 2
Split at depth 2, 2 -> 1, 1
Split at depth 2, 2 -> 1, 1
Split at depth 2, 3 -> 1, 2
Split at depth 2, 2 -> 1, 1
Split at depth 2, 3 -> 1, 2
Split at depth 2, 3 -> 1, 2
Split at depth 2, 2 -> 1, 1
Split at depth 2, 2 -> 1, 1
Split at depth 1, 2 -> 1, 1
Split at depth 2, 3 -> 1, 2
Split at depth 2, 3 -> 1, 2
Split at depth 2, 2 -> 1, 1
Split at depth 2, 3 -> 1, 2
Split at depth 2, 2 -> 1, 1
Split at depth 2, 2 -> 1, 1
Split at depth 3, 3 -> 1, 2
Split at depth 4, 4 -> 2, 2
Split at depth 3, 2 -> 1, 1
Split at depth 4, 2 -> 1, 1
Split at depth 4, 4 -> 2, 2
Split at depth 4, 2 -> 1, 1
Split at depth 5, 3 -> 1, 2
Split at depth 5, 3 -> 1, 2
Split at depth 4, 2 -> 1, 1
Split at depth 5, 2 -> 1, 1
Split at depth 5, 2 -> 1, 1
Split at depth 5, 3 -> 1, 2
Split at depth 5, 2 -> 1, 1
Split at depth 5, 3 -> 1, 2
Split at depth 5, 3 -> 1, 2
Split at depth 4, 4 -> 2, 2
Split at depth 5, 3 -> 1, 2
Split at depth 4, 2 -> 1, 1
Split at depth 5, 2 -> 1, 1
Split at depth 5, 2 -> 1, 1
Split at depth 5, 2 -> 1, 1
Split at depth 4, 2 -> 1, 1
Split at depth 5, 3 -> 1, 2
Split at depth 4, 2 -> 1, 1
Split at depth 5, 3 -> 1, 2
Split at depth 5, 3 -> 1, 2
Split at depth 5, 2 -> 1, 1
Split at depth 5, 2 -> 1, 1
Split at depth 5, 2 -> 1, 1
Split at depth 5, 3 -> 1, 2
Split at depth 5, 2 -> 1, 1
Split at depth 5, 3 -> 1, 2
Split at depth 5, 3 -> 1, 2
Split at depth 5, 2 -> 1, 1
Split at depth 5, 2 -> 1, 1