# Game programmer Interview question

This topic is 3437 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

1. Write a function that given a string of digits and a target value, prints where to put +'s and *'s between the digits so they combine exactly to the target value. Note there may be more than one answer, it doesn't matter which one you print. Examples: "1231231234",11353 -> "12*3+1+23*123*4" "3456237490",1185 -> "3*4*56+2+3*7+490" "3456237490",9191 -> "no solution" [Edited by - srikanthpv on November 21, 2008 2:20:36 AM]

##### Share on other sites
Quote:
 Original post by srikanthpv1. Write a function that given a string of digits and a target value, prints where to put +'s and *'s between the digits so they combine exactly to the target value. Note there may be more than one answer, it doesn't matter which one you print.Examples:"1231231234",11353 -> "12*3+1+23*123*4""3456237490",1185 -> "3*4*56+2+3*7+490""3456237490",9191 -> "no solution"

I hate this kind of questions, last year i got a game interview where they gave me 1 hour to answer a bunch of question like this...

I answer as fast as possible to their questions (15minutes)... maybe not everything right... but i prefer a good conversation....

##### Share on other sites
I was thinking the same way...It took me 2 hours to reach something close by...But i dont think that guy was satisfied with it though...I am still working on the code...Will come out with it in a day...

##### Share on other sites
how is this even a interview?? If someone told me they where going to interview me and asked me this, I'd be pissed.

##### Share on other sites

Hey bro this was the easiest of the lot i got...
Good one's are yet to come...M just trying to analyze this 1 fist...

##### Share on other sites
wait a moment...
I can easilly make up a simple algorithm that will eventually reach out but it will take forever...

kinda like

"abcdefg" ->
a+b+c+d+e+f+g ?
ab+c+d+e+f+g ?
abc+d+e+f+g ?
abcd+e+f+g ?
abcde+f+g ?> too big then
abcd+ef+g ?
abcd+efg ? not big enough then
...

but that is crap... there should be a better algorithm, no?
maybe
X / a > or <?
X / ab > or <?

no.. I cant figure it out...
whats the answer on this one?

Yours truly
K

##### Share on other sites
Does this scream "genetic programming" to anyone else? [smile]

EDIT: At any rate, as a quick and dirty solution I would probably construct a binary tree out of the digits, and iterate all the permutations of node operations looking for solutions. For a string of length N there are N-1 nodes and 3 operators (+, *, and "concat"), which is 3N-1 solutions. So not too many for a small number of digits (19683 for 10 digits), but it grows fast!

[Edited by - Zipster on November 21, 2008 5:31:39 AM]

##### Share on other sites
Here is mine in C# - took about 20 minutes.

using System;using System.Collections.Generic;using System.Linq;using System.Text.RegularExpressions;namespace ConsoleApplication2{    class Program    {        static IEnumerable<string> AllMyThingies(string input)        {            return AllMyThingies(input, 1);        }        static IEnumerable<string> AllMyThingies(string input, int offset)        {            if (offset < input.Length)            {                IEnumerable<string> a = AllMyThingies(input, offset + 1);                IEnumerable<string> b = AllMyThingies(input.Insert(offset, "+"), offset + 2);                IEnumerable<string> c = AllMyThingies(input.Insert(offset, "*"), offset + 2);                IEnumerable<string> all = a.Concat(b).Concat(c);                foreach (string v in all)                    yield return v;            }            yield return input;        }        static void Main()        {            foreach (string s in Thingy("3456237490", 1185))                Console.WriteLine(s);            Console.WriteLine("Done");            Console.ReadLine();        }        static long ParseMathString(string input)        {            Regex mult = new Regex("[0-9]+\\*[0-9]+");            Regex add = new Regex("[0-9]+\\+[0-9]+");            input = RegexReplace(mult, input);            input = RegexReplace(add, input);            return long.Parse(input);        }        static long ParseWeinerMathString(string input)        {            string[] s = input.Split(new char[] { '+', '*' });            if (s.Length == 1)                return long.Parse(input);            else if (s.Length > 2)                throw new ArgumentException("Oh poopies!");            else            {                long a = long.Parse(s[0]);                long b = long.Parse(s[1]);                char op = input[s[0].Length];                if (op == '+')                    return a + b;                else if (op == '*')                    return a * b;                else                    throw new ArgumentException("Oh poopies^2!");            }        }        static string RegexReplace(Regex regex, string input)        {            Match match;            while ((match = regex.Match(input)).Value.Length > 0)            {                long result = ParseWeinerMathString(match.Value);                input = input.Replace(match.Value, result.ToString());            }            return input;        }        static IEnumerable<string> Thingy(string input, long target)        {            foreach (string s in AllMyThingies(input))            {                if (ParseMathString(s) == target)                    yield return s;            }        }    }}

Basically, it puts a * and + in every place possible, then parses it using the ParseMathString() for complex strings and ParseWeinerMathString() for simple operations (a+b or a*b). Took 1 second to find every possible combination for "1231231234" = 11353;

And if you were wondering - yes, this is how I really program. Like it? I'm for hire!

##### Share on other sites
It's just a search space and a relatively small one. Being small a naive a try every possible combination would work well enough. At each point you could easily evaluate whether is might be possible to hit the goal (multiply up all remaining numbers) or whether you'd already blown it (add up all remaining numbers) With larger strings A* might perform quite well.

Personally as an interviewer I'd be far more interested in discussing possible techniques to solve the problem than any actual code produced. Perhaps for a junior position I would want to see code but for regular and senior programmers I think this is largely wasting peoples time.

##### Share on other sites
Well, if anyone is interested, I rewrote my piece of unreadable crap. It now takes about 100ms. Pretty much the same algorithm, but I redid the parser - now it just converts all substrings into longs once, then works with longs the rest of the way. Also, made it abort early on values too large.

using System;using System.Collections.Generic;using System.Diagnostics;using System.Linq;namespace ConsoleApplication2{    class Program    {        const long opA = -1;        const long opM = -2;        static long _target;        static int _targetLen;        static string _targetStr;        static IEnumerable<string> AllMyThingies(string input)        {            return AllMyThingies(input, 1);        }        static IEnumerable<string> AllMyThingies(string input, int offset)        {            if (offset < input.Length)            {                IEnumerable<string> a = AllMyThingies(input, offset + 1);                IEnumerable<string> b = AllMyThingies(input.Insert(offset, "+"), offset + 2);                IEnumerable<string> c = AllMyThingies(input.Insert(offset, "*"), offset + 2);                IEnumerable<string> all = a.Concat(b).Concat(c);                foreach (string v in all)                    yield return v;            }            yield return input;        }        static void Main()        {            Stopwatch w = new Stopwatch();            w.Start();            foreach (string s in Thingy("3456237490", 1185))                Console.WriteLine(s);            w.Stop();            Console.WriteLine(w.ElapsedMilliseconds);            Console.ReadLine();        }        static long ParseMathString(string input)        {            string[] strs = input.Split(new char[] { '+', '*' });            foreach (string s in strs)            {                if ((s.Length > _targetLen) || (s.Length == _targetLen && s[0] > _targetStr[0]))                    return -1;            }            List<long> values = new List<long>(strs.Length * 2);            int offset = -1;            for (int i = 0; i < strs.Length - 1; i++)            {                values.Add(int.Parse(strs));                offset += strs.Length + 1;                char c = input[offset];                if (c == '+')                    values.Add(opA);                else if (c == '*')                    values.Add(opM);            }            values.Add(long.Parse(strs[strs.Length - 1]));            if (!UBERPARSEM(values))                return -1;            if (!UBERPARSEA(values))                return -1;            return values[0];        }        static IEnumerable<string> Thingy(string input, long target)        {            _target = target;            _targetStr = target.ToString();            _targetLen = _targetStr.Length;            foreach (string s in AllMyThingies(input))            {                if (ParseMathString(s) == target)                    yield return s;            }        }        static bool UBERPARSEA(List<long> lala)        {            for (int i = 1; i < lala.Count; i += 2)            {                if (lala == opA)                {                    long nachos = lala[i - 1] + lala[i + 1];                    if (nachos > _target)                        return false;                    lala[i - 1] = nachos;                    lala.RemoveRange(i, 2);                    return UBERPARSEA(lala);                }            }            return true;        }        static bool UBERPARSEM(List<long> lala)        {            for (int i = 1; i < lala.Count; i += 2)            {                if (lala == opM)                {                    long nachos = lala[i - 1] * lala[i + 1];                    if (nachos > _target)                        return false;                    lala[i - 1] = nachos;                    lala.RemoveRange(i, 2);                    return UBERPARSEM(lala);                }            }            return true;        }    }}

Seeing as all the ParseMathString() calls now only take about 20-30ms, looks like the only place to really improve now is to just make less strings... checking every combination is clearly not ideal.

• 12
• 9
• 13
• 41
• 15