COMP10001 Foundations of Computing Week 9, Lecture 2
COMP10001 Foundations of Computing
Project 2
Semester 1, 2023
Chris Ewin, Alistair Moffat, and Alex Zable
© 2023 The University of Melbourne
COMP10001 Foundations of Computing Week 9, Lecture 2
Lecture Outline
1 What Is A FoCdle?
2 The Four Tasks
3 The Bonus Marks
4 The Boring Stuff
COMP10001 Foundations of Computing Week 9, Lecture 2
Wordles
Maybe you have played the game
wordle.
A secret word must be identified
via a sequence of guesses.
The smaller the number of guesses
it takes you to get secret word, the
“smarter” (or luckier) you are.
Requires logic and vocabulary.
Image: https://opensource.com/article/22/1/open-source-accessibility-wordle
COMP10001 Foundations of Computing Week 9, Lecture 2
FoCdles
Instead of logic and vocabulary, let’s have a puzzle that takes logic
and arithmetic. Enter the FoCdle!
COMP10001 Foundations of Computing Week 9, Lecture 2
FoCdles
Instead of logic and vocabulary, let’s have a puzzle that takes logic
and arithmetic. Enter the FoCdle!
COMP10001 Foundations of Computing Week 9, Lecture 2
FoCdles
Instead of logic and vocabulary, let’s have a puzzle that takes logic
and arithmetic. Enter the FoCdle!
COMP10001 Foundations of Computing Week 9, Lecture 2
FoCdles
Instead of logic and vocabulary, let’s have a puzzle that takes logic
and arithmetic. Enter the FoCdle!
COMP10001 Foundations of Computing Week 9, Lecture 2
FoCdle Structure
A FoCdle is a string with seven elements:
〈value〉 〈operator〉 〈value〉 〈operator〉 〈value〉 = 〈result〉
where:
• 〈value〉 is an integer, 1 . . . 99, with no leading “0”s
• 〈operator〉 is one of “+”, “–”, “*”, “%”
• 〈result〉 is a positive integer, 1 . . ., with no leading “0”s
and where the 〈result〉 is mathematically correct.
The difficulty of a FoCdle is its length, counted in character positions.
COMP10001 Foundations of Computing Week 9, Lecture 2
FoCdle Structure
All FoCdle expressions are evaluated according to the rules of Python,
with “*” and “%” taking precedence over “+” and “–”.
The Python function eval(string) computes and returns the value of
its argument, which must be a valid Python expression:
>>> mystr = "21"
>>> mystr += "*"
>>> mystr += "3"
>>> eval(mystr)
63
This is a very powerful facility that you’ll need in your programs.
COMP10001 Foundations of Computing Week 9, Lecture 2
Lecture Outline
1 What Is A FoCdle?
2 The Four Tasks
3 The Bonus Marks
4 The Boring Stuff
COMP10001 Foundations of Computing Week 9, Lecture 2
Task 1 – Being A Bit Random
This task asks for a function create_secret(difficulty):
>>> create_secret (8)
"5*6 -1=29"
>>> create_secret (10)
"37*50%56=2"
>>> create_secret (12)
"84%85+24=108"
>>> create_secret (14)
"27*71*40=76680"
COMP10001 Foundations of Computing Week 9, Lecture 2
Task 1 – Being A Bit Random
You need to generate random expressions with three 〈value〉s and two
〈operator〉s, and then compute the corresponding result. If the
overall string is the required length, it is returned.
If it is the wrong length, the process repeats, up to MAX_TRIALS times.
A message is returned if a FoCdle could not be generated.
>>> create_secret (16)
"No FoCdle found of that difficulty"
COMP10001 Foundations of Computing Week 9, Lecture 2
Task 2 – Setting Colors
This task asks for a function set_colors(secret, guess):
>>> set_colors("1+2*3=7", "1 -4+7=4")
[(0, '1', 'green '), (1, '-', 'grey'), (2, '4', 'grey'),
(3, '+', 'yellow '), (4, '7', 'yellow '), (5, '=', 'green '),
(6, '4', 'grey')]
The codes:
• green: matching both value and location
• yellow: matches a value, but in a different location
• grey: does not match a symbol
COMP10001 Foundations of Computing Week 9, Lecture 2
Task 2 – Setting Colors
Multiplicity matters, and where there is more than one option, it is
the leftmost position in guess that is assigned “yellow”:
COMP10001 Foundations of Computing Week 9, Lecture 2
Task 3 – Checking Restrictions
Each call to set_colors() adds information, perhaps partially
repeating already-known facts, but also (hopefully) adding new
information that helps restrict the possible answers.
The list all_info contains one sublist for each call to set_colors().
This task asks for a function passes_restrictions(guess, all_info)
that returns True if guess complies with all of the restrictions
currently in all_info, and False if not.
COMP10001 Foundations of Computing Week 9, Lecture 2
Task 3 – Checking Restrictions
With that function, can sketch a solution-finding program as:
all_info = []
nguesses = 0
while True:
gcount = 0
# iterate a controlled number of times to try and find
# a guess that complies with the information that has
# been built up
while True:
new_guess = create_guess(all_info , difficulty)
COMP10001 Foundations of Computing Week 9, Lecture 2
Task 3 – Checking Restrictions
Function create_guess() tries to create a good guess, and then
passes_restrictions() decides whether it should be used. But only
GCOUNT_MAX candidates are considered before one gets used anyway.
if passes_restrictions(new_guess , all_info ):
# seems like it might be a good guess
break
gcount += 1
if gcount > GCOUNT_MAX:
# just use this guess anyway
break
COMP10001 Foundations of Computing Week 9, Lecture 2
Task 3 – Checking Restrictions
# for better or worse , now apply that latest guess
new_info = set_colors(secret , new_guess)
nguesses += 1
if all_green(new_info ):
# wow , we have the answer , party time
return (nguesses , new_guess)
else:
# didn't hit the solution , but hopefully will get
# additional information to use when generating next
# candidate
all_info.append(new_info)
Like Task 2, Task 3 can be tested deterministically. Task 1 cannot.
COMP10001 Foundations of Computing Week 9, Lecture 2
Task 4 – Candidate Generation
This task asks for a function create_guess(all_info, difficulty).
The simplest process you can consider generates candidates in which:
• all “green” labels in all_info are matched
• all “yellow” and “grey” labels at any given character position in
all_info are complied with.
As a minimum, you need to tabulate the options not excluded in each
character position, and make a random choice amongst them.
COMP10001 Foundations of Computing Week 9, Lecture 2
Task 4 – Candidate Generation
There is no requirement that you create 〈result〉s that are correct.
There is no requirement that the 〈value〉s are in the right range, or
(for example) that there are exactly two 〈operator〉s and one “=”.
>>> create_guess ([], 10)
"143%+2227 -"
>>> create_guess ([[(0, "3", "green"), (1, "+", "grey")]], 10)
"35+=14%%3="
Like Task 1, this task is non-deterministic, and involves randomness.
COMP10001 Foundations of Computing Week 9, Lecture 2
Lecture Outline
1 What Is A FoCdle?
2 The Four Tasks
3 The Bonus Marks
4 The Boring Stuff
COMP10001 Foundations of Computing Week 9, Lecture 2
Bonus Marks
Yes, you can get to 15 marks with a quite “dumb” version of
create_guess(). It just has to tabulate the available characters at
each position, and make sure it complies with the known “color”
information for that position (considered in one position at a time).
But you can keep going if you wish to have more fun!
How? That’s up to you.
COMP10001 Foundations of Computing Week 9, Lecture 2
Bonus Marks
We will measure the “precision” of any create_better_guess()
functions by “playing” a large number of random FoCdle games
(more than 100) in our test harness.
The 50 students with the lowest average values for nguesses (see the
program sketch given above) over our set of secret FoCdles will be
given 2 bonus marks, and the next 150 lowest average nguesses
programs will get one mark, provided that they do better than the
“dumb” mechanism that is the starting point.
COMP10001 Foundations of Computing Week 9, Lecture 2
Bonus Marks
The lecturers and tutors will not be providing any guidance on how to
make the create_better_guess() function – you are on your own in
this regard.
COMP10001 Foundations of Computing Week 9, Lecture 2
Bonus Marks
Are there any constraints? Absolutely YES!
1. Your create_better_guess() function must only make use of the
overall rules of FoCdles, and the information supplied via all_info;
and
2. Your function must execute sufficiently quickly that when we use it
we’ll be able to solve more than 100 FoCdles (involving perhaps 1000
calls to your function) within a few seconds of computation time (and
within any other resource limits imposed by Grok).
Game on? (Or game off, that’s also ok!)
COMP10001 Foundations of Computing Week 9, Lecture 2
Lecture Outline
1 What Is A FoCdle?
2 The Four Tasks
3 The Bonus Marks
4 The Boring Stuff
COMP10001 Foundations of Computing Week 9, Lecture 2
The Boring Stuff
As with Project 1:
• This is an individual assessment
• The material submitted must be your own unassisted work
• Don’t give anyone your code before the marks are released
• You must not make use of AI services such as ChatGPT, and
must not solicit solutions from programming and “tutoring” sites
• Deadline: 6pm Friday 19 May
• Special Consideration requests:
comp10001-semester1@unimelb.edu.au