ptnega's technical blog

Interpretation of binary searching algorithm

Problem: Given a random number in range [a, b] (inclusive). What is the maximum number of reasonable attempt the player has to make to get the number?

Let’s start with a more familiar problem: You’ve lost your cow on a rectangular grassland. Assume that the cow is at a fixed position on the land. How would you look for your cow?

This is my idea to find mine if I’m in that situation:

  1. Divide the land by 2, search for the 1st half.
    1. If the cow is there, I search no more.
    2. If it’s not, I will search in the 2nd half. But I will NOT search the whole 2nd half.
      1. I divide it by 2 (again) and search for the 1st new half. If the cow’s there, I search no more,
      2. and if it’s not, I will do the exactly same thing as I’ve done in the previous step.
      3. I will do this again and again until I find my cow. The searching ends when the line I used to divide the land is duplicated with one of those I’ve made in the previous steps. My cow will be on that line 😀

Do you see something that I’ve done the same in each step? Divide the land by 2. It’s exactly the concept of binary searching, that’s why they call it *binary* 😀

Each time you divide the range of searching by 2, you also reduce the time of searching by 2. If your answer is not in this half, then it must be in the other half! The searching ends when you cannot divide the searching range anymore. In other words, “Thisrange” / 2 = “Thisrange” so Thisrange must be zero (You search no more :D)

Each time you divide the range by 2, thus the number of attempts you’ve made is about log2(Range). More specific to say, the number of attempts equals to [log2(Range)] + 1 with [x] is the integral part of x. 2 ^ [log2(Range)] does not guarantee that you’ve searched all in the range. Since you cannot make “half of an attempt” or “quarter of an attempt”, you need to add 1 to your number of attempts.

Of course, that is the answer to the worst case that you need to run to every corner of the land to find your cow. If you’re a bit lucky, you are likely to find your cow in even 3, 2 or just 1 attempt.

To sum up, the maximum number of attempts you need to make to find a random number in range [a, b] is: [log2(b – a + 1)] + 1.

 

Leave a comment »

Installing Wine on Ubuntu 15.10

In this post, I will show you different ways of installing Wine on Ubuntu, and in my tutorial, I’m using Ubuntu 15.10.

A. Installing in the simplest and most common way

  1. Using the command line

In Ubuntu, open a Terminal using the shortcut Ctrl + Alt + T then type the following command:

sudo apt-get install wine

You can also press the [Tab] key to see more options, like this:

Screenshot from 2015-12-25 23-54-13

You can change the “wine” parameter in the command above to “wine1.4” or “wine1.6”. It depends on which version of Wine you want to install.

By default, just leave it “wine” and hit [Enter]. You will then be asked to provide your password, just type it (it is not visible) and hit [Enter] one more time to start the installation.

Screenshot from 2015-12-26 00-48-46

2. Using the Ubuntu Software Center

Firstly, search for the Ubuntu Software Center

Screenshot from 2015-12-26 00-11-10

Then, search for Wine

Screenshot from 2015-12-26 00-12-01

Click on the Install button as shown in the picture above. Then, you’ll be asked to provide your password. Type in in the box and hit [Enter] to start the installation.

B. Installing using a PPA Repository

There are two main steps to install Wine in this way. I’ll guide you through them.

  1. Adding the PPA Repository
  • Using the command line

Open the Terminal and type the following command:

sudo add-apt-repository ppa:ubuntu-wine/ppa

You will be asked for your password and your confirmation of adding the repository. Type your password and hit [Enter] to continue.

Screenshot from 2015-12-26 01-25-48

After adding the repo, you need to update the APT package information:

sudo apt-get update

Screenshot from 2015-12-26 01-28-29

  • Using the User Interface

Search for the Software and UpdatesScreenshot from 2015-12-26 00-11-10

Navigate to the Other Sofwares tab:

Screenshot from 2015-12-26 00-13-05

Click on the Add.. button and then paste the line below to the box:

ppa:ubuntu-wine/ppa

Screenshot from 2015-12-26 00-12-55

Click Add Source and close the window. You will be prompted to update the APT package information.

Screenshot from 2015-12-26 00-13-09

Click Reload and… wait for it 😀

Screenshot from 2015-12-26 00-13-12

Now, you’ve done adding the PPA repository. Let’s move on to the next step.

2. Installing Wine using command line

Open a Terminal window and type the following command:

sudo apt-get install wine

This time, let’s press [Tab] to see if there’s any difference:

Screenshot from 2015-12-25 23-55-56

Notice the differences? We now have even more options than before. Here we’ve got the newest version – wine1.8. And this means that using a PPA Repository provides you the lastest version of Wine.

This time, I replaced “wine” in the command by “wine1.8”

I didn’t encountered any errors during the installation:

Screenshot from 2015-12-26 00-04-34

Screenshot from 2015-12-26 00-07-37

And done!

Screenshot from 2015-12-26 00-08-08

The first time you run Wine, you will be asked to install Wine-mono and Wine-gecko. Just click Install and everything will be okay.

Screenshot from 2015-12-26 00-09-00

Hope you find my tutorial useful. If you encounter any problems during the installation, let me know in the comments.

Leave a comment »

How to set up fossasia.github.io locally using Jekyll

In this post, I’ll show you how to set up fossasia.github.io locally using Jekyll. This post is for this Google Code-in 2014 task from FOSSASIA:

https://www.google-melange.com/gci/task/view/google/gci2014/5794409786376192

So, these are what you need to run this site locally on your machine:

1. Jekyll data files of the site. You can find it in its github repository.

2. Jekyll, of course 🙂

Let’s start!

1. How to get Jekyll data files of the site?

There are two ways to get the repository on your computer.

a. You can download a zip file contains all the files you need:

Screenshot from 2015-01-11 11:49:14

Extract the zip file and you will have the data you need.

b. You can also clone the repository from github:

You can fork the repo or not. It’s optional. To fork the repo, click the button on the top-right corner of the page:

Screenshot from 2015-01-11 11:49:14

Here, I didn’t fork the repo to my account.I cloned it directly from fossasia using this command:

git clone https://github.com/fossasia/fossasia.github.io

Screenshot from 2015-01-11 11:39:07

It will be easy to sync my local repo on the machine with the one from fossasia. If you clone the forked one, use this command instead:

git clone https://github.com/yourusername/fossasia.github.io

To get updates from the owner of the repo, follow the instruction here: https://help.github.com/articles/syncing-a-fork/

Use this command to get into your workspace:

cd fossasia.github.io

You had your data files. Let’s setup Jekyll!

2. How to setup Jekyll?

To have Jekyll installed on your machine, you need some requirements:

– Ruby >= 1.9.2 (I encountered problem with Ruby’s version and found this requirement. I haven’t read the instruction very much, just installed Jekyll my myself)

– Rubygems, you had “gem” when you installed Ruby 😀

– NodeJS, or another JavaScript runtime (for CoffeeScript support)

Last but not least: Linux, or Mac OS X. I’m using Ubuntu 14.04 LTS.

Here’s how I installed Jekyll:

a. Installing ruby and get ‘gem’

The first time I read the task, I made a mistake, silly mistake. I “installed Jekyll using apt-get” (You know, “sudo apt-get install jekyll”, can’t help laughing at myself). In this task, Jekyll can’t be installed using that command. You should install Jekyll using rubygems. So, firstly, I installed ruby using this command:

sudo apt-get install ruby1.9.3

Screenshot from 2015-01-10 23:35:28

Actually, I had installed jekyll before working on this task. So I had to remove all the requirements, and uninstall jekyll to get those screenshots 😀 Absent-minded… As I said, I had problem with ruby when install Jekyll using ‘gem’. You need ruby with version >= 1.9.2 to go through the installation. I’m sorry for not having the screenshot of that error here.

I don’t know if other users meet this problem. You can leave comment here to make this problem clear 😀

I check my ruby version using this command:

ruby -v

Screenshot from 2015-01-10 23:35:41

Ah, now I have ruby1.9.3 installed 😀 both ‘gem’ and ruby 😀

Let’s get to the next step.

b. Installing JavaScript Runtime

I use NodeJS as JavaScript runtime. A very familiar command to us:

sudo apt-get install nodejs

Screenshot from 2015-01-10 23:36:39

I had no trouble in installing nodejs.

Now I had all the requirements. The final step to install jekyll, is “using gem to install Jekyll” 😀

The first time I use gem to install Jekyll, I met this message:

ERROR: While executing gem … (Gem::FilePermissionError)
You don’t have write permissions into the /var/lib/gems/1.9.1 directory.

Screenshot from 2015-01-11 13:02:19

It’s because I didn’t run this command as root. So add “sudo” to the beginning of the command to solve this problem 🙂

Another look at that error. As I said before, I met problem with ruby version but don’t have screenshot here. I found it’s strange that the command requires permissions for /var/lib/gems/1.9.1 directory, but I get error for not having ruby1.9.3 (!?) I think I need some more comments from other users.

This time I run the command without geting any errors:

Screenshot from 2015-01-10 23:53:01

Now you had Jekyll installed on your computer 🙂

How I run fossasia.github.io locally on my machine?

– Go into the fossasia.github.io folder you cloned or extracted in the 1st step.

– Simply run this command:

jekyll serve

Screenshot from 2015-01-11 13:28:47

Then I opened my browser: localhost:4000. Here the result:

Screenshot from 2015-01-10 23:55:14

Screenshot from 2015-01-10 23:55:21

Screenshot from 2015-01-10 23:55:28

Screenshot from 2015-01-10 23:55:43

Screenshot from 2015-01-10 23:55:52

“IT’S WORKING, YAYYYYYY…”

I was so excited then… Because the biggest problem I faced through the installation, is the speed of Internet. I’m from Vietnam, and the AAG (Asia-America Gateway) cable, which is the main cable of our region, has broken since 5/1/2015. It’s being fixed, and hasn’t done yet. I had to keep my machine on for a long time just to install the requirements, or download something, or just google something. Every activity takes time because of slow Internet 😦

I also met difficulties about “dependencies” while using apt-get. But it didn’t last long. I just used some familiar command such as: “sudo apt-get -f install”, …

Sometimes, when I had to wait during the installation, I played the guitar. It’s interesting and relaxing. You may want to try 😀

Moving to Jekyll has advantages. These are what I think:

– It’s simple to run the website with HTML files.

– No database, just static parts loaded. So, more security.

– Easier to contribute to the website. You can make changes on your own repo, run for a test, and ask the owner of the site for changes.

– Using markdown, so easy to change things.

Hope you enjoy my “experience”. Thanks for reading 🙂

And… sorry for my bad English.

Leave a comment »