В настольной игре «Поселенцы Катана» есть пять типов ресурсов: Кирпич, Бревно, Руда, Пшеница и Овцы. Строительство поселения стоит Кирпич, Бревно, Пшеница и Овца. Однако вы также можете торговать четырьмя одинаковыми ресурсами, чтобы получить ресурс другого типа. Например, если у вас в руке было четыре руды, вы могли бы обменять их всех и получить одну овцу.

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

Твое задание

Ввод будет последовательностью букв B, L, O, W, и S, взятые в любом приемлемом формате. Эти буквы соответствуют пяти типам ресурсов, приведенным выше. Вы должны указать, есть ли у меня ресурсы, необходимые для построения поселения, принимая во внимание возможность торговли четырьмя видами.

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

Заметки

• Вам не нужно выводить, какие сделки мне нужно совершить или сколько расчетов я мог бы построить. Простое «да» или «нет» подойдет.
• Вы не можете предполагать, что входные данные находятся в каком-либо определенном порядке. В частности, вы не можете предполагать, что ресурсы одного и того же типа сгруппированы, так OBLSOчто это допустимый ввод.
• Это проблема принятия решения , поэтому вы можете использовать любое значение, которое хотите обозначить «да» и «нет», если два выбранных значения различны и согласованы.
• Здесь нас интересуют только те правила, которые перечислены выше. Более сложные правила Settlers of Catan, такие как торговля с другими игроками или в гаванях, здесь не актуальны.
• Входные символы ( B, L, O, W, S) могут быть заменены другими значениями , если это проще для конкретного языка выбора, до тех пор, пока пять различных входов. Если вы используете другие входные значения, укажите их в своем ответе.

Примеры

BLWS -> Yes
OOOOWLB -> Yes (trade four O for a S)
OOW -> No
BBBO -> No
(empty input) -> No
BBBBLW -> No
BBBBBLW -> Yes (trade four B for a S)
OOOOOOOOOOOOOOOO -> Yes (sixteen O; trade for B, L, W, S)
BLBLBLBLBL -> Yes (trade L for W and B for S)
BLSWBLSWBLSW -> Yes (extra, unused resources are ignored)

Python 2 , 54 байта

lambda s:sum((s+"BLSW"*3).count(n)/4for n in"BLSWO")>3

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

Для каждого из наших ресурсов, мы считаем число «свобод» данных при наличии n этого ресурса. Свобода представляет возможность заполнить один из слотов кирпичного бревна-пшеницы-овцы, который мы должны заполнить, чтобы рассчитаться, учитывая тот факт, что мы можем преобразовать наши ресурсы.

Для всех BLSW, имеющих один ресурса дает нам одну такую ​​свободу, а каждое дополнительное превышение 4 дает нам другую. Правило подсчета свободы выглядит так:

* Having 1 brick/log/wheat/sheep gives 1 freedom.
* Having 5 bricks/logs/wheat/sheep gives 2 freedoms.
* Having 9 bricks/logs/wheat/sheep gives 3 freedoms.
* …

Так п кирпичей / бревен / пшеницы / овец дают ⌊ (n + 3) / 4⌋ свобод.

Для руд учитываются только лишние четверки. Правило подсчета свободы выглядит так:

* Having 4 ores gives 1 freedom.
* Having 8 ores gives 2 freedoms.
* Having 12 ores gives 3 freedoms.
* …

Так , п руды дают ⌊n / 4⌋ свободы.

Теорема: мы можем урегулировать, если и только если у нас есть ≥ 4 таких «свобод».

Таким образом, мы считаем наши свободы и проверяем, есть ли ≥ 4 из них. Чтобы обрабатывать подсчет руд как ⌊n / 4⌋, а других ресурсов ⌊ (n + 3) / 4⌋, мы искусственно увеличиваем количество других ресурсов на 3, а затем считаем countn / 4⌋ для всех из них. Мы делаем это путем сопоставления (s+"BLSW"*3).countвместоs.count .

доказательство :

• Предположим, мы можем решить. Затем для каждого из [B, L, S, W] мы либо (а) использовали 1 из того ресурса, который у нас уже был, либо (б) пожертвовали 4 какого-то другого ресурса (включая руды) для его создания. В любом случае мы учитываем как минимум 1 свободу по вышеуказанным правилам. Итак, у нас ≥ 4 свободы.

• Предположим , что мы имеем 4 свободы, к из которых из - за «перегибы» (каждая свобода от руд избыток, и каждая свобода от других ресурсов , в прошлом первый также) и 4-к из которых являются свидетель , владеющих не менее одной кирпич / бревно / пшеница / овца (тот, который дал «первую свободу»). Затем мы заполняем 4-k слоты кирпичом / бревном / пшеницей / овцой, которые дали нам первую свободу, и заполняем оставшиеся k слотов путем преобразования наших эксцессов. Все 4 слота заполнены, и мы можем решить. Очевидно, мы можем сделать это, если у нас более 4 свобод.

Это доказательство отстой, но я сонный. Я уверен, что есть лучшее объяснение.

Python 2 ,  52  51 байт

-1 байт благодаря Люку (заменить >=0на <0, инвертируя False/True результаты)

lambda h:sum(~-(h+"O").count(c)/4for c in"BOWLS")<0

Безымянная функция принимает строку символов B , O , W , L и S (как в OP) и возвращаетFalse если вы можете решить или Trueнет.

Попробуйте онлайн!(принуждает вывод к yes/noOP).

Как?

Это порт моего желе ответа. Нам нужно наверстать упущенное B , W , L или S из остатка после использования одного из них. Таким образом, мы можем добавить дополнительный O к нашей руке, затем уменьшить все счетчики на единицу, затем целочисленно разделить все счетчики на четыре и затем сложить - если результат равен нулю или более, мы можем рассчитать (либо потому, что не было пропущенных необходимых ресурсов или потому что мы можем торговать, чтобы получить недостающий (ые).

lambda h:sum(~-(h+"O").count(c)/4for c in"BOWLS")<0
lambda h:                                           - a function that takes h (a string)
                                 for c in"BOWLS"    - for each letter, c, in "BOWLS":
                h+"O"                               -   append "O" to h
               (     ).count(c)                     -   count c instances
              -                                     -   negate
             ~                                      -   bitwise not (this is -x-1)
                               /4                   -   integer divide by 4
                                                    -    (NB: -1 and 0 are not affected)
         sum(                                   )   - sum the five values
                                                 <0 - less than zero? (inverted result)

Pyth , 14 байт

gsm/t/+Q4d4U5Z

Попробуй это здесь! или Проверьте все контрольные примеры.

Pyth ,  31 27 17  16 байт

<3s/R4/L+Q*3U4U5

Проверьте контрольные примеры.

Как это работает?

Объяснение № 1

gsm/t/+Q4d4U5Z   - Full program.

  m        U5    - Map over the range [0, 5) with a variable d.
      +Q4        - The input, with a 4 appended (this corresponds to O)
     /   d       - Count the occurrences of the current value in ^.
    t            - Decrement.
   /      4      - Integer division by 4.
 s               - Sum
g            Z   - Is non-negative (is the sum ≥ 0)?  
                 - Output implicitly.

Объяснение № 2

<3s/R4/L+Q*3U4U5   - Full program.

          *3U4     - The range [0, 4) repeated 3 times.
        +Q         - The input with ^ appended.
      /L      U5   - Count the occurrences of each element in [0, 5) in ^.
   /R4             - Integer division of each by 4.
  s                - Sum.
<3                 - Is higher than 3?
                   - Output implicitly.

Вот коды, используемые моей программой:

B -> 0
L -> 1
S -> 2
W -> 3
O -> 4

Желе ,  13  12 байт

;5ċЀ5’:4S>-

Монадическая ссылка, принимающая список чисел, представляющих ресурсы, которыми вы владеете, и возвращающая, 1если вы можете успокоиться или0 нет.

Ресурсы, 1, 2, 3, 4, 5где 5представляет руды .

Попробуйте онлайн! или посмотрите набор тестов (используя OP IO).

Как?

Идея состоит в том, чтобы сначала посчитать ресурсы по типу, а затем уменьшить все значения B , L , W и S на один - если мы не подсчитали ни одного из этих четырех, то у них теперь будут записи -1 - нам нужно получить их из наших оставшихся ресурсов (это на самом деле достигается путем добавления дополнительного O ( 5) и уменьшения всех пяти счетчиков на 1 ). Затем мы делим целое число на все эти значения на четыре, чтобы увидеть, сколько единиц мы можем обменять с каждым из наших оставшихся счетчиков по типу ресурса, не влияя на счетчики -1 и 0 (обратите внимание, что -1 целое число, деленное на четыре,-1 , а не 0). Наконец, мы складываем значения и проверяем, будет ли результат больше или равен нулю (здесь можно использовать больше -1 , поскольку у нас всегда есть целые числа).

;5ċЀ5’:4S>- - Link: list of numbers (BLWSO:12345) e.g. [3,2,2,2,2,2,5,5,5,5] (WLLLLLOOOO)
;5           - concatenate a five                       [3,2,2,2,2,2,5,5,5,5,5]
     5       - literal 5
   Ѐ        - map across implicit range(5) = [1,2,3,4,5]:
  ċ          -   count                                  [ 0, 5, 1, 0, 5]
      ’      - decrement (vectorises)                   [-1, 4, 0,-1, 4]
       :4    - integer divide by four                   [-1, 1, 0,-1, 1]
         S   - sum                                      0
           - - literal -1                              -1
          >  - greater than?                            1

Java 8, 101 байт

Лямбда из int[]в boolean. Присвоить Function<int[], Boolean>.

a->{int h,f[]=new int[5],i=0;for(int x:a)f[x]++;for(h=f[4]/4;i<4;)h+=--f[i]>>-1|f[i++]/4;return~h<0;}

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

Вход и выход

Входные данные - это массив целых чисел от 0 до 4 включительно. 4 представляет руду, а другие отображения несущественны. Мои тестовые примеры - это прямые переводы тех, кто в вопросе, с 0 как Кирпич, 1 как Бревно, 2 как Пшеница и 3 как Овцы.

Выход - можно ли построить поселение.

Ungolfed

a -> {
    int
        h,
        f[] = new int[5],
        i = 0
    ;
    for (int x : a)
        f[x]++;
    for (h = f[4] / 4; i < 4; )
        h += --f[i] >> 31 | f[i++] / 4;
    return ~h < 0;
}

объяснение

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

Линия

h += --f[i] >> 31 | f[i++] / 4;

корректируется hсоответствующим образом независимо от того, есть ли ресурсы (дефицит) или есть хотя бы один ресурс (излишек). f[i]уменьшается для учета требуемого ресурса в случае излишка, производя -1 в случае нехватки. Сдвиг вправо со знаком сокращает выражение до 0 (избыточный регистр) или -1 (регистр нехватки), так что побитовое ИЛИ с числомf[i++] / 4 избыточных четверок (в случае с избыточным кодом) не влияет на случай дефицита, но приводит к числу Сам в избытке дела.

Подтверждения

• -9 байт благодаря Nevay, мастеру битов

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

^
BBBLLLWWWSSS
O`.
((.)\2{3}.*){4}

Попробуйте онлайн! Объяснение: Построение поселения требует 4 ресурсов, которые являются либо вашими первыми B, L, W или S, либо любыми другими 4 ресурсами того же типа. Это эквивалентно добавлению трех из каждого из этих четырех типов ресурсов, а затем подсчету, чтобы увидеть, есть ли у вас четыре набора из четырех.

Желе , 23 байта

œ-4R¤©Ġs€4ẎL€>3+®e€$S>3

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

Обратитесь к следующей таблице для значений:

B: 1
L: 2
O: 5
W: 3
S: 4

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

O`.
O{4}
a
}`([^a])\1{4}
$1a
O

D`[^a]
.{4}

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

Python 3 , 79 78 байт

Редактировать: -1 байт благодаря @ Mr.Xcoder

lambda x:3<sum((a>0)+~-a*(a>1)//4for a in map(x.count,"BLSW"))+x.count("O")//4

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

MATL , 19 байт

Oh!5:=s4&\w4:)ghs3>

Ввод - это числовой вектор строки, в котором буквы представлены в виде чисел следующим образом:

B: 1
L: 2
W: 3
S: 4
O: 5

Вывод 1для правды,0 для ложных.

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

Как это работает

1. Подсчет вхождений каждого ресурса.
2. Div-мод им на 4.
3. Посчитайте, сколько из остатков для первых четырех ресурсов (букв BLWS) отличны от нуля. Это дает число с .
4. Суммируйте коэффициенты. Это дает число с .
5. Выведите ли c + s ≥ 4.

Код комментария

Oh     % Append 0 to implicit input. This is just in case inpout is empty
!      % Convert into column vector
5:     % Push row vector [1 2 3 4 5]
=      % Compare for equality, element-wise with broadcast
s      % Sum of each column. Gives number of times that each entry of
       % [1 2 3 4 5] appears in the input
4&\    % Mod-div 4, element-wise. Pushes vector of remainders and then vector
       % of quotients of division by 4
w      % Swap. Brings remainders to top
4:)    % Get the first four entries
g      % Convert to logical. This transforms non-zero values into 1
h      % Concatenate with vector of quotients
s      % Sum
3>     % Does the result exceed 3? Implicitly display

> <> 61 байт

510ap\~1(n;
1+$ap> i:0(?v8%:ag
0:ga:v?=5:+1<$-}$,4-%4:-}-${:)

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

Использует следующее сопоставление ресурсов:

O -> 0
B -> 1
L -> 2
W -> 3
S -> 4

Это действительно не имеет значения , что отображение используются, до тех пор , пока они в диапазоне 0-4, и 0используются для О. Позволяет использовать то , что ищешь комбинацию BLWSявляется таким же , как поиск комбинации , OBLWSа уже имея Oв системе рука.

05AB1E , 19 байтов

0 -> Руда
1 -> Кирпич
2 -> Бревно
3 -> Пшеница
4 -> Овцы

Возвращает 0, когда ложь, и 1 в противном случае.

{γvyDĀi¼¨}g4÷}¾)O3›

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

Объяснение:

{γvyDĀi¼¨}g4÷}¾)O3› Implicit input, e.g. 0030201
{                   Sort -> 0000123
 γ                  Split into chunks of consecutive elements: [0000, 1, 2, 3]
  vy                For each chunk...
    DĀ                 ...is different than 0?
      i¼¨}                ...if true: increment the counter by 1, and 
                              remove 1 element from the chunk
          g4÷         ...divide the number of elements by 4
             }      End For
              ¾     Push the counter
               )    Wrap the entire stack in a list
                O   Sum of that list
                 3> True if > 3
                    Implicit output

Неконкурентное решение: 17 байт

В 05AB1E была ошибка, когда я впервые представил это решение, когда некоторые операторы плохо обрабатывали пустые вводы. Это привело к ответу на это решение1 на пустой вход. Теперь это исправлено, поэтому это решение работает просто отлично.

Разница здесь в том, что мы добавляем руду до удаления одного из каждого ресурса без разбора, считая количество ресурсов, удаленных таким образом. Затем мы уменьшаем счетчик на 1, чтобы получить правильное число B, L, W и S.

0«{γε¨g4÷¼}O¾<+3›

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

JavaScript (SpiderMonkey) , 116 байт

s=>Array.from("BLOWS").reduce((m,c)=>Math.floor(((s+"BLSW".repeat(3)).match(new RegExp(c,'g'))||"").length/4)+m,0)>3

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

Супер Clunky плохой ответ. Я уверен, что это может быть убрано больше. Метод вдохновлен ответом Линн в этой теме.

Котлин , 131 129 байт

представление

fun r(i:String):Any=i.split("").groupingBy{it}.eachCount().map{when(it.key){
""->0
"O"->it.value/4
else->(it.value+3)/4}}.sum()>3

Тест

fun r(i:String):Any=i.split("").groupingBy{it}.eachCount().map{when(it.key){
""->0
"O"->it.value/4
else->(it.value+3)/4}}.sum()>3

data class TestData(val input:String, val output:Boolean) {
    fun run() {
        val out = r(input)
        if (out != output) {
            throw AssertionError("Failed test: ${this} -> $out")
        }
    }
}
fun main(args: Array<String>) {
    listOf(

            TestData("BLWS", true),
            TestData("OOOOWLB", true),
            TestData("OOW", false),
            TestData("BBBO", false),
            TestData("", false),
            TestData("BBBBLW", false),
            TestData("BBBBBLW", true),
            TestData("OOOOOOOOOOOOOOOO", true),
            TestData("BLBLBLBLBL", true),
            TestData("BLSWBLSWBLSW", true)
    ).forEach(TestData::run)
    println("Test passed")
}

Не может работать на TryItOnline, но работает на try.kotlinlang.org