2
\$\begingroup\$

In answering this question on Stack Overflow, I decided to stretch my legs in Haskell a bit to see if I could implement a solution to find the count of lucky triples in a list of ints.

A lucky triple is any triple (j, k, l) where j <= k <= l and l `mod` k == 0 && k `mod` j == 0. A correct implementation counts how many unique combinations of elements of an [Int] are valid lucky triples.

import Data.List (sort)

answer :: [Int] -> Int
answer xs = foldr ((+) . foldr ((+) . length) 0) 0 $ twoStepFactors
  where
    twoStepFactors = map mapFactors $ mapFactors $ sort xs

mapFactors :: [Int] -> [[Int]]
mapFactors xs = mapFactors' xs []
mapFactors' [] acc = acc
mapFactors' (x:xs) acc = mapFactors' xs newAcc 
  where
    factors = filter ((==0) . (`mod` x)) xs
    newAcc | null factors = acc
           | otherwise = acc ++ [factors]
\$\endgroup\$
  • \$\begingroup\$ answer could also be sum $ map sum $ map (map length) twoStepFactors but I'm not sure that's better!! \$\endgroup\$ – Adam Smith Jul 6 '17 at 16:58
3
\$\begingroup\$

If mapFactors' is put in a where clause of mapFactors, it isn't globally accessible and you can call it go or something because the scoping already points out it belongs to mapFactors.

Swapping gos argument order lets you say mapFactors = go [].

++ [_] is a smell. Instead of passing down an accumulator and growing it to the right, you can pass it out as the return value and grow it to the left.

mapFactors :: [Int] -> [[Int]]
mapFactors = go where
  go [] = []
  go (x:xs) = newAcc $ go xs where
    factors = filter ((==0) . (`mod` x)) xs
    newAcc | null factors = id
           | otherwise = (:) factors

The filtering can happen after go is done.

mapFactors :: [Int] -> [[Int]]
mapFactors = filter (not . null) . go where
  go [] = []
  go (x:xs) = filter ((==0) . (`mod` x)) xs : go xs

tails helps express go in terms of map:

mapFactors :: [Int] -> [[Int]]
mapFactors = filter (not . null) . map go . tails where
  go [] = []
  go (x:xs) = filter ((==0) . (`mod` x)) xs

Let's use sum from that comment and inline the once-used twoStepFactors (imo if you're only giving a name to explain what something does, use comments)

answer :: [Int] -> Int
answer xs = sum $ map (sum . map length . mapFactors) $ mapFactors $ sort xs

There doesn't seem to be a reason to filter out the []s.

List comprehensions neatly let us skip the empty tail, and get rid of go.

mapFactors :: [Int] -> [[Int]]
mapFactors xss = [filter ((==0) . (`mod` x)) xs | x:xs <- tails xss]
\$\endgroup\$
1
\$\begingroup\$

I'm not seeing the point of sort or mapFactors. The relationship between j and l is just the transitive relationship through k, so the total number of lucky triples is the sum over k of (number of j which work with this k) times (number of l which work with this k). Emphasis on number of: there's no need to generate an [Int] or to count them in any particular order.

\$\endgroup\$
  • \$\begingroup\$ sorting once allows me to find products without searching the entire list, saving me an n^2 run over the list. I'm not sure how to implement the algorithm you outline (and not completely sure I understand what you mean by "sum over k"), but I think you mean to count the factors of each element present in the list, subtract one from that (since k will always be a factor of k), then multiply that by itself less one? I'm not sure that's correct, since it implies that no two factors would be co-prime which is obviously false. \$\endgroup\$ – Adam Smith Jul 7 '17 at 14:46
  • \$\begingroup\$ e.g. in the list [1..6], evaluating 6 would give factors [6, 3, 2, 1]. Applying that algorithm would seem to give 6 pairs: [(3, 1), (2, 1)] which are accurate, but also [(3, 2)] which are co-prime, and all their inverses [(1, 3), (1, 2), (2, 3)] \$\endgroup\$ – Adam Smith Jul 7 '17 at 14:48
  • \$\begingroup\$ It still looks n^2 to me, and in fact I think it has to be: consider the extreme case where all the elements of the list are equal. Python implementation to show what I mean. \$\endgroup\$ – Peter Taylor Jul 7 '17 at 15:29
  • \$\begingroup\$ Your implementation doesn't handle duplicate numbers well. Try answer([1,1,1]) (which should be one, since (1, 1, 1) is itself a lucky triple). Regardless in a sorted list you only need to compare each element of index j with elements of index >j. No element of index <=j can be a valid product (except itself, but that's double-dipping!) \$\endgroup\$ – Adam Smith Jul 7 '17 at 15:36
  • 1
    \$\begingroup\$ Ah, no, I see the problem. I'm also counting some tuples (i, j, i) when L[i] = L[j] \$\endgroup\$ – Peter Taylor Jul 7 '17 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.