Page 1 of 2

How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 7:27 am
by theudulf
Greetings,

How to create word with all Lower and upper-cases possibilities:
for example Wood, wOod, woOd, wooD, WOod, WoOd, WooD, wOOd, wOoD, WOOd, WOoD, wOOd, wOoD, woOD, WOOd, WoOD, wOOD, WOOD and others upper and lower letters combination.
For now I'm able to create Wood, wOod, woOd, wooD using:

Code: Select all

for ($i=0;$i<=(261);$i++)
	{
		$ask = mysql_query("SELECT * FROM dict WHERE id='$i'");

		$data = mysql_fetch_array($ask);
		$num = strlen($data['text0']);
		
			for($f=1; $f<$num; $f++)
				{
		$text=$data['text0'];
				
		$backup= $text[$f-7]. $text[$f-6]. $text[$f-5]. $text[$f-4].$text[$f-3].$text[$f-2].$text[$f-1].strtoupper($text[$f]).$text[$f+1].$text[$f+2].$text[$f+3].$text[$f+4].$text[$f+5].$text[	$f+6].$text[$f+7];
				
				$word= trim($backup);
							
				mysql_query("INSERT INTO dict4 (word) VALUES('$word')");
							
				}
        }
Do you have any idea how to create others?

Regards,
Simon.

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 9:38 am
by Jonah Bron
Nobody answer this one, I'm taking a crack at it! :D

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 9:52 am
by pickle
Treat it like an array. Start with all lowercase letters, then in a fancy algorithm capitalize the first letter, then the second letter, then the third, and so on. Then move on & capitalize the first and second letters, then also the third, then 1,2,4, then 1,2,5, etc

If you've got a word with 5 characters, those that are capitalized would look like this:

1
1,2
1,3
1,4
1,5
1,2
1,2,3
1,2,4
1,2,5
1,3
1,2,3
1,2,3,4
1,2,3,5

Obviously there will be duplicates, but array_unique() can solve that simply enough.

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 10:00 am
by Apollo
You're making this way too complicated :) Try this:

Code: Select all

function GetAllCaseCombinations( $s )
{
  $s1 = strtolower($s);
  $s2 = strtoupper($s);
  $n = strlen($s);
  $c = array();
  for($i=0; $i<$n; $i++)
  {
    $c[] = ($s1[$i]==$s2[$i]) ? 2 : 0;
  }
  $output = array();
  for($i=0; $i<$n;)
  {
    $s = '';
    for ($i=0; $i<$n; $i++)
    {
      $s .= $c[$i] ? $s2[$i] : $s1[$i];
    }
    $output[] = $s;
    for ($i=0; $i<$n; $i++)
    {
      if (1==($c[$i]^=1)) break;
    }
  }
  return $output;
}
GetAllCombinations('Wood') would now result in an array with all 16 combinations.

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 10:07 am
by Jonah Bron
Binary, anyone?

Code: Select all

function AllCases($s)  {
    $s = str_split(strtolower($s));
    $c = array();
    $t = bindec(str_pad('', count($s), '1'));
    for ($i = 0; $i <= $t; $i++){
        $ts = $s;
        $x = array_pad(str_split(decbin($i)), count($s)*-1, '0');
        foreach ($x as $k => $d){
            $ts[$k] = $d == '1' ? strtoupper($ts[$k]) : $ts[$k];
        }
        $c[] =  implode($ts);
    }
    return $c;
}
Just using the inherit properties of the base 2 numeral system. No point in reinventing the wheel! :D

Edit: Oops! Thanks mikosiko, fixed (both problems).

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 10:58 am
by theudulf
Thank you for your help!!! I used result used by Jonah, this is GREAT! Now i need to understand it properly ;)

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 11:01 am
by mikosiko
"Improved"... :wink: only if you change $total for $t

both algorithms are interesting... but interestingly enough both give different results Apollo's gave 32 elements and Jonah 31 ... so one is off by one :)

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 11:13 am
by theudulf
Previous version is working, you just needed do change < $total to <= $ total ;)

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 11:17 am
by Jonah Bron
Already done. Fixed that when mikosiko mentioned only 31 results.

I really love logic problems like this. This should have been in the challenge index :idea:

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 11:34 am
by theudulf
Che che, thank you again for your help, I didn't do this kind of problem using php and beside of this I'm noob (I'm learning it since october 2009 so not so long) and this guy (I attend postgraduates studies) told that "we could use anything we know, for example java, c#, php, and others) and didn't provide us any valuable help. For know all DB table contains almost 2 670 000 rows :p

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 12:48 pm
by Apollo
Mine is binary too, and safe with regard to non-alphabetic characters (e.g. "Ran-dom" would still give 64 results, not 128).

Also I haven't done any timing but I'm quite sure mine is a lot faster (not having split and implode the arrays all the time). I do like Jonah's approach with bindec though, very original :)

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 12:59 pm
by mikosiko
Jonah : Script Execution Time: 0.0005018711 seconds
Apollo : Script Execution Time: 0.0001881123 seconds


and the winner is ....... :drunk:

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 2:06 pm
by Jonah Bron
I concede :) Maybe I can optimize it?

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 2:31 pm
by Jonah Bron
Mind re-checking the execution time, mikosiko?

Code: Select all

function AllCases($s)  {
    $s = strtolower($s);
    $s2 = strtoupper($s);
    $c = array();
    $l = strlen($s);
    for ($i = 0, $t = bindec(str_pad('', $l, '1')); $i <= $t; $i++){
        $c[] = $s;
        $x = str_pad(decbin($i), $l, '0', STR_PAD_LEFT);
        for ($w = 0; $w < $l; $w++){
            $c[$i][$w] = ($x[$w] === '1') ? $s2[$w] : $s[$w];
        }
    }
    return $c;
}
Sorry Apollo, I stole your avoid-strtoupper-every-time idea. If it's any consolation, I probably would have come up with it eventually... Please don't strike me down with a bolt of lightning 8O

Re: How to create string PAssword, PaSsword, etc.

Posted: Thu May 27, 2010 3:23 pm
by Jonah Bron
Here's the results:

Apollo: 0.000059594297409058
Me: 0.000091614603996277

Better. Mine is still ~52% slower. You officially win. 8) Any minute Feyd is going to make one that's faster than yours and smaller than mine.

Now, where's my crying smiley :wink: ?