Inserting digits to satisfy equation

Question

You are given 3 non negative numbers: \$x\$, \$y\$ and \$z\$, and must minimize the number of digits (non negative) inserted at any place in the numbers \$x\$, \$y\$, or \$z\$ to make

$$x + y = z$$

(a clarification: you can add any non negative digit any number of time at any place )

(you can assume that \$x\$, \$y\$, \$z\$ and your final integers after insertion won't overflow the integer limit in your language)

Example:

$$x=1, y=10, z=30$$

$$1 + 10 = 30 $$ $$1(0) +1(2)0 = (1)30$$

i.e \$10+120 = 130\$

The minimum insertions is 3 here.

$$x=1 , y=1 , z=3$$

$$1 + 1 = 3 $$
$$(3)1 + 1 = 3(2) \;\text{or}\; 1 + 1(2) = (1)3$$

Here, the answer is 2.

$$x=11 , y=11 , z=33$$

$$11 + 11 = 33$$ $$11(2) + 1(2)1 = (2)33 \;\text{or}\; 1(2)1 + (2)11 = 33(2)$$

Here, the answer is 3.

$$x=3 , y=0 , z=0$$

$$3 + 0 = 0$$ $$3 + 0 = 0(3)$$

Here, the answer is 1,because as stated in earlier clarification, you can add any non negative digit any number of time at any place, so there can be leading zeroes too.

There can be multiple ways for same number of minimal insertion.

If possible while answering please write a short explanation of what you did. This is code-golf, so the shortest answer in bytes per language wins.

Answer 1

JavaScript (ES6), 164 bytes

Thanks to @l4m2 for identifying several bugs and suggesting the alternate version below

(x,y,z)=>(F=k=>(g=(k,s=z+`-${x}-`+y,n=9)=>eval(s.replace(/\d+/g,'"$&"'))?k&&[...s,0].some((_,i)=>g(k-1,s.slice(0,i)+n+s.slice(i)))||n&&g(k,s,n-1):1)(k)?k:F(k+1))(0)

Try it online!

How?

We build the string s with the pattern z-x-y and recursively attempt to insert k additional digits until eval(s) is 0.

Commented

(x, y, z) => (                 // main function taking (x, y, z)
  F = k => (                   // F is a recursive function taking a counter k
    g = (                      // g is a recursive function taking:
      k,                       //   k = number of digits to insert
      s = z + `-${x}-` + y,    //   s = expression string "z-x-y"
      n = 9                    //   n = next digit to insert
    ) =>                       //
    eval(s.replace(            // if the expression does not evaluate to 0:
      /\d+/g, '"$&"'           // (add quotes to prevent any number with a
    )) ?                       // leading 0 to be parsed as octal)
      k &&                     //   if k is not equal to 0,
      [...s, 0].some((_, i) => //   for each position i from 0 to len(s):
        g(                     //     do a recursive call to g:
          k - 1,               //       decrement k
          s.slice(0, i) + n +  //       insert n at position i
          s.slice(i)           //       (and implicitly restart with n = 9)
        )                      //     end of recursive call
      ) ||                     //   end of some()
      n &&                     //   if n is not equal to 0:
        g(k, s, n - 1)         //     do a recursive call to g with n - 1
    :                          // else:
      1                        //   success
  )(k)                         // initial call to g with the current value of k
  ?                            // if successful:
    k                          //   return k
  :                            // else:
    F(k + 1)                   //   try again with k + 1
)(0)                           // initial call to F with k = 0

---

JavaScript (Node.js), 158 bytes

A slower but 6 bytes shorter variant suggested by @l4m2

(x,y,z)=>(F=k=>(g=(k,s=z+`-${x}-`+y,i=~s.length*-10)=>k*i--?g(k-1,s.slice(0,t=i/10)+i%10+s.slice(t))|g(k,s,i):!eval(s.replace(/\d+/g,'"$&"')))(k)?k:F(k+1))(0)

Try it online!

Answer 2

Python 2, 161 257 bytes

def g(L):
 k=0;F="-%s %s %s"%L,
 while all(sum(map(int,X.split()))for X in F):k+=1;F=[x[:y/10+1]+`y%10`+x[y/10+1:]for x in F for y in range(10*len(x))]
 return k

Try it online!

-1 byte thanks to @ovs!

Takes in a tuple of 3 integers L, in order (z, x, y).

How it works:

F stores all insertions with k digits added (in the form "-z x y"). At each stage, we check if string X in F splits to three integers that satisfy the equality by evaluating the sum of (the integers in) X.split(). When going to the next stage, the +1 in the slicing prevents a digit from being inserted before the minus sign. The int conversion is to prevent any leading zero from being interpreted as an octal integer.

Answer 3

05AB1E, 33 bytes

∞.ΔI„+-S.ιSÐм.ø.œJs>ù9Ýyãδ.ιJ.E_à

Extremely slow brute-force approach, so it's barely unable to complete any of the test cases resulting in 3..

Try it online.

Here a slightly faster but incorrect approach to at least show the three test cases work as intended: Try it online. The difference is the õ.ø, which is Ðм.ø in the full program. The õ.ø surround the list of characters with a single leading/trailing empty string, whereas the Ðм.ø surrounds it with multiple empty leading/trailing strings (up to the amount of digits in the total input, plus 2 for the +-).

Explanation:

∞.Δ               # Find the first positive integer which is truthy for:
   I              #  Push the input-list [x,y,z]
    „+-S          #  Push character-pair ["+","-"]
        .ι        #  Interleave it with the input-list
                  #   i.e. [1,10,30] → [1,"+",10,"-",30]
          S       #  Convert it to a flattened list of characters
                  #   → [1,"+",1,0,"-",3,0]
           Ð      #  Triplicate this list
            м     #  Remove all characters in this list from the list,
                  #  leaving a list of empty strings of the same size
                  #   i.e. [1,"+",1,0,"-",3,0] → ["","","","","","",""]
             .ø   #  Surround the earlier list with these empty strings as 
                  #  leading/trailing items
                  #   → ["","","","","","","",1,"+",1,0,"-",3,0,"","","","","","",""]

The examples in the rest of the explanation uses a single empty leading/trailing string, since it's otherwise a bit too verbose. The actual functionality remains the same.

               .œ #  Get all partitions of this list
                  #   → [[[""],["1"],["+"],["1"],["0"],["-"],["3"],["0"],[""]],
                  #      [[""],["1"],["+"],["1"],["0"],["-"],["3"],["0", ""]],
                  #      ...,
                  #      [["","1","+","1","0","-","3","0",""]]]
                J #  Join each inner-most list together to a string
                  #   → [["","1","+","1","0","-","3","0",""],
                  #      ["","1","+","1","0","-","3","0"],
                  #      ...,
                  #      ["1+10-30"]]
   s              #  Swap so the current number is at the top of the stack
    >             #  Increase it by 1
                  #   i.e. 3 → 4
     ù            #  Only keep the partitions of that size
                  #   → [["","1","+","10-30"],
                  #      ["","1","+1","0-30"],
                  #      ...,
                  #      ["1+10-","3","0",""]]
   9Ý             #  Push list [0,1,2,3,4,5,6,7,8,9]
     yã           #  Get the current number's cartesian product of this list
                  #   i.e. 3 → [[0,0,0], [0,0,1], ..., [9,9,9]]
       δ          #  Apply on the two lists double-vectorized:
        .ι        #   Interleave the lists
                  #    → [[["",0,"1",0,"+",0,"10-30"],["",0,"1",0,"+",1,"10-30"],...],
                  #       [["",0,"1",0,"+1",0,"0-30"],["",0,"1",0,"+1",1,"0-30"],...],
                  #       ...,
                  #       [...,["1+10-",9,"3",9,"0",9,""]]]
          J       #  Join every inner-most list to a string
                  #   → [["010+010-30","010+110-30",...],
                  #      ["010+100-30","010+110-30",...],
                  #      ...,
                  #      [...,"1+10-93909"]]
           .E     #  Evaluate each as Python-code
                  #   → [[-10,90,...],
                  #      [80,90,...],
                  #      ...,
                  #      [...,-93898]]
             _    #  Check if any result is 0 (1 if 0; 0 otherwise)
              à   #  And take the flattened maximum to check if any was truthy
                  # (after which the result is output implicitly)

Answer 4

Charcoal, 52 50 bytes

⊞υθＷ⬤υ⁻Σκ⊗Ｉ⊟⪪κ=«≔υη≔⟦⟧υＦηＦ⊕ＬθＦχ⊞υ⁺⁺…κλμ✂κλ»Ｉ⁻Ｌ⊟υＬθ

Try it online! Link is to verbose version of code. Takes input as an "equation" i.e. 1+1=3. Quite slow but usually manages to compute answers of up to 3 on TIO. Edit: Tweaked to be slightly less slow. Explanation:

⊞υθ

Start with the initial equation.

Ｗ⬤υ⁻Σκ⊗Ｉ⊟⪪κ=«

Repeat while none of the equations add up. Charcoal has a builtin for taking the sum of all the strings of digits within a string, but this obviously gives x+y+z, so I compare that against 2z. (Using an evaluation function would fail if I ever inserted a leading zero anywhere.)

≔υη≔⟦⟧υ

Make a copy of the list so far so that I can empty it out.

ＦηＦ⊕ＬθＦχ

For each equation, each possible insertion point and each digit, ...

⊞υ⁺⁺…κλμ✂κλ

... insert the digit into the equation at that point and save the result.

»Ｉ⁻Ｌ⊟υＬθ

Output the number of digits inserted.

Answer 5

Ruby, 142 bytes

->*x{r=[a=x];3.times{|x|w=a[x];(w..?9+w).grep(/#{w.chars*".*"}/){|z|*b=a;b[x]=z;r<<b}}until eval"%s+%s==%s"%a=r.shift;a.join.size-x.join.size}

Try it online!

Input integers as strings, is very slow if the solution is 3 or more.

Quick explanation:

->*x{r=[a=x];

The arguments are in an array, we need to create a copy of that (a), and an array of possible solutions (r)

3.times{|x|w=a[x];(w..?9+w).grep(/#{w.chars*".*"}/){|z|*b=a;b[x]=z;r<<b}}

Add a single digit in all possible positions to each argument separately. Instead of interpolating strings, generate all numbers between the argument and the same number with a 9 prepended, and then filter using a regex (e.g.: if the argument is "11", find all numbers containing the regex /1.*1/ between 11 and 911)

until eval"%s+%s==%s"%a=r.shift;a.join.size-x.join.size}

Evaluate the expression using the first element of the array of possible solutions. If this is false, then repeat the process using this element as a starting point for the next iteration. We don't need to check for octal numbers since no 0 will be prepended to any number (and this solves also the case [0,0,0]) If the comparison is true, the result we need is the difference in length between the solution and the input arguments (concatenated).

Answer 6

Haskell, ¹²⁵ 120 bytes

f.pure.unwords
f l=last$1+f[take i s++d:drop i s|s<-l,i<-[0..length s],d<-show$56^7]:[0|0<-foldr1(-).map read.words<$>l]

Try it online!

The relevant function is f.pure.unwords, which takes as input a list [x,z,y]; integers are represented as strings.