2Max

June 5, 2020

One way to solve this problem is to collect input numbers with similar digit-sums in a hash table, compute the two-maximums of each hash set, and return the maximum. Instead, we solve the problem using the cluster function of a previous exercise and a few auxiliary functions:

(define (2max xs)
  (if ( xs))))
(define (sum-digits n)
  (sum (digits n)))
(define (f x)
  (apply max (map sum (map 2max
    (cluster sum-digits <lt; xs)))))

Here are two examples:

> (f '(51 17 71 42))
93
> (f '(1 2 3 4 5 6))
-1

The pieces are individually small and easy to understand, which makes the whole function equally easy to understand. You can run the program at https://ideone.com/KcT9Ix.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
4 Comments »

4 Responses to “2Max”

  1. Zack said
    June 5, 2020 at 9:26 AM

    Interesting exercise. Here is my take on it using Julia 1.4: https://pastebin.com/uEPBeKBc

    Have a nice weekend!

  2. matthew said
    June 5, 2020 at 9:47 AM

    Scan the array, keeping track of the largest number seen so far for each digit sum:

    def max2(a):
    s = {} # s[n] = largest k seen so far with dsum(k) = n
    max = -1
    for n in a:
        dsum = sum(int(c) for c in str(n))
        if dsum not in s:
            s[dsum] = n # A new digit sum
        else:
            m = s[dsum]
            if max < 0 or m+n > max: max = m+n # Update max
            if n > m: s[dsum] = n # Update s
    return max
  3. Daniel said
    June 5, 2020 at 7:59 PM

    Here’s a not-particularly efficient, not-particularly readable solution in Python.

    def two_max(l):
    p = sorted(((sum(int(c) for c in str(x)), x) for x in l), reverse=True)
    return max((b + d for (a, b), (c, d) in zip(p, p[1:]) if a == c), default=-1)

print(two_max([51, 71, 17, 42]))
print(two_max([1, 2, 3, 4, 5, 6]))

    Output:

    93
-1
  4. Globules said
    June 7, 2020 at 7:27 AM

    Here’s a Haskell version.

    import Data.List (insertBy, unfoldr)
import Data.Map (elems, fromListWith)
import Data.Ord (Down(..), comparing)

max2 :: Integral a => [a] -> a
max2 xs = maximum ((-1) : top2Sums xs)

top2Sums :: Integral a => [a] -> [a]
top2Sums = map sum . filter ((==2) . length) . elems .
              fromListWith (\[n] -> top2 n) . digitSums

top2 :: Ord a => a -> [a] -> [a]
top2 x = take 2 . insertBy (comparing Down) x

digitSums :: Integral a => [a] -> [(a, [a])]
digitSums = map (\x -> (sum (digits x), [x]))

digits :: Integral a => a -> [a]
digits = unfoldr step
  where step 0 = Nothing
        step n = let (q, r) = quotRem n 10 in Just (r, q)

main :: IO ()
main = mapM_ (print . max2) [ []
                            , [0]
                            , [51, 71, 17, 42]
                            , [51, 71, 17, 42, 2223]
                            , [51, 71, 17, 42, 2222]
                            ]

    $ ./max2
-1
-1
93
93
2293

Leave a comment