21
\$\begingroup\$

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 , so the shortest answer in bytes per language wins.

\$\endgroup\$
4
  • 8
    \$\begingroup\$ Welcome to Code Golf Stack Exchange. This is a really interesting challenge, but could use some more example cases. \$\endgroup\$
    – Adám
    May 4 at 6:12
  • 5
    \$\begingroup\$ Welcome to Code Golf! I removed the programming-puzzle tag since it is for a totally different kind of challenges. Looks like a nice and well-specified challenge, though a few more test cases would definitely be helpful. If you have another challenge idea, please use the sandbox to get feedbacks before posting it to main. It is recommended to wait for at least 72 hours (3 days) to get enough feedback. \$\endgroup\$
    – Bubbler
    May 4 at 6:13
  • 3
    \$\begingroup\$ Sorry for my negligence, I will definitely use sandbox from next time, also I have added some more examples. Thanks for your kind suggestions. \$\endgroup\$ May 4 at 7:00
  • 6
    \$\begingroup\$ I had deleted my answer as it is incorrect. Suggested testcases: 1+9=0, 11+91=2, 15+85=0, 10+90=0 \$\endgroup\$
    – tsh
    May 4 at 16:49
10
\$\begingroup\$

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!

\$\endgroup\$
11
  • \$\begingroup\$ 153 \$\endgroup\$
    – l4m2
    May 4 at 15:09
  • \$\begingroup\$ Also yours fail [1,9,1] mine fail [1,9,19] \$\endgroup\$
    – l4m2
    May 4 at 15:15
  • \$\begingroup\$ No console.log(f( "9", "1", "19")) still return 3. Easy fix though \$\endgroup\$
    – l4m2
    May 4 at 15:38
  • \$\begingroup\$ Do console.log(f( "0", "0", "0")) fall into infinite loop? \$\endgroup\$
    – l4m2
    May 4 at 15:41
  • \$\begingroup\$ I pop my 3 bytes \$\endgroup\$
    – l4m2
    May 4 at 15:42
7
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ An absolutely brilliant algorithm. Particularly notable tricks include putting z in the front to allow simpler avoidance of insertion before the minus sign, and the use of for y in range(10*len(x)) with division and modulo to save bytes from a nested loop. Thank you. \$\endgroup\$
    – blhsing
    May 7 at 1:23
4
\$\begingroup\$

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)
\$\endgroup\$
4
  • \$\begingroup\$ For when 100k rep? :P \$\endgroup\$
    – RGS
    May 7 at 20:49
  • 1
    \$\begingroup\$ @RGS Will probably be a while tbh. Since my new job I barely codegolfed, since I have a lot less time in between work waiting for stuff (installations, Jenkins builds, project compilations, etc.), which is actually a good thing, but it does mean a significant amount of less time I want to spend on codegolfing. I almost never codegolf in my own time, since I have way too many other hobbies I enjoy more, so I used to do it a lot in between work at my previous job. But I'll still make an answers here and there, so I'll get to that 100k eventually. ;) \$\endgroup\$ May 8 at 10:29
  • 1
    \$\begingroup\$ I see :D enjoy your new job! \$\endgroup\$
    – RGS
    May 8 at 10:49
  • 1
    \$\begingroup\$ @RGS Thanks! I already am. :) Been working there for almost two months now, and enjoy it a lot. \$\endgroup\$ May 8 at 10:55
2
\$\begingroup\$

Charcoal, 52 50 bytes

⊞υθW⬤υ⁻Σκ⊗I⊟⪪κ=«≔υη≔⟦⟧υFηF⊕LθFχ⊞υ⁺⁺…κλμ✂κλ»I⁻L⊟υLθ

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.

W⬤υ⁻Σκ⊗I⊟⪪κ=«

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.

FηF⊕LθFχ

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

⊞υ⁺⁺…κλμ✂κλ

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

»I⁻L⊟υLθ

Output the number of digits inserted.

\$\endgroup\$
2
\$\begingroup\$

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).

\$\endgroup\$
1
\$\begingroup\$

Haskell, 125 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.