X + Y = Z - mas em qual base?

20

O desafio

Dados 3 números X, Ye Zna base B, encontre um número Bno qual a adição Xe o Yrendimento Z. As entradas x = 20, Y = 12e Z = 32poderia originar 5porque 20 + 12 = 32em 5 de base.

  • Você pode supor que sempre haverá uma base na qual a adição está correta (há casos em que não existe uma base, graças a @ MasonWheeler e @ Não a Charles, por alguns exemplos disso).
  • A base mais baixa possível é 1. Você pode usar 1s ou 0s como dígitos em unário, mas não pode misturá-los.

I / O

  • Os dígitos dos números de entrada serão números inteiros não negativos.
  • Você pode supor que os números de entrada contenham zeros à esquerda, de modo que tenham um comprimento específico (ou igual).
  • Você pode pegar os números no formato mais conveniente, desde que não seja pré-processado. Isso inclui o formato geral dos três números de entrada e o formato dos dígitos de cada um desses números. Por favor, deixe claro qual formato você usa.
  • Se houver várias bases possíveis, você poderá produzir todas ou apenas uma delas.
  • Você pode assumir que os números base e de entrada estarão dentro dos limites numéricos do seu idioma.

Regras

  • Função ou programa completo permitido.
  • Regras padrão para entrada / saída.
  • Aplicam-se brechas padrão .
  • Isso é , portanto, a menor contagem de bytes vence. O desempate é uma submissão anterior.

Casos de teste

O formato de entrada aqui é uma lista de números inteiros para representar cada número. As três listas são separadas por vírgulas.
Observe que às vezes existem várias bases possíveis. Somente uma solução (aleatória) é produzida aqui.

[12, 103], [4, 101], [16, 204] -> 349
[4, 21, 25], [5, 1, 20], [9, 23, 17] -> 28
[16, 11], [25, 94], [41, 105] -> 147
[2, 140], [21, 183], [24, 100] -> 223
[8, 157], [1, 28], [9, 185] -> 227
[2, 158], [88], [3, 12] -> 234
[8, 199], [1, 34], [9, 233] -> 408
[3, 247], [7, 438], [11, 221] -> 464
[3, 122], [3, 2], [6, 124] -> 480
[6, 328], [3, 31], [9, 359] -> 465
[2, 1, 0, 0, 0, 0], [1, 2, 0, 0, 1, 0, 1, 0], [1, 2, 2, 1, 1, 0, 1, 0] - > 3
[16, 105], [16, 120], [33, 84] -> 141
[15, 60], [9, 30], [24, 90] -> 268
[2, 0], [1, 2], [3, 2] -> 5
[1, 3, 3, 7], [1, 2, 3], [1, 4, 6, 0] -> 10
[0], [1, 12, 8], [1, 12, 8] -> 16
[1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1], [1, 0, 0, 1, 0, 1, 1, 1, 0, 0 , 1], [1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0] -> 2
[1], [1], [1,1] -> 1

Você pode gerar casos de teste adicionais com este programa Pyth . Insira uma base na primeira linha e os valores decimais para Xe Ynas duas linhas a seguir.
Além disso, você pode usar este programa Pyth para criar vários casos de teste de uma vez usando valores aleatórios. Basta digitar a quantidade desejada de casos de teste na entrada.

Feliz codificação!

Denker
fonte

Respostas:

12

Geléia, 16 11 7 bytes

_/N,‘FṀ

Essa abordagem é fortemente baseada na resposta Octave do @ beaker .

O formato de entrada é Z, Y, X , com ordem de dígitos little-endian, usando o dígito 0 para unário.

Experimente online! ou execute todos os casos de teste .

Como funciona

Em vez de testar incrementalmente bases possíveis, isto resolve o polinómio que corresponde à matriz P: = X + Y - Z . Isso retorna o maior coeficiente de P ≠ 0 - que deve ser uma raiz, já que existe pelo menos uma base válida - ou o dígito mais alto de X , Y e Z , incrementado por 1 .

_/N,‘FṀ  Main link. Argument: [Z, Y, X]

_/       Reduce by subtraction; yield Z - X - Y.
         This works since Z must have at least as many digits as X and Y.
  N      Negate to yield X + Y - Z.
    ‘    Yield [Z, Y, X], with all digits increments by 1.
   ,     Pair the results to the left and to the right.
     F   Flatten the resulting, nested list.
      Ṁ  Compute the maximum.
Dennis
fonte
11

Pitão, 13 bytes

f!-FiRTQheSsQ

Espera Z, seguido por X e Y.

Suíte de teste

Essencialmente, testamos todas as bases possíveis, começando com mais um que o maior dígito. O teste é que convertemos cada número na base em questão, dobramos a subtração sobre os números e negamos logicamente o resultado.

isaacg
fonte
5
Então este leva pouco como zeros?
Fund Monica's Lawsuit
3
@QPaysTaxes Acho que você quis dizer unário, e sim.
Mego 25/03
4
@Mego eu quis dizer unário, autocorreção significava o que queria dizer.
Fund Monica's Lawsuit
10

Oitava, 67 75 38 32 bytes

Porque "repetir TODAS as coisas" é muito trabalho.

@(x,y,z)max([m=max(x+y-z) z])+~m

Requer 0 preenchimento para tornar as matrizes de entrada do mesmo tamanho, por exemplo:

[2, 158],[88],[3, 12]
becomes
[2, 158],[0, 88],[3, 12]

Como 0é usado para preenchimento, 1é usado como token para unário.

(Agradecemos a @DenkerAffe pelo esclarecimento na pergunta.)

Amostra executada em ideone .


Breve explicação:

Tome um caso que não envolva transporte:

   [ 8, 199]
 + [ 1,  34]
 -------------
     9, 233
 - [ 9, 233]
 -------------
     0,   0 --- no carries

Nesse caso, não há restrições na base, desde que seja maior que qualquer "dígito". Simplesmente pegue o elemento max de z(as z >= x,y) e adicione 1 (ou qualquer número inteiro positivo).

No caso de uma entrega (sem entrega), excedemos a base em uma das colunas e a diferença entre x+ye zé a base:

   [ 2, 140]
 + [21, 183]
--------------
    23, 323
 - [24, 100]
 -------------
    -1  223
     ^   ^------ base
     |---------- carry in

Se a soma da segunda coluna também exceder a base, exigindo uma execução, bem como a entrada, seu valor seria base+(-1). Teremos uma coluna em algum lugar à direita com uma transferência e nenhuma transferência que possua o valor base (maior) correto.

taça
fonte
9

Haskell, 90 73 bytes

f l=[b|b<-[1..],all(<b)$id=<<l,[x,y,z]<-[foldl((+).(b*))0<$>l],x+y==z]!!0

Exemplo de uso: f [[3, 247],[7, 438],[11, 221]]-> 464.

Simplesmente tente todas as bases b(onde bé maior que o máximo dos dígitos). Escolha o primeiro onde x+y==z.

Edit: @xnor salvou muitos bytes, principalmente se livrando do import Data.Digits.

nimi
fonte
1
Se unDigits bfaz o que penso, deve ser mais curto para implementar como foldl(\x y->b*x+y)0ou equivalente foldl((+).(b*))0.
Xnor
1
É mais curto para tomar a maximumapós achatamento: b<-[1+(maximum$id=<<l)..].
Xnor
1
Ou, o teste para maximumcomo b<-[1..],all(<b)$id=<<l.
Xnor
Isso funciona para entrada em que a base 1 é a única solução? Não posso executar isso com os compiladores online que encontrei, portanto não posso me testar.
Denker 25/03
@ DenkerAffe: não devem ser os dígitos dde um bnúmero base 0 <= d < b, então, para a base1 o único dígito possível é 0? f [[0],[0],[0,0]]avalia como 1.
N
8

MATL , 20 bytes

`GY:@XJZQ2:"wJZQ-]]J

A entrada está no formato (observe as chaves externas):

{[4, 21, 25],[5, 1, 20],[9, 23, 17]}

Isso funciona na versão atual (15.0.0) .

Experimente online!

Explicação

`        % do...while index
  G      %   push input. First time pushed nothing but asks for input implicitly
  Y:     %   unpack the cell array, pushing the three numeric arrays
  @      %   loop index: candidate base
  XJ     %   copy into clipboard J
  ZQ     %   evaluate polynomial: interpret third array in that base
  2:"    %   for loop: do this twice (subtract the other numbers from the third)
    w    %     swap, to process another array
    J    %     push base
    ZQ   %     evaluate polynomial: interpret array in that base
    -    %     subtract
  ]      %   end for loop. A result 0 indicates a solution has been found
]        % end do....while loop. Exit if top of stack is 0
J        % push found base. Implicitly display
Luis Mendo
fonte
8

MATL, 13 12 bytes

--X>t~1G+hX>

Tradução do meu resposta Octave para o MATL. (Minha primeira resposta MATL!)

  • A ordem de entrada é Z, X, Y(ou, Z, Y, Xse preferir, eu sou fácil)
  • Matrizes de entrada são preenchidas com zero para comprimentos iguais
  • Leva pouco atraente como 1

Experimente online!

Explicação

--X>t~1G+hX>

--            % M = Z - X - Y
  X>          % P = max(M)
    t~        % Duplicate and negate
      1G      % Push 1st argument (Z) 
        +     % ~P + Z
         h    % Concatenate [P (~P + Z)]
          X>  % Return max
taça
fonte
3
unário é muito pouco atraente por AutoCorreção estes dias
Charlie