21
\$\begingroup\$

I like to play (The Settlers of) Catan on Board Game Arena with totally random number tokens. These tokens determine the production rate of the terrain tiles beneath:

There are 18 number tokens, two each of 3, 4, 5, 6, 8, 9, 10, 11 and one each of 2 and 12. A valid arrangement of these tokens on the board (19 hexes in a side-3 hexagon) has each token placed in exactly one hex, leaving one empty hex (the desert), and none of the 6 and 8 tokens adjacent. So a 6 cannot be adjacent to the other 6, an 8 cannot be adjacent to the other 8 and a 6 cannot be adjacent to an 8.

Task

Output a valid random arrangement of the number tokens. Each possible arrangement only needs a nonzero probability of being output.

You may output in any reasonable format, which may be 2D (like the valid and invalid outputs below) or 1D (e.g. mapping the hexes to a 19-character string in a fixed and consistent order). In either case it must be specified how the different positions in the output map to the hexagon. You may use any set of 11 different symbols to denote the number tokens or lack thereof.

This is ; fewest bytes wins.

Valid outputs

These use A B C for 10 11 12 respectively and . for the empty desert hex.

  6 3 8
 2 4 5 A
5 9 . 6 9
 A B 3 C
  8 4 B
  B 9 A
 5 6 C 8
6 4 B 5 3
 2 8 9 3
  A . 4
  B B C
 3 3 A A
2 4 6 . 6
 4 5 9 9
  8 5 8

Invalid outputs

This one has three 5s and only one 4:

  6 A 2
 C 5 9 3
8 B 3 6 A
 . 9 4 5
  5 B 8

The two 6s are adjacent here:

  5 2 4
 3 8 B 4
9 B 3 5 8
 A 6 9 C
  . 6 A

A 6 and an 8 are adjacent here:

  4 3 A
 . 8 2 5
4 6 A 8 B
 5 C 3 9
  B 6 9
\$\endgroup\$
2
  • 16
    \$\begingroup\$ I wanna see a Hexagony answer... \$\endgroup\$
    – hakr14
    Nov 29, 2022 at 20:51
  • 6
    \$\begingroup\$ Not to be confused with Catalan numbers :) \$\endgroup\$
    – Arnauld
    Nov 30, 2022 at 8:36

10 Answers 10

12
\$\begingroup\$

JavaScript (ES6), 162 bytes

f=(s=`  . 2 3  
 3 4 4 5 
5 6 6 8 8
 9 9 A A 
  B B C`,a=s.match(e=/\S/g).sort(_=>Math.random()-.5))=>/[68](.|[^]{8,10})[68]/.exec(s)?f(s.replace(e,_=>a.pop())):s

Try it online!

Uniform distribution, 163 bytes

The ways the grid is shuffled in the above version, some patterns have a higher probability than others -- which is fine as per the challenge rules. But getting a uniform distribution just costs one extra byte.

f=(s=`  . 2 3  
 3 4 4 5 
5 6 6 8 8
 9 9 A A 
  B B C`,a=s.match(e=/\S/g))=>/[68](.|[^]{8,10})[68]/.exec(s)?f(s.replace(e,_=>a.splice(Math.random()*n--,1),n=19)):s

Try it online!

Commented

f = (                    // f is a recursive function taking:
  s = `...`,             //   s = initial 2D grid, with an invalid pattern
  a =                    //   a[] = array of
    s.match(e = /\S/g)   //         non-space characters
    .sort(_ =>           //         shuffled
      Math.random() - .5 //         using a random sort() callback
    )                    //
) =>                     //
/[68](.|[^]{8,10})[68]/  // test the validity of the grid by detecting
.exec(s)                 // 6's or 8's separated by 1, 8 or 10 characters
                         // (line-break included)
?                        // if it's not valid:
  f(                     //   try again with another grid:
    s.replace(           //     replace in s:
      e,                 //       each non-space character with
      _ => a.pop()       //       the next character taken from a[]
    )                    //     end of replace()
  )                      //   end of recursive call
:                        // else:
  s                      //   success: return s
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I really like this solution. \$\endgroup\$
    – Jonah
    Nov 29, 2022 at 23:36
5
\$\begingroup\$

Retina, 79 bytes


  . 2 3  ¶ 3 4 4 5 ¶5 6 6 8 8¶ 9 9 A A ¶  B B C
/[68](?s:.|.{8,10})[68]/+O?`\S

Try it online! Explanation: Based on @Arnauld's JavaScript answer.


  . 2 3  ¶ 3 4 4 5 ¶5 6 6 8 8¶ 9 9 A A ¶  B B C

Insert the tokens in an invalid layout.

/[68](?s:.|.{8,10})[68]/+`

Repeat while the layout is invalid...

O?`\S

... shuffle the tokens.

\$\endgroup\$
5
\$\begingroup\$

Jelly, 39 bytes

ỊTḤ>þ“©©©Çð   ‘S+Ɗạþ`Ff“£µ¿‘
17Ż%⁵⁵;ẊÇ¿

A niladic Link that yields a flat list of the tokens to be placed in row-major order.

The mapping from question values to the outputted tokens is:

Catan (Question):  2   3   4   5   6   8   9  10  11  12   .
    Token (code):  9   3   4   5   0   1   2   6   7   8  10

Try it online! Or see a formatted version (translates tokens to Catan values and pretty-prints as a hexagon).

(Also here is version that only prints the sixes and eights.)

How?

ỊTḤ>þ“©©©Çð   ‘S+Ɗạþ`Ff“£µ¿‘ - Helper Link, is invalid?: list of tokens
Ị                            - insignificant? (abs(x)<=1 - i.e. is Catan 6 or 8?) (vectorises)
 T                           - truthy, 1-indexed indices
  Ḥ                          - double (vectorises)
                 Ɗ           - last three links as a monad f(X=that):
     “©©©Çð   ‘              -   code-page indices = [6,6,6,14,24,32,32,32]
    þ                        -   (X) table with (that) using:
   >                         -     greater than?
               S             -   (column-wise) sum
                +            -   add (X) (vectorises)
                    `        - use (that) as both arguments of:
                   þ         -   table using:
                  ạ          -     absolute difference
                     F       - flatten
                       “£µ¿‘ - code-page indices = [2,9,11]
                      f      - filter keep
                               -> nonempty list (truthy) if invalid
                                  empty list (falsey) if valid

17Ż%⁵⁵;ẊÇ¿ - Link, get random Catan Distribution: no arguments
17         - seventeen
  Ż        - zero range -> [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]
    ⁵      - ten
   %       - modulo -> [0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7]
     ⁵     - ten
      ;    - concatenate ->  [10,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7]
         ¿ - while...
        Ç  - ...condition: call the Helper Link (above)
       Ẋ   - ...action: shuffle
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Couldn't you remove the spaces? \$\endgroup\$ Nov 30, 2022 at 3:18
  • 1
    \$\begingroup\$ @ParclyTaxel The three spaces are encoding the three \$32\$s. \$\endgroup\$ Nov 30, 2022 at 9:37
  • 1
    \$\begingroup\$ (...without them, the adjacency check for elements in row four and row five will be incorrect.) \$\endgroup\$ Nov 30, 2022 at 11:28
5
\$\begingroup\$

Excel VBA, 408 361 352 bytes

Saved 9 bytes thanks to Taylor Raine

Golfed code: (Note: VBA will autoformat this code by adding spaces in many places and a few other niceties.)

Sub z
Set g=[C4:E6,F2:G4,D3:E3,E2,F5]
x:
Set c=New Collection
c.Add 2
c.Add 12
For i=1To 2
For j=3To 11
c.Add j
Next j,i
c.Remove 7
For Each s In g
k=CInt(1+Int(Rnd*c.Count))
s.Value=c(k)
c.Remove k
Next
For Each s In g
u=0
For Each t In Union(s.Offset(-1,0).Resize(2,2),s.Offset(0,-1).Resize(2,2))
If t=6Or t=8Then u=u+1
Next
If u>2GoTo x
Next
End Sub

Formatted and commented code:

Sub z()
    ' Define our game board
    Set g = [C4:E6,F2:G4,D3:E3,E2,F5]
    
    ' Setup a label so we can loop back here and start over as needed
    ' I know this uses GoTo which is [bad] but it's the shortest way to loop
x:
    
    ' Create a list of all the numbers we want to populate into the grid
    ' We need to recreate this on each loop because it'll be emptied later in this process
    Set c = New Collection
    c.Add 2
    c.Add 12
    For i = 1 To 2  'Add all the numbers 3-11 twice
        For j = 3 To 11
            c.Add j
        Next
    Next
    c.Remove 7  ' As it happens, the 7th term will be one of the "7" values and we only need one of those.
    
    ' Populate the grid with a random entry from that list and then remove it from the list.
    For Each s In g
        k = CInt(1 + Int(Rnd * c.Count))
        s.Value = c(k)
        c.Remove k
    Next
    
    ' Look for more than one instance of 6 or 8 in each set of adjacent hexes
    For Each s In g
        u = 0
        ' Check a rotated hexagonal-ish shape centered on the current cell
        For Each t In Union(s.Offset(-1, 0).Resize(2, 2), s.Offset(0, -1).Resize(2, 2))
            ' This is less bytes than something like "If Abs(s-7)=1Then" because this has more spaces than can be removed
            If t = 6 Or t = 8 Then u = u + 1
        Next
        If u > 2 Then GoTo x     ' Loop if you found more than two (since we check the center cell twice)
    Next
End Sub

Output format:

Output is in a spaced out grid spanning the range C2:G6 in the active sheet. The values are 2-12 with 7 being the desert. It is a rotated and compressed version of the hexagonal grid. If you translated the first example in the question into Excel, you may want it to look like image below. I've added colors for clarity later and outlined all the cells that would be considered adjacent to the desert in the middle of the board.

Spaced Out Grid

However, that spaced out thing is not very byte-friendly. We're going to rotate it 45° and compress it. Here's the same board with the same colors and the same cells outlined in a border showing they're adjacent to the desert:

Rotated and Compressed Grid

To better show how this looks like the original board, I'm going to rotate the text 45°. Tilt your head to the left and you should see a perfectly normal Catan board.

Rotated Text

Example board generation:

With the colors and borders back in place, here's a video showing the generation of some random boards. The top left board is where the code is outputting data. The bottom left board is full of formulas show it shows the same data as the top left but in the more expanded layout. The diamond shape to the right is a snapshot of the same results (again linked by formulas) but with the text rotated 45° CCW and then the whole snapshot rotated 45° CW so it looks like a normal board. The places where it pauses is where a good board was found, I waited, then ran the script again.

Board Generation GIF

\$\endgroup\$
3
  • 1
    \$\begingroup\$ This is a wonderful solution! And don't worry about using GoTo in golfing - sometimes its just the best way to golf VBA. You can drop a couple of bytes by dropping the () after the sub definition, condensing the nexts into next j,i and then dropping the then before GoTo \$\endgroup\$ Apr 12, 2023 at 1:19
  • \$\begingroup\$ Since you are marching across all of the cells, you don't need to check both directions - you only need to check if a given cell is 6 or 8 and if it has a neighboring 6 or 8 to its top right with something like For Each t In s.Offset(-1).Range("A1,B1:B2"):If(s=6Or s=8)And(t=6Or t=8)GoTo x:Next \$\endgroup\$ Dec 12, 2023 at 20:31
  • \$\begingroup\$ If you rotate to the 45° CW instead of CCW, and use [SEQUENCE(10)+{1,2}] to help build your collection, you can get this golfed down a good bit - snippet on TIO \$\endgroup\$ Dec 12, 2023 at 20:49
4
\$\begingroup\$

Charcoal, 73 bytes

W¬KA«⎚P→↙×ψ³‖C‖O↓≔⟦⟧υW⁻…³¦²²υ⊞υ‽κ¤⭆υ⁺§…α¹¹κ F⁵F⁹«J⁻λ²κ¿‹IKK¿‹I⌈⊞OKM⊟KD³→⎚

Try it online! Link is to verbose version of code. Uses A, B and C to represent 2, 12 and the desert, J and K to represent 6 and 8 and intervening letters for the remaining tokens. Explanation:

W¬KA«

Repeat while the canvas is empty.

⎚P→↙×ψ³‖C‖O↓

Outline a hexagon. (The extra Clear(); at the beginning ensures that the cursor is at the origin, as it is not there at the end of the loop.)

≔⟦⟧υW⁻…³¦²²υ⊞υ‽κ¤⭆υ⁺§…α¹¹κ 

Shuffle the tokens and fill in the hexagon.

F⁵F⁹«J⁻λ²κ

Loop over the canvas.

¿‹IKK¿‹I⌈⊞OKM⊟KD³→⎚

If an adjacent pair of J and/or K are found then clear the canvas.

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

Python, 184 bytes

from random import*
f=lambda s=".2C"+2*"345#%9AB":any((x:=(*s[:3],"_",*s[3:-3],"_",*s[-3:],*"___"))[i]<'.'>min(x[i+4:i+6]+~-~-i%5*(x[i+1],))for i in range(20))and f(sample(s,k=19))or s

Attempt This Online!

# and $ represent tiles 6 and 8 respectively; the rest of the encoding are the same as in the example.

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

05AB1E, 56 54 bytes

12L7Kû¨¨[.rD18Ýü2ZÝ3LÌû£ü2εé`δ‚εND>‚è}}˜2ô«èJ€ê68æδÊß#

Uses 1 for the empty desert hex. The other numbers are the same.
Outputs as a flat list.

Try it online or try it with pretty-print.

Explanation:

12L7Kû¨¨  # Get a list of the numbers:
12L       #  Push a list in the range [1,12]
   7K     #  Remove the 7
     û    #  Palindromize it
      ¨¨  #  Remove the trailing [2,1]
[         # Start an infinite loop:
 .r       #  Randomly shuffle the list
   D      #  Duplicate this list
 18Ýü2ZÝ3LÌû£ü2εé`δ‚εND>‚è}}˜2ô«èJ€ê68æδÊß#
          #  Pop the copy, and check whether it's valid (see below)
  #       #  If it is valid: stop the infinite loop
          #  (after which the valid shuffled list is output implicitly as result)
18Ý       # Push a list in the range [0,18]
   ü2     # Get its overlapping pairs: [[0,1],[1,2],...,[16,17],[17,18]]
Z         # Push its flattened maximum (18), without popping the list
 Ý        # Push a list in the range [0,18] again
  3L      # Push list [1,2,3]
    Ì     # Increase each by 2 to [3,4,5]
     û    # Palindromize it to [3,4,5,4,3]
      £   # Split the [0,18] list into parts of those sizes
ü2        # Get overlapping pairs of these lists
  ε       # Map over each pair of lists:
   é      #  Sort the lists by length
    `     #  Pop and push both lists separated to the stack
     δ    #  Apply double-vectorized:
      ‚   #   Pair values together
   ε      #  Inner map over these lists of pairs:
    N  ‚  #   Pair the current index
     D>   #   With the index+1
        è #   Use this [index,index+1] to get the pairs at those indices
  }}      # Close the nested maps
    ˜2ô   # Flatten it two levels down to a single list of pairs:
    ˜     #  Flatten the list of lists of pairs
     2ô   #  Split the flattened list back into parts of size 2
«         # Merge it to the list of overlapping pairs of [0,18]
 è        # Get the values at those indices from the shuffled list
  J       # Join each inner pair together to a string
   ې     # Sorted-uniquify the digits of each inner string
68        # Push 68
  æ       # Pop and push its powerset: ["",6,8,68]
   δ      # Apply double-vectorized:
    Ê     #  Not equals check
     ß    # Get the flattened minimum to verify none are falsey

The index-pairs to check each adjacent hex, generated by 18Ýü2ZÝ3LÌû£ü2εé`δ‚εND>‚è}}˜2ô«, are:

[[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10],[10,11],[11,12],[12,13],[13,14],[14,15],[15,16],[16,17],[17,18],[0,3],[0,4],[1,4],[1,5],[2,5],[2,6],[3,7],[3,8],[4,8],[4,9],[5,9],[5,10],[6,10],[6,11],[7,12],[8,12],[8,13],[9,13],[9,14],[10,14],[10,15],[11,15],[12,16],[13,16],[13,17],[14,17],[14,18],[15,18]]

     0   1   2
   3   4   5   6
 7   8   9  10  11
  12  13  14  15
    16  17  18

Try it online.

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

Python 3, 391 bytes:

from random import*
R=range
P=lambda i:' '*int((9-(i*2-1))/2)
def b():
 while 1:
  t=[*'2C.'+'345689AB'*2];shuffle(t)
  B,f=[P(i)+' '.join(t.pop(0)for _ in R(i))+P(i)for i in[3,4,5,4,3]],1
  for x in R(5):
   for y in R(9):
    for X,Y in[(1,1),(-1,1),(1,-1),(-1,-1),(0,2),(-2,0)]:
     if 0<=(j:=x+X)<5 and 0<=(k:=y+Y)<9 and {'6','8'}&{B[x][y],B[j][k]}=={B[x][y],B[j][k]}:f=0
  if f:yield B

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ (1) There's an extra 7 in your code. (2) 1D formatting is acceptable as per the rules. \$\endgroup\$ Nov 29, 2022 at 20:17
1
\$\begingroup\$

JavaScript (ES6), 157 bytes

The output format for this version was inspired by Jonathan Allan's answer.

Returns a flat array with the following mapping:

-1 0 1 2 3 4 5 6 7 8 9
 . 6 8 9 3 4 5 A B C 2
f=_=>(a=[...s="8889999_____0000111"].map((_,i)=>~-i%10).sort(_=>Math.random()-.5)).some((v,i)=>227259>>i&(g=k=>3>>a[i+k]&3>>v&1)(1)|g(q=s[i]-5)|g(q+1))?f():a

Try it online!

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

Ruby, 132 bytes

f=->{a=([*0..10]*2)[i=0,q=19].shuffle
"&&X,,,^1,,,]+&&WKK".bytes{|b|q&&=a[i]/2+[a[i+=1]|b&64,a[b/5%5+i],a[b%5+i]].min/2>0}
q ?a:f[]}

Try it online!

Outputs a flat array. Uses the same tokenization as Jonathan Allen. (the footer of the TIO link converts 10 to hexadecimal A for better presentation.)

Catan (Question):  2   3   4   5   6   8   9  10  11  12   .
    Token (code):  9   3   4   5   0   1   2   6   7   8  10

Explanation

We generate a flat array of all 11 tokens, duplicate it to 22 elements, truncate to 19 elements to discard the extra 8 9 10, then shuffle. We check if the arrangement is valid, and if so, return it. Otherwise we call recursively to try again.

For each element (except the last one) we check if any of the (up to 3) adjacent elements following it are incompatible. The elements to be checked (to the right, below, and diagonally) are shown as an offset in the table below.

134 134 .34
145 145 145 .45
1.5 145 145 145 .4.
    1.4 134 134 .3.
        1.. 1.. ...

This was encoded in a magic string as follows. For the below and diagonal offsets, we subtract 1 from each and encode as a two-digit base 5 number. Thus .45 becomes 34 becomes 3x5 + 4 = decimal 19. If a below or diagonal check is NOT required, we pick a number that gives a duplicate check in one of the other directions.

We then add a multiple of 25 to it to bring it into the printable ASCII range. If checking of an element to the right is NOT required, we add a further multiple of 25 to increase the value above 64.

Decoding should be apparent from the code, but I will add commented code later when I have time.

\$\endgroup\$

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.