some badly written code

Mar 11, 2016  

Heh, didn’t know what else to title this sort of scrapbook/notebook entry. Basically I hadn’t looked at Codewars for a long time, so I went back and tried the next “Kata”.

Problem: Given two integers m, n (1 <= m <= n) we want to find all integers between m and n whose sum of squared divisors is itself a square.

(E.g. 42 has divisors: 1,2,3,6,7,14,21,42, the squares of which are 1,4,9,3649,196,441,1764, and sum to 2500, which is a square)

I wrote my trivial solution, tried it and the submission failed because it timed out. So I hacked away, and uglified my solution, until it was using “memoized” divisors.

I ran it locally and it seemed faster, then I submitted it, and … it timed out again. I gave up, and moved on. I guess the lesson to be learnt is that it’s always easy to code yourself into a corner?

Solution:

module Codewars.G964.Sumdivsq where

import Data.List
import Data.Map as M

intSqrt :: Int -> Int
intSqrt = floor . sqrt . fromIntegral

isSquare :: Int -> Bool
isSquare x = x == (intSqrt x)^2

sumSq :: [Int] -> Int
sumSq list = sum [x^2 | x <- list]

multiply :: Int -> [Int] -> [Int]
multiply factor oldDivlist = factor : oldDivlist ++ (Data.List.map (* factor) oldDivlist)

divisorHelper :: Int -> Int -> Int -> (Map Int [Int]) -> [Int] -> (Map Int [Int], [Int])
divisorHelper n lower upper knownDivs listDivs =
  if lower > upper
  then (M.insert n listDivs knownDivs, listDivs)
  else
    let otherDiv = n `div` lower
    in
      if (n `rem` lower /= 0)
      then
        -- Keep going till we can divide
        divisorHelper n (lower+1) upper knownDivs listDivs
      else
        if otherDiv == lower
        then
          -- Special case: we reach a square divisor
          (M.insert n (lower : listDivs) knownDivs, lower : listDivs)
          -- Ok, we need to know if we've seen the bigger number before
        else case M.lookup otherDiv knownDivs of
          Just oldDivlist ->
            -- We're done!
            let newDivlist = nub $ (lower : listDivs) ++ (multiply lower oldDivlist)
            in
              (M.insert n newDivlist knownDivs, newDivlist)
          Nothing -> divisorHelper n (lower+1) (otherDiv-1) knownDivs (lower : otherDiv : listDivs)


divisors :: Int -> (Map Int [Int]) -> (Map Int [Int], [Int])
divisors n knownDivs = divisorHelper n 1 n knownDivs []

listSquaredHelper :: Int -> Int -> Map Int [Int] -> [(Int, Int)] -> [(Int, Int)]
listSquaredHelper lower upper knownDivs sqList =
  if lower > upper
  then
    sqList
  else
    let (newKnownDivs, divs) = divisors lower knownDivs
        s = sumSq divs
    in
      if isSquare s
      then
        listSquaredHelper (lower+1) upper newKnownDivs  ((lower,s):sqList)
      else
        listSquaredHelper (lower+1) upper newKnownDivs sqList

listSquared :: Int -> Int -> [(Int, Int)]
listSquared m n = reverse $ listSquaredHelper m n M.empty []

I clearly have a long way to go in understanding the “why” of Haskell performance. My initial solution was much, uh … simpler. I didn’t save it but I translated that into Clojure, which looks something like this:

(ns sumdivsq.core)

(defn is-square
  [n]
  (== n (Math/pow (int (Math/sqrt n)) 2)))

(defn sum-sq
  [lst]
  (int (reduce + (map #(Math/pow % 2) lst))))

(defn divisors
  [n]
  (if (== n 1)
    [1]
    (conj (filter #(== 0 (mod n %)) (range 1 (inc (/ n 2)))) n)))

(defn list-squared
  [m n]
  (letfn [(lfh [n]
            (let [ssq (sum-sq (divisors n))]
              (when (is-square ssq)
                [n, ssq])))]
    (keep #(lfh %) (range m n))))

Certainly looks very nice, and it passed all the tests, but I was too impatient to begin optimizing it, and left this one behind too …