GopherProxy

	ga.c - brcon2024-hackathons - Bitreichcon 2024 Hackathons
	git clone git://bitreich.org/brcon2024-hackathons git://enlrupgkhuxnvlhsf6lc3fz…
	Log
	Files
	Refs
	Tags
	Submodules
	---
	ga.c (3316B)
	---
	1 #include <stdint.h>
	2 #include <stdio.h>
	3 #include <stddef.h>
	4 #include <stdlib.h>
	5 #include <string.h>
	6
	7 struct machine {
	8 uint8_t a;
	9
	10 uint8_t loads;
	11 uint8_t adds;
	12 uint8_t subs;
	13 uint8_t times;
	14 uint8_t noops;
	15
	16 uint8_t instr;
	17 };
	18
	19 enum {
	20 LOAD,
	21 ADD,
	22 SUB,
	23 TIMES,
	24 END,
	25 };
	26
	27 #define CODE_LENGTH 16
	28 #define POOL_LENGTH 16
	29 struct genome {
	30 uint8_t code[CODE_LENGTH + 1]; /* +1 sentinal (0) */
	31 uint16_t fitness;
	32 } pool[POOL_LENGTH];
	33
	34 uint8_t newcode[CODE_LENGTH];
	35
	36 void
	37 execute(struct machine *m, size_t l, uint8_t code[])
	38 {
	39 size_t ip;
	40 int16_t c;
	41
	42 for (ip = 0; ip < l;) {
	43 switch (code[ip++] & 0x7) {
	44 case LOAD:
	45 m->loads++;
	46 m->a = code[ip++];
	47 break;
	48 case ADD:
	49 m->adds++;
	50 c = (int16_t)m->a + code[ip++];
	51 if (c > 255)
	52 m->a = 0;
	53 else
	54 m->a = c;
	55 break;
	56 case SUB:
	57 m->subs++;
	58 c = (int16_t)m->a - code[ip++];
	59 if (c < 0)
	60 m->a = 0;
	61 else
	62 m->a = c;
	63 break;
	64 case TIMES:
	65 m->times++;
	66 m->a = (uint16_t)m->a * code[ip++] / 255;
	67 break;
	68 case END:
	69 m->instr++;
	70 return;
	71 break;
	72 default:
	73 m->noops++;
	74 break;
	75 }
	76 m->instr++;
	77 }
	78 }
	79
	80 void
	81 mutate(uint8_t code[], size_t l)
	82 {
	83 uint8_t i, bi, j;
	84
	85 for (j = 0; j < 4; j++) {
	86 if (rand() % 100 >= 50)
	87 continue;
	88
	89 i = rand() % CODE_LENGTH;
	90 bi = rand() % 8;
	91
	92 code[i] ^= 1 << bi;
	93 }
	94 }
	95
	96 #define min(a, b) (((a) < (b)) ? (a) : (b))
	97
	98 void
	99 cross(uint8_t a[], size_t al, uint8_t b[], size_t bl, uint8_t c[], size_…
	100 {
	101 uint8_t i, si, sl;
	102 uint8_t one, two;
	103
	104 if (rand() % 2) {
	105 one = a;
	106 two = b;
	107 } else {
	108 one = b;
	109 two = a;
	110 }
	111
	112 si = rand() % (min(al, bl) + 1);
	113 sl = rand() % (min(al, bl) - si + 1);
	114
	115 for (i = 0; i < si; i++)
	116 c[i] = one[i];
	117
	118 for (; i < si + sl; i++)
	119 c[i] = two[i];
	120
	121 for (; i < cl; i++)
	122 c[i] = one[i];
	123 }
	124
	125 void
	126 cross2(uint8_t a[], size_t al, uint8_t b[], size_t bl, uint8_t c[], size…
	127 {
	128 uint8_t i;
	129
	130 for (i = 0; i < al; i++)
	131 c[i] = a[i] + b[i];
	132 }
	133
	134 void
	135 printcode(uint8_t code[], size_t l)
	136 {
	137 uint8_t i;
	138
	139 for (i = 0; i < l;) {
	140 switch (code[i++] & 0x7) {
	141 case LOAD:
	142 printf("LOAD %d ", code[i++]);
	143 break;
	144 case ADD:
	145 printf("ADD %d ", code[i++]);
	146 break;
	147 case SUB:
	148 printf("SUB %d ", code[i++]);
	149 break;
	150 case TIMES:
	151 printf("TIMES %d ", code[i++]);
	152 break;
	153 case END:
	154 printf("END ");
	155 return;
	156 break;
	157 default:
	158 printf("NOOP ");
	159 break;
	160 }
	161 }
	162 }
	163
	164 int
	165 main(void)
	166 {
	167 struct machine m;
	168 struct genome g1, g2, *w1;
	169 size_t i, j;
	170
	171 for (i = 0; i < POOL_LENGTH; i++) {
	172 for (j = 0; j < CODE_LENGTH; j++)
	173 pool[i].code[j] = rand();
	174 pool[i].code[j] = 0;
	175 }
	176
	177 do {
	178 g1 = g2 = w1 = NULL;
	179
	180 for (i = 0; i < POOL_LENGTH; i++) {
	181 memset(&m, 0, sizeof(m));
	182
	183 execute(&m, CODE_LENGTH, pool[i].code);
	184 pool[i].fitness = m.a * 255 / (m.instr + m.loads…
	185
	186 if (!g1 \|\| g1->fitness < pool[i].fitness) {
	187 g2 = g1;
	188 g1 = &pool[i];
	189 } else if (!g2 \|\| g2->fitness < pool[i].fitness)…
	190 w1 = g2;
	191 g2 = &pool[i];
	192 } else if (!w1 \|\| w1->fitness > pool[i].fitness)…
	193 w1 = &pool[i];
	194 }
	195 }
	196
	197 printf("g1->fitness = %d, g2->fitness = %d, w1->fitness …
	198 cross(g1->code, CODE_LENGTH, g2->code, CODE_LENGTH, newc…
	199 mutate(newcode, CODE_LENGTH);
	200
	201 printcode(newcode, CODE_LENGTH);
	202 puts("");
	203
	204 memcpy(w1->code, newcode, CODE_LENGTH);
	205 } while (1);
	206 }