hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Sample Solving Algorhythm

 
Reply to topic    hacker.org Forum Index » Runaway Robot Puzzle View previous topic
View next topic
Sample Solving Algorhythm
Author Message
MaxistXXL



Joined: 20 Nov 2007
Posts: 13
Location: Earth

Post Sample Solving Algorhythm Reply with quote
Hi,
I was wondering, if you could post a programm like in the other challanges.
I wrote 750 lines of perl, but sometimes it wont find a path (currently at level 90...). I mean, thats live, no problem, but, aehm, debugging is extremely hard, if I dont know when it should find a path, and when it is correct, not to find one...

Maybe I'll write a brute-force-algo, but maybe you can offer a slightly better one Very Happy.

greetings:
der Maxist

_________________
War is terrorism, but with a higher budget.
Mon Jan 07, 2008 10:58 pm View user's profile Send private message
MaxistXXL



Joined: 20 Nov 2007
Posts: 13
Location: Earth

Post Reply with quote
Ok, i did it...
Its Perl, and it is fucking bruteforceing. Its made to show ONE solution, not all, so, if it needs some hours, its not a problem for me. Btw, if it would be more complex, noobs could steel it Very Happy.

If you just want to have a tool which gives you one solution for debugging, feel free to use this.
Dont forget to change YOURNAME and YOURPASSWORD...

Code:
#!/usr/bin/perl
use strict;
use warnings;

#Benoetigte Variablen:
my @levelinfo;
my ($tempstring, $pfad);
my $i;
&website_auslesen("");

$i = 0;
$levelinfo[3] += 2;
$levelinfo[4] += 2;
$tempstring = "X"x$levelinfo[3];
for (1..($levelinfo[4]-2)){
 $tempstring .= "X".substr($levelinfo[0], $i, $levelinfo[3]-2)."L";
 $i += $levelinfo[3] - 2;
}
$tempstring .= "X"."L"x($levelinfo[3]-2)."X";
$levelinfo[0] = $tempstring;


$i = $levelinfo[2];
do{
 print "$i\n";
 $pfad = "."x$i;
 $tempstring = &bruteforce($pfad);
 $i++;
}while($tempstring eq "falsch");
print "$tempstring\n";

sub bruteforce{
 my $tempstring;
 my $pfad = $_[0];
 my $i = index($pfad, "\.");
 if($i > -1){
  substr($pfad, $i, 1) = "R";
  $tempstring = &bruteforce($pfad);
 }else{
   $tempstring = &verifizieren($pfad);
   if($tempstring eq "falsch"){return $tempstring;}
   else{return $pfad;}
 }
 if($tempstring ne "falsch"){return $tempstring;}
 else{
  substr($pfad, $i, 1) = "D";
  $tempstring = &bruteforce($pfad);
  return $tempstring;
 }
}

sub verifizieren{
 my ($mom_x, $mom_y) = (1, 1);
 my $zaehler = -1;
 do{
  $zaehler++;
  if($zaehler == length($pfad)){$zaehler = 0;}
  if(substr($_[0], $zaehler, 1) eq "R"){$mom_x++;}
  elsif(substr($_[0], $zaehler, 1) eq "D"){$mom_y++;}
 }while(substr($levelinfo[0], $mom_y*$levelinfo[3]+$mom_x, 1) eq ".");
 if(substr($levelinfo[0], $mom_y*$levelinfo[3]+$mom_x, 1) eq "X"){return "falsch";}
 else{return "richtig";}
}

sub website_auslesen {
 use LWP::Simple; #Packet, um den HTML-Inhalt auszulesen, initialisieren
  my $htmlinhalt = get("http://www.hacker.org/runaway/index.php?name=YOURNAME&password=YOURPASSWORD")
   || die "KANN WEBSITE NICHT OEFFNEN"; #auslesen des HTML-Inhaltes
  my $zahl = index($htmlinhalt, "FVterrainString=");
  my $zahl2 = index($htmlinhalt, "\"", $zahl) - $zahl;
 $htmlinhalt = substr($htmlinhalt, index($htmlinhalt, "FVterrainString="), $zahl2);
 @levelinfo = split("&", $htmlinhalt);
 foreach $zahl (0..$#levelinfo) {
  $levelinfo[$zahl] = substr($levelinfo[$zahl], (index($levelinfo[$zahl], "=") + 1));
 }
}


_________________
War is terrorism, but with a higher budget.
Tue Jan 08, 2008 12:01 am View user's profile Send private message
antirem



Joined: 29 Dec 2008
Posts: 10

Post Reply with quote
dyam.. thats a nice piece for that..


what level did you get to?

_________________
please dont use DD-WRT
Hacker - One who is proficient at using or programming a computer; a computer buff
Mon Dec 29, 2008 6:11 am View user's profile Send private message
Chocoholic



Joined: 16 Feb 2009
Posts: 44
Location: UK

Post Scheme Reply with quote
Just in case someone is interested, here's a recursive backtracking algorithm written in Scheme.

That language is great, it's by far the most elegant one I know! It's dangerous though, if you have to write something in Java (or a similar language) later on, you easily get frustrated that everything is so complicated and the result is goddamn ugly.

As for the algorithm: it's a very simplistic version of what i'm using at the moment and implements no optimisation whatsoever. The playfield parameter is an array of booleans, where true means a blocked field. The rest should speak for itself.

Code:
; solve by trial and error (backtracking)
(define (solve playfield w h minlen maxlen)
  (define (fail? solution full-solution x y)
    (cond ((null? solution)
           (fail? full-solution full-solution x y))
          ((or (>= x w) (>= y h)) #f) ; win
          ((vector-ref (vector-ref playfield y) x) #t) ; sucks
          ((= (car solution) 1)   ; 1 = D
           (fail? (cdr solution) full-solution x (+ y 1)))
          (else   ; 0 = 'R
           (fail? (cdr solution) full-solution (+ x 1) y))))
  (define (solve-iter solution n)
           (let ((rev (reverse solution)))
             (cond ((and (>= n minlen)
                         (not (fail? rev rev 0 0))) rev)
                   ((< n maxlen)
                    (or (solve-iter (cons 0 solution) (+ n 1))
                        (solve-iter (cons 1 solution) (+ n 1))))
                   (else #f))))
      (or (solve-iter '(0) 1) (solve-iter '(1) 1)))


Edith says: made code prettier
Sun Mar 29, 2009 1:25 am View user's profile Send private message ICQ Number
megabreit



Joined: 03 Jan 2009
Posts: 141

Post Reply with quote
Please don't "inspire" adum to introduce another programming language into the challenge arena. Shocked
The "boiling point" was Ada... but Scheme would be even stranger... it looks a bit like Lisp but with less brackets...
I mean... nothing against Scheme... it might perfectly fit your needs... but I simply won't see ANY programming language in the challenges Laughing

BTW: How long did your solver take? I'm using a similar backtrack approach (in another programming language) but without recursion. My solver took about 5 min to solve level 100... I just want to estimate the runtime.

Edit: No answer necessary... I read some more posts in the forum and know now what to expect. My solver is slowing down rapidly. But I also got some ideas on how to improve my solver... even though I don't think that I could make it as fast as gfoot's.
Tue Apr 07, 2009 10:25 pm View user's profile Send private message
Chocoholic



Joined: 16 Feb 2009
Posts: 44
Location: UK

Post Reply with quote
megabreit wrote:
Please don't "inspire" adum to introduce another programming language into the challenge arena. Shocked
The "boiling point" was Ada... but Scheme would be even stranger... it looks a bit like Lisp but with less brackets...
I mean... nothing against Scheme... it might perfectly fit your needs... but I simply won't see ANY programming language in the challenges Laughing

Actually... that's a FABULOUS idea! If some nasty Schemeish thing pops to my head in near future I'll mail it to adum. Thanks. Very Happy

Oh and by the way scheme interpreters are muuuch easier to come by than an Ada compiler. Or well... maybe not, seen as both present in some linux distribution's repositories.
Sun Apr 12, 2009 7:14 pm View user's profile Send private message ICQ Number
gfoot



Joined: 05 Sep 2007
Posts: 269
Location: Brighton, UK

Post Reply with quote
I thought "Cons Car" was in Scheme, but I know very little LISP so it doesn't make much difference to me.
Sun Apr 12, 2009 11:42 pm View user's profile Send private message
mazetto



Joined: 16 Apr 2009
Posts: 1
Location: indonesia

Post Reply with quote
Sad
Thu Apr 16, 2009 1:35 am View user's profile Send private message Visit poster's website Yahoo Messenger
megabreit



Joined: 03 Jan 2009
Posts: 141

Post Scheme vs. Lisp Reply with quote
I'm not sure about the difference between Scheme and LISP. There was only one occasion in the past I had to deal with LISP and never saw Scheme in the wild. I solved "Cons Cars" with LISP documentation and interpreter, so I'm pretty sure that it was LISP... but why not ask the author (if known)?
Tue Apr 21, 2009 8:05 pm View user's profile Send private message
blablaSTX



Joined: 17 Aug 2009
Posts: 11

Post Reply with quote
scheme vs. Lisp:
Scheme is a lisp with guaranteed tail-call elimination, guaranteed continuation support and a few other nice semantic highlights. The syntax is lisp (aka functions with parens around). btw. the number and usage of parens is the same, so megabreit probably had too much of dope when looking at the code (Wink. It is actually a lot of fun to program in scheme, but occasionally hard to read if you are not used to it. But every hacker should know it - the insight you gain into computing is really worth the effort (and continuations are a fantastic invention - look at the seaside web framework...)

recursive brute force backtracking:
brought me roughly to level 140 with reasonable (an hour or so) computation time (using smalltalk). then, a new algo was needed to "break the sound barrier".
I guess, your milage might vary, but somewhere between 100 and 150, everyone will encounter that limit - no matter which language and optimizations you use (hand tuning your c or asm code will only give you a few levels more - so it is not worth the effort)

edith: a typo
Mon Aug 31, 2009 12:38 am View user's profile Send private message Visit poster's website
silvermane2



Joined: 19 Apr 2010
Posts: 1

Post Reply with quote
Yo what up community I need some help.....been with this since olden days with programming and ms dos....and back doors....
Mon Apr 19, 2010 4:30 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Runaway Robot Puzzle 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.