hmm, wikipedia may be on your side there. I was going by the definition Bobo gave in his post
However, we can define a larger infinity by taking the power set of the set of all integers. By theorem 2, the cardinality of this set is necessarily strictly greater than aleph-0. We define this new cardinality to be aleph-1. (Incidentally, it is undecidable without a further axiom whether there is another cardinality between aleph-0 and aleph-1. Fortunately, it's irrelevant to the problem at hand.) Aleph-1 is also infinity, but it's a strictly larger infinity than aleph-0. It also happens to be the cardinality of the set of any continuum.
Finally, we are ready to construct aleph-2. To define it, we just take the power set again! That is, we need to take the set of all subsets of the set of all subsets of the integers. This is an even larger cardinality and so is given a new name, aleph-2. You can continue taking power sets to construct aleph-3, aleph-4, and so on.
That definition seems more convenient if one didn't assume GCH, since all aleph-numbers remain well-defined and workable without - none of the things we talked about actually require the GCH. It just isn't the "official" definition and we should have talked about |N|, |2^N|, |2^2^N|, ... instead of aleph-numbers.
So, again, the set of all closed curves has the same cardinality of R.
Hmm.. can you please look over my attempted proof 8 posts above this and tell me where I went wrong? I suspect that my fuzzy block isn't "continuous", but I lack the proper definitions for "continuous" that I'd need to satisfy.
thatguy wrote:
Maybe we should have a separate thread for maths PhD students and postdocs... this is going over my head a bit.
I'm just a computer science student with a bachelor (soon master), neither math nor PhD. While some basic math education beyond high school is certainly required for some topics, it's often enough to spend an hour on wikipedia and google. Can you guess that I never worked with curves before Bobo posted his challenge?
A bit of time may be required, but after all, the thread title is math *challenges*, not math trivialities.
Warp wrote:
Tub wrote:
|2^R| = aleph-2.
Doesn't that assume the generalized continuum hypothesis? (Or am I misunderstanding something about it?)
No, the definition of aleph-numbers is
aleph-(n+1) = 2^aleph-n
The GCH only states that there's no additional cardinality between aleph-n and aleph-(n+1), but that's neither relevant for my statement you quoted, nor for the proof p4wn3r posted.
ok bobo, this is starting to annoy me. You said you asked your professor, but claim you don't know the answer - so a math professor didn't know, either?
I've been trying to approach it step by step. Starting with the not-so-curvy-curves, also called polygons.
There's a bijection from R to the set of all polygons in 2-space, by the following algorithm:
a) transform the real into an infinite bitstring (like we discussed a few pages ago)
b) read a positive integer from the beginning of the bitstring (there are ways to read an integer of arbitrary size while consuming only a finite amount of bits. I can elaborate if you want me to). Add 3 to the integer to get n = the amount of vertices of the polygon.
c) by bitwise deinterleaving, split the rest of the bitstring into 2*n infinite bitstrings. Transform each of these back into a real and use them as coordinates for the vertices.
So the set of polygons has cardinality aleph-1; the set of simple polygons cannot be larger.
We can simply make it a bit more curvy by allowing each edge to be a bezier curve, by reading an additional 2 points per vertex to be used as control points.
But how "curvy" can we make it without requiring more than a finite amount of reals per edge? What if our curve is fractal in nature, like one connected region of the mandelbrot set, and cannot possibly be approximated by a polygon with a finite amount of edges?
At this point I'm not sure about the exact definition of a simple, closed curve. But let me try one final injection:
P([0,1]) -> C
We take a subset S of [0,1] and construct the interior area of a curve as
I = { (x, 0) | x \in S } \union { (x, y) | x \in [0,1], y \in (0, 1] }
We get a 1x1 block where one of its edges is a bit fuzzy. It is unique wrt rotating, scaling and translations; to make it unique wrt reflections we could just add another feature at either side.
For any point in the set, there's another point arbitrarily close to it. Is that property enough to claim that it's connected, and to claim that its border is a simple, closed curve?
If so, we finally know
aleph-2 <= |C| <= aleph-2
The proofs for both bounds work regardless of the restrictions wrt rotations and reflections; so the set of all curves, and the set of non-congruent curves must both have the same cardinality.
There's a trivial injection
R+ -> C
where you map each positive real number x to the triangle (0,0), (-1,0), (x,2) - they're unique including rotations and mirroring, even including scaling and translations.
So it's at least aleph-1; intuitively, one would expect it to be strictly larger.
It's also at most aleph-2; intuitively, one would expect it to be strictly less.
I'm hoping it's right in the middle so we can get a paper out of this ^^
Bobo the King wrote:
This hints to me that the cardinality of the set of all simple, closed curves is actually strictly less than 2|ℝ|.
Bobo the King wrote:
I think it's unlikely that the cardinality is less than aleph-2
|2^R| = aleph-2.You can't really assume both at the same time ;)
What is the cardinality of the set of all simple, closed curves in two dimensions, excluding all rotations and reflections? If you cannot prove it easily, can you provide a lower bound on its cardinality? If you can quickly prove that its cardinality is greater than aleph-2[..]
Going by wikipedia about the aleph numbers.. We'll be assuming AC for this one, right?
With C being the set of 2d-curves and P(x) the power set of x, there's obviously an injection from
C -> P(R x R)
where you just map a curve onto the set of all points (x,y) on the curve (or inside the curve, either one works). Since
| RxR | = |R| = aleph-1
we know that
|C| <= |P(RxR)| = 2^aleph-1 = aleph-2
Since you hinted that it must be greater than aleph-2 I'll accept that as proof by authority and state:
|C| = aleph-2
Or we could find an injection from an aleph-2 set onto the curves, but I'm having trouble with that.
My first idea was to start with
P(R+) -> C
Order the given set, then draw a "circle" around the origin with varying radius. Always starting with the smallest radius at the same angle (i.e. towards positive y direction) would account for rotations, always going clockwise would account for reflections.
But we need to interpolate the missing pieces of the curve, and if we just added one of the interpolated points to the initial set, we have a second set that maps to the same curve. Or rather an uncountably infinite amount of sets mapping to the same curve.
And there's also the problem of infinite subsets of R+ potentially neither being countable, nor having a smallest element, so the whole "ordering" idea goes out the window.
Before we do any bitwise interleaving, we'd need to define a unique bit-representation of a real. There's always the duality of 1.0000... and 0.1111..., which we need to get rid of.
One might be tempted to just disallow all representations that end in an infinite series of 1, thus working on a well defined subset of all infinite bitstrings. But bitwise interleaving is not a bijection between that set and that set squared: try a number ending in .....10101010... It is within the allowed set. But when splitting into two numbers, one will end in ...1111.. and is thus outside the set.
Bitwise interleaving is better suited to programming problems, where bit representations tend to be finite (and thus unique).
I guess the easiest way would be to scroll up 5 posts, where p4wn3r already described a bijection between reals and all infinite substrings. Those are safe to interleave, just pretty far from the binary representations we're used to.
Oh. I overlooked the connection from subsets to infinite bitstrings. Finding a bijection from the latter is still tricky, but obviously easier than going directly from subsets.
Thanks for the detailed writeups!
some numbers have two decimal expansions though (1.0000... = 0.99999...). Though the constructed number differs in at least one digit from any in the list, that alone doesn't suffice to claim that it's not equal to any.
That doesn't invalidate the proof, but it'd require at least an additional sentence to take care of, if you want to be rigorous.
Warp wrote:
(Therefore, I surmise, the CDA cannot be used to demonstrate that the set of irrational numbers is uncountable...)
Indeed it cannot. But as flip said, once the uncountability of the reals is established, there are simpler proofs for that.
Now for a question of my own: the cardinality of the reals is supposedly equal to the cardinality of the power set of all integers, or
| |R | = 2^{ | |N | }
Is there an actual, intuitive bijection between the set of reals and the power set of the integers? Wikipedia lists proofs that the cardinalities must be equal, but nothing as nice as a bijection.
No, canthors argument is valid. Either the constructed number is not in the original set, or the list is incomplete. Possibly both. So in each case, you need to examine both possibilities. If you can exclude one, it must be the other.
With the rational numbers, we know that a complete list is possible (you can construct one if you like). But we shouldn't assume that the number we constructed is rational, since we didn't construct a fraction of integers, but an infinite decimal representation. A randomly constructed infinite decimal representation is almost surely not rational anyway; in this special case the construction guarantees that it's not.
With the reals, the constructed number is guaranteed to be a real number between 0 and 1. After all, we have its infinite decimal expansion and it starts with a zero before the decimal point. Thus, it's a real number between 0 and 1. You cannot conclude that it's "not a real number"; we know it has to be.
Since we know that the constructed number should have been in the list, but isn't, the list must be incomplete, thus the premise of enumerability must be false.
I remember playing this game back then on my Amiga, 22 years ago. Man, I'm getting old. Thanks to the password system one could just restart where one left off. It still kept me busy for quite a while, but eventually I made my way through all 100 levels.
There is already an unassisted speedrun over at sda:
http://speeddemosarchive.com/Pushover.html
I can't do a comparison this week (I'm on vacation and have very limited bandwidth here), but does the TAS visibly improve the unassisted run in terms of strategies or precision? And how does the actual run time compare?
Yes, I agree that each thing has a good purpose, and I use all of them, but which case did I mention that unique_ptr fits the bill?
I was refering to asprintf from your blog post. Or anything else that would be called a "factory" in java or a "source" in c++. Returning std::unique_ptr<Object> instead of Object * makes ownership transfer explicit. It also defaults the calling function to deallocate the object, requiring special code to keep it alive, instead of the other way around.
Just one?
Use after free.
Double free.
Anything derived from the above.
I was counting instances of bugs, not types of bugs. I can't remember when I last had a double free bug in my code (or 3rd party library code). Usually, the free'd pointer goes out of scope anyway so it isn't much of an issue.
YMMV of course.
Note though that unique_ptr prevents both types of bugs you mentioned.
You present a case where pointer nulling is absolutely required, and that's in functions which allocate and return a new object, but have multiple failure conditions. Manual cleanup of the already allocated resources is an error prone process, and nulling of the return pointer is important.
However, the manual cleanup code disappears once destructors, unique_ptr and friends appear; just throw an exception or return nullptr and all is well.
What I was getting at: memory and error handling in C is a pain. Advising meticulous pointer nulling and error checking seems weird when there are better alternatives available, that can do the job with less code complexity (=fewer possibilities for human error), equal memory consumption and better performance. And I'm not aware of many platforms where C compilers exist, but not C++ compilers.
Nach wrote:
std::unique_ptr is rarely the best solution though, as very often, you'll be better served with an std::deque, std::vector, std::string, or something along those lines. In a ~25,000 line library I have, new is only called in two places.
Also, don't forget about std::shared_ptr.
Each tool serves a purpose. For functions that return a pointer to a newly allocated object (like your example), unique_ptr fits the bill. (Or, in your special case, std::string)
OmnipotentEntity wrote:
Using make_shared and make_unique are generally advised for performance reasons because of cache locality (ie, they can use just one call to new, to contain both the object being held and all of the various doodads that the pointer class needs, rather than taking some object that's already been newed somewhere, and newing somewhere else the pointer information.)
That's true for shared pointer, since the reference counter and the object get allocated at the same memory location. unique_ptr does not have a reference counter or any other memory overhead (it's just a pointer!), and make_unique does not improve performance.
There are three reasons make_unique is useful:
* For exception safety in certain situations: http://herbsutter.com/gotw/_102/
* for brevity, auto x = std::make_unique<MyClass>(1, 2, 3) is shorter than std::unique_ptr<MyClass> x( new MyClass(1, 2, 3) );
* for consistency with make_shared etc.
OmnipotentEntity wrote:
C++14 is near or at its final draft, and because make_unique is considered a correction of a defect in C++11, I don't see it going away in any quantum reality.
If it should go away, it's a template function with 5 lines of code and thus trivial to reimplement.. all you'd need to do is refactor it to a private namespace.
As those above me said, for optimal results, you don't stop searching until it's perfect. Though it's understandable if you don't want to invest the time required.
A good starting point would be to dissect the RNG. Which memory locations are related? What's the algorithm, what's the periodicity?
If, say, there's only 256 RNG states (which isn't really uncommon in games), you can write a LUA script to generate the next level based on each of the 256 states, pick the best one and make it happen. (or, for the first level, pick the best ones and compare RNG waiting time to level time). With just 256 states, you could just make a screenshot of each layout and manually pick the best.
If there are more than 256 RNG states, you'd need an algorithm for determining which layouts are good, then manually compare the best ones. As you noted, such an algorithm is nontrivial to write. Minimum number of blocks between start and goal is a good metric. Items on the path is a good metric, the closer to the start the better. And so on.
A way to deal with different conflicting metrics, when one lacks a total cost function over all metrics, is to use a skyline filter.
Example:
Layout A requires bombing 10 blocks and yields 3 flame powerups on the way.
Layout B requires bombing 9 blocks and yields 4 flame powerups.
Layout C requires bombing 8 blocks and yields 2 flame powerups.
Since layout B is better or equal to A in every single metric, layout A can be discarded. With layouts B and C, either has its advantages, so neither can be discarded.
While this will still leave a bunch of possible layouts to manually check, it can remove a lot of obviously inferior levels.
except personally I think the fastest time should be the No.1 goal no matter what.
I disagree. Finishing four games at (roughly) the same time requires an impressive amount of planning.
The alternative would be to finish SMB1 ASAP, then playing the second half as a Triplerun instead of a Quadrun. I feel that that'd violate the spirit of the category.
thatguy: the twist is 360°, not 180°, so it's still two-sided.
However, if you trace the borders of the neck and back openings, you have two rings. In the normal shirt, they're separate. In your shirt, they're intertwined. I believe that you cannot separate that link without cuts.
/edit: I need to type faster. ;)
Good suggestions, thanks.
When trying to install them, most just claimed to be "not compatible with my device", though neither said why. My android version is above the claimed minimum, and no other requirements were displayed.
ScummVM then allowed me to click on "install", but that failed with a very arcane message. The internet suggests this happens every time google updates their play store, and I should just clear all caches, remove my google account, restart the phone and reinitialize everything - that should fix the problem. Though when I try to remove the account, my phone says I cannot do that and I should just reset the phone to factory settings. Because google updated the play store. Right. Seems sensible.
I'm starting to wonder whether I accidentally bought a windows phone.
In any case, it seems like I cannot install apps any more, so I guess I'll have to start reading books :(
Thanks for your suggestions, anyway. I didn't know about PPSSPP before, and will certainly try it on my non-android computers.
Hello,
I'm in desperate need for some entertainment on my new daily commute, so I tried to turn to mobile games. Unfortunately, almost anything I can find on google play wants full access to network, contacts, personal data, maybe the ability to initiate calls and send SMS, and this one game even asked for my mother's phone number. My faith in humanity was badly hurt when I noticed how many people had gladly installed such obvious malware.
So.. who can help me find the pearls in the giant pile?
I'm currently busy with lazors
https://play.google.com/store/apps/details?id=net.pyrosphere.lazors
The version I have installed is quite old, completely free, didn't even ask for network access. Not sure about the current version; I cannot upgrade because it's not compatible with my device for an unspecified reason.
Any other suggestions? Emulators are obviously acceptable, open source preferred. I've only found a bunch of commercial ports or "free" demos without quicksaving, are there any others?
Super Metroid seems to have game ending sequences laying around throughout its code (or lucky coincidences).
It has this one memory address that indicates the current state of the game: "intro", "menu", "playing" etc. It has one value for "end sequence". If you manage to set that value, the next frame the end sequence plays.
There seem to be a lot of memory corrupting glitches in SM, overwriting huge portions of the RAM. Any other game would usually crash if you do that. In SM, if you manage to activate the end sequence, all is well: the end sequence is loaded from ROM, the corrupted RAM contents don't matter any more.
So there's still just one end sequence, but a pretty good chance for heavy memory corruption to successfully trigger it without crashing.
Nach wrote:
Shoot certain walls with certain beams
Some of the glitched beams just execute a giant memcpy() each frame the projectile is alive, which is part of the reason the murder beam lags so much.
Nach wrote:
I once got all the items in the game to reset just by shinesparking into a particular spot in Crateria. I wasn't even trying to do anything weird.
Do elaborate. I don't believe I've seen a way to trigger memory corruption with the shinespark before.
Obviously yes vote‚ but I found this run really less entertaining than the ACE run‚ which was really different from the other SM runs‚ showcasing some funny glitches such as the pause glitch (I dont remember the exact name).
I agree. The ACE route is unique from norfair to the end; this run is stuff you've seen before, followed by a few seconds of WTF-glitch and an outro. Although the glitch is awesome and groundbreaking (kudos to total!), the ratio of entertaining to boring is reaching zeldaesque levels.
Unfortunately I have to agree for now that it has to obsolete the ACE run, since the ACE run doesn't do anything besides finishing the game. Though if anyone were to use the ACE glitch to do something more interesting, I'd be all for reinstating the ACE category.
If you want to TAS your own game, it's been well established that you need to write it for the 65c816, glitch the game into the SMW cartridge, then TAS that.
no.
Android 2.3.6 on a samsung galaxy pocket, default browser:
First Party Session: Success
First Paty Long Term: Success
First HTTP Auth: Failure
the other three didn't even appear.
Nach wrote:
Tub wrote:
No, I haven't found a way to do reliable authentication inside a third-party iframe yet.
You only need one method to work to achieve authentication. If the system supports multiple and can switch between them, it should work.
Can you elaborate what you're trying to do? There's a different set of requirements for, say, user tracking vs. user authentication, for whether you control the first party site or not, and how frequent page reloads are in the first and third party pages.
The difficult part is obviously to get the client to remember his credentials across page reloads when neither cookies nor local storage work, but depending on the circumstances there are indeed some workarounds. I don't see your scripts testing for page reloads though; especially the HTTP auth example seems contrived: when you're sending ajax requests and you already know the credentials, you may as well pass them as GET or POST parameters instead.
If you find a way to reliably allow a third-party site to track their users across sessions in ALL circumstances, even when 3rd party cookies are disabled, that would be considered a bug by the browser vendors.
Not to badmouth him or anything, but wasn't Radix one of the most vocal opponents and bashers of TASing back in the day? I seem to remember something like that.
He never liked them, but I cannot remember him being openly hostile about them as a concept. Unless of course someone dared submit them to sda.
In fact, he was the first from SDA staff to be constructive enough to post the TAS explanation page to educate speedrunners about the issues surrounding them.
You may be confusing him with nate, from metroid2002.com. He helped out on sda, mostly with capturing and encoding from VHS tapes (since he had the equipment), and was very hostile towards TASing. He wouldn't explain the concept of TASing without using the word "cheating", he openly talked about wanting to "destroy" TASing, and his own forum had some not-so-nice word replacements for the word TAS. I don't know where he stands today.
Browser: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Firefox/24.0. Setting "Accept third party cookies" set to "never", for privacy reasons.
Third Party Session and Third Party Long Term: Failure
Note that many browsers are trying to restrict third party cookies by default, using "smart" solutions like accepting third party cookies only from sites you've visited before. IIRC Safari already does that and firefox is working on it.
No, I haven't found a way to do reliable authentication inside a third-party iframe yet.
