Hard fractals · curves · bits

Dragon curve

Fold a strip of paper in half again and again, open it to right angles, and a dragon unfolds.

Write dragon(order). Return the 2 ** order + 1 corner points [x, y] of a dragon curve made of 2 ** order unit segments. Coordinates are on screen: x right, y down. Call show(points) after each point is added so the dragon grows on the stage.

Start at [0, 0] facing right, heading (1, 0), and take the first segment to [1, 0]. Before segment i + 1, for i from 1 to 2 ** order - 1, turn: divide i by 2 until it is odd, call that k; if k % 4 === 1 turn right, otherwise turn left. Then step one unit along the new heading.

On screen, turning right from heading (dx, dy) gives (-dy, dx), and turning left gives (dy, -dx). Facing right and turning right, you face down.

Example: dragon(2). Segment 1 goes to [1, 0]. i = 1 is odd with 1 % 4 === 1, so turn right to face down: [1, 1]. i = 2 halves to 1, right again, face left: [0, 1]. i = 3 has 3 % 4 === 3, turn left to face down: [0, 2]. Result: [[0, 0], [1, 0], [1, 1], [0, 1], [0, 2]].

Tests you can see

dragon(2)[[0,0],[1,0],[1,1],[0,1],[0,2]]
dragon(4)[[0,0],[1,0],[1,1],[0,1],[0,2],[-1,2],[-1,1],[-2,1],[-2,2],[-3,2],[-3,1],[-2,1],[-2,0],[-3,0],[-3,-1],[-4,-1],[-4,0]]
dragon(9)[[0,0],[1,0],[1,1],[0,1],[0,2],[-1,2],[-1,1],[-2,1],[-2,2],[-3,2],[-3,1],[-2,1],[-2,0],[-3,0],[-3,-1],[-4,-1],[-4,0],[-5,0],[-5,-1],[-4,-1],[-4,-2],[-3,-2],[-3,-1],[-2,-1],[-2,-2],[-3,-2],[-3,-3],[-2,-3],[-2,-4],[-3,-4],[-3,-5],[-4,-5],[-4,-4],[-5,-4],[-5,-5],[-4,-5],[-4,-6],[-3,-6],[-3,-5],[-2,-5],[-2,-6],[-1,-6],[-1,-5],[-2,-5],[-2,-4],[-1,-4],[-1,-3],[0,-3],[0,-4],[-1,-4],[-1,-5],[0,-5],[0,-6],[1,-6],[1,-5],[2,-5],[2,-6],[1,-6],[1,-7],[2,-7],[2,-8],[1,-8],[1,-9],[0,-9],[0,-8],[-1,-8],[-1,-9],[0,-9],[0,-10],[1,-10],[1,-9],[2,-9],[2,-10],[3,-10],[3,-9],[2,-9],[2,-8],[3,-8],[3,-7],[4,-7],[4,-8],[5,-8],[5,-7],[4,-7],[4,-6],[3,-6],[3,-7],[2,-7],[2,-6],[3,-6],[3,-5],[2,-5],[2,-4],[3,-4],[3,-3],[4,-3],[4,-4],[3,-4],[3,-5],[4,-5],[4,-6],[5,-6],[5,-5],[6,-5],[6,-6],[7,-6],[7,-5],[6,-5],[6,-4],[7,-4],[7,-3],[8,-3],[8,-4],[7,-4],[7,-5],[8,-5],[8,-6],[9,-6],[9,-5],[10,-5],[10,-6],[9,-6],[9,-7],[10,-7],[10,-8],[9,-8],[9,-9],[8,-9],[8,-8],[7,-8],[7,-9],[8,-9],[8,-10],[9,-10],[9,-9],[10,-9],[10,-10],[11,-10],[11,-9],[10,-9],[10,-8],[11,-8],[11,-7],[12,-7],[12,-8],[13,-8],[13,-7],[12,-7],[12,-6],[11,-6],[11,-7],[10,-7],[10,-6],[11,-6],[11,-5],[10,-5],[10,-4],[11,-4],[11,-3],[12,-3],[12,-4],[13,-4],[13,-3],[12,-3],[12,-2],[11,-2],[11,-3],[10,-3],[10,-2],[9,-2],[9,-3],[10,-3],[10,-4],[9,-4],[9,-5],[8,-5],[8,-4],[9,-4],[9,-3],[8,-3],[8,-2],[7,-2],[7,-3],[6,-3],[6,-2],[7,-2],[7,-1],[6,-1],[6,0],[7,0],[7,1],[8,1],[8,0],[7,0],[7,-1],[8,-1],[8,-2],[9,-2],[9,-1],[10,-1],[10,-2],[11,-2],[11,-1],[10,-1],[10,0],[11,0],[11,1],[12,1],[12,0],[13,0],[13,1],[12,1],[12,2],[11,2],[11,1],[10,1],[10,2],[11,2],[11,3],[10,3],[10,4],[11,4],[11,5],[12,5],[12,4],[11,4],[11,3],[12,3],[12,2],[13,2],[13,3],[14,3],[14,2],[15,2],[15,3],[14,3],[14,4],[15,4],[15,5],[16,5],[16,4],[15,4],[15,3],[16,3],[16,2],[17,2],[17,3],[18,3],[18,2],[17,2],[17,1],[18,1],[18,0],[17,0],[17,-1],[16,-1],[16,0],[15,0],[15,-1],[16,-1],[16,-2],[17,-2],[17,-1],[18,-1],[18,-2],[19,-2],[19,-1],[18,-1],[18,0],[19,0],[19,1],[20,1],[20,0],[21,0],[21,1],[20,1],[20,2],[19,2],[19,1],[18,1],[18,2],[19,2],[19,3],[18,3],[18,4],[19,4],[19,5],[20,5],[20,4],[21,4],[21,5],[20,5],[20,6],[19,6],[19,5],[18,5],[18,6],[17,6],[17,5],[18,5],[18,4],[17,4],[17,3],[16,3],[16,4],[17,4],[17,5],[16,5],[16,6],[15,6],[15,5],[14,5],[14,6],[15,6],[15,7],[14,7],[14,8],[15,8],[15,9],[16,9],[16,8],[17,8],[17,9],[16,9],[16,10],[15,10],[15,9],[14,9],[14,10],[13,10],[13,9],[14,9],[14,8],[13,8],[13,7],[12,7],[12,8],[11,8],[11,7],[12,7],[12,6],[13,6],[13,7],[14,7],[14,6],[13,6],[13,5],[14,5],[14,4],[13,4],[13,3],[12,3],[12,4],[13,4],[13,5],[12,5],[12,6],[11,6],[11,5],[10,5],[10,6],[9,6],[9,5],[10,5],[10,4],[9,4],[9,3],[8,3],[8,4],[9,4],[9,5],[8,5],[8,6],[7,6],[7,5],[6,5],[6,6],[7,6],[7,7],[6,7],[6,8],[7,8],[7,9],[8,9],[8,8],[7,8],[7,7],[8,7],[8,6],[9,6],[9,7],[10,7],[10,6],[11,6],[11,7],[10,7],[10,8],[11,8],[11,9],[12,9],[12,8],[13,8],[13,9],[12,9],[12,10],[11,10],[11,9],[10,9],[10,10],[11,10],[11,11],[10,11],[10,12],[11,12],[11,13],[12,13],[12,12],[13,12],[13,13],[12,13],[12,14],[11,14],[11,13],[10,13],[10,14],[9,14],[9,13],[10,13],[10,12],[9,12],[9,11],[8,11],[8,12],[9,12],[9,13],[8,13],[8,14],[7,14],[7,13],[6,13],[6,14],[7,14],[7,15],[6,15],[6,16],[7,16],[7,17],[8,17],[8,16],[7,16],[7,15],[8,15],[8,14],[9,14],[9,15],[10,15],[10,14],[11,14],[11,15],[10,15],[10,16],[11,16],[11,17],[12,17],[12,16],[13,16],[13,17],[12,17],[12,18],[11,18],[11,17],[10,17],[10,18],[11,18],[11,19],[10,19],[10,20],[11,20],[11,21],[12,21],[12,20],[11,20],[11,19],[12,19],[12,18],[13,18],[13,19],[14,19],[14,18],[15,18],[15,19],[14,19],[14,20],[15,20],[15,21],[16,21],[16,20],[15,20],[15,19],[16,19],[16,18],[17,18],[17,19],[18,19],[18,18],[17,18],[17,17],[18,17],[18,16],[17,16],[17,15],[16,15],[16,16]]

More tests are hidden. The server runs them all before a time counts.

Call show() while your code works and the run plays back here.

javascriptdragon()

function dragon(order) {
  const points = [[0, 0], [1, 0]];
  let dx = 1;
  let dy = 0;
  // turn, then step, for each remaining segment
  return points;
}

function dragon(order) {
  const points = [[0, 0], [1, 0]];
  let dx = 1;
  let dy = 0;
  // turn, then step, for each remaining segment
  return points;
}

Tab indents · Cmd/Ctrl+Enter runs