17
\$\begingroup\$

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

\$\endgroup\$
  • 5
    \$\begingroup\$ I... actually stayed up late last night pondering the Levenshtein distance between various matchstick digits... What an odd coincidence :P \$\endgroup\$ – ETHproductions Jul 25 '17 at 17:03
  • 1
    \$\begingroup\$ Can empty slots formed in the middle be ignored at the end? E.g. 919, 2 -> 991 \$\endgroup\$ – DanTheMan Jul 26 '17 at 0:20
  • \$\begingroup\$ Related \$\endgroup\$ – geokavel Jul 26 '17 at 1:02
  • \$\begingroup\$ wheat wizard, which grid is being used? \$\endgroup\$ – tuskiomi Jul 26 '17 at 3:27
  • \$\begingroup\$ @tuskiomi "However you may not make one slot into 2 or make new slots between existing ones" \$\endgroup\$ – Wheat Wizard Jul 26 '17 at 3:28
7
\$\begingroup\$

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:

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I gave you a +1 because I've never seen a winning answer have such a lower score than the other answer. I assume it's because it's the lack of online testing options. Maybe some people who have Mathematica could come and test it out and verify that it works well, so you could get some more upvotes. Or maybe someone could convert it to Octave if possible. \$\endgroup\$ – geokavel Jul 27 '17 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.