# The Image of the Dragon

I saw a cool gif of the twin dragon curve made from a square, and wondered what would happen if we started from another base image. So I wrote a program to do this. It's so cool that I thought it would be fun to do it as a challenge.

You will take in a square image with an edge length that is a power of 2 (greater than 4).

To make this image you should start by dividing your image into 4 vertical bands of equal size and shifting adjacent bands one 8th of the size of the image in opposite directions (shifted bands should wrap around to the other side). You should then repeat this process each time splitting the image into twice as many divisions and shifting by half as far as the previous time. Each iteration you should alternate between vertical and horizontal shifts. You should iterate until the shift requires you to shift by a fractional number of pixels (this will always be 1/2) at which point you are done.

When shifting vertically odd numbered bands from the left (zero-indexed) should shift down while even shift up. When shifting horizontally odd numbered bands from the top should shift left while even numbered bands should shift right.

You need only output/display the end result of the transformation, not all the intermediate steps like in the gif.

This is so the goal is to minimize the length of you source code as measured in bytes.

## Worked through example

I will work through the cat gif shown at the top of the page frame by frame.

Here is the starting image: This image is 512 by 512 pixels. We will break it in 4 bands to start and shift each band by 1/8 the image size (64 pixels) vertically. We will now divide it into twice as many bands (8 bands) and shift it half as far as last time (32 pixels). This time we will shift horizontally. We will now shift vertically again this time splitting into 16 bands and shifting each band by 16 pixels. 32 bands, 8 pixels, horizontal shift 64 bands, 4 pixels, vertical shift. 128 bands, 2 pixels, horizontal shift. 256 bands, 1 pixel, vertical shift. Since the next shift would require us to move each band by half a pixel we will stop at this point and output the result.

## Test cases

I have a working script that can make these images so I thought I would let you guys choose the images for the test cases. So if you have a square image that is a power of 2 wide that you would like to see become dragonified. Feel free to send it to me and I'll make it a test case.  You should also test on a plain white or solid black image so that you can determine whether or not pixels are disappearing or not.

• Apr 23 '17 at 20:11
• Image of the dragon? ahem Apr 23 '17 at 20:28
• related Apr 23 '17 at 23:44

# MATLAB, 237 bytes

function A=r(A);n=size(A,1);p=@(a,v)permute(a,[v,3]);k=n/8;v=1:2;while k>=1;b=mod(0:n-1,4*k)<2*k;x=find(b);y=find(~b);c=[k+1:n,1:k;n-k+1:n,1:n-k];A=p(A,v);c=c(3-v,:);A(x,:,:)=A(x,c(1,:),:);A(y,:,:)=A(y,c(2,:),:);A=p(A,v);k=k/2;v=3-v;end


Took a little bit of guess work as I did not understand the procedure from the specs, but with the help of the image it worked. # Python 2, 317313304 298

from PIL import Image
I=Image.open(input())
w,h=I.size
b,p,q,s=4,w/8,1,1
while p>1:o=I.copy();o.paste(I,[(w-p,0),(0,w-p)][q==1]);o.paste(I,[(p-w,0),(0,p-w)][q==1]);q*=-1;x=0;exec'o.paste(I.crop([(0,x,w,x+p*2),(x,0,x+p*2,w)][s%2]),[(q*p,x),(x,q*p)][s%2]);q*=-1;x+=p*2;'*b;p/=2;I=o;s+=1;b*=2
o.show()


# Mathematica, 177 bytes

It is slow and not fully golfed.

r=ImageRotate;r[#2,Pi/2(3-#)]&@@Nest[{#+1,ImageAssemble@MapIndexed[RotateLeft[#,(-1)^#2]&]@ImagePartition[r@#2,Reverse@d/2^{#,#-1}]}&@@#&,{3,#},Log2@Min[d=ImageDimensions@#]-2]&


This is Lena: This is Lena the Dragon: ## Haskell + hip, 256 bytes

import Graphics.Image
(d?s)w@(x,y)|k<-div s$2^d,k>0,(y,x)<-(d+1)?s$(y,x)=(mod(x+(-1)^(mod(div y k)2+d)*div k 2)s,y)|1>0=w
q::Image VS YCbCr Word8->IO()
q i=writeImageExact JPG[]"o"\$backpermute(dims i)(2?rows i)i


I lose a lot of bytes in this answer to weirdness going on in the hip library. Namely I have to use the Exact functions for some reason I can only imagine is a bug with the non-exact counter parts, and I have to add a type signature for q. I'd also prefer to display the image instead of writing but there is an issue with the native display being non-blocking and when I make it blocking the image is output in negative for some reason. Maybe fiddling with the input format would make this shorter, currently it takes a jpg image stored in a file called i and outputs to one called o.

# APL (dzaima/APL), 109 107 bytes

f←{x←⊃P5.size←⍵.sz⋄s←4⋄P5.setup←{0 0P5.G.img P5.img{r←x÷s×2÷x⍴(x÷s)⌿1¯1⋄2|2⍟s+←s:←⍵⌽⍨-r⋄⍉r⌽⍉⍵}⍣{s=x}⍵.mat}}


Try it online!

A dfn which takes an APLImg object as an argument, and displays the dragonized image.
• (x÷s×2)×x÷s×2÷