This puzzle isn't too difficult. Having said that though, my solution isn't too elegant. I generally do all of these puzzles/challenges in PHP, which is a language I know through and through, however I've decided to start using Python instead. There's no doubt features of the language and functions I'm not properly utilising, but in time I hope to remedy this.
If you have a solution, please post it, as I'd love to read through it.
# Ensure we have the proper amount of arguments
if len(sys.argv) < 2:
print "Please pass through a file to open"
sys.exit(0)
# Let's open the file
filename = sys.argv[1]
try:
file = open(filename,"r").read()
except:
print "An error has occured when opening the file"
# Let's parse the data in to a dictionary
lines = file.split("\n")
people = {}
pointer = 1 # Where we currently are
while len(people) < int(lines[0].strip()):
(person, amount) = re.sub(" \s+", " ", lines[pointer].strip()).split(" ")
amount = int(amount)
people[person] = []
for x in range(1, amount + 1):
pointer += 1
people[person].append(lines[pointer].strip())
pointer += 1
# Sort out the liars from the ones telling truth
(truth, liars) = ([],[])
# Now let's go through and see if someone is telling the truth
def tellingTruth(name, trail=[]):
# If we've already determined whether or not they're liars/telling truth
if name in truth:
return len(trail) % 2 != 0
elif name in liars:
return len(trail) % 2 == 0
# Loop through
if name not in trail:
trail.append(name)
for i in range(0, len(people[name])):
if people[name][i] in trail: #we've already checked
if len(trail) <= 2:
return None
else:
return ( len(trail) - 1 ) % 2 == 0
else:
trail.append(people[name][i])
return tellingTruth(people[name][i], trail)
# Let's go through and determine who's lying and who isnt
for i in range(0,len(people)):
isTruth = tellingTruth(people.keys()[i], [])
if isTruth == True:
truth.append(people.keys()[i])
elif isTruth == False:
liars.append(people.keys()[i])
# Have a preliminary list, let's see if that solves
for person in truth:
subjects = people[person]
for subject in subjects:
if subject not in liars:
liars.append(subject)
for person in liars:
subjects = people[person]
for subject in subjects:
if subject not in truth:
truth.append(subject)
Not goin' to lie, this is harder than it seems haha, Working on it in Java since I'm trying to learn it. I'll post up my sources when I finish it.
10 Dec. 2011, 12:03am
Artificial
I enjoyed it. The trick with these sort of things is to think through how you'd do it yourself, and then just write an algorithm automate it.
Let me know when you've finished. I've had a brief look at their next puzzle (breathalyzer), and it looks interesting, so I'll probably do it either today or tomorrow. Either way, looking forward to seeing your solution.
10 Dec. 2011, 05:02pm
MattSmith
Ill be sure to finish it up tonight then after I finish some other software I've been working on.
15 Dec. 2011, 07:54am
Artificial
I take it then, you did not succeed?
16 Dec. 2011, 11:53pm
MattSmith
Nah, Havnt had time between making bank and school.
17 Dec. 2011, 04:12am
MattSmith
Scenarios Alex made over Skype:
Code:
5
George 1
Isaac
Stephen 1
Galileo
Galileo 1
Tommaso
Tommaso 1
Galileo
Isaac 1
Galileo
Solution:
Code:
3 2
Code:
8
John 1
Tony
Jane 1
Ricky
Tony 1
Matt
Mark 1
Ricky
Brad 1
Johnson
Matt 1
Brad
Ricky 1
John
Johnson 1
Ricky
Solution:
Code:
5 3
---------- Post added at 11:12 PM ---------- Previous post was at 10:27 PM ----------
Mine:
Short Version:
Spoiler:
Code:
import java.util.*;
import java.io.*;
public class FacebookPuzzle20_1
{
public static void main(String[] args)
{
try {
String lines = "", str;
int t = 0, l = 0;
BufferedReader in = new BufferedReader(new FileReader("puzzle.txt"));
public class FacebookPuzzle20
{
public static void main(String[] args)
{
try {
String lines = "", str;
int t = 0, l = 0;
BufferedReader in = new BufferedReader(new FileReader("puzzle.txt"));
String[] lieChart = lines.split("\n");
int mPos = lieChart[1].length();
Map<String, Integer> m = new TreeMap<String, Integer>(); // Map of the liars and truth tellers, sorted by a 0 and 1, key being the name.
for(int x = 0; x<lieChart.length; x++)
{
if(x!=0) // If it isnt the first line, this is where the person count exists.
{
String key = lieChart[x].split(" ")[0];
int value = 0;
boolean mContainsNameAlready = m.containsKey(key); // Name has already been in, if so flip it.
if(mContainsNameAlready)
{
if(m.get(key) == 1) // If this person is a 1 already put 0, else, put 1
m.put(key, 0);
else
m.put(key, 1);
}
else
{
if(lieChart[x].length() == mPos) // If telling a accusation (assume 1), else, being blamed (assume 0)
m.put(key, 1);
else
m.put(key, 0);
}
}
}
// Organize our truth and liars integers.
for(int y = 0; y<m.size(); y++)
{
String valueOfMY = m.values().toArray()[y].toString();
if(valueOfMY.contains("1")) // If 1 count t, else, count l
t++;
else
l++;
}
// Determine if t or l is larger, print larger one first.
if(t>=l)
System.out.println(t + " " + l);
else
System.out.println(l + " " + t);
}catch(IOException e){}
}
}
17 Dec. 2011, 11:25am
Artificial
Nice solution, poor readability though! :p
Although technically you didn't meet the input requirements. Tsk tsk.
17 Dec. 2011, 02:43pm
Snow-kun
Quote:
Originally Posted by Artificial
Nice solution, poor readability though! :p
Although technically you didn't meet the input requirements. Tsk tsk.
Send me some tutorial and I might be able to get it soon. :p
17 Dec. 2011, 05:26pm
The Unintelligible
Quote:
Originally Posted by Snow-kun
Send me some tutorial and I might be able to get it soon. :p
i too desire "some tutorial." can u link me to some mattsmit & artificial?
17 Dec. 2011, 06:20pm
MattSmith
Quote:
Originally Posted by The UnIntelligible
i too desire "some tutorial." can u link me to some mattsmit & artificial?
Possibly Ill write one up later. There are atleast 3 ways me and alex have thought of over skype to do this. I'll probably do a tutorial on how I wrote mine. As of right now, these are CHALLENGES for a reason.
---------- Post added at 01:20 PM ---------- Previous post was at 01:06 PM ----------
Alright, updated my post with my source and added one that you can read. Undid all my lambda and such. Slightly more readable. Kinda messy though.
17 Dec. 2011, 10:00pm
MattSmith
Check out the difficulty ratings on all the puzzles:
It's actually very easy if you first do it manually. On a piece of paper/whiteboard, create two columns and write down the accuser's name in left hand column and who they're accusing in right hand column. From there, try to figure out who is lying and who is telling the truth (I'll give you a hint - it's not too important who you identify as the liars and whose telling the truth - there's a reason they asked you to output the numbers of the two groups as opposed to the individuals in the two groups).
If you can do it manually, you just have to write an algorithm to automate it.