@JohnRennie Hi

@Dante hi :-)

Morning!

I have about half an hour before I need to start work. What did you want to ask?

Okay, gimme a couple of minutes till I comment the code

codechef.com/DEC19B/problems/BINADD

Ready?

OK

copied?

I had flipped the strings to make calculation easier

Got it, yes.

I know it ain't efficient, but currently it's enough for me even if it passes 2 subtasks

So what are you asking?

The code isn't getting accepted

Wrong answer error

No idea why

This would take a while And I need to start work now I'm afraid.

As I mentioned Monday mornings are very busy for me.

Oh...okay.

@JohnRennie yes you did

@Dante hi. I've finished work but I guess it's 3 p.m. in India so too late.

Hey, @JohnRennie are you fine with simple algorithms?

Like Depth-first search, breadth-first searches?

To be honest I have no formal training in algorithms, so the names you mention I have never heard. That doesn't mean I don't know the algorithm as I may have encountered it under an other name.

Okay. I have given two coordinates of 8 * 8 chessboard, I have to find the path length of the shortest path a knight would have to travel from point 1 -> point 2. Would it be more efficient to first explore a particular path or explore all path upto a particular depth? I have some feeling that former is better, but I am asking as I am implementing these for the first time, and I guess it would take a lot of effort, so I find it slightly reasonable to ask.

At each step there are 8 moves a knight can make so a brute force tree search is going to scale as 8^n, which is a bit scary :-)

Not always, only if current position of the knight is in smaller central 6*6 chess board, but yes, it would be.

I would be inclined to use some form of weighting to prioritise which steps to treat first e.g. a step towards the target should be prioritised over a step away from the target.

But that would make the short U or V type path harder to find, won't they?

U or V type path? Those are terms I don't know.

Oh, sorry, the terms were just invented. :) From those I mean moves like e5->c4->d6 , the point that I wanna make if my starting point is e5 and if I prioritize farther point to the goal as a low one, here c4 being relatively father, would have low priority.

@AjayMishra I think there are two separate strategies:

You'll have a small number of known special cases e.g. when the end square is immediately next to the current square you have known optimum strategies. So you don't need a tree search for these.

You'll only need to do a brute force search when the current and target square are far apart, and in that case prioritising moves in the direction of the target square probably works well.

I solved the question by almost the same method. Thanks, though.