commit 9d185ab6e37685ebf1276a1991d46623af00f802
Author: Ryan Wolf <rwolf@borderstylo.com>
Date: Sun, 7 Mar 2010 23:45:00 -0800
initial import
Diffstat:
| A | makefile | | | 19 | +++++++++++++++++++ |
| A | perm_gen.c | | | 109 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | perm_gen.h | | | 19 | +++++++++++++++++++ |
| A | primes.c | | | 79 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | primes.h | | | 15 | +++++++++++++++ |
| A | tturns_small.c | | | 54 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | utils.c | | | 424 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | utils.h | | | 48 | ++++++++++++++++++++++++++++++++++++++++++++++++ |
8 files changed, 767 insertions(+), 0 deletions(-)
diff --git a/makefile b/makefile
@@ -0,0 +1,19 @@
+CC = gcc
+
+tturns_small: tturns_small.o
+ $(CC) -O3 primes.o perm_gen.o utils.o tturns_small.o -o tturns_small
+
+tturns_small.o: utils.o utils.h tturns_small.c
+ $(CC) -O3 -c primes.o perm_gen.o utils.o tturns_small.c
+
+utils.o: primes.o perm_gen.o utils.c utils.h
+ $(CC) -O3 -c primes.o perm_gen.o utils.c
+
+primes.o: primes.c primes.h
+ $(CC) -O3 -c primes.c
+
+perm_gen.o: perm_gen.c primes.h
+ $(CC) -O3 -c perm_gen.c
+
+clean:
+ rm -rf *.o
diff --git a/perm_gen.c b/perm_gen.c
@@ -0,0 +1,109 @@
+/***
+* perm_gen.c
+*
+* adapted from http://cs/courses/fall2008/algorithms/code/c_examples/structs.c
+* and http://cs/courses/fall2008/algorithms/code/c_examples/node_list.c
+***/
+
+#include <stdio.h> // printf
+#include <stdlib.h> // for malloc
+
+// link
+// alias for pointer
+typedef struct link_type *link;
+// structure pointed to
+struct link_type {
+ int value;
+ link next;
+};
+// constructor
+link new_link(int value, link next){
+ link self = (link) malloc(sizeof(struct link_type));
+ if (self){ // don't do this if memory wasn't allocated.
+ self->value = value; // set fields
+ self->next = next;
+ }
+ return self;
+}
+
+// build a chain of links
+link new_chain(int links) {
+ // make an empty chain
+ link cur = NULL;
+ int i = 0;
+ for (i; i < links; i++) {
+ link next = new_link(0, cur);
+ cur = next;
+ }
+ return cur; // last link in chain
+}
+
+// chain utilities
+
+// chain comparision
+// 1 for true, 0 for false
+int chains_equal (link first, link second) {
+ while (first->next != NULL) {
+ if (second->next == NULL) { // if first is longer than second
+ return 0;
+ }
+ else if (first->value != second->value) {
+ return 0;
+ }
+ first = first->next; // advance along chains
+ second = second->next;
+ }
+ // if second is longer than first
+ if (second->next != NULL) {
+ return 0;
+ }
+ // if they are the same length and each link has the same value
+ return 1;
+}
+
+// copy a chain
+link chain_cpy(link target) {
+ if (target == NULL) {
+ return NULL;
+ }
+ link first = new_link(target->value, NULL);
+ link last = first;
+ link tmp_tar = target;
+ while (tmp_tar->next != NULL) {
+ tmp_tar = tmp_tar->next; // advance
+ link next = new_link(tmp_tar->value, NULL);
+ last->next = next;
+ last = next;
+ }
+ return first;
+}
+
+// print chain
+int print_chain(link cur) {
+ while (cur != NULL) {
+ printf("%d ", cur->value);
+ cur = cur->next;
+ }
+ return 0;
+}
+
+int perm_gen_test() {
+ link first = new_chain(3); // two empty chains, length 3
+ link second = new_chain(3);
+ printf("Test (expect 1): %d\n", chains_equal(first, second)); // are equal
+
+ second = new_chain(2); // turn one of them into a chain of 2
+ printf("Test (expect 0): %d\n", chains_equal(first, second)); // no longer equal
+
+ first->next->next->value = 4; // set the value of the last link in the first chain
+ printf("Test (expect 4): %d\n", first->next->next->value); // print it
+
+ second = new_chain(3); // change second chain back to length 3
+ printf("Test (expect 0): %d\n", chains_equal(first, second)); // are not equal
+
+ // printing
+ printf("Test (expect 0 0 4): ");
+ print_chain(first);
+ printf("\n");
+ return 0;
+}
diff --git a/perm_gen.h b/perm_gen.h
@@ -0,0 +1,19 @@
+/**
+* perm_gen.h : "header" (i.e. API interface) for perm_gen.c code.
+*
+* adapted from http://cs/courses/fall2008/algorithms/code/c_examples/multiple_files/some_func.h
+**/
+
+typedef struct link_type *link;
+struct link_type {
+ int value;
+ link next;
+};
+
+link new_chain(int links);
+
+link chain_cpy(link target);
+
+int chains_equal (link first, link second);
+
+int print_chain(link cur);
diff --git a/primes.c b/primes.c
@@ -0,0 +1,79 @@
+/***
+* primes.c
+*
+* generate an singly-linked list of the first n primes
+***/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+// from http://cs/courses/fall2008/algorithms/code/c_examples/node_list.c
+typedef struct prime_type *prime;
+struct prime_type {
+ int value;
+ prime next;
+};
+
+// constructor for single prime node
+prime new_prime(int value, prime next) {
+ prime self = (prime) malloc(sizeof(struct prime_type));
+ if (self){ // don't do this if memory wasn't allocated.
+ self->value = value; // set fields
+ self->next = next;
+ }
+ return self;
+}
+
+// given a number and a list of all primes lower than that number,
+// determine if number is prime
+int is_prime(int n, prime prime_node) {
+ while (prime_node != NULL) {
+ if (n % prime_node->value == 0) {
+ return 0;
+ }
+ prime_node = prime_node->next;
+ }
+ return 1;
+}
+
+// given a list of primes, find the next prime to add to the list
+int next_prime(prime first, int last_prime) {
+ int to_check = last_prime + 1;
+ while (!is_prime(to_check,first)) {
+ to_check++;
+ }
+ //printf(" the prime after %d is %d\n", last_prime, to_check);
+ return to_check;
+}
+
+// build list of n primes, return first
+prime first_n_primes(int n) {
+ prime first = new_prime(2,NULL);
+ prime cur = first;
+ while (n > 1) {
+ n--;
+ prime next = new_prime(next_prime(first, cur->value), NULL);
+ cur->next = next;
+ cur = next;
+ }
+
+ return first;
+}
+
+// print list of primes
+int print_primes(prime first) {
+ prime cur = first;
+ printf(" list of primes: ");
+ while (cur != NULL) {
+ printf("%d ", cur->value);
+ cur = cur->next;
+ }
+ printf("\n");
+
+ return 0;
+}
+
+int primes_test() {
+ prime first = first_n_primes(10);
+ return print_primes(first);
+}
diff --git a/primes.h b/primes.h
@@ -0,0 +1,15 @@
+/**
+* primes.h : "header" (i.e. API interface) for primes.c code.
+*
+* adapted from http://cs/courses/fall2008/algorithms/code/c_examples/multiple_files/some_func.h
+**/
+
+typedef struct prime_type *prime;
+struct prime_type {
+ int value;
+ prime next;
+};
+
+prime first_n_primes(int n);
+
+int print_primes(prime first);
diff --git a/tturns_small.c b/tturns_small.c
@@ -0,0 +1,54 @@
+/***
+* tturns_small.c
+*
+* Ryan Wolf
+*
+***
+* version 2: same great taste, plus the commandline
+* arguements you want.
+***
+* outputs a dot file of all of the relationships between
+* possible states of a game of twist turns
+* usage:
+* $ time ./tturns_small 3 2
+* graph T {
+* "2 1 0 " -- "1 2 0 ";
+* "2 1 0 " -- "1 0 2 ";
+* "2 1 0 " -- "0 2 1 ";
+* "1 2 0 " -- "2 1 0 ";
+* "1 2 0 " -- "2 0 1 ";
+* "1 2 0 " -- "0 1 2 ";
+* "2 0 1 " -- "0 2 1 ";
+* "2 0 1 " -- "0 1 2 ";
+* "2 0 1 " -- "1 2 0 ";
+* "0 2 1 " -- "2 0 1 ";
+* "0 2 1 " -- "2 1 0 ";
+* "0 2 1 " -- "1 0 2 ";
+* "1 0 2 " -- "0 1 2 ";
+* "1 0 2 " -- "0 2 1 ";
+* "1 0 2 " -- "2 1 0 ";
+* "0 1 2 " -- "1 0 2 ";
+* "0 1 2 " -- "1 2 0 ";
+* "0 1 2 " -- "2 0 1 ";
+* }
+*
+* real 0m0.002s
+* user 0m0.000s
+* sys 0m0.004s
+*
+***/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "utils.h" // twist turns utilities
+
+main(int argc, char* argv[]) {
+ if (argc == 3 && atoi(argv[1]) >= atoi(argv[2])) {
+ state universe = build_universe(atoi(argv[1]),atoi(argv[2]));
+ print_states_dot(universe);
+ }
+ else {
+ printf(" usage: .tturns_small 'number of tiles' 'diameter of wheel'\n");
+ }
+ return 0;
+}
diff --git a/utils.c b/utils.c
@@ -0,0 +1,424 @@
+/***
+* utils.c
+*
+* utility subroutines for tree
+*
+***
+* version 2
+***
+* print_states_dot() now only prints one of the two links,
+* using Jim's pointer trick.
+* now outputs colored links (red for rotation, red for step)
+***/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "primes.h"
+#include "perm_gen.h"
+
+// type definitions used later
+typedef struct advance_node_type *advance_node;
+typedef struct state_type *state;
+
+// since the number of times you can advance the tiles is variable,
+// links to the states that result from those changes will go into an
+// array
+struct advance_node_type {
+ int steps; // how far to advance
+ state leads_to; // what state you enter after making that move
+ advance_node next;
+};
+
+// constructor for advance_node
+advance_node new_advance_node(int i, advance_node next, state leads_to) {
+ advance_node self = (advance_node) malloc(sizeof(struct advance_node_type));
+ if (self){ // don't do this if memory wasn't allocated.
+ self->steps = i; // set fields
+ self->next = next;
+ self->leads_to = NULL;
+ }
+ return self;
+}
+
+//
+struct state_type {
+ link board;
+ state next;
+ state rotate;
+ advance_node advances;
+};
+
+// constructor for single node
+state new_state(link chain, state next) {
+ state self = (state) malloc(sizeof(struct state_type));
+ if (self){ // don't do this if memory wasn't allocated.
+ self->board = chain; // set fields
+ self->next = next;
+ self->rotate = NULL; // set later
+ self->advances = NULL; // set later
+ }
+ return self;
+}
+
+// utilities
+
+// compute the base signature of a chain of a given size
+// i.e. if the board is size 3, the base sig is
+// (first prime) * (second prime) * (3rd prime)
+// 2*3*5 = 30
+int base_signature(prime list) {
+ int product = 1;
+ while (list != NULL) {
+ product *= list->value;
+ list = list->next;
+ }
+ return product;
+}
+
+// compute the signature of a given chain
+// i.e. if the chain is (0,1,1):
+// sig = 2*3*3 = 18
+int gen_sig (link chain, prime list) {
+ link first_chain = chain;
+ prime first_prime = list;
+ int product = 1;
+ while (chain != NULL) {
+ int i = chain->value;
+ list = first_prime;
+ //printf(" for %d:\n", chain->value);
+ while((list != NULL) && (i > 0)) {
+ i--;
+ list = list->next;
+ }
+ //printf(" prime is %d\n", list->value);
+ product *= list->value;
+ chain = chain->next;
+ }
+ return product;
+}
+
+// given the base signature of chain of length n,
+// determine if a given chain contains duplicates
+int no_dupes(link chain, int sig, prime primes) {
+ if (gen_sig(chain, primes) != sig) {
+ return 0;
+ }
+ return 1;
+}
+
+// given a chain and a distance, advance chain until that position
+// fails for numbers higher than n-1, where n is the size of the chain
+link advance(link chain, int r) {
+ link old_start = chain; // pointer to first
+ // move to the rth node
+ while (r > 0) {
+ r--;
+ chain = chain->next;
+ }
+ link new_start = chain; // this is the new start of the chain
+ // move to the end of the chain
+ while (chain->next != NULL) {
+ chain = chain->next;
+ }
+ chain->next = old_start; // connect old start to end
+ // add the null to the end of old chain segment
+ while (chain->next != new_start) {
+ chain = chain->next;
+ }
+ chain->next = NULL;
+ return new_start;
+}
+
+// given a chain and a wheel radius, spin the first r elements of the chain
+link spin(link chain, int r) {
+ link old = chain;
+ // move to the rth node
+ while (r > 1) {
+ r--;
+ chain = chain->next;
+ }
+ link new_start = chain;
+ link broken = chain->next; // bit that is not spun
+ link end = broken;
+ // pull bits off start, add to end of broken
+ while (old->next != end) {
+ link tmp = old->next;
+ old->next = broken;
+ broken = old;
+ old = tmp;
+ }
+ new_start->next = broken; // reconnect broken bits to start
+ return new_start;
+}
+
+// print list of chains
+int print_states(state first) {
+ printf(" list of states:\n");
+ state tmp = first;
+ while (tmp != NULL) {
+ printf(" %p\n board: ", tmp);
+ link links = tmp->board;
+ while (links != NULL) {
+ printf("%d ", links->value);
+ links = links->next;
+ }
+ printf("\n");
+ printf(" rotate: %p\n", tmp->rotate);
+ printf(" steps: ");
+ advance_node tmp_ad = tmp->advances;
+ while (tmp_ad != NULL) {
+ printf("%d->%p ", tmp_ad->steps, tmp_ad->leads_to);
+ tmp_ad = tmp_ad->next;
+ }
+ printf("\n");
+ tmp = tmp->next;
+ }
+ return 0;
+}
+
+// radix addition
+// returns a new chain
+link radix_increment(link target, int base) {
+ link new = chain_cpy(target);
+ link marker = new;
+ while (marker != NULL) {
+ if (marker->value < (base - 1)) {
+ marker->value++;
+ return new;
+ }
+ marker->value = 0;
+ marker = marker->next;
+ }
+ return NULL; // not big enough
+};
+
+// given n (number of links in chain), return list of possible advances
+advance_node n_advances(int n) {
+ n--;
+ advance_node marker = new_advance_node(n, NULL, NULL);
+ while (n > 1) {
+ n--;
+ advance_node new_node = new_advance_node(n, marker, NULL);
+ marker = new_node;
+ }
+ return marker;
+}
+
+// given the number of links, create a list of all the chain permutations with
+// that many links
+state generate_perms(int n) {
+ //printf(" generating possible chains:\n");
+ // list of the first n primes
+ prime primes = first_n_primes(n);
+ // base signature
+ int base_sig = base_signature(primes);
+ //printf(" base signature: %d\n", base_sig);
+ // empty chain list
+ state states = new_state(NULL, NULL);
+ states->advances = n_advances(n);
+ // first one is lowest possible number with all linksn_
+ link lowest = new_chain(n);
+ link cur = lowest;
+ int c = n;
+ // fill in the first links
+ // i.e. 0 1 2 3
+ while (cur != NULL) {
+ c--;
+ cur->value = c;
+ cur = cur->next;
+ }
+ //printf(" lowest: ");
+ // print_chain(lowest);
+ //printf("\n");
+ // highest possible is reverse of lowest
+ int k = 0;
+ link highest = new_chain(n);
+ cur = highest;
+ while (cur != NULL) {
+ cur->value = k;
+ cur = cur->next;
+ k++;
+ }
+ //printf(" highest: ");
+ // print_chain(highest);
+ //printf("\n");
+ states->board = lowest; // first link in chain
+ state tmp_state = states; // generic marker version
+ link poss = chain_cpy(tmp_state->board);
+ //printf(" trying: (*success)\n");
+ while (!chains_equal(tmp_state->board, highest)) {
+ poss = radix_increment(poss, n);
+ //printf(" ");
+ //print_chain(poss);
+ if (no_dupes(poss, base_sig, primes)) {
+ state add_state = new_state(chain_cpy(poss), NULL);
+ add_state->advances = n_advances(n);
+ tmp_state->next = add_state;
+ tmp_state = add_state;
+ //printf("*");
+ }
+ //printf("\n");
+ }
+ return states;
+}
+
+// given a list of states and a board, find the state with the board
+state board_search(link query, state states) {
+ state marker = states;
+ while (marker != NULL) {
+ if (chains_equal(query, marker->board)) {
+ return marker;
+ }
+ marker = marker->next;
+ }
+ return NULL;
+}
+
+// given a state, pair it with it's rotated state
+int link_rotations(state this_state, state states, int diameter) {
+ if (this_state->rotate != NULL) {
+ return 0;
+ }
+ link board = spin(chain_cpy(this_state->board), diameter);
+ state mate = board_search(board, states);
+ if (mate) {
+ this_state->rotate = mate;
+ mate->rotate = this_state;
+ return 1;
+ }
+ return 0;
+}
+
+// given a state and a step, pair it with it's complementary step
+int link_steps(state this_state, state states, advance_node adv, int n) {
+ if (adv->leads_to != NULL) {
+ return 0;
+ }
+ link board = advance(chain_cpy(this_state->board), adv->steps);
+ state mate = board_search(board, states);
+ if (mate) {
+ adv->leads_to = mate;
+ int i = n - adv->steps;
+ advance_node tmp_adv = mate->advances;
+ while (tmp_adv->steps != i) {
+ tmp_adv = tmp_adv->next;
+ }
+ tmp_adv->leads_to = this_state;
+ return 1;
+ }
+ return 0;
+}
+
+// given a number of links and the wheel diameter,
+// create the list of permutations and link them
+state build_universe(int n, int d) {
+ state states = generate_perms(n);
+ state st_marker = states;
+ while (st_marker != NULL) {
+ link_rotations(st_marker, states, d);
+ advance_node adv_marker = st_marker->advances;
+ while (adv_marker->next != NULL) {
+ link_steps(st_marker, states, adv_marker, n);
+ adv_marker = adv_marker->next;
+ }
+ st_marker = st_marker->next;
+ }
+ return states;
+}
+
+// print board in dot-friend format
+int print_board_dot(link board) {
+ printf("\"");
+ print_chain(board);
+ printf("\"");
+ return 1;
+}
+
+// print states in dot format
+int print_states_dot(state states, int n) {
+ printf("graph T {\n");
+ state st_marker = states;
+ while (st_marker != NULL) {
+/***
+* if p1 < p2
+* prevents duplicates
+* (Jim's idea)
+***/
+ // print rotate relationship
+ if (st_marker < st_marker->rotate) {
+ print_board_dot(st_marker->board);
+ printf(" -- ");
+ print_board_dot(st_marker->rotate->board);
+ printf(" [color=red];\n");
+ }
+ // print each advance relationship
+ advance_node ad_marker = st_marker->advances;
+ while (ad_marker != NULL) {
+ if (st_marker < ad_marker->leads_to) {
+ print_board_dot(st_marker->board);
+ printf(" -- ");
+ print_board_dot(ad_marker->leads_to->board);
+ printf(" [color=blue];\n");
+ }
+ ad_marker = ad_marker->next;
+ }
+ st_marker = st_marker->next;
+ }
+ printf("}\n");
+ return 0;
+}
+
+
+int test_utils() {
+ printf("***general utility tests\n");
+ prime test_prime = first_n_primes(3);
+ print_primes(test_prime);
+ int base = base_signature(test_prime);
+ printf(" base signature: %d\n", base);
+ link test_chain = new_chain(3);
+ test_chain->value = 0;
+ test_chain->next->value = 1;
+ test_chain->next->next->value = 2;
+ printf(" chain: ");
+ print_chain(test_chain);
+ printf("\n");
+ printf(" chain signature: %d\n", gen_sig(test_chain, test_prime));
+ printf(" no dupes? (expect 1): %d\n", no_dupes(test_chain, base, test_prime));
+ link test_chain2 = advance(test_chain, 2);
+ printf(" advance chain 2: ");
+ print_chain(test_chain2);
+ printf("\n");
+ link test_chain3 = spin(test_chain2, 2);
+ printf(" spin chain 2: ");
+ print_chain(test_chain3);
+ printf("\n");
+ test_chain3 = radix_increment(test_chain3, 3);
+ printf(" add 1 radix 3: ");
+ print_chain(test_chain3);
+ printf("\n");
+ test_chain3 = radix_increment(test_chain3, 3);
+ printf(" add 1 radix 3: ");
+ print_chain(test_chain3);
+ printf("\n");
+ test_chain3 = radix_increment(test_chain3, 3);
+ printf(" add 1 radix 3: ");
+ print_chain(test_chain3);
+ printf("\n");
+ test_chain3 = radix_increment(test_chain3, 3);
+ printf(" add 1 radix 3: ");
+ print_chain(test_chain3);
+ printf("\n");
+ ////////////////////////////////
+ printf("***make the universe, pair some states\n");
+ state test_state = generate_perms(3);
+ link_rotations(test_state, test_state, 2);
+ link_steps(test_state->next, test_state, test_state->next->advances->next, 3);
+ print_states(test_state);
+ ///////////////////////////////
+ printf("***make the universe, fill all states\n");
+ print_states(build_universe(3, 2));
+ printf("***output for dot\n");
+ print_states_dot(build_universe(3, 2),3);
+ return 0;
+}
+
diff --git a/utils.h b/utils.h
@@ -0,0 +1,48 @@
+/**
+* utils.h : "header" (i.e. API interface) for utils.c code.
+*
+* adapted from http://cs/courses/fall2008/algorithms/code/c_examples/multiple_files/some_func.h
+**/
+
+#include "primes.h"
+#include "perm_gen.h"
+
+// c seems to want all the definitions, so here they are agian
+// DEFINTIONS
+// type definitions used later
+typedef struct advance_node_type *advance_node;
+typedef struct state_type *state;
+
+// since the number of times you can advance the tiles is variable,
+// links to the states that result from those changes will go into an
+// array
+struct advance_node_type {
+ int steps; // how far to advance
+ state leads_to; // what state you enter after making that move
+ advance_node next;
+};
+
+//
+struct state_type {
+ link board;
+ state next;
+ state rotate;
+ advance_node advances;
+};
+
+/***
+*
+* API
+*
+***/
+
+// build_universe
+// generates the "universe" of a game of twistturns
+// (each of the possible board states, and the links between them)
+// usage: state built_universe(the number of tiles in the game, the diameter of the wheel);
+state build_universe(int n, int d);
+
+// print_states_dot
+// prints out the relationships between each state in a universe in dot format
+// usage: print_states_dot(universe);
+int print_states_dot(state states);
