Bạn có chắc chắn muốn xóa bài viết này không ?
Problem Solving - Essential Skill for Developers
Hi guys, as you already know, problem solving is one of the indispensable skills that developers and software engineers need to possess nowadays. We need to practice this skill regularly to be well-prepared for problems that may arise from our job in the future. However, I have recognized that not many schools and universities in Vietnam focus on improving problem-solving skill of their students.
I started studying at University of Wollongong, Australia six months ago. In my first semester, I had to take a subject which is called "Problem Solving". In the subject, I was introduced to a broad range of problems, and I also had a lot of opportunities to solve problems myself. At first, it was very hard as I was not used to solving problems in high school. (In high school, I solved Math problems by memorizing the formula ). However, after consitently practicing solving problems, my skill was enhanced significantly.
Therefore, I reckon it would be great if I can help the developer community by putting some of the problems that I learnt on this post so you can practice as well. Below are some of the problems that might be interesting to solve as a way to entertain yourself after a day of hard work .
All problems were constructed by Dr. Ian Piper - University of Wollongong, Australia.
For this post, there is no prerequisite. Surprise, surprise . You don't have to memorize any Mathematical formulas or know anything in advance to solve the following problems. Although these problems might seem pretty simple and easy to understand, some are very hard to solve.
I will not give the answers to you guys directly as it would be better if you can solve these problems by your self first. If you have any questions just comment below and I will check this post regularly to assist you guys.
Give it a go and have fun solving problems
(Note: The problems can be solved in many different ways as @Joe has pointed out (Sociological, Psychological, Political, Technological, Logic).)
Problem 1 - River Crossing
Four people, Alice, Bob, Carol and Dave are travelling at night along a road when they come to a bridge over a river.
The river is too wide and flows too fast to safely cross other than go over the bridge which is narrow and unfenced.
At most two people can cross the bridge together.
The group has a single torch and it is not safe to cross the bridge without carrying the torch.
If two people cross together, they will travel at the speed of the slower person.
The problem is to find a way to get the entire group across the river as quickly as possible.
- Alice: 1 minute
- Bob: 3 minutes
- Carol: 4 minutes
- Dave: 10 minutes
You have a bag with three types of object in it.
Each turn you remove 2 objects of different types and replace them with an object of the third type. (You are allowed to look in the bag when you are taking things out)
For what starting conditions can we finish with exactly one object in the bag?
Problem 3 - River Crossing 2
Three couples (husband and wife) wish to cross a river using a small boat.
Only two people will fit in the boat at a time.
Each husband is too jealous to leave his wife with another man.
Get everyone safely across the river
You have an old fashioned balance scale.
You also have 5 weights, each an integer number of kg.
You need to be able to weigh objects to the nearest kg.
What is the largest object you can weigh?
Remember: With your five weights, you must be able to weigh every object whose weight is lower than your largest object. For example, if your largest object is 100kg, you must be able to weigh all objects from 1kg, 2kg, 3kg, ..., up to 100kg.
Hint: For example, my 5 weights are 1kg, 2kg, 3kg, 4kg, 5kg. Then I am able to weigh objects of 1kg, 2kg, 3kg, 4kg, 5kg, 6kg (by putting 1kg & 5kg weights on one side and the object on the other side), 7kg, ...., 15kg (all 5 weights on one side, object on the other side).
Problem 5 - Tetrominoes
a) If a rectangular board is completely covered with tetrominoes show that at least one side must be of even length.
b) If a rectangular board can be completely covered by T tetrominoes show that the number of squares on the board must be a multiple of 8.
c) If a rectangular board can be completely covered by L tetrominoes show that the number of squares on the board must be a multiple of 8.
Problem 6 - Matchstick Game
We have one pile of matches. Two players take it in turn to remove matches according to the rules. The winner is the player who takes the last match.
- First move must leave at least one match (If there are 10 matches in the beginning, you can only take at most 9 matches)
- Each player can take any number of matches from 1 to 2n where n is the last player move.
What is the strategy to win this game?
Problem 7 - Knight and Knaves
Every inhabitant of a mythical island is either a knight or a knave
Knight always tell the truth
Knaves always lie
There are three natives, A, B and C.
A says "B and C are of the same type".
What question can we ask C to find out if A is telling the truth?
Problem 8 - Logic
Find the implication of the following group of statements.
The only animals in this house are cats.
Every animal is suitable for a pet, that loves to gaze at the moon.
When I detest an animal, I avoid it.
No animals are carnivorous, unless they prowl at night.
No cat fails to kill mice.
No animals ever take to me, except what are in this house.
Kangaroos are not suitable for pets.
None but carnivora kill mice.
I detest animals that do not take to me.
Animals, that prowl at night, always love to gaze at the moon.
You have a supply of black and white balls.
You may arrange them in a line provided that you never place two black balls together.
You may have multiple white balls together.
For example, this is an allowed line: black-white-black.
So is this: white-black-white-white-black.
But not this: white-black-black-white.
How many ways can you arrange 0 balls? 1 ball? 2 balls? n balls? (Hint: use induction).
Prove your answer for n balls.
(Rememeber: the ordering is important. For example, white-white-black & black-white-white are two different line)
Problem 10 - Ball Breaking
We have two bowling balls and a multi storey building.
We know that if we drop a ball from a sufficiently high window it will break.
Let us define a test as the process of dropping a ball from a specific floor.
Our aim is to find out which is the lowest floor from which dropping a ball breaks it. Let's call this the critical floor.
We also want to do this with the smallest number of tests.
What is the mimimum number of tests that I need to conduct to find the critical floor in a 100-floor building?
What order should I test the floors in?
What is the highest floor you can reach with n tests?
(Hint: There are two cases to consider: Before the first ball breaks & After the first ball breaks.)
Hard question for geniuses only: What is the highest floor you can reach with n tests if you have k balls?
This puzzle involves a board with 2n + 1 spaces in a line and n white counters and n black counters.
The board is set up with the white counters to the left, the black counters to the right and a single empty space between them.
For n = 3 the set up looks like this...
The aim of the puzzle is to exchange the two colours subject to the following rules:
- White counters may only move right;
- Black counters may only move left;
- A counter may move to an adjacent empty space;
- A counter may jump over another counter of the opposite colour into an empty space.
Try to solve the problem for n=1, 2, 3. Then find a general solution algorithm that works for all n?
Consider that we have a 3 by 3 board, with 1 empty position and eight tiles, one in each of the other position. Each title is labelled with a distinct digit from 1 to 8.
The objective is to move from a given initial state to a goal state.
The only moves allowed are to move a tile adjacent to the current empty position, into the empty position.
Try to solve the problem above then look at the following initial state.
Is the following tile puzzle solvable?
If it is, show me the solution; if not, prove it
Problem 13 - Pirate Democracy
Consider n pirates, ordered by toughness:
- P1 < P2 < ... < Pn-1 < Pn
- where Pi < Pj indicates that pirate i is weaker than pirate j.
The pirates have, as a group, obtained 100 gold coins.
The toughest pirate gets to propose how the coins should be divided amongst them.
Each pirate votes,
against, the proposed distribution of coins.
If a majority votes in favour, then the division proposal stands.
If there is a draw, the toughest pirate Pn gets the casting vote so it still stands.
However, if less than half of the pirates vote in favour, Pn is made to walk the plank.
- Pirates like killing people
- But they like gold more!
What distribution should the toughest pirate propose to maximize his/her gains?
- How does this vary as a function of n?
Priates really like gold so if they think they will get more gold, they will vote
Pirates like killing people. So, if they think they would get the same amount of gold, they will vote
There doesn't have to be anything 'fair' about the proposed division, it just has to get enough votes.
Try to solve the problem for 1, 2, 3, ... pirates. Find the pattern.
Eventually there will be nothing more for the toughest pirate to give away but he can still keep his life. Identify the dead positions & survive positions from then on. (For example, if there are 315 pirates, will the toughest pirate survive? )
(Hint: At some point the toughest pirate will get some support from pirates who aren't being given gold, simply because it means they get to live)
Near the Knight & Knaves island there is Red & Blue island.
222 'perfectly' logical people inhabit Red & Blue island
Each has a Blue or Red spot on the back of their head.
The Red & Blue islanders have no mirrors and never discuss spot colours.
Nobody knows the colour of their own spot, but they can see the colour of everyone else's.
Each morning everyone on the island gathers in the public meeting place at 6 a.m.
- Strict custom, which is always followed, dictates that anyone who has determined the colour of their spot must declare this and leave forever.
- They otherwise never leave
One day a rude tourist visits and announces at the morning gathering:
I can see that at least one of you has red spot
The tourist leaves and returns a year later. There is nobody on the island.
What has happened? (Assume the tourist tells the truth)
A large block of cheese on the ISS is cut into a 3x3x3 grid of subcubes which looks like a rubic.
A space mouse starts eating one corner, and moves on to adjacent pieces until they are all eaten. Could the mouse eat the center piece last? Prove your answer.
(Adjacency is direct: horizontal or vertical, diagonal moves are not allowed.)
In summary, I hope that you could improve your problem solving skill by conquering the above problems. By the way, don't panic if you cannot solve some of the problems, they are very tricky. I was struggling when I tried to solve those problems too. The thing is you have a chance to practice. Anyway, hopefully this post is helpful and I will see you soon in my next post . Cheers!