User:Ledrug/bits: Difference between revisions
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>
- include <stdlib.h>
- include <stdint.h>
- 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>