Найти нажатия клавиш для экранной клавиатуры scala

Question

Я пытаюсь решить вопрос недавнего интервью, используя Scala.

У вас есть экранная клавиатура, которая представляет собой сетку из 6 строк по 5 столбцов в каждой. С алфавитами от A до Z и пустое пространство располагаются в строке сетки в первую очередь.

Вы можете использовать это на экранной клавиатуре для ввода слов... с помощью пульта дистанционного управления телевизора, нажимая клавиши "Влево", "Вправо", "Вверх", "Вниз" или "ОК" для ввода каждого символа.

Вопрос: по заданной строке ввода найдите последовательность нажатий клавиш, которые необходимо нажать на пульте дистанционного управления для ввода ввода.

Реализацию кода можно найти по адресу

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

Я пытался решить эту проблему, используя три разных подхода..

1. Простой 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. разделяй и властвуй - Использует механизм разделяй и властвуй. Алгоритм похож на сортировку слиянием. * Мы разделяем входное слово на два, если длина> 3 *, мы рекурсивно вызываем подпрограмму, чтобы получить путь левой и правой половин из разделения. * В конце... мы добавляем нажатия клавиш для первого + нажатия клавиш от конца первой строки до начала второй строки + нажатия клавиш для второй. * По сути, мы разделяем входную строку на две меньшие половины, пока не доберемся до размера 4. для меньших 4 мы используем сгиб справа.

   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 - использует свойство, лежащее в основе операции, ассоциативно (но не коммутативно). * Например, нажатия клавиш ("ABCDEFGHI", startChar = 'A') == нажатия клавиш ("ABC", startChar='A')+ нажатия клавиш ("DEF", "C") + нажатия клавиш ("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
   }
   

Мои вопросы: 1. Является ли подход "разделяй и властвуй" лучше, чем фолд?

2. сложить и разделить и победить лучше, чем foldLeft (для этой конкретной задачи)

3. Есть ли способ, которым я могу представить подход "разделяй и властвуй" или подход Fold как монаду? Я вижу, как ассоциативный закон удовлетворяется... но я не могу понять, присутствует ли здесь моноид... и если да, то чего он добился для меня?

4. Является ли подход "Разделяй и властвуй" лучшим вариантом для решения этой конкретной проблемы?

5. Какой подход лучше подходит для искры?

Любые предложения приветствуются.

Answer 1

Вот как бы я это сделал:

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

Основным моментом здесь является использование par метод распараллеливания последовательности (Char, Char)так, чтобы он мог распараллелить mapи принять оптимальную реализацию для fold,

Алгоритм просто принимает символы в String два на два (представляющие единицы пройденного пути), вычисляет путь между ними, а затем объединяет результат. Обратите внимание, что fold("")(_ ++ _) в основном mkString (хотя mkString на параллельном сборе осуществляется seq.mkString так что это гораздо менее эффективно).

Чего не хватает вашим реализациям, так это распараллеливания задач. Даже при использовании подхода "разделяй и властвуй" вы никогда не выполняете код параллельно, поэтому вы будете ждать окончания первой половины, прежде чем начинать вторую (даже если они абсолютно независимы).

Предполагая, что вы используете распараллеливание, классическая реализация fold для параллельных последовательностей - это именно тот алгоритм "разделяй и властвуй", который вы описали, но может случиться так, что он лучше оптимизирован (например, он может выбрать другое значение, чем 3 Что касается размера фрагментов, я склонен доверять разработчикам scala-collection по этим вопросам).

Обратите внимание, что fold на String вероятно реализовано с foldLeft, так что нет добавленной стоимости, чем то, что вы сделали с foldLeft, если вы не используете .par до.

Возвращаясь к вашим вопросам (я в основном повторю то, что только что сказал):

1) Да, разделяй и властвуй лучше, чем сбрасывай... на String (но не на параллельном String)

2) Fold может быть только лучше, чем FoldLeft с некоторой параллелизацией, и в этом случае он будет так же хорош (или лучше, чем, если есть лучшая реализация для конкретной параллельной коллекции) разделяй и властвуй.

3) Я не вижу, какое отношение монады здесь имеют к чему-либо. оператор и ноль для fold действительно должен образовывать моноид (в противном случае у вас возникнут проблемы с упорядочением операций, если оператор не ассоциативный, и с нежелательным шумом, если ноль не является нейтральным элементом).

4) Да, я знаю, когда-то распараллелил

5) Искра по своей сути параллельна, поэтому основной проблемой будет объединение всех частей вместе в конце. Я имею в виду, что RDD не упорядочен, так что вам нужно будет хранить некоторую информацию о том, какая часть ввода должна быть размещена в вашем кластере. Как только вы сделали это правильно (используя разделы и тому подобное, это, вероятно, сам вопрос), используя map а также fold все еще работает как шарм (Spark был спроектирован так, чтобы иметь API, максимально приближенный к scala-collection, так что это действительно хорошо здесь).