Google Code Jam – Rotate

It’s time for some basic finger exercise. The Google Code Jam Rotate is very trivial, so relax and fire up your IDE.

I was a bit lazy, so there is no reading of the input sets, just a two-dimensional array and two functions

Rotating

As the Google solution pointed out, there is actually no need to really rotate the 2dim array. Just push everything to the right, as if gravity would be to the right. That’s the same as rotating everything and keeping gravity towards the bottom. But we save a few lines this way.

So here is the “gravity from the right” code

public static void fakeRotate(char[][] board) {

    for (int i = 0; i < N; i++) {
        for (int j = N - 1; j >= 0; j--) {
            if (board[i][j] != '.') {
                // push to right
                int m = 1;
                while ((j + m) < N && board[i][j + m] == '.') {
                    board[i][j + m] = board[i][j + (m - 1)];
                    board[i][j + (m - 1)] = '.';
                    m++;
                }
            }
        }
    }
}

Checking for a winner

Now we have everything ready to look for a winner. I decided to start from the top left and walk through the game board step by step. I keep going right till I'm at the end, then go to the beginning of the next line.
Progressing this way, I only need to check in four directions. Towards right, bottom, diagonally upwards-right and diagonally downwards-right.

public static void checkForWinner(char[][] board) {
    boolean redWins = false;
    boolean blueWins = false;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] != '.') {

                // winning once is good enough
                if (board[i][j] == 'B' && blueWins == true) {
                    break;
                }
                if (board[i][j] == 'R' && redWins == true) {
                    break;
                }

                // check to the right
                int m = 1;
                while (j + m < N && board[i][j + m] == board[i][j]) {
                    if (++m == K) {
                        switch (board[i][j]) {
                        case 'R':
                            redWins = true;
                            System.out.println("RED");
                            break;
                        case 'B':
                            blueWins = true;
                            System.out.println("BLUE");
                            break;
                        }
                    }
                }

                // check bottom
                m = 1;
                while (i + m < N && board[i + m][j] == board[i][j]) {
                    if (++m == K) {
                        switch (board[i][j]) {
                        case 'R':
                            redWins = true;
                            System.out.println("RED");
                            break;
                        case 'B':
                            blueWins = true;
                            System.out.println("BLUE");
                            break;
                        }
                    }
                }

                // check diagonal bottom
                m = 1;
                while (i + m < N && j + m < N && board[i + m][j + m] == board[i][j]) {
                    if (++m == K) {
                        switch (board[i][j]) {
                        case 'R':
                            redWins = true;
                            System.out.println("RED");
                            break;
                        case 'B':
                            blueWins = true;
                            System.out.println("BLUE");
                            break;
                        }
                    }
                }

                // check diagonal top
                m = 1;
                while (i - m >= 0 && j + m < N && board[i - m][j + m] == board[i][j]) {
                    if (++m == K) {
                        switch (board[i][j]) {
                        case 'R':
                            redWins = true;
                            System.out.println("RED");
                            break;
                        case 'B':
                            blueWins = true;
                            System.out.println("BLUE");
                            break;
                        }
                    }
                }

            }

        }

    }

}

That's a bit of copy and paste, maybe you have a better solution.

That was already it. Not much to say, is there?

If you're bored you can do some improvements and share it in the comments.

  • optimize the code for checking for a winner, e.g. stop checking if the space is not sufficient for K stones to win
  • use multiple threads to check the board
  • write a parser to read the input file from the Google Code Jam

I hope you had some fun, questions and improvements are welcome. If you want to submit a patch write me using the contact form.

The code can be found as usual on github

Google Code Jam – Theme Park

Theme Park is another good example of a problem which can be solved with a fairly simple algorithm. The simple version will solve the small input set without a problem, but will run almost infinitely with the large dataset.

You can read the problem on the Google Code Jam site: Theme Park

simple solution

The simple solution is to put the groups in a static array, use a pointer that “wraps around” using modulo and fill the roller coaster until it’s so full, that the next group does not fit in, then let it ride earning income accordingly to the seats taken.

This is a correct solution, but unfortunately a bit slow. The input set can have a roller coaster with up to 109 seats and 108 rides and groups as large as 107.

So going through each entry every time step by step would use a lot of calculation time. The be precise, that would be O(NR).

simple optimization, brining it down to O(N)

As you can see, the roller coaster runs way more often than groups stand in line. So to some point, you will reach a group which has already been in the roller coaster as first group. And that’s the exact situation we’re looking for.

Every time we fill the roller coaster, we store the position of the first group who enters the ride, remember how many people went in and store the position of the group which will fill the roller coaster first on the next run. If we then check before the run, if this group has been in first, we already know the result and we know, that from thereon we know the subsequent groups.

From this point on we can iterate on our stored results and performance increases to O(R), that’s a speed up of at least 103.

Google Code Jam – The Snapper Chain

The Google problems are always nice, sometimes even a bit too tricky. This years entry problem was quite nice with some difficulties you could run in.

You need to read the problem first, to follow the article, so here’s the link: http://code.google.com/codejam/contest/dashboard?c=433101#s=p0&a=0

If you’re a hands on programmer first you might just want implement the chain without looking at the problem more extensively. So you might end up with something like this:

                        // snapping
// snapping
boolean toggle = true;
for (int j = 0; j < snaps; j++) {
	toggle = true;
	for (int k = 0; k < snapperCount; k++) {
		if(toggle == false){
			break;
		}
		if (toggle == true) {
			snapper[k] = !snapper[k];
		}
		if (snapper[k] == true) {
			toggle = false;
		}

	}
}

// we need power on all snappers
boolean power = true;
for (int j = 0; j < snapperCount; j++) {
	if (snapper[j] == false) {
		power = false;
		break;
	}
	
}

Continue reading

Are you producing banana software?

Bananas are picked from the tree green and unripe. Their ripening process continues while they are transported to the markets and end up at the customer. Let us just ignore the fact, that the ripening process is initiated by an artifical condition.

So Banana-Software is software, that “ripes” while in production at the customer. Some people might call it Beta-Software. I’ve seen plenty of examples where software went into production when it was still Banana-Software.

There’s nothing bad in developing software in close contact with the customer. Eg. using Extreme Programming, Rapid Prototyping or some other agile method you prefer. But when it comes to putting software into production, there are some things to consider.

Before you ship, make sure that:

all quick and dirty hacks are removed

Leaving hacks in a software is a major crime. Not that it will not work, but in the future when extending the software they might break your neck. So take the time and clean up messy implementations and refactor, if needed.

the business cases are covered with unit tests

There’s nothing worse than when your application stores or processes data wrongly. Cleaning up the data might take long time, and might not even be possible without your customer doing some work again. So it’s mandatory to write test cases for you business layer.

check for bottlenecks

Of course your software runes fine on you development machine with you being the sole user. So try a performance or stress test to check for bottlenecks. A profiler will also show you where you can expect some problems.

the customer has seen a beta version and did not detect major flaws

If you did not develop in a model with close customer contact you should at least show him a version which is close to shipping, before you start polishing the frontend. Now is the right time to detect major misunderstandings, if there are any. Also discuss some ideas for the GUI that would make life for the user easier.

the software is properly archived and the build process is future safe

So two years later you should extend NoBanana-Soft v1.0. The big problem is, where’s the code to build the version you actually shipped? And if you still find it, does it still build?
That’s really not something you need to find out. Your VCS should have taken care of the first problem and your CIS of the second.
If you’re not using VCS or CIS, start now !

the software is well documented and there is a installation and maintainance manual

There should be a quick introduction on how to install the software and all the requirements to get it to run. A little architecture diagram for developers is always nice. So take the time to document everything necessary to know. So whenever someone has to digg out the software for whatever reason, he does not have to start by reading the source to get a knowledge of what it does.

Google Code Jam – Africa Qualification Round 2010

The Google Code Jam is an interesting option to work on some challenging problems.
With the first qualification round coming up at May 7th, it’s time to look at the Africa qualification round, to see what to expect.

You have 24 hours to solve three rather simple problems. Solving two problems brings you into the next round.

I will present my Java solutions. The Code Jam site provides the code of every contestant.

Store Credit

read problem description
You just need two nested loops to find the matching articles. Just a finger exercise.

for (int i = 0; i < items.size(); i++) {
			for (int j = i + 1; j < items.size(); j++) {

				// is this the right shopping?
				int newSum = items.get(i) + items.get(j);

				if (newSum == credit) {
					return "Case #" + caseNr + ": " + (i + 1) + " " + (j + 1);
				}
			}

}

Reverse Words

read problem description
Just reverse a list of words? Guess that's doable. Well, the code is not elegant, but it works.

for (int i = 1; i <= cases; i++) {
			out.writeBytes("Case #"+i+": ");
			String[] words = in.readLine().split("\\ ");
			List<String> wordList = Arrays.asList(words);
			Collections.reverse(wordList);
			for(Iterator it = wordList.iterator(); it.hasNext();){
				out.writeBytes(it.next()+" ");
			}
			out.writeBytes("\n");
}

T9 Spelling

read problem description
The first task with a little challenge. You have to insert a break when you have letters on the same numeric button. So I checked if the previous button is the same as the recent on. If yes, insert a break. So you can separate AB (2 22) from BA (22 2). That's all.

public class T9Spelling {

	/**
	 * @param args
	 */

	static HashMap<String, String> t9Map;

	public static void main(String[] args) throws NumberFormatException,
			IOException {

		FileInputStream inFile = new FileInputStream(new File(
				"C-large-practice.in"));
		DataInputStream in = new DataInputStream(inFile);
		FileOutputStream outFile = new FileOutputStream(new File("out.txt"));
		DataOutputStream out = new DataOutputStream(outFile);

		int cases = Integer.parseInt(in.readLine());

		t9Map = new HashMap<String, String>();
		fillMap();

		for (int i = 1; i <= cases; i++) {
			out.writeBytes("Case #" + i + ": ");
			String t9, t9last = "";

			String text = in.readLine();
			for (int j = 0; j < text.length(); j++) {

				t9 = t9Map.get(String.valueOf(text.charAt(j)));
				
				// do we need a break? (letters are on same button)
				if (j > 0 && (t9.charAt(0)) == t9last.charAt(0)) {
					out.writeBytes(" ");
				}

				out.writeBytes(t9);
				t9last = t9;
			}
			out.writeBytes("\n");
		}

	}

	public static void fillMap() {
		t9Map.put("a", "2");
		t9Map.put("b", "22");
		t9Map.put("c", "222");
		t9Map.put("d", "3");
		t9Map.put("e", "33");
		t9Map.put("f", "333");
		t9Map.put("g", "4");
		t9Map.put("h", "44");
		t9Map.put("i", "444");
		t9Map.put("j", "5");
		t9Map.put("k", "55");
		t9Map.put("l", "555");
		t9Map.put("m", "6");
		t9Map.put("n", "66");
		t9Map.put("o", "666");
		t9Map.put("p", "7");
		t9Map.put("q", "77");
		t9Map.put("r", "777");
		t9Map.put("s", "7777");
		t9Map.put("t", "8");
		t9Map.put("u", "88");
		t9Map.put("v", "888");
		t9Map.put("w", "9");
		t9Map.put("x", "99");
		t9Map.put("y", "999");
		t9Map.put("z", "9999");
		t9Map.put(" ", "0");
	}

}

Round 1 was quite simple, wasn't it? There's still time to register.
See you in the contest.

Using an EntityManagerFactory with JPA, Hibernate and Wicket

If you read the previous article “@OneToMany Relationship with Java, Hibernate and Annotations” you might have noticed some
imperfections in the persistence layer. On the code side we have been
lazy by just using FetchType.EAGER. This of course puts extra stress on
the database, because in our example, for each BlogPost all Comments are
fetched, even though they might not be displayed.

Maybe you played around with the example
version 0.1.1(download tarball).
You might have noticed that if you switch to FetchType.LAZY you will
most likely get a no session or session was closed on certain operations.

Let’s take a closer look on where we did get our Session from
 

// in BlogPostDAO
Session session = HibernateUtil.getSession();

<pre class="prettyprint">
// in HibernateUtil
public class HibernateUtil {

    private static final SessionFactory sessionFactory;
    static {
        try {
            AnnotationConfiguration configuration = new AnnotationConfiguration();
            configuration.addAnnotatedClass(BlogPost.class);
            configuration.addAnnotatedClass(Comment.class);
            sessionFactory = configuration.buildSessionFactory();

        } catch (Throwable ex) {
            // Log exception!
            throw new ExceptionInInitializerError(ex);
        }
    }

    public static Session getSession() throws HibernateException {
        return sessionFactory.openSession();
    }

}

As you can see, we open a new Session each time we request a Session via
getSession(). Each DAO file did get its own Session which it closes
after using. So operating on a lazy initialized class member does give a
no session or session was
closed

error. Because by the time you want to display the comments, the Session
is already closed. Hibernate did use proxy objects (read more on
Proxy Visor Pattern
) instead of the real comments. Now the first read access hits the
Comments member, and Hibernate needs to load the content from the
database, but the Session is already closed.

Now is the time to take the design up a notch by introducing Spring 3
into the project. We’re especially looking at the
LocalContainerEntityManagerFactoryBean
. We use it to set up a JPA EntityManagerFactory and pass it into our
persistence layer using dependency injecton.

There is a really good example on how to do this with Wicket, it’s
called powerblog and it can be found here:
tutorialWicketSpringJPAHibernateCore

As you can see I updated yawblog using a setup similar powerblog’s. You find the
yawblog
source on github
.

If you look into YawJPAImpl you will recognize that the EntityManager is used to handle all
database operations. The spring context is set up, that the YawJPAImpl
is a bean available to the Wicket application. Whenever you need access to the persistence layer, you can get the bean
using the
@SpringBean
annotation.

public class BasePage extends WebPage {
    @SpringBean(name = "yawData")
    protected YawJPAImpl yawData;

    @Override
    protected void onBeforeRender() {
        super.onBeforeRender();
        Application.get().getMarkupSettings().setStripWicketTags(true);
    }

    public BasePage() {
        add(new Label("navigation_panel", yawData.getPage("navigationPanel").getContent()).setEscapeModelStrings(false));
        add(new Label("right_sidebar", yawData.getPage("rightSidebar").getContent()).setEscapeModelStrings(false));
        add(new Label("dashboard", yawData.getPage("dashboard").getContent()).setEscapeModelStrings(false));
        add(new Label("footer", yawData.getPage("footer").getContent()).setEscapeModelStrings(false));
    }
}

Now you can use the member yawData to access the persistence layer in
every page which extends BasePage.

@OneToMany Relationship with Java, Hibernate and Annotations

NOTE: There is a follow up here: <a href="http://unitedcoderscom.appspot.com/nico-heid/using-an-entitymanagerfactory-with-jpa-hibernate-and-wicket">Using an EntityManagerFactory with JPA, Hibernate and Wicket</a> which fixes some design flaws.</cite>

If you followed the first article on hibernate: <a href="/nico-heid/java-persistence-hibernate-annotations">Java persistence with Hibernate and Annotations</a> you might be interested in how to create relationship between classes (or sql tables).

Let's pretend we're writing a little blog software. We only need articles and comments. To keep it simple, one article can have many comments. Comments can have no comments.

The database, once filled, should look like this:

<blockquote>
mysql> select * from BlogPost;
+-------------+-----------------------------+---------------------+--------------------------+-----------+----------------+
| BLOGPOST_ID | content                     | date                | path                     | published | title          |
+-------------+-----------------------------+---------------------+--------------------------+-----------+----------------+
|           1  | the content blows your mind | 2010-01-12 14:25:24 | /2010/01/a_monster_title | Y         | a moster title | 
+-------------+-----------------------------+---------------------+--------------------------+-----------+----------------+

mysql> select * from Comment;
+------------+---------------------+----------------------+
| COMMENT_ID | comment             | blogPost_BLOGPOST_ID |
+------------+---------------------+----------------------+
|          1 | and a lousy comment |                    1 | 
+------------+---------------------+----------------------+

</blockquote>

Simple enough. Because we're lazy and we've learned a bit since the last article, we let hibernate create the tables for us. Therefor add hibernate.hbm2ddl.auto=create-drop to your hibernate.properties file.

Now we take a look at the two Java classes we need. First the BlogPost:

<pre class="prettyprint">
import java.io.Serializable;
import java.util.Date;
import java.util.Set;

import javax.persistence.CascadeType;
import javax.persistence.Column;
import javax.persistence.Entity;
import javax.persistence.FetchType;
import javax.persistence.GeneratedValue;
import javax.persistence.GenerationType;
import javax.persistence.Id;
import javax.persistence.OneToMany;
import javax.persistence.Table;

import org.hibernate.annotations.Type;

import com.unitedcoders.yawblog.persistence.dao.PersistenceUtil;

@Entity
@Table(name = "BlogPost")
public class BlogPost extends PersistenceUtil implements Serializable {

	private Long id;
	private String title;
	private String content;
	private Boolean published;
	private Date date;
	private String path;
	private Set<Comment> comments;
	
	@Id
	@GeneratedValue(strategy=GenerationType.AUTO)
	@Column(name="BLOGPOST_ID")
	public Long getId() {
		return id;
	}

	public void setId(Long id) {
		this.id = id;
	}

	@Column
	public String getTitle() {
		return title;
	}

	public void setTitle(String title) {
		this.title = title;
	}
	
	@Column
	public String getContent() {
		return content;
	}

	public void setContent(String content) {
		this.content = content;
	}

	@Column
	@Type(type="yes_no")
	public Boolean getPublished() {
		return published;
	}

	public void setPublished(Boolean published) {
		this.published = published;
	}

	@Column
	public Date getDate() {
		return date;
	}

	public void setDate(Date date) {
		this.date = date;
	}

	@Column
	public String getPath() {
		return path;
	}
	
	@OneToMany(fetch=FetchType.EAGER, cascade = CascadeType.ALL, mappedBy="blogPost")
	public Set<Comment> getComments() {
		return comments;
	}

	public void setComments(Set<Comment> comments) {
		this.comments = comments;
	}

	public void setPath(String path) {
		this.path = path;
	}

}

And the comments:

import java.io.Serializable;

import javax.persistence.AssociationOverride;
import javax.persistence.CascadeType;
import javax.persistence.Column;
import javax.persistence.Entity;
import javax.persistence.FetchType;
import javax.persistence.GeneratedValue;
import javax.persistence.GenerationType;
import javax.persistence.Id;
import javax.persistence.JoinColumn;
import javax.persistence.ManyToOne;
import javax.persistence.Table;

@Entity
@Table(name = "Comment")
public class Comment extends Serializable {

        private Long id;
	private String comment;
        private BlogPost blogPost;
	
	
	@ManyToOne(fetch = FetchType.EAGER)
	public BlogPost getBlogPost() {
		return blogPost;
	}

	public void setBlogPost(BlogPost blogPost) {
		this.blogPost = blogPost;
	}

	@Id
	@GeneratedValue(strategy=GenerationType.AUTO)
	@Column(name="COMMENT_ID")
	public Long getId() {
		return id;
	}

	public void setId(Long id) {
		this.id = id;
	}

	@Column
	public String getComment() {
		return comment;
	}

	public void setComment(String comment) {
		this.comment = comment;
	}

}

As you can see, the mapping magic is just a few annotation. In BlogPost you define the Comments as @OneToMany. Important is the mappedBy, this has to point to the member in the target class (Comment). In the Comment class itself you have to define the @ManyToOne relationship. Because the annotations are directly above the class names, hibernate knows which tables it has to map to each other.

And because we want to try it, here's some sample code for filling the DB

                // s2 is the hibernate session, however you want to create it
        	BlogPost bp = new BlogPost();
		bp.setTitle("a moster title");
		bp.setContent("the content blows your mind");
		bp.setDate(new Date());
		bp.setPath("/2010/01/a_monster_title");
		bp.setPublished(true);
		
		
		Set set = new HashSet();
		Comment c = new Comment();
		c.setComment("and a lousy comment");
		set.add(c);
		bp.setComments(set);
		c.setBlogPost(bp);
		s2.save(bp);
		s2.close();

That's it.

The full source and overhead can be found on github: http://github.com/nheid/yawblog
Check it out with: git clone git://github.com/nheid/yawblog.git v0.1.1

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close