Scala solutions are rejected because they exceed compile time limit...


  • 1
    E

    I think I have a quite reasonable 80-line answer to this question in Scala, but it was rejected because the compile time limit is exceeded... Either this limit should be raised, or Scala should not be accepted as a language option. It's otherwise a waste of time.


  • 0

    @entartete Hi, could you please attach your code here so I can troubleshoot the problem? You can also send the code directly to me at support@leetcode.com. Thanks!


  • 0
    E

    Hi @1337c0d3r , thanks for the reply!

    Please find the code attached below. I haven't tested it thoroughly, but it worked on the sample input used in the question when I ran it locally.

    object Solution {
      def main(args: Array[String]): Unit = {
        val result = shoppingOffers(List(2, 5), List(List(3, 0, 5), List(1, 2, 10)), List(3, 2))
        println(result)
      }
    
      def shoppingOffers(price: List[Int], special: List[List[Int]], needs: List[Int]): Int = {
        // for every price, compute the set of remaining needs if we spent that much.
        // for every offer, apply offer to every remaining need set at price-offer.cost
        var costToRemainingNeeds = Map(0 -> Set(needs))
        var reachedZeroNeed = false
    
        var currentCost = 0
        while (!reachedZeroNeed) {
          currentCost += 1
    
          // check every offer and regular price for applicability
          // if we can reach zero need, the current cost is the solution
    
          for ((itemPrice, itemIndex) <- price.zipWithIndex) {
            costToRemainingNeeds.get(currentCost - itemPrice) match {
              case Some(needsSet) => {
                // if regular purchase is applicable, add new remaining needs for this cost
                costToRemainingNeeds +=
                  currentCost -> (costToRemainingNeeds.getOrElse(currentCost, Set()) ++ applyRegularPurchase(needsSet, itemIndex))
              }
              case None => {
                // item cannot be purchased.
              }
            }
          }
    
          for (offer <- special) {
            val offerPrice = offer.last
            val offerItems = offer.take(offer.size - 1)
    
            costToRemainingNeeds.get(currentCost - offerPrice) match {
              case Some(needsSet) => {
                costToRemainingNeeds +=
                  currentCost -> (costToRemainingNeeds.getOrElse(currentCost, Set()) ++ applyOffer(needsSet, offerItems))
              }
              case None => {
                // offer cannot be applied.
              }
            }
          }
    
          costToRemainingNeeds.get(currentCost) match {
            case Some(needsSet) => {
              reachedZeroNeed = needsSet.exists(needs => needs.forall(n => n == 0))
            }
            case None =>
          }
        }
    
        currentCost
      }
    
      def applyRegularPurchase(remainingNeeds: Set[List[Int]], itemIndex: Int): Set[List[Int]] = {
        val matchingNeeds = remainingNeeds.filter(needs => needs(itemIndex) > 0)
        matchingNeeds map (needs => needs.patch(itemIndex, Seq(needs(itemIndex) - 1), 1))
      }
    
      def applyOffer(remainingNeeds: Set[List[Int]], offer: List[Int]): Set[List[Int]] = {
        val matchingNeeds = remainingNeeds.filter(needs => offerApplicable(needs, offer))
        matchingNeeds map (needs => applyOffer(needs, offer))
      }
    
      def offerApplicable(needs: List[Int], offer: List[Int]): Boolean = {
        needs.zip(offer).forall {
          case (needItem, offerItem) => needItem >= offerItem
        }
      }
    
      def applyOffer(needs: List[Int], offer: List[Int]): List[Int] = {
        needs.zip(offer) map {
          case (needItem, offerItem) => needItem - offerItem
        }
      }
    }
    

  • 2
    S

    Hi, I am wondering if there are any updates on this problem? My scala solutions to usual practice problems are being rejected because of time limit issues as well. As a simple example, the following one line solution to the Hamming Distance problem:

    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
    

    computes in 11ms in Java, but 478 ms in Scala.

    Thanks.


  • 0
    K

    Hi there, I'm facing the same issue. Is there any update on this problem?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.