Monthly Archives: March 2011

What the people want, or at least what brought them here…


Q & A based on searches that brought readers here yesterday, if the answer isn’t painfully obvious.

compass dh mosquito – Its on the sidewall to the left of the pilot, about where their knee bends. Same horizontal, direct reading compass as a Hurricane or Spitfire.

how to thin water based paint for spraying – Thin to the consistency of whole milk. Distilled water is good, distilled water 50:50 with isopropanol (rubbing)  alcohol is good, and evaporates faster. Both work with Polly Scale, Gunze Sangyo, Tamiya acrylic and Testor’s Acryl paints. Tamiya make a water and alcohol solvent (not isopropanol…) which works better for Tamiya acrylic paint.
I have read descriptions of people using lacquer thinner with water based paints- well, obviously it would evaporate REALLY fast.
polly scale ship colors – I’ll have to look this up- there was a Coast Guard Orange that I used for my 1/72 DHC-6 Twin Otter- it was either Polly Scale or Testors’ Acryl, and in a line of colors for nautical subjects. In addition, Polly Scale offer a collection of blues and grays identified as the various shades used in the US Navy’s WWII camouflage.
polly scale paint drying time – somewhat depends on how thickly its applied, and whether its thinned first. A brushed coat applied lightly can dry in as little as 20-30 minutes. A heavy coat might take an hour or two.

doolittle b 25 colors – Olive Drab over Neutral Gray. Propellers & hubs black. Wheels and gear legs “steel” paint.

vallejo us navy blue
Mmm – *which* US Navy Blue? Intermediate Blue? Blue-Gray? Sea Blue? Non-specular or glossy? Uniform blue? Dungaree blue? The blueish-grays of A-4 / F-14 / F-5 / F-21 (Kfir) Dis-similar Air Combat training Agressors? Blue Angels blue? That’s easy- insignia blue and white.

bac 707 to fed std 595 – For my money BAC-707 is approximately FS-36495 diluted with 8 parts white to 3 parts 36495.

paint color abbott green – never heard of it but I can see why it would up here.

bronze green tamiya

1/72 hasegawa f4f wildcat

dhc6 1:144

rc hobby store east bay, san francisco
bay area hobby shops
model car decal paper sf bay retailers

oxygen 61 gray

download tptp for netbeans

mig23.dwg 1
trislander aircraft
p-38l f5g aerial photography plane

Advertisements

Recursion, working it out in advance


In a recent pair of interviews, I was asked tree data structure questions, and I flubbed the first one. Hacking at a function that received a pointer to a node and that I needed to use as the launching point for recursion, not the recursive bit itself. Not pretty. NEXT time, I managed to gather up my wits, with a bit of help from my interviewer, Jim Gill, I managed to thread the needle and there it was, a recursive operation that worked. Sho-‘nuf!  That original is at the bottom of this post- a complete, working version, follows this introduction. Its about 180 lines, with a lot of white space.

And here’s the deal. You can’t make  a sensible recursive routine by simply getting the pointer and recalling that top level routine. YES recursion needs something that takes a pointer to node, and yes,  you call it with a child of the original node. But there’s more to it. A non-recursive superstructure which supports a recursive heart.

So here’s a complete, working, version, that compiles and runs using “gcc” on Mac OS 10.5.8. It takes a bit more than what I started with. “C” and other versions will follow, as separate postings.

Macintosh-6:interview Bill4$ cat recursion_v.cpp
/* recursion_v.cpp */
/* Follow-up to ___ recursion problem with Jim Gill, web prowling question at ____ */

/* input:
(M)
|   \
(N)  (P)
|  \    \
(Q) (S)  (T)
(3 level b tree, M has two children, N and P, and N has two children, Q and S.  P has one child – T.)

output:
Q, S, T, N, P, M

*/

#include <iostream>
#include <vector>

/* Structure in which the input data arrives: */

struct node {
std::vector <node*> children;  std::string name;
};

/* Structure the result vector (array) is built from: */
struct nameNLevel  {
std::string name;   int level;
};

/*
* Synopsis: void recur( node* n, int level, std::vector* nsNLs )
* args:
* node*    n     this node, which has a name, may have children
* int        level    number of steps down the tree
* std::vector    nsNLs   pointer to the vector of node-name, level structs we’ll want to report
* returns:
* no return value. Node name and level are put into the vector of nameLevel structs.
* Mar 27, 2011  Bill Abbott
*/

void recur( node* n, int level, std::vector <nameNLevel>* nsNLs ){

/* To collect additions, nsNLs vector must be passed as a pointer! */
/* Unlike an array in C, an std::vector isn’t passed as a pointer automatically! */
nameNLevel* nNL = new nameNLevel;
nNL->name = n->name;
nNL->level = level;
nsNLs->push_back( *nNL );

int vecIdx = nsNLs->size() – 1;

//    std::cout << nsNLs->size() << ”  ” << vecIdx << ”    “;
std::cout << (*nsNLs)[ vecIdx ].level << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name.size() << ”  “;
std::cout << (*nsNLs)[ vecIdx ].name.c_str() << ”    “;

std::cout << (nsNLs->back()).name << ”  ” << (nsNLs->back()).level << ”  ” << n->name << ”  ” << level << ”  “;
std::cout << nsNLs->size() << ”  ” ;
std::cout << n->children.size() << ”  ” << (0 != n->children.size()) << “\n”;
if ( 0 != n->children.size()) {   /* there are children */
for (int childCount =0; childCount < ( n->children.size()); childCount++ ){
recur(  n->children[childCount], level+1, nsNLs ); /* recursive call- children & next level… */
} /* for int childCount… */
} /* if ( 0!=  */

} /* recur *

/*
* Synopsis: void passThrough( node* n )
* args:
* node*    n     this node, which has a name, may have children
* returns:
* no return value. creates and outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011  Bill Abbott
*/

void passThrough( node* n ) {
std::vector namesNLevels;
int level = 0;

recur( n, level, &namesNLevels );

std::cout<< namesNLevels.size()  << ”  ” << “\n”;

int maxLevel = 0;
for (int i=0; i < namesNLevels.size(); i++ ) {
std::cout<< maxLevel << ”  ” << i << “\n”;
if (namesNLevels[i].level > maxLevel) {
maxLevel = namesNLevels[i].level;
} /* if */
} /* for */

/* note: recursion isn’t getting the data in the order we want… */
/* so, order them before printing. */

for (level=maxLevel; level >= 0; level–){
for (int i=0; i < namesNLevels.size(); i++ ) {
if (namesNLevels[i].level == level){
std::cout << namesNLevels[i].name <<  ” “;
} /* if (namesNLevels…) */
} /* for i */
} /* for level */

printf( “\n”);

}

/*
* Synopsis: int main( int argc, char* argv[] )
* args:
* int        argc    count of command line arguments
* char*    argv[]    vector of zero-terminated arrays of char containing command line args
* returns:
* no return value. creates a tree of nodes, outputs vector of node names,
* “highest” level first, in ascending order of child vector contents..
* Mar 27, 2011  Bill Abbott
*/

int main( int argc, char* argv[] ) {

/* 3 level b tree:
* M has two children, N and P, and
*    N has two children, Q and S.
*        Q has no children
*        S has no children
*    P has one child – T.
*        T has no children
*/

node* T = new node;
T->children.clear();
T->name = “T”;

node* S = new node;
S->children.clear();
S->name = “S”;

node* Q = new node;
Q->children.clear();
Q->name = “Q”;

node* P = new node;
P->children.push_back(T);
P->name = “P”;

node* N = new node;
N->children.push_back(Q);
N->children.push_back(S);
N->name = “N”;

node* M = new node;
M->children.push_back(N);
M->children.push_back(P);
M->name = “M”;

passThrough( M );

return( 1 );

————- Example output, with my debug couts—————-

Macintosh-6:interview Bill4$ c++ recursion_v.cpp
Macintosh-6:interview Bill4$ a.out
0  M  1  M    M  0  M  0  1  2  1
1  N  1  N    N  1  N  1  2  2  1
2  Q  1  Q    Q  2  Q  2  3  0  0
2  S  1  S    S  2  S  2  4  0  0
1  P  1  P    P  1  P  1  5  1  1
2  T  1  T    T  2  T  2  6  0  0
6
0  0
0  1
1  2
2  3
2  4
2  5
Q S T N P M
Macintosh-6:interview Bill4$

————————– Here’s how this started:——————–

Ok- it was whiteboard code and didn’t compile. I’m working on that. Staring with std::vector blahblah  which seems like some really kewl Java/C++ library good stuff. What Kernighan and Ritchie were hoping for.

input:
(M)
|     \
(N) (P)
|     \    \
(Q) (S) (T)
(3 level b tree, M has two children, N and P, and N has two children, Q and S.  P has one child – T.

output:
Q, S, T, N, P, M

typedef struct node {
std::vector <node*> children;  std::string name;
}

typedef nameNLevel {
std::string name;   std::int level;
}

void passThrough( node* n ) {
std::Array namesNLevels;
int level = 0;

recur( n, level, namesNLevels );

int maxLevel = 0;

for (int i=0; i
if (namesNLevels[i].leve l> maxLevel) {
maxLevel = namesNLevels[i].level;
} /* if */
} /* for */

/* note: recursion isn’t getting the data in the order we want… */
/* so, order them before printing. */

for (level=0; level =<maxLevel; level++){
for (i=0; i<
if (atoi(namesNLevels[i].name) == level){  printf( “%s “, namesNLevels[i].name } /* longer but more robust */
} /* for i */
} /* for level */

printf( “\n”);

}

void recur( node* n, integer level, std::Array nsNLs ){
/* its an array, gets passes as a pointer anyhow */
nsNLs.pushback( new nameNLevel( n->name, level));

if ( 0 != n->children.count()) {   /* there are children */
for (int childCount =0; childCount < ( n->children.count()); childCount++ ){
recur(  n->children[childCount], level+1, nsNLs );
/* recursive call- children & next level… */
} /* for int childCount… */
} /* if ( 0!=  */

}

A nice page at IBM regarding recursion:

http://www.ibm.com/developerworks/linux/library/l-recurs.html#

Good stuff!

Cool interview questions


Q – What 3 Unix utilities would you take to a desert island, and why?

A: Find, Grep, hmm, gnuplot. Find and Grep are very capable, deep, and reliable. It would be easier not to have to re-do them myself, whereas sort, ls, df, even ps aren’t nearly as difficult to re-write myself.

Q: You have two strings, needle and haystack. Both are very long- haystack is at least as long as needle, could be longer. Potentially, millions of characters.

Q1: What’s the fastest way to determine whether all the characters in needle are found in haystack? Order doesn’t have to be the same, but if there are 27 ‘A’ characters in needle, we want to know whether there are at least 27 in haystack. And on through the rest of the, say, 8 bit character set.

A: Obviously, the trick here is to NOT do an N * N solution where each character in needle results in a read (or even a partial read) of haystack. Yet, one can’t avoid reading needle at least once. So: make an array with 256 elements, coresponding to character values 0 to 255. Initialize all array members to 0. Read through needle, incrementing the count for each character value when that character is encountered. For example: needle is “needle”. Character counts are:

d: 1
e: 3
l: 1
n: 1

Once needle has been completely read and counted, start reading haystack, and *decrement* the count (but stop at 0)  for each character value whenever one of those characters appears. The read through haystack ends when either all the character counters are “0”, which is success, or when haystack is exhausted AND at least one character counter is greater than zero.

This solution is on the order of 2N + some constant, much better than the N * N obvious technique.

Q2: The A1 technique requires 256 counters of 20+ bits – most likely 32 bit integers. So it requires 1K bytes. How can the job be done with the very least amount of memory, but as long a run time as it takes?

A2: 2, 32 bit integers, and a character, are enough. One integer is an index (indice) into needle or haystack, one is a counter. The character is incremented through all possible character values. For each character value, the count is zeroed, then needle is stepped through, adding one to the counter for every instance of the target character code. After needle is completely counted, the same index is used to step through the locations in haystack, and the integer in the counter is decremented (provided it started off positive) any time the target character is found. But not below 0. If any trial gets to the end of haystack with a non-zero counter value, return a fail and give up. If the counter gets to zero while decrementing, look no further, increment the character, start on the next character.