# Background

Saw this problem on TheJobOverflow which seems to be a LeetCode question.

It bothered me that the "challenge" of this problem was to recognize the need for a specific data-type (in this case a MaxHeap/PriorityQueue).

I did another, more complicated solution, that uses folding

# Problem

You are given a list of stones' weights (positive integer numbers);
While there are at least two stones in the list, take the two heaviest stones and smash them together;

if the weights were equal, both stones are destroyed;
otherwise the lighter stone gets destroyed and the heavier one becomes the difference of the two values.
You know need to consider this "remainder" stone as well as all the other stones

The process ends when there is one or no stones in the list, and the result is either the last remaining stone, or zero if there are no stones left.

## Notes

The main problem that you need to solve for here is the fact that, at all times, you need perfect knowledge/information on the state of the list. You need to know EXACTLY which two stones are CURRENTLY the two heaviest. WHILE adding to the list of known stones.

As you smash stones you will inevitably be left with a remainder stone that you need to put somewhere. The new stone might now be the heaviest or the lightest, you don't know yet and you now need to keep track of it.

The Reference Solution (written in CPP) uses a MaxHeap/PriorityQueue as it is the most efficient way to keep the maximum sized stone (integer) in a convenient position while being able to add to the structure in efficient time.

# Personal Goals

• Attempt to not use special data types outside of base lib.
(There is a Heap package on Hackage, but can we do it without it?)
(nothing too fancy)
• Attempt a "naive" approach
(could a beginner stumble upon this with a rudimentary grasp of Haskell?)
• Should be performant
(probably won't be better than the cpp implementation but should be about as fast and show the same time complexity

# The Code

naiveLastStone :: (Num a, Ord a) => [a] -> a
naiveLastStone = proccess . revSort
where
revCompare = flip compare
revSort    = sortBy revCompare
revInsert  = insertBy revCompare

proccess []  = 0
proccess [x] = x
proccess (x:y:ls)
| n == 0     = proccess ls
| otherwise  = proccess $revInsert n ls where n = x - y  # Explanation ## Init naiveLastStone :: (Num a, Ord a) => [a] -> a naiveLastStone = proccess . revSort  compose the process with the reverse sort we process the list in order, heaviest to smallest ## Helpers  revCompare = flip compare revSort = sortBy revCompare revInsert = insertBy revCompare  idiomatic acceding sort and insert ## process first the base cases: empty list means return 0 and one stone left means return it.  proccess [] = 0 proccess [x] = x  then the actual processing of the list  | n == 0 = proccess ls | otherwise = proccess$ revInsert n ls
where n = x - y

1. We are operating on the presumption that the list is ordered, large to small. The first 2 items will be the largest, and the second largest. (we need to keep the list sorted as we work with it)
2. If remainder is 0, the rocks were destroyed and we process the next rocks | else
3. The remainder rock exists, we now need to put it into the the list in the correct position.
We use insert (using our acceding revInsert) as it has the property of keeping a sorted list, sorted. Our list is now in the correct order for the next iteration.

# Performance

Checked against TheJobOverflow cpp solution

code time array size
cpp (-O3) ~0.8s 10 000 000
cpp (-O3) ~2.5s 20 000 000
cpp (-O3) ~3.8s 40 000 000
cpp (-O3) ~8.0s 80 000 000
cpp (-O3) ~10.0s 100 000 000
cpp (-O3) ~30.0s 800 000 000

Sadly my solution is showing O(n^2) as apposed to the O(n log n) of the cpp solution.

# Personal Goals Met

1. Yes
2. Yes
3. Yes
4. No^2
• I'm not sure if your solution is correct. Consider for example process 0 [10,9,8,3,2] == 4 but it should be [10-9,8,3,2] -> [8-3,2,1] -> [5-2,1] -> [3-1] -> 2. Mar 20 at 8:29
• You are 100% correct. I will edit Mar 20 at 10:40
• I am actually gutted right now. I got too excited about this "simple" solution and didn't properly test it. So I broke rule one for CodeReview: "don't post broken code". I am going to update it with a very much worse solution and make the post beter later. I just need it to not be wrong right now. Mar 21 at 0:36
• @maxtaldykin Does the code work now? Mar 21 at 12:40
• @pacmaninbw, Haven't tried it, but looks like it does. Mar 22 at 15:30

The sort seems to be a merge-sort; I trust that it's O(n log(n)). But insert is noted as O(N), and you're calling it O(N) times, so it's a good bet that this is the/a problem.
I don't actually have a good solution for you. In order to have an O(log(N)) insert, you'll need at minimum an O(1)-indexing data structure, preferably an always-sorted array or maybe a tree. I can't find any such thing in base.
My only suggestion might be to unpack the source code for sort to somehow perform the rock-smashing during merging? Could be tricky...