A solution for a Greedy Choice Algorithm Solution from TopCoder


/**
 * You are playing a computer game and a big fight is planned between two armies.
 * You and your computer opponent will line up your respective units in two rows,
 * with each of your units facing exactly one of your opponent's units and vice versa.
 * Then, each pair of units, who face each other will fight and the stronger one will be
 * victorious, while the weaker one will be captured. If two opposing units are equally strong,
 * your unit will lose and be captured. You know how the computer will arrange its units,
 * and must decide how to line up yours. You want to maximize the sum of the strengths of
 * your units that are not captured during the battle.
 * You will be given a int[] you and a int[] computer that specify the strengths of
 * the units that you and the computer have, respectively. The return value should be an int,
 * the maximum total strength of your units that are not captured.
 *
 * FROM TOP CODER
 *
 * your array
 * {651, 321, 106, 503, 227, 290, 915, 549, 660, 115,
 * 491, 378, 495, 789, 507, 381, 685, 530, 603, 394,
 * 7, 704, 101, 620, 859, 490, 744, 495, 379, 781,
 * 550, 356, 950, 628, 177, 373, 132, 740, 946, 609,
 * 29, 329, 57, 636, 132, 843, 860, 594, 718, 849}
 *
 * computer array
 * {16, 127, 704, 614, 218, 67, 169, 621, 340, 319,
 * 366, 658, 798, 803, 524, 608, 794, 896, 145, 627,
 * 401, 253, 137, 851, 67, 426, 571, 302, 546, 225,
 * 311, 111, 804, 135, 284, 784, 890, 786, 740, 612,
 * 360, 852, 228, 859, 229, 249, 540, 979, 55, 82}
 *
 * Returns: 25084
 *
 */

import java.util.Arrays;
public class Main {

	public void findMaxStrength(int[] computer, int[] player){
		Arrays.sort(computer);
		Arrays.sort(player);
		int index = computer.length-1;
		int smallIndex = 0;
		for(int i = computer.length-1; i>=0; i--){
			if(player[index] <= computer[i]){
				shift(player, smallIndex, index);
				index--;
			}else{
				index--;
			}
		}
	}

	public int[] shift(int[] a, int index1, int index2){
		int e = a[index1];
		for(int i = index1; i
Share

Dynamic Programming Example – Find n.th Fibonacci number –

Dynamic programming is a concept that provides faster solutions for divide and conquer problems that have some number of overlapping sub problems. Generally this concept is used for optimization problems like finding longest common sub-sequence of two arrays.

However I used the concept in finding n th Fibonacci number. Here is the code that I used.

public class Main {
	int q;
	public static void main(String args[]){
		new Main().fibonacci(40);
	}

	public void fibonacci(int n){
		ArrayList r = new ArrayList();

		for(int i = 0; i < n+1; i++){
			r.add(-1);
		}
		fibonacci(n, r);
		System.out.println(q);
	}

	public int fibonacci(int n, ArrayList r){
		if (r.get(n)>= 0){
			return r.get(n);
		}else if(n == 0){
			q = 0;
		}else if(n == 1){
			q = 1;
		}else{
			q = fibonacci(n-1, r)+fibonacci(n-2, r);
		}
		r.set(n, q);
		return q;
	}
}
Share

Getting Rid Of Bayblon Search Engine on Firefox

There is a known issues about the babylon search engine direction while you want to use the default search engine of your browser (like I lived 🙂 so I search about the solution and concluded such a solution:

Step1: Uninstall your Firefox (included all your personal information in Firefox) and reboot.

Step2: Instal “CCleaner” free edition (since the problem is about the register file of your browser about the babylon toolbar. It infects on the registers that you  need to delete)

Step3: Delete all cookies about the babylon in the program and fix the registry files by again the program

Step4: Re install Firefox

That’s all 🙂

Share


Using MouseListener with Jgraph

I am currently developing a java application Jgraph library and I faced with a problem to use mouse listener. I found the way of using so hard thus I want to share who searches for it. Here is the solution:

 

 


graphComponent.getGraphControl().addMouseListener(new MouseAdapter(){
public void mousePressed(MouseEvent e) {
// TODO Auto-generated method stub
if(e.getClickCount() == 2){
long x = e.getX();
long y = e.getY();
mxGraphComponent graphComponent = new mxGraphComponent(graph);
Object cell = graphComponent.getCellAt((int) x, (int)y);
System.out.println(graph.convertValueToString(cell));

}
}

});

Share

Working with Datamapper in RUBY.

Step 0: Introducing DataMapper

DataMapper is an ORM: an Object-Relational Mapping. Basically, it’s a library that lets you work with your database from object-oriented code. There’s absolutely no SQL in this tutorial at all. However, an ORM uses a regular database under the covers; we’ll be using sqlite3 today, but you could just use a different adapter to work with a mysql, postgresql or other database.

In Singing with Sinatra – The Recall App, Dan Harper introduced you to DataMapper. In this tutorial, we’re going to take a deeper dive in to working with the library.


Step 1: Installing the Right Gems

The first step is installing the required gems. The DataMapper functionality is broken into many different gems, so you’ll have to install several different parts. Of course, we’re not going to work with it all; but these are the gems you’ll have to install.

  • sqlite3: This is the database gem.
  • dm-core: This is the core functionality of DataMapper.
  • dm-migrations: This gem does the database migration.
  • dm-validations: As you’ll guess, this offers data validation functionality.
  • dm-timestamps: Helps with timestamping database records.
  • dm-sqlite-adapter: This is the adapter that connects DataMapper to your database; we’ll be using sqlite here, but you can use the dm-postgres-adapterdm-mysql-adapter, or whatever suits your fancy.

Once you’ve got all those gems installed , we’re ready to go.


Step 2: Creating a Basic Model

Let’s start by creating a basic model. Models are defined in classes. However, we first have to connect to our database.

Actually, the very first thing is requiring our libraries at the top of our file.

  1. require ‘dm-core’
  2. require ‘dm-timestamps’
  3. require ‘dm-validations’
  4. require ‘dm-migration’

So now that we have DataMapper in the environment, let’s connect to the database.

  1. DataMapper.setup :default, “sqlite://#{Dir.pwd}/database.db”

The first parameter tells DataMapper to use the default adapter for the database type. The second is the link / URL for the database. Since we’re using sqlite, we’re just linking to a database file. Note that we don’t have to create this file; DataMapper will create it for us.

Now we’re ready to create the model. As you know, this is a class.

  1. class User
  2. include DataMapper::Resource
  3. property :id       , Serial
  4. property :username , String
  5. property :email    , String
  6. end

The first step is to include the DataMapper::Resource module. This gives you the custom methods you’ll use in your class. The most important method here is property. Here, we’re using it to create three different properties: an id, a username, and an email. As you see, the first parameter in property is a symbol that’s the name of the property. The second is the type. You understand String, of course, but what’s serial. Actually, property :id, Serial is DataMapper’s shorthand for the primary key; ‘serial’ is an auto-incrementing integer. That’s your primary key!


Step 3: Migrating the Database

Now that we’ve created our model, we need to migrate the database. If you’re not familiar with migrating a database, it’s the process of changing the schema of the database. This could be adding a column, renaming a column, or changing properties of a column. DataMapper offers two ways to do this:

  1. DataMapper.auto_migrate!
  2. DataMapper.auto_upgrade!

The difference here is that auto_migrate! will clear all the data from the database; the auto_upgrade!methods tries to reconcile what’s in the database already with the changes you want to make. The way this works is that after your model class, you’ll call one of these methods. You don’t want to be runningauto_migrate! every time you load the model, of course, but you might want to run auto_upgrade! on every reload in development. I’ve done it this way in Sinatra:

  1. configure :development do
  2. DataMapper.auto_upgrade!
  3. end

You’ll notice that so far, we haven’t had to touch a single SQL query; that’s the point of using on ORM is that you can write normal code and have that work with relational databases.


Step 4: Adding some Advanced Attributes

Now that we have our feet wet with DataMapper, let’s take our model to another level. Let’s start with timestamps.

Timestamps

We’re requiring the dm-timestamps gem, so why not use it? If we add ‘created_at’ and ‘updated_at’ properties to the model, this gem will automatically update those fields.

property :created_at, DateTime
property :updated_at, DateTime

Of course, you don’t need to add both, if you don’t want them.

Options

There are several options that you can add to each field. For example, if you want a field to be required, or unique, or have a default value, you can do that there. Let’s create a post model to showcase some of this:

  1. class Post
  2. include DataMapper::Resource
  3. property :slug       , String   , key: true, unique_index: true, default: lambda { |resource,prop| resource.title.downcase.gsub ” “, “-” }
  4. property :title      , String   , required: true
  5. property :body       , Text     , required: true
  6. property :created_at , DateTime
  7. property :updated_at , DateTime
  8. end

We’re mixing things up a bit here; our ‘title’ and ‘body’ are required fields. We’re defining the ‘slug’ property as the primary key, and saying that it must be a unique index. Don’t get scared off by the default value of ‘slug.’ Of course, you can just use a raw value of whatever type your property is, but we’re doing something more. Ruby (and other languages) has lambdas, which you could think of as a small function. It’s something that can take “parameters” and return a value, just like a function. If we use a lambda as the value of the ‘default’ property, DataMapper will pass it the resource (or database record you’re working with) and the property itself (in this case, ‘slug’). So here, what we’re doing is taking the value inresource.title (the title property), putting it in lowercase, and using gsub method (think globalsubstitution) to switch every space to a dash. This way, something like this:

  1. “This is a Title”

Will become this:

  1. “this-is-a-title”

Note: Don’t get confused with how we’re using options here. First of all, remember that when a hash is the last parameter of a method, we don’t need to add the curly braces. Also, with Ruby 1.9, there’s a new hash syntax. Previously, hashes looked like this:

  1. { :key => “value” }

You can still do this in 1.9, and you have to if you you’re not using symbols as your keys. But, if you are using symbols as keys, you can do this instead:

  1. { key: “value” }

Basically, you just move the colon to the end of the symbol (no space!) and remove the rocket.

Validations

There’s a lot you can do with validation in DataMapper, and you can read all about it here. However, let’s take a look at the basics.

There are two ways to do validations; we’re going to use the method that adds your validations to the options hash. For the email property in the User model, we’ll set the format validation:

  1. property :email, String, format: :email_address

In this case, we’re using a built-in regex that DataMapper offers; we could put a custom regex there if we wanted something else.

Let’s require a certain length on the password:

  1. property :password, String, length: 10..255

If you’re not familiar with the 10..255 notation, that’s a Ruby range. We’re saying that the password must be between 10 and 255 characters long.

Associations

How about foreign keys? DataMapper makes this real easy. Let’s associate our User and Post models. We want a user to be able to have many posts, and a post to belong to a user.

In the User model, add this line

  1. has n, :posts

Then, in the Post model, do this:

  1. belongs_to :user

In the database, this adds a user_id property to a post table. In practice, it’s really easy; we’ll see this soon.

Custom Property Accessors

If you want to customize the input for a given property, you can add custom property accessors. For example, let’s say we want to make sure a user’s username is always stored in lowercase. We can add property accessor methods similar to the way you would in a normal class. This way, we take the value the user is trying to store and fix it up. Let’s do this:

  1. def username= new_username
  2. super new_username.downcase
  3. end

We’re defining the username=, so when the username is assigned, it will be lowercased. The super part just passes our value to this method’s super method, which is the one we are overriding.

Note: According to the documentation (see both here and here), we should be able to do @username = new_username.downcase in the method above. This is what I did in the screencast, and as you know, it didn’t work as expected. Since recording the screencast I’ve discovered that the documentation is wrong, and that super is the way to do this.


Step 5: Creating and Finding Records

Well, now that our models are created, let’s add a few records to test them out. We can do this a few ways. First, we can create a record with the new method, passing a hash of attributes, or assigning them individually.

  1. user = User.new username: “JoeSchmo”, firstname: “Joe”, lastname: “Schmo”, email: “joe@schmo.com”, password: “password_12345”
  2. user.save
  3. user = User.new
  4. user.username = “Andrew”
  5. # etc.
  6. user.save

When using User#new, you have to call the save method to actually put the record in the database. If there’s an error (remember those validations?), the save method will return false. Then, you can go to theerrors property to see the errors; it’s a DataMapper::Validations::ValidationsErrors object, but you can iterate over the errors with the each method.

  1. user.errors.each do |error|
  2. puts error
  3. end

If you want to make and save a record in one fell swoop, use the create method, of course passing it an attributes hash.

  1. User.create username: “joeschmo”, firstname: “Joe”, lastname: “Schmo”, email: “joe@schmo.com”, password: “password_!@#$%”

Boom: created and saved!

How about finding a record in the database? If you know the key of the record you’re looking for, just use the get method:

  1. User.get(1)
  2. Post.get(“this-is-a-title”)

Yes, you’re seeing that this works with both normal integer keys and other types of keys. Since we said the slug was the key in the Post model, we can get by slug.

What about those fields that could be the same for multiple records? You’ve got three options for that: first, last, and all. Just pass them a hash, and they get the records for you

  1. User.first firstname: “Andrew”
  2. User.last( :lastname => “Schmo”)
  3. User.all  #gets all the post

 

Share



Google brings flight search into the Jet Age

d

The new search, powered by the data and algorithms it got when it bought ITA Software for $700 million in April, can be found directly at Google.com/flights, or in its usual results when a user types in a query such as “flights from lax to atl.”

Google’s purchase of ITA Software was contested by many vertical travel search companies on the grounds of anti-competitiveness, but the feds ultimately approved the purchase in April, with a few conditions on Google’s licensing of the data to third parties. Microsoft’s Bing launched with its own travel search as a way to differentiate itself from Google, using predictive technology to counsel searchers on whether a fare price was likely to go up or down.

Trying out Google’s take on flight search, one can see why traditional flight search engines feared the deal. Google has clearly integrated ITA’s smart algorithms that make sense of ever-changing airline inventory with its massive search infrastructure.

The site’s defining feature? Speed. Results from flight searches show up almost instantly—which comes as something of a miracle, given how accustomed we’ve all become to ten second-waits to find a cheap fare to Boise, Idaho.

The search has the usual bells and whistles to refine searches and a nifty map.

Currently, booking a flight requires you to click over to an airline’s site, which isn’t always seamless since you may have to repick the exact flight when you hit the airline’s page. The flight search also gives you the option to limit a search to only one airline, but in the case of choosing Virgin America, Google seemed to have no data.

Despite those limitations, one can only assume that there have been better days inside companies such as Expedia, Orbitz, Kayak, and Hipmunk.

Share