Next Spaceship

Driving into future...

POJ 3468 a Simple Problem With Integers

| Comments

Like POJ 3264 Balanced Lineup, segment tree is used.

The point is not to push down delta value to descendents, just keeping it on current node if the addition is for all its descendents.

Source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n, q;
long long cc[1 << 22];
long long dd[1 << 22];

void update(int ii,int s,int t,int ss,int tt, int c) {
    if(ss>tt) return; int mid((s+t)/2);
    if(s==ss&&t==tt) {dd[ii]+=c; return;}
    update(ii*2,s,mid,ss, min(mid,tt), c);
    update(ii*2+1,mid+1,t, max(mid+1,ss),tt,c);
    cc[ii] = cc[ii*2] + cc[ii*2+1] + dd[ii*2]*(mid-s+1) + dd[ii*2+1]*(t-mid);
}

long long query(int ii,int s,int t,int ss,int tt) {
    if(ss>tt) return 0; int mid((s+t)/2);
    if (s==ss&&t==tt){
        return cc[ii] + dd[ii]*(tt-ss+1);
    }
    return query(ii*2,s,mid,ss, min(mid,tt))
        +query(ii*2+1,mid+1,t, max(mid+1,ss),tt) + dd[ii]*(tt-ss+1);
}

int main() {
    scanf("%d", &n);
    scanf("%d", &q);
    memset(cc, 0, sizeof(cc)/sizeof(long long));
    memset(dd, 0, sizeof(dd)/sizeof(long long));
    for (int i = 1; i <= n; ++i){
        int a;
        scanf("%d", &a);
        update(1, 1, n, i, i, a);
    }
    for (int i = 0; i < q; ++i) {
        char o[2];
        int a, b, c;
        scanf("%1s", o);
        if (o[0] == 'C') {
            scanf("%d", &a);
            scanf("%d", &b);
            scanf("%d", &c);
            update(1, 1, n, a, b, c);
        }
        else {
            scanf("%d", &a);
            scanf("%d", &b);
            printf("%lld\n", query(1, 1, n, a, b));
        }
    }
    return 0;
}

POJ 3264 Balanced Lineup

| Comments

This is a classic range minimum query and range maximum query problem.

Segment tree, with \(O(\log_2{n})\) updating complexity and \(O(\log_2{n})\) query complexity, is a perfect data structure for this problem.

Actually this is really easy once segment tree is imported.

Source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define H 1000000
#define N 50010

int n, q;
int h[N];
int c_min[1 << 22],c_max[1<<22];

void update(int ii,int s,int t,int ss,int tt) {
    if(ss>tt) return; int mid((s+t)/2);
    if(s==ss && t==tt){ c_min[ii]=c_max[ii]=h[ss]; return;}
    update(ii*2,s,mid,ss, min(mid,tt));
    update(ii*2+1,mid+1,t, max(mid+1,ss),tt);
    c_min[ii]=min(c_min[ii*2],c_min[ii*2+1]);
    c_max[ii]=max(c_max[ii*2],c_max[ii*2+1]);
}

int min_query(int ii,int s,int t,int ss,int tt) {
    if(ss>tt) return H+1; int mid((s+t)/2);
    if(s==ss&&t==tt) return c_min[ii];
    return min(min_query(ii*2,s,mid,ss, min(mid,tt)),
        min_query(ii*2+1,mid+1,t, max(mid+1,ss),tt));
}

int max_query(int ii,int s,int t,int ss,int tt) {
    if(ss>tt) return -1; int mid((s+t)/2);
    if(s==ss&&t==tt) return c_max[ii];
    return max(max_query(ii*2,s,mid,ss, min(mid,tt)),
        max_query(ii*2+1,mid+1,t, max(mid+1,ss),tt));
}

int main() {
    scanf("%d", &n);
    scanf("%d", &q);
    memset(c_min, 0, sizeof(c_min)/sizeof(int));
    memset(c_max, 0, sizeof(c_max)/sizeof(int));
    for (int i = 1; i <= n; ++i){
        scanf("%d", &h[i]);
        update(1, 1, H, i, i);
    }
    for (int i = 0; i < q; ++i) {
        int a, b;
        scanf("%d", &a);
        scanf("%d", &b);
        printf("%d\n", max_query(1, 1, H, a, b) - min_query(1, 1, H, a, b));
    }
    return 0;
}

Phonetic Alphabet

| Comments

Today I study phonetic alphabet, which is really helpful the moment like pronounsing B as D.

NATO Phonetic Alphabet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
A as in Alpha
B as in Bravo
C as in Charlie
D as in Delta
E as in Echo
F as in Foxtrot
G as in Golf
H as in Hotel
I as in India
J as in Juliet
K as in Kilo
L as in Lima
M as in Mike
N as in November
O as in Oscar
P as in Papa
Q as in Quebec
R as in Romeo
S as in Sierra
T as in Tango
U as in Uniform
V as in Victor
W as in Whiskey
X as in X-ray
Y as in Yankee
Z as in Zulu

Western Union Phonetic Alphabet

Open Source Python Based Wiki: First Wiki

| Comments

First Wiki is a wiki written in Python. I write this because I counln’t find a beautiful wiki in Python.

First Wiki is based on shire, which is a web framework based on Tornado Web Server, MongoDB and Bootstrap.

First Wiki is open source, license is https://github.com/liangsun/firstwiki/blob/master/LICENSE. Source code is hosted on GitHub.

Features

  • Version control
  • Markdown rendering
  • User authentication and authorization
  • Beautiful
  • Python based
  • Open source

Getting Started

1
2
3
4
5
git clone https://github.com/liangsun/firstwiki.git
cd firstwiki
pip install -r pip-req.txt
python scripts/init.py
python start.py

Open http://127.0.0.1:8004 Go hacking!

Resetting Default Input Method in Mac OS

| Comments

I became a Dvorak guy. Before that, I had initialized my Mac to a U.S. keyboard layout. After I changed my Mac to Dvorak keyboard layout, everything worked like a charm except the login window was still the U.S. layout. This frustrates me a lot. So today I spend a little time to reslove this issue.

The easiest way is to re-initialize the system by this command:

1
sudo "/System/Library/CoreServices/Setup Assistant.app/Contents/MacOS/Setup Assistant"

But in this way, I have to creat a new user, which means I have to do some migration work. I think there must be a elegent way to resolve this. After Googleing a while, I find the solution.

1
2
3
sudo cp /Library/Preferences/com.apple.HIToolbox.plist /tmp/
sudo chmod 777 /tmp/com.apple.HIToolbox.plist
plutil -convert xml1 /tmp/com.apple.HIToolbox.plist

Now open /tmp/com.apple.HIToolbox.plist in a text editor (e.g. vim or Emacs).

Throughout the file you will find several mentions of a KeyboardLayout ID key followed by an integer and KeyboardLayout Name followed by a string. Change these strings to the name of your custom keyboard layout and the id integers to the ID of your layout (the easiest way to find the right values is to compare with your user settings found in the file ~/Library/Preferences/com.apple.HIToolbox.plist

1
2
3
sudo cp ~/Library/Preferences/com.apple.HIToolbox.plist /tmp/my.plist
plutil -convert xml1 /tmp/my.plist
cat /tmp/my.plist

Also the value of the key AppleCurrentKeyboardLayoutInputSourceID must be changed accordingly (for this circumstance it’s com.apple.keylayout.Dvorak). Again you can find this value in your local preference file.

Once these changes are done, save the file and go back to the terminal. To play it safe, you can create a copy of the original com.apple.HIToolbox.plist file, just in case you made an error and need to roll back. Then do the following:

1
2
sudo cp /tmp/com.apple.HIToolbox.plist /Library/Preferences/
sudo chmod 644 /Library/Preferences/com.apple.HIToolbox.plist

Exit the terminal, and restart the computer (logout is not sufficient: the file will not be reread). After restart, you should have your keyboard layout in the login screen. You may need to restart twice.

How to Get Coordinate of a ClickableSpan Inside a TextView

| Comments

I have a TextView with many ClickableSpan.

On click on a ClickableSpan, I have to get the coordinate on screen of it (to show a custom View at his position).

The problem is that the onClick() method of the ClickableSpan gives me in parameter a View, the TextView which contains the ClickableSpan.

Thanks to Google, I find this solution. This helps me to win a Leopard Buffet. :D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
@Override
public void onClick(View widget) {

    TextView parentTextView = (TextView) widget;

    Rect parentTextViewRect = new Rect();

    // Initialize values for the computing of clickedText position
    SpannableString completeText = (SpannableString)(parentTextView).getText();
    Layout textViewLayout = parentTextView.getLayout();

    double startOffsetOfClickedText = completeText.getSpanStart(this);
    double endOffsetOfClickedText = completeText.getSpanEnd(this);
    double startXCoordinatesOfClickedText = textViewLayout.getPrimaryHorizontal((int)startOffsetOfClickedText);
    double endXCoordinatesOfClickedText = textViewLayout.getPrimaryHorizontal((int)endOffsetOfClickedText);


    // Get the rectangle of the clicked text
    int currentLineStartOffset = textViewLayout.getLineForOffset((int)startOffsetOfClickedText);
    int currentLineEndOffset = textViewLayout.getLineForOffset((int)endOffsetOfClickedText);
    boolean keywordIsInMultiLine = currentLineStartOffset != currentLineEndOffset;
    textViewLayout.getLineBounds(currentLineStartOffset, parentTextViewRect);


    // Update the rectangle position to his real position on screen
    int[] parentTextViewLocation = {0,0};
    parentTextView.getLocationOnScreen(parentTextViewLocation);

    double parentTextViewTopAndBottomOffset = (
        parentTextViewLocation[1] -
        parentTextView.getScrollY() +
        parentTextView.getCompoundPaddingTop()
    );
    parentTextViewRect.top += parentTextViewTopAndBottomOffset;
    parentTextViewRect.bottom += parentTextViewTopAndBottomOffset;

    parentTextViewRect.left += (
        parentTextViewLocation[0] +
        startXCoordinatesOfClickedText +
        parentTextView.getCompoundPaddingLeft() -
        parentTextView.getScrollX()
    );
    parentTextViewRect.right = (int) (
        parentTextViewRect.left +
        endXCoordinatesOfClickedText -
        startXCoordinatesOfClickedText
    );

    int x = (parentTextViewRect.left + parentTextViewRect.right) / 2;
    int y = parentTextViewRect.bottom;
    if (keywordIsInMultiLine) {
        x = parentTextViewRect.left;
    }

    Log.d("location2:" + x + "," + y);
}

Write LaTeX With Octopress & MathJax

| Comments

Install Mathjax

The easiest method is to add by CDN, but the drawback is the CDN is not always stable and it doesn’t work if you want to develop offline and want to preview via the rake preview command.

Another way is to host Mathjax by yourself. So I choose this method. Before doing this, it’s a good idea to fork Octopress to your own repositories, so that you can make changes on it and save the configuration.

With Octopress, it is easy to custom the header file. Open the file source/_includes/custom/head.html, and add the following lines:

1
<script src="/mathjax/unpacked/MathJax.js"></script>

Then cd to the source/ folder and add Mathjax as a submodule:

1
git submodule add git://github.com/liangsun/MathJax.git mathjax

Here I use my forked MathJax repository, because I did some hack job ;-) Of course you can use the official repository, it’s here.

Install rdiscount With LaTeX Support

The official rdiscount doesn’t support LaTeX, while there are some other MarkDown rendering engines like kramdown, Pandoc etc, but these soltions either don’t support the \( and \) LaTex delimiters, which is my favourite writing style, or they only support the $ or $$ delimiters, and don’t support the inline equation, which I can not endure, so I forked it and added LaTeX support. If you want to know how it works: https://github.com/liangsun/rdiscount/commits/master.

1
2
3
4
git clone git://github.com/liangsun/rdiscount.git
cd rdiscount
gem build rdiscount.gemspec
gem install rdiscount-*.gem

Open the _config.yml file and find this line

1
gem 'rdiscount', '~> 2.0.7'

Replace with this line

1
gem 'rdiscount', '9.0.0.0'

Add rsync-exclude

Once you have successfully rake deploy your files to server, which will take some time because the mathjax folder is big, you can add a rsync-exclude file to exclude the mathjax folder in following deployments. Add a file named rysnc-exclude in the top folder of Octopress and put the following lines in it:

1
2
3
.git
.gitignore
mathjax

This will make the deploying speed as fast as without MathJax.

Also edit the Rakefile file, find this line,

1
FileList["#{args.source}/**/.*"].exclude("**/.", "**/..", "**/.DS_Store", "**/._*").each do |file|

and replace with this line,

1
FileList["#{args.source}/**/.*"].exclude("**/.", "**/..", "**/.DS_Store", "**/._*", "**/.git", "**/.gitignore").each do |file|

Test

1
2
3
Write an equation in \(\TeX\) now: \(\frac{1}{\Bigl(\sqrt{\phi \sqrt{5}}-\phi\Bigr) e^{\frac25 \pi}} =
1+\frac{e^{-2\pi}} {1+\frac{e^{-4\pi}} {1+\frac{e^{-6\pi}}
{1+\frac{e^{-8\pi}} {1+\ldots} } } }\), enjoy!

Write an equation in \(\TeX\) now: \(\frac{1}{\Bigl(\sqrt{\phi \sqrt{5}}-\phi\Bigr) e^{\frac25 \pi}} = 1+\frac{e^{-2\pi}} {1+\frac{e^{-4\pi}} {1+\frac{e^{-6\pi}} {1+\frac{e^{-8\pi}} {1+\ldots} } } }\), enjoy!

1
Another one: \(\frac{\frac{a}{b}}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{b}}}}}}}}}}}}\)

Another one: \(\frac{\frac{a}{b}}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{\frac{a}{b}}}}}}}}}}}}\)

1
Maxwell's Equations: \(\begin{split}\nabla \times \vec{\mathbf{B}} -\, \frac1c\, \frac{\partial\vec{\mathbf{E}}}{\partial t} & = \frac{4\pi}{c}\vec{\mathbf{j}} \\   \nabla \cdot \vec{\mathbf{E}} & = 4 \pi \rho \\ \nabla \times \vec{\mathbf{E}}\, +\, \frac1c\, \frac{\partial\vec{\mathbf{B}}}{\partial t} & = \vec{\mathbf{0}} \\ \nabla \cdot \vec{\mathbf{B}} & = 0 \end{split}\)

Maxwell’s Equations: \(\begin{split}\nabla \times \vec{\mathbf{B}} -\, \frac1c\, \frac{\partial\vec{\mathbf{E}}}{\partial t} & = \frac{4\pi}{c}\vec{\mathbf{j}} \\ \nabla \cdot \vec{\mathbf{E}} & = 4 \pi \rho \\ \nabla \times \vec{\mathbf{E}}\, +\, \frac1c\, \frac{\partial\vec{\mathbf{B}}}{\partial t} & = \vec{\mathbf{0}} \\ \nabla \cdot \vec{\mathbf{B}} & = 0 \end{split}\)

Wolfram Language Is Close to Release

| Comments

News

I’m excited to receive a message from Wolfram Language Team today:

We’re getting closer to the official release of the Wolfram
Language–and we are starting to demo it more publicly. Here are
a few highlights:

—————————–
Injecting Computation Everywhere
—————————–

Stephen Wolfram has posted a “speaker’s cut” of his “Injecting
Computation Everywhere” talk given at SXSW in Austin, Texas,
earlier this month. It includes some unique examples showcasing
the versatility and richness of the Wolfram Language, including:

* Tweeting an image using the Wolfram Language
* Classifying and interpreting handwritten digits
* Symbolically nesting an interface element to create a fractal interface
* Creating an app that displays images as seen through the eyes of a cat or dog

Moving from simple to more complex features and programs, Stephen
also introduces new Wolfram products and technologies, like
Wolfram Programming Cloud, Wolfram Data Science Platform, the
Wolfram Data Framework, and much more.

Read the full post at:
http://url.wolfram.com/1NRJCaGI/

—————————–
Introduction to the Wolfram Language
—————————–

Designed for the new generation of programmers, the Wolfram
Language has a vast depth of built-in algorithms and knowledge,
all automatically accessible through its elegant unified symbolic
language.

Watch Stephen Wolfram introduce the Wolfram Language and the
concept of knowledge-based programming in his new video at:
http://url.wolfram.com/2arFN81K/

—————————–
New Wolfram Language Code Gallery
—————————–

Covering a variety of fields, programming styles, and project
sizes, the Wolfram Language Code Gallery shows examples of what
can be done with the knowledge-based Wolfram Language–including
deployment on the web or elsewhere.

See the Wolfram Language in action at:
http://url.wolfram.com/1GbzUafO/

Enjoy!

What is Wolfram Language

Designed for the new generation of programmers, the Wolfram Language has a vast depth of built-in algorithms and knowledge, all automatically accessible through its elegant unified symbolic language. Scalable for programs from tiny to huge, with immediate deployment locally and in the cloud, the Wolfram Language builds on clear principles—and 25+ years of development—to create what promises to be the world’s most productive programming language.

Principles and Concepts of Wolfram Language

  • Knowledge-based programming
  • Meta-algorithms and superfunctions
  • Everything fits together
  • Everything is an expression
  • WDF: Wolfram Data Framework
  • Natural language understanding (NLU)
  • Universal deployment
  • CDF: Computable Document Format
  • WolframLink, Wolfram Connected Devices Project, etc.
  • Everything is interactive
  • Completely scalable
  • Multiparadigm fusion language
  • 25+ year lineage

Encrpyt Login Password With RSA

| Comments

Today I’m thinking about questions of those website using http protocol. When user logins in a http website, how to protect the password’s security. The conclusion is it is not easy to do so, because I haven’t figured out a method to prevent the possibility of man-in-the-middle attack without a PKI infrastructure. Maybe in the future, with the use of quantum cryptography, we can do that easily, but currently it’s hard.

Nevertheless, we still can make the process of login more securier. One approach is to hash password, and only transmit the digest instead of the plain password. To use this method, don’t forget to change salt frequently enough. But now I want to use another approach, just for fun.

To implement this, we need two parts. One for the back-end, and the other for the front-end. I’m gonna to use a Python server as the back-end and a js script to implement the front-end.

Python Server

Install the pure python rsa package:

1
pip install rsa

Then we can use it to generate a (public key, private key) tuple.

1
2
3
4
import rsa
(pubkey, privkey) = rsa.newkeys(512)
n = '%x' % pubkey.n
e = '%x' % pubkey.e

Pass the e and n variable to front-end.

Javascript

Download js rsa from http://www-cs-students.stanford.edu/~tjw/jsbn/

For now I just use the demo website http://www-cs-students.stanford.edu/~tjw/jsbn/rsa.html.

Copy the n variable to the Modulus (hex) input box and copy the e variable to the Public exponent (hex, F4=0x10001) input box.

Enter a message in Plaintext (string) and click encrypt.

Now we get the encrypted message in Ciphertext (hex).

Pass the ciphertext to Pytho server.

Python Sever Again

We get the ciphertext, but now we need translate it from hex to str first.

1
2
import re
ciphertext = ''.join([chr(int(x, 16)) for x in re.findall(r'\w\w', ciphertext)])

Now get the plaintext.

1
2
import rsa
plaintext = rsa.decrypt(ciphertext, privkey)

Security Notes

This method does not prevent the man-in-the-middle attack, and also if a router between the server and client has been hacked and hackers can it to modify the js file used in the login page.

Shire - a Framework Based on Tornado Web & MongoDB

| Comments

Merry Christmas!

Today, I open sourced a project named shire via Github.

shire is a web framework based on Tornado and MongoDB.

Why choose Tonado Web and MongoDB?

As this slide share shows, for joy and freedom.

shire also arms with bootstrap and jinja2, so it’s powerful. But it is small and flexible enough to do any customization based on it.

shire is designed for developers to quickly implement a website and prevent from wasting time on undertaking considerable basic jobs like configing db, adding bootstrap, user administration, signin, sign out, uploading resources etc.

Tinker it as you like!

Don’t forget to submit a pull request!

Getting Started

Make sure you have successfully installed MongoDB and Python 2.7

(To prepare a production environment, you may also need nginx, supervisord.)

1
2
pip install -r pip-req.txt
python start.py

Open http://127.0.0.1:8004

Go hacking!