Скала способ найти элементы один за другим

Question

Я ищу метод, который возвращает истину или ложь, учитывая List [String] со следующей логикой.

• Список называется "1 start", когда A находится в списке
• Список называется «2 start», если после «B» есть строка «C»

Например,

• [A, B, Z] этот список «1 начало», но не «2 начало»
• [A, B, Z, C] этот список «2 начало» и «1 начало»

сейчасЯ хочу функцию hasTwoStarts, которая будет возвращаться, если в списке есть начало, после которого следует любой из двух.Это означает, что любая из следующих комбинаций должна возвращать true:

"1 start" "1 start" [A, B, Z, M, A] 
"1 start" "2 start" [A, B, Z, C, T]
"2 start" "1 start" [Z, B, C, X, A]
"2 start" "2 start" [B, X, C, M, B, C]

, и если ни в одном из вышеприведенных случаев она возвращает false

В нефункциональном режиме это может быть достигнуто с помощью грязной логики цикла, ноЕсть ли лучший функциональный способ решить эту проблему?

Также сворачивание списка итераций.

Answer 1

Это решение делает один проход по списку и останавливается, как только решение найдено. Это хвостовая рекурсия, поэтому он должен скомпилироваться в простой цикл.

def hasTwoStarts[T](list: List[T]) = {
  @annotation.tailrec
  def loop(l: List[T], startCount: Int, seenB: Boolean): Boolean = l match {
    case _ if startCount == 2 => true
    case Nil => false
    case h :: t => h match {
      case A =>
        loop(t, startCount + 1, seenB)
      case B =>
        loop(t, startCount, true)
      case C if seenB =>
        loop(t, startCount + 1, false)
      case _ =>
        loop(t, startCount, seenB)
    }
  }

  loop(list, 0, false)
}

Это очень специфическое решение проблемы, и его необходимо будет переработать, если будет изменено какое-либо из условий запуска.

Answer 2

Хотя вопрос кажется немного расплывчатым (по крайней мере, придумайте более подходящие имена, чем "1 start" & "2 start"?), Вы можете использовать следующие код-фрагмент (ы)

---

Начиная с этих служебных методов

// Utility methods
def endIndexOf1Start(list: List[String], startIndex: Int = 0): Option[Int] = {
  val firstIndex: Int = list.indexOf("A", from=startIndex)
  if (firstIndex >= 0) Some(firstIndex) else None
}

def endIndexOf2Start(list: List[String], startIndex: Int = 0): Option[Int] = {
  lazy val indexOfB: Int = list.indexOf("B", from=startIndex)
  lazy val indexOfC: Int = list.indexOf("C", from=indexOfB)
  if ((indexOfB >= 0) && (indexOfC > indexOfB)) Some(indexOfC) else None
}

def endIndexOfSomeStart(list: List[String], startIndexOpt: Option[Int] = None): Option[Int] = {
  val startIndex: Int = startIndexOpt.getOrElse(0)
  lazy val _endIndexOf1Start: Option[Int] = endIndexOf1Start(list, startIndex)
  lazy val _endIndexOf2Start: Option[Int] = endIndexOf2Start(list, startIndex)
  _endIndexOf1Start.orElse(_endIndexOf2Start)
}

---

Напишите метод, который дает Boolean: есть ли 2 отдельных ( не перекрывающихся ) запускается или нет

// Final decider method
def containsTwoStarts(list: List[String]): Boolean = {
  lazy val endIndexOfFirstStart: Option[Int] = endIndexOfSomeStart(list)
  lazy val endIndexOfSecondStart: Option[Int] = endIndexOfSomeStart(list, endIndexOfFirstStart)
  (endIndexOfFirstStart.nonEmpty && endIndexOfSecondStart.nonEmpty)
}

---

Данный пример ввода

// Sample input
val sampleInputs: List[List[String]] = List(
  List("A", "B", "Z", "M", "A"),
  List("A", "B", "Z", "C", "T"),
  List("Z", "B", "C", "X", "A"),
  List("B", "X", "C", "M", "B", "C")
)

---

Вот пример ввода-вывода

// invocation
sampleInputs.map(l => endIndexOf1Start(l, 0))
sampleInputs.map(l => endIndexOf2Start(l, 0))
sampleInputs.map(l => endIndexOfSomeStart(l, None))
sampleInputs.map(containsTwoStarts)

res0: List[Option[Int]] = List(Some(0), Some(0), Some(4), None)
res1: List[Option[Int]] = List(None, Some(3), Some(2), Some(2))
res2: List[Option[Int]] = List(Some(0), Some(0), Some(4), Some(2))
res3: List[Boolean] = List(true, true, true, true)