Change code to use functional style

Question

I tried to solve a programming contest problem in Scala, but I have a feeling, that it could be done in a more functional way. I compared it with the solution written in imperative style and it is not shorter or less complex at all. Do you have any idea how to "impove" or approach the problem in a more functional way?

Here is my solution:

object Sunshine extends App {

  def tanning(bedNumber:Int, part1 : List[Char], part2: List[Char], inBed: List[Char], tanned:Int, walkedAway: Int) : Int  = {

     val actCustomer =part2.head
     val tanningTuple=(part1.indexOf(actCustomer),inBed.indexOf(actCustomer),bedNumber>inBed.length,part2.tail)

     tanningTuple  match {
      case(_,_,_,Nil)  => walkedAway
        // enter,can be tanned
      case (-1,-1,true,_) =>
        tanning(bedNumber,actCustomer::part1,part2.tail,actCustomer::inBed,tanned,walkedAway)
        // enter, can not be tanned
      case (-1,-1,false,_) =>
        tanning(bedNumber,actCustomer::part1,part2.tail,inBed,tanned,walkedAway)
        //leave, not in bed
      case (x ,-1,_,_) if x>=0 =>
        tanning(bedNumber,actCustomer::part1,part2.tail,inBed,tanned,walkedAway+1)
      //leave, in bed
      case (x,y,_,_) if x>=0 && y>=0 =>
        tanning(bedNumber,actCustomer::part1,part2.tail,inBed-actCustomer,tanned+1,walkedAway)
    }
  }

  println(tanning(2,List(),"ABBAJJKZKZ".toList,List(),0,0))
  println(tanning(3,List(),"GACCBDDBAGEE".toList,List(),0,0))
  println(tanning(3,List(),"GACCBGDDBAEE".toList,List(),0,0))
  println(tanning(1,List(),"ABCBCA".toList,List(),0,0))
}

Answer 1

A good way to think about this problem is to list the different cases when a customer is encountered in the list:

1. The person arrives and there is a bed available => the person gets a tan and the number of available bed decreases by one
2. The person arrives and there is not a bed available => the person won't tan
3. The person leaves and they got a tan => the number of available beds increases by one
4. The person leaves and they didn't get a tan => nothing special happens

When there are no more customers then we need to return the number of people who didn't tan.

This is embodied by the following function:

def step(avail: Int, tanned: Set[Char], not_tanned: Set[Char], customers: List[String]): Int = {
  customers match {
    // case 3 above
    case c::cs if tanned(c) => step(avail+1, tanned, not_tanned, cs)
    // case 4 above
    case c::cs if left(c) => step(avail, tanned, not_tanned, cs)
    // case 1 above
    case c::cs if avail > 0 => step(avail-1, tanned+c, not_tanned, cs)
    // case 2 above
    case c::cs if avail == 0 => step(avail, tanned, not_tanned+c, cs)
    // exit condition, no more customers
    case Nil => not_tanned.size
  }
}

Since the problem statement says that no customer visits more than once and everyone who doesn't get a tan leaves before the people getting tans do it isn't necessary to remove people from the sets or maintain a list of waiting customers in case a bed opens up.

The step function above needs to be called with an initial state which, assuming needs is the number of beds in the salon and customers is the string specified in the problem, is

step(needs, Set(), Set(), customers.toList)

It is possible to transform the step function into a fold which would remove the explicit list traversal, but in my opinion that would hurt the readability of the code.

A complete version of the code is

object tanning {
  def howmanyleft(nbeds: Int, customers: String): Int = {
    def step(avail: Int, tanned: Set[Char], not_tanned: Set[Char], customers: List[Char]): Int = {
      customers match {
        case c::cs if tanned(c) => step(avail+1, tanned, not_tanned, cs)
        case c::cs if not_tanned(c) => step(avail, tanned, not_tanned, cs)
        case c::cs if avail > 0 => step(avail-1, tanned+c, not_tanned, cs)
        case c::cs if avail == 0 => step(avail, tanned, not_tanned+c, cs)
        case Nil => not_tanned.size
      }
    }
    step(nbeds, Set(), Set(), customers.toList)
  }
  def main(args: Array[String]) {
    println(howmanyleft(2, "ABBAJJKZKZ"))
    println(howmanyleft(3, "GACCBDDBAGEE"))
    println(howmanyleft(3, "GACCBGDDBAEE"))
    println(howmanyleft(1, "ABCBCA"))
  }
}

Answer 2

Here is my solution, functional albeit using mutable collections .

import scala.collection.mutable

def tan(numBeds: Int, customersData: Seq[Char]): Int = {
    val currentCustomers = mutable.Set[Char]()
    val walkedAway = mutable.Set[Char]()
    customersData.filter {
        case c if currentCustomers.contains(c) => {
            // this customer is leaving after a tan
            currentCustomers.remove(c)
            false
        }
        case c if walkedAway.contains(c) => {
            // this customer has already walked away
            walkedAway.remove(c)
            false
        }
        case c if currentCustomers.size >= numBeds => {
            // this customer walks away
            walkedAway.add(c)
            true
        }
        case c => {
            // this customer lays for a tan
            currentCustomers.add(c)
            false
        }
    }.size
}