{{ message }}

Instantly share code, notes, and snippets.

# ericnormand/00 Maximum Concatenation.md

Last active Jun 2, 2019

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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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.))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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))))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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.)))