Programming Fundamentals
Objectives
- using arrays
- using struct arrays
- creating functions
- using while loops for repetition
Reminder: Help sessions
Help sessions are running this week!
These are one of the best ways for you to get one on one help with a tutor for any course content (including Lab Exercises and Assignments).
For the dates and times of the help sessions, see the Help Session Timetable.
To join a help session, or for more information, see the COMP(1511|1911) Help Session Microsoft Teams.
For face-to-face help sessions, the lab map can be found here. If help sessions are running in other buildings you can use Lost on Campus to help you find them.
Revision Videos!
Need a quick recap or revision on a topic we have looked at?
Head over to our Revision Videos Playlist! Here, you can watch some short youtube videos to help you understand and revise topics we have learnt so far!
If you watched one of the revision videos, please take a minute or two to fill out the survey here. Please note that this survey is completely optional and anonymous but aims to give feedback and provide suggestions fore more videos!
Activities To Be Completed
The following is a list of all the activities available to complete this week...
Worth 1 mark(s) in total:
- devowel
- print_pi_style
- scanning_into_array_style
- points
Worth 1 mark(s) in total:
- savings_analysis
- cs_calculator
Worth 0.5 mark(s) in total:
- detective
- rewrite_letters
Problem sets are capped at 15 marks (there are 4 possible bonus marks from the three-dot exercises that can bring you up to a total of 15 if you missed out on any other marks in the one- or two-dot exercises).
Completing just the one and two-dot exercises every week can give you the full 15 marks needed in this component.
For more details, see the course outline.
Preparation
Before the lab you should re-read the relevant lecture slides and their accompanying examples.
When attempting the following exercises, make sure to read the whole exercise, including any hints and assumptions that may make the exercise easier.
Exercise
(●◌◌)
:
Devowelling Text
Write a C program devowel.c which reads characters from its input and writes
the same characters to its output, except it does not write lower case vowels
('a', 'e', 'i', 'o', 'u').
Your program should stop only at the end of input.
Examples
dcc devowel.c -o devowel ./devowel Are you saying 'Boo' or 'Boo-Urns'? Ar y syng 'B' r 'B-Urns'? In this house, we obey the laws of thermodynamics! In ths hs, w by th lws f thrmdynmcs!
1511 style devowel.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest devowel
When you are finished working on this exercise,
you and your lab partner must both
submit your work by running give:
give cs1511 lab04_devowel devowel.c
Note, even though this is a pair exercise,
you both must run give from your own account
before Monday 17 March 18:00
to obtain the marks for this lab exercise.
Exercise
(●◌◌)
:
Print out pi to a certain number of digits
Good code style is required for this exercise.
To get full marks in this exercise, you MUST pass the automatic style checker
(1511 style).
If 1511 style finds any issues in your code, the maximum mark you can
achieve for this exercise is capped at 75%.
To run the automatic style checker on your code, use the following command:
1511 style print_pi_style.c
Download print_pi_style.c here
Or, copy these file(s) to your CSE account using the following command:
1511 fetch-activity print_pi_style
Your task is to add code to these functions in print_pi_style.c:
void print_pi_style(int num_digits) {
// DO NOT CHANGE THIS LINE
int pi[MAX_DIGITS] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
// TODO: Finish this function below
}
Write a C program, print_pi_style.c, which prints out the first n digits of
pi, where n is specified by the user.
The main function has already been written for you. There's an empty function
that has been provided for you called print_pi_style that takes in one
integer as an argument.
Place your code (only the printing code) inside this function. You can NOT put all of your code in main for this exercise, main must remain unmodified.
Examples
dcc print_pi_style.c -o print_pi_style ./print_pi_style How many digits of pi would you like to print? 3 3.14 ./print_pi_style How many digits of pi would you like to print? 5 3.1415 ./print_pi_style How many digits of pi would you like to print? 10 3.141592653
Assumptions/Restrictions/Clarifications
- You can assume that n >= 2 AND n <= 10, however, do not use this as a reason to avoid while loops.
1511 style print_pi_style.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest print_pi_style
When you are finished working on this exercise,
you must
submit your work by running give:
give cs1511 lab04_print_pi_style print_pi_style.c
You must run give
before Monday 17 March 18:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give must be entirely your own.
Exercise
(●◌◌)
:
Scanning numbers into an array
Good code style is required for this exercise.
To get full marks in this exercise, you MUST pass the automatic style checker
(1511 style).
If 1511 style finds any issues in your code, the maximum mark you can
achieve for this exercise is capped at 75%.
To run the automatic style checker on your code, use the following command:
1511 style scanning_into_array_style.c
Download scanning_into_array_style.c here
Or, copy these file(s) to your CSE account using the following command:
1511 fetch-activity scanning_into_array_style
Write a C program scanning_into_array_style.c which scans in a certain amount
of numbers from the user and fills an array with them.
- First, it scans in the quantity of numbers from the user.
- Then, it scans in that many numbers from the user.
Once the array is filled with the numbers the user input, call a pre-written function that prints the minimum and maximum values in that array
Examples
dcc scanning_into_array_style.c -o scanning_into_array_style ./scanning_into_array_style How many numbers: 5 Please enter numbers: 1 2 3 4 5 Minimum: 1 Maximum: 5 ./scanning_into_array_style How many numbers: 4 Please enter numbers: 3 -2 7 1 Minimum: -2 Maximum: 7
Assumptions/Restrictions/Clarifications
- The given inputs will always be integers.
- The given list of numbers will never be more than 100 numbers.
1511 style scanning_into_array_style.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest scanning_into_array_style
When you are finished working on this exercise,
you must
submit your work by running give:
give cs1511 lab04_scanning_into_array_style scanning_into_array_style.c
You must run give
before Monday 17 March 18:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give must be entirely your own.
Exercise
(●◌◌)
:
Using struct arrays to store points of a shape
Download points.c here
Or, copy these file(s) to your CSE account using the following command:
1511 fetch-activity points
Complete the C program points.c, so that it scans in all the points of a shape
into an array of structs. It should then print out the points that were
given.
First, it scans in the number of points that the shape has. Then, it scans in the coordinates of each point. Afterwards, it prints out the points in order.
Examples
dcc points.c -o points ./points How many points in the shape? 2 Enter points: 1.231 4.560 7.892 0.12 Shape Points: 1: x = 1.231, y = 4.560 2: x = 7.892, y = 0.120 ./points How many points in the shape? 4 Enter points: 6.340 2.781 5.675 2.453 4.893 0.123 0.232 3.349 Shape Points: 1: x = 6.340, y = 2.781 2: x = 5.675, y = 2.453 3: x = 4.893, y = 0.123 4: x = 0.232, y = 3.349
Assumptions/Restrictions/Clarifications
- When asked for the number of points, you will be given a non-zero positive integer.
- All inputs will be the correct type and non-zero positive numbers.
- The number of points will not exceed 10.
1511 style points.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest points
When you are finished working on this exercise,
you must
submit your work by running give:
give cs1511 lab04_points points.c
You must run give
before Monday 17 March 18:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give must be entirely your own.
Exercise
(●●◌)
:
Savings Analysis
Download savings_analysis.c here
Or, copy these file(s) to your CSE account using the following command:
1511 fetch-activity savings_analysis
You have been provided with some starter code savings_analysis.c with functions for you to complete: calc_yearly_deposits, calc_yearly_spending, calc_ending_balance and calc_months_saving_goal_met. It is your job to implement the functions and complete the program.
The program reads in the user's starting balance and monthly saving goal for the year. This is followed by 12 months of deposits and 12 months of spending. The program then runs a series of functions to analyse the account over the year. It is your job to complete these functions.
Examples
dcc savings_analysis.c -o savings_analysis ./savings_analysis Please enter starting balance: 1320 Please enter monthly saving goal: 60 Please enter monthly deposits: 208 234 182 182 208 156 156 182 208 208 234 260 Please enter monthly spending: 120 103 150 122 130 372 106 115 127 124 104 200 Yearly deposits = $2418 Yearly spending = $1773 Ending balance = $1965 You met the monthly saving goal 9 times! ./savings_analysis Please enter starting balance: 500 Please enter monthly saving goal: 220 Please enter monthly deposits: 800 850 900 870 820 880 890 830 910 850 860 840 Please enter monthly spending: 600 620 610 630 640 615 610 625 600 630 635 670 Yearly deposits = $10300 Yearly spending = $7485 Ending balance = $3315 You met the monthly saving goal 8 times!
Assumptions/Restrictions/Clarifications
- The function names in your solution should be the same as the provided starter code.
- Numbers entered will always be positive integers.
- The correct amount of input will always be provided. That is, the number of monthly deposits and monthly spending will always be 12.
- You must implement the functions specified to pass the autotests and receive marks for this activity.
1511 style savings_analysis.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest savings_analysis
When you are finished working on this exercise,
you must
submit your work by running give:
give cs1511 lab04_savings_analysis savings_analysis.c
You must run give
before Monday 17 March 18:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give must be entirely your own.
Exercise
(●●◌)
:
Create a simple calculator, reading different numbers of integers
For this exercise, make a program called cs_calculator.c which will scan in
instructions until End-Of-Input (which we enter to our terminal with the
keyboard shortcut CTRL-D) and prints the output as
specified below. An instruction is a character, followed by one or two positive
integers.
The first character identifies what type the instruction is.
- If the first character in the instruction is
's', then your program should print out the square of the next number in the instruction. - If the first character in the instruction is
'p', then your program should print out the value of the next number raised to the power of the number after next.
Examples
dcc cs_calculator.c -o cs_calculator ./cs_calculator Enter instruction: s 2 4 Enter instruction: p 5 3 125 Enter instruction: s 4 16 Enter instruction: p 3 4 81 Enter instruction: ./cs_calculator Enter instruction: p 3 3 27 Enter instruction: s 10 100 Enter instruction:
One major challenge of this exercise is figuring out how to use scanf
effectively. The lessons you learn in this exercise regarding scanf will be
useful in assignment 1!
Assumptions/Restrictions/Clarifications
- You can assume that the first character in the instruction is only either
's'or'p' - You can assume that for each instruction, the correct number of successive positive integers will be given.
- The autotest for this exercise expects your program to end WITHOUT a new line
character when the user presses
Ctrl-D. This means that the command prompt for the next command should be on the same line as the end of your program.
1511 style cs_calculator.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest cs_calculator
When you are finished working on this exercise,
you and your lab partner must both
submit your work by running give:
give cs1511 lab04_cs_calculator cs_calculator.c
Note, even though this is a pair exercise,
you both must run give from your own account
before Monday 17 March 18:00
to obtain the marks for this lab exercise.
Exercise
(●●●)
:
Detective
Download detective.c here
Or, copy these file(s) to your CSE account using the following command:
1511 fetch-activity detective
Your mission (if you choose to accept it) is to complete the program detective.c to decipher encoded messages.
Over the past few months UNSW Security Society has found seemingly normal messages paired with random numbers. To help you solve this challenge we have created the program detective.c that reads in the message and numbers, storing them in a struct array.
We have been lucky enough to find one decoded message:
Encoded Message: muahahaha_we're_so_evil#_GNTY
Secret Numbers: 7-23-3-6-13-22-24-2-16-4-14-18-20-11-9-28-21-1-27-8-0-26-12-5-10-15-25-19-17
Deciphered Message: haha_we_are_TeasiNG_You
Our observations from this are:
- Messages seem to end with a
#. - There are always the same number of letters as there are numbers.
- Letters maintain their case between their encoded and deciphered message.
- Each number is unique counting from
0ton - 1(wherenis the number of letters).
We wish you luck detective!
Examples
dcc detective.c -o detective ./detective Please enter Encrypted Message: muahahaha_we're_so_evil#_GNTY Please enter Secret Numbers: 7-23-3-6-13-22-24-2-16-4-14-18-20-11-9-28-21-1-27-8-0-26-12-5-10-15-25-19-17 Secret Message is: haha_we_are_TeasiNG_You ./detective Please enter Encrypted Message: STUDENTS_L0VE_COMP1511_#new_students_aww_:) Please enter Secret Numbers: 28-12-24-38-6-33-36-27-16-7-19-17-39-2-11-14-32-31-41-23-18-15-0-21-35-9-40-20-1-30-5-42-4-25-13-26-37-34-22-8-29-10-3 Secret Message is: sTEw_MeET_at_Unsw_tuNneLS_11:05
Assumptions/Restrictions/Clarifications
- The maximum number of characters is 100.
- The number of characters in the encrypted message and the amount of secret numbers are the same.
- The case of each letter is preserved in translation.
- Messages will end with a
#.
1511 style detective.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest detective
When you are finished working on this exercise,
you must
submit your work by running give:
give cs1511 lab04_detective detective.c
You must run give
before Monday 17 March 18:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give must be entirely your own.
Exercise
(●●●)
:
Rewrite Letters
Download rewrite_letters.c here
Or, copy these file(s) to your CSE account using the following command:
1511 fetch-activity rewrite_letters
A sequence of characters can be rewritten by replacing a chosen character with a rewriting rule. For example, the sequence of characters "This is X" can be rewritten by replacing character 'X' with rewriting rule "COMP1511" to yield "This is COMP1511".
Rewriting can also be done with more than one character at a time. For example, the sequence of characters "All X are Y" can be rewritten by replacing X with "squares" and Y with "rectangles" to yield "All squares are rectangles".
Task
Write a C program rewrite_letters.c that rewrites an initial sequence of letters by replacing specified characters based on user-defined rules.
The program should:
- Prompt for an initial sequence of characters.
- Read the first character to replace.
- Read the rewriting rule to replace the first character.
- Read the second character to replace.
- Read the rewriting rule to replace the second character.
- Apply the rewriting rules to the initial sequence, replacing all instances of the letters to be rewritten with their replacement rule.
- Output the rewritten result.
Examples
dcc rewrite_letters.c -o rewrite_letters ./rewrite_letters Initial letters: All @ must gather at the # immediately. 1st letter to be rewritten: @ 1st rewriting rule: ninjas 2nd letter to be rewritten: # 2nd rewriting rule: chocolate fountain All ninjas must gather at the chocolate fountain immediately. ./rewrite_letters Initial letters: aba 1st letter to be rewritten: a 1st rewriting rule: xx 2nd letter to be rewritten: b 2nd rewriting rule: yyy xxyyyxx ./rewrite_letters Initial letters: How much X would a XY Y if a XY could Y X? 1st letter to be rewritten: X 1st rewriting rule: wood 2nd letter to be rewritten: Y 2nd rewriting rule: chuck How much wood would a woodchuck chuck if a woodchuck could chuck wood? ./rewrite_letters Initial letters: 143 = (m + n) * (m - n) 1st letter to be rewritten: m 1st rewriting rule: 12 2nd letter to be rewritten: n 2nd rewriting rule: 1 143 = (12 + 1) * (12 - 1)
Assumptions/Restrictions/Clarifications
- The following will contain 1024 characters or less:
- The sequence of initial letters.
- The rewriting rules.
- The final rewritten result.
- The letters to be rewritten will always be input by the user.
- The letters to be rewritten will be unique. For example:
- If the first letter to be rewritten is an
'a'then the second letter to be rewritten will be a letter other than'a'.
- If the first letter to be rewritten is an
- The rewriting rules will always be input by the user.
- Your program must be able to handle all printable ASCII characters (decimal
codes
32to126). This excludes any control characters (from0to31) and the delete character (127).
1511 style rewrite_letters.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest rewrite_letters
When you are finished working on this exercise,
you must
submit your work by running give:
give cs1511 lab04_rewrite_letters rewrite_letters.c
You must run give
before Monday 17 March 18:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give must be entirely your own.
Exercise — individual:
(Not for Marks) Refactoring - Class Details
Download class_details.c here
Or, copy these file(s) to your CSE account using the following command:
1511 fetch-activity class_details
For this activity, you've been provided with a fully working program: class_details.c.
While this code produces the correct output, it's code style is not very good.
In particular, class_detail.c is full of magic numbers and repeating code,
and it's main function is more than 200 lines long!
Try running 1511 style class_details.c to see even more of it's style issues.
For this activity your job is to go through and improve the readability of the code by
- Replacing magic numbers with enums and #defines,
- Breaking it up into small functions (less than 40 lines),
- Using those functions to remove unnecessary repetition,
- Writing some function comments to document the code.
You shouldn't change any of the actual functionality of the program i.e. none of the changes you make should change any of the program's output.
Program description
Below is a description of the program. Keep in mind that this has all already been implemented for you.
The provided program scans in and stores the details of students in a class. It first scans in the size of the class, and then scans in the details of each of the students including:
- zID
- Degree type (Undergraduate/Postgraduate)
- Major (if an Undergraduate)
- Assignments mark (Collated mark of assignments and labs)
- Exam mark
- Course grade
Once all student details have been scanned in, the program then loops and scans
in commands. It doesn't stop looping until the QUIT command is entered. The
program performs one of the following tasks:
- Command 0 Help: Display program instructions
- Command 1 (Display Student): Print the details of a specific student
- Command 2 (Display Class): Print the details of all students in a class
- Command 3 (Quit): Exit the program
Examples
dcc class_details.c -o class_details
./class_details
Enter Class Size: 1
Student 1:
Enter zID: 5111111
Select Degree Type:
0: Undergraduate
1: Postgraduate
0
Select Major:
0: Computer Science
1: Database Systems
2: eCommerce Systems
3: Artificial Intelligence
4: Programming Languages
5: Computer Networks
6: Embedded Systems
7: Security Engineering
8: None
2
Enter Assignments mark (out of 60): 35.5
Enter exam mark (out of 40): 30
Enter Command Number (0 for Help): 0
Enter a number corresponding to one of the following commands:
0 (Help): Display program instructions
1 (Display Student): Print the details of a specific student
2 (Display Class): Print the details of all students in a class
3 (Quit): Exit the program
Enter Command Number (0 for Help): 1
Enter Student zID: 5222222
No student with that zID exists
Enter Command Number (0 for Help): 1
Enter Student zID: 5111111
z5111111: {
Degree Type: Undergraduate
Major: eCommerce Systems
Assignments Mark: 35.50/60
Exam Mark: 30.00/40
Course Grade: 65.50/100
}
Enter Command Number (0 for Help): 100
Invalid Command
Enter Command Number (0 for Help): 3
Exiting Program
./class_details
Enter Class Size: 2
Student 1:
Enter zID: 5111111
Select Degree Type:
0: Undergraduate
1: Postgraduate
0
Select Major:
0: Computer Science
1: Database Systems
2: eCommerce Systems
3: Artificial Intelligence
4: Programming Languages
5: Computer Networks
6: Embedded Systems
7: Security Engineering
8: None
6
Enter Assignments mark (out of 60): 35.5
Enter exam mark (out of 40): 30
Student 2:
Enter zID: 5222222
Select Degree Type:
0: Undergraduate
1: Postgraduate
1
Enter Assignments mark (out of 60): 40.5
Enter exam mark (out of 40): 25.9
Enter Command Number (0 for Help): 2
Students:
z5111111: {
Degree Type: Undergraduate
Major: Embedded Systems
Assignments Mark: 35.50/60
Exam Mark: 30.00/40
Course Grade: 65.50/100
}
z5222222: {
Degree Type: Postgraduate
Assignments Mark: 40.50/60
Exam Mark: 25.90/40
Course Grade: 66.40/100
}
Enter Command Number (0 for Help): 1
Enter Student zID: 5222222
z5222222: {
Degree Type: Postgraduate
Assignments Mark: 40.50/60
Exam Mark: 25.90/40
Course Grade: 66.40/100
}
Enter Command Number (0 for Help): 3
Exiting Program
Assumptions/Restrictions/Hints
- You should not change the functionality of the program in any way
- If there are any edge cases not handled by the original code (e.g. students sharing zids), you do not need to modify the code to handle them
- All inputs will positive, and be the correct type
1511 style class_details.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest class_details
Exercise — individual:
(Not For Marks) Debugging - Letter Search
Download debug_letter_search.c here
Or, copy these file(s) to your CSE account using the following command:
1511 fetch-activity debug_letter_search
Note that this exercise is not marked or worth marks!
Debugging Tips!
Some debugging tips for you:
- dcc output - as you run into issues, dcc will point you to where the errors are. Remember that dcc gives you the line number the issue is on, and will give some sort of explanation. Make sure you read everything dcc gives you. Sometimes we get “errors carried forward”, so find your first error, fix that, then recompile.
- print statements - sometimes it can be handy to see if the flow of your code puts you in the spot you expect it to be (ie. inside the right if statement, or going through a loop the correct amount of times). A quick way you can check this is by putting print statements in your code for testing purposes, like
"the value of x is %d and y is %d". This lets you check that you got against what you expected. - COMP1511 debugging guide
The Task
This exercise reads in a letter from the user, and then searches more input given by the user for that letter, or until CTRL+D is entered. It then tells the user if the search was sucessful or not.
Examples
dcc debug_letter_search.c -o debug_letter_search ./debug_letter_search Which letter are we searching for?: g COMP1511 is awesome! hmmm, how about this? what about now? hm. How about frog? We found g!!! ./debug_letter_search Which letter are we searching for?: ? No questions here. Only sentences. I could have a question. Nah The mission was not successful :(
Walkthrough
Below is a video walkthrough of this exercise! Make sure to attempt it before watching this video
1511 style debug_letter_search.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest debug_letter_search
Exercise — individual:
(Not For Marks) Debugging - Clouds
Download debug_cloud.c here
Or, copy these file(s) to your CSE account using the following command:
1511 fetch-activity debug_cloud
Note that this exercise is not marked or worth marks!
Debugging Tips!
Some debugging tips for you:
- dcc output - as you run into issues, dcc will point you to where the errors are. Remember that dcc gives you the line number the issue is on, and will give some sort of explanation. Make sure you read everything dcc gives you. Sometimes we get “errors carried forward”, so find your first error, fix that, then recompile.
- print statements - sometimes it can be handy to see if the flow of your code puts you in the spot you expect it to be (ie. inside the right if statement, or going through a loop the correct amount of times). A quick way you can check this is by putting print statements in your code for testing purposes, like
"the value of x is %d and y is %d". This lets you check that you got against what you expected. - COMP1511 debugging guide
The Task
This exercise reads in some cloud heights from a user and works out what type of clouds they are. The program then prints out the total count for all the types.
Note that fog clouds are the lowest, then cumulo, then alto, then cirro clouds occur at the highest heights.
Examples
dcc debug_cloud.c -o debug_cloud ./debug_cloud Enter some clouds: 200 550 880 2500 100000 CLOUDS There are 1 fog clouds There are 2 cumulo clouds There are 1 alto clouds There are 1 cirro clouds ./debug_cloud Enter some clouds: 65000 80000 3000 4000 4690.23 12.54 24.57 8 CLOUDS There are 3 fog clouds There are 0 cumulo clouds There are 3 alto clouds There are 2 cirro clouds
Walkthrough
Below is a video walkthrough of this exercise! Make sure to attempt it before watching this video
1511 style debug_cloud.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest debug_cloud
Exercise — individual:
(Not for Marks) Fractal Turtle 🐢 (extra-hard)
Download fractal_turtle.c here
Or, copy these file(s) to your CSE account using the following command:
1511 fetch-activity fractal_turtle
The goal of this activity is to display fractals on the terminal. To do this, three topics are combined:
- Turtle Graphics - to draw images based on sequences of characters.
- L-Systems - to generate sequences of characters.
- Fractals - the types of images we are interested in.
These topics will be introduced, followed by instructions for the activity.
Turtle Graphics
Turtle Graphics is a simplified drawing system where an imaginary turtle moves around the screen according to commands.
Initially, the turtle faces up towards the top of the screen. It then follows commands to draw on the canvas:
Fmoves the turtle forwards 2 steps while painting a line.fmoves the turtle forwards 2 steps, without painting a line.+turns the turtle left by 90 degrees.-turns the turtle right by 90 degrees.
Using these commands, we can create images by instructing the turtle where to move and when to draw.
For example, if we wanted to paint the blue shapes in Figure 1, we could use the instructions FFF-FffF-F-fff+f+F-FF. Our turtle would interpret this sequence of characters according to the annotations in Figure 2.
Figure 1. Example turtle graphic.
Figure 2. Turtle interpretation of FFF-FffF-F-fff+f+F-FF.
But how can we represent these graphics in the terminal?
We could choose to represent each blue painted tile by a hash '#', and each unpainted tile by a space ' '. But due to the unequal heights and widths of characters printed to the terminal, this results in the skewed image shown by Figure 3.
### ###
# #
# #
#
# ###
# #
# #
#
#
Figure 3. Sad turtle graphics ☹.
Luckily, this can be fixed! We represent each tile as two characters on the terminal:
- For each painted tile, we use two characters: a space
' 'followed by a hash'#'i.e." #". - For each unpainted tile, we use two spaces i.e.
" ".
This results in the terminal output shown in Figure 4. Compare this to Figure 1.
# # # # # #
# #
# #
#
# # # #
# #
# #
#
#
Figure 4. Happy turtle graphics 🐢.
# # # # # # # #
Figure 5. The turtle interpretation of F-F-F-F draws a square.
#
#
# # #
#
# # # # #
#
# # #
#
#
Figure 6. The turtle interpretation of F-F+F+FF-F-F+F draws a squiggle.
#
#
#
#
# # # # #
# #
# # # # #
#
#
#
#
Figure 7. The turtle interpretation of FF+F-F-FF-F-F-fFF draws a circuit element.
#
#
# # # #
# # #
# # #
# # #
# # # # # # #
# # #
# # #
# # #
# # # #
#
#
Figure 8. The turtle interpretation of F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF draws a birds-eye view of a road with two cars.
L-Systems
Writing out long sequences (such as F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF) can be tedious and error-prone. Instead, we use a find-and-replace method known as an L-System to generate these sequences automatically. We begin with a short sequence and apply simple rules to expand it into larger sequences.
An L-system is a set of rules used to generate complex sequences of characters.
Given a sequence of characters, we can rewrite it by replacing chosen characters according to designated rules.
For example, starting with an initial sequence of characters "abc" we could rewrite it by replacing:
- every
awith rule"ba", and - every
bwith rule"baab".
Initially, we have:
"abc"
After one rewrite:
"babaabc"
After the second rewrite:
"baabbabaabbababaabc"
And so on...
Each rewrite replaces every occurrence of a character with the sequence of characters from its corresponding rule.
By employing L-systems, we can use simple rules to systematically produce long and complex sequences of characters.
Fractals
For this activity: a fractal is a shape that repeats a pattern at difference scales.
For example, suppose we begin with the single vertical line in Figure 9 resulting from the turtle interpretation of F.
# # #
Figure 9. A single vertical line: F.
If we replace F with F-F+F+FF-F-F+F (i.e. replace it with the squiggle from Figure 6) the rewritten sequence of characters is F-F+F+FF-F-F+F, and is shown by Figure 10. We've replaced every line by a squiggle, and since we started with one line, the result is one squiggle.
#
#
# # #
#
# # # # #
#
# # #
#
#
Figure 10. The turtle interpretation of F-F+F+FF-F-F+F is a squiggle.
Now we're at the main point of this exercise: what if we do it again? Let's replace every line (every F character) in the squiggle F-F+F+FF-F-F+F with another squiggle F-F+F+FF-F-F+F.
The rewritten result is the long sequence of characters F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F+F-F+F+FF-F-F+FF-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F. The turtle interpretation of these commands is illustrated in Figure 11 to be a squiggle of squiggles!
At this point it's worth pausing to observe that this shape is a large squiggle, where every edge has been replaced by a smaller squiggle. This is an example of what we're calling a fractal: a shape that repeats a pattern at different scales.
#
#
# # #
#
# # # # #
#
# # # # # #
# # #
# # # # # # #
# # #
# # # # # #
#
# # # # #
#
# # # # # # # # #
# # # # #
# # # # # # # # # # # # #
# # # # #
# # # # # # # # #
#
# # # # #
#
# # # # # #
# # #
# # # # # # #
# # #
# # # # # #
#
# # # # #
#
# # #
#
#
Figure 11. A squiggly-squiggle resulting from replacing F by F-F+F+FF-F-F+F two times.
Task
Write a C program fractal_turtle.c that repeatedly rewrites an initial sequence of characters by replacing characters 'F' and 'f' with user-defined rules, and then prints a turtle interpretation of the resulting sequence to the terminal.
The program should:
- Read an initial sequence of characters consisting of any combination of
'F','f','+', or'-'. - Prompt the user to enter a rewriting rule for
'F'. - Prompt the user to enter a rewriting rule for
'f'. - Ask for the number of times to apply the rewriting rules.
- Apply the rewriting rules, replacing each instance of
'F'and'f'with the corresponding rewriting rule. Revisiting the section on L-Systems may be helpful here. - Print each intermediate rewrite (e.g. the initial string, the 1st rewrite, the 2nd rewrite, etc) to the terminal.
- Output the turtle interpretation of the final sequence of rewritten characters to the terminal.
Examples
dcc fractal_turtle.c -o fractal_turtle
./fractal_turtle
Initial characters (F, f, -, +): F
Rewriting rule for 'F': F-F+F+FF-F-F+F
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 1
Rewrite 0: F
Rewrite 1: F-F+F+FF-F-F+F
#
#
# # #
#
# # # # #
#
# # #
#
#
./fractal_turtle
Initial characters (F, f, -, +): F
Rewriting rule for 'F': F-F+F+FF-F-F+F
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 2
Rewrite 0: F
Rewrite 1: F-F+F+FF-F-F+F
Rewrite 2: F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F+F-F+F+FF-F-F+FF-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F+F-F+F+FF-F-F+F
#
#
# # #
#
# # # # #
#
# # # # # #
# # #
# # # # # # #
# # #
# # # # # #
#
# # # # #
#
# # # # # # # # #
# # # # #
# # # # # # # # # # # # #
# # # # #
# # # # # # # # #
#
# # # # #
#
# # # # # #
# # #
# # # # # # #
# # #
# # # # # #
#
# # # # #
#
# # #
#
#
./fractal_turtle
Initial characters (F, f, -, +): F-F-F-F
Rewriting rule for 'F': F-F+F+FF-F-F+F
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 1
Rewrite 0: F-F-F-F
Rewrite 1: F-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F-F-F+F+FF-F-F+F
# # #
# #
# # # # # # #
# # # #
# # # # # # # # #
# #
# # # # # # # # # #
# #
# # # # # # # # #
# # # #
# # # # # # #
# #
# # #
dcc fractal_turtle.c -o fractal_turtle
./fractal_turtle
Initial characters (F, f, -, +): F
Rewriting rule for 'F': FF+F-F-FF-F-F-fFF
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 1
Rewrite 0: F
Rewrite 1: FF+F-F-FF-F-F-fFF
#
#
#
#
# # # # #
# #
# # # # #
#
#
#
#
./fractal_turtle
Initial characters (F, f, -, +): F
Rewriting rule for 'F': FF+F-F-FF-F-F-fFF
Rewriting rule for 'f': fffff
Number of times to apply the rewriting rules: 2
Rewrite 0: F
Rewrite 1: FF+F-F-FF-F-F-fFF
Rewrite 2: FF+F-F-FF-F-F-fFFFF+F-F-FF-F-F-fFF+FF+F-F-FF-F-F-fFF-FF+F-F-FF-F-F-fFF-FF+F-F-FF-F-F-fFFFF+F-F-FF-F-F-fFF-FF+F-F-FF-F-F-fFF-FF+F-F-FF-F-F-fFF-fffffFF+F-F-FF-F-F-fFFFF+F-F-FF-F-F-fFF
#
#
#
#
# # # # #
# #
# # # # #
#
#
#
#
#
#
#
# # # # #
# #
# # # # #
#
# # # # # # #
# # # # #
# # # # # # # # # # # # # # # # # # #
# # # # # #
# # # # # # # #
# #
# # # # # # # # # #
# # # #
# # # # # # # # # #
# #
# # # # # # # #
# # # # # #
# # # # # # # # # # # # # # # # # # #
# # # # #
# # # # # # #
#
# # # # #
# #
# # # # #
#
#
#
#
#
#
#
# # # # #
# #
# # # # #
#
#
#
#
./fractal_turtle
Initial characters (F, f, -, +): F-F-F-F
Rewriting rule for 'F': FF+F-F-FF-F-F-fFF
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 1
Rewrite 0: F-F-F-F
Rewrite 1: FF+F-F-FF-F-F-fFF-FF+F-F-FF-F-F-fFF-FF+F-F-FF-F-F-fFF-FF+F-F-FF-F-F-fFF
# # #
# #
# # # # # # # # # #
# # # #
# # # # #
# #
# # # # # # # # # #
# # # #
# # # # # # # # # #
# #
# # # # #
# # # #
# # # # # # # # # #
# #
# # #
dcc fractal_turtle.c -o fractal_turtle
./fractal_turtle
Initial characters (F, f, -, +): F
Rewriting rule for 'F': F+F-F-F+F
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 1
Rewrite 0: F
Rewrite 1: F+F-F-F+F
#
#
# # #
#
# # #
#
#
./fractal_turtle
Initial characters (F, f, -, +): F
Rewriting rule for 'F': F+F-F-F+F
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 2
Rewrite 0: F
Rewrite 1: F+F-F-F+F
Rewrite 2: F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F
#
#
# # #
#
# # # # #
# # #
# # # # # #
#
# # #
#
# # #
#
# # # # # #
# # #
# # # # #
#
# # #
#
#
./fractal_turtle
Initial characters (F, f, -, +): F
Rewriting rule for 'F': F+F-F-F+F
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 3
Rewrite 0: F
Rewrite 1: F+F-F-F+F
Rewrite 2: F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F
Rewrite 3: F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F
#
#
# # #
#
# # # # #
# # #
# # # # # #
#
# # #
#
# # # # #
# # #
# # # # # # # # # # #
# # # # #
# # # # # # # # # #
# # #
# # # # # # # # # # # #
# # # # # # #
# # # # # # # # # # # #
#
# # #
#
# # # # #
# # #
# # # # # #
#
# # #
#
# # #
#
# # # # # #
# # #
# # # # #
#
# # #
#
# # # # # # # # # # # #
# # # # # # #
# # # # # # # # # # # #
# # #
# # # # # # # # # #
# # # # #
# # # # # # # # # # #
# # #
# # # # #
#
# # #
#
# # # # # #
# # #
# # # # #
#
# # #
#
#
dcc fractal_turtle.c -o fractal_turtle
./fractal_turtle
Initial characters (F, f, -, +): F-F-F-F
Rewriting rule for 'F': FF-F-F-F-FF
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 2
Rewrite 0: F-F-F-F
Rewrite 1: FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF
Rewrite 2: FF-F-F-F-FFFF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FFFF-F-F-F-FF-FF-F-F-F-FFFF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FFFF-F-F-F-FF-FF-F-F-F-FFFF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FFFF-F-F-F-FF-FF-F-F-F-FFFF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FFFF-F-F-F-FF
# # # # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # #
# # # # # #
# # # # # # # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # # # # #
# # # # # #
# # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # #
./fractal_turtle
Initial characters (F, f, -, +): F-F-F-F
Rewriting rule for 'F': FF-F--F-F
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 2
Rewrite 0: F-F-F-F
Rewrite 1: FF-F--F-F-FF-F--F-F-FF-F--F-F-FF-F--F-F
Rewrite 2: FF-F--F-FFF-F--F-F-FF-F--F-F--FF-F--F-F-FF-F--F-F-FF-F--F-FFF-F--F-F-FF-F--F-F--FF-F--F-F-FF-F--F-F-FF-F--F-FFF-F--F-F-FF-F--F-F--FF-F--F-F-FF-F--F-F-FF-F--F-FFF-F--F-F-FF-F--F-F--FF-F--F-F-FF-F--F-F
# # # # # # # # # # # # # # # # # # #
# # # # # #
# # # # # # # # # #
# # #
# # # # # # # #
# # # #
# # # # # # # # #
# # #
# # # # #
# #
# # # # #
# # #
# # # # # # # # #
# # # #
# # # # # # # #
# # #
# # # # # # # # # #
# # # # # #
# # # # # # # # # # # # # # # # # # #
./fractal_turtle
Initial characters (F, f, -, +): F
Rewriting rule for 'F': FF-F--F-F
Rewriting rule for 'f': f
Number of times to apply the rewriting rules: 3
Rewrite 0: F
Rewrite 1: FF-F--F-F
Rewrite 2: FF-F--F-FFF-F--F-F-FF-F--F-F--FF-F--F-F-FF-F--F-F
Rewrite 3: FF-F--F-FFF-F--F-F-FF-F--F-F--FF-F--F-F-FF-F--F-FFF-F--F-FFF-F--F-F-FF-F--F-F--FF-F--F-F-FF-F--F-F-FF-F--F-FFF-F--F-F-FF-F--F-F--FF-F--F-F-FF-F--F-F--FF-F--F-FFF-F--F-F-FF-F--F-F--FF-F--F-F-FF-F--F-F-FF-F--F-FFF-F--F-F-FF-F--F-F--FF-F--F-F-FF-F--F-F
#
#
# # #
#
# #
# #
# # # # # # #
# #
# # # #
#
#
#
# #
# #
# # # # # #
# #
# # # # # # #
# # # # #
# # # # # # # # # # # # # # # # # # #
# # # # #
# # # # # # # # #
# #
# # # # #
# # #
# # # # # # # #
# #
# # # #
#
#
#
#
#
# # #
#
#
#
#
#
# # #
#
# #
# #
# # # # # # #
# #
# # # #
#
#
#
#
#
# # #
#
#
#
#
./fractal_turtle
Initial characters (F, f, -, +): F+F+F+F
Rewriting rule for 'F': F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF
Rewriting rule for 'f': ffffff
Number of times to apply the rewriting rules: 1
Rewrite 0: F+F+F+F
Rewrite 1: F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF+F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF+F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF+F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF
# # # # #
# #
# # # # #
# # # # # # # # # # # # #
# #
# # # # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # #
# # # # # #
# # # # # # # # # # # # # #
# # # # # #
# # # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # # #
# #
# # # # # # # # # # # # #
# # # # #
# #
# # # # #
Assumptions/Restrictions/Clarifications
-
Use of the following C language features is not permitted for this activity:
- Two-dimensional arrays.
- Variable-length arrays.
- Dynamically allocated memory e.g. any use of
malloc().
-
There is no predefined limit or maximum size (number of rows or columns) required to output the turtle interpretation. Your program should be able to handle arbitrarily large output sizes.
-
Every
'#'character is printed with a space' 'before it. In particular: note from the examples that a'#'character is never printed in the first column of output as it is always preceded by a space' '. -
The following inputs will contain
16384characters or less:- The sequence of initial letters.
- The rewriting rules.
- All rewritten sequences of characters.
-
The initial sequence of characters will never be empty.
-
It is possible for a rewriting rule to be empty e.g. to replace an
'f'with no characters at all. -
Your program must be able to handle all printable ASCII characters (decimal codes
32to126). This excludes any control characters (from0to31) and the delete character (127). -
The number of times to apply the rewriting rules will be a non-negative integer (zero is a valid input).
1511 style fractal_turtle.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest fractal_turtle
Submission
give.
You can run give multiple times.
Only your last submission will be marked.
Don't submit any exercises you haven't attempted.
If you are working at home, you may find it more convenient to upload your work via give's web interface.
Remember you have until Week 5 Monday 18:00 to submit your work.
You cannot obtain marks by e-mailing your code to tutors or lecturers.
You check the files you have submitted here.
Automarking will be run by the lecturer several days after the submission deadline,
using test cases different to those autotest runs for you.
(Hint: do your own testing as well as running autotest.)
After automarking is run by the lecturer you can view your results here. The resulting mark will also be available via give's web interface.