hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Second attempt, still stuck :-(

 
Reply to topic    hacker.org Forum Index » OneOfUs View previous topic
View next topic
Second attempt, still stuck :-(
Author Message
prototyp



Joined: 12 Jun 2009
Posts: 2

Post Second attempt, still stuck :-( Reply with quote
Hi Guys,

I got into this years ago and got up to about lvl 100, now I've got some time on my hands and decided to try again - new algorithms(!), new code, new tricks... slightly better result (lvl125).

I'm using a variation of Dijkstra, and it works a dream for most levels (<=1 second) but occasionally it gets stuck (often levels 58, 78 or 86) (the randomness is introduced by perl's hashing algorithm - which is OK, since equivalent nodes are normally selected at random anyway)

I'm testing connectivity (to prevent islands being cut off) and a few other optimisations, but when it starts back-tracking it quickly reduces to a brute-force behaviour Sad

What sort of things can hint at problems early, or are there some positive things to search for, such as the number of edges connecting with a node, etc...?

On a side note, does the choice between a node-based and edge based algorithm make things easier / harder?

cheers, thank in advance and a tip-of-the-hat to the author (Adum?) Great puzzle!
Sat Apr 19, 2014 5:29 am View user's profile Send private message
camel



Joined: 26 Dec 2007
Posts: 50
Location: Austria

Post Reply with quote
There are very performant algos out there and even binaries taking a specific input format to solve the HP/HC problem. Why re-invent the wheel when you already identified the kind of algorithm you need?
Wed May 28, 2014 4:23 am View user's profile Send private message
camel



Joined: 26 Dec 2007
Posts: 50
Location: Austria

Post Reply with quote
Also forget Perl! I am also a Perl veteran but the problems here get so big that Perl just is the wrong choice in terms of speed, memory management, robustness, etc. ... you will just get frustrated. When I ported my Modulo solver from Perl to C++ I solved another 15 levels in like 10 seconds when Perl would haven taken days.
Wed May 28, 2014 4:27 am View user's profile Send private message
prototyp



Joined: 12 Jun 2009
Posts: 2

Post Reply with quote
"Why re-invent the wheel?", you ask?

How about: "I like the challenge and see it as brain-sport".
I absolutely *hate* hand-wavey claims like "just download it from the 'net" - that doesn't solve anyone's problems at all! I don't want to be spoon fed, I wouldn't be here if I did Smile

By the way, even though I have identified the problem, I haven't actually found a tool/library that I thought would actually solve this problem. Maybe I'm blind or keep looking in the wrong place.
(or could it be that I'm "restricting" my search to non-windows platforms?)

As far as I can tell, I've got the theory "not entirely wrong", but something is still missing - at least I'm up to level 200+ now - but it's nothing like runaway robot where once I came up with *my solution*, I coded it and watched it blast through all 500 levels. That was a real buzz! Smile Just running some code I got from somewhere else? Boring!

Anyway, since my last post I've built an interactive one-of-us-graph-viewer/solver so that I can stop the algorithm, step back and forwards and even change decisions, and actually *see* what's going on. (written in java btw.)
Speed is not the problem, it can be used interactively and isn't even multi-threaded.
But it HAS taught me all kinds of stuff and it also shows how the puzzles get more intricate (e.g. I can actually see and identity different structures in the graphs - at least visually, the challenge is to identify them programmatically).

The viewer still has a few bugs but if someone is interested, I could post it on github and you could try out your own algorithms. (I still need to clean it up a bit first before I publish it though).
If/when I publish it, it *won't* have the solver class - just the ability to visualise the levels and an API so you can add your own solver to it. (the solver is a delegate - the program works fine without a solver, just can't do anything automatically)

As for perl, I've written code for one-of-us in perl, java, go & C - the language really isn't my problem Smile
(this should be solvable in any language - the question is not how good the language is, but whether you've simplified the problem and whether you're using the language effectively)

Cheers
Fri May 30, 2014 4:04 pm View user's profile Send private message
camel



Joined: 26 Dec 2007
Posts: 50
Location: Austria

Post Reply with quote
Well if you genuinely believe that the language doesn't make any difference then good luck. Try solving the Crossflip challenge with Perl on a standard computer ...
Sat Oct 11, 2014 4:51 pm View user's profile Send private message
camel



Joined: 26 Dec 2007
Posts: 50
Location: Austria

Post Reply with quote
Same goes for the OneOfUs Challenge. One of the most performant HP/HC solvers out there runs for a few minutes on the last level. Perl is at least 4-5 magnitudes slower ...
Sat Oct 11, 2014 4:53 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » OneOfUs All times are GMT
Page 1 of 1

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.