Here's another freebie!! I signed up for a programming problem of the day. I got my first one today, rated "easy".
Here's the description of the problem.
https://git.qoto.org/Absinthe/sum-of-number-in-list/blob/master/README.md
My code to solve it, though not clean and delicious, is in that same repo, but certainly give it a crack before peeking. :)
@Absinthe this one was actually "easy", just translated the description and mercury solved it for me (no squinting required), so I decided to throw in some input handling and that was the painful part as usual.
https://git.sr.ht/~namark/mercury_stuff/tree/master/toys/pairs_add_up_to.m
But of course the real challenge is doing it in one pass... in a language that might not have a concept of a pass...
@namark I really do wish I could run the code :(
I usually try not to involve I/O in the problems as that can just add an unnecessary layer of complexity to most things.
So, let me ask, the line that says
A + B = K ... does that generate a whole bunch of things like (1 + K-1) (2 + K-2) (3 + K-3) and so on?
If that is the case, what does it feel like if your list of numbers are large? Like 1,234,567,890?
@namark maybe i will try it from sources this weekend.
@Absinthe How it works? I'm not sure myself.
The idea is that you just write rules/goals, and then the program(I guess) comes along and tries to satisfy those goals. If it manages to do so the predicate as a whole succeeds(becomes true), otherwise it fails(becomes false).
Tat specific predicate is something like:
The sum of A and B must be equal to K and
A must be in the List and
B must be in the List.
@Absinthe It probably does generate(or just go through) all the pairs under the hood, but I'm not sure exactly how. If it's really smart and aware of associativity of addition, it might even skip the equivalent pairs.
@Absinthe One fun thing is that order of goals usually doesn't matter, so could arrange the 3 lines in that predicate however you want, they are just rules/constraints and the program will read them all and try to satisfy them all together. In abstract terms that is, not sure what's really going on under the hood.
I just found an error in my implementation, I wonder if you might want to test yours.
Here is the issue. Let's say your list of numbers is [2, 5, 8, 3, 7, 9] and your K=4 So, in my case I take K-2 to get 2 and search for it in the list and find it. But it is not a second 2 just the only 2. I believe I would return True, and it should be false. No one ever said the numbers in the table were unique, so in theory there could be 2 2's or just one.
I will be able to fix one way that I did it, but I am not sure I will still be able to pull off the 1 line solution :)
@Absinthe Yep, had the exact same issue. Fixed by requiring the indices of A and B in the list to be distinct.
Also did some performance tests. Before the fix it was not too horrible - took about a minute for the worst case with 100,000 elements.
After fix however... even 1000 elements take like 13 seconds, and 10,000 overflows the stack, so I'm obviously doing this the wrong way. Have a strong urge to go back to C++ now.
@Absinthe Made a couple c++ versions:
A simple one
http://ix.io/1XbV/cpp
and a clever one
http://ix.io/1Xc2/cpp
On my old T400 they take 1 minute and 20 seconds respectively and hopefully are correct this time around.
Will see if I can get anywhere near any of those with Mercury.
Equivalent implementations for these in Mercury:
"simple" one, still sluggish but at least doesn't overflow
https://git.sr.ht/~namark/mercury_stuff/tree/master/toys/array_pairs_add_up_to.m
"clever" one, pretty good performance (somewhere in between the two c++ versions), but at this point I completely abandoned the logic programming approach
https://git.sr.ht/~namark/mercury_stuff/tree/master/toys/clever_pairs_add_up_to.m
@namark
This has now been fixed.
@Absinthe nice, and the "one line" version seems quite optimal too.
@namark Thanks! It still doesn't feel intuitive yet. If I came across such a line I would have to work it out to see what it did. But hey, it does work and with all the corner cases I could think of.
@Absinthe true, I don't think I would be able to understand that, if I didn't already know what it was trying to do.
Then again I don't know python, and can still kind of make sense of it given the context. Definitely much more readable than an equivalent Mercury version I'm about to push :D
@namark I have not had a chance to try to compile mercury yet. I don't do much with procedural languages. I guess there is no time like the present.
@namark that's pretty cool. But without understanding all the predicates and such it was hard to follow what the code was doing. But it seemed that when you did A + B = K that it didn't know anything about the list, so when it went through the member call, I was wondering what it might be trying to test
@Absinthe It wasn't really that hard to install, just downloaded the 14.0.1(i think) source release from the website, and
./configure
make
make install
It only needs gcc and gnu make.
The only slightly tricky part was adding the bin directory from the installation to the system PATH.
It took a few hours to build on my super old desktop.