The Drawing Book Algorithm 📖📖

In this article, I'll be describing how I solved the Drawing Book Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

If this is your first time reading my data structures and algorithms article, please consider reading more in my Algos in Plain English series.😃

Problem 🎲

A teacher asks the class to open their books to a page number. A student can either start turning pages from the front of the book or from the back of the book. They always turn pages one at a time. When they open the book, page 1 is always on the right side:

When they flip page 1, they see pages 2 and 3. Each page except the last page will always be printed on both sides. The last page may only be printed on the front, given the length of the book. If the book is n pages long, and a student wants to turn to page p, what is the minimum number of pages to turn? They can start at the beginning or the end of the book.

Given n and p , find and print the minimum number of pages that must be turned in order to arrive at page p .

Example

n = 5

p = 3

Using the diagram above, if the student wants to get to page 3 , they open the book to page 1, flip 1 page and they are on the correct page. If they open the book to the last page, page 5, they turn 1 page and are at the correct page. Return 1.

Function Description

Complete the pageCount function in the editor below. pageCount has the following parameter(s):

• int n: the number of pages in the book
• int p: the page number to turn to

Returns

• int: the minimum number of pages to turn

Samle Input 0:

Samle Output 0:

Explanation:

If the student starts turning from page 1, they only need to turn 1 page:

If a student starts turning from page 6, they need to turn 2 pages:

Return the minimum value, 1.

Solution 🔎

In plain English, we are given a book with n pages, and a page p to turn to. We need to count how many page turns it'll take to get to page p, flipping from beginning or the end of book, and return the smallest number of turns.

Please see the Sample Input with diagrams for a better understanding of the problem.

I thought this challenge was interesting because it's one of those real world problems that can be translated to a programming problem. Being able to think about this translation is very important for a programmer, because most real world problems are generally unstructured, so you can only code out the problem after you have translated it.🙂

To test our solution, let's consider a different sample input.

A 5 page book, and we are expected to flip to page 4.

The expected output is:

So let's begin!

Step 1️⃣: Convert the Drawing Book to a List of Sublists.📖

To translate this problem, we'll start by converting our book to a List of sublists, where each sublist represents a pair of pages.

Our goal in this step is to translate the image above into [ [0, 1], [2, 3], [4, 5], ]

1. Before we can get a List of sublists, we'll first need to create a List containing all pages up to n. We'll store the result in an all_pages variable.

    all_pages = [i for i in range(0, n+1) ] 
    # [0, 1, 2, 3, 4, 5]
   

2. Next, we'll create the sublists by slicing all_pages list, and store it in page_set.

    page_set  = [ all_pages[i : i+2] for i in range(0, n+1, 2)]
    # [[0, 1], [2, 3], [4, 5]]
   

Step 2️⃣: Loop through the sublists to find page p.

Before we start looping, we'll create three variables:

• forward_counter: an integer for counting the number of page turns from the beginning of the book.
• backward_counter: an integer for counting the number of page turns from the end of the book.
• result: a List for storing the forward_counter and backward_counter counters.

1. We need to get the number of page turns when flipping from the beginning and end of the book.
2. So we'll loop through the sublists page_set while checking if the given page number p is contained in any given sublist.
3. If p is not found in a given sublist, we'll update forward_counter when looping forward or the backward_counter while looping from the end.
4. We can loop backwards by calling reversed() on page_set. Calling reversed on the list of sublists doesn't create a new list, but instead creates a reverse iterator and allows us to iterate in reverse.

5. Once p is found, we'll end the iteration and break out of the forward and backward loops.

    for page in page_set:
        if p in page:
            break
        else:
            forward_counter += 1
   
    for page in reversed(page_set):
        if p in page:
            break
        else:
            backward_counter += 1
   

Step 3️⃣: Return the minimum number of pages to turn.

All we need to do here is return the smaller of the two counters: forward_counter and backward_counter.

We do this by appending both counters to a new list called result and returning the minimum.

    result.append(forward_counter)    # [2]
    result.append(backward_counter)    # [2, 0]

    return min(result)
    # 0

Step 4️⃣: Putting it all together.⚙️⚙️

Full code:

def pageCount(n, p):
    # Write your code here
    forward_counter = 0
    backward_counter = 0
    result = []


    all_pages = [i for i in range(0, n+1) ]

    page_set  = [ all_pages[i : i+2] for i in range(0, n+1, 2)]

    for page in page_set:
        if p in page:
            break
        else:
            forward_counter += 1

    for page in reversed(page_set):
        if p in page:
            break
        else:
            backward_counter += 1

    result.append(forward_counter)
    result.append(backward_counter)

    return min(result)

pageCount(5, 4)
# 0

Hope this article helped with understanding this challenge. Happy Coding!👨🏽‍💻