Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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.

(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.)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.