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