User:Dan Bron/Temp/SkinCount

From J Wiki
Jump to: navigation, search

Work in progress --- inductive vs deductive

How many layers does an onion have?

For the sake of my fragile ego I decided to improve the time and space performance of my onion solution.

   NB.  The code below was created by the contributions to
   NB.  and collaboration on the JForums.
   onion0    =: [: ({.&.> #~ 0 ~: */@:$&>) |.@:|:@:}.&.>^:a: @: < @: i.
   onion1    =: +/\@(,@(] {. |:@((1 0 + i.@-@|.)@[)) # +:@] $ (, -)@(1 , {:@[)) {.
   s         =: 1 : '| $ /:@;@u f.'

   spiral    =: onion0 s
   involute  =: onion1 s

The problem was harder than I thought. The fundamental trouble spiral is that it is structural, rather than mathematical. That is, involute invents (or defines) onion order, whereas spiral discovers it. In other words: involute is deductive' (__it tells the data__ how to behave), and spiral is inductive (__the data tells is__ how to behave). This approach makes the solution easier to invent, understand, and maintain, and was more inline with the solutions to the zigzag puzzle, but at the cost of time and space (and, hence, my ego).

I doubt a structural solution can ever compete with a mathematical one (it uses boxes, it's contains a lot of redundant information, etc), but perhaps we can close the gap a bit. Examining spiral :

 0 [:  (                     ) (                      )@:  <@:i.
 1      {.&.> #~ 0 ~: */@:$&>   (                    )
 2                               |.@:|:@:}.&.> (    )
 3                                              ^:a:

Each line here represents a different action in spiral. In English, this algorithm might read something like "Grow an onion (line 0), peel layers (line 2) until there's nothing left (line 3), and sweep the floor (line 1)."


Two things make this algorithm slow. First, the boxing (represented by the < >s in the code). This is fundamental to a structural solution in

Lines 2 3 are the heart of the solution.

The heart of the structural solution could be read as "Here's an ontion" One obvious place to start is the ^:a:, which could be read as "until you're done". Well, clearly, the size (and shape) of the onion holds some relation to the nu

The problem was harder than I thought it was.

I doubt it'll ever compete with the mathematical solutions, but improving it Since it's structural rather than definitional (its' inductive rather tit discovers rather than defines