Hal W Canary 3

A program for obscure mathematics...

This IS the pinnacle of my career.

By the way, you can use this code in accordance with the GNU GPL license.

hexagon.cpp
/* 
   (c) 2001-2003 Hal Canary, University of Wisconsin-Madison

   Licence Information:

	This program is free software; you can redistribute it and/or
	modify it under the terms of version 2 of the GNU General
	Public License as published by the Free Software Foundation.

	A copy of the licence can be found at:
			http://www.gnu.org/licenses/gpl.txt

	This program is distributed in the hope that it will be
	useful, but WITHOUT ANY WARRANTY; without even the implied
	warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
	PURPOSE.  See the GNU General Public License for more details.

   How do I compile this?
   $ g++ -o hexagon hexagon.cpp
   
   What do the terminal matchings mean?
        1   2            
        |   |                             
   12   |   |   3              1   2		  
     \ / \ / \ /  	     o---o---o    
      |   |   |   	 12 / \ / \ / \ 3  
 11   |   |   |   4	   o---o---o---o  
   \ / \ / \ / \ /	11/ \ / \ / \ / \ 4
    |   |   |   | 	 o---o---o---o---o
    |   |   |   |      10 \ / \ / \ / \ / 5
   / \ / \ / \ / \	   o---o---o---o  
 10   |   |   |   5	 9  \ / \ / \ / 6  
      |   |   |   	     o---o---o    
     / \ / \ / \  	       8   7	  
    9   |   |   6  	 		  
        |   |     	 		  
        8   7         	 		                        
*/

#include <iostream>
#include <stdlib.h>

using namespace std;

/**
 * hexagon class.  
 * can print out all lozenge tilings of a particular size regular hexagon.
 * can print all of the dpfl terminal matchings.
 * Hal Canary, April 2001.
 **/

const int MAXSIZE = 50;

/**
 * class for a hexagon/GelfandSquare
 **/
class Hexagon {
public:
    /** 
     * constructor: makes the smallest gelfand square.
     **/
    Hexagon(int sizein);

    /**
     * default constructor:  sets size to 1.
     **/
    Hexagon();

    /**
     * changes the gelfand square.
     **/
    int iterate();

    /**
     * constructs two matrices that represent the matching/tiling.
     **/
    int makeBW();
    
    /**
     * prints out the tiling (assumes you've run makeBW).
     **/
    int printBW(ostream& o);

    /**
     * prints out the gelfand square.
     **/
    int printGS(ostream& o);

    /**
     * prints out all of the dpfl terminal matchings.
     * Assumes you've run makeBW.
     **/
    int printMatchings(ostream& o);

private:
    //fields:
    int size;                             // size of the regular hexagon.
    int gelfand [MAXSIZE+1] [MAXSIZE+1] ; // GelfandSquare
    char black [2*MAXSIZE][2*MAXSIZE] ;   // black triangles
    char white [2*MAXSIZE][2*MAXSIZE] ;   // white triangles

    //functions:

    /**
     * Recursive Iteration function.
     * parameters: current position in GS.
     * returns 1 if we are done iterating, else 0
     **/
    int iterateR(int row, int col);       

    /**
     * matching function.
     * returns the terminal that matches the starting Terminal.
     **/
    int match(int startTerminal);       

    /**
     * Recursive flux Move function.
     * returns termianl on which the dpf line ends.
     **/
    int rmove(char type, int row, int col, char dir);

    /**
     * returns 0 if not a terminal.  
     * otherwise returns terminal number.
     **/
    int amterm(char type, int row, int col);
};

Hexagon::Hexagon(int sizein) { 
    size = sizein;
    if (size > MAXSIZE) {
	size = MAXSIZE;
    }
    gelfand[0][0] = 0;
    for (int j=1; j < size+1; j++) { 
	gelfand[0][j] = (2 * size) + 1;
    }
    for (int i=1; i < size+1; i++) {
	for (int j=0; j < size+1; j++) {
	    gelfand[i][j] = size-i+1;
	}
    }
}
Hexagon::Hexagon() { 
    size = 1;
    gelfand[0][0] = 0;
    for (int j=1; j < size+1; j++) { 
	gelfand[0][j] = (2 * size) + 1;
    }
    for (int i=1; i < size+1; i++) {
	for (int j=0; j < size+1; j++) {
	    gelfand[i][j] = size-i+1;
	}
    }
}

int Hexagon::iterate() { 
    return iterateR(size, size);
}

int Hexagon::iterateR(int row, int col) {
    if (gelfand[row][col] < gelfand[row-1][col]-1 ) {
	gelfand[row][col]++;
	return 0;
    } 
    else {
	if (col > 1) {
	    if (iterateR(row, col-1) == 1) 
		return 1 ;
	    else { 
		gelfand[row][col] = gelfand[row][col-1];
		return 0;
	    }
	}
	else if (row > 1) {
	    if (iterateR(row-1, size) == 1) 
		return 1 ;
	    else { 
		gelfand[row][col] = gelfand[row][col-1];
		return 0;
	    }
	}
	else if (row == 1 && col == 1) 
	    return 1;
	else
	    return 40;
    }
}

int Hexagon::printGS(ostream& o) {
    for (int i=0; i < size+1; i++) {
	for (int j=0; j < size+1; j++) {
	    o << gelfand[i][j] << '\t' ;
	}
	o << endl;
    }
}

int Hexagon::makeBW() { 
    //black is either r, l, d, or ' '
    //white is either r, l, u, or ' '
    //start the empty bleg.
    for (int i=0; i < 2*size; i++) {
	for (int j=0; j < 2* size; j++) {
	    black[i][j] = '_' ;
	    white[i][j] = '_' ;
	}
    }   

    for (int i=0; i < size; i++) {
	for (int j=0; j < size-1-i; j++) {
	    black[i][j] = ' ' ;
	    white[2*size-i-1][2*size-j-1] = ' ' ;
	}
    }
    for (int i=size; i < 2*size; i++) {
	for (int j=3*size-i-1 ; j < 2*size; j++) {
	    black[i][j] = ' ' ;
	    white[2*size-i-1][2*size-j-1] = ' ' ;
	}
    }
    //insert the up-down tiles...
    for (int i=1; i < size+1; i++) {
	for (int j=1; j < size+1; j++) {
	    int rowblack = i+j-2;
	    int rowwhite = i+j-1;
	    int col = gelfand[i][j] -1 ;
	    white[rowwhite][col] = 'V';
	    black[rowblack][col] = 'A';
	}
    }

    //insert the left-right tiles...
    for (int i=0; i < size; i++) {
	if (black[i][size-i-1] != 'A') {
	    black[i][size-i-1] = '<';
	}
    }
    for (int i=0; i < size; i++) {
	for (int j=size-i; j< 2*size; j++) {
	    if (white[i][j] == 'V' ) {
		if (black[i][j] != 'A' ) {
		    black[i][j] = '<' ;
		}
	    }
	    else if (black[i][j-1] == '<') {
		white[i][j] = '>' ;
		if (black[i][j] != 'A') {
		    black[i][j] = '<';
		}
	    }
	    else {
		white[i][j] = '<';
		black[i][j] = '>';
	    }
	}
    }

    for (int i=size; i < 2*size; i++) {
	if (white[i][0] != 'V') {
	    white[i][0] = '<';
	}
    }
    for (int i=size; i < 2*size; i++) {
	for (int j=0; j< 3*size-i-1; j++) {
	    if (black[i][j]== 'A') {
		if (white[i][j+1] != 'V') {
		    white[i][j+1] = '<' ;
		}
	    }
	    else if (white[i][j]== '<') {
		black[i][j] = '>';
		if (white[i][j+1] != 'V') {
		    white[i][j+1] = '<' ;
		}
	    }
	    else {
		black[i][j] = '<';
		white[i][j+1] = '>';
	    }
	}
    }    
    return 0;
}    

int Hexagon::printBW(ostream& o) { 
    for (int i=0; i < 2*size; i++) {
	for (int j=0; j < i; j++) {
	    o << ' ' ;
	}
	for (int j=0; j < 2* size; j++) {
	    if (i>=size && white[i][j]==' '){
		j = 2*size;
	    }
	    else {
		o << white[i][j] ;
		o << black[i][j] ;
	    }
	}
	o << endl;
    }   
    return 0;
}

int Hexagon::printMatchings(ostream& o) {
    for (int i=1 ; i <= 6 * size ; i=i+2) {
	o << i << ':' << match(i) <<  ' ' ;
    }
    o << endl;
    return 0;
}

int Hexagon::match(int go) {
    if      (go > 0      && go <=   size) { 
	return rmove('w', 0, go+size-1, 'd');
    }
    else if (go > size   && go <= 2*size) { 
	return rmove('b', go-size-1, 2*size-1, 'l');
    }
    else if (go > 2*size && go <= 3*size) {  
	return rmove('w', go-1-size, 4*size-go, 'l');
    }
    else if (go > 3*size && go <= 4*size) {  
	return rmove('b', 2*size-1, 4*size-go, 'u');
    }
    else if (go > 4*size && go <= 5*size) {  
	return rmove('w', 6*size - go, 0, 'r');
    }
    else if (go > 5*size && go <= 6*size) {  
	return rmove('b', 6*size-go, go-5*size-1, 'r');
    }
    else {
	return 7000;
    }
}

int Hexagon::rmove(char type, int row, int col, char dir) { 
    //decide next tile/node.
    char newdir;
    int newrow;
    int newcol;
    char newtype;
    if (type == 'b') {
	char match = black[row][col];
	newtype = 'w';
	if      (match == 'A' && dir == 'l') {  newdir = 'l'; }
	else if (match == 'A' && dir == 'r') {  newdir = 'r'; }
	else if (match == '<' && dir == 'u') {  newdir = 'l'; }
	else if (match == '<' && dir == 'r') {  newdir = 'd'; }
	else if (match == '>' && dir == 'u') {  newdir = 'r'; }
	else if (match == '>' && dir == 'l') {  newdir = 'd'; }
	else return 666;
	if      (newdir == 'd') { newcol = col;   newrow = row+1; }
	else if (newdir == 'r') { newcol = col+1; newrow = row;   }
	else if (newdir == 'l') { newcol = col;   newrow = row;   }
    }
    else if (type == 'w') {
	char match = white[row][col];
	newtype = 'b';
	if      (match == 'V' && dir == 'l') { newdir = 'l'; }
	else if (match == 'V' && dir == 'r') { newdir = 'r'; }
	else if (match == '<' && dir == 'd') { newdir = 'l'; }
	else if (match == '<' && dir == 'r') { newdir = 'u'; }
	else if (match == '>' && dir == 'd') { newdir = 'r'; }
	else if (match == '>' && dir == 'l') { newdir = 'u'; }
	else { return 20000; }
	if (newdir == 'l') { newcol = col-1; newrow = row;   }
	if (newdir == 'u') { newcol = col;   newrow = row-1; }
	if (newdir == 'r') { newcol = col;   newrow = row;   }
    }
    //if that next tile==terminal, return terminal.
    int x = amterm(newtype, newrow, newcol);
    if (x != 0) {
	return x;
    }
    //else return rmove of next tile...
    else {
	return rmove(newtype, newrow, newcol, newdir) ;
    }
}

int Hexagon::amterm(char type, int row, int col) { 
    if (type == 'b') {
	if (row == 2*size-1) {
	    return (4*size)-col ;
	}
	else if (col == 2*size-1) {
	    return size+1+row;
	} 
	else if (col+row == size-1) {
	    return 5*size+col+1;
	}
	else { 
	    return 0;
	}
    }
    else if (type == 'w') {
	if (row == 0) {
	    return  (col -size +1) ;
	}
	else if (col == 0) {
	    return (6*size-row);
	} 
	else if (col+row == (3*size)-1) {
	    return (row+size+1);
	}
	else { 
	    return 0;
	}
    }
    else {
	return 0;
    }
}
 
int main(int argc, char *argv[]) {
    int size = 0;
    if (argc == 1) {
	cerr << "How big do you want your hexagon?\n"
	     << "Usage: hexagon size [options]\n" 
	     << "``size'' is the size of the hexagon \n"
	     << "\tOptions:\n"
	     << "\tg = print Gelfand Square\n" 
	     << "\th = print Hexagon\n"
	     << "\tc = count tilings\n"
	     << "\tm = do not print matchings\n"   
	     << "example:  ./hexagon 2 hc \n";
	return 1;
    }
    else {
	if (size = abs(atoi(argv[1])) ) {
	    if ( size > MAXSIZE ) {
		size = MAXSIZE ;
	    }
	}
	else {
	    cerr << "Usage: gelfand size [options]" << endl
		 << "and ``size'' is an positive integer less than " 
		 << MAXSIZE << "."<< endl;
	    return 1;
	}
    }
    int printGSon = 0;
    int printBWon = 0;
    int counton = 0;
    int printMatchings = 1;
    if (argc >= 3) {
	for(int i = 0; argv[2][i] != '\0' ; i++) {
	    if (argv[2][i] == 'g') 
		printGSon = 1;
	    if (argv[2][i] == 'h')
		printBWon = 1;
	    if (argv[2][i] == 'c')
		counton = 1;
	    if (argv[2][i] == 'm')
		printMatchings = 0;
	}
    }
    
    Hexagon hex(size);
    long count = 1;
    long count2 = 0;

    if (printGSon ==1) {
	hex.printGS(cout);
	cout << endl;
    }
    if (printBWon == 1 || printMatchings == 1)
	hex.makeBW();
    if (printBWon == 1)
	hex.printBW(cout);
    if (printMatchings == 1)
	hex.printMatchings(cout);
    if (printBWon == 1) 
	cout << endl;

    while (hex.iterate() == 0) {
	if (counton == 1){
	    if (count == 1999999999) {
		count = 0;
		count2++;
	    }
	    else {
		count++;
	    }
	}
	if (printGSon ==1) {
	    hex.printGS(cout);
	    cout << endl;
	}
	if (printBWon == 1 || printMatchings == 1)
	    hex.makeBW();
	if (printBWon == 1) 
	    hex.printBW(cout);
	if (printMatchings == 1)
	    hex.printMatchings(cout);
	if (printBWon == 1) 
	    cout << endl;
    }
    if (counton == 1) {
	if (count2==0) 
	    cout << "Total number of tilings = " << count << endl;
	else 
	    cout << 2*count2 << "000000000 + " << count << endl;
    }
    return 0; 
}

file modification time: 2003-12-08 05:33:47

Copyright 1997-2013 by Hal Canary.
mailto: halcanary at gmail dot com
http://halcanary.org