23
\$\begingroup\$

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.

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 , 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)
\$\endgroup\$
  • 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 '17 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 '17 at 21:33
  • \$\begingroup\$ Is it OK for the program to require the input to be sorted? \$\endgroup\$ – NieDzejkob Sep 5 '17 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\$ – Silvio Mayolo Sep 5 '17 at 16:39
  • \$\begingroup\$ @SilvioMayolo sorry, I don't know how I missed that \$\endgroup\$ – NieDzejkob Sep 5 '17 at 16:43

14 Answers 14

16
\$\begingroup\$

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.

\$\endgroup\$
  • 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\$ – Pureferret Sep 5 '17 at 9:51
  • 2
    \$\begingroup\$ Precisely! (The string is "OOOOBLWBLSWBLSWBLSW", actually, but the counts are the same, of course.) \$\endgroup\$ – Lynn Sep 5 '17 at 10:34
  • \$\begingroup\$ Python map being 'backwards' always confuses me! \$\endgroup\$ – Pureferret Sep 5 '17 at 10:35
  • \$\begingroup\$ The space between in"BLSWO" is unnecessary in Python, isn't it? Seems to work in TIO at least.. \$\endgroup\$ – Kevin Cruijssen Sep 5 '17 at 13:16
8
\$\begingroup\$

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

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
\$\endgroup\$
6
\$\begingroup\$

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

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
\$\endgroup\$
  • \$\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 '17 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 '17 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 '17 at 20:34
  • \$\begingroup\$ Now that's some juicy bit hacking! \$\endgroup\$ – Jakob Sep 4 '17 at 21:24
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Retina, 43 bytes

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

D`[^a]
.{4}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

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

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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