22
\$\begingroup\$

Similar in spirit to Number of distinct tilings of an n X n square with free n-polyominoes and Partition a square grid into parts of equal area, this challenge will have you count ways of partitioning a triangle in a triangular grid. The goal of this challenge is to write a program that outputs \$ a(n,m)\$, the number of ways to partition a triangle of side length \$n\$ into equal parts containing \$m\$ cells each. The parts must contiguous, where two cells are considered touching if they share a side.

Examples

Up to rotation and reflection, there are two ways to partition the size-\$4\$ triangle into equal parts of size \$8\$, so \$a(4,8) = 2\$:

First partition of the length 4 triangle into two parts of size 8 Second partition of the length 4 triangle into two parts of size 8

Up to rotation and reflection, there are three ways to partition the size-\$4\$ triangle into four parts of size \$4\$, so \$a(4,4) = 3\$:

First partition of the length 4 triangle into parts of size 4 Second partition of the length 4 triangle into parts of size 4 Third partition of the length 4 triangle into parts of size 4

Table

 n |  m | a(n,m)
---+----+-------
 1 |  1 | 1
 2 |  1 | 1
 2 |  2 | 0
 2 |  4 | 1
 3 |  1 | 1
 3 |  2 | 0
 3 |  3 | 1
 3 |  9 | 1
 4 |  1 | 1
 4 |  2 | 0
 4 |  3 | 0
 4 |  4 | 3
 4 |  8 | 2
 4 | 16 | 1

(I've made this table by hand, so comment if you spot any mistakes.)

Challenge

Write a program that takes an input \$n\$, which is the size of a triangle, and a parameter \$m\$, which is the size of each region, and return the number of ways to partition the size \$n\$ triangle into \$n^2/m\$ parts of size \$m\$ up to the rotations and reflections of the triangle. Your code should be able to handle the inputs in the table on TIO, and it should be able to handle larger inputs in principle.

This is a challenge, so the shortest code wins.

\$\endgroup\$
13
  • 2
    \$\begingroup\$ Why doesn't a(4,8) count the case where the bottom row and center triangle are red? \$\endgroup\$
    – att
    Aug 25 '20 at 6:08
  • 2
    \$\begingroup\$ It's implied from the examples, so I assume that the 'equal parts' must be contiguous and that touching-corners don't count as contiguity, but it's probably worth including this in the specification (unless I missed it). \$\endgroup\$ Aug 25 '20 at 7:30
  • 2
    \$\begingroup\$ @pxeger, it means exactly that. We're counting "essentially different" partitions, so if two layouts are the same after flipping or rotating by 120°, then we count them as one. \$\endgroup\$ Aug 25 '20 at 16:50
  • 1
    \$\begingroup\$ A simple "code golf" search in OEIS reveals many entries that were submitted after asking questions here. In these cases I believe that you should also edit the stack exchange questions providing the new OEIS link and letting people know that their effort lead to a new entry. Here is just an example oeis.org/A334398 \$\endgroup\$
    – ZaMoC
    Aug 28 '20 at 6:41
  • 2
    \$\begingroup\$ For the entries I've been involved in, feel free to use a reference to my OEIS account. Maybe you can just ask the other users if they happen to have an account as well and if they don't mind being credited with their full name. \$\endgroup\$
    – Arnauld
    Aug 28 '20 at 8:35
16
+200
\$\begingroup\$

JavaScript (ES7),  367 362 359  357 bytes

Saved 1 byte thanks to @Shaggy

Expects (n)(m).

n=>m=>(T=Array(n*n).fill(N=0),g=(A,P=[-1],k=T.findIndex(v=>!v),B=[...A,P[S='sort']()][S]())=>g[B]?0:~[1,1,0,1,1,0][M='map'](r=>g[B=B[M](P=>P[M](i=>~i?(y=i**.5|0)*y-i-(r?1-((~y*~y+~i>>1)-n)**2:y*~-~y):i)[S]())[S]()]=1)/P[m]?~k?g(B):++N:T[M]((v,j)=>v||(~P?P.every(i=>(y=i**.5|0)^j**.5|(i-j)**2-1&&j-i+2*(i+y&1?y:~y)):j-k)||T[T[j]++,g(A,[...P,j]),j]--))([])&&N

Try it online!

How?

TL;DR

This is a recursive search that keeps track of all the patterns that were already tried, transformed in all possible ways, in order to prune the search as soon as possible when a collision is found. This allows it to perform at a decent speed on small triangles despite an otherwise inefficient piece-building method.

Triangle description and cell indexing

A size-\$n\$ triangle is simply stored as an array of \$n^2\$ binary values. Empty cells are marked with \$0\$'s and occupied cells are marked with \$1\$'s.

JS initialization:

T = Array(n * n).fill(0)

By convention, the cells are numbered from \$0\$ to \$n^2-1\$, from left to right and top to bottom.

tile indexing

Below are some basic formulas:

  • The 0-indexed row of the cell \$c\$ is \$y_c=\lfloor\sqrt{c}\rfloor\$
  • The 0-indexed position of the cell \$c\$ within its row is \$c-{y_c}^2\$
  • The 0-indexed distance of the cell \$c\$ from the last cell in its row is \${(y_c+1)}^2-c-1\$

Testing whether 2 cells are neighbors

Two cells \$c\$ and \$d\$ are horizontal neighbors if \$y_c=y_d\$ and \$|c-d|=1\$ (e.g. \$c=10\$ and \$d=11\$, or the other way around).

Two cells \$c\$ and \$d\$ are vertical neighbors if either:

  • \$c+y_c\$ is even and \$d=c+2\times(y_c+1)\$ (e.g. \$c=3\$ and \$d=7\$)
  • \$c+y_c\$ is odd and \$d=c-2\times y_c\$ (e.g. \$c=7\$ and \$d=3\$)

Hence the following JS expression which is truthy if the cells i and j are not neighbors:

(y = i ** .5 | 0) ^ j ** .5 | (i - j) ** 2 - 1 && j - i + 2 * (i + y & 1 ? y : ~y)

Reflections

A vertical reflection is applied by doing:

$$d=2\times y_c\times (y_c+1)-c$$

Examples:

$$2\times y_{10}\times (y_{10}+1)-10=2\times 3\times 4-10=14\\ 2\times y_{14}\times (y_{14}+1)-14=2\times 3\times 4-14=10$$

reflection

Rotations

A 120° rotation is applied by doing:

$$d=\left(n-\left\lfloor\dfrac{(y_c+1)^2-c-1}{2}\right\rfloor\right)^2+{y_c}^2-c-1$$

Examples:

  • \$c=0\$ is turned into \$d=15\$
  • \$c=7\$ is turned into \$d=12\$

rotation

Combining reflections and rotations

In the JS implementation, both formulas are combined into the following expression. This code applies a reflection to the cell i when r = 0 or a rotation when r = 1.

(y = i ** .5 | 0) * y - i - (
  r ?
    1 - ((~y * ~y + ~i >> 1) - n) ** 2
  :
    y * ~-~y
)

To get all possible transformations of a tiling, we apply 2 rotations, followed by a reflection, followed by 2 rotations, followed by a reflection.

Hence the loop:

[1, 1, 0, 1, 1, 0].map(r =>
  /* ... apply the transformation to each cell of each piece of the tilling ... */
)

Describing the tiling

Each piece of the tiling is stored in an array of \$m+1\$ entries consisting of a leading -1 followed by \$m\$ indices corresponding to the cells it contains.

The current piece is stored in P[]. The array A[] contains the previous pieces. The array B[] contains the previous pieces and the current piece, with all pieces sorted in lexicographical order and all indices also sorted in lexicographical order within each piece.

Example:

The following tiling:

tiling

would be described with:

B = [
  [ -1, 0, 1, 2, 3 ],
  [ -1, 10, 11, 4, 9 ],
  [ -1, 12, 5, 6, 7 ],
  [ -1, 13, 14, 15, 8 ]
]

Once coerced to a string, this gives a unique key that allows us to detect whether a similar configuration was already encountered and prune the search.

"-1,0,1,2,3,-1,10,11,4,9,-1,12,5,6,7,-1,13,14,15,8"

The purpose of the -1 markers is to make sure that an incomplete piece followed by another piece in the key is not mixed up with another complete piece.

The keys are stored in the underlying object of the function g.

Main algorithm

The recursive search function goes as follows:

  • find the position k of the first empty cell in the triangle
  • update B[]
  • abort if B[] was already encountered
  • apply all transformations to B[] and mark them as encountered
  • if P[] is complete:
    • if the triangle is full (k is set to -1): we've found a new valid tiling, so increment the number of solutions N
    • otherwise, append P[] to A[] and start building a new piece
  • if P[] is not yet complete:
    • if P[] does not contain any tile, append k to it
    • otherwise, try to append the index of each tile that has at least one neighbor in P[]
\$\endgroup\$
5
  • 8
    \$\begingroup\$ Another lovely solution, Arnauld! If not for you, many of my challenges would go unanswered! \$\endgroup\$ Aug 26 '20 at 18:20
  • \$\begingroup\$ Is there a straightforward way to modify this so that it outputs examples of each of the a(n,m) partitions instead of the count? \$\endgroup\$ Aug 26 '20 at 20:16
  • \$\begingroup\$ Not much of a saving but -1 byte by passing the empty array as an argument on the first call of g, instead of assigning it as the default parameter of A. \$\endgroup\$
    – Shaggy
    Aug 26 '20 at 20:32
  • 1
    \$\begingroup\$ @PeterKagey You can replace ++N with console.log(++N,B.map(a=>a.sort((a,b)=>a-b))). The cells are numbered from \$0\$ to \$n^2-1\$, from left to right and top to bottom. \$\endgroup\$
    – Arnauld
    Aug 26 '20 at 21:29
  • \$\begingroup\$ @PeterKagey Please note that I've fixed a bug that was causing some distinct combinations to be considered identical for larger triangles (e.g. f(6)(6) was invalid). The above patch to display example solutions still works with the updated version, but each entry now includes a leading -1 that should be ignored. \$\endgroup\$
    – Arnauld
    Aug 27 '20 at 8:04
11
+500
\$\begingroup\$

Scala 3, 526...358 357 bytes

n=>m=>{val S=Set
var(c,d)=S(S(S(1->1)))->0
while(d<1&c!=S()){d=c.count{t=>t.size*m==n*n&t.forall(_.size==m)}
c=(for{t<-c
s<-t
a->b<-s
c=a%2*2-1
x->y<-S(a-1->b,a+1->b,(a+c,b+c))--t.flatten
if 0<y&y<=n&0<x&x<y*2}yield
S(0 to 4:_*).scanLeft(if(s.size<m)t-s+(s+(x->y))else t+S(x->y)){(t,i)=>t.map(_.map{(x,y)=>Seq((x,n+1-y+x/2),y*2-x->y)(i%2)})})map(_.head)}
d}

Try it in Scastie!

Dotty's tupled parameter destructuring save a few bytes, but it's pretty much the same as the approach below.

Scala 2, 548...362 361 bytes

n=>m=>{val S=Set
var(c,d)=S(S(S(1->1)))->0
while(d<1&c!=S()){d=c.count{t=>t.size*m==n*n&t.forall(_.size==m)}
c=(for{t<-c
s<-t
a->b<-s
c=a%2*2-1
x->y<-S(a-1->b,a+1->b,(a+c,b+c))--t.flatten
if 0<y&y<=n&0<x&x<y*2}yield
S(0 to 4:_*).scanLeft(if(s.size<m)t-s+(s+(x->y))else t+S(x->y)){(t,i)=>t.map(_.map{case(x,y)=>Seq((x,n+1-y+x/2),y*2-x->y)(i%2)})})map(_.head)}
d}

Try it online

Ungolfed version

To see the individual triangles

Explanation

Each point is represented by an x-y pair (Int,Int). The x-position starts out at 1 at the left and increases as it goes to the right. The y-position starts out at 1 at the top and increases as it goes to the bottom. A piece of the triangle is represented as a set of points (Set[(Int,Int)]), and a triangle (possible solution) is represented as a set of those pieces (Set[Set[(Int,Int)]])

The first line defines c, a Set which will hold all possible solutions (and currently just holds a single partially completed triangle that holds a single piece that holds a single point (\$(1,1)\$, the top of the triangle)). d says how many of those triangles are completed. This is the variable that will be returned at the very end.

The bulk of the function is taken up by a while loop that runs as long as d is 0 and c is not empty (if d is more than 0, it means we've found all the triangles we're ever going to find, and if c is empty, it means there aren't any possible solutions).

Each iteration, d is set to the number of triangles in c that have has \$\frac{n*n}{m}\$ pieces and all their pieces are of size m. For that, the expression c.count{t=>t.size*m==n*n&t.forall(_.size==m)} can be used.

Then, we find the next value of c. The code creates new triangles by adding neighbors to the old triangles in c, and to ensure only unique triangles are kept, it first creates a set of all 6 permutations for each of the new triangles. Because c is a Set, it removes duplicates by default without us having to do any work. After the permutations have been generated and the duplicates remove, it's simple to extract a single permutation with <all_permutations>map(_.head).

When the while loop ends, we simply return d.

Specifics:

Generating new triangles

For every shape in a triangle, we take all its neighbors, and remove the ones that are already in the triangle. Then, if the shape already has \$m\$ cells, we make a new shape containing only the neighbor and add it to the triangle, otherwise we add the neighbor to the shape. For comprehensions make this part easy:

for { 
  t <- c              //For every triangle t in c
  s <- t              //For every piece/shape s in t
  a -> b <- s         //For every point (a, b) in s
  e = a % 2 * 2 - 1   //This is just to reuse
  //The cell to the left, the cell to the right, and the cell above/below
  neighbors <- Set( (a - 1, b) , (a + 1, b) , (a + e, b + e) )
  //x and y are the coordinates of the neighbor
  x -> y <- neighbors -- t.flatten //Remove neighbors already in the triangle
  //Make sure the neighbor is within bounds of the triangle
  if 0 < y & y <= n & 0 < x & x < y * 2 
} yield (
  if (s.size < m) t - s + (s + (x -> y)) //If s is not full, add the neighbor to s
  else t + Set(x -> y) //Otherwise, make a new shape containing just (x, y)
)

The new triangles are not directly yielded, this is just an example.

Generating all permutations

Each triangle has 6 different permutations, which can be found by alternating between reflecting over the y-axis and rotating 60 degrees clockwise + reflecting it over the y-axis. We can scanLeft over a range of numbers, doing the first transformation when the element is even, and the second when it's odd.

Assuming we already have a triangle <new_triangle>, we can scan left over a range of 5 numbers, leaving us with 6 triangles:

0.to(4).scanLeft(<new_triangle>){ 
  (t, i) => //i is the current index/element, t is the triangle to transform
  t.map { s => //Transform every shape s in t
    s.map {
      case (x, y) => //Transform every point in s (x, y)
        //If i is even, it will rotate+reflect, if it's odd, it will reflect
        Seq( (x, n + 1 - y + x / 2) , (y * 2 - x, y) )(i%2)
    }
  }
}

Reflecting a point over the y-axis:

For a point \$(x,y)\$, the y-coordinate stays the same after reflecting, and the x-coordinate becomes \$y * 2 - x\$, since \$y * 2\$ is the biggest possible x-coordinate for a given y-coordinate.

Rotating a point 60 degrees clockwise + reflecting it over the y-axis:

You can rotate and reflect a point at once if you keep the x-coordinate the same and set the y-coordinate to \$n + 1 - y + x / 2\$.

Commented:

//Take n and m, curried
n => m => {
  val S = Set //The Set companion object, to reuse later
  //c holds all our possible solutions/triangles as we build them
  //d holds how many of the triangles in c are complete
  var (c, d) = S(S(S(1 -> 1))) -> 0

  //While we haven't found any complete triangles and 
  //the set of possible solutions is nonempty, keep going
  while (d < 1 & c != S()) {
    //Count how many of c's triangles have n*n/m pieces, each with m cells
    d = c.count { t => t.size * m == n * n & t.forall(_.size == m) }
    //This for comprehension adds a cell to each triangle and
    //generates all permutations of each new triangle
    c = (for { 
      t <- c
      s <- t
      a -> b <- s
      c = a % 2 * 2 - 1
      x -> y <- S(a - 1 -> b, a + 1 -> b, (a + c, b + c)) -- t.flatten
      if 0 < y & y <= n & 0 < x & x < y * 2
    } yield 
      S(0 to 4:_*).scanLeft(
         if (s.size < m) t - s + (s + (x -> y))
         else t + Set(x -> y)
      ) { (t, i) =>
         t.map(_.map { case (x, y) =>
           Seq((x, n + 1 - y + x / 2), y * 2 - x -> y)(i % 2)
         })
      }
      //Convert the Seq of permutations to a set so duplicates can be compared out of order and removed
     )  //End of massive for-comprehension 
     map (_.head) //Extract only the first permutation from each set of permutations
  }
  d
}
```
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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