Solve a Matchstick puzzle On puzzling SE there are what are called "matchstick problems" in which math is written in match sticks and you are allowed to move a certain number of them to get a certain property.

In this question we will be considering only integers represented in a 7-segment display format.  Here are all 10 digits in that format:

 __          __   __          __    __    __    __    __
|  |     |   __|  __|  |__|  |__   |__      |  |__|  |__|
|__|     |  |__   __|     |   __|  |__|     |  |__|   __|    


Each segment of the display is one "match-stick" which can be moved independently of the rest of the number.  Matchsticks are indivisible and indestructible, the cannot be broken or removed by any means.

A common puzzle is to take a number given in base 10 and try to make the largest number possible in a given number of moves.  A move is considered to be one movement of a matchstick from any occupied slot to any other unoccupied slot.  You are perfectly permitted to make new digits on either side of the number, for example 0 can be made into 77 give 3 moves

 __      __  __      __   __      __   __
|  |    |  |        |  |    |       |    |
|__| ,   __|     ,     |      ,     |    |


However you may not make one slot into 2 or make new slots between existing ones, for example turning a 4 into an 11 in the middle of a number or inserting new digits in between existing ones.  Each move need not make a proper number but the final result should be a proper number in the base 10 seven segment display.  You need not use every move if you do not wish to.  Unlike on puzzling this is a [tag:close ended question] you may not use any operators (multiplication, exponentiation, etc.) or mathematical constants (Pi, Graham's number, etc.) in your answers.

Task

Write a program or function that takes a number and a number of moves as input and returns the largest number that can be made with that many moves on the original number.

This is a code-golf question so answers will be scored in bytes, with less bytes being better.

Test Cases

n, moves -&gt; max
0, 1     -&gt; 9
0, 3     -&gt; 77
0, 4     -&gt; 111
8, 3     -&gt; 74
220, 1   -&gt; 320
220, 2   -&gt; 520
220, 3   -&gt; 7227
220, 4   -&gt; 22111
220, 5   -&gt; 32111
747, 1   -&gt; 747
747, 2   -&gt; 7171
747, 3   -&gt; 7711


Related
JavaScript (ES6), 297 286 279 267 bytes

Takes input in currying syntax (s)(k), where s is an array of digit characters and k is the number of moves (integer).

s=&gt;k=&gt;(B=(n,b=0)=&gt;n?B(n^n&amp;-n,b+1):b,b=[...p='u"[k,iy#}m'].map(c=&gt;c.charCodeAt()+2),r=[],g=(n,d='')=&gt;n?n&gt;0&amp;&amp;b.map((v,i)=&gt;g(n-B(v),d+i)):r.push(d))(s.reduce((s,c)=&gt;s+B(b[c]),M=0))&amp;&amp;b.map((_,j)=&gt;r.map(n=&gt;M=[...n+p].reduce((t,d,i)=&gt;t+B(b[d]^b[s[i-j]]),0)&gt;k*2|+n&lt;M?M:n))|M


Test cases



let f=

s=&gt;k=&gt;(B=(n,b=0)=&gt;n?B(n^n&amp;-n,b+1):b,b=[...p='u"[k,iy#}m'].map(c=&gt;c.charCodeAt()+2),r=[],g=(n,d='')=&gt;n?n&gt;0&amp;&amp;b.map((v,i)=&gt;g(n-B(v),d+i)):r.push(d))(s.reduce((s,c)=&gt;s+B(b[c]),M=0))&amp;&amp;b.map((_,j)=&gt;r.map(n=&gt;M=[...n+p].reduce((t,d,i)=&gt;t+B(b[d]^b[s[i-j]]),0)&gt;k*2|+n&lt;M?M:n))|M

console.log("0   / 1 -&gt; " + f([..."0"  ])(1)) // -&gt; 9
console.log("0   / 3 -&gt; " + f([..."0"  ])(3)) // -&gt; 77
console.log("0   / 4 -&gt; " + f([..."0"  ])(4)) // -&gt; 111
console.log("8   / 3 -&gt; " + f([..."8"  ])(3)) // -&gt; 74
console.log("220 / 1 -&gt; " + f([..."220"])(1)) // -&gt; 320
console.log("220 / 2 -&gt; " + f([..."220"])(2)) // -&gt; 520
console.log("220 / 3 -&gt; " + f([..."220"])(3)) // -&gt; 7227
console.log("220 / 4 -&gt; " + f([..."220"])(4)) // -&gt; 22111
console.log("220 / 5 -&gt; " + f([..."220"])(5)) // -&gt; 32111
console.log("747 / 1 -&gt; " + f([..."747"])(1)) // -&gt; 747
console.log("747 / 2 -&gt; " + f([..."747"])(2)) // -&gt; 7171
console.log("747 / 3 -&gt; " + f([..."747"])(3)) // -&gt; 7711






How?

Shape data and helper function


The array b describes the shapes of the digits as 7-bit integers, where each bit is a segment:



For instance, the shape of "7" is 0b0100101 = 37.
The helper function B() returns the number of 1's in the binary representation of a given number:

B = (n, b = 0) =&gt; n ? B(n ^ n &amp; -n, b + 1) : b



Step #1

We first count the number of matchsticks used in the input number:

s.reduce((s, c) =&gt; s + B(b[c]), 0)


Step #2

We pass this value to the recursive function g(), which populates a list r with all numbers that can be built with exactly this number of matchsticks:

g = (n, d = '') =&gt;
  n ?
    n &gt; 0 &amp;&amp;
    b.map((v, i) =&gt; g(n - B(v), d + i))
  :
    r.push(d)


For instance, g(5) will load [ '17', '2', '3', '5', '71' ] into r.

Step #3

We now have to select the highest number M in r which can actually be obtained from the input number, within the allowed number of moves k.

Because each number n in r uses exactly as many matchsticks as the input number s, the number of moves required to transform s into n equals half the number of segment differences between each of their digits.

The number of segment differences between two digits x and y is given by the number of 1's in the binary representation of b[x] XOR b[y].

Finally, it's important to note that we need to try several possible digit alignments, because the first digit of s is not necessarily mapped to the first digit of n. The shift between the digits is given by the variable j in the code.