alien-nums.clj

(ns alien-nums
  (:require (clojure.contrib [combinatorics :as comb :only cartesian-product]
			     [seq-utils :as seq-utils :only indexed])))

(defn leading-zero? [lang num] 
  (= (first num) (first lang)))
  
(defn generate-nums [lang]
  (when-let [lst (map list lang)]
    (let [fcp #(map flatten
		   (comb/cartesian-product lst %1))]
      (remove #(leading-zero? lang %)
	      (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]
  (and (every? (set lang) num)
       (not (leading-zero? 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)))))

Hi jneira,

one thing that I wondered is how to implement smart memoization in a solution such as yours and mine. The only thing that requires memoization is the radix and the index of the number in each language's radix, not the actual symbols (in this case characters) of the language.

I think this would be a nice next step for the improvement of both our algorithms. What do you think?

Luis Sergio Oliveira

I have to think deeply in your recursive solution which is more efficient (nearly constant time!), mine is horribly slow, at least O(n) cause it walk (with some and nth) each seq of nums until reach the solution . I'll try to combine them is some way