Alien Numbers
September 24, 2010
This task is very similar to the digits and undigits functions in the Standard Prelude. We will convert input from alien digit-strings to decimal numbers using the source language, then convert back to alien digit-strings for output using the target language. Here are alien->number and its helper function char->digit, which is curried for convenient use by map:
(define (char->digit lang)
(lambda (c)
(let loop ((lang lang) (d 0))
(if (char=? (car lang) c) d
(loop (cdr lang) (+ d 1))))))
(define (alien->number lang str)
(let* ((lang (string->list lang))
(radix (length lang))
(str (string->list str)))
(undigits (map (char->digit lang) str) radix)))
And here is the translation back:
(define (digit->char lang)
(lambda (d)
(list-ref lang d)))
(define (number->alien lang n)
(let* ((lang (string->list lang))
(radix (length lang))
(num (digits n radix)))
(list->string (map (digit->char lang) num))))
Translate takes an alien digit-string, a source language, and a target language, and perform the conversion from one to the other. Here is translate with some examples showing its use; note the hex-to-binary conversion in the third example:
(define (translate alien source target)
(number->alien target (alien->number source alien)))
> (translate "9" "0123456789" "oF8") ; (9*10^0 = 9)
Foo
> (translate "Foo" "oF8" "0123456789") ; (1*3^2 + 0*3^1 + 0*3^0 = 9)
9
> (translate "13" "0123456789abcdef" "01") ; (1*16^1 + 3*16^0 = 19)
10011
> (translate "CODE" "O!CDE?" "A?JM!.") ; (2*6^3 + 0*6^2 + 3*6^1 + 4*6^0 = 454)
JAM!
Finally we process a file, fetching the input using read-word from the Mark V. Shaney exercise:
(define (do-file filename)
(with-input-from-file filename
(lambda ()
(let ((n (string->number (read-word))))
(do ((i 1 (+ i 1))) ((< n i))
(let ((alien (read-word))
(source (read-word))
(target (read-word)))
(display "Case #")
(display i)
(display ": ")
(display (translate alien source target)))
(newline))))))
We used digits and undigits from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/GPar0q3v.
Simple solution in haskell:
alien number base1 base2 = map (fst . (b2 !!)) $ reverse $ undigits base10 l2 where undigits 0 _ = [] undigits n b = (n `mod` b) : undigits (n `div` b) b base10 = foldl ((+) . (* l1)) 0 digits digits = map (\c -> find c b1) number find c (x:xs) = if fst x == c then snd x else find c xs b1 = zip base1 [0..] b2 = zip base2 [0..] l1 = length base1 l2 = length base2C# Solution
public static string sourceToDestination(string alianNumber, string sourceLanguage, string destinationLanguage)
{
int decimalValue = 0;
int product = 1;
int sourceRadix = sourceLanguage.Length;
int destinationRadix = destinationLanguage.Length;
string newNumber = “”;
for (int i = alianNumber.Length – 1; i >= 0; i–, product = product * sourceRadix)
{
char numb = alianNumber[i];
int alianValue = -1;
for (int j = 0; j 0; decimalValue = decimalValue / destinationRadix)
{
newNumber = destinationLanguage[decimalValue % destinationRadix] + newNumber;
}
return newNumber;
}
C# again copy paste does not like me
public static string sourceToDestination(string alianNumber, string sourceLanguage, string destinationLanguage)
{
int decimalValue = 0;
int product = 1;
int sourceRadix = sourceLanguage.Length;
int destinationRadix = destinationLanguage.Length;
string newNumber = "";
for (int i = alianNumber.Length - 1; i >= 0; i--, product = product * sourceRadix)
{
char numb = alianNumber[i];
int alianValue = -1;
for (int j = 0; j 0; decimalValue = decimalValue / destinationRadix)
{
newNumber = destinationLanguage[decimalValue % destinationRadix] + newNumber;
}
return newNumber;
}
Actually wordpress doesn’t like me.
Hope it works this time and that someone can delete the failed attempts.
public static string sourceToDestination(string alianNumber, string sourceLanguage, string destinationLanguage)
{
int decimalValue = 0;
int product = 1;
int sourceRadix = sourceLanguage.Length;
int destinationRadix = destinationLanguage.Length;
string newNumber = "";
for (int i = alianNumber.Length – 1; i >= 0; i–, product = product * sourceRadix)
{
char numb = alianNumber[i];
int alianValue = -1;
for (int j = 0; j <= sourceLanguage.Length – 1; j++)
{
if (sourceLanguage[j] == numb)
{
alianValue = j;
break;
}
}
decimalValue += (alianValue * product);
}
for (; decimalValue > 0; decimalValue = decimalValue / destinationRadix)
{
newNumber = destinationLanguage[decimalValue % destinationRadix] + newNumber;
}
return newNumber;
}
[…] response of my article a scheme solution (and haskel as […]
Mine in F#
let human_numeric_value (n:string) (number_system:string) = let pos = List.ofSeq n |> List.map (fun (c:char) -> number_system.IndexOf(c)) |> List.rev let mutable v = 0 for i in [0..pos.Length - 1] do v <- v + pos.[i] * (pown number_system.Length i) v let rec convert (n:int) (power_base:int) = if (n / power_base < 1) then [n] else (n % power_base) :: (convert (n / power_base) power_base) let alien_number (n:string) (src_system:string) (dst_system:string) = let tmp = convert (human_numeric_value n src_system) (dst_system.Length) |> List.rev let ret = List.map (fun x -> dst_system.[x]) tmp System.String.Concat(Array.ofList(ret)) alien_number "9" "0123456789" "oF8" alien_number "Foo" "oF8" "0123456789" alien_number "13" "0123456789abcdef" "01"Here is mine in Clojure:
(defn decimal-to-lang "Converts decimal-num to the equivalent number in lang as a string. The algorithm was a translation of the algorithm by Rodrigo Menezes in C# that he posted in the programming praxis site." [decimal-num lang] (let [lang-radix (count lang)] (loop [decimal-value decimal-num lang-num []] (if (>= 0 decimal-value) (apply str lang-num) (recur (int (/ decimal-value lang-radix)) (concat [(nth lang (mod decimal-value lang-radix))] lang-num)))))) (defn digit-index [digit lang] (loop [i 0] (if (= digit (nth lang i)) i (recur (inc i))))) (defn lang-to-decimal [alien-num lang] (let [radix (count lang) ralien-num (reverse alien-num)] (loop [i 0 decimal-num 0 product 1] (if (= i (count ralien-num)) decimal-num (recur (inc i) (+ decimal-num (* (digit-index (nth ralien-num i) lang) product)) (* radix product)))))) (defn convert-num "Convert alien-num which is in source-lang into the same number in target-lang" [alien-num source-lang target-lang] (decimal-to-lang (lang-to-decimal alien-num source-lang) target-lang))The full solution with tests is here.
My clojure generating data structures to meet the adequated functions:
oops
(ns alien-nums
(:require (clojure.contrib [combinatorics :as comb :only cartesian-product]
[seq-utils :as seq-utils :only indexed])))
(defn generate-nums [lang]
(when-let [lst (seq lang)]
(let [leading-zero? #(= (first %) (first lang))
fcp #(remove leading-zero?
(map flatten
(comb/cartesian-product lst %1)))]
(apply concat (iterate fcp lst)))))
(defn get-index [nums num]
(first (some #(when (= (second %) (seq num)) %)
(seq-utils/indexed nums))))
(defn valid-num [lang num]
(every? (set lang) num))
(defn convert-num [alien-num from-lang to-lang]
(let [[from-nums to-nums]
(map generate-nums [from-lang to-lang])
idx (when (valid-num from-lang alien-num)
(get-index from-nums alien-num))]
(when idx (apply str (nth to-nums idx)))))
[…] response of my article a scheme solution (and haskel as […]