Of Code and Me

Somewhere to write down all the stuff I'm going to forget and then need

Phone number code puzzle November 4, 2011

Filed under: Coding,Scala — Rupert Bates @ 1:53 pm

Once upon a time I was presented with the following test in an interview:

Given a mapping of digits to an array of characters, ie.
"1"={},
"2"={"A","B","C"},
"3"={"D","E","F"},

etc.

Print out all the string permutations a given input of digits maps to.
So for instance the string “23” should return:
AD
AE
AF
BD
BE
BF
CD
CE
CF

Another way to think of this is a function that returns all the possible combinations of letters the digits could represent if they were keypresses on a standard phone keypad.

I did a pretty bad job at this when I was asked it, partly because it was quite late at night, and partly because it’s not the sort of thing you find yourself doing that often, but today I found myself with a little bit of spare time on my hands and thought I’d give it another go.

I chose to do it in Scala rather than in Java which I had used last time and of course this led to the solution being much more elegant and succinct. If fact this is exactly the sort of problem that demonstrates the value of functional programming.

import collection.immutable.{List, Map}
import java.lang.String

object PhoneNumbers extends App {
  val input = "1234"
  val data = Map(
    0 -> List("0"),
    1 -> List("1"),
    2 -> List("a", "b", "c"),
    3 -> List("d", "e", "f"),
    4 -> List("g", "h", "i"),
    5 -> List("j", "k", "l"),
    6 -> List("m", "n", "o"),
    7 -> List("p", "q", "r", "s"),
    8 -> List("t", "u", "v"),
    9 -> List("w", "x", "y", "z")
  )
  getCombinations(input.substring(0, 1), input.substring(1))
    .foreach(f => Console.println(f))

  def getCombinations(current: String, remaining: String): List[String] = {
    val vals = data(Integer.parseInt(current));
    if (remaining.length() == 0)
      return vals

    val restOfString = getCombinations(remaining.substring(0, 1), remaining.substring(1))

    vals
      .map(f => restOfString.map(f2 => f + f2))
      .flatten
  }
}

Advertisements
 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s