Facebook Puzzle Challenge - Liar Liar - Difficulty Easy

[Artificial]

URL to challenge:

http://www.facebook.com/careers/puzzles.php?puzzle_id=20

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.

Spoiler:

#!/usr/bin/python
import sys
import re

# 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)
    
# Let's now output
if len(truth) > len(liars):
  print str(len(truth)) + " " + str(len(liars))
else:
  print str(len(liars)) + " " + str(len(truth))

[MattSmith]

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.

[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.

[MattSmith]

Ill be sure to finish it up tonight then after I finish some other software I've been working on.

[Artificial]

I take it then, you did not succeed?

[MattSmith]

Nah, Havnt had time between making bank and school.

[MattSmith]

Scenarios Alex made over Skype:

5
George	1
Isaac
Stephen	1
Galileo
Galileo	1
Tommaso	
Tommaso	1
Galileo
Isaac  	1
Galileo

Solution:

3 2

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:

5 3

---------- Post added at 11:12 PM ---------- Previous post was at 10:27 PM ----------

Mine:

Short Version:

Spoiler:

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"));

			while ((str = in.readLine()) != null)
	        	lines = lines + str + "\n";

			String[] lieChart = lines.split("\n");
			int mPos = lieChart[1].length();

			Map<String, Integer> m = new TreeMap<String, Integer>();
			for(int x = 0; x<lieChart.length; x++)
				if(x!=0) m.put(lieChart[x].split(" ")[0], (m.containsKey(lieChart[x].split(" ")[0]) ? (m.get(lieChart[x].split(" ")[0]) == 1 ? 0 : 1) : ((lieChart[x].length() == mPos) ? 1 : 0)));

			for(int y = 0; y<m.size(); y++) if(m.values().toArray()[y].toString().contains("1")){ t++; }else{ l++; } 
			System.out.println((t>=l) ? (t + " " + l) : (l + " " + t) );
		}catch(IOException e){}
	}
}

Commented Version / Kinda Readable version.

Spoiler:

import java.util.*;
import java.io.*;

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"));

			while ((str = in.readLine()) != null)
	        	lines = lines + str + "\n";

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

[Artificial]

Nice solution, poor readability though!

Although technically you didn't meet the input requirements. Tsk tsk.

[Snow-kun]

Nice solution, poor readability though!

Although technically you didn't meet the input requirements. Tsk tsk.

Send me some tutorial and I might be able to get it soon.

[The UnIntelligible]

Send me some tutorial and I might be able to get it soon.

i too desire "some tutorial." can u link me to some mattsmit & artificial?

[MattSmith]

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.

[MattSmith]

Check out the difficulty ratings on all the puzzles:

Engineering Puzzles | Facebook

Im doing this one now:

http://www.facebook.com/careers/puzzles.php?puzzle_id=8

[Artificial]

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.