Thue Morse Sequence - PHP Implementation

README.md

Thue Morse Sequence - PHP Implementation

Recently, I got a job vacancy test and this is the one of questions i've got. I'm absolutely new here so CMIIW 😉

Usage

Simply download the gist and create new file called whatever.php then copy-paste lines below:

!#/usr/bin/env php
<?php

// Load the file
require 'ThueMorse.php';

// Pop the last argument
$seq = (int) array_pop($_SERVER['argv']);
// Initiate the class
$thueMorse = new ThueMorse;

// Simply dump it
var_dump($thueMorse->calculate($seq));
// or concat the result as string
// echo implode('', $thueMorse->calculate($seq));

Back to your terminal and run

$ php whatever.php 5

You'll see something like this

array(6) {
  [0] =>
  string(1) "0"
  [1] =>
  string(2) "01"
  [2] =>
  string(4) "0110"
  [3] =>
  string(8) "01101001"
  [4] =>
  string(16) "0110100110010110"
  [5] =>
  string(32) "01101001100101101001011001101001"
}

License

Do What the Fuck You Want to Public License

ThueMorse.php

<?php
/**
 * Thue Morse Sequence - PHP Inmplementation
 *
 * @author  Fery Wardiyanto <ferywardiyanto@gmail.com>
 * @link    http://feryardiant.me
 * @license WTFPL (http://www.wtfpl.net/)
 */
class ThueMorse
{
    /**
     * Calculate the sequence
     *
     * @param  int $seq Sequence
     * @return array
     */
    public function calculate($seq)
    {
        $res = [];
        $seq = $seq >= 0 ? (int) $seq : 0;

        for ($i = 0; $i <= $seq; $i++) {
            if ($i === 0) {
                $tmp = '0';
            } else {
                $prev = $res[($i - 1)];
                $tmp = $prev.$this->reverse($prev);
            }

            $res[$i] = $tmp;
        }

        return $res;
    }

    /**
     * Reverse $prev sequence
     *
     * @param  string $prev Previous sequence
     * @return string
     */
    private function reverse($prev)
    {
        if (strlen($prev) > 1) {
            $arr = [];

            foreach (str_split($prev) as $num) {
                $arr[] = $this->flip($num);
            }

            return implode('', $arr);
        }

        return $this->flip($prev);
    }

    /**
     * Flip $num
     *
     * @param  string $num Numeric string between 0 or 1
     * @return string
     */
    private function flip($num)
    {
        return $num === '0' ? '1' : '0';
    }
}

Great!