Как лучше решить это упражнение более неизменяемым способом?

Я пытаюсь решить проблему на HackerRank. Я пытаюсь решить эту проблему более функциональным способом (используя неизменность). Я попытался решить, но я не полностью уверен в этом.

Вот ссылка на проблему:

https://www.hackerrank.com/challenges/sock-merchant/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup

Мое изменяемое решение выглядит следующим образом:

/**
  * Mutable solution
  * MSet => mutable set is used
  * val pairs => it is delclared var and getting reassigned
  */

import scala.annotation.tailrec
import scala.collection.mutable.{Set => MSet}

def sockMerchant2(n: Int, ar: Array[Int]): Int = {
  val sockInventory : MSet[Int] = MSet.empty[Int]
  var pairs = 0
  ar.foreach { elem =>
    if(sockInventory.contains(elem)) {
      pairs = pairs + 1
      sockInventory -= elem
    } else sockInventory += elem
  }
  pairs
}

sockMerchant(5, Array(1,2,1,2,4,2,2))

Неизменная версия того же решения:

/**
  * Solution with tail recursion.
  * Immutable Set is used. No variable is getting reassigned
  * How it is getting handled internally ?
  * In each iteration new states are assigned to same variables.
  * @param n
  * @param ar
  * @return
  */

import scala.annotation.tailrec
def sockMerchant(n: Int, ar: Array[Int]): Int = {
  @tailrec
  def loop(arr: Array[Int], counter: Int, sockInventory: Set[Int]): Int ={
    if(arr.isEmpty) counter
    else if(sockInventory.contains(arr.head))
      loop(arr.tail, counter +1, sockInventory-arr.head)
    else loop(arr.tail, counter, sockInventory + arr.head)
  }
  loop(ar, 0, Set.empty)
}

sockMerchant(5, Array(1,2,1,2,4,2,2))

Каков идеальный способ решить эту проблему, учитывая принципы функционального программирования?


immutability scala functional-programming tail-recursion immutable-collections
person Sandio    schedule 14.07.2019    source источник
comment
@jwvh Спасибо за решение. Он проходит все тестовые случаи. Я предполагаю, что Identity относится к ключам сгенерированной карты. Здесь тип данных элемента массива — Int, поэтому домен для ключей будет Int. Правильно ли это понимание?   -  person Sandio    schedule 14.07.2019
comment
Это правильно. identity означает группировать ваши элементы по их значениям. Другими словами, если a == b, то они будут сгруппированы вместе. Подпись типа Array#groupBy — groupBy[K](f: (T) => K): Map[K,Array[T]]. Поскольку ar равно Array[Int], то groupBy(identity) возвращает Map[Int, Array[Int]].   -  person jwvh    schedule 15.07.2019

Ответы (1)


arrow_upward
2
arrow_downward

Первая возможность - использовать сопоставление с образцом:

  def sockMerchant(n: Int, ar: Array[Int]): Int = {
    @tailrec
    def loop(list: List[Int], counter: Int, sockInventory: Set[Int]): Int =
    list match {
      case Nil =>
        counter
      case x::xs if sockInventory.contains(x) =>
        loop(xs, counter +1, sockInventory-x)
      case x::xs =>
        loop(xs, counter, sockInventory + x)
    }
    loop(ar.toList, 0, Set.empty)
  }

Если вы измените Array на List, вы получите хорошее читаемое решение.

Еще более функциональным решением было бы использование folding:

  def sockMerchant(n: Int, ar: Array[Int]): Int = {
    ar.foldLeft((0, Set.empty[Int])){case ((counter, sockInventory), x: Int) =>
      if (sockInventory.contains(x))
        (counter +1, sockInventory-x)
        else
        (counter, sockInventory + x)
    }._1
  }

Это немного сложнее читать/понимать, поэтому, когда я начинал, я предпочитал версию с recursion.

И как показывает jwvh в своем комментарии - если вы не можете сделать это в одну строку с помощью Scala - вы можете что-то упустить ;).

person pme    schedule 14.07.2019
comment
Спасибо за решение. Оба решения работают и проходят все тестовые случаи. - person Sandio; 14.07.2019