Liar, Liar -- Facebook Puzzle

This was an interesting puzzle from Facebook. See the code below; i do not include unit test code here. You should be able to create a project in an IDE such as Eclipse (which is what I use) and create a class with the code below in the class. Similarly, you can use Eclipse to create the unit test code.

By the way, the code below is not completely robust though it works in several cases; a few more TODOs to be addressed that you see in the code. I got tired and so have put this code out without completing it.

For preciseness, the situation that the code does not address is when you lack commonality while processing each group of accuser and accused people leading to a disjoint group of liars and non-liars. The code works fine otherwise.

PUZZLE
As a newbie on a particular internet discussion board, you notice a distinct trend among its veteran members; everyone seems to be either unfailingly honest or compulsively deceptive. You decide to try to identify the members of the two groups, starting with the assumption that every senior member either never lies or never tells the truth. You compile as much data as possible, asking each person for a list of which people are liars. Since the people you are asking have been around on the board for a long time, you may assume that they have perfect knowledge of who is trustworthy and who is not. Each person will respond with a list of people that they accuse of being liars. Everyone on the board can see that you are a tremendous n00b, so they will grudgingly give you only partial lists of who the liars are. Of course these lists are not to be taken at face value because of all the lying going on.

You must write a program to determine, given all the information you've collected from the discussion board members, which members have the same attitude toward the telling the truth. It's a pretty popular discussion board, so your program will need to be able to process a large amount of data quickly and efficiently.

------------------------------------------------------------------------------------
CODE:

/**
* THIS PROGRAM SOLVES A PUZZLE THAT WAS GIVEN ON FACEBOOK; DETAILS BELOW.
*
* Your program must take a single command line argument; the name of a file. It must
* then open the file and read out the input data. The data begins with the number of
* veteran members n followed by a newline. It continues with n chunks of information,each
* defining the accusations made by a single member. Each chunk is formatted as follows:
*
* followed by m lines each containing the name of one member that the accuser says is a
* liar. accuser name and m are separated by some number of tabs and spaces. m will
* always be in [0, n]. All member names contain only alphabetic characters and are
* unique and case-sensitive.
*
*
*/
package com.farooq;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;

/**
* @author fanjum
*
*/
public class LiarDetection {
// a few TO DO's remain before this can be called robust code
//The basic algorithm works and has been tested.

/**
* @param args
*/

private ArrayList realGroupOne = new ArrayList();
private ArrayList realGroupOneOpposite = new ArrayList();
private ArrayList dummyGroupOne = new ArrayList();
private ArrayList dummyGroupOneOpposite = new ArrayList();

boolean doneWithAll; // to check if all people have been categorized
int lineNumber; // to maintain info about the number of lines read from file.
static String fileName; // the file which contains the detailed info
int numberOfPeople;
FileReader fileToRead; // file reader to be kept open until done
BufferedReader filebuffer;
int dummyCounter; // to split groups in the dummyGroup
final int DUMMY_INIT = 1000;

public static void main(String[] args) {

// get the file name;
fileName = "C:\\tempfiles\\file_liar_liar.txt";

// get the object initialization done
LiarDetection LD = new LiarDetection();

//now divide the people into two arrays associated with created LD object

LD.dividePeople();

System.out.println("WE ARE DONE");
//PRINT TWO REAL ARRAY LISTS IF YOU WANT and check.
for (int i=0;i System.out.println("next in this group is " +LD.realGroupOne.get(i));
}
for (int i=0; i < LD.realGroupOneOpposite.size(); i++) {
System.out.println("next in opposite groups i " +LD.realGroupOneOpposite.get(i));
}
}

public LiarDetection() {

String first_line, next_line;
String first_part, second_part; // to read the accuser name and number accused
int space_index; //to determine where accuser name ends and number accused begins
int numAccused; //to determine number accused
dummyCounter =DUMMY_INIT; // initializing dummyCounter to 1000;
//open the file and keep it open

try {
fileToRead = new FileReader(fileName);
filebuffer = new BufferedReader(fileToRead);

//read teh file and get the number numberOfPeople;

first_line = filebuffer.readLine();
numberOfPeople = Integer.valueOf(first_line).intValue();

// read the first block with member name, number accused m and accused names
lineNumber = 1; // to signify that one line was read
next_line = filebuffer.readLine().trim();
space_index = next_line.indexOf(" ");
first_part = next_line.substring(0, space_index); //name of accuser
second_part = next_line.substring(space_index).trim(); //number of accused in String
numAccused = Integer.valueOf(second_part).intValue(); //convert to int
realGroupOne.add(first_part);

for (int i=1; i<=numAccused; i++) {
//put all this in one of the two real ArrayLists;
//associate lineNumber with number of lines read so you know where to start next
next_line = filebuffer.readLine().trim();
realGroupOneOpposite.add(next_line);
}
} catch (Exception e) {
System.out.println("have an exception" +e);
}


}

public void dividePeople() {
// we start to divide people into two camps
// we start with 2 since we have read the accusation of first member
for (int mem_number=2; mem_number<=numberOfPeople; mem_number++) {
//make a call to see if we are done;
doneWithAll = checkIfDone();

if (!doneWithAll) {
//not divided all, so go to read accusation of mem_number
//A. read name of next member and the accusation list as String and String[]
//B. put the String and String[] in proper ArrayLists real or dummy and return here
//next method does both A and B above
divideNextGroup();
} else {
//we have divided all and so we are done
//close FILEREADER
try {
if (fileToRead != null)
fileToRead.close();
} catch (Exception e) {

}
break;
}
}


}
public boolean checkIfDone() {
// check if realGroupOne and realGroupOneOpposite have all n members with no dups
//if dups then a problem
//also the dummyGroupOne and its pair should have no members.
if (realGroupOne.size() + realGroupOneOpposite.size() == numberOfPeople) {
// we are done
return true;
} else {
return false;
}

}

public void divideNextGroup(){
String next_line;
String accuser_name, number_accused; // to read the accuser name and number accused
int numAccused; //number accused as an int
int space_index; //to determine where accuser name ends and number accused begins
String [] accused = new String[numberOfPeople];
boolean dividedIntoGroup; // true when the group members are put into one of four arrayLists.

try {
//read next member into String accuser_name
//read list of accused into String[] accused; accuser_name and accused go into different groups
next_line = filebuffer.readLine().trim();
space_index = next_line.indexOf(" ");
accuser_name = next_line.substring(0, space_index); //name of accuser
number_accused = next_line.substring(space_index).trim(); //number of accused in String
numAccused = Integer.valueOf(number_accused).intValue(); //convert to int
for (int i=0;i accused[i] = filebuffer.readLine().trim();
}

//check if accuser in realGroupOne or realGroupOneOpposite and if so
// ensure that all accused are in the other group; ensure no duplicates while adding.
dividedIntoGroup = isGroupInRealList(accuser_name, accused,numAccused);

if (!dividedIntoGroup) {
// not divided into realList, so check dummyList
dividedIntoGroup = isGroupInDummyList(accuser_name, accused,numAccused);

if (!dividedIntoGroup) {
//still not divided into group, so we put this in the dummyLists separated by an ID
putGroupInDummyList(accuser_name, accused, numAccused);
}
}

}catch (Exception e){

}

// when here the group has been divided in either the real group or the dummy group; so done
}

public boolean isGroupInRealList(String accuserName, String[] accusedList, int numberAccused) {

boolean inList = false;

// 6. check if A is IN any of the two real ArrayLists;
// 7a. If A in any of two real ArrayLists, add (B,C,...N) to the paired AL GO TO 4A.
// 7b. If A in none of two real ArrayLists, GO TO 8.
// 8. check if any of (B,C,..N) is in any of two real ArrayLists.
// 9a. If (B,C,..N) in any of two real ArrayLists add others to same AL,
// add A to paired AL, GO TO 4A.

// ALSO CHECK FOR INCONSISTENCY AND THROW AN EXCEPTION OR WHATEVER:
if (realGroupOne.contains(accuserName)) {
// accuser is in GroupOne, so add all in accusedList to other without dups
inList = true;
for (int i=0;i if (realGroupOne.contains(accusedList[i])) {
//this is a problem, should not happen
}
if (realGroupOneOpposite.contains(accusedList[i])) {
//accused name is already in list and so go to next
continue;
} else {
realGroupOneOpposite.add(accusedList[i]);
}
}

} else if (realGroupOneOpposite.contains(accuserName)) {
//accuser is in GroupOneOpposite so add all in accusedList to other without dups
inList = true;
for (int i=0;i if (realGroupOneOpposite.contains(accusedList[i])) {
//this is a problem, should not happen
}
if (realGroupOne.contains(accusedList[i])) {
//accused name is already in list and so go to next

} else {
realGroupOne.add(accusedList[i]);
}
}

} else {

//so accuser is not in either of real lists; so check if accused names are in either
for (int i=0;i //check if each accused in either of real lists
if (realGroupOne.contains(accusedList[i])) {
//add all the rest of the accusedList to GroupOne without duplicates
//and add accuser to other group
inList = true;
for (int j=i+1;j //add rest of group to GroupOne
if (!(realGroupOne.contains(accusedList[j]))) {
//add to this group
realGroupOne.add(accusedList[j]);
}
}
realGroupOneOpposite.add(accuserName);

break;
}
if (realGroupOneOpposite.contains(accusedList[i])) {
//add all the rest of the accusedList to GroupOne without duplicates
//and add accuser to other group
inList = true;
for (int j=i+1;j //add rest of group to GroupOne without duplicates
if (!(realGroupOneOpposite.contains(accusedList[j]))) {
//add to this group
realGroupOneOpposite.add(accusedList[j]);
}
}
realGroupOne.add(accuserName);

break;

}

}

}
return inList;
}

public boolean isGroupInDummyList(String accuserName, String[] accusedList, int numberAccused) {
int indexOfName, indexOfCounter;
int tempindex;
boolean indummylist = false;
// 10. check if A in any of two dummy ALs.
// 10a. If A in any of two dummy ALs, add (B, C,...N) to same block in paired dummy AL.
// GO TO 4A.
// 10b. check if any of B,C, ...N in any of two dummy ALs.
// 10c. Merge all the blocks that contain any of B,C, ...N into one TEMPBLOCK with unique elements.
// also remove the blocks when you put them into TEMPBLOCK;
// 10d. for every block that contains B,C,..N, merge the corresponding block in other
// AL into one TEMPBLOCK with unique elements.
// 10e. get teh next counter, add to dummy AL and merge TEMPBLOCK back into dummy AL.
// each TEMPBLOCK should be in a different dummy AL.

if (dummyGroupOne.contains(accuserName)) {
// accusername is in this; find index and add to same subGroup in other dummy group
indexOfName = dummyGroupOne.indexOf(accuserName);
indummylist = true;
for (int j=indexOfName; j >=0; j--) {
// to go and figure out the counter index
try {
indexOfCounter = Integer.valueOf(dummyGroupOne.get(j)).intValue();
//so now indexOfCounter contains the counter number
tempindex = dummyGroupOneOpposite.indexOf(Integer.toString(indexOfCounter));

for (int i=0; i //have to check if the ith accused is in dummy list but we skip that now
//TO DO --- SO THIS IS TO BE FIXED
dummyGroupOneOpposite.add(tempindex+1,accusedList[i]);
}
} catch(NumberFormatException e) {
continue;
}
}

} else if (dummyGroupOneOpposite.contains(accuserName)) {
//accuserName is in this; find index and add to same subGroup in other dummy group
indexOfName = dummyGroupOneOpposite.indexOf(accuserName);
indummylist = true;
for (int j=indexOfName; j >=0; j--) {
// to go and figure out the counter index
try {
indexOfCounter = Integer.valueOf(dummyGroupOneOpposite.get(j)).intValue();
//so now indexOfCounter contains the counter number
tempindex = dummyGroupOne.indexOf(Integer.toString(indexOfCounter));

for (int i=0; i //have to check if the ith accused is in dummy list but we skip that now
//TO DO --- SO THIS IS TO BE FIXED
dummyGroupOne.add(tempindex+1,accusedList[i]);
}
} catch(NumberFormatException e) {
continue;
}
}
}

//now check if accused[] are in either of the groups, if so add accuser to other dummy group
//also ensure rest of accused[] are in the same subgroup

//TO DO -- check on this and complete this.


// TO DO -- ALSO MERGE REAL AND DUMMY LISTS;
return indummylist;
}

public void putGroupInDummyList(String accuserName, String[] accusedList, int numberAccused) {
// 11. If (B,C,..N) in none of four ALs add A to dummyAL_G1 and (B,C,..N)
// to dummyAL_G2 after counter

//adding accuser to dummy Group One after counter
dummyGroupOne.add(Integer.toString(dummyCounter));
dummyGroupOne.add(accuserName);

//adding accused to dummy Group OneOpposite after counter
dummyGroupOneOpposite.add(Integer.toString(dummyCounter));
for (int i=0; i< numberAccused; i++) {
dummyGroupOneOpposite.add(accusedList[i]);
}
dummyCounter++;

}
}