Solve a Matchstick puzzle

Question

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 -> max
0, 1     -> 9
0, 3     -> 77
0, 4     -> 111
8, 3     -> 74
220, 1   -> 320
220, 2   -> 520
220, 3   -> 7227
220, 4   -> 22111
220, 5   -> 32111
747, 1   -> 747
747, 2   -> 7171
747, 3   -> 7711

Related

Answer 1

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

Test cases

let f=

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

console.log("0   / 1 -> " + f([..."0"  ])(1)) // -> 9
console.log("0   / 3 -> " + f([..."0"  ])(3)) // -> 77
console.log("0   / 4 -> " + f([..."0"  ])(4)) // -> 111
console.log("8   / 3 -> " + f([..."8"  ])(3)) // -> 74
console.log("220 / 1 -> " + f([..."220"])(1)) // -> 320
console.log("220 / 2 -> " + f([..."220"])(2)) // -> 520
console.log("220 / 3 -> " + f([..."220"])(3)) // -> 7227
console.log("220 / 4 -> " + f([..."220"])(4)) // -> 22111
console.log("220 / 5 -> " + f([..."220"])(5)) // -> 32111
console.log("747 / 1 -> " + f([..."747"])(1)) // -> 747
console.log("747 / 2 -> " + f([..."747"])(2)) // -> 7171
console.log("747 / 3 -> " + f([..."747"])(3)) // -> 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) => n ? B(n ^ n & -n, b + 1) : b
  

Step #1

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

s.reduce((s, c) => 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 = '') =>
  n ?
    n > 0 &&
    b.map((v, i) => 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.

Answer 2

Mathematica, 188 197 200 203 170 174 bytes

NOTE: The code is still kind of buggy. I'm working on it.

+30 bytes for bug

(p=PadLeft;q=IntegerDigits;g=Join@@(#~q~2~p~7&/@ToCharacterCode["w$]m.k{% o"][[1+q@#]])&;h=(v=g@#2~#~96-g@i~#~96;Tr@v==0&&Tr@Abs@v<=2#3)&;For[i=10^Tr@g@#,!h[p,##]&&!h[PadRight,##],--i];i)&

The character between % and o should be 0x7F but SE won't allow it. You could click pastebin link to copy the original code.

The code takes a lot of time when there're more than 6-7 sticks. (You could modify the starting value of i to a smaller number to test it)

Explanation

g is a helper function converting digits into a list of stick representation (according to here), such as {1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1} for 220.

h is a helper function to deal with left-padding and right-padding between two numbers.

f iterates from 10^Tr@g@# (upper limit) to 1 to look for a integer whose stick representation has a same quantity of 1 -> 0 and 0 -> 1 compared to the original number and the quantity is smaller or equal than second argument.