ericnormand/00 Maximum Concatenation.md

## 00 Maximum Concatenation.md

      
    Raw
  

              00 Maximum Concatenation.md
            
          
    Redo: largest concatenation
Folks, two weeks ago, my puzzle was to write a function that returned the largest concatenation of integers. I got lots of answers, which I shared last week. But Val Waeselynck let me in on something: only his worked for this very simple case:
(maxcat [90 9])
The other solutions (including the one I called "exemplary" in the newsletter), return 909, while 990 is clearly bigger.
I have to admit something: I didn't test them thoroughly, either. I always expected you, the puzzle player, to test them yourselves. Wouldn't that make a better exercise? But I think it's too much to ask. Who has the time?
So this week, I'm resurfacing the same largest concatenation problem as before. But this time, I've created a testbed. It's a small project with tests. You fill in the stub function with your implementation and test it. Feel free to read the tests for insights.
Here's the problem again:
Largest integer from concatenation
If I have a list of integers, I can concatenate their base-10 strings to get one large integer. However, if I reorder them, then concatenate them, I could get a larger integer. The task here is to find the largest integer you can create by concatenating a given set of integers.
The testbed can be found here.

  
## Kannan Ramamoorthy.clj
(defn custom-comparator
  "Sorts the given 2 numbers in alphanumerically reverse order.
  ie., each digit will be compared to the corresponding digit(from left) in the
  other number. If all the digits of the least number is equal to the corresponding
  digits in big number, then the least number is considered big.
  Ex, 2>20>200>1>119"
  [num1 num2]
  (loop [str1 (str num1) str2 (str num2)]
    (if (or (empty? str1) (empty? str2))
        (or (if(empty? str1) -1 1))
        (do
          (if-not (= (first str1) (first str2))
            (compare str2 str1)
            (recur (subs str1 1) (subs str2 1)))))))

(defn maxcat
  "Returns the largest integer you can create by concatenating
  the integers in ns."
  [ns]
  (BigInteger. (reduce
                 #(str %1 %2) ; Concatenate the sorted collection
                  "" ; Start reducing with empty string
                 (sort ; sort in custom reverse order
                   custom-comparator
                   ns))))

## Lindsay Davies.clj
(defn shift-add [n e]
  (let [oom (fn [b p]
              (let [b2 (quot b 10)]
                (if (pos? b2)
                  (recur b2 (inc p))
                  p)))]
    (+' (*' n (apply *' (repeat (oom e 1) 10))) e)))

(defn maxcat
  [xs]
  (when (seq xs)
    (->> xs
         (sort #(compare (shift-add %2 %1) (shift-add %1 %2)))
         (reduce shift-add))))

## Mark Champine.clj
(defn maxcat
  "Return largest integer that can be created by concatenating
  a collection of integers v in any order."
  [v]
  (->> v
       (sort
        (fn [x y]
          (compare
           (BigInteger. (str y x)) (BigInteger. (str x y)))))
       (apply str)
       BigInteger.))

## Steve Miner.clj
(defn maxcat
   "Returns the largest BigInt you can create by concatenating
  the non-negative long integers in ns."
  [ns]
  (let [dcompare (fn [a b]
                   (let [c (compare (str b a) (str a b))]
                     (if (zero? c)
                       (compare (count a) (count b))
                       c)))]
    (bigint (apply str (sort dcompare (map str ns))))))

## Valentin Waeselynck.clj
(defn non-negative-integer?
  [i]
  (and
    (integer? i)
    (not (neg? i))))

(defn maxcat [is]
  {:pre [(seqable? is)
         (not (empty? is))
         (every? non-negative-integer? is)]}
  (->> is
    (mapv #(Long/toString % 10))
    (sort (fn compare-base10 [s1 s2]
            (compare
              (BigInteger. (str s2 s1))
              (BigInteger. (str s1 s2)))))
    (apply str)
    (BigInteger.)))
	(defn custom-comparator
	"Sorts the given 2 numbers in alphanumerically reverse order.
	ie., each digit will be compared to the corresponding digit(from left) in the
	other number. If all the digits of the least number is equal to the corresponding
	digits in big number, then the least number is considered big.
	Ex, 2>20>200>1>119"
	[num1 num2]
	(loop [str1 (str num1) str2 (str num2)]
	(if (or (empty? str1) (empty? str2))
	(or (if(empty? str1) -1 1))
	(do
	(if-not (= (first str1) (first str2))
	(compare str2 str1)
	(recur (subs str1 1) (subs str2 1)))))))

	(defn maxcat
	"Returns the largest integer you can create by concatenating
	the integers in ns."
	[ns]
	(BigInteger. (reduce
	#(str %1 %2) ; Concatenate the sorted collection
	"" ; Start reducing with empty string
	(sort ; sort in custom reverse order
	custom-comparator
	ns))))
	(defn shift-add [n e]
	(let [oom (fn [b p]
	(let [b2 (quot b 10)]
	(if (pos? b2)
	(recur b2 (inc p))
	p)))]
	(+' (' n (apply ' (repeat (oom e 1) 10))) e)))

	(defn maxcat
	[xs]
	(when (seq xs)
	(->> xs
	(sort #(compare (shift-add %2 %1) (shift-add %1 %2)))
	(reduce shift-add))))
	(defn maxcat
	"Return largest integer that can be created by concatenating
	a collection of integers v in any order."
	[v]
	(->> v
	(sort
	(fn [x y]
	(compare
	(BigInteger. (str y x)) (BigInteger. (str x y)))))
	(apply str)
	BigInteger.))
	(defn maxcat
	"Returns the largest BigInt you can create by concatenating
	the non-negative long integers in ns."
	[ns]
	(let [dcompare (fn [a b]
	(let [c (compare (str b a) (str a b))]
	(if (zero? c)
	(compare (count a) (count b))
	c)))]
	(bigint (apply str (sort dcompare (map str ns))))))
	(defn non-negative-integer?
	[i]
	(and
	(integer? i)
	(not (neg? i))))

	(defn maxcat [is]
	{:pre [(seqable? is)
	(not (empty? is))
	(every? non-negative-integer? is)]}
	(->> is
	(mapv #(Long/toString % 10))
	(sort (fn compare-base10 [s1 s2]
	(compare
	(BigInteger. (str s2 s1))
	(BigInteger. (str s1 s2)))))
	(apply str)
	(BigInteger.)))