It would be great if someone could give me a hint what's wrong in my code.
Furthermore would testdata with a lot authors/papers be helpful.
Code: Select all
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
public class Main
{
static Map<String, Author> authorIdx;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintStream cout = System.out;
StringBuffer sbOut = new StringBuffer();
String line = reader.readLine();
StringTokenizer tokenizer = new StringTokenizer(line);
int numScenarios = Integer.parseInt( tokenizer.nextToken());
for (int i = 0; i < numScenarios; i++)
{
authorIdx = new HashMap<String, Author>();
// Database Size and Name Size
line = reader.readLine();
while (line.trim().length() == 0)
{
line = reader.readLine();
}
tokenizer = new StringTokenizer(line);
int numPapers = Integer.parseInt( tokenizer.nextToken());
int numNames = Integer.parseInt( tokenizer.nextToken());
String[] papers = new String[numPapers];
String[] names = new String[numNames];
// read database
for (int j = 0; j < numPapers; j++)
{
line = reader.readLine();
papers[j] = line;
}
// read names
for (int j = 0; j < numNames; j++)
{
line = reader.readLine();
names[j] = line;
names[j] = trim(line);
createAuthor(names[j]);
}
// Solve it
// 1. Build Author Graph
for (String paper : papers)
{
Collection<String> paperAuthors = splitPaper( paper);
for (String authorName : paperAuthors)
{
Author author = authorIdx.get( authorName);
if (author == null)
{
author = createAuthor(authorName);
} else
{
for (String coAuthorName : paperAuthors)
{
if (!coAuthorName.equals( authorName))
{
Author coAuthor = authorIdx.get( coAuthorName);
if (coAuthor == null)
{
coAuthor = createAuthor( coAuthorName);
}
author.addCoAuthor( coAuthor);
}
}
}
}
}
// 2. Measure distance from Erdos
Author erdosHimself = authorIdx.get( "Erdos, P.");
if (erdosHimself == null)
{
erdosHimself = createAuthor( "Erdos, P.");
}
erdosHimself.erdosNo = 0;
List<Author> hasToBeProcessed = new ArrayList<Author>();
hasToBeProcessed.add( erdosHimself);
while(!hasToBeProcessed.isEmpty())
{
Author author = hasToBeProcessed.remove( 0);
author.processed = true;
for (Author a : author.getCoAuthors())
{
if ((author.erdosNo + 1) < a.erdosNo)
{
a.erdosNo = author.erdosNo + 1;
}
if (!a.processed && !hasToBeProcessed.contains( a))
{
hasToBeProcessed.add(a);
}
}
}
// Dump Result
sbOut.append( "Scenario " + (i+1) + "\n");
for (String name : names)
{
Author author = authorIdx.get( name);
if (author != null)
{
String erdNr;
if (author.erdosNo == Integer.MAX_VALUE)
{
erdNr = "infinity";
} else {
erdNr = String.valueOf( author.erdosNo);
}
sbOut.append(name + " " + erdNr + "\n");
}
}
}
cout.print(sbOut.toString());
}
static Collection<String> splitPaper(String paper)
{
// 0: name vollständig gelesen, erwarte neuen namen
// 1: Nachname gelesen, erwarte vorname
paper = trim(paper);
int colon = paper.indexOf( ':');
if (colon > 0)
{
paper = paper.substring( 0, colon);
}
int state = 0;
int lastIndex = 0;
Collection<String> names = new HashSet<String>();
int nameStart = 0;
while (true)
{
int comma = paper.indexOf( ',', lastIndex);
if (comma != -1)
{
if (state == 0)
{
nameStart = lastIndex;
state = 1;
} else
{
String name = paper.substring( nameStart, comma);
name = name.trim();
names.add( name);
state = 0;
}
lastIndex = comma+1;
} else {
if (state == 1)
{
String name = paper.substring( nameStart);
name = name.trim();
names.add( name);
}
break;
}
}
return names;
}
static Author createAuthor(String name)
{
Author a = new Author(name);
authorIdx.put( name, a);
return a;
}
static String trim(String s)
{
int from = 0;
int to = s.length()-1;
while (s.charAt( from) == ' ' || s.charAt( from) == '\t')
{
from++;
}
while (Character.isWhitespace( s.charAt( to)))
{
to--;
}
StringBuffer sb = new StringBuffer();
for (int i=from; i<=to; i++)
{
char c = s.charAt( i);
if (c == ' ')
{
sb.append( c);
while(i<=to && s.charAt( i+1) == ' ')
{
i++;
}
} else
{
sb.append( c);
}
}
return sb.toString();
}
static class Author
{
String name;
int erdosNo;
boolean processed;
Collection<Author> coAuthorOf;
Author(String name)
{
this.erdosNo = Integer.MAX_VALUE;
this.processed = false;
this.name = name;
coAuthorOf = new HashSet<Author>();
}
Collection<Author> getCoAuthors()
{
return coAuthorOf;
}
void addCoAuthor(Author a)
{
coAuthorOf.add( a);
}
@Override
public String toString()
{
return name;
}
@Override
public boolean equals(Object obj)
{
return name.equals( ((Author)obj).name);
}
@Override
public int hashCode()
{
return name.hashCode();
}
}
}
