prce
Level: Roachling
Rank Points: 14
Registered: 09-30-2009
IP: Logged

File: DROD.py (6.5 KB)
Downloaded 106 times.
License: Public Domain

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



OK, one more secret room before the master wall comes down.

Tahnan
Level: Smitemaster

Rank Points: 2467
Registered: 11-14-2005
IP: Logged

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.

zwetschenwasser
Level: Master Delver

Rank Points: 200
Registered: 05-22-2007
IP: Logged

I think it involves

____________________________
Currently working on GaTEB and KDD (never finished the silly thing).

prce
Level: Roachling
Rank Points: 14
Registered: 09-30-2009
IP: Logged

Tahnan: oh right... it uses that ": Secret Room" style. Thanks! I'll cross-post this thread over there.

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

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.

Pekka
Level: Smiter
Rank Points: 302
Registered: 09-19-2007
IP: Logged

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.