Can I Settle Down?

Question

In The Settlers of Catan board game, there are five resource types: Brick, Log, Ore, Wheat, and Sheep. Building a settlement costs a Brick, a Log, a Wheat, and a Sheep. However, you can also trade in four identical resources to get a resource of a different type. For instance, if you had four ores in your hand, you could trade all of them in and get one sheep.

Your job is to determine whether or not I can build a settlement, given my hand.

Your Task

Input will be a sequence of the letters B, L, O, W, and S, taken in any reasonable format. These letters correspond to the five resource types given above. You should output whether or not I have the resources necessary to build a settlement, taking into account the possibility of trading four of a kind.

This is code-golf, so shortest code in bytes wins.

Notes

• You do not have to output what trades I need to perform or how many settlements I could build. A simple "yes" or "no" will do.
• You may not assume that the input is in any specific order. In particular, you may not assume that resources of the same type are grouped together, so OBLSO is a valid input.
• This is decision-problem, so you may use any value you want to mean "yes" and "no", as long as the two chosen values are distinct and consistent.
• The only rules we're concerned with here are the ones listed above. More complicated Settlers of Catan rules like trading with other players or at harbours are not relevant here.
• The input characters (B, L, O, W, S) can be substituted with other values if it is easier for your particular language of choice, so long as there are five distinct inputs. If you use other input values, please specify them in your answer.

Examples

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)

Answer 1

Python 2, 54 bytes

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

Try it online!

For each of our resources, we count the number of “freedoms” given by having n of that resource. A freedom represents an opportunity to fill one of the brick-log-wheat-sheep slots we need to fill in order to settle, accounting for the fact that we can convert our resources.

For all of BLSW, having one of the resource gives us one such freedom, and every additional excess of 4 gives us another. The freedom-counting rule is like this:

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

So n bricks/logs/wheat/sheep give ⌊(n+3)/4⌋ freedoms.

For ores, only the excess foursomes count. The freedom-counting rule is like this:

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

So n ores give ⌊n/4⌋ freedoms.

Theorem: we can settle if and only if we have ≥ 4 such “freedoms”.

So we count our freedoms and check if there are ≥ 4 of them. To handle counting ores as ⌊n/4⌋ but other resources ⌊(n+3)/4⌋, we artificially inflate the counts for the other resources by 3 and then count ⌊n/4⌋ for all of them. We do this by mapping (s+"BLSW"*3).count instead of s.count.

Proof:

• Suppose we can settle. Then for each of [B, L, S, W], we either (a) used 1 of that resource that we already had, or (b) sacrificed 4 of some other resource (including ores) to create it. In either case, we count at least 1 freedom by the above rules. So we have ≥ 4 freedoms.

• Suppose we have 4 freedoms, k of which are due to “excesses” (every freedom from ores is an excess, and every freedom from other resources past the first one also is) and 4−k of which are witness of owning at least one brick/log/wheat/sheep (the one that gave the “first freedom”). Then we fill 4−k slots with the brick/log/wheat/sheep that gave us our first freedom, and fill the remaining k slots by converting our excesses. All 4 slots are filled and we can settle. We can obviously still do this if we have more than 4 freedoms.

This proof sucks, but I’m sleepy. I’m sure there’s a better explanation.

Answer 2

Python 2,  52  51 bytes

-1 byte thanks to Luke (replace >=0 with <0, inverting the False/True results)

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

An unnamed function taking a string of the characters B, O, W, L, and S (as in the OP) and returning False if you can settle or True if not.

Try it online! (coerces the output to the yes/no of the OP).

How?

This is a port of my Jelly answer. We need to make up for any missing B, W, L, or S from the remainder after using one of each of them. As such we can add an extra O to our hand, then reduce all the counts by one, then integer divide all counts by four and then sum - if the result is zero or more we can settle (either because there were no missing required resources or because we can trade to acquire the missing one(s)).

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)

Answer 3

Pyth, 14 bytes

gsm/t/+Q4d4U5Z

Try it here! or Verify all the test cases.

Pyth,  31 27 17  16 bytes

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

Verify the test cases.

How do these work?

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

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

---

These are the codes used by my program:

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

Answer 4

Jelly,  13  12 bytes

;5ċЀ5’:4S>-

A monadic link accepting a list of numbers representing the resources you own and returning 1 if you can settle down or 0 if not.

The resources are 1, 2, 3, 4, 5 where 5 represents Ore.

Try it online! or see the test-suite (using the OP IO).

How?

The idea is to first count the resources by type, then reduce all counts of B, L, W, and S by one - if we counted none for any of these four then they will now have entries of -1 - we need to acquire them from our remaining resources (This is actually achieved by adding an extra O (5) and reducing all five counts by 1). Next we integer-divide all these values by four to see how many units we may trade for with each of our remaining counts by resource type while not affecting the -1 and 0 counts (note that -1 integer-divided by four is -1, not 0). Lastly we add up the values and check if the result is greater than or equal to zero (here greater than -1 can be used since we always have integers).

;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

Answer 5

Java 8, 101 bytes

Lambda from int[] to boolean. Assign to 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;}

Try It Online

Input and output

Input is an array of integers from 0 to 4, inclusive. 4 represents Ore, and the other mappings are immaterial. My test cases are direct translations of those in the question, with 0 as Brick, 1 as Log, 2 as Wheat, and 3 as Sheep.

Output is whether a settlement can be built.

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

Explanation

h is the number of resource quadruples available to trade. We iterate over each resource type (except Ore), incrementing h for each quadruple of extra resources we have, and decrementing where no resources are present. Then our result is whether h is nonnegative.

The line

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

adjusts h appropriately regardless of whether there are no resources (shortage) or there is at least one resource (surplus). f[i] is decremented to account for the required resource in the surplus case, producing -1 in the shortage case. The signed right shift reduces the expression to 0 (surplus case) or -1 (shortage case), so that a bitwise OR with the number f[i++] / 4 of surplus quadruples (in the surplus case) has no effect in the shortage case but results in the number itself in the surplus case.

Acknowledgments

• -9 bytes thanks to Nevay, master of bits

Answer 6

Retina, 34 bytes

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

Try it online! Explanation: Building a settlement requires 4 resources which are either your first B, L, W, or S, or any other 4 resources of the same type. This is equivalent to adding three of each of those four types of resources, and then counting to see whether you have four sets of four.

Answer 7

Jelly, 23 bytes

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

Try it online!

Refer to the following table for the values:

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

Answer 8

Retina, 43 bytes

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

D`[^a]
.{4}

Try it online!

Answer 9

Python 3, 79 78 bytes

Edit: -1 byte thanks to @Mr.Xcoder

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

Try it online!

Answer 10

MATL, 19 bytes

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

Input is a numeric row vector where the letters are represented as numbers as follows:

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

Output is 1 for truthy, 0 for falsy.

Try it online!: verify all test cases.

How it works

1. Count ocurrences of each resource.
2. Div-mod them by 4.
3. Count how many of the remainders for the first four resources (letters BLWS) are nonzero. This gives a number c.
4. Sum the quotients. This gives a number s.
5. Output whether c+s ≥ 4.

Commented code

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

Answer 11

><>, 61 bytes

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

Try it online!

Uses the following resource mapping:

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

It doesn't really matter what mapping is used, as long as they're in the range 0-4, and 0 is used for O. Makes use of the fact that looking for the combination BLWS is the same as looking for the combination OBLWS while already having an O in hand.

Answer 12

05AB1E, 19 bytes

0 -> Ore
1 -> Brick
2 -> Log
3 -> Wheat
4 -> Sheep

Returns 0 when false, and 1 otherwise.

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

Try it online!

Explanation:

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

Non-competive solution: 17 bytes

There was a bug in 05AB1E when I first submitted that solution, where some operators badly handled empty inputs. This resulted in this solution answering 1 on an empty input. This has now been fixed, so this solution works just fine.

The difference here is that we add an ore prior to removing one of each resource, indiscriminately, counting the number of resources removed that way. We then decrement the counter by 1 to get the correct number of B, L, W and S.

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

Try it online!

Answer 13

Kotlin, 131 129 bytes

Submission

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

Cannot work on TryItOnline, but works on try.kotlinlang.org

Answer 14

JavaScript (SpiderMonkey), 116 bytes

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

Try it online!

Super Clunky bad answer. I'm sure it could be cleaned up more. Method inspired by Lynn's answer in this thread.