Fork me on GitHub
#beginners
<
2019-03-27
>
Thomas Lisankie01: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))

Chris O’Donnell01: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))

hipster coder01:03:16

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

hipster coder01:03:38

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

Chris O’Donnell01: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.

hipster coder01:03:48

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

hipster coder01:03:40

What does the unit test fail on?

hipster coder01:03:48

The code should return true or false

hipster coder01:03:50

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

butterguns01:03:10

Examine your first (if expression

hipster coder01:03:05

Why is it returning true if tree? Is nil

hipster coder01:03:57

Shouldnt it return false if tree? Is nil

Chris O’Donnell01:03:53

I think nil is intended to represent an empty tree.

Thomas Lisankie01:03:36

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

Thomas Lisankie01:03:46

@UFQAPAUU8 Thanks, I’ll look at it

Thomas Lisankie01:03:13

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

Thomas Lisankie02:03:09

It doesn’t seem that’s the case

butterguns02:03:28

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

butterguns02:03:02

Zoom out, and look at the fn as a whole

butterguns02:03:16

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

butterguns02:03:05

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

butterguns02:03:17

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

butterguns02:03:42

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

butterguns02:03:43

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

valerauko03:03:18

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

Thomas Lisankie03:03:07

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

Eric Clack13:04:16

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

Eric Clack13:04:44

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

Eric Clack13:04:22

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

Eric Clack13: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))
   )
))

hipster coder01: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

hipster coder04: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.

hipster coder04:03:09

What is the highest max value possible in your code?

hipster coder04:03:26

800,000th prime # is?

hipster coder04: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.

hipster coder04: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

👍 4
lilactown04:03:51

yeah I’m also able to run the code

hipster coder04: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

hipster coder04: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?

hipster coder04:03:16

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

hipster coder04:03:21

And nth is probably throwing the index out of bounds error

hipster coder04:03:53

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

hipster coder04: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!

hipster coder04:03:46

(nth coll index not-found)

hipster coder04:03:07

not-found should skip the index error

hipster coder04:03:00

Says nth is O(n) complexity on sequences

hipster coder04: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 😕

hipster coder04:03:14

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

hipster coder05:03:19

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

hipster coder05: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...

hipster coder05: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?

hipster coder05:03:28

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

hipster coder05:03:38

Testing for intermediate values will cause 2^n complexity

hipster coder05:03:50

If nth is called repeatedly

hipster coder05: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)

hipster coder05: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

hipster coder05:03:04

Save every 10,000 numbers

hipster coder05:03:27

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

hipster coder05: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)

👍 4
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.

hipster coder05:03:02

Must be storing some insanely large numbers?

seancorfield05:03:28

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

😆 4
hipster coder05: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).

hipster coder05: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!).

😮 4
hipster coder05:03:26

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

hipster coder05:03:44

But all the prime formulas look like sequence formulas

hipster coder05: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 🙂

hipster coder05:03:57

Check if the # is divisible by 1 to 9

hipster coder05:03:09

Because 1 to 9 makes up all numbers

hipster coder05:03:46

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

hipster coder05:03:15

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

hipster coder05: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.

hipster coder05:03:19

:rolling_on_the_floor_laughing:

seancorfield05:03:12

(289 is divisible by 17)

hipster coder05:03:05

Ya... you are right

seancorfield05:03:28

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

😆 4
hipster coder05:03:36

Its a vedic math trick

hipster coder05:03:01

All primes end in 1, 3, 7, 9

hipster coder05: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?

hipster coder05: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!"...

😆 5
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)

hipster coder05: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.

😆 8
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

hipster coder05:03:57

Prime numbers are the cardinal points on a base 12 system

hipster coder05:03:18

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

hipster coder05:03:55

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

hipster coder05: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)

hipster coder06:03:35

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

tabidots06:03:45

289 isn't prime

hipster coder06:03:58

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

hipster coder06:03:19

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

hipster coder06: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.

hipster coder06: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.

ok07: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?

ok08: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.

👍 4
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

victorb14: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

victorb14: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)

victorb16: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

bringe15: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)

bringe15:03:18

Any tips would be appreciated simple_smile

dtsiedel15: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

bringe15: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

bringe15:03:29

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

dtsiedel15: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

👍 4
tdantas16: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

tdantas16:03:09

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

tdantas16:03:24

I’m doing that @hiredman

tdantas16:03:33

and injecting on my server component the clients

Mario C.18: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 C.18:03:49

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

Mario C.18:03:12

hmm I guess not

ghadi18:03:13

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

Mario C.18: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 C.18:03:45

good catch because ive seen that around our code base somewhere

Mario C.18:03:00

but what if you are dereferencing right after?

Mario C.18: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 C.19:03:48

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

Mario C.19: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

Mario C.19:03:35

that makes sense

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 C.19: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

👍 5
5
tabidots23:03:11

Neat, thanks!