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 , so shortest code in bytes wins.


  • 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 , 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.


BLWS -> Yes
OOOOWLB -> Yes (trade four O for a S)
OOW -> No
BBBO -> No
(empty input) -> 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)
  • 13
    \$\begingroup\$ "Building a settlement costs a Brick, a Log, a Wheat, and a Sheep". Yes, to perform the ritual of building a settlement, you need one sheep. Wonder why there aren't any vegetarians? \$\endgroup\$
    – Okx
    Sep 4, 2017 at 16:33
  • 5
    \$\begingroup\$ @Okx , the sheep gives the milk that goes with the bread from the wheat to feed the builders while they build (they take the sheep with them at the end as payment). No animals were hurt in the building of the settlement \$\endgroup\$
    – Aganju
    Sep 4, 2017 at 21:33
  • \$\begingroup\$ Is it OK for the program to require the input to be sorted? \$\endgroup\$
    – Maya
    Sep 5, 2017 at 14:58
  • \$\begingroup\$ @NieDzejkob No, requiring an ordering is specifically disallowed. Your program must be prepared to handle any sequence of the five resources. \$\endgroup\$ Sep 5, 2017 at 16:39
  • \$\begingroup\$ @SilvioMayolo sorry, I don't know how I missed that \$\endgroup\$
    – Maya
    Sep 5, 2017 at 16:43

14 Answers 14


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.


  • 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.

  • 2
    \$\begingroup\$ So say s is OOOOBLW, you end up getting sum(n/4for n in map(("OOOOBLWBBBLLLSSSWWW").count,"BLSWO"))>3...so for each of BLOWS you count how many times it appears in that starter string of "BLWS"*3, then sum it up. \$\endgroup\$ Sep 5, 2017 at 9:51
  • 2
    \$\begingroup\$ Precisely! (The string is "OOOOBLWBLSWBLSWBLSW", actually, but the counts are the same, of course.) \$\endgroup\$
    – lynn
    Sep 5, 2017 at 10:34
  • \$\begingroup\$ Python map being 'backwards' always confuses me! \$\endgroup\$ Sep 5, 2017 at 10:35
  • \$\begingroup\$ The space between in"BLSWO" is unnecessary in Python, isn't it? Seems to work in TIO at least.. \$\endgroup\$ Sep 5, 2017 at 13:16

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).


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)
  • \$\begingroup\$ How about using False for 'yes' and True for 'no'? Then you could change >= to <, saving 1 byte. \$\endgroup\$
    – Luke
    Sep 4, 2017 at 21:58
  • \$\begingroup\$ I prefer your choice of resource ordering to that of the question! \$\endgroup\$
    – Neil
    Sep 5, 2017 at 9:26

Jelly,  13  12 bytes


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).


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

Pyth, 14 bytes


Try it here! or Verify all the test cases.

Pyth,  31 27 17  16 bytes


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
  • \$\begingroup\$ +%ld4/ld4 -> s.Dld4 \$\endgroup\$ Sep 4, 2017 at 17:54
  • \$\begingroup\$ Oh, alright then. \$\endgroup\$ Sep 4, 2017 at 17:55
  • \$\begingroup\$ I believe //Q4 4 can be /Q16 but I'm not really sure... \$\endgroup\$ Sep 4, 2017 at 18:09
  • \$\begingroup\$ @EriktheOutgolfer It was invalid... Fails for BBBO, for example \$\endgroup\$
    – Mr. Xcoder
    Sep 4, 2017 at 18:09
  • \$\begingroup\$ @EriktheOutgolfer No, it's count the occurences of 4 and divide by 4. \$\endgroup\$
    – Mr. Xcoder
    Sep 4, 2017 at 18:10

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.


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


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.


  • -9 bytes thanks to Nevay, master of bits
  • \$\begingroup\$ -3 bytes: ...for(h=f[4]/4;i<4;h+=f[i++]/4)n+=--f[i]>>-1;return~h<n;. \$\endgroup\$
    – Nevay
    Sep 4, 2017 at 20:16
  • \$\begingroup\$ 103 bytes: 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++]/4)h+=--f[i]>>-1;return~h<0;} \$\endgroup\$
    – Nevay
    Sep 4, 2017 at 20:27
  • 2
    \$\begingroup\$ 101 bytes: 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;} \$\endgroup\$
    – Nevay
    Sep 4, 2017 at 20:34
  • \$\begingroup\$ Now that's some juicy bit hacking! \$\endgroup\$
    – Jakob
    Sep 4, 2017 at 21:24

Retina, 34 bytes


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.


Jelly, 23 bytes


Try it online!

Refer to the following table for the values:

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

Retina, 43 bytes



Try it online!


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!

  • \$\begingroup\$ If you are willing to switch to Python 2, you can do it in 77 bytes \$\endgroup\$
    – Mr. Xcoder
    Sep 4, 2017 at 17:12
  • \$\begingroup\$ 78 in Py 3, or 76 in Py 2 \$\endgroup\$
    – Mr. Xcoder
    Sep 4, 2017 at 17:16
  • \$\begingroup\$ @Mr. Xcoder Why don't you make a Python 2 solution? \$\endgroup\$
    – Jakob
    Sep 4, 2017 at 17:22
  • \$\begingroup\$ @Jakob Because it is way too similar to Halvard's. \$\endgroup\$
    – Mr. Xcoder
    Sep 4, 2017 at 17:23
  • \$\begingroup\$ @Mr.Xcoder will keep it Python 3 \$\endgroup\$ Sep 4, 2017 at 17:36

MATL, 19 bytes


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

><>, 61 bytes

1+$ap> i:0(?v8%:ag

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.


05AB1E, 19 bytes

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

Returns 0 when false, and 1 otherwise.


Try it online!


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


Try it online!


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.


Kotlin, 131 129 bytes


fun r(i:String):Any=i.split("").groupingBy{it}.eachCount().map{when(it.key){


fun r(i:String):Any=i.split("").groupingBy{it}.eachCount().map{when(it.key){

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

            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)
    println("Test passed")

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.