Monthly Archives: February 2013

JenPop: genetic populations in your hands

I’ve started developing a new hobby project (yeah, why not finish the other projects first?), that can create entire generations of nodes based on a single parent, according to the rules and score methods you provide! It’s JenPop (if you didn’t guess, J is for Java :D, Gen is for genetic, Pop is for population) and I already have code to throw at you!

At the moment, only 2 features are available:

  • Create generations and children (of any object) based on the rules you provide, from a parent class extending GeneticNode;
  • Get node scores and best nodes based on the rules you provide;

And as a bonus, a sample of Tic Tac Toe implementing the above features, that will never lose. Can’t lose even when playing against itself! 😀 For the moment, the only way you can download and use it is by downloading the tarball from my Google Drive, but I’ll host the project online as soon as I decide where to.

As the next step, I’m aiming into being able to process the best “path” to use after calculating nodes from many generations, looking at the possibilities from the current state. After that, I think I’ll implement some cross-over methods, so that you can “diverse” your population, it’s useful for some problems.

Needless to say, I’m quite happy with the results at this moment.

See ya!

Scheduled posts, week content teaser: genetic algorithms, project hosting

So this is my first scheduled post. 😀 After this one, I plan to schedule all the others, to keep content flowing at a constant rate, at least once a day.

I’ve updated my about page, put some more information, including linkedin information and profiles.

Will work towards or research a bit on “genetic algorithm frameworks” on Java. I’ve created one for a tic-tac-toe project during college, would like to have something flexible for now. Will this become my first public open source project? 😀 I guess so! More on that during the week!

Also, where to host it? Github? SourceForge? Google Code? Microsoft CodePlex? More into it during the week!

See? Plenty new things to talk about! 😀 See you later!

As far as motivation goes…

So I find myself at this wonderful weekend, nothing to do but fun stuff, including writing to the blog. If you can’t see posts from the mentioned period, well, you can already guess what’s going on. It’s been hard to focus and code/write while at home. I only tend to do it when I’m alone, and so far, it’s been a complete mess.

Apart from playing with XBMC (installed some games, emulators/roms, played with radio-streaming playlists, will dedicate posts for those in the future) and watching Saint Seiya episodes on youtube (oh old times… :D) nothing of value was generated. Also, headaches took a great deal of my will to do things and get up from bed.

And today, after I found that my old IBAK tablet (those cheap custom android things) is working again (it tends to stop working from time to time, and function again after a week of two of deep unchgarged rest), I’ve decided to read some more of Steve Jobs’ biography, which is great and inspiring. Not that I think he’s a role model (far from that, as a person he played pretty awfully with others, check Folklore.org or read the book for some examples), but his will to change the way things were done seems to motivate me. So much that I actually got out of bed (it’s 10 PM atm), and wrote this post.

I’m figuring out how to pipeline daily posts into wordpress so that I have content everyday and keep the writing to “when I can”. See you tomorrow! 😉

Tibia time: Carlin’s Explosion

Well, I’m an old Tibia MMORPG player (Jack Bouer used to be my main character) and even after retiring, I continued to back it’s (at the time vibrant) community for a while, be it by drawing the infamous TibiaNews’ Comic Strips (removed from the original server, re-uploading to my gDrive… soon) and the original TibiaScoop.com (merged with TibiaNews.net, apparently) games that I’ve launched. There was one game that I’d like to start, which was Carlin’s Explosion.

You’re a powerful bloodthirsty player, and clueless newbies are trying to get to the depot at all costs. Magically rewarded with infinite mana points, you decide to stop them by launching waves of the most powerful attack spell (at the time) the Ultimate Explosion! Kill as many newbies as you can before they fill the depot!

It contained an online highscore mechanism (that I can’t host for now, so it is disabled) where site members could compete. 🙂 Beside being based on the original tibia sprites, all artwork was remade by me (CipSoft complained at the time about using the original Tibia artwork on it). So, here it is! The infamous Java-based game, Carlin’s Explosion (hosting is for now a courtesy of Google Drive)! 😀

Java package download (run with hopefully just a double-click, or with a “java -jar CarlinExplosion.jar”).

Since I can’t host the jar with direct access (for an applet version), some screenshots:

Title Screen

Instructions Screen

Gameplay

Game Over Screen

I’ll upload the source code and artwork soon, after some quick review! 😀 Happy gaming!

CodeJam 2009 Qualification C

Will deliver some more posts today! 😀 Gotta hurry!

This time we’ll focus on Qualification C problem, entitled Welcome to Code Jam.

So you’ve registered. We sent you a welcoming email, to welcome you to code jam. But it’s possible that you still don’t feel welcomed to code jam. That’s why we decided to name a problem “welcome to code jam.” After solving this problem, we hope that you’ll feel very welcome. Very welcome, that is, to code jam.

If you read the previous paragraph, you’re probably wondering why it’s there. But if you read it very carefully, you might notice that we have written the words “welcome to code jam” several times: 400263727 times in total. After all, it’s easy to look through the paragraph and find a ‘w’; then find an ‘e’ later in the paragraph; then find an ‘l’ after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase “welcome to code jam”.

To be more precise, given a text string, you are to determine how many times the string “welcome to code jam” appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], …, input[s[18]] is the string “welcome to code jam”.

The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.

Yeah… like it would make any difference, besides the trimmed result… 😛

Here’s our code:

# "Constants" - gotta be careful because there's no native solution in python
target = "welcome to code jam"
nullify= '-'

# Our "solve for X" function
def rec(line, pointer, letterIndex, times):

    #If our letterIndex turned out the same as our phrase length, we can count
    if (letterIndex == len(target)-1):
        times += 1
        return times

    #If not, we've got work to do. While we still have the current expected letter on the string, do
    while line[pointer:len(line)].count(target[letterIndex+1]) > 0:
        #print "Searching letter %c, %d occurrences left on line \"%s\" from position %d" % (target[int(letterIndex+1)], line[pointer:len(line)].count(target[letterIndex+1]), line, pointer)

        #Go look for the next letter, from where the current letter is
        times = rec(line, line.index(target[letterIndex+1], pointer, len(line)), letterIndex+1, times)
        #"Erase" our current letter position, so we don't search it again from here
        line = line[:pointer]+line[pointer:len(line)].replace(target[letterIndex+1], nullify, 1)

    return times

# Get header
line = raw_input()
cases = int(line)

# Solve test cases
for i in range(cases):
    line = raw_input()

    times = 0
    letterIndex = -1
    pointer = 0

    times = rec(line, pointer, letterIndex, times)

    # Prints only last 4 digits
    fnum = "%04d" % times
    print "Case #%d: %s" % (int(i+1), fnum[max(0,len(fnum)-4):len(fnum)])

exit()

I’ve added comments on the code to describe what it does (I love command cascades, as you can see with all these connected string splits), but essentially:

  • Read phrase;
  • Start from position 0 on recursive function;
  • The function first checks if we’re looking for beyond the last “welcome to the code jam” letter; scores a point if so 🙂
  • Not being at the end, checks if we have the expected letter on the phrase;
  • If we have, branches to look for the next letter from the current letter and mark so it won’t be searched again;
    else, return how many times we could complete “welcome to code jam” with phrase letters so far.

Evolving the posts with small and clear code (at least for my standards) is the intention, guess I could make it this time. 🙂 Happy jammin’!

CodeJam 2009 Qualification B

Aaaaaand here we are!

So, link to the problem entitled Watersheds:

http://code.google.com/codejam/contest/90101/dashboard#s=p1

And it says:

Geologists sometimes divide an area of land into different regions based on where rainfall flows down to. These regions are called drainage basins.

Given an elevation map (a 2-dimensional array of altitudes), label the map such that locations in the same drainage basin have the same label, subject to the following rules.

  • From each cell, water flows down to at most one of its 4 neighboring cells.
  • For each cell, if none of its 4 neighboring cells has a lower altitude than the current cell’s, then the water does not flow, and the current cell is called a sink.
  • Otherwise, water flows from the current cell to the neighbor with the lowest altitude.
  • In case of a tie, water will choose the first direction with the lowest altitude from this list: North, West, East, South.

Every cell that drains directly or indirectly to the same sink is part of the same drainage basin. Each basin is labeled by a unique lower-case letter, in such a way that, when the rows of the map are concatenated from top to bottom, the resulting string is lexicographically smallest. (In particular, the basin of the most North-Western cell is always labeled ‘a’.)

So, looks like a path problem. As a path problem, we need to calculate which route to use based on series of rules, like walking through a map and choosing where to go next. Since usually the same deciosion applies to all “map units”, recursion is your friend. 🙂

To the I/O Rules:

Input

The first line of the input file will contain the number of maps, TT maps will follow, each starting with two integers on a line — H and W — the height and width of the map, in cells. The next H lines will each contain a row of the map, from north to south, each containingW integers, from west to east, specifying the altitudes of the cells.

Output

For each test case, output 1+H lines. The first line must be of the form

Case #X:

where X is the test case number, starting from 1. The next H lines must list the basin labels for each of the cells, in the same order as they appear in the input.

For each problem, there’s an array filled with height values. What we need to do is fill these arrays with letters, starting from ‘a’. The rules are quite simple:

To better explain the rules, I’ll separate the neighboors in two classes: path neighboors and loop neighboors.

  • Path neighboors: map units that belong to the same “route” and are next to each other. The ones we choose to move to.
  • Loop neighboors: map units that our loop tells us to go to. Usually, loops iterate through arrays the same way: through lines, left to right. Our loop neighboor will be the next neighboor which the loop tells us to go.

For each block, do:

  • Check our number. Are we already a letter on the result? If so, move to the loop neighboor, else, go on.
  • Check the 4 neighboors. Is our number bigger than theirs? No? Then we’re a sink. Write our letter on the result, increase the current letter, move to next neighboor. If our number is bigger, keep going… 😉
  • Which neighboor has the lowest number? There’s a tie? Ok, then let’s choose based on the priorities: North, then West, then East and South. If there’s no tie, choose the lowest. Write our letter and go to the chosen neighboor. 🙂

And… here’s the code. It’s old and really bad written, so be careful. Haven’t tested it recently but I guess it works. If it doesn’t, well… tell me! 😀

from numpy import *
from array import *

alphabet = "abcdefghijklmnopqrstuvwxyz"
cur_basin = 0
ma = [['a']]

"""
N W E S
"""

def rec( m, ma, h, w, l, a, cur_basin):
    lv = 65535
    lh = 0
    lw = 0

    if (l != 0):
        if (m[l-1][a] < lv):
            lh = l-1
            lw = a
            lv = m[lh][lw]
    if (a != 0):
        if (m[l][a-1] < lv):
            lh = l
            lw = a-1
            lv = m[lh][lw]
    if (a != w-1):
        if (m[l][a+1] < lv):
            lh = l
            lw = a+1
            lv = m[lh][lw]
    if (l != h-1):
        if (m[l+1][a] < lv):
            lh = l+1
            lw = a
            lv = m[lh][lw]

    if ma[l][a] < 'a':
        if lv >= m[l][a]:
            cur_basin+=1
            ma[l][a] = alphabet[cur_basin]

        else:
            if ma[lh][lw] >= 'a':
                ma[l][a] = ma[lh][lw]

            else:
                cur_basin+=1
                ma[l][a] = alphabet[cur_basin]
                ma[lh][lw] = ma[l][a]
    else:
        if lv > m[l][a]:
            if (l != h-1):
                ma,cur_basin = rec(m, ma, h, w, l+1, a, cur_basin)
            elif (a != w-1):
                ma,cur_basin = rec(m, ma, h, w, l, a+1, cur_basin)
            elif (a != 0):
                ma,cur_basin = rec(m, ma, h, w, l, a-1, cur_basin)
            elif (l != 0):
                ma,cur_basin = rec(m, ma, h, w, l-1, a, cur_basin)

        elif lv < m[l][a]:
            if ma[lh][lw] < 'a':
                ma[lh][lw] = ma[l][a]

    return ma,cur_basin

line = raw_input()

cases = int(line)

for i in range(cases):
    header =  str.split(raw_input())
    h = int(header[0])
    w = int(header[1])

    m = zeros((h,w))
    ma = [['a']]

    cur_basin = 0
    maxh= 0

    for l in range(h):
        mapline = str.split(raw_input())
        ma.append(mapline)
        if l == 0:
            ma.pop(0)
        for a in range(len(mapline)):
            m[l][a] = int(mapline[a])
            maxh = max(maxh,m[l][a])

    ma[0][0] = alphabet[cur_basin]

    for l in range(h):
        for a in range(w):
            ma,cur_basin = rec(m, ma, h, w, l, a, cur_basin)

    print "Case #%d:" % int(i+1)
    for l in range(h):
        for a in range(w):
            if a < w-1:
                print "%c" % ma[l][a],
            else:
                print "%c" % ma[l][a]

exit()

I don’t remember why I decided to use “inverted axis” (at least for me, using “lines, columns” isn’t usual as I rather do “columns, lines” for positioning) and why it’s so bad to read (hurry?).

Well, happy coding, I guess! 😛