I thought I was decent enough at FP… until I met this problem.
While skimming through an algorithmic problem repo, I found an interesting one.
The crux of the problem was “pairing a list into (n, n + k)
without duplicates”. (assumed to be possible for given inputs)
For example, given a list [1, 3, 4, 6, 7, 10, 12, 15]
and k = 3
,
we’d obtain [(1, 4), (3, 6), (7, 10), (12, 15)]
. Quite a tricky one.
In an imperative paradigm, you might sort the list,
and then maintain a secondary index for right-found
along with the main index.
To illustrate,
- encounter 1, put it in.
[(1, 4)]
,right-found
at 0 - encounter 3, put it in.
[(1, 4), (3, 6)]
,right-found
at 0 - encounter 4. 0th left is 1, 4 = 1 + 3. 1’s right-counterpart found,
right-found
at 1 - encounter 6. 1th left is 3, 6 = 3 + 3. 3’s right-counterpart found,
right-found
at 2 - encounter 7. not a right-counterpart, so put it in.
[(1, 4), (3, 6), (7, 10)]
,right-found
at 3 - (goes on like this)
I feel ashamed of incapability to come up with a functional solution for this one. How should I solve this problem in functional paradigm?