Dans le jeu d'échecs, il y a un morceau appelé la reine qui peut attaquer n'importe quel autre morceau qui est sur la même ligne, colonne ou diagonale. Aux échecs, il y a généralement deux côtés, noir et blanc, chaque pièce appartenant à l'une des équipes. Les pièces ne peuvent pas attaquer les pièces appartiennent à la même équipe.
Votre objectif est de découvrir les plus grandes armées coexistantes pacifiques pour une planche carrée. C'est le plus grand nombre de reines noires et blanches pouvant tenir sur le plateau de sorte qu'aucune deux reines ne peuvent s'attaquer et le nombre de reines noires est égal au nombre de reines blanches.
Vous recevrez en entrée la longueur latérale d'une planche carrée, et vous devrez afficher le nombre de tailles des plus grandes armées coexistantes pacifiques pouvant tenir sur cette planche.
Il s'agit de code-golf , les règles standard pour le tag s'appliquent.
Ces cas de test englobent toutes les réponses connues. Votre solution doit être une réponse généralisée qui, avec suffisamment de puissance et de temps de calcul, peut calculer la solution pour n'importe quelle valeur d'entrée.
dix 2: 0 3: 1 4: 2 5: 4 6: 5 7: 7 8: 9 9: 12 10: 14 11: 17 12: 21 13: 24
Réponses:
C, 476 octets, DFS itérant des reines blanches, O (2 n 2 )
518 octets, DFS avec élagage, O (2 n )
577 octets, DFS itérant des reines blanches et noires, O (?)
Fondamentalement, le code parcourt les possibilités de reine blanche et vérifie si la reine noire pourrait être placée à ce moment-là.
Tableau de référence de vitesse (en secondes):
la source
Clingo , 90 octets
Démo
la source
Python 2 |
325284217 octetsEssayez-le en ligne!
Modifier: tuples remplacés par des entiers en g et d'autres modifications triviales.
Edit2: octets jusqu'à 217 grâce à musicman523 et CalculatorFeline !
Comment ça fonctionne
Le programme parcourt toutes les positions possibles des
nreines et filtre les points non pacifiquesgcausés par la position des reines. Si les points restants sont supérieurs àncela, cela signifie qu'il est possible pour lesnarmées de la reine de rester en paix. Si pour la valeur suivante den, aucune situation paisible n'est trouvée, le programme se termine avec le code de sortie:,n-1qui est la réponse. Bref, c'est de la force bruteLe programme peut être accéléré en remplaçant les deux dernières lignes par
la source
from module import*pour tout importer à partir d'un module et enregistrer des octets.Haskell ,
169156153152octetsDéfinit une fonction
g, peut être jouable au golf. Essayez-le en ligne! Sur TIO, une fois compilé avec-O2, cela prend environ 36 secondes pour n = 4 et expire sur n = 5 . La complexité temporelle doit être O (n 2 4 n 2 ) .Explication
Nous itérons sur les valeurs possibles du nombre de reines ( q ). Pour chaque q , nous générons toutes les paires de sous-ensembles taille- q de [1..n] 2 , un ensemble de reines noires ( b ) et une de reines blanches ( w ). Ensuite, chaque élément de b est vérifié par rapport à chaque élément de w pour voir s'ils partagent une ligne, une colonne, une diagonale ou une anti-diagonale. Cela prend également en charge deux pièces partageant la même coordonnée. La plus grande valeur de q qui admet une configuration paisible est la valeur finale.
Les deux premières lignes du programme définissent la fonction
!, qui calcule les sous-kséquences de longueur d'une listex. L'implémentation se fait par une récursion de base: soit choisissez le premier élément à faire dans l'ensemble ou non et récursif à la queue, décrémentantksi nécessaire. Ensuite, la liste vide ou atteinte, vérifiez celak==0.La deuxième fonction auxiliaire
&prend un nombreq(nombre de reines de chaque côté) et une listel(les coordonnées x de la carte, également utilisées comme coordonnées y), et retourne une valeur booléenne indiquant s'il existe une configuration pacifique. Nous calculons d'abordpla liste des sous-qséquences de longueur de la liste des valeurs[x,y,x-y,x+y], oùxetys'étendentl. Ils représentent la ligne, la colonne, la diagonale et l'anti-diagonale d'un carré(x,y)sur le plateau.Ensuite, nous avons le résultat de
q&l. Nous dessinons deux sous-séquencesbet àwpartir dep, jumelons les 4 listes entre elles de toutes les manières possibles, et vérifions qu'elles diffèrent toujours dans les 4 coordonnées. Si certains choixbetwaboutissent à un résultat véridique, nous revenonsTrue.La dernière ligne est la fonction principale. Étant donné
n, il trouve simplement la plus grande valeur possible deqce quiq&[1..n]est vrai.la source