Every day I'm Eulerin'...

[Dantius]

Since there seem to be plenty of math/science/CompSci people on this forum, I was wondering if anybody else here participated in Project Euler? I just started an account, and I'm already 30 problems in (goodbye weekend!), and let me tell you, the feeling of accomplishment you get for solving it is fantastic- not to mention that you get way, way better at your language of choice when doing it (I'm a Mathematica/Excel/pen and paper guy, BTW).

 

So, am I alone in doing this? How far along is everybody else here?

[Student of Trinity]

Sounds like fun, except that I already have more math problems than I can handle. Happy trails!

[Niemand]

Aran was doing this a while back and sucked me into it, but I had only a short time before work hit me hard and I had to set it aside; I think I've only done five problems.

 

I would like to get back to it, but I already burned up my entire weekend learning to send and receive stuff over the internet with fastcgi and libcurl and tinkering with some template metaprogramming stuff.

[Dintiradan]

Project Euler is on my long list of things I want to try someday, but I haven't gotten around to it. Part of the reason is that I don't want to spend my recreation time doing stuff that resembles my work too much. The other part is that whenever I do want to program in my spare time, there's always something more important to do. For instance, this evening I'm improving some software I wrote for my brother-in-law, a random group generator for his high school math classes, with a few extra bells and whistles. Also, every so often I feel guilty about not finishing some minor projects I said I would.

 

Another thing is that I'm motivated by the algorithm that solves a certain problem, but once I know the algorithm I have absolutely no motivation to solve the problem anymore. For instance, I used to do Sudoku puzzles. At one point in my undergrad, I was learning Prolog, and we wrote a CSP solver. And suddenly, my addiction was cured.

 

Were I ever to do the Project Euler problems, I'd force myself to do as much with pen and paper as possible. My programming skills don't need as much honing as my math skills do. I'd probably get through them faster if I just did brute force programming though. For instance, my first instinct when I see the first problem is "oh, let's just write this atrocious Perl script that loops over all the numbers, check if they are divisible, and then sum if true". After thinking for another ten seconds, I think "oh, I can save time, just loop through the multiples of three and the multiples of five". After a bit more thought, I realize that, hey, I can probably write closed form expressions for the problem, and solve it in one fell swoop. But by the time I get the answer, my original (horribly inefficient) script has solved the problem.

 

C++ aside: Niemand, you've been working with C++ far longer than I have. Is there some way to write a template class, but still split it into .cc and .h files? I think my executable size is ballooning because I've got all my code for template classes inside my header files.

 

(Also, I'd like a magical way to have a pure virtual template function. Also, concepts should have remained part of the new standard.)

[Niemand]

Spoiler, because this is all a response to Dinti's aside and has nothing to do with the thread topic.

Click to reveal..

Originally Posted By: Dintiradan

C++ aside: Niemand, you've been working with C++ far longer than I have. Is there some way to write a template class, but still split it into .cc and .h files? I think my executable size is ballooning because I've got all my code for template classes inside my header files.

Your executable will end up the same size no matter how you split up the code, since every unique instantiation of each template has to be linked in in the end. You can move template definitions out of headers (which will reduce compile time, since only one translation unit will take the hit of having to compile that template) if you can ensure that other TU's don't need to actually see inside the template. A good way to do this is that if you know you'll be using certain instantiations, declare both the template in the header, then implement the template and instantiate it as needed in the implementation file.

 

An example:

Click to reveal..

Code:

// foo.htemplate <typename T>class Foo{private:	T t;public:	Foo<T>(const T& t):t(t){}	T foo();};// foo.cpp#include "foo.h"template <typename T>T Foo<T>::foo{	return(t+5);}//only cases of Foo I expect to ever needtemplate class Foo<int>;template class Foo<double>;

 

Clearly, this won't work if you really wanted to frequently instantiate Foo with a wide variety of parameters; but if you know that your program will only ever need a couple of cases this works.

 

Quote:

Also, I'd like a magical way to have a pure virtual template function.

I can just barely imagine why you might want such a thing, although I never have previously myself. Unfortunately it's not hard to imagine why implementing such a thing would be hellish; a given class could end up with a different vtable in each translation unit, and you would have to either find some way to reconcile them (at link time?) or give up having static vtables. One might, with some work, manage to simulate this by composing one's own vtable structure sort-of dynamically but there are several tricky issues that I haven't tried to think through.

 

Quote:

Also, concepts should have remained part of the new standard.

I know Realistically there were some problems, and though I don't recall exactly what the two differing camps were, I remember that I mostly agreed with Stroustrup's position, but still saw that the other side brought up some important points that didn't seem like they could be ignored. In the end, nobody had a single, cohesive system by which concepts should work that addressed all the problems, so it had to be let go. I'm hoping that by 2016 we'll have been able to resolve this and the next version can have them put in. I think it's going to help that there are now multiple people I know of who are tinkering with implementing concepts and so will actually be able to say what works well and what doesn't.

[Aran]

Yeah, started late in 2009. Wheee!

 

[Metatron]

Well, I was bored during my lab hours so I tried to find the site. I remembered that it was projecteuler.something, but I didn't remember whether it was a .com or a .org. Not wanting to appear foolish, I didn't bother googling. I went directly to the .com, which is apparently a scam site. It's probably a website set up by Dantius to steal bank account information and passwords.

 

Joke's on you, I'm a student. I'm POOR.

[ĐªгŦĦ Єяŋϊε]

there's always overdraft

[Dantius]

Originally Posted By: Metatron

Well, I was bored during my lab hours so I tried to find the site. I remembered that it was projecteuler.something, but I didn't remember whether it was a .com or a .org. Not wanting to appear foolish, I didn't bother googling. I went directly to the .com, which is apparently a scam site. It's probably a website set up by Dantius to steal bank account information and passwords.

Joke's on you, I'm a student. I'm POOR.

If I were to do such a thing, it would be unprofitable to do such a scam on a site populated by games, who ten to be both a) young, and therefore not very wealthy, and tech/scam savvy.

I'd instead try, I dunno, a golfing forum or a stockbroker forum or something where the userbase is older, richer, and less Internet-smart.

[The Mystic]

Quote:

Edit Reason: Dantius Fact # 0-1: I used to make money as a student by hustling people in chess games. Intelligent people have a tendency to vastly overestimate their skill at chess. Must be a vanity thing.

I wish I would've thought of that. In high school, I had a reputation for being a fairly good chess player. Some of my opponents had rich parents, so I could've made a small fortune--or at least enough money to pay for lunch every day.

[Alorael at Large]

That often doesn't work as well if you're in a fixed place with fixed opponents. They won't put up money if they know they can't be you, and they'll know that after a game or two if they didn't before.

 

—Alorael, who thinks there might be more money in the long tail of poorer but stupider people. It's the spam theory, and it seems to work great.

[Aran]

Originally Posted By: The Mystic

Quote:

Edit Reason: Dantius Fact # 0-1: I used to make money as a student by hustling people in chess games. Intelligent people have a tendency to vastly overestimate their skill at chess. Must be a vanity thing.

I wish I would've thought of that. In high school, I had a reputation for being a fairly good chess player. Some of my opponents had rich parents, so I could've made a small fortune--or at least enough money to pay for lunch every day.

For this to have worked, the reputation would have been counterproductive.

[The Mystic]

Well, the reputation wasn't all that widespread until about halfway through my senior year, when it was discovered that I was nearly unbeaten up to that point. Also, even after my reputation was well known, nearly all of my opponents had a bad habit of mistaking me for an idiot who had a decent amount of luck with a chessboard.

 

So yes, the reputation was, in fact, counterproductive to a high degree; either that, or the vast majority of opponents were just that stupid. During the three years when I had a study hall (which was when I normally played), I lost maybe half a dozen games total.

 

EDIT: @Alorael— Even after going down in flames dozens of times, some of my opponents insisted on coming back for more, saying that I would win through either luck or cheating. It wasn't so much the spam theory as the "do the same thing repeatedly in the hope of a different outcome" theory.

[Alorael at Large]

You were lucky in chess? I think perhaps your opponents were missing key pieces of information about the game. metainformation on perfection and completeness, perhaps.

 

—Alorael, who is also baffled by the cheating. It's not very easy to cheat in a game in which you both spend most of your time looking at the board and keeping track of where things are.

[The Mystic]

I don't think it was luck; it was probably more the fact that my opponents had very little (if any) concept of strategy. And it definitely wasn't luck in some of the games; occasionally I played against two or three people at once, and they'd discuss their next move out loud for all to hear.

 

As for the cheating, that would've been impossible, especially since there were usually a dozen or so spectators. I honestly have no idea how I could've cheated, even if I had wanted to. Nevertheless, one of my opponents insisted that I was cheating, and refused to play against me after three consecutive losses.

[Lilith]

Originally Posted By: The Mystic

As for the cheating, that would've been impossible, especially since there were usually a dozen or so spectators. I honestly have no idea how I could've cheated, even if I had wanted to. Nevertheless, one of my opponents insisted that I was cheating, and refused to play against me after three consecutive losses.

it's possible to cheat if you're the only person at the table who knows the rules

[The Mystic]

My opponents knew the rules; in fact, some knew them better than I do. They just didn't know [self-censored] about strategy and refused to admit it.

[Karoka]

I remember in eighth grade, I'd beat everyone in the chess club (I wasn't in the chess club) during lunch, then I would leave sad because the security guard would beat me in 3 or so moves.

[Alorael at Large]

It literally cannot be luck if you're using any normal definition of luck in games. There isn't any at all in chess.

 

—Alorael, who has never won a game of chess in three moves. Four moves is his minimum if you don't count collusion by his opponent to pull off fool's mate.

[Dintiradan]

@Niemand:

Click to reveal..

Splitting up .cc and .h files for template classes: Yeah, I've seen that trick, but I wanted a magical (non-existent) way to do it in general. Mostly, I just hate the huge recompilation times whenever I change my implementation in the header file, but I can often avoid that by making a non-template abstract superclass. Good practice is to program to an interface anyway.

 

Yeah, I know pure virtual template functions are impossible. As for my use case: I've got game playing algorithms that play arbitrary two-player zero-sum games. I've got a Board class that takes X and Y as template parameters, to specify the dimensions of the board. I'd like to subclass Board for specific games, but you can't have virtual functions inside a template class. I can get around this by using has-a relationships instead of is-a relationships, but it's still a bit cludgy. What I should probably look into is making Board not be a template class, and dynamically allocating the bitboard. But I don't know what the performance hit would be like.

 

Times like these I miss the type system in Java. An object's type is itself an object. All classes descend from one class. And generics in Java use type erasure, so you can do a lot of things with generics that templates can't do (at the cost of stuff like template specification, which I never use anyway).

 

Luck in chess:

 

You'd be surprised at how strangely some people define luck in games, even Richard Garfield, who's got a Ph.D. in combinatorial mathematics and has designed many games and thus should know better:

Quote:

This means that by my definition there is no luck in tic-tac-toe between people who know the game. Unless a player is hopelessly distracted, the game will always end in a draw. It also means that there is luck in chess. When I play someone of comparable skill, no one can predict the outcome for certain. Against a more skilled player — even Kasparov — I could blindly walk into a superior line of play, not realizing the long-term implications of my moves.

 

EDIT: Huh, can't figure out what's wrong with my link. Just hover for the full text.

[The Mystic]

Originally Posted By: Karoka

I remember in eighth grade, I'd beat everyone in the chess club (I wasn't in the chess club) during lunch, then I would leave sad because the security guard would beat me in 3 or so moves.

We didn't have a chess club, and there wasn't much interest in forming one.

And don't feel so bad about being beaten in chess by a security guard; he's obviously had more time to learn the game. One of my worst defeats was when I played against one of the teachers. As it turned out, I was way out of my league; I learned shortly afterwards that he participated at least semi-regularly in some local (and possibly state) tournaments. I got crushed in about 15-20 moves.

[Lilith]

i once beat everyone in my chess club but i was wielding a shovel at the time

[Goldengirl]

Originally Posted By: Lilith

i once beat everyone in my chess club but i was wielding a shovel at the time

What where the chess pieces made of that you had to use a shovel to move them!?

[Dikiyoba]

Originally Posted By: Dintiradan

EDIT: Huh, can't figure out what's wrong with my link. Just hover for the full text.

Probably too long or something like that. I broke it into two parts for you, and now it works just fine.

Originally Posted By: Goldenking

What where the chess pieces made of that you had to use a shovel to move them!?

Human chess pieces, duh.

Dikiyoba was never very good at chess in high school. It started out fine, but in half a dozen moves or so suddenly one side had five queens, the other side was preparing to launch an aerial raid, the kings were either safe in their bunkers or fleeing down the hallways, and the pawns from both sides had joined together to go on strike to demand cooler moves.

[Niemand]

Continuing subthread:

Click to reveal..

Quote:

Splitting up .cc and .h files for template classes: Yeah, I've seen that trick, but I wanted a magical (non-existent) way to do it in general. Mostly, I just hate the huge recompilation times whenever I change my implementation in the header file, but I can often avoid that by making a non-template abstract superclass. Good practice is to program to an interface anyway.

Using an abstract base class and a template class which inherits from it is a very common idiom, although I don't know a name for it. (It might be listed somewhere in More C++ Idioms somewhere though. There's some very nifty stuff in there, although the large unfinished swathes are a bit maddening.)

 

Quote:

Yeah, I know pure virtual template functions are impossible. As for my use case: I've got game playing algorithms that play arbitrary two-player zero-sum games. I've got a Board class that takes X and Y as template parameters, to specify the dimensions of the board. I'd like to subclass Board for specific games, but you can't have virtual functions inside a template class. I can get around this by using has-a relationships instead of is-a relationships, but it's still a bit cludgy. What I should probably look into is making Board not be a template class, and dynamically allocating the bitboard. But I don't know what the performance hit would be like.

It's not terribly clear to me why defining the size of the board statically is particularly useful to you; about the only thing I can immediately think of the it might enable would some loop unrolling and the like. Assuming you don't make board objects left and right it should be a problem to allocate the storage on the heap, right?. (And if it is, there's always alloca. )

 

Quote:

Times like these I miss the type system in Java. An object's type is itself an object. All classes descend from one class. And generics in Java use type erasure, so you can do a lot of things with generics that templates can't do (at the cost of stuff like template specification, which I never use anyway).

Being able to construct a type with something other than a type-declaration would occasionally be nice, but I've very rarely found myself desiring to do such a thing. Having everything descend from a single base type has never seemed very useful to me. Using this is frequently frowned on in Java now anyway, and it's only done in a half-baked way, since Java still has primitives which aren't objects. If you really like this sort of thing, though, you can always create your own ultimate base class in C++ and derive everything from it; I've seen various frameworks which do.

 

Java generics, though? Blech! Okay, to be fair I'm not actually familiar with what the fancier features of generics in Java can do, but my impression was always sort of the reverse; generics felt wimpy and underdeveloped. . .

 

(Watch in awe as I try to teach myself Java generics in order to critique them, thus making a total fool of myself, before your very eyes!)

 

Wildcards appear to do mostly what concepts do in C++, except that in C++ so far concepts exist only in documentation for humans and in the deductions made automatically by the compiler during template parameter substitution. It would be nice to have formal syntax for them, but they function today (if a bit clumsily, at times) without it.

 

Code:

void printCollection(Collection<?> c) {	for (Object e : c) {		System.out.println(e);}}

is roughly equivalent to:

Code:

template <typename T>void printCollection(const T& c){	for(const typename T::value_type& i : c)		std:cout << i << std::endl;}

(I added the requirement that the collection have a member type that describes what type it holds, but hopefully you'll agree that that's pretty trivial, given that C++ containers are homogeneous by convention.)

 

And while I can't do this in Java:

Code:

Collection<?> c = new ArrayList<String>();c.add(new Object()); // compile time error

In C++ I can:

Code:

template <typename T>void addNewToCollection(T& t){	//Look what I can do with types that I haven't erased!	t.push_back(typename T::value_type());}

 

Bounded wildcards achieve the same thing as enable_if in C++. Sadly, the syntax surrounding the use of enable_if is ungodly, but it does work, and once you become familiar with it, it actually can become possible to read.

Code:

template <typename T>void onlyDrawShapes(T& t,         typename boost::enable_if <	    boost::is_base_of<Shape, T >, 	    void>::type* = NULL){	t.draw();}

In C++, though, I can write an enable_if with any condition I want, not just one based on inheritance (is_enum, is_function, is_floating_point, has_trivial_constructor, is_convertible, just to pick some interesting ones from those available in boost). Template specialization is a powerful tool, since it enables things like static selection of different variants of a function depending on arguments types, and combining it with enable_if allows for some very nifty stuff. Basically, it gives you another mechanism akin to function overloading.

 

Above, I wrote addNewToCollection in terms of push_back, which works for (using namespace std; ) vector, deque, and list, but not set or queue. With partial specialization I can fix that:

Code:

template <typename Element, typename UnderlyingContainer>void addNewToCollection(std::queue<Element, UnderlyingContainer>& t){	t.push(T());}template <typename Key, typename Compare, typename Allocator>void addNewToCollection(std::set<Key, Compare, Allocator>& t){	t.insert(Key());}

With more work (using enable_if) I could probably fix this generically for any type which has a push member function, and any type which has an insert member function.

 

Here's one that's actually somewhat useful (it might be overkill, but it was more fun to teach myself to do this than to study the integral promotion rules):

Click to reveal..

Code:

//A helper function for safely testing whether a particular value of some source integer type //can be losslessly converted to another target integer type////Example:// To test whether the current value of an integer of type int16_t can be safely converted// to uint8_t://    int16_t someVar;//    ...//    if(inRange<uint8_t>(someVar))//        //someVar can be safely converted to uint8_ttemplate<typename TargetType, typename SourceType>typename boost::enable_if_c <!std::numeric_limits<SourceType>::is_signed,bool //if the enable_if succeeds, this is the return type>::typeinRange(SourceType i){	return((boost::integer_traits<TargetType>::const_max>=boost::integer_traits<SourceType>::const_max) 		   || (i<=SourceType(boost::integer_traits<TargetType>::const_max)));}template<typename TargetType, typename SourceType>typename boost::enable_if_c <std::numeric_limits<SourceType>::is_signed && !std::numeric_limits<TargetType>::is_signed,bool //if the enable_if succeeds, this is the return type>::typeinRange(SourceType i){	if(i<0)		return(false);	return((std::numeric_limits<TargetType>::max()>=std::numeric_limits<SourceType>::max()) 		   || (i<=SourceType(boost::integer_traits<TargetType>::const_max)));}template<typename TargetType, typename SourceType>typename boost::enable_if_c <std::numeric_limits<SourceType>::is_signed && std::numeric_limits<TargetType>::is_signed,bool //if the enable_if succeeds, this is the return type>::typeinRange(SourceType i){	if(i>=0)		return((boost::integer_traits<TargetType>::const_max>=boost::integer_traits<SourceType>::const_max) 			   || (i<=SourceType(boost::integer_traits<TargetType>::const_max)));	return((boost::integer_traits<TargetType>::const_min<=boost::integer_traits<SourceType>::const_min) 		   || (i>=SourceType(boost::integer_traits<TargetType>::const_min)));}

 

And let's not forget: Templates are turing complete. That just gives rise to too many wonderfully horrible possibilities to possibly be able to forgo.

 

Am I missing something? I actually thought before skimming that document that there were more things Java generics did. Were more added in 1.6?

 

While I'm ranting, some other parallels between recent Java and C++ additions which I notice:

• The new auto is just the reverse of the diamond operator. (It seems superior to me, in fact, since it can also be used in many situations besides merely avoiding repetitively stating template parameters.)
• Language support for collections in Java is targeted at the same problem as C++ initializer lists. Anyone who wants to can write a class which can be constructed from an initializer list; it isn't clear to me whether the Java syntax feature has the same underlying generality.
• Automatic Resource Management - Java is still attempting to correct for the lack of deterministic destructors.
• Binary literals in Java; user defined literals in C++

Unsurprisingly, both sets of language designers are discovering the same sets of problems, and solving them in similar ways.

 

Um, yeah, chess! I'm no good at it.