Saturday, October 29, 2016

How to Disable Annoying Paste Function of Mouse Middle Button

If there is one thing I really hate about my current GNOME desktop environment is its default paste function mapped to the mouse middle button. This is simply so annoying that I was looking for a way to get rid of this. After some trials, I have found one that actually works very well, and I would like to share it with anyone who is also having this problem. This post is based on this and this.

First, install xinput package if already not installed.
$ sudo apt-get install -y xinput

Next, list input devices and look for your mouse:
$ xinput list | grep 'id='
⎡ Virtual core pointer                     id=2 [master pointer  (3)]
⎜   ↳ Virtual core XTEST pointer               id=4 [slave  pointer  (2)]
⎜   ↳ Microsoft Microsoft® Nano Transceiver v1.0 id=11 [slave  pointer  (2)]
⎜   ↳ Microsoft Microsoft® Nano Transceiver v1.0 id=12 [slave  pointer  (2)]
⎣ Virtual core keyboard                   id=3 [master keyboard (2)]
    ↳ Virtual core XTEST keyboard             id=5 [slave  keyboard (3)]
    ↳ Power Button                             id=6 [slave  keyboard (3)]
    ↳ Video Bus                               id=7 [slave  keyboard (3)]
...


OK, so it tells me what input devices are connected. Under Virtual core pointer, I see my Microsoft Mouse, which is mapped to 11 and 12. In my case, it was the first device:
$ xinput get-button-map 11
3 2 1 5 4 6 7 8 9 10 11 12 13

The second number represents mapping of the middle button, so I simply disable it by setting it to 0:
$ xinput set-button-map 11 3 0 1

That's it. I now confirm that the middle mouse button no longer functions! Well, I want to keep it this way all the time, so I created a script
$ echo "xinput set-button-map 11 3 0 1" > ~/disable_middle.sh
$ chmod u+x ~/disable_middle.sh

I made it execute every time GNOME starts up by creating diable-middle-button.desktop file in ~/.config/autostart/ folder with the following
[Desktop Entry]
Type=Application
Exec=~/disable_middle.sh
Hidden=false
NoDisplay=false
X-GNOME-Autostart-enabled=true
Name[en_US]=disable-middle-button
Name=disable-middle-button
Comment[en_US]=
Comment=


Now, your mouse middle button will be disable every time you start up GNOME!

Wednesday, October 26, 2016

Three Minutes Daily Vim Tip: Paste without Strange Indentation Behavior

I may have encountered a strange behavior in vim when you try to paste some codes with system-generic method (i.e., Ctrl+V) rather than vim method (i.e., yy and p). Here is how to fix it:

:set paste

This option will let vim know that you will be pasting text, and vim is to paste the text as is, without trying to auto-indent. When you are done pasting, simply set

:set nopaste

Happy vimming!

Solution to "error while loading shared libraries"

I was trying to run a  simple executable that makes use of opencv library, and I encountered an error:
$ ./a.out
./a.out: error while loading shared libraries: libopencv_shape.so.3.1: cannot open shared object file: No such file or directory

I was certainly able to locate the file manually in the proper directory:
$ find / -name libopencv_shape.so.3.1
/usr/local/lib/libopencv_shape.so.3.1

Very interesting. This is probably because I manually compiled and installed opencv3.1.0 from sources. In any case, here is the solution.

First, we need to look for the shared library path. The system dynamic linker locations are specified in /etc/ld.so.conf file, which probably includes .conf files in /etc/ld.so.conf.d/ folder. Each of the .conf files in the folder specifies the system dynamic linker locations, such as /lib/x86_64-linux-gnu.

Also, one can define the shell-variable LD_LIBRARY_PATH to include the directory of the shared library file that needs to be linked.

My case? It was a subtle. I certainly had the library folder included in one of the config files:
$ cat /etc/ld.so.conf.d/libc.conf
# libc default configuration
/usr/local/lib

Yet, I was still getting the error. Why? That's because I needed to manually load config:
$ sudo ldconfig

I guess make install command of opencv did not automatically do this. For more info, please take a look at this document. You also might be interested in loading one-time shared library files without neither of the methods above, from here.

Tuesday, October 25, 2016

Three Minutes Daily Vim Tip: Disable F1 Key

<F1> is by default mapped to vim help, but this is rather annoying, especially when I have mapped <F2> and <F3> for switching between tabs. Here is how to disable <F1> key mapping in vim.

Simply add these two lines of codes into ~/.vimrc:
nmap <F1> :echo<CR>
imap <F1> <C-o>:echo<CR>

Note: if you using GNOME, then F1 is snatched by GNOME before vim, in which case you will likely get some help menu even if you have disabled F1 from vim. IN this case, simply disable F1 from the terminal --> preferences --> shortcuts --> help --> backspace.

Sunday, October 23, 2016

How to Mark C/C++ Files in Android Studio

UPDATED: please refer to this post for much simpler way! The instruction below is officially deprecated.

There are basically two ways to link native C/C++ files in Android Studio. One way is to use CMake, and the other is to use NDK-BUILD tool. In OpenCV Android samples, it does it by NDK-BUILD tool. as you can see here. However, the problem with NDK-BUILD method is that Android Studio does not treat JNI native source files as C/C++ files; it is quite annoying to code directly in Android Studio when you don't have function-completion features or auto-syntax checks, etc.

Here, I will show you how to trick Android Studio to mark JNI native source files as C/C++ files when building with NDK-BUILD method. Basically, I will add CMake file to link C/C++ file folder for compilation so that Android Studio will mark all C/C++ files in the folder as C/C++ with correct syntax guide. For more info on adding C/C++ support in Android Studio, refer to Google's official documentation.

First, Install NDK and CMake components for your Android Studio. Also make sure that you are running Android Studio 2.2 or higher.

Locate C/C++ files that are linked with your Android project. This is probably src/main/jni folder in the app module directory. Create an empty C/C++ file in the folder: src/main/jni/empty.cpp.

Next, create CMakeLists.txt file in the app's directory with the following content:
cmake_minimum_required(VERSION 3.4.1)
add_library(native-lib
             SHARED
             src/main/jni/empty.cpp )
include_directories(/usr/include/)
include_directories(/usr/local/include/)

The last parameter should point to the newly created empty C/C++ file. Also make sure to add as many include directories as needed. 

Next, add the following lines in the app module's build.gradle file:
android {
...
    externalNativeBuild {
        cmake {
            path "CMakeLists.txt"
        }
    }
...
}

Now, sync gradle file and compile. You will notice that Android Studio now considers all C/C++ files in the src/main/jni folder as native C/C++ files. You can now directly edit your C/C++ files from Android Studio with syntax checks, method completion, etc!


Saturday, October 22, 2016

How to Restore Nexus Devices to Factory Images

I have Nexus 4 device which I do not use anymore. I decided use it for Android development. Here is how to flash/restore Nexus device to factory image. This post is basically a short-form recap of Google's official document.

Step 1, download the appropriate factory image at the right side of this webpage.

Step 2, unzip it and locate flash-all.sh file.

Step 3, restart your Android phone into fastboot mode. You can connect your Nexus and run the following command from a computer:
$ adb reboot bootloader
or use key-combos found here.

Step 4, while Nexus is connected to the computer and booted up in fastboot mode, execute flash-all.sh file from your computer as root. You need fastboot utility. If you have Android Studio installed, you already have it. Otherwise, you could download the command line SDK from here. Make sure to run with root privilege!
$ sudo ./flash-all.sh

That's it! It will automatically carry out some tasks and reboots, and restore your phone into factory image.

Thursday, October 20, 2016

Three Minutes Daily Vim Tip: Setting to Preloaded Colors

Vim comes with some color schemes. It will save some hassle if you can find one that looks good. Here is how to try them!

First, locate pre-loaded colors. Usually the files are in /usr/share/vim/vim73/colors/ directory, assuming you have vim7.4. Try
$ find / -name desert.vim 2>/dev/null

/usr/share/vim/vim73/colors/desert.vim

Now you can search the directory
$ ls /usr/share/vim/vim73/colors/*.vim
/usr/share/vim/vim73/colors/blue.vim
/usr/share/vim/vim73/colors/darkblue.vim
/usr/share/vim/vim73/colors/default.vim
/usr/share/vim/vim73/colors/delek.vim
/usr/share/vim/vim73/colors/desert.vim
/usr/share/vim/vim73/colors/elflord.vim
/usr/share/vim/vim73/colors/evening.vim
/usr/share/vim/vim73/colors/koehler.vim
/usr/share/vim/vim73/colors/morning.vim
/usr/share/vim/vim73/colors/murphy.vim
/usr/share/vim/vim73/colors/pablo.vim
/usr/share/vim/vim73/colors/peachpuff.vim
/usr/share/vim/vim73/colors/ron.vim
/usr/share/vim/vim73/colors/shine.vim
/usr/share/vim/vim73/colors/slate.vim
/usr/share/vim/vim73/colors/torte.vim
/usr/share/vim/vim73/colors/zellner.vim

In vim, set the color by
:color desert

To set it as your default color, simply do
$ echo ":color desert" >> ~/.vimrc

Enjoy vim!

Saturday, October 15, 2016

Android Studio .GITIGNORE File

This is my personal Android Studio .gitignore file:
.gradle
/.idea/workspace.xml
/.idea/libraries
.DS_Store
/build
/captures
*.apk
*.ap_
*.dex
*.class
bin/
gen/
Thumbs.db
.DS_Store
.classpath
.project
*.iml
.idea
.gradle
build/
obj/
/*/out
/*/*/build
/*/*/production
*.iws
*.ipr
*~
*.swp
*.so
*.a

How to Integrate OpenCV for Android Tutorial 2 and Tutorial 3 Modules

OpenCV Android Tutorial 2 shows how to setup JNI to import C++ native code, while Tutorial 3 shows how to control Android camera to take a picture. In this tutorial, I will go over step by step how to integrate Tutorial 2 and Tutorial 3 modules; that is, we will be building an app that will both let us import native C++ OpenCV code and control Android camera to take picture.

To me, it seems easier to integrate JNI into Tutorial 3 module, so the following will simply add JNI capability to Tutorial 3 module.

First, import Tutorial 3 module from OpenCV Android.

Next, edit openCVTutorial3CameraControl/build.gradle file to use NDK, similar to below:
import org.apache.tools.ant.taskdefs.condition.Os
apply plugin: 'com.android.application'

android {
    compileSdkVersion 22
    buildToolsVersion "24.0.3"

    defaultConfig {
        applicationId "org.opencv.samples.tutorial3"
        minSdkVersion 8
        targetSdkVersion 22

        ndk {
            moduleName "camera_control" // this is the native module name
        }
    }

    buildTypes {
        release {
            minifyEnabled false
            proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.txt'
        }
    }

    sourceSets.main {
        jniLibs.srcDir 'src/main/libs'
        jni.srcDirs = []
    }

    task ndkBuild(type: Exec) {
        if (Os.isFamily(Os.FAMILY_WINDOWS)) {
            commandLine 'ndk-build.cmd', '-C', file('src/main').absolutePath
        } else {
            commandLine '/home/linuxnme/Android/Sdk/ndk-bundle/build/ndk-build', '-C', file('src/main').absolutePath // replace with your path
        }
    }

    tasks.withType(JavaCompile) {
        compileTask -> compileTask.dependsOn ndkBuild
    }
}

dependencies {
    compile project(':openCVLibrary310')
}

Make sure to note NDK module name; in my case it is set to camera_control. Also, make sure to compile openCVLibrary with the same SdkVersion by editing the library's build.gradle file.

Next, edit Tutorial3Activity.java file to look like following:
...
public class Tutorial3Activity extends Activity implements CvCameraViewListener2, OnTouchListener {
    private static final String TAG = "OCVSample::Activity";
...
    public native void FindFeatures(long matAddrGr, long matAddrRgba);
    private BaseLoaderCallback mLoaderCallback = new BaseLoaderCallback(this) {
        @Override
        public void onManagerConnected(int status) {
            switch (status) {
                case LoaderCallbackInterface.SUCCESS:
                {
                    Log.i(TAG, "OpenCV loaded successfully");
                    System.loadLibrary("camera_control");
                    mOpenCvCameraView.enableView();
                    mOpenCvCameraView.setOnTouchListener(Tutorial3Activity.this);
                } break;
                default:
                {
                    super.onManagerConnected(status);
                } break;
            }
        }
    };
...

   public Mat onCameraFrame(CvCameraViewFrame inputFrame) {
        Mat mRgba =  inputFrame.rgba();
        Mat mGray = inputFrame.gray();
        FindFeatures(mGray.getNativeObjAddr(), mRgba.getNativeObjAddr());
        return mRgba;
    }
...

Make sure to use the same native module name.

Next, copy jni folder from Tutorial 2. Edit Application.mk file to set
APP_ABI := all

Edit Android.mk file to change JNI module name:
LOCAL_MODULE    := camera_control

Also, edit line 12 of this file to correctly point to your jni folder of OpenCV Android SDK.

Edit jni_part.cpp to correct the function names as below:
...
extern "C" {
JNIEXPORT void JNICALL Java_org_opencv_samples_tutorial3_Tutorial3Activity_FindFeatures(JNIEnv*, jobject, jlong addrGray, jlong addrRgba);

JNIEXPORT void JNICALL Java_org_opencv_samples_tutorial3_Tutorial3Activity_FindFeatures(JNIEnv*, jobject, jlong addrGray, jlong addrRgba)
{
    Mat& mGr  = *(Mat*)addrGray;
    Mat& mRgb = *(Mat*)addrRgba;
    vector<KeyPoint> v;
...

Enjoy Android development!

Android Studio - How to View Method Parameters

On Linux, press <Ctrl> + P
On Mac, press <Command> + P

How to Follow a Symbolic Link All the Way

You may have heavily nested symbolic links, and here is how to find its final destination. For example, if you are looking for the java executable:

$ readlink -f $(which java)

That's it!

How to Change Default JDK with AlternativesI

Here is how to set Oracle's JDK as your default. You can apply this to set OpenJDK as default as well very easily.

First, you will need to download Oracle's JDK. Visit here to download the latest JDK for your system.

For Debian-based Linux, you simply need to download the tar.gz archive and extract to a folder. For example,
$ tar xvfz jdk-8u101-linux-x64.tar.gz
$ sudo mv jdk1.8.0_101 /opt/

Next, set Oracle's JDK as an alternative:
$ sudo update-alternatives --install /usr/bin/java java /opt/jdk1.8.0_101/bin/java 100
$ sudo update-alternatives --install /usr/bin/javac javac /opt/jdk1.8.0_101/bin/javac 100

Finally, set whichever version you would prefer:
$ sudo update-alternatives --config java
$ sudo update-alternatives --config javac

That's it!

Wednesday, October 12, 2016

Installation of Multiple Instances of the Same Android App

Sometimes, you have your template app, from which you develop different apps. However, Android will count apps that have branched from the same app as one app.

Say you have your template app T. You modify T and create app A. You also create app B by modifying another copy of T. Now, you want to install both apps A and B into your phone, but it won't work; one will overwrite the other, because A, B have branched from T.

One way to install both A and B on a single phone is to change their applicationid in the app's build.gradle file. In most case, the applicationid is identical to the main activity package name. Make sure to change the top-most name of applicationid. After the change, build clean and invalidate caches and restart Android Studio. 

Now, you should be able to install both A and B as long as their applicationid's are different.

How to Apply .gitignore File To an Existing Repository

When you update or add .gitignore file to not track unnecessary files, such as object files and binary files, this is what you can do to apply the change to an existing repository.

$ git commit -m "outstanding changes before applying .gitignore"
$ git rm -r --cached .
$ git add .
$ git commit -m "applying .gitignore"

That's it!


Saturday, October 8, 2016

How to Log Visitors' IP Addresses, OS, and Browser

This tutorial is based on the answers by deceze and Gaurang.

The following code will log the visitor's IP address and access time, OS, and browser:


<?php
$user_agent     =   $_SERVER['HTTP_USER_AGENT'];

function getOS() {
    global $user_agent;
    $os_platform    =   "Unknown OS Platform";
    $os_array       =   array(
                            '/windows nt 10/i'     =>  'Windows 10',
                            '/windows nt 6.3/i'     =>  'Windows 8.1',
                            '/windows nt 6.2/i'     =>  'Windows 8',
                            '/windows nt 6.1/i'     =>  'Windows 7',
                            '/windows nt 6.0/i'     =>  'Windows Vista',
                            '/windows nt 5.2/i'     =>  'Windows Server 2003/XP x64',
                            '/windows nt 5.1/i'     =>  'Windows XP',
                            '/windows xp/i'         =>  'Windows XP',
                            '/windows nt 5.0/i'     =>  'Windows 2000',
                            '/windows me/i'         =>  'Windows ME',
                            '/win98/i'              =>  'Windows 98',
                            '/win95/i'              =>  'Windows 95',
                            '/win16/i'              =>  'Windows 3.11',
                            '/macintosh|mac os x/i' =>  'Mac OS X',
                            '/mac_powerpc/i'        =>  'Mac OS 9',
                            '/linux/i'              =>  'Linux',
                            '/ubuntu/i'             =>  'Ubuntu',
                            '/iphone/i'             =>  'iPhone',
                            '/ipod/i'               =>  'iPod',
                            '/ipad/i'               =>  'iPad',
                            '/android/i'            =>  'Android',
                            '/blackberry/i'         =>  'BlackBerry',
                            '/webos/i'              =>  'Mobile'
                        );

    foreach ($os_array as $regex => $value) {
        if (preg_match($regex, $user_agent)) {
            $os_platform    =   $value;
        }
    }
    return $os_platform;
}

function getBrowser() {
    global $user_agent;
    $browser        =   "Unknown Browser";
    $browser_array  =   array(
                            '/msie/i'       =>  'Internet Explorer',
                            '/firefox/i'    =>  'Firefox',
                            '/safari/i'     =>  'Safari',
                            '/chrome/i'     =>  'Chrome',
                            '/edge/i'       =>  'Edge',
                            '/opera/i'      =>  'Opera',
                            '/netscape/i'   =>  'Netscape',
                            '/maxthon/i'    =>  'Maxthon',
                            '/konqueror/i'  =>  'Konqueror',
                            '/mobile/i'     =>  'Handheld Browser'
                        );

    foreach ($browser_array as $regex => $value) {
        if (preg_match($regex, $user_agent)) {
            $browser    =   $value;
        }
    }
    return $browser;
}

$user_os        =   getOS();
$user_browser   =   getBrowser();

$device_details =   $user_browser." ".$user_os;
$line = date('Y-m-d H:i:s') . " - $_SERVER[REMOTE_ADDR]" . " " . $device_details;

file_put_contents('visitors.log', $line . PHP_EOL, FILE_APPEND);
?>

Make sure that the current directory is owned by www-data.
$ sudo chown www-data:www-data .

You will see a log file visitors.log in the current directory with a log similar to:
2016-10-08 12:33:13 - 12.34.56.78 Chrome Linux

How to Allow a Visitor Upload Image Files on Your Web Server

This post is based on this tutorial with some minor modifications.

If you want to let a visitor upload an image file to your web server, here is how to do. I will assume that you have a http and php server running on your system. If not, please refer to this post.

First, create a simple upload.html file:
<html>
<head>
</head>
<body>
    <form action="upload.php" method="post" enctype="multipart/form-data">
            Select image to upload:
                <input type="file" name="fileToUpload" id="fileToUpload">
                <input type="submit" value="Upload Image" name="submit">
    </form>
</html>

Next, create upload.php file:
<?php
$target_dir = "upload/";
$target_file = $target_dir . basename($_FILES["fileToUpload"]["name"]);
$uploadOk = 1;
$imageFileType = pathinfo($target_file,PATHINFO_EXTENSION);
// Check if image file is a actual image or fake image
if(isset($_POST["submit"])) {
    $check = getimagesize($_FILES["fileToUpload"]["tmp_name"]);
    if($check !== false) {
        echo "File is an image - " . $check["mime"] . ".<br>";
        $uploadOk = 1;
    } else {
        echo "File is not an image.<br>";
        $uploadOk = 0;
    }
}
// Check file size
if ($_FILES["fileToUpload"]["size"] > 5000000) {
    echo "Sorry, your file is too large.<br>";
    $uploadOk = 0;
}
// Allow certain file formats
if($imageFileType != "jpg" && $imageFileType != "png" && $imageFileType != "jpeg"
&& $imageFileType != "gif" && $imageFileType != "webp" && $imageFileType != "jxr" ) {
    echo "Sorry, only jpg, jpeg, png, webp, jxr, & gif files are allowed. Also, the extension must be all LOWER case!<br>";
    $uploadOk = 0;
}
// Check if $uploadOk is set to 0 by an error
if ($uploadOk == 0) {
    echo "Sorry, your file was not uploaded.<br>";
// if everything is ok, try to upload file
} else {
    if (move_uploaded_file($_FILES["fileToUpload"]["tmp_name"], $target_file)) {
        echo "The file ". basename( $_FILES["fileToUpload"]["name"]). " has been uploaded.<br>";
        echo "<br>http://SERVER_IP/" . $target_dir . basename( $_FILES["fileToUpload"]["name"]) . "<br>";
    } else {
        echo "Sorry, there was an error uploading your file.<br>";
    }
}
?>
]

Make sure to replace SERVER_IP with your server's IP address. Now, you can browse to your upload.html file, choose an image file, and upload to the server.

Make sure that the target directory is owned by www-data, the web werver.
$ sudo chown www-data:www-data /var/www/html/upload

Make sure to implement more security checks. You surely don't want any random visitor upload random files on the server!

How to Find out Visitor's IP Address

Here is how to find out a visitor's IP address using PHP:
<?php
    echo $_SERVER['REMOTE_ADDR']
?>

You can always embed this in HTML file:
<html>
<head></head>
<body>
    Your IP Address is <?php echo $_SERVER['REMOTE_ADDR'] ?>.
</body>
</html>

Note that the web server must be configured to parse the PHP code inside html file to display it correctly. You may want to refer tho this post to do this in Debian.

How to Setup a Home Web Server on Debian Jessie

Here is how to setup a home web server on Debian Jessie.

First, install apache web server. This will serve html files.
$ sudo apt-get install -y apahce2

If you haven't configured sudo, please take a look at this post to see how to configure sudo in Debian.

Next, install php5. This will server php files.
$ sudo apt-get install -y php5 libapache2-mod-php5

Now, your default server root directory is /var/www/html. You can add your html and php files here for your server to serve.

Finally, you probably may want to serve html files that embed php code in it. To do this, you need to edit /etc/apache2/mods-enabled/php5.conf file and add the following lines:
<FilesMatch ".+\.html$">
   SetHandler application/x-httpd-php
</FilesMatch>

To reload the config file, restart the server:
$ sudo service apache2 restart

Now, create /var/www/html/test.html file with the following code:
<html>
    <body>
        <h1>HTML file with PHP Code</h1>
        <?php
        echo "This code is run by PHP server";
        ?>
    </body>
</html>

In your web browser, go to http://SERVER_IP_ADDRESS/test.html
You should see the following text if your server is properly configured:
HTML file with PHP Code
This code is run by PHP server

By the way, if you want to override the config setting with .htaccses file, you need to edit
/etc/apache2/apache2.conf file and edit to
<Directory /var/www/>
    Options FollowSymLinks
    AllowOverride All
    Require all granted
</Directory>

Enjoy your web server!


Friday, October 7, 2016

How to Enable Auto-Completion after SUDO command in Mac OS X

By default on Mac OS X system, tab-auto completion is not on when you type in sudo command. For example, if you do
$ hdiu <tab>

it will auto-complete to
$ hdiutil

However, if you were to do the same with sudo command,
$ sudo hdiu <tab>

nothing really happens. This is because the feature is not turned on by default.

To turn on the feature, simply do
$ echo "complete -cf sudo" >> ~/.bash_profile
$ . ~/.bash_profile

That's it!

Monday, October 3, 2016

Computing Max Diff

Assume you can somehow foresee stock price for, say 1000 days, from today. If you are given, say k, chances to buy and sell those stock at all different days, how would you calculate the maximum profit you could get? Assume that you can only hold max 1 share at a time, so you won't be able to buy, buy, buy, and sell, sell, sell. You will need to buy, sell, buy, sell, ... and so forth.

For example, consider the daily price to be x_i = {4005 1330 6570 4925 7112 6182 177 1843 2897 5557 8561 5875 7069 6192 4358 8624} for i=1,2,..,16. If you are given 3 chances each to buy and sell this stock at each different day, what would be the maximum profit?

One way would be to buy at x_1, x_3, x_5 while selling at x_2, x_4, x_6, but this probably won't get you the maximum profit.

This is the classical max difference problem. Let's see how we can solve this.

As with any other algorithm problem, you should start looking for some sort of recursive relationship. Define

S(n,k) = max profit you would get by buy-sell k times with the last sell at x_n.

For example, S(3,1) would be x_3 - x_2, and S(5, 2) would be x_3 - x_2 + x_5 - x_4

It is not easy to instantly find the relation between S(n,k) and S(n-1,k) or S(n,k-1) or S(n-1,k-1). We need some helper variable. Define

B(n,k) = max cash you would get by buy-sell k-1 times before x_n, and buying kth time at x_n.

For example, B(1,1) would be -x_1, which is the only option. B(2,1) would be -x_2, and B(6,3) would be  x_3 - x_2 + x_5 - x_4 - x_6.

Now, we see the recursive relation between B and S:

B(n,k) = max[S(i, k-1)] - x_n for i<n
S(n,k) = max[B(i,k)] + x_n for i<n

OK, does that mean we need to store B and S 2D-arrays and find max for each (n,k)? Well, one way to avoid this is to instead store maxB and maxS 2D-arrays and store the max value up to n. For example, maxB[n][k] will be the max of B(1,k) through B(n,k).

The following is the source code for this.


Note that this requires O(n*k) space, which could be quite a lot. To reduce this, notice how maxB[i][k] and maxS[i][k] are of no usage for n>i+1. Therefore, at the end of each loop in n, we can update maxS and maxB and overwrite. In this way, we can store maxB[k] and maxS[k] 1-D arrays.

The following is the source code for this.


There is one little catch here though. We must loop through k in descending order, so that getS and getB functions access maxS and maxB from the previous loop in n, not the newly updated in the current loop in n.

Saturday, October 1, 2016

How to Reverse Mouse Scroll Direction in Debian and Ubuntu

This post is based on here.

To reverse mouse scroll direction, in case you like natural scrolling direction, edit /usr/share/X11/xorg.conf.d/10-evdev.conf file and add the line highlighted in green:
...
Section "InputClass"
        Identifier "evdev pointer catchall"
        MatchIsPointer "on"
        MatchDevicePath "/dev/input/event*"
        Option "ButtonMapping" "1 2 3 5 4 6 7 8"
        Driver "evdev"
EndSection
...

Restart X11 to take effect!