La Fée VerteSep 26, 2019

#toyprogrammingchallenge

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

README.md · master · La Fée Verte / sum of number in list

GitLab Enterprise Edition

Show threadnamark

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

#toyprogrammingchallenge #mercurylang

~namark/mercury_stuff: toys/pairs_add_up_to.m - sourcehut git

Sep 27, 2019 at 8:39amWeb
Show threadLa Fée VerteSep 27, 2019

@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?

Show threadnamarkSep 27, 2019
@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.
Show threadLa Fée VerteSep 27, 2019
@namark maybe i will try it from sources this weekend.
Show threadnamarkSep 27, 2019
@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.
Show threadnamarkSep 27, 2019
@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.
Show threadnamarkSep 27, 2019
@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.
Show threadLa Fée VerteSep 27, 2019

@namark

#toyprogrammingchallenge

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 :)

Show threadnamarkSep 27, 2019

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

Show threadLa Fée VerteSep 28, 2019
@namark
This has now been fixed.
Show threadnamarkSep 28, 2019
@Absinthe nice, and the "one line" version seems quite optimal too.
Show threadLa Fée VerteSep 28, 2019
@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.
Show threadnamarkSep 28, 2019

@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

Show threadLa Fée VerteSep 28, 2019
@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.
Show threadLa Fée VerteSep 27, 2019
@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