Can water solve a maze? [video] | Hacker News Reader

Can water solve a maze? [video]

youtube.com

348 pointsgronky_125 comments

He's wrong about why that maze towards the end of the video doesn't empty out the supply tank. It's not surface tension, but rather it is the fact that the path goes up and down. The down parts of the path will be filled with air, and the up parts will be filled with water. Water is more dense than air, so the supply must have more pressure than the sum of all the heights of the up parts in order for water to flow.

This is why you don't have water pipes in your house go up and down loads of times. It can cause an air lock preventing water from flowing.

I thought so, because the first area of surface tension he pointed out is disconnected from the rest of the water. So that surface tension alone would have to explain it. But there was a lot of water up there!

I guess it is the same as the upsidedown glass of water with a sheet of paper underneath trick.

Mostly, but surface tension in aggregate is meaningful.

Surface tension is doing two things, first it’s contributing to back pressure several times in the same way it’s just barely keeping water from over topping. Secondly it’s taking up volume in air pockets thus increasing the pressure of those pockets. So, if he added soap to reduce surface tension the tank wouldn’t empty but it would end up lower. My guess is roughly an inch but it’s worth testing.

What's great about this video and the discussion is that something as familiar as water can have new and non intuitive things to learn about it. Are there any other examples of common things that have non obvious behaviour from every day experience?

water has a fair number interesting properties

https://www.chemistryworld.com/features/the-weirdness-of-wat...

> Are there any other examples of common things that have non obvious behaviour from every day experience?

How about the chain fountain (also from Steve Mould): https://www.youtube.com/watch?v=_dQJBBklpQQ

Sounds like great AskHN material to me, especially if you allow computers-related answers : - )

If you pump air through sand, it turns into a fluid. https://thekidshouldseethis.com/post/royal-institution-fluid... An important example application is in getting grain to flow smoothly out of a grain silo.

Some substances are "non-Newtonian fluids" meaning that they are liquid normally but turn solid under pressure. Famously, a mixture of cornstarch and water does this, which kids can have endless fun with: https://www.youtube.com/watch?v=Fnd-2jetT1w An example application is bulletproof vests which allow their wearers to move normally but will stop a bullet.

> If you pump air through sand, it turns into a fluid.

A recently-published fantasy novel uses "seas" of this as a premise: https://www.amazon.com/Tress-Emerald-Sea-Cosmere-Projects-eb...

ZipString/string shooter: https://www.youtube.com/watch?v=rffAjZPmkuU (other videos: https://www.youtube.com/watch?v=SOEXXlXi4RA / https://www.youtube.com/watch?v=f2krPkJ1pfs)

Slightly related: https://www.youtube.com/watch?v=BSSecjKRxEE (slow moving waves in moving rope)

Bruce Yeany have many good videos covering various physics phenomena.

How does that reconcile with the syphon principle? You'd figure that once the water is flowing out of the end, even if the tank was below some of the water's path, the flow would continue until all the water was gone.

Siphons work best once air has been excluded from the path. In fact, they work exactly as the opposite to why this maze isn't draining the whole source tank. In a working siphon, the head of water in the downwards direction is greater than the head of water in the upwards direction, which pulls the water forwards. In this case, because of the air columns in the down direction, there is a greater head of water in the upwards direction than the downwards direction, causing a reverse back-pressure.

Yep. It's easy to test for yourself that a siphon will quickly stop working if you let too much air into it.

This is also why you can't make very tall siphons, as if the pressure gets too low at the top the water will boil off, create a gas pocket of water vapor, and stop the siphon.

Yeah -- I was disappointed that he didn't show an example of a maze which is not solved by water (for a finite amount of head). I most often experience this phenomenon is when I'm putting the garden hoses away for the winter when you want all the water out of them. However, if they tend to curl up, then you can get into the state where the water won't come out of the hose once some air gets in. The only solution is to straighten them out.

I agree. It's weird, because I have to believe he realizes how it works (eg what it can "solve" and what it can't). Just demonstrating a little though experiment would go a long way.

https://youtu.be/zdkp9N3qfkI is a good overview of air lock.

Reminded me:

https://en.m.wikipedia.org/wiki/Water_integrator

  The Water Integrator (Russian: Гидравлический интегратор Gidravlicheskiy integrator) was an early analog computer built in the Soviet Union in 1936 by Vladimir Sergeevich Lukyanov. It functioned by careful manipulation of water through a room full of interconnected pipes and pumps. The water level in various chambers (with precision to fractions of a millimeter) represented stored numbers, and the rate of flow between them represented mathematical operations. This machine was capable of solving inhomogeneous differential equations.

Also see "A brief history of liquid computers": https://royalsocietypublishing.org/doi/10.1098/rstb.2018.037...

When I first started learning EE I conceptualized it with water. Ie voltage / potential is a higher water level vs else where. But this takes it to a whole new level, impressive!

If you search the web (or only Youtube), there are even digital water computers out there.

There's a whole Wikipedia page for the water-electricity analogy:

https://en.wikipedia.org/wiki/Hydraulic_analogy

What's funny is the math is identical between resistor - inductor - capacitor circuits, spring - mass - damper mechanical systems, and tank - pipe - valve fluid systems. The main difference between them is how you calculate the equivalent of resistance, inductance, and capacitance.

The thing that I found most interesting was actually the little side discussion about all mazes being two pieces. Something that I had never considered, but seems fairly self evident (assuming only one path exists through the maze).

Also makes me wonder what a proof would look like.

> Also makes me wonder what a proof would look like.

Start with the simplest possible maze (i.e. one square with a start and a finish) which will be in two pieces. Then show that all possible additions will not add further pieces except for when you "cut" into an existing piece to make a separate non-solution route (i.e. a looped route that takes you back to the same point).

(Having any loops in the maze would break the condition of there being only one solution as you could take a detour round the loop as many times as you like and thus have an infinite number of "solutions")

> (Having any loops in the maze would break the condition of there being only one solution as you could take a detour round the loop as many times as you like and thus have an infinite number of "solutions")

The loop could be somewhere inaccessible from the starting point. Perhaps your logic holds if you insist that all pathways in the maze are connected, though.

Or define that the "maze" is the collection of all the reachable areas from the start position. Then, it doesn't matter what you do in inaccessible areas as they're not part of the maze.

Meh. Sophistry. Changing definitions to get unexpected results is boring.

The simple truth is that the original proposition "all mazes being two pieces" is just false.

Obviously false when you have multiple exists, or when there is only one exit/entrance and the goal is to reach the middle of the maze. But even if we stick to one entrance one exit mazes you can have multiple paths from exit to entrance which cut the maze into multiple pieces.

But even if we constrain ourselves to one entrance, one exit mazes with a single solution path you can trivially construct a maze inside a large room without connecting it to the walls. Thus creating a third piece to the maze.

It is just simply false.

>But even if we constrain ourselves to one entrance, one exit mazes with a single solution path you can trivially construct a maze inside a large room without connecting it to the walls. Thus creating a third piece to the maze.

I would be intrigued to see that "trivial" solution - how do you prevent there being two routes (and thus solutions) around the third piece without connecting it to the wall?

I see what you are saying, yes the maze wouldn't have only a single solution after the construction of an inner maze.

In the literature on mazes, the distinction you are talking about is described to using the terms "simply connected" abd "multiply connected" from topology.

See e.g. https://www.britannica.com/topic/number-game/Mazes

I'd consider it to be specifying the "maze" more accurately. The idea is to be able to come up with an interesting statement (such as "all mazes of this type can be made of just two pieces"), but if you include non-reachable areas as part of the maze, then it reduces the number of interesting statements available but also doesn't add to the process of examining the routes and solution.

If you consider the same type of maze but have it in three dimensions, then all of them can be made out of just one piece, so it's clear that the definition of "maze" is too encompassing.

This comment took me straight back to Discrete Math in college, learning about inductive reasoning.

You can make a maze with only one path (other than paths that double back on themselves), but has three pieces: https://i.imgur.io/R4j6TH3_d.png

I think this is basically a flaw in the intuitive definition (or maybe only my intuitive definition) of "doubling back".

That maze has 3 solutions though. If there is only one solution, without reversing, it has to be 2 pieces.

In your case there are technically two paths through the maze (straight through and going through the loop).

Except that this maze clearly has at least two solutions. Straight through the corridor, or via the loop. And that's assuming you don't wander around the loops n times.

Three solutions if you want to be nitpicky. You can go around the clockwise, and counter-clockwise :)

Infinite solutions. You can take as many loops as you like before continuing to the exit.

But, to me, that requires doubling back on yourself (going through the little passageway twice). This is what I meant by my definition of going back on yourself being wrong

Not if your path trace kills you like the lightcycle trails in Tron.

Hmm interesting indeed. He also shows that you can use the "bucket fill" paint tool on any part of the maze to automatically highlight and visually "separate" that half from the other half of the maze.

Now can we use THIS property to automatically solve a maze? make the WALLS of the MAZE themselves out of transparent TUBES and fill THEM with dyed water? An then the solved maze is simply the path that always has dyed walls on one side and transparent walls on the other. Not sure what the mathematical proof for this will look like but sounds nearly as good as the original "water can solve a maze" proof?

Most maze solving algorithms don't really interact with the maze in that way. You generally act on cells/spaces and whether or not the adjacent cells are connected or blocked.

To use this property on a maze you'd have to traverse the whole maze using the typical cell adjacency, reconstruct it in a format that lets you bucket fill the walls, do that, and then also construct an algorithm which acts using the different colored walls. It only really works for a person interacting with a maze in a format where they can bring it into a picture editor.

> all mazes being two pieces

This is true for mazes with only one path from start to end. Each additional path necessitates a separate piece (path permutations nonwithstanding)

He says that in the video...

> mazes with only one path from start to end

One of my favourite bits of trivia: it is this property (being "unicursal") which leads to a maze being more specifically characterized as a labyrinth.

That's interesting, but it's a weird definition. In the myth of the Minotaur, the labyrinth Theseus is trapped in surely must have branches (or he wouldn't need a ball of thread), so it doesn't fit this definition.

Wikipedia[1] also notes this contradiction:

> Although early Cretan coins occasionally exhibit branching (multicursal) patterns, the single-path (unicursal) seven-course "Classical" design without branching or dead ends became associated with the Labyrinth on coins as early as 430 BC, and similar non-branching patterns became widely used as visual representations of the Labyrinth – even though both logic and literary descriptions make it clear that the Minotaur was trapped in a complex branching maze.

[1] https://en.wikipedia.org/wiki/Labyrinth

You could say the English language is...

Puts on sunglasses

A-maze-ing.

This is a consequence of max flow/min cut duality if I recall correctly.

This reminds me of trying to imagine a "Flatland" creature's biology; you can't really have one with a digestive tract.

You could have, the creature would just need a pair of zippers that unzip and zip the digestive tract as materials pass through, a bit like RNA polymerase unwinds and rewinds a strand of DNA. The zipper's teeth could act as conduits for the nervous and circulatory systems.

Did you see this by any chance? https://twitter.com/matthen2/status/1642236406465454082?s=46...

>Also makes me wonder what a proof would look like.

I think you need to be very careful in how you define a maze, lest you run the risk of rediscovering the difficulties involved with the Jordan Curve Theorem.

If you are using a gas rather than a liquid, it is even simpler. Just set a high pressure at the beginning and a low pressure at the end. The gas will automatically follow the steepest part of the pressure gradient.

The static solution can be calculated by solving the Poisson equation. In [1] you can see a small implementation of the idea.

[1] https://simulationcorner.net/maze/

Some if Buls Berglund's recent videos about waves in mazes made me realize this.

Funnily enough he uploaded a video two hours ago that shows what it looks like.

https://youtu.be/lBLlYmM6tjU

AFAIK this would also work with an incompressible fluid like water if you started the maze fully filled than add a sink at the exit and a source at the entrance. You wouldn't have any bubbles in that case and the current would flow along the solution.

It would be interesting to see what would happen to a fully filled maze if, once you got a steady continuous flow at the entrance and exit, you injected some dye into the water at the maze entrance.

It would have been even more interesting if this was not in the linked video!

Sorry, I didn't explain myself well enough. I mean start with the maze completely filled with water such that there's no pockets of air left, and water pressure is sufficient for water to race through continuously. Then introducing a distinct dye. The difference would be that it would have far less turbulence from splashing/pooling.

This reminds me of Collaborative Diffusion https://en.wikipedia.org/wiki/Collaborative_diffusion

A classic example is programming the ghosts in pacman to trap the player, which seems to require a sophisticated, collaborative strategy. Instead, a much simpler solution is to make a "pacman smell" diffuse through the maze:

- The cell containing pacman has its "smell" clamped to 1

- Cells containing walls and ghosts have their "smell" clamped to 0

- The "smell" of an empty cell is the average of its neighbours

This way, dumb hill-climbing will move the ghosts along the fastest route to the player. "Collaborative" behaviour emerges from the "smell" being clamped to 0 by ghosts: if a route to the player is already blocked-off by a ghost, those behind will not get any "smell" from that direction, and will take other routes instead; effectively cutting-off all of the escape routes. (I implemented this in Pygame many years ago, and it was no fun to play, since the ghosts were way too smart!)

I never knew there was a proper term for this technique! In the roguelike development community, these are known as "Dijkstra maps", and people use them for all sorts of things. [1] One of the coolest tricks the article describes is the idea of constructing several different Dijkstra maps for a particular game map, and then multiplying them together under certain circumstances to get a net weight for each tile.

1: http://www.roguebasin.com/index.php/The_Incredible_Power_of_...

Very nice.

I think that the explanation given for why the water stops flowing [1] is wrong. It has likely less to do with the surface tension "on the lip" (see video) and more with the fact that that all air bubbles in the maze become pressurized and their cumulative pressure is enough to push back on the water trying to get into the maze and prevent it from flowing in.

I do agree though that it's a rather unexpected behavior.

[1] https://www.youtube.com/watch?v=81ebWToAnvA&t=370

It shouldn't be, because every bit of upwards pressure towards the exit is compensated by the same amount of downwards pressure on the path before. I'm surprised there is that much static resistance in the maze.

So it's basically A* with higher scores when going towards gravity, very cool.

Another physics problem analogue I really like is the problem of fastest travel from point A to point B when you have to cross a river. One approach to solve is is to treat it as a minimization problem by writing down everything, another one is to realize light beams have already solved this problem for you, and the problem becomes much simpler when your river entry angle α and swimming angle β have to satisfy (sin α)/v_walking = (sin β)/v_swimming and the fastest path is the one which just happens to satisfy this angle constraint

Assuming the heuristic follows triangle inequality, then it is A*.

animals like ants and dogs intuitively "solve" the equation too

> [2:39] ... Actually a maze becomes very easy to solve if you colour the two parts separately.

Breezing through that example like he didn't just blow my mind, wow. It makes so much intuitive sense.

Unless you are the maze constructor, coloring the maze pieces is at least as hard as solving it.

If you color it the way he describes solving the maze (by keeping one hand on the wall the whole time), then solving it and coloring it should be the same operation, yes? Because if you haven't touched part of that wall yet, then you aren't at the exit. And anything you haven't touched is part of a different piece.

This reminds me of this classic paper [1] "Maze Solving by Chemotactic Droplets". Oil droplets sense a chemical gradient as variation of interfacial tension, using what is commonly known as the "Tears of wine", or Marangoni effect, to propel themselves to the exit.

[1] https://pubs.acs.org/doi/full/10.1021/ja9076793

You should check how bacterias navigate through mazes. They can navigate through complex environments (chemotaxis and swarming). Bacteria can sense gradients of chemicals and adjust their movements accordingly to find the optimal path through a maze. The ability of bacteria to communicate and coordinate their movements to solve more complex mazes is hella impressive.

Sounds like more known name for it is "ant colony optimisation". Lots of computer science algorithms and structures are based on that principle

https://en.wikipedia.org/wiki/Ant_colony_optimization_algori...

For sufficiently large mazes it must get harder to push the water through. Water can't solve a Tesla valve. (https://en.wikipedia.org/wiki/Tesla_valve)

Yes, water can solve a Tesla valve:

> Steady flow experiments, including with the original design, however, show smaller ratios of the two resistances* in the range of 2 to 4.[6] It has also been shown that the device works better with pulsatile flows.[6]

*Ratio of resistance to water flowing "forward" vs. "backward" through the Tesla valve.

Though if you stretch things far enough - say, a thick layer of "waterproof" clay - your statement is correct for most purposes.

Rectifying diodes also have limitations for how much reverse voltage they can block. When I fiddled with circuitry I was surprised how low that could be for cheap rectifiers. It sank some of my naive designs.

Real circuits can have transistors or resettable fuses to handle out-of-spec situations and shut down.

I've often wondered, is this vaguely analogous to the quantum wave function and what's happening when particles try all possible paths?

https://en.wikipedia.org/wiki/De_Broglie%E2%80%93Bohm_theory

https://en.wikipedia.org/wiki/Hydrodynamic_quantum_analogs

Thank you

Maze solving by gravity assisted literal flood-fill [1]

https://en.wikipedia.org/wiki/Flood_fill

Inspired by Steve mould, I had some fun doing something quite similar a while ago experimenting with Bell Siphon, 3d printing, and numerical simulation. If this interest someone here I just pushed it to Thingiverse now https://www.thingiverse.com/thing:5948252 https://www.youtube.com/watch?v=S748mcM0MSg

As Steve showed, it's particularly important to take into account both air and water.

There is still some work needed to make it Sim2Real and optimize the design automatically.

The ambitious end-goal, is to have a cascading siphon (not so dissimilar than the flushing mechanism in your toilet) that can reliably be switched on by a single additional drop of water. (Currently I achieve this goal using a Shishi Odoshi fountain to arm the siphon very reliably but it still has one moving part, but that's a story for another day).

Quite fun, messy and time-consuming rabbit-hole to go down to, cause you need to get the details right.

> 404 you’ve reached the end of the thingiverse

Sorry republished it, should be OK now

This reminds me of The Dumbest Way To Solve A Maze [1] by Numberphile - similar approach. Posted on HN before [2]

[1] https://www.youtube.com/watch?v=BvwgdrC8vlE

[2] https://news.ycombinator.com/item?id=32799511

The practical application of this fluid maze is the automatic transmission's valve body:

https://youtube.com/v/u4kM67f_P3A?t=23

Tangent: Change your transmission fluid. Lifetime transmission fluid spec is the lifetime of your vehicle's powertrain warranty.

Now do it with a superfluid [1].

[1] https://en.m.wikipedia.org/wiki/Superfluidity

You can also solve a maze with Cellular Automata: https://github.com/philtomson/CellularAutomata#you-can-solve...

Also have a look at this interactive simulation: https://app.physion.net/scenes/water-maze-solver

Would this work as well if the maze had horizontal path instead vertical, when gravity and bottom-up air pressure wouldn't be helping the water find the path? I think it would look more like the one from Bergman Joe.

Not sure if mazes are np complete but if so could we map other problems into maze designs and the water can solve problems for us?

I thought we decided to use electricity and silicon mazes instead?

But there were attempts to use water too, e.g. MONIAC: https://en.m.wikipedia.org/wiki/MONIAC

If you extend the definition of the maze a bit, aren't all circuits mazes?

But then, you can keep extending it and say that everything is a computer and also a maze.

Anyway, the brain gymnastics is a lot of fun, at least for me.

They are not NP at all. A perfect maze (with one solution) as a connectivity graph is a tree. Finding the path through a tree can be done by DFS in linear O(N) time.

all P problems are in NP \pedantic

Simple video, yet fascinating

What happens if we use a Tesla valve for a maze?

can this work with light? how would it be different. just trying to imagine a light solving a maze

Light goes in a straight line an reflects. If the walls are diffuse, a tiny amount of light is always going to make it out at some point, but what does that have to do with this?

A computer is a computer, and our universe is a computer. So, it's possible we're living in a simulation but not one that was intentionally constructed by a higher life form, but rather, a simulation that emerged from nature (e.g. electrons whizzing along the surface of silica rock on a desolate planet). Our universe could recursively be computers all the way down.

A computer is always imperfect though, compared to the universe, which is very stable and extremely perfect to the last detail. I don't think we can even compare since the scale and the domain is so vast.

If a tree is standing in a forest, but no one is there to watch it. Does the tree get rendered every frame?

Yes, it does.

No, it doesn't.

Depends on the programmer.

Depends on the hardware being targeted.

Depends on the deadline

If it is a simulation, what is it simulating? There would have to be a "real" reference to compare against?

I don't think a simulation needs to simulate anything real. Eg. if I have a program that runs Conway's game of life, that would be also be a simulation, but there's nothing "real" it references against.

In other words, the universe simulating ours might work completely differently, and some beings there are just testing how different laws of physics (i.e. ours) work out.

The definition of simulation is:

imitation of a situation or process. "simulation of blood flowing through arteries and veins"

I love the game of life but I don't really consider it a simulation, it's a toy that with the right parameters could simulate something.

some beings there are just testing how different laws of physics (i.e. ours) work out

Or there is a practical use like energy extraction. Or they live (if that even applies) in a universe that generates what our closest concepts of are e.g. time and energy, and they have to spend them massively in simulations to survive. Or their laws of nature tend to overcommunicate (dilute) them into a single being, so they simulate everything we see for islands of “themselves” to remain distinct. They split themselves endlessly with perception because that’s the trick in their situation.

One of my nightmares is to wake up from this and realize you woken up from a mild depression into a horror of a true existence, and this isn’t even a final level. Makes sense, since if god is infinite, why shouldn’t he be infinitely suffering. Why would he (you) create all this if not to escape from null-reality.

If I launch a random cellular automaton there isn't as much a real reference I'm trying to compare it to as just seeing what cool things it does. Maybe I can coax it into something comparable if I want, e.g. pick rule 110 and set it up to run ChatGPT and write this comment, but the only "realness" requirement is it follow what logic allows not it has a real reference it's supposed to emulate and be compared to.

I wouldn't call that a simulation though, it's just a looping process with rules. A simulation implies imitation, so if it's not imitating anything is it a simulation?

It would be simulating causality. If you had a water maze that was large enough - with enough gates, switches, and circuits - then it would be turing complete and simulate its own universe. But the more likely scenario is that it doesn't compile into anything. The point is, given enough time, and space (it's going to be one large maze) it's capable of applying the same rules of causality, and calculating the same math across all universes. That said, if your quarks and neutrinos blip in and out of existence, you can blame it on the turbulent water maze(s) higher in our simulation stack. :)

Factorio running inside minecraft running inside roblox.

Turtles all the way down...

The simulation theory simply postpones the hard problem of consciousness. It's like a magician trick, pulling wool over the eyes, moving your attention away from the real problem long enough, so that you stop thinking about it.

Even without consciousness, the existence of the universe faces the same causality issues.

All the talk of simulations, multiverses, etc is IMO expending a lot of effort to avoid facing the possibility of a Creator - the “uncaused cause” or something existing outside of time and space.

The presence of a creator does not change anything. Who created the creator?

That’s the point - something completely beyond our notions of causality or the arrow of time has to be at the foundation of it.

The creator remains without a creation. The notion that most schools of thought have is, the creator is unborn and born at the same time and has always existed. Creator does not have a point of creation, not even death because those rules only apply to the materialistic universe.

That's quite a cop out. Excuse me if I don't take your word for it.

It isn't a cop out because the creator in the conclusion of this type of argument (e.g. Aquinas' third way) is not just another contingent being like other things, but rather a being whose existence is necessary in itself.

> Aquinas' third way

Thank you! This was very interesting to read about. Learned something new today :D

How so? By “hard problem” do you mean defining what consciousness is?

"the hard problem" (of consicousness) is a well known term in philosophy, science, metaphysics, just look it up.

The simulation theory is literally a species of creationism, which I find quite amusing.

>it's possible we're living in a simulation but not one that was intentionally constructed by a higher life form,

what about a simulation constructed by us. the conceit of The Invisibles comics.

Reply on news.ycombinator.com