Taglia un triangolo in parti uguali!

Aug 25 2020

Simile nello spirito a Numero di tassellature distinte di un quadrato n X n con n-poliomini liberi e Partiziona una griglia quadrata in parti di area uguale , questa sfida ti farà contare i modi per suddividere un triangolo in una griglia triangolare. L'obiettivo di questa sfida di code-golf è scrivere un programma che restituisca \$ a(n,m)\$, il numero di modi per partizionare un triangolo di lunghezza laterale \$n\$in parti uguali contenenti \$m\$cellule ciascuno. Le parti devono essere contigue, dove due celle sono considerate toccanti se condividono un lato.

Esempi

Fino alla rotazione e alla riflessione, ci sono due modi per partizionare la dimensione- \$4\$triangolo in parti uguali di dimensione \$8\$, quindi \$a(4,8) = 2\$:

Fino alla rotazione e alla riflessione, ci sono tre modi per partizionare la dimensione- \$4\$triangolo in quattro parti di dimensione \$4\$, quindi \$a(4,4) = 3\$:

tavolo

 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

(Ho creato questa tabella a mano, quindi commenta se trovi errori.)

Sfida

Scrivi un programma che accetta un input \$n\$, che è la dimensione di un triangolo e un parametro \$m\$, che è la dimensione di ogni regione e restituisce il numero di modi per partizionare la dimensione \$n\$triangolo in \$n^2/m\$parti di dimensioni \$m\$ fino alle rotazioni e riflessioni del triangolo . Il tuo codice dovrebbe essere in grado di gestire gli input nella tabella su TIO e dovrebbe essere in grado di gestire input più grandi in linea di principio.

Questa è una sfida di golf da codice , quindi il codice più breve vince.

Risposte

13 Arnauld Aug 26 2020 at 13:38

JavaScript (ES7),  367 362 359  357 byte

Salvato 1 byte grazie a @Shaggy

Aspetta (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

Provalo online!

Come?

TL; DR

Si tratta di una ricerca ricorsiva che tiene traccia di tutti i pattern già provati, trasformati in tutti i modi possibili, in modo da potare la ricerca il prima possibile quando viene trovata una collisione. Ciò gli consente di funzionare a una velocità decente su piccoli triangoli nonostante un metodo di costruzione dei pezzi altrimenti inefficiente.

Descrizione del triangolo e indicizzazione delle celle

Una taglia- \$n\$triangolo viene semplicemente memorizzato come un array di \$n^2\$valori binari. Le celle vuote sono contrassegnate con \$0\$e le celle occupate sono contrassegnate con \$1\$'S.

Inizializzazione JS:

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

Per convenzione, le celle sono numerate da \$0\$a \$n^2-1\$, da sinistra a destra e dall'alto in basso.

Di seguito sono riportate alcune formule di base:

  • La riga indicizzata 0 della cella \$c\$è \$y_c=\lfloor\sqrt{c}\rfloor\$
  • La posizione indicizzata 0 della cella \$c\$all'interno della sua riga è \$c-{y_c}^2\$
  • La distanza indicizzata 0 della cella \$c\$dall'ultima cella della sua riga è \${(y_c+1)}^2-c-1\$

Verificare se 2 celle sono vicine

Due celle \$c\$e \$d\$sono vicini orizzontali se \$y_c=y_d\$e \$|c-d|=1\$(ad es. \$c=10\$e \$d=11\$o viceversa).

Due celle \$c\$e \$d\$ sono vicini verticali se:

  • \$c+y_c\$è pari e \$d=c+2\times(y_c+1)\$(ad es. \$c=3\$e \$d=7\$)
  • \$c+y_c\$è strano e \$d=c-2\times y_c\$(ad es. \$c=7\$e \$d=3\$)

Da qui la seguente espressione JS che è veritiera se le cellule ie nonj sono vicine:

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

Riflessi

Una riflessione verticale viene applicata facendo:

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

Esempi:

$$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$$

Rotazioni

Si applica una rotazione di 120 ° facendo:

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

Esempi:

  • \$c=0\$è trasformato in \$d=15\$
  • \$c=7\$è trasformato in \$d=12\$

Combinare riflessioni e rotazioni

Nell'implementazione JS, entrambe le formule sono combinate nella seguente espressione. Questo codice applica un riflesso alla cella iquando r = 0o una rotazione quando r = 1.

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

Per ottenere tutte le possibili trasformazioni di una piastrellatura, applichiamo 2 rotazioni, seguite da una riflessione, seguite da 2 rotazioni, seguite da una riflessione.

Da qui il ciclo:

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

Descrivere la piastrellatura

Ogni pezzo della piastrellatura è memorizzato in un array di \$m+1\$voci costituite da un interlinea -1seguito da \$m\$ indici corrispondenti alle celle che contiene.

Il brano corrente viene memorizzato in P[]. La matrice A[]contiene i pezzi precedenti. L'array B[]contiene i pezzi precedenti e il pezzo corrente, con tutti i pezzi ordinati in ordine lessicografico e tutti gli indici anche ordinati in ordine lessicografico all'interno di ogni pezzo.

Esempio:

La seguente piastrellatura:

sarebbe descritto con:

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

Una volta costretto a una stringa, questo fornisce una chiave univoca che ci consente di rilevare se una configurazione simile è già stata rilevata e di sfoltire la ricerca.

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

Lo scopo dei -1marcatori è quello di assicurarsi che un pezzo incompleto seguito da un altro pezzo nella chiave non sia confuso con un altro pezzo completo.

Le chiavi vengono memorizzate nell'oggetto sottostante della funzione g.

Algoritmo principale

La funzione di ricerca ricorsiva è la seguente:

  • trova la posizione kdella prima cella vuota nel triangolo
  • aggiornare B[]
  • interrompi se B[]è già stato rilevato
  • applicare tutte le trasformazioni B[]e contrassegnarle come incontrate
  • se P[]è completo:
    • se il triangolo è pieno ( kè impostato su -1): abbiamo trovato una nuova piastrellatura valida, quindi incrementa il numero di soluzioniN
    • altrimenti, aggiungere P[]al A[]e iniziare a costruire un nuovo pezzo
  • se P[]non è ancora completo:
    • se P[]non contiene alcuna tegola, aggiungere kad essa
    • altrimenti, prova ad aggiungere l'indice di ogni tessera che ha almeno un vicino P[]
5 user Aug 30 2020 at 16:10

Scala 3 , 526 ... 358 357 byte

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}

Provalo in Scastie!

La destrutturazione dei parametri tupla di Dotty risparmia pochi byte, ma è più o meno la stessa dell'approccio seguente.

Scala 2, 548 ... 362 361 byte

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}

Provalo online

Versione ungolfed

Per vedere i singoli triangoli

Spiegazione

Ogni punto è rappresentato da una coppia xy (Int,Int). La posizione x inizia da 1 a sinistra e aumenta man mano che va a destra. La posizione y inizia da 1 in alto e aumenta man mano che si va verso il basso. Un pezzo del triangolo è rappresentato come un insieme di punti ( Set[(Int,Int)]) e un triangolo (possibile soluzione) è rappresentato come un insieme di quei pezzi ( Set[Set[(Int,Int)]])

La prima riga definisce c, a Setche conterrà tutte le possibili soluzioni (e attualmente contiene solo un singolo triangolo parzialmente completato che contiene un singolo pezzo che contiene un singolo punto ( \$(1,1)\$, la parte superiore del triangolo)). ddice quanti di quei triangoli sono stati completati. Questa è la variabile che verrà restituita alla fine.

La maggior parte della funzione è occupata da un ciclo while che viene eseguito finché dè 0 e cnon è vuoto (se dè maggiore di 0, significa che abbiamo trovato tutti i triangoli che troveremo, e se cè vuoto, significa che non ci sono soluzioni possibili).

Ogni iterazione dè impostata sul numero di triangoli cche hanno \$\frac{n*n}{m}\$pezzi e tutti i loro pezzi sono di dimensioni m. Per questo, è c.count{t=>t.size*m==n*n&t.forall(_.size==m)}possibile utilizzare l'espressione .

Quindi, troviamo il valore successivo di c. Il codice crea nuovi triangoli aggiungendo vicini ai vecchi triangoli in ce per garantire che vengano conservati solo triangoli univoci, crea prima un insieme di tutte e 6 le permutazioni per ciascuno dei nuovi triangoli. Poiché cè un Set, rimuove i duplicati per impostazione predefinita senza che dobbiamo fare alcun lavoro. Dopo che le permutazioni sono state generate e i duplicati rimossi, è semplice estrarre una singola permutazione con <all_permutations>map(_.head).

Quando il ciclo while finisce, torniamo semplicemente d.

Specifiche:

Generazione di nuovi triangoli

Per ogni forma in un triangolo, prendiamo tutti i suoi vicini e rimuoviamo quelli che sono già nel triangolo. Quindi, se la forma ha già \$m\$celle, creiamo una nuova forma contenente solo il vicino e lo aggiungiamo al triangolo, altrimenti aggiungiamo il vicino alla forma. Per la comprensione semplifica questa parte:

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

I nuovi triangoli non vengono prodotti direttamente, questo è solo un esempio.

Generazione di tutte le permutazioni

Ogni triangolo ha 6 diverse permutazioni, che possono essere trovate alternando la riflessione sull'asse y e la rotazione di 60 gradi in senso orario + riflettendola sull'asse y. Possiamo scanLeftsu un intervallo di numeri, eseguendo la prima trasformazione quando l'elemento è pari e la seconda quando è dispari.

Supponendo di avere già un triangolo <new_triangle>, possiamo scansionare rimanenti su un intervallo di 5 numeri, lasciandoci con 6 triangoli:

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

Riflettendo un punto sull'asse y :

Per un punto \$(x,y)\$, la coordinata y rimane la stessa dopo la riflessione e la coordinata x diventa \$y * 2 - x\$, poiché \$y * 2\$ è la coordinata x più grande possibile per una data coordinata y.

Ruotando un punto di 60 gradi in senso orario + riflettendolo sull'asse y :

Puoi ruotare e riflettere un punto contemporaneamente se mantieni la stessa coordinata x e imposti la coordinata y su \$n + 1 - y + x / 2\$.

Commentato:

//Take n and m, curried
n => m => {
  //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) = Set(Set(Set(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 != c -- c) {
    //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 <- Set(a - 1 -> b, a + 1 -> b, (a + c, b + c)) -- t.flatten
      if 0 < y & y <= n & 0 < x & x < y * 2
    } yield 
      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)
         })
      }.toSet  
      //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
}
```