Stefan
Level: Smitemaster

Rank Points: 2119
Registered: 05-25-2004
IP: Logged

File: OrbBanger_DH.java (6.1 KB)
Downloaded 97 times.
License: Public Domain

Atch wrote:
Thanks too to Stefan, you must be a supreme programmer, but why are you keeping your program to yourself? It wouldn’t mean anything to me but surely others would be interested. I had envisaged something like 25^25 iterations taking many thousands of billions of years to compute.

No, I'm not a supreme programmer (far from it), but I took a bit of a different approach to the problem (well, to the implementation anyway). The application takes about 3 hours to run (for this particular puzzle), but if the solution had involved more than 8 orb strikes, it would have taken much, much longer.

The reason I've been keeping the program to myself is primarily because it isn't user-friendly. At all. The information about the doors and orbs is hard-coded into the program... (of course, it doesn't have to be that way, but I'm too lazy to do anything about it) Edit: Needless to say, I haven't used it very often. I originally created it to solve the orb puzzle in The Fool's Errand, and I've used it maybe seven times since.
However, if someone is interested in looking at the code, I'm attaching it here (I beautified the code a bit, and added some comments). This isn't really a release, because it's quite useless unless you know how to modify and compile it. Do whatever you like with it.

____________________________
0.099³

---

[Last edited by Stefan at 03-31-2006 04:15 PM]

RoboBob3000
Level: Smitemaster

Rank Points: 1980
Registered: 10-23-2003
IP: Logged

Atch wrote:

RoboBob3000 wrote:
Just eyeballing this, I think I see a solution.

This is unbelievable RoboBob, I stand in awe!

Heh, it was mostly a lucky break on my part, thanks to the way you formatted your list in your post. I usually approach orb puzzles by first looking for candidates for which orb needs to be struck last, that is to say, orbs that don't close any doors. It just so happened that all of the orbs on the right side of your list (except for the one that closed the final three doors) had this property. I also noticed that none of those particular orbs opened any doors. Glancing through them, I saw that they toggled each door exactly once, provided that orb #9 was struck early enough. I surprised myself at how easily the solution was obtained as well.

My guess is that since the required orbs were evenly spaced (and because there are 25 levels in his hold) that there is some sort of clue suggesting that you do what you do somewhere. What does that scroll in the middle say?

I'm crummy at chess, but good at getting lucky. And if it earns me a +7, I'm not complaining.

____________________________
http://beepsandbloops.wordpress.com/

Atch
Level: Delver
Rank Points: 81
Registered: 08-29-2003
IP: Logged

RoboBob3000 wrote:
What does that scroll in the middle say?

The scroll in the middle of the orbs says:

I present to you:
The Twenty-five Gates
of the Red Hawk

So, no clues to the orb puzzle.

The one by the stairs says:

You have completed Deep Hold!
Brave Smitemaster, you have come
through many perils and survived.
I bestow upon you

THE ORDER OF
THE RED HAWK

Perhaps I’ll get a badge.

cchittleborough
Level: Delver
Rank Points: 32
Registered: 06-27-2004
IP: Logged

File: SolveOrbs.pl (6.3 KB)
Downloaded 89 times.
License: Public Domain

Here's my Perl program for solving orb puzzles. Note the super-original name. Windows users will need to download ActivePerl from www.activestate.com; it's big, but smaller than Java. It's a command line tool, so you probably want to open a command window in the directory containing SolveOrbs.pl. If you type

perl SolveOrbs.pl

it will output a terse description of how to use it (written in programmer jargon, I'm afraid). Feel free to hack on it.

____________________________
-- Chris[topher] Chittleborough

silver
Level: Smitemaster
Rank Points: 915
Registered: 01-18-2005
IP: Logged

cchittleborough wrote:
Here's my Perl program for solving orb puzzles.

I wrote one or two perl programs over the ages to solve orb rooms, but always considered the code throwaway (and apparently did do so).

didn't bother with using "vec" to store doors, just used bit operations on binary numbers. rather, I did everything just the way I'd do it in C:

1) I represent the doors as a single number, a bunch of bits.
2) I use '0' for open and '1' for closed, because it makes the loop condition very simply "while ($doors) { ... }"
3) I turn each orb into three bitmasks:
a) I build an "and" mask like this:
bit X is 0 if the orb opens door X
bit X is 1 if the orb closes, toggles, or has no effect
b) I build an "or" mask like this:
bit X is 1 if the orb closes door X
bit X is 0 if the orb opens, toggles, or has no effect
c) I build an "xor" mask like this:
bit X is 1 if the orb toggles door X
bit X is 0 if the orb opens, closes, or has no effect

now each try of an orb is just the application of the 3 masks:
$doors &= $bitmasks[$orb]{'open'}
$doors |= &bitmasks[$orb]{'close'}
$doors ^= &bitmasks[$orb]{'toogle'}

the perl version isn't amazing, but the C version would fly.


____________________________

---

[Last edited by silver at 04-03-2006 05:47 AM]

david-r-emett
Level: Goblin
Rank Points: 17
Registered: 02-14-2006
IP: Logged

File: orb-solver.zip (53.4 KB)
Downloaded 111 times.
License: Public Domain

Thought I would contribute my orb solving program. It's written in C++ and uses a similar way of storing orbs to what silver suggested, however, you only need an or and xor bitmask if you apply the or first:

------ or xor
close: 11 (opens then toggles :)
open : 10
toggl: 01
nothn: 00

It uses a practically brute force method, but is guaranteed to return the shortest orb sequence (well, one of them). It solves the 25-gate problem in 22 seconds on my machine (a64 3000+), using something like 200-300MBs of memory :D

edit: now stops once it finds solution (takes 3 seconds now for 25 gates on my machine)

---

[Last edited by david-r-emett at 04-06-2006 03:00 AM]

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

File: OrbSolver.exe (96 KB)
Downloaded 507 times.
License: Public Domain

Here's another one. It uses an efficient algorithm (something like O(n^2.5)) that systematically solves the problem, rather than doing a brute force search, so it's very fast. (The 25 gate problem takes a split second.) It's written in VC++ .NET, so I'm afraid it'll only work on Windows. Maybe someone could build a version for other platforms - Only the I/O uses Windows stuff, so it should be easy enough. If anyone's interested in the source, for whatever reason, I'll be happy to tidy it up a bit and post it. Please just ask. I don't mind at all, but I do mind doing it if no-one's going to even look at it.

Using the program:
It's a stand-alone .exe, so just put it anywhere and run it.
Enter the initial orb configuration in the format OCCOOC... (Not case-sensitive.)
Ditto the target configuration.
Orb actions are entered as follows: (using Open, Close, Toggle and Leave).
-You can type something like O1 C3 T5 O6 4 C7 8, which would mean open 1, 4 and 6, close 3, 7 and 8, and toggle 5. (So you don't have to repeat symbols, and the numbers can appear in any order. You can also leave spaces or not, and it's not case-sensitive.)
-You can also type something like OLCOTOCC for the same effect, but generally, the first format is much more convenient.
-Each orb must go on a separate line. You can leave blank lines, but you can't break an orb's line.

I think you get the idea, but just say if it's not clear. Please let me know if there's a problem. Comments and suggestions welcome.

The algorithm:
I'm only giving a brief outline. Again, just ask if you'd like more detail. The basic idea is that we can repeatedly reduce the puzzle to a smaller one by finding an orb (or combination of orbs) we may as well hit last, removing doors corresponding to Os and Cs from the problem, and toggling target entries corresponding to Ts. What's more, finding such an orb is a matter of solving a system of linear equations.
More exactly: Let's call an orb "good" if it contains at least one O or C, and every O or C is equal to the corresponding entry in the target. Call it "bad" if it has some O or C that does not equal the corresponding entry in target. Otherwise (i.e. when it contains no Os or Cs), call it "ugly" (it's an appropriate term.)
Now, assume there is a solution:
First, suppose there is a good orb: There's no harm in appending a good orb to any solution (we may have to hit it twice to eliminate it's toggles). On the other hand, if we're going to hit it last, we can remove doors corresponding to Os and Cs, since this last hit is going to fix them. So (remembering to toggle target entries corresponding to Ts) the problem reduces to a smaller one.
Otherwise, maybe we can solve the whole problem in one go using only the ugly orbs. There is such a solution if and only if the matrix equation Ax = I+T has a solution modulo 2, where the columns of A are the ugly orbs (with Ls changed to 0s and Ts changed to 1s), I is the initial configuration (with Os changed to 0s and Cs to 1s) written as a column vector, and T, similarly, the target configuration. This equation is easily solved using Gauss-Jordan elimination.
Otherwise, there must be some bad orb that can be turned into a good orb by following it with some ugly orbs. (Just consider any solution: There are no good orbs, not all orbs are ugly, so take the last bad orb. If the orbs following it don't turn it into a good orb, the solution isn't a solution after all.) Again, we can find such a bad orb by solving the equation A'x=B'+T' for every bad orb B, where A and T are as before, except that rows corresponding to Ls and Ts of B are removed, and B' is B with Ls and Ts removed, Os changed to 0s, and Cs changed to 1s.
So, in all cases we can either solve the problem directly, or reduce it to a smaller problem. (Note that bad orbs can become good in the smaller problem etc.)

That's the gist of it. I'm working on a version of the program that will show all possible solutions, if anyone's interested. (It's mainly just a matter of it not stopping when it finds a solution.)


EDIT: Update. Fixed a potential memory problem.
EDIT: It's written using .NET 1.1. Sorry if that's bad.

---

[Last edited by michthro at 04-05-2006 08:45 AM]

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

File: RedHawks25.txt (402 bytes)
Downloaded 186 times.
License: Public Domain

Oh, I forgot to mention you can save your work etc. For convenience, I'm attaching the input for the 25 orb puzzle. Just open it with the program, click "Solve", and read off the solution at the bottom.

coppro
Level: Smitemaster
Rank Points: 1309
Registered: 11-24-2005
IP: Logged

Any source code?

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

OK, I'll post the source tomorrow sometime.

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

File: OrbSolver.zip (17.4 KB)
Downloaded 107 times.
License: Public Domain

Here's the source. I didn't bother too much, but I did add some comments. I'm new to .NET, so I'd be very grateful if someone would tell me what the .NET equivalent of SendMessage(...) is. I'm also not too confident that I used the .NET string stuff the best possible way.
Otherwise, I don't think it would be worth adding an all solutions function, or even minimal solutions, since finding a minimal solution looks like (in the worst case, when all orbs are ugly) an exponential problem, so you can't do better than brute force (except that you know there will be no repetitions, and order doesn't matter, but it's still of exponential order). It would be interesting to have a proof one way or the other, though.

Atch
Level: Delver
Rank Points: 81
Registered: 08-29-2003
IP: Logged

Re: michthro’s OrbSolver

This is wonderful stuff michthro, thank you very much, it gives us an insight into the mind that is currently achieving so many high scores on Caravel.net. Orb puzzles are now defunct – aren’t they?

I ran Red Hawk’s 25-gate problem and, as you say, the solution was instantaneous but what you failed to mention was that it is not the eight-orb solution that we have had from RoboBob and Stefan but an alternative fourteen-orb one – 15, 12, 8, 6, 2, 22, 2, 20, 19, 16, 11, 1, 18, 3 (it does work). It would be interesting to see your development of the program to pick out other solutions.

You said: put the program anywhere and run it but I kept on getting the error message: R6029: Application cannot run in active version of Microsoft.NET Runtime until I put it in the directory: WINDOWS\\Microsoft.NET\\Framework (with version 1.1).

Well, I’m off to zap a few more of those old orb puzzles.

Syntax
Level: Smitemaster
Rank Points: 1218
Registered: 05-12-2005
IP: Logged

Well you've obviously gotta uninstall .net before running any .net file s)

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

Atch wrote:
Orb puzzles are now defunct – aren’t they?

Well, the program will quickly solve any orb puzzle that an architect (however devious) can fit into a DROD room. As you noticed, it won't necessarily give you a minimal solution. The thing is, finding a minimal solution is a problem that simply can't be solved quickly (I suspect, though I'm working on settling this issue). So let's say you come across another 25-gate problem. If you want a minimal solution, you can try one of the brute force programs (I'd suggest david-r-emmett's). If the solution doesn't require too many orb hits, you'll get your answer. However, if the solution requires at least, say, 15 orb hits, it's going to take days/months/years, if not something ridiculous like much longer than the lifetime of the universe. In such a case my program will at least give you some solution quickly, which is the main thing. Anyway, I'll make it optionally look for minimal solutions, but before I add brute force stuff, I'd like to make sure it's really necessary.

You said: put the program anywhere and run it but I kept on getting the error message: R6029: Application cannot run in active version of Microsoft.NET Runtime until I put it in the directory: WINDOWS\\Microsoft.NET\\Framework (with version 1.1).

Sorry about that. I'm not very clued up on what all can go wrong with .NET programs. All I know is that a lot can go wrong. I'll edit in that it uses version 1.1. Thanks for mentioning this.

silver
Level: Smitemaster
Rank Points: 915
Registered: 01-18-2005
IP: Logged

AAAARGH!

I had just wrapped up a C implementation of my solver and then went to remove my emacs backup files with "rm *~" but I didn't notice the ~ key was sticking until after I hit return.

the solver part of my program was pretty simple, but I had a couple hundred lines of code to parse files containing puzzle setups :/

(of course, I was just writing a plain text file on a linux system and compiling with gcc, so the resulting program was only going to be of use to linux geeks, anyway :/ )


____________________________

david-r-emett
Level: Goblin
Rank Points: 17
Registered: 02-14-2006
IP: Logged

micthro:
actually, the running time of my program is fairly unrelated to the number of orb hits in the solution, it will find a 20 orb-hit solution just as fast as it will find an 8 orb-hit solution (while solving the 25-gate problem, it covers the entire 2^25 possible door states) [edit: ok this isnt quite true now because it now stops once it has found a solution]. however, it does have running time (and memory usage) proportional to 2^numdoors * numorbs, so if some really evil architect made an orb puzzle with just a few more doors it would crumble (and no that isnt a challenge ). excellent job on the efficient orb-solver btw

silver:
unlucky . i dont know if theres an equivalent app for linux (never used it much myself), but i keep "pci file recovery" installed for when i accidentally delete stuff http://www.pcinspector.de/file_recovery/uk/download.htm

---

[Last edited by david-r-emett at 04-06-2006 03:03 AM]

Briareos
Level: Smitemaster

Rank Points: 3516
Registered: 08-07-2005
IP: Logged

silver wrote:
(of course, I was just writing a plain text file on a linux system and compiling with gcc, so the resulting program was only going to be of use to linux geeks, anyway :/)

Never misunderoverestimate the usefullness of Cygwin...

____________________________
"I'm not anti-anything, I'm anti-everything, it fits better." - Sole
R.I.P. Robert Feldhoff (1962-2009)

Insane
Level: Master Delver

Rank Points: 154
Registered: 08-06-2005
IP: Logged

Have fun using your orbsolvers in a room in my upcoming hold.
It features an orb puzzle with no less than 280 orbs and 109 doors.

It's fairly easy if you know the trick though, while the orb-solver programs would go cocobananas .

Also, many thanks to michthro's OrbSolver.exe program.
I used it to test every single orb puzzle in the complete level for possibility, without having to frustrate at it myself, and so I can write down the shortest possibility for personal use during testing .

-Insane

NiroZ
Level: Smitemaster
Rank Points: 1302
Registered: 02-12-2006
IP: Logged

Insane wrote:
Have fun using your orbsolvers in a room in my upcoming hold.
It features an orb puzzle with no less than 280 orbs and 109 doors.

It's fairly easy if you know the trick though, while the orb-solver programs would go cocobananas .

Also, many thanks to michthro's OrbSolver.exe program.
I used it to test every single orb puzzle in the complete level for possibility, without having to frustrate at it myself, and so I can write down the shortest possibility for personal use during testing .

-Insane

I don't know what your hold is, but you just managed to scare me away from ever playing it.

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

If all orbs can be always reached, the polynomial algorithm were suggested somewhere above. Make sure this is not the case .

Insane
Level: Master Delver

Rank Points: 154
Registered: 08-06-2005
IP: Logged

File: 208orbs.png (122.5 KB)
Downloaded 1381 times.
License: Public Domain

NiroZ wrote:

Insane wrote:
Have fun using your orbsolvers in a room in my upcoming hold.
It features an orb puzzle with no less than 280 orbs and 109 doors.

It's fairly easy if you know the trick though, while the orb-solver programs would go cocobananas .

Also, many thanks to michthro's OrbSolver.exe program.
I used it to test every single orb puzzle in the complete level for possibility, without having to frustrate at it myself, and so I can write down the shortest possibility for personal use during testing .

-Insane

I don't know what your hold is, but you just managed to scare me away from ever playing it.

I can give you nightmares if I want.



-Insane

---

[Last edited by Insane at 03-16-2007 02:36 PM]

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

Simple (for computer)! Because all orbs are reachable.

Tahnan
Level: Smitemaster

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

halyavin wrote:
Simple (for computer)! Because all orbs are reachable.

Assuming that you can actually input all of that information. I use an orb-solver occasionally, myself, but the idea of clicking on that many orbs to see what they do makes me twitch.

Maurog
Level: Smitemaster

Rank Points: 1501
Registered: 09-16-2004
IP: Logged

Must be some exotic definition of 'simple'... 2^280 possible states are enough to keep a computer busy for years.

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!

Briareos
Level: Smitemaster

Rank Points: 3516
Registered: 08-07-2005
IP: Logged

Insane wrote:
I can give you nightmares if I want.

Urge to rise... killing.

np: Landesvatter - Raun. (Lax)

____________________________
"I'm not anti-anything, I'm anti-everything, it fits better." - Sole
R.I.P. Robert Feldhoff (1962-2009)

zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

A tip: Put some hints in other rooms. That might make me not dissuaded from just stopping when I get there...or waiting for the exact orbpress sequence from Rabscuttle.

____________________________

Kevin_P86
Level: Smitemaster

Rank Points: 535
Registered: 06-28-2005
IP: Logged

Insane wrote:
Also, many thanks to michthro's OrbSolver.exe program.
I used it to test every single orb puzzle in the complete level for possibility, without having to frustrate at it myself, and so I can write down the shortest possibility for personal use during testing .

If you don't want to play it, what makes you think anyone else will?

____________________________
+++++[>+++++<-]>[>+++>++++>+++++<<<-]>.>+.>-------.<++++.+++++.

Insane
Level: Master Delver

Rank Points: 154
Registered: 08-06-2005
IP: Logged

Kevin_P86 wrote:

Insane wrote:
Also, many thanks to michthro's OrbSolver.exe program.
I used it to test every single orb puzzle in the complete level for possibility, without having to frustrate at it myself, and so I can write down the shortest possibility for personal use during testing .

If you don't want to play it, what makes you think anyone else will?

It's just that I'm bad and everybody else is good.
Even MeckMeck GRE enjoyed my hold, even though he dislikes orb puzzles.

See my topic in Architecture.

-Insane

Edit: Also, I'm not even sure if my orb puzzle is even possible, while players know it's possible and thus keep trying.

---

[Last edited by Insane at 03-16-2007 06:32 PM]

Banjooie
Level: Smitemaster

Rank Points: 1645
Registered: 12-12-2004
IP: Logged

The trick is if you make really really annoying rooms, even if they're still possible, we still want to punch you in the face.

The only reason anyone will ever play a room like that is if there is some sort of high score to be gleaned from it.

Insane
Level: Master Delver

Rank Points: 154
Registered: 08-06-2005
IP: Logged

Banjooie wrote:
...we still want to punch you in the face.

Wich is precicely the goal of holds such as JtRH .

-Insane

Edit: So much for my abstract sense of humor.
-1.

Great job..

---

[Last edited by Insane at 03-17-2007 12:15 PM]