top | item 46703744

(no title)

compsciphd | 1 month ago

years ago on an ACM programming contest we had a problem that was given a starting and ending position on a chess board, find the minimum # of moves it takes for a knight to go from one to the next.

the proper way to solve is this via breadth first search. while my team was working on other problems, I basically solved all possibilities by hand. (i.e. the it was basically just a delta-x/delta-y matrix with a few exceptions if the knight would have to go off the board).

As you had (have?) less computer than team members, when I finally got a chance to a computer, instead of programming out a breadth first search, I just inputted my hand calculated matrix with some scaffolding and submitted quickly and got a validation message quickly back.

I still wonder if that was the fastest turnaround time for a single problem they have seen :)

discuss

order

No comments yet.