Post Reply 
Programming puzzles: processing lists!
05-24-2017, 08:28 PM (This post was last modified: 05-24-2017 08:39 PM by pier4r.)
Post: #88
RE: Programming puzzles: processing lists!
(05-24-2017 06:12 PM)DavidM Wrote:  A quick test shows that the performance degradation is significant when comparing reals and integers for equality.

I realize that this set of commands is a bit more application-specific than something like GoferLists. But they may still be of some use.

I'm a fan of "look this works under those conditions". Making super generic routines is surely helpful and maybe fun, but one has to start small, otherwise one never starts.

So once you define properly the expected input, that's it. Another person can improve it (as it was done for the GoFerList. Open source has this strength).

(05-24-2017 06:43 PM)DavidM Wrote:  I will confess that I've had no desire to approach that particular challenge, partially because it's probably been at least 20 years since I had to code any kind of graph-traversal routines. Also because it made my head spin every time I tried to reconcile the problem description with any kind of RPL approach. That said, I don't think I'd like to use SQL for it, either. I applaud your efforts and will be happy for you when you solve it. Smile

I do believe the #20 (I mistook with the #21 all the time, damn me) is not that difficult to solve, at least trivially. Just for me it is divided in 3 parts:
- generate the input, done.
- process it to let it be analyze by the "find the clique" routine. That is the part where I#m stuck because I tried to use DOLIST and DOSUBS that are not debug friendly. And the idea to process the input is not even that difficult, but the details are.
- compute the largest clique (naively), still undone part but I have the basic algorithm in mind.

Graphs can be nasty, but not that of a problem. I mean especially when I pick the challenges from sites like careercup.com , even if I variate them a bit, the problems cannot be too hard because are meant to be solved in some hours (with python or other comfy languages I guess).

As I wrote multiple times, I got frustrated by the attempts to debug DOLIST/DOSUBS (because sometimes they accept empty stacks as result of the program, sometimes not, for example, it is not so clear) and I started to look elsewhere before trying again. Since one of my todo-s is to explore SQLite (that is pretty beefy in terms of capabilities, I was not expecting that), I started to use it there.

The code, not working, in userRPL, is here: https://app.assembla.com/spaces/various-...erations.s

lines 2583 - 3117 (as usual, mostly are comments). The list generator and the input collector works. The part to extend the reachability of the nodes does not.

In SQL is here: https://app.assembla.com/spaces/various-..._201705.sh

So far it works, although the debug was intensive, but now I need to see how to determine the largest clique. I have the algorithm in mind but not its translation in SQL and I don't want to end up to use WITH RECURSIVE ... SELECT . Or maybe yes? dunno.

If I have to be honest, I do think that, in the cause I had debug-friendly DOLIST and DOSUBS, the userRPL approach is way less weird than the SQL approach because userRPL has all those nice functions for lists, SQL does not have much functions to make actions between tables. Or at least I do not know them so far. So the actions allowed by userRPL give more freedom to the user.

edit: I forgot, thanks for the moral support! I actually feel really bad, the #20 was a variant of a question for an amazon software engineer position and I guess they allowed like 1 hour to solve it, and I'm stuck since days.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Programming puzzles: processing lists! - pier4r - 05-24-2017 08:28 PM



User(s) browsing this thread: 1 Guest(s)