Make them sum to 10,000

Question

We've recently reached the threshold of 10,000 questions on PPCG. Hooray! Let's celebrate this with a simple challenge.

Input

Two integers \$A\$ and \$B\$, both in \$[1..9999]\$, such that \$A+B<10000\$.

Task

Your task is to add one single digit to one of these integers or one single digit to both of them such that \$A+B=10000\$. If adding a digit to both \$A\$ and \$B\$, it need not necessarily be the same digit.

The new digit can be added at the beginning, at the end or anywhere in the middle of the original integer. However, you can't add a leading zero.

Example:

For \$A=923\$, the following transformations are valid:

$$\color{red}1923\\92\color{red}73\\923\color{red}8$$

But these ones are invalid:

$$\color{red}{0}923\\\color{red}{10}923\\9\color{red}{4}2\color{red}{7}3$$

Given \$A=923\$ and \$B=72\$, there are two possible solutions:

$$923\color{red}8 + 7\color{red}62 = 10000\\92\color{red}73 + 72\color{red}7 = 10000$$

Output

You must print or output a list of all possible solutions.

For the above example, the expected output would be [[9238,762],[9273,727]].

Rules

• I/O can be processed in any reasonable, unambiguous format. You may use strings, lists of digits, etc. instead of integers.
• The input is guaranteed to have at least one solution.
• You are allowed not to deduplicate the output. However, it would be appreciated if the test code is deduplicating it with some post-processing, for instance in the footer section of TIO.
• This is a code-golf challenge.

Test cases

Input    --> Output

934, 654 --> [[9346,654]]

737, 628 --> [[7372,2628]]

9122, 88 --> [[9122,878]]

923, 72  --> [[9238,762],[9273,727]]

998, 3   --> [[9968,32],[9987,13]]

900, 10  --> [[9900,100],[9090,910]]    NB: solutions such as [9000,1000] are NOT valid
                                            (more than one digit added to 10)

363, 632 --> [[3673,6327],[3638,6362]]

288, 711 --> [[2881,7119],[2882,7118],[2883,7117],[2884,7116],[2885,7115],[2886,7114],
              [2887,7113],[2888,7112],[2889,7111]]

365, 635 --> [[365,9635],[1365,8635],[2365,7635],[3365,6635],[4365,5635],[5365,4635],
              [6365,3635],[7365,2635],[8365,1635],[9365,635],[3065,6935],[3165,6835],
              [3265,6735],[3465,6535],[3565,6435],[3665,6335],[3765,6235],[3865,6135],
              [3965,6035],[3605,6395],[3615,6385],[3625,6375],[3635,6365],[3645,6355],
              [3655,6345],[3675,6325],[3685,6315],[3695,6305],[3650,6350]]

Answer 1

Haskell, 99 97 82 81 bytes

^{-16 bytes thanks to Delfad0r (taking inputs as a list, using abusing that we don't need to deduplicate -> n can always be in [0,4] & using a clever combination of input-format and ap)!}

filter((==1e4).sum).mapM([read.(take n<>(c:).drop n)|c<-['0'..'9'],n<-[0..4]]<*>)

Try it online!

Answer 2

R, 96 bytes

function(a,b)(w<-grep(gsub("",".?",a?b),1:1e4?9999:0)?r<-1e4-w)[w+a<2&r+b<2]
"?"=paste
"+"=adist

Try it online!

Explanation (ungolfed)

function(a,b){
    # Regex inserting ".*": (998,3) => ".?9.?9.?8.? .?3.?"
  regex <- gsub("",".?",paste(a,b)) 
    # Positions matching in the whole vector of strings that add to 10K ("1 9999", "2 9998", "3 9997", "4 9996", ...)
  w <- grep(regex,paste(1:1e4,9999:0)) 
    # 10K minus these matching positions
  r <- 1e4-w 
    # Form position-string vector of ('pos1 10K-pos1', 'pos2 10K-pos2', ...)
  paste(w,r)[
  # Filter only those positions where the edit distance between the matched numbers and the originals are less than 2
    adist(w,a)<2 & adist(r,b)<2 
  ]
}

We assign ? to paste. That lets us do something cool: a<-b?c<-d does inline assignments within the paste call, which we couldn't do with any other operator than ?, since it has lower precedence than <-.

Now as @JoKing kindly pointed out, there can be cases like 900 10 where two insertions could take place such as 9100 8100. So we filter out matches where the number of characters in either number has increased by more than 1. The quick way to do this is with the Levenshtein edit distance adist which we bind to +.

Answer 3

Pyth, 28 27 25 24 22 20 bytes

fq^;4sT*FmvsmXLkdThl

Try it online here, or verify all the test cases here - the test suite deduplicates the result by prepending a {.

Input is as a list of strings.

fq^;4sT*FmvsmXLkdThldQ   Implicit: Q=eval(input()), T=10
                         Trailing d, Q inferred
         m           Q   Map each input string, as d, using:
                   ld      Take the length of d
            m     h        Map 0 to the above (inclusive), as k, using:
             X  d            Insert into d...
               k             ... at position k...
              L  T           ... each number [0-9]
           s               Flatten the result
          v                Convert each back to an integer
       *F                Take the cartesian product of the result
                         (this generates all possible pairs of mutated numbers)
f                        Keep the pairs, as T, where...
     sT                  ... the sum of the pair...
 q                       ... is equal to...
  ^;4                    ... 10,000 (; == 10 here, so this is 10^4)

Edit 4: Saved another 2 bytes, thanks to Mr Xcoder - v vectorises by default, and L uses m underneath, so mapping over range is implied, making the U unneccesary too

Edit 3: Introduced to global use of ; operator to retain access to 10 to save 2 bytes, thanks to FryAmTheEggman and issacg:

fq^T4sT*FmvMsmXLkdUThl

Edit 2: I forgot the sum operator exists, how embarassing...

Edit 1: Previous version accepted a list of integers as input, performing string conversions manually, for 27 bytes:

fq10000+FT*FmvMsmXLk`dUThl`

Answer 4

Perl 6, 64 bytes

->\a{grep {all (a Z~$_)X~~/^(.*)(.*)$0.?$1$/},(^1e4 Z(1e4...1))}

Try it online!

This is a port of G B's answer using a regex to check if the numbers are valid. Thanks to nwellnhof for porting it.

Old answer, 127 110, 88 bytes

-22 bytes thanks to nwellnhof!

->\a{grep {all ~<<a Z∈.map:{.comb.combinations(.comb-1..*)>>.join}},(^1e4 Z(1e4...1))}

Try it online!

Anonymous code block that takes in a list of two numbers and returns a list of pairs of numbers.

Rather than fiddle about with inserting the digits in, this solution checks every combination of numbers that sum to 10000 and filters that the given numbers are part of the pair.

Explanation:

->\a{  # Anonymous code block that takes an argument a
     grep ... ,(^1e4 Z(1e4...1))    # Filter from all pairs that add to 10000
         {      ~<<a     # Stringify the contents of a
                     .map:{      # Map the pair to
                           .comb  # The digits of the number
                           .combinations(.comb-1..*)  # The combinations of the digits
                           >>.join  # Each combination joined
                           # Note that combinations preserve order
                           # "123" -> (12,13,123)
                          }
          all       Z∈   # Zip that each element of a is an element of the combination
         }
}

Answer 5

R, 179 161 150 144 bytes

function(a,b,w=g(a),r=rep(g(b),e=1e4))paste(w,r)[w+r==1e4]
g=function(x,n=sum(x|1)){for(i in 0:n)for(j in 0:9)F=c(F,append(x,j,i)%*%10^(n:0));F}

Try it online!

35 bytes saved by @JayCe and @Giuseppe.

Explanation

Helper function g gets all possible insertions.

g <- function(x,            # Input vector of digits
              n=sum(x|1)    # Length of x
              ) {
  for(i in 0:n)             # i is the insertion point
    for(j in 0:9)           # j is a digit from 0 to 9
      # Dot product of vector of digits with insert and 10^(n:0) performs the
      # conversion to integer (and gets rid of the leading 0s)
      F=c(F,append(x,j,i)%*%10^(n:0))  # F is a non-reserved built-in alias to FALSE (numerically 0)
  F
}

Main function.

f <- 
function(a,                 # Input vectors of digits
         b,
         w=g(a),            # Get all possible insertions for a
         r=rep(g(b),e=1e4)  # Insertions for b replicated 1e4 times each
         )
  paste(w,r)[w+r==1e4]      # paste and w+r recycle w to match length of r
                            # Lots of duplication!

I've noticed after the fact that this is essentially the same logic as the Pyth answer.

Answer 6

Ruby, 93 91 bytes

->a,b{(1..r=10000).map{|x|/^(.*)(.*:)\1.?\2(.*)(.*):\3.?\4$/=~[a,x,b,y=r-x]*?:&&[x,y]}-[p]}

Try it online!

Try every single number up to 10000, and use the regex to check if the numbers match.

Answer 7

Jelly, 30 bytes

DµJṬ€k€jþ9Ż¤;9R¤;€$ḌF)ŒpS=ȷ4ƊƇ

Try it online!

Kind of clumsy because Jelly has no insertion.

Explanation

                                   Given [a, b].
Dµ                   )             Get [digits(a), digits(b)] then map:
  JṬ€k€jþ9Ż¤;9R¤;€$ḌF                Generate all the insertions.
                      Œp           Cartesian product: get all pairs.
                        S=ȷ4ƊƇ     Filter for: sum equal to ȷ4 (10000).

                       Given e.g. [6,3,5]:
J                      Get [1,2,3].
 Ṭ€                    Get [[1], [0,1], [0,0,1]].
   k€                  Split input with these: gets us
                         [[6],[3,5]] , [[6,3],[5]] , [[6,3,5],[]]
     jþ9Ż¤             Join table-wise with [0..9]
                         → [[[6,0,3,5], [6,3,0,5], [6,3,5,0]],
                            [[6,1,3,5], [6,3,1,6], [6,3,5,1]], …]
          ;9R¤;€$      Append the prefixings of the input by [1..9].
                           [[1,6,3,5], [2,6,3,5], [3,6,3,5]]…
                 ḌF    Undigits all, and flatten.

Answer 8

Python 3, 165 160 153 125 117 bytes

• Saved 5 bytes thanks to @JackBrounstein suggestion to remove set from the return value, as the output can contain duplicates.
• Saved 7 by replacing range(len(s)) with range(5).
• Saved 23 bytes thanks to @Eric Duminil's suggestion to replace itertools with nested list comprehensions (and removing a space).
• Saved 8 thanks to @Jo King's suggestion to replace nested list comprehension with a single loop and modulus operator.

Using itertools and a simple helper function. Accepts strings as input, returns a set of ints as output.

c=lambda s:[int(s[:i%5]+str(i//5)+s[i%5:])for i in range(50)]
lambda a,b:{(i,j)for i in c(a)for j in c(b)if i+j==1e4}

Answer 9

PHP, 162 159 bytes

lovely example for a generator function!

function f($n){for($n+=.1;$n>=1;$n/=10)for($d=-1;$d++<9;)yield strtr($n,".",$d)/10|0;}foreach(f($argv[1])as$x)foreach(f($argv[2])as$y)$x+$y-1e4||print"$x+$y\n";

takes input from command line arguments; prints duplicates. Run with -nr '<code> or try it online.

Answer 10

Pyth, 18 bytes

fqsT^;4*FsMvXLRRTT

Demonstration, test suite (test suite is deduplicated with leading {).

The input is in the form of a list of two strings.

XLRRTT: L and R perform nested maps. Since there are 3 of them, we will perform a triply nested map of the X function. In this case, the X function will insert a character at a designated position into a string.

The string is the input, which is implicit and placed by the first R. The character ranges over 0 ... 9, so we have all possible inserted digits, and is placed by the L. The range is given by T, which is implicitly set to 10, which is implicitly treated as [0 ... 9]. The position ranges over 0 ... 9, which is sufficient, because inserting a number after the 10th position will never be useful. Duplicate results are fine. The range is placed by the second R, and given by the second T.

v: Nested cast strings to ints.

sM: Flatten the second level of lists, leaving us with a list of all possible numbers after digit insertion, for each of the input numbers.

*F: Take the Cartesian product of the two lists of possible numbers.

fqsT^;4: Filter on the pairs whose product is 10000. ; takes the value of 10 here, as T is in use as the filter variable, and ; always as the value of the variable which is in use.

Answer 11

Japt, 30 29 25 23 bytes

Takes input as an array of strings, outputs an array of arrays of strings.

£L²ôs f_à øX
rï k@L²aXx

Try it

---

Explanation

£L²ôs f_à øX
£                :Map each X
 L               :  100
  ²              :  Squared
   ô             :  Range [0,L²]
    s            :  Convert each to a string
      f_         :  Remove elements that return false
        à        :    All combinations of current element
          øX     :    Contains X?
rï k@L²aXx
r                :Reduce by
 ï               : Cartesian product
   k@            :Remove each X that returns true (not 0)
     L²          :  100 squared
      a          :  Absolute difference with
        Xx       :   X reduced by addition
      

Answer 12

Javascript (Node) - 183 136 123 Bytes

123 Bytes thanks to Shaggy

a=>b=>(o={},g=(s,h)=>[...s+0].map((y,x)=>{for(y=10;y--;)h(s.slice(0,x)+y+s.slice(x))}))(a,x=>g(b,y=>1e4-x-y?0:o[+x]=+y))&&o

136 Bytes thanks to Arnauld

e=(h,c,i=h.length+1,j)=>{for(;i--;)for(j=10;j--;)c(h.slice(0,i)+j+h.slice(i))}
f=(a,b,c=[])=>e(a,n=>e(b,m=>1E4-n-m||c.push([+n,+m])))||c

Old Code

Not proud of it, but figured I'd submit anyways. Creates a string prototype function akin to map which takes up the bulk of the bytes. Function just iterates through both permutations, and finds when 1000-a-b is 0. Takes input as strings.

String.prototype.e=function(c){let h=this,L=h.length,i,j;for(i=0;i<=L;i++)for(j=0;j<=9;j++)c(h.slice(0,i)+j+h.slice(i,L));}
f=(a,b,c=[])=>a.e(n=>b.e(m=>1E4-n-m?c:c.push([+n,+m])))?c:c

Try it online!

Ungolfed

String.prototype.e=function(c) {
  let h=this,L=h.length,i,j;
  for(i=0;i<=L;i++)
    for(j=0;j<=9;j++)
      c(h.slice(0,i)+j+h.slice(i,L));
}
f=(a, b, c=[]) =>
  a.e(n =>
    b.e(m =>
      1E4-n-m ? c : c.push([+n,+m])
    )
  ) ? c : c

Answer 13

Jelly, 23 bytes

œcL’$$€ċ"⁹o⁼"Ạ
ȷ4ḶṚĖDçƇ

A monadic link accepting a list of lists of digits
(e.g. for the example of 923 and 72 the input is [[9,2,3],[7,2]])

Try it online! (footer makes it so I/O is a pair of two integers in and a [formatted] list of pairs of integers out)

Or see the test-suite.

How?

Checks all the pairs of "numbers" (lists of digits) which sum to 10000 for validity by forming all ways to choose n-1 digits from those "numbers" maintaining order; and keeps those which are valid (where validity also allows for the "number" under test to be equal to the original "number").

œcL’$$€ċ"⁹o⁼"Ạ - Link 1, is piar valid?: pairToCheck, originalInputPair
      €        - for each list of digits in pairToCheck: e.g. [9,2,3]
     $         -   last two links as a monad:
    $          -     last two links as a monad:
  L            -       length                                 3
   ’           -       decremented                            2
œc             -     choices of that many items               [[9,2],[9,3],[2,3]]
         ⁹     - chain's right argument (originalInputPair)
        "      - zip with: (i.e. apply the following f(x,y) *respectively* across the results above and the originalInputPair)
       ċ       -   count occurrences
            "  - zip with (this time with an implicit right argument of originalInputPair)
           ⁼   -   equal (non-vectorising version)
          o    - locgical OR (vectorising version) i.e. we now have: [OR(isOneDigitLonger(item1),isEqual(item1)), OR(isOneDigitLonger(item2),isEqual(item2))]
             Ạ - all?

ȷ4ḶṚĖDçƇ - Main Link: list (pair) of lists of digits
ȷ4       - literal 10^4 -> 10000
  Ḷ      - lowered range -> [0,1,2,...,9998,9999]
   Ṛ     - reversed -> [9999,9998,...,2,1,0]
    Ė    - enumerate -> [[1,9999],[2,9998],...,[9998,2],[9999,1],[10000,0]] (N.B. last is redundant, but this does not matter)
     D   - to decimals -> [[[1],[9,9,9,9]],[[2],[9,9,9,8]],...,[[9,9,9,8],[2]],[[9,9,9,9],[1]],[[1,0,0,0,0],[0]]]
       Ƈ - filter keep those for which this is truthy:
      ç  -   call last link as a dyad (with a right argument of the pair of lists of digits)

Answer 14

Stax, 24 bytes

⌐çΘ♠╖øû°-h∟ñµ%üw▲∞Ç╫[½π=

Run and debug it

Those program takes its two inputs as an array of strings, like this.

["934", "654"]

Answer 15

Charcoal, 33 bytes

ΦＥ×χφＩ⟦ι⁻×χφι⟧⌊Ｅι№Ｅ⊕ＬλΦλ⁻ξρ§⟦θη⟧μ

Try it online! Link is to verbose version of code. Explanation:

   χ                                10
    φ                               1000
  ×                                 Multiply
 Ｅ                                  Map over implicit range
       ι    ι                       Current value
        ⁻×χφ                        Subtract from 10000
      ⟦      ⟧                      Pair of values
     Ｉ                              Cast to string
Φ                                   Filter
                ι                   Current pair
               Ｅ                    Map
                     λ              Current value
                    Ｌ               Length
                   ⊕                Increment
                  Ｅ                 Map over implicit range
                       λ            Current value
                      Φ             Filter over characters
                         ξ          Range value
                          ρ         Character index
                        ⁻           Subtract
                            ⟦θη⟧    Original inputs as a list
                                μ   Index of current value
                           §        Get input at that index
                 №                  Count matching values
              ⌊                     Minimum
                                    Implicitly print each pair double-spaced

In case you didn't understand that, it runs through all the pairs of values that add to 10000 (as strings), then counts how many times each input matches against the result of deleting up to 1 character from the respective value. If the minimum count is nonzero then both inputs matched and this is a possible solution.

Answer 16

Ruby, 110 bytes

Accepts strings as input, returns an array of array of integers.

Based on the python version. For a given integer, C creates an array of numbers that can be created by adding a digit.

The lambda iterates over every possible pair and selects the one whose sum is 10000.

C=->n{(0..49).map{|i|([n[0...i%5],i/5,n[i%5..-1]]*'').to_i}}
->(a,b){C[a].product(C[b]).select{|i,j|i+j==1e4}}

Try it online!

Answer 17

05AB1E (legacy), 36 bytes

0ìε.œʒg3‹}εU9ÝεXDgiìësý}}}˜}`âʒOT4mQ

Can without a doubt be golfed substantially.. Especially inserting the digits, including a leading/trailing one.

Try it online or verify all test cases (ê in the footer is to Uniquify & Sort).

Explanation:

0ì                            # Prepend a 0 before each of the input numbers
  ε                        }  # Map each to:
   .œ                         #  Take all possible partitions
     ʒg3‹}                    #  Only keep those of length 1 or 2
          ε              }    #  Map each partition to:
           U                  #   Pop and store the partition in variable `X`
            9Ý                #   List in the range [0, 9]
              ε         }     #   Map each of those digits to:
               X              #    Get the variable `X`
                Dgi           #    If it's a single number (length == 1):
                   ì          #     Prepend `X` before this digit
                  ë           #    Else (length == 2):
                   sý         #     Join both numbers in `X` with the current digit
                  }           #    Close the if-else
                          ˜   #   Flatten the list of lists
`                             # Now push both lists to the stack
 â                            # Create all possible pairs (cartesian product)
  ʒ                           # Filter this list of pairs by:
   O                          #  Take the sum of the two numbers
    T4m                       #  Push 10000 (10^4)
       Q                      #  And check if they are equal

Answer 18

Vyxal, 43 bytes

⌐ƛ⟨⟩n£¥Lʀ(x|n¬₀r(¥CC←x nSṀṅIJ));ḣhẊ'∑k2=   

Try it Online! Takes input of the form: "a,b"

Explanation:

?⌐ƛ⟨⟩n£¥Lʀ(x|n¬₀r(¥CC←x nSṀṅIJ));ḣhẊ'∑k2= # full program
?⌐                                       # split implicit input on ","
  ƛ⟨⟩n£¥Lʀ(x|n¬₀r(¥CC←x nSṀṅIJ));         # "insert" lambda map over input
                                ḣh       # unlist them
                                  Ẋ      # cartesian product [a,b]*[c,d]=[[a,c],[a,d],[b,c],[b,d]]
                                   '∑k2  # filter lambda, sum of pair == 10000

The insert lambda can definitely be improved, but I am having trouble figuring out a way to map it instead of explicitly loop over it.

Answer 19

Jelly, 25 bytes

LŻœṖ€z⁶ZjþØDVẎṢḊ)p/S⁼ȷ4ƊƇ

Try it online!

Not the shortest Jelly solution here but maybe someone can golf this? I am stumped