Author |
Message |
Captain Segfault
Joined: 05 May 2007 Posts: 67 Location: San Carlos, CA |
|
Re: Languages? |
|
 |
 |
Issue is that I built it in PHP-cli, which is what is causing the speed cap on mine. I might learn perl to see if I can get it up to speed. |
What's causing your speed cap is your algorithm. Implementing it in hand optimized assembler isn't going to get you *that* much further. You can probably hit 513 with a better algorithm in your language; assuming PHP-cli is within a factor of 10 of Perl, my algorithm ported to it would finish runaway within a day or two.
|
|
Wed Jun 27, 2007 9:07 am |
 |
 |
hackapple
Joined: 20 Aug 2007 Posts: 1
|
|
Hard game |
|
I began to feel or interesting, and slowly continue to play, I feel it will be difficult to move with the brain.
Carefully look at, no clue. Many thought, but also want to point out things.
|
|
Mon Aug 20, 2007 2:13 am |
|
 |
alina

Joined: 25 Aug 2007 Posts: 242 Location: DarkNet |
|
Re: Hard game |
|
 |
 |
I began to feel or interesting, and slowly continue to play, I feel it will be difficult to move with the brain.
Carefully look at, no clue. Many thought, but also want to point out things. |
i found it the same ..it is quite nice.. 
|
|
Sat Aug 25, 2007 5:53 pm |
|
 |
gfoot
Joined: 05 Sep 2007 Posts: 269 Location: Brighton, UK |
|
|
|
 |
 |
It seemed to hang for quite a while (maybe 10 seconds) on lvl504 for some reason. Must have been a particularly difficult one. 513 however was solved in about a second (after it had been downloaded). |
It's an interesting problem, because you can get to various stages with progressively more scalable algorithms, and it's not always a matter of starting from scratch - in some cases the tweaks were relatively minor.
I'm now in a position where I can solve any puzzle in under 1.5 seconds. Only three of the 513 levels take longer that 1 second, and I can solve all of them (from predownloaded copies) in under a minute. It's a shame the server can't produce bigger boards - I'm wondering how far my algorithm actually would scale now.
Interestingly, I got to level 511 on an NP algorithm (refactored on level 98, and optimised to reduce memory usage by level 200) - some levels took a while, though (e.g. 5/20/40 minutes). Level 511, however, took over a day and still didn't get a solution - something about that one was particularly stressing my algorithm's lack of scalability.
It was only a relatively simple change to one of the lower level routines to get it to the point it's at now. I think that's what's interesting here - relatively simple tweaks to the algorithm can have such dramatic (and visible) effects.
Level 504 came about 15th for me, in terms of time taken, and 512/513 are the top two. It's interesting if different "good" algorithms have trouble on different levels - I guess it could be down to either randomization of generated levels, or fairly arbitrary preferences in the algorithms (e.g. prefer longer or shorter solutions, prefer horizontal before vertical moves).
In case it's of any interest, my solver is written in Python (which I'm not very experienced with), with a shell script harness to fetch pages and submit the solutions the script works out. Python's not the fastest language in the world, but I agree with points others have made - it's mostly about the algorithm, not the language. However, bad use of any language can cause terrible performance - especially when it comes to data structures.
|
|
Fri Sep 07, 2007 11:28 pm |
|
 |
Captain Segfault
Joined: 05 May 2007 Posts: 67 Location: San Carlos, CA |
|
|
|
 |
 |
Interestingly, I got to level 511 on an NP algorithm |
Nitpick: algorithms aren't NP. Languages/problems are NP. NP does not mean "non polynomial". 
|
|
Sat Sep 08, 2007 8:02 pm |
 |
 |
falcon2424
Joined: 30 Apr 2007 Posts: 30
|
|
|
|
I'm kind of curious how other people solved this and got their algorithms to be so fast.
I know that some of the key components of mine were a bit of pre-processing on the entire board to identify unreachable squares. Then I 'collapsed' the board for each of the possible legal ending points of a single iteration of a solution.
Did everyone else use something like this, too?
|
|
Sun Sep 23, 2007 5:18 pm |
|
 |
gfoot
Joined: 05 Sep 2007 Posts: 269 Location: Brighton, UK |
|
|
|
I didn't bother identifying unreachable areas - it was no gain for me. My algorithm would have given up before looking at them anyway.
I think you're already doing roughly the same things as me. The operations are all pretty cheap, and it scales well. I'd be interested to hear if anyone has anything better. In practice I think board size doesn't bother it much, but sequence length ends up most significant.
[edit: cut out specific solution information]
Last edited by gfoot on Mon Nov 03, 2008 11:38 pm; edited 1 time in total |
|
Tue Oct 09, 2007 7:59 pm |
|
 |
Conkers_bfd
Joined: 12 Nov 2007 Posts: 1
|
|
|
|
Got to 100 by hand, and now it doesnt let me see the board?
|
|
Tue Nov 13, 2007 2:49 am |
|
 |
V4hn
Joined: 27 Nov 2007 Posts: 14
|
|
|
|
GOTCHA!
Quite optimized C++ with an bash-interface for down-/uploading
I started using a simple recursive BF 'till Level 100.
Optimized it by implementing BF iterative and adding preprocessing of the map 'till Level 161
Then made up a completely new - iterative - algorithm - just reused the preprocessing of the map
and implemented some more small improvements..
If the number of levels in here will go beyond 700, I may think about some other improvements,
which will start to be useful by that level . But 'till then,
go on playing with your code
V4hn
remark _for_ the moderators: i think this thread gives away too much information
on the well-scaling algorithms, even when i read it after coding mine...
may someone removes at least some of the information given?
After all it takes a lot of fun out of the coding, if you know exactly what to do..
_________________
 |
|
Wed Feb 13, 2008 9:04 pm |
|
 |
<<D.A.>>
Joined: 15 Aug 2007 Posts: 647 Location: nowhere |
|
Re: Runaway Robot Puzzle |
|
 |
 |
 |
 |
http://www.hacker.org/runaway/index.php?name=<username>&password=<password>&path=DRR |
|
i have a little problem with logging in... there are special symbols in my username, < and >, which result in incorrect username... is there any solution to such a problem??
|
|
Thu May 15, 2008 8:47 pm |
|
 |
Allosentient
Joined: 10 Apr 2008 Posts: 273
|
|
|
|
Hello,
Replace < with %3C
Replace > with %3E
If there is a way to fix it on your end, that is what will work.
You can find a complete chart here:
http://www.ascii.cl/htmlcodes.htm
Best of luck!
|
|
Thu May 15, 2008 10:04 pm |
|
 |
Hephaestus
Joined: 17 May 2008 Posts: 5
|
|
|
|
I havent actually quite finished all the levels just yet - chuggin away around 470 right now - but i think itll make it sometime today. I used a similar solution to gfoot and falcon2424 (preprocess board and then make small compressed boards from various possible instruction lengths). But I have this weird problem - some take about 16 milliseconds not counting download, and most are under a second, but some random ones take upwards of 10-20 mins for no apparent reason. Did anyone else get that or is it some obscure bug in my code?
|
|
Thu May 29, 2008 9:28 am |
|
 |
The_Dark_Avenger
Joined: 11 Jun 2008 Posts: 115
|
|
|
|
 |
 |
Hello,
Replace < with %3C
Replace > with %3E
If there is a way to fix it on your end, that is what will work.
You can find a complete chart here:
http://www.ascii.cl/htmlcodes.htm
Best of luck! |
well, for forums it works, but here doesn't... had to use ultimate solution 
|
|
Wed Jun 11, 2008 11:54 pm |
|
 |
s_e_m_u_d
Joined: 25 Nov 2008 Posts: 3 Location: jakarta-batam.indonesia |
|
|
|
 |
 |
damn ... i dont understand... |
idem za... 
_________________ SEMUD HAS ENTERED |
|
Tue Nov 25, 2008 6:15 am |
|
 |
osterlaus
Joined: 02 Nov 2008 Posts: 20
|
|
|
|
 |
 |
remark _for_ the moderators: i think this thread gives away too much information
on the well-scaling algorithms, even when i read it after coding mine...
may someone removes at least some of the information given?
After all it takes a lot of fun out of the coding, if you know exactly what to do.. |
I agree to you: Here are some hints given. But I'd like to discuss alternative solving strategies with you as I had come to level 166 with my algorithm - but it's getting very slow now and having found a solution for the last levels seems to contain some luck...
|
|
Wed Dec 31, 2008 10:57 am |
 |
 |
|