Can water solve a maze? [video] • Hacker News Board

Re: Can water solve a maze? [video]

#91

Post by hinkley » Mon, Apr 03, 2023, 3:58 PM UTC

lupire wrote: post #70

DavidPiper wrote: post #16

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

Re: Can water solve a maze? [video]

#92

Post by lazyant » Mon, Apr 03, 2023, 4:09 PM UTC

_v7gu wrote: post #35

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

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

Re: Can water solve a maze? [video]

#93

Post by pjsg » Mon, Apr 03, 2023, 4:10 PM UTC

mnw21cam wrote: post #20

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. T…

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.

Re: Can water solve a maze? [video]

#94

Post by hinkley » Mon, Apr 03, 2023, 4:12 PM UTC

bell-cot wrote: post #32

OscarCunningham wrote: post #3

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

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.

Re: Can water solve a maze? [video]

#95

Post by bootsmann » Mon, Apr 03, 2023, 4:18 PM UTC

freetime2 wrote: post #15

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.

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

Re: Can water solve a maze? [video]

#96

Post by agilob » Mon, Apr 03, 2023, 4:24 PM UTC

noobcoder wrote: post #85

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

Re: Can water solve a maze? [video]

#97

Post by agilob » Mon, Apr 03, 2023, 4:25 PM UTC

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.

Re: Can water solve a maze? [video]

#98

Post by kurthr » Mon, Apr 03, 2023, 4:28 PM UTC

pjsg wrote: post #93

mnw21cam wrote: post #20

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. T…

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

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.

Re: Can water solve a maze? [video]

#99

Post by scarmig » Mon, Apr 03, 2023, 4:40 PM UTC

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

Re: Can water solve a maze? [video]

#100

Post by chriswarbo » Mon, Apr 03, 2023, 4:44 PM UTC

s-macke wrote: post #4

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/

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