Rosetta Code

User:Ledrug/bits: Difference between revisions

User page Discussion

User:Ledrug/bits (view source)

Revision as of 21:26, 16 September 2012

2,744 bytes added ,  11 years ago
no edit summary
No edit summary
No edit summary
 
(12 intermediate revisions by the same user not shown)
Line 2:
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
 
#define N 100
typedef uint32_t pint;
#define D 6
typedef uint64_t xint;
typedef unsigned int uint;
 
typedef float flt;
int is_prime(xint);
typedef struct { flt p1, p2; int32_t hold; } strat;
strat ** prob;
#define P(op, sc, h) (prob[(op) * N + (sc)][h])
inline flt better(strat * p) {
return p->hold ? p->p1 : p->p2;
}
 
inline intflt next_primep_better(pintint pop, int sc, int h) {
return better(&P(op, sc, h));
}
 
#define FOR(x, n) for (x = 0; x < n; x++)
 
void mkarray()
{
int i, j;
if (p == 2) return 3;
prob = malloc(sizeof(*prob) * N * N);
for (p += 2; p > 1 && !is_prime(p); p += 2);
strat * pp = calloc(sizeof(*pp), N * N * (N + 1) / 2);
if (p == 1) return 0;
 
return p;
FOR(i, N) FOR(j, N)
prob[i * N + j] = pp, pp += N - j;
}
 
int is_primestep_array(xint n)
{
int converged = 1;
# define NCACHE 8192
int i, j, k, r;
# define S (sizeof(uint) * 2)
static uint cache[NCACHE] = {0};
 
FOR(i, N) FOR(j, N) FOR(k, N - j) {
pint p = 2;
strat *p = &P(i, j, k);
int ofs, bit = -1;
 
flt p_current = p_better(i, j, k), chance1, chance2;
if (n < NCACHE * S) {
ofs = n / S;
bit = 1 << ((n & (S - 1)) >> 1);
if (cache[ofs] & bit) return 1;
}
 
chance1 = 1 - p_better(j + k, i, 0); // if holding
do {
if (n % p == 0) return 0;
if (p * p > n) break;
} while ((p = next_prime(p)));
 
chance2 = 1 - p_better(j, i, 0); // if rolling
if (bit != -1) cache[ofs] |= bit;
for (r = 2; r <= D; r++)
return 1;
chance2 += (j + k + r >= N) ? 1 : p_better(i, j, k + r);
chance2 /= D;
 
p->p1 = chance1;
p->p2 = chance2;
p->hold = k && chance1 > chance2;
 
if (converged && fabs(p_better(i, j, k) - p_current) > 1e-4)
converged = 0;
}
 
return converged;
}
 
void write_array()
int decompose(xint n, pint *out)
{
int i, =j, 0k;
FOR(i, N) {
pint p = 2;
while FOR(n >j, pN *- pi) {
while printf(n"%2d %2d: p", ==i, 0j) {;
out[i++]FOR(k, =N) p;{
n strat *p /= p&P(k,i,j);
putchar(p->hold ? '.' : 'R');
printf("(%.3f %.3f) ", p->p1, p->p2);
}
putchar('\n');
}
putchar('\n');
if (!(p = next_prime(p))) break;
}
if (n > 1) out[i++] = n;
return i;
}
 
int main(void)
{
int i, j,= len0;
mkarray();
xint z;
 
pint out[100];
while (!step_array())
for (i = 2; i < 64; i = next_prime(i)) {
fprintf(stderr, "iter %d\n", ++i);
z = (1ULL << i) - 1;
 
printf("2^%d - 1 = %llu = ", i, z);
write_array();
fflush(stdout);
len = decompose(z, out);
for (j = 0; j < len; j++)
printf("%u%s", out[j], j < len - 1 ? " x " : "\n");
}
 
return 0;
}</lang>
 
<lang c>#include <stdio.h>
<lang c>#include <ucontext.h>
#include <stdlib.h>
#include <stdintstdio.h>
#include <stdarg.h>
#include <string.h>
 
struct hist_t {
typedef uint32_t pint;
ucontext_t caller, callee;
typedef uint64_t xint;
void **in, *out;
typedef unsigned int uint;
int first;
struct hist_t *prev;
uint8_t *pbits;
} *hist;
pint sieved;
 
void backtrack() {
#define MAX_PRIME (~(uint32_t)1)
if (!hist) {
#define MAX_PRIME_SQ 65535U
puts("backtracking exhausted");
#define PBITS (MAX_PRIME * 8 / 30 + 1)
abort();
pint next_prime(pint);
int is_prime(pint);
void sieve(pint);
 
uint8_t bit_pos[30] = {
0, 1<<0, 0, 0, 0, 0,
0, 1<<1, 0, 0, 0, 1<<2,
0, 1<<3, 0, 0, 0, 1<<4,
0, 1<<5, 0, 0, 0, 1<<6,
0, 0, 0, 0, 0, 1<<7,
};
 
uint8_t rem_num[] = { 1, 7, 11, 13, 17, 19, 23, 29 };
 
void init_primes()
{
pint tgt = 4;
pbits = malloc(PBITS);
 
FILE *fp = fopen("primebits", "r");
if (fp) {
fread(pbits, 1, PBITS, fp);
sieved = MAX_PRIME_SQ;
fclose(fp);
return;
}
setcontext(&hist->callee);
 
memset(pbits, 255, PBITS);
sieved = 5;
while (sieved < MAX_PRIME_SQ) {
if (sieved > tgt) {
tgt *= 2;
fprintf(stderr, "sieve %u\n", sieved);
}
sieve(sieved);
}
fp = fopen("primebits", "w");
fwrite(pbits, 1, PBITS, fp);
fclose(fp);
}
 
ucontext_t* hpush()
void sieve(pint p)
{
struct hist_t *h = malloc(sizeof(*h));
xint p1 = p * p;
pint oh->in = sieved0;
h->out = 0;
unsigned char bits;
h->prev = hist;
uint32_t addr;
hist = h;
off_t shift[8];
return &hist->caller;
int n_shift = 0, i;
}
 
void hpop() {
if (sieved > 5)
struct hist_t *s = hist;
while (sieved < p + 30) {
hist = hist->prev;
addr = p1 / 30;
bits = bit_pos[p1 % 30];
if (!n_shift || addr > shift[n_shift - 1])
shift[n_shift++] = addr;
 
if (s->in) free(s->in);
pbits[addr] &= ~bits;
free(s->callee.uc_stack.ss_sp);
sieved = next_prime(sieved);
free(s);
p1 = p * sieved;
}
sieved = next_prime(o);
 
i = 0;
addr = o = shift[0] + p;
while (addr < PBITS) {
pbits[addr] = pbits[addr - p];
addr = o + shift[i++];
if (i == n_shift) {
i = 0;
o += p;
}
}
 
backtrack();
}
 
pintvoid next_primeyield(pintvoid *p)
{
hist->out = p;
off_t addr;
swapcontext(&hist->callee, &hist->caller);
uint8_t bits, rem;
}
 
void hinit(void **in, void (*func)())
if (p > 5) {
{
addr = p / 30;
if (!hist->in) {
bits = bit_pos[ p % 30 ] << 1;
hist->in = in;
for (rem = 0; (1 << rem) < bits; rem++);
getcontext(&hist->callee);
while (pbits[addr] < bits || !bits) {
hist->callee.uc_stack.ss_sp = malloc(4096);
addr++;
hist->callee.uc_stack.ss_size = 4096;
bits = 1;
hist->callee.uc_link = &hist->caller;
rem = 0;
makecontext(&hist->callee, func, 0);
}
setcontext(&hist->callee);
if (addr >= PBITS) return 0;
while (!(pbits[addr] & bits)) {
rem++;
bits <<= 1;
}
p = addr * 30 + rem_num[rem];
return p;
}
switch(p) {
case 2: return 3;
case 3: return 5;
case 5: return 7;
}
return 2;
}
 
#define amb (getcontext(hpush())+_amb)
int decompose(xint n, xint *f)
void *_amb(int n, ...)
{
void iter() {
pint p = 0;
int i = 0;
for (i = 0; hist->in[i]; i++)
while (n >= (xint)p * p) {
yield(hist->in[i]);
if (!(p = next_prime(p))) break;
hpop();
while (n % p == 0) {
n /= p;
f[i++] = p;
}
}
 
if (n > 1) f[i++] = n;
returnint i;
va_list ap;
void **buf = calloc((1 + n), sizeof(buf[0]));
 
va_start(ap, n);
for (i = 0; i < n; i++)
buf[i] = va_arg(ap, void*);
va_end(ap);
 
hinit(buf, iter);
return hist->out;
}
 
int main(void)
{
int ijoin(char *a, len;char *b) {
return a[strlen(a) - 1] == b[0];
pint p = 0;
}
xint f[100], po;
init_primes();
 
char *a = amb(3, "the", "that", "a"),
while ((p = next_prime(p)) < 63) {
*b = amb(3, "frog", "elephant", "thing"),
po = (1LLU << p) - 1;
printf("2^%u*c = %llu =amb(3, "walked", p"treaded", po"grows");,
*d = amb(3, "slowly", "quickly", "deathly");
fflush(stdout);
 
if (join(a, b) && join(b, c) && join(c, d))
printf("%s %s %s %s\n", a, b, c, d);
else
amb(0);
 
// should put a backtrack barrier here
 
int s[] = {1, 2, 3, 4};
 
int x = *(int*)amb(4, s, s+1, s+2, s+3);
int y = *(int*)amb(3, s, s+1, s+2);
int z = *(int*)amb(3, s, s+1, s+2);
 
//if (! (x > y && y < z && z < x && (x > 4))) // make "thing grows slowly"
if (! (x > y && y < z && z < x && !(x & 1)))
backtrack();
 
printf("%d %d %d\n", x, y, z);
 
len = decompose(po, f);
for (i = 0; i < len; i++)
printf("%llu%s", f[i], i == len - 1 ? "\n" : " x ");
}
return 0;
}</lang>
 
<lang lisp>(defmacro or= (x y) `(setf ,x (logior ,x ,y)))
(defmacro and= (x y) `(setf ,x (logand ,x ,y)))
 
(defconstant +N+ 1)
(defconstant +S+ 2)
(defconstant +W+ 4)
(defconstant +E+ 8)
(defconstant +V+ 16)
 
(defun show-maze (a)
(let ((h (1- (array-dimension a 0)))
(w (1- (array-dimension a 1)))
(g " │││─┘┐┤─└┌├─┴┬┼"))
(write-line "")
(loop for y from 0 to h do
(loop for x from 0 to w do
(format t "~c" (char g (logand (aref a y x) (lognot +V+)))))
(format t "~%"))))
 
(defun make-maze (w h)
(let* (xs (size (* (1- w) (1- h)))
(w2 (* 2 w)) (h2 (* 2 h))
(walls (make-array (list (1+ h2) (1+ w2))
:element-type 'integer :initial-element 0)))
 
(flet ((visit (y x) (or= (aref walls y x) +V+))
(rand-element (list r)
(loop for x in list with c = 1 with sel do
(if (zerop (random c)) (setf sel x))
(incf c r)
finally (return sel)))
(connect (c1 c2)
(let ((y1 (car c1)) (y2 (car c2))
(x1 (cdr c1)) (x2 (cdr c2)))
(if (= x1 x2)
(progn (or= (aref walls (min y1 y2) x1) +S+)
(or= (aref walls (1+ (min y1 y2)) x1) +S+)
(or= (aref walls (1+ (min y1 y2)) x1) +N+)
(or= (aref walls (max y1 y2) x1) +N+))
(progn (or= (aref walls y1 (min x1 x2)) +E+)
(or= (aref walls y1 (1+ (min x1 x2))) +E+)
(or= (aref walls y1 (1+ (min x1 x2))) +W+)
(or= (aref walls y1 (max x1 x2)) +W+)))))
(neighbor (cell)
(loop with cnt = 0 with next-cell
for (dy dx) in '((-2 0) (2 0) (0 2) (0 -2)) do
(let ((y (+ (car cell) dy)) (x (+ (cdr cell) dx)))
(if (and (array-in-bounds-p walls y x)
(not (logtest (aref walls y x) +V+))
(zerop (random (incf cnt))))
(setf next-cell (cons y x))))
finally (return next-cell))))
(setf xs (append
(loop for y from 0 to h
collect (cons (* 2 y) 0) collect (cons (* 2 y) w2)
do (let ((y2 (* 2 y)))
(visit y2 0) (visit y2 w2)
(when (< y2 h2)
(connect (cons y2 0) (cons (+ 2 y2) 0))
(connect (cons y2 w2) (cons (+ 2 y2) w2)))))
(loop for x from 0 to w
collect (cons 0 (* 2 x)) collect (cons h2 (* 2 x))
do (let ((x2 (* 2 x)))
(visit 0 x2) (visit h2 x2)
(when (< x2 w2)
(connect (cons 0 x2) (cons 0 (+ 2 x2)))
(connect (cons h2 x2) (cons h2 (+ 2 x2))))))))
 
(loop while xs do
;(let* ((c (elt xs (random (length xs)))) (c2 (neighbor c)))
(let* ((c (rand-element xs 100)) (c2 (neighbor c)))
;(let* ((c (first xs)) (c2 (neighbor c)))
(cond ((not c2) (setf xs (remove c xs :test #'equal)))
(t (connect c c2)
(visit (car c2) (cdr c2))
(decf size)
(push c2 xs)
))))
 
(show-maze walls))))
 
(print (make-maze 42 25))</lang>
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/196657...196670"