wordGenerator back door

[tdxev]

Se da functia wordGenerator care genereaza o lista de cuvinte formata din caracterele primite ca argument ex. wordGenerator('abc');

Lungimea sirului de caractere e variabila.

x = wordGenerator('abc'); // Lista creata este de lungime infinita

x =

1 - a
2 - b
3 - c
4 - aa
5 - ab
6 - ac
7 - ba
8 - bb
9 - bc
10 - ca
11 - cb
12 - cc
13 - aaa
14 - aab
15 - aac
16 - aba
17 - abb
18 - abc
19 - aca
20 - acb
21 - acc
22 - baa
23 - bab
24 - bac
25 - bba
26 - bbb
27 - bbc
28 - bca
29 - bcb
30 - bcc
31 - caa
32 - cab
33 - cac
34 - cba
35 - cbb
36 - cbc
37 - cca
38 - ccb
39 - ccc
40 - aaaa
41 - aaab
42 - aaac
43 - aaba
44 - aabb
45 - aabc
46 - aaca
47 - aacb
48 - aacc
49 - abaa
50 - abab
51 - abac
52 - abba
53 - abbb
54 - abbc
55 - abca
56 - abcb
57 - abcc
58 - acaa
59 - acab
60 - acac
61 - acba
62 - acbb
63 - acbc
64 - acca
65 - accb
66 - accc
67 - baaa
68 - baab
69 - baac
70 - baba
71 - babb
72 - babc
73 - baca
74 - bacb
75 - bacc
76 - bbaa
77 - bbab
78 - bbac
79 - bbba
80 - bbbb
81 - bbbc
82 - bbca
83 - bbcb
84 - bbcc
85 - bcaa
86 - bcab
87 - bcac
88 - bcba
89 - bcbb
90 - bcbc
91 - bcca
92 - bccb
93 - bccc
94 - caaa
95 - caab
96 - caac
97 - caba
98 - cabb
99 - cabc
100 - caca
101 - cacb
102 - cacc
103 - cbaa
104 - cbab
105 - cbac
106 - cbba
107 - cbbb
108 - cbbc
109 - cbca
110 - cbcb
111 - cbcc
112 - ccaa
113 - ccab
114 - ccac
115 - ccba
116 - ccbb
117 - ccbc
118 - ccca
119 - cccb
120 - cccc
121 - aaaaa
122 - ....
...
...
9999999999999999999999999999999999...

Se cere crearea unei functi (metode) care sa returneze rezultatul de la linia 48884560, pentru sirul de caractere "abc", fara a genera/parcurge intreaga lista de cuvinte;

Se poate folosi ori ce limbaj de programare doriti.

Mai pe scurt vreau rezultatul de la linia : 48884560;

[cmiN]

Enter charset: abc

Line: 48884560

bccabbbaacbbbcba

Sub o secunda -->

Python:

#! /usr/bin/env python
# 09.10.2010 <> 09.10.2010 | cmiN
# wordGenerator 4 tdxev @ rstcenter.com

def main():
    charset = raw_input("Enter charset: ")
    line = int(raw_input("Line: "))
    base = len(charset)
    result = 0
    exponent = 0
    genstr = ""
    while result < line:
        exponent += 1
        result += base ** exponent
    result -= base ** exponent
    for e in xrange(exponent - 1, -1, -1):
        pos = -1
        while result < line:
            result += base ** e
            pos += 1
        result -= base ** e
        genstr += charset[pos]
    print genstr


if __name__ == "__main__":
    main()

Sigur sunt metode recursive sau de backtracking sau plm ce se foloseste mult mai rapide . Oricum in py se misca aproape instantaneu, deci in C ...

[tdxev]

aceasta este functia creata de mine , arata ca naiba dar merge

function wordGeneratorBackDoor($charset,$nr)
{
	$w=strlen($charset);
	if ($nr<=$w){return substr($charset,$nr-1,1);}
	$CLb=1;
	$CLsum=0;
	$CLsumi=0;
	$CLnr=0;
	while ($nr>$CLsum){
		$CLnr++;
		$CLsumi += $CLb;   
		$CLb = pow($w,$CLnr);  
		$CLsum += $CLb; 
		}	
	$CLsumi--;
	$CLp=$nr-$CLsumi;
	$CLcur=$CLb*$w;
	$thex='';
	for ($i=$CLnr; $i>0; $i--){
		$CLcur=$CLcur/$w;
		$m=$CLcur/$w;
		if ($m==1){
			$rest=$nr%$w;
			if ($rest==0) {
				$thex.=substr($charset,$w-1,1);
					} else {
				$thex.=substr($charset,$rest-1,1);	
					}
			}
		if ($m!=1)
		for ($k=1; $k<=$w; $k++){
			if ((($m*$k)>=$CLp) && ($CLp < ($m*($k+1)))){
				$thex.=substr($charset,$k-1,1);
				if ($k>1) {$CLp=$CLp-(($k-1)*($m));}  
				$k=$w+1;
				}
		}
	}
	return $thex;
}

echo wordGeneratorBackDoor('abc',48884560);

[kNigHt]

#include <iostream>
#include <math.h>
using namespace std;
unsigned long x;
unsigned long count = 0, pointer = 1;
int a[500];

int get_nr(int start, int div, int point) {
	if(start + div >= x) return 1;
	if(start + div*2 >= x) return 2;
	if(start + div*3 >= x) return 3;
}

void gimme(int start, int point) {
	if(point > 0) {
		int div = pow(3, point-1);
		a[pointer-point] = get_nr(start, div, point);
		gimme(start + div*(a[pointer-point]-1) , point-1);
	}	
}

int main() {
	cout << "Introdu pozitia: "; cin >> x;
	while(count <= x) {
		count += pow(3, pointer);
		pointer++;
	}
	pointer--;
	int start_pos = count - pow(3, pointer);
	gimme(start_pos, pointer);
	cout << "Elementul de pe pozitia " << x << " este: ";
	for(int i = 0; i < pointer; i++) {
		if(a[i] == 1) cout << "a";
		if(a[i] == 2) cout << "b";
		if(a[i] == 3) cout << "c";
	}
	cout << "\n";
	return 0;
}

[m32mark]

<?php
set_time_limit(0);

function wordGenerator($x, $poz){ static $ctr;
    for($i=0,$z="",$e="if(++\$ctr==\$poz) echo ";$i<16;$i++){
	$z.="foreach(\$x as \$y[$i])"; $e.="\$y[$i].";
        eval($z.$e."\"<br />\";");
    }
}
wordGenerator(array(a,b,c), 48884560);
?> 

afiseaza: bccabbbaacbbbcba.

Script scris la betie.

Pentru rezultate de sub o secunda recomand rularea scriptului pe un calculator gen sequoia sau jaguar

[tdxev]

Da vad ca rezultatul este bun, da.. chiar ca trebuie un "sequoia" pentru el

[m32mark]

Recunosc ca metoda mea e cam cea mai putin inteligenta, numai ca am incercat sa rezolv intr-un alt fel (ca la scoala ), e o metoda mai economica de linii din script dar nu si la performanta/memorie