Tuesday 2 July 2013

Find the Median of a Large Set of Number

Task:
There are 10G disordered numbers, you need to find out the median. You have 2G bytes memory.

Solution:

The simplest method is sorting all numbers then find the middle item:

1  2  3  … 49  50  51  … 98  99  100

There are two defects:

1. Not necessary to sort all numbers
2. Occupies too much memory

Improved:

Create a data table which count the numbers in separated ranges:
(After first scan)

Range 1-20 21-40 41-60 61-80 81-100
Count 20 20 20 20 20

The median must in range [41-60] while the offset is 10 which means the 10th item in the range block is the median

Next, program will scan data set again, and only copy 20 ranged numbers into memory. Do a sort and grab the 10th item.

=======

Assume the numbers are unsigned 64bit integer. So each number occupies 8 bytes. 2G ram could handle no more than 256M numbers each time. The 10G number set could be separated into 40 groups.

Then, define several ranges from 0 to 2^64 -1, looks like arithmetic sequence:

( Pseudo code )

int64 a = 2^64 / 4096;

int64[4096] b ;

Array b statistics the volume of numbers hit in the range. In current code, each b in the array maps a range of 2^64 / 4096 = 2^52

For instance, if there is a number 68846541654532100.

68846541654532100 / (2^52) = 15.287

will lead to:

b[15]++;

 

The program do a initial process, read 256M numbers each time, for 40 main loops. In each loop, compare function will find out the range of each number and update the b[4096]. When loops done, we will get a full record b[4096].

Find the Median range:

int64 sum=0;
int64 prev=0;
int i;
for (i=0 ; i < 4096 ; i++)
{
  prev=sum;
  sum += b[i];
  if (sum >= 2^64 / 2)
    break;
}
int64 offset=(2^64 /2 – prev);
print( i );

Median must located in:
from  i*a  to  (i+1)*a-1
and must be the offset=(2^64 /2 – prev) item in the target block.

Program will scan 10G number set again, but only pick the numbers in the specific range and write them to file system.

IF the final file is less than 2G, sort the content, and pick the ‘offset’ item.

IF the final file is greater than 2G, separate it again as previous steps but smaller range. Do not forget to translate the offset.

Friday 28 June 2013

Monty Hall problem (Three-Door problem)

http://en.wikipedia.org/wiki/Monty_Hall_problem

image

The most well known statement of the problem is:

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice? (Whitaker, 1990, as quoted by vos Savant 1990a)

Vos Savant's response was:

Yes; you should switch. The first door has a 1/3 chance of winning, but the second door has a 2/3 chance. Here’s a good way to visualize what happened. Suppose there are a million doors, and you pick door #1. Then the host, who knows what’s behind the doors and will always avoid the one with the prize, opens them all except door #777,777. You’d switch to that door pretty fast, wouldn’t you?

image

image

So the ratio between WIN vs LOSE should be 66.6 : 33.3

I spend some time to write a simulator to check. (code is a bit ugly but it works)

Game class:

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package montyhallproblem;

/**
*
* @author celeron533
*/
public class Game {

public Door[] doors;

public Game() {
this.doors = new Door[]{new Door(), new Door(), new Door()};//create doors
doors[(int) (Math.random() * 3)].item = Item.car;//allocate the prize
}
public int playerInitial;

public void playerInitialSelection(int s) {
playerInitial = s;
}

public int hostOpenGoatDoor() {
if (doors[playerInitial].item == Item.car) {
//open one door of the rest
int open;
do {
open = (int) (Math.random() * 3);
} while (open == playerInitial);
doors[open].opened = true;
return open;
} else {//when player select a goat door, host open the left goat door
for (int i = 0; i < 3; i++) {
if (i == playerInitial) {//skip player selection
continue;
} else {
if (doors[i].item == Item.car) {//skip car door
continue;
} else {//open
doors[i].opened = true;
return i;
}
}
}
}
return -1;
}

public class Door {

public boolean opened = false;
public Item item = Item.goat;
}

public enum Item {
car, goat
}

@Override
public String toString() {
String result = "select_" + playerInitial + " ";
for (int i = 0; i < 3; i++) {
result += doors[i].item + "_" + doors[i].opened + " ";
}
return result;
}
}


Main class:


/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package montyhallproblem;

/**
*
* @author celeron533
*/
public class MontyHallProblem {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Game game;
int playerSelect, hostOpen;
int keepSelectionWins = 0;
int switchSelectionWins = 0;
for (int i = 0; i < 10000000; i++) {
game = new Game();
playerSelect = (int) (Math.random() * 3);
game.playerInitialSelection(playerSelect);
hostOpen = game.hostOpenGoatDoor();
//Statistical results
if (game.doors[playerSelect].item == Game.Item.car) {
keepSelectionWins++;
} else {
switchSelectionWins++;
}
//System.out.println(game.toString());
}
System.out.println("keepSelectionWins: " + keepSelectionWins);
System.out.println("switchSelectionWins:" + switchSelectionWins);
}
}


 


And the perfect result:


run:
keepSelectionWins: 3333349
switchSelectionWins:6666651
BUILD SUCCESSFUL (total time: 3 seconds)


image

Monday 10 June 2013

Create a Simple Java REST Web Service Client

A web service is a method of communication between two electronic devices over the World Wide Web.  [Wikipedia]

Unlike some private protocol, RESTful web service use common web protocol and encapsulate data into XML format.

For example, client sent a photo search request to flickr:

http://api.flickr.com/services/rest/?method=flickr.photos.search&api_key=b673a1be26fa7463c7036d9d0e3339e7&text=gundam&format=rest&api_sig=028e6e4f5041b8974069d4ead1f7f2ea

And flickr will response

<?xml version="1.0" encoding="utf-8" ?>
<rsp stat="ok">
<photos page="1" pages="1842" perpage="100" total="184172">
<photo id="9004970606" owner="91423658@N05" secret="fb1d4dbf62" server="5340" farm="6" title="gundam" ispublic="1" isfriend="0" isfamily="0" />
<photo id="9004399158" owner="32670813@N07" secret="978879e163" server="7325" farm="8" title="Bandai advertisement in Gundam Seed Destiny Remaster" ispublic="1" isfriend="0" isfamily="0" />
</photos>
</rsp>

 


===============Create the project in Netbeans=================


Create a new Java Application


image


 


Right click on your project –> New –> Other…


In ‘Web Services’ category, select ‘RESTful Java Client’ file


image


Follow the wizard, java codes and xml schema will be generated automatically.


image


In NewJerseyClient.java, all APIs are listed. You only need to call the mapped function with proper parameters and the function will raise a connection and make a request.


The Rsp.java is used to unmarsal the XML response.


 


# Do NOT forget to add the app key in your request.


## Because this in only a very simple example, you need to disable the ‘login’ authority function.


 


Sample code:


public static void main(String[] args) {
// TODO code application logic here
NewJerseyClient flickrREST = new NewJerseyClient();
RestResponse result = flickrREST.photo_search("gundam");
unmarsal(result.getDataAsString());
}

private static void unmarsal(String xml) {
ByteArrayInputStream stream=new ByteArrayInputStream(xml.getBytes());
Rsp rsp = JAXB.unmarshal(stream, Rsp.class);
System.out.println("Stat:"+rsp.getStat());
Rsp.Photos photos = rsp.getPhotos();
System.out.println("Page:" + photos.getPage() + " Pages:" + photos.getPages()
+ " PerPage:" + photos.getPerpage() + " TotalResults:" + photos.getTotal());
for (Rsp.Photo photo : photos.getPhoto()) {
System.out.println("PhotoID:" + photo.getId() + " Title:" + photo.getTitle());
}
}



===========More works could be done to improve the user interface====


image

Saturday 27 April 2013

IT elements in the animation (Part IV)–Evangelion Q

(Part II & Part III are missing. Sad smileThey will be completed in the coming weeks)

Evangelion: 3.0 You Can (Not) Redo. (ヱヴァンゲリヲン新劇場版:Q)

A new organization, WILLE, which is NERV’s rival. Start-up its new battleship called “WUNDER” when it encountered the angel.

Evangelion Shin Gekijouban Q (BDrip 1920x1080 x264 FLACx2 5.1ch)-ank.mkv_20130427_190330.781

As an IT guy, it is interesting to inspect the booting screen~

 

Boot up screen with POST

Evangelion Shin Gekijouban Q (BDrip 1920x1080 x264 FLACx2 5.1ch)-ank.mkv_20130427_163826.206

Evangelion Shin Gekijouban Q (BDrip 1920x1080 x264 FLACx2 5.1ch)-ank.mkv_20130425_210241.304

Here is what on the screen

SYSTEM SETUP ( STARTUP ) KhaOS version = 3.00
CONFIGURATION
*Device Config = All Devices
HDD CONTROLLER
HDD Controller Mode = Auto-Selected
I/O PORTS
*Serial = COM1(HBK33/BD310)
*Parallel = LPT1(RB338/TR9/TB3)
*Sound = Enabled
HDD I/O
Build-in HDD
= Primary ID(1FH000L/IRQ14)
= Secondary ID(B1005/IRQ21)
= Preliminary ID(CD666/DUMMY SYS.)
DISPLAY
*Holograph Segment Address = C000HF
 
KDB BUS
*KDB BUS = IRQ
ARCHITECT
*Main = Ver.3.10 *3.22Build.
*Sub = Ver.3.22 *3.10Build.
*Dummy = Ver.6.66 *6.66Build.

 

Wait… COM1 LPT1 ?

I haven’t seen them for a long long time

ASUS_M4N78-AM_lpt_com

IRQ14 is normally reserved for PATA (IDE) controller

==============

The next scene is the rolling code on the screen.

System is BUSY

Evangelion Shin Gekijouban Q (BDrip 1920x1080 x264 FLACx2 5.1ch)-ank.mkv_20130425_211955.795

Evangelion Shin Gekijouban Q (BDrip 1920x1080 x264 FLACx2 5.1ch)-ank.mkv_20130425_212327.237

Question:
What’s the programing language on the screen?

struct
comment style /* */
code block { }

01

 

for [element] in [collection] do {…}

02

 

if [condition] then {…}

QQ截图20130427172745

 

define a new function by using ‘fn’ keyword
and
local ret = #()

QQ截图20130427172758

 

However,
C, C++, C#, Java, JavaScript, VB, BVScript, VBA, python
can not satisfy this coding style

What the hell is that?

New let me try to find out some other keywords.

For example, “EmptyModifier”

QQ截图20130427172856

Bingo!

It’s MaxScript, from 3ds max.

mxse02darkscintilla_band

Completed

Evangelion Shin Gekijouban Q (BDrip 1920x1080 x264 FLACx2 5.1ch)-ank.mkv_20130425_213157.674Evangelion Shin Gekijouban Q (BDrip 1920x1080 x264 FLACx2 5.1ch)-ank.mkv_20130425_213234.646

All green

Evangelion Shin Gekijouban Q (BDrip 1920x1080 x264 FLACx2 5.1ch)-ank.mkv_20130425_213536.871

Evangelion Shin Gekijouban Q (BDrip 1920x1080 x264 FLACx2 5.1ch)-ank.mkv_20130425_213544.435

Ignite main engine.

Evangelion Shin Gekijouban Q (BDrip 1920x1080 x264 FLACx2 5.1ch)-ank.mkv_20130425_213555.340

Sunday 14 April 2013

Weekend Project: Miscellaneous

Headphone + Joystick repair.

Both of the equipment is left by former roommate.

Some buttons on panel have no reaction unless you press them firmly. It seems Conductive Rubber under the buttons are dirty.

20130330_120000

20130330_120010

Teardown the device.

20130330_150748

Water wash the buttons/rubber and clean the PCB by using eraser.

20130330_150807

Finally, reassemble the joystick and do a test.

 

=================HeadPhone=============

Logitech headphone.

The volume controller has problem. Even very tiny touch on the controller will mute the right hand side speaker.

20130330_132003

Teardown.

20130330_132206

At first, I thought just the right-pass of variable resistor is open circuit. Soldering three new ‘Bridge’ will cross the problem.

20130330_133514

The Bridge (from another headphone dead body~)

20130330_133749

Done. Bridges connected the end-points of tuner

20130330_135430

Unfortunately, annoying buzz and mute problem still exists.

I realized it was not a open circuit, but a short circuit. There is an unexpected connection between Right and Ground cable.

Plan B:

Direct connection, no tuner.

20130330_14343420130330_143916

Tested, all green.

Mission accomplished.

Wednesday 6 March 2013

Write a Simple Game with LWJGL (LightWeight Java GL)

This post will show a demo on how to write an OpenGL game by using Java.

LWJGL is a framework not only a java tool package but also contains cross-platform complied OpenGL API files. These native clients could work on the following operation systems: Windows, Linux, MacOSX, and Solaris. Despite Java program efficiency issues, LWJGL gets out a possible solution that developers need only deploy the core code and the rests (OpenGL relative) will auto-adjusted by the framework.

Pong is a very famous & simple console game. So I implement it as the ‘Hello World’ project.

image

Initially, let me introduce the basic game logic (although most of you know it XD)

  • 2 Players (one human and one computer), each player controls a bat
  • 1 Ball
  • Control the bat move up and down, try to hit the ball, do not miss it

Sketch:

image

Before we start write code, add LWJGL libraries first.

  1. Download LWJGL jar files
  2. Attach these jar files to out project
  3. Add native GL files to the project. This step is crucial. Select the files which match you current/target operation system
  4. (optional) Add Javadoc
  5. Now it should looks like the image below

image

Great! Ready to work.

============

Firstly, define the entities.

This operation may unnecessary for such small project. But it still helps us to build a well-formed OO program.

image

Two interfaces: Entity & MoveableEntity

Two abstract classes: AbstractEntity & AbstraceMoveableEntity

Code:

package entites;

public interface Entity {
public void draw();
public void update(int delta);
public void setLocation(double x, double y);
public void setX(double x);
public void setY(double y);
public void setWidth(double width);
public void setHeight(double height);
public double getX();
public double getY();
public double getHeight();
public double getWidth();
public boolean intersects(Entity other);

}



package entites;

import java.awt.Rectangle;

public abstract class AbstractEntity implements Entity {

protected double x, y, width, height;
protected Rectangle hitbox = new Rectangle();

public AbstractEntity(double x, double y, double width, double height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}

@Override
public void setLocation(double x, double y) {
this.x = x;
this.y = y;
}

@Override
public void setX(double x) {
this.x = x;
}

@Override
public void setY(double y) {
this.y = y;

}

@Override
public void setWidth(double width) {
this.width = width;

}

@Override
public void setHeight(double height) {
this.height = height;

}

@Override
public double getX() {
return x;
}

@Override
public double getY() {
return y;
}

@Override
public double getHeight() {
return height;
}

@Override
public double getWidth() {
return width;
}

@Override
public boolean intersects(Entity other) {
hitbox.setBounds((int) x, (int) y, (int) width, (int) height);
return hitbox.intersects(other.getX(), other.getY(), other.getWidth(),
other.getHeight());
}

}



package entites;

public interface MoveableEntity extends Entity {
public void setDX(double dx);
public void setDY(double dy);
public double getDX();
public double getDY();
}



package entites;

public abstract class AbstractMoveableEntity extends AbstractEntity implements
MoveableEntity {

protected double dx, dy;

public AbstractMoveableEntity(double x, double y, double width,
double height) {
super(x, y, width, height);
this.dx = 0;
this.dy = 0;
}

@Override
public void update(int delta) {
this.x += delta * dx;
this.y += delta * dy;
}

public void setDX(double dx) {
this.dx = dx;
}

public void setDY(double dy) {
this.dy = dy;
}

public double getDX() {
return dx;
}

public double getDY() {
return dy;
}

}



 


>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>


Time to setup the main body of Pong.



  1. Initialize OpenGL

  2. Initialize all necessary Objects

  3. Make some Objects “move”

  4. Listening users key-press actions

  5. Also, AI should response

  6. Game logic (hit? miss? win? lose?)

  7. Refresh the screen

The codes are very simple. I believe you can understand most of them.
( Because I am lazy ^_^ )


package pong;

import java.util.Random;

import org.lwjgl.*;
import org.lwjgl.input.Keyboard;
import org.lwjgl.opengl.*;
import entites.AbstractMoveableEntity;
import static org.lwjgl.opengl.GL11.*;

public class PongGame {

public static final int WIDTH = 640, HEIGHT = 480;
private boolean isRunning = true;
private long lastFrame;
private Ball ball;
private Bat bat;
private Bat computerBat;

public PongGame() {
setUpDisplay();
setUpOpenGL();
setUpEntities();
setUpTimer();

while (isRunning) {
render();
logic(getDelta());
input();
computer();
Display.update();
Display.sync(60);
if (Display.isCloseRequested()) {
isRunning = false;
}
}

Display.destroy();
}

private void computer() {
if (ball.getX() > 350 && ball.getDX()>0) {
if (ball.getY() + ball.getHeight() / 2 > computerBat.getY()
+ computerBat.getHeight() / 2 + 4
&& computerBat.getY() + computerBat.getHeight() <= HEIGHT) {
computerBat.setDY(0.2);
} else if (ball.getY() + ball.getHeight() / 2 < computerBat.getY()
+ computerBat.getHeight() / 2 - 4
&& computerBat.getY() >= 0) {
computerBat.setDY(-0.2);
} else {
computerBat.setDY(0);
}
}
else{
computerBat.setDY(0);
}
}

private void input() {
if (Keyboard.isKeyDown(Keyboard.KEY_UP) && bat.getY() >= 0) {
bat.setDY(-0.2);
} else if (Keyboard.isKeyDown(Keyboard.KEY_DOWN)
&& bat.getY() <= HEIGHT - bat.getHeight()) {
bat.setDY(0.2);
} else {
bat.setDY(0);
}
}

public long getTime() {
return (Sys.getTime() * 1000) / Sys.getTimerResolution();
}

public int getDelta() {
long time = getTime();
int delta = (int) (time - lastFrame);
lastFrame = time;
return delta;
}

private void logic(int delta) {
ball.update(delta);
computerBat.update(delta);
bat.update(delta);
//ball hit the bat
if (ball.getX() <= bat.getX() + bat.getWidth()
&& ball.getX() >= bat.getX()
&& ball.getY() + ball.getHeight() >= bat.getY()
&& ball.getY() <= bat.getY() + bat.getHeight()) {
ball.setDX(Math.abs(ball.getDX()));
Random ran = new Random();
ball.setDY(ball.getDY() + bat.getDY() / 3
+ (double) (1 - ran.nextInt(2)) / 200);
}
//ball hit the computerBat
if (ball.getX() + 10 >= computerBat.getX()
&& ball.getX() + 10 <= computerBat.getX() + 10
&& ball.getY() + ball.getHeight() >= computerBat.getY()
&& ball.getY() <= computerBat.getY() + computerBat.getHeight()) {
ball.setDX(-Math.abs(ball.getDX()));
}

//top & bot border
if (ball.getY() < 0 || ball.getY() > HEIGHT - ball.getHeight()) {
ball.setDY(-ball.getDY());
}

if (ball.getX() < 0 || ball.getX() > WIDTH - ball.getWidth()) {
//reset game
setUpEntities();
}

//fix DY if DY is too large
if (Math.abs(ball.getDY()) > Math.abs(ball.getDX() * 1.5)) {
ball.setDY(ball.getDY() / 1.5);
}

}

private void render() {
glClear(GL_COLOR_BUFFER_BIT);
ball.draw();
bat.draw();
computerBat.draw();
}

private void setUpTimer() {
lastFrame = getTime();
}

private void setUpEntities() {
bat = new Bat(20, (HEIGHT / 2 - 80 / 2), 10, 80);
computerBat = new Bat(WIDTH - 20 - 10, (HEIGHT / 2 - 80 / 2), 10, 80);
ball = new Ball(WIDTH / 2 - 10 / 2, HEIGHT / 2 - 10 / 2, 10, 10);
ball.setDX(-0.15);
}

private void setUpOpenGL() {
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glOrtho(0, WIDTH, HEIGHT, 0, 1, -1);
glMatrixMode(GL_MODELVIEW);
}

private void setUpDisplay() {
try {
Display.setDisplayMode(new DisplayMode(WIDTH, HEIGHT));
Display.setTitle("pong");
Display.create();
} catch (LWJGLException e) {
e.printStackTrace();
System.exit(0);
}

}

private static class Bat extends AbstractMoveableEntity {

public Bat(double x, double y, double width, double height) {
super(x, y, width, height);
}

@Override
public void draw() {
//glColor3d(1.0, 1.0, 1.0);
glRectd(x, y, (x + width), (y + height));
}
}

private static class Ball extends AbstractMoveableEntity {

public Ball(double x, double y, double width, double height) {
super(x, y, width, height);
}

@Override
public void draw() {
//glColor3d(1.0, 1.0, 1.0);
glRectd(x, y, x + width, y + height);
}

}

public static void main(String[] args) {
new PongGame();
}
}

Thursday 21 February 2013

Three notebook repair in Nov.2012


1. DELL Inspiron
29/Oct/2012
"HDD not found"
Cannot boot the system

Dell's design is quite disgusting, you could only replace the memory from back panel but not HDD.
The HDD is directly fixed on motherboard. After I unmounted the HDD and connect it to my laptop. My laptop could not identify it, totally broken down. The customer said there is no sensitive data in that HDD, no need to do data recovery.

The rests is simple. Buy a brand new HDD, replace the broken one and install OS.



2. Lenovo V460
14/Nov/2012

Overheating issue. Auto-reboot when playing 3D games.
CPU standby Temp = 70 C
When doing pressure testing, both CPU & GPU Temp > 99 C
2 or 3 seconds later, system frozen, no response and then reboot.

Because of the heat pipe radiator is embedded on motherboard, I must disassemble the machine.


Clean and reapply thermal grease.



3. Asus K42Jc (My own laptop)
19/Nov/2012
Remove dust only






Wireless NIC

Empty chip

Reserved space for Bluetooth

Left-Right button of touchpad

Power button and a LED on the left

Heat exchanger with dust

Heat exchanger without dust

Fan


Tuesday 19 February 2013

CANNON PG-510 Printer Cartridge Refill

Printer: Cannon MP280
Color ink printer & scanner

Third party ink (black)


20ml

Could refill 2.6 times for my printer cartridge
So, it is easy to calculate the capacity of cartridge:
20 / 2.6 = 7.7 ml

I also brought a larger ink tank from China:
150 ml
150 / 7.7 = 19.5 times
WOW!

There is an air vent on the cartrige but it is too narrow for the injecter. Expand/Ream it.

And tear off the sticker. You will see the air gateway

Prepare for injection

7ml

Done.
Paste a new sticker.