plasmid
-
Posts
1756 -
Joined
-
Last visited
-
Days Won
25
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by plasmid
-
-
13 hours ago, Molly Mae said:
I'll call that a hit. My thinking was...
Spoiler...a fireplace, but after thinking about it I can't tell the difference between a fireplace and a wood burning oven anyway.
For the wave, I was thinking roof of a house (which is why the wave that the fireplace/chimney is mostly under is singular, although potentially in a sea of waves in a neighborhood). The oven's aroma is certainly as characteristic a spume as smoke from a chimney. The clue about harpooning is a reference to a fire poker which will rile the fire up, but it's apparently no longer commonplace enough to be widely recognized by everyone since people rarely have wood burning fireplaces any more.
-
-
-
-
Not a sink disposal. While I imagine the last stanza has happened with some of those, I hope it's not commonplace enough to belong in a riddle.
-
On the right track, but not quite there yet.
-
I feast on meals of mindless fare
With blubber to keep it all in
For what’s inside should stay right there
Or you’ll face a calamitous end‘Neath peaking wave I spend the days
While mostly conceal’d, I presume
Unless my presence breath betrays
As characteristic’s my spumeAlas, I find myself engaged
By man with a wretched harpoon
Assaulted thus, I shriek enraged
With hellish retort for the goon -
How I'm interpreting it so far:
SpoilerTwo needles have nothing but a small dose of pain... I'll consider those just ordinary needles that can prick skin.
The first and last needle: one contains illness and pain and I'll consider that one to have a tip with poison. The other provides release... I'm not sure what to think of that, it might mean an antidote or it might mean something like cyanide that'll just flat out kill you without too much suffering, or it might even be sleep since there's a clue later on that refers to a sleeping needle and there's reason to suspect that the clue about release could be referring to the sleeping needle.
Sleep lies to the left of nothingness... to me that implies that it's the last needle (it's to the left of the edge of the set of needles). The clue about the first and last needle refer to one that has illness and pain (which sure doesn't seem like it's referring to sleep) and to another that provides release. And providing release is more plausible to be a reference to sleep. Sleep could be a euphemism for death, but it says sleep lies to the right of death so I'm guessing that sleep really does mean sleep and not death.
So I'll consider that set of clues to mean that the last needle is laced with a sleeping potion, the needle just before it is laced with cyanide, the first needle is laced with poison, there are two needles with nothing, one "interesting creation" and a thing we seek (which might or might not be synonymous with the interesting creation). But that only accounts for 6 or 7 of the 8 needles and doesn't give enough information to figure out which one to pick. Aside from of course avoiding numbers 1, 7, and 8 (unless you want to take a nap).
-
Spoiler
When Al gets on the plane, he will do one of three things: (1) he will sit in his own seat, (2) he will sit in Bert's seat, or (3) he will sit in someone else's seat. The odds that he will sit in his own seat (and be guaranteed to not have to move) or in Bert's seat (and be guaranteed to have to move) are equal.
If Al sits in someone else's seat, call that someone else Charlie. Al will have to move if and only if Charlie has to move and claim his assigned seat which Al took. And Charlie will either (1) sit in Al's seat so Al won't have to move, (2) sit in Bert's seat so Al will have to move (note that the odds of picking Al's seat or Bert's seat are again equal), or (3) sit in someone else's seat so that Al and Charlie will both have to move if and only if that someone else has to claim their seat which Charlie took.
This keeps repeating until someone sits in Al's seat (so Al doesn't have to move) or sits in Bert's seat (so Al has to move), and at each step in the process the person who's taking a seat has equal probability of choosing Al's seat or choosing Bert's seat. So the odds that Al has to move are 50/50.
-
Optimizing Captain Ed’s answer a little more
SpoilerInstead of using a right angle with the North side and West side, consider rotating that so it’s oriented like a V (with a right angle at the bottom). Now instead of having those two lines meet at the northwest corner, push the intersection toward the center of the square a bit and draw a line from the northwest corner to the intersection, so instead of a V it looks like a Y.
To make the math easier, I’ll re-scale distances so the distance from the center of the square to a corner is now defined as 1. If you move the intersection toward the center of the square by a distance of X, and you think of the original North side and West side as hypotenuses of a right triangle with the other two sides of the right triangle having length 1, then the new length for each of the hypotenuses will be
sqrt(A2 + B2)
sqrt(1 + [1-X]2)
sqrt(1 + 1 – 2X + X2)
sqrt(X2 – 2X + 2)
The total length of the lines (excluding the diagonal line from the southeast corner to the center) is twice that length (to count both the North and West lines) plus X.
X + 2 sqrt(X2 – 2X + 2)
Take the derivative of that with respect to X to find out where it reaches a minimum, doing a substitution so you can calculate the derivative
u = X2 – 2X + 2
du/dx = 2X – 2
d/dx = 1 + d/du [2 sqrt(u)] du/dx
= 1 + (u-1/2) (2X – 2)
= 1 + (2X – 2) / sqrt(X2 – 2X + 2)
The derivative is zero at
2X – 2 = sqrt(X2 – 2X + 2)
4X2 – 8X + 4 = X2 – 2X + 2
3X2 – 6X + 2 = 0
By the quadratic formula
X = [6 ± sqrt(36 – 24)] / 6 = 1 ± sqrt(12)/6
Since X being greater than 1 makes no sense, just consider the negative term
X = 1 – sqrt(12)/6 = 1 – sqrt(1/3) ~= 0.4226So move the North and West lines so they don’t intersect at the northwest corner and instead intersect ~0.5774 units away from the square’s center (remember that a unit is now defined as the distance from the square’s center to a corner) and draw a line the rest of the way from that intersection to the northwest corner. The total length (again excluding the diagonal line from the southeast corner) would be
0.4226 + 2 sqrt(12 + [sqrt(1/3)]2) ~= 2.732
compared to using the edges of the square which would have length
2 sqrt(12 + 12) ~= 2.828Adding back the length of the diagonal from the southeast corner to the center of the square (which is just 1 the way I’ve defined distances) and converting from the units I’m using to units where the length of an edge of the square is 1 gives the total length at
(2.732 + 1) / sqrt(2) ~= 2.639And it looks (approximately) like this
-
Is there an easier way to reach the solution? If I try to handle the case of an infinite number of princes to choose from, and I deal with the exact formula I was working with initially instead of the simplified approximation that I ended up using to be able to actually calculate an answer, then I get
Spoiler
Then you get to take the derivative of that with respect to N, set it to zero, and find the limit as K goes to infinity. Which will involve converting factorials to gamma functions so you can take the derivative. And will most definitely lead to more table flipping.
-
Spoiler
It sure looks like 1/e, but when I try taking the derivative of that formula I had earlier and setting it to zero, it turns into a mess. FWIW, I'm getting the following:
My estimate was
Sum[GCD=2 to K] N(K-N)GCD-1 / (GCD-1)KGCDWe’re trying to find the value of N that makes that function maximal, so take the derivative and find out where it’s zero.
d/dN =
Sum[GCD=2 to K] d/dN [N(K-N)GCD-1 / (GCD-1)KGCD] =Sum[GCD=2 to K] d/dN [N(K-N)GCD-1] / (GCD-1)KGCD
Using the product rule [(fg)’ = f’g + fg’] where f(N) = N, f’(N) = 1, g(N) = (K-N)GCD-1, g’(N) =
substitute u = K-N, du/dN = -1
d (K-N)GCD-1 / dN
= d uGCD-1 / du x du/dN
= -(GCD-1) uGCD-2
= -(GCD-1) (K-N)GCD-2So we have
Sum[GCD=2 to K] [(K-N)GCD-1 – N(GCD-1)(K-N)GCD-2] / (GCD-1)KGCDSum[GCD=2 to K] (K-N)GCD-2 [(K-N) – N(GCD-1)] / (GCD-1)KGCD
And that's as far as i got before I flipped a table.
(╯°□°）╯︵ ┻━┻
-
I know of a way to do this while flipping no more than two coins. And a hint:
SpoilerIf the total number of coins in play is a power of 2, I know how to do it with a single coin flip.
-
On 4/3/2018 at 7:34 PM, plasmid said:
This is a start but not a complete answer.
If you care only about whether the Princess picks the Most Wonderful Prince, and don’t care whether a failed attempt gets her the second best guy or the village donkey because you consider anything less than the best to be a loss:
Call the highest ranking guy among the first N the Greatest Chump Dude (GCD, not to be confused with greatest common denominator). The odds that the GCD is the Most Wonderful Prince (MWP, rank #1) is simply the odds that MWP is within the first group of N, so
P(GCD = #1) = N/100
The odds that the GCD is the second highest ranking suitor is the product of (the odds that GCD is not MWP) x (the odds that the second ranking guy is within the first N suitors if you’re given that GCD is not MWP), so
P(GCD=2) = [(100-N)/100] x (N/99)
By similar logic, the odds that the GCD is the third ranking suitor is
P(GCD=3) = [(100-N)/100] x [(99-N)/99] x (N/98)
Et. cetera.If you know the rank of GCD (and if GCD is not MWP) then you know the Princess will pick the first suitor that outranks GCD, so the odds that she picks MWP will be [1/(GCD-1)].
So the odds that both (GCD is the second best suitor) and (she picks MWP if you’re given that GCD was the second best suitor) are
P(GCD=2) x [1/(GCD-1)]
[(100-N)/100] x (N/99) x [1/(2-1)]
[(100-N)/100] x (N/99)
And the odds that both (GCD is the third best suitor) and (she picks MWP if you’re given that GCD was the third best suitor) are
P(GCD=3) x [1/(GCD-1)]
[(100-N)/100] x [(99-N)/99] x (N/98) x [1/(3-1)]
[(100-N)/100] x [(99-N)/99] x (N/98) x [1/2]And the overall odds that she picks MWP are the sum of all of those (odds that GCD is rank M) x (odds that she picks MWP if you’re given that GCD was rank M) terms for M=2 to 100. That ends up being a function of N, but it’s a function that’s too complex to solve without resorting to a computer unless you can simplify it.
I’m going to make the math easier by
Spoilernot assuming that there are 100 suitors, but assuming there are a “large” number of suitors. Let’s say it’s the whole kingdom, K, so modifying my previous answer accordingly we have:
P(GCD=1) = N/K
P(GCD=2) = (K-N)/K x N/(K-1) ~= (K-N)/K x N/K = N(K-N) / K2
P(GCD=3) = (K-N)/K x (K-N-1)/(K-1) x N/(K-2) ~= [(K-N)/K]2 x N/K = N(K-N)2 / K3
P(GDC=X) ~= N(K-N)X-1 / KXAnd the odds of picking MWP for any given GCD are still 1/(GCD-1) so the odds of picking MWP are approximately
Sum[GCD=2 to K] N(K-N)GCD-1 / (GCD-1)KGCD
That doesn’t make it easy enough to just calculate by hand, but it does make it easy enough to make a spreadsheet to handle the calculations. If I make K=100, then this estimate says that the best number of chumps is 37 of the hundred, which would leave (ironically?) about a 37% chance of getting the MWP.
-
I changed the way the algorithm works, so that it more systematically checks all possible paths for all possible mazes and is guaranteed to eventually find the shortest possible set of instructions that will solve every maze of size n x n. The bad news is that it takes a long time to run. Even after doing what I could to make this run reasonably efficiently, it still could only process a 3 x 3 maze and will take a while to process even a 4 x 4 maze, albeit on a crummy laptop.
If this was a question posed to programmers, and the person asking the question knew full well that the numbers would get huge fast (checking all possible instructions for a 17 step solution would mean checking 417 = 17 billion potential solutions against almost 4000 mazes for the 4 x 4 case) and was making the point that you'll need to come up with something other than exhaustive brute force (sort of like the algorithm I had earlier but probably a smarter version), then it would make sense.
At any rate, this is a solution for any 3 x 3 maze with the shortest possible number of moves.
SpoilerRDRRDLLDDRR
-
This is a start but not a complete answer.
If you care only about whether the Princess picks the Most Wonderful Prince, and don’t care whether a failed attempt gets her the second best guy or the village donkey because you consider anything less than the best to be a loss:
SpoilerCall the highest ranking guy among the first N the Greatest Chump Dude (GCD, not to be confused with greatest common denominator). The odds that the GCD is the Most Wonderful Prince (MWP, rank #1) is simply the odds that MWP is within the first group of N, so
P(GCD = #1) = N/100
The odds that the GCD is the second highest ranking suitor is the product of (the odds that GCD is not MWP) x (the odds that the second ranking guy is within the first N suitors if you’re given that GCD is not MWP), so
P(GCD=2) = [(100-N)/100] x (N/99)
By similar logic, the odds that the GCD is the third ranking suitor is
P(GCD=3) = [(100-N)/100] x [(99-N)/99] x (N/98)
Et. cetera.If you know the rank of GCD (and if GCD is not MWP) then you know the Princess will pick the first suitor that outranks GCD, so the odds that she picks MWP will be [1/(GCD-1)].
So the odds that both (GCD is the second best suitor) and (she picks MWP if you’re given that GCD was the second best suitor) are
P(GCD=2) x [1/(GCD-1)]
[(100-N)/100] x (N/99) x [1/(2-1)]
[(100-N)/100] x (N/99)
And the odds that both (GCD is the third best suitor) and (she picks MWP if you’re given that GCD was the third best suitor) are
P(GCD=3) x [1/(GCD-1)]
[(100-N)/100] x [(99-N)/99] x (N/98) x [1/(3-1)]
[(100-N)/100] x [(99-N)/99] x (N/98) x [1/2]And the overall odds that she picks MWP are the sum of all of those (odds that GCD is rank M) x (odds that she picks MWP if you’re given that GCD was rank M) terms for M=2 to 100. That ends up being a function of N, but it’s a function that’s too complex to solve without resorting to a computer unless you can simplify it.
-
It reached a final set of instructions for a 5 x 5 maze, which I'm sure you're all dying to see...
SpoilerRRRRDDDDRRRRDDDURRRRDDDUURRRRDDDUUURRRRDDDLDDRRRRDDRRRRDURRRRDLDDRRRRUUURRRRDDDLUURRRRDDDURRRDDUUURRRRDDDDLUUURRRRDDDULUURRRRDDDLLDDRRRRDDRRRRDURRRRDLDDRRRRUURRRDDULUURRURRDDDDULLDDRDRRRDRLDLDDRRRRLUURRDRRDUULLDDDRDRRRRDDURRDDLLUURRRRDDDRRURRDDDDLLUUURRRRDDDDRRDDLULUURRURRDDDDURRDDDDUUURRURRDDDDRRURRDDUURRDDLDDDRRURRDDRRUURRDDDULLUURRRRDDDLDLDDRRURRDDRRURRDDUURRDDRRUURRDDLLUUURRURRDDDDULLUURRURRDDDDRRUUURRDDDDLDDRRDDRRRRDURRRRDLLLDDRRRRDDRRRRDURRRRDLDDRRRRLLDDRDRRDULLDDRDRRRUULLDDDRDRRRRDDURRDDRRURRDDUURRRRDDURRDLLLLDDRRRRDDRRRRDURRRRDLLDLDDRRRDRLDDRRRRLLLDDRRRRDLDDRRRRLUURRDRRDURRDDLULLDDRDRDRRRDRRURRDUURRDDULLLDDRRDRRDRRRRLDDRRRRLLDDRRRRURRRDDLUUURRRDDRDLDDRDULUURRRDDRDLDDRDULLLLDDRRRDRDRRRRURRRRDLDDRRRRLULLDDLDDRRRRURRRRDLLULLDDRDRRRDRLDDRRRRURRRRDRRLULLLDDRDRDRRRLDDRRRRDRRURRDRDLLUUURRRDDRDLULUURRRDDRDLDDRDRLLDDRRDRUURRDRRDLUURRDRRDLLLDDRDRRDRRURRDRRLDDRRUURRDDRRLDLLDDRDRRULLDDRDRRULULLDDRDRDRRRDRRURRDRRDURRDUURRRDRDLUURRDRDLDDRRDURRDUULLLDDRDRDRRRLDDRRRRDRRURRDRDUURURRDDDRLUURURRDDDRLDDRULULLDDLDDRRRRLLDDRRRRURRDRDRUULLLLDDRRDRDRRRRDRLDDRRRRLLDDRRRRURRDRLULLDDRDRRLLUULLDDDRDRRRRDRRLLDDRRURRDDRRUURRDDRRLDDRLUURRRDDRLDDRLUUURRRDDDRLDDRLUURURRDDDRLDDRDRLULULLDDRDRDRRRLDDRRRRURRDRRDRUURRRDDRDRLDDRURURRDDRLUURRRDDRLDDRDRLUULLLDDRDRDRRRLDDRRRRDRRURRRDDRUURRRDDRDRLDDRURURRDDRLUURRRDDRLDDRUUUURRRDDDDRLDDDRULUURRRDDDDRLUURRRDDDDRLUUUURRRDDDDRLDDDRUULUURRRDDDDRUUURRDDDRLDDDRLDDRRDRDUURURRRDDDLLUURRRRDDDURRRDDDRRLUUURRDRRDDLLUUURRRRDDDULUURRRRDDDLULUURRRRDDDULLUURRRRDDDRRRRDURRRRDLDDRRDDLUURRRRDDRRDRRURRRDLLDDRRDRRDRRRRLLLDDRRDRRDRRLDDRDRRRULLDDRDRDRRRLDDRRRRURRDDRRDUURRDDRRDUUURRDDRRDLLLLDDRRDRRDLUURRDRRDUUURRDDRRDLLLLDDDDRRRRUURRDDDRRLDLLDDRDRRLULLDDRDRDRRRLDDRRRRURRDLLUUURRRDRDDLULUURRRDRDDRRDRDDLDDRRDULLLDDRRDRRDURRRDDRRLLDDRDRRRULLLLDDRDRRRDURRRRDRRRULLDLLDDRDRRRURRRDRLDDRRUURRDDDRRUUURRDDDRRLDLDDRRULULLDDRDRDRRRLDDRRRRUUUURRDDDDRRLLLDDRDRRLLULLDDRDRDRRRLDDRRRRURRDRRDRDUURRRDDRDUUURRRDDRDLUURRDRDLLUUUURRRDDDRDLDDRDURURRDRDLLUURRRDRDLDDRDULLLDDRRDRDURRRDLLDDRRDRDLULLLDDRRDRRDURRRRDLDDRRUURRDDDRRUUURRDDDRRUULLLDDRDRDRRRLDDRRRRURRDRDLULLDDRDRRDURRDRUUUURRDDDRRDRRLDLDDRRDLUURURURRDDLDDRRULULLLDDRRDRDRURRRDRLDDRRRDRULLULLDDRDRRDRURRRDRULLLLDDRRDRDRRLDDRRRLLDDRDRRRURRDRRLUURRRDDDRLDDRLUUURRRDDDRULUURRRDDDRLDDRLUURURRDDDDRLDDRLULULLDDRDRDRRRLDDRRRRURRDRRDRUURRRDDRDRLDDRURURRDDRLUURRRDDRLDDRDRLUULLLDDRDRDRRRLDDRRRRURRRDDRUURRRDDRUUURRRDDDRLDDDRURURRDDRURRDDDRLUURRRDDRLUUURRRDDDRLDDDRULUURRRDDDRURRDDDRLDDDRULLLDDRRDDRDDRLLDDRRDDRURURRDDRUUUURRRDDDDRLUUUURRRDDDDRLDDDDRULUUURRRDDDDRUULUURRRDDDDRLLUUURRRRDDDULUURRRRDDDUURRRRDDDRRRDDLDDRRRDDLLUUUURRRRDDDDLUULUURRRRDDDDUUURRRRDDDDULLUURRRRDDDUUUURRRRDDDDURRRDDDRRRRDDDRRRUURRRRDDDLUURRRRDDDUUURRRRDDDULUURRRRDDDLDDRRDDRRRRDURRRRDDLUURRDRRDLLDDRRDRRDRRRRLLLDDRRDRRDRRRRLDDRDRRRULLDDRDRDRRRLDDRRRRDRRURRDDRRDUURRDDRRDUUURRDDRRDLLLLDDRRDRRDRRRRLUURRDRRDUUURRDDRRDLLLLDDDDRRRRUURRDDDRRLDLLDDRDRRLULLDDRDRDRRRLDDRRRRDRRURRDRULLLDDRRDRRDRRRRURRRDLDDRRRRLULLLDDRRDRRDRRRRURRRRDULLLLDDRRDRRDRRRRURRRRDLDDRRRRULULLDDRDRDRRRLDDRRRRDRRLLDDRRDRRRRLLULLDDRDRDRRRLDDRRRRURRDRRURRDLUURRDRDLDDRDUURRDRDLULLLDDRDRDRRRLDDRRRRDRRUUUURRDDDDRRDLDDRDURRRDRDRRDLLDDRRDRDRRDLULLDDRDRRDRDLLLDDRRRDURRDRRLLLLDDRRRDRDRRRDLLDDRRRDURRRDULLLDDRRDRRDRRURRRDUULLLDDRDRDRRRLDDRRRRDRRURRDRDULULLLDDRRDRDRRRRURRRDRULLLLDDRRRDRULLULLDDRDRRDRURRRDRLUURRDRDRLLDDRRLULULLDDDDRRRRURRDRRLLDDRRDRRUURRRDDRLDDRUUURRRDDDDRLUURRRDDDRLDDRUUUURRRDDDDRLUUURRRDDDDRLDDRULUURRRDDDRLDDRLUUUURRRDDDDRLDDRDDRULLDDRDRDRLLLDDRRDDRLUULLLDDRDRDRRRLDDRRRRDRRURRRDDRUURRRDDRURRDDDRLDDDRLUURRRDDRURRDDDRULLLLDDRDRRDRURRRRDLUUURRDRRDDDLLUURRRRDDRRLDDRDDURRDDURRDDDRUURRRDDDRLDDRUUURRRDDDRLUURRRDDDRLDDRULUURRRDDDRLDDRLLDDRRRDDRLDDRLLLDDRRDDRLLLLDDRRRDDRURURRDDRDDR
This will work (unless my program is buggy), but I would be surprised if this is anywhere near optimal. And I'm not going to attempt a 10 x 10.
-
Was this a problem posed to a bunch of programmers? A solution for any 4x4 maze (although IDK whether or not this is an optimal one) is
SpoilerRRRDDDRRRDDURRRDDUURRRDDLDDRRRDRRRLUURRRDDLLDDRRRDRRRLLLDDRRRDRRRLDDRRURRDULLDDRDRRRURRDDRUURRDDRULLLDDRRDRRRLULLDDRDRRRURRDRDRLDDR
(Feel free to check it by hand for all possible 4x4 mazes if you like.)
But when I tried running the algorithm to solve any 5x5 maze, it's been running for a while and still hasn't found a solution. I can't guarantee that this approach will find one. I'll paste the perl code below.
Spoiler#!/usr/bin/perl use strict; use warnings; if (@ARGV < 1) { print "syntax: $0 MazeSize [Verbose]\n"; print "MazeSize is the size of the maze\n"; print "Verbose (optional) can be any value; "; print "this acts as a flag if you want\n"; print "to see everything while calculations are done\n"; die; } # Read the size of the n x n maze and whether or not # to be verbose from the command line my $size = $ARGV[0]; my $verbose = 0; if (@ARGV > 1) { $verbose = $ARGV[1]; } # The array $maze[$x][$y] will have each square of the maze plus # a perimeter of concrete blocks, so the ranges for x and y will # be from 0 to $size+1, where the values from 1 to $size are the # "actual" maze. my @maze; # Start off with an empty list of instructions my @moves = (); # The main loop # This will create each possible configuration of mazes for the # given size. # Then for each configuration, it will use a greedy algorithm (?) # to number each square in the maze with the number of steps to the # exit. And it will make sure that there is a path from the start # to the exit for this particular maze configuration. # Then it will make a robot at (0, 0) walk according to the current # string of instructions (if there is any) and find out where it # ends up. # Then it will make the robot follow the numbers from the spot # where it's standing to the exit and append that to the instructions. # # After it does that for every configuration of mazes, it will # go through all of that all over again, and keep repeating until it # goes through every confinguration of mazes without ever having to # append any more instructions to the current instruction set. # The $finished variable will be 1 if no more instructions needed # to be appended and 0 if any needed to be appended. my $finished = 0; until ($finished) { $finished = 1; # Make each possible configuration of mazes. Basically, you # take a binary number with n^2 digits and convert all the # 1s into cement blocks (-1) while leaving all the 0s empty (0). # The loop increments by 2 each step so the least significant # digit in the binary string is never 1, and only goes up to # 2^((size^2)-1) so the most significant digit is never 1 -- # otherwise the start or end position would be blocked. MAZELOOP: for (my $seed=0; $seed < 2**(($size**2)-1); $seed+=2) { my $sprintf_arg = "%0" . $size**2 . "b"; my $binaryseed = sprintf($sprintf_arg, $seed); if ($verbose) {print "\nBinary seed: $binaryseed\n";} for (my $x=1; $x<=$size; $x++) { for (my $y=1; $y<=$size; $y++) { $maze[$x][$y] = -1 * substr($binaryseed, -1, 1, ""); } } # Set the perimeter (cells with coordinate 0 or $size+1) to -1 for (my $x=0; $x<=$size+1; $x++) { $maze[$x][0] = -1; $maze[$x][$size+1] = -1; $maze[0][$x] = -1; $maze[$size+1][$x] = -1; } # Give the goal (the cell at $maze[$size-1][$size-1]) a # value of 1. Then use a greedy algorithm to give every # other square in the maze a number indicating how many # steps it would take to reach the exit (plus 1). # Continue until no new cells can be given a number. $maze[$size][$size] = 1; my $nextstep = 1; my $nomore = 0; until ($nomore) { $nextstep++; $nomore = 1; for (my $x=1; $x<=$size; $x++) { for (my $y=1; $y<=$size; $y++) { if ($maze[$x][$y] == 0) { if ( ($maze[$x-1][$y] > 0) || ($maze[$x+1][$y] > 0) || ($maze[$x][$y-1] > 0) || ($maze[$x][$y+1] > 0) ) { $maze[$x][$y] = -2; } } } } for (my $x=1; $x<=$size; $x++) { for (my $y=1; $y<=$size; $y++) { if ($maze[$x][$y] == -2) { $maze[$x][$y] = $nextstep; $nomore = 0; } } } } if ($verbose) { print "This maze is\n"; for (my $y=0; $y<=$size+1; $y++) { for (my $x=0; $x<=$size+1; $x++) { printf ("% i ", $maze[$x][$y]); } print "\n"; } } # Make sure that there is a path from the start to the # finish, which will be true if and only if $maze[1][1] # is greater than zero. Otherwise, go to the next step # in MAZELOOP next MAZELOOP if ($maze[1][1] == 0); if ($verbose) {print "This maze has a path to the exit\n";} # Make the robot follow the current set of instructions my $x=1; my $y=1; for (my $move=0; $move<@moves; $move++) { if (($moves[$move] == 0) && ($maze[$x+1][$y]>0)) {$x++;} if (($moves[$move] == 1) && ($maze[$x][$y+1]>0)) {$y++;} if (($moves[$move] == 2) && ($maze[$x-1][$y]>0)) {$x--;} if (($moves[$move] == 3) && ($maze[$x][$y-1]>0)) {$y--;} } # If the robot is not already at the goal while ($maze[$x][$y] > 1) { # Make $finished be zero $finished = 0; # And make the robot look for steps to reach a lower # number square if ($maze[$x+1][$y] == $maze[$x][$y]-1) {push(@moves, 0); $x++;} elsif ($maze[$x][$y+1] == $maze[$x][$y]-1) {push(@moves, 1); $y++;} elsif ($maze[$x-1][$y] == $maze[$x][$y]-1) {push(@moves, 2); $x--;} elsif ($maze[$x][$y-1] == $maze[$x][$y]-1) {push(@moves, 3); $y--;} unless ($verbose) { print "Current instructions:\n"; for (my $move=0; $move<@moves; $move++) { if ($moves[$move]==0) {print "R";} elsif ($moves[$move]==1) {print "D";} elsif ($moves[$move]==2) {print "L";} elsif ($moves[$move]==3) {print "U";} } print "\n\n"; } } if ($verbose) { print "Current instructions:\n"; for (my $move=0; $move<@moves; $move++) { if ($moves[$move]==0) {print "R";} elsif ($moves[$move]==1) {print "D";} elsif ($moves[$move]==2) {print "L";} elsif ($moves[$move]==3) {print "U";} } print "\n"; } } } print "\nFinal instructions:\n"; for (my $move=0; $move<@moves; $move++) { if ($moves[$move]==0) {print "R";} elsif ($moves[$move]==1) {print "D";} elsif ($moves[$move]==2) {print "L";} elsif ($moves[$move]==3) {print "U";} } print "\n";
-
I agree with Rainman; we need a description of how the marbles were selected to be placed into the jar in the first place.
If you were to say that someone flipped a fair coin 100 times and put a white marble in the jar if he saw head and a black marble in the jar if he saw tails, then that would be enough of a description to take on the problem. And I bet the answer would be a lot different if someone picked a random number from 0 to 100 with equal probability and put N white marbles and 100-N black marbles in the jar.
-
Ah, the hospital's rule. Of course. I vaguely remember that from high school.
More importantly, I also found out that my memory of integration by parts was faulty, and that seems to have been the real issue. From the top:
SpoilerIf we’re dealing with a Poisson distribution where the probability of having an interval x between two bags is proportional to e-x, then we need to re-calculate the probability of being a non-nearest neighbor segment. If you’re given a segment of length L, then the probability that it’s larger than an adjacent segment (or equivalently that an adjacent segment is smaller than L) is
Integral[x=0 to L] e-x / Integral[x=0 to infinity] e-x
[x=0 to L] -e-x / [x=0 to infinity] -e-x
(-e-L + e0) / (-e-infinity + e0)
(-e-L + 1) / (0 + 1)
1 - e-L
So the probability that both adjacent segments are smaller than L and therefore you have a non-nearest neighbor segment is the square of that, or
1 - 2e-L + e-2LIn my previous calculation, a segment would appear with uniform probability regardless of its length, but in this case the probability that you would observe a segment of length x is dependent on the value of x. To account for that, the ultimate value you want is the integral of [length of the segment] · [probability of seeing a segment of that length] · [probability that it’s a non-nearest neighbor segment] divided by the integral of [length of the segment] · [probability of seeing a segment of that length], which would be
Integral[x=0 to infinity] x·e-x·(1-2e-x+e-2x) / Integral[x=0 to infinity] x·e-x
Integral[x=0 to infinity] xe-x-2xe-2x+xe-3x / Integral[x=0 to infinity] xe-x
Split the terms in the numerator and use integration by parts to get
[-xe-x – Integral(-e-x) + xe-2x – Integral(e-2x) – 1/3 xe-3x – Integral(-1/3 e-3x)] / [-xe-x – Integral(-e-x)]
[-xe-x – e-x + xe-2x – -1/2 e-2x) – 1/3 xe-3x – 1/9 e-3x] / [-xe-x – e-x]
[-(x+1)e-x + (x+1/2)e-2x – (1/3 x + 1/9)e-3x] / [-(x+1)e-x]
When you evaluate the numerator and denominator over the range from x=0 to x=infinity, all of the terms at x=infinity go to zero because of the e-x terms. So just take the negative of the x=0 value, and you get
[1e0 – 1/2 e0 + 1/9 e0] / [1e0]
[1 – 1/2 + 1/9] / 1
11/18 -
On 3/12/2018 at 1:53 PM, bonanova said:
For Poisson, appropriately scaled, cumulative prob for (L<x) is F(x) = (1 - e-x) and the pdf for (L=x) is f(x) = F'(x) = e-x. So f(x) says our interval is x, and F(x), for each neighbor, says that's longer than they are. So a large interval's expected length is int (0,inf) {x f(x) F(x) F(x) } dx. (The same integral without the x gives the probability that an interval is large. Turns out it's 1/3.) Integrate by parts using u=x and dv= { f F2 dx } = (1/3) d( F3 - 1 ). Then the (uv) term {x (F3 -1) } is zero at both 0 and inf, leaving just int (0, inf) ( 1 - F3 ) dx = int (0, inf) { 3e-x - 3e-2x + e-3x } dx. Was your inf involved with the (uv) term?
If you do that and the (uv) term is x(F3-1), then at x=infinity wouldn't you end up with infinity times zero?
If there's a rule about the limit of multiplication between x and functions with e-x as x goes to infinity, then maybe I could use that in the route I was taking.
-
Two more clarification questions
SpoilerFirst, I see no reason to ever use the 75 cent option. If you pay 75 cents to get two pieces at random and you don’t return a piece, then you would have been better off using the 25 cent option twice and spending 50 instead of 75 cents. If you pay 75 cents to get two pieces at random and do return a piece, then you would have only spent 50 cents, but you would have gotten two random pieces and returned a non-butterscotch piece. You would have been better off paying 25 cents twice to get two random pieces without returning a non-butterscotch, because if you do return a non-butterscotch then that just decreases your chances of getting a butterscotch on subsequent rounds. If that analysis is wrong because of an incorrect assumption then let me know.
Second, I think it could make a difference exactly how the 1.50 option works. Specifically, if the machine would have randomly pulled out five non-butterscotch candies, would it drop one of them and pick up a butterscotch? Or would it drop all of them back into the bin and mix all the candies still in the bin and then draw five more random candies? Or would it set the five that it picked aside and draw five more candies that were not in its initial draw before dumping everything back into the bin?
-
Is it allowable to design a key that can open multiple different locks?
If each lock has multiple positions where a subset of the pins at each position (potentially at different positions for each lock) need to be raised to the correct height in order to be opened, then it would be fairly straightforward to design one key for each general while still using the total number of locks in the answers above.
If you're limited in how many positions the pins of a lock can be in, then things might get complicated.
-
On 3/14/2018 at 9:09 AM, Molly Mae said:
You could represent the bazillion dollar coin as a binary number using the first 10 coins. That covers the 2
10 possibilities. You can make it more efficient by using the 11th bit to define whether heads is 0 or 1. This saves flips in the event that you need to flip more than half of the coins to make the correct binary number. Depending on the number of coins, you could extend or reduce the amount of bits you use by using the fewest bits that can represent the highest possible number.
So if you have N coins to choose from, instead of needing log2N coins to specify its position you can guarantee that you only need (log2N / 2) + 1 flips. Nice move to halve the upper limit, but with 1000 coins you could still be in for an hour of nyan.
On 3/15/2018 at 4:54 AM, plainglazed said:Flip coins to make the bazillion coin the center of the longest string of the same value (heads or tails). Would expect about nine consecutive heads or tails would be enough to be both easily spotted and not take very many flips. At some point it could make more sense to break up other existing long strings vs adding to the indicating string. The downfall of this strategy is if the valuable coin is near either end, but you could strategize to flip the first or last coin to heads if the money coin is in the say first eight coins and the next three coins then tell at what position taking at most five flips, otherwise flip (if necessary) the first and last coins to tails.
That might work well for random configurations ... the math to figure out how many flips it would take on average would be difficult and maybe worth being its own question. But the worst case scenario if the bazillion coin is in the middle, the left half is all heads, and the right half is all tails would be a real pain.
Coin hunt
in New Logic/Math Puzzles
Posted
That looks like it nailed it, PG! As for a way of saying it in under a minute...
... use the binary operator XOR