This past weekend, Lutron hosted the 2nd Annual Lehigh-Lafayette Programming Competition, which Lehigh ended up winning. This year’s problem was quite interesting and the range of solutions, at least from Lehigh’s side was just as interesting. The problem consisted of Battleship on a 50 by 50 board, with the goal of minimizing the number of shots fired to win the game, with shots to the same location twice counting against your score. Lutron provided the trivial solution of brute forcing the solution by firing in every position.
I hate to say this but it took much longer than I expected to get all the provided code up and running in my environment, as NetBeans didn’t seem to want to add the provided jar as a library for compilation. However, once I got this running I wrote a helper function to handle firing, which would ignore any shots to the same location. I also included checks on if the game was won here to prevent any further shots from being fired. Once this was done, I moved to a simple checkerboarding approach to find each ship, and then I wrote a method to expand on any locations that returned a hit, to sink the ship. This method was trivial in the sense that it expanded the location where the ship was found and expanded in both horizontal and vertical directions to get an idea of the direction of the ship. From there I continued firing in any direction that had a hit in the original phase until I got a sunk or a miss. I then expanded the last point if it was a hit, to check if there were any other ships coming off the end.
Once the sinking code was up and running, I modified my checkerboarding approach to start with larger squares then hone in smaller until the game was one. As a safety check, I would then brute force a solution to guarantee a win to prevent disqualification if a solution was not already found.
Given more time, I would have split the board much better than I previously did. Once this stage was done, I would have used probability tables. I think using a total of 4 probability tables, one for each length of ship, would have given me a very good solution. The table would store the number of times that particular ship could be in a location. By summing all of the tables, the shots with the highest probabilities could be taken, based on what ships were left. I will be attempting to get this solution to the problem up and running to see how it compares against some of the others.