# Make them sum to 10,000

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\$$.

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 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]]

• It’s not a simple challenge if I can’t type it out and be confident it works while in my car. ;p – Quintec Sep 28 '18 at 11:47
• @Quintec I'd recommend against typing anything while you're in your car. :p – Arnauld Sep 28 '18 at 11:48
• @Arnauld He didn't say he's the driver. ;-) (Serious note: 4 off-topic comments so far, my 3-comment handicap for those purposes is beeping loudly. :P) – Erik the Outgolfer Sep 28 '18 at 11:51
• When jelly solutions take more than 20 bytes it’s a tough challenge! – Regis Portalez Sep 29 '18 at 14:39
• output a list of all possible solutions Oh bummer. That'd be difficult for my Runic language. I could probably write a program that could output a solution! – Draco18s Sep 29 '18 at 16:59

# 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!

# 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


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
]
}


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

• Thanks for checking! I now filter out matches where there is more than one insertion per number. – J.Doe Sep 29 '18 at 9:28

# Pyth, 2827252422 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*FmvMsmXLkdUThl

• @KevinCruijssen it does indeed, 10 is usually T, but in function blocks the variables are re-purposed to act as iteration variables instead - in the filter block the iteration variable just so happens to be T, so it can't be used. This means that 10 ^ 4 would be ^10 4, which is 5 bytes long, so no shorter unfortunately – Sok Sep 28 '18 at 12:43
• @Sok Ah ok. So the T in UT is still 10, for the [0,10) range. But at f...T the T has become an iteration variable for the filter. Thanks for the explanation, that makes sense! And doing T4^ earlier, saving it in a variable, and using that variable in the filter is (at least) 5 bytes as well of course. – Kevin Cruijssen Sep 28 '18 at 12:50
• You can replace 10000 with ^;4. – FryAmTheEggman Sep 28 '18 at 22:19
• ; always has the value of the iteration variable in the global context, in this case 10. So ^;4 is what you're looking for. – isaacg Sep 29 '18 at 1:17
• 20 bytes: fq^;4sT*FmvsmXLkdThl. (Pyth beating Jelly? o.O Hooray) – Mr. Xcoder Sep 29 '18 at 9:17

# 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
}
}

• Just curious: can't you use the fact that the pairs can be written as (i,1e4-i) instead of iterating over every (i,j) and filtering them? – Eric Duminil Sep 28 '18 at 16:16

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

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


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

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

# Japt, 302925 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


# Javascript (Node) - 183136 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

• Here are some quick wins. This is basically the same code without the 'golf-unfriendly' statements (String.prototype, function, let, this) and with a few other optimizations. – Arnauld Sep 29 '18 at 8:58
• From there, you can save 4 more bytes by using a map() instead of the outer for loop. NB: the only reason why we use j as the 1st parameter of the callback function is that we want it to be defined in this scope. – Arnauld Sep 29 '18 at 9:33
• @Arnauld thanks I really appreciate it, you’re a legend man. Post your answer tho, I don’t want to take yours, I’m just doing it for fun. – Asleepace Sep 29 '18 at 10:41
• I'm not going to answer my own challenge and this code is just a modification of yours, so feel free to use it. No worries! – Arnauld Sep 29 '18 at 10:53
• Knocked @Arnauld's suggestions down to 123 bytes – Shaggy Sep 29 '18 at 15:50

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


# Stax, 24 bytes

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


Run and debug it

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

["934", "654"]


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

# 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}

• Because the output can include duplicates, you don't need to call set in the last line for -5 bytes. – Jack Brounstein Sep 28 '18 at 19:20
• @JackBrounstein, Thanks. I missed that part of the rules. – user2699 Sep 28 '18 at 20:25
• @EricDuminil, Thanks. I did not know about set comprehensions, that's a neat trick. – user2699 Sep 29 '18 at 12:45
• 117 bytes – Jo King Sep 29 '18 at 13:05
• @JoKing Clever. After all these suggestions the solution barely resembles what I started with. – user2699 Sep 29 '18 at 14:04

# 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!

# 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


# 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