Facebook Puzzle Challenge - Liar Liar - Difficulty Easy

**Artificial** · 04 Dec. 2011 10:02am

URL to challenge:

Code:

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:

Code:

#!/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** · 08 Dec. 2011 01:30am

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** · 10 Dec. 2011 12:03am

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** · 10 Dec. 2011 05:02pm

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

**Artificial** · 15 Dec. 2011 07:54am

I take it then, you did not succeed?

**MattSmith** · 16 Dec. 2011 11:53pm

Nah, Havnt had time between making bank and school.

**MattSmith** · 17 Dec. 2011 04:12am

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

			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:

Code:

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** · 17 Dec. 2011 11:25am

Nice solution, poor readability though! :p

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

**Snow-kun** · 17 Dec. 2011 02:43pm

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

**The Unintelligible** · 17 Dec. 2011 05:26pm

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?

**MattSmith** · 17 Dec. 2011 06:20pm

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.

**MattSmith** · 17 Dec. 2011 10:00pm

Check out the difficulty ratings on all the puzzles:

Engineering Puzzles | Facebook

Im doing this one now:

Code:

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

**Artificial** · 17 Dec. 2011 10:16pm

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.

Thread: Facebook Puzzle Challenge - Liar Liar - Difficulty Easy

LinkBack

Thread Tools

Search Thread

Rate This Thread

Display

Facebook Puzzle Challenge - Liar Liar - Difficulty Easy

Tags for this Thread

Posting Permissions