The topic where you can tell how you liked the challenge, & how you solved it
I didn’t like it.
It was like solving a sudoku game. No programming skill needed. No relation with matrix theme.
I went the logic way instead And it worked quite nicely( I just took into account too late the “no isoslated island” rule to pass advanced tests ).
To finnish my program to top 100% completion, I just have to add backtracking if and only if I have no other solution to solve the problem ( multile choices tests ).
That’s the intended way, good job
I quite enjoyed this problem and discovering new strategies/tips to solve it.
I’m not sure what you mean by “the logic way”, but if you mean heuristics to detect forced moves, well… sure, but, it only goes so far. To solve the last tests, you need exploration. And since a well-designed exploration will solve easy tests as well, you can pretty much drop the logic way altogether
Seriously, yes. It’s too much detailed and basically gives away the whole solution.
Honestly, i think that’s okay, because you actually need to implement it, even if it’s quite detailled, some specific detail are not explained and need some skills to code it.
I really liked this contest, but then it was my first
It was a bit sad, that I only had very limited time, but I decided to try anyways. I got the logic part pretty much done and submitted without trying to get backtracking/exploration working (I was late already anyways).
I only wish I would have realized that my logic not to connect two 1s or double-connect two 2s, needs to check if those two nodes are the only nodes for the “back to the basics” test-case…
Well, actually I want to rewrite my post this morning
I just didn’t have enough time to rewrite yesterday, haha.
Let’s do this, and i’ll clear my post !
Well, I don’t a hundred percent agree for this (sorry ).
When I saw the 2nd puzzle in contest, I was quite surprised because I had seen this puzzle before (a long time ago). But the main point is: solving this puzzle by hand is totally different than solving by program.
The best example is when dealing with “multiple solution” puzzle. The 2nd puzzle (and also sudoku) is often made with a unique solution, therefore we sometimes found some tricky tricks or maybe some good counter-examples when we solved it by hand. I think, there are too many tricks that can be found when solving this puzzle. So, if you try to think programmatically there is always be a nice way to solve this without acknowledging all the tricks like on this site : [http://www.conceptispuzzles.com/de/index.aspx?uri=puzzle/hashi/techniques25] (as ronlobo stated on “APU: Improvement Phase puzzle discussion”)
My strategy (I hope no hard-spoiler this time) :
- The board is actually relative small (1 <= height, witdh <= 30), I thought the puzzle can be solved by clever bruteforce and also nice pruning (and in the end I added some heuristics). The bruteforce coded recursively.
- The states for my recursive are coordinates x and y.
- If there is no node or 0-node in (x,y), skip this coordinates (call next function).
- If not a.k.a (1-8)-node in (x,y), then check its horizontal and vertical neighbours (very similar to 1st puzzle). Check if this node can be decreased until 0. And then, try all possible links for this node and call next function.
- When trying to link, make sure to decrease the linked nodes.
- If recursive ends, there is going to be a final check.
- The final check has to make sure that : The board doesn’t contain (non 0)-node, the graph are connected, and the links are not crossing each other (well, it is quite tricky but actually easy ).
And… it’s done!
hi there, I tried this problema like a CSP (Constraint Satisfaction Problem), every possible link are my variables and each node represent a constraint, plus other constraints like “links can’t cross other links” and “all nodes must be connected”, the simple way to solve this kind of problems is backtracking, however it takes a lot of time for most tests so it just failed. Then I tried with “hill climbing” approach more specifically with a genetic algorithm taking a population between 10 and 40 and a mutation rate of 0.3 and 0.8 but one more time, there is not enough time to find the solution for the most complex tests, finally I get back to the backtracking algorithm but this time I added an evaluation function to see if each time I make a variable assignment this violates a constraint, only the "all nodes must be connected " constraint is checked at the end, it works perfectly, I got 100% , lamentably I did not follow this approach in the contest and there I only could solve the basic tests.
Ooh so that’s why this test was here (back to basics) ! I was wondering how could one pass the previous tests and fail this one…
@athin : First of all, thanks for taking note of my previous comment. Also, if I judged that your first post was spoiling the problem, it is not only because it was a detailed solution, but also a very good solution. So I’m not surprised, watching the report this morning, to find that you arrived first at the contest ! It is possible that your algorithm might simply be the most efficient, aside from minor improvements.
Then, a kind of paradox happened : after you removed your algorithm description, an admin contested that it was spoiling. The question was worth debating, but there was no way to debate it since it was not visible anymore.
So, instead, why not debate this one ? To me, it looks a lot like previous description, maybe with a little less detail. Yes, there are more gaps, but it doesn’t look too hard to fill them. But I’d be interested to know what others think on this matter. Maybe it could be an interesting discussion
Btw, Mr. @SaiksyApo requoted my previous solution and then removed it again after I rewrote it.
But it will be very interesting to discuss and debate this “issue” I think
Hmmm… I wonder what people think about this solution if it will be the first time for him to see the solution (not the original one).
In this kind of topic, we want spoil for sure. (It’s not linked to the puzzle APU).
So if someone want a solution, I prefer that he found a well formatted post about the strategy to implement here instead of a source code found on GitHub or whatever.
It would be nice to be able to see the code of other contestants once the challenge is over, for educational purposes. Unless I’m missing something I can only see my own “report”.
Since the challenges have been added to the games pool, maybe you could at least allow the people who have actually participated to see what others did.
It’s on the roadmap of the team, they said they’ll do it eventually
Well it’s already obvious that people who are participated in contest are getting huge amount of coding points, even people who was not very successful. And this gap for people who have joined not so long time ago actually insuperable. So why we can’t go little bit further and introduce incentive system for people who participated in contest but didn’t completed in time for 100%. Let this people take some more points if they finally completed this task but were little bit late.
Because all i see is that a lot of people just started to ignore this task because challenge is already ended. As i think that every thing you’ve started should be done till the end no matter what. Isn’t it a right way to do things?
You can still finish the contest (and earn points for doing so) as the 2 puzzles are now in the solo games section. For most people, solo puzzles even worth more points than they earned with the contest.