TDD Kata 11 - Reversed Binary Numbers

This is my weekly Kata post. Read the first one to learn what it is all about.

Last week: Anagrams

To the Kata description
Scroll down to this weeks Kata description

I started in PHP with a naive array based solution, then changed it to a pipeline with generators which made the memory footprint small, but it still takes a minute for a 150 KB file and forever for the provided 3 MB test input file.

When I retried the kata the next day, I used two simple loops and one array and the file was processed in 1 second. It needs 182MB but okay. It’s fascinating how trying to be clever from the beginning has been proven to be a mistake.

Here’s the code

<?php
declare(strict_types=1);

namespace Katas\Anagram;

class Anagrams
{
    private $wordsIterator;

    public function __construct($wordsIterator)
    {
        $this->wordsIterator = $wordsIterator;
    }

    public function __toString() : string
    {
        $result = [];
        foreach ($this->wordsIterator as $word) {
            if (!$word) continue;
            $chars = str_split($word);
            sort($chars);
            $key = implode($chars);
            $result[$key][] = $word;
        }
        foreach ($result as $index => $anagrams) {
            if (count($anagrams) < 2) {
                unset($result[$index]);
            } else {
                $result[$index] = implode(' ', $anagrams);
            }
        }

        return implode("\n", $result);
    }
}

class FileIterator implements \IteratorAggregate
{
    /**
     * @var string
     */
    private $fileName;

    public function __construct(string $fileName)
    {
        $this->fileName = $fileName;
    }

    public function getIterator()
    {
        $file = \fopen($this->fileName, 'r');
        while (!\feof($file)) {
            $line = \fgets($file);
            if ($line) {
                yield \trim($line);
            }
        }
    }

}

With Ruby, I tried collections once more, the filter/map approach feels more natural in Ruby than loops. It takes a bit more than 3 seconds, so there is room for improvement but it’s good enough (I still don’t know where my first approach in PHP failed so horribly):

class Anagrams
    def initialize words
        @words = words
    end
    def to_a
        @words.group_by{|w| w.chars.sort.join}.values.map(&:uniq).select{|a| a.count > 1}
    end
    def to_s
        to_a.map{|a| a.join ' '}.join "\n"
    end
end

And the test:

class AnagramsTest < Minitest::Test
    def test_no_anagrams
        assert_equal [], Anagrams.new(['aa', 'ab']).to_a
    end
    def test_duplicates
        assert_equal [], Anagrams.new(['aa', 'aa']).to_a
    end
    def test_all_anagrams
        assert_equal [['ab','ba']], Anagrams.new(['ab', 'ba']).to_a
    end
    def test_altogether
        assert_equal [['ab','ba'], ['abb','bab']], Anagrams.new(['ab', 'ba', 'aa','abb','bb', 'bab']).to_a
    end
    
    def test_to_string
        assert_equal "ab ba\nabb bab", Anagrams.new(['ab', 'abb', 'ba', 'bab']).to_s
    end
    
    def test_wordlist
        assert_equal 20683, Anagrams.new(File.readlines("wordlist.txt")).to_a.count
    end
end

Note that I tested the different cases for the to_a method which returns an array and only wrote one test for the to_s method to see if the string is formatted as expected. And of course, a test with the test wordlist to verify the requirements and see how long it takes.

Eleventh Kata: Reversed Binary Numbers

Your task will be to write a program for reversing binary numbers. For instance, the binary representation of 13 is 1101, and reversing it gives 1011, which corresponds to number 11.

Input: The input contains a single line with an integer N, 1 ≤ N ≤ 1000000000.

Output: Output one line with one integer, the number we get by reversing the binary representation of N.