I think a more optimal way to do piston extenders for n blocks is to use modular arithmetic. ([x mod y] is the remainder when x is divided by y, e.g. 35 mod 10 = 5) [these brackets aren't required, i just use them for clarity] basically, you push the first [n mod 12] blocks ([n mod 12] -> 1), then [12 + n mod 12], and repeat until you get to n. this is actually a generalization of @abugidaiguess's method for 13 pistons. If n mod 12 = 0 (i.e. n is divisible by 12), then it saves no extra steps. But otherwise, it saves exactly [n - (ceil(n / 12)) * (n mod 12)] over what is shown in the video! some examples: 13 pistons (video): 12 -> 1, 13 -> 1; 12 + 13 = 25 steps 13 pistons (modular): 1, 13 -> 1; 1 + 13 = 14 steps steps saved: 25 - 14 = 11 30 pistons (video): 12 -> 1, 24 -> 1, 30 -> 1; 12 + 24 + 30 = 66 steps 30 pistons (modular): 6 -> 1, 18 -> 1, 30 -> 1; 6 + 18 + 30 = 54 steps steps saved: 66 - 54 = 12 500 pistons (video): 12 -> 1, 24 -> 1, ..., 492 -> 1 (that's 12 * 41, btw), 500 -> 1; 12 * (1 + 2 + ... + 41) + 500 = 10832 steps 500 pistons (modular): 8 -> 1, 20 -> 1, 32 -> 1, ..., 488 -> 1, 500 -> 1; 8 * 42 + 12 * (1 + 2 + ... + 41) = 10668 steps saved: 10832 - 10668 = 164 (that's a lot!) btw I used a computer program to generate the number of steps for that last one, so it may not be 100% accurate!
nice, that makes sense! for all cases other than multiples of 12, this way of doing it produces a shorter sequence. funnily enough, this is actually what gets implemented in the redstone version! In game, I always forced the subsequences to line up with the back, because that way I can change the number of pistons without having to shift the redstone. notice how at 19:09 it starts with 4 -> 1 because its a 40 piston extender mind if I pin this comment? would be nice to share this info with everyone! and it could serve as a thread for more discussion about this in the replies
@@mattbatwings yeah that would be awesome! i'm totally fine with being pinned :) interesting that the redstone ends up producing the shorter sequence anyway. and i'm not much of a redstone guy, so those builds you make always blow my mind, even after all the explanations! also i just joined the discord server and it looks great ^^
@mattbatwings yeeeaaahh I fel smerter that Matt it took me like 1 sec to figure out this anyway I hope this little mistake didn't make this video feel less professional, since you could have made a program that tested all possibilities, knowing that there is a finite and small number of them for a 13-long extender. This way you could have seen that this method was more optimal. no worries though, you can't be the best at redstone computing and door making.
For the record, short (1TP/0TP) pulses will also retract blocks, *if* the block was in the extended position when the pulse was produced - so can also be time-optimised in that way
For a 13 piston extender 1 , 13 -> 1 is more optimal than 12->1, 13->1. Further for a n-piston extender rather than iterating 12->1, 24->1 … n->1 you can simply do (n mod 12) -> 1, (n mod 12) + 12 -> 1, (n mod 12) + 24 -> 1 … n -> 1
@@profx33this method optimizes the number of piston extensions, however it can still be run in parallel so asymptotically it would take the same amount of time per extension as the method proposed in the video, simply with fewer extensions hence less time. Additionally the use of zero tick mechanics can be used to improve the time between piston firing.
13->1 does not move all the blocks. Remember there is iron (or some other block) in front and the index of a piston is equal to the number of blocks in front of it. Pistons can only push 12 blocks, so piston 13 can’t activate since it has 13 blocks in front of it.
This is the second video I've seen on that, but the first I've actually watched and I have no idea what it is. (the other being mate in Omega, the chess one)
@@burningnetherite4206 Summit of Math Education is competiton to foster the creation math content online. Anyone could join competition until 19th August. Now you can't join as a participant but you can still join as a judge
The way you parallelized this is actually really similar to how CPUs are optimized. Cpus have several stages they have to do, and they used to have to every stage before the clock cycle. But modern cpus will only do one stage per clock cycle, but will run them all in parallel by starting a new instruction on each clock cycle.
I feel like this is exactly the type of video that 3b1b loves to see with this SoME. I love how gaming communities can go together like this with the math community.
In the case of minecraft, all the people that are serious about redstone builds (talking about "technical" minecraft players) are on the smarter side of the gaming community and are not afraid of crunshing numbers and investing more time doing math about the game than actually playing it. I always like it, when I catch myself calculating growth of supplies, output of farms, speed of a vehicle, damage over time, and so on, in the middle of a gaming session 😅
Looked at the profile of the video creator just now, and in fact, it is not a math guy doing minecraft, but a minecraft guy doing math 😂 Technical player right there.
haha, the minecraft community (specifically the redstone community) is intertwined with the maths community. There's just too much overlap for it not to be the case.
I've gotta give you props for this. This is gotta be one of the most clear explanations I've seen. No crazy music; and straight to the point, and showing the steps behind each thought and conclusion. Subbed.
for a 13 piston extender, you can just do 1, 13 → 1 saves 11 extensions, and should be fairly simple to generalise up until 24 at least edit: as a few replies have pointed out, it actually doesn't really matter which piston is extended first. i just happened to choose 1 in my head edit 2: wow okay so it turns out the method i thought of has since been generalised by the pinned commenter (who actually called it "@abugidaiguess's method"!) i honestly didn't put much thought into the comment beyond the specific case for a 13 piston extender, so i'm really glad other people did! :D
There is a way to think about piston extenders which I would like to share! 1. Think about the blocks being moved to be air block, instead of pistons. 2. When an air block is in a certain location, movement on the two sides doesn't interfere with each other. 3. We can look at only a single air at a time, we can simply assume the movement in the back to happen first, until the air space is filled. 4. When extending, there are N air blocks to be moved. The first air block moves N meter, and the N'th air block moves 1 meter. 5. Moving air K meter to the back takes at least K/12 piston movements, rounded up, which is written as ⌈k/12⌉. This is because air moves a maximum distance of 12 blocks per piston movement. 6. Since this is always possible, the minimal amount of piston movements for an extension of N meter is the sum of ⌈k/12⌉, from k=1 to k=N. 7. This logic works the same for retraction; the minimal amount of movements is the sum of ⌈k/1⌉=k, from k=1 to k=N, which is actually just equal to ½N(N+1), or the N'th triangular number. Personally, I think my proof is very elegant, hope this helps!
This is the most elegant proof I've seen so far - thank you for sharing! I saw your note about winning IMO - that's absolutely incredible, congratulations!
@@mattbatwings Thank you, but I didn't 'win' the International Mathematical Olympiad; multiple people win gold medals every year. In all of the Olympiads, half of the competitors wins a medal, and the ratio between gold, silver and brons is 1 : 2 : 3. 100 countries send their six best competitors to the IMO, so a little less than 50 people win a gold medal. I was 19th.
A detailed analysis of the optimal extension sequence: Consider the total cost of an n-extension. We can consider the total cost to move all required blocks 1 block forward, 2 blocks forward, 3 blocks forward etc. separately, because each extension pushes a subset of the pistons/block which have all currently been moved forward the same amount of times (i.e. it is impossible to simultaneously push two pistons that have moved a different number of times each, because there will be an air gap in between). The first set of blocks (that needs to be moved forward once) has size n, then the next set (that moves forward twice) n - 1, then n - 2 and so on until there is only 1 block that must be moved n times. The kth of these has size (n - k + 1) and requires ceil[(n - k + 1) / 12] extensions as each extension can only push at most 12 blocks. So the total cost is the sum from k=1 to n of ceil[(n - k + 1) / 12]. Notice, however, that this is equivalent to ceil[(n - 1 + 1) / 12] + cost(n - 1), that is, ceil(n / 12) + cost(n - 1), with cost(0) = 0. This can therefore be expressed as cost(n) = ceil(n/12) * (6 + n - 6*ceil(n/12)). Also note that this lower bound is achievable because we can simply do the process one step at a time, moving forward the first n-1 pistons in ceil(n/12) steps, then the next n-2 in ceil((n-1)/12), etc. The most interesting piston extender math (in my opinion) is that of "hipster" extenders, which are piston extenders that extend beyond the wiring itself. This means in order to power pistons beyond the wiring, movable power sources such as redstone blocks or observers must be extended and retracted themselves. This makes the analysis of the optimal sequence slightly more tricky. Every distance extended/retracted beyond the wiring requires recursively using the distances 1, 2 or 3 blocks before it one or more times (in order to extend and retract the power source, and move the piston back 1 block), leading to exponential growth in the length of the sequence.
Yes, what we care about most is the length of the sequence (not the actual sequence itself), so I defined the function cost(n) to be the length of an optimal n-extension.
Solution "may" not be optimal. It "may" be the case that somewhere in an optimal solution, a piston extension is used in both the moving of the 7th block and also the 10th which could make a better solution than the one you propose. I put "may" because I think you're right, but you didn't prove this "may" had to be wrong.
@@viktort9490No, this solution is rigorous. In fact, what you say is true (a piston extension IS used in the moving of both the 7th and 10th blocks) - the point is that it can be used to move BOTH those blocks if and only if they have moved the same amount of times so far, or there would be an air gap between and only the 10th block would be moved. This then leads to the independence of each distance moved and the rest of the proof.
after finding that dispensers are a dynamical system I'm not surprised you've found some math surrounding piston extenders that warrants a whole math explanation vid, excited to see what you've put together and best of luck with your submission
(This comment was made before the premiere) My guess for the video is gonna be deriving an algorithm for finding the order in which pistons need to be fired to close/open an nth long piston extender That and/or deriving the correct timings to do such
@@austinclees9252extender designs are simpler than that, my prediction is that it's gonna be about the observer + 2tick-repeater design which is infinitely expandable and uses just a clock and a timer to get all the pulses, it's a really smart design because although the inputs are kinda intuitive, the piston sequence isn't but in the end it all somehow manages to work
EXTENSION PARALLELIZATION is exactly what GPU's do comparatively to CPU's ... and there are engineers called CUDA programmers their job is to find a way to parallelize chunks of repetitive codes in order to take advantage of the shear amount of cuda cores that can parallelize process data
So I had an idea at around 8:12, and that's that the 13 block extension could be done more simply than 12->1, 13->1. I believe that the sequence 12, 13, 12->1 would also work but with less repetition. Therefore, this disproves that the formula for sequences of individual extensions does not necessarily always give an optimal result. Edit: Well it's not something unique I've came up with, but it is still true so I'll take that. Great video as always
the formula does allow for an infinitely expandable and modular design to an extender though. using the most optimal number of pushes would require different extenders to have their own different redstone circuits.
@@Drawliphantyou don't need to push an expanded piston. You do a quick pulse with one of the first 12 pistons. It will push everything forward and not have time to pull it back. Then the gap created means 13 can now fire to fill that gap and then you can just go down the line.
I'm not a redstone nerd, but I am a math nerd and I love doing random stuff in Minecraft. I liked this video a lot, such a creative entry to the contest!
3Blue1Brown--Grant Sanderson is one of my most watched channels on youtube. You are an absolute legend for sharing with the world the wonders of Maths and Minecraft, Mattbatwings. Thank you for all that you do; this is incredible!
I see that some people want piston 1 to push the block right in front of it, and then do [13,1], but I feel like starting as close to the next chunk as possible would be a bit more optimal, as in, for 13 pistons, piston 12 pushes, then you do [13,1]. For 25 pistons, you'd do 12, then 24, then [25,1], so you always end up only doing the n->1 pushes when you can push for the entire chain, instead of having any sub-chain pushes that aren't a single push that moves 12 pistons 1 step forward to free up pistons further back in the chain. To further extrapolate: Make every multiple of 12, starting from 12*1 and working up towards 12*m < n, push the 12 blocks in front of it, and when you reach 12*(m+1) >= n, just do the n->1 push chain.
@@anon1963First of all, higher level math is beautiful and not boring in its own right. Second, there are millions of applications of many, if not most, areas of math
Very nice! Also some clarifications: • pistons don't need a long pulse to retract, they can retract with a normal single pulse. Technically you can get away with zero tick stuff to push multiple pistons in sequence at the same time but that gets very glitchy with update order shenanigans and you really don't wanna mess with that. • as others have pointed out, the reason you can't prove that the repeated steps are optimal is cause they aren't: the modular method is! • the act of sticky Pistons leaving behind a block when powered for a single tick is called "block spitting" and it was originally a bug, much like some other redstone features (quasi-connectivity comes to mind) • we technically have infinite piston extenders and retractors, though it's a bit cheaty to call then "extenders" since those are their own category of redstone tech: if you place a piston to push something that drags a sticky piston (facing backwards) with itself - such as a slime block - and then that triggers this piston to pull the other one along, you'd have a self-dragging contraption that moves infinitely until it encounters an obstacle. You can make the movement itself trigger pistons by using observer blocks. TA-DA! You have made a *redstone flying machine*! And fun fact, observers triggering when they move is ALSO a bug that became a feature! Aaaaah Minecraft...
The proof for the Retracrion only needs a small addition to be valid for any number of blocks: -6 is proven to be ideal for a 3 piston retraction -any extra piston adds n (new number of pistons) block movements, because every block in the old chain (n-1 pistons + 1 block upfront) needs to move back one more block each -any extra piston adds n ( new number of pistons) retractions in this algorythm, becase n->1 is added at the end of it => the required block movements and the number of retractions start at the same number and rise by an equal amount for each itteration of n, therefore both numbers are equal for any given n Q.E.D.
I see a lot of people with the optimal solution for piston extension but not a formal proof, so I figure I might give one. Apologies if someone else already did so. I'm going to generalize the problem slightly to be "each piston can move at most 'm' blocks". Just take m=12 for the specific solution. To describe an optimal optimal solution, define q, r as non-negative integer s.t. n=q * m + r, r < m (quotient and remainder) TLDR, an optimal solution is to move block m, 2m, 3m until qm, then if r != 0 move the nth block. After this process the leftmost piston should be followed by a gap followed by the other n-1 pistons next to each other. Then repeat this solution recursively on the n-1 pistons. You can prove this is optimal using induction and by showing that any other opt sequence is at least as good as this one by reordering steps in the sequence. --- Lemma 1: Lower bound for optimal sequence is (n - 1). Pf: Define a component to be a collections of pistons next to each other that are not interrupted by gaps. The problem starts of with 1 components (of size n), and ends up with n components (each of size 1, each individual piston is it's own component). When a piston is pushed in the rightmost component the number of components increases by 1, otherwise it stays the same since the block of pistons being split off joins the component directly after it. So at least (n-1) steps are needed to get to the final state. ---- In your video you showed examples of (n-1) length sequences for n S_j and there must be a gap after the S_i+y piston, so swapping them in our sequence doesn't change the blocks they push out, and after applying both steps swapped we end up in the same configuration as before. With the above, we can keep moving primitive steps before non-primitive ones and end up with a new sequences Q_1, ... Q_K where all the the primitive steps of the original sequence are done before the non-primitive ones (in the same order; aside another way to put this is that the subsequences are independent to the action of piston pushing - there's some group theory way to formalize this if you want). The primitive steps at the beginning must be strictly increasing, since each step decreases the size of the leftmost component, and it must end with a step where the left-most piston is extended, since we need to end up with a leftmost component of size 1 by the end. Now notice that there's always two components here, except for the initial state which has one component. This is because we're only acting on the leftmost component, we can only increase the number of components if we act on the rightmost component, and the only time the left and rightmost components are the same is at the start. The most that any operation can push out is 'm' pistons, and pushing out in our case means transferring from the left component to the right component. By the end of process you will up with a left component of size one and a right component of size n (we started with n+1 pistons). This means that we need at least ceiling(n+1/m) primitive steps. The sequence from the TLDR does this, but if there's a remainder then there's a lot of other solutions too since you could move the remainder first (like some other solution here do, or mix and match etc.). Once you do this you have the leftmost piston by itself and the remaining piston is a single component of length n, so we just use our inductive hypothesis and repeat the same procedure to the remaining parts. --- So yeah, there you have it. Hopefully I didn't make any mistakes there.
9:05 You can find a quadratic lower bound on the number of elements in your extension sequence as follows. Your initial state with n pistons can be represented by a sequence P^(n+1) H^n where P denotes a piston (or the block to push) and H a "hole", i.e., air. Your final state is (P H)^n P Note that both states have the same length. All your moves, i.e., individual piston extensions, will just swap P's and H's around in the state. So this means that the n holes must be moved somehow such that they appear in the even (2nd, 4th and so on) positions, by means of piston extensions. Observe that every move must take a clump P^l H with l
The true infinite piston extender: A flying machine Edit: How did this get 600 likes? wow. If anything i thought i'd get criticised for dodging the video's topic
On extension optimality: Your sequence is sub-optimal in *two* ways: [edit: never mind, you mentioned the second improvement at 9:14.] As others have pointed out, in your 13 piston example, you can extend only piston 1 and then do the 13->1 sequence. And for a 14-piston extender, you _COULD_ do 2->1 first and then 14->1. But you can now do some operations *simultaneously*: You do 2 first, then 1 and 14 at the same time, then 13->1. For 25, you do 1 in the first "tick", then the second "tick" start the 13->1 sequence, then the third "tick" start the 25->1 sequence. And so on. I think that's the optimum. It adds only a single "tick" for every group of 12 that the pistons need to be split into.
Very nice how contraction parallelization enables you to have it work with a log of blocks in adequate amount of time. So instead of n! steps you just need 2n-1. Every for small amount like 10 blocks the difference is incredible 10! = 3628800, 2*10-1 = 19
This is actually a great way to introduce mathematical induction, that I've never thought of as a huge maths and redstone nerd! Ty again mattbattwings and best of luck !!
the way you have the parallel pisron firing reminds me of a smarter every day video called STRANGE but GENIUS Caterpillar Speed Trick with caterpillars that ride each other like a wave
Extending two pistions (and having one pushing the other) at the same time (in the same game tick) is possible. I uploaded a short video showing in which cases this is possible, because there are some limitations to that. I don't know if this can be used to speed up pistion extenders even more.
This video unironically made math interesting to me. Your visuals are really easy to follow, I only backtracked like once (I usually backtrack a lot in videos). I like how you started simple and gradually went more complex leading to formulas. I'm definitely subbing!
Something that I find very cool about this is that it kinda resembles liquid travel through a narrow tube, or low resolution fluid simulations. The spaces between the blocks look like air bubbles floating up and out as they break the surface tension of the water above them.
Something that didnt get said here but i think is mathematically interesting is that the retraction system is just the reverse of the push system when the push limit is 1 block.
A few observations : 1. Extension length formula is 6*floor((n-1)/12)*(floor((n-1)/12)+1) + n 2. For retraction, two different recursive formulas are possible, depending on whether you chose 1 or 3 for the 3 piston extender. You can choose to bridge the nth gap first and then recursively bridge the next gap, on and on, or you can do it the opposite way, bridging the 1st gap, then the 2nd, and so on. Indicating relevant subsequences with a semicolon, one sequence gives 1; 2, 1; 3, 2, 1, while the other gives 1, 2, 3; 1, 2; 1. Both are the same length. In recursive notation they both start with S(1) = 1, but the one in the video is Sequence(n) = Sequence(n-1), n - > 1, while the alternative is Sequence(n) = Sequence(n-1), 1 -> n.
Love this, math isn't exactly the _last_ thing I think of when I think of minecraft, so it's cool to see a deep dive into one of the game's most versatile mechanics!
Loved this video! Another interesting bit of minecraft math that I've been looking into is an algorithm for generating piston sequences for a piston door of any size
For the extender, it's better to think about trying to activate the backmost piston as soon as possible, similar to how it worked without a push limit. As it's only possible to move 12 blocks at a time, start with piston 12. Next, the furthest behind 12 that can successfully activate is 24, then 36, etc. Activate all the multiples of 12 until piston n can activate, then activate all the multiples of 12 until (n-1) can activate, repeat for all pistons in the extender. So the method for an n-piston extender, in pseudocode, looks like: let k = n while k > 0 let j = 12 while j < k { push j let j = j + 12 } push k let k = k - 1 } This sequence for the 40-piston extender is: 12, 24, 36, 40, 12, 24, 36, 39, 12, 24, 36, 38, 12, 24, 36, 37, 12, 24, 36, 12, 24, 35, 12, 24, 34, 12, 24, 33, 12, 24, 32, 12, 24, 31, 12, 24, 30, 12, 24, 29, 12, 24, 28, 12, 24, 27, 12, 24, 26, 12, 24, 25, 12, 24, 12, 23, 12, 22, 12, 21, 12, 20, 12, 19, 12, 18, 12, 17, 12, 16, 12, 15, 12, 14, 12, 13 -> 1 which has 88 pushes, while your method uses 112 pushes. It's unfortunately not nearly as neat to write the sequence out nor capable of parallelization, but it definite saves pushes. I believe this is optimal, though I don't know how to go about proving it. Though it seems @arcycatten already came up with a different solution that agrees on number of pushes, has a neater sequence, and is parallelizable.
i have 0 interest in redstone and hardly any interest in math but you explain this in such an interesting way that i cannot stop paying attention. its so easy to understand because of the visuals and how well you explain everything, i love this.
The extension sequence you describe is not optimal for every length piston extender. For example, with the 13 extender, you can have any one of the pistons 1-12 fire, creating a gap, then just extend from 13 to 1. However, I think this is just as fast as the sequence you named with parallelization, although requiring more piston extensions. Yours is probably easier to wire though (at least smaller) because you can just repeatedly power the same line from the back.
As someone who studies advanced level mathematics and physics at school and also plays videogames like Minecraft for fun, i always considered gaming and my studies to be completely separate from each other and not at all connected. Gaming is always little more than a fun leisure activity whilst my studies in physics and maths is more important and mandatory schoolwork. However, watching this video has opened my eyes fact that there are likely many different connections between maths (and maybe even physics) and the games that i play.
@@czechmateyoulost1755 I mean A Level maths and physics. It's the qualifications you take at age 16 and 17 in the UK where you usually pick 3 or 4 subjects of your choice that you want to study before you use your grades in your subjects after the end of 2 years of study once you've done your final exams to enrol at university
Started watching in the background while playing minecraft, just for background audio, but I have now spent the last 15 minutes just watching the video, standing still in minecraft. Nice work, very entertaining, and awesome :)
BRO YOU ARE RIGHT!!! I thought you were just trying to make fun of us with the "Just be good" thing, so i whipped out my sketch book, drew from a reference, and IT LOOKS SO FUCKING GOOD!!!!!! imma try to keep up with this.
A simple answer that is also a proof (at least with some simplification is to always push as many blocks as possible). Since in total the amount of movement done by each block can be counted and we know this movement is necessary, pushing the maximum possible at any one point will minimize the amount of instructions given. An additional argument that makes understanding this easier, that changes the approach slightly is that we can always push from the left first, since these are necessary and cannot be done by pushes further right, this then also reduces the problem to smaller instances. I.e. f(25) = (12, 24, 25)+f(24). Funnily this also reduces to a fairly simple recursive formula f(n) = (12*i | for I in (1,n) if 12*i sum_{i=1}^n ceiling(i/12) or even simpler sum_{i=1}^{ceiling(n/12)} i*min(12, n-12*(i-1)).
As I just noticed, this then also generalizes to the parallelization case, since we are maximizing the amount of parallel operations we can do at any one time, while minimizing the amount of operations given. This however, does appear almost impossible to actually implement ingame though 😕
I believe using the dividsion algorithm, n=sq+r, r from 0 to q-1, is a simpler formulation, using q=12 of course. Also, i believe the most optimal (though less simple/practical) sequence for an n piston extender is as follows: Let {12m} 1 to s indicate the sequence 12, 24, ... , 12s. Let [{12m} 1 to s, n-(a-1)]r indicate the sequence which consists of the sequence in square brackets repeated r times, where "a" is a counter (so the first time a=1, second time a=2, third a=3, and so on till a=r). The optimal sequence then, for some n=12s+r, r from 0 to q-1, is: [{12m} 1 to s, n-(a-1)]r, [[{12m} 1 to s-c, (n-r)-12(c-1)-b]12](s-1), 12->1, where "a" is a counter for r, b is a counter for 12, and c is a counter for s-1 (so for the first 12 repitions, b goes from 1 to 12 but c is 1, and for the next 12 c=2, and so on until c=s-1). In essence, this moves every multiple of 12 piston (rather than doing 12m->1) then moves the "highest" piston, which goes down by 1 each iteration. In counting steps, this video's proposed sequence {12m->1} 0 to s, n->1 has 12(1+2+...+s)+n steps. The sequence proposed in this comment has r(s+1)+12s(s+1)-12(1+2+...+s) steps, which can be simplified to n(s+1)-12(1+2+...+s) steps. In comparing, note that 12(1+2+...+s)=12((s^2)-(1+2+...+(s-1))) and see that, with the video's on the LHS and this comment's on the RHS, after simplifying we have 0?=?r-12. r-12
this is mathematically and visually elegant and beautiful. never seen piston extenders explained in such an approachable way. i sure wish this kinda thing existed before slime flying machines!
17:14 For people who are more nerdy: Let Len(n) be the length of Sequence(n). So we have Len(3) = 6 as Sequence(3) = 1,2,1,3,2,1 which is 6 items long. We now have a second recursive relationship: Len(n) = Len(n-1) + n This works because Sequence(n) is a combination of n->1, which necessarily has length n, and Sequence(n-1) which has length Len(n-1). We also have a base case of Len(1) = 1. Solving the recurrence relation we have, after rearranging: Len(n) - Len(n-1) = n Is a bit difficult to explain. The short version is that we can find a closed formula for Len(n) in terms of n. You can find explanations of how to do this online but it’d be too hard to explain in a UA-cam comment. The short version is that you get the following formula: Len(n) = n(n+1)/2 Finally, let’s consider the retraction. The block must retract n blocks, piston 1 must retract n-1 blocks, and so on. In general, piston k must retract n-k blocks so the total retraction is the sum S = n + n-1 + n-2 + … + 3 + 2 + 1 + 0. This is the famous triangular sun and has a closed formula (which you can prove). The sum S has the following closed formula: S = n(n+1)/2 Well isn’t that neat? They have the same closed formula! As we showed that the length of the sequence we generate is equal to the minimum number of retractions, it therefore follows that the sequence generated is optimal. QED.
It's not optimal: for a 13 piston extender, you have 1, 13->1. (14 steps; clearly less than 12->1, 13->1 with 25 steps). In general we have that n%12->1, 12+(n%12)->1, 24+(n%12)->1, ..., n->1 is a valid solution. e.g. for 25: 1, 13->1, 25->1 Your solution takes n + 6((n//12)^2 + n//12) steps (where // is floor division) mine takes (n%12)(n//12 + 1) + 6((n//12)^2 + n//12). n//12 = (n - n%12)/12 n%12 < 12 => (n%12)(n//12 + 1) = (n%12)((n - n%12)/12) + (n%12) < 12((n - 12)/12) + 12 = n - 12 + 12 = n Hence (n%12)(n//12 + 1) < n Hence (n%12)(n//12 + 1) + 6((n//12)^2 + n//12) < n + 6((n//12)^2 + n//12) So my solution is more efficient in general.
This is the best video I've seen in a while. Obviously math and redstone relate quite heavily, but somehow with the animations and explanation, it was very clear and concise. Thank you for your inspiration.
the 13-piston example is best to illustrate that the 12-1, 13-1 system isn't optimal: If you trigger piston 1 first, then piston 13 has 12 blocks in front of it. the sequence 1, 13-1 would thus work the same as your sequence of 12-1, 13-1 while only adding a single piston push to the original. For something like 24 pistons, firing piston 12 first will "break off" the front set of blocks, then piston 24 can push the latter section, but then it stalls again so you need to push 12 again, then you can pust piston 23 etc. so the sequence becomes an alternation: 12,24,12,23,12,22 etc. which should end up being a lot faster than 12-1, 24-1 I've not finished the video but i saw you ask so i thought i'd post. I tried to build something in creative mode really quickly to see what i can do but realised i don't know how to pulse the redstone signal yet lol.
As someone who is currently in their first year of uni learning computational thinking and someone who grew up loving Minecraft, this is such a cool video and quite inspiring actually. Thank you for this! Keep up the great work
It is just amazing work. I have very much respect to people like you, because you made whole video which have a lot of details and explains in easy way smart, little tricky and interesting thing
i just noticed that the retraction sequence can also work as a extention sequence and actually you don't rly need a long pulse to grab a block, a short pulse can retract a block too, if the sticky piston and the block don't have space beetween them a short pulse will separate them with a 1 block gap like you showed, but starting the other way around with a gap of one block beetween the piston and the block a short pulse will close that gap like a long one. using this fact you can make a full piston extender that enable retraction only using the retraction sequence which would not be the fastest but would use only 1 circuit for bothand i think observer blocks give a pretty fun way to do it.
The retraction problem is very similar to the tower of hanoi, a way it can be visualised is counting up in binary where when a digit changes from a 0 to a 1 the the piston corresponding to that retracts, i.e. 001 - first piston retracts 010 - second piston retracts 011 - first piston 100 - third piston and so on. This method can also be used for the tower of hanoi which is an old wodden puzzle
Just found your channel through this video and Holy shit your videos have been the highlight of my week! Absolutely amazing videos that give me the same feeling as watching Ben Eater videos. Keep it up!
there is actually a pattern for the retraction pattern for the piston, it's called the " Triangle read by rows: row n lists the first n positive integers in decreasing order", which is quite fascinating to find this mathematical coincidence
Optimal extension is given by f(n)= ceil(n/push lim) + f(n-1) Ceil is just rounding up after division. The idea is extend the final piston while using the remaining as little as possible. This will then produce a smaller chunk of size n-1 which we apply the same rule recursively. The final piston can be extended after ceil(n/push lim) pushes, and that value corresponds to maximal chunks (meaning always pushing the push limit) lies before it.
I actually used those principles in my designs before, in both my one wide, and my bigger designs. The only thing I changed was the following: I wanted to make my designs as compact as possible, not as fast as possible. This lead to me not being able to feed extra inputs to the pistons from the side, so in my designs, the signal starts at the back, and moves towards the front of the extender. When it reaches the first 12 pistons of the extender, it will automatically start extending, since the push limit isn't a problem anymore. Because I just input all the inputs needed, the next batch of 12 pistons will start extending immediately after. That goes on until the very end of the extender is reached, and works for every piston extender length. It completely eliminates the risk of accidentally inputting a signal at the wron block, thus being way simpler, but comes at the cost, that it might take some time until the extender starts extending. For an extender that only has 50 pistons or so, that only are a few seconds, however I made a 1000 piston extender on that principle and it takes quite some time to start extending xD. All my designs are on my channel, tho I won't post links to them here, since this comment is not meant as some sort of ad, but I want to share my experience on making a compacter, simpler design, ober a faster one.
I love this kind of video, hope you will continue to make them after SoME3. The incorporation and application of mathematics into minecraft was really well done. My one minor piece of constructive criticism is that, while I could feel that it worked, the proof that you showed for the retraction being optimal needed to be completed. Thank you so much for this great video.
Bro I swear if 20 years from now we gonna see math problems like this asking like “If we have a piston extension with 30 pistons how long is the length from the back piston to the block when activated”
Man gotta love my two interests colliding in this! Also, two notes: For the retraction, it’s pretty easy to continue the proof for perfect optimization. First, how many more blocks get pushed forward between n and n+1? It would be n, since, as it was noted near the beginning, the nth piston has n blocks in front of it, and each piston added shifts everything in front of it forward 1 block. Next, how many more retractions are added with each piston? Again, n, as the sequence just adds n->1 to the end. Thus, this sequence is optimal for all n. (Assuming n is a natural number) Secondly, it’s kinda hard to see, but it looks like the final system is not only optimal for pulses needed, but also time taken. For it to be time optimal, the end block must be moved with every set of pulses, which I’m pretty sure it does. Gotta love it! Puts Mumbo’s monstrosity of a 22 piston extender he made a few years ago to absolute shame
In CompSci terms, the piston extension formula can be described as a "greedy algorithm": Simply power the rightmost (oriented based off your video) piston with the largest (up to 12) number of blocks in front of it. Repeat until no piston has a block in front of it
CHECK OUT PART 2 for corrections and more math! :D ua-cam.com/video/6emS04mkRGs/v-deo.htmlsi=RLGIBlMooxlgN848
I am your enemy. 👿
😢
Is it mathematical induction?
I don’t think about everything in detail nut if n is 13 why not 12, 13 -> 1 it has 14 extensions while 12 ->1, 13-> 1 has much more @mattbatwings
why is matt here
I think a more optimal way to do piston extenders for n blocks is to use modular arithmetic. ([x mod y] is the remainder when x is divided by y, e.g. 35 mod 10 = 5) [these brackets aren't required, i just use them for clarity]
basically, you push the first [n mod 12] blocks ([n mod 12] -> 1), then [12 + n mod 12], and repeat until you get to n.
this is actually a generalization of @abugidaiguess's method for 13 pistons.
If n mod 12 = 0 (i.e. n is divisible by 12), then it saves no extra steps.
But otherwise, it saves exactly [n - (ceil(n / 12)) * (n mod 12)] over what is shown in the video!
some examples:
13 pistons (video): 12 -> 1, 13 -> 1; 12 + 13 = 25 steps
13 pistons (modular): 1, 13 -> 1; 1 + 13 = 14 steps
steps saved: 25 - 14 = 11
30 pistons (video): 12 -> 1, 24 -> 1, 30 -> 1; 12 + 24 + 30 = 66 steps
30 pistons (modular): 6 -> 1, 18 -> 1, 30 -> 1; 6 + 18 + 30 = 54 steps
steps saved: 66 - 54 = 12
500 pistons (video): 12 -> 1, 24 -> 1, ..., 492 -> 1 (that's 12 * 41, btw), 500 -> 1; 12 * (1 + 2 + ... + 41) + 500 = 10832 steps
500 pistons (modular): 8 -> 1, 20 -> 1, 32 -> 1, ..., 488 -> 1, 500 -> 1; 8 * 42 + 12 * (1 + 2 + ... + 41) = 10668
steps saved: 10832 - 10668 = 164 (that's a lot!)
btw I used a computer program to generate the number of steps for that last one, so it may not be 100% accurate!
nice, that makes sense! for all cases other than multiples of 12, this way of doing it produces a shorter sequence.
funnily enough, this is actually what gets implemented in the redstone version! In game, I always forced the subsequences to line up with the back, because that way I can change the number of pistons without having to shift the redstone. notice how at 19:09 it starts with 4 -> 1 because its a 40 piston extender
mind if I pin this comment? would be nice to share this info with everyone! and it could serve as a thread for more discussion about this in the replies
@@mattbatwings yeah that would be awesome! i'm totally fine with being pinned :)
interesting that the redstone ends up producing the shorter sequence anyway. and i'm not much of a redstone guy, so those builds you make always blow my mind, even after all the explanations!
also i just joined the discord server and it looks great ^^
Damn, nice funny words Mr magic man!
0_0
@mattbatwings
yeeeaaahh I fel smerter that Matt it took me like 1 sec to figure out this
anyway I hope this little mistake didn't make this video feel less professional, since you could have made a program that tested all possibilities, knowing that there is a finite and small number of them for a 13-long extender. This way you could have seen that this method was more optimal.
no worries though, you can't be the best at redstone computing and door making.
For the record, short (1TP/0TP) pulses will also retract blocks, *if* the block was in the extended position when the pulse was produced - so can also be time-optimised in that way
Which is what every single demonstration after that explanation uses. So yeah, that's some crucial information.
i was gonna say that
Thing is the system measures time in extensions/retractions, not in tick speed.
@@LineOfThy that is because as far as i know a 0/1t pulse still takes 2t to move the block
@@hunorfekete7413 Ye but it's still one extension/retraction
For a 13 piston extender 1 , 13 -> 1 is more optimal than 12->1, 13->1. Further for a n-piston extender rather than iterating 12->1, 24->1 … n->1 you can simply do (n mod 12) -> 1, (n mod 12) + 12 -> 1, (n mod 12) + 24 -> 1 … n -> 1
This saves you floor(n/12)*(12 - (n mod 12) total steps on the extension. Correct me if I’m wrong but this is provably optimal
@@rohiem7554 now prove that this is the fastest :D
@@profx33this method optimizes the number of piston extensions, however it can still be run in parallel so asymptotically it would take the same amount of time per extension as the method proposed in the video, simply with fewer extensions hence less time. Additionally the use of zero tick mechanics can be used to improve the time between piston firing.
13->1 does not move all the blocks. Remember there is iron (or some other block) in front and the index of a piston is equal to the number of blocks in front of it. Pistons can only push 12 blocks, so piston 13 can’t activate since it has 13 blocks in front of it.
@@peterbullard8040thats why they activated 1 first.
14:05 The little touch with the empty blocks accentuated by the glass texture is so aesthetically pleasing!
It's so cool that #SoME3 is getting some really creative entries even from the channels you wouldn't expect to join.
This is the second video I've seen on that, but the first I've actually watched and I have no idea what it is.
(the other being mate in Omega, the chess one)
@@TyphoonBeam It's a yearly competition organized by 3Blue1Brown (a yt channel) to support smaller educational and other math related creators
What’s SoME3?
@@burningnetherite4206 Summit of Math Education is competiton to foster the creation math content online. Anyone could join competition until 19th August. Now you can't join as a participant but you can still join as a judge
@@burningnetherite4206third edition of the summer of math exposition
The way you parallelized this is actually really similar to how CPUs are optimized. Cpus have several stages they have to do, and they used to have to every stage before the clock cycle. But modern cpus will only do one stage per clock cycle, but will run them all in parallel by starting a new instruction on each clock cycle.
I feel like this is exactly the type of video that 3b1b loves to see with this SoME. I love how gaming communities can go together like this with the math community.
In the case of minecraft, all the people that are serious about redstone builds (talking about "technical" minecraft players) are on the smarter side of the gaming community and are not afraid of crunshing numbers and investing more time doing math about the game than actually playing it. I always like it, when I catch myself calculating growth of supplies, output of farms, speed of a vehicle, damage over time, and so on, in the middle of a gaming session 😅
Looked at the profile of the video creator just now, and in fact, it is not a math guy doing minecraft, but a minecraft guy doing math 😂 Technical player right there.
As a math nerd and minecraft fan, I am very happy with this video
haha, the minecraft community (specifically the redstone community) is intertwined with the maths community. There's just too much overlap for it not to be the case.
I've gotta give you props for this. This is gotta be one of the most clear explanations I've seen. No crazy music; and straight to the point, and showing the steps behind each thought and conclusion.
Subbed.
for a 13 piston extender, you can just do 1, 13 → 1
saves 11 extensions, and should be fairly simple to generalise up until 24 at least
edit: as a few replies have pointed out, it actually doesn't really matter which piston is extended first. i just happened to choose 1 in my head
edit 2: wow okay
so it turns out the method i thought of has since been generalised by the pinned commenter (who actually called it "@abugidaiguess's method"!)
i honestly didn't put much thought into the comment beyond the specific case for a 13 piston extender, so i'm really glad other people did! :D
Came here to say this.
This
I was thinking 12, 13→1 which works basically the same way
I had the same idea only just starting from the back. (12,13→1)
Edit: eivindhamre3026 wrote the same thing 30s before me
@@kajatoth9151 too slow
There is a way to think about piston extenders which I would like to share!
1. Think about the blocks being moved to be air block, instead of pistons.
2. When an air block is in a certain location, movement on the two sides doesn't interfere with each other.
3. We can look at only a single air at a time, we can simply assume the movement in the back to happen first, until the air space is filled.
4. When extending, there are N air blocks to be moved. The first air block moves N meter, and the N'th air block moves 1 meter.
5. Moving air K meter to the back takes at least K/12 piston movements, rounded up, which is written as ⌈k/12⌉.
This is because air moves a maximum distance of 12 blocks per piston movement.
6. Since this is always possible, the minimal amount of piston movements for an extension of N meter is the sum of ⌈k/12⌉, from k=1 to k=N.
7. This logic works the same for retraction; the minimal amount of movements is the sum of ⌈k/1⌉=k, from k=1 to k=N, which is actually just equal to ½N(N+1), or the N'th triangular number.
Personally, I think my proof is very elegant, hope this helps!
This is the most elegant proof I've seen so far - thank you for sharing! I saw your note about winning IMO - that's absolutely incredible, congratulations!
@@mattbatwings Thank you, but I didn't 'win' the International Mathematical Olympiad; multiple people win gold medals every year.
In all of the Olympiads, half of the competitors wins a medal, and the ratio between gold, silver and brons is 1 : 2 : 3.
100 countries send their six best competitors to the IMO, so a little less than 50 people win a gold medal.
I was 19th.
@@caspermadlener4191I appreciate your work to the Minecraft community and I Hope, One day, to see your name in the podium of the IMO👏
@@Lumyx_x Thank you, but I was already on the IMO podium in 2022, and the IMO is ment for people before university.
@@caspermadlener4191 In every case, your explanation was perfect, even if I am not a great mathematical Person, i clearly understood It, thx
A detailed analysis of the optimal extension sequence:
Consider the total cost of an n-extension. We can consider the total cost to move all required blocks 1 block forward, 2 blocks forward, 3 blocks forward etc. separately, because each extension pushes a subset of the pistons/block which have all currently been moved forward the same amount of times (i.e. it is impossible to simultaneously push two pistons that have moved a different number of times each, because there will be an air gap in between). The first set of blocks (that needs to be moved forward once) has size n, then the next set (that moves forward twice) n - 1, then n - 2 and so on until there is only 1 block that must be moved n times. The kth of these has size (n - k + 1) and requires ceil[(n - k + 1) / 12] extensions as each extension can only push at most 12 blocks. So the total cost is the sum from k=1 to n of ceil[(n - k + 1) / 12]. Notice, however, that this is equivalent to ceil[(n - 1 + 1) / 12] + cost(n - 1), that is, ceil(n / 12) + cost(n - 1), with cost(0) = 0. This can therefore be expressed as cost(n) = ceil(n/12) * (6 + n - 6*ceil(n/12)).
Also note that this lower bound is achievable because we can simply do the process one step at a time, moving forward the first n-1 pistons in ceil(n/12) steps, then the next n-2 in ceil((n-1)/12), etc.
The most interesting piston extender math (in my opinion) is that of "hipster" extenders, which are piston extenders that extend beyond the wiring itself. This means in order to power pistons beyond the wiring, movable power sources such as redstone blocks or observers must be extended and retracted themselves. This makes the analysis of the optimal sequence slightly more tricky. Every distance extended/retracted beyond the wiring requires recursively using the distances 1, 2 or 3 blocks before it one or more times (in order to extend and retract the power source, and move the piston back 1 block), leading to exponential growth in the length of the sequence.
So wait you boiled the extension process down to a function? I could be very wrong because i am dog ass at math, nice explanation though!
Yes, what we care about most is the length of the sequence (not the actual sequence itself), so I defined the function cost(n) to be the length of an optimal n-extension.
@@sammyuri ah okay thanks for clarifying
Solution "may" not be optimal. It "may" be the case that somewhere in an optimal solution, a piston extension is used in both the moving of the 7th block and also the 10th which could make a better solution than the one you propose.
I put "may" because I think you're right, but you didn't prove this "may" had to be wrong.
@@viktort9490No, this solution is rigorous. In fact, what you say is true (a piston extension IS used in the moving of both the 7th and 10th blocks) - the point is that it can be used to move BOTH those blocks if and only if they have moved the same amount of times so far, or there would be an air gap between and only the 10th block would be moved. This then leads to the independence of each distance moved and the rest of the proof.
Justwatched 3b1b SoME3 recommendations. Sadly didn't see this in the 25, but did see it in the comments. So came here to watch it. Again. Good job. 👍
after finding that dispensers are a dynamical system I'm not surprised you've found some math surrounding piston extenders that warrants a whole math explanation vid, excited to see what you've put together and best of luck with your submission
(This comment was made before the premiere)
My guess for the video is gonna be deriving an algorithm for finding the order in which pistons need to be fired to close/open an nth long piston extender
That and/or deriving the correct timings to do such
@@austinclees9252extender designs are simpler than that, my prediction is that it's gonna be about the observer + 2tick-repeater design which is infinitely expandable and uses just a clock and a timer to get all the pulses, it's a really smart design because although the inputs are kinda intuitive, the piston sequence isn't but in the end it all somehow manages to work
Which vid was this?
@@NickGarcia1519it's just a dispenser math video, can look it up on yt
oh my god this was the most beautiful math video i've ever seen
It appears 3Blue1Brown has reached the Minecrafters
Yeah i like both
EXTENSION PARALLELIZATION is exactly what GPU's do comparatively to CPU's ... and there are engineers called CUDA programmers their job is to find a way to parallelize chunks of repetitive codes in order to take advantage of the shear amount of cuda cores that can parallelize process data
So I had an idea at around 8:12, and that's that the 13 block extension could be done more simply than 12->1, 13->1. I believe that the sequence 12, 13, 12->1 would also work but with less repetition. Therefore, this disproves that the formula for sequences of individual extensions does not necessarily always give an optimal result.
Edit: Well it's not something unique I've came up with, but it is still true so I'll take that. Great video as always
n < 13: n --> 1, n> 13: 1 + (Number of pistons - 13) ---> (Result of the past equation ) - 1, n --> 1 (One at a time)
The formula at 9:11 doesn't produce optimal results every time. Take the 13 piston extender, you could do 1, 13->1 and that's 14 pushes insted of 25
the formula does allow for an infinitely expandable and modular design to an extender though. using the most optimal number of pushes would require different extenders to have their own different redstone circuits.
the formula ends up being the same after parrelisation
@@Drawliphant You need to 1 tick piston 1, or honestly any piston other than 13, and then extend all pistons 13 -> 1
@@Drawliphantyou don't need to push an expanded piston. You do a quick pulse with one of the first 12 pistons. It will push everything forward and not have time to pull it back. Then the gap created means 13 can now fire to fill that gap and then you can just go down the line.
I'm not a redstone nerd, but I am a math nerd and I love doing random stuff in Minecraft. I liked this video a lot, such a creative entry to the contest!
3Blue1Brown--Grant Sanderson is one of my most watched channels on youtube. You are an absolute legend for sharing with the world the wonders of Maths and Minecraft, Mattbatwings. Thank you for all that you do; this is incredible!
I see that some people want piston 1 to push the block right in front of it, and then do [13,1], but I feel like starting as close to the next chunk as possible would be a bit more optimal, as in, for 13 pistons, piston 12 pushes, then you do [13,1].
For 25 pistons, you'd do 12, then 24, then [25,1], so you always end up only doing the n->1 pushes when you can push for the entire chain, instead of having any sub-chain pushes that aren't a single push that moves 12 pistons 1 step forward to free up pistons further back in the chain.
To further extrapolate:
Make every multiple of 12, starting from 12*1 and working up towards 12*m < n, push the 12 blocks in front of it, and when you reach 12*(m+1) >= n, just do the n->1 push chain.
This is the intersection of multiple internal Venn Diagrams I have. Math, Redstone, etc. What a video! Hope your SoME3 sub wins!
This is probably one of the most intriguing and entertaining Redstone videos I've ever watched
I’m so excited.
SoME has been a great way for a pure math undergrad like myself to pass the summer. Cant wait to see how you take things :D
even just a middle schooler like me!
why math bruh it's so boring when you don't have anything to apply it to
@@anon1963 frick you! Maths is the best
@@anon1963some people just find it fun.😊😊😊😊
@@anon1963First of all, higher level math is beautiful and not boring in its own right. Second, there are millions of applications of many, if not most, areas of math
Yoooooo, kinda sick you're submitting to SoM3. Didn't see it coming, but it's very welcome
I didn't think you would participate SoME3 ! This was definitely a surprise, but a pleasant one =)
Very nice! Also some clarifications:
• pistons don't need a long pulse to retract, they can retract with a normal single pulse. Technically you can get away with zero tick stuff to push multiple pistons in sequence at the same time but that gets very glitchy with update order shenanigans and you really don't wanna mess with that.
• as others have pointed out, the reason you can't prove that the repeated steps are optimal is cause they aren't: the modular method is!
• the act of sticky Pistons leaving behind a block when powered for a single tick is called "block spitting" and it was originally a bug, much like some other redstone features (quasi-connectivity comes to mind)
• we technically have infinite piston extenders and retractors, though it's a bit cheaty to call then "extenders" since those are their own category of redstone tech: if you place a piston to push something that drags a sticky piston (facing backwards) with itself - such as a slime block - and then that triggers this piston to pull the other one along, you'd have a self-dragging contraption that moves infinitely until it encounters an obstacle. You can make the movement itself trigger pistons by using observer blocks. TA-DA! You have made a *redstone flying machine*! And fun fact, observers triggering when they move is ALSO a bug that became a feature! Aaaaah Minecraft...
The footage of you actually building the contraptions is really nice, please continue to do this
The proof for the Retracrion only needs a small addition to be valid for any number of blocks:
-6 is proven to be ideal for a 3 piston retraction
-any extra piston adds n (new number of pistons) block movements, because every block in the old chain (n-1 pistons + 1 block upfront) needs to move back one more block each
-any extra piston adds n ( new number of pistons) retractions in this algorythm, becase n->1 is added at the end of it
=> the required block movements and the number of retractions start at the same number and rise by an equal amount for each itteration of n, therefore both numbers are equal for any given n
Q.E.D.
mattbatwings and 3blue1brown crossover is not something I know I needed, but holy crap I'm all here for it O.O
if only
its not really a crossover. Its just a video for 3b1bs math video contest
Lol
I see a lot of people with the optimal solution for piston extension but not a formal proof, so I figure I might give one. Apologies if someone else already did so.
I'm going to generalize the problem slightly to be "each piston can move at most 'm' blocks". Just take m=12 for the specific solution.
To describe an optimal optimal solution, define q, r as non-negative integer s.t. n=q * m + r, r < m (quotient and remainder)
TLDR, an optimal solution is to move block m, 2m, 3m until qm, then if r != 0 move the nth block. After this process the leftmost piston should be followed by a gap followed by the other n-1 pistons next to each other. Then repeat this solution recursively on the n-1 pistons.
You can prove this is optimal using induction and by showing that any other opt sequence is at least as good as this one by reordering steps in the sequence.
---
Lemma 1: Lower bound for optimal sequence is (n - 1).
Pf: Define a component to be a collections of pistons next to each other that are not interrupted by gaps. The problem starts of with 1 components (of size n), and ends up with n components (each of size 1, each individual piston is it's own component). When a piston is pushed in the rightmost component the number of components increases by 1, otherwise it stays the same since the block of pistons being split off joins the component directly after it. So at least (n-1) steps are needed to get to the final state.
----
In your video you showed examples of (n-1) length sequences for n S_j and there must be a gap after the S_i+y piston, so swapping them in our sequence doesn't change the blocks they push out, and after applying both steps swapped we end up in the same configuration as before.
With the above, we can keep moving primitive steps before non-primitive ones and end up with a new sequences Q_1, ... Q_K where all the the primitive steps of the original sequence are done before the non-primitive ones (in the same order; aside another way to put this is that the subsequences are independent to the action of piston pushing - there's some group theory way to formalize this if you want). The primitive steps at the beginning must be strictly increasing, since each step decreases the size of the leftmost component, and it must end with a step where the left-most piston is extended, since we need to end up with a leftmost component of size 1 by the end. Now notice that there's always two components here, except for the initial state which has one component. This is because we're only acting on the leftmost component, we can only increase the number of components if we act on the rightmost component, and the only time the left and rightmost components are the same is at the start. The most that any operation can push out is 'm' pistons, and pushing out in our case means transferring from the left component to the right component. By the end of process you will up with a left component of size one and a right component of size n (we started with n+1 pistons). This means that we need at least ceiling(n+1/m) primitive steps. The sequence from the TLDR does this, but if there's a remainder then there's a lot of other solutions too since you could move the remainder first (like some other solution here do, or mix and match etc.). Once you do this you have the leftmost piston by itself and the remaining piston is a single component of length n, so we just use our inductive hypothesis and repeat the same procedure to the remaining parts.
---
So yeah, there you have it. Hopefully I didn't make any mistakes there.
9:05
You can find a quadratic lower bound on the number of elements in your extension sequence as follows.
Your initial state with n pistons can be represented by a sequence
P^(n+1) H^n
where P denotes a piston (or the block to push) and H a "hole", i.e., air. Your final state is
(P H)^n P
Note that both states have the same length. All your moves, i.e., individual piston extensions,
will just swap P's and H's around in the state.
So this means that the n holes must be moved somehow such that they appear in the even
(2nd, 4th and so on) positions, by means of piston extensions.
Observe that every move must take a clump
P^l H with l
This brings me back to mumbo jumbo building triple piston extenders
The true infinite piston extender: A flying machine
Edit: How did this get 600 likes? wow. If anything i thought i'd get criticised for dodging the video's topic
Flying mashine go brrrrrr😂😅😂😅
@@davidmunizwessels8520 “
Frfr
To easy
till the chunk it is in hides
On extension optimality: Your sequence is sub-optimal in *two* ways: [edit: never mind, you mentioned the second improvement at 9:14.]
As others have pointed out, in your 13 piston example, you can extend only piston 1 and then do the 13->1 sequence.
And for a 14-piston extender, you _COULD_ do 2->1 first and then 14->1. But you can now do some operations *simultaneously*: You do 2 first, then 1 and 14 at the same time, then 13->1.
For 25, you do 1 in the first "tick", then the second "tick" start the 13->1 sequence, then the third "tick" start the 25->1 sequence.
And so on.
I think that's the optimum. It adds only a single "tick" for every group of 12 that the pistons need to be split into.
0:16 this "me lmao" guy is pretty insane
Very nice how contraction parallelization enables you to have it work with a log of blocks in adequate amount of time. So instead of n! steps you just need 2n-1. Every for small amount like 10 blocks the difference is incredible 10! = 3628800, 2*10-1 = 19
Funfact: retraction doesnt need a long pulse. With a sticky piston and a block on it. You can use 2 short pulses to extract and then retract
Sometimes it's better to assume cows are spheres in a vaccum.
@@atlascove1810 This makes me remember the science diagram of a cow's aerodynamics.
This was an incredible video, the visuals were super helpful and the math was impressive. Great job!
This is actually a great way to introduce mathematical induction, that I've never thought of as a huge maths and redstone nerd! Ty again mattbattwings and best of luck !!
This helped me make a one sided stackable piston extender using coppet bulbs and I just wanted to say thank you for simplifying these things for us!
Very good visuals! Sloimay made very cool animations. But I'd like to see more on retraction parallelization, it seemed quite glossed over.
it’s not that complicated! each retraction of n pistons takes exactly 2n - 1 steps with parallelization, and n(n + 1)/2 steps without it
the way you have the parallel pisron firing reminds me of a smarter every day video called STRANGE but GENIUS Caterpillar Speed Trick with caterpillars that ride each other like a wave
Extending two pistions (and having one pushing the other) at the same time (in the same game tick) is possible. I uploaded a short video showing in which cases this is possible, because there are some limitations to that. I don't know if this can be used to speed up pistion extenders even more.
This video unironically made math interesting to me. Your visuals are really easy to follow, I only backtracked like once (I usually backtrack a lot in videos). I like how you started simple and gradually went more complex leading to formulas. I'm definitely subbing!
0:02 *cries* The first tutorial World I ever played…
sameeeee
@@ajmod73 YAY!
Something that I find very cool about this is that it kinda resembles liquid travel through a narrow tube, or low resolution fluid simulations. The spaces between the blocks look like air bubbles floating up and out as they break the surface tension of the water above them.
Couldnt you in a 13 piston seqience just start with 12 then 13 and then 12-1, instead of 12-1 then 13-1
Something that didnt get said here but i think is mathematically interesting is that the retraction system is just the reverse of the push system when the push limit is 1 block.
10:30 oooh that's a wrong combination of numbers :)
I don’t know if it includes this but, you can do a 12 push for anything less than 25, then do the 24-1. This saves alot of redstone
This saves 11 pushes and works if repeated
Minecraft is honestly what convinced me to go to engineering school.
A few observations :
1. Extension length formula is 6*floor((n-1)/12)*(floor((n-1)/12)+1) + n
2. For retraction, two different recursive formulas are possible, depending on whether you chose 1 or 3 for the 3 piston extender. You can choose to bridge the nth gap first and then recursively bridge the next gap, on and on, or you can do it the opposite way, bridging the 1st gap, then the 2nd, and so on.
Indicating relevant subsequences with a semicolon, one sequence gives 1; 2, 1; 3, 2, 1, while the other gives 1, 2, 3; 1, 2; 1.
Both are the same length. In recursive notation they both start with S(1) = 1, but the one in the video is Sequence(n) = Sequence(n-1), n - > 1, while the alternative is Sequence(n) = Sequence(n-1), 1 -> n.
Love this, math isn't exactly the _last_ thing I think of when I think of minecraft, so it's cool to see a deep dive into one of the game's most versatile mechanics!
Loved this video! Another interesting bit of minecraft math that I've been looking into is an algorithm for generating piston sequences for a piston door of any size
Just casually scrolling through for all of the people who think they are smart and found the more optimal Extention method
For the extender, it's better to think about trying to activate the backmost piston as soon as possible, similar to how it worked without a push limit.
As it's only possible to move 12 blocks at a time, start with piston 12. Next, the furthest behind 12 that can successfully activate is 24, then 36, etc. Activate all the multiples of 12 until piston n can activate, then activate all the multiples of 12 until (n-1) can activate, repeat for all pistons in the extender.
So the method for an n-piston extender, in pseudocode, looks like:
let k = n
while k > 0
let j = 12
while j < k {
push j
let j = j + 12
}
push k
let k = k - 1
}
This sequence for the 40-piston extender is:
12, 24, 36, 40, 12, 24, 36, 39, 12, 24, 36, 38, 12, 24, 36, 37, 12, 24, 36, 12, 24, 35, 12, 24, 34, 12, 24, 33, 12, 24, 32, 12, 24, 31, 12, 24, 30, 12, 24, 29, 12, 24, 28, 12, 24, 27, 12, 24, 26, 12, 24, 25, 12, 24,
12, 23, 12, 22, 12, 21, 12, 20, 12, 19, 12, 18, 12, 17, 12, 16, 12, 15, 12, 14, 12, 13 -> 1
which has 88 pushes, while your method uses 112 pushes.
It's unfortunately not nearly as neat to write the sequence out nor capable of parallelization, but it definite saves pushes. I believe this is optimal, though I don't know how to go about proving it.
Though it seems @arcycatten already came up with a different solution that agrees on number of pushes, has a neater sequence, and is parallelizable.
but spacewalker 46 piston extender >>>>
Crafty!! Hi :)
And btw avogadoo’s infinite extendable instant piston extender >>>>>>>>>>> :)
i have 0 interest in redstone and hardly any interest in math but you explain this in such an interesting way that i cannot stop paying attention. its so easy to understand because of the visuals and how well you explain everything, i love this.
The extension sequence you describe is not optimal for every length piston extender. For example, with the 13 extender, you can have any one of the pistons 1-12 fire, creating a gap, then just extend from 13 to 1. However, I think this is just as fast as the sequence you named with parallelization, although requiring more piston extensions. Yours is probably easier to wire though (at least smaller) because you can just repeatedly power the same line from the back.
Honestly this is a great vid, the topic is interesting and presented very well.
I've been playing with redstone for the last 11 years, and only now do I understand how to generalize piston extenders. This is so cool!
10:30 twin towers
Lmao
bruh
As someone who studies advanced level mathematics and physics at school and also plays videogames like Minecraft for fun, i always considered gaming and my studies to be completely separate from each other and not at all connected. Gaming is always little more than a fun leisure activity whilst my studies in physics and maths is more important and mandatory schoolwork. However, watching this video has opened my eyes fact that there are likely many different connections between maths (and maybe even physics) and the games that i play.
what counts as advanced level mathematics?
@@czechmateyoulost1755 I mean A Level maths and physics. It's the qualifications you take at age 16 and 17 in the UK where you usually pick 3 or 4 subjects of your choice that you want to study before you use your grades in your subjects after the end of 2 years of study once you've done your final exams to enrol at university
@@ShaneB24642 Oh okay, i thought you were studying math at university
for a 13 piston extender can't you just do 12 then 13->1 for the extension
You have to give a pulse, wich maked it more complicated
@@huseyinemreeken3024 but it still would be the fastest way without grouping
Started watching in the background while playing minecraft, just for background audio, but I have now spent the last 15 minutes just watching the video, standing still in minecraft. Nice work, very entertaining, and awesome :)
BRO YOU ARE RIGHT!!! I thought you were just trying to make fun of us with the "Just be good" thing, so i whipped out my sketch book, drew from a reference, and IT LOOKS SO FUCKING GOOD!!!!!! imma try to keep up with this.
The explanation of redstone and specifically the piston was done so well and allows people who haven’t even played Minecraft to get into the video.
Thank you for helping fellow youtubers by putting the music you use in the description, well all appreciate it
15:54 TRIANGLE NUMBERS!
I ran into a lot of these number sequences when doing abstract math for fun a while ago
Fantastic video :D
A simple answer that is also a proof (at least with some simplification is to always push as many blocks as possible). Since in total the amount of movement done by each block can be counted and we know this movement is necessary, pushing the maximum possible at any one point will minimize the amount of instructions given. An additional argument that makes understanding this easier, that changes the approach slightly is that we can always push from the left first, since these are necessary and cannot be done by pushes further right, this then also reduces the problem to smaller instances. I.e. f(25) = (12, 24, 25)+f(24). Funnily this also reduces to a fairly simple recursive formula f(n) = (12*i | for I in (1,n) if 12*i sum_{i=1}^n ceiling(i/12) or even simpler sum_{i=1}^{ceiling(n/12)} i*min(12, n-12*(i-1)).
As I just noticed, this then also generalizes to the parallelization case, since we are maximizing the amount of parallel operations we can do at any one time, while minimizing the amount of operations given. This however, does appear almost impossible to actually implement ingame though 😕
I believe using the dividsion algorithm, n=sq+r, r from 0 to q-1, is a simpler formulation, using q=12 of course. Also, i believe the most optimal (though less simple/practical) sequence for an n piston extender is as follows:
Let {12m} 1 to s indicate the sequence 12, 24, ... , 12s. Let [{12m} 1 to s, n-(a-1)]r indicate the sequence which consists of the sequence in square brackets repeated r times, where "a" is a counter (so the first time a=1, second time a=2, third a=3, and so on till a=r). The optimal sequence then, for some n=12s+r, r from 0 to q-1, is: [{12m} 1 to s, n-(a-1)]r, [[{12m} 1 to s-c, (n-r)-12(c-1)-b]12](s-1), 12->1, where "a" is a counter for r, b is a counter for 12, and c is a counter for s-1 (so for the first 12 repitions, b goes from 1 to 12 but c is 1, and for the next 12 c=2, and so on until c=s-1). In essence, this moves every multiple of 12 piston (rather than doing 12m->1) then moves the "highest" piston, which goes down by 1 each iteration.
In counting steps, this video's proposed sequence {12m->1} 0 to s, n->1 has 12(1+2+...+s)+n steps. The sequence proposed in this comment has r(s+1)+12s(s+1)-12(1+2+...+s) steps, which can be simplified to n(s+1)-12(1+2+...+s) steps. In comparing, note that 12(1+2+...+s)=12((s^2)-(1+2+...+(s-1))) and see that, with the video's on the LHS and this comment's on the RHS, after simplifying we have 0?=?r-12. r-12
this is mathematically and visually elegant and beautiful. never seen piston extenders explained in such an approachable way. i sure wish this kinda thing existed before slime flying machines!
17:14 For people who are more nerdy:
Let Len(n) be the length of Sequence(n). So we have Len(3) = 6 as Sequence(3) = 1,2,1,3,2,1 which is 6 items long. We now have a second recursive relationship:
Len(n) = Len(n-1) + n
This works because Sequence(n) is a combination of n->1, which necessarily has length n, and Sequence(n-1) which has length Len(n-1). We also have a base case of Len(1) = 1.
Solving the recurrence relation we have, after rearranging:
Len(n) - Len(n-1) = n
Is a bit difficult to explain. The short version is that we can find a closed formula for Len(n) in terms of n. You can find explanations of how to do this online but it’d be too hard to explain in a UA-cam comment. The short version is that you get the following formula:
Len(n) = n(n+1)/2
Finally, let’s consider the retraction. The block must retract n blocks, piston 1 must retract n-1 blocks, and so on. In general, piston k must retract n-k blocks so the total retraction is the sum
S = n + n-1 + n-2 + … + 3 + 2 + 1 + 0.
This is the famous triangular sun and has a closed formula (which you can prove). The sum S has the following closed formula:
S = n(n+1)/2
Well isn’t that neat? They have the same closed formula! As we showed that the length of the sequence we generate is equal to the minimum number of retractions, it therefore follows that the sequence generated is optimal. QED.
It's not optimal: for a 13 piston extender, you have 1, 13->1. (14 steps; clearly less than 12->1, 13->1 with 25 steps).
In general we have that n%12->1, 12+(n%12)->1, 24+(n%12)->1, ..., n->1 is a valid solution.
e.g. for 25: 1, 13->1, 25->1
Your solution takes n + 6((n//12)^2 + n//12) steps (where // is floor division) mine takes (n%12)(n//12 + 1) + 6((n//12)^2 + n//12).
n//12 = (n - n%12)/12
n%12 < 12
=> (n%12)(n//12 + 1) = (n%12)((n - n%12)/12) + (n%12) < 12((n - 12)/12) + 12 = n - 12 + 12 = n
Hence (n%12)(n//12 + 1) < n
Hence (n%12)(n//12 + 1) + 6((n//12)^2 + n//12) < n + 6((n//12)^2 + n//12)
So my solution is more efficient in general.
This is the best video I've seen in a while. Obviously math and redstone relate quite heavily, but somehow with the animations and explanation, it was very clear and concise. Thank you for your inspiration.
the 13-piston example is best to illustrate that the 12-1, 13-1 system isn't optimal:
If you trigger piston 1 first, then piston 13 has 12 blocks in front of it. the sequence 1, 13-1 would thus work the same as your sequence of 12-1, 13-1 while only adding a single piston push to the original.
For something like 24 pistons, firing piston 12 first will "break off" the front set of blocks, then piston 24 can push the latter section, but then it stalls again so you need to push 12 again, then you can pust piston 23 etc.
so the sequence becomes an alternation: 12,24,12,23,12,22 etc. which should end up being a lot faster than 12-1, 24-1
I've not finished the video but i saw you ask so i thought i'd post. I tried to build something in creative mode really quickly to see what i can do but realised i don't know how to pulse the redstone signal yet lol.
As someone who is currently in their first year of uni learning computational thinking and someone who grew up loving Minecraft, this is such a cool video and quite inspiring actually. Thank you for this! Keep up the great work
It is just amazing work. I have very much respect to people like you, because you made whole video which have a lot of details and explains in easy way smart, little tricky and interesting thing
A short pulse can also pull a block, if it's detached from the piston already.
I got bored and decided to output the formulas:
(n - 6 * c) * (c + 1) - the number of pushing actions (optimized)
(2 * n - 1) - the number of folding actions(n > 0)
Where:
c = n // 12
For example:
13 pistons (modular): 1, 13 -> 1; 1 + 13 = 14 steps or
( 13 - 6 * (13 // 12) ) * (13 // 12 + 1) = 14 steps
30 pistons (modular): 6 -> 1, 18 -> 1, 30 -> 1; 6 + 18 + 30 = 54 steps or
( 30 - 6 * (30 // 12) ) * (30 // 12 + 1) = 54 steps
500 pistons (modular): 8 -> 1, 20 -> 1, 32 -> 1, ..., 488 -> 1, 500 -> 1; 8 * 42 + 12 * (1 + 2 + ... + 41) = 10668 steps or
( 500 - 6 * (500 // 12) ) * (500 // 12 + 1) = 10668 steps
If something is wrong, write in the comments
bro a SOME video by you is just such a crazy crossover i didn’t even suspect could happen. it makes sense tho 🔥
i just noticed that the retraction sequence can also work as a extention sequence
and actually you don't rly need a long pulse to grab a block, a short pulse can retract a block too, if the sticky piston and the block don't have space beetween them a short pulse will separate them with a 1 block gap like you showed, but starting the other way around with a gap of one block beetween the piston and the block a short pulse will close that gap like a long one.
using this fact you can make a full piston extender that enable retraction only using the retraction sequence which would not be the fastest but would use only 1 circuit for bothand i think observer blocks give a pretty fun way to do it.
10:20 it's the same principle used in CPUs to parallelize instructions, it's called "instruction pipelining"
The retraction problem is very similar to the tower of hanoi, a way it can be visualised is counting up in binary where when a digit changes from a 0 to a 1 the the piston corresponding to that retracts, i.e.
001 - first piston retracts
010 - second piston retracts
011 - first piston
100 - third piston
and so on. This method can also be used for the tower of hanoi which is an old wodden puzzle
Just found your channel through this video and Holy shit your videos have been the highlight of my week! Absolutely amazing videos that give me the same feeling as watching Ben Eater videos. Keep it up!
Bro is The Best Maths Teacher in the world...
Change My Mind
there is actually a pattern for the retraction pattern for the piston, it's called the " Triangle read by rows: row n lists the first n positive integers in decreasing order", which is quite fascinating to find this mathematical coincidence
I feel like UA-cam is listening to my lectures when I see videos that directly apply what I just learned😅
Optimal extension is given by f(n)= ceil(n/push lim) + f(n-1)
Ceil is just rounding up after division. The idea is extend the final piston while using the remaining as little as possible. This will then produce a smaller chunk of size n-1 which we apply the same rule recursively.
The final piston can be extended after ceil(n/push lim) pushes, and that value corresponds to maximal chunks (meaning always pushing the push limit) lies before it.
I actually used those principles in my designs before, in both my one wide, and my bigger designs. The only thing I changed was the following: I wanted to make my designs as compact as possible, not as fast as possible. This lead to me not being able to feed extra inputs to the pistons from the side, so in my designs, the signal starts at the back, and moves towards the front of the extender. When it reaches the first 12 pistons of the extender, it will automatically start extending, since the push limit isn't a problem anymore. Because I just input all the inputs needed, the next batch of 12 pistons will start extending immediately after. That goes on until the very end of the extender is reached, and works for every piston extender length. It completely eliminates the risk of accidentally inputting a signal at the wron block, thus being way simpler, but comes at the cost, that it might take some time until the extender starts extending. For an extender that only has 50 pistons or so, that only are a few seconds, however I made a 1000 piston extender on that principle and it takes quite some time to start extending xD. All my designs are on my channel, tho I won't post links to them here, since this comment is not meant as some sort of ad, but I want to share my experience on making a compacter, simpler design, ober a faster one.
I love this kind of video, hope you will continue to make them after SoME3. The incorporation and application of mathematics into minecraft was really well done. My one minor piece of constructive criticism is that, while I could feel that it worked, the proof that you showed for the retraction being optimal needed to be completed. Thank you so much for this great video.
I love the formality reminds me of actual discrete math problems taught in my university
Bro I swear if 20 years from now we gonna see math problems like this asking like “If we have a piston extension with 30 pistons how long is the length from the back piston to the block when activated”
Your design is so clean, simple, and infinitely expandable!
This video was everything I was hoping it'd be from the premise. Very nice
Man gotta love my two interests colliding in this!
Also, two notes:
For the retraction, it’s pretty easy to continue the proof for perfect optimization.
First, how many more blocks get pushed forward between n and n+1? It would be n, since, as it was noted near the beginning, the nth piston has n blocks in front of it, and each piston added shifts everything in front of it forward 1 block.
Next, how many more retractions are added with each piston? Again, n, as the sequence just adds n->1 to the end.
Thus, this sequence is optimal for all n. (Assuming n is a natural number)
Secondly, it’s kinda hard to see, but it looks like the final system is not only optimal for pulses needed, but also time taken. For it to be time optimal, the end block must be moved with every set of pulses, which I’m pretty sure it does.
Gotta love it! Puts Mumbo’s monstrosity of a 22 piston extender he made a few years ago to absolute shame
In CompSci terms, the piston extension formula can be described as a "greedy algorithm": Simply power the rightmost (oriented based off your video) piston with the largest (up to 12) number of blocks in front of it. Repeat until no piston has a block in front of it