Some error occured while loading page for you. Please try again.
Sort 13 Discussions, By:
Please Login in order to post a comment
Has anyone solved this using clojure? What data structure did you use for Priority Queue? Did you write your own implementation? Based on splay trees? I tried priority map but it seems to be too slow.
I haven't find any sincere effort in clojure till now, except yours.
Anyway, I have doubled the time limits for clojure.
i tried to implement a datastructure (https://stackoverflow.com/a/11385422) using a heap based on a modified version of https://gist.github.com/pepijndevos/781061
Unfortunately still getting timeouts in 50% of the testcases ...
I ported few heaps from PFDS book. I used splay heap IIRC.
thanks! i tried your heap variants. they all seemed to perform a bit worse than the version i used initially resulting in more timeouts (score of 20/30 instead of 40).
Next i tried out an alternative heap implementation (https://github.com/shamsimam/clj-priority-queue). Using this i was able to get the full score of 80.
Data.MultiSet is not found, but based on the discussion it should be available.
I know this problem is a couple of years old, but I solved it differently than the methods in the editorial, just using Data.Set. It resulted in a lot less code, and I was wondering if it would be worth adding to the editorial.
This seems impossible to solve in Clojure. Anyone else here with any success in Clojure? Help is welcome.
yeah, I implemented persistent heap data structure.
Read this book www.cambridge.org/gb/academic/subjects/computer-science/programming-languages-and-applied-logic/purely-functional-data-structures :-)
That was fun.
Is it futile to try with TailRecursion OR MutualRecursion ( Scala ) .. I had no luck so far ...
If we follow command pattern and try to undo the commands it will not work as well...
I have had success with recursion .. but it will fail for huge numbers ...
Is there any standard Alogorithm for this problem ?
It seems Data.PQueue, Data.Heap, and Data.MultiSet all cannot be found... so I'm not sure of the data structure to use, unless I should implement my own? I've seen below that Data.MultiSet and Data.PQueue are suggested packages with efficient data structures to solve this, but I keep getting a "package not found" error. Does anyone know why?
Same. Hope someone could help with it.
Can you add SML (NJ) to list of supported languages?
SML is functional programming language. http://www.smlnj.org/
Okay. Give us sometime.
Hi, thanks for providing such an interesting problem here. But it seems that Data.Multiset or Data.PQueue can not compile cause the module cannot be found. Could you please help with it? Thanks very much!
I keep on getting runtime errors with some test inputs, but I cannot reproduce them on my laptop using the given test case. I assume, my solution is allocating too much memory. Any reason that the actual runtime error is not reported? What are the memory limits for running programs?
Hi @juhovuori, we are facing a issue wrt java/scala time limit (threading issue). We are fixing it. Meanwhile I have increased the time limit for this challenge.
This issue effects only those submission' run whose running time is near the allowed time limit.
Hi @johovuori, it seems I forgot to revert here. This issue has been fixed nearly a month ago.
Consider enabling https://hackage.haskell.org/package/heap-1.0.0/docs/Data-Heap.html
My list implementation certainly isn't fast enough :)
Hi @seanhess, I had gone through your submission. It's an inoptimal one.
Currently there are two alternative for Data.Heap
We will go through above suggestion :)
Yeah, my solution was lame, but all the algorithms I looked up used Heaps. It looks like MultiSet will work great, thanks for your help.
I implemented it with using multiset via 2 min max heaps, but still timed out on two test cases. The PrioritQueue you linked is some strange monadic thing I don't understand.
What about this one? https://hackage.haskell.org/package/pqueue-1.2.1 - The performance characteristics are perfect.
I mean: would you consider enabling it?
I can consider it only if it is required/non-redundant. You know: higher numbe of packages -> higher probability of getting in cabal-hell.
Try unlocking editorials. There's my solution using multiset :)
I'm getting "Could not find module `Data.MultiSet'" compiler error. I thought it should work. Have you exluded this module?