Last Stone Weight Problem in Haskell using list `insert`

Question

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?)
• Attempt Idiomatic Haskell
  (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
haskell (-O2)	~0.5s	10000
haskell (-O2)	~2.5	20000
haskell (-O2)	~11.3s	40000
haskell (-O2)	~60.3s	80000

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

• max taldykin: 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.
• WesAtWork: You are 100% correct. I will edit
• WesAtWork: 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.
• pacmaninbw: @maxtaldykin Does the code work now?
• max taldykin: @pacmaninbw, Haven't tried it, but looks like it does.

Answer 1

Our first question should be "why is it O(N^2)?"

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

• WesAtWork: Yeah thanks! I am still working the problem in my off time (my mind won't let it go). The "unpacking the merge sort" could be a very good idea! The reason it is O^2 (or might just look like it) could be that the haskell code Is, in fact, unpacking the insert, but what ends up happening is that a "tower" of thunks build up at the horizon of the list. Every subsequent iteration require (n) times of shifting the entire "tower" a step. I am testing worst case [1..n], the sort needs to flip this AND the insert needs to traverse THE ENTIRE LIST eventually to place all the 1s at the end.