Thread

A while back there was a flurry of interesting programming challenges. I’ve got my own now. i would be pleased if you took a look and gave feedback or sent up some code. i’ll post my answer in a few days.

This is something I have solved, but it took me a while to get to something reasonably fast and flexible.

Here’s the challenge:

gmail.com allows you to make many variations of your email address. you may already know that you can use plus-addressing (adding a plus sign and then another string) and gmail will deliver it. for example, a gmail address like this: .(JavaScript must be enabled to view this email address) will also get mail for [email protected] and [email protected], etc…

what you may not know is that gmail allows you to use many dot-variations of the mailbox. for example all of these addresses are delivered by gmail to .(JavaScript must be enabled to view this email address): .(JavaScript must be enabled to view this email address), .(JavaScript must be enabled to view this email address), and .(JavaScript must be enabled to view this email address)

challenge: list ALL of the dot-variations for an arbitrary mailbox. (edited to clarify dot-variations, not plus-addressing)

starting with:
.(JavaScript must be enabled to view this email address)

and ending with:
.(JavaScript must be enabled to view this email address)

and all the variations in between.

You mean with just the .‘s in various places? Or with some + aswell. Surely if we use + then it could be infinite.

right, plus addressing is not the challenge. dot-addressing is.

I started working on my PHP solution to this challenge (and will probably do one in Python as well). I also presented this to a few of my coworkers, I’ll post their responses if/when I get them. I presented the challenge as follows:

As you may know, periods within the Inbox alias of a GMail account don’t matter. For instance, an address of .(JavaScript must be enabled to view this email address) would receive messages sent to .(JavaScript must be enabled to view this email address), .(JavaScript must be enabled to view this email address), even .(JavaScript must be enabled to view this email address).

Your challenge is to write a script that outputs every possible combination of a dot-notated Gmail address (recurring periods are not allowed, only a single period between letters). The input address is .(JavaScript must be enabled to view this email address).

hi michael,

thanks for making the wording for the challenge clearer! i also realized (though it is implied) that the email address has to be valid - so no multi-dots and no dots starting or ending the mailbox.

the script above generates quite a few valid email addresses, but not the full complement. it leaves out .(JavaScript must be enabled to view this email address) for instance.

the mailbox “thisemail” has 9 characters so there are 2^8 solutions.

Not actually having the patience to code this, But… I would convert the character count of the username to a binary number (as sophistry indicates 2^8), and then count up from 0 to that number placing a ‘.’ between characters for each count in the sequence.

hmmmm…. wired… i’m not sure how to do a speed test on pseudocode. 😊

also, i just noticed that the EE forum script did not convert the plus-addressing email addresses on the original post. that has been fixed in the CI codebase - the plus character is now in the auto_link() regex. time to backport auto_link() to the EE forum, guys. 😉

[email protected]
.(JavaScript must be enabled to view this email address)

[email protected]

Dang… have to rethink it :(

...I’m not sure how to do a speed test on pseudocode.

Me neither. But where is xwero when you need him?, he loved this stuff! 😊

So, the amount of end-result is simple to calculate, in this example 2^8.

I would insert the periods randomly, and add it to an array (of course only, if it doesn’t exist yet in the array). When the array fullfills the size of 2^8, I have all permutations.

... ah, it should be fast and optimized? 😉))

We came up with this solution, although we just read wiredesignz had something similar.

function calculate_email($email = '[email protected]')
    {
        $inbox = str_replace('.', '', current(explode('@', $email)));
        $domain = end(explode('@', $email));
        $length = strlen($inbox) -1;
        $posibilities = pow(2,$length)-1;

        // dump the inbox in an array
        for ($k = 0; $k <= $length; $k++)
        {
            $letterarray[] = substr($inbox, $k, 1);
        }

        // start counting in binary for all the possible solutions
        for ($i = 0; $i <= $posibilities; $i++)
        {
            echo $i .' : ';
            $bin = decbin($i);
            $binlength = $length - strlen($bin);

            $j = 0;
            
            // zerofill empty space
            while ($j <= $binlength)
            {
                $bin = '0'.$bin;
                $j++;
            }

            // replace all binary 1's for dots
            foreach($letterarray as $key=>$value)
            {
              if (substr($bin, $key, 1) == '1')
              {
                  echo '.';
                  echo $value;
              }
              else
              {
                echo $value;
              }
             
           }
           echo '@'.$domain.'
';
        }
    }

Also note the use of 3 different forms of loops 😉

Total Execution Time      0.0321

thanks for playing guys! that was fun.

i started attacking the problem the same way MW did - loops.

then i thought along the lines of sledgehammer - fill randomly and cull.

then, only after looking at some of the output, i noticed that there was a binary pattern going on - and then it hit me: bits!

that was the solution proposed by wiredesignz and implemented by noxie. nicely done.

here’s the solution i had come up with after quite a bit of tinkering and tidying… there are some nice tricks in there if i do say so myself. 😉 and it is a teeny-tiny bit faster than noxie’s excellent submission.

// build the variations for a gmail address
    function gb($em='[email protected]')
    {
        $mb = str_replace('.','',strtok($em,'@'));
        
        $letters_array = preg_split('//', $mb, -1, PREG_SPLIT_NO_EMPTY);
        $last_letter = array_pop($letters_array);
        $bits = strlen($mb)-1;
        $mask_array = range(0,pow(2,$bits)-1);
        foreach($mask_array as $decimal)
        {
            // zero pad to make the foreach easier to read
            $bin = substr(str_repeat('0',$bits) . decbin($decimal), -$bits);
            $out = '';
            foreach($letters_array as $key => $letter)
            {
                $out .= $letter . (($bin[$key]) ? '.' : '');
            }
            $arr[] = $out . $last_letter;
        }
        print_r($arr);
    }

That’s a sexy piece of code sophistry. I think even Derek Jones would get orgasmic looking at that. 😊

Good work.