Dans le jeu de société The Settlers of Catan , il existe cinq types de ressources: brique, bûche, minerai, blé et mouton. La construction d'une colonie coûte une brique, une bûche, un blé et un mouton. Cependant, vous pouvez également échanger quatre ressources identiques pour obtenir une ressource d'un type différent. Par exemple, si vous aviez quatre minerais en main, vous pourriez tous les échanger et obtenir un mouton.

Votre travail consiste à déterminer si oui ou non je peux construire un règlement, compte tenu de ma main.

Ta tâche

Entrée sera une séquence des lettres B, L, O, Wet S, pris dans tout format raisonnable. Ces lettres correspondent aux cinq types de ressources indiqués ci-dessus. Vous devez indiquer si j'ai ou non les ressources nécessaires pour construire un règlement, en tenant compte de la possibilité de négocier quatre types.

C'est le code-golf , donc le code le plus court en octets gagne.

Remarques

• Vous n'avez pas à générer les transactions que je dois effectuer ou le nombre de colonies que je pourrais construire. Un simple «oui» ou «non» fera l'affaire.
• Vous ne pouvez pas supposer que l'entrée est dans un ordre spécifique. En particulier, vous ne pouvez pas supposer que les ressources du même type sont regroupées, c'est donc OBLSOune entrée valide.
• C'est un problème de décision , vous pouvez donc utiliser n'importe quelle valeur que vous voulez signifier «oui» et «non», tant que les deux valeurs choisies sont distinctes et cohérentes.
• Les seules règles qui nous intéressent ici sont celles énumérées ci-dessus. Les règles plus compliquées des colons de Catane comme le commerce avec d'autres joueurs ou dans les ports ne sont pas pertinentes ici.
• Les caractères d'entrée ( B, L, O, W, S) peuvent être substitués par d' autres valeurs s'il est plus facile pour votre langue particulière de choix, tant il y a cinq entrées distinctes. Si vous utilisez d'autres valeurs d'entrée, veuillez les spécifier dans votre réponse.

Exemples

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 octets

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

Essayez-le en ligne!

Pour chacune de nos ressources, nous comptons le nombre de «libertés» accordées en ayant n de cette ressource. Une liberté représente une opportunité de remplir l'un des créneaux de brique-bûche-blé-mouton que nous devons remplir pour nous installer, ce qui explique le fait que nous pouvons convertir nos ressources.

Pour l'ensemble de BLSW, avoir l' une des ressources nous donne une telle liberté, et chaque excès supplémentaire de 4 nous en donne une autre. La règle de comptage des libertés est la suivante:

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

Donc n briques / billes / blé / mouton donnent ⌊ (n + 3) / 4⌋ libertés.

Pour les minerais, seuls les quatuors en excès comptent. La règle de comptage des libertés est la suivante:

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

Alors n minerais donnent ⌊n / 4⌋ libertés.

Théorème: nous pouvons régler si et seulement si nous avons ≥ 4 de ces "libertés".

Nous comptons donc nos libertés et vérifions s'il y en a ≥ 4. Pour gérer le comptage des minerais comme ⌊n / 4⌋ mais pour les autres ressources ⌊ (n + 3) / 4⌋, nous gonflons artificiellement les comptes des autres ressources par 3, puis comptons ⌊n / 4⌋ pour chacun d'eux. Nous faisons cela en mappant (s+"BLSW"*3).countau lieu de s.count.

Preuve :

• Supposons que nous puissions nous installer. Ensuite, pour chacun de [B, L, S, W], nous avons (a) utilisé 1 de cette ressource que nous avions déjà, ou (b) sacrifié 4 d'une autre ressource (y compris des minerais) pour la créer. Dans les deux cas, nous comptons au moins 1 liberté selon les règles ci-dessus. Nous avons donc ≥ 4 libertés.

• Supposons que nous ayons 4 libertés, dont k sont dues à des «excès» (toute liberté vis-à-vis des minerais est un excès, et toute liberté par rapport aux autres ressources après la première l'est également) et dont 4-k témoignent de la possession d'au moins une brique / bûche / blé / mouton (celui qui a donné la «première liberté»). Ensuite, nous remplissons 4 k emplacements avec la brique / bûche / blé / mouton qui nous a donné notre première liberté, et remplissons les k emplacements restants en convertissant nos excès. Les 4 emplacements sont occupés et nous pouvons nous installer. Nous pouvons évidemment continuer à le faire si nous avons plus de 4 libertés.

Cette preuve est nul, mais j'ai sommeil. Je suis sûr qu'il y a une meilleure explication.

Python 2 ,  52  51 octets

-1 octet grâce à Luke (remplacer >=0par <0, inverser les False/ Truerésultats)

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

Une fonction sans nom prenant une chaîne de caractères B , O , W , L et S (comme dans l'OP) et retournant Falsesi vous pouvez régler ou Truesinon.

Essayez-le en ligne! (contraint la sortie versyes/nol'OP).

Comment?

Ceci est un port de ma réponse Jelly. Nous devons compenser tout B , W , L ou S manquant du reste après avoir utilisé l'un d'eux. En tant que tel, nous pouvons ajouter un O supplémentaire à notre main, puis réduire tous les décomptes d'un, puis l'entier diviser tous les décomptes par quatre, puis additionner - si le résultat est zéro ou plus, nous pouvons régler (soit parce qu'il n'y avait pas de ressources requises manquantes ou parce que nous pouvons échanger pour acquérir le ou les manquants).

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 octets

gsm/t/+Q4d4U5Z

Essayez-le ici! ou Vérifiez tous les cas de test.

Pyth ,  31 27 17  16 octets

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

Vérifiez les cas de test.

Comment ça marche?

Explication # 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.

Explication # 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.

Ce sont les codes utilisés par mon programme:

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

Gelée ,  13  12 octets

;5ċЀ5’:4S>-

Un lien monadique acceptant une liste de numéros représentant les ressources que vous possédez et vous renvoyant 1si vous pouvez vous installer ou 0non.

Les ressources sont 1, 2, 3, 4, 5où 5représente le minerai .

Essayez-le en ligne! ou voir la suite de tests (en utilisant l'OP IO).

Comment?

L'idée est de compter d'abord les ressources par type, puis de réduire tous les comptes de B , L , W et S de un - si nous n'en comptons aucun pour l'un de ces quatre, ils auront maintenant des entrées de -1 - nous devons acquérir les à partir de nos ressources restantes (Ceci est en fait réalisé en ajoutant un O supplémentaire ( 5) et en réduisant les cinq comptes de 1 ). Ensuite, nous divisons toutes ces valeurs par quatre pour voir combien d'unités nous pouvons échanger avec chacun de nos décomptes restants par type de ressource sans affecter les décomptes -1 et 0 (notez que -1 entier divisé par quatre est-1 , pas 0 ). Enfin, nous additionnons les valeurs et vérifions si le résultat est supérieur ou égal à zéro (ici supérieur à -1 peut être utilisé car nous avons toujours des entiers).

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

Lambda de int[]à boolean. Attribuer à 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;}

Essayez-le en ligne

Entrée et sortie

L'entrée est un tableau d'entiers de 0 à 4 inclus. 4 représente Ore, et les autres mappings sont sans importance. Mes cas de test sont des traductions directes de ceux de la question, avec 0 comme brique, 1 comme bûche, 2 comme blé et 3 comme mouton.

La sortie est de savoir si un règlement peut être construit.

Non golfé

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

Explication

hest le nombre de quadruples de ressources disponibles pour le commerce. Nous itérons sur chaque type de ressource (sauf Ore), en incrémentant hpour chaque quadruple de ressources supplémentaires que nous avons et en décrémentant là où aucune ressource n'est présente. Ensuite, notre résultat est de savoir si hest non négatif.

La ligne

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

s'ajuste de hmanière appropriée, qu'il n'y ait pas de ressources (pénurie) ou qu'il y ait au moins une ressource (excédent). f[i]est décrémenté pour tenir compte de la ressource requise dans le cas d'excédent, produisant -1 dans le cas de pénurie. Le décalage vers la droite signé réduit l'expression à 0 (cas d'excédent) ou -1 (cas de pénurie), de sorte qu'un OU au niveau du bit avec le nombre f[i++] / 4de quadruples excédentaires (dans le cas d'excédent) n'a aucun effet dans le cas de pénurie mais se traduit par le nombre lui-même dans le cas excédentaire.

Remerciements

• -9 octets grâce à Nevay, maître des bits

Rétine , 34 octets

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

Essayez-le en ligne! Explication: La construction d'une colonie nécessite 4 ressources qui sont soit vos premières B, L, W ou S, soit 4 autres ressources du même type. Cela équivaut à ajouter trois de chacun de ces quatre types de ressources, puis à compter pour voir si vous disposez de quatre ensembles de quatre.

Gelée , 23 octets

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

Essayez-le en ligne!

Reportez-vous au tableau suivant pour les valeurs:

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

Rétine , 43 octets

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

D`[^a]
.{4}

Essayez-le en ligne!

Python 3 , 79 78 octets

Edit: -1 octet grâce à @ Mr.Xcoder

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

Essayez-le en ligne!

MATL , 19 octets

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

L'entrée est un vecteur de ligne numérique où les lettres sont représentées comme des nombres comme suit:

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

La sortie est 1pour la vérité, 0pour la fausse.

Essayez-le en ligne!: Vérifiez tous les cas de test .

Comment ça marche

1. Comptez les occurrences de chaque ressource.
2. Divisez-les par 4.
3. Comptez combien de restes pour les quatre premières ressources (lettres BLWS) sont différents de zéro. Cela donne un nombre c .
4. Additionnez les quotients. Cela donne un nombre s .
5. Sortie si c + s ≥ 4.

Code commenté

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 octets

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

Essayez-le en ligne!

Utilise le mappage de ressources suivant:

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

Peu importe le mappage utilisé, tant qu'ils sont dans la plage 0-4, et 0est utilisé pour O. Utilise le fait que la recherche de la combinaison BLWSest la même que la recherche de la combinaison OBLWStout en ayant déjà un Oin main.

05AB1E , 19 octets

0 -> Minerai
1 -> Brique
2 -> Bûche
3 -> Blé
4 -> Mouton

Renvoie 0 lorsqu'elle est fausse et 1 sinon.

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

Essayez-le en ligne!

Explication:

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

Solution non compétitive: 17 octets

Il y avait un bogue dans 05AB1E lorsque j'ai soumis cette solution pour la première fois, où certains opérateurs ont mal géré les entrées vides. Cela a conduit cette solution à répondre 1sur une entrée vide. Cela a maintenant été corrigé, donc cette solution fonctionne très bien.

La différence ici est que nous ajoutons un minerai avant de retirer une de chaque ressource, sans distinction, en comptant le nombre de ressources supprimées de cette façon. Nous décrémentons ensuite le compteur de 1 pour obtenir le nombre correct de B, L, W et S.

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

Essayez-le en ligne!

JavaScript (SpiderMonkey) , 116 octets

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

Essayez-le en ligne!

Super mauvaise réponse. Je suis sûr qu'il pourrait être nettoyé davantage. Méthode inspirée de la réponse de Lynn dans ce fil.

Kotlin , 131 129 octets

Soumission

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

Tester

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

Ne peut pas fonctionner sur TryItOnline, mais fonctionne sur try.kotlinlang.org