jeronymo

Wildcard challenge

Jun 18th, 2011
326
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2. /**
  3.  * Wildcard challenge
  4.  * Escrever um algoritmo, em php, que tenha como entrada uma string composta por palavras separadas por pipe ( | )  e a saída seja uma sequência com todos os wildcards possíveis.
  5.  * Exemplos.:
  6.  * Entrada: “sao-paulo”
  7.  * Saída:   *
  8.  * Entrada: “sao-paulo|restaurante”
  9.  * Saída:   sao-paulo|*
  10.  *          *|restaurante
  11.  */
  12.  
  13. // lê uma linha da entrada
  14. $input = trim(fgets(STDIN));
  15. // separa as palavras pelo pipe
  16. $palavras = explode('|',$input);
  17.  
  18. $totalPalavas = count($palavras);
  19.  
  20. if($totalPalavas == 1) {
  21.     print "*";
  22.     return ;
  23. }
  24.  
  25. // binário é base 2, então tem 2^n combinações de sequências para n bits
  26. $totalCombinacoes = pow(2, $totalPalavas);
  27.  
  28. for($i = 1; $i < ($totalCombinacoes - 1); $i++) {
  29.  
  30.     $bin = format_binary($i, $totalPalavas);
  31.     $sequencia = "";
  32.  
  33.     // itera sobre cada bit do binário resultante
  34.     for($j = 0; $j < strlen($bin); $j++) {
  35.         if($j != 0) $sequencia .= "|";
  36.         // se for bit 1, troca pelo wildcard; se não troca pela palavra da posição
  37.         $sequencia .= ($bin[$j] == "1") ? '*' : $palavras[$j];
  38.     }
  39.  
  40.     print $sequencia."\n";
  41.  
  42. }
  43.  
  44. /**
  45.  * Transforma um número decimal em binário com um número fixo de bits
  46.  * @param int $numero Número decimal
  47.  * @param int $numbits Quantidade de bits
  48.  * @return string
  49.  */
  50. function format_binary($numero, $numbits) {
  51.     // transforma em binário
  52.     $bin = decbin($numero);
  53.     // retorna um 'zerofill' no binário
  54.     return substr(str_repeat(0,$numbits),0,$numbits - strlen($bin)) . $bin;
  55. }
  56. ?>
RAW Paste Data