Resolver um quebra-cabeça Matchstick

17

No enigmático SE, existem os chamados "problemas do palito de fósforo", nos quais a matemática é escrita em palitos de fósforo e você pode mover um certo número deles para obter uma determinada propriedade.

Nesta questão, consideraremos apenas números inteiros representados em um formato de exibição de 7 segmentos. Aqui estão todos os 10 dígitos nesse formato:

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

Cada segmento da tela é um "palito de fósforo" que pode ser movido independentemente do restante do número. Os palitos de fósforo são indivisíveis e indestrutíveis, não podem ser quebrados ou removidos por qualquer meio.

Um quebra-cabeça comum é pegar um número dado na base 10 e tentar tornar o maior número possível em um determinado número de movimentos. Uma jogada é considerada um movimento de um palito de fósforo de qualquer slot ocupado para outro slot não ocupado. Você está perfeitamente autorizado a criar novos dígitos em ambos os lados do número, por exemplo, 0 pode ser transformado em 77 e dar 3 movimentos

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

No entanto, você não pode transformar um slot em 2 ou criar novos slots entre os existentes, por exemplo, transformar um 4 em 11 no meio de um número ou inserir novos dígitos entre os existentes. Cada movimento não precisa criar um número adequado, mas o resultado final deve ser um número adequado na exibição dos sete segmentos da base 10. Você não precisa usar todos os movimentos se não desejar. Ao contrário de intrigante, essa é uma [tag: pergunta encerrada], você não pode usar nenhum operador (multiplicação, exponenciação etc.) ou constantes matemáticas (Pi, número de Graham etc.) em suas respostas.

Tarefa

Escreva um programa ou função que use um número e um número de movimentos como entrada e retorne o maior número que pode ser feito com tantos movimentos no número original.

Esta é uma questão de para que as respostas sejam pontuadas em bytes, com menos bytes sendo melhores.

Casos de teste

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

Relacionado

Post Rock Garf Hunter
fonte
5
Eu ... realmente ficou até tarde na noite passada ponderando a distância Levenshtein entre vários dígitos palito ... O que uma estranha coincidência: P
ETHproductions
11
Os slots vazios formados no meio podem ser ignorados no final? Por exemplo919, 2 -> 991
DanTheMan
Veja também
geokavel
mago do trigo, qual grade está sendo usada?
Tuskiomi
@tuskiomi "No entanto, você não pode transformar um slot em 2 ou criar novos slots entre os existentes"
Post Rock Garf Hunter

Respostas:

7

JavaScript (ES6), 297 286 279 267 bytes

Recebe entrada na sintaxe de curry (s)(k), onde s é uma matriz de caracteres de dígitos e k é o número de movimentos (número inteiro).

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

Casos de teste


Quão?

Dados de forma e função auxiliar

  • A matriz b descreve as formas dos dígitos como números inteiros de 7 bits, em que cada bit é um segmento:

    7 segmentos

    Por exemplo, o formato de "7" é 0b0100101 = 37.

  • A função auxiliar B () retorna o número de 1s na representação binária de um determinado número:

    B = (n, b = 0) => n ? B(n ^ n & -n, b + 1) : b

Passo 1

Primeiro, contamos o número de palitos de fósforo usados ​​no número de entrada:

s.reduce((s, c) => s + B(b[c]), 0)

Passo 2

Passamos esse valor para a função recursiva g () , que preenche uma lista r com todos os números que podem ser construídos com exatamente esse número de palitos de fósforo:

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

Por exemplo, g (5) será carregado [ '17', '2', '3', '5', '71' ]em r .

Etapa 3

Agora temos que selecionar o número mais alto M em r que pode realmente ser obtido a partir do número de entrada, dentro do número permitido de movimentos k .

Como cada número n em r usa exatamente o número de palitos de fósforo que o número de entrada s , o número de movimentos necessários para transformar s em n é igual à metade do número de diferenças de segmentos entre cada um de seus dígitos.

O número de diferenças de segmento entre dois dígitos x e y é dado pelo número de 1's na representação binária de b [x] XOR b [y] .

Finalmente, é importante observar que precisamos tentar vários alinhamentos de dígitos possíveis, porque o primeiro dígito de s não é necessariamente mapeado para o primeiro dígito de n . A mudança entre os dígitos é dada pela variável j no código.

Arnauld
fonte
1

Mathematica, 188 197 200 203 170 174 bytes

NOTA: O código ainda é um tipo de buggy. Eu estou trabalhando nisso.

+30 bytes para 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)&

O caractere entre %e odeve ser, 0x7Fmas o SE não permitirá. Você pode clicar no link pastebin para copiar o código original.

O código leva muito tempo quando há mais de 6-7 varas. (Você pode modificar o valor inicial de ipara um número menor para testá-lo)

Explicação

gé uma função auxiliar que converte dígitos em uma lista de representação de stick (de acordo com aqui ), como {1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1}para 220.

h é uma função auxiliar para lidar com preenchimento esquerdo e preenchimento direito entre dois números.

fitera de 10^Tr@g@#(limite superior) para 1procurar um número inteiro cuja representação de stick tenha a mesma quantidade 1 -> 0e em 0 -> 1comparação com o número original e a quantidade seja menor ou igual ao segundo argumento.

Keyu Gan
fonte
Eu dei um +1 a você porque nunca vi uma resposta vencedora ter uma pontuação tão baixa quanto a outra resposta. Eu suponho que é porque é a falta de opções de teste online. Talvez algumas pessoas que possuem o Mathematica possam testá-lo e verificar se ele funciona bem, para que você possa obter mais votos positivos. Ou talvez alguém possa convertê-lo para Octave, se possível.
geokavel