Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Thanks!
It actually turns out the author made an entire paper titled "Platonic solids in Z3" which completely solves this problem, and more. (as if I could possibly be the only person on earth to come up with this problem...)
I never went as far as to try to characterize every single cube/tetrahedron/octahedron that was possible, but I'll just give the examples I had in mind:
1) Geometrically, a tetrahedron is "half" a cube, in the sense that it can be embedded inside a cube with its four corners touching four of the cube's corners:
(from math.stackexchange)
So if a unit cube has corners 000, 001, 010, 011, 100, 101, 110, 111, the tetrahedron has corners 000, 011, 101, 110. It can be checked that these four points are all equidistant from each other, with a distance of sqrt(2).
2) The integer points that are distance of 1 away from the origin (think of the sulfur hexafluoride molecule) form an octahedron:
(from math.brown.edu)
3) Finally the dodecahedron and icosahedron are not possible, because each one contains 5 points that form a regular pentagon, as shown by the red dots in the following image:
(edited from various wikipedia images)
And as p4wn3r mentioned already, a regular pentagon cannot be embedded in Z3. Thus, these two solids are not possible.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
From what I could see online, there are some algorithms to enumerate solutions for some cases. I would have to check if some can be simplified to provide a solution that always works.
I'm interested in knowing what kind of algorithms you are referring to. I constructed my examples by finding an appropriate set of integer points, taking advantage of the fact that these solids are highly symmetric.
p4wn3r wrote:
Here's a partial result I could already obtain: this is impossible for the dodecahedron. Why? Because it's impossible to construct a regular pentagon using a 3d lattice.
Yes, actually the only regular n-gons that are embeddable in the cubic lattice are the 3-gon (equilateral triangle), 4-gon (square) and 6-gon (regular hexagon). The others (5-gon, 7-gon, 8-gon, and so on) are not possible because, similar to what you said, the cosine of the interior angle will be an irrational number.
Actually, I found out just recently that regular 5-gon, 7-gon, 8-gon, ... cannot be embedded in any lattice, regardless of the arrangement of points or the number of dimensions. This is because of an ingenious proof by descent that contradicts the existence of such a regular n-gon (if such n-gon can be embedded in the lattice, arbitrarily smaller ones can be generated from this in the lattice, contradicting the lattice property of a minimum distance between every pair of points). This proof only fails for the 3-gon (you get a larger triangle), 4-gon (you get the same square), and 6-gon (all generated points are the same making the hexagon degenerate).
Curiously, equilateral triangles (and regular hexagons) can be embedded in the integer lattice Zn for n>=3 dimesions, but not when n=2.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I was thinking about the five Platonic solids ...
... and whether it is possible to represent them in 3D space, using only integer coordinates for the vertices. The solid can be any size and rotated in any way, but all the vertices must have coordinates which are all integers.
The cube can be done just by taking combinations of 0 and 1 for the coordinates, like in the image below (taken from a Brown University course website):
But for the others, the problem doesn't seem so obvious.
1) Can you find a way to do it for the tetrahedron (solid in the top-left)?
2) Can you find a way to do it for the octahedron (solid in the center)?
3) What about the dodecahedron (bottom-left) and the icosahedron (bottom-right)?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Comparison video:
Link to video
Not too much editing here. Just this submission (NEW), and the published run from 12 years ago (OLD), side by side. Audio is from this submission.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I didn't know there was an 8-bit Mega Man game with rooms that have both horizontal and vertical scrolling at the same time!
It looks like to me there could be places to optimize movement. Like, jumping up to the next ledge can be done faster. I can't easily show it, but the currently published run has this movement.
Some bosses appear to be done faster in the published run as well, especially Wave Man (using charged Buster much more).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
In V2.0 (2018 Japanese/English version) there is a frame delay whenever you stop rising from a jump unless you bonk the ceiling. V1.0 and V1.1 does not have this (there is no delay). I had assumed it was a stylistic decision to make it different for V2.0, but apparently this was reversed in V2.1 to the old behavior? I only suspected it when I saw that you were making short jumps in the hallway before the boss.
I had no idea V2.1 was this different. Can Fortranm or anybody else tell me whether there are any other huge changes in V2.1 (physics, bosses, etc.) that I have no idea of?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
p4wn3r wrote:
In any case, what is the curve?
I'll answer the question first. The curve is the same as a composite Bezier curve made up of quadratic Bezier curves joined together. If this answer alone doesn't satisfy you, I can go ahead and explain:
Chaikin's algorithm, as described above, is shown in the following diagram (I derived these images from a PDF on Chaikin's Algorithm.):
The red circles are the control points. I have also displayed the midpoints (not necessarily accurately) between the control points as blue squares. n=0 is the starting configuration.
To go from n=0 to n=1, create new control points by taking the midpoint between the red circles and the blue squares. Delete the old control points (shown with hollow red circles). Finally, mark new midpoints between the new red circles. Notice: the previous blue squares will always remain as midpoints of the new configuration. So if we go from n=1 to n=2 similarly, all previous blue squares will be there as well, and new blue squares will be added.
This results in key point #1: the curve that the algorithm converges to is the completion ("limit") of all the blue squares generated by the algorithm.
Now a quadratic Bezier curve is just: For three points A, B, C, the quadratic Bezier curve on {A,B,C} is the parametric curve (1-t)2A+2(1-t)tB+t2C for t in [0,1]. Since translation of {A,B,C} just translates the corrsponding Bezier curve, let's assume A is the origin O, so the curve is just 2(1-t)tB+t2C. See the diagram below:
Here I've constructed B' (midpoint of OB), D' (midpoint of BC) and C' (midpoint of B'D'). By definition, C' is the point on the Bezier curve corresponding to t=0.5. Also notice that this construction parallels the construction in Chaikin's algorithm: If O and C are blue squares and B the red circle between them, we create new red circles B' and D', and a new blue square C'.
Key point #2: Each new blue square in Chaikin's algorithm can be generated by taking the point on the Bezier curve on each possible set of consecutive symbols {blue square, red circle, blue square} where t=0.5.
Finally, note that Chaikin's algorithm is recursive. So we just need to show that the Bezier curves are themselves "recursive"; that is, the Bezier curve on {O,B,C} can be split into two smaller Bezier curves, one on {O,B',C'} and one on {C',D',C}.
First, note that B' = B/2 and C' = B/2+C/4 . So the Bezier curve on {O,B',C'} is given by 2(1-s)sB'+s2C' = sB-s2B+s2B/2+s2C/4 = sB-s2B/2+s2C/4 . If we now take the Bezier curve on {O,B,C} and restrict it to t in [0,0.5] and let s=2t (so it goes from 0 to 1), we get 2(1-t)tB+t2C = 2tB-2t2B+t2C = sB-s2B/2+s2C/4 , the same as above.
So the Bezier curve on {O,B',C'} is just the Bezier curve on {O,B,C} restricted to [0,0.5]. By symmetry, the Bezier curve on {C,D',C'} is just the Bezier curve on {C,B,O} restricted to [0,0.5]; switching them around gives the Bezier curve on {C',D',C} is the same as the Bezier curve on {O,B,C} restricted to [0.5,1].
This gives key point #3: Bezier curves are "recursive" in the manner shown above; a starting Bezier curve can be recursively divided into smaller Bezier curves where the control points correspond to Chaikin's algorithm as above.
Thus, the key points all together say that, for a starting configuration, Chaikin's algorithm gives a composite Bezier curve composed of quadratic Bezier curves where the control points for each quadratic Bezier curve consist of two consecutive midpoints of the Chaikin's algorithm control points, and the Chaikin's algorithm control point between them.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
It's a curiosity that this bonus level isn't in the V2.0 version ( Battle Kid - Fortress of Peril (2018 ver 2.000)(J)[!] ). It isn't really that long anyway but I have no clue why it was removed. Maybe it was too short?
V2.0 also has some new bonus levels - are you doing any of them?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I did it similarly, except the ODE is obviously separable:
dy/dx = 2y/x
1/y dy = 2/x dx
ln(y) = 2ln(x)+C
y = e^(2ln(x)+C) = e^(2ln(x))*e^c = Ax^2
So the curve is quadratic.
Of course, if the factor k is something other than 2, we get y = Ax^k, a power function.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
It's not very often there is both a retro PC game and a port of that same retro game to the retro system it appears most similar to. This might be one of the first few times ever, actually.
I watched this TAS, and it actually reminded me of Battle Kid a lot. Fortunately this game doesn't appear to kill you as fast. Actually, Battle Kid is actually mentioned in the credits as an inspiration, which is a nice touch.
And yes, I like the fact that you chose to make glitchless the first submission of this game to TASVideos, even though anyone could have done glitched. I agree that it is the right choice.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Here's a problem I was thinking of regarding an image that was posted on the solution to a previous Riddler Express.
The Riddler Express question was basically as follows. Performing a workload evenly over one year (365 days) can be thought of as: Each day, take the amount of workload that is left and divide it by the number of days remaining, and do that amount of work. However, you wish to finish sooner, so instead you do this: Each day, take the amount of workload that is left and divide it by the number of days remaining, and do twice that amount of work. With this new scheme, how long would it take to finish?
Like some Riddler Expresses before, this is clearly a quickie question not meant for any deeper analysis (the answer by the way is 364 days). However, that's not the problem I'm asking here. My problem concerns the following image on the solution page, which actually analyzes the two schemes in detail and graphs them out ("Riddler Workload" is the new scheme):
As expected, the normal scheme is linear since you're working evenly. However, the new scheme is an interesting curve.
Is there any particular insight as to what this curve is, and why? (Let's assume the rate at which you do the workload is continuous as a function of time, rather than something to be updated every day.)
Edit: Changed the wording a bit.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Didn't realize the game was this glitched, although I can't say I understood much of how these glitches work.
And for a moment I thought you were aiming for 100% rooms as part of "100%", because I couldn't understand why you were zipping through so many rooms when you only had to collect 20 trinkets.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Hm... I don't remember Another World / Out of this World having funky background music. Reminds me of certain DOS games on different sound cards.
Also, I remember this game being glitched enough to have some skips, although I can never remember exactly how the skips work or why. IIRC, a lot of the game is scripted.
Is the difference of frames / lag between E and U ROMs solely because of implementation of PAL vs NTSC difference? After all, PAL is 50fps and NTSC is 60fps (approximately, if not exact).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Almost forgot to comment.
IgorOliveira666 wrote:
I think the most interesting thing about this TAS is the fact that it completely broke the hack. 95% of the levels were not completed as the author would like them to be.
In general, I am against breaking hacks in this way. If a hack is completely broken by a TAS, why should I care about the hack in the first place?
Besides, there aren't any glitches that aren't already in the glitchfest TAS, so nothing new there either.
Oops. Looks like someone exposed where I got this problem from. I'm going to have to hide it better in the future.
As OmnipotentEntity wrote, the expected number of moves from N to 1 is indeed the (N-1)th harmonic number. It can also be explained as follows:
(E(N) is the expected number of moves to go from N to 1.)
For N=2, the sequence is always a single move 2→1, so E(2)=1.
For N>2, either the next move is N→N-1, or it is not. If the next move is N→N-1, then the expected number of moves is 1+E(N-1). If the next move is N→K where K<N-1 (that is, we exclude the possibility of N→N-1), it's the same as starting with N-1 and considering the move as N-1→K, so the expected number of moves is E(N-1).
So the expected number of moves all together is:
E(N) = 1/(N-1) * (1+E(N-1)) + N/(N-1) * E(N-1) = E(N-1) + 1/(N-1).
So it's just the previous value plus 1/(N-1). Together with E(2)=1, this gives E(N) = 1+(1/2)+(1/3)+...+(1/(N-1)), that is, the (N-1)th harmonic number.
Dacicus wrote:
Let M(x) be the number of sequences leading from x down to 1 via the method described in the problem, where x > 1. When the starting number is N, there are N-1 possibilities for the next number in the sequence. Call this next number k. If k = 1, then we're done. For each 1 < k < N, there are M(k) sequences leading from k down to 1 that we need to include in M(N). Thus M(N) = M(N - 1) + M(N - 2) + ... + M(2) + 1. That last 1 is for the N→1 case. However, M(N - 2) + ... + M(2) + 1 is just M(N - 1), so M(N) = 2 M(N - 1). Obviously, M(2) = 1, which leads to M(N) = 2N - 2.
Curiously (even though that doesn't quite lead to the answer), counting the number of possible sequences from N down to 1 is equivalent to finding the number of compositions of N-1, which is 2N - 2.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I remember playing around with this game briefly a very long time ago (can't remember when) and noticing how strange it was that jumping made you so much faster.
Anyway, looks good, the TAS is as I would have expected. Though I recall the game was supposed to be titled "Beethoven's 2nd", but apparently the box covers in some regions have the name you put in your submission?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Here's a problem I've been thinking about:
----
You start with a positive number N>1 and want to get down to 1 in a number of moves. Each move consists of going from the current number to a smaller positive number random based on uniform randomness. That is, from k, randomly go to a number 1, 2, ... , k-1 , each with equal probability. Keep doing this until you reach the number 1.
For example, starting from 8, a sample three-move sequence is 8→5→2→1: Starting with 8, go from 8→5 (5 is chosen with probability 1/7), then from 5→2 (2 is chosen with probability 1/4), then from 2→1 (1 is chosen with probability 1).
Starting from N, what is the expected number of moves to reach the number 1?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Personally, I'm not into kaizo hacks. If a hack doesn't look like I will even remotely have fun trying to play it, I typically won't enjoy watching it either.
MESHUGGAH wrote:
To be sure, I've just googled NES SMB3 Super Orb Bros and it seems the SMB3 legends call this one of the greatest ROM hack to exist.
I'd like to see sources backing up the statement.
In particular, I'm wondering who these "SMB3 legends" are.
(from math.stackexchange)
So if a unit cube has corners 000, 001, 010, 011, 100, 101, 110, 111, the tetrahedron has corners 000, 011, 101, 110. It can be checked that these four points are all equidistant from each other, with a distance of sqrt(2).
2) The integer points that are distance of 1 away from the origin (think of the sulfur hexafluoride molecule) form an octahedron:
(from math.brown.edu)
3) Finally the dodecahedron and icosahedron are not possible, because each one contains 5 points that form a regular pentagon, as shown by the red dots in the following image:
(edited from various wikipedia images)
And as p4wn3r mentioned already, a regular pentagon cannot be embedded in Z3. Thus, these two solids are not possible.
... and whether it is possible to represent them in 3D space, using only integer coordinates for the vertices. The solid can be any size and rotated in any way, but all the vertices must have coordinates which are all integers.
The cube can be done just by taking combinations of 0 and 1 for the coordinates, like in the image below (taken from a Brown University course website):
But for the others, the problem doesn't seem so obvious.
1) Can you find a way to do it for the tetrahedron (solid in the top-left)?
2) Can you find a way to do it for the octahedron (solid in the center)?
3) What about the dodecahedron (bottom-left) and the icosahedron (bottom-right)?
The red circles are the control points. I have also displayed the midpoints (not necessarily accurately) between the control points as blue squares. n=0 is the starting configuration.
To go from n=0 to n=1, create new control points by taking the midpoint between the red circles and the blue squares. Delete the old control points (shown with hollow red circles). Finally, mark new midpoints between the new red circles. Notice: the previous blue squares will always remain as midpoints of the new configuration. So if we go from n=1 to n=2 similarly, all previous blue squares will be there as well, and new blue squares will be added.
This results in key point #1: the curve that the algorithm converges to is the completion ("limit") of all the blue squares generated by the algorithm.
Now a quadratic Bezier curve is just: For three points A, B, C, the quadratic Bezier curve on {A,B,C} is the parametric curve (1-t)2A+2(1-t)tB+t2C for t in [0,1]. Since translation of {A,B,C} just translates the corrsponding Bezier curve, let's assume A is the origin O, so the curve is just 2(1-t)tB+t2C. See the diagram below:
Here I've constructed B' (midpoint of OB), D' (midpoint of BC) and C' (midpoint of B'D'). By definition, C' is the point on the Bezier curve corresponding to t=0.5. Also notice that this construction parallels the construction in Chaikin's algorithm: If O and C are blue squares and B the red circle between them, we create new red circles B' and D', and a new blue square C'.
Key point #2: Each new blue square in Chaikin's algorithm can be generated by taking the point on the Bezier curve on each possible set of consecutive symbols {blue square, red circle, blue square} where t=0.5.
Finally, note that Chaikin's algorithm is recursive. So we just need to show that the Bezier curves are themselves "recursive"; that is, the Bezier curve on {O,B,C} can be split into two smaller Bezier curves, one on {O,B',C'} and one on {C',D',C}.
First, note that B' = B/2 and C' = B/2+C/4 . So the Bezier curve on {O,B',C'} is given by 2(1-s)sB'+s2C' = sB-s2B+s2B/2+s2C/4 = sB-s2B/2+s2C/4 . If we now take the Bezier curve on {O,B,C} and restrict it to t in [0,0.5] and let s=2t (so it goes from 0 to 1), we get 2(1-t)tB+t2C = 2tB-2t2B+t2C = sB-s2B/2+s2C/4 , the same as above.
So the Bezier curve on {O,B',C'} is just the Bezier curve on {O,B,C} restricted to [0,0.5]. By symmetry, the Bezier curve on {C,D',C'} is just the Bezier curve on {C,B,O} restricted to [0,0.5]; switching them around gives the Bezier curve on {C',D',C} is the same as the Bezier curve on {O,B,C} restricted to [0.5,1].
This gives key point #3: Bezier curves are "recursive" in the manner shown above; a starting Bezier curve can be recursively divided into smaller Bezier curves where the control points correspond to Chaikin's algorithm as above.
Thus, the key points all together say that, for a starting configuration, Chaikin's algorithm gives a composite Bezier curve composed of quadratic Bezier curves where the control points for each quadratic Bezier curve consist of two consecutive midpoints of the Chaikin's algorithm control points, and the Chaikin's algorithm control point between them.
As expected, the normal scheme is linear since you're working evenly. However, the new scheme is an interesting curve.
Is there any particular insight as to what this curve is, and why? (Let's assume the rate at which you do the workload is continuous as a function of time, rather than something to be updated every day.)
Edit: Changed the wording a bit.