Raf's Problem

Another nice problem for testing your programming skills:

Given a String (x) containing only characters a-z, write a function (f)
that returns a base 10 integer, which converts the String as if it were
a base 26 numeral. Function f is bijective**.


Here are some example runs:

x      | f(x)
empty  | 0
a      | 1
b      | 2
z      | 26
aa     | 27
az     | 52
ba     | 53
bz     | 78
aaa    | 703
aaz    | 728
... 
aza    | 1353

Using your preferred programming language, implement function f.

* - it's known as Raf's problem and I saw it on Tony Morris `lambda blog
** - BUG: this function is injective since we can't use `spaces in number to string encoding ***
*** - we can make use of spaces if numeral separator is two-spaced but it is not what was asked - see example for encoding 26 and 27


Following is sample solutions done in Scala / Python / Haskell. Not sure about complexity level but it seems that python isn't shortest language anymore??

Haslell

str2num = foldl (\acc x -> acc * 26 + (ord x - (ord 'a') + 1)) 0

Scala

def str2num(str: String): Int = {
    val base = 26
    val offset = 'a'.toInt -1
    var res = 0
    for (c <- str) {
      val digit = if (c == ' ') 0 else (c.toInt - offset)
      res = res * base + digit
    }
    res
  }

  def num2str(n: Int): String = {
    val base = 26
    val offset = 'a'.toInt -1

    def aux(n: Int): List[Char] = (n / base, n % base) match {
      case (0, 0) => List(' ')
      case (0, r) => List((r + offset).toChar)
      case (q, 0) => 'z' :: aux(q-1)
      case (q, r) => (r + offset).toChar :: aux(q)
    }


    val res = aux(n).reverse.mkString
    if (res == " ") res else res.trim
  }

  test("Raf's Problem"){
    // x   | f(x)
    val tests = Map (
      " "   ->  0,
      "a"   ->  1,
      "b"   ->  2,
      "z"   ->  26,
      "aa"  ->  27,
      "az"  ->  52,
      "ba"  ->  53,
      "bz"  ->  78,
      "aaa" ->  703,
      "aaz" ->  728,
      "aza" ->  1353)
    for (t <- tests) {
      println(t._1 + " -> " + t._2 + " => <" + num2str(t._2) + ">")
      assert(str2num(t._1) == t._2)
      assert(t._1 == num2str(t._2))
    }
  }

Python

import string


def code(number):
    if number>0 and number<27:
        return chr(number+96)

def decode(s):
    if s in string.ascii_lowercase:
        return ord(s)-96


def coding(number):
    if number==0:
        return ""
    s=[]
    while number>0:
        x=number%26
        if x==0:
            x=26
            number=number-26
        y=code(x)    
        t=[y]+s
        s=t
        number=number/26

    return ''.join(s).split()[0]

def decoding(s):
    l=len(s)
    num=0
    for i in s:
        if not i==' ':
            c=decode(i)
            num=num*26+c
    return num

Super python

#!/usr/bin/python
 
from math import pow
from sys import argv

"""Details
16.09.2010
Given a String (x) containing only characters a-z, write a function (f) that returns a base 10 integer, which converts the String as if it were a base 26 numeral. Function f is bijective.

Nicu Marcu
*.*@*-*.com
"""

letters=map(chr, range(97,123))
 
def str2num(text):
 to_str2num=[]
 for l in text:
  index=1
  for ll in letters:
   if l == ll:
    to_str2num.append(index)
   index+=1
 index=0
 result=0
 for l in reversed(to_str2num):
  p = int(pow(26,index))
  result+=l*p
  index+=1
 
 return result
  

def num2str(nr):
 result=[]
 
 a = divmod(int(nr),26)
 rez = a[0]
 rest = a[1]
 
 if rez==0:
  result.append(rest)
  return result
 if rez==1 and rest==0:
  result.append(26)
  return result
 while(1):
  if rest==0:
   result.append(26)
   rez-=1
  else:
   result.append(rest)
  if rez==0:
   return result
  if rez<=26:
   result.append(rez)
   return result
   break
  else:
   a = divmod(rez,26)
   rez = a[0]
   rest = a[1]
 
def main():
 funct = argv[1]
 arg = argv[2]
 if funct=="str2num":
  print str2num(arg)
 if funct=="num2str":
  a = reversed(num2str(arg))
  world=""
  for i in a:
   world+=letters[i-1]
 
  print world
 return 1
main()