trouver les frappes clavier à l'écran pour scala

Question

Je suis en train de résoudre une question récente interview à l'aide Scala ..

Vous avez un clavier à l'écran qui est une grille de 6 lignes, 5 colonnes chacune. Avec les alphabets de A à Z et l'espace vide sont d'abord disposés dans la rangée de la grille.

Vous pouvez utiliser ce clavier à l'écran pour taper des mots .. en utilisant votre télécommande TV en appuyant sur les touches Gauche, Droite, Haut, Bas ou OK pour taper chaque caractère. Question: à l'aide d'une chaîne d'entrée, trouvez la séquence de touches à appuyer sur la télécommande pour saisir l'entrée.

La mise en œuvre du code peut être trouvé à

https://github.com/mradityagoyal/scala/blob/master/OnScrKb/src/main/scala/OnScrKB.scala

J'ai essayé de résoudre cela en utilisant trois approches différentes ..

1. simple forldLeft.

   def keystrokesByFL(input: String, startChar: Char = 'A'): String = { 
   val zero = ("", startChar) 
   //(acc, last) + next => (acc+ aToB , next) 
   def op(zero: (String, Char), next: Char): (String, Char) = zero match { 
       case (acc, last) => (acc + path(last, next), next) 
   } 
   val result = input.foldLeft(zero)(op) 
   result._1 
   

   }

2. diviser pour mieux régner - Utilise diviser pour régner mécanisme. L'algorithme est similaire au tri par fusion. * Nous divisons le mot d'entrée en deux si la longueur est> 3 * nous appelons récursivement le sous-programme pour obtenir le chemin des moitiés gauche et droite de la scission. * A la fin .. nous ajoutons les frappes pour les premières touches + de la fin de la première chaîne au début de la deuxième chaîne + les séquences de touches pour la seconde. * Essentiellement, nous divisons la chaîne d'entrée en deux moitiés plus petites jusqu'à ce que nous arrivions à la taille 4. Pour plus petit que 4, nous utilisons le pli droit.

   def keystrokesByDnQ(input: String, startChar: Char = 'A'): String = { 
   def splitAndMerge(in: String, startChar: Char): String = { 
       if (in.length() < 4) { 
       //if length is <4 then dont split.. as you might end up with one side having only 1 char. 
       keystrokesByFL(in, startChar) 
       } else { 
       //split 
       val (x, y) = in.splitAt(in.length()/2) 
       splitAndMerge(x, startChar) + splitAndMerge(y, x.last) 
       } 
   } 
   splitAndMerge(input, startChar) 
   

   }

3. Fold - utilise la propriété que l'opération sous-jacente est associative (mais non commutative). * Par exemple, les séquences de touches ("ABCDEFGHI", startChar = 'A') == combinaisons de touches ("ABC", startChar = 'A') + combinaisons de touches ("DEF", "C") + combinaisons de touches ("GHI", 'F')

   def keystrokesByF(input: String, startChar: Char = 'A'): String = { 
       val mapped = input.map { x => PathAcc(text = "" + x, path = "") } // map each character in input to case class PathAcc("CharAsString", "") 
       val z = PathAcc(text = ""+startChar, path = "") //the starting char. 
   
       def op(left: PathAcc, right: PathAcc): PathAcc = { 
       PathAcc(text = left.text + right.text, path = left.path + path(left.text.last, right.text.head) + right.path) 
       } 
       val foldresult = mapped.fold(z)(op) 
   
       foldresult.path 
   } 
   

Mes questions: 1. la diviser pour mieux régner approche mieux que Fold?

1. sont Fold et diviser pour mieux régner mieux que foldLeft (pour ce problème spécifique)

2. Est-il possible que je peux représenter la diviser pour mieux régner l'approche ou l'approche Fold en tant que Monade? Je peux voir que la loi associative est satisfaite ... mais je ne suis pas capable de comprendre si un monoï est présent ici .. et si oui .. qu'est-ce que cela fait pour moi?

3. Divide et conquer approche-t-il le meilleur disponible pour ce problème particulier?

4. Quelle approche est la mieux adaptée pour les étincelles?

Toutes les suggestions sont les bienvenues ..

Answer 1

Voilà comment je le ferais:

def keystrokes(input: String, start: Char): String = 
((start + input) zip input).par.map((path _).tupled).fold("")(_ ++ _) 

Le principal point utilise la méthode par ici pour paralléliser la séquence de (Char, Char), afin qu'il puisse paralléliser le map, et prendre la mise en œuvre optimale pour fold.

L'algorithme prend simplement les caractères dans le String deux par deux (représentant les unités de chemin à parcourir), calcule le chemin entre eux, puis concatène le résultat. Notez que fold("")(_ ++ _) est fondamentalement mkString (bien que mkString sur la collecte parallèle est implémentée par seq.mkString donc il est beaucoup moins efficace).

Ce qui manque cruellement à vos implémentations, c'est la parallélisation des tâches. Même dans votre approche de diviser pour régner, vous ne courez jamais de code en parallèle, alors vous attendez que la première moitié soit terminée avant de commencer la seconde moitié (même si elles sont totalement indépendantes).

En supposant que vous utilisez parallélisation, la mise en œuvre classique de fold sur des séquences parallèles est précisément l'algorithme de division et conquer vous avez décrit, mais il est peut-être qu'il est mieux optimisé (par exemple, il peut choisir une autre valeur que 3 pour taille de morceau, j'ai tendance à faire confiance à la mise en œuvre de la collection scala sur ces questions).

Notez que fold sur String est probablement mis en œuvre avec foldLeft, donc il n'y a pas de valeur ajoutée que ce que vous avez fait avec foldLeft, sauf si vous utilisez .par avant.

Retour à vos questions (je le répète, la plupart du temps ce que je viens de dire):

1) Oui, la diviser pour mieux régner est mieux que ... fois sur String (mais pas sur parallélisés String)

2) Le pli ne peut être meilleur que FoldLeft avec une sorte de parallélisation, auquel cas il sera aussi bon (ou meilleur que, s'il y a une meilleure implémentation pour une collection parallélisée particulière) diviser-et-conquérir.

3) Je ne vois pas ce que les monades ont à voir avec quoi que ce soit ici. l'opérateur et le zéro pour fold doivent en effet former un monoïde (sinon, vous aurez quelques problèmes avec l'ordre de fonctionnement si l'opérateur n'est pas associatif, et un bruit non désiré si zéro n'est pas un élément neutre).

4) Oui, que je sache, une fois parallélisés

5) Spark est parallèle en soi, de sorte que la question principale serait de rejoindre tous les morceaux ensemble à la fin. Ce que je veux dire, c'est qu'un RDD n'est pas commandé, donc vous aurez besoin de garder des informations sur quel élément d'entrée doit être placé dans votre cluster. Une fois que vous avez fait cela correctement (en utilisant des partitions et autres, ce sera probablement une question entière), en utilisant map et fold fonctionne toujours comme un charme (Spark a été conçu pour avoir une API aussi proche que possible de la collection scala, donc c'est vraiment bien ici).