Учитывая добавленную пирамиду $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}$ и$P_{i,j+1}$ в середине, отсюда и название «дополнительнаяпирамида».

• $\forall P_{i,j},P_{i,j}\in\mathbb N^*$ , то есть, каждое число в пирамиде является положительным целым числом от нуля.
• $\forall i>1,P_{i,j}=P_{i-1,j}+P_{i-1,j+1}$ , то есть каждое число, не входящее в базовый слой пирамиды, является суммой двух чисел под ней.
• Если $P_1$ имеет $n$ чисел, $P_i$ имеет $n-i+1$ чисел, поэтому $P_{i,n-i+1}$ является самым правым числом $P_i$ . Проще говоря, каждый слой имеет на одно число меньше, чем слой под ним.

Дополнение пирамида головоломка $Q$ является дополнением пирамиды с некоторыми удаленными числами (заменены $?$ ). Его решение является дополнением пирамиды $P$ , где $\forall Q_{i,j}\ne{?},P_{i,j}=Q_{i,j}$ , то есть числа, которые изначально присутствовали в головоломке, остались без изменений. Такая головоломка может иметь более одного решения.

Ваша задача, учитывая дополнительную пирамидальную головоломку, определить, есть ли у нее одно решение.

вход

Вы можете получить ввод в любой из следующих форм, но будьте последовательны:

• Массив слоев.
• Массив слоев, имеющих форму пирамиды, с использованием непротиворечивого целочисленного значения в качестве разделителя между элементами (используется только один раз каждый раз), а также заполнения слева и справа. Разделитель и отступ должны быть одинаковыми.
• Массив слоев с одинаковым допустимым отступом справа или слева (в этом случае вы должны быть согласованным и не смешивать отступы справа и слева).

Обратите внимание, что для представления пропущенного числа необходимо использовать непротиворечивое значение, которое не является строго положительным целым числом; это значение нельзя использовать в качестве отступа. Кроме того, вы можете взять объединенные слои (вы можете разделить их), и порядок может быть либо от основания к вершине, либо от вершины к основанию.

Выход

Одно из двух последовательных различных значений, где одно представляет наличие уникального решения, а другое - отсутствие решения или наличие нескольких решений.

правила

• $Q_{i+1,j}=Q_{i,j}+Q_{i,j+1}$ всегда будет истинным, если$Q_{i,j},Q_{i,j+1},Q_{i+1,j}\in\mathbb N^*$ , то есть вход гарантированно не будет содержать число поверх двух других чисел, которое не является их суммой, если известны все три числа.
• $\exists Q_{i,j},Q_{i,j}\ne{?}$то есть пирамида будет содержать хотя бы одно известное число.
• Не делай этого .
• Это код-гольф , поэтому выигрывает самый короткий ответ! Однако не позволяйте этому отговаривать вас от публикации решения только потому, что ваш язык «слишком многословен».

Контрольные примеры

Массив со слоями от вершины до основания используется для этих тестовых случаев с 0представлением $?$,

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

Отработанные примеры

Тестовые случаи работают здесь.

Уникальное решение 1

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

Шаг 1: $x+y=2\leftrightarrow x=y=1$ .

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

Шаг 2: $x=y=1\leftrightarrow x+y=2$ .

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

Шаг 3: $x=y=2\rightarrow x+y=4$ .

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

Шаг 4: $x+4=10\leftrightarrow x=6$ .

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

Шаги 5-6 похожи на 4.

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

Так что здесь у нас есть уникальное решение.

Уникальное решение 2

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

Шаг 1: Здесь нет очевидного подхода, поэтому давайте попробуем использовать минимально возможные значения.

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

Шаги 2-5: похоже, что минимальные значения приводят к решению, поэтому это единственное решение и, следовательно, уникальное.

$$\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}$$

Подсказка: Существует одна теорема о сложении пирамидальных головоломок, связанных с этой загадкой, которую вы можете доказать, если подумаете.

Уникальное решение 3

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

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

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

Это явно уникальное решение.

Нет решения 1

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

$\min\mathbb N^*=1\rightarrow x,y\ge1\rightarrow x+y\ge2>1$ , поэтому решения не существует.

Нет решения 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$ , что является противоречием, поэтому решения не существует.

Неуникальное решение

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

Два решения:

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

Поскольку существует как минимум два решения, уникального решения не существует.

Желе , 18 16 байтов

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

Попробуйте онлайн!

Монадическая ссылка, которая принимает пирамиду в обратном порядке и возвращает 1 для true и 0 для false. Создает все возможные пирамиды с основанием до максимального числа в пирамиде и проверяет, существует ли одно уникальное совпадение для ввода.

Спасибо @Arnauld за указание, что это не удалось [[1,0],[0]]; сейчас исправлено.

Спасибо @JonathanAlan за сохранение 2 байта!

объяснение

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 # (интерактивный компилятор Visual C #) , 303 227 байт

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

Выдает исключение, если true, работает нормально, если false.

Попробуйте онлайн!

Wolfram Language (Mathematica) , 85 88 байт

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

Попробуйте онлайн!

+3 исправлено.

Грубая сила: для всех баз со значениями посмотрите, соответствует ли полученная пирамида заданной форме, и проверьте, равно ли общее число совпадений 1. Принимает входные данные в виде списка уровней, сначала базы, с представлением пропущенных чисел.1..(sum of all numbers)0

05AB1E , 25 байтов

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

Принимает слои пирамиды в перевернутом порядке, от основания до кончика (то есть [[0,0,0,1],[0,2,0],[0,0],[10]]).

Кроме того, кажется, что где-то в 05AB1E есть ошибка .Γвнутри карты .. ©...®šДолжно быть только ...yš-1 байт ..

Попробуйте онлайн или проверьте еще несколько тестов .

Незначительная альтернатива для равных байтов ©.ΓüO}®šможет быть [Ðg#ü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 байт

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]

Принимает вверх ногами пирамиду, например [[0,0,0,1],[0,2,0],[0,0],[10]].

Попробуйте онлайн!

Подход грубой силы в Хаскеле:

• создать все возможные базовые слои t( mapM(\_->[1..sum(sum<$>x)])x), где числа идут от 1 до суммы всех чисел во входной пирамиде
• создать пирамиду из t( iterate(z(+)=<<tail)t)
• сравнить каждый слой поэлементно с input ( z(z(#))x). Функция сравнения a # bвозвращает, Trueесли оба числа равны или равны aнулю ( a*b==a*a).
• возьмите 1для каждой соответствующей пирамиды и сравните полученный список с одноэлементным списком [1].