“Random Facebook quiz” (part 3/3)

[et_pb_section admin_label=”section”][et_pb_row admin_label=”row”][et_pb_column type=”4_4″][et_pb_text admin_label=”Text”]

Well I can’t leave this alone. Here’s a ‘C’ version:


#include
#include
#include
char *words[] = {
"tsar", "rat", "tar", "star",
"tars", "cheese", "mow", "lox",
NULL
};
#define LETTERS 26
// the following assumes the alphabet is no more than 256 symbols
static char hashcount[LETTERS];
// the following assumes a word's symbols never repeats more than 256
static char hashbuffer[LETTERS*3+1];
char *hash(char *word) {
char *ptr = word;
int i;
for (i=0; i= 'a' && c <= 'z') hashcount[c-'a']++; ptr++; } ptr = hashbuffer; for (i=0; i 1) {
sprintf(ptr, "%x", hashcount[i]);
ptr += (hashcount[i]/16 + 1);
}
}
}
*ptr = '\0';
return strdup(hashbuffer);
}
int main(int argc, char *argv[]) {
char **id = NULL;
char *printed = NULL;
int i, j, len=0;
while (1) {
if (words[len] == NULL) break;
len++;
}
id = (char **)malloc(len*sizeof(char *));
printed = (char *)malloc(len*sizeof(char));
for (i=0; i

...and its output:


[0] tsar : arst
[1] rat : art
[2] tar : art
[3] star : arst
[4] tars : arst
[5] cheese : ce3hs
[6] mow : mow
[7] lox : lox
===
tsar
star
tars
===
rat
tar
===
cheese
===
mow
===
lox

[/et_pb_text][/et_pb_column][/et_pb_row][/et_pb_section]

“Random Facebook quiz” (part 2/3)

PhiPi from the Propeller forums pointed out that my simple id() function would treat the words “MOW” and “LOX” as the same. This means my code “accidently worked” for the dataset provided in the question.

PhiPi made a suggestion that I ran with. I tweaked the id() function and came up with this:


t = { "tsar", "rat", "tar", "star", "tars", "cheese", }
function id(s)
local t = {}
for i=1,26 do t[i] = 0 end
for i=1,#s do
local c = string.lower(s:sub(i,i))
if c >= "a" and c <= "z" then local h = string.byte(c) - ("a"):byte() + 1 if h > 0 then t[h] = t[h] + 1 end
end
end
local r = ""
for i=1,26 do
if t[i] > 0 then
r = r .. string.char(("a"):byte() + i - 1)
end
if t[i] > 1 then
r = r .. t[i]
end
end
return r
end
p = {} u = {}
print("* word -> id *")
for i=1,#t do
p[i] = 0
u[i] = id(t[i])
print(t[i], u[i])
end
for i=1,#u do
if p[i] == 0 then
p[i] = 1
print("===")
print(t[i])
for j=i+1,#u do
if p[j] == 0 and u[i] == u[j] then
p[j] = 1
print(t[j])
end
end
end
end

which outputs:


* word -> id *
tsar arst
rat art
tar art
star arst
tars arst
cheese ce3hs
===
tsar
star
tars
===
rat
tar
===
cheese

“Random Facebook quiz” (part 1/3)

My friends on the Parallax Propeller forum posted the following quiz:

During a 45-minute Facebook job interview you could be requested to write a C++ from scratch that does this:
You have a list of these words
“tsar”, “rat”, “tar”, “star”, “tars”, “cheese”

re-arrange them so the anagrams (words that have the same letters) are grouped together.
output order not important.

Here’s my take (albeit in Lua instead of C++):

t = { "tsar", "rat", "tar", "star", "tars", "cheese", }
function id(s)
local n=0
for i=1,#s do
n = n + s:byte(i,i)
end
return n
end
u = {}
p = {}
for i=1,#t do
p[#p+1] = 0
u[#u+1] = id(t[i])
end
for i=1,#u do
if p[i] == 0 then
p[i] = 1
print("===")
print(t[i])
for j=1,#u do
if p[j] == 0 and u[i] == u[j] then
p[j] = 1
print(t[j])
end
end
end
end

…and the output…

===
tsar
star
tars
===
rat
tar
===
cheese

“Solution to Problem 4”

A Lua response to Problem 4:

Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

function eval(a, i)
if not i then i = 1 max = 0 end
if i == #a then
local n = tonumber(table.concat(a))
if n > max then max = n end
else
for j=i,#a do
a[i],a[j] = a[j],a[i]
eval(a, i+1)
a[i],a[j] = a[j],a[i]
end
end
end
eval({50, 2, 1, 9})
io.write("max is ", max, "\n")

Output is:

max is 95021

“Solution to Problem 5”

A dude recently posted some programming challenges on his blog (here) that were mentioned on Reddit r/programming.

Problem 5 caught my eye and below, I’ve posted a short and sweet Lua brute-force to solve it:

Write a program that outputs all possibilities to put + or – or nothing between the numbers 1, 2, …, 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.

a = {
1, "", 2, "", 3, "", 4, "", 5, "",
6, "", 7, "", 8, "", 9
}
function inc(a)
for i=2,#a,2 do
if a[i] == "" then a[i] = "+" return true end
if a[i] == "+" then a[i] = "-" return true end
if a[i] == "-" then a[i] = "" end
end
return false
end
function eval(a)
local s = table.concat(a)
if loadstring("return " .. s)() == 100 then print(s) end
end
repeat eval(a) until inc(a) == false

Output looks like:

123-45-67+89
12-3-4+5-6+7+89
12+3+4+5-6-7+89
123+4-5+67-89
1+2+3-4+5+6+78+9
12+3-4+5+67+8+9
1+23-4+56+7+8+9
1+2+34-5+67-8+9
1+23-4+5+6+78-9
123+45-67+8-9
123-4-5-6-7+8-9