Luet oppimateriaalin englanninkielistä versiota. Mainitsit kuitenkin taustakyselyssä
osaavasi suomea. Siksi suosittelemme, että käytät suomenkielistä versiota, joka on
testatumpi ja hieman laajempi ja muutenkin mukava.
Suomenkielinen materiaali kyllä esittelee englanninkielisetkin termit.
Kieli vaihtuu A+:n sivujen yläreunan painikkeesta. Tai tästä: Vaihda suomeksi.
About This Page
Questions Answered: What higher-order methods do Strings have?
Can I write an algorithm that operates on strings? My friend claims
to be good at Hangman; how can I teach them a lesson?
Topics: Additional practice on implementing algorithms, strings,
Maps, and higher-order methods.
What Will I Do? Program, once you work out what the program is
supposed to do. A single programming assignment makes up most of
Rough Estimate of Workload:? Five hours? You don’t need to
write a great amount of code, but it will take time to get to know
the program’s domain, come up with a solution, translate the solution
into code, and test the program. Don’t get stuck; ask for help.
Points Available: C90.
Related Modules: Peeveli (new).
The facts listed below should be already familiar. Revisit the earlier chapters or the
Scala Reference for details as needed.
Collections such as buffers and vectors have many first-order
methods (such as take, contains, and indexOf; Chapter 4.2)
and higher-order methods (such as filter, map, and maxBy;
Chapters 6.3, 7.1, and 10.1).
Strings consist of elements of type Char, each of which
represents a single letter or other character (Chapter 5.2).
Strings have many methods that are specific to string
processing (such as trim and toUpperCase; Chapter 5.2).
Strings are objects; they are collections with characters as
elements (Chapter 5.2). The things you can do with a collection,
such as loop over it with for, you can also do with a String
Strings share many first-order methods with other collections
(such as take, contains, and indexOf; Chapter 5.2).
Now, knowing that Strings are collections, it’s natural that they too have
higher-order methods, many of which you already know.
Let’s use foreach to print each of a string’s elements (characters):
Now let’s take a longer string and filter out everything but lower-case letters. We’ll
be assisted by the isLower method on Chars:
"Let's offroad!".filter( _.isLower )res0: String = etsoffroad
sorted sorts characters as per their natural ordering (Chapter 10.1), which is defined
"Let's offroad!".sortedres1: String = " !'Ladeffoorst"
In Unicode, the upper-case alphabet comes before
the lower-case one.
With sortBy, we can — for instance — sort the letters by their lower-case
"Let's offroad!".sortBy( _.toLower )res2: String = " !'adeffLoorst"
Calling toLower on a Char produces its lower-case version.
Observe the difference between this output and the earlier one.
The map method constructs its return value by applying its parameter function to each
character in the string. Here are a couple of examples:
"Let's offroad!".map( char => if char.isLower then char.toUpper else char.toLower )res3: String = lET'S OFFROAD!
"Hi!".map( _.isLower )res4: IndexedSeq[Boolean] = Vector(false, true, false)
A, I, and N have been correctly guessed. Five guesses have missed
the mark, so the riddler has drawn a stick figure with 1) a head,
2) a body, 3, 4) two arms, and 5) a leg. The next incorrect guess
means the second leg is drawn and the guesser loses.
Hangman is a classic word game for two: one player — the riddler — picks a word
and the other player — the guesser — tries to figure out what the word is, guessing
one letter at a time. The length of the word is known to both players. Each time the
guesser picks a letter, the riddler must reveal all those positions in the target word
where that letter appears. If the letter doesn’t appear in the target word at all, the
guess is a miss and the riddler draws an additional element into a line drawing of a
hanging stick figure.
If the guesser misses a few times, the drawing will be completed and the guesser loses
the game. The guesser wins in case they manage to reveal the entire word.
That’s pretty much all there is to it, but you can read up on the game in Wikipedia if you like. Hangman will probably
remind some readers of Wordle <https://en.wikipedia.org/wiki/Wordle>_, a game that
went viral in December 2021 and is something like a cross between Hangman and Mastermind.
There are many digital variants of Hangman in which the computer takes the role of the
riddler and the human player is the guesser. Just like the traditional pen-and-paper
version, these variants are based on the premise that the guesser can trust the riddler.
Our take on Hangman is different. In the game we’re about to program, the riddler
is something called Peeveli, and it doesn’t play fair.
In a regular game of Hangman, the riddler picks the target word at the start of the
game and scrupulously reveals letters as the correct answers accumulate. But what if
the riddler wasn’t trustworthy?
Imagine the scene. The game has just started, you are the guesser, and the riddler
has just — unbeknownst to you — picked the target word BAZAAR. The concealed word
initially looks like this:
_ _ _ _ _ _
If you now guess A, the riddler should reveal three copies of that letter. But they could
instead mentally switch their original target word for an A-less one — BELIEF is an
example — and inform you that there is no A and your guess is a miss.
Imagine another scene. You’ve managed to guess all but one of the letters in this
five-letter word, but the next incorrect guess with lose you the game.
_ A S I S
Suppose you haven’t guessed the letters B and O yet. There are only two possible answers:
BASIS and OASIS. However, if you pick B, the riddler can claim they were thinking of
OASIS, and vice versa. You can’t beat the dishonest riddler!
In the game of Peeveli, the computer is the riddler and the human player is the
guesser. The game is challenging because the computer cheats methodically. It uses a vast
vocabulary in combination with a devious algorithm: it doesn’t actually pick a target
word at all, instead keeping track of all the existing words that continue to be plausible
correct solutions, given the previous guesses and the letters already revealed as a
consequence. Whenever the player guesses a letter, Peeveli tries to keep its options
open: it selects which (if any) letters to reveal so that there are as many potential
solutions left as possible.
Imagine a scenario with you as the riddler. The target word is supposed to have four
letters. Further imagine that there are no four-letter words in English apart from the ten
listed below. The target word must therefore be one of those ten.
ALSO AREA AUNT GURU HAWK IDEA JUJU PLAY TUNA ZERO
Your opponent’s first guess is the letter A. What should you do?
First, you should see where the A’s appear in the list of known four-letter words.
ALSO AREA AUNT GURU HAWK IDEA JUJU PLAY TUNA ZERO
Now you can identify a few groups of words with different patterns of A’s in them:
Begins and ends with an A.
One A as the first letter.
One A as the second letter.
One A as the third letter.
One A as the last letter.
No A’s at all.
GURU, JUJU, ZERO
This basically means that you need to pick one of six alternatives. A good basic strategy
is to pick the largest group, which in this instance is the last one. So you inform your
opponent that the word has no A’s and memorize the fact that there are three plausible
solutions left: GURU, JUJU, and ZERO.
If the vocabulary had additionally contained APEX and ARMY, which begin with an A, the
group A___ would have been the largest. In that scenario, you would have revealed the
initial A and memorized the plausible solutions ALSO, APEX, ARMY, and AUNT.
Suppose you’ve chosen the group with GURU, JUJU, and ZERO, and your opponent’s next
guess is the letter U. This results in the groups _U_U (with GURU and JUJU) and
____ (with ZERO). The former is larger, so you tell your opponent there are U’s in
the second and fourth slots.
Whenever your opponent guesses a letter that doesn’t appear in any of the plausible
solutions, you have only a single group that encompasses all the words that remain.
Obviously, you’ll then pick that group.
Occasionally, you’ll find that there are multiple groups of equal size. In such cases,
you could pick an arbitrary group or break the tie by choosing the group that reveals the
The Peeveli game doesn’t draw a hanging figure; it tallies missed
guesses by displaying letters in red. The letters start appearing
when the player has only a small number of incorrect guesses left.
The module Peeveli contains a partial implementation of the game described above.
The GUI is in working order but the riddler is sorely lacking in smarts.
Try playing the game as given. The app object is o1.peeveli.gui.PeeveliApp.
You’ll notice several things:
The riddler is really lenient, not at all
what we intended. It accepts all guesses
and always reveals one more letter of the
target word on each guess.
The game doesn’t end when it should.
You can change vocabularies in the menu.
You can enable a testing mode where Peeveli
uses the text console to print out all the
remaining plausible solutions after each
guess. (The given riddler meekly prunes down
the list to just one solution, though.)
Study the module’s Scaladocs and program code.
Implement the missing parts that make Peeveli work as cleverly as
we planned above.
In the above description of Peeveli’s algorithm, we mentioned that
when word groups are equal in size, it might be a good idea to
pick the group that reveals fewer letters to the guesser. That is
completely optional in this assignment. Implement that additional
bit of devilry only if you want an additional challenge. Otherwise,
just pick any of the equally sized groups.
You’ll need to edit only GameState.scala.
It’s a good idea to implement the private method reveal and use
it in guessLetter.
When you write literals, remember that whereas String literals
go in double quotation marks as in "myString", Char literals
such as 'c' use single quotes.
groupBy (Chapter 10.1)
A+ presents the exercise submission form here.
Assignment unavailable in English
In the Finnish edition of this ebook, there is an optional
assignment here that involves the Finnish language. This
assignment is unfortunately not available in English, as
an English version of it would make little sense. Sorry.
(The “end-of-week survey” is in this chapter already, because 10.3 is completely optional.)
Please note that this section must be completed individually.
Even if you worked on this chapter with a pair, each of you should submit the form separately.
Time spent: (*) Required
Please estimate the total number of minutes you spent on this chapter (reading, assignments,
etc.). You don’t have to be exact, but if you can produce an estimate to within 15 minutes or
half an hour, that would be great.
Written comment or question:
You aren’t required to give written feedback. Nevertheless, please
do ask something, give feedback, or reflect on your learning!
(However, the right place to ask urgent questions about programs
that you’re currently working on isn’t this form but the lab sessions
or Piazza. We can’t guarantee that anyone will even see anything
you type here before the weekly deadline.)
The additional questions below concern the past O1 Week (whose last
chapter this is) as a whole. Answering these questions is not mandatory,
but we hope that you do. In any case, please remember to submit this
form; the button is down there.
Your answers will be accessible by the course staff. We’ll combine the
answers of all O1 students to compute (anonymous) statistics that will help
us improve the course and to research programming education. We are grateful
for your patience in answering these questions!
The past Week of O1 (i.e., the chapters with their assignments) was fun to do.
1 — not at all true
7 — completely true
no answer / skip question
I would describe the past Week as very interesting.
I felt pressured while doing the past Week.
During the Week, I felt that I wanted to learn more about the topic.
I had to force myself to do this Week’s activities.
I did not feel nervous at all while doing the past Week.
I thought the past Week was boring.
I felt very tense while doing the past Week.
I thought the past Week was quite enjoyable.
While I was working on the past Week, I was thinking about how much I enjoyed it.
The contents of the Week felt exciting.
I was very relaxed in doing the past Week.
The past Week did not hold my attention at all.
During this Week, I did some tasks in order to avoid feeling badly about myself.
I very much enjoyed O1 during the past Week.
I was anxious while working on the past Week.
Comparing the past Week of O1 to my other studies, I’ve been feeling...
1 — much less pressure from O1 than from other courses
4 — equal pressure from O1 and other courses
7 — much more pressure from O1 than from other courses
Comparing the past Week of O1 to my other studies, I’ve been...
1 — much less stressed about O1 than about other courses
4 — equally stressed about O1 and other courses
7 — much more stressed about O1 than about other courses
During the past Week, I felt interested in my other, non-O1 studies (regardless of what I thought of O1).
I enjoyed the past Week of O1 more than I enjoyed my other studies during the same time.
Thousands of students have given feedback and so contributed to this ebook’s design.
The ebook’s chapters, programming assignments, and weekly bulletins have been written in
Finnish and translated into English by Juha Sorva.
The appendices (glossary, Scala reference,
FAQ, etc.) are by Juha Sorva unless otherwise specified on the page.
The automatic assessment of the assignments has been developed by: (in alphabetical order)
Riku Autio, Nikolas Drosdek, Joonatan Honkamaa, Antti Immonen, Jaakko Kantojärvi, Niklas
Kröger, Kalle Laitinen, Teemu Lehtinen, Jaakko Nakaza, Strasdosky Otewa, Timi Seppälä,
Teemu Sirkiä, Anna Valldeoriola Cardó, and Aleksi Vartiainen.
The illustrations at the top of each chapter, and the similar drawings elsewhere in the
ebook, are the work of Christina Lassheikki.
The animations that detail the execution Scala programs have been designed by Juha
Sorva and Teemu Sirkiä. Teemu Sirkiä and Riku Autio did the technical implementation,
relying on Teemu’s Jsvee and Kelmu toolkits.
The other diagrams and interactive presentations in the ebook are by Juha Sorva.
The O1Library software
has been developed by Aleksi Lukkarinen and Juha Sorva. Several of its key components
are built upon Aleksi’s SMCL
The pedagogy of using O1Library for simple graphical programming (such as Pic) is
inspired by the textbooks How to Design Programs by Flatt, Felleisen, Findler, and
Krishnamurthi and Picturing Programs by Stephen Bloch.
The course platform A+ was originally created at Aalto’s LeTech
research group as a student project. The open-source project
is now shepherded by the Computer Science department’s edu-tech team and hosted by the department’s IT
Markku Riekkinen is the current lead developer; dozens of Aalto students and others have also contributed.
The A+ Courses plugin,
which supports A+ and O1 in IntelliJ IDEA, is another open-source project. It has been designed and
implemented by various students
in collaboration with O1’s teachers.
For O1’s current teaching staff, please see Chapter 1.1.
Peeveli is a derivative of a similar programming assignment designed by Keith Schwarz.
In Unicode, the upper-case alphabet comes before the lower-case one.