Проблема декантации

23

Учитывая, что N графинов (0 < N <10), в которых может содержаться C 0 ... C N-1 литров (0 < C <50), и цель G литров, пожалуйста, определите, возможно ли достичь этой цели, используя только следующие действия:

  • Заполнить графин
  • Пустой графин
  • Налейте из одного графина в другой, пока тот, на который вылили, не заполнится, или тот, из которого выливают, пуст

Целевое количество G должно быть количеством воды в одном из контейнеров в конце. Вы не можете иметь «выходной графин».

Примеры

N : 2
C 0 : 5
C 1 : 12
G : 1
Результат: Да

N : 3
C 0 : 6
C 1 : 9
C 2 : 21
G : 5
Результат: нет

Подсказка: чтобы рассчитать, возможно ли это, проверьте, делится ли G на GCD емкостей. Также убедитесь, что он поместится в контейнере.

Помните, что это код-гольф , поэтому выигрывает код с наименьшим количеством байтов.

Leaderboards

Вот фрагмент стека, который генерирует как регулярную таблицу лидеров, так и обзор победителей по языкам.

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

# Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Если вы хотите включить в заголовок несколько чисел (например, потому что ваш результат равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:

# Perl, 43 + 2 (-p flag) = 45 bytes

Вы также можете сделать название языка ссылкой, которая затем будет отображаться во фрагменте списка лидеров:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Показать фрагмент кода

code-golf math Оливер Ни
источник
Связанный.
Мартин Эндер,
Есть ли «выходной графин»? Ака, если у меня есть графин 1 размера, возможна ли какая-нибудь емкость?
Натан Меррилл
@MartinEnder Ааа. Исправлена.
Оливер Ни
@NathanMerrill Не существует «графин вывода». Вы должны быть в состоянии получить его в одном из данных графинов.
Оливер Ни
9
Этот же вызов был в песочнице .
xnor

Ответы:

5

Желе , 9 8 7 байт

-1 байт благодаря @Dennis (используйте целочисленное деление :, а не не меньше чем <¬)

Ṁ:a⁸g/ḍ

TryItOnline

Как?

Ṁ:a⁸g/ḍ - Main link: capacities, goal
Ṁ       - maximum capacity
 :      - integer division with goal (effectively not less than goal since non-0 is True)
  a     - and
   ⁸    - left argument (capacities)
    g/  - gcd reduce over list (gcd of capacities)
      ḍ - divides
Джонатан Аллан
источник
17

Haskell, 35 байт

l%n=n`mod`foldr1 gcd l<1&&any(>=n)l

Эта статья доказывает результат, который значительно упрощает проблему. Опора 1 говорит, что

Вы можете достичь цели именно тогда, когда это:

  • Кратный наибольшему общему делителю (gcd) мощностей,
  • Максимальная максимальная вместимость

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

Звоните оператору %как [3,6,12]%9.

37-байтовая альтернатива:

l%n=elem n[0,foldr1 gcd l..maximum l]
XNOR
источник
Я считаю, что цель должна вписываться в один из графинов, она должна быть меньше объема самого большого графина (на основании комментария @ Oliver «Вы должны иметь возможность поместить его в один из предоставленных графинов».).
m-chrzan
Удобно, что на самом деле это определение используется в статье, и я неправильно понял, так что это легко исправить.
xnor
6

05AB1E , 9 8 9 байт

Использует кодировку CP-1252

ZU¿%²X>‹‹

объяснение

          # true if
   %      # target size modulo
ZU¿       # gcd of decanter sizes
        ‹ # is smaller than
    ²X>‹  # target size is less than or equal to max decanter size

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

Сохраненный 1 байт, используя уловку «меньше» из ответа MATL Луиса Мендо

Emigna
источник
1
используя менее чем трюк ... который я узнал от Денниса :-)
Луис Мендо
Фактический ответ по-прежнему 9 байтов ;-)
ETHproductions
@ETHproductions Ой! Кажется, я только обновил объяснение и ссылку TIO, а не фактический код. Спасибо :)
Emigna
5

MATL , 10 байт

&Zd\&G<~a<

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

Это использует подход @ xnor .

&Zd    % Take array C as input. Compute the gcd of its elements
\      % Take number G as input. Compute that number modulo the above. Call this A
&G     % Push the two inputs again: C, then G
<~a    % Gives 1 if some element of C is at least G; 0 otherwise. Call this B
<      % Gives true if A is 0 and B is 1; otherwise gives false
Луис Мендо
источник
5

Excel: 43 байта

=AND(MOD(A10,GCD(A1:A9))=0,A10<=MAX(A1:A9))

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

Как использовать:
Положите эту формулу в любом месте, кроме A1-A10.
Затем введите объемы Деканта, содержащие объемы в ячейках A1: A9 (поскольку число декантов фиксировано) и цель в A10. клетки без декантов должны быть оставлены пустыми. Куда бы вы ни поместили формулу, результат будет. ИСТИНА, если вы можете достичь цели, ЛОЖЬ, если вы не можете.


источник
5

JavaScript (ES6), 58 байт

(n,a)=>a.some(e=>n<=e)&n%a.reduce(g=(d,e)=>d?g(e%d,d):e)<1

Еще один порт ответа @ xnor. Да, я reduceснова использую !

Нил
источник
3
Альтернативная e=>n<=e
подфункция
4

Сетчатка , 39 байт

\d+
$*
^(?>(1+)(,?\1)*;)(\1+)$(?<=\3.+)

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

6,9,21;5

Выход 0(ложно) или 1(правдиво).

Попробуйте онлайн! (Первая строка включает набор тестов, разделенных переводом строки.)

объяснение

\d+
$*

Это просто преобразует ввод в унарный. После этого мы просто сопоставляем действительные входные данные с одним регулярным выражением:

^(?>(1+)(,?\1)*;)(\1+)$(?<=\3.+)

Часть внутри (?>...)находит GCD. Мы делаем это, находя самую большую подстроку, 1+с которой мы можем сопоставить все графины (допуская опционально ,только после полного соответствия GCD). Сама атомарная группа ( (?>...)), так что механизм регулярных выражений не возвращается к делителям GCD, если целевой объем не может быть сопоставлен (в противном случае группа 1будет в некоторой точке уменьшена до совпадения с одним, 1и все входные данные будут достоверными) ,

Найдя GCD, мы пытаемся сопоставить целевой объем с кратным простым (\1+)$.

Наконец, мы проверяем, что целевой объем не превышает емкость самого большого графина, гарантируя, что объем может быть сопоставлен с любым графином (?<=\3.+).

Мартин Эндер
источник
3

Рубин, 35 байт

->n,g{g<=n.max&&1>g%n.reduce(:gcd)}
м-chrzan
источник
2

PARI / GP , 31 байт

Довольно просто. Проверка max ( vecmax) очень дорогая, мне интересно, можно ли это сделать лучше.

f(c,g)=g%gcd(c)<1&&vecmax(c)>=g
Чарльз
источник
2

Perl, 47 байт

Включает +2 для -ap

Запустите с размерами банок в первой строке STDIN и целевыми банками во второй строке:

decanter.pl; echo
2 5 12
1
^D

decanter.pl:

#!/usr/bin/perl -p
$_=($_<@G)>$_%$=;$=--while@G[@F]=grep$_%$=,@F

Это решение необычно тем, что обрабатывает входные данные построчно и выводит что-то для каждого из них. Вывод для первой строки был тщательно продуман, чтобы быть пустым, в то время как вторая строка печатает решение. Два байта теряется на ()потому , что <и >предназначены для неассоциативных в Perl.

Решение регулярных выражений также хорошо, но 49 байтов:

#!/usr/bin/perl -p
s/\d+/1x$&/eg;$_=/^(?>(1+)( |\1)*:)(\1+)$/&/$3./

(некоторые детали, украденные из раствора Retina)

Для этого введите STDIN в виде jar-файлов, разделенных пробелами, и цель после ::

decanter.pl <<< "2 5 12:1"

Трудно превзойти языки со встроенным gcd(21 байт) и max(7 байт) для этого ...

Тон Хоспел
источник
0

Scala, 90 53 байта

def h(g:Int,a:BigInt*)=a.max>g&&a.reduce(_ gcd _)%g<1

Работает в основном так же, как и другие ответы, но в Scala нет встроенной функции gcd. Scala имеет встроенную функцию gcd, но только для BigInt.

corvus_192
источник