Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
DrD2k9 wrote:
The only concern I have with displaying the internal clock is that it may run faster than actual time, making it look like the playthrough has been artificially sped up.
I don't think this is possible, unless there is a serious emulation error.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
c-square wrote:
Looks like there's no delay for joystick input. It should be easy to update JPC-rr so you can use the number keys to control the joystick, if you'd like.
There is one problem I'm running into: I can send an AXISA command with a positive number, and Roger goes left. Same with AXISB and up. However, I haven't figured a way to go right or down yet. The input doesn't take negative numbers. Anyone else have an idea? I'll play with it more tomorrow.
What are the specifics of joystick input in JPC-rr? Are there commands other than AXISA and AXISB, and if so, what do they do? What are the possible values for AXISA and AXISB? Did you try a number at the top of its possible range?
DrD2k9 wrote:
Does the guy who buys the skimmer work on an RNG timer?
Not really, but there is one situation in that room where random() is called, which Radiant already mentioned on a previous page. If you leave the skimmer key in the skimmer and walk off and come back, there is a 34% chance of it being stolen. If you can manipulate it so that it won't be stolen, then you don't need to take out the key. (Also, there is no need to say "no" to that guy the first time. Just walk off after he gives his first offer.)
Edit: The alien waiting to be killed by the slot machine runs on an RNG timer. It takes 71+54*(x-2) ticks for him to be killed, where x is a random number between 2 and 7.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Thanks DrD2k9 for the information.
According to Radiant, the RNG is advanced once immediately after creating the seed. So I took your values and looked at the previous seed:
(for each of these, the first number is the index, where index(0)=0, and the second number is its corresponding seed value)
It looks like the sequence of initial seeds (before advancing it) starts at 4 for 0ms, then goes 22 (for 1000ms), 40 (for 2000ms), 58, 76, 95, ...
Normally the seed goes up by 18, but in some cases the number jumps by 19. It appears to occur every five numbers, but, as you said, at 59000 milliseconds it jumps by 19 instead of 18. Assuming that you mean that 59000ms is the first exception to this rule, the average seed increase appears to be between 18.203 and 18.204. Notably, this number is approximately the clock frequency of MS-DOS, normally cited to be 18.2Hz.
My conjecture is that the initial seed is the DOS clock frequency times RTC time (in seconds) plus 4, mod 65536.
Could you send the seed value for RTC 86399000ms? (This is one second before 86400000ms, which you said starts the cycle over).
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Radiant wrote:
The f2/f4 combo is a similar message for input that is completely not understood. It does not affect this run.
No, this is well understood. The code is:
if (isset(f2) &&
!isset(f4)) {
random(89,91,v64);
print.v(v64);
reset(f2);
}
f2 means "the player has issued a command line", f4 means "said() command has accepted the user input". This code is executed if all words are dictionary words but no specific said() command is defined for it.
FractalFusion wrote:
In fact, any command that consists of dictionary words but is not understood at all, i.e. no said() option exists in either logic.0 or current logic, happens to call random() as well. That is why entering "y" advances the RNG.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
DrD2k9 wrote:
If I understand Logic.000 correctly,
Getting something increases the random seed.
looking at something increases the random seed.
entering something increases the random seed.
specifically typing "use" something increases the random seed
Or maybe these only increase random if the 'something' is a non-recognized object in the game.
Radiant, can you clarify/confirm?
I assume you are referring to:
if ((said("check out","anyword") ||
said("check out","anyword","anyword"))) {
random(70,72,v64);
print.v(v64);
}
("check out" is the same as "look")
The code above is default code that is only executed if no other said() option is provided by the current room's logic. Ex: In the room you start in (room 2), "look hall" and "look wall" both have said() options, so those parts of the code are executed. On the other hand, "look waterfall" does not, so in this case the default code is executed and random() is called.
In fact, any command that consists of dictionary words but is not understood at all, i.e. no said() option exists in either logic.0 or current logic, happens to call random() as well. That is why entering "y" advances the RNG.
By the way, the AGI documentation may be of help when trying to understand the code.
Edit: Initial seed value appears to occur at the beginning of logic.2. There is a random() at the top which initializes RNG, even though the random() call is useless because f86 is not set until later in the code (and thus no guard can appear at the beginning).
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
- OK, so apparently it runs even faster than the last encode I saw. The timing seems to be different too. Maybe the last encode was wrong? (The audio still doesn't work properly.) Anyway, I had to watch the non-waiting parts of the encode on 0.25x speed to even have a chance at following anything in this TAS. It is far more enjoyable at that speed.
- What really bothers me is that, provided what everyone here is saying is indeed true, the AGI system only polls for movement input a fixed number of times per second (somewhere between 10-20 times a second) regardless of how fast the actual game is going (whether "normal", "fast", 100 ticks per second, or 5000) or how many times JPC-rr polls for input ("JPC-rr frames"). This has the effect that movement precision is inversely proportional to game speed, which paradoxically makes the TAS look less polished than if the game were capped at saner speeds.
- Nice to see some glitches I mentioned before made it into this TAS.
- DrD2k9, I appreciate that you took the effort to entertain during the waiting times. I personally would have preferred if you entered text that was relevant to the game or this TAS instead.
- I wouldn't really worry about missing the root maze. A TAS at this speed will never make it look impressive so it's no real loss that it's not there. I wouldn't worry about 100% either.
- I look forward to the Space Quest 1 TAS.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
OmnipotentEntity wrote:
If you take the harmonic series and remove only the terms that contain a 9 will the series converge or diverge? Prove it.
The series converges. Proof: Among all the positive integers that don't have the digit 9, there are 8 1-digit numbers, 8*9 2-digit numbers, 8*9*9 3-digit numbers, ... , 8*9k-1 k-digit numbers, and so on. Therefore the series is bounded above by
8(1)+8*9(1/10)+8*9*9(1/100)+...+8*9k-1(1/10k-1)+...
= 8(1+9/10+(9/10)2+...+(9/10)k-1+...)
= 8(1/(1-9/10)) = 8*10 = 80,
and the summation terms are all positive and go to 0. Therefore it converges.
Same argument if you exclude terms with the digit j, j something other than 9. (For j=0, the 8's in the proof above become 9's.)
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Actually I prefer watching at 0.5x speed. (This TAS really is super fast.)
Unfortunately for you, I have played this game to death as well as speedran it on "fast speed max" many years ago. So I have a lot of comments.
DrD2k9 wrote:
This is basically an interactive prologue to the game, but there are necessary items that must be collected from the lockers in the airlock to complete the game.
The items in the locker are not necessary to complete the game. There are alternate solutions for the Labion Terror Beast and the platform guard on the next screen. It is unknown which strategy is faster.
- Getting the keycard: You don't need to get the keycard off the dead guard at the crashed hovercraft. I think it is faster to get the keycard from the platform guard if you stone him, especially in your TAS where he falls right in front of the door (if you lure him down, you don't even need a keycard).
DrD2k9 wrote:
Side Note: I was absolutely floored that I was able to navigate the root maze at 'fastest' game speed without dying or having to change speeds
You do not need to do the root maze or get the berries at all. By taking advantage of a glitch, you can enter the deep part of the swamp before the monster gets you, then "hold breath" to escape. (To do this, enter the screen from the bottom, going to the right, then go up-right when you are about 1/4 of the way across, before the monster gets you. Going diagonally makes it harder for the monster to get you.)
DrD2k9 wrote:
This is the insanely long portion of this TAS! It's roughly three and a half minutes of watching Roger sit in one place. He takes the shuttle off the planet and tries to escape but has the shuttle controls overridden by Vohal which brings Roger to the asteroid. It's a really boring portion to watch
If it is strictly timed based on the system clock with no way to speed it up, then I think there are fun things you could have done during this sequence, without slowing down the TAS.
DrD2k9 wrote:
He also briefly stumbles into a unisex bathroom
About that, since you came from the right side of the screen, you could have entered the right door and exited the left, instead of entering and exiting the left door.
- About stopping the salesman launch: IIRC, it is possible to make it to the end of the game before the salesman launch timer runs out. (On Version 2.0F anyway; I recall that different versions had different timer amounts.) The game at the end simply says something like "Unfortunately, you failed to stop the launch of the clones dooming Xenon to the most horrible of fates! Way to go, %s1.", then continues with the ending. It is not a death.
- About the oxygen mask and the tube glass cracking sequence: If the game is on a fast enough speed like "fastest", I think it is possible to make it to the door after the cracking occurs but before the game kills you off. I could be wrong; the timing of some events seems a little different in JPC-rr (as opposed to DOSBox), so it could simply not be possible on JPC-rr.
DrD2k9 wrote:
Unable to both open a pod and enter before being caught, Roger must flee the robot.
This is why lower speeds exist. It should be possible to "press button" then quickly "go pod" in time, without having to flee the robot. If not possible on "fastest", it should be done on "fast".
Speaking of "fastest" being hard to control, I'm not sure why the input fps is set so low. On PC, you should be capable of an input fps of 1000 at least. IIRC the last time I used JPC-rr, I think there was a way to change the input fps.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Great that there was a surprisingly easy way to fix the emulation errors. This TAS is looking good now.
c-square wrote:
Doing this requires three extra slot pulls and six 'Y-enter' rng skips. It takes 8 frames for a losing slot pull, 10 frames for a winning slot pull and 7 frames to do a 'Y-enter' skip. In the end, this route costs 70 frames in RNG manipulation:
Assuming I understand how the random() calls work, I found a strategy that costs only 32 frames:
(first number is index but is different from yours; mine has 0 at index 0)
By the way, how many frames does it cost to exit and re-enter the machine? How about saving and restoring?
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Bobo the King wrote:
Anyway, I jogged my memory by checking out Wikipedia's page on contour integrals. Example 2 there corresponds to your problem statement with t = i*a^2
Example 2 with t = i*a^2 gives the integral of e^(-a^2 z)/(z^2+1).[1] OmnipotentEntity asked for the integral of e^(-a^2 z^2)/(z^2+1).
The method described in Example 2 doesn't seem to work for e^(-a^2 z^2)/(z^2+1), primarily because the arc integral can't be bounded reasonably (values of z near pure imaginary numbers give values far from zero in the negative direction when squared; this gives a very large number for e^(-a^2 z^2)). In fact, WolframAlpha claims (citation) that the answer is not pi*e^(-a^2) (the expected answer being the contour integral around z=i), but actually pi*e^(-a^2)*(1-erf(a)), where erf is the error function. I wouldn't know how to prove this.
[1] Actually, this isn't even valid. In Example 2, t specifically has to be a real number for the argument that the arc integral goes to 0 to hold.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Bobo the King wrote:
Riddle 1:
...
the maximum number of unique handshakes per arrangement is n (everyone shakes the hand of the person to their left and to their right, which double-counts the number of handshakes)
The maximum number of unique handshakes per arrangement is far greater than n; a person is permitted to reach across the table to shake the hand of someone not sitting adjacent, provided that arms never cross.
The number of possible handshakes per arrangement is not important to this problem though. The problem asks for the number of unique seating arrangements required to get everyone to shake hands, and the answer is ceil(log2(n)), ceil(x) being the least integer that is greater than or equal to x.
Bobo the King wrote:
Riddle 4:
...
It turns out there's one free variable, so you need to use an augmented matrix and put it in reduced row-echelon form.
There are 5 equations and 5 unknowns in this problem, and according to my calculation, there is a unique solution. I don't know where this "free variable" is coming in. Did you mean redundant equation? (But there are only 5 equations.)
You may possibly be correct that the last row is an integer multiple of some other rows/columns (but I haven't worked out the problem to completion yet so I wouldn't know).
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
The emulation is this messed up in JPC-RR? RIP AGI TASes.
Regarding this game: It's too bad the slot machine can't be manipulated very well. I was hoping that it would have been possible to manipulate easily; it's the one thing that would have made this TAS impressive from a technical standpoint. (Is it possible to type and enter something that could manipulate RNG as well?)
About adventure games done fast: Even though I love these adventure games, I am not a fan of adventure games run at incomprehensible speeds. I would much prefer if there was enough time between "key actions" for the viewer to at least have an idea what is going on. Even I can barely keep up, despite having played this game many times before.
Anyway, I would normally have liked a TAS of this game to be published, but, if the emulation problems cannot be fixed, I think it would be better not to publish.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
OmnipotentEntity wrote:
But if $$a$$ is not a real number then bringing $$\mathrm{e}^{a t}$$ into the $$\Re$$ isn't allowed. But we get the same answer. So if we try to compute the integral in this way it's an abuse of notation.
Instead of using Re(eiωx) for cos(ωx), use (1/2)(eiωx+e-iωx) instead. (This follows from Euler's formula.) Then it will work out to be the same answer. This way, we do not need to worry about abuse of notation; it works when a is complex. In fact, it now works even if ω is complex. (Euler's formula holds for complex values as well.)
By the way, the image you uploaded isn't visible in imgur without going into expand mode. It may be because the background color is regarded as transparent, even though it should be white. Edit: The image is directly linked now, which solves the problem.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Bobo the King wrote:
What do the variables there represent?
The variables are expected values.
More specifically, EABCD, EAABC, EAABB, and EAAAB are the expected number of turns required to go from state ABCD, AABC, AABB, AAAB (respectively) to state AAAA. The following relations apply to these values:
EABCD=1+EAABC,
EAABC=1+(6/12)EAABC+(4/12)EAAAB+(2/12)EAABB,
EAABB=1+(4/12)EAABB+(8/12)EAAAB,
EAAAB=1+(6/12)EAAAB+(3/12)EAABB+(3/12)(0).
Then one can solve this to get EAAAB=5.5, EAABB=7, EAABC=8, EABCD=9. The expected number of turns to go from ABCD to AAAA is 9.
That's what the Riddler is trying to say.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Warp wrote:
OmnipotentEntity wrote:
And the answer is yes. Because we know that lim(x->0) -x / x3 = -infinity. So we just need to set g(x) to -x and we set 1/ln(f(x)) = x3 which gives f(x) = exp(x-3)
That seems to indeed work.
The function f(x) given above does not have a (two-sided) limit as x->0.
The one I came up with was f(x)=exp(-x-4), g(x)=x2, and a=0. In this case, f(x), g(x) and f(x)g(x) all have the (two-sided) limit 0 as x->0.
Bobo the King wrote:
Riddles were super easy this week.
Sure was. This was the easiest since a very long time ago, if ever.
Both Riddler problems are pretty much known to every math enthusiast (the first is Nim, the second is one of the characterizations of the Fibonacci sequence). As if that wasn't enough, Riddler Express ended up linking to the Nim Wikipedia page which tells you exactly how to solve it.
The Riddler Classic generalization is a little more interesting (the frog can jump up to n steps, instead of just 2), but anyone can just write a computer program (or even just use an Excel spreadsheet) to figure it out. The most interesting thing I found out was concerning the growth rate of each sequence depending on n.
For n=2, the growth rate is exponential with a base of (1+sqrt(5))/2 (the golden ratio); this is a known property of the Fibonacci sequence. As n grows larger, the base grows; however, the limit of the bases is 2 as n goes to infinity (if you sum all past terms, you get the powers of 2). The base is just the largest real root of xn-xn-1-xn-2-...-x-1, or in other words the largest real solution to (x-2)xn=-1. From this equation, it is clear that x must be less than 2. Approximate bases are as follows:
n=2: 1.61803
n=3: 1.83929
n=4: 1.92756
n=5: 1.96595
n=6: 1.98358
n=7: 1.99196
n=8: 1.99603
n=9: 1.99803
n=10: 1.99902
Edit: Changed "exponent" to "base". I still say stupid stuff sometimes.
Edit 2: Fixed f(x).
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Bobo the King wrote:
The Price is Right question seems like it would be easier to thoroughly investigate, although FractalFusion has warned in the past that game theory problems are too difficult for Riddler challenges. I'll look into it.
The game theory problems I was referring to as difficult are mostly games that involve payoff matrices; those games involve players making their choices at the same time. Since the decision to spin the wheel on the Price is Right is sequential (P1 chooses first, then P2 uses prior information to choose, then P3), this problem is easier to understand conceptually than those involving payoff matrices. It's just a matter of working backwards (find P3's strategy, then P2's, then P1's).
The optimal strategy for spinning the wheel has already been discussed on many sites so you can just look it up if you want to see what it is.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
The prisoner and levers problem lives on, even a week later! Steve Schaefer, a commenter for this page, posted a better strategy in the comment section. I'm not sure if anyone else found this out, because neither us, nor Hector Pefo, nor Riddler, nor Car Talk arrived at this strategy. The strategy gives a way for the 99 non-counting prisoners to flip the tally lever only once, while ensuring the counter does not overcount because of some random starting configuration. It is as follows:
Call the levers A and B (A is the tally lever, B the dummy lever). Prisoners 2 through 100 each do the following:
- If lever A has not been flipped by the prisoner yet, and the prisoner saw lever A in the up position any time previously, and lever A is down, flip lever A up. Otherwise, flip lever B.
Prisoner 1 does the following:
- Keep a count starting from 0. If lever A is down, flip lever A up. If lever A is up and Prisoner 1 flipped lever A down on the previous (one before) visit, flip lever A down and add one to the count. Otherwise, flip lever A down and don't add anything. When the count reaches 99, declare that all of the prisoners have been to the room.
I ran the expected value calculation and it comes out to be 11096.054 visits, a 45.8% improvement over the other strategy's value of 20476.663.
It may even be possible to improve with a different Prisoner 1 strategy of flipping the tally lever (but always flipping the tally lever already seems quite reasonable).
Flip wrote:
...
...
..o
.st
wx.
Which conveniently is 5 remaining, so we can just race 'em.
ostwx..........twx
Which gives you the 2nd/3rd place in 7 races, deriving the top three: wxy
The result of racing ostwx isn't necessarily twx; it could be wtx, stx, ost, xot, ...
(This would of course decide the second and third places.)
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
I'll explain how I got 20476.663 (I didn't use simulation, just calculation of expected values which requires a computer).
First, if p is the chance of success, the expected number of trials required to get the first success is 1/p. I assume that everyone understands this (this is a special case of the negative binomial distribution). For example, at any given point, the expected number of visits required to get Prisoner 1 to visit the room is 1/(1/100)=100.
Now define:
● n: the number of prisoners who still need to flip up the tally lever once or twice.
● k: the number of prisoners who still need to flip up the tally lever twice.
● (n,k): the current tally lever state of Prisoners 2-100, n and k defined above.
● E(n,k): the expected number of visits required to go from state (n,k)→(0,0), where the tally lever starts and ends in the down position (Prisoner 1 must witness the tally lever in the up position and flip it down for the final time).
Now E(0,0)=0. We calculate a recurrence relation for E(n,k) as follows: there are n prisoners who still need to flip the tally lever; k who need to flip it twice and n-k who need to flip it once. The expected number of visits until one of these n prisoners is selected is 100/n. Then Prisoner 1 has to be selected (expected number of visits 100). Finally, the next state is
● (n,k)→(n,k-1), if a prisoner was selected who needed to flip it twice, with probability k/n, or
● (n,k)→(n-1,k), if a prisoner was selected who needed to flip it once, with probability (n-k)/n = 1-k/n.
So the recurrence equations for n>0 are:
● E(n,0) = 100/n + 100 + E(n-1,k).
● E(n,k) = 100/n + 100 + (k/n)E(n,k-1) + (1-k/n)E(n-1,k).
● E(n,n) = 100/n + 100 + E(n,k-1).
Using this, we calculate the important values
● E(1,0) = 200,
● E(99,98) ≈ 20426.653,
● E(99,99) ≈ 20527.663.
Finally, we consider the start. If the tally lever starts up, then Prisoner 1 has to be selected (expected number of visits 100), in order to flip it to the down position first. Thereafter, we need the expected number of visits required to go from (99,99)→(1,0) (remember that a count of 197 is sufficient to determine that all of Prisoners 2-100 have visited the room). So:
● Exp(start up) = 100 + E(99,99) - E(1,0) ≈ 20427.663.
If the tally lever starts down, then it depends on the first prisoner to visit the room. There are two cases:
Prisoner 1 is selected: The tally lever remains down. As above we need the expected number of visits required to go from (99,99)→(1,0). So:
● Exp(start down, P1) = E(99,99) - E(1,0) ≈ 20327.663.
Prisoner 2-100 is selected: That prisoner flips up the tally lever. Then Prisoner 1 has to be selected (expected number of visits 100), but that flip up of the tally lever is not counted. To get a count of 197, we need the expected number of visits required to go from (99,98)→(0,0). So:
● Exp(start down, P2-100) = 100 + E(99,98) ≈ 20526.653.
So:
● Exp(start down) = 1 + (1/100)Exp(start down, P1) + (99/100)Exp(start down, P2-100)) ≈ 20525.663.
Finally:
● Exp(visits) = (1/2)Exp(start up) + (1/2)Exp(start down) ≈ 20476.663.
Bobo the King wrote:
ABDC would not return "zero" in this case; it would return "one" instead.
I noticed because the starting case ABCD --> "two" was the case which I used to convince myself that five consultations (four to identify the correct permutation) was required in the worst case regardless of which permutations you use for the second and later consultations.
I believe the rest of your reasoning is correct. (By the way, I think that how you interpreted it is the most reasonable interpretation of the problem. If that is what the Riddler intended, then the footnote was not only pointless but misleading as well.)
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Bobo the King wrote:
This week's Riddler challenges are fairly easy, I thought.
You must be smarter than me, because both questions are difficult in my opinion.
Classic puzzle:
Finding the overall strategy is tricky. The solutions are given on this site. I was only able to get the strategy for the case where the initial positions of the levers are known, but I failed to find the strategy when the initial positions are unknown and I had to look it up.
To summarize, the strategy is as follows: Call the levers A and B. Prisoners 2 through 100 each do the following:
- If lever A has not been flipped by the prisoner twice yet, and lever A is down, flip lever A to up. Otherwise, if lever A has been flipped twice, or if lever A is already up, flip lever B.
Prisoner 1 does the following:
- The first time Prisoner 1 goes to the lever room, if lever A is up, flip it to down; otherwise flip lever B. From this point on, Prisoner 1 keeps a running count, starting at 0. For the second and subsequent visits, if lever A is up, flip it to down and add one to the count; otherwise flip lever B and don't add anything to the count. When the count reaches 197, Prisoner 1 declares to the warden that all of the prisoners have been to the room.
For the average number of visits to the lever room made in total by the prisoners (assuming the prisoners are chosen uniformly at random, and assuming random initial lever positions), I calculated it as about 20476.663 using computer software. Bobo the King, how did you get your answer? Whatever it is, it isn't the same as mine.
Express puzzle:
Bobo the King, could you explain how to interpret the problem? I have read the statement of the problem over and over but I do not know what the Riddler exactly wants. Specifically, the part where it says "How many times should you have to consult the oracle, in the worst case, <footnote>Assuming you learn from each iteration and don’t keep trying the same wrong answers.</footnote> to assemble the tower correctly?" Does it want the worst case of the best strategy to minimize the expected number of consultations? The worst case of the best strategy to minimize the worst-case (maximum) number of consultations? The maximum number of consultations possible without any regard to strategy (bound by the rule that "you learn from each iteration")?
Edit:
Flip wrote:
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
I got a fence layout of total length 2/3+sqrt(3)/4+pi/6 (~1.6232781). I think this is the best I can do, as I am unwilling to do further calculations.
See the diagram below. I am assuming that the fences satisfy a horizontal symmetry. The common point of the fences lies halfway between the left and right edges. One fence goes vertically down from this point to the bottom edge, and the other two are circular arcs from the common point to the left and right edges, intersecting the edges at right angles. (The isoperimetric problem can be used to show that these circular arcs are optimal.)
From the diagram, r is the radius of curvature of the arc, θ is the angle subtended by the arc, and b is the height of the vertical fence. θ ranges between 0 and pi/2. Some calculation gives r = 0.5/sin(θ), and b = 2/3 - r2(θ-0.5sin(2θ)), and the total length of the fencing is b+2rθ. Plugging in b and r, and minimizing gives the minimum as 2/3+sqrt(3)/4+pi/6 (~1.6232781) at θ=pi/6, and r=1 and b=2/3+sqrt(3)/4-pi/6 (~0.5760806).
The only way to beat this (if possible) is to use something that doesn't have horizontal or vertical symmetry.
Bobo the King wrote:
Anyway, I'm miffed that this is yet another, "Interpret this puzzle as I see it," type of problem.
Actually, the Riddler had a similar problem with a similar solution last year, and I had no trouble arriving at the cycle-following solution there, but I missed it here because of the wrong interpretation. (Seeing as how the other interpretation is an actual problem, I'll just call the earlier interpretation "wrong" from now on.)
The problem here was given for a very small (2 out of 4) number of boxes, didn't mention anything about choosing boxes in any order, gave no hint to the actual answer (5/12 for 2 out of 4, decreasing as the number of boxes increases but never less than 30.68%) and had a stated goal up front that was laughably easy ("Concoct a strategy that beats the naive strategy"), which further suggested the wrong interpretation. I know the 100 prisoners problem is supposed to be tricky, but it isn't supposed to be tricky in this manner. The fact that this puzzle comes only 5 weeks after another game show problem that is indeed solved using a predetermined strategy didn't help matters.
Bobo the King wrote:
Also, I just noticed that the official answer for last week's coin flipping puzzle is 143, not 134, although I also see that The Riddler did not take into account the possibility that both coins turn up heads the same number of times.
Based on the economics paper linked in the Riddler, I don't think the problem was ever intended to be mathematically precise, but only to "illustrate the common tendency to over-weight past data in forecasting the future", as the abstract puts it.
I'll post the exact wording of the problem (as posed by the Riddler) again:
On the table in front of you are two coins. They look and feel identical, but you know one of them has been doctored. The fair coin comes up heads half the time while the doctored coin comes up heads 60 percent of the time. How many flips — you must flip both coins at once, one with each hand — would you need to give yourself a 95 percent chance of correctly identifying the doctored coin?
By not being precise, the problem opened itself up to a few different interpretations:
@ "What is the smallest n such that if you flip both coins n times, observe the result, and guess which coin is doctored, your guess is correct at least 95% of the time?" (us) (answer: 134)
@ "What is the smallest n such that if you flip both coins n times, the doctored coin turns up more heads than the fair coin at least 95% of the time?" (paper, Riddler, Hector Pefo) (answer: 143)
@ "What is the expected number of flips required to first observe a result that determines the doctored coin with at least 95% certainty (posterior probability)?". (Laurent Lessard) (answer: about 73)
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
I got 1.6266 by replacing the slant lines (the straight fences that don't meet the edge of the square at a right angle) with circular arcs that divide the areas equivalently.
Any straight fence that does not meet the edge of the square at a right angle can be replaced with a circular arc to lower its length.
Bobo the King wrote:
Has anyone come up with anything else for the game show puzzle where 100 people try to find their names in 100 boxes?
I came across another person's approach to this problem: Each player can progressively open boxes depending on which boxes they opened previously. They are not limited to choosing 50 boxes and opening them all at the same time.
This, in my opinion, is a much better interpretation of the problem.
Editor, Experienced Forum User, Published Author, Expert player
(2159)
Joined: 6/15/2005
Posts: 3303
Bobo the King wrote:
My strategy that led to 1.633 miles of fencing was just two parallel diagonal fences that make 45 degree angles with the sides of the square. This beat three other strategies with three fences meeting at a central node.
Two parallel diagonal fences that make 45 degree angles with the sides of the square? That seems to give 4/sqrt(3), or about 2.31, not 1.633.
Did you calculate the leg lengths of the 45-45-90 triangles bound by the diagonals as sqrt(1/3) instead of sqrt(2/3)? If I did my math right, it should be sqrt(2/3).
From the diagram, r is the radius of curvature of the arc, θ is the angle subtended by the arc, and b is the height of the vertical fence. θ ranges between 0 and pi/2. Some calculation gives r = 0.5/sin(θ), and b = 2/3 - r2(θ-0.5sin(2θ)), and the total length of the fencing is b+2rθ. Plugging in b and r, and minimizing gives the minimum as 2/3+sqrt(3)/4+pi/6 (~1.6232781) at θ=pi/6, and r=1 and b=2/3+sqrt(3)/4-pi/6 (~0.5760806).
The only way to beat this (if possible) is to use something that doesn't have horizontal or vertical symmetry.
