User:Ledrug/bits: Difference between revisions

From Rosetta Code
Content added Content deleted
mNo edit summary
mNo edit summary
Line 132: Line 132:
}
}
return (void*)-1;
return (void*)-1;
}</lang>
<lang c>#include <stdio.h>
#include <string.h>

#define maxn 1000000
#define maxp 1000
int primes[maxp] = {2, 3}, n_primes = 2;

#ifdef KNUTH
char knuth[20000+2];
#endif

int show = 0;
void make_primes()
{
int i, n = 3, p;
while (n_primes < maxp) {
n += 2;
for (i = 0; i < n_primes; i++) {
p = primes[i];
if (n % p == 0) break;
if (p * p >= n) {
primes[n_primes++] = n;
break;
}
}
}
}

int length[maxn + 2] = {0, 0, 1, 2, 2};

int ones_(int n)
{
int r = 0;
while (n) {
if (1 & n) r++;
n >>= 1;
}
return r;
}

int lg2(int n)
{
int r = 0, i = 1;
while (i < n) r++, i *= 2;
return r;
}

int lb(int n)
{
int x = lg2(n);
return x - (n != (1 << x));
}

int seq_len(int n);

typedef struct { int out, sum, tail, l, u; } rec;

int iter;
int seq_insert(rec *x, int len, int p, int pos)
{
int j, i, min, max;
i = pos ? pos : seq_len(p);

while (i < len && p > x[i].u) i++;

if (i >= len || p < x[i].l) return 0;
iter++;
if (show) printf("insert %d %d\n", p, pos);

x[i].l = x[i].u = p;
x[i].out ++;
x[i].sum += len;
if (!x[len].tail || x[len].tail > p) x[len].tail = p;

#if 0
for (j = i + 1; j < len; j++) {
if (x[j].u > x[j-1].u * 2) x[j].u = x[j-1].u * 2;
if (x[j].l <= x[j-1].l) x[j].l = x[j-1].l + 1;
}

for (j = i - 1; j >= 2; j--) {
if (x[j].u >= x[j+1].u) x[j].u = x[j+1].u - 1;
if (x[j].l < x[j+1].l/2) x[j].l = x[j+1].l / 2;
}
#endif
min = max = i;
for (j = i; j < len && x[j+1].u > x[j].u * 2; j++)
x[j+1].u = x[j].u * 2;
if (max < j) max = j;

for (j = i; j < len && x[j+1].l <= x[j].l; j++)
x[j+1].l = x[j].l;
if (max < j) max = j;

for (j = i; i > 2 && x[j-1].u >= x[j].u; j--)
x[j-1].u = x[j].u - 1;
if (min > j) min = j;

for (j = i; i > 2 && x[j-1].l * 2 < x[j].l; j--)
x[j-1].l = (x[j].l + 1)/2;
if (min > j) min = j;

if (show) for (i = 0; i <= len; i++)
printf("(%d,%d)%s", x[i].l, x[i].u, i == len ? "\n": "->");

for (j = min; j < max; j++) if (x[j].u < x[j].l) return 0;

return 1;
}

void copy(rec *x, rec *n, int len)
{
memcpy(x, n, sizeof(rec) * len);
}

int seq_recur(rec *in, int len)
{
rec x[32];
int i, p, q, n, r, lim;

if (len < 2) return 1;
n = in[len].u;

if (in[len-1].u == in[len-1].l) {
if (n == in[len-1].u * 2 ||
n == in[len-1].u + 1 ||
n == in[len-1].u + 2)
if (seq_recur(in, len -1)) return 1;
}

if (show) {
printf("%d|", len);
for (i = 0; i <= len; i++)
printf("%d,%d%s", in[i].l, in[i].u, i == len ? "\n": " -> ");
}


if (n > in[len-1].u + in[len-2].u) {
if (n & 1) return 0;
if (seq_insert(in, len, n/2, len-1)) {
in[len-1].out++;
return seq_recur(in, len-1);
}
return 0;
}

//for (p = n/2, q = n - p; p; p--,q++) {
lim = 0;
if (in[len].out == 1) {
lim = in[in[len].sum].tail;
if (show)
printf("lim %d %d %d\n", len, in[len].sum, lim);
}
if (lim < 1) lim = 1;

//for (p = n/2, q = n - p; p >= lim; p--, q++) {
for (p = lim, q = n - p; p <= q; p++,q--) {
if (seq_len(q) >= len || p != q && seq_len(p) >= len)
continue;

// for (i = 0; i < len; i++) x[i] = in[i];
copy(x, in, 32);

r = len - 1;

if (x[len-1].u == x[len-1].l && x[len-1].u != q) r = 0;
if (show) printf("[%d] need %d %d\n", len, p, q);
if (seq_insert(x, len, q, r) && seq_insert(x, len, p, 0)
&& seq_recur(x, len - 1))
{
for (i = 0; i < len; i++) in[i] = x[i];
return 1;
};
}
return 0;
}

int seq(int n, int *in, int len)
{
int r, i;
rec x[32] = {{0}};
x[0].l = 1; x[1].l = 2; x[len].l = n;
x[0].u = 1; x[1].u = 2; x[len].u = n;

for (i = 2; i < len; i++) {
x[i].l = x[i - 1].l + 1;
x[i].u = x[i - 1].u << 1;
}
for (i = len - 1; i >= 2; i--) {
if (x[i].l * 2 < x[i + 1].l) x[i].l = (x[i + 1].l + 1) / 2;
if (x[i].u >= x[i+1].u) x[i].u = x[i+1].u - 1;
}

r = seq_recur(x, len);
if (r && show) {
printf("Success\n");
for (i = 0; i <= len; i++)
printf("%d,%d%s", x[i].l, x[i].u, i == len ? "\n": " -> ");
}
for (i = 0; i <= len; i++) in[i] = x[i].u;

return r;
}

int seq_len(int n)
{
int r, x[32], lb, l, u, i, j, o, ones[64];

if (length[n] || n <= 2) return length[n];

for (j = n, lb = -1, o = 0; j; j >>= 1, lb++)
if (j & 1) ones[o++] = lb;

u = lb + o - 1;
l = lb + lg2(o);


#if 0
for (i = 0; ; i++) {
r = primes[i];
if (r * r > n) break;
if (n % r) continue;
if (u > (j = seq_len(r) + seq_len(n / r))) u = j;
}
#else
for (i = 2; i * i <= n; i++) {
if (n % i) continue;
if (u <= (j = seq_len(i))) continue;
if (u > (j += seq_len(n / i))) u = j;
}
#endif
if (l == u) goto done;

// if (u > (j = seq_len(n - 1) + 1)) u = j;
// if (l == u) goto done;

if (o <= 3) l = u;
else if (o == 4) {
i = ones[3] - ones[2], j = ones[1] - ones[0];
if (i == j || i == j + 1 ||
(j == 1 && (i == 3 || (i == 5 && ones[2] == ones[1] + 1))))
u = lb + 2;
}
else {
iter = 0;
while (l < u) {
if (!seq(n, x, l)) l++;
else {
printf("lower: %d %d %d\n", n, l, u - l);
u = l;
}
}
printf("iter %d %d\n", n, iter);
}
done:
length[n] = u;

#ifdef KNUTH
if (u != knuth[n])
printf("######### disc: %d %d %d\n", n, l, knuth[n]);
#endif

// printf("%d %d %d\n", n, l, u);
// fflush(stdout);

return u;
}

void pb(int n)
{
int x = 1;
while (x <= n) {
putchar((x & n) ? '#':'-');
x <<= 1;
}
putchar('\n');
}

int yy[] = {1, 2, 4, 8, 16, 32, 64, 128, 129, 257, 340, 514, 771, 1111};
int main()
{
int i, j, t, top, x[32];
make_primes();
int total = 0;

#ifdef KNUTH
FILE *fp = fopen("out", "r");
knuth[0] = 32;
fread(knuth + 1, 1, 20000, fp);
fclose(fp);
for (i = 0; i < 20001; i++) knuth[i] -= 32;
#endif

show = 0;
top = 11129;
for (i = 0; i < top; i++) {
seq(i, x, t = seq_len(i));
printf("== %d ==\n", i);
pb(i);
for (j = 0; j <= t; j++) pb(x[j]);
putchar('\n');
total += iter;
}

printf("%d\n", total);
return 0;
}</lang>
}</lang>

Revision as of 19:49, 12 September 2011

<lang c>#include <stdio.h>

  1. include <stdlib.h>
  2. include <stdint.h>
  3. include <string.h>

typedef uint32_t hash_t;

typedef struct hash_value_t { void *data; char *key; struct hash_value_t *chain; } hash_value_t;

typedef struct hash_table_t { hash_value_t **v, *pool; size_t n, cap; } hash_table_t, *htbl;

inline hash_t hash(char *s) { hash_t hash; for (hash = 0; *s; s++) { hash += *s; hash += (hash << 10); hash ^= (hash >> 6); } hash += hash << 3; hash ^= hash >> 11; hash += hash << 15; return hash; }

htbl hash_new(size_t size) { htbl h = calloc(1, sizeof(hash_table_t)); if (!size) size = 4;

for (h->cap = 1; h->cap < size; h->cap <<= 1);

h->v = calloc(h->cap, sizeof(hash_value_t*)); h->pool = 0; return h; }

hash_value_t *hash_get_storage(htbl t) { size_t len; hash_value_t *p = t->pool; if (!p) { len = 1024; if (len > t->cap) len = t->cap; t->pool = calloc(len, sizeof(hash_value_t)); for (p = t->pool; len > 1; len --) p->chain = p + 1; p = t->pool; } t->pool = p->chain; return p; }

void hash_insert_node(htbl t, hash_value_t *p) { size_t idx = hash(p->key) % t->cap; p->chain = t->v[idx]; t->v[idx] = p; }

void hash_expand(htbl t) { size_t i, c = t->cap; hash_value_t *p, *tmp;

t->v = realloc(t->v, sizeof(hash_value_t*) * c * 2); memset(t->v + c, 0, c * sizeof(hash_table_t*));

t->cap *= 2; for (i = 0; i < c; i++) { p = t->v[i]; if (!p) continue;

t->v[i] = 0; while (p) { tmp = p->chain; p->chain = 0; hash_insert_node(t, p); p = tmp; } } }

void hash_insert(htbl t, char *s, void *data) { hash_value_t *p = hash_get_storage(t); if (t->n * 5 >= t->cap * 4) hash_expand(t); p->key = strdup(s); p->data = data; hash_insert_node(t, p); t->n ++; }

void* hash_remove(htbl t, char *s) { size_t idx = hash(s) % t->cap; hash_value_t *head = 0, *p = t->v[idx];

while (p) { if (!strcmp(p->key, s)) break; head = p; p = p->chain; } if (!p) return 0;

free(p->key);

if (head) head->chain = p->chain; else t->v[idx] = p->chain;

p->chain = t->pool; t->pool = p; t->n--; return p->data; }

void* hash_lookup(htbl t, char *s) { size_t idx = hash(s) % t->cap; hash_value_t *p; p = t->v[idx]; while (p) { if (!strcmp(p->key, s)) return p->data; p = p->chain; } return (void*)-1; }</lang>