# Find potentional sponsor for every animal

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++){
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;
}

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];

for (int i = 0; i < A; i++) {
int id = scn.nextInt();
String name = scn.next();
scn.nextLine();
}

for (int i = 0; i < S; i++) {
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:");
for (int i : result) {
if (i == -1){
}
}

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() + " ");
}
}

}
}
}
}

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?

• Welcome to Code Review. Can you include the class Animal, please? Even if very simple, it is better to include the complete code.
– Marc
Oct 26, 2021 at 12:09
• ok, i included the animal class Oct 26, 2021 at 12:35
• The problem description is written in different language. Oct 26, 2021 at 12:36
• This may be of interest.
– vnp
Oct 26, 2021 at 16:21

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> {

@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.
*/
.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