Developing an Algorithm to Draw Stars

Do this on

Our goal is to create a new function star, so that star 12, blue draws a blue twelve-pointed star.

Introduction to Functions

Here is the most important concept in all of programming:

Programs define their own functions

A function is a miniature program. In CoffeeScript, a function is written with an arrow -> typed as two symbols next to each other (the minus and the greater-than) like this:

(input) -> something to do

Writing and Naming Functions

A function that advances the turtle by ten times a distance is

(x) -> fd 10 * x

Name a function like any variable, using =.

scoot = (x) -> fd 10 * x

After the definition, we can write scoot 7 or scoot 5 + 2. In other words, scoot can be used just like predefined functions like fd or rt.

Making a star Function

Functions can be long. This code defines a star function using indented lines after the ->:

star = (n, k) ->    # define a function star with two inputs and code to follow:
  pen k             # use the chosen color.
  for [1..n]        # repeat the following n times:
    fd 100          # move forward.
    rt 2 * 360 / n  # turn right using a magic star formula.

speed 10            # draw fast!
star 7, red         # use our newly-defined function!


  1. Enter the program above that defines the star function, and save it as "star1". Some tips:
  2. Test out the star function with different numbers, and note the outcomes below:
Test Outcome Test Outcome
star 5, red  star 9, red 
star 6, red  star 10, red 
star 7, red  star 11, red 
star 8, red  star 12, red 

Debugging the Algorithm

There is a problem with star whenever we ask for an even number of points:

star = (n, k) ->
  pen k
  for [1..n]
    fd 100
    rt 2 * 360 / n

speed 10
star 8, red

What causes the bug?

The problem is in the "magic" formula 2 * 360 / n. To understand, read on.

The Geometry of Stars

Drawing a star is similar to drawing a regular polygon. After the turtle has gone all the way around all n corners, it will come back to where it started, facing the same direction it started.

The difference between a star and a polygon is its winding number: In a polygon, all the turns total up to 360° because each of the n turns is (360/n)°. So the turtle winds once around the center: its "winding number" is 1. In a star, the turtle turns total to a larger multiple of 360, such as 2×360, which gives it a winding number of 2.

If we change the "magic formula" to 3 * 360 / n, we will get a star with winding number 3. That experiment is shown below.

star = (n, k) ->
  pen k
  for [1..n]
    fd 100
    rt 3 * 360 / n

speed 10
star 8, red

The problem is this: if the winding number evenly divides the number of corners, we retrace old corners exactly. For example, when using the winding number 2 with 8 points, 2 divides 8, and we retrace the same 4 corners twice. The winding number 3 works better.

An Algorithm With an Answer: Picking a Winding Number

How do we pick a winding number for an n-pointed star? We can write an algorithm for that!

  1. To pick a winding number for a star with n points:
    1. Check every number c from 2 to n as follows:
      1. If c not a divisor of n:
        1. Then c is our answer.

Translated from words into CoffeeScript:

winding = (n) ->        # define a function named winding.
  for c in [2..n]       # vary c from 2 to n, starting at 2.
    if (n % c) isnt 0   # if c is not a divisor of n then:
      return c          # c is the answer.

write winding 8         # run our function and write the answer.

Here are tools that we used to write this algorithm in CoffeeScript:

for c in [2..n]  Control. Here c is a looping variable. When for is used with a looping variable, it repeats its block of code once for each value of in the range, or until a special command like return quits the loop.
if  Control. if condition runs the indented code only when the condition is true.
%  Arithmetic. The "modulo" arithmetic operator, written using the percent symbol x % y, calculates the remainder when x is divided by y. For example, 15 % 5 is 0 becuase 5 divides 15 exactly, but 15 % 4 is 3.
isnt  Arithmetic. x isnt y  tests if two values are unequal. For example, (n % c) isnt 0 tests if there is a nonzero remainder when n is divided by c.
return  Control. When inside a function, return answer ends the calculation.


  1. Enter the program above that defines the winding function, and save it as "winding". Remember:
  2. Test out the winding function with different numbers, and note the outcomes below:
Test Outcome Test Outcome
winding 5  winding 9 
winding 6  winding 10 
winding 7  winding 11 
winding 8  winding 12 

Using one Function inside Another

After we define winding, we can use it anywhere, including inside the star function. Here is how:

winding = (n) ->        # define the function winding
 for c in [2..n]
   if (n % c) isnt 0
     return c 

star = (n, k) ->        # define the function star
  pen k
  w = winding n         # use winding to pick w
  for [1..n]
    fd 100
    rt w * 360 / n      # use w as the winding number

star 12, purple         # draw a star!

The Importance of Testing

It is important to test algorithms! If you test this algorithm carefully, you will find that it still does not work for some values of n. For example, star 18, red draws a shape with only 9 stars.

It turns out that a better way to choose a winding number is to choose a number that has no common divisors with n (other than 1).

The following is Euclid's algorithm to calculate the greatest common divisor of two numbers:

gcd = (a, b) ->
  while b isnt 0    # repeat the indented lines while b isn't zero:
    if a > b        #  if a is greater than b, then do this:
      a = a - b     #   replace a with the difference (a - b)
    else            #  otherwise (if a is not greter than b):
      b = b - a     #   replace b with the difference (b - a)
  return a          # after the loop is done, the answer is a

If a and b have no common divisors, then gcd(a, b) is 1.


  1. Save the top program on this page as "star2" and test it. For what number larger than 18 does the algorithm draw the wrong number of corners? ______
  2. Create a program called "star3" that modifies winding to use gcd instead of %:
    1. Add the definition of gcd to your program before you use it.
    2. Make your program find a value for c that satisfies the condition gcd(n, c) is 1.
    3. Test the program carefully. How many corners are drawn by star 18, red? ______
  3. The "pointiest" stars are produced when the winding number is closest to half of n. Create a program "star4" that produces pointy stars:
    1. The primitive function floor rounds down, so floor(n/2) is half of n, rounded down.
    2. Experiment with a reversed loop for [floor(n/2)..1].
    3. For which positive integer n does star draw the least-pointy shape? ______
  4. Make a version named "star5" that uses speed Infinity, pen path and fill gold.