Efficient Problem Solving
Lesson Objective
In this lesson we will be dealing with a structured way of approaching programming questions and solving them efficiently. We will learn about the various methodologies and techniques used to get the right approach towards solving a question by simply discussing a problem of getting the shortest path in the puzzle. This is a self-paced class.
Why do we need to solve a problem efficiently?
Today's world has countless computer softwares that help us in getting any task done in an instant. They are made up of many small and big programs that come together to make up the software. Have you ever wondered what these programs would be and how they all connected to one another? Our general thinking when facing a problem is often based on the brute force approach. A software written using the brute force approach would take minutes to hours, to complete a simple task which can be done in seconds.
Remember 💡 Solving a programming problem efficiently is much more important rather than just solving it. Our aim should be achieving the goal with efficiency rather than simply achieving it any way possible.
💭 💭 What is the difference between efficiency and effectiveness?
Introduction to the Lesson
Today, we will be working on three topics:
- Cut Hive Puzzles
- Algorithmic Patterns
- Bakuro Puzzles
All these topics will help you to understand the concept of efficient problem solving and make thinking about these topics fun and interesting.
Let’s run and try some crazy fun puzzles now!
Source: scooby doo running GIF - Find & Share on GIPHY
Cut Hive Puzzles
These puzzles are inspired by the ‘Cut block’ puzzles that originate in Japan.
As the name suggests, Cut Hive Puzzles consist of a block of hexagons i.e. the ‘hive’, with different areas segregated and marked out using bold lines.
💬💬 The word area(s) will be used repetitively in the following explanation and it refers to any collection of one or more hexagons that are outlined with thick bold lines.
The following figure shows an example of a cut hive problem:
There are two important rules required to successfully solve this type of puzzle:
Rule 1: Each area must contain numbers from 1 up to the number N, where N is the total number of hexagons in the area.
For example, the topmost area in the puzzle above consists of 4 hexagons so those hexagons must be filled with the numbers: 1, 2, 3 and 4 with no repetition in the numbers.
If the bolded area has two hexagons (observe bottom left in the figure above) then it must be filled with the numbers 1 and 2.
Rule 2: No two hexagons can be filled with the same number if they share an edge along any direction. Therefore, in the grid below above since there is a 4 in the middle hexagon implies that there cannot be a 4 in any of the 5 hexagons surrounding it that share a common edge.
Problem Statement: Complete the following cut hive problem without violating the rules:
Approach
Step 1: The first and most basic approach is to select an area of hexagons enclosed in the bold lines and strictly apply rule 1 to fill numbers into the hexagons of the selected area. Make sure that you don’t violate rule 1 during this process before you move onto the next step.
Step 2: The next step is to do the same for all the other separate areas one by one.
Step 3: In this step you have to apply rule 2. Pick out a hexagon from a selected bold area and check if that hexagon shares an edge with another hexagon containing the same number. Do this for all hexagons and if this condition arises, swap that number with another number of a hexagon in the same area.
Step 4: Check whether the numbers on hexagons sharing the edges are still same or not. If they remain the same then swap it with another number. Do this until all the hexagons of the given area do not share the same number with any of the hexagons which are sharing an edge with it.
After performing these operations on all the areas we will get the desired result without violating any rules.
Alternative Efficient Approach:
Step 1: Choose a hexagon which has already been filled with a number. Now place different numbers on the hexagons that share each of the six edges of the chosen hexagon. In doing so, place each number such that it is in compliance with rule 2 as discussed above.
Perform step 1 on all pre-filled hexagons before moving on to step 2.
Step 2: Now start filling out the hexagons of a given area with numbers from 1 to X where X is the total number of hexagons of that area such that they are in compliance with rule 2 discussed above.
Both the above methods will guide you to the same solution which is shown below:
Follow up questions:
Attempt the following Cut Hive puzzles. You are given the solution after each question to help you cross-check your answers and rectify any mistakes.
Question 1:
Question 2:
Question 3:
Try exploring more such puzzles that are so widely available online. It develops your patience for trial and error that you may encounter when you face errors in your codes in the future.
Source: Mental Health GIF by mtv
Search Algorithm- Algorithmic patterns
In this topic we will be learning techniques on how to develop the most efficient algorithm for a problem by solving some interesting puzzles to keep your brain running.
These puzzles will train your brain and develop your thinking on algorithm building in the right direction.
Problem Statement:
You have been given an array of integer elements and a number in a circle. Your task is to identify whether this number is present in the array or not. If it is present then print the position of it in the array and if not then print -1.
Consider the following figure for better understanding of the question:
Intuition for the approach:
Observe the figure above. If this was assigned to you using a piece of paper and pen, what would your approach be?
You would simply spot the number to be searched for and count the position of it in the array starting from 0. We do not realise that in the process of simply spotting the number in the array, our brain is looking at each element of the array and comparing it with the number in the circle to see if they match.
If we began our search from any randomly chosen position in the array, it is inefficient and confusing to keep track of the elements already compared. You may also skip a few elements and get the incorrect result.
Approach:
We start our search and comparison from the first element of the array and move forward.
The number given in the circle is the input element to be searched for. We begin by comparing 7 with the element at the 0th index of the array.
📌📌 Remember that all arrays have their indexes values from 0 to n-1 where n is the size of the array.
The element at the 0th index is 5 which is not equal to 7. Now we increment the value of our position by 1 to reach the element at index 1 which is the number 2. Observe again that 2 ≠ 7, so we keep incrementing the position index till we encounter 7 = 7. Since 7 is at index 3, we do not need to move further and simply print the position as 3.
Follow up questions:
Try solving the questions similar to the example discussed above. It will increase your understanding on how algorithms work and guide you to think in the right direction for building up an efficient algorithm.
Question 1:
Check the Solution!
Question 2:
Check the Solution!
Question 3:
Check the Solution!
Question 4:
Check the Solution!
Question 5:
Check the Solution!
Question 6:
Check the Solution!
The first occurrence of the required number is at index 1 so we print position as 1.
Question 7:
Check the Solution!
The number to be searched for does not occur in the given array so we print its position as -1.
The above questions provided are good practice to keep your brains up and running. If you believe you need more practice on such questions, we urge you to explore further from the vast variety of questions available in books as well as the internet.
Let’s move on to the last topic of this lesson (phew!).
Bakuro Puzzles
These puzzles are binary versions of the popular Kakuro puzzle. The empty cells of the grid must be filled with the numbers 1, 2, 4, 8,16 …. and so on (i.e., only powers of 2). As is with Kakuro, in Bakuro puzzles the numbers in each block in a column or row must add up to the number given in the clue above or to the left, respectively. No number can be used twice within any sum. The clues are given in both binary and decimal form. The answers must also be written in both binary and decimal form. Here is an example along with its solution and the method to how to approach in the right direction for a given problem. You will get a better understanding of how the puzzle works when you solve the example with us. Let’s go 🚀 🚀
Problem statement:
Solve the given bakuro puzzle as shown below:
Let us start with understanding the basic logical intuition involved in solving this problem:
Intuition:
Step 1: We can deduce the answer by a simple observation that the top row adds up to 3. The only way this can be done with the numbers 1,2,4 and 8 is by performing 1 + 2.
Step 2: Now the leftmost column must add up to 9, so the numbers must be split like 1 + 8.
Step 3: In steps 1 & 2 we found out what the numbers would be split into but this was done in no particular order. Let’s look at which number falls into which cell.
The top left cell must hold a number from both those sums, which means it must be 1 (0001 in binary). Now if the top left cell holds 1, then the top right cell must hold 2 (0010 in binary) to make the row add up to 3.
Step 4: Similarly, the bottom right column must be 8 (1000 in binary) to make the leftmost column add to 9. That leaves the bottom right cell which must hold 4 as the bottom row has to add up to 12 (8 + 4). That also makes the rightmost column add to 6 as required.
And there you have it! We have successfully solved a Bakuro puzzle. As you move ahead and solve more such questions, you will see that the numbers fall into the right cells like chess pieces in a chess match.
Calculation Hint :
Binary numbers are a way of making up numbers that only consist of 0s and 1s by adding powers of 2 (1, 2, 4, 8, …) together.Similarly, decimal numbers involve adding powers of 10 (1, 10, 100, 1000) together.
❓ ❓ Have you noticed any patterns in the numbers?
The answers that go in the grid only have a single 1 in their binary representation. The binary of the clue actually tells you which numbers you are looking for. 12 is 1100 in binary which says that 12 is made up of one 8 (1000) and one 4 (0100) with no 2s and no units added together. The row must therefore hold an 8 and a 4. Similarly, 9 is 1001 in binary i.e. one 8 (1000), no 4, no 2 and one unit (0001) added together, so its column must hold an 8 and a 1.
So the solution to this looks like this:
Follow up:
Now try solving the following questions for more practice:
Question 1:
Question 2:
Question 3:
