crossrefme: Facebook quiz solution

A couple of months ago I stumbled upon this puzzle on the facebook jobs page. I thought I might take a crack at it, based on my interpretation of the problem. If anyone has a better solution please leave me a comment. I call it the "Brute Force LCM method."

Using the example given I figured out which key belongs to which.

key['a'] = 'l'; key['b'] = 'c'; key['c'] = 'z';
key['d'] = 'f'; key['e'] = 't'; key['f'] = 'm';
key['g'] = 'i'; key['h'] = 'w'; key['i'] = 'o';
key['j'] = 'k'; key['k'] = 'd'; key['l'] = 'g';
key['m'] = 'j'; key['n'] = 'n'; key['o'] = 'a';
key['p'] = 's'; key['q'] = 'e'; key['r'] = 'b';
key['s'] = 'u'; key['t'] = 'h'; key['u'] = 'v';
key['v'] = 'y'; key['w'] = 'q'; key['x'] = 'r';
key['y'] = 'p'; key['z'] = 'x';

Notice that with the exception of 'n' it takes 5 step to get from a character back to its original. i.e a to l, l to g, g to i, i to o, o to a. So every character has a 5 step shortest path except for n which has a path of 1 step. So if you have a string made of any of these characters you'll take 5 steps to
return back to the original string. If however, you have a string made up of n's the you'll
have only have 1 step to get back. If your string has a mixture of characters and an 'n'
then it still takes 5 steps.

Jodt Dabn
Kafh Flcn
Dlmw Mgzn
Fgjq Jixn
Mike Korn

That is, although to n loops once, the other characters loops 5 times so the n has to loop 5 times to catch up with the other characters. If n had a path of
2 instead then it would have had to loop 10 times for all the characters to catch up. If you do
this manually you'll see this. If you notice, 10 is the Lowest Common Multiple(LCM) of 5 and 2. So going back to our example, the LCM of 5 and 1 is 5. Therefore, given and string, the maximum number of loops it goes through before getting back to it's original state is the LCM of all the cycles which is 5.

So the algorithm is as follows,

We find the shortest path each character takes to get back to it's original character.
(Hence the term Brute Force)

//iterate through each letter and cycle through them until we get back to the orig character.
//we count the lenght of the cycle
for (var j=0; j<size; j++){
var current = nme.charAt(j);
var start = current;
var next = key[current];

while (next != start &&amp;amp;amp;amp;amp; current !== null){
current = key[current];
next = key[current];
count++;
}
a = lcm(count,a); //the LCM of all the cycles is the answer
count = 1;
}
return a;

We then find the LCM of all the paths using Euclid's algorithm.

function lcm(a,b){
return a * b / gcd(a,b);
}

function gcd(a,b){
if (b==0)
return a;
else
return gcd(b, a%b);
}

I have attached full code listing below;

<html>
<head></head>
<body>
<script language = 'JavaScript'>
<!--
//@author: AL SAM
//@date: 21 June 2006
//@description: Possible solution to the facebook Korn Shell puzzle using "Brute Force LCM method"
//  http://www.facebook.com/jobs_puzzles/?puzzle_id=7

var key= new Array();
key['a'] = 'l';
key['b'] = 'c';
key['c'] = 'z';
key['d'] = 'f';
key['e'] = 't';
key['f'] = 'm';
key['g'] = 'i';
key['h'] = 'w';
key['i'] = 'o';
key['j'] = 'k';
key['k'] = 'd';
key['l'] = 'g';
key['m'] = 'j';
key['n'] = 'n';
key['o'] = 'a';
key['p'] = 's';//
key['q'] = 'e';
key['r'] = 'b';
key['s'] = 'u';//
key['t'] = 'h';
key['u'] = 'v';//
key['v'] = 'y';//
key['w'] = 'q';
key['x'] = 'r';
key['y'] = 'p';//
key['z'] = 'x';


function korn(fname, lname){
var fn = fname.toLowerCase();
var ln = lname.toLowerCase();
var nme = fn + ln;
var size = nme.length;
var count = 1;
var a = 1;

//iterate through each letter and cycle through them until we get back to the orig character.
//we count the lenght of the cycle
for (var j=0; j> 2;
document.write(ans2 + "
");
//-->
</script>

<form name="korn_form">
<input type="text" id="fname" value="firstname"/> <input type="text" id="lname" value="lastname"/> <input type="button" value="go" onclick="suger();"/>
</form>
<div id="ans"/>

<script language = 'JavaScript'>
<!--
function suger(){
var fn = document.getElementById('fname').value;
var ln = document.getElementById('lname').value;
var ans = korn(fn,ln);
document.getElementById('ans').innerHTML = " ans = " + ans;
}
//-->
</script>
</body>
</html>

crossrefme

Tuesday, July 03, 2007

Facebook quiz solution

No comments:

About Me

Related Links

Blog Archive