Bit late to the party, but I still wanted to pop in and thank everyone who contributed tricks and work to this awesome run. And it's cool to see a few other old names pop in again for this occasion *waves*
I remember times where we thought that movement in super metroid was fully understood, and all that remained was to compare more route variations and to do better subpixel optimizations. The heap of new techs in this run pleasantly proves that wrong. I didn't expect to ever see a 100% route this smooth, nor a maridia back entrance, but I'm really happy that I did.
So here's the obligatory pointless yes vote on a published run.
I'm not aware of any general purpose compressor that will detect backreferences with a distance of more than a gigabyte. It's not exactly a common use case.
There are special archivers (like bisqwit's cromfs), and there are ways to store duplicate files as hardlinks (like rdfind), but those are linux only.
Git is simply the best solution here. It's not particularly fast with large, binary files, but it compresses them really well if you kick it in the right place.
Commit all the files, then run
> git gc --aggressive
and it should try to compare all files against each other to determine which are just minor changes of another.
On the other hand, worrying about 8 GB of disk space? What year is this?
I'll just leave a couple of links that the riddler omitted.
If you're going to turn to wolfram, don't ignore this page:
http://mathworld.wolfram.com/GoatProblem.html
More decimal places of the solution can be found on
http://oeis.org/A133731
Turns out this problem also has a Wikipedia page, which claims that the problem was first published in 1748.
It is an old problem; the oldest variation I could find was published in 1982. I've tackled it before (on a different forum) and I'll leave two hints:
1) one possible approach is to use formulas from here: https://en.wikipedia.org/wiki/Circular_segment
2) no matter your approach, you'll get a tangled mess of a formula which you cannot solve. Do a numerical approximation.
EDIT: It looks like not even 7 is the optimal. It's possible to get 6! To do this I used a computer program, though. The quick and dirty code below gets the job done. There are many solutions that get 6. The first one that appears is (1,4,13,29). When target is set to 5, no solutions appear:
Your code got mangled there, but it's easy enough to see the dynamic programming invariant.
It's worth noting that these solutions don't allow people to use the greedy strategy when giving change: just keep tossing the highest-valued coin that's smaller than the remaining change.
98 = 29 + 29 + 29 + 4 + 4 + 1 + 1 + 1 (8 coins)
as opposed to
98 = 29 + 29 + 13 + 13 + 13 + 1 (6 coins)
The riddle specifically asks to optimize without regard to anything else, but any actual currency I know does make sure that the greedy strategy is optimal.
The best solutions appear to be (1,5,18,25) or (1,5,18,29); of all the solutions with a maximum of 6 coins, these have the lowest average coins (3.89).
/edit: I got a bit ninja'd there.
A bit disappointing, but not entirely unexpected: allowing coins with negative values does not yield any better solutions, though (-1,2,11,28), (-55,8,13,15) and several others work with 7 coins.
That test is technically true, but in practice it rejects too few candidates to be useful.
To figure out the exact percentage, try figuring out (or finding) a proof for your first claim. Work backwards to figure out the minimal requirements for your candidate for the proof to work. See how many mersenne candidates satisfy those requirements.
(I've done it, but I won't spoil the results for now. It's insightful to do on your own.)
Revisiting the Riddler's problem, I found a simple way to prove that, for every base b, there is a minimum N, depending on b, for which all base b sequences of length ≥N have a solution.
Beautifully simple. Induction over base is a clever approach.
N10 = 1024 is quite a loose bound, but that's fine.
FractalFusion wrote:
I assume this is what Tub really wanted to believe the actual problem was
Brute forcing wouldn't answer the question if there was no minimum length, and it wouldn't answer the question within a week if the minimum length was just a bit larger than 7. It just didn't seem like a promising approach.
Since we know that every sequence with 7 digits has a valid equality, we can say for sure that for every sequence with N ≥ 14 digits there is a valid equality.
That is true. I can sleep better now. It's not a pretty proof if it involves a 10-million-element lookup table, but it's a proof.
Now that I have a bit more time, let me document my failed approaches anyway. Try to prove that every sequence with at least N digits contains a subsequence that evaluates to 0 when you add the right amount of ()+-*/^, but not =.
If you can prove that, then every sequence with 2N digits can be turned into an equation 0 = 0.
Trivially, if there's a 0 in the sequence, you're done.
If there's a repetition (11 or 123123), you're done (1-1 or 123-123).
If two neighbouring subsequences are permutations of each other (123321), you're done (1+2+3)-(3+2+1).
I've tested the latter by recursively generating a counter-example; as said I've found a sequence with 10.000 digits that was free of successive permutations.
Fun fact: you can generate such a sequence with only four different digits. Using this approach, I can answer the riddler's question in all bases up to 4 (yes, given a sufficient length, you can always make a true equation), but not for base 5 and above.
Another approach I tried involves finding a subset that satisfies the Partition Problem. The wikipedia example is S = {3,1,1,2,2,1} => S1 = {1,1,2,1} and S2 = {3,2}
Prefix everything from S1 with + and everything from S2 with -, then 311221 can be turned into -3+1+1+2-2+1 = 0
But not every sequence can be partitioned in such a way, no matter the length (like you mentioned, if the sum of all digits is odd). Fortunately we only require a subsequence to be partitionable, but I wouldn't know how to prove that, if it is true.
Going away from 0, you can also try to prove that every sequence of length >= n begins with a subsequence that can evaluate to 1. Then every sequence >= 2n can be turned into
1^(stuff) = 1^(stuff)
I had no luck with that, either.
The "solution" to last week's Riddler classic infuriates me. So is there a minimum length, where every number can be turned into an equation or not?
This is not a computational problem. Even showing 100% solvability for n says nothing about n+1. And you cannot compute all n.
I tried to find a strategy to turn any sufficiently long string into 0, turning the equation into (stuff) * 0 = (stuff) * 0 * (stuff), but with mere addition and substraction of single digits, that's not always possible up to n = 10.000 (I aborted the search there). I found no way to generalize a more complicated strategy. Did any of you have more luck?
However, I've never understood how time traveling into the past in theory works (never mind all the possible paradoxes that could bring). Despite physicists saying it's theoretically possible to do.
There are solutions to the formulas of general relativity which contain closed time-like curves, and those would allow at least some form of backwards time travel.
One solution with closed time-like curves involves wormholes. Wormholes cannot just connect different points in space, but also different points in time (if they don't, just accelerate one end, and time dilation does the rest). Now if the time difference is huge, and the space distance is small, then it's possible to enter the "future" end, arrive at the "past" end, then travel outside the wormhole back to the "future" end. If you're fast enough, you can arrive before you left, meeting younger yourself, and then you get to have sex with your grandma or something (I forgot how these work).
All these theorized forms of time travel involve regular travel along weird spacetimes. There's no machine with a dial you can set to "hitler's birth", and *poof* you're there - never mind the fact that such a machine would get the location wrong, due to the earth constantly moving. If you have a sufficiently weird spacetime, then your time machine is a regular space ship, and the journey will take time (i.e. the travelers will age).
However, it is not at all obvious if such solutions describe (parts of) the universe we live in.
For one, the fact that something would not violate GR does not imply that it exists. More intuitively, a skyscraper made of unicorn-flavored pudding does not violate GR. That doesn't mean that one exists, it doesn't even mean that one can be constructed, and it certainly does not imply that such a thing would be stable. Same with wormholes.
Second, GR is not an accurate description of our universe, because it ignores quantum effects. As far as I'm aware, all solutions with closed time-like curves contain parts where quantum effects are expected to be significant. We'll have to wait for a theory of quantum gravity, and then re-run all those solutions. Many physicists expect the closed time-like curves to go away when including quantum effects.
You can also start at the other end, QM. The schrödinger equation is pretty clear on the concept of time, and that does not involve time travel. But it's not a complete and accurate description of our universe, either, so we still don't know.
tl;dr: backwards time travel is really unlikely, but has not conclusively been proven impossible. GR says "maybe", QM says "no", and at least one of those answers is wrong.
So the problem is that Link is a germophobe, and he's afraid of touching unsanitized door knobs? But when someone else opens the door for him, it's fine to go through?
How would a player's strategy change if the boxes they open depend on previously opened boxes? If they don't find their own name in a box, does it offer any information about where their name is?
The additional information is the knowledge of the names in the box, combined with the knowledge that a previous player has not yet failed the game while employing a certain strategy based on names.
For example, let player 1 open box A and read the name. If it says "player 2", open box B, otherwise open anything but box B.
Let player 2 open box B and read the name. If it says "player 1", and player 1 has not failed the game, then the name "player 2" must have been in box A. There's your additional knowledge; reading either "player 1" or "player 2" is a guaranteed win, while anything else would still allow random guesswork.
I've formalized a simple strategy and done the math on a 4-player game. Unless I've miscalculated again, that'd yield roughly twice the winning chance of the unmodified game.
The strategy can be generalized to the n-player game, but I haven't done the math on that. I'm sure the formula is somewhere in some combinatorics textbook.
/edit: alright, I've found this gread combinatorics textbook called "wikipedia", which not only has the formula, it also links to the name of the problem. It yields ~30% for the 50 of 100 case, and the name is a bit less game-show-like, the 100 prisoners problem. Since the ridder's deadline is over, I've linked it, but it's fun to try to figure out before reading.
*sigh* if multiple people smarter than me fail to match my solution, then obviously my solution is wrong.
After I finally found my mistake, my solution actually matches bobo's ~1.635. thatguy's post reads like he should also arrive at the same value.
You have a fixed area (3x 1/3), and for f miles of fencing, the sum of all three circumferences is 4+2*f.
Minimizing the sum of circumferences means that you want all three areas to be roughly circle-like. Cutting two circle-like areas from the corner seems useful, until you realize that the remaining third area is way too inefficient.
Same with curves. They seem efficient because they optimize one side of the fence, but they'll turn the other side of the fence into a concave mess.
Intuitively, the only strategies where all three areas remain roughly circle-like and convex are those with a point somewhere in the middle and three straight fences to the property border. My solution with ~1.533 is one of those, but I cannot prove whether it's optimal.
For Classic, I obtained an optimal strategy that was better than 1 in 10.
My first guess resulted in something "better than 1 in 10". As the riddler did not ask for optimality, that'll do.
This could be improved to 1 in 3 if you decide that the rules don't explicitely prevent you from swapping the contents of the two boxes you opened ;)
Bobo the King wrote:
Without going into too much detail, the best strategy I found used a hair under 1.633 miles of fencing.
There is a simple strategy with 1.666 miles of fencing, so I suspected that 1.633 is not optimal. I tried one variation, wrote a function determining fence length based on a certain angle, then used wolframalpha to determine the global minimum, arriving at a pretty odd number: ~1.533 miles. Not sure if that's optimal, but it's enough to send you back to the drawing board :p
/edit: or maybe yours was a typo and you got 1.533 too?
Bobo the King wrote:
I drew some inspiration from bubbles, which tend to maximize volume for a given surface area and are often straight lines. Of course, in retrospect, there are plenty of situations where a bubble follows a curved path...
AFAIK bubbles are only round on the outside. Boundaries between touching bubbles always end up straight (at least those I've observed).
My solution has just straight lines, and I don't believe that curving any of them would yield further improvements.
I did another attempt using run-lengths. Assuming you can still see your friends (and not just their hats), you assign places in a circle to everyone.
Notation (3, 2, 1, 1) means that along the circle, there are 3 of one color, 2 of the other, 1 of the first, 1 of the other. I'll always list the longest run first (or, in one case, the shortest one last), which usually means that 14 hat-combinations exibit this behaviour (7 through rotation, times two for switching colors).
A) 2x (7)
B) 14x (6, 1)
C) 14x (5, 2)
D) 14x (4, 3)
E) 14x (4, 1, 1, 1)
F) 14x (3, 2, 1, 1)
G) 14x (3, 1, 2, 1)
H) 14x (3, 1, 1, 2)
I) 14x (2, 2, 2, 1)
J) 14x (2, 1, 1, 1, 1, 1)
9*14 + 2 = 128, so we didn't miss anything. What properties can we use?
Most patterns have four runs.
Rule: If your neighbours have the same color, guess in such a way that the number of runs is four. This fails all patterns with 2 or 6 runs, while pattern A gets no guesses
Revised rule: Additionally, if you see 6 of the same color, guess the same color; thus winning pattern A
Result: 72/128 ~ 56.25%
Most of the patterns have exactly one run with length 3 or more; only D has two, and I+J have none.
Rule: If your neighbours have the same color, find the longest run not involving your neighbours. If there is none (i.e. you see 6 of the same color), do not vote. If the longest run has a length of 1 or 2, vote the same color as your neighbours. Winning B,C,E,F,G,H, failing I, J, no guesses on A, D
Result: 84/128 = 65.6%. Again.
Not sure if further improvements are possible with this.
Ok, apparently this isn't spoiler-free any longer. Let's talk business.
Bruno got the same chance as I did, but his rules are a lot more complicated.
My strategy is: if you see exactly 4 or 6 hats of the same color, guess the other color. Otherwise, pass.
This will win on any 1/6 or 3/4 split, but is guaranteed to lose on 0/7 or 2/5. Works out to 84/128 ~ 65.6%, too.
Bobo the King wrote:
Maybe we can come up with a Bayesian analysis of this problem along the lines of P(my hat is white|I see six black hats) etc.
That P is 0.5, no matter what you do. That path does not lead to a solution.
/edit: there is no communication after the hats are chosen. The riddle says so. Nobody knows what anybody else has (or hasn't) guessed.
No communication is possible during the game — you make your guesses or passes in separate soundproof rooms — but you are allowed to confer beforehand to develop a strategy.
If "randomly" means 50/50 chance for everyone to get either black or white, then the resulting distribution has some patterns that can be exploited.
No single person can do better than 50/50. But the outcome of the contest is not determined by one guess. If you can manipulate it in such a way that you have a high likelyhood of few people guessing correctly (and everyone else passing), and a low likelyhood of everyone making a wrong guess, then the average outcome of each guess is still 50/50, but the chances of winning the contest have improved.
While I was still working out the numbers, BrunoVisnadi has already posted a great hint. With seven people, I can find a simple strategy for ~54.7% chance of winning. With a bit more complexity, I can improve the strategy to ~65.6%.
The riddle doesn't say anything about the friends being arranged in a circle (or otherwise having an order), so I'm out of ideas for further improvements.
I cannot copy/paste, so here's the condensed version:
User Agent: Mozilla/5.0 (Maemo; Linux U; Jolla; Sailfish; Mobile; rv:31.0) Gecko/31.0 Firefox/31.0 Sailfish Browser/1.0
The webworker variant works just fine. Results are all correct, times are:
14218
27692
54854
109917
221785
28118
55778
111557
Then the phone locked and stopped executing javascript, and I'm not in the mood to restart and keep tapping my phone.
AMD E2-1800 APU with Radeon(tm) HD Graphics
If I remember, I'll try on a ryzen tomorrow.
Oh and by the way, opening braces on the same line if you're using javascript.,
If you need to understand why Q isn't divisible by any of the established primes, then the simplest intuition I know is this:
For every integer p, if X is a multiple of p, then X+p is the next multiple, and any number in between X and X+p (including X+1 for p > 1) is not divisible by p.
This gets cleaner and more rigorous by invoking modular arithmetics, but you don't need to know modular arithmetics (nor trigonometry) to understand it.
You still haven't told us what you mean by "smooth". You can make it C1-continuous by deriving both functions, comparing their value at x=0.5 and scaling until they match. That's easy.
If you require C2-continuous or more, moving the center point won't be enough.
Css transitions use cubic bezier curves for easing. IIRC they're perfectly smooth, and the parametrization used in css guarantees that the curve is monotoneous in time and doesn't self-intersect. For any real application, I'd use those.
If you can guarantee satisfaction, you can have the bed and my wife takes the couch. <3
Seriously, I'll talk to her and get back to you in a day or two. PM me your email address please; I don't check these forums as often as I should any more.
Roaming costs within the EU should have been completely eliminated... 6 days ago, actually. But you may need to provide your passport when buying a SIM (because, you know, terrorists couldn't possibly buy a SIM on ebay), and I don't know if a russian passport will do. Maybe someone from Finland knows details.
