Fork me on GitHub
#beginners
<
2019-03-27
>
thomas74501:03:24

Hi, so I feel like I’m going crazy. I’m relatively new to Clojure (been using it on and off for a month or so) and I’m going through problems on 4Clojure. I’m on question 95 (http://www.4clojure.com/problem/95) and I’ve been wrestling with it for a few hours now and have absolutely no idea why it’s not passing the unit tests. I can’t see how it’s logically different from an answer I found online (the answer-key version is far more elegant, that’s for sure). Can somebody lend me a second pair of eyes? What am I doing wrong? My version:

(fn tree? [tree]
    (if (= tree nil)
    true)
    (if (seq? tree)
    (if (= (count tree) 3)
        (if (and (tree? (second tree)) (tree? (last tree)))
        true
        false)
        false)
    false))
The answer key (https://gist.github.com/SegFaultAX/3607101 )’s version:
(fn tree? [coll]
    (cond
    (or (seq? coll) (vector? coll))
        (and (= 3 (count coll)) (tree? (nth coll 1)) (tree? (nth coll 2)))
    (nil? coll) true
    :else false))

codonnell01:03:06

Here's a properly indented version of your solution. Might help:

(fn tree? [tree]
  (if (= tree nil)
    true)
  (if (seq? tree)
    (if (= (count tree) 3)
      (if (and (tree? (second tree)) (tree? (last tree)))
        true
        false)
      false)
    false))

nathantech200501:03:16

I thought defn was used to define a function? Is fn a defined function?

nathantech200501:03:38

I cannot tell what fn is because I wouldn't name a function fn.

codonnell01:03:21

It's a named anonymous function; the name is scoped to the function body. You can use them for recursion, and they also can make stacktraces a little bit easier to read.

nathantech200501:03:48

Ahh ok. Its a lambda. fn is a reserved keyword for a lambda?

nathantech200501:03:40

What does the unit test fail on?

nathantech200501:03:48

The code should return true or false

nathantech200501:03:50

I have to be honest. Its difficult to line up the parans... can you use a cond ?

mattmorten01:03:10

Examine your first (if expression

nathantech200501:03:05

Why is it returning true if tree? Is nil

nathantech200501:03:57

Shouldnt it return false if tree? Is nil

codonnell01:03:53

I think nil is intended to represent an empty tree.

thomas74501:03:36

Yeah, if you look at the problem I linked, nil denotes a “leaf” of the tree.

thomas74501:03:46

@ Thanks, I’ll look at it

thomas74501:03:13

@ I don’t see what’s wrong with it. Do if statement have to have two branches or something?

thomas74502:03:09

It doesn’t seem that’s the case

mattmorten02:03:28

You are correct, but that isn't quite the point

mattmorten02:03:02

Zoom out, and look at the fn as a whole

mattmorten02:03:16

(fn tree? [tree]
   (an-expression)
   (another-expression)
   (and-another-expression) <-- this will be returned
)

mattmorten02:03:05

(fn tree? [tree]
  (if (= tree nil)
    true) <--- this will never be returned
  (if (seq? tree)
   .... <snip>

mattmorten02:03:17

My suggestion is you at least make the (if (seq? tree) expression the "else"

mattmorten02:03:42

(fn tree? [tree]
  (if (= tree nil)
    true
    (if (seq? tree)

mattmorten02:03:43

This is merely an initial suggestion. There are many other ways to clean up this code

vale03:03:18

you'd have to nest the following ifs into the first's else branch

thomas74503:03:07

@ Ohhhhh. Damn, I didn’t know Clojure only returns on the last expression. Thanks!

eric98613:04:16

I just tried that question and noticed that seq? doesn't work for vectors, only lists, whereas sequential? works for both.

eric98613:04:44

If your code failed on the third test that could be it.

eric98613:04:22

Here's my solution if it's any help...

eric98613:04:26

(fn istree [atree]
  (or
   (nil? atree)
   (and (sequential? atree) (= 3 (count atree))
    	(not (nil? (first atree)))
       	(istree (second atree))
        (istree (nth atree 2))
   )
))

nathantech200501:03:23

Is anyone using vim with emacs? Evil mode. On OSX. Wiii. I got it to work. Just had to restart emacs.

tabidots04:03:39

Is there a limit to lazy sequences? I am trying to solve Project Euler #357, which basically requires generating primes up to 100 million. The general prime? filter I'd cooked up (more or less memoized trial division) is too slow for this particular problem, so I borrowed a lazy-sequence solution from someone on SO:

(def lazy-primes
 ;; Adapted from 
 (letfn [(no-smaller-prime-factors? [x]
           (not-any? (fn [p] (divisible? x p))
                     (take-while #(<= % (Math/sqrt x)) lazy-primes)))]
   (lazy-seq (filter no-smaller-prime-factors? (drop 2 (range))))))
There is nothing wrong with my algorithm to solve the problem (as I've tested it on smaller limits), but I kept getting the wrong answer. Finally, after banging my head against the wall tons of times, I finally realized that the lazy sequence craps out somewhere between 1 and 10 million such that counting the items in the sequence above some n does not yield a higher count. Lo and behold, (nth lazy-primes 800000) gives me
Execution error (IndexOutOfBoundsException) at scratch.euler2/eval48451 (form-init5213815999557406566.clj:1).
null
Can anyone shed some light on this? And how I might work around it?

zugnush04:03:25

I noticed that the error is an Index out of bounds, which I guess is coming from the nth. (last (take 800000 lazy-primes)) worked for me, don't know why nth is limited though

nathantech200504:03:02

It is not running the function? Crashes on line 1?

tabidots04:03:08

@nathantech2005 re: long limit—I didn't think of that! I thought "oh, I'm just finding square roots, there's no need to coerce to bigint (or place to do so)." Interestingly, I was able to get around the Out of Bounds error by changing Math/sqrt x to tower/expt x 1/2, but finding the 800,000th prime seems like it will take all afternoon. re: function crashing—I'm just running it in the REPL. No crash at 700,000 or below.

nathantech200504:03:09

What is the highest max value possible in your code?

nathantech200504:03:26

800,000th prime # is?

nathantech200504:03:40

Over the 64 bit long maximum?

tabidots04:03:22

I cannot get a value higher than 8325781, which is far less than the 800,000th prime.

tabidots04:03:53

Seems to be around the 560,000th prime or so.

nathantech200504:03:15

Hmm.. index error is not a stack error though. I dont think its a 64 long max problem

zugnush04:03:17

i don't think it's an overflow

(last (take  800000 lazy-primes ))
;; => 12195257

lilactown04:03:51

yeah I’m also able to run the code

nathantech200504:03:56

Ya, you'd get an explicit overflow error. I just checked my fibonacci code.

lilactown04:03:41

user=> (defn divisible? [i p] (zero? (rem i p)))
#'user/divisible?
user=> (def lazy-primes
  #_=>  ;; Adapted from 
  #_=>  (letfn [(no-smaller-prime-factors? [x]
  #_=>            (not-any? (fn [p] (divisible? x p))
  #_=>                      (take-while #(<= % (Math/sqrt x)) lazy-primes)))]
  #_=>    (lazy-seq (filter no-smaller-prime-factors? (drop 2 (range))))))
#'user/lazy-primes
user=> (time (nth lazy-primes 800000))
"Elapsed time: 29022.974863 msecs"
12195263

tabidots04:03:48

Weird, I just tried to "refresh" the function by converting it back to Math/sqrt x (bad idea) and then back to tower/expt x 1/2 again. It seems to get stuck at the first value I find? i.e., after clearing the cached sequence from memory, this is what I get:

(last (take 100000 lazy-primes))
=> 364031
(last (take 300000 lazy-primes))
=> 364031
(last (take 600000 lazy-primes))
=> 364031

nathantech200504:03:32

What is your JVM running on? Memory/ram?

tabidots04:03:11

I have no idea. I'm working in Atom via Proto-REPL. Must be some memory issue because I'm now getting out of bounds errors even on nth lazy-primes 40000 I guess?

nathantech200504:03:16

I think you are getting the same number, because a lazy seq caches the first result

nathantech200504:03:21

And nth is probably throwing the index out of bounds error

nathantech200504:03:53

But I cannot find a max allowed on the sequence data type... I'd assume it depends on ram, memory

nathantech200504:03:13

Because the default JVM can eat a ton of memory... depends on underlieing data structures and complexity big O

tabidots04:03:40

Ah, I restarted Atom and the REPL and I'm getting results again. (Except with nth, as you say, which is still throwing the Index OOB error.) It is already becoming too slow at (last (take 200000 lazy-primes)) though. Worse yet, I need all of the primes up to n (100 million), not just the nth, and I have no idea how many primes that is. So frustrating because everyone says this problem is so easy! Conceptually it isn't very hard but I just can't get my computer to do it. I might end up just rewriting this one in Python just to get it over with. Thanks for your help guys!

nathantech200504:03:46

(nth coll index not-found)

nathantech200504:03:07

not-found should skip the index error

nathantech200504:03:00

Says nth is O(n) complexity on sequences

nathantech200504:03:49

Ok... I think the problem is

tabidots04:03:01

That makes sense. But even if nth was O(1), it wouldn't really help much in this case since I need them all 😕

nathantech200504:03:14

You are looking for a number at exactly the 800,000 index and its missing

nathantech200505:03:19

It depends... if you call nth each time in a loop, that is linear times linear = exponential

nathantech200505:03:02

Calling nth 800,000 has to go through sequence, 1 at a time

tabidots05:03:05

It's missing because the first result from the lazy-seq is cached, right? Because now (time (count (doall (take 400000 lazy-primes)))) is giving me the same count for 400k, 1M, 10M, etc...

nathantech200505:03:34

Lazy seq caches the first result, memoizes it

tabidots05:03:25

So basically I should just restart the REPL, run the code for the problem without testing intermediate values, and let the program run all afternoon until it gets the answer?

nathantech200505:03:28

I think the problem is... there is no 800,000 index

nathantech200505:03:38

Testing for intermediate values will cause 2^n complexity

nathantech200505:03:50

If nth is called repeatedly

nathantech200505:03:08

Linear inside linear, loop inside loop

tabidots05:03:10

No, not testing for intermediate values in the program. Just testing in the REPL (but results are still cached)

nathantech200505:03:52

I would try to batch process it

tabidots05:03:04

Problem is when I try to test 800,000 right off the bat, I have no idea how long it is going to take (and the real count I need is, well, I have no idea). Seems like this is one I should just let run overnight

nathantech200505:03:04

Save every 10,000 numbers

nathantech200505:03:27

Id modify it into a batch... estimate time for each 10,000 #s, resets memory resources, see where it crashes

nathantech200505:03:54

But memory probably is fine... just an example

tabidots05:03:51

Cool, thanks for your help. I don't have a C++ background so I am pretty clueless about memory allocation and all the really low-level stuff. Although I do get the impression that Clojure is not the best fit for this problem anyway (given the ginormous range of numbers involved). There aren't many, but I had to raise the white flag on a couple others and switch over to Python.

seancorfield05:03:13

I can't repro your IndexOutOfBoundsException -- I can get (nth lazy-primes 1000000) just fine (but it takes a long time to get there)

seancorfield05:03:51

But as it stands your lazy-primes will eventually eat up all available memory because you're holding on to the entire sequence there.

tabidots05:03:57

It must have been a memory issue on my machine, because the upper bound that would trigger the exception was not consistent.

nathantech200505:03:02

Must be storing some insanely large numbers?

seancorfield05:03:28

I'm still waiting for it to calculate 10000000 primes (or crash) 🙂

nathantech200505:03:16

I wonder if it will exceed a big int

seancorfield05:03:30

But Euler 357 doesn't require you calculate all those primes. It just requires that you have a fast way of determining whether any given number is prime or not.

seancorfield05:03:32

And it also wants you to produce the list of divisors for any given number. Which is a related computation (primes have no divisors other than themselves or 1).

nathantech200505:03:05

I'd check 1 to 9 with a modulo operator

tabidots05:03:46

Well, I have another non-lazy-seq function that I use for most problems. It is technically a primality checker and I use it, memoized, with filter? on range to generate a sequence, which (for its simplicity) is surprisingly fast up to a decent number (a million or so?). But it was too slow for this problem. The reason I wanted to calculate all the primes is because the initial set of candidates will be all numbers that are 1 less than a prime. (And the valid numbers are a subset of those.) So I thought it would be faster to do it that way than to test every even number. The rest of the problem (divisors and all) is manageable; I'm getting correct results as long as I can generate primes correctly.

seancorfield05:03:46

Fair point. I strongly suspect the "best" answer is something mathematically clever rather than anything brute force (which tends to be the case with a lot of these Euler problems... which is why I gave up on Project Euler... and I'm a mathematician by training!).

nathantech200505:03:26

Ya... example... there is a formula to find nth fibonacci... called Binet Formula

nathantech200505:03:44

But all the prime formulas look like sequence formulas

nathantech200505:03:45

Maybe he can run it concurrently

seancorfield05:03:04

Certainly given unlimited memory you can calculate and cache them all (which is probably why they set the limit to be 100,000,000 to try to prevent brute force solutions?).

seancorfield05:03:19

There's a lot of filtering you can do since for d + n/d the divisors are going to be symmetric (5 + 30/5 is the same as 6 + 30/6, and the same is true for all the smaller/larger divisors).

tabidots05:03:29

Yeah, absolutely. So I looked at this problem up, down and sideways but still couldn't think of any fast, intuitive way to check the validity of a given number. Of course, I don't have a math background at all; just getting into "real math" for the first time since high school.

seancorfield05:03:38

I last studied "serious" math in university in the early 80's 🙂

nathantech200505:03:57

Check if the # is divisible by 1 to 9

nathantech200505:03:09

Because 1 to 9 makes up all numbers

nathantech200505:03:46

If there is a remainder on all the divisions... it is prime

nathantech200505:03:15

29 / 9, 29 / 8, 29 / 7 etc

nathantech200505:03:28

Modulo is a remainder

seancorfield05:03:44

Everything is divisible by 1. 289 is not divisible by 2..9 tho' but it isn't prime.

nathantech200505:03:19

:rolling_on_the_floor_laughing:

seancorfield05:03:12

(289 is divisible by 17)

nathantech200505:03:05

Ya... you are right

seancorfield05:03:28

(all those years of math study still count for something 😆 )

nathantech200505:03:36

Its a vedic math trick

nathantech200505:03:01

All primes end in 1, 3, 7, 9

nathantech200505:03:19

But have to divide by 6, and check if remainder is 1 or 5

tabidots05:03:30

That's basically wheel factorization, isn't it?

nathantech200505:03:18

I have no idea... but it is interesting to find out why it works

seancorfield05:03:02

Heh, what was I saying earlier about Project Euler? 🙂

seancorfield05:03:54

I love how it's "tune in next week to learn about the 5% of numbers for which this doesn't work!"...

dpsutton05:03:00

sicp contains a primality check that works for all but a very small number of primes (chapter 2 i think)

seancorfield05:03:15

(my (take 100000000 lazy-primes) still hasn't completed, BTW)

nathantech200505:03:40

He's going to melt his ram

seancorfield05:03:58

That's been fun, but I'm out for the night. See y'all tomorrow. I'll leave my REPL running that to see what I get...

dpsutton05:03:43

my favorite footnote ever

tabidots05:03:06

haha, thanks for sacrificing your RAM in the name of mathematics 😄

dpsutton05:03:08

> Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering.

tabidots05:03:39

Hmm... If that's the case, I wonder if something not too elaborate like using Java interop for isProbablePrime would be sufficient to make the problem tractable. Will have to try after lunch

nathantech200505:03:57

Prime numbers are the cardinal points on a base 12 system

nathantech200505:03:18

The 1, 3, 7, 9 and modulo 1, 5 works

nathantech200505:03:55

If you use a clock, base 12. You will see the pattern... I found a video on it

nathantech200505:03:44

I'll write some code, tomorrow... getting sleepy

tabidots05:03:22

289 fails the 1-3-7-9 mod 6 test as well (289 mod 6 = 1)

nathantech200506:03:35

Mod 6 must = 1 or 5, then it is prime

tabidots06:03:45

289 isn't prime

nathantech200506:03:58

Ok... try this... numberphile better be accurate 😂

nathantech200506:03:19

Omg... nevermind. 289 would go in the power. Meaning a 289th degree polynomial

nathantech200506:03:32

I will look tomorrow. But it says Binet also works for primes over 5

andy.fingerhut06:03:06

There are pretty good reasons why factoring very large numbers is computationally difficult, although I hear from a friend who has been looking seriously into the issue that quantum computers are likely to be able to start doing a few problems faster than today's computers in 5 years or so. I am not 100% certain whether factoring large numbers is one of them, but I think it is.

nathantech200506:03:28

I am looking up Fermat's test

tabidots06:03:59

@dpsutton Thanks for suggesting a probabilistic method. I used isProbablePrime to create the initial list of candidates, and then used my trial division primality checker to confirm the validity of the candidates. My machine managed to get the correct answer after 13.5 minutes.

(defn problem-357 [lim]
  "Find the sum of all positive integers n not exceeding 100 000 000
  such that for every divisor d of n, d+n/d is prime."
  (let [primes     (->> (range (inc lim))
                        (filter #(.isProbablePrime (BigInteger/valueOf %) 5)))
        candidates (map dec primes)
        valid?     (fn [n]
                     (loop [d 2]
                       (cond
                         (> d (tower/sqrt n))          true
                         (or (not (h/divisible? n d))
                             (h/prime? (+ d (/ n d)))) (recur (inc d))
                         :else                         false)))]
    (reduce + (filter valid? candidates))))

(time (problem-357 100000000))
;; Elapsed time: 808512.398784 msecs
Finally, I can forget about this stupid problem! Thanks for your help everyone.

twaima07:03:11

why lein run does not run in background?

andy.fingerhut08:03:33

Have you tried lein run & to see if it will run in the background that way, assuming that the command shell you are using, e.g. bash, uses the syntax & at the end of the command to start the process in the background?

twaima08:03:29

it will not start to listen for ports unless I run fg later - weird because if I run simple bash script this way it will run in background.

andy.fingerhut08:03:14

I'd recommend asking in the #leiningen channel -- someone there may know more about why that is, or if there is a way to make it work as you are hoping.

lepistane14:03:31

Hi, Is there a way to do a`trigger fn if atom value changes`? similar how reagent atom works - trigger rerender once atom state changes? but in my case call that fn

victorbjelkholm42914:03:22

registers a function that gets called every time the passed in agent/atom/var/ref changes

lepistane14:03:08

i looked at that but i am afraid ordering might get messed up

victorbjelkholm42914:03:41

ordering? You might have to explain a bit more what you're trying to do

lepistane14:03:54

less spam for people like this. Basically i have an atom that holds information about task. running true/false. There could be situation where i have task running in the background meaning :running true. but i've turned off it's next execution. and new task is being submitted. (button mashing) instead of new task running while old one is running i would like if it triggered after (once task is done it puts :running false in atom)

victorbjelkholm42916:03:58

sorry, it's hard to notice thread replies... Feels like you would have one internal atom per task, and something around that can check in general if tasks are running. I'm sorry, but I still quite don't understand the issue clearly

brandon.ringe15:03:45

I'm working on this problem: http://www.4clojure.com/problem/118 And I am attempting to solve with lazy-seq as this seems to make sense. However, I can't figure out why this is not working.

(defn my-map
  [f s]
  (lazy-seq (cons (f (first s)) (my-map f (rest s)))))
It's the first time I've tried to use lazy-seq. When I run the following code I get a nullpointerexception.
clojure-test.core=> (my-map inc [1 2 3])

NullPointerException   clojure.lang.Numbers.ops (Numbers.java:1013)

brandon.ringe15:03:18

Any tips would be appreciated simple_smile

dts.siedel15:03:27

What happens when s becomes empty? You haven't defined a base case for your recursive call, so eventually s will be empty. Then (inc nil) gives your null pointer

brandon.ringe15:03:59

Hmm i was wondering about this, and if that is the case where would the check go? I see in this example they use rest similarly with no check. https://clojuredocs.org/clojure.core/lazy-seq#example-542692d3c026201cdc326ff1

brandon.ringe15:03:29

But yeah that didn't make sense to me anyway. @dts.siedel

dts.siedel15:03:18

That sieve returns an infinite sequence. With lazy sequences you can do that (ex. (range) tries to return every number from 0 on) - note that they call take 20 when they use it, because otherwise it would try to give them every prime number

oliv16:03:22

quick question guys I’m using component and I have some Services ( http clients ) which need some configuration ( api-tokens / auth … ) is it ok to create a component for that Http Clients ?

hiredman16:03:15

it is a matter of taste. when using component I like for any services used to be made a first class value as their own component

hiredman16:03:15

so for example if I was using the github api, instead of creating a http client component I would make a github api component

oliv16:03:09

yeah, I meant, create a component for each service ! like you said github api component

oliv16:03:24

I’m doing that @hiredman

oliv16:03:33

and injecting on my server component the clients

mario.cordova.86218:03:49

If you create a list of futures and then dereference them right after creation, is that considered pointless? Couldn't you have just ran the functions sequentially?

mario.cordova.86218:03:49

result [(future (ten-min-func)) (future (five-min-func)) (future (twenty-min-func)))] and then (map deref result)

ghadi18:03:13

they're still running in the background, and you're still waiting for all of them to complete

mario.cordova.86218:03:16

now that i wrote that out

ghadi18:03:43

but map is lazy, remember

ghadi18:03:16

do you might not be waiting at the point of the code that runs (map deref result). Whoever realizes that seq will do the waiting

hiredman18:03:55

you also have to careful when creating futures, if you create them in a lazy seq they of course won't run until the seq is realized

hiredman18:03:28

so for example using for or map to create a seq of futures, then maping deref, then forcing that seq is bad

mario.cordova.86218:03:45

good catch because ive seen that around our code base somewhere

mario.cordova.86218:03:00

but what if you are dereferencing right after?

mario.cordova.86218:03:43

futures (map .... ) then (doall (map deref futures)

ghadi18:03:15

that's the scenario that hiredman was mentioning. map is lazy, so the futures (first map) won't be launched until the second map happens

mario.cordova.86219:03:48

I understand but I guess I dont understand the error in that

mario.cordova.86219:03:20

If I call (doall (map deref futures) right after then whats the problem?

ghadi19:03:10

it's equivalent to running @(future1) @(future2) @(future3)

ghadi19:03:19

which was probably not the intent of using the futures

ghadi19:03:40

they're effectively running in the current thread

ghadi19:03:49

and future2 isn't launched until future1 completes

ghadi19:03:55

you want to spawn them all at once, then wait all at once

ghadi19:03:59

(but mapv or something eager instead of map)

mario.cordova.86219:03:10

gotcha, thanks for clearing that up

noisesmith19:03:17

@mario.cordova.862 for (let [futures (map ...)] (doall (map deref futures))) the futures aren't created until the ones before them return

noisesmith19:03:22

(modulo chunking)

noisesmith19:03:59

you want to create all of them in one go, or at least explicitly control how many are in flight instead of relying on lazy-seq internals for the pipelining

tabidots23:03:44

@noisesmith How did you make the fancy code chunk? I’m still new to Slack

noisesmith23:03:15

@tabidots via the + button on the left

tabidots23:03:11

Neat, thanks!