User:Ledrug/bits

From Rosetta Code

<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> <lang c>#include <stdio.h>

  1. include <string.h>
  1. define maxn 1000000
  2. define maxp 1000

int primes[maxp] = {2, 3}, n_primes = 2;

  1. ifdef KNUTH

char knuth[20000+2];

  1. 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;

  1. 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; }

  1. 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] = Template: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);


  1. 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; }

  1. 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; }

  1. 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;

  1. ifdef KNUTH

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

  1. 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;

  1. 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;

  1. 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>

Retrieved from "https://rosettacode.org/wiki/User:Ledrug/bits?oldid=196664"