W grze planszowej The Settlers of Catan istnieje pięć rodzajów zasobów: cegła, kłoda, ruda, pszenica i owca. Budowa osady kosztuje cegłę, kłodę, pszenicę i owcę. Możesz jednak także wymienić cztery identyczne zasoby, aby uzyskać zasób innego typu. Na przykład, jeśli masz w ręku cztery rudy, możesz wymienić je wszystkie i zdobyć jedną owcę.

Twoim zadaniem jest ustalenie, czy mogę zbudować osadę, biorąc pod uwagę moją rękę.

Twoje zadanie

Wejście będzie ciągiem liter B, L, O, W, i S, podjęte w dowolnym rozsądnym formacie. Litery te odpowiadają pięciu typom zasobów podanym powyżej. Powinieneś wypisać, czy mam zasoby niezbędne do zbudowania ugody, biorąc pod uwagę możliwość handlu tego rodzaju.

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.

Notatki

• Nie musisz generować, jakie transakcje muszę wykonać ani ile rozliczeń mogę zbudować. Wystarczy proste „tak” lub „nie”.
• Być może nie przyjąć, że wejście jest w dowolnej kolejności określonej. W szczególności nie można zakładać, że zasoby tego samego typu są pogrupowane razem, więc OBLSOjest to prawidłowe dane wejściowe.
• Jest to problem decyzyjny , więc możesz użyć dowolnej wartości, którą chcesz oznaczać „tak” i „nie”, o ile dwie wybrane wartości są różne i spójne.
• Jedyne zasady, którymi się tu zajmujemy, to te wymienione powyżej. Bardziej skomplikowane zasady Osadników z Catanu, takie jak handel z innymi graczami lub w portach, nie są tutaj istotne.
• Znaki wejściowe ( B, L, O, W, S) można zastąpić innymi wartościami, jeśli jest to łatwiejsze dla danego języka wyboru, tak długo, jak istnieje pięć odrębnych wejść. Jeśli używasz innych wartości wejściowych, podaj je w swojej odpowiedzi.

Przykłady

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 bajty

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

Wypróbuj online!

Dla każdego z naszych zasobów liczymy liczbę „swobód” podanych przez posiadanie n tego zasobu. Wolność stanowi okazję do wypełnienia jednego z miejsc na cegły z kłody pszenicy i owiec, które musimy wypełnić, aby się osiedlić, biorąc pod uwagę fakt, że możemy przekształcić nasze zasoby.

Dla wszystkich BLSW posiadanie jednego z zasobów daje nam taką swobodę, a każdy dodatkowy nadmiar 4 daje nam inną. Reguła liczenia wolności wygląda następująco:

* 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.
* …

Tak więc n cegieł / kłód / pszenicy / owiec daje ⌊ (n + 3) / 4⌋ wolności.

W przypadku rud liczy się tylko nadmiar czwórki. Reguła liczenia wolności wygląda następująco:

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

Więc n rudy dać ⌊n / 4⌋ wolności.

Twierdzenie: możemy rozstrzygnąć wtedy i tylko wtedy, gdy mamy ≥ 4 takie „wolności”.

Dlatego liczymy nasze wolności i sprawdzamy, czy jest ich ≥ 4. Aby obsłużyć liczenie rud jako ⌊n / 4⌋, ale innych zasobów ⌊ (n + 3) / 4⌋, sztucznie zwiększamy liczbę pozostałych zasobów o 3, a następnie liczymy ⌊n / 4⌋ dla wszystkich z nich. Robimy to poprzez mapowanie (s+"BLSW"*3).countzamiast s.count.

Dowód :

• Załóżmy, że możemy się osiedlić. Następnie dla każdego z [B, L, S, W] albo (a) wykorzystaliśmy 1 z tego zasobu, który już mieliśmy, lub (b) poświęciliśmy 4 inne zasoby (w tym rudy), aby je utworzyć. W obu przypadkach liczymy co najmniej 1 wolność według powyższych zasad. Mamy więc 4 swobody.

• Załóżmy, że mamy 4 swobód, z których k spowodowane są „ekscesy” (co wolność od rud jest nadmiar, a każda wolność od innych zasobów przeszłość pierwszy jest również) i 4-k, które są świadectwem posiadania co najmniej jednego cegła / kłoda / pszenica / owca (ta, która dała „pierwszą wolność”). Następnie wypełniamy 4-k szczeliny cegłą / kłodą / pszenicą / owcą, które dały nam pierwszą swobodę, i wypełniamy pozostałe k szczelin, przekształcając nasze ekscesy. Wszystkie 4 miejsca są zajęte i możemy się rozstrzygnąć. Oczywiście nadal możemy to zrobić, jeśli mamy więcej niż 4 swobody.

Ten dowód jest do kitu, ale jestem śpiący. Jestem pewien, że jest lepsze wytłumaczenie.

Python 2 ,  52  51 bajtów

-1 bajt dzięki Łuk (zastępuje >=0się <0, odwracając False/ Truewyników)

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

Nienazwana funkcja pobierająca ciąg znaków B , O , W , L i S (jak w OP) i zwracająca, Falsejeśli możesz się ustatkować, a Truejeśli nie.

Wypróbuj online! (wymusza wyjścieyes/nona OP).

W jaki sposób?

To jest port mojej odpowiedzi na żelki. Musimy uzupełnić brakujące B , W , L lub S z pozostałej części po użyciu jednego z nich. W związku z tym możemy dodać dodatkowe O do naszej ręki, następnie zmniejszyć wszystkie zliczenia o jeden, następnie liczbę całkowitą podzielić wszystkie zliczenia na cztery, a następnie zsumować - jeśli wynik wynosi zero lub więcej, możemy ustalić (albo dlatego, że nie brakowało wymaganych zasobów) lub ponieważ możemy handlować, aby zdobyć brakujący (e)).

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 bajtów

gsm/t/+Q4d4U5Z

Wypróbuj tutaj! lub Zweryfikuj wszystkie przypadki testowe.

Pyth ,  31 27 17  16 bajtów

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

Sprawdź przypadki testowe.

Jak to działa?

Wyjaśnienie nr 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.

Wyjaśnienie nr 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.

Oto kody używane przez mój program:

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

Galaretka ,  13  12 bajtów

;5ċЀ5’:4S>-

Monadyczny link przyjmujący listę liczb reprezentujących posiadane zasoby i zwracający, 1jeśli możesz się ustatkować, a 0jeśli nie.

Zasoby są 1, 2, 3, 4, 5tam, gdzie 5reprezentuje rudę .

Wypróbuj online! lub zobacz pakiet testowy (używając OP IO).

W jaki sposób?

Chodzi o to, aby najpierw policzyć zasoby według typu, a następnie zmniejszyć wszystkie liczby B , L , W i S o jeden - jeśli nie policzymy żadnych dla żadnej z tych czterech, będą one miały teraz wpisy -1 - musimy zdobyć je z naszych pozostałych zasobów (w rzeczywistości osiąga się to poprzez dodanie dodatkowego O ( 5) i zmniejszenie wszystkich pięciu liczb o 1 ). Następnie dzielimy liczby całkowite przez wszystkie te wartości przez cztery, aby zobaczyć, za ile jednostek możemy handlować przy każdej z naszych pozostałych liczb według typu zasobu, nie wpływając jednocześnie na liczby -1 i 0 (zauważ, że -1 podzielona przez liczbę całkowitą przez cztery to-1 , nie 0 ). Na koniec dodajemy wartości i sprawdzamy, czy wynik jest większy lub równy zero (tutaj można użyć wartości większej niż -1, ponieważ zawsze mamy liczby całkowite).

;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 bajtów

Lambda od int[]do boolean. Przypisz do 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;}

Wypróbuj online

Wejście i wyjście

Dane wejściowe to tablica liczb całkowitych od 0 do 4 włącznie. 4 oznacza Rudę, a inne odwzorowania są nieistotne. Moje przypadki testowe są bezpośrednimi tłumaczeniami tych, o których mowa, z 0 jako cegła, 1 jako kłoda, 2 jako pszenica i 3 jako owca.

Dane wyjściowe określają, czy można zbudować osadę.

Bez golfa

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

Wyjaśnienie

hto liczba poczwórnych zasobów dostępnych do handlu. Wykonujemy iterację nad każdym typem zasobów (z wyjątkiem Rudy), zwiększając hdla każdej czterokrotności dodatkowych zasobów, które mamy, i zmniejszając, gdy nie ma żadnych zasobów. Zatem naszym wynikiem jest to, czy hjest nieujemne.

Linia

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

dostosowuje hodpowiednio, niezależnie od tego, czy nie ma zasobów (niedobór), czy jest przynajmniej jeden zasób (nadwyżka). f[i]jest zmniejszany w celu uwzględnienia wymaganego zasobu w przypadku nadwyżki, dając -1 w przypadku niedoboru. Podpisane przesunięcie w prawo zmniejsza wyrażenie do 0 (przypadek nadwyżki) lub -1 (przypadek niedoboru), tak że bitowo LUB z liczbąf[i++] / 4 poczwórnych nadwyżek (w przypadku nadwyżki) nie ma wpływu w przypadku niedoboru, ale skutkuje liczbą sama w przypadku nadwyżki.

Podziękowanie

• -9 bajtów dzięki Nevay, mistrzowi bitów

Retina , 34 bajty

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

Wypróbuj online! Objaśnienie: Budowa osady wymaga 4 zasobów, które są albo twoimi pierwszymi B, L, W lub S, lub dowolnymi 4 innymi zasobami tego samego typu. Jest to równoważne z dodaniem trzech z każdego z tych czterech rodzajów zasobów, a następnie zliczeniem, aby sprawdzić, czy masz cztery zestawy czterech.

Galaretka , 23 bajty

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

Wypróbuj online!

Wartości znajdują się w poniższej tabeli:

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

Siatkówka , 43 bajty

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

D`[^a]
.{4}

Wypróbuj online!

Python 3 , 79 78 bajtów

Edycja: -1 bajt dzięki @ Mr.Xcoder

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

Wypróbuj online!

MATL , 19 bajtów

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

Dane wejściowe to numeryczny wektor wiersza, w którym litery są przedstawione w następujący sposób:

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

Wyjście jest 1na prawdę, 0na fałsz.

Wypróbuj online!: Sprawdź wszystkie przypadki testowe .

Jak to działa

1. Policz okazje każdego zasobu.
2. Div-mod je o 4.
3. Policz, ile reszt dla pierwszych czterech zasobów (liter BLWS) jest niezerowych. Daje to liczbę c .
4. Suma ilorazów. To daje liczbę s .
5. Wyjście, czy c + s ≥ 4.

Skomentowany kod

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 bajtów

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

Wypróbuj online!

Wykorzystuje następujące mapowanie zasobów:

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

To naprawdę nie ma znaczenia, co wykorzystywane jest odwzorowanie, tak długo, jak są one w przedziale 0-4, a 0służy do O. Wykorzystuje fakt, że szuka kombinacji BLWSjest taka sama jak szuka kombinacji OBLWSnatomiast już posiadające Oin dłoń.

05AB1E , 19 bajtów

0 -> Ruda
1 -> Cegła
2 -> Dziennik
3 -> Pszenica
4 -> Owca

Zwraca 0, gdy jest fałszem, a 1 w przeciwnym razie.

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

Wypróbuj online!

Wyjaśnienie:

{γ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

Rozwiązanie niekonkurencyjne: 17 bajtów

Wystąpił błąd w 05AB1E, kiedy po raz pierwszy przesłałem to rozwiązanie, w którym niektórzy operatorzy źle traktowali puste dane wejściowe. Spowodowało to odpowiedź tego rozwiązania 1na puste wejście. Zostało to już naprawione, więc to rozwiązanie działa dobrze.

Różnica polega na tym, że dodajemy rudę przed usunięciem każdego z zasobów, bez rozróżnienia, licząc liczbę zasobów usuniętych w ten sposób. Następnie zmniejszamy licznik o 1, aby uzyskać prawidłową liczbę B, L, W i S.

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

Wypróbuj online!

JavaScript (SpiderMonkey) , 116 bajtów

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

Wypróbuj online!

Super Clunky zła odpowiedź. Jestem pewien, że można by to bardziej wyczyścić. Metoda inspirowana odpowiedzią Lynn w tym wątku.

Kotlin , 131 129 bajtów

Uległość

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

Test

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")
}

Nie działa na TryItOnline, ale działa na try.kotlinlang.org