You are kinda Replacable to Me

Question

You are provided with a non-empty array \$A\$ of integers, all greater than 0. But what good is an array if the elements do not sum up to the number \$N\$ (also provided as input)...

So to change that, you can pick any integer of your choice present in the array and replace any of its digits with a different digit between 0-9 of your choice. What is the minimum number of digits that you should replace so that the sum of the elements becomes \$N\$?

Note that after replacing the digits, some of the numbers may contain leading zeroes, which is fine. For example: you can change \$123\$ to \$023\$, or even \$000\$ if you want to. However, the input will not contain any leading zeroes and you cannot assume any before the input number.

Example

Consider the array \$A=[195, 95]\$ and \$N = 380\$. You can do the following replacements:

1. 195 -> 185
2. 185 -> 181
3. 181 -> 281
4. 95 -> 99

So the new array is \$A=[281,99]\$ with a sum of \$380\$ in 4 steps. However, this is not minimal and you can do it in even fewer steps:

1. 195 -> 295
2. 95 -> 85

So we got our desired sum in 2 steps. There is no way to get a sum of \$380\$ in less than 2 steps so the answer for \$A=[195, 95]\$ and \$N = 380\$ will be \$2\$.

More examples

  A, N -> Answer
[195, 95], 380 -> 2
[100, 201], 0 -> 3
[32, 64], 96 -> 0
[7, 1, 1], 19 -> 2
[100, 37], 207 -> 1
[215], 25 -> 2
[123, 456], 1998 -> 6 

Rules

• Standard loopholes are forbidden.
• You do not need to handle inputs for which answer does not exist.
• This is code-golf, so the shortest code, in bytes, wins.

Answer 1

Haskell, ^95… 93 bytes

a#n|s<-show=minimum[sum[1|(x,y)<-s a`zip`s b,x/=y]|b<-mapM(mapM(:s(56^7)))a,n==sum(read<$>b)]

Try it online!

The relevant function is (#), which takes as input the array a and the integer n and returns the minimum number of moves. Elements of a are represented as strings of digits.

How?

Standard bruteforce, we try all the possible substitutions and return the minimum number of changes. The only things I'm vaguely proud of are the show tricks I've found while working on this answer.

• First of all, mapM(:show(56^7)) is shorter than mapM(\_->['0'..'9']) for enumerating all the possible digits substitutions of a single number. We save 3 bytes and we gain an exponentially slower solution.
• Moreover, using show a`zip`show b instead of zip(a>>=id)$b>>=id saves another byte.
• With the two previous tricks, we use the show function often enough that defining an alias for it saves an additional byte.

Answer 2

JavaScript (ES6),  132 123  120 bytes

Saved 3 bytes by wrapping in eval(), as suggested by @l4m2

Expects (list)(n), where list is an array of strings.

a=>n=>eval('for(m=k=1+a.join``;k--;)m=a.map(x=>s-=x.replace(/./g,j=>(d=~~i%10,t+=d!=j,i/=10,d)),s=n,i=k,t=0)|s|t>m?m:t')

Try it online!

Commented

This is a version without eval() for readability.

a =>                        // a[] = list of positive integers, as strings
n => {                      // n = target sum
  for(                      // loop:
    m = k =                 //   start with m = k = a number higher than 10 ** p
      1 + a.join``;         //   where p is the total number of digits in a[]
    k--;                    //   stop when k = 0 (decrement it afterwards)
  )                         //
    m =                     //   update the minimum m:
      a.map(x =>            //     for each integer x in a[]:
        s -=                //       subtract from s:
          x.replace(        //         replace in x
            /./g, j => (    //         each digit j:
              d = ~~i % 10, //           extract the next digit d from i
              t += d != j,  //           increment t if d is not equal to j
              i /= 10,      //           divide i by 10
              d             //           replace j with d
            )               //
          ),                //         end of replace
          s = n,            //         start with s = copy of n,
          i = k,            //         i = copy of k
          t = 0             //         and t = 0 (counter of modified digits)
      )                     //     end of map()
      | s                   //     if s is not equal to 0
      | t > m ? m           //     or t is greater than m, leave m unchanged
              : t;          //     otherwise, update it to t
  return m                  // end of loop: return m
}                           //

Answer 3

JavaScript (Node.js), 140 bytes

n=>g=x=>x.every(t=>t.split`+`.reduce((a,b)=>a-b,n))&&1+g(x,x.map(t=>{for(i in t)for(j=10;1/t[i]&&j--;)x.push(t.slice(0,i)+j+t.slice(-~i))}))

Try it online!

If no expression equals, replace every digit to any another and try again

Answer 4

Jelly, 20 bytes

^{Maybe there's a smarter way to approach this for golf?}

D©⁵ṁḶŒp€ŒpḌS⁼ɗƇn®§§Ṃ

A dyadic Link accepting a list of positive integers, \$A\$, on the left and an integer, \$N\$, on the right that yields the minimal number of digit changes to make to \$A\$ that are needed to make it sum to \$N\$.

Try it online! Or see all but one of the tests or the other one.

How?

D©⁵ṁḶp/€ŒpḌS⁼ɗƇn®§§Ṃ - Link: positive integer array A; integer N
D                    - decimal digit lists (for each of A)
 ©                   - copy that to the register for later (and yield it for now)
  ⁵                  - literal ten
   ṁ                 - mould-like (the digit lists)
    Ḷ                - lowered range (giving us [0,1,...,9] for each digit of each number in A)
       €             - for each (digit-option-list-of-lists):
     Œp              -   Cartesian product (giving us all digit lists we could make for each of A)
        Œp           - Cartesian product (giving us all lists of such possibilities)
              Ƈ      - filter by:
             ɗ       -   last three links as a dyad - f(x=that, N)
          Ḍ          -     convert (each) from base ten
           S         -     sum
            ⁼        -     equals (N)?
                ®    - recall the original digits lists of A from the register
               n     - not equal? (vectorises)
                 §   - sum of each
                  §  - sum of each
                   Ṃ - minimum

Answer 5

Ruby, 154 bytes

->a,n{[0].product(*a.map{|c|[*0...10**c.to_s.size]}).select{|x|x.sum==n}.map{|c|(0...a.size).sum{|i|a[i].digits.zip(c[i+1].digits).count{|x,y|x!=y}}}.min}

Try it online!

Not particularly clever: for each element of a, checks all numbers between 0 and 10^(number of digits), then filters the substitutions which yields the desired sum, and counts the digits that have changed.

Answer 6

Charcoal, 38 bytes

ＮθＩ⌊ＥΦＥＸχＬη⭆η⎇⁼λ,λ﹪÷ιＸχμχ⁼θΣιΣＥη¬⁼λ§ιμ

Try it online! Very slow, so TIO can't handle arrays where the total length of digits and commas is greater than 5. Explanation:

Ｎθ                                      First input as a number
        χ                               Predefined variable `10`
       Ｘ                                Raised to power
          η                             Second input as a string
         Ｌ                              Length
      Ｅ                                 Map over implicit range
            η                           Second input as a string
           ⭆                            Map over characters and join
               λ                        Current character
              ⁼                         Equal to
                ,                       Literal string `,`
             ⎇                          If true then
                 λ                      Current character else
                    ι                   Outer value
                   ÷                    Integer divide
                      χ                 Predefined variable `10`
                     Ｘ                  Raised to power
                       μ                Inner index
                  ﹪                     Modulo
                        χ               Predefined variable `10`
     Φ                                  Filter strings where
                            ι           Current string
                           Σ            Sum as array of integers
                         ⁼              Equal to
                          θ             First input as a number
    Ｅ                                   Map over strings
                               η        Second input as a string
                              Ｅ         Map over characters
                                  λ     Current character
                                ¬       Is not
                                 ⁼      Equal to
                                   §ιμ  Character from string
                             Σ          Take the sum
   ⌊                                    Take the minimum
  Ｉ                                     Cast to string
                                        Implicitly print