Trie as you Might

A trie is a data structure that makes it easy to search for words or prefixes in a corpus. The structure of the trie reduces the complexity of searching for a word or a prefix down from O(n) where n is the number of words in the dictionary to O(m)where m is the length of the query [1]. Pretty sweet, huh?

Visualization of a Trie, from wikipedia.

So when I ran across a leetcode question which needed a trie, I realized that I’d never actually written one before. Hence this blog post. Before I get into my implementation I want to give a huge shout out to Shubhadeep Roychowdhury who wrote an awesome blog post on the trie structure. I based a lot of my code on his implementation of the trie.

With that being said, I built a few additions to Roychowdhury’s trie. First of all there is a Trie class itself which contains TrieNode‘s. I also built out the __contains__ magic method so you can search within your trie using the in keyword. So here we go:

Side note, see those type hints?! Apparently in python 3.5 they added them as ways to help indicate the types that are expected (and returned) from functions. Python is still totally dynamically typed, but they serve as hints to the reader.

Anyway, the code is pretty self explanatory but if you have any questions please leave them in a comment below. Also, if you use this code note that it is not battle tested, so act accordingly.

Topological Sort

Leetcode had another good question this morning which involved using topological sort, which I hadn’t heard of until today. According to the wiki: “a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering”. In other words, given a bunch of vertices and directed edges, a topological sort finds an ordering where parent nodes always occur before child nodes in the graph. There may be more than one correct answer to this type of problem.

For example, the graph:

could have multiple answers. According to wikipedia:

  • 5, 7, 3, 11, 8, 2, 9, 10 (visual left-to-right, top-to-bottom)
  • 3, 5, 7, 8, 11, 2, 9, 10 (smallest-numbered available vertex first)
  • 5, 7, 3, 8, 11, 10, 9, 2 (fewest edges first)
  • 7, 5, 11, 3, 10, 8, 9, 2 (largest-numbered available vertex first)
  • 5, 7, 11, 2, 3, 8, 9, 10 (attempting top-to-bottom, left-to-right)
  • 3, 7, 8, 5, 11, 10, 2, 9 (arbitrary)

are all valid topological sorts.

Now that we know a bit about topological sorting, let’s move on to the question.

The Question

The question is asking about prerequisites for courses. It asks if there is a valid ordering to take the classes based upon the list of prereqs. In other words, is there a valid way to topologically sort the given nodes based on the edges of prerequisites.

A Solution

I adapted the topological sort from Wikipedia in my solution, I also built a simple Node class which has a status to help with the sort. This is an accepted solution:

The main thing that’s different here is that my visit function will return False if it ever encounters a node marked T in any of its recursive calls. In other words, if there is a cycle the entire function will return False and my canFinish function will also return False. If we can successfully traverse our nodes, that means that there is a valid topological sort and we can return True. Note how easily this could be changed to instead return a valid topological sort.

Complexity

I build the list of nodes, which will happen in O(n) time where n is the number of courses. I also have to add all of the edges, which will happen in O(e) time where e is the number of prerequisite edges. I then perform the topological sort which is linear with regard to n. I can’t think of a valid graph where e > n, but an invalid graph could contain more prerequisite edges than the number of courses. Therefore, I suggest that the time complexity is O(max(n, e)).

For space, I store n nodes and e edges. The edges are not necessarily dependent on the number of nodes. I suggest the space complexity is O(n+e).

Leetcode | Compare Version Numbers

I decided to do an easy one today, but it still had a few good tricks! Here is the prompt:

Ok, seems straightforward enough. Let’s think this through. How are we comparing version numbers? Well, the left-most number has the most priority, one to the right the second most priority, etc… we should just be able to compare these version numbers in order from left to right. Right?

Well, one caveat we need to consider is what happens if one version number is longer than another. We could check the lengths and return the longer one… but there is an edge case there that doesn’t work out (consider 1.0 and 1). So what else can we do?

Simply, just make them the same length! Zero-pad the shorter entry on the right so that they’re the same length. Then we can simply compare. Take a look:

I could clean up my padd function a bit, but it gets the job done. And that’s it!

Complexity Analysis

Let’s see, we may have to pad one of the numbers with zeros, which will take O(d) time where d is the difference in length between the two strings. Then we have to go through the length of the split version numbers once. This is O(n). This term will dominate the zero padding so I think it’s safe to ignore it. Therefore the time complexity is O(n) where n is the size of the longest version number after splitting.

For space, we save two split version numbers which is by definition O(n) as well. Therefore the space complexity is O(n) as well.

I think if we didn’t split into arrays and instead just did the comparisons on the original strings we could get this to constant space, but this speedup doesn’t really seem worth it to me in this problem.

Leetcode | Word Ladder II

In preparation for fulltime interviews in the coming months I’ve been doing a lot of leetcode questions. I have many feelings on whether or not this is the best way to determine someone’s coding abilities, but that’s for a different post. I wanted to share my struggles with one particular question: word ladder ii. I’m not going to paste the prompt here, so if you’re reading this maybe read the prompt first.

Why did I find this one particularly challenging? I’m not sure, exactly. I know all of the strategies involved, I’ve done similar questions before, I know all of the data structures… I think just the size of the problem perhaps got to me. Anyway, I’m going to go over a few failed attempts of mine (they both worked, just timed out on some test cases) followed by a working solution. I’ll conclude with some final thoughts.

Solution 1

My first mistake was I just started coding. This usually ends poorly for me with these types of questions. I tried to come up with a strategy but since I was timing myself, I figured the solution would unfold as I went. This is what my first code looked like:

The basic strategy here was to do a DFS which generated possibilities on the fly (potential next words) and stopped once we found the endWord. Once I did, I saved the min_so_far to save how deep in the graph we are. This way, we never go deeper than that and can cut off searches early. Unfortunately, this had many flaws. Some include:

  • DFS instead of BFS. DFS means that we could end up searching deeper than we need to. More on this later.
  • Not using good data structures. Everything is saved as an array here. For searching repeatedly or checking for existence dictionaries and sets would work better.
  • Overly recursive. Sure, the recursive solution may seem sexy but it’s rarely the fastest and in this case was the final nail in the coffin of this solution.

To be clear, this solution worked it was just very slow.

Solution 2

This solution DID perform much better, but unfortunately it was just adding enhancements to my already poor code. Here is what it looked like:

OhhHHhh! Look how shiny and modular everything is! He even added a Node class. Unfortunately, at this point I didn’t realize that the problem was DFS and so even though this performed way better, it still wasn’t good enough to pass the tests on leetcode. TBH, in an interview this would probably fly because the code is sound. But, again, missing the benefits of BFS here is a silly mistake that wouldn’t have been good in an interview.

Solution 3

At this point I was depressed, sad, and stuck. So, I looked at the discussion section and found a great python solution that I adapted to get things working finally. Here is the code:

The author had a couple of good strategies which I will consider for future problems. Namely:

  • Instead of calculating hamming distance with every word in the wordList, just iterate through every letter. This caps the number of combinations you try at each level and works well when your words are small and your wordLists are huge.
  • BFS first to generate the graph and only then DFS to search the graph. BFS for graph generation means that we will ALWAYS find the shortest distance and will never search deeper than that. There might be other solutions ending at that layer, but we will never search below that.
  • set()‘s and {}‘s save the day here. Lookup and existence checking are much faster than arrays for these data structures.

Now running this code on even the largest dataset in the test scenarios yields:

I’d call that a victory!

Complexity Analysis

#TODO

Customize Field Errors with Rails 5 & Bootstrap 4

Building a new app for one of my clients I had the need to customize Rails’ internal form error fields. By default Rails will add the field_with_errors class to an invalid input and call it a day. Unfortunately, if you’re using Bootstrap 4 (I’m using Beta) then you’re going to need to do a lot of customization in order for this to look right.

But, I hate trying to fight Bootstrap, so I set about trying to make Rails and Bootstrap play nice. I adapted this solution from rubyplus.org to work with the new Bootstrap 4 layouts. The gist is available on my github: Customize Field Errors with Rails 5 and Bootstrap.  It’s pretty simple, but here’s what you need to do.

Like I said, pretty simple but it makes things look a lot more snazzy.

What do you think? Comment here or on the gist to let me know what you think. Enjoy!

Solution: HackerRank Sherlock and Moving Tiles in Ruby

This one was pretty fun! To be honest, I found it a little tricky at first but once I got the hang of it the math was pretty easy. The key is understanding that the velocity of each square is how much they each move on the line y = x every interval. NOT how much to increment each (x,y) coordinate every interval as I naively thought.

So, first of all, let’s check out the question prompt and get a solid grasp of the question. Then let’s do some math to solve for t, which is the amount of time needed for square q to be the proper area.

     \begin{document}t = time \\ v_1 = velocity \ of \ \square_1 \\ v_2 = velocity \ of \ \square_2 \\ l_q = length \ of \ side \ \square_q \\ x = side \ of \ the \ right \ \triangle \ with \ bottom-left \ corner \ of \ \square_1 \ and \ \square_2 \ as \ vertices \\ \\ \begin{equation*} Diagonal \ between \ \square_1 \ and \ \square_2 \\ &= t \cdot v_2 - t \cdot v_1 \\ &= t(v_2 - v_1) \vspace{5mm} \\ \end{equation*} Pythagorean \ Theorem \ gives \ us: \\ \begin{equation*} [t(v_2 - v_1)]^2 = 2 \cdot x^2 \\ \end{equation*} \begin{equation*} x &= \frac {t \cdot (v_2 - v_1)} {\sqrt{2}} \end{equation} \vspace{5mm} To find l_q: \\ \begin{equation*} l_q = l - x = l - \frac {t \cdot (v_2 - v_1)} {\sqrt{2}} \\ l_q - l = - \frac {t \cdot (v_2 - v_1)} {\sqrt{2}} \\ l - l_q = \frac {t \cdot (v_2 - v_1)} {\sqrt{2}} \\ \sqrt{2} \cdot (l - l_q) &= t \cdot (v_2 - v_1) \\ t &= \frac {\sqrt{2} \cdot (l - l_q)} {(v_2 - v_1)} \end{equation} \end{document}

Apologies for the LaTeX with the poor formatting, I’m not entirely used to it yet. Perhaps with a few more of these problems I will be!

Anyway, when we solve for time we’re basically looking for when one side of square q will be the square root of the sought-after area. In order to implement this in Ruby I built a simple PORO that just implements the equation from above in Ruby.

Remember, though, that the velocity of square 1 could be larger than the velocity of square 2. The equation above was built with the velocity of square 2 being greater than the velocity of square 1. There are a couple ways to account for this, but I simply just took the absolute value of the result to achieve the correct answer.

This worked for every test case. Were you able to solve this problem? What strategies did you use to do so?

Atom Error: ‘Const’ is available in ES6 (use ‘esversion: 6’)

I recently upgraded to using the Atom editor to do a majority of my coding. I shied away from it at first because I experienced an error that caused it to eat up all of my memory constantly. Now, months later, they seem to have addressed that issue and it works great! I like it almost as much as Sublime Text now, and feel like I’m going to enjoy it even more soon.

But, as I was progressing through the SurviveJS book recently I found that the JSHint linter I was using didn’t play nice with ES6. Every time I would use something ES6-y like:

My linter would blow up, red all over.

Specifically the error said: “‘const’ is available in ES6 (use ‘esversion: 6’) or Mozilla JS extensions (use moz). (W104)”. Initiating Google-fu yielded unhelpful results. After digging though, here is the fix for this problem.

JSHint has to be configured with a .jshintrc file in the project’s root directory. Simply create a .jshintrc file there with the following object:

Save. Problem solved! Don’t know why this has to be so complicated but hopefully this will save you time going through your Atom package settings uselessly.

Rotating Shapes in a Coordinate Plane Using Javascript

tetris logoFor this week’s Viking Code School project we’re tasked with building a Javascript/jQuery version of Tetris. One of the more complicated aspects of this project was building pieces that actually rotate when a button is pressed (like Tetris pieces are wont to do).

Here’s my implementation for the rotation. Keep in mind that Tetris.Model.getCurrentBlock() returns the CurrentBlock object from my model. This object consists of Coordinates in the form of  {x: x, y: y} among some other useful things like the color of the block and the coordinate that I’d like to use as the Pivot  point, which will come in handy later.

This is what a CurrentBlock object might look like:

This is my function to rotate said block:

There are a lot of variables for now for the sake of clarity, but let’s take a look at what’s actually going on. First of all, I’m getting the coordinates for each SubBlock  in my CurrentBlock  (saved as blockCoords ) so that I can cycle through them. Then, I’m getting the index of my Pivot  coordinate for this shape and then getting the actual coordinates of said Pivot .

After that, my for  loop cycles through each SubBlock in my CurrentBlock  and converts it to a point relative to the Pivot  point. In Euclidian geometry I am essentially treating the Pivot  point as the origin and then making the other points relative to this origin. Then I use the equation for a 90 degree rotation around the origin (which my points are now relative to) and then convert these points back to the area on the coordinate plane where they originally were by adding the x and y elements of the rotated point to the x and y elements of the pivot point. This will yield us the proper coordinates for each of the other SubBlocks  relative to the Pivot  point.

What do you think of this technique? Are there any better ways to rotate a block using Javascript in a coordinate plane? Looking forward to hearing your answers too!

For the latest version of my Tetris game click here (NOTE: it’s not fully functional yet)

Wicked PDF using Rails 4 on Heroku

Intro

A recent project I began building on Rails was a monthly report generator for our employees at BrandYourself. Functionally it needs to allow our representatives to input information quickly or easily, allow them to edit it using a WYSIWYG editor after the report has been created, and finally save the report to a PDF in the browser so the rep can download it and email to our clients. It sounded like a simple project at first, but implementation proved complicated.

Setup

The two main gems that I used for this project were:

Bootsy was essentially plug-and-play, while wicked PDF required a lot of playing with to get it working.

Bootsy

Bootsy was so easy to use I’m not even going to dive too deeply into this gem. Basically, on whichever form you’d like to impliment the WYSIWYG editor you use a special bootsy_area method for form_for. Here’s an example:

It’s that simple.

Wicked PDF

Before taking on this project I didn’t realize how difficult in-browser PDF generation was. Wicked PDF takes a lot of the sting out of this process, but it’s still not easy to setup. A lot of the problems stemmed from Wicked PDF being a wrapper for a binary library called wkhtmltopdf which does the heavy lifting for converting HTML to PDF. But, since this is a binary library (which I’ve never really worked with until now) it was tough to get this working properly on Heroku.

The basic setup for wicked_pdf is straightforward. First install the gem, and make sure you have wkhtmltopdf installed on your local machine: usually this is stored in /usr/local/bin on Macs. Then you’ll want to run rails g wicked_pdf to setup the the gem. This just creates a wicked_pdf.rb initializer in your app.  Following the other steps on their github you can easily get this setup properly on your local app! The way it’s setup you can add .pdf to the end of any URL and it will convert that page to a PDF; pretty cool! The basic idea is something like this in your controller:

Don’t let this fool you though, implementing this on Heroku is another endeavor.

Wicked PDF on Heroku

Wicked PDF on Heroku is a challenge because of the way wkhtmltopdf works. Locally, this library is stored in /usr/local/bin but obviously Heroku doesn’t have this out of the box. So, we have to ensure that Heroku has access to this library so it can utilize it. After a lot of research on Google I found a potential solution which had me firstly download the Linux version of wkhtmltopdf. This is available from their website under obsolete downloads (which turned out not to be so obsolete). I used the latest version of the Linux 64-bit library which was version 0.11.0.

Once this was downloaded I unzipped the library and put it in my /bin folder in my app. After that was done, I had to change where Wicked PDF looked for this library if we were in a production environment. This code, obtained from stack overflow, was added to the wicked_pdf.rb initializer:

This finally got wicked PDF working on Heroku even though there are still a few bugs.

Future #TODOs

Aside from general functionality TODOs there are still a few things tricky with Wicked PDF. Most specifically getting it to allow the use of Google fonts when generating PDFs. Presently, the font that I’ve included in the report doesn’t seem to be displaying properly in the generated PDF. At first this was because Heroku was blocking an “insecure” connection to Google fonts (since it was using http://) but changing this to https:// fixed this pretty quickly.

Other than that, everything seems to be working rather well with this project! I’m excited to continue to build it out and develop more functionality to improve the overall efficiency of our company 🙂

 

Trevor Elwell Best ORM in NYC

Have you heard that Trevor Elwell is the best ORM in NYC?I read a post earlier about using robots.txt files to get results to rank high for certain keywords. Needless to say, I was extremely intrigued by this! So I wanted to write this blog post as an experiment to see if this actually worked. I imagine that will get squashed by Google in a few weeks or so but keep an eye on the results for my name over the next couple of weeks and let’s see what happens.

Now that I think of it though, I should probably make this post a little meatier in order for it to get indexed properly. So with that in mind, I’ll talk a little bit about my day. Aside from the usual day-to-day routine of putting out fires (not literal ones, of course) throughout the office a some of this day has been dedicated to building a CSS training curriculum. Ideally, I want to train other members of my team in the basics of CSS and HTML to a point where they can manipulate WordPress websites with relative ease. There have been a lot of resources online that I’ve been able to utilize in my quest, and I think this course will prove to be a great learning experience for those who go through it.

The best resource I’ve found, so far, has been CodeAcademy’s HTML/CSS track. I’ve personally gone through this course and think it’s a great introduction to these integral languages to web development. My worry is that many of my ‘students’ don’t have too much web dev experience in general- will they be able to pick up the basics behind a language through this course the same way I was? I guess only time will tell but since the individuals I’ll be teaching are all intelligent this isn’t going to be a huge concern of mine.

Anyway, let’s see if this experiment works. As you know, Trevor Elwell is the best ORM in NYC. Have a great weekend!