One of the things I didn’t really care about when I was coming up with my Google Maps Craigslist mashup thing was the correctness of the database schema. I’ve written database schema before, but this time I just got sort of lazy. When porting the application to CakePHP, I realized it was a bad idea to slack off. Today I spent some time refactoring and adding a association table to the db.
I also learned some more MySQL syntax stuff. Previously, I had worked with Rails, which sort of handles the query making itself. Since I wrote a custom listing parser, I had to do some MySQL magic with JOINs and whatnot.
I also worked a lot on the Facebook puzzle that I wrote about earlier today. I came up with an approach that was better than the last one I came up with, but only slightly. It’s still in the range of O(n), so I’ll have to figure out the last “clever” thing before I’ve got it finished. It’s actually a lot more interesting now due to the efficiency constraints.
So I got a comment on my original post about the Facebook Programming Puzzle called “Prime Bits” that asked:
did you get this part ?
Your implementation should have a running time faster than O(n), where n is b - a.
id like to see how you solved it.
I felt really stupid for not catching that part until I checked the Google cache of the page. Apparently Facebook added that requirement some time after April 2nd and, presumably, getting a lot of inefficient entries (mine included).
It’s also funny to note that if you look at the actual html, there’s a fun message hidden in comments that reads “with ‘efficient’ meaning whatever you think it ought to mean.” Touché, facebook, touché.
Off the top of my head, I can think of a way using dynamic programming to make the problem a lot more efficient. I’m not sure whether or not it’s just an amortization hack, or an actual better than O(n) implementation, technically.
Okay, so I went ahead and coded up the dynamic programming version. The running time actually does increase at a less than O(n) rate, so I think it counts. Maybe I’ll plot out the running time growth for good measure. I believe it’s in the neighborhood of log(n). I guess I’ll send this new version along with my resume again, and see if they’ll respond this time 
Also, Rest in Peace, Mark Zuckerberg. You’ll be sorely missed.
When I searched for ‘prime numbers’ just now on Google, the first hit was a sponsored link for Ask.com. You would think it’s a conflict of interest for Google to be suggesting a competitor to its users. When you think about it, though, Google is also taking money from Ask.com, literally!
It’s especially strange seeing Ask.com advertising on Google so soon after being criticized for launching a guerrilla negative ad campaign against them…
Today technically counts as day 5 of my Craigslist and Google Maps Mashup thing since I didn’t work on it at all yesterday due to getting Command and Conquer 3: Kane Edition. I got the limited edition number 73137, which is cool since it’s a palindrome!
Anyway, today I actually did work a little bit on the mashup. I spent most of my time switching out from a random php output file to a CakePHP setup. I haven’t ever used CakePHP before, but I have used Ruby on Rails quite a bit. CakePHP is sort of like PHP’s answer to rails. It copies a lot of the ideas and conventions that Ruby on Rails expects developers to follow.
Because of the similarities between CakePHP and Rails, I found it pretty simple to migrate the PHP I already had to CakePHP. I just had to learn the proper syntax to get everything working in Cake. I still think Ruby is a really beautifully simple language to write code in. Cake tries to get things looking Ruby-ish, but there’s still some weirdness involved. It’s good for me to be learning these PHP things anyway, though. I’ve put PHP on the backburner for too long.
Tomorrow, if I have time to work on the project, I think I’ll implement the actual UI side of things. I have a rough idea of how I want users to be able to interact with the site. Hopefully designing the interface will be as easy as it is in Rails.
Today I made a bit more progress with my Craigslist Google Maps mashup thing. I setup the database table that handled the pictures for the listings, and added the images to the view as well. After that, I setup a new parser to parse the listings that can be found at the Michigan off-campus housing listings page. I’m not sure if I should make a separate page for these, or include them in the Craigslist listings…
I also came across a weird bug. When I ran the new Michigan parsing script by going to the page from a web browser, the thing would run fine, but after I uploaded to the server and ran it from the command line, it would flip out. It took me a really long time to figure out, but it turns out that I was calling a separate function by passing a value and not a reference.
I actually thought this might be a problem when writing the function, but when it worked, I forgot about the issue momentarily. The weird part is that the function works fine when you hit the .php file from a browser, and not when you run it from the command line. It must be some setting in the environment…
Besides that minor problem, everything seems to be going along smoothly. PHP has a lot of nice built in functionality for doing string manipulation, which this project has a lot of. It’s also got really nice networking and file reading capability. I guess that makes sense, since it originally came about as a tool for creating websites.
Tomorrow I’ll try to get the mashup site setup with actual options and navigation. Right now it’s just set on Ann Arbor. I’ll have to do some routing to get the many different options that people might want set up.
Recent Comments