---------------------------------------------------------
---------------------------------------------------------
---------------------------------------------------------
---------------------------------------------------------
---------------------------------------------------------
---------------------------------------------------------
---------------------------------------------------------
---------------------------------------------------------
---------------------------------------------------------
---------------------------------------------------------
---------------------------------------------------------
Optimized dungeon robbery: The best I could manage is to enter at one of the 7s at top left, taking 5, then go down,
right, up, right, down, and right. Then open each of the 2s leading to the 9s at the bottom, spending 29 coins to
take 48, for a net of 19.
Joseph DeVincentis
---------------------------------------------------------
Hi Ed,
So far, the best I've found is starting from the bottom middle door
(price = 2), and passing thru doors 2-8-1-4-1-7-2, with a net of 18
coins. I believe one can immediately cross off the rightmost column and
the doors leading to it as a dead loss (although I had to check that I
could'nt do better by starting from the right middle door and passing into
the center room).
If you assume that you don't go thru a room more than once, you can do an
interesting transform: Take the number of coins in the center of each
room, divide by two, and subtract that number from the price of all doors
into the room. Then erase the coins in the center of the room, and each
door will give you the net cost of going thru it (since, if you go thru
the room, you pass thru exactly two of the doors). One can then take the
dual of this planar graph, and ask for the minimum value based loop
passing thru each point at most once (or, by multiplying all numbers by -1,
the maximum value loop, whose value corresponds to how many coins you
gain).
-Craig Helfgott
---------------------------------------------------------
Is the answer a net profit of 19 coins?
If rooms are labeled:
A B C
D E F
G H I
Enter G from west, take 9 coins and go back out to west through the still-open door (net profit 7 coins)
Enter H from south, take 9 coins and go back out to south (net profit 14 coins)
Enter F from east (net profit 14 coins)
Move from F to E (net profit 15 coins)
Move from E to B (net profit 17 coins)
Move from B to A (net profit 18 coins)
Open door from A to D, pick up 9 coins and go back to A (net profit 26 coins)
Exit A to north or west (net profit 19 coins)
You can pick up the coins in C (from F) and I (from outside) but they don’t increase your profit.
Jeff V.
---------------------------------------------------------
Rooms
ABC
DEF
GHI
in 2->G-> 2 (free) out = +7
in 2->H-> 2 (free) out = +7
in 3->F->2->C->7->B->1->E->4->D->1->A->7 out = +5
Total = +19
Juha Saukkola
---------------------------------------------------------