Сколько разделов содержат только идеальные квадраты?

16

Учитывая неотрицательное целое число или список цифр, определите, каким образом число может быть сформировано путем объединения квадратных чисел, которые могут иметь начальные нули.

Примеры

input -> output # explanation
164 -> 2 # [16, 4], [1, 64]
101 -> 2 # [1, 01], [1, 0, 1]
100 -> 3 # [100], [1, 00], [1, 0, 0]
1 -> 1 # [1]
0 -> 1 # [0]
164900 -> 9 # [1, 64, 9, 0, 0], [1, 64, 9, 00], [1, 64, 900], [16, 4, 900], [16, 4, 9, 0, 0], [16, 4, 9, 00], [16, 49, 0, 0], [16, 49, 00], [16, 4900]

правила

  • Применяются стандартные лазейки
  • Это поэтому выигрывает самый короткий ответ в байтах
HyperNeutrino
источник
Можем ли мы принять ввод как список цифр?
полностью человек
почему 1 -> 1, но 0 -> 0?
Иона
@ Джона Опечатка ... xD
HyperNeutrino
1
@totallyhuman Конечно.
HyperNeutrino

Ответы:

7

Haskell , 135 байт

s x=any((x==).(^2))[0..x]
c(a:b:x)=a*10+b:x
c x=x
h[x]=1>0
h x=(s.head)x
f x@(_:_:_)|y<-until h c x=f(tail y)+f(c y)
f x=sum[1|any s x]

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

Возможно, еще не очень хорошо играли в гольф, но это удивительно сложная проблема

Пост Рок Гарф Хантер
источник
7

Желе , 8 байт

ŒṖḌƲẠ€S

Монадическая ссылка, содержащая список цифр и возвращающая неотрицательное целое число.

Попробуйте онлайн! или посмотрите набор тестов .

Как?

ŒṖḌƲẠ€S - Link: list of digits              e.g. [4,0,0,4]
ŒṖ       - all partitions                         [[4,0,0,4],[4,0,[0,4]],[4,[0,0],4],[4,[0,0,4]],[[4,0],0,4],[[4,0],[0,4]],[[4,0,0],4],[4,0,0,4]]
  Ḍ      - convert from decimal list (vectorises) [[4,0,0,4],[4,0,   4 ],[4,    0,4],[4,      4],[   40,0,4],[   40,    4],[    400,4],     4004]
   Ʋ    - is square? (vectorises)                [[1,1,1,1],[1,1,   1 ],[1,    1,1],[1,      1],[    0,1,1],[    0,    1],[      1,1],        0]
     Ạ€  - all truthy? for €ach                   [        1,          1,          1,          1           0,            0,          1,        0]
       S - sum                                    5
Джонатан Аллан
источник
6

Haskell , 88 байт

f x=sum[0.5|y<-mapM(\c->[[c],c:" "])x,all((`elem`map(^2)[0..read x]).read).words$id=<<y]

Определяет функцию, fкоторая принимает строку и возвращает число с плавающей запятой. Очень медленно. Попробуйте онлайн!

объяснение

Я использую мой совет Haskell для вычисления всех разделов строки с mapMи words. Фрагмент mapM(\c->[[c],c:" "])xзаменяет каждый символ 'c'строки xлибо одноэлементной строкой, "c"либо двухэлементной строкой "c "и возвращает список всех возможных комбинаций. Если я возьму один из результатов, yобъединю его и вызову wordsрезультат, он будет разбит на вставленные пробелы mapM. Таким образом, я получаю все разбиения xв смежные подстроки. Затем я просто подсчитываю те результаты, где каждый элемент разбиения является идеальным квадратом (находя его в списке [0,1,4,9,..,x^2]). Предостережение заключается в том, что каждый раздел считается дважды, с пробелом и без него, поэтому я беру сумму0.5s вместо 1s; Вот почему тип результата является плавающим.

f x=                       -- Define f x as
 sum[0.5|                  -- the sum of 0.5 for
  y<-                      -- every y drawn from
  mapM(\c->[[c],c:" "])x,  -- this list (explained above)
                           -- (y is a list of one- and two-element strings)
  all(...)                 -- such that every element of
                 id=<<y]   -- concatenated y
          .words$          -- split at spaces satisfies this:
                           -- (the element is a string)
   (...).read              -- if we convert it to integer
    `elem`                 -- it is an element of
    map(^2)                -- the squares of
    [0..read x]            -- the numbers in this list.
Zgarb
источник
4

Python 3 , 148 139 135 134 байтов

10 байтов благодаря Арнольду Палмеру.

def f(a):
 s=[a[:1]]
 for i in a[1:]:s=sum([[x+[i],x[:-1]+[x[-1]*10+i]]for x in s],[])
 return sum({n**.5%1for n in x}=={0}for x in s)

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

Пропитанная монахиня
источник
Я бы дважды проверил это, но я верю, что это работает. 140 символов.
Арнольд Палмер
Я дурак и оставил пространство между %1и for...
Арнольд Палмер
Замена [[a[0]]]с [a[:1]]сохранением байта
Арнольд Палмер
Вместе мы переиграли Хаскелла.
Утренняя монахиня
Самое приятное то, что это было отчасти благодаря сетам, которыми я никогда не пользовался, пока ты вчера не разместил мой ответ на вопрос о черепахе .
Арнольд Палмер
2

Mathematica, 141 байт

Count[FreeQ[IntegerQ/@Sqrt[FromDigits/@#],1<0]&/@(FoldPairList[TakeDrop,s,#]&/@Flatten[Permutations/@IntegerPartitions[Length[s=#]],1]),1>0]&


ввод (список цифр)

[{1,6,4}]

J42161217
источник
Я думаю, что это дает неправильный ответ для 1649: я считаю три раздела, которые образуют квадраты (а именно {1,64,9}, {16,4,9}и {16,49}), но ваша функция возвращает 4.
Не дерево
Кроме того, я заметил, что вы использовали конструкции, как Table[(function of s[[i]]),{i,Length[s=(stuff)]}]несколько раз; Вы обычно можете сыграть в гольф до (function of #)&/@(stuff).
Не дерево
1
@ Нет, ты абсолютно прав! Я сделал много изменений, следовал вашим инструкциям, и это работает как шарм! спасибо
J42161217
2

Python 2 , 173 163 байта

lambda s:len([l for l in[''.join(sum(zip(s,[','*(n>>i&1)for i in range(len(s))]+['']),())).split(',')for n in range(2**~-len(s))]if {int(x)**.5%1for x in l}=={0}])

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

Редактировать: 10 байтов сохранено благодаря ArnoldPalmer

Час Браун
источник
1
Можете ли вы сохранить байт, используя .5вместо 0.5?
Числовой маньяк
Вы можете. Вы также можете сохранить некоторые байты с помощью того же трюка, который я использовал для публикации в Leaky Nun's Python 3. Кроме того, в вашем ответе было напечатано не количество элементов, а сами элементы, поэтому я добавил это. Если вы хотите сохранить полученный результат, он минус дополнительные 5 байтов. 163 байта
Арнольд Палмер
Хороший трюк с пониманием, Арнольд.
Час Браун