You are not logged in.
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.
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.
My Arch Linux Stuff • Forum Etiquette • Community Ethos - Arch is not for everyone
Offline
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
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
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...
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
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
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
You may already be aware of this, but it's an excellent text that moves at a good pace.
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 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
Last edited by karkhaz (2015-05-28 16:31:17)
Offline
skottish wrote:You may already be aware of this, but it's an excellent text that moves at a good pace.
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.
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
@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
My Arch Linux Stuff • Forum Etiquette • Community Ethos - Arch is not for everyone
Offline
@Skottish
Nice code!
Thanks. I really appreciate it.
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