You are not logged in.

#26 2014-08-24 23:14:01

Xyne
Moderator/TU
Registered: 2008-08-03
Posts: 5,793
Website

Re: Interesting numerical problem from Google: post your implementations

karkhaz wrote:

Cheers. I haven't replied for a few days because I'm super-impressed with xyne's solution, and want to devote a few hours to trying to understand it.

smile

I have simplified the code and added comments to make it easier to follow. I had unnecessary conditions and other cruft in there from testing different things.

code

Offline

#27 2014-08-25 13:07:44

skottish
Forum Fellow
From: Here
Registered: 2006-06-16
Posts: 7,932

Re: Interesting numerical problem from Google: post your implementations

This is based on Xyne's idea. I didn't study Xyne's 'slope' code; I decided to implement something on my own. It auto-terminates at 1111111111:

import Data.ByteString.Builder as BB

import Data.Monoid
import System.IO

ones :: Int -> Int
ones n
  | n == 0     = 0 
  | n < 10     = 1
  | digit == 0 = go next 0 1 1
  | otherwise  = go next 1 1 1
  where
    (next, digit) = n `quotRem` 10
    num = n
    go n acc pass tens
      | n == 0    = acc
      | otherwise = go next (acc + result) (pass + 1) (tens * 10)      
      where
        (next, digit) = n `quotRem` 10
        p = pass * tens
        t = 10 * tens
        result
          | digit == 0 = 0
          | digit == 1 = p + num `rem` t + 1
          | otherwise  = p * digit + t

matches :: [BB.Builder]
matches = go 1
  where
    go n
      | n >= 1111111111 = []
      | diff == 0  = BB.intDec n <> BB.char7 '\n' : go (n + 1) 
      | diff <= 10 = go (n + 1)
      | otherwise  = go (n + diff `quot` 10)
      where 
        diff = abs (ones n - n)

main :: IO ()
main = hPutBuilder stdout $ mconcat matches
v6 > time ./v6

..snip..

real	0m0.007s
user	0m0.003s
sys	0m0.003s

Fancy naming convension, yes?

Updated Clojure version implementing the same matches function.

(ns cl2.core
  (:gen-class)
  (:require [clojure.java.io :as io :only (reader)]))

(defn ones
  ([n]
    (cond
      (== n 0) 0
      (< n 10) 1
      (== (rem n 10) 0) (ones (quot n 10) 0 1 1 n)
      :else (ones (quot n 10) 1 1 1 n)))
  ([n' acc' pass' tens' orig-n]
    (loop [n n', acc acc', pass pass', tens tens']
      (let [next-n (quot n 10)
            digit  (rem n 10)
            p      (* pass tens)
            t      (* 10 tens)
            result (cond
                     (== digit 0) 0
                     (== digit 1) (+ p (rem orig-n t) 1)
                     :else (+ (* p digit) t))]
        (if (== n 0)
          acc    
          (recur next-n (+ acc result) (+ pass 1) (* tens 10)))))))

(defn matches
  ([] (matches 1))
  ([n]
    (lazy-seq
      (let [diff (Math/abs (long (- (ones n) n)))]
        (cond
          (== n 1111111111) []
          (== diff 0)  (cons n (matches (+ n 1)))
          (<= diff 10) (matches (+ n 1)) 
          :else (matches (+ n (quot diff 10)))))))) 

(defn -main
  []
  (doseq [out (matches)]
    (println out)))
cl2 > time java -jar target/uberjar/cl2-0.1.0-SNAPSHOT-standalone.jar

...snip...

real	0m0.939s
user	0m1.767s
sys	0m0.093s

*** LAST EDIT ***

General code cleanup and removal of unnecessary notes in this post.

Last edited by skottish (2014-08-28 12:00:31)

Offline

#28 2014-08-26 19:20:29

skottish
Forum Fellow
From: Here
Registered: 2006-06-16
Posts: 7,932

Re: Interesting numerical problem from Google: post your implementations

I believe that I got the algorithm correct this time. Both versions automatically terminate at 1111111111. I'm not as fast as Xyne, but as long as I'm right behind him, then I'm pretty damn happy. See the previous post.

By the way, what are all of you using to do your plotting?

**EDIT**

I let the Haskell version terminate at the same place that Xyne's code terminates and the run time basically didn't change.

Last edited by skottish (2014-08-26 20:48:02)

Offline

#29 2014-08-26 21:49:48

karkhaz
Member
Registered: 2014-01-25
Posts: 77

Re: Interesting numerical problem from Google: post your implementations

skottish wrote:

I believe that I got the algorithm correct this time. Both versions automatically terminate at 1111111111. I'm not as fast as Xyne, but as long as I'm right behind him, then I'm pretty damn happy. See the previous post.

The code looks really nice. This is going to be helpful in my iminent studies of haskell...

skottish wrote:

By the way, what are all of you using to do your plotting?

You mean for run times? I just use time, as you do. If you meant for the graph in the first post, I used gnuplot.

Offline

#30 2014-08-26 22:06:52

skottish
Forum Fellow
From: Here
Registered: 2006-06-16
Posts: 7,932

Re: Interesting numerical problem from Google: post your implementations

karkhaz wrote:

The code looks really nice. This is going to be helpful in my iminent studies of haskell...

Thanks. I'm still haven't touched the more advanced topics yet, but will get back to that soon.

You may already be aware of this, but it's an excellent text that moves at a good pace.

http://learnyouahaskell.com/chapters

karkhaz wrote:
skottish wrote:

By the way, what are all of you using to do your plotting?

You mean for run times? I just use time, as you do. If you meant for the graph in the first post, I used gnuplot.

The graph was what I was referring to. I'll have to play around with it some. I'd rather prefer a smaller package like that than to dig into a larger mathematics system.

Last edited by skottish (2014-08-26 22:22:12)

Offline

#31 2014-08-27 00:04:36

karkhaz
Member
Registered: 2014-01-25
Posts: 77

Re: Interesting numerical problem from Google: post your implementations

skottish wrote:

You may already be aware of this, but it's an excellent text that moves at a good pace.

http://learnyouahaskell.com/chapters

Thanks, a cursory skim through this looks good. (And I don't think I've ever encountered a programming book with such cute illustrations...) I've been mainly messing around on the interactive toplevel with no guidance thus far, so I'll probably use this when it's time to get more serious.

skottish wrote:

The graph was what I was referring to. I'll have to play around with it some. I'd rather prefer a smaller package like that than to dig into a larger mathematics system.

Yes. The language is rather large, but it's no larger than what it needs to be given how flexible it is. The ability to generate graphs non-interactively from text files is a big win for me, no need to press lots of pretty buttons like in Mathmatica or whatever.

If you're interested:

graph.gnu

set xlabel "n"
set ylabel "f(n)"
set logscale x
set logscale y
set terminal png
set output 'graph.png'
plot "graph.dat" notitle, "fx.dat" notitle with linespoints

In graph.dat, have a list of x and f(x) in two columns:

1 1
2 1
...
10 2
11 4
...

And in fx.dat, have

1 1
100000000 100000000

(just two datapoints, since we are drawing a line between them).

Then, running gnuplot graph.gnu will give you
DluqA.png

Last edited by karkhaz (2015-05-28 16:31:17)

Offline

#32 2014-08-27 00:14:35

skottish
Forum Fellow
From: Here
Registered: 2006-06-16
Posts: 7,932

Re: Interesting numerical problem from Google: post your implementations

karkhaz wrote:
skottish wrote:

You may already be aware of this, but it's an excellent text that moves at a good pace.

http://learnyouahaskell.com/chapters

Thanks, a cursory skim through this looks good. (And I don't think I've ever encountered a programming book with such cute illustrations...) I've been mainly messing around on the interactive toplevel with no guidance thus far, so I'll probably use this when it's time to get more serious.

The strictness can be, well, challenging. But, it's actually a really cool language to work with. It'll take a little time to get used to the error messages, but once you start to get a feel for them, it's generally very easy to figure out what went wrong. One of the big upshots to Haskell is that if your code compiles, it will run. It may not do exactly what you want it to, but it will run.

karkhaz wrote:
skottish wrote:

The graph was what I was referring to. I'll have to play around with it some. I'd rather prefer a smaller package like that than to dig into a larger mathematics system.

Yes. The language is rather large, but it's no larger than what it needs to be given how flexible it is. The ability to generate graphs non-interactively from text files is a big win for me, no need to press lots of pretty buttons like in Mathmatica or whatever.

Thanks a million for this. It's all that I needed to see to be convinced that it's a tool that I want to have around.

Offline

#33 2014-08-27 22:34:08

Xyne
Moderator/TU
Registered: 2008-08-03
Posts: 5,793
Website

Re: Interesting numerical problem from Google: post your implementations

@Skottish
Nice code!

You can shave off a little time using the same trick that you used in the other thread:

...
import Data.ByteString.Builder as BB
import Data.Monoid
import System.IO

...

builder :: [Int] -> BB.Builder
builder [] = mempty
builder (x:xs) = BB.intDec x <> BB.char7 '\n' <> builder xs

main :: IO ()
main = hPutBuilder stdout $ builder matches

Offline

#34 2014-08-28 02:42:11

skottish
Forum Fellow
From: Here
Registered: 2006-06-16
Posts: 7,932

Re: Interesting numerical problem from Google: post your implementations

Xyne wrote:

@Skottish
Nice code!

Thanks. I really appreciate it.

Xyne wrote:

You can shave off a little time using the same trick that you used in the other thread:

...snip...

I tried another variation on this theme before, and it actually slowed me down. I'm curious if the way that you did this here will get me any faster in the *cough* not-quite-dead other thread. I'm only 0.9 seconds behind you for my smaller data set. Around two for the larger...

I implemented both my Haskell and Clojure versions using arbitrary length intergers with this new version. With your chages to the Haskell code and stopping at 11111111111111111111111111111111111111111111111111, I'm at 0.023 seconds. Not so bad now. The Clojure version was mostly unaffected because most of the .9xx seconds is the JVM starting up.

*** EDIT ***

In case anyone is interested, this is what the totals of the absolute value of the differences between f(n) and n over the set of 1..1111111111 breaks down to. It's easy to see why Xyne's idea works so well:

>= 50000            -> 1108456134
>= 40000 && < 50000 -> 550012
>= 30000 && < 40000 -> 428501
>= 20000 && < 30000 -> 557914
>= 10000 && < 20000 -> 448427
>= 5000  && < 10000 -> 265994
>= 1000  && < 5000  -> 338169
>= 500   && < 1000  -> 30404
>= 100   && < 500   -> 28335
            < 100   -> 7221

And, if anyone is interested to see how I came to my conclusion that my version would work, this is what happens from 1111111000..1111111110. As you can see, the "jump" values that I used always end up getting within 10. If it were possible that there were values above this, this would still be valid:

    n           ones      diff jump
1111111000   1111110307   693   69
1111111001   1111110315   686   68
1111111002   1111110322   680   68
1111111003   1111110329   674   67
1111111004   1111110336   668   66
1111111005   1111110343   662   66
1111111006   1111110350   656   65
1111111007   1111110357   650   65
1111111008   1111110364   644   64
1111111009   1111110371   638   63
1111111010   1111110379   631   63
1111111011   1111110388   623   62
1111111012   1111110396   616   61
1111111013   1111110404   609   60
1111111014   1111110412   602   60
1111111015   1111110420   595   59
1111111016   1111110428   588   58
1111111017   1111110436   581   58
1111111018   1111110444   574   57
1111111019   1111110452   567   56
1111111020   1111110459   561   56
1111111021   1111110467   554   55
1111111022   1111110474   548   54
1111111023   1111110481   542   54
1111111024   1111110488   536   53
1111111025   1111110495   530   53
1111111026   1111110502   524   52
1111111027   1111110509   518   51
1111111028   1111110516   512   51
1111111029   1111110523   506   50
1111111030   1111110530   500   50
1111111031   1111110538   493   49
1111111032   1111110545   487   48
1111111033   1111110552   481   48
1111111034   1111110559   475   47
1111111035   1111110566   469   46
1111111036   1111110573   463   46
1111111037   1111110580   457   45
1111111038   1111110587   451   45
1111111039   1111110594   445   44
1111111040   1111110601   439   43
1111111041   1111110609   432   43
1111111042   1111110616   426   42
1111111043   1111110623   420   42
1111111044   1111110630   414   41
1111111045   1111110637   408   40
1111111046   1111110644   402   40
1111111047   1111110651   396   39
1111111048   1111110658   390   39
1111111049   1111110665   384   38
1111111050   1111110672   378   37
1111111051   1111110680   371   37
1111111052   1111110687   365   36
1111111053   1111110694   359   35
1111111054   1111110701   353   35
1111111055   1111110708   347   34
1111111056   1111110715   341   34
1111111057   1111110722   335   33
1111111058   1111110729   329   32
1111111059   1111110736   323   32
1111111060   1111110743   317   31
1111111061   1111110751   310   31
1111111062   1111110758   304   30
1111111063   1111110765   298   29
1111111064   1111110772   292   29
1111111065   1111110779   286   28
1111111066   1111110786   280   28
1111111067   1111110793   274   27
1111111068   1111110800   268   26
1111111069   1111110807   262   26
1111111070   1111110814   256   25
1111111071   1111110822   249   24
1111111072   1111110829   243   24
1111111073   1111110836   237   23
1111111074   1111110843   231   23
1111111075   1111110850   225   22
1111111076   1111110857   219   21
1111111077   1111110864   213   21
1111111078   1111110871   207   20
1111111079   1111110878   201   20
1111111080   1111110885   195   19
1111111081   1111110893   188   18
1111111082   1111110900   182   18
1111111083   1111110907   176   17
1111111084   1111110914   170   17
1111111085   1111110921   164   16
1111111086   1111110928   158   15
1111111087   1111110935   152   15
1111111088   1111110942   146   14
1111111089   1111110949   140   14
1111111090   1111110956   134   13
1111111091   1111110964   127   12
1111111092   1111110971   121   12
1111111093   1111110978   115   11
1111111094   1111110985   109   10
1111111095   1111110992   103   10
1111111096   1111110999    97    9
1111111097   1111111006    91    9
1111111098   1111111013    85    8
1111111099   1111111020    79    7
1111111100   1111111028    72    7
1111111101   1111111037    64    6
1111111102   1111111045    57    5
1111111103   1111111053    50    5
1111111104   1111111061    43    4
1111111105   1111111069    36    3
1111111106   1111111077    29    2
1111111107   1111111085    22    2
1111111108   1111111093    15    1
1111111109   1111111101     8    0
1111111110   1111111110     0    0

Last edited by skottish (2014-08-28 03:12:42)

Offline

Board footer

Powered by FluxBB