[Question]
  [
Similar in spirit to [Number of distinct tilings of an n X n square with free n-polyominoes](https://codegolf.stackexchange.com/q/194056/53884) and [Partition a square grid into parts of equal area](https://codegolf.stackexchange.com/questions/179074/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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") 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](https://i.stack.imgur.com/cwPad.png)](https://i.stack.imgur.com/cwPad.png)
[![Second partition of the length 4 triangle into two parts of size 8](https://i.stack.imgur.com/zF4zH.png)](https://i.stack.imgur.com/zF4zH.png)
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](https://i.stack.imgur.com/IITjm.png)](https://i.stack.imgur.com/IITjm.png)
[![Second partition of the length 4 triangle into parts of size 4](https://i.stack.imgur.com/sDCut.png)](https://i.stack.imgur.com/sDCut.png)
[![Third partition of the length 4 triangle into parts of size 4](https://i.stack.imgur.com/F5DeW.png)](https://i.stack.imgur.com/F5DeW.png)
# 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](https://en.wikipedia.org/wiki/Dihedral_group_of_order_6).*
Your code should be able to handle the inputs in the table on [TIO](https://tio.run/#), and it should be able to handle larger inputs in principle.
This is a [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") challenge, so the shortest code wins.
  
[Answer]
# 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!](https://tio.run/##fZDBbqMwEEDv/Yr0QmbAJphkV7tIA2puPTRCKjfLK0UNQSYJVKRCawnx66lJKnVXhR48tvxm5o1dbtvt@aXRr2@8qnf5ZU@XiuITxZDRQ9NsDVRuhf5eH4@woQBZQfDAUpJcKHagzJJq91jt8r/QUnzfIluT9H3f5shnmp/r5m2uAJV8thEpLuRaJUHUS8EEC9g1KvlE89P21SY21wxayycFKcXpsGuKe52AIe26/o8uQNdwzaFJBAfojdsbr9dxLJBX6LphZG94bzDSeJNeoyKBi1SeVNIfkgLWGHneJsqG/tCy0k7Wdh30aZL6eZs3ZrD@o/xTXg@geTk4uHCckmsvdEF7xhGJiawRo5IfsOsymclSeR4r7FcNn5GyUqFdnCOCVOg4m8tLXZ3rY@4f6wL2IBBmAnG2WMzE3f8o/B6FNxSMoNV41XK64XK64YCW01W/x9Fq2rWadq0@XWPo413LEfTrhsKvSPz8GOPyDg "JavaScript (Node.js) – 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](https://i.stack.imgur.com/myUWb.png)](https://i.stack.imgur.com/myUWb.png)
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](https://i.stack.imgur.com/LHEJq.png)](https://i.stack.imgur.com/LHEJq.png)
### 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](https://i.stack.imgur.com/dasUy.png)](https://i.stack.imgur.com/dasUy.png)
### 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](https://i.stack.imgur.com/BGNXd.png)](https://i.stack.imgur.com/BGNXd.png)
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[]`
[Answer]
# [Scala 3](https://dotty.epfl.ch/), ~~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!](https://scastie.scala-lang.org/UZoguHDFQ36m0XVp6C5ZdQ)
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](https://scastie.scala-lang.org/LRWqpdpxQcyDNEmTLjchWw)
[Ungolfed version](https://scastie.scala-lang.org/R8meXNzcR8aM580CtLYOWQ)
[To see the individual triangles](https://tio.run/##tVPLjtowFN3nK1xEkZ04ATKoalEcqYsuKnVWzG6KRiYYlDYxNDaIEPLt9NohhUm7GI2mDnZyH@f6Pg4q4Rk/bxY/RKLRPU8lqs663Ar0wGZCP5qNv0pNYZP53FmKVYzl1GhyeyZT4/IwN9643SM/HhFYra3a8wwtWRIkm53UlWaxDlR6FG7OmHTlYKCD1abgWYafrJ6xnNROusLLeHRKglR9ybe6JEmwSjMtipcGEJkSkC3NKW4SwWQ4xeBY6chPHBX52sGcLkjkKydhY5@/D93QwQdagmomfmHuj/14QblnX5h7CV14CSHpCo0iVg7KSA7g4zA4RKUbeuNrHu@ebBhSl6nIlghqUTazKCfaVx6G38GPwcEkibRn2tYoSIVPVBMWAwZyCFKomGuBNb0jUF7Ot1VzJlwJewmLTX/3TEK2JcT1xmQYOns39CHivq7JKuP6HhDQN1OVpvrfYXBpMPAJmFocUqXViZxsH0/I06A8D13HXHZkpd9ehLEEWEiMInSPhGJIhPhH4rwdkcDjrVi0/K@8uDSlJUfLDvYXPaAKqeH/pi5jfxVRdq8hyotmBwwIXkWboOEN3hGys51GO8scxx2aoaMcasa8WKsp@lwUvHyc6SKV6zlBDFUOgmVy1AJigOYbxMJWixAeU3gIbcWwK6KQjp7Jk1v7HUXjjvzMH@S7jv3TrTzp4Ccd/MTgn8sTmMSt/JGGt/L4A8SzYnMCNxC2vCwIivymCeTSFYS20CedSdzzL6tHLhbTsUKYfllakw5A9STrS4py1s8pKli/oGi90axfAciSre51MRcRmbhm3lcFQk9dhVX9bAaJexXqUfuga9hrkc26cX8oUi7XmZh@l8gg/7xuwNevG6DxaA1cKVFo3NbDWNFYasfs@vwb)
## 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
}
```
```
]