IBM Ponder This July 2018: Obscure Triplet

The IBM Ponder This are fun coding/math/logic challenges that are sponsored by IBM Haifa on a monthly basis, and that's been going on for several years now. Some challenges are really obscure and complex, others can be solved with the help of some programming language. I've managed to solve three in the past - the prize is just bragging rights with your name posted on their challenge pages:

http://www.research.ibm.com/haifa/ponderthis/challenges/October2016.html
http://www.research.ibm.com/haifa/ponderthis/challenges/September2016.html
https://www.research.ibm.com/haifa/ponderthis/challenges/October2014.html

The latest one was posted on July 2018, and this is it: http://www.research.ibm.com/haifa/ponderthis/challenges/July2018.html:

"
This month's challenge is based on a riddle I heard from Odelia Moshe Ostrovsky (thanks!).

Let's call a triplet of natural numbers "obscure" if one cannot uniquely deduce them from their sum and product. For example, {2,8,9} is an obscure triplet, because {3,4,12} shares the same sum (19) and the same product (144).

Find a triplet of ages {a,b,c} that is obscure and stays obscure for three more years: {a+1,b+1,c+1}, {a+2,b+2,c+2} and {a+3,b+3,c+3}.
"

Here is the approach I took:
  • Assume that we'll be able to find the answer by trying the range 1<=a<=b<=c<=100. This was just an initial assumption to minimize computational complexity
  • Build a cache for all combinations of (a,b,c) based on the key which is made of (a+b+c)_(a*b*c)
  • With the cache built, go thru all the (a,b,c) again. Lookup the cache to see if the upcoming years are also obscure. If so, you found the solution
And with that approach, we're actually able to find a solution!!!

Found: 7 30 54
For 7 30 54: (7 30 54) (10 18 63) 
For 8 31 55: (8 31 55) (10 22 62) 
For 9 32 56: (9 32 56) (12 21 64) 
For 10 33 57: (15 19 66) (10 33 57) 

Code is below, cheers, Boris.


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace IBMPonderThisJune2018
{
class Program
{
static void Main(string[] args)
{
Hashtable sumMul = new Hashtable();

long MAX = 100;
int nYears = 3;
int seed = 1;

Console.WriteLine("Pre-processing...");
for (long a = seed; a <= MAX; a++)
{
for (long b = a + 1; b <= MAX; b++)
{
for (long c = b + 1; c <= MAX; c++)
{

string key1 = GetKey(a, b, c);
if (!sumMul.ContainsKey(key1))
{
Hashtable triple = new Hashtable();
triple.Add(a.ToString() + "_" + b.ToString() + "_" + c.ToString(), true);
sumMul.Add(key1, triple);
}
else
{
Hashtable triple = (Hashtable)sumMul[key1];
triple.Add(a.ToString() + "_" + b.ToString() + "_" + c.ToString(), true);
sumMul[key1] = triple;
}
}
}
}
Console.WriteLine("Done");
Console.WriteLine("Processing");

string key = "";
for (long a = seed; a <= MAX; a++)
{
for (long b = a + 1; b <= MAX; b++)
{
for (long c = b + 1; c <= MAX; c++)
{
bool found = true;
for (int i = 0; i < nYears + 1; i++)
{
key = GetKey(a + i, b + i, c + i);
if (sumMul.ContainsKey(key) && ((Hashtable)sumMul[key]).Count > 1)
{
continue;
}
else
{
found = false;
break;
}
}

if (found)
{
Console.WriteLine("Found: {0} {1} {2}", a, b, c);
for (int i = 0; i < nYears + 1; i++)
{
Console.Write("For {0} {1} {2}: ", a + i, b + i, c + i);
key = GetKey(a + i, b + i, c + i);
Hashtable triple = (Hashtable)sumMul[key];
foreach (string k in triple.Keys)
{
string[] parts = k.Split('_');
Console.Write("({0} {1} {2}) ", parts[0], parts[1], parts[2]);
}
Console.WriteLine();
}
return;
}
}
}
}
}

static string GetKey(long a, long b, long c)
{
long sum = a + b + c;
long product = a * b * c;
return sum.ToString() + "_" + product.ToString();
}
}
}

Comments

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons