# Messy Medians

# Messy Medians

maruks + 2 comments 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.

abhiranjan + 1 comment I haven't find any sincere effort in clojure till now, except yours.

abhiranjan + 0 comments Anyway, I have doubled the time limits for clojure.

abendt + 1 comment 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 ...

maruks + 1 comment I ported few heaps from PFDS book. I used splay heap IIRC. https://github.com/maruks/clj-data/tree/master/src/maruks/data

abendt + 0 comments 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.

eythor88 + 0 comments Data.MultiSet is not found, but based on the discussion it should be available.

RogerB + 0 comments 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.

ppsreejith + 1 comment This seems impossible to solve in Clojure. Anyone else here with any success in Clojure? Help is welcome.

maruks + 0 comments 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 :-)

manpacket1 + 0 comments That was fun.

ManjeshGowda + 0 comments Hi, 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 ?

thomasd + 1 comment 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?

zeyuanxy + 0 comments Same. Hope someone could help with it.

maruks + 1 comment Can you add SML (NJ) to list of supported languages? SML is functional programming language. http://www.smlnj.org/

abhiranjan + 1 comment Okay. Give us sometime.

juhovuori + 1 comment 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?

abhiranjan + 1 comment 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.abhiranjan + 0 comments Hi @johovuori, it seems I forgot to revert here. This issue has been fixed nearly a month ago.

seanhess + 1 comment Consider enabling https://hackage.haskell.org/package/heap-1.0.0/docs/Data-Heap.html

My list implementation certainly isn't fast enough :)

abhiranjan + 3 comments 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 :)seanhess + 1 comment 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.

abhiranjan + 0 comments Welcome :)

seanhess + 2 comments 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.

seanhess + 1 comment I mean: would you consider enabling it?

abhiranjan + 0 comments I can consider it only if it is required/non-redundant. You know: higher numbe of packages -> higher probability of getting in cabal-hell.

abhiranjan + 0 comments Try unlocking editorials. There's my solution using multiset :)

ivanbessonov + 0 comments I'm getting "Could not find module `Data.MultiSet'" compiler error. I thought it should work. Have you exluded this module?

Sort 13 Discussions, By:

Please Login in order to post a comment