Paralysis Analysis - Part 2

-
The solution to the problem is this:

Word #1: PARALYSIS
Word #2: ANALYSIS

Best Split: PARALY * SIS (587893 * 141 = 82892913 with delta 228 (0.0000387826%) compared to ANALYSIS (82893141)))

First, it is impossible to find a way to split PARALYSIS in such a way that the multiplication of its two parts would arrive exactly at ANALYSIS. But it is possible to get very close, with a discrepancy of only 0.0000387826%.
The idea of how to solve this problem lies on few insights:
1) Brute-force is doable. Remember that we cannot have repeated digits, and we only have digits from 1-9 in the mix. Because of that we'll have a lower bound of 9!. In reality though, the loop might be stretched to 9^9, which is still doable (387,420,489).
2) The split of the words into two incurs into a simple binary and linear separation of the word PARALYSIS, which will only affect the constant of the algorithm by a factor of Len(PARALYSIS)-1 (or a factor of 8x), which even when multiplied by the worst-case in #a, still leads to a reasonably small number of combinations (around 3 billion). To give you an idea, in my own laptop a for-loop from 1 to 3B takes 7 seconds.
3) The other computations are very simple mathematical computations, and won't incur much into the overall execution time.

Code is below. In few seconds the answer pops-up. Now try taking into account the "zero" which wasn't allowed in the original problem.


using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Collections;

using System.IO;

 

namespace MathWord

{

    class Program

    {

        static void Main(string[] args)

        {

            if (args.Length != 2)

            {

                Console.WriteLine("MathWord.exe <word1> <word2>");

                return;

            }

 

            string word1 = args[0].ToUpper();

            string word2 = args[1].ToUpper();

            Hashtable letterMap = new Hashtable();

            Hashtable usedDigit = new Hashtable();

            long minDelta = Int64.MaxValue;

            string bestPart1 = "";

            string bestPart2 = "";

            string bestMapping1 = "";

            string bestMapping2 = "";

            string bestResult = "";

            string bestRightSideMapping = "";

 

            Console.WriteLine("Processing...");

            Process(word1,

                    word2,

                    0,

                    letterMap,

                    usedDigit,

                    "",

                    "",

                    ref minDelta,

                    ref bestPart1,

                    ref bestPart2,

                    ref bestMapping1,

                    ref bestMapping2,

                    ref bestResult,

                    ref bestRightSideMapping);

            Console.WriteLine("Done!");

            Console.WriteLine();

 

            if (bestMapping1.Length == 0 ||

                bestMapping2.Length == 0)

            {

                Console.WriteLine("No Solution!");

            }

            else

            {

                double deltaPerc = (minDelta * 100.0) / (Int64.Parse(bestMapping1 + bestMapping2));

 

                Console.WriteLine("Word #1: {0}", word1);

                Console.WriteLine("Word #2: {0}", word2);

                Console.WriteLine("Best Split: {0} * {1} ({2} * {3} = {4} with delta {5} ({6}%) compared to {7} ({8})))", bestPart1,

                                                                                                                          bestPart2,

                                                                                                                          bestMapping1,

                                                                                                                          bestMapping2,

                                                                                                                          bestResult,

                                                                                                                          minDelta,

                                                                                                                          deltaPerc.ToString("F10"),

                                                                                                                          word2,

                                                                                                                          bestRightSideMapping);

            }

        }

 

        static void Process(string word1,

                            string word2,

                            int currentPosition,

                            Hashtable letterMap,

                            Hashtable usedDigit,

                            string wordNumber1,

                            string wordNumber2,

                            ref long minDelta,

                            ref string bestPart1,

                            ref string bestPart2,

                            ref string bestMapping1,

                            ref string bestMapping2,

                            ref string bestResult,

                            ref string bestRightSideMapping)

        {

            //Base case

            if (currentPosition >= word1.Length + word2.Length)

            {

                CheckWordNumber(word1,

                                wordNumber1,

                                word2,

                                wordNumber2,

                                ref minDelta,

                                ref bestPart1,

                                ref bestPart2,

                                ref bestMapping1,

                                ref bestMapping2,

                                ref bestResult,

                                ref bestRightSideMapping);

 

                return;

            }

 

            //Induction

            int relativeCurrentPosition = 0;

            string currentWord = "";

 

            bool firstWord = false;

            if (currentPosition < word1.Length)

            {

                relativeCurrentPosition = currentPosition;

                currentWord = word1;

                firstWord = true;

            }

            else

            {

                relativeCurrentPosition = currentPosition - word1.Length;

                currentWord = word2;

                firstWord = false;

            }

 

            if (letterMap.ContainsKey(currentWord[relativeCurrentPosition]))

            {

                Process(word1,

                        word2,

                        currentPosition + 1,

                        letterMap,

                        usedDigit,

                        firstWord ? wordNumber1 + (string)letterMap[currentWord[relativeCurrentPosition]] : wordNumber1,

                        firstWord ? wordNumber2 : wordNumber2 + (string)letterMap[currentWord[relativeCurrentPosition]],

                        ref minDelta,

                        ref bestPart1,

                        ref bestPart2,

                        ref bestMapping1,

                        ref bestMapping2,

                        ref bestResult,

                        ref bestRightSideMapping);

            }

            else

            {

                //for (int i = (currentPosition == 0) ? 1 : 0; i < 10; i++)

                for (int i = 1; i < 10; i++)

                {

                    if (!usedDigit.ContainsKey(i))

                    {

                        letterMap.Add(currentWord[relativeCurrentPosition], i.ToString());

                        usedDigit.Add(i, true);

                        Process(word1,

                                word2,

                                currentPosition + 1,

                                letterMap,

                                usedDigit,

                                firstWord ? wordNumber1 + i.ToString() : wordNumber1,

                                firstWord ? wordNumber2 : wordNumber2 + i.ToString(),

                                ref minDelta,

                                ref bestPart1,

                                ref bestPart2,

                                ref bestMapping1,

                                ref bestMapping2,

                                ref bestResult,

                                ref bestRightSideMapping);

                        usedDigit.Remove(i);

                        letterMap.Remove(currentWord[relativeCurrentPosition]);

                    }

                }

            }

        }

 

        static void CheckWordNumber(string word1,

                                    string wordNumber1,

                                    string word2,

                                    string wordNumber2,

                                    ref long minDelta,

                                    ref string bestPart1,

                                    ref string bestPart2,

                                    ref string bestMapping1,

                                    ref string bestMapping2,

                                    ref string bestResult,

                                    ref string bestRightSideMapping)

        {

            long rightSide = Int64.Parse(wordNumber2);

            for (int i = 1; i < wordNumber1.Length; i++)

            {

                long part1 = Int64.Parse(wordNumber1.Substring(0, i));

                long part2 = Int64.Parse(wordNumber1.Substring(i));

                long delta = (long)Math.Abs((part1 * part2) - rightSide);

                if (delta < minDelta)

                {

                    bestPart1 = word1.Substring(0, i);

                    bestPart2 = word1.Substring(i);

                    bestMapping1 = wordNumber1.Substring(0, i);

                    bestMapping2 = wordNumber1.Substring(i);

                    bestResult = Convert.ToString(part1 * part2);

                    bestRightSideMapping = wordNumber2;

                    minDelta = delta;

                }

            }

        }

    }

}

 

Comments

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

Prompt Engineering and LeetCode

-
Image
With AI it becomes super interesting to try to "guide" it to solve a coding (LeetCode) problem. An example would be this one here:  The Knight’s Tour - LeetCode 2664. The Knight’s Tour Medium 11 0 Add to List Share Given two positive integers  m  and  n  which are the height and width of a  0-indexed  2D-array  board , a pair of positive integers  (r, c)  which is the starting position of the knight on the board. Your task is to find an order of movements for the knight, in a manner that every cell of the  board  gets visited  exactly  once (the starting cell is considered visited and you  shouldn't  visit it again). Return  the array   board   in which the cells' values show the order of visiting the cell starting from 0 (the initial place of the knight). Note that a  knight  can  move  from cell  (r1, c1)  to cell  (r2, c2)  if  0 <= r2 <= m - 1  and  0 <= c2 <= n - 1  and  min(abs(r1 - r2), abs(c1 - c2)) = 1  and  max(abs(r1 - r2), abs(c1 - c2)) = 2 .  
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more