Brad Gunn

So, I recently met with the dev team over at http://www.lot18.com/ and they’ve inspired me to maintain this blog a great deal more. It’s been a while since I was challenged in such a way that inspires me to push forward. As a web developer, including the lot18 developers, often we do not get to utilize that fancy CS degree as our day to day really isn’t enthralled in algorithms and such.

They posed two questions at different points that can be answered with one response.

Question 1: How do you remove duplicate strings from an array of N length?

Question 2: How do you think the classic analogue T9 auto complete might have worked?

My answer?
- A tree map that utilizes a hash lookup. Theoretically O(log n )

I don’t believe they were too happy with my 30 second off the cuff answer, but it wouldn’t exactly be wrong. I had to explain what I meant and they gave me a puzzled answer. They believed that the hash generation would be too expensive.

My new answer?
- http://en.wikipedia.org/wiki/Trie A trie data structure.

A trie data structure is similar to my concept but offers a few additional benefits. When you construct the trie you automatically ensure that duplicates are removed. If you value order, while doing your insertion you can mark which index ( or just remove it ) from your array. The benefit here is the data structure itself. Once constructed, you now have a fully traversable tree in N time with a low multiplier.

This means that the tree can be constructed around your numeric pad 1 – 0 # *. Each button representing a node that can be searched at most 4 times ( 3 numbers per key, some 4 ). Each node can be assigned a weight for how many times you have favored a certain path.

giving it further thought, this was a rather brilliant way to make the most out of those old phone processors!

I’ll be writing a Trie data structure in PHP shortly and sharing it. Although it would be far from the most optimized solution ( C lib would be best ) … it would provide a nice test for creating that library later on!

( if your goal is to only remove duplicates, a sort and forward comparison works a lot better. If your goal is to remove duplicates and store strings for manipulation, trie is the best )

I spent a few hours on trying to figure out why this wasn’t doing what I wanted it to do.

My setup: I was creating a dynamic form wizard that would load steps forward and backward dynamically via ajax. Processing server side would determine what step you should fill out next based upon choices you already filled out in the form.

Each one of these forms was using ajax validation. My problem was that as soon as a single form was validated, any number of future forms would not validate. Do you know what the trick is? A unique ID. (yep that simple).

My code looked like this:

$form=$this->beginWidget(‘CActiveForm’, array( ‘id’=>$formId, ‘enableAjaxValidation’=>true, ‘enableClientValidation’=>false, ‘clientOptions’=> array(‘validateOnSubmit’=>true,’afterValidate’=>$js,’validationUrl’=>’/main/regvalid’), ));

As soon as you change ‘id’ to something meaningful, you can have any number of ajax validated forms work on the same page. Neat huh? This may be something people take for granted, as they may have simply made unique names from the get-go… but this complex way of tracking steps really bit me in the ***. When you hit the ‘back’ button, validation would not work — why? Yii already marked that ID as validated. So even when you hit back, I had to reset the ajax by reloading the entire thing.

This may save some one a few hours of debugging. My form wizard is now awesome!

I am a few days late on this news, but Yii 1.1.8 was released on June 26th. This comes 3 months after 1.1.7 was launched late March and provides a laundry list of bug fixes and a few enhancements.

Most of the bug fixes, I’ve never come across and I have been using Yii for quite a while. Usually things I’ve come across land up being developer error! More posts to come on that topic in the future.

If you haven’t used Yii yet, you should check it out. Sure, it’s one of a dozen PHP frameworks — but it brings some new concepts to the table. Like some other ORMs, it offers two ways to interact with the database. Each with it’s own strengths and weaknesses. On top of that, everything that can be lazily loaded is lazily loaded (take that Drupal!) That includes queries. If you do model->together(‘join’) until you do $data->join .. that join is simply not executed.

That is the most useful for 1 to many or many to many joins. If you encapsulate that query and do not use the data in the join, the query is spared saving resources.

What else does Yii offer? Scenarios. How often have you tried to create a a user based system using ORMs? You create your registration form and set the password as required. Every time that user attempts to change their data your ORM complains about their password being missing!

So, instead you can set scenarios. 1 for registraion, 1 for profile updates, 1 for password updates etc etc!

If you haven’t checked out Yii — I suggest you do! I’ll be posting more on Yii in the times to come.

Welcome to WordPress. This is your first post. Edit or delete it, then start blogging!