Ruby Meetup Code Puzzles - October, 2019

At the Perth Ruby Meetup, hosted at 65 Bits the second Wednesday of every month, after presentations and pizza we work through a handful of programming puzzles to stretch our Ruby knowledge and learn from the techniques of others.

For these challenges we pick two selections from LeetCode. LeetCode is an online platform for software developers to refine their coding interview skills, but we use it as a source of fun and entertaining puzzles. One of the benefits is that it's web based so anyone with a web browser can log on and start coding straight away without the need to install the language on your computer.

At the October Meetup we posed two challenges: Unique Number of Occurrences and Find Words That Can Be Formed by Characters.

Challenge 1 - Unique Number of Occurrences

Link to challenge

This is a warmup exercise just to get us in the puzzle solving mood.

Paul Walker shared his solution, it's a brute force technique but effective:

Bruce Werdschinski came up with this solution which is slightly faster but uses the same amount of memory:

---

Challenge 2 - Find Words That Can Be Formed by Characters

Link to challenge

This is a much harder problem to solve and took most of us quite some time to get through! Then there's the additional challenge of finding a solution that is quick and uses less memory.

The first solution comes from Paul Walker, out of all of the solutions his uses the least memory.

Paul iterates through the array of words, and then through each character of the selected word, to then use count method to compare the character of each word against the chars input to see if they match. And to improve performance the comparison exists the loop early when there is no match. Nice one. Paul's solution took 530ms and uses 10.2Mb of memory.

Paul Walker's solution:

Andy Holland presented a few solutions on the night as well.

The first uses each_with_object to turn the chars input into a hash containing the frequency of each character that chars contains. Then select is used to iterate through the words and only return those that are "good" words.

On line 8 Andy uses each_with_object to start with a duplicate of the frequency hash created on line 5 which then subtracts the characters from word from that hash. counter is then assigned a hash that contains the leftover characters and their count. If that count is less than 0 for any letter, then more letters were used than was provided so the word is not "good". The all? method on line 12 returns true if all of the counter values are larger or equal to 0.

This neat trick works as Hash.new(0) is passed to each_with_object in line 5, ensuring that the default value for hash keys is 0, so if a letter is in a word and not in chars it defaults to 0 and will be decremented to -1 the first time it's seen.

Line 13 then sums the length of all "good" returns from select to solve the puzzle. Nice elegant solution in Ruby!

Andy Holland's first solution:

However Leetcode told us that it's not the faster solution taking 660ms (and slower than Paul's version), so Andy came up with another solution. It's a similiar approach to Paul's solution, except that instead of counting the characters, arrays indexes are used to find and then remove matching characters. This approach is the fastest so far at 480ms and uses 10.3Mb of memory.

Andy Holland's second solution:

Once I (Bruce) got home I tried a different approach. Using a reducer to iterate over the words allows us to return one value, the length of all "good" words. Inside the reducer's block we add the length of a word if it is found to be "good".

Similiar to Paul's technique this code uses character counts to determine whether a word is "good" or not. There is a micro-optimisation that determines the length of the word by using with_index so that we don't have to call the expensive word.length method later. This version uses 10.3Mb of memory compared to Paul's version taking 10.1Mb, but is much faster overall and takes only 68ms.

Bruce Werdschinski's solution:

We hope that's been an entertaining look at our approaches, and we'd love to see you at a Perth Ruby Meetup hosted at 65 Bits soon!