Pathfinder

June 30th, 2013 by Robbie

minimal-treeFinished CS106B, just in time to begin “Start Up Engineering” on Coursera. I had alot of trouble finishing this final exercise, because it was the last one, and my attention had already moved on somewhat. I’m definitely going to have to start using this stuff for real now. I’ve done more than enough exercises. This isn’t the whole thing but I’ve got a Github account now and will put the whole course up on there asap…

Here’s the main cpp;

/**
 * File: pathfinder.cpp
 * --------------------
 * This is the primary file where you'll place most of your code.
 */

#include <cmath>
#include <fstream>
#include <iostream>
#include <string>
#include "console.h"
#include "pathfinder-graph.h"
#include "pathfinder-graphics.h"
#include "pqueue-heap.h"
#include "error.h"
#include "gwindow.h"
#include <map>
#include "pqueue.h"
#include "point.h"
#include "tokenscanner.h"
#include "set.h"
#include "simpio.h"
#include "strlib.h"
#include "vector.h"
#include "path.h"
#include "lexicon.h"

using namespace std;

/**
 * Function: giveInstructions
 * Usage: giveInstructions();
 * --------------------------
 * Describes the Pathfinder assignment on the console.  This text has
 * been retained in its original form to preserve the assignment history.
 */
static void giveInstructions();
/**
 * Function: quitAction
 * Usage: quitAction(g);
 * ---------------------
 * Called when the user clicks the Quit button in the control strip.
 */

static Node *findNode(const GPoint &pt, PathfinderGraph *&graph);
static bool responseIsAffirmative(const string& prompt);
static void quitAction();
static void runDijkstra(PathfinderGraph *&graph);
static void kruskalAction(PathfinderGraph *&graph);
static void dijkstraAction();
static void mapAction(PathfinderGraph *&graph);
static void clickAction(const GPoint &pt, PathfinderGraph *&graph);
static void loadMap(PathfinderGraph *graph, string datafile);
static Vector<Set< Node *> > processArcs(Vector<Set< Node *> > MST, Arc *out);


/**
 * Function: main
 * --------------
 * Defines the entry point for the entire application.
 */
int main() {
    GWindow gw(kWindowWidth, kWindowHeight + kControlStripHeight);
    initPathfinderGraphics(gw);
    giveInstructions();
    
    PathfinderGraph *graph = new PathfinderGraph;
    string datafile = "USA";
    loadMap(graph, datafile);
    
    addButton("Map", mapAction, graph);
    addButton("Dijkstra", dijkstraAction);
    addButton("Kruskal", kruskalAction, graph);
    addButton("Quit", quitAction);
    
    defineClickListener(clickAction, graph);
    
    pathfinderEventLoop();
    
    return 0;
}

static void giveInstructions() {
    cout << "This masterful piece of work is a graph extravaganza!" << endl;
    cout << "The main attractions include a lovely visual presentation" << endl;
    cout << "of the graph along with an implementation of Dijkstra's" << endl;
    cout << "shortest path algorithm and Kruskal's computation of" << endl;
    cout << "a minimal spanning tree.  Enjoy!" << endl << endl;
}

        
static void loadMap(PathfinderGraph *graph, string datafile) {
    int result = graph->setMapFile(datafile);
    if (result == -1) {
        cout << "That file doesn't want to load, or doesn't exist." << endl;
        cout << "Make sure you don't use file extensions, just the name of the file." << endl;
        if (responseIsAffirmative("Do you want to try again?")) {
            mapAction(graph);
        }
    }
    
    string map = graph->getMapFile();
    drawPathfinderMap(map);
    Set<Node *> mapnodes = graph->getNodes();
    foreach (Node *next in mapnodes) {
        drawPathfinderNode(next->loc, "Black", next->name);
    }
    Set<Arc *> maparcs = graph->getArcs();
    foreach (Arc *route in maparcs) {
        drawPathfinderArc(route->start->loc, route->finish->loc, "Black");
    }
}

static bool responseIsAffirmative(const string& prompt) {
    while (true) {
        string answer = getLine(prompt);
        if (!answer.empty()) {
            switch (toupper(answer[0])) {
                case 'Y': return true;
                case 'N': return false;
            }
        }
        cout << "Please answer yes or no." << endl;
    }
}

static void clickAction(const GPoint &pt, PathfinderGraph *&graph) {
    Node *found = findNode(pt, graph);
    if (found->name != "VOID") {
        drawPathfinderNode(found->loc, "Red");
        graph->setHighlightedNode(found);
        if (graph->checkNodes()) {
            runDijkstra(graph);
        }
    }
}



static void quitAction() {
    exitGraphics();
}

static void kruskalAction(PathfinderGraph *&graph) {
    
    drawPathfinderMap(graph->getMapFile());// reboot mapfile
    
    Set<Node *> cities = graph->getNodes();
    Vector<Arc *> routes = graph->getKruskalArcs();// get arcs without return trips
    graph->clearArcs();
    
    foreach(Node *edge in cities) {
        edge->arcs.clear();
    }
    
    HeapPQueue<Arc *> *pq = new HeapPQueue<Arc *>;
    
    for (int i = 0; i < routes.size(); i++) {// pull all of the arcs off, enqueue
        pq->enqueue(routes[i], arcCmp);// with arcCmp comparitor from cmfn header
    }
    
    Vector<Set< Node *> > MST;// Vector of sets with one node per set is initial minimal spanning tree
    
    foreach(Node *city in cities) {//populate vector mst
        Set<Node *> zone;
        zone.add(city);
        MST.add(zone);
    }
    
    while (pq->size() != 0) {// whilst there are more arcs in the pqueue, update mst by processing the arcs
        Arc *out = pq->extractMin(arcCmp);
        MST = processArcs(MST, out);
    }
    
    delete pq;
}

static void dijkstraAction() {
    
    cout << "Click on starting and finishing location to cue Dijkstra..." << endl;
    
    
}
            
static Vector<Set< Node *> > processArcs(Vector<Set< Node *> > MST, Arc *out) {
    Vector<Set< Node *> > testMST = MST;// new test mst is only returned if kruskal algorithm is satisfied and adding the arc involves joining 2 sets
    
    Arc *back = new Arc;// create new return trip arc for each arc in the pqueue
    back->start = out->finish;
    back->finish = out->start;
    back->cost = out->cost;
    string distance = realToString(out->cost);
    int One;// initialise ints for positions on the MST vector
    int Two;
    for (int i = 0; i < testMST.size(); i++) {
        if (testMST[i].contains(out->start)) {
            Set< Node *> part1 = testMST[i];// pull set from vector if it contains node from start of arc
            foreach(Node *start in part1) {
                if (start->name == out->start->name) {
                    start->arcs.add(out);// add outgoing arc to ercs
                    One = i;// One int is updated as position in for loop
                }
            }
    }
        if (testMST[i].contains(back->start)) {
            Set< Node *> part2 = testMST[i];// pull set if it contains node from finish
            foreach(Node *finish in part2) {
                if (finish->name == back->start->name) {
                    finish->arcs.add(back);
                    Two = i;// Two int is updated
                }
            }
        }
    }
    Set<Node *> newset = testMST[One];
    if (One != Two) {// If one and two are different, combine and return the new tree
        newset = testMST[One] += testMST[Two];
        testMST[One] = newset;
        testMST.remove(Two);
        cout << distance + ": " + out->start->name + " - " + out->finish->name << endl;
        drawPathfinderNode(out->start->loc, "Red", out->start->name);// Update the console and map etc...
        drawPathfinderNode(out->finish->loc, "Red", out->finish->name);
        drawPathfinderArc(out->start->loc, out->finish->loc, "Red");
        return testMST;
    }
    else {
        cout << distance + ": " + out->start->name + " - " + out->finish->name + "(not needed)" << endl;
        return MST;// Or return the old tree
    }
}

static void mapAction(PathfinderGraph *&graph) {
    cout<< "Please enter the name of the graph data file (without extension): ";
    string mapname = getLine();
    loadMap(graph, mapname);
}

static Node *findNode(const GPoint &pt, PathfinderGraph *&graph) {
    Node *result = new Node;
    result->name = "VOID";
    double x = pt.getX();
    double y = pt.getY();
    Set<Node *> graphnodes = graph->getNodes();
    foreach (Node *next in graphnodes) {
        GPoint nodeloc = next->loc;
        double compx = nodeloc.getX();
        double compy = nodeloc.getY();
        if (x < compx + 8 && x > compx - 8) {
            if (y < compy + 8 && y > compy - 8) {
                result = next;
            }
        }
    }
    return result;
}

static void runDijkstra(PathfinderGraph *&graph) {
    Vector<Node *> selection = graph->getSelected();// Pulls vector of 2 selected nodes
    Node *start = selection[0];
    Node *destination = selection[1];
    string dname = destination->name;
    start->dist = 0;// distance from start is zero
    
    Set<Node *> fixednodes;
    
    HeapPQueue<Path> *paths = new HeapPQueue<Path>;// instantiate path pqueue
    Path startpath;
    startpath.pathcost = 0;// start path distance is zero
    startpath.addNode(start);
    paths->enqueue(startpath, pathCmp);// enqueue with pathCmp comparator (in cmpfn.h header)
    
    Path result;
        while (true) {
        
            Path newpath = paths->extractMin(pathCmp);
            string pathstring = newpath.getRoute();
            cout << "Dequeue the shortest path: " + pathstring << endl;
            Node *next = newpath.getNode();
            string query = next->name;
            if (query == dname) {
                result = newpath;
                break;
            }
            Set<Arc *> startarcs = next->arcs;
           
            fixednodes.add(next);
            double routedist = newpath.pathcost;
            string dist = realToString(routedist);
            cout << "Fix the distance to " + next->name + " at " + dist << endl;
            cout << "Process the arcs out of " + next->name + " (" + newpath.getNextArcs() << endl;
                foreach(Arc *arc in startarcs) {
                    Node *dest = arc->finish;
                    Path nextpath = newpath;
                    if (!fixednodes.contains(dest)) {
                        nextpath.addArc(arc);
                        nextpath.addNode(dest);
                        string pathstring = nextpath.getRoute();
                        cout << "Enqueue the path: " + pathstring << endl;
                        paths->enqueue(nextpath, pathCmp);
                    }
                    else if (fixednodes.contains(dest)) {
                        cout << "   Ignore " + dest->name + " because it's distance is fixed." << endl;
                    }
                    result = newpath;
        }
    }
    delete paths;
    
    Vector<Arc *> resultarcs = result.getArcPath();
    Vector<Node *> resultnodes = result.getNodePath();
    Set<Arc *> maparcs = graph->getArcs();
    Set<Node *> mapnodes = graph->getNodes();
    foreach (Node *next in mapnodes) {
            drawPathfinderNode(next->loc, "Gray", next->name);
    }
    foreach (Arc *route in maparcs) {
            drawPathfinderArc(route->start->loc, route->finish->loc, "Gray");
        
    }
    for (int i = 0; i < resultarcs.size(); i++) {
        Arc *paint = resultarcs[i];
        drawPathfinderArc(paint->start->loc, paint->finish->loc, "Red");
    }
    for (int n = 0; n < resultnodes.size(); n++) {
        Node *draw = resultnodes[n];
        drawPathfinderNode(draw->loc, "Red");
    }

}

Path Header;

/*
 * File: path.h
 * ------------
 * This file is the interface for a Path class, which consists of a
 * sequence of arcs.
 */

#ifndef _path_h
#define _path_h

#include "vector.h"
#include "set.h"
#include "graphtypes.h"

class Path {

public:

    void addNode(Node *newnode);
	void addArc(Arc *newone);
	int pathcost;
    Node *getNode();
    std::string getRoute();
    std::string getNextArcs();
    Vector<Node *> getNodePath();
    Vector<Arc *> getArcPath();

private:
    Vector<Node *> pathofnodes;
    Vector<Arc *> pathofarcs;

};

#endif

Path cpp;

/**
 * File: path.cpp
 * --------------
 * This file implements the Path class.
 */

#include "path.h"
#include "strlib.h"

void Path::addArc(Arc *newone) {
        pathcost += newone->cost;
        pathofarcs.add(newone);
}

void Path::addNode(Node *newnode) {
        newnode->dist = pathcost;
        pathofnodes.add(newnode);
}

Node *Path::getNode() {
    Node *result = pathofnodes[pathofnodes.size() -1];
    return result;
}

std::string Path::getRoute() {
    string result = "";
    for (int i = 0; i < pathofnodes.size(); i++) {
        Node *next = pathofnodes[i];
        string nodename = next->name;
        if (i < pathofnodes.size() - 1) {
            result = result + " " + nodename + " ->";
        }
        else if (i == pathofnodes.size() - 1) {
            string coststring = integerToString(pathcost);
            result = result + " " + nodename + " (" + coststring + ")";
        }
    }
    return result;
}

std::string Path::getNextArcs() {
    string result = "";
    Node *last = pathofnodes[pathofnodes.size() -1];
    Set<Arc *> nextarcs = last->arcs;
    foreach(Arc* next in nextarcs) {
        Node *place = next->finish;
        string add = place->name;
        result = result + add + ", ";
    }
    result[result.size() - 1] = ')';
    return result;
}

Vector<Node *> Path::getNodePath() {
    return pathofnodes;
}
Vector<Arc *> Path::getArcPath() {
    return pathofarcs;
}

Graph header;

#ifndef _pathfinder_graph_
#define _pathfinder_graph_

#include <string>

#include "graphtypes.h" // for struct Node

class PathfinderGraph {

public:
    int setMapFile(const std::string& filename);
    const std::string& getMapFile() const;
    void setHighlightedNode(Node *node);
    Node *getHighlightedNode() const;
    bool checkNodes();
    Set<Node *> getNodes();
    Set<Arc *> getArcs();
    Vector<Node *> getSelected();
    void clearArcs();
    Vector<Arc *> getKruskalArcs();

private:
    std::string mapFile;
    Node *highlightedNode;
    int loadDataFile(const string& filename);
    SimpleGraph dataFile;
    Vector<Arc *> kruskalarcs;
    Vector<Node *> selected;
    static const double INFIN_VAL = 1000000;
};

#endif

Graph cpp;

/**
 * File: pathfinder-graph.cpp
 * --------------------------
 * Provides the (fairly obvious) implementation of
 * the PathfinderGraph class.
 */

#include "pathfinder-graph.h"
#include "tokenscanner.h"
#include "strlib.h"
#include "simpio.h"

using namespace std;

int PathfinderGraph::setMapFile(const string& filename) {
    mapFile = "images/" + filename + ".jpg";
    highlightedNode = NULL;
    int result = loadDataFile(filename);
    return result;
}

const string& PathfinderGraph::getMapFile() const {
    return mapFile;
}

void PathfinderGraph::setHighlightedNode(Node *node) {
    if (selected.size() >= 2) {
        selected.clear();
    }
    selected.add(node);
    highlightedNode = node;
}

Node *PathfinderGraph::getHighlightedNode() const {
    return highlightedNode;
}

bool PathfinderGraph::checkNodes() {
    if (selected.size() == 2) {
        return true;
    }
    return false;
}

int PathfinderGraph::loadDataFile(const string& filename) {
    dataFile.nodeMap.clear();
    dataFile.nodes.clear();
    dataFile.arcs.clear();
    kruskalarcs.clear();

    map<string, Node *>::iterator iter;
    ifstream inp;
    string datafile = "data-files/" + filename + ".txt";
    inp.open(datafile.c_str());
        if (inp.is_open() == true) {
            if (inp.fail()) { error("Could not open file");
                inp.clear();
                return -1;
            }
    }
    string row;
    Vector<string> filereadout;
    while (getline(inp, row)) {
        filereadout.add(row);
    }
    inp.close();

    filereadout.remove(0);
    filereadout.remove(0);
    TokenScanner scanner;
    scanner.ignoreWhitespace();

    while (true) {
        string line = filereadout[0];
        if (line == "ARCS") break;
        Node *newnode = new Node;
        double x;
        double y;
        scanner.setInput(line);
        string nodename;
            for (int i = 0; i < 3; i++) {
                string next = scanner.nextToken();
                if (i == 0) {

                    newnode->name = next;
                    nodename = next;
                    newnode->dist = INFIN_VAL;
                }
                else if (i == 1) {

                    x = stringToReal(next);
                }
                else if (i == 2) {

                    y = stringToReal(next);
                }
            }
        GPoint location(x, y);
        newnode->loc = location;
        dataFile.nodeMap.insert(pair<string, Node *> (nodename, newnode));

        filereadout.remove(0);
    }

    filereadout.remove(0);

    while (filereadout.size() > 0) {
        string line = filereadout[0];
        scanner.setInput(line);
        Arc *newarc1 = new Arc;
        Arc *newarc2 = new Arc;
        Node *currnode = new Node;
        Node *nextnode = new Node;
        string one;
        string two;
        for (int i = 0; i < 3; i++) {
            if (i == 0) {
                one = scanner.nextToken();
                iter = dataFile.nodeMap.find(one);
                currnode = iter->second;
                newarc1->start = currnode;
                newarc2->finish = currnode;
            }
            else if (i == 1) {
                two = scanner.nextToken();
                iter = dataFile.nodeMap.find(two);
                nextnode = iter->second;
                newarc1->finish = nextnode;
                newarc2->start = nextnode;
            }
            else if (i == 2) {
                scanner.scanNumbers();
                string thirdstring = scanner.nextToken();
                double third = stringToReal(thirdstring);
                newarc1->cost = third;
                newarc2->cost = third;
            }
        }
        kruskalarcs.add(newarc1);
        currnode->arcs.add(newarc1);
        nextnode->arcs.add(newarc2);
        dataFile.arcs.add(newarc1);
        dataFile.arcs.add(newarc2);
        filereadout.remove(0);
    }

    foreach (string word in dataFile.nodeMap) {
        iter = dataFile.nodeMap.find(word);
        Node *nextnode = iter->second;
        dataFile.nodes.add(nextnode);
    }
    if (filereadout.isEmpty()) return 1;
    return 0;
}

Set<Node *> PathfinderGraph::getNodes() {
    Set<Node *> result = dataFile.nodes;
    return result;
}

Set<Arc *> PathfinderGraph::getArcs() {
    Set<Arc *> result = dataFile.arcs;
    return result;
}

Vector<Node *> PathfinderGraph::getSelected() {
    return selected;
}

void PathfinderGraph::clearArcs() {
    dataFile.arcs.clear();
    foreach(Node *next in dataFile.nodes) {
        next->arcs.clear();
    }
}

Vector<Arc *> PathfinderGraph::getKruskalArcs() {
    return kruskalarcs;
}

And this is a partially templatized version of my heap pqueue that can take paths and arcs;

//
//  pqueue-heap.h
//  pathfinder
//
//  Created by Robbie on 08/06/2013.
//
//

#ifndef __pathfinder__pqueue_heap__
#define __pathfinder__pqueue_heap__

#include <string>
#include "cmpfn.h"
#include <iostream>

template <typename ElemType>
class HeapPQueue {
public:

	HeapPQueue<ElemType>() {
        capacity = START_CAPACITY;
        heap = new ElemType[capacity];
        logSize = 0;

    }

	~HeapPQueue<ElemType>() {
        delete[] heap;
    }

	static HeapPQueue *merge(HeapPQueue *one, HeapPQueue *two, int (*cmp) (ElemType, ElemType)) {
        HeapPQueue<ElemType> *mergeheap = new HeapPQueue<ElemType>;
        int size1 = one->logSize;
        int size2 = two->logSize;
        mergeheap->capacity = size1 + size2;
        mergeheap->expandCapacity();// create empty array with enough capacity

        for (int i = 1; i <= size1; i++) {// two for loops in case one and two are different sizes
            ElemType copy1 = one->getAt(i);
            mergeheap->add(copy1);
        }

        for (int y = 1; y <= size2; y++) {
            ElemType copy2 = two->getAt(y);
            mergeheap->add(copy2);
        }

        int tail = mergeheap->logSize;
        int head = tail / 2;
        mergeheap->reverseHeapify(head, tail, cmp);// heapify
        return mergeheap;
    }

	void enqueue(const ElemType &elem, int (*cmp) (ElemType, ElemType)) {
        if (logSize + 10 == capacity) {
            expandCapacity();
        }
        logSize++;//Set logSize to 1 to start, so can use logSize for heap calculations
        heap[logSize] = elem;//first element set to index 1, not using index 0 at all
        bubbleUp(logSize, cmp);
    }

    ElemType extractMin(int (*cmp) (ElemType, ElemType)) {
        ElemType first = heap[1];
        //if (first == "") error("Attempting to extract from empty queue");
        ElemType last = heap[logSize];
        heap[1] = last;//replace first with last word
        //heap[logSize] = "";//erase last word from array
        logSize--;//decrease logSize
        heapIfy(1, cmp);
        return first;
    }

    ElemType peek() const {
        ElemType first = heap[1];
        return first;
    }

    int size() {
        return logSize;
    }

private:

    void bubbleUp(int i, int (*cmp) (ElemType, ElemType)) {
        if (i / 2 == 0) return;// base case = index 1

        ElemType insert = heap[i];
        ElemType node = heap[i / 2];

        if (cmp(insert, node) != -1) return;// return if bubbled up to the right position
        heap[i] = node;// swap
        heap[i / 2] = insert;
        bubbleUp(i / 2, cmp);// recursively bubbleUp
    }

    void expandCapacity() {
        capacity *= 2;
        ElemType *oldheap = heap;
        heap = new ElemType[capacity];
        for (int i = 1; i <= logSize; i++) {
            heap[i] = oldheap[i];
        }

        delete[] oldheap;
    }

    void heapIfy(int node, int (*cmp) (ElemType, ElemType)) {// need some sort of comp function which gets sent pointer to comp plus
        if (node >= logSize) return;// base case

        int L = node * 2;// left and right nodes
        int R = (node * 2) + 1;
        int smallest = 0;

        if (L <= logSize && cmp(heap[node], heap[L]) == 1) {// check in bounds and assign smallest if left is smaller than node
            smallest = L;
        }
        else smallest = node;

        if (R <= logSize && cmp(heap[R], heap[smallest]) == -1) {// check in bounds etc...
            smallest = R;
        }
        if (smallest != node) {// if node isnt smallest swap with smallest
            ElemType swap = heap[smallest];
            heap[smallest] = heap[node];
            heap[node] = swap;
        }
        else if (smallest == node) return;// or return

        heapIfy(smallest, cmp);// recursively heapify
    }

    void reverseHeapify(int head, int tail, int (*cmp) (ElemType, ElemType)) {
        int newtail = head;
        int newhead = head / 2;// each segment is a generation of nodes
        if (newhead / 2 < 1) return;

        for (int i = newhead; i <= newtail; i++) {// cycle through each segment and heapify each node
            heapIfy(i, cmp);
        }
        reverseHeapify(newhead, newtail, cmp);
    }

    void add(ElemType word) {
        heap[logSize + 1] = word;
        logSize++;
    }

    ElemType getAt(int index) {
        ElemType word = heap[index];
        return word;
    }

    int logSize;
    static const int START_CAPACITY = 1000;
    int capacity;
    ElemType *heap;

};

#endif /* defined(__pathfinder__pqueue_heap__) */

Huffman Encoding

May 25th, 2013 by Robbie

It feels good to have written a compression program! One more exercise to go and CS106B is done…

This was all about debugging. Working out how to do it doesn’t take very long. Some of the bugs, once I’d found them, were bemusing. One of them turned out to be a bug in the map class provided by Stanford. Another was simply about the way I was declaring an addition to a string. Both the way I was doing it and the way that worked mean the same thing, as far as I’m aware. But I got into it, you just have to accept that if you get ahead of yourself, you’re probably going to have to end up checking every individual part for bugs. On the evidence of this, test-driven programming makes sense- so that you know that every function or class that you add does what it’s supposed to, before you add it. It turns out that a pseudo eof is only necessary if you aren’t using the frequency in the root node to decompress in a loop. So if you were to decompress recursively. But I found that had weird bugs too- I suspect due to bugs in the class libraries.

Header file for the Encoding class;

/**
 * File: encoding.h
 * ----------------
 * Defines the Encoding class to manage all aspects of the
 * Huffman compression and decompression algorithms.
 */

#ifndef _encoding_
#define _encoding_

#include "bstream.h"
#include "types.h"
#include <map>
#include "pqueue.h"


class Encoding {
    
public:
    
    void compress(ibstream& infile, obstream& outfile);
    void decompress(ibstream& infile, obstream& outfile);
    

private:
    
    PQueue huffqueue;
    Node *currentroot;
    Node *treeroot;
    map<int, int> frequencyTable;
    map<int, std::string> referenceTable;
    int leafcount;
    
    void getFrequency(ibstream& infile);
    void enqueueNodes();
    void buildTree(int leaves);
    void createReferenceTable(int leaves);
    void tracePaths(Node *root, std::string path, int leaves);
    void encodeFile(ibstream& infile, obstream& outfile, int leaves);
    void deleteTree(Node *root);
    void writeHeader(obstream& outfile, int leaves);
    void extractHeader(ibstream& infile);
    void decodeFile(ibstream& infile, obstream& outfile, int filesz);
    
};

#endif

cpp file for the Encoding class;

/**
 * File: encoding.cpp
 * ------------------
 * Place your Encoding class implementation here.
 */

#include "encoding.h"
#include "string.h"
#include "strlib.h"



using namespace std;


void Encoding::compress(ibstream& infile, obstream& outfile) {
    
    getFrequency(infile);
    
    enqueueNodes();
    
    int leaves = frequencyTable.size();
    buildTree(leaves);
    createReferenceTable(leaves);
    Node *root = huffqueue.extractMin();
    deleteTree(root);
    encodeFile(infile, outfile, leaves);
    infile.close();
    outfile.close();
    frequencyTable.clear();
    referenceTable.clear();
}

void Encoding::decompress(ibstream& infile, obstream& outfile) {
    
    extractHeader(infile);
    
    enqueueNodes();
    
    int leaves = frequencyTable.size();
    buildTree(leaves);
    treeroot = huffqueue.peek();
    int filesz = treeroot->frequency;
    
    decodeFile(infile, outfile,filesz);
    deleteTree(treeroot);
    frequencyTable.clear();
    referenceTable.clear();
}

void Encoding::getFrequency(ibstream& infile) {
    
    int ch;
    map<int, int>::iterator iter;
    while((ch = infile.get()) != EOF){
        if(frequencyTable.count(ch) != 0){
            iter = frequencyTable.find(ch);
            int count = iter->second;
            iter->second = ++count;
        }
        
        else {
            frequencyTable.insert(pair<int, int> (ch, 1));
        }
    }
}

void Encoding::enqueueNodes() {
    
    map<int, int>::iterator iter;
    
    foreach(int key in frequencyTable) {// enqueue leaf nodes
        iter = frequencyTable.find(key);
        int freq = iter->second;
        
        Node* newnode = new Node;
        newnode->character = key;
        newnode->frequency = freq;
        newnode->zero = NULL; 
        newnode->one = NULL;
        
        huffqueue.enqueue(newnode, freq);
    }
}

void Encoding::buildTree(int leaves) {
    
    for (int i = 1; i < leaves; i++) {
        
        Node *newnode = new Node;// Create new non-leaf node
        newnode->character = VOID;
        
        Node *zeronode = huffqueue.extractMin();
        
        newnode->zero = zeronode;// pull next node from queue and attach to zero
        
        Node *onenode = huffqueue.extractMin();
        
        newnode->one = onenode;// pull next node from queue and attach to one
        
        int newfreq = zeronode->frequency + onenode->frequency;
        newnode->frequency = newfreq;// new node's frequency is combined frequency
        huffqueue.enqueue(newnode, newfreq);// enqueue
    }
}

void Encoding::createReferenceTable(int leaves) {// wrapper function for backtracking recursion
    Node *root = huffqueue.peek();
    string path = "";
    leafcount = 0;
    tracePaths(root, path, leaves);
}

void Encoding::tracePaths(Node *root, string path, int leaves) {// backtracking recursion to trace paths
    if (leafcount >= leaves) {// base case is when the leafcount has reached the number of leaves in the tree
        return;
    }
    
    if (root->character != VOID) {// identify a leaf
        
        int ch = root->character;
        
        referenceTable.insert(pair<int, string> (ch, path));// insert into referenceTable
        leafcount++;// raise leaf count by one
        
        return;// rewind
    }
    
    for (int i = 0; i < 2; i++) {// for loop for one and zero pointers
        if (i == 0) {
            if (root->zero != NULL) {// check that zero pointer isnt null
                
                Node *zeronode = root->zero;// get the next node
               
                tracePaths(zeronode, path + "0", leaves);// recursively trace the paths, add 0 to path string
            }
        }
        else if (i == 1) {
            if (root->one != NULL) {// same process for one pointer
                
                Node *onenode = root->one;
                
                tracePaths(onenode, path + "1", leaves);
            }
        }
    }
    return;// rewind
}

void Encoding::deleteTree(Node *root) {// free up the memory from the tree
    if(root == NULL){
        return;
    }
    
    else{
        Node *zeronode = root->zero;
        Node *onenode = root->one;
        
        delete root;
        
        deleteTree(zeronode);
        deleteTree(onenode);
    }
}

void Encoding::encodeFile(ibstream& infile, obstream& outfile, int leaves) {
    
    infile.rewind();
    
    writeHeader(outfile, leaves);
    int ch;
    map<int, string>::iterator iter;
    while((ch = infile.get()) != EOF){
        iter = referenceTable.find(ch);
        string encoding = iter->second;
            for (int i = 0; i < encoding.size(); i++) {
                char bit = encoding.at(i);
                if (bit == '0') {
                    outfile.writebit(0);
                }
                else if (bit == '1') {
                    outfile.writebit(1);
            }
        }
    }
}

void Encoding::writeHeader(obstream& outfile, int leaves) {
    
    outfile << leaves << ' ';// leave a gap after the number of leaf nodes
    
    map<int, int>::iterator iter;
    foreach(int key in frequencyTable) {
        iter = frequencyTable.find(key);
        int freq = iter->second;
        outfile << key << ' ';// leave gaps again
        outfile << freq << ' ';
    }
}

void Encoding::extractHeader(ibstream& infile) {
    int number;
    infile >> number;
    infile.get();
    string numstring = integerToString(number);
    for (int i = 0; i < number; i++) {
        int key;
        infile >> key;
        infile.get();
        int freq;
        infile >> freq;
        infile.get();
        frequencyTable.insert(pair<int, int> (key, freq));
    }
}

void Encoding::decodeFile(ibstream& infile, obstream& outfile, int filesz) {
    
    for (int i = 0; i < filesz; i++) {
        currentroot = treeroot;
        
        while (currentroot->character == VOID) {
            int n = infile.readbit();
            if (n == 1) {
                currentroot = currentroot->one;
            }
            else currentroot = currentroot->zero;
        }
        int ch = currentroot->character;
        outfile.put(ch);
    }
    outfile.close();
    infile.close();
}

Node and VOID constant in a separate header;

//
//  types.h
//  huffman
//
//  Created by Robbie on 20/05/2013.
//
//

#ifndef huffman_types_h
#define huffman_types_h



const int VOID = 256;


struct Node {
   
    int character;
    
    Node *zero;
    
    Node *one;
    
    int frequency;
    
};



#endif

Ashley Bickerton

May 20th, 2013 by Robbie

Mood break. I’m in the middle of Huffman Encoding, which is frustrating, not because it’s difficult to think through, but because the bugs are silly. A friend of mine told me, nearly a year ago when I decided to learn to program, that “programming is easy, debugging is hard”. That’s very true. I’m now on my second week doing this, off and on, which is the longest I’ve ever spent on a single program. I’m building little programs just to eek out the junk from little parts of my program. Which makes me think that I have to have some counterpoint. I’ve been wondering how to produce physical objects for a while, and the amazing Ashley Bickerton is much on my thoughts right now;

AB_LM9919_Mades_Warung_I_hr2

AB_LM16175_White_Head_II_hr2

AB_LM11266_Dream_hr2

AB_LM9876_Davidsons_hr2

AB_LM11019_Famili_hr2

Priority Queue, implementation 3: heap

April 10th, 2013 by Robbie

Here’s the heap implementation. I think I’m going to have a go at binomial heap too. This one was tricky because of the way merge is set up as a static member function. I figured expandCapacity is expensive, so I created a new instance and called expand capacity to a big enough size, on the empty array. Then copied one and two into it before heapifying it. Whether that would actually make any difference in speed, I’m not really sure.

Heap implementation header file;

#ifndef _binary_heap_pqueue_
#define _binary_heap_pqueue_

#include "pqueue.h"
#include <string>

class HeapPQueue : public PQueue {
public:
	HeapPQueue();
	~HeapPQueue();
	
	static HeapPQueue *merge(HeapPQueue *one, HeapPQueue *two);
	
	void enqueue(const std::string& elem);
    std::string extractMin();
    std::string peek() const;
    
private:
    static const int START_CAPACITY = 1000;
    int capacity;
    std::string *heap;
    void bubbleUp(int logSize);
    void expandCapacity();
    void heapIfy(int node);
    void reverseHeapify(int head, int tail);
    void add(std::string word);
    std::string getAt(int index);

};

#endif

Heap implementation class file;

#include "pqueue-heap.h"
#include "error.h"
using namespace std;

HeapPQueue::HeapPQueue() {
    capacity = START_CAPACITY;
    heap = new string[capacity];
    
}
HeapPQueue::~HeapPQueue() {
    delete[] heap;
    
}

string HeapPQueue::peek() const {
    string first = heap[1];
	return first;
}

string HeapPQueue::extractMin() {
    string first = heap[1];
        if (first == "") error("Attempting to extract from empty queue");
            string last = heap[logSize];
            heap[1] = last;//replace first with last word
            heap[logSize] = "";//erase last word from array
            logSize--;//decrease logSize
            heapIfy(1);
            return first;
}

void HeapPQueue::heapIfy(int node) {
    if (node >= logSize) return;// base case
    
    int L = node * 2;// left and right nodes
    int R = (node * 2) + 1;
    int smallest = 0;
        if (L <= logSize && heap[node] > heap[L]) {// check in bounds and assign smallest if left is smaller than node
            smallest = L;
    }
        else smallest = node;
    
        if (R <= logSize && heap[R] < heap[smallest]) {// check in bounds etc...
            smallest = R;
    }
        if (smallest != node) {// if node isnt smallest swap with smallest
            string swap = heap[smallest];
            heap[smallest] = heap[node];
            heap[node] = swap;
    }
        else if (smallest == node) return;// or return
        
    heapIfy(smallest);// recursively heapify
}

void HeapPQueue::enqueue(const string& elem) {
    if (logSize + 10 == capacity) {
        expandCapacity();
    }
    logSize++;//Set logSize to 1 to start, so can use logSize for heap calculations
    heap[logSize] = elem;//first element set to index 1, not using index 0 at all
    bubbleUp(logSize);
}

void HeapPQueue::expandCapacity() {
    capacity *= 2;
    string *oldheap = heap;
    heap = new string[capacity];
        for (int i = 1; i <= logSize; i++) {
            heap[i] = oldheap[i];
    }
    
    delete[] oldheap;
}

void HeapPQueue::bubbleUp(int i) {
    if (i / 2 == 0) return;// base case = index 1
    
    string insert = heap[i];
    string node = heap[i / 2];
        if (insert >= node) return;// return if bubbled up to the right position
        heap[i] = node;// swap
        heap[i / 2] = insert;
        bubbleUp(i / 2);// recursively bubbleUp
}

HeapPQueue *HeapPQueue::merge(HeapPQueue *one, HeapPQueue *two) {
    HeapPQueue *mergeheap = new HeapPQueue;
    int size1 = one->logSize;
    int size2 = two->logSize;
    mergeheap->capacity = size1 + size2;
    mergeheap->expandCapacity();// create empty array with enough capacity
    
    for (int i = 1; i <= size1; i++) {// two for loops in case one and two are different sizes
        string copy1 = one->getAt(i);
        mergeheap->add(copy1);
    }
    
    for (int y = 1; y <= size2; y++) {
        string copy2 = two->getAt(y);
        mergeheap->add(copy2);
    }

    int tail = mergeheap->logSize;
    int head = tail / 2;
    mergeheap->reverseHeapify(head, tail);// heapify 
    return mergeheap;
}

void HeapPQueue::add(string word) {
    heap[logSize + 1] = word;
    logSize++;
}
 
string HeapPQueue::getAt(int index) {
    string word = heap[index];
    return word;
}

void HeapPQueue::reverseHeapify(int head, int tail) {
    int newtail = head;
    int newhead = head / 2;// each segment is a generation of nodes
    if (newhead / 2 < 1) return;
    
        for (int i = newhead; i <= newtail; i++) {// cycle through each segment and heapify each node
            heapIfy(i);
    }
    reverseHeapify(newhead, newtail);
}

Priority Queue, implementations 1 & 2

April 7th, 2013 by Robbie

Here are the first two implementations of priority Queue. Fairly straightforward, although a doubly linked list is a bit fiddly.

Doubly linked list header file;

#ifndef _linked_list_pqueue_
#define _linked_list_pqueue_

#include "pqueue.h"
#include <string>

class LinkedListPQueue : public PQueue {
public:
	LinkedListPQueue();
	~LinkedListPQueue();
	
	static LinkedListPQueue *merge(LinkedListPQueue *one, LinkedListPQueue *two);
	
	void enqueue(const std::string& elem);
    std::string extractMin();
    std::string peek() const;
	
private:
	struct cellT {
        std::string word;
        cellT *prev;
        cellT *next;
    };
    
    cellT *head, *tail, *cursorA, *cursorB;
};

#endif

Doubly linked list class file;

#include "pqueue-linked-list.h"
#include "error.h"


using namespace std;

LinkedListPQueue::LinkedListPQueue() {
    head = tail = NULL;
}

LinkedListPQueue::~LinkedListPQueue() {
    cellT *cp = head;
    while (cp != NULL) {
        cellT *del = cp->next;
        delete cp;
        cp = del;
    }
}

string LinkedListPQueue::peek() const {
    if (isEmpty()) error("Empty queue");
    string first = head->word;
    return first;
}

string LinkedListPQueue::extractMin() {
    if (isEmpty()) error("Empty queue");
    string first = head->word;
    cellT *dequeued = head;
    head = head->next;
    delete dequeued;
    logSize--;
    return first;
    
}

void LinkedListPQueue::enqueue(const string& elem) {
    cellT *newCell = new cellT;
    newCell->word = elem;
        if (isEmpty()) {
            newCell->prev = NULL;
            newCell->next = NULL;
            head = tail = newCell;
    }
        else if (elem <= head->word) {
            newCell->next = head;
            head->prev = newCell;
            newCell->prev = NULL;
            head = newCell;
    }
        else if (elem >= tail->word) {
            tail->next = newCell;
            newCell->prev = tail;
            newCell->next = NULL;
            tail = newCell;
    }
        else {
            for (cursorA = tail; cursorA != NULL; cursorA = cursorA->prev) {
                if (cursorA->word <= elem) {
                    cursorB = tail;
                    while (cursorB->prev != cursorA) {
                        cursorB = cursorB->prev;
            }
                    cursorB->prev = newCell;
                    newCell->prev = cursorA;
                    newCell->next = cursorB;
                    cursorA->next = newCell;
                    break;
            }
        }
    }
    logSize++;
}

LinkedListPQueue *LinkedListPQueue::merge(LinkedListPQueue *one, LinkedListPQueue *two) {
	LinkedListPQueue *result = new LinkedListPQueue;
    for (int i = 0; i < 1000; i++) {
        string test1 = one->extractMin();
        string test2 = two->extractMin();
        result->enqueue(test1);
        result->enqueue(test2);
    }
	return result;
}

Vector based pqueue header file;

#ifndef _vector_pqueue_
#define _vector_pqueue_

#include "pqueue.h"
#include <string>
#include "vector.h"



class VectorPQueue : public PQueue {
public:
	VectorPQueue();
	~VectorPQueue();
	
	static VectorPQueue *merge(VectorPQueue *one, VectorPQueue *two);
	
	void enqueue(const std::string& elem);
    std::string extractMin();
    std::string peek() const;
	
private:
    Vector<string> pQueue;
};

#endif

Vector based pqueue class file;

#include "pqueue-vector.h"

using namespace std;

VectorPQueue::VectorPQueue() {
    Vector<string> pQueue;
}

VectorPQueue::~VectorPQueue() {
    
}

string VectorPQueue::peek() const {
    if(isEmpty()) {
        error("peek; Attempting to peek at an empty queue");
    }
    string result = pQueue.get(0);
	return result;
}

string VectorPQueue::extractMin() {
    if (isEmpty()) {
        error("extractmin; Queue is empty");
    }
    int min = 0;
    string minimum = pQueue.get(0);
	for (int i= 1; i < logSize; i++) {
        string check = pQueue.get(i);
        if (check < minimum) {
            min = i;
            minimum = check;
        }
    }
    pQueue.remove(min);
    logSize--;
	return minimum;
}

void VectorPQueue::enqueue(const string& elem) {
	pQueue.add(elem);
    logSize++;
}

VectorPQueue *VectorPQueue::merge(VectorPQueue *one, VectorPQueue *two) {
    VectorPQueue *result = new VectorPQueue;
    for (int i = 0; i < 1000; i++) {
        string test1 = one->extractMin();
        string test2 = two->extractMin();
        result->enqueue(test1);
        result->enqueue(test2);
        }
	return result;
}

Immersion Kickstarter

March 3rd, 2013 by Robbie

So this is what’s happening with the Immersion project! I’d like to throw it open for participation, with anyone who wants to contribute. I’m going to publish a book and continue to do exhibitions on it, and I’d like the collaborative element to be part of that. If you click through to the Kickstarter page, look at update #1. Within two days of launching we’ve already had a very cool idea about how to use the proposed site in a way that will create work that I simply wouldn’t be able to do on my own. I’m excited! What with the programming I’m doing, I’m becoming less and less interested in actually shooting work (I will continue to shoot Immersion till the project finishes). Instead it’s become much more interesting to think about ways to create participatory and more engaging projects…

The rewards for the project include the book, a collector’s edition of the book, and limited edition prints.

Sort Detective

February 20th, 2013 by Robbie

I haven’t had a chance to do any of this for a while. Sort Detective was pretty easy though- I did it late last night. Here’s my answers;

1. Mysterysort1 is Merge Sort. It’s fast, but not as fast as quicksort. NlogN complexity class and there’s not much difference when it sorts unsorted, sorted or reverse sorted.

2. Mysterysort2 is Insertion sort. It’s quadratic and faster on sorted than reverse sorted.

3. Mysterysort3 is Quicksort- it’s very fast, roughly NlogN complexity, falls to quadratic when dealing with sorted or reverse sorted data.

4. Mysterysort4 is Selection sort. It’s quadratic, not much difference between sorted, reverse sorted or unsorted data.

5. Mysterysort5 is Bubble sort. It’s slow, does well on sorted, badly on reverse sorted, as you’d expect.

My adjusted algorithm is below, but I couldn’t get #include cmpfn.h to load in XCode. So I couldn’t use the OperatorCmp function. So this algorithm only works for integers, chars etc, it isn’t fully generalized. That’s a trivial task though. I’ll see if there’s any alternatives I can use. All I did was randomize the selection of the pivot and then swap it out with the first cell of the vector, which is treated as the pivot (the rest of the algorithm is unchanged). It’s very simple and very effective. The adjusted quicksort remains much faster than any other algorithm on data of reasonable size (except for the original quicksort, on unsorted data), and quicksort’s normal worst-case scenarios become blisteringly fast. It remains NlogN. It’s only possible weak point is repeated bad luck on the randomized choice of pivot. That, however, is extremely unlikely since the pivot is chosen at every level of the recursion.

If anyone knows how to get #include cmpfn.h working on XCode, or if there’s an alternative, please email me! The libStanfordCPPLib is loaded…

template <typename Type>
void mySort(Vector<Type>& t, int start, int finish) {
    if (start >= finish) return;
    int boundary = Partition(t, start, finish);
    mySort(t, start, boundary - 1);
    mySort(t, boundary + 1, finish);
}

template <typename Type>
int Partition(Vector<Type>& t, int start, int finish) {
    int randompoint = randomInteger(start, finish);
    Type pivot = t[randompoint];
    Type startvalue = t[start];
    t[start] = pivot;
    t[randompoint] = startvalue;
    int count = start + 1;
    int rh = finish;
    while (true) {
        while (count < rh && t[rh] >= pivot) rh--;
        while (count < rh && t[count] < pivot) count++;
        if (count == rh) break;
        int temp = t[count];
        t[count] = t[rh];
        t[rh] = temp;
    }
    if (t[count] >= pivot) return start;
    t[start] = t[count];
    t[count] = pivot;
    return count;
}

Boggle

January 20th, 2013 by Robbie

boggleScreen2

It says on the assignment brief for this exercise to properly decompose the Boggle program, before starting work. Of course I didn’t. By this stage I was getting cocky and felt like recursion was getting easy. This problem has the capacity to produce hard-to-find bugs if you don’t prepare. My mistake was passing the x and y of the next square/current square, as a parameter. That doesn’t work- much better to get x and y from whatever you’re storing the path of tiles in. They tell you to split the execution between human and player turns, which I did, but I had the computer turn call two of the same functions. The first time I’ve re-used functions! I think if I’d done it flat-out it would have taken me maybe 3 days. Which gives me quite alot of respect for those kids at Stanford! Apparently the CS106B page has changed since I linked to it, so someone asked me to send the course files I’m working from. I’ll try and post them on this blog soon…

/**
 * File: boggle.cpp
 * ----------------
 * Implements the game of Boggle.
 */
 
#include <cctype>
#include <iostream>
using namespace std;

#include "simpio.h"
#include "gwindow.h"
#include "gboggle.h"
#include "map.h"
#include "grid.h"
#include "random.h"
#include "lexicon.h"

const int kBoggleWindowWidth = 650;
const int kBoggleWindowHeight = 350;
const int kBoggleBoardSize = 4;
const int kBoggleCubesSize = 16;


const string kStandardCubes[16] = {
   "AAEEGN", "ABBJOO", "ACHOPS", "AFFKPS",
   "AOOTTW", "CIMOTU", "DEILRX", "DELRVY",
   "DISTTY", "EEGHNW", "EEINSU", "EHRTVW",
   "EIOSST", "ELRTTY", "HIMNQU", "HLNNRZ"
};

const string kBigBoggleCubes[25] = {
   "AAAFRS", "AAEEEE", "AAFIRS", "ADENNN", "AEEEEM",
   "AEEGMU", "AEGMNN", "AFIRSY", "BJKQXZ", "CCNSTW",
   "CEIILT", "CEILPT", "CEIPST", "DDLNOR", "DDHNOT",
   "DHHLOR", "DHLNOR", "EIIITT", "EMOTTT", "ENSSSU",
   "FIPRSY", "GORRVW", "HIPRRY", "NOOTUW", "OOOTTU"
};


static void playGame();
static void welcome();
static void giveInstructions();
static bool responseIsAffirmative(const string& prompt);
static void createBoard(Vector<Vector<string> >& cubes, Grid<char>& board);
static void forceBoardConfig(Grid<char>& board);
static bool isWord(string playerword, Lexicon& english);
static bool notUsed(string playerword, Set<string>& usedwords);
static bool longEnough(string playerword);
static bool findStart(string playerword, Grid<char>& board);
static bool findSquares(string playerword, Grid<char>& board, Vector<GPoint>& path, Set<GPoint>& usedsquares, Vector<int>& lastwordsize, string& found);
static void nextSquare(string playerword, Grid<char>& board, Vector<GPoint>& path, Set<GPoint>& usedsquares, string& found, int dir);
static void removeSquare(Vector<GPoint>& path, Set<GPoint>& usedsquares, Vector<int>& lastwordsize, string& found);
static void highlightWord(Vector<GPoint>& path);
static bool wordHasGrown(Vector<int>& lastwordsize, string& found);
static void computerTurn(Grid<char>& board, Set<string>& usedwords, Lexicon& english);
static bool findWords(Grid<char>& board, Vector<GPoint>& path, Vector<int>& lastwordsize, Set<GPoint>& usedsquares, Set<string>& foundwords, string& compfound, Set<string>& usedwords, Lexicon& english, bool endcheck);
static void buildWord(Grid<char>& board, Vector<GPoint>& path, Set<GPoint>& usedsquares, Set<string>& foundwords, string& compfound, Set<string>& usedwords, Lexicon& english, int dir);
static void processSquare(Vector<GPoint>& path, Set<GPoint>& usedsquares, Set<string>& foundwords, string& compfound, Set<string>& usedwords, Lexicon& english, string& temporary, GPoint& result);
    


int main() {
    
    while (true) {
        
        playGame();
        
        if (!responseIsAffirmative("Would you like to play again?")) {
            break;
        }
    }

   return 0;
}

static void playGame() {
    
    GWindow gw(kBoggleWindowWidth, kBoggleWindowHeight);
    initGBoggle(gw);
    welcome();
    Lexicon english("EnglishWords.dat");
    if (responseIsAffirmative("Do you need instructions? ")) {
        giveInstructions();
    }
    
    Vector<Vector<string> > cubes;
    Grid<char> board(kBoggleBoardSize, kBoggleBoardSize);
    drawBoard(kBoggleBoardSize, kBoggleBoardSize);
    createBoard(cubes, board);
    Set<string> usedwords;
    cout << "I'll give you a chance to set up the board to your specification, which makes it easier to confirm your boggle program is working." << endl;
    if (responseIsAffirmative("Do you want to force the board configuration? ")) {
        forceBoardConfig(board);
    }
    else {
        createBoard(cubes, board);
    }
    for (int boardx = 0; boardx < kBoggleBoardSize; boardx++) {
        for (int boardy = 0; boardy < kBoggleBoardSize   ; boardy++) {
            char letter = board.get(boardx, boardy);
            labelCube(boardx, boardy,letter);
        }
    }
    cout << endl;
    cout << "Ok, take all the time you want and find all the words you can!  Signal that you're finished by entering an empty line." << endl;
    while (true) {
        cout << "Enter a word :";
        string playerwordinit = getLine();
        string playerword = toUpperCase(playerwordinit);
        if (playerword == "") {
            break;
        }
        if (isWord(playerword, english) && notUsed(playerword, usedwords) && longEnough(playerword)) {
            if (findStart(playerword, board)) {
                usedwords.add(playerword);
            }
            else {
                cout << "You can't make that word." << endl;
            }
        }
    }
    computerTurn(board, usedwords, english);

}

static void welcome() {
    cout << "Welcome!  You're about to play an intense game ";
    cout << "of mind-numbing Boggle.  The good news is that ";
    cout << "you might improve your vocabulary a bit.  The ";
    cout << "bad news is that you're probably going to lose ";
    cout << "miserably to this little dictionary-toting hunk ";
    cout << "of silicon.  If only YOU had a gig of RAM..." << endl << endl;
}

static void giveInstructions() {
    cout << endl;
    cout << "The boggle board is a grid onto which I ";
    cout << "I will randomly distribute cubes. These ";
    cout << "6-sided cubes have letters rather than ";
    cout << "numbers on the faces, creating a grid of ";
    cout << "letters on which you try to form words. ";
    cout << "You go first, entering all the words you can ";
    cout << "find that are formed by tracing adjoining ";
    cout << "letters. Two letters adjoin if they are next ";
    cout << "to each other horizontally, vertically, or ";
    cout << "diagonally. A letter can only be used once ";
    cout << "in each word. Words must be at least four ";
    cout << "letters long and can be counted only once. ";
    cout << "You score points based on word length: a ";
    cout << "4-letter word is worth 1 point, 5-letters ";
    cout << "earn 2 points, and so on. After your puny ";
    cout << "brain is exhausted, I, the supercomputer, ";
    cout << "will find all the remaining words and double ";
    cout << "or triple your paltry score." << endl << endl;
    cout << "Hit return when you're ready...";
    getLine();
}

static bool responseIsAffirmative(const string& prompt) {
    while (true) {
        string answer = getLine(prompt);
        if (!answer.empty()) {
            switch (toupper(answer[0])) {
                case 'Y': return true;
                case 'N': return false;
            }
        }
        cout << "Please answer yes or no." << endl;
    }
}

static void createBoard(Vector<Vector<string> >& cubes, Grid<char>& board) {
    for (int i = 0; i < 16; i++) {
        Vector<string> onecube;
        for (int letter = 0; letter < 6; letter++) {
            string cube = kStandardCubes[i];
            string side = cube.substr(letter, 1);
            onecube.add(side);
        }
        cubes.add(onecube);
    }
    for (int swap = 0; swap < cubes.size(); swap++) {
        int swap2 = randomInteger(swap, cubes.size() - 1);
        Vector<string> element1 = cubes.get(swap);
        Vector<string> element2 = cubes.get(swap2);
        cubes.set(swap2, element1);
        cubes.set(swap, element2);
    }
    Vector<string> selections;
    for (int x = 0; x < 16; x++) {
        Vector<string> cubethrow = cubes.get(x);
        int random = randomInteger(0, 5);
        string selection = cubethrow.get(random);
        selections.add(selection);
    }
    int selectionsindex = 0;
    for (int boardx = 0; boardx < kBoggleBoardSize; boardx++) {
        for (int boardy = 0; boardy < kBoggleBoardSize   ; boardy++) {
            string position = selections.get(selectionsindex);
            char position2 = position[0];
            board.set(boardx, boardy, position2);
            selectionsindex++;
        }
    }
}

static void forceBoardConfig(Grid<char>& board) {
    cout << "Enter a 16-character string to identify which letters you want on the cubes." << endl;
    cout << "The first 4 letters are the cubes on the top row from left to right, the next 4 letters are the second row, and so on." << endl;
    cout << "Enter the string: ";
    string playerselect = getLine();
    cout << "This is the playerselect " + playerselect << endl;
    if (playerselect.size() < kBoggleCubesSize) {
        cout << "That string isnt long enough!" << endl;
        forceBoardConfig(board);
    }
    else if (playerselect.size() >= kBoggleCubesSize) {
        int stringindex = 0;
        for (int boardx = 0; boardx < kBoggleBoardSize; boardx++) {
            for (int boardy = 0; boardy < kBoggleBoardSize   ; boardy++) {
                char select = playerselect[stringindex];
                char upperselect = toupper(select);
                board.set(boardx, boardy, upperselect);
                stringindex++;
            }
        }
    }
}

static bool isWord(string playerword, Lexicon& english) {
    if (english.contains(playerword)) {
    return true;
    }
    else {
        cout << "That isn't a word!" << endl;
    }
    return false;
}

static bool notUsed(string playerword, Set<string>& usedwords) {
    if (usedwords.contains(playerword)) {
        cout << "You already used that word." << endl;
        return false;
    }
    return true;
}

static bool longEnough(string playerword) {
    if (playerword.size() < 4) {
        cout << "I'm sorry, but we have our standards." << endl;
        cout << "That word doesn't meet the minimum word length." << endl;
        return false;
    }
    return true;
}

static bool findStart(string playerword, Grid<char>& board) {
    char beginning = playerword[0];
    char uppercase = toupper(beginning);
    for (int x = 0; x < kBoggleBoardSize; x++) {
        for (int y = 0; y < kBoggleBoardSize; y++) {// loop cycles through each space of the board looking for start letter
            char boardlocation = board.get(x, y);
            if (uppercase == boardlocation) {
                Vector<GPoint> path;// stores path of matched letters
                Vector<int> lastwordsize;// stores size of the word in the previous turn to check wordhasgrown
                Set<GPoint> usedsquares;// stores the usedsquares so they arent re-used in same word
                string found = playerword.substr(0, 1);
                lastwordsize.insert(0, 1);
                GPoint start(x, y);
                path.add(start);
                usedsquares.add(start);
                if (findSquares(playerword, board, path, usedsquares, lastwordsize, found)) {
                    highlightWord(path);
                    recordWordForPlayer(playerword, HUMAN);
                    return true;
                }
            }
        }
    }
    return false;
}

static bool findSquares(string playerword, Grid<char>& board, Vector<GPoint>& path, Set<GPoint>& usedsquares, Vector<int>& lastwordsize, string& found) {
    
    if (playerword == found) {// Base case of found word matches the player input word
        return true;
    }
    
    if (found.size() == 0) {// if the found word goes back to empty, return false and cycle to the next start letter
        return false;
    }
    
        for (int dir = 0; dir < 8; dir++) {// loop of 8, one per possible direction
            
            nextSquare(playerword, board, path, usedsquares, found, dir);// returns GPoint of next square
        
               if (wordHasGrown(lastwordsize, found)) {// if the word has grown
                    if (findSquares(playerword, board, path, usedsquares, lastwordsize, found)) {// recurse to new loop till its solved
                        return true; 
                }
            }
        }
    removeSquare(path, usedsquares, lastwordsize, found);// remove square after the loop and rewind to earlier decision
    return false;
}

        
static void nextSquare(string playerword, Grid<char>& board, Vector<GPoint>& path, Set<GPoint>& usedsquares, string& found, int dir) {
    
    GPoint newstart = path.get(path.size() - 1);
    int x = newstart.getX();
    int y = newstart.getY();
    int length = found.size();
    char target = playerword[length];
    if (dir == 0) {// dir is loop number from findsquares- direction
        if (board.inBounds(x + 1, y)) {
            char thisone = board[x + 1][y]; // for each cycle of the loop check a letter on the board around the source tile
            GPoint result(x + 1, y);
                if (target == thisone && !usedsquares.contains(result)) {
                    found = found + target;
                    path.add(result);
                    usedsquares.add(result);
            }
        }
    }
    if (dir == 1) {
        if (board.inBounds(x - 1, y)) {
            char thisone = board[x - 1][y];
            GPoint result(x - 1, y);
                if (target == thisone && !usedsquares.contains(result)) {
                    found = found + target;
                    path.add(result);
                    usedsquares.add(result);
            }
        }
    }
    if (dir == 2) {
        if (board.inBounds(x, y + 1)) {
            char thisone = board[x][y + 1];
            GPoint result(x, y + 1);
                if (target == thisone && !usedsquares.contains(result)) {
                    found = found + target;
                    path.add(result);
                    usedsquares.add(result);
            }
        }
    }
    if (dir == 3) {
        if (board.inBounds(x, y - 1)) {
            char thisone = board[x][y - 1];
            GPoint result(x, y - 1);
                if (target == thisone && !usedsquares.contains(result)) {
                    found = found + target;
                    path.add(result);
                    usedsquares.add(result);
            }
        }
    }
    if (dir == 4) {
        if (board.inBounds(x - 1, y - 1)) {
            char thisone = board[x - 1][y - 1];
            GPoint result(x - 1, y - 1);
                if (target == thisone && !usedsquares.contains(result)) {
                    found = found + target;
                    path.add(result);
                    usedsquares.add(result);
            }
        }
    }
    if (dir == 5) {
        if (board.inBounds(x + 1, y - 1)) {
            char thisone = board[x + 1][y - 1];
            GPoint result(x + 1, y - 1);
                if (target == thisone && !usedsquares.contains(result)) {
                    found = found + target;
                    path.add(result);
                    usedsquares.add(result);
            }
        }
    }
    if (dir == 6) {
        if (board.inBounds(x + 1, y + 1)) {
            char thisone = board[x + 1][y + 1];
            GPoint result(x + 1, y + 1);
                if (target == thisone && !usedsquares.contains(result)) {
                    found = found + target;
                    path.add(result);
                    usedsquares.add(result);
            }
        }
    }
    if (dir == 7) {
        if (board.inBounds(x - 1, y + 1)) {
            char thisone = board[x - 1][y + 1];
            GPoint result(x - 1, y + 1);
                if (target == thisone && !usedsquares.contains(result)) {
                    found = found + target;
                    path.add(result);
                    usedsquares.add(result);
            }
        }
    }
}
    
static void removeSquare(Vector<GPoint>& path, Set<GPoint>& usedsquares, Vector<int>& lastwordsize, string& found) {
    if (found.length() > 0) {
    GPoint erase = path.get(path.size() - 1);
    found.erase(found.length() - 1);
    int newwordsize = found.length();
    lastwordsize.set(0, newwordsize);
    path.remove(path.size() - 1);
    usedsquares.remove(erase);
    }
}

static void highlightWord(Vector<GPoint>& path) {
    for (int i = 0; i < path.size(); i++) {
        GPoint update1 = path.get(i);
        int x = update1.getX();
        int y = update1.getY();
        highlightCube(x, y, true);
    }
    pause(200);
    for (int n = 0; n < path.size(); n++) {
        GPoint update2 = path.get(n);
        int x = update2.getX();
        int y = update2.getY();
        highlightCube(x, y, false);
    }
}


static bool wordHasGrown(Vector<int>& lastwordsize, string& found) {//
    int currentsize = found.length();
    int lastsize = lastwordsize.get(0);
    if (lastsize >= currentsize) {
        lastwordsize.set(0, currentsize);
        return false;
    }
    
    else if (lastsize < currentsize){
        lastwordsize.set(0, currentsize);
        return true;
    }
}

static void computerTurn(Grid<char>& board, Set<string>& usedwords, Lexicon& english) {
    Set<string> foundwords;
    for (int x = 0; x <= kBoggleBoardSize; x++) {
        for (int y = 0; y <= kBoggleBoardSize; y++) {
            string compfound;
                if (x < kBoggleBoardSize && y < kBoggleBoardSize) {
                    char boardlocation = board.get(x, y);
                    compfound = compfound + boardlocation;
            }
            
            Vector<GPoint> path;// stores path of matched letters
            Vector<int> lastwordsize;// stores size of the word in the previous turn to check wordhasgrown
            Set<GPoint> usedsquares;// stores the usedsquares so they arent re-used in same word
            bool endcheck = false;// during the loop send out false for recursive base case
            if (x == kBoggleBoardSize || y == kBoggleBoardSize) {
                endcheck = true;// hits the final extra loop and sends true
            }
            
            lastwordsize.insert(0, 1);
            GPoint start(x, y);
            path.add(start);
            usedsquares.add(start);
            if (findWords(board, path, lastwordsize, usedsquares, foundwords, compfound, usedwords, english, endcheck)) {
                break;
            }
        }
    }
    
    foreach (string word in foundwords) {
        recordWordForPlayer(word, COMPUTER);
    }
    
}

static bool findWords(Grid<char>& board, Vector<GPoint>& path, Vector<int>& lastwordsize, Set<GPoint>& usedsquares, Set<string>& foundwords, string& compfound, Set<string>& usedwords, Lexicon& english, bool endcheck) {
    if (endcheck == true) {// base case is the extra loop in computerturn that sends out endcheck bool
        return true;
    }
    
    if (compfound.size() == 0) {
        return false;
    }
    
        for (int dir = 0; dir < 8; dir++) {
            
            buildWord(board, path, usedsquares, foundwords, compfound, usedwords, english, dir);
            
            if (wordHasGrown(lastwordsize, compfound)) {// re-use wordhasgrown function
                if (findWords(board, path, lastwordsize, usedsquares, foundwords, compfound, usedwords, english, endcheck)) {
                    return true;
            }
        }
    }
    removeSquare(path, usedsquares, lastwordsize, compfound);// re-use removesquare function
    return false;
}
        
static void buildWord(Grid<char>& board, Vector<GPoint>& path, Set<GPoint>& usedsquares, Set<string>& foundwords, string& compfound, Set<string>& usedwords, Lexicon& english, int dir) {
    
    GPoint newstart = path.get(path.size() - 1);
    int x = newstart.getX();
    int y = newstart.getY();
    string temporary = compfound;
    
    if (dir == 0) {// dir is loop number from findsquares- direction
        if (board.inBounds(x + 1, y)) {
            char thisone = board[x + 1][y]; // for each cycle of the loop check a letter on the board around the source tile
            temporary = temporary + thisone;
            GPoint result(x + 1, y);
            if (usedsquares.contains(result) == false) {
            processSquare(path, usedsquares, foundwords, compfound, usedwords, english, temporary, result);
            }
        }
    }
        
    if (dir == 1) {
        if (board.inBounds(x - 1, y)) {
            char thisone = board[x - 1][y];
            temporary = temporary + thisone;
            GPoint result(x - 1, y);
            if (usedsquares.contains(result) == false) {
            processSquare(path, usedsquares, foundwords, compfound, usedwords, english, temporary, result);
            }
        }
    }
        
    if (dir == 2) {
        if (board.inBounds(x, y + 1)) {
            char thisone = board[x][y + 1];
            temporary = temporary + thisone;
            GPoint result(x, y + 1);
            if (usedsquares.contains(result) == false) {
            processSquare(path, usedsquares, foundwords, compfound, usedwords, english, temporary, result);
            }
        }
    }
        
    if (dir == 3) {
        if (board.inBounds(x, y - 1)) {
            char thisone = board[x][y - 1];
            temporary = temporary + thisone;
            GPoint result(x, y - 1);
            if (usedsquares.contains(result) == false) {
            processSquare(path, usedsquares, foundwords, compfound, usedwords, english, temporary, result);
            }
        }
    }
        
    if (dir == 4) {
        if (board.inBounds(x - 1, y - 1)) {
            char thisone = board[x - 1][y - 1];
            temporary = temporary + thisone;
            GPoint result(x - 1, y - 1);
            if (usedsquares.contains(result) == false) {
            processSquare(path, usedsquares, foundwords, compfound, usedwords, english, temporary, result);
            }
        }
    }
        
    if (dir == 5) {
        if (board.inBounds(x + 1, y - 1)) {
            char thisone = board[x + 1][y - 1];
            temporary = temporary + thisone;
            GPoint result(x + 1, y - 1);
            if (usedsquares.contains(result) == false) {
            processSquare(path, usedsquares, foundwords, compfound, usedwords, english, temporary, result);
            }
        }
    }
        
    if (dir == 6) {
        if (board.inBounds(x + 1, y + 1)) {
            char thisone = board[x + 1][y + 1];
            temporary = temporary + thisone;
            GPoint result(x + 1, y + 1);
            if (usedsquares.contains(result) == false) {
            processSquare(path, usedsquares, foundwords, compfound, usedwords, english, temporary, result);
            }
        }
    }
        
    if (dir == 7) {
        if (board.inBounds(x - 1, y + 1)) {
            char thisone = board[x - 1][y + 1];
            temporary = temporary + thisone;
            GPoint result(x - 1, y + 1);
            if (usedsquares.contains(result) == false) {
            processSquare(path, usedsquares, foundwords, compfound, usedwords, english, temporary, result);
            }
        }
    }
}

static void processSquare(Vector<GPoint>& path, Set<GPoint>& usedsquares, Set<string>& foundwords, string& compfound, Set<string>& usedwords, Lexicon& english, string& temporary, GPoint& result) {
    
    if (english.containsPrefix(temporary) || english.contains(temporary)) {
            path.add(result);
            usedsquares.add(result);
            compfound = temporary;
            if (english.contains(compfound) && compfound.size() >= 4 && !usedwords.contains(compfound)) {
                foundwords.add(compfound);
        }
    }
}

Recursion Warm Ups: Exercise 3, Dominosa

January 8th, 2013 by Robbie

dominosaScreenforweb

Unexpectedly epic. Probably has post Christmas flab on it. I like the way the Stanford exercises are always hooked up to a graphics window and carefully thought out to make the whole thing very visual. Recursive backtracking is quite tricky but amazingly satisfying to get it going. The process is definitely becoming like building. Not that I’ve ever built anything, except for some plastic models when I was a kid. Which I promptly set fire to, nine times out of ten.

/**
 * File: dominosa.cpp
 * ------------------
 * This animates the brute-force discovery of a solution
 * to a 2 x n dominosa board.
 */

#include <iostream>
#include <cmath>
using namespace std;

#include "simpio.h"
#include "grid.h"
#include "random.h"
#include "set.h"
#include "map.h"
#include "dominosa-graphics.h"

static void welcome();
static int getIntegerInRange(string prompt, int low, int high);
static void populateBoard(Grid<int>& board, int low, int high);
static bool canSolveBoard(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, int numColumns);
static void certifyPairings(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns);
static bool findPairs(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns, int rewind);
int tryPairing1(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns);
int tryPairing2(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns);
static void deletePairings(DominosaDisplay& display, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumn);
static void buildNumbers( Grid<int>& board, Map<coord, int>& numbers, int numColumns);

int main() {
	DominosaDisplay display;
	welcome();
	while (true) {
		int numColumns = getIntegerInRange("How many columns? [0 to exit]: ", 9, 25);
		if (numColumns == 0) break;
		Grid<int> board(2, numColumns);// grid from the starter file of the exercise- hardly used it
        Set<pair<int, int> > pairings;// Set of pairs to keep track of the pairings
		populateBoard(board, 1, ceil(2 * sqrt(numColumns)));
        Map<coord, int> numbers;// key of tile coordinates and a map of the numbers
        buildNumbers(board, numbers, numColumns);
		display.drawBoard(board);
		if (canSolveBoard(display, board, numbers, pairings, numColumns)) {
			cout << "The board can be solved, and one such solution is drawn above." << endl;
		} else {
			cout << "This board you see can't be solved." << endl;
		}
	}
	
	cout << "Okay, thanks for watching, and come back soon." << endl;
    cout << "Click the mouse anywhere in the window to exit." << endl;
	return 0;
}

static void welcome() {
	cout << "Here we'll illustrate the use of recursive backtracking to" << endl;
	cout << "discover a solution to various 2 x n Dominosa boards.  In some" << endl;
	cout << "cases there won't be any solutions, and in the cases where there are" << endl;
	cout << "multiple solutions, we'll just find one of them." << endl;
	cout << endl;
}

static int getIntegerInRange(string prompt, int low, int high) {
	while (true) {
		int response = getInteger(prompt);
		if (response == 0 || (response >= low && response <= high)) return response;
		cout << "Sorry, but I can't use that number." << endl;
	}
}

static void populateBoard(Grid<int>& board, int low, int high) {
	for (int row = 0; row < board.numRows(); row++) {
		for (int col = 0; col < board.numCols(); col++) {
			board[row][col] = randomInteger(low, high);
		}
	}
}

static bool canSolveBoard(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, int numColumns) {
    
    Vector<int> orientation;// to keep track of the direction that the numbers are paired in- 1 for vertial, 2 and 3 for horizontal
    if (findPairs(display, board, numbers, pairings, orientation, numColumns, 0)) {
        certifyPairings(display, board, numbers, pairings, orientation, numColumns);
        return true;
    }
    
    else {
        
        return false;
    }
}

static void certifyPairings(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int col) {
    
    int check = col;
    for (int i = check - 1; i > -1; i--) {
        int direction = orientation.get(i);
        if (direction == 1) {
            int one = board.get(0, i);
            int two = board.get(1, i);
            coord coord1, coord2;
            coord1.row = 0;
            coord1.col = i;
            coord2.row = 1;
            coord2.col = i;
            pair<int, int> pair;
                if (one <= two) {
                    pair = make_pair(one, two);
                }
                else if(two < one) {
                    pair = make_pair(two, one);
                }
            if (pairings.contains(pair)) {
                display.certifyPairing(coord1, coord2);
            }
        }
        else if (direction == 2) {
            coord coordthree, coordfour, coordfive, coordsix;
            coordthree.row = 0;
            coordthree.col = i;
            coordfour.row = 0;
            coordfour.col = i - 1;
            coordfive.row = 1;
            coordfive.col = i;
            coordsix.row = 1;
            coordsix.col = i - 1;
            int oneupper = numbers.get(coordthree);
            int twoupper = numbers.get(coordfour);
            int onelower = numbers.get(coordfive);
            int twolower = numbers.get(coordsix);
            
            pair<int, int> pair1, pair2;
                if (oneupper <= twoupper) {
                    pair1 = make_pair(oneupper, twoupper);
                }
                else if (twoupper < oneupper) {
                    pair1 = make_pair(twoupper, oneupper);
                }
                if (onelower <= twolower) {
                    pair2 = make_pair(onelower, twolower);
                }
                else if (twolower < onelower) {
                    pair2 = make_pair(twolower, onelower);
                }
            if (pairings.contains(pair1) && pairings.contains(pair2) ) {
                display.certifyPairing(coordthree, coordfour);
                display.certifyPairing(coordfive, coordsix);
            }
        }
    }
}

static void buildNumbers( Grid<int>& board, Map<coord, int>& numbers, int numColumns) {
    for (int row = 0; row < 2; row++) {
        for (int column = 0; column < numColumns; column++) {
            int number = board[row][column];
            coord location;
            location.row = row;
            location.col = column;
            numbers.put(location, number);
        }
    }
}

static bool findPairs(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns, int rewind) {
    
    int numcolumn = pairings.size();
    
    if (numcolumn == numColumns) return true; // base case, if the set of pairs has reached the size of numColumns, it's done
    
    if (numcolumn < numColumns) {
        
        for (int i = 1; i < 3; i++) {
            
            if (i == 1) {// Do vertical pairing on loop 1, and horizontal second loop
                rewind = tryPairing1(display, board, numbers, pairings, orientation, numColumns);
            }
            
            else if (i == 2) {// try pairing 2 horizintally
                rewind = tryPairing2(display, board, numbers, pairings, orientation, numColumns);
            }
                     
            if (rewind != 1) {// the result from tryPairing determines if it skips the recursion and rewinds
                if (findPairs(display, board, numbers, pairings, orientation, numColumns, rewind)) return true;
            }
        }
        
        deletePairings(display, numbers, pairings, orientation, numColumns);// rewind to an earlier decision

    }
	return false;
}

int tryPairing1(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns) {
    int col = pairings.size();
        coord coordone, coordtwo;
        coordone.row = 0;
        coordone.col = col;
        coordtwo.row = 1;
        coordtwo.col = col;
        int one = numbers.get(coordone);
        int two = numbers.get(coordtwo);
        
        pair<int, int> pair;
        
        if (one <= two) {
            pair = make_pair(one, two);
        }
        else if (two < one) {
            pair = make_pair(two, one);
        }
        
        if (pairings.contains(pair) == false) {
            pairings.add(pair);
            display.provisonallyPair(coordone, coordtwo);
            orientation.add(1);
            return 0;
        }
        else if (pairings.contains(pair) == true) {
            display.vetoProvisionalPairing(coordone, coordtwo);
            display.eraseProvisionalPairing(coordone, coordtwo);
            return 1;
        }
    return 1;
}

            
int tryPairing2(DominosaDisplay& display, Grid<int>& board, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumns) {
    int col = pairings.size();
    if (col < numColumns) {
        coord coordthree, coordfour, coordfive, coordsix;
            coordthree.row = 0;
            coordthree.col = col;
            coordfour.row = 0;
            coordfour.col = col + 1;
            coordfive.row = 1;
            coordfive.col = col;
            coordsix.row = 1;
            coordsix.col = col + 1;
            int oneupper = numbers.get(coordthree);
            int twoupper = numbers.get(coordfour);
            int onelower = numbers.get(coordfive);
            int twolower = numbers.get(coordsix);
    
        pair<int, int> pair1, pair2;
    
            if (oneupper <= twoupper) {
                pair1 = make_pair(oneupper, twoupper);
            }
            else if (twoupper < oneupper) {
                pair1 = make_pair(twoupper, oneupper);
            }
            if (onelower <= twolower) {
                pair2 = make_pair(onelower, twolower);
            }
            else if (twolower < onelower) {
                pair2 = make_pair(twolower, onelower);
            }
            
            if (col == numColumns - 1) {// stops it going out of bounds
                
                return 1;
            }
        
            if (pair1 == pair2) {// if the pairs are the same only one will get insterted into the set and everything will go out of sync
                display.vetoProvisionalPairing(coordthree, coordfour);
                display.vetoProvisionalPairing(coordfive, coordsix);
                display.eraseProvisionalPairing(coordthree, coordfour);
                display.eraseProvisionalPairing(coordfive, coordsix);
                return 1;
            }
            else if (pairings.contains(pair1) == false && pairings.contains(pair2) == false) {
                pairings.add(pair1);
                pairings.add(pair2);
                orientation.add(3);// add numbers to orientation- has to be two different numbers otherwise it'll repeat the delete when rewinding
                orientation.add(2);
                display.provisonallyPair(coordthree, coordfour);
                display.provisonallyPair(coordfive, coordsix);
                return 0;
            }
            else if (pairings.contains(pair1) == false && pairings.contains(pair2) == true) {
                display.provisonallyPair(coordthree, coordfour);
                display.vetoProvisionalPairing(coordfive, coordsix);
                display.eraseProvisionalPairing(coordthree, coordfour);
                display.eraseProvisionalPairing(coordfive, coordsix);
                return 1;
            }
            else if (pairings.contains(pair1) == true && pairings.contains(pair2) == false) {
                display.vetoProvisionalPairing(coordthree, coordfour);
                display.provisonallyPair(coordfive, coordsix);
                display.eraseProvisionalPairing(coordthree, coordfour);
                display.eraseProvisionalPairing(coordfive, coordsix);
                return 1;
            }
            else {
                display.vetoProvisionalPairing(coordthree, coordfour);
                display.vetoProvisionalPairing(coordfive, coordsix);
                display.eraseProvisionalPairing(coordthree, coordfour);
                display.eraseProvisionalPairing(coordfive, coordsix);
                return 1;
                }
            }
    return 0;
}

static void deletePairings(DominosaDisplay& display, Map<coord, int>& numbers, Set<pair<int, int> >& pairings, Vector<int>& orientation, int numColumn) {
    int col = pairings.size() - 1;
    
    if (orientation.size() > 0 && col > -1) {
        int erasor = orientation.get(orientation.size() - 1);
            if (erasor == 1) {
            
            coord coord1, coord2;
            coord1.row = 0;
            coord1.col = col;
            coord2.row = 1;
            coord2.col = col;
            int one = numbers.get(coord1);
            int two = numbers.get(coord2);
            pair<int, int> pair;
        if (one <= two) {
            pair = make_pair(one, two);
        }
        else if (two < one) {
            pair = make_pair(two, one);
        }
            pairings.remove(pair);
            orientation.remove(orientation.size() - 1);
            display.eraseProvisionalPairing(coord1, coord2);
        
    
}
        else if (erasor == 2) {
    
            coord coord3, coord4, coord5, coord6;
            coord3.row = 0;
            coord3.col = col;
            coord4.row = 0;
            coord4.col = col - 1;
            coord5.row = 1;
            coord5.col = col;
            coord6.row = 1;
            coord6.col = col - 1;
            int oneupper = numbers.get(coord3);
            int twoupper = numbers.get(coord4);
            int onelower = numbers.get(coord5);
            int twolower = numbers.get(coord6);
        
            pair <int, int> pair1, pair2;
        
        if (oneupper <= twoupper) {
                pair1 = make_pair(oneupper, twoupper);
        }
        else if (twoupper < oneupper) {
                pair1 = make_pair(twoupper, oneupper);
        }
        if (onelower <= twolower) {
                pair2 = make_pair(onelower, twolower);
        }
        else if (twolower < onelower) {
                pair2 = make_pair(twolower, onelower);
        }
            pairings.remove(pair1);
            pairings.remove(pair2);
            orientation.remove(orientation.size() - 1);
            orientation.remove(orientation.size() - 1);
            display.eraseProvisionalPairing(coord3, coord4);
            display.eraseProvisionalPairing(coord5, coord6);
        }
    }
}

Recursion Warm Ups: Exercise 2, Mnemonics

December 17th, 2012 by Robbie

Another quite enjoyable one. The equivalent to printing out values as a way of debugging/trying out ideas, in recursion, seems to be to write pseudo code. Never really did it before this exercise and it helps enormously.

/**
 * File: generate-mnemonics.cpp
 * ----------------------------
 * This is an application that compiles phone numbers (or, more generally,
 * numbers) to mnemonics, where the digit-to-letter mappins are consistent
 * with those listed on a traditional telephone keypad.
 */

#include <string>    // for string
#include <iostream>  // for cout, endl
using namespace std;

#include "console.h"
#include "simpio.h"  // for getLine
#include "vector.h"  // for the Vector class template
#include "map.h"     // for the Map class template

static void buildMappings(Map<char, string>& mappings);
static bool isAllPositiveDigits(const string& response);
static string getPhoneNumber();
static void generateMnemonics(string rest, Map<char, string>& mappings, Vector<string>& mnemonics);
static void setUpMnemonics(const string& number, Map<char, string>& mappings, Vector<string>& mnemonics);
    
int main() {
    Map<char, string> mappings;
    buildMappings(mappings);
    while (true) {
        string number = getPhoneNumber();
        if (number.empty()) break;
        Vector<string> mnemonics;
        setUpMnemonics(number, mappings, mnemonics);
        cout << "These are the possible mnemonics: " << endl << endl;
        int count = 0;
        foreach (string mnemonic in mnemonics) {
            cout << "  " << mnemonic;
            count = (count + 1) % 9;
            if (count % 9 == 0) cout << endl;
        }
        cout << endl;
    }
    
    return 0;
}

static void setUpMnemonics(const string& number, Map<char, string>& mappings, Vector<string>& mnemonics) {
    char startkey = number[0];
    string rest = number.substr(1);
    string start = mappings.get(startkey);
    for (int i = 0; i < start.size(); i++) {
        string stub = start.substr(i, 1);// turn the start string into stubs
        mnemonics.add(stub);// and add to the mnemonics vector
        }
    generateMnemonics(rest, mappings, mnemonics);
}

static void generateMnemonics(string rest, Map<char, string>& mappings, Vector<string>& mnemonics) {
    if (rest == "") {// base case- wait till "rest" (all the keys) is gone and then return
        return;
    } else {
        Vector<string> temporary;// if results are stored in mnemonics during the loop it'll be infinite
        char key = rest[0];
        string next = mappings.get(key);
            if (rest.size() > 1) {// remove the current number from the string of keys
                rest = rest.substr(1);
        }
            else {
                rest = "";
        }
        for (int stub = 0; stub < mnemonics.size(); stub++) {// pull the stubs from mnemonics
            string current = mnemonics.get(stub);
            for (int nextone = 0; nextone < next.length(); nextone++) {// cycle through next characters and add to the stubs
                string character = next.substr(nextone, 1);
                string result = current + character;
                temporary.add(result);// add results to temporary
            }
        }
        mnemonics = temporary;// copy temporary on to mnemonics
        generateMnemonics(rest, mappings, mnemonics);
    }
}
                                  
static string getPhoneNumber() {
    while (true) {
        string response = getLine("Enter a string of digits [or hit <enter> if you're done]: ");
        if (isAllPositiveDigits(response)) return response;
        cout << "Whatever you enter, make sure it includes only digit characters in ['2', '9'].  ";
        cout << "Please try again." << endl;
    }
}

static bool isAllPositiveDigits(const string& response) {
    for (int i = 0; i < response.size(); i++) {
        if (response[i] < '2' || response[i] > '9') {
            return false;
        }
    }
                                      
    return true;
}
                                  
static void buildMappings(Map<char, string>& mappings) {
    const string options[] = {
        "ABC", "DEF", "GHI", "JKL",
        "MNO", "PQRS", "TUV", "WXYZ"
        };
                                      
    for (int i = 0; i < sizeof(options)/sizeof(options[0]); i++) {
        mappings['2' + i] = options[i];
    }
}