Dada uma pirâmide de adição , determine se ela pode ser resolvida. Uma pirâmide de adição consiste em camadas , cada uma com um número menor que o número abaixo dela. A camada é simbolizada como . é a camada base e é a camada no topo de . O ésimo número de é indicado como . é o número mais à esquerda de , e é o número à direita de . Você pode visualizar residindo em cima de$P$i P i P 1 P i + 1 P i j P i P i , j P i , 1 P i P i , j + 1 P i , j P i + 1 , j P i , j$i$$P_i$$P_1$$P_{i+1}$$P_i$$j$$P_i$$P_{i,j}$$P_{i,1}$$P_i$$P_{i,j+1}$$P_{i,j}$$P_{i+1,j}$$P_{i,j}$e no meio, daí o nome " pirâmide de adição ".$P_{i,j+1}$

• $\forall P_{i,j},P_{i,j}\in\mathbb N^*$ , ou seja, todo número na pirâmide é um número inteiro positivo diferente de zero.
• $\forall i>1,P_{i,j}=P_{i-1,j}+P_{i-1,j+1}$ , ou seja, todos os números que não estão na camada base da pirâmide são a soma de os dois números abaixo dele.
• Se possui números, possui , portanto, é o número mais à direita de . Em termos mais simples, cada camada tem um número a menos que a camada abaixo dela.$P_1$$n$$P_i$$n-i+1$$P_{i,n-i+1}$$P_i$

Um quebra-cabeça de pirâmide de adição é uma pirâmide de adição com alguns números removidos (substituídos por ). Sua solução é uma pirâmide de adição , onde , ou seja, os números que estavam originalmente presentes no quebra-cabeça têm foi deixado inalterado. Esse quebra-cabeça pode ter mais de uma solução.$Q$$?$$P$$\forall Q_{i,j}\ne{?},P_{i,j}=Q_{i,j}$

Seu trabalho é, com um quebra-cabeça de pirâmide adicional, determinar se ele tem exatamente uma solução.

Entrada

Você pode obter informações de qualquer uma das seguintes formas, mas seja consistente:

• Matriz de camadas.
• Matriz de camadas, em forma de pirâmide, usando um valor inteiro não positivo consistente como um separador entre os elementos (usados ​​apenas uma vez por vez), bem como o preenchimento esquerdo e direito. O separador e o preenchimento devem ser os mesmos.
• Matriz de camadas com um preenchimento válido direito ou esquerdo consistente (neste caso, você deve ser consistente e não misturar o preenchimento direito e esquerdo).

Observe que um valor consistente que não seja um número inteiro estritamente positivo deve ser usado para representar um número ausente; esse valor não pode ser usado como preenchimento. Além disso, é possível concatenar as camadas (ainda é possível separá-las) e a ordem pode ser da base para o topo ou da parte superior para a base.

Resultado

Um dos dois valores distintos consistentes, em que um representa a presença de uma solução única e o outro a ausência de uma solução ou a presença de mais de uma solução.

Regras

• $Q_{i+1,j}=Q_{i,j}+Q_{i,j+1}$ sempre será verdadeiro se$Q_{i,j},Q_{i,j+1},Q_{i+1,j}\in\mathbb N^*$ , ou seja, a entrada é garantido que não contenha um número em cima de dois outros números que não é a soma deles se todos os três números forem conhecidos.
• $\exists Q_{i,j},Q_{i,j}\ne{?}$, ou seja, a pirâmide conterá pelo menos um número conhecido.
• Não faça essas coisas .
• Isso é código-golfe , então a resposta mais curta vence! No entanto, não deixe que isso o desencoraje de postar uma solução apenas porque seu idioma é "muito detalhado".

Casos de teste

Uma matriz com as camadas da parte superior à base é usada para esses casos de teste, com 0representação $?$.

[[10], [0, 0], [0, 2, 0], [0, 0, 0, 1]] -> True
[[32], [0, 0], [0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] -> True
[[0], [1, 1]] -> True
[[1], [0, 0]] -> False
[[10], [5, 5], [2, 3, 2], [0, 0, 0, 0]] -> False
[[5], [0, 0], [0, 0, 0]] -> False

Exemplos trabalhados

Os casos de teste são trabalhados aqui.

Solução única 1

$$\begin{array}c&&&10\\&&?&&?\\&?&&2&&?\\?&&?&&?&&1\end{array}$$

Passo 1: $x+y=2\leftrightarrow x=y=1$ .

$$\begin{array}c&&&10\\&&?&&?\\&?&&2&&?\\?&&\color{red}1&&\color{red}1&&1\end{array}$$

Etapa 2: $x=y=1\leftrightarrow x+y=2$ .

$$\begin{array}c&&&10\\&&?&&?\\&?&&2&&\color{red}2\\?&&1&&1&&1\end{array}$$

Passo 3: $x=y=2\rightarrow x+y=4$ .

$$\begin{array}c&&&10\\&&?&&\color{red}4\\&?&&2&&2\\?&&1&&1&&1\end{array}$$

Passo 4: $x+4=10\leftrightarrow x=6$ .

$$\begin{array}c&&&10\\&&\color{red}6&&4\\&?&&2&&2\\?&&1&&1&&1\end{array}$$

As etapas 5 a 6 são semelhantes a 4.

$$\begin{array}c&&&10\\&&6&&4\\&\color{red}4&&2&&2\\\color{red}3&&1&&1&&1\end{array}$$

Então aqui temos nossa solução exclusiva.

Solução única 2

$$\begin{array}c&&&&&32\\&&&&?&&?\\&&&?&&?&&?\\&&?&&?&&?&&?\\&?&&?&&?&&?&&?\\?&&?&&?&&?&&?&&?\end{array}$$

Etapa 1: não há uma abordagem óbvia aqui, então vamos tentar usar os valores mínimos possíveis.

$$\begin{array}c&&&&&32\\&&&&?&&?\\&&&?&&?&&?\\&&?&&?&&?&&?\\&?&&?&&?&&?&&?\\\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1\end{array}$$

Etapas 2-5: Parece que os valores mínimos resultam em uma solução, portanto, esta é a única solução e, portanto, única.

$$\begin{array}c&&&&&32\\&&&&\color{red}{16}&&\color{red}{16}\\&&&\color{red}8&&\color{red}8&&\color{red}8\\&&\color{red}4&&\color{red}4&&\color{red}4&&\color{red}4\\&\color{red}2&&\color{red}2&&\color{red}2&&\color{red}2&&\color{red}2\\1&&1&&1&&1&&1&&1\end{array}$$

Dica: existe um teorema sobre quebra-cabeças de pirâmide de adição relacionado a esse quebra-cabeça que você pode provar se pensar bastante.

Solução única 3

$$\begin{array}c&?\\1&&1\end{array}$$

Passo 1: $x=y=1\rightarrow x+y=2$ .

$$\begin{array}c&\color{red}2\\1&&1\end{array}$$

Esta é uma solução obviamente única.

Sem solução 1

$$\begin{array}c&1\\?&&?\end{array}$$

$\min\mathbb N^*=1\rightarrow x,y\ge1\rightarrow x+y\ge2>1$

Sem solução 2

$$\begin{array}c&&&10\\&&5&&5\\&2&&3&&2\\?&&?&&?&&?\end{array}$$

$x+y=2\leftrightarrow x=y=1$

$$\begin{array}c&&&10\\&&5&&5\\&2&&3&&2\\\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1\end{array}$$

$1+1=3$

Solução não exclusiva

$$\begin{array}c&&5\\&?&&?\\?&&?&&?\end{array}$$

Duas soluções:

$$\begin{array}c&&5&&&&&&&5\\&2&&3&&&&&3&&2\\1&&1&&2&&&2&&1&&1\end{array}$$

Como existem pelo menos duas soluções, não há solução única.

Geléia , 18 16 bytes

FṀ‘ṗLSƝƬ€Ṗ€a@ċ⁼1

Experimente online!

Um link monádico que pega a pirâmide na ordem inversa e retorna 1 para verdadeiro e 0 para falso. Gera todas as pirâmides possíveis com uma base até o número máximo na pirâmide e verifica se há uma correspondência exclusiva para a entrada.

Agradecemos a @Arnauld por apontar que isso falhou [[1,0],[0]]; agora corrigido.

Obrigado a @JonathanAlan por salvar 2 bytes!

Explicação

F                | Flatten
 Ṁ               | Maximum
  ‘              | Increase by 1
   ṗ             | Cartesian power of this with:
    L            | - Length of input
        €        | For each:
       Ƭ         | - Repeat the following until no change
     SƝ          |   - Sum of neighbours
         Ṗ€      | Remove last element from each list
           a@    | Logical and input with each list
             ċ   | Count times input appears
              ⁼1 | Check if equal to 1

C # (Compilador interativo do Visual C #) , 303 227 bytes

n=>{int i=n.Max(x=>x.Max()),j=n.Count,t=0,k,m=0,z;for(;t<Math.Pow(i,j);){k=t++;var s=n.Select(_=>(a:k%i+1,k/=i).a).ToList();if(n.All(x=>(z=0,b:x.All(o=>o==s[z++]|o<1),s=s.Skip(1).Select((a,b)=>a+s[b]).ToList()).b))m++;}m/=m-1;}

Lança exceção se true, executa normalmente se false.

Experimente online!

Wolfram Language (Mathematica) , 85 88 bytes

Count[l=Length@#;NestList[2#~MovingMedian~2&,#,l-1]&/@Range@Max@#~Tuples~l,#/. 0->_]==1&

Experimente online!

+3 fixo.

Força bruta: para todas as bases com valores , verifique se a pirâmide resultante corresponde à forma especificada e verifique se o número total de correspondências é 1. É inserido como uma lista de níveis, base primeiro, com a representação de números ausentes.1..(sum of all numbers)0

05AB1E , 25 bytes

ZÌLsgãε©.Γü+}¨®š.S*˜O_}OΘ

Toma as camadas da pirâmide em ordem invertida, da base à ponta (ou seja [[0,0,0,1],[0,2,0],[0,0],[10]]).

Além disso, parece haver um bug em algum lugar do 05AB1E .Γdentro de um mapa. O valor ©...®šdeve ser ...yšde -1 byte.

Experimente online ou verifique mais alguns casos de teste .

Uma alternativa menor de bytes iguais para ©.ΓüO}®špoderia ser [Ðg#üO}\): Experimente online.

Explicação:

Z        # Get the flattened maximum of the (implicit) input (without popping)
 Ì       # Increase it by 2
  L      # Create a list in the range [1, max+2]
   sg    # Swap to get the input again, and get the length (amount of layers)
     ã   # Create a cartesian product of this list repeated that many times
ε        # Map each inner list to:
 ©       #  Store it in variable `®` (without popping)
  .Γ     #  Collect all results until the following doesn't change anymore:
    ü    #   Get the pairwise:
     +   #    Sums
   }®š   #  After we've collected all, prepend the original list `®`
 .S      #  Now compare this potential pyramid with the (implicit) input-pyramid
         #  (-1 if a<b; 0 if a==b; 1 if a>b)
   *     #  Multiply that with the (implicit) input-pyramid
    ˜O   #  Then take the flattened sum
      _  #  And check that this sum equals 0 (1 if truhy; 0 if falsey)
}O       # After the map, take the sum to get the amount of truthy values
  Θ      # And trutify it (== 1), since we must output distinct values instead of truthy/falsey
         # (after which the result is output implicitly)

Haskell, 106 bytes

z=zipWith
a#b=a*b==a*a
f x=[1|t<-mapM(\_->[1..sum(sum<$>x)])x,all and$z(z(#))x$iterate(z(+)=<<tail)t]==[1]

Toma uma pirâmide de cabeça para baixo, por exemplo [[0,0,0,1],[0,2,0],[0,0],[10]].

Experimente online!

A abordagem da força bruta em Haskell:

• crie todas as camadas base possíveis t( mapM(\_->[1..sum(sum<$>x)])x), onde os números vão de 1 à soma de todos os números na pirâmide de entrada
• crie uma pirâmide a partir de t( iterate(z(+)=<<tail)t)
• compare cada camada em termos de elementos com a entrada ( z(z(#))x). A função de comparação a # bretornará Truese os dois números forem iguais ou aforem zero ( a*b==a*a).
• pegue uma 1para cada pirâmide que corresponda e compare a lista resultante com a lista de singleton [1].