Second attempt, still stuck :-(

prototyp · Post by **prototyp** » Sat Apr 19, 2014 5:29 am

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

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!

camel · Post by **camel** » Wed May 28, 2014 4:23 am

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?

camel · Post by **camel** » Wed May 28, 2014 4:27 am

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.

prototyp · Post by **prototyp** » Fri May 30, 2014 4:04 pm

"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

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!

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

(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

camel · Post by **camel** » Sat Oct 11, 2014 4:51 pm

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

camel · Post by **camel** » Sat Oct 11, 2014 4:53 pm

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