The Green Dot Square Puzzle

I found this puzzle on Quora and decided to solve it using NodeBox...

Given twelve dots in a cross pattern the puzzle is to find all possible squares where each corner of the square lands on a separate dot.

Here is the Quora link: https://www.quora.com/Can-you-solve-the-green-dot-square-logic-puzzle

To solve the puzzle I found all 495 possible ways of choosing 4 dots from a set of 12 and counted the number of unique side lengths of the resulting quadrilaterals. Whenever that count was one (all sides equal) I found another square. I used more nodes drawing the solutions than I did finding them (see screenshot).

Writing the Nodebox network was a more interesting puzzle than the puzzle itself. There were two challenges.

First, how do you list all possible combinations for (N choose K)? Most algorithms in other languages use recursion, but Nodebox doesn't do recursion. If you know K you can hardcode nested for loops, but NodeBox doesn't do loops either. I finally came up with a simple solution that could be easily adapted to other cases using a subnetwork called AddCombo.

For N choose K, create a list of integers from 0 to N-K+1. Feed that into the first AddCombo node and set "Upper Bound" to N-K+2. Feed that into another AddCombo with Upper Bound set to N-K+3. Repeat until the final Upper Bound = N. The final AddCombo box will generate a list of comma-separated strings with every possible combination.

The other challenge was finding the sides of the resulting quadrilaterals (and later drawing the squares). This is trickier than it might seem at first because you don't know what order the points are in so you can't just connect them. With 4 points there are 6 possible connections (4 sides plus 2 diagonals). Fortunately, the diagonals will always be longer than the sides so you can use that information to cull the diagonals.

Screenshot and NodeBox network attached. Enjoy!

This is super-cool. Also, it looks really good (both the network and the view :-)

Thanks, Frederik!

I sure wish NodeBox could do recursion. My "AddCombo" nodes come tantalizingly close, but I still have to manually add K-1 nodes myself.

If you look at my "Conway's Game of Life" network, you will see that I managed some recursion by writing each generation to the hard disk (using a custom node) and then reading what I wrote. This was a kludgey way to sneak some state into NodeBox's stateless world. I think you once talked about a "monad" to hold a speck of state to support recursion in a similar, less kludgey way.

How hard would it be to add recursion to NodeBox?

John

In NodeBox Live, we now have stateLoad / stateSave nodes that — as the names suggest — load and save state. We use these for feedback networks, useful to simulate particles, for example.

Would that help for recursion?

Frederik,

Almost, but not quite.

A simple example of recursion is the factorial function:

function factorial ( n ) :
if n < 2 then return 1
else return n * factorial ( n - 1 )

I have attached a mockup of how such a function might be implemented in NodeBox (see screenshot).

The screenshot shows a subnetwork called factorial which takes a single (integer) parameter n and returns n! The compare node tests whether n < 2. If true (1), the switch is set to 1. If false (0), the switch is set to n * me ( n-1 ).

This is all perfectly normal except for the node called "me". Me would be a special node that could only be used inside another subnetwork. Me would simply stand in for its parent. It would have the same number of parameters as its parent (sprouting new parameter ports automatically whenever its parent was altered).

If you could provide us with this magic "me" node, NodeBox would then be able to do recursion and a whole new continent of possibilities would open up.

stateLoad and stateSave, if I understand them correctly, would at least make a factorial function possible, but I believe that in order to use them you would have to hit play.

You could feed a frame node and an n value into a subnetwork which would then check to see whether frame > n. If so it would return the saved value. Otherwise it would retrieve the state from the previous frame, multiply that by the current frame value, and store the result in the state.

This would sort of work, but you'd have to "crank" it by hitting play until the recursion was complete. I don't want to have to hit play just to calculate a factorial.

Hard hard would it be to add a "me" node to NodeBox?

great example John, so you make a list with every 4 elements combination, then check lengths... a cross node would be nice to help make the list

about recursion, for string replacement it would be handy to be able to work with lists too (and concatenate could have 7 inputs like combine btw)

Hi Frederik,

Are you still there?

I am curious what you think of my proposal for a "me" node. Is it feasible?

I am working on another project right now that really needs recursion.

John