# Developing an Algorithm to Draw Stars

Do this on pencilcode.net

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!

```

Exercises

1. Enter the program above that defines the `star` function, and save it as "star1". Some tips:
• Since the function is longer than one line, its code is indented below the `->`.
• Indenting is important: be sure to indent all the lines in the function neatly.
• The block of code inside the loop inside the function must be doubly-indented.
• Defining `star = ...` will not run it yet. To run it you must use it: `star 7, red`.
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.

Exercises

1. Enter the program above that defines the `winding` function, and save it as "winding". Remember:
• Indenting is important: be sure to indent all the lines in the function neatly.
• Lines doubly-indented after the `while` will happen inside the loop.
• Since you want to `return` the answer outside the loop, `return` should not be doubly-indented. But since the `return` is part of the function, it should be singly-indented.
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.

Exercises

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`.