Mini coding competition

sick...count me in! [:D]

What would be involved in this coding comp?

Ok, here's the challenge: Demonstrate the best use of the STL. This will be in the form of a simple program that does a small task while taking advantage of the STL. Here is an example that reads white-space delimed input into a vector:

[code]
#include
#include
#include
#include

using namespace std;

int main(int argc, char** argv)
{
// variables used
vector output;

// push back strings from cin, splits on whitespace
copy(istream_iterator(cin), istream_iterator(), back_inserter(output));

// output to screen
copy(output.begin(), output.end(), ostream_iterator(cout, "
"));

// wait for user to hit enter before closing
cin.clear(); cin.get();
}
[/code]

Programs will be judged on code size (smaller is better), code elegance (keep it clean), and functionality (more bang for your buck). Entries close midnight 31st of December. You may have up to 2 entries. At this point, it will just be me judging. What I say goes.

I see a problem in having prizes for this
This seems soemthing that's probably impossible to judge effectively.

well, then...count me out im afraid...

at this point in time my brain is unable to understand much of the STL...

Oh come on! This is just a fun little comp to help people with STL. The prize is a bonus. I'll post up some examples if that will help some people. Do not be affraid of the STL!

I don't fear the STL, but I've got two games about pirates that need to be made, tons of research and no time.

I'll have a think about something to enter, will be good to catch up on some STL.

i might still enter, i just have to do some research and think of something to make...

I'm in. Can we agree that many of Microsoft's (older) compilers support the STL in a very very bad and nonstandard way, and that if needs be the code can use STLPort, or GCC or similar?

-d

I don't suppose it should matter which STL implementation you use, as long as it's standard conforming code, I guess this would mean no extensions. (And a reasonably new compiler.)

well, after only a short amount of tinkering, i think i can understand how the STL works...

but the competition seems very general, was there anything specific you were looking for? if you could post some more examples that would be helpful.

If i get some time before December 31st i'll give it a crack.

OMG, the possibility of getting a free game! I'm in. Hopefully i can get think up something in the next couple of weekends. Do you want us to just post our entries in this thread?

I put a thread up in the competition section for entries.

http://www.sumea.com.au/forum/topic.asp?TOPIC_ID=2575

It was mentioned that it's not actually a programmer challenge,
but I don't know how to delete the thread. Oops!

Here's a quick one to get the ball rolling, a simple replacement for the standard STL sort algorithm:

[code]#include
#include
#include
#include

using namespace std;

template void merge_sort(T &data, P predicate)
{
T::size_type size = data.size();

if(size == 2)
{
// A single pair, put them in order
T::iterator a = data.begin();
T::iterator b = data.begin() + 1;

if(predicate(*b, *a)) swap(*a, *b);
}
else if(size > 2)
{
T::size_type mid = size / 2;

// Split the data into two halves
T a(data.begin(), data.begin() + mid);
T b(data.begin() + mid, data.end());

// Sort each half individually
merge_sort(a, predicate);
merge_sort(b, predicate);

// Combine the two sorted halves
merge(a.begin(), a.end(), b.begin(), b.end(), data.begin(), predicate);
}
}

int get_random_int()
{
return rand() % 100;
}

int main(int argc, char **argv)
{
static const int size = 20;

// Generate a random unordered data set
vector data(size);
generate_n(data.begin(), size, get_random_int);

// Test our Merge Sort
merge_sort(data, less());

// Display
copy(data.begin(), data.end(), ostream_iterator(cout, " "));
cout << endl;

return 0;
}[/code]
To me the best thing about STL is that it gives you a reliable base on which you can easily experiment with different ideas. It abstracts you just enough that you can concentrate on optimising what's really important, the algorithms rather than individual lines of code. I went for easy to read but my first performance modification would be to make it sort in place to reduce the amount of array copying going on in each recursion. After that I suggest changing to a different algorithm, haha!

• Clean easy to read code.
• All trivial tasks covered by standard STL components.
• Works with any container providing random access iterators.
• Works with any type your predicate can compare.

I tested this briefly on VC++ .Net, apologies for any bugs or incompatibilites.

quote:Originally posted by kalin

I put a thread up in the competition section for entries.

http://www.sumea.com.au/forum/topic.asp?TOPIC_ID=2575

It was mentioned that it's not actually a programmer challenge,
but I don't know how to delete the thread. Oops!

BALETED!

Here is an example that reads words from a file into a set (which is sorted) and outputs them to the screen.

[code]
#include
#include
#include
#include
#include
#include

using namespace std;

class Word
{
private:
string chars;

public:
friend istream& operator>> (istream& is, Word& ch );

operator const string& ()
{
return chars;
}

bool operator < (const Word& rhs) const
{
return chars < rhs.chars;
}
};

istream& operator>> (istream& is, Word& w )
{
w.chars.clear();

// dump non-alpha chars at the begining
while (is.good() && !isalpha(is.peek()))
{
is.get();
}

// get all the alpha chars
while (is.good() && isalpha(is.peek()))
{
w.chars += is.get();
}

return is;
}

int main(int argc, char** argv)
{
// variables used
set output;
ifstream fin((argc > 1) ? argv[1] : "input.txt");

// insert Words from file stream
copy(istream_iterator(fin), istream_iterator(), inserter(output, output.begin()));

// output to screen
copy(output.begin(), output.end(), ostream_iterator(cout, "
"));

// wait for user to hit enter before closing
cin.clear(); cin.get();
}
[/code]

edited:
BALETED!
...I mean fixed closing code tag

How do we enter the competition?
Just post the code up here on the forum?

I'll set something up next week, it will probably be by email.

Here is a simple file copying program.
Usage: "copy output.ext input.ext"

I'll probably try and think up something more complicated later,
but this is a nice simple example of how nice STL is to work with. :)

[code]
#include
#include

int main(int argc, char** argv)
{
if (argc >= 3)
std::ofstream(argv[2]) << std::ios::binary << (std::ifstream(argv[1]));
return 0;
}
[/code]

kalin needs more {}s

Okay, here's one. It does a search and replace on a given text file:

[code]
#include
#include
#include
#include
#include

using namespace std;

/*
redwyre's mini coding contest

Usage:
replace

Replaces all occurances of with in
*/

ofstream fout;

void putwords(string s)
{
// Put words into file
fout << s + " ";
}

int main(int argc, char **argv)
{
list words;
ifstream fin;
string s;

if (argc < 4)
{
cout << "Usage: replace " << endl;
return -1;
}

// Open file
fin.open(argv[1]);
if(!fin)
{
cout << "Couldn't open file " << argv[1] << endl;
return -1;
}

// Read all words into list
while(!fin.eof())
{
getline(fin, s, ' ');
words.push_back(s);
}

// Close input file stream and open output file stream
fin.close();
fout.open(argv[1]);
if (!fout)
{
cout << "Couldn't open file " << argv[1] << endl;
return -1;
}

// Replace oldstring with newstring
replace_copy(words.begin(), words.end(), words.begin(), string(argv[2]), string(argv[3]));
for_each(words.begin(), words.end(), putwords);

fout.close();

return 0;
}
[/code]

To submit your entries, feel free to post them here, but make sure you send them to me via email: xxx with the subject starting with "[Sumea]" I'll try and get everything sorted and announce the winner before the end of January.

[code]
//cache invert sqrt class and testbed

#include
#include
#include
#include

typedef float real;
typedef signed int s32;
typedef unsigned char u8;

struct TCommonCache_InverseSqrt
{
bool operator()(const float lhs, const float rhs) const
{
return (lhs < rhs);
}
};

class CCommonCache_InverseSqrt
{
public:
~CCommonCache_InverseSqrt(void);
bool Clear(void);
bool GetInverseSqrt( const real in_square, real & out_root);
private:
typedef std::map< real, real, TCommonCache_InverseSqrt> TRealRootMap;
private:
TRealRootMap m_root_map;
};

CCommonCache_InverseSqrt::~CCommonCache_InverseSqrt(void)
{
Clear();
return;
}

bool CCommonCache_InverseSqrt::Clear(void)
{
m_root_map.clear();
return true;
}

bool CCommonCache_InverseSqrt::GetInverseSqrt(const real in_square, real & out_invert_root)
{
TRealRootMap::const_iterator iterate;
real root;
bool ok;

ok = true;

if (ok)
{
ok = (0.0F <= in_square);
}
if (ok)
{
iterate = m_root_map.find(in_square);

if (iterate == m_root_map.end())
{
if (in_square == 0.0F)
{
root = 0.0F;
}
else
{
root = sqrt(in_square);
}

if (root != 0.0F)
{
out_invert_root = (real)(1.0F / root);
}
else
{
out_invert_root = 0.0F;
}

m_root_map[in_square] = out_invert_root;
}
else
{
out_invert_root = iterate->second;
}
}

assert(ok);

return ok;
}

s32 main(s32 argc, u8 ** argv)
{
CCommonCache_InverseSqrt invert_sqrt_cache;
real input_number;
real invert_sqrt;
bool loop;

printf("CCommonCache_InverseSqrt testbed: David Coen 041230
");

loop = true;
while (loop == true)
{
input_number = 0.0F;

printf(" please input a number (zero to exit)
");
scanf("%f", &input_number);

if (input_number != 0.0F)
{
invert_sqrt_cache.GetInverseSqrt(input_number, invert_sqrt);
printf(" invert square root is %f
", invert_sqrt);
}
else
{
loop = false;
}
}

return 0;
}
[/code]

ONE DAY LEFT!!

quote:Originally posted by davidcoen
[code]
bool CCommonCache_InverseSqrt::GetInverseSqrt(const real in_square, real & out_invert_root)
{
TRealRootMap::const_iterator iterate;
real root;
bool ok;

ok = true;

if (ok)
{
ok = (0.0F <= in_square);
}
if (ok)
{
iterate = m_root_map.find(in_square);

if (iterate == m_root_map.end())
{
if (in_square == 0.0F)
{
root = 0.0F;
}
else
{
root = sqrt(in_square);
}

if (root != 0.0F)
{
out_invert_root = (real)(1.0F / root);
}
else
{
out_invert_root = 0.0F;
}

m_root_map[in_square] = out_invert_root;
}
else
{
out_invert_root = iterate->second;
}
}

assert(ok);

return ok;
}
[/code]

A little constructive criticism. There are a few ways that I think you can improve your code.[;)]

After performing the following steps:

1. remove unnecessary variables and redundant checks
2. use ternary operators where appropriate
3. use a tolerance value (EPSILON) when comparing floating point numbers to avoid precision errors
4. a little re-ordering
5. recognise that it always returns true and make the function void
6. add comments!!!

The code above appears to reduce to:
[code]
void CCommonCache_InverseSqrt::GetInverseSqrt(const real in_square, real & out_invert_root)
{
TRealRootMap::const_iterator iterate;

// assert that a real root exists
assert(in_square > EPSILON);

// some comment
iterate = m_root_map.find(in_square);

// some comment
if (iterate != m_root_map.end())
{
// some comment
out_invert_root = iterate->second;
}
else // some comment
{
// output inverse of root
out_invert_root = (real)(1.0F / sqrt(in_square)));

// set inverse value of root in map
m_root_map[in_square] = out_invert_root;
}
}

[/code]
The EPSILON checks may be unnecessary if the "real" class (template?) handles precision checks (I wasn't sure, I usually code in C).

Update: I got rid of a ternary operator and the check that the root is valid. If in_square is greater than a well-conditioned threshold (EPSILON), the root should be valid... I think that this is a reasonable assumption...

//Display Hello Message
#include

using namespace std;

int main (void)
{
cout << "Hello World" << endl;

return 0;
}

LOL USF! That effort earns a prize in my book [:D]

Hehe ? USF ? first you bring us programmer art, and now artist programming! Brilliant!