The Fascinating Math behind Piston Extenders #SoME3

This is my submission for the Summer of Math Exposition, hosted by @3blue1brown

Piston Animations created by @Sloimay

0:00 Introduction
0:36 What is Minecraft?
1:42 What is a Piston Extender?
2:16 Problem Statement
2:35 Extension Sequences
8:51 Extension Optimality
9:13 Extension Parallelization
11:11 Extension Circuit
12:38 Retraction Sequences
16:15 Retraction Optimality
17:16 Retraction Parallelization
17:40 Retraction Circuit
18:52 Showcase
19:45 Thanks for watching!

Music (in order):

[arcycatten]

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!

[agma]

14:05 The little touch with the empty blocks accentuated by the glass texture is so aesthetically pleasing!

[youtubeviewerxx]

It's so cool that #SoME3 is getting some really creative entries even from the channels you wouldn't expect to join.

[owencmyk]

I'm aware somebody else has already found this out in the comments, but I noticed a counter-example to your 13>1 12>1 being optimal is you can simply extend 12 and then 13>1. Saving like... 12 extensions

[rohiem]

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

[ifroad]

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.

[kf]

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. 👍

[Starwort]

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

[Julian_H]

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.

[ncolyer]

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 <3

[wildwyatxbox]

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.

[abugidaiguess]

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
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

[caspermadlener]

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!

[sammyuri]

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.

[eee_inn]

9:00 definitely not optimal. Just think of a 13 extender, instead of doing 25 pushes like your method, you could extend #1, and then do 13->1, totaling 14 extensions, saving 11 over yours, which is generalizable to longer extenders

[cheeseburgermonkey]

It appears 3Blue1Brown has reached the Minecrafters

[deepmaths]

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

[LupusMobile]

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!

[shhdev]

oh my god this was the most beautiful math video i've ever seen

[commandblock]

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