So Dang Close To Perfect Score on Travelling Salesman Inverted Challenge

Got some code to yield paths with a score of 588, literally 1 road away from the perfect score (which is evidently achievable base on the leaderboard for the problem).

I've tried quite a fair amount of ideas, which got increasingly better scores on it, but I think that last road is going to need a different strategy.

Towards the end I mainly tried out some ideas, ran them for maybe 20 seconds and abandoned them if they didn't look like they were going to get the perfect score (based on the program output as it's trying stuff).

I'm not throwing in the towel yet, but this problem has beaten me for tonight, and I should get some sleep :P (it's 5:33 AM for me as of writing this)

It's fine to not necessarily have a great solution to your own challenge. If the best solution was obvious it wouldn't be a challenge :P

I think it is kind of unfortunate that we aren't able to share ideas so much or show each other our attempts at these challenges, as these challenges would probably have more interesting discussion than typical problems. Of course this can't be, because obviously people could then just copy each other's solutions.

On the color cubes one, that one certainly looks even tougher. On brief inspection of it though, I see an obvious way that you can achieve a score of at least 9,221,365. Which is better than the 4 lowest scores on that challenge. I guess off the top of my head, I think I would go about it by maybe having a genetic algorithm with some modifications...

I don't compete on CodeForces or TopCoder, and well not any other site really.

The sites I've used are...

• https://projecteuler.net -> Did 108 problems from this site. I think its a pretty fantastic collection of problems. But its been 2 years since I last did any problems from it.
• https://codingbat.com/java -> I've done all of the problems(there are 317) from this site. Though they don't get too complicated.

I do recall signing up for other sites and doing some problems from them (such as the CodeChef one you found), but I think I had quickly lost interest or got distracted and went on to something else.

Most of my experience/intuition comes from

• My own exploration of math/programming
• Computer Science coursework at UCSC
• Taking some math classes for fun at UCSC. Right now I intend to turn it into a double major though.
• People asking for my help studying for their midterms/finals
• People asking for my help understanding the concepts they needed to do their assignments in Computer Science and Math classes.
• Discussing with professors directly after class or during their office hours with questions and ideas inspired from the course content, if any.
• Watching a lot of random youtube videos relating to science and math.

Lots of emphasis on the first of these: "My own exploration...". Many things I do in my life feed back into my own personal exploration, which I carry out with pencil and paper. A fond memory of mine was when I was taking Geometry, and the teacher had noted that there were infinitely many pythagorean triples. It sounded like a pretty incredible claim, and I manually found a fair amount of triples on paper and tried to look for a pattern. Fortunately, at some point I decided to say "OK, what if I just assumed that the long side of the right triangle is exactly 1 larger than one of the other sides". This leads to x^2 + a^2 = (x+1)^2, which leads to a^2 = 2x+1 with a little bit of algebra. Then I was like, hm, 2x+1 can be any odd number... and a^2 can be odd if a is odd... then we can just get a pythagorean triple by picking some a that is odd and solving for x,x+1. I showed this to the teacher and he verified that the idea works :). I think that may have been the beginning to where I understood the math we were being taught is not just about following a procedure to arrive at an answer, but you can also make discoveries (or rediscover things independently).

I think of this self exploration of things I find interesting to be an significant part of my life and a big reason for the success that I've had. I go through at least 3 reams of paper each year.

On that note actually, the "Easter Eggs" problem has provided an interesting thing to explore. I haven't completed the problem yet because although there is a simple brute force solution that has O(2^n) complexity, I figured out that actually you can do it with a polynomial time algorithm, but I gotta work out the kinks in the implementation of the algorithm I thought for it. Perhaps in a similar way to how some problems on the site have an "Advanced" version, this one could too?

Anyways, I think I might eventually visit the TopCoder or CodeForces or other sites that have competitive programming going on, but for now I'll finish up what's on this site first, try to get #1 in the rankings, and maybe suggest some problems already, (I have some ideas for some that might be interesting, but this post is long already, I'll show you them another time), and if new problems pop up on this site I'll come back and do those too :P

one of the tops had solution which just measured percentage of some color... and it gave about 75% match

That's pretty funny. Kind of in a similar vein, I think I've also heard that a lot of the time, a simple Bayesian based algorithm outperforms other overly complicated approaches that some people come up with.

but it looks like you are just the man for this :)

I'm flattered. I'll make sure to check it out eventually since you highly recommend it, but perhaps not just yet :P

One of my school teachers told "programming couldn't be taught, it only could be learnt"

Unfortunately, this does seem to be the pattern that I see. Some try to learn programming and... just don't get it. But I want to believe that this is not the case. I want to think that, in general, anyone can do anything if they just work hard enough at it. Perhaps it is just that most people don't try hard enough, but I know of a couple of people that have tried very hard with limited success.

Another pattern I notice, in university, is that some people have a weak math understanding and for the algorithms class in particular it makes it very very hard for them.

I also feel that a lot of online courses for programming are unsatisfactory. One in particular comes to mind is the codeacademy course for Java, which I have found to be very bare bones (though I haven't checked it in years, I reckon it hasn't changed).

I hope to one day curate and organize a good collection of online resources (and create parts of it as well) that someone with no programming experience and little interest in math can have their curiosity sparked and familiarize them with ideas and intuition that can lead to a point where things click and they'll be able to start exploring for themselves, and figure out how to teach themselves as well.