Deluge

[jonik555]

Very hard for me... I did it at 4th try. After each try I was so mad, that I left it for week and didnt think about it Nice challenge!!!!
my code is:

Code: Select all

4444***0> 0<3+0<1+> 0<2+0<> 00<1+<1->      
0<<<1-0^44*1v1^/*-35*:78*5-?0<<<1-<0:6?84*2+g01-0<<<1->0<<<1-0<1+<>0<1+0^<1+1v>  
0<<<1+0^44*1v1^/*-0  :78*5-?0<<<1+<0:6?84*2+g01-0<<<1+>0<<<1+0<1+<>0<1+0^<1+1v>      
0<<<44*    :1+677*+?0<<<44*-<0:4?58*g01-0<<<44*->0<<<44*-0<1+<>0<1+0^<1+1v>           
0<<<6425***:1-677*+?0<<<44*+<0:4?58*g01-0<<<44*+>0<<<44*+0<1+<>0<1+0^<1+1v>                 
10<<<>4444***0> 0<<0<1+<1-:1+4?10>!0<<1+0<>257*+c

(without newlines ofcourse )

How did You solved it?

[Karian]

I can't directly find my code, since it has been a while I did any HVM challenges. I'm just having more fun with Superhack challenges these days.

The main idea was having one function with 2 parameters (coordinates) passed that checks the value at it's current location. If it was black, it ends, if it is white, change it to black, and call the same funtion for all 4 squares touching your current coordinate.

In the final result, for making the cycle limit, I had actually 4 functions, so that I could exclude the direction I was coming from in the check. It was a bit more code, but it made the execution time a lot smaller.

[lifthrasiir]

My solution:

Code: Select all

005c!           calls the recursive procedure at (0,0)
0^0:1^35*:*1-   pushes non-zero iff 0 <= x <= 15
2^0:3^35*:*1-   pushes non-zero iff 0 <= y <= 15
*35*?           if one or both is zero, then it is out of bound
1^1^44**+0^     pushes a memory location for current position (twice)
<4?d            if it is empty then skip to the recursion part;
                otherwise remove a spare memory location from the stack
dd$             cleans up the stack and return
                (this code is also used by 35*? above)
11v>            now set the memory location to 1 (i.e. non-empty) and
1^1^1+5c        recursively search for four directions
1^1^1-5c
1^1+1^5c
1v1-1v5c$

Personally I found "{v}{min}:{v}{max}:*" to be handy; it pushes -1 when min < v < max, 0 when v is either min or max, and 1 otherwise.

[chiefrocker]

Nice idea, that efficient bounds check! I did three versions:

The first version copied the 16x16 image into a 18x18 image with borders, so I did not need bound checking. I then could then implement flood fill with 1d indices, using appropriate strides for the 2d neighbors. That version worked with the example image, but was not accepted as valid solution (potentially using too many cycles; it was >44k for the example).

Code: Select all

28*28**36*36*1^28*1+*3^3^+4^1^:136*+?1-11^3^+>11^>056*-gdd28*1+3^3^28*1+*+4^1^:54*?3^-11^3^+>11^>156*-g1vd2^1++28*0^69*?1-0^28**2^2^5^*+35*1-2^1^+<2^2^+>0^0:1-139*-?ddd379*-gd3^3^3^*+6>6<7>10>03^-1>01-2>2^3>59*9*  c259*+9*   c899*+  ?5789*+*c0^<7?d158*-g11^>0^0<+59*9* c0^1<+59*9*    c0^2<+59*9*   c0^3<+59*9*    cd034*9*-g2^2^1++28*0^69*?1-0^4^*2^+28*2^*35*1-2^1^+<2^2^+>0^0:1-139*-?ddd379*-gd!7<1-0^7><$0^<3?d9g7<>7<1+7>$7<6<-$

The second try was a reimplementation in which I maintained 2d coordinate pairs on the stack, used -2 as "end of stack" marker value, and performed bounds checking on the top values at the beginning of the main loop. The code was fairly short, but needed >52k cycles on the example image. Many of my refactoring tries in fact worsened that, so I eventually gave up.

Code: Select all

02-000^0:1+2^0:1+*136*+4*?0^28*:1+2^28*:1++6?dd77*g1^1^28**+0^<9?ddd249+*g11v>1+1^1^2-1^1-1^1+1^2+1^2gdd0^02-:1-249+9*-?!

Finally, I came to the conclusion that I should allow for a longer code, but using fewer cycles, and I did the bounds checking after drawing a pixel, before putting neighbors on the stack:

Code: Select all

02-001^1^28**+0^<49+?ddd2189+8*+*g11v>0^1:1+156*+6*?0^27*:1-2259*+*?1^1:1+35*4*?1^27*:1-249+*?1-1^1^2+1^1-1^1-1^2+1^28*g1-1^1^2+1^1-1^1-28*g1-1^1^2+1^1+1^1-25*7*g1^1:1+2237*+*?1^27*:1-54*?1-1^1-1^1+1^2+1^25*g1-1^1-1^1+25*g1-1^1+1^1+25*7*g1^1:1+2237*+*?1^27*:1-54*?1+1^1-1^1-1^2+1^25*g1+1^1-1^1-25*g1+1^1+1^1-0^02-:1-158*8*-?!%

[/i]