Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your feedback on a survey! Each completed response supports our community and gives you a chance to win a $25 Amazon gift card!


kirkd

Member Since 06 Jan 2000
Offline Last Active Oct 19 2013 05:32 PM

Topics I've Started

Tkinter - asksavefilename vs askopenfilename - neither?

19 October 2013 - 10:10 AM

In my application I want to let the user specify a new file name or pick an existing file which will simply be appended. 

 

asksavefilename works to specify a new file, but it throws a warning window if an existing file is picked saying it will be overwritten. 

askopenfilename lets you pick an existing file without the overwrite warning, but you can't specify a new file

 

Any ideas how to make either of these work or am I going to have to roll my own dialog?  If I could force asksavefilename not to throw the overwrite warning, that would be great.

 

-Kirk

 


Data structure to represent/access synonym lists

06 June 2013 - 02:08 PM

I have data which consists of list of synonyms and within each list there is a preferred synonym.  For example, [A,b,c,d,e] and [Z,y,x,w,v], with the capitalized letter being the preferred name for that particular list of synonyms.  I want to be able to access all the members of the synonym list with any member of that list, and I want to be able to access the preferred name for a synonym list by any member of the list. 

 

The things that come to mind in C++ are maps and multimaps, and in Python Dictionaries.  I don't know of a version of multimap in Python.  Even with these, though it seems clunky.

 

For maps/dictionaries, I could create a vector/list of each synonym list which is stored in a map/dictionary multiple times, once for each item in the synonym list.  If this were in C++ I could store the pointer to the vector of each one to save some space.  Something like:

 

std::vector<std::string> syn_list_a

std::vector<std::string> syn_list_z

std::map<std::string, std::vector<string> > syn_map

std::map<std::string, std::string> > pref_map

 

syn_map["A"] = &syn_list_a

syn_map["b"] = &syn_list_a

...

syn_map["Z"] = &syn_list_z

syn_map["y"] = &syn_list_z

...

pref_map["A"] = "A"

pref_map["b"] = "A"

...

pref_map["Z"] = "B"

pref_map["y"] = "B"

 

For Python, I could translate this to dictionaries.

 

But, this all seems very inelegant and clunky.  Any suggestions for a better way??


2D Array - really that hard?

26 February 2013 - 11:00 AM

OK, I have to play.

 

Over a decade ago I was working on a project with another developer whose job it was to implement the model for a 2D scatter plot.  The scatter plot had the ability to color-by and size-by - pick a data column and you would get a color or size gradient based on the data values. We had settled on 20 color steps and 20 size steps for the plot, and he was perplexed by how to accomplish this.  I suggested a 20x20 2D array, each element of which would hold the indices of the points corresponding to that a particular size and color, with the data range divided by 20 to get the bins for each one.  Not the most elegant solution, but seemed workable.

 

We were developing in VB 6 and he was enamored with dictionaries - everything was a dictionary.  So, he developed a dictionary that would be accessed by a two element string consisting of the bin locations.  In other words instead of the array bins(x,y), he had the dictionary bins["x,y"].  In his code, he would compute the color/size bin numerically, combine these into a string, use this to access the dictionary.  OK, whatever.

 

Put on top of this that his code computed the color and size bin locations in different locations and they might not always occur in the same order - sometimes you got "color,size" and sometimes you got "size,color."  It all depended on if the user clicked "color by" or "size by" first.  Oh, and he would use "first element 0" based calculations in one area and "first element 1" based calculations in another area. 

 

Now the kicker - the item stored in the dictionary was - wait for it - another dictionary.  This one was accessed by breaking up the original string key, doing some non-sensical conversions (not the obivous 20*y+x to get a linearlized array from the 2D array), and then access this dictionary with that new, converted key.  Which was converted to a string.

 

I inherited this code when he left.

 


Online card game - backend questions

11 December 2012 - 01:00 PM

I've come up with an idea for a card game which I think would be good as an in-person as well as an online game. The details of the game are quite superfluous to my question, which is...

Given a multiplayer card game, or even something like Words with Friends, what are the backend requirements? I have no experience with this sort of thing, and I'm probably way out of my league on it all, but I'm curious as to what such a game entails. Is it run on a server which players log into and all the gameplay is managed there, or is it be done on the users' machines? How about as an Android app?

-Kirk

A* implementation with templates - feedback?

24 October 2012 - 01:17 PM

At the risk of being either laughed or flamed off the planet...

I wrote what I hope to be a very generic A* implementation using templates. I had wrestled with tyring to do this same sort of thing using a class hierarchy, but it became very unweildy very quickly. I haven't had much experience with templates, so I thought this might be a good place to start. All that being said, below are the two clases that seem to be serving me very well right now. Any comments and constructive criticisms are welcome.

Here's the GraphSearch class which does the actual search.
[source lang="cpp"]/** @author Robert Kirk DeLisle rkdelisle@gmail.com @version 0.1 @section LICENSE @section DESCRIPTION GraphSearch Template Class Provides different graph search/pathfinding algorithms. Currently: Dijkstra A* IDA* Fringe Search Usage: GraphSearch<Searchable, Heuristic> Searchable class: Any class intended to serve as a node within a graph for the search. Must implement: std::string GetUID() - retrieve a globally unique ID for the node vector< Searchable * > GetNeighbors() - get all valid neighbors of this node from the graph float G() - retrieve the G value (cost thus far) for this node void G(float value) - set the G value for this node float GetCostToExpand() - how much did it cost to expand this node from the parent Searchable * GetParentNode() - retrieve a pointer to the parent node. If null, assumed to be the start location of the search std::string GetGeneratingTransform() - what is the parsable transform that led to generation of this node from the parent a vector of these will be stored as the solution/path from Start to Goal void ReplaceNode( Searchable * ) - used to replace one node (the caller) with another (the parameter) in the search this will maintain the order of the nodes in the list and apply the correct costs if we find a shorter path to a node after first evaluating it These functions need to be defined to operate on the Searchable class: bool NodeSort( Searchable &left, Searchable &right ) - sorting algorithm used by GraphSearch to maintain search priority returns (left.F() > right.F()) bool IsGoal( Searchable * ) - is this node the goal? Heuristic Template Class: A class providing a function to calculate the appropriate heuristic for the search. Implements: float ComputeH( Searchable & ) - compute and store the heuristic for the passed node Note: for Dijkstra, ComputeH() returns 0.0*/#ifndef GRAPHSEARCH_12Oct12_RKD#define GRAPHSEARCH_12Oct12_RKD#include <vector>#include <map>#include <string>#include <algorithm>#include <iostream>template<class Searchable, class H>class GraphSearch{ private: /** The priority queue will be a vector managed by std::algorithm::make_heap(), ::push_heap() and ::pop_heap(). */ std::vector<Searchable *> vpq_open_list; /** To facilitate searching the priority queue, a std::map will be maintained in parallel. */ std::map<std::string, Searchable *> map_open_list; // /** Closed list will be a std::map to facilitate easy searching */ std::map<std::string, Searchable *> map_closed_list; /** Vector to hold the solution. Each entry correponds to the results of Searchable::GetGeneratingTransform() moving from node to node in the search space. Each transformation is a string that comes from Searchable::GetGeneratingTransform() and correcponds to a transormation applied to the object represented by the node. */ std::vector<std::string> m_Solution; bool m_SolutionFound; /** Store the transformations necessary to move from the Start node to the Goal node. Each transformation is a string that comes from Searchable::GetGeneratingTransform() and correcponds to a transormation applied to the object represented by the node. */ std::vector<std::string> StorePathToGoal(Searchable *); //capture the path to the goal once it is found //return the length of that path /** Delete dynamic objects stored in open and closed lists */ void FreeLists(); public: /** Default constructor. Initialize necessary variables. */ GraphSearch() { Init(); }; /** Initialize object variables. */ void Init() { m_SolutionFound = false; m_Solution.clear(); vpq_open_list.clear(); map_open_list.clear(); map_closed_list.clear(); }; /** The A* Search Algorithm \param *Start - Pointer to the start node as a Searchable object. \param *heu - Heuristic object to be used by the algorithm. \return true if a solution is found false if the search space is fully evaluated and no solution is found */ bool AStar(Searchable *Start, H heu); /** Retrieve the solution/path from Start to Goal */ std::vector<std::string> GetSolution() { return m_Solution; }; /** Default destructor */ ~GraphSearch() {};};template<class Searchable, class H>bool GraphSearch<Searchable, H>::AStar(Searchable *Start, H heu){ //run A* from the start node to the goal node //if a solution is found, store it in the m_Solution variable //and return "true", otherwise, return "false" Searchable *current; std::vector<Searchable *> neighbor_list; Init(); vpq_open_list.push_back(Start); std::make_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort); map_open_list[ Start->GetUID() ] = Start; Start->G(0.0); while (!vpq_open_list.empty()) { std::pop_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort); current = vpq_open_list.back(); if ( IsGoal(current) ) { m_SolutionFound = true; StorePathToGoal( current ); //take the Start out of the lists so that it doesn't get deleted map_open_list.erase(Start->GetUID()); map_closed_list.erase(Start->GetUID()); FreeLists(); return true; } vpq_open_list.pop_back(); map_open_list.erase( current->GetUID() ); map_closed_list[ current->GetUID() ] = current; neighbor_list = current->GetNeighbors(); for( typename std::vector<Searchable *>::iterator it=neighbor_list.begin(); it != neighbor_list.end(); it++ ) { if ( map_closed_list.find( (*it)->GetUID() ) != map_closed_list.end() ) { delete *it; continue; } if ( map_open_list.find( (*it)->GetUID() ) != map_open_list.end() ) { typename std::map<std::string, Searchable *>::iterator ol_it = map_open_list.find( (*it)->GetUID() ); if ( (*ol_it).second->G() > current->G() + (*it)->GetCostToExpand() ) { (*ol_it).second->ReplaceNode( (*it) ); (*ol_it).second->G( current->G() + (*it)->GetCostToExpand() ); (*ol_it).second->H( heu.ComputeH( (*ol_it).second )); std::make_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort); } delete *it; } else { (*it)->G( current->G() + (*it)->GetCostToExpand() ); (*it)->H( heu.ComputeH( (*it) )); map_open_list[ (*it)->GetUID() ] = (*it); vpq_open_list.push_back( (*it) ); std::push_heap(vpq_open_list.begin(), vpq_open_list.end(), NodeSort); } } } m_SolutionFound = false; return false; //if we get here, we've exhaused the entire search space}template<class Searchable, class H>std::vector<std::string> GraphSearch<Searchable, H>::StorePathToGoal(Searchable *current){ //capture the path to the goal once it is found //return the length of that path m_Solution.clear(); if ( !m_SolutionFound ) return m_Solution; while( current->GetParentNode() != 0 ) { m_Solution.push_back( current->GetGeneratingTransform() ); current = current->GetParentNode(); }; std::reverse(m_Solution.begin(), m_Solution.end()); return m_Solution;}template<class Searchable, class H>void GraphSearch<Searchable, H>::FreeLists(){ for ( typename std::map<std::string, Searchable *>::iterator it=map_open_list.begin(); it!=map_open_list.end(); it++) delete (*it).second; map_open_list.clear(); for ( typename std::map<std::string, Searchable *>::iterator it=map_closed_list.begin(); it!=map_closed_list.end(); it++) delete (*it).second; map_closed_list.clear();}#endif[/source]


This is an example of a Heuristic Class that is used by GraphSearch. The only necessary function is ComputeH but I put in the option to pick from multiple heuristics before it is passed to GraphSearch.

[source lang="cpp"]/** @author Robert Kirk DeLisle rkdelisle@gmail.com @version 0.1 @section LICENSE @section DESCRIPTION Heuristic Template Class example For use with GraphSearch Template Class Provides a heuristic for the 2x2x2 Rubik's Cube Usage: GraphSearch<Searchable> Searchable class: Any class intended to serve as a node within a graph for the search and for which a heuristic is calculated. Must implement: ComputeH( Searchable & ) - returns a heuristic estimate of distance to the goal from the passed Searchable node*/#include <map>#include <fstream>#include <string>#include <sstream>#include <iostream>#ifndef CUBE2HEURISTIC_2012OCT09_RKD#define CUBE2HEURISTIC_2012OCT09_RKDtemplate<class Searchable>class Cube2Heuristic{ public: /** For this example, two possible heuristics are available: DIJKSTRA returns 0.0 as Dijkstra search uses no heuristic UPDOWNFACE returns the max of the number of turn necessary to properly position (NOT orient) the top corners or the bottom corners. */ enum Heuristics { DIJKSTRA, UPDOWNFACE }; /** Compute the heuristic value \param *node - Pointer to the node of interest. \return the computed value */ float ComputeH(Searchable *node); /** For this example, I have set up the ability to pre-select which heuristic you want to use. \param h - Value from the Cube2Heuristic::Heuristics enumeration */ void SetHeuristic( Heuristics h ) { m_SelectedHeuristic = h; }; /** Default constructor. Initialize any heuristics and set a default one to be used. */ Cube2Heuristic() { InitUpDownFace(); m_SelectedHeuristic = UPDOWNFACE; }; /** Default destructor. */ ~Cube2Heuristic() {}; private: /** Holds the pre-computed heuristic. \param .first - A UID for the 2x2x2 Cube \param .second - The maximum of the number of turns to properly position (NOT orient) the upper corners or the lower corners. */ std::map<unsigned int, int> UpDownFaceHeuristic; /** Initialize the heuristic */ void InitUpDownFace(); /** Retrieve the precomputed UPDONWFACEHEURISTIC - used by ComputeH() \param *node - pointer to the node/2x2x2 cube of interest */ float GetUpDownFaceHeuristic(Searchable *node); Heuristics m_SelectedHeuristic;};template<class Searchable>float Cube2Heuristic<Searchable>::GetUpDownFaceHeuristic(Searchable *node){ return std::max( UpDownFaceHeuristic[node->GetTopID()], UpDownFaceHeuristic[node->GetBottomID()] );};template<class Searchable>float Cube2Heuristic<Searchable>::ComputeH(Searchable *node){ switch ( m_SelectedHeuristic ) { case DIJKSTRA: return 0.0; case UPDOWNFACE: return GetUpDownFaceHeuristic(node); default: return 0.0; }}template<class Searchable>void Cube2Heuristic<Searchable>::InitUpDownFace(){ std::fstream HFile; std::string incomingLine; int pos, moves; unsigned int ID; HFile.open("UpDownFace.heu", std::ios::in); while ( !HFile.eof() ) { std::getline(HFile, incomingLine); pos = incomingLine.find(","); std::istringstream( incomingLine.substr(0,pos) ) >> ID; std::istringstream( incomingLine.substr(pos+1) ) >> moves; UpDownFaceHeuristic[ID] = moves; } HFile.close();};#endif[/source]

PARTNERS