Hackerrank problem - how to go faster? - Haskell

Welcome to the Functional Programming Zulip Chat Archive. You can join the chat here.

Home#Haskell
Hackerrank problem - how to go faster?
James Sully
2020-09-25 11:50:11

So I'm working on the following hackerrank problem:
https://www.hackerrank.com/challenges/super-digit/problem

I have the following solution:

import Text.Read (readMaybe)
import Data.Semigroup (stimes)

digits :: Integer -> [Integer]
digits n = reverse $ revDigits n
  where
    revDigits n
      | n < 10 = [n]
      | otherwise = (n `mod` 10) : revDigits (n `div` 10)

fromDigits :: [Integer] -> Integer
fromDigits = foldl1 (\x y -> 10*x+y)

digitSum = sum . digits

makeP :: Integer -> Integer -> Integer
makeP n k = read $ stimes k (show n)

readInts :: String -> Maybe [Integer]
readInts = traverse readMaybe . words

superDigit :: Integer -> Integer
superDigit n
  | n < 10 = n
  | otherwise = superDigit $ digitSum n

doIt :: String -> String
doIt input = case readInts input of
  Just [n, k] -> show . superDigit $ makeP n k
  _           -> "invalid input"


interactLn :: (String -> String) -> IO ()
interactLn f = putStrLn . f =<< getLine

main = interactLn doIt

I'm failing some of the tests, but it's with a runtime error. When I tried it with the input from the test on my laptop, it got the correct answer after a few seconds. I think what's happening is that my code is being killed because it's too slow. I profiled with the following:

echo '4757362 10000' | ./superdigit +RTS -p

And got the following profile:

        Fri Sep 25 21:40 2020 Time and Allocation Profiling Report  (Final)

           superdigit +RTS -p -RTS

        total time  =        1.46 secs   (1456 ticks @ 1000 us, 1 processor)
        total alloc = 1,084,500,184 bytes  (excludes profiling overheads)

COST CENTRE      MODULE SRC                         %time %alloc

digits.revDigits Main   superDigit.hs:(7,5)-(9,57)   98.2   96.4
makeP            Main   superDigit.hs:17:1-36         0.9    3.1


                                                                                               individual      inherited
COST CENTRE              MODULE                SRC                          no.     entries  %time %alloc   %time %alloc

MAIN                     MAIN                  <built-in>                    53          0    0.0    0.0   100.0  100.0
 CAF                     Main                  <entire-module>              105          0    0.0    0.0    99.9  100.0
  digitSum               Main                  superDigit.hs:14:1-23        113          1    0.0    0.0     0.0    0.0
  main                   Main                  superDigit.hs:36:1-22        106          1    0.0    0.0    99.9  100.0
   interactLn            Main                  superDigit.hs:34:1-39        107          1    0.1    0.0    99.9  100.0
    doIt                 Main                  superDigit.hs:(28,1)-(30,32) 108          1    0.0    0.0    99.9  100.0
     superDigit          Main                  superDigit.hs:(23,1)-(25,39) 111          3    0.0    0.0    99.0   96.9
      digitSum           Main                  superDigit.hs:14:1-23        114          0    0.8    0.4    99.0   96.9
       digits            Main                  superDigit.hs:(5,1)-(9,57)   115          2    0.0    0.2    98.2   96.5
        digits.revDigits Main                  superDigit.hs:(7,5)-(9,57)   116      70006   98.2   96.4    98.2   96.4
     makeP               Main                  superDigit.hs:17:1-36        112          1    0.9    3.1     0.9    3.1
     readInts            Main                  superDigit.hs:20:1-37        110          0    0.0    0.0     0.0    0.0
  readInts               Main                  superDigit.hs:20:1-37        109          1    0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Handle.FD      <entire-module>              101          0    0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Handle.Text    <entire-module>               99          0    0.1    0.0     0.1    0.0
 CAF                     GHC.IO.Encoding       <entire-module>               91          0    0.0    0.0     0.0    0.0
 CAF                     Text.Read.Lex         <entire-module>               84          0    0.0    0.0     0.0    0.0
 CAF                     GHC.Conc.Signal       <entire-module>               82          0    0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Encoding.Iconv <entire-module>               68          0    0.0    0.0     0.0    0.0

So it seems like the problem is my digits functions is too slow. Any suggestions on speeding it up? Do I need to resort to arrays? I don't even think hackerrank will let me use packages other than base?

Super Digit | HackerRank
Super Digit
TheMatten
2020-09-25 11:55:50

You can try DList instead of plain list to avoid reversing

James Sully
2020-09-25 11:57:56

Wouldn't reverse show up in the profile if that was the problem though? (I'm actually a bit confused about why is doesn't) but it seems like it's spending all the time in the subfunction revDigits, which doesn't do the actual reversing

TheMatten
2020-09-25 12:01:02

Hmm, yeah - I guess it then may be interesting to look at Core to see whether that arithmetics gets unboxed

Torsten Schmits
2020-09-25 12:02:51

you're using foldl1 on a list, which is unsafe.
and I don't understand your solution given the problem. why are you operating on integers instead of strings?

Torsten Schmits
2020-09-25 12:05:19

something along the schematic lines of recurse . show . foldMap digitToInt should be a complete solution

James Sully
2020-09-25 12:05:52

Oh fromDigits is vestigial I think

James Sully
2020-09-25 12:05:59

I'm not using it

James Sully
2020-09-25 12:07:20

What's recurse?

Torsten Schmits
2020-09-25 12:07:52

a placeholder for the name of the function that first checks whether the string length is 1 and contains the expression

James Sully
2020-09-25 12:09:00

foldMap (Sum . digitToInt) ?

James Sully
2020-09-25 12:09:11

oh wait

James Sully
2020-09-25 12:09:14

I'm getting confused

Torsten Schmits
2020-09-25 12:09:18
run [a] = digitToInt a
run as = run (show (foldMap digitToInt as))
Torsten Schmits
2020-09-25 12:09:23

right, Sum

James Sully
2020-09-25 12:11:11

Oh, so you're saying I don't need to do all the converting

Torsten Schmits
2020-09-25 12:11:20

exactly!

James Sully
2020-09-25 12:11:54

That makes sense. Thanks! I'll try that

Torsten Schmits
2020-09-25 12:12:05

(also unsafe btw) :embarrassed:

James Sully
2020-09-25 12:12:19

digitToInt is partial?

Torsten Schmits
2020-09-25 12:12:30

yeah

James Sully
2020-09-25 12:12:45

ah well

James Sully
2020-09-25 12:21:18

Yeah, I passed a couple more cases. Thanks very much for your help! Now gotta debug the next issue haha

Torsten Schmits
2020-09-25 12:21:35

keep 'em coming!

James Sully
2020-09-25 12:21:55

New version, before I look into the next case

import Text.Read (readMaybe)
import Data.Monoid (Sum(..), getSum)
import Data.Semigroup (stimes)
import Data.Char (digitToInt)

makeP :: Integer -> Integer -> String
makeP n k = stimes k (show n)

superDigit :: String -> Int
superDigit [c] = digitToInt c
superDigit n   = superDigit . show . getSum . foldMap (Sum . digitToInt) $ n

readInts :: String -> Maybe [Integer]
readInts = traverse readMaybe . words

doIt :: String -> String
doIt input = case readInts input of
  Just [n, k] -> show . superDigit $ makeP n k
  _           -> "invalid input"

interactLn :: (String -> String) -> IO ()
interactLn f = putStrLn . f =<< getLine

main = interactLn doIt
James Sully
2020-09-25 12:25:29

The issue is still speed, the next input is

7404954009694227446246375747227852213692570890717884174001587537145838723390362624487926131161112710589127423098959327020544003395792482625191721603328307774998124389641069884634086849138515079220750462317357487762780480576640689175346956135668451835480490089962406773267569650663927778867764315211280625033388271518264961090111547480467065229843613873499846390257375933040086863430523668050046930387013897062106309406874425001127890574986610018093859693455518413268914361859000614904461902442822577552997680098389183082654625098817411306985010658756762152160904278169491634807464356130877526392725432086439934006728914411061861235300979536190100734360684054557448454640750198466877185875290011114667186730452681943043971812380628117527172389889545776779555664826488520325234792648448625225364535053605515386730925070072896004645416713682004600636574389040662827182696337187610904694029221880801372864040345567230941110986028568372710970460116491983700312243090679537497139499778923997433720159174153 100000
James Sully
2020-09-25 12:25:43

I actually got a segfault when I tried to profile that

TheMatten
2020-09-25 12:26:04

I guess it's time to switch to text :sweat_smile:

James Sully
2020-09-25 12:27:45

True!

James Sully
2020-09-25 12:28:15

I'm curious why I'd be getting a segfault there. Super strange

Torsten Schmits
2020-09-25 12:28:36

you're parsing this behemoth into an integer!

James Sully
2020-09-25 12:29:04

Ah, of course

James Sully
2020-09-25 12:30:06

Ok, off to mess with it again

James Sully
2020-09-25 12:49:44

Ok, I now have 

import qualified Data.Text as T
import           Data.Text (Text)
import qualified Data.Text.IO as T
import Data.Semigroup (stimes)
import Data.Char (digitToInt)

makeP :: Text -> Integer -> Text
makeP n k = stimes k n

superDigit :: Text -> Int
superDigit n
  | T.length n == 1 = digitToInt $ T.head n
  | otherwise       = superDigit
                    . txtShow
                    . T.foldl (\n c -> n + digitToInt c) 0
                    $ n

doIt :: Text -> Text
doIt input = case T.words input of
  [n, k] -> txtShow . superDigit $ makeP n (txtRead k)
  _      -> T.pack "invalid input"

txtRead :: Read a => Text -> a
txtRead = read . T.unpack

txtShow :: Show a => a -> Text
txtShow = T.pack . show

interactLn :: (Text -> Text) -> IO ()
interactLn f = T.putStrLn . f =<< T.getLine

main = interactLn doIt

Still getting a long wait followed by a segfault

James Sully
2020-09-25 12:50:06

I have a feeling it has to do with Show and Read, although I'm not sure how to avoid them

James Sully
2020-09-25 12:50:12

I guess i'd better profile again

James Sully
2020-09-25 12:55:38

Ah, I think I'm going to have to set up a stack project in order to profile text?

James Sully
2020-09-25 12:55:53

annoying

Torsten Schmits
2020-09-25 12:56:25

what about cabal --enable-library-profiling?

James Sully
2020-09-25 12:57:06

I'm currently just using a single file, will that work for globally installed packages?

Torsten Schmits
2020-09-25 12:57:07

also, use Text.foldl' to avoid laziness

Torsten Schmits
2020-09-25 12:57:29

James Sully said:

I'm currently just using a single file, will that work for globally installed packages?

I guess not

James Sully
2020-09-25 12:57:55

Is that for if I have an existing cabal project?

Torsten Schmits
2020-09-25 12:58:06

yeah, wrong assumption

Torsten Schmits
2020-09-25 12:59:18

btw, are you compiling with -O2?

James Sully
2020-09-25 13:00:43

With the strict fold, It gets the correct answer after a few seconds rather than segfaulting, but still not fast enough for hackerrank

James Sully
2020-09-25 13:01:00

Torsten Schmits said:

btw, are you compiling with -O2?

No, I didn't want to make assumptions about how hackerrank is compiling

James Sully
2020-09-25 13:01:14

I guess it's worth it for experimenting

James Sully
2020-09-25 13:01:52

-O2 Didn't seem to make a huge difference

James Sully
2020-09-25 13:02:21

man this is a heavy duty problem for something labelled "Difficulty: medium"

James Sully
2020-09-25 13:05:15

I'm gonna try profiling with stack

Torsten Schmits
2020-09-25 13:10:04

well if you're going for performance this will only get you so far, since you're operating on boxed Ints. for a bare-metal experience you'll need something like UArray

Torsten Schmits
2020-09-25 13:10:56

no idea if ghc can optimize that away in your current implementation tho

James Sully
2020-09-25 13:14:29
[I] james@SurfaceLaptop ~/D/h/superDigit> cat superDigit-exe.prof                                                                                                                3s 503ms
        Fri Sep 25 23:13 2020 Time and Allocation Profiling Report  (Final)

           superDigit-exe +RTS -N -p -RTS

        total time  =        0.45 secs   (1785 ticks @ 1000 us, 4 processors)
        total alloc = 536,275,952 bytes  (excludes profiling overheads)

COST CENTRE  MODULE SRC                         %time %alloc

superDigit   Main   app/Main.hs:(11,1)-(16,23)   49.7    0.0
makeP        Main   app/Main.hs:8:1-22           34.9  100.0
superDigit.\ Main   app/Main.hs:15:41-56         15.2    0.0


                                                                                                             individual      inherited
COST CENTRE       MODULE                SRC                                               no.     entries  %time %alloc   %time %alloc

MAIN              MAIN                  <built-in>                                        222          0    0.0    0.0   100.0  100.0
 CAF              Data.Text.Array       <entire-module>                                   410          0    0.0    0.0     0.0    0.0
 CAF              Data.Text.Internal.IO <entire-module>                                   399          0    0.0    0.0     0.0    0.0
 CAF              GHC.Conc.Signal       <entire-module>                                   337          0    0.0    0.0     0.0    0.0
 CAF              GHC.IO.Encoding       <entire-module>                                   319          0    0.0    0.0     0.0    0.0
 CAF              GHC.IO.Encoding.Iconv <entire-module>                                   317          0    0.0    0.0     0.0    0.0
 CAF              GHC.IO.Handle.FD      <entire-module>                                   309          0    0.0    0.0     0.0    0.0
 CAF              Text.Read.Lex         <entire-module>                                   270          0    0.0    0.0     0.0    0.0
 CAF              GHC.Event.Thread      <entire-module>                                   263          0    0.0    0.0     0.0    0.0
 CAF              GHC.Event.Poll        <entire-module>                                   240          0    0.1    0.0     0.1    0.0
 CAF:lvl4_r84l    Main                  <no location info>                                441          0    0.0    0.0     0.0    0.0
  main            Main                  app/Main.hs:32:1-22                               451          0    0.0    0.0     0.0    0.0
   interactLn     Main                  app/Main.hs:30:1-43                               452          0    0.0    0.0     0.0    0.0
    doIt          Main                  app/Main.hs:(19,1)-(21,34)                        453          0    0.0    0.0     0.0    0.0
     makeP        Main                  app/Main.hs:8:1-22                                454          0    0.0    0.0     0.0    0.0
 CAF:lvl_r84e     Main                  <no location info>                                438          0    0.0    0.0     0.0    0.0
 CAF:main1        Main                  <no location info>                                442          0    0.0    0.0     0.0    0.0
  main            Main                  app/Main.hs:32:1-22                               444          1    0.0    0.0     0.0    0.0
   interactLn     Main                  app/Main.hs:30:1-43                               445          1    0.0    0.0     0.0    0.0
 main             Main                  app/Main.hs:32:1-22                               446          0    0.0    0.0    99.9  100.0
  interactLn      Main                  app/Main.hs:30:1-43                               447          0    0.1    0.0    99.9  100.0
   doIt           Main                  app/Main.hs:(19,1)-(21,34)                        449          1    0.1    0.0    99.9  100.0
    superDigit    Main                  app/Main.hs:(11,1)-(16,23)                        456          4   49.7    0.0    64.9    0.0
     superDigit.\ Main                  app/Main.hs:15:41-56                              457  100000011   15.2    0.0    15.2    0.0
     txtShow      Main                  app/Main.hs:27:1-23                               458          3    0.0    0.0     0.0    0.0
    makeP         Main                  app/Main.hs:8:1-22                                450          1   34.9  100.0    34.9  100.0
    txtRead       Main                  app/Main.hs:24:1-25                               455          1    0.0    0.0     0.0    0.0
    txtShow       Main                  app/Main.hs:27:1-23                               459          1    0.0    0.0     0.0    0.0
   readTextDevice Data.Text.Internal.IO libraries/text/Data/Text/Internal/IO.hs:133:39-64 448          1    0.0    0.0     0.0    0.0
codygman
2020-09-25 13:14:59

I bet this is just read and show being slow. You can use text-show from hackage, not sure if you can use it on hacker rank

James Sully
2020-09-25 13:16:36

Oh, cool, I'll try that.

James Sully
2020-09-25 13:17:06

Although it doesn't seem like that's the issue in the profile? I'm not super confident in interpreting it

codygman
2020-09-25 13:17:12

Don't forget foldl' and not foldl

James Sully
2020-09-25 13:19:15

I can't imagine the intended solution is Arrays, given the question is under Practice > Functional Programming > Recursion with medium difficulty haha

Torsten Schmits
2020-09-25 13:19:30

right :smile:

codygman
2020-09-25 13:19:51

Profile says makeP is slow, maybe make it's arguments strict with bangpatterns

Torsten Schmits
2020-09-25 13:21:22

try {-# LANGUAGE Strict #-}

codygman
2020-09-25 13:21:23

Data.Text.Strict version of getLine? I think that exists

Torsten Schmits
2020-09-25 13:22:16

also probably helpful to hardcode the input to rule out IO :smile:

James Sully
2020-09-25 13:23:04

Just waiting for text-show to build

James Sully
2020-09-25 13:42:44
{-# LANGUAGE Strict #-}

--{-# LANGUAGE BangPatterns #-}

import qualified Data.Text as T
import           Data.Text (Text)
import qualified Data.Text.IO as T
import Data.Semigroup (stimes)
import Data.Char (digitToInt)
import TextShow

makeP :: Text -> Integer -> Text
makeP n k = stimes k n

superDigit :: Text -> Int
superDigit n
  | T.length n == 1 = digitToInt $ T.head n
  | otherwise       = superDigit
                    . showt
                    . T.foldl' (\n c -> n + digitToInt c) 0
                    $ n

doIt :: Text -> Text
doIt input = case T.words input of
  [n, k] -> showt . superDigit $ makeP n (txtRead k)
  _      -> T.pack "invalid input"

-- only called once for k
txtRead :: Read a => Text -> a
txtRead = read . T.unpack

--txtShow :: Show a => a -> Text
--txtShow = T.pack . show

interactLn :: (Text -> Text) -> IO ()
interactLn f = T.putStrLn . f =<< T.getLine

-- main = interactLn doIt
main = T.putStrLn $ doIt input

input = T.pack "7404954009694227446246375747227852213692570890717884174001587537145838723390362624487926131161112710589127423098959327020544003395792482625191721603328307774998124389641069884634086849138515079220750462317357487762780480576640689175346956135668451835480490089962406773267569650663927778867764315211280625033388271518264961090111547480467065229843613873499846390257375933040086863430523668050046930387013897062106309406874425001127890574986610018093859693455518413268914361859000614904461902442822577552997680098389183082654625098817411306985010658756762152160904278169491634807464356130877526392725432086439934006728914411061861235300979536190100734360684054557448454640750198466877185875290011114667186730452681943043971812380628117527172389889545776779555664826488520325234792648448625225364535053605515386730925070072896004645416713682004600636574389040662827182696337187610904694029221880801372864040345567230941110986028568372710970460116491983700312243090679537497139499778923997433720159174153 100000"
James Sully
2020-09-25 13:43:11

profile:

        Fri Sep 25 23:42 2020 Time and Allocation Profiling Report  (Final)

           superDigit-exe +RTS -N -p -RTS

        total time  =        0.28 secs   (1131 ticks @ 1000 us, 4 processors)
        total alloc = 536,261,176 bytes  (excludes profiling overheads)

COST CENTRE  MODULE SRC                         %time %alloc

superDigit   Main   app/Main.hs:(16,1)-(21,23)   52.0    0.0
makeP        Main   app/Main.hs:13:1-22          34.0  100.0
superDigit.\ Main   app/Main.hs:20:41-56         14.1    0.0


                                                                                                                                   individual      inherited
COST CENTRE                MODULE                                SRC                                            no.     entries  %time %alloc   %time %alloc

MAIN                       MAIN                                  <built-in>                                     353          0    0.0    0.0   100.0  100.0
 CAF                       Data.Text.Internal.Builder.Int.Digits <entire-module>                                530          0    0.0    0.0     0.0    0.0
 CAF                       GHC.Conc.Signal                       <entire-module>                                468          0    0.0    0.0     0.0    0.0
 CAF                       GHC.IO.Encoding                       <entire-module>                                450          0    0.0    0.0     0.0    0.0
 CAF                       GHC.IO.Encoding.Iconv                 <entire-module>                                448          0    0.0    0.0     0.0    0.0
 CAF                       GHC.IO.Handle.FD                      <entire-module>                                440          0    0.0    0.0     0.0    0.0
 CAF                       Text.Read.Lex                         <entire-module>                                401          0    0.0    0.0     0.0    0.0
 CAF                       GHC.Event.Thread                      <entire-module>                                394          0    0.0    0.0     0.0    0.0
 CAF                       GHC.Event.Poll                        <entire-module>                                371          0    0.0    0.0     0.0    0.0
 CAF:$fTextShowInt_$cshowt TextShow.Data.Integral                src/TextShow/Data/Integral.hs:103:10-21        650          0    0.0    0.0     0.0    0.0
  showt                    TextShow.Classes                      src/TextShow/Classes.hs:123:5-23               712          1    0.0    0.0     0.0    0.0
   showtPrec               TextShow.Classes                      src/TextShow/Classes.hs:108:5-41               713          1    0.0    0.0     0.0    0.0
    showtlPrec             TextShow.Classes                      src/TextShow/Classes.hs:149:5-43               716          1    0.0    0.0     0.0    0.0
 CAF:input_r4KV            Main                                  app/Main.hs:41:1-5                             699          0    0.0    0.0     0.0    0.0
  input                    Main                                  app/Main.hs:41:1-1024                          711          1    0.0    0.0     0.0    0.0
 CAF:lvl3_rawP             Main                                  <no location info>                             700          0    0.0    0.0     0.0    0.0
  main                     Main                                  app/Main.hs:39:1-30                            720          0    0.0    0.0     0.0    0.0
   doIt                    Main                                  app/Main.hs:(24,1)-(26,34)                     721          0    0.0    0.0     0.0    0.0
    makeP                  Main                                  app/Main.hs:13:1-22                            722          0    0.0    0.0     0.0    0.0
 CAF:lvl_rawL              Main                                  <no location info>                             698          0    0.0    0.0     0.0    0.0
 CAF:main1                 Main                                  <no location info>                             704          0    0.0    0.0     0.0    0.0
  main                     Main                                  app/Main.hs:39:1-30                            706          1    0.0    0.0     0.0    0.0
 CAF:main2                 Main                                  <no location info>                             703          0    0.0    0.0   100.0  100.0
  main                     Main                                  app/Main.hs:39:1-30                            709          0    0.0    0.0   100.0  100.0
   doIt                    Main                                  app/Main.hs:(24,1)-(26,34)                     710          0    0.0    0.0   100.0  100.0
    superDigit             Main                                  app/Main.hs:(16,1)-(21,23)                     723          4   52.0    0.0    66.0    0.0
     superDigit.\          Main                                  app/Main.hs:20:41-56                           727  100000011   14.1    0.0    14.1    0.0
     showt                 TextShow.Classes                      src/TextShow/Classes.hs:123:5-23               724          0    0.0    0.0     0.0    0.0
      showtPrec            TextShow.Classes                      src/TextShow/Classes.hs:108:5-41               725          0    0.0    0.0     0.0    0.0
       showtlPrec          TextShow.Classes                      src/TextShow/Classes.hs:149:5-43               726          0    0.0    0.0     0.0    0.0
        showbPrec          TextShow.Data.Integral                src/TextShow/Data/Integral.hs:(104,5)-(112,28) 728          3    0.0    0.0     0.0    0.0
         showbPrec.isTrue  TextShow.Data.Integral                src/TextShow/Data/Integral.hs:112:9-28         729          3    0.0    0.0     0.0    0.0
    makeP                  Main                                  app/Main.hs:13:1-22                            719          1   34.0  100.0    34.0  100.0
    txtRead                Main                                  app/Main.hs:30:1-25                            718          1    0.0    0.0     0.0    0.0
    showt                  TextShow.Classes                      src/TextShow/Classes.hs:123:5-23               714          0    0.0    0.0     0.0    0.0
     showtPrec             TextShow.Classes                      src/TextShow/Classes.hs:108:5-41               715          0    0.0    0.0     0.0    0.0
      showtlPrec           TextShow.Classes                      src/TextShow/Classes.hs:149:5-43               717          0    0.0    0.0     0.0    0.0
       showbPrec           TextShow.Data.Integral                src/TextShow/Data/Integral.hs:(104,5)-(112,28) 730          1    0.0    0.0     0.0    0.0
        showbPrec.isTrue   TextShow.Data.Integral                src/TextShow/Data/Integral.hs:112:9-28         731          1    0.0    0.0     0.0    0.0
 main                      Main                                  app/Main.hs:39:1-30                            707          0    0.0    0.0     0.0    0.0
  doIt                     Main                                  app/Main.hs:(24,1)-(26,34)                     708          1    0.0    0.0     0.0    0.0
James Sully
2020-09-25 13:44:25

Unfortunately hackerrank won't let me use text-show

James Sully
2020-09-25 13:45:37

I think I'm done with this one for now, this problem is wack

James Sully
2020-09-25 13:48:24

Oh I spoiled myself and looked at the solution. It's an algorithmic thing, not an optimization thing.

James Sully
2020-09-25 13:48:36

Goddamn hahaha

codygman
2020-09-25 13:49:25

stimes is O(log n) btw, stimesIdempotent is O(1)

codygman
2020-09-25 13:49:56

I like trying to make all of the problems optimization problems to practice benchmarking lol

codygman
2020-09-25 13:50:43

Idk if you can use stimesIdempotent actually

James Sully
2020-09-25 13:52:24

It's just that
digitSum (k repeats of n) == k * digitSum n

James Sully
2020-09-25 13:52:40

this allows you to start the recursion with a much smaller number

James Sully
2020-09-25 14:14:30

final solution:

import Data.Char (digitToInt)

superDigit :: String -> Int
superDigit [d] = digitToInt d
superDigit n = superDigit . show . digitSum $ n

digitSum :: String -> Int
digitSum = sum . map digitToInt

doIt :: String -> String
doIt input = case words input of
  [n, k] -> let initial :: String
                initial = show $ read k * digitSum n
            in  show . superDigit $ initial
  _      -> "invalid input"

interactLn :: (String -> String) -> IO ()
interactLn f = putStrLn . f =<< getLine

main = interactLn doIt
Torsten Schmits
2020-09-25 14:15:13

boooringggg :sweat_smile:

James Sully
2020-09-25 14:15:18

hahaha

James Sully
2020-09-25 14:16:03

At least I learned how to profile

James Sully
2020-09-25 14:16:38

and also not to

James Sully
2020-09-25 14:18:32

They say "don't try to guess what the perf problem is, use profiling". But I had the issue at one higher level up, I guessed that I needed to micro optimize instead of noticing the macro optimization of thinking about the problem differently.

James Sully
2020-09-25 14:23:55

Thanks very much for your help @Torsten Schmits @codygman !

Torsten Schmits
2020-09-25 14:24:15

it was a pleasure!

Powered by Haskell | Questions? Contact srid