Skip to content

Instantly share code, notes, and snippets.

@noonat noonat/level1.py
Created Jan 24, 2013

Embed
What would you like to do?
Some code to solve the Colossal Cue puzzles at http://adventure.cueup.com/
m = 4294967296
a = 69069
c = 1
seed = 6
for i in range(4):
seed = (a * seed + c) % m
print "%i" % (seed % 36)
stack = []
braces = ('{{[{{{{}}{{}}}[]}[][{}][({[(('
'{{[][()()]}}{[{{{}}}]}))][()]'
'{[[{((()))({}(())[][])}][]()]'
'}{()[()]}]})][]]}{{}[]}}')
opening_braces = '{[('
closing_braces = '}])'
for index, brace in enumerate(braces):
if brace in opening_braces:
stack.append(opening_braces.index(brace))
else:
opening_index = stack.pop()
closing_index = closing_braces.index(brace)
if opening_index != closing_index:
print "error at %i" % index
break
import pprint
cols = 5
rows = 5
costs = [[8, 8, 4, 4, 5],
[4, 9, 6, 4, 8],
[8, 6, 4, 1, 2],
[4, 8, 2, 6, 3],
[0, 6, 8, 8, 4]]
cells = []
for y in range(rows):
cells.append([])
for x in range(cols):
cell = {'cost': costs[y][x],
'x': x,
'y': y}
cells[y].append(cell)
def get_cell(x, y):
if x < 0 or y < 0 or x >= cols or y >= rows:
return None
return cells[y][x]
neighbors = []
for y in range(rows):
neighbors.append([])
for x in range(cols):
ns = [('w', get_cell(x - 1, y)),
('e', get_cell(x + 1, y)),
('n', get_cell(x, y - 1)),
('s', get_cell(x, y + 1))]
neighbors[y].append(ns)
x1 = 0
y1 = 4
x2 = 4
y2 = 0
chips = 35
dirs = []
path = []
def visit(cell):
global i, chips
x = cell['x']
y = cell['y']
chips -= cell['cost']
path.append(cell)
if chips >= 0:
if cell['x'] == x2 and cell['y'] == y2:
if chips == 0:
pprint.pprint(path)
print ' '.join(dirs)
raise TypeError
else:
for direction, neighbor in neighbors[y][x]:
if neighbor is not None:
dirs.append(direction)
visit(neighbor)
dirs.pop()
chips += cell['cost']
path.remove(cell)
try:
visit(cells[y1][x1])
except TypeError:
pass
// llvm-gcc -O3 --std=c99 -Wall -o level4 level4.c && ./level4
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
const uint64_t m = 4294967296;
const uint64_t a = 69069;
const uint64_t c = 1;
const uint8_t targets[] = {34, 27, 16, 1, 34, 31, 24, 17, 34, 35, 16, 13};
const uint8_t targets_length = sizeof(targets) / sizeof(uint8_t);
uint64_t vax_random(const uint64_t seed) {
return (a * seed + c) % m;
}
int main(int argc, char **argv) {
uint64_t seed;
uint8_t last_percent = 0;
for (uint64_t initial_seed = 0; initial_seed < m; ++initial_seed) {
uint8_t percent = (int)((float)initial_seed / m * 100);
if (last_percent < percent) {
last_percent = percent;
fprintf(stderr, "\b\b\b\b%3i%%", percent);
fflush(stderr);
}
seed = initial_seed;
bool seed_matched = true;
for (uint8_t i = 0; i < targets_length; ++i) {
seed = vax_random(seed);
if (seed % 36 != targets[i]) {
seed_matched = false;
break;
}
}
if (seed_matched == true) {
fprintf(stderr, "\b\b\b\bmatched with seed %llu\n", initial_seed);
break;
}
}
for (uint8_t i = 0; i < 3; ++i) {
seed = vax_random(seed);
fprintf(stdout, "%llu\n", seed % 36);
}
return 0;
}
// llvm-gcc -O3 --std=c99 -Wall -o level5 level5.c && ./level5
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef enum dir_s {
DIR_N = 0,
DIR_S = 1,
DIR_W = 2,
DIR_E = 3
} dir_t;
typedef struct neighbor_s {
struct neighbor_s * next;
struct room_s * room;
dir_t dir;
} neighbor_t;
typedef struct room_s {
int32_t x;
int32_t y;
int32_t cost;
neighbor_t * neighbors;
} room_t;
typedef struct path_s {
dir_t dir;
room_t *room;
int32_t cost;
} path_t;
#define WIDTH 12
#define HEIGHT 12
room_t rooms[HEIGHT][WIDTH];
const int32_t room_costs[HEIGHT][WIDTH] = {
{0, 8, 1, 7, 8, 8, 5, 2, 9, 5, 9, 5},
{8, 5, 1, 1, 5, 6, 9, 4, 4, 5, 2, 1},
{7, 2, 3, 5, 2, 9, 2, 6, 9, 3, 9, 4},
{9, 2, 5, 9, 8, 9, 5, 7, 7, 5, 9, 6},
{2, 4, 6, 7, 1, 4, 2, 6, 6, 2, 5, 8},
{2, 8, 1, 5, 3, 8, 4, 9, 7, 5, 2, 3},
{2, 9, 3, 5, 6, 7, 2, 4, 9, 4, 2, 5},
{6, 3, 1, 7, 8, 2, 3, 3, 6, 7, 9, 3},
{2, 5, 7, 4, 2, 7, 8, 5, 5, 3, 5, 8},
{5, 2, 9, 8, 3, 6, 1, 4, 9, 5, 6, 3},
{4, 6, 9, 8, 5, 4, 9, 7, 6, 4, 6, 8},
{2, 7, 7, 1, 9, 9, 7, 3, 7, 2, 2, 5}
};
room_t * const start_room = &rooms[0][0];
room_t * const goal_room = &rooms[11][11];
int32_t chips = 444;
neighbor_t neighbor_pool[WIDTH * HEIGHT * 4];
neighbor_t * neighbor_pool_next = neighbor_pool;
unsigned char dir_char(const dir_t dir) {
switch (dir) {
case DIR_N: return 'n';
case DIR_S: return 's';
case DIR_W: return 'w';
case DIR_E: return 'e';
default: return '?';
}
}
room_t * room_get(const int32_t x, const int32_t y) {
if (x < 0 || y < 0 || x >= WIDTH || y >= HEIGHT) {
return NULL;
}
return &rooms[y][x];
}
void room_add_neighbor(room_t * const room, const dir_t dir) {
room_t * neighbor_room;
switch (dir) {
case DIR_N: neighbor_room = room_get(room->x, room->y - 1); break;
case DIR_S: neighbor_room = room_get(room->x, room->y + 1); break;
case DIR_W: neighbor_room = room_get(room->x - 1, room->y); break;
case DIR_E: neighbor_room = room_get(room->x + 1, room->y); break;
default: neighbor_room = NULL;
}
if (!neighbor_room) {
return;
}
neighbor_t * const neighbor = neighbor_pool_next++;
neighbor->next = room->neighbors;
neighbor->room = neighbor_room;
neighbor->dir = dir;
room->neighbors = neighbor;
}
void rooms_add_cost(const int32_t cost) {
for (int32_t y = 0; y < HEIGHT; ++y) {
for (int32_t x = 0; x < WIDTH; ++x) {
room_t * const room = &rooms[y][x];
if (room != goal_room) {
rooms[y][x].cost += cost;
}
}
}
}
void rooms_init() {
memset(rooms, 0, sizeof(rooms));
for (int32_t y = 0; y < HEIGHT; ++y) {
for (int32_t x = 0; x < WIDTH; ++x) {
room_t * const room = &rooms[y][x];
room->x = x;
room->y = y;
room->cost = room_costs[y][x];
}
}
neighbor_pool_next = neighbor_pool;
memset(neighbor_pool, 0, sizeof(neighbor_pool));
for (int32_t y = 0; y < HEIGHT; ++y) {
for (int32_t x = 0; x < WIDTH; ++x) {
room_t * const room = &rooms[y][x];
room_add_neighbor(room, DIR_N);
room_add_neighbor(room, DIR_S);
room_add_neighbor(room, DIR_W);
room_add_neighbor(room, DIR_E);
}
}
}
bool room_visit(const room_t * const room, const int depth, path_t ** out_path,
int32_t * out_path_depth) {
chips -= room->cost;
if (chips == 0 && room == goal_room) {
*out_path_depth = depth;
*out_path = malloc(sizeof(path_t) * depth);
memset(*out_path, 0, sizeof(path_t));
return true;
} else if (chips > 0) {
if (depth != 0) {
rooms_add_cost(1);
}
for (neighbor_t * n = room->neighbors; n; n = n->next) {
const int32_t cost = n->room->cost;
if (room_visit(n->room, depth + 1, out_path, out_path_depth)) {
path_t * const path = *out_path + depth;
path->dir = n->dir;
path->room = n->room;
path->cost = cost;
return true;
}
}
if (depth != 0) {
rooms_add_cost(-1);
}
}
chips += room->cost;
return false;
}
int main(int argc, char ** argv) {
rooms_init();
path_t * path = NULL;
int32_t path_depth = 0;
if (room_visit(start_room, 0, &path, &path_depth)) {
fprintf(stdout, "i\tdir\tcost\n");
for (int32_t i = 0; i < path_depth; ++i) {
path_t * p = path + i;
fprintf(stderr, "%i\t%c\t%i\n", i, dir_char(p->dir), p->cost);
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.