Tchisla Solution Finder

There is a beautiful math puzzle game called Tchisla. The goal is to express a number with a single digit and math operations, using as few digit occurencies as possible.

For example, here is the optimal solution to express ‘100’ using ‘2’s:

100=((22-2)/2)^2

2 * (2 + 2 * (2 + 22))

A friend of mine struggled expressing ‘1024’ with only 3 eights and I thought that it is a good 1 hour task which I could use in interviews. The idea is quite simple: we will generate all possible expressions and then evaluate each of them.

It is pretty obvious that the number of possible expressions is infinite. Even using one digit ‘2’ we can use indefinite number of operators, like:

sqrt(2), sqrt(sqrt(2)), sqrt(sqrt(2!)), …

The first step is to create a class to represent one node of the evaluation tree:

public class Node
{
      public int? val;
      public Node? left;
      public Node? right;

      public Node(int val)
      {
            this.val = val;
      }

      public Node(Node left, Node right)
      {
            this.left = left;
            this.right = right;
      }

      public string[] GetVariants()
      {
            string[] prefixes = new string[] { "", "Sqrt", "-"};
            if (val.HasValue)
            {
                  return prefixes.Select(s => $"{s}({val.Value})").ToArray();
            }
            else
            {
                  var leftVariants = left!.GetVariants();
                  var rightVariants = right!.GetVariants();
                  return prefixes.SelectMany(s => leftVariants.SelectMany(l => rightVariants.SelectMany(r =>
                  new string[]{
                        $"{s}({l}+{r})",
                        $"{s}({l}-{r})",
                        $"{s}({l}*{r})",
                        $"{s}({l}/{r})",
                        $"{s}(Pow({l},{r}))",
                        })
            )).ToArray();
            }
      }

      public override string ToString()
      {
            if (val.HasValue)
            {
                  return val.Value.ToString();
            }
            else
            {
                  return $"({left!.ToString()}-{right!.ToString()})";
            }
      }
}

The Node class can contain either an integer value or two operands, left and right. The most important method is GetVariants(), which produces all possible expression variants for the given node. It combines all possible one-operand functions (-val, sqrt(val)) with all possible two-operand functions (val1+val2, val1*val2, pow(val1,val2)) and returns all the possible string expression corresponding to the given tree.

Let’s write the tree generator which will produce all possible expression trees for the given string of digits:

public class TreeGenerator
{
      public IEnumerable<Node> Generate(char digit, int count)
      {
            var str = new string(digit, count);
            return GetNodes(str);
      }

      public IEnumerable<Node> GetNodes(string str)
      {
            yield return new Node(Convert.ToInt32(str));
            for (int i = 1; i < str.Length; i++)
            {
                  var left = GetNodes(str.Substring(0, i));
                  var right = GetNodes(str.Substring(i));
                  foreach (var l in left)
                  {
                        foreach (var r in right)
                        {
                              yield return new Node(l, r);
                        }
                  }
            }

      }
}

The GetNodes() methods splits the input string in all possible ways and passed it recursively for the future processing.

And now we are ready for the final step: evaluate all the possible expressions and select only those which give us the right answer:

public class Node
{
      public int? val;
      public Node? left;
      public Node? right;

      public Node(int val)
      {
            this.val = val;
      }

      public Node(Node left, Node right)
      {
            this.left = left;
            this.right = right;
      }

      public string[] GetVariants()
      {
            string[] prefixes = new string[] { "", "Sqrt", "-"};
            if (val.HasValue)
            {
                  return prefixes.Select(s => $"{s}({val.Value})").ToArray();
            }
            else
            {
                  var leftVariants = left!.GetVariants();
                  var rightVariants = right!.GetVariants();
                  return prefixes.SelectMany(s => leftVariants.SelectMany(l => rightVariants.SelectMany(r =>
                  new string[]{
                        $"{s}({l}+{r})",
                        $"{s}({l}-{r})",
                        $"{s}({l}*{r})",
                        $"{s}({l}/{r})",
                        $"{s}(Pow({l},{r}))",
                        })
            )).ToArray();
            }
      }

      public override string ToString()
      {
            if (val.HasValue)
            {
                  return val.Value.ToString();
            }
            else
            {
                  return $"({left!.ToString()}-{right!.ToString()})";
            }
      }
}
using NCalc;

public class Calculator
{
      Node root;
      /// <summary>
      /// Initializes a new instance of the <see cref="Calculator"/> class.
      /// </summary>
      public Calculator(Node node)
      {
            this.root = node;
      }

      /// <summary>
      /// Get all possible variants to get the result.
      /// </summary>
      public IEnumerable<string> Calculate(int res)
      {
            var resultTarget = Convert.ToDouble(res);
            foreach (var v in this.root.GetVariants())
            {

                  Expression e = new Expression(v, NCalc.EvaluateOptions.NoCache);
                  if (!e.HasErrors())
                  {
                        var resultCurrent = Math.Round(Convert.ToDouble(e.Evaluate()), 4);
                        if (Math.Abs(resultCurrent - resultTarget) < 0.00001)
                        {
                              yield return v;
                        }
                  }
                  else
                  {
                        Console.WriteLine($"Error: {e.Error}");
                        Console.WriteLine($"Input: {v}");
                  }

            }
      }

      public override string ToString()
      {
            return this.root.ToString();
      }
}

We use the NCalc library, which evaluates a string and give us a result. The only trick here is the comparison. Since floating points calculations are involved, we have to compare values with some precision. 4 decimal places looks like a good enough approximation for the result.

And the very last point is to run calculation for our task and select the best result:

void solutions(char digit, int count, int result)
{

      var generator = new TreeGenerator();
      foreach (var node in generator.Generate(digit, count))
      {
            Calculator calc = new Calculator(node);
            var res = calc.Calculate(result).OrderByDescending(o => o.Length).ToArray();
            foreach (var v in res)
            {
                  Console.WriteLine($"{v}");
            }
      }

}
  solutions('8', 3, 1024);
Console.WriteLine("Finished.");

We get the results ordered by the length of the final expression. And here are the variants:

Sqrt(Pow(-(Sqrt(8)+Sqrt(8)),(8)))
(Pow(Sqrt(Sqrt(8)+Sqrt(8)),(8)))
Sqrt(Pow((Sqrt(8)+Sqrt(8)),(8)))