ga.c - brcon2024-hackathons - Bitreichcon 2024 Hackathons
HTML git clone git://bitreich.org/brcon2024-hackathons git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/brcon2024-hackathons
DIR Log
DIR Files
DIR Refs
DIR Tags
DIR 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_t cl)
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_t cl)
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 = %d\n", g1->fitness, g2->fitness, w1->fitness);
198 cross(g1->code, CODE_LENGTH, g2->code, CODE_LENGTH, newcode, CODE_LENGTH);
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 }