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.

About these ads

Pages: 1 2

10 Responses to “Alien Numbers”

  1. Mithrandir said

    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 base2
    
  2. Rodrigo Menezes said

    C# 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;
    }

  3. Rodrigo Menezes said

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

  4. Rodrigo Menezes said

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

  5. [...] response of my article a scheme solution (and haskel as [...]

  6. Khanh Nguyen said

    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"
    
    
  7. 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.

  8. jneira said

    My clojure generating data structures to meet the adequated functions:

  9. jneira said

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

  10. [...] response of my article a scheme solution (and haskel as [...]

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

Follow

Get every new post delivered to your Inbox.

Join 609 other followers

%d bloggers like this: