Tous Les Possible De Tic Tac Toe Combinaisons Gagnantes
J'ai eu un entretien ont été on m'a demandé une apparence simple, l'algorithme de la question: "Écrire un algorithme de me rendre possible toutes les combinaisons gagnantes pour tic tac toe." Je ne peut toujours pas trouver une méthode efficace pour gérer cela. Est-il un algorithme standard ou commun qui devrait être appliquée à des questions similaires, comme ce que je ne suis pas au courant?
paxdiablo la réponse de travaux; vous pouvez également l'approche de 'l'autre côté': démarrer à partir d'un vide conseil, et de jouer chaque jeu, garder une trace de la finale de positions gagnantes atteint. Ce serait plus de travail que paxdiablo réponse, mais de plus en plus complexes, jeu de tic tac toe est peut-être plus facile.
OriginalL'auteur DroidT | 2015-02-25
Vous devez vous connecter pour publier un commentaire.
C'est un de ces problèmes est en fait assez simple pour que la force brute et, alors que vous pourriez utilisation combinatoire, théorie des graphes, ou de nombreux autres outils complexes à résoudre, je serais vraiment impressionné par les candidats qui reconnaissent le fait il y a un moyen plus facile (du moins pour ce problème).
Il y a seulement 39, ou 19,683 combinaisons possibles de placer
x
,o
ou<blank>
dans la grille, et non pas tous ceux qui sont valides.D'abord, la position du jeu est celui où la différence entre
x
eto
compte n'est pas plus qu'un, car ils ont pour une alternance de mouvements.En outre, il est impossible d'avoir un état où les deux côtés de trois dans une rangée, de sorte qu'ils peuvent être réduits. Si tous les deux ont trois dans une rangée, puis l'un d'eux aurait gagné dans le précédente déplacer.
Il y a en fait une autre limite qu'il est impossible pour un côté à avoir remporté de deux façons différentes sans cellule (encore une fois, ils auraient gagné dans le mouvement précédent), ce qui signifie que:
ne peut pas être atteint, tandis que:
peut être. Mais nous pouvons ignorer que depuis il n'y a aucun moyen de gagner de deux façons sans cellule sans avoir déjà violé la "différence maximale de règle, car vous avez besoin de six cellules pour que, avec l'adversaire que trois.
Je voudrais donc simplement d'utiliser la force brute et, pour chaque position où la différence est zéro ou un, entre les comtes, vérifiez les huit possibilités de gains pour les deux côtés. En supposant que l'un d'entre eux a obtenu une victoire, c'est légal, jeu gagnant.
Ci-dessous est une preuve de concept en Python, mais d'abord la sortie de
time
lorsqu'il est exécuté sur le processus d'envoi de la sortie de/dev/null
de montrer comment il est rapide:Le code:
Comme un intervenant l'a souligné, il y a une restriction. Le gagnant pour un conseil, ne peut pas avoir moins de cellules que le perdant puisque cela signifie que le perdant tout juste de déménager, malgré le fait que le gagnant avait déjà gagné sur le dernier mouvement.
Je ne vais pas changer le code pour prendre en compte mais ce serait une simple question de vérification qui a le plus de cellules (la dernière personne qui a déménagé) et de s'assurer de la ligne de réussite appartenait.
J'ai reçu votre point 🙂 totalement oublié l'espace d'option, donc je vais reprendre mon commentaire 🙂
Une différence de un déménagement ne devrait pas être autorisée dans les deux sens. Le perdant ne peut pas se déplacer après que l'adversaire a gagné.
bon point, je vais ajouter que dans la réponse, mais je ne vais pas la peine de modifier le code.
Merci @paxdiablo pour la réponse détaillée! Pourriez-vous clarifier ce qui se passe avec le code, en particulier dans la dernière boucle, pour nous les non développeurs php?
OriginalL'auteur paxdiablo
Une autre façon serait de commencer avec chacun des huit positions gagnantes,
et de manière récursive remplir dans toutes les combinaisons (démarrer avec insertion de 2
o
's, puis ajouter unex
pour chaqueo
; évitero
positions gagnantes):OriginalL'auteur גלעד ברקן
C'est une java équivalent exemple de code
paquet testit;
public class TicTacToe {
}
`
OriginalL'auteur Vijay Rumao
Aujourd'hui j'ai eu un entretien avec Apple et j'ai eu la même question. Je ne pouvais pas penser bien à ce moment. Plus tard, avant d'aller à une réunion, j'ai écrit la fonction pour les combinaisons dans les 15 minutes, et quand je suis revenue de la réunion, j'ai écrit la fonction de validation de nouveau dans 15 minutes. Je suis nerveuse à des entrevues, des Apple de ne pas les fiducies de mon cv, ils seulement faire confiance à ce qu'ils voient dans l'interview, je ne les blâme pas, de nombreuses entreprises sont les mêmes, je dis juste que quelque chose dans ce processus d'embauche n'a pas l'air très intelligent.
Il en soit, voici ma solution en Swift 4, il y a 8 lignes de code pour les combinaisons de fonction et 17 lignes de code pour vérifier valide d'un conseil d'administration.
Cheers!!!
OriginalL'auteur user5117217