Interview Question
Country: South Africa
#include <time.h>
#if 0
Logic
N O R T H +
E A S T +
S O U T H +
W E S T =
E A R T H
n1 = 2*(H + T)
n1%10 = H
n2 = 2*(T + S) + n1/10
n2%10 = T
n3 = (R + A + U + E) + n2/10
n3%10 = R
n4 = (2*O + E + W) + n3/10
n4%10 = A
n5 = N + S + n4/10
n5 = E
#endif
bool
choose_ow(int *O, int *W, int *N, int S, int A, int E, int n3, uint8_t used[])
{
int o, w, n;
int n4, n5;
for (o=*O; o<10; o++) {
if (used[o]) continue;
used[o] = 1;
*O = o;
for (w=*W; w<10; w++) {
if (used[w]) continue;
n4 = (o * 2) + E + w + n3/10;
if (n4%10 != A) continue;
used[w] = 1;
*W = w;
for (n=*N; n<10; n++) {
if (used[n]) continue;
n5 = n + S + n4/10;
if (n5 != E) {
continue;
}
used[n] = 1;
*N = n;
return TRUE;
} // N
if (n==10) {
used[w] = 0;
}
} // W
if (w==10) {
used[o] = 0;
}
} // O
return FALSE;
}
bool
choose_raue (int *R, int *A, int *U, int *E, int n2, uint8_t used[])
{
int r, a, u, e;
int n3;
for (r=*R; r<10; r++) {
if (used[r]) continue;
used[r] = 1;
*R = r;
for (a=*A; a<10; a++) {
if (used[a]) continue;
used[a] = 1;
*A = a;
for (u=*U; u<10; u++) {
if (used[u]) continue;
used[u] = 1;
*U = u;
for (e=*E; e<10; e++) {
if (used[e]) continue;
n3 = (r + a + e + u) + n2/10;
if (n3%10 == r) {
used[e] = 1;
*E = e;
return TRUE;
}
} // E
if (e==10) {
used[u] = 0;
}
} // U
if (u==10) {
used[a] = 0;
}
} // A
if (a==10) {
used[r] = 0;
}
}
return FALSE;
}
int
main ()
{
uint8_t used[10];
int n1, n2, n3, n4, n5;
int H, T, S, R, A, W, E, O, N, U;
bool found = FALSE;
clock_t start, end;
double cpu_time_used;
start = clock();
H = T = S = R = A = W = E = O = N = U = 0;
for (H=0; H<10; H++) {
memset(used, 0, sizeof(used));
used[H] = 1;
for (T = 0; T<10; T++) {
if (used[T]) continue;
n1 = 2 * (H + T) ;
if ((n1%10) != H) {
continue;
}
used[T] = 1;
for (S=0; S<10; S++) {
if (used[S]) continue;
n2 = (2 * (T + S)) + n1/10;
if (n2%10 != T) continue;
used[S] = 1;
R = A = U = E = 0;
raue:
if (choose_raue(&R, &A, &U, &E, n2, used) == FALSE) {
used[S] = 0;
continue;
}
n3 = (R + A + U + E) + n2/10;
O = W = N = 0;
if (choose_ow(&O, &W, &N, S, A, E, n3, used) == FALSE) {
used[R] = used[A] = used[U] = used[E] = 0;
E++;
goto raue;
} else { // choose_owns
printf("Found the values: H %d, T %d, S %d, R %d, A %d, W %d, E %d, O %d, N %d, U %d\n",
H, T, S, R, A, W, E, O, N, U);
S = T = 10;
}
} // S
if (S == 10) {
used[T] = 0;
}
} // T
if (T == 10) {
used[H] = 0;
}
} // H
end = clock();
cpu_time_used = ((double) (end - start) * 1000) / CLOCKS_PER_SEC;
printf("%lfmsec count %d\n", cpu_time_used);
return 0;
}
/*
*/
#include "basic.h"
#include <time.h>
#if 0
N O R T H +
E A S T +
S O U T H +
W E S T =
E A R T H
n1 = 2*(H + T)
n1%10 = H
n2 = 2*(T + S) + n1/10
n2%10 = T
n3 = (R + A + U + E) + n2/10
n3%10 = R
n4 = (2*O + E + W) + n3/10
n4%10 = A
n5 = N + S + n4/10
n5 = E
#endif
bool
choose_ow(int *O, int *W, int *N, int S, int A, int E, int n3, uint8_t used[])
{
int o, w, n;
int n4, n5;
for (o=*O; o<10; o++) {
if (used[o]) continue;
used[o] = 1;
*O = o;
for (w=*W; w<10; w++) {
if (used[w]) continue;
n4 = (o * 2) + E + w + n3/10;
if (n4%10 != A) continue;
used[w] = 1;
*W = w;
for (n=*N; n<10; n++) {
if (used[n]) continue;
n5 = n + S + n4/10;
if (n5 != E) {
continue;
}
used[n] = 1;
*N = n;
return TRUE;
} // N
if (n==10) {
used[w] = 0;
}
} // W
if (w==10) {
used[o] = 0;
}
} // O
return FALSE;
}
bool
choose_raue (int *R, int *A, int *U, int *E, int n2, uint8_t used[])
{
int r, a, u, e;
int n3;
for (r=*R; r<10; r++) {
if (used[r]) continue;
used[r] = 1;
*R = r;
for (a=*A; a<10; a++) {
if (used[a]) continue;
used[a] = 1;
*A = a;
for (u=*U; u<10; u++) {
if (used[u]) continue;
used[u] = 1;
*U = u;
for (e=*E; e<10; e++) {
if (used[e]) continue;
n3 = (r + a + e + u) + n2/10;
if (n3%10 == r) {
used[e] = 1;
*E = e;
return TRUE;
}
} // E
if (e==10) {
used[u] = 0;
}
} // U
if (u==10) {
used[a] = 0;
}
} // A
if (a==10) {
used[r] = 0;
}
}
return FALSE;
}
int
main ()
{
uint8_t used[10];
int n1, n2, n3, n4, n5;
int H, T, S, R, A, W, E, O, N, U;
bool found = FALSE;
clock_t start, end;
double cpu_time_used;
start = clock();
H = T = S = R = A = W = E = O = N = U = 0;
for (H=0; H<10; H++) {
memset(used, 0, sizeof(used));
used[H] = 1;
for (T = 0; T<10; T++) {
if (used[T]) continue;
n1 = 2 * (H + T) ;
if ((n1%10) != H) {
continue;
}
used[T] = 1;
for (S=0; S<10; S++) {
if (used[S]) continue;
n2 = (2 * (T + S)) + n1/10;
if (n2%10 != T) continue;
used[S] = 1;
R = A = U = E = 0;
raue:
if (choose_raue(&R, &A, &U, &E, n2, used) == FALSE) {
used[S] = 0;
continue;
}
n3 = (R + A + U + E) + n2/10;
O = W = N = 0;
if (choose_ow(&O, &W, &N, S, A, E, n3, used) == FALSE) {
used[R] = used[A] = used[U] = used[E] = 0;
E++;
goto raue;
} else { // choose_owns
printf("Found the values: H %d, T %d, S %d, R %d, A %d, W %d, E %d, O %d, N %d, U %d\n",
H, T, S, R, A, W, E, O, N, U);
S = T = 10;
}
} // S
if (S == 10) {
used[T] = 0;
}
} // T
if (T == 10) {
used[H] = 0;
}
} // H
end = clock();
cpu_time_used = ((double) (end - start) * 1000) / CLOCKS_PER_SEC;
printf("%lfmsec count %d\n", cpu_time_used);
return 0;
}
/*
'NORTH' +
'0EAST' +
'0WEST' +
'SOUTH'
===========
'EARTH'
2(H + T) % 10 = H // constraint 1
(2(T + S) + 2(H+T)/5) % 10 = T constraint 2
Solving these two reduces the problem from 10! into 7! Baam.
That is heavily reduced.
Now let's see how H, T, S are there.
*/
def is_valid( map ){
north = map.h + 10 * ( map.t + 10 * ( map.r + 10* ( map.o + 10 * map.n )))
east = map.t + 10 * ( map.s + 10 * ( map.a + 10* ( map.e ) ) )
west = map.t + 10 * ( map.s + 10 * ( map.e + 10* ( map.w ) ) )
south = map.h + 10 * ( map.t + 10 * ( map.u + 10* ( map.o + 10 * map.s ) ) )
earth = map.h + 10 * ( map.t + 10 * ( map.r + 10* ( map.a + 10 * map.e ) ) )
earth == ( north + east + west + south )
}
digits = [0:10].asList
// find constraint 1
c1_pairs = join(digits,digits) where { ($.l != $.r) && ( $.l == 2 * sum($.o) % 10 ) }
// get next set of constrant 2 ?
c2_tuples = join(digits,c1_pairs) where {
#(H,T) = $.r
S = $.l
S !@ $.r && ( ( 2 *( T + S ) + 2*(H+T)/10 ) % 10 == T )
} as { d = { 'h' : $.r.0 , 's' : $.l , 't' : $.r.1 } }
rest_of_lettrers = [ 'a' , 'e' , 'n', 'o', 'r', 'u' ,'w' ]
// now that we have established the 3 items,
// rest 7 has to be chosen who are not ... in the group
for ( t : c2_tuples ) {
other_digits = digits - t.values
// now permuatate the other_digits
for ( p : perm( other_digits ) ){
// assign into map
d = dict( rest_of_lettrers ) as { [ $.o, p[$.i] ] }
d |= t // the whole map
if ( is_valid( d ) ){
println( d )
}
}
}
Producing...
{a=1, r=6, s=0, t=8, e=5, u=3, w=7, h=4, n=2, o=9}
{a=2, r=5, s=0, t=8, e=6, u=1, w=7, h=4, n=3, o=9}
{a=3, r=1, s=0, t=8, e=7, u=9, w=2, h=4, n=5, o=6}
{a=3, r=5, s=0, t=8, e=7, u=9, w=2, h=4, n=6, o=1}
{a=0, r=5, s=1, t=6, e=7, u=2, w=4, h=8, n=3, o=9}
{a=3, r=2, s=1, t=6, e=7, u=9, w=4, h=8, n=5, o=0}
{a=3, r=4, s=1, t=6, e=7, u=9, w=0, h=8, n=5, o=2}
{a=9, r=5, s=1, t=6, e=3, u=7, w=4, h=8, n=2, o=0}
{a=9, r=0, s=1, t=6, e=7, u=3, w=2, h=8, n=5, o=4}
{a=3, r=1, s=2, t=5, e=9, u=7, w=6, h=0, n=4, o=8}
{a=4, r=1, s=2, t=5, e=8, u=7, w=6, h=0, n=3, o=9}
{a=7, r=8, s=2, t=5, e=9, u=3, w=4, h=0, n=6, o=1}
{a=8, r=9, s=2, t=5, e=4, u=7, w=6, h=0, n=1, o=3}
{a=8, r=6, s=2, t=5, e=7, u=4, w=1, h=0, n=3, o=9}
{a=9, r=8, s=2, t=5, e=4, u=6, w=7, h=0, n=1, o=3}
{a=9, r=6, s=2, t=5, e=7, u=3, w=8, h=0, n=4, o=1}
{a=9, r=6, s=4, t=1, e=7, u=3, w=0, h=8, n=2, o=5}
{a=2, r=3, s=5, t=8, e=7, u=9, w=1, h=4, n=0, o=6}
{a=2, r=6, s=5, t=8, e=7, u=9, w=3, h=4, n=1, o=0}
{a=2, r=6, s=5, t=8, e=9, u=7, w=1, h=4, n=3, o=0}
{a=3, r=7, s=5, t=8, e=6, u=9, w=1, h=4, n=0, o=2}
{a=6, r=0, s=5, t=8, e=9, u=3, w=1, h=4, n=2, o=7}
{a=7, r=1, s=5, t=8, e=9, u=2, w=6, h=4, n=3, o=0}
{a=9, r=1, s=5, t=8, e=6, u=3, w=7, h=4, n=0, o=2}
require 'ostruct'
require 'benchmark'
k = Benchmark.measure do
ps = []
(0..9).each do |h|
(0..9).each do |t|
if (temp = h + (2 * t)) % 10 == 0
k = (temp / 10)
ot = OpenStruct.new
ot.h = h
ot.t = t
ot.k = k
ps << ot
end
end
end
new_ps = []
ps.each do |ps_n|
(0..9).each do |s|
if (temp = ps_n.t + (2 * s) + ps_n.k) % 10 == 0
l = (temp / 10)
ot = ps_n.clone
ot.s = s
ot.l = l
new_ps << ot
end
end
end
ps = new_ps
new_ps = []
ps.each do |ps_n|
(0..9).each do |a|
(0..9).each do |u|
(0..9).each do |e|
if (temp = a + u + e + ps_n.l) % 10 == 0
m = temp / 10
ot = ps_n.clone
ot.a = a
ot.u = u
ot.e = e
ot.m = m
new_ps << ot
end
end
end
end
end
ps = new_ps
new_ps = []
ps.each do |ps_n|
(0..9).each do |o|
(0..9).each do |w|
if (temp = (2 * o) + ps_n.e + w + ps_n.m - ps_n.a ) % 10 == 0
q = temp / 10
ot = ps_n.clone
ot.o = o
ot.w = w
ot.q = q
new_ps << ot
end
end
end
end
ps = new_ps
new_ps = []
ps.each do |ps_n|
(0..9).each do |n|
if (temp = n + ps_n.s + ps_n.q) == ps_n.e
ot = ps_n.clone
ot.n = n
new_ps << ot
end
end
end
ps = new_ps
puts ps.size * 10 # multiplied by 10 as for each 0 <= R <= 9, the problem condition satisfies.
end
public static void main(String[] args) {
String s1 = "north";
String s2 = "east";
String s3 = "west";
String s4 = "south";
String result = "earth";
long s = System.currentTimeMillis();
solve(s1, s2, s3, s4, result);
System.out.println("Time: " + (System.currentTimeMillis()-s));
}
public static void solve(String s1, String s2, String s3, String s4, String result) {
Map<Integer, Map<Character, Integer>> map = new HashMap<Integer, Map<Character, Integer>>();
s1 = reverse(s1);
s2 = reverse(s2);
s3 = reverse(s3);
s4 = reverse(s4);
result = reverse(result);
for (int i = 0; i < 5; i++) {
Map<Character, Integer> t = new HashMap<Character, Integer>();
if (i < s1.length() && t.get((Character) s1.charAt(i)) != null) {
int c = t.get((Character) s1.charAt(i));
t.put((Character) s1.charAt(i), c + 1);
} else if(i < s1.length()){
t.put((Character) s1.charAt(i), 1);
}
if (i < s2.length() && t.get((Character) s2.charAt(i)) != null) {
int c = t.get((Character) s2.charAt(i));
t.put((Character) s2.charAt(i), c + 1);
} else if(i < s2.length()){
t.put((Character) s2.charAt(i), 1);
}
if (i < s3.length() && t.get((Character) s3.charAt(i)) != null) {
int c = t.get((Character) s3.charAt(i));
t.put((Character) s3.charAt(i), c + 1);
} else if(i < s3.length()) {
t.put((Character) s3.charAt(i), 1);
}
if (i < s4.length() && t.get((Character) s4.charAt(i)) != null) {
int c = t.get((Character) s4.charAt(i));
t.put((Character) s4.charAt(i), c + 1);
} else if(i < s4.length()) {
t.put((Character) s4.charAt(i), 1);
}
map.put(i, t);
}
int[] nos = new int[10];
for (int i = 0; i < 10; i++)
nos[i] = -1;
int[] alph = new int[26];
for (int i = 0; i < 26; i++)
alph[i] = Integer.MAX_VALUE;
int n = solutions(map, result.toCharArray(), 0, nos, alph, 0, 0, new ArrayList<String>());
System.out.println("Total = " + n);
}
public static int solutions(Map<Integer, Map<Character, Integer>> map, char[] res, int i, int[] nos, int[] alph,
int carry, int count, List<String> list) {
if (i == map.size()) {
if(carry == 0){
String str = "";
for(int l = 0; l < 26; l++){
if(alph[l] != Integer.MAX_VALUE){
str += ((char)('a'+l)) + ":" + alph[l] + " ";
}
}
if(!list.contains(str)){
list.add(str);
//System.out.println(str);
return count + 1;
}
return count;
}else{
return count;
}
}
Map<Character, Integer> m = map.get(i);
int p = 0;
for (Map.Entry<Character, Integer> en : m.entrySet()) {
char c = en.getKey();
int mul = en.getValue();
if (alph[c - 'a'] != Integer.MAX_VALUE) {
p += mul * alph[c - 'a'];
} else {
for (int g = 0; g < nos.length; g++) {
if (nos[g] == -1) {
nos[g] = g;
alph[c - 'a'] = g;
count = solutions(map, res, i, nos, alph, carry, count, list);
alph[c - 'a'] = Integer.MAX_VALUE;
nos[g] = -1;
}
}
}
}
for(int q = 0; q <= i; q++){
Map<Character, Integer> mh = map.get(q);
for (Map.Entry<Character, Integer> en : mh.entrySet()) {
char c = en.getKey();
if(alph[c -'a'] == Integer.MAX_VALUE)
return count;
}
}
p += carry;
if (alph[res[i] - 'a'] != Integer.MAX_VALUE && (p % 10) == alph[res[i] - 'a']) {
count = solutions(map, res, i + 1, nos, alph, (p / 10), count, list);
} else if (alph[res[i] - 'a'] != Integer.MAX_VALUE && (p % 10) != alph[res[i] - 'a']) {
return count;
} else if (alph[res[i] - 'a'] == Integer.MAX_VALUE && nos[p % 10] == -1) {
alph[res[i] - 'a'] = (p % 10);
nos[p % 10] = (p % 10);
count = solutions(map, res, i + 1, nos, alph, (p / 10), count, list);
alph[res[i] - 'a'] = Integer.MAX_VALUE;
nos[p % 10] = -1;
} else if (alph[res[i] - 'a'] == Integer.MAX_VALUE && nos[p % 10] != -1) {
return count;
}
return count;
}
public static String reverse(String str) {
char[] arr = str.toCharArray();
String rev = "";
for (int i = arr.length - 1; i >= 0; i--)
rev += arr[i];
return rev;
}
- md.etemad September 21, 2017