Announcement: Be excellent to each other.


Caravel Forum : Caravel Boards : General : brute force puzzle solver for TCB Echo Chasms : 1 South, 2 East (Perhaps this is overkill...)
New Topic New Poll Post Reply
Poster Message
prce
Level: Roachling
Rank Points: 14
Registered: 09-30-2009
IP: Logged

File: DROD.py (6.5 KB)
Downloaded 106 times.
License: Public Domain
icon brute force puzzle solver for TCB Echo Chasms : 1 South, 2 East (+3)  
...but I was frustrated by this room. (Apparently graduate school has caused my spatial/Tetris skills to desert me.) And no one else seems to have had any trouble, since there's no Hints and Solutions thread on this topic.

How frustrated did I get?

See attached. (Sorry about the Very Ugly Code!) Since there are 46,809,527,353,344 possible combinations of upper-left X,Y coordinates for the pieces, I had to preselect, first by checking the 2,187 different combinations of Y-coordinate for overruns (which took a few moments to run), then the 1,337,720,832 combinations of X-coordinate (which took about 18 hours on one core of my desktop.) It boiled down to 62 x 1,236 = 76,632 possibilities, 0.000000164% of the original possibility space. Checking these for overlaps, in two dimensions, took about a minute.

Everybody else probably solved it just by looking at it. But DO YOU KNOW...

Click here to view the secret text


OK, one more secret room before the master wall comes down.
09-30-2009 at 12:37 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
Tahnan
Level: Smitemaster
Avatar
Rank Points: 2467
Registered: 11-14-2005
IP: Logged
icon Re: brute force puzzle solver for TCB Echo Chasms : 1 South, 2 East (+1)  
There actually is a thread about the room, but I forget what the weird restrictions are on searching for them if you don't have CaravelNet.

As a Python script-writer myself, I'll be interested to take a look at this, just as soon as I have a moment to breathe again.
09-30-2009 at 08:27 AM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
zwetschenwasser
Level: Master Delver
Avatar
Rank Points: 200
Registered: 05-22-2007
IP: Logged
icon Re: brute force puzzle solver for TCB Echo Chasms : 1 South, 2 East (-1)  
I think it involves

____________________________
Currently working on GaTEB and KDD (never finished the silly thing). :yahoo:
10-03-2009 at 04:59 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
prce
Level: Roachling
Rank Points: 14
Registered: 09-30-2009
IP: Logged
icon Re: brute force puzzle solver for TCB Echo Chasms : 1 South, 2 East (0)  
Tahnan: oh right... it uses that ": Secret Room" style. Thanks! I'll cross-post this thread over there.
10-04-2009 at 12:43 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged
icon Re: brute force puzzle solver for TCB Echo Chasms : 1 South, 2 East (-1)  
You are not alone. My program for this room was a lot faster though as far as I remember. But your achievement is still very good for an average man.

PS This is only the tip of the iceberg. Computers with some human help are capable to find very effective solutions for a lot of rooms. That is the place where the dark side of the DROD is hiding in.
10-09-2009 at 11:10 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
Pekka
Level: Smiter
Rank Points: 302
Registered: 09-19-2007
IP: Logged
icon Re: brute force puzzle solver for TCB Echo Chasms : 1 South, 2 East (+1)  
I think the average man is too preoccupied with having slightly less than two legs to bother with writing programs like this at all. (Or should you say fewer here? We're talking about only a tiny fraction of a leg that is missing after all.)

Anyway, for a solution that is efficient when considering the running time of the program, you probably should look at the wonderfully named Algorithm X. It can be implemented by making links dance.

http://en.wikipedia.org/wiki/Dancing_Links

However, we might assume that pcre was rather more interested in optimizing the programmer's time instead of the program's running time. He could have, for example, used those few trifling hours the program took to run to do something useful, such as solving other rooms.

You could also make a fairly effective solution by checking all the 10! possible permutations of the pieces with a suitable search algorithm, like depth-first. Ideally we can even implement pruning in the search.

I have in fact solved a similar puzzle having more pieces with this method, and it didn't take too long. You have to make up some rule which assigns a one-one relation between permutations and placements of the pieces--for example using some ordering of all the possible squares the pieces may touch. I shall leave this, as they say, an exercise to the reader.

10-09-2009 at 08:10 PM
View Profile Show all user's posts This architect's holds Quote Reply
New Topic New Poll Post Reply
Caravel Forum : Caravel Boards : General : brute force puzzle solver for TCB Echo Chasms : 1 South, 2 East (Perhaps this is overkill...)
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.9
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.