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


  • 3
    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
        }
      }
    }
    

  • 4
    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?


  • 0
    G

    I have the same problem too. For the first problem which is Two Sum problem. This is my code snippet. It runs in 6ms in my IDE

    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        nums.zipWithIndex.toList.combinations(2).find(i => i.map(_._1).sum == target).get
        .map(_._2).toArray
    }
    

  • 0
    R

    I had the same issue on the string reversal question.


  • 1
    R

    The problem with Scala submissions persists...
    Tried submitting 557. Reverse words in string III, but always exceeds time limit.
    Same approach in java and python works no problem.
    Must conclude that Scala code functionality is broken, unusable.


  • 0

    Hi, we have increased Scala's time limit for both compile and run code. I believe this should resolve most issues you're having. Please let me know if you still see issues, and I'll fix it. Thanks.


  • 0
    K

    @1337c0d3r I'm still getting TLE for simple scala code. Here is my two sum solution, which is almost the same as the one posted earlier. It also gets TLE.

    object Solution {
      def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        nums.combinations(2).find(_.sum == target).get.map(nums.indexOf)
      }
    }
    

    Is it possible to ignore time limits or to further raise them? I would be ok with my solution not being considered "accepted", but I'd like to know if my outputs are correct.

    Immutable / functional code is sometimes an order of magnitude slower than its mutable counterpart (estimation I've heard thrown around), but it's the style of programming that is used for my line of work. Scala compile times are also known to be pretty poor unfortunately.


Log in to reply
 

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