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))
}

• Brian: In Scala, pattern matching is eager so the first pattern that is matched wins. It is generally a good practice to order pattern matches from most specific to least specific. Your pattern matches include a lot of wildcards. I'd suggest limiting the wildcards and trying place the pattern with more wildcards towards the end.

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
}

• kiritsuku: filter {_ match {case ...}} can be written as filter {case ...}