The winners of the Shadows of the Knight contest, Gangrene and MockingHawk, share with us their insights about their code and strategies. And we also have a special guest’s contribution: kameleono, who ranked first in Scala, also sent us his code review. Thanks a lot to the three of you!
Gangrene’s Debrief
(1st place on the podium | France | Python | 1:34:48)
For the first task, Batman already knows the direction in which the hostages are to be found. The best way to reach them as quickly as possible is thus, with each turn, to divide the search-zone in two by going to the middle of the zone.
To do this, I started with two one-dimensional tables, showing all rows and columns available.
With each new turn these two tables are recalculated, and the average value is returned.This choice is not optimal in terms of time of calculation, because I was only able to use 4 variables xmin,xmax,ymin,ymax to define the field of my search.I made this choice because Python allows me to very easily manipulate the tables (lists), and to free myself from rounded calculations, which are a real source of error.In the second task, Batman no longer knows in which direction the hostages will be, but only knows if he’s getting closer or more distant from them.
As the example from the instructions shows, the search-zone can also take the shape of a polygon defined by our movements and the results obtained. In practice, it is not – or not very – useful to play with such a polygon. I decided to keep to the same system as in the previous exercise, with two lists of integers.
As the instructions no longer gave a direction to follow, I searched coordinate by coordinate: first X, then Y.
I thus begin with the X.
In the same manner as the previous exercise, one looks intuitively to divide the field of search into two.
The equation to obtain the new position is thus x_new = x_max + x_min – x (x_min and x_max are the minimum and maximum values calculated, and not 0 and W-1).
There is a problem however: with this calculation one can jump outside of the building and… die! This problem is easy to resolve: it is enough to bring oneself to 0 or to x_max. But this creates a second problem: the space is no longer divided into two equal parts.
This, the organizers of CodinGame did indeed notice, and they incited the joker to place his hostages at the extremities of the building in several test cases.
The solution that I found is to divide Batman’s movement by 2 when he finds himself at the edge of the building.
In this manner, I achieve a sort of equilibrium: when he should jump out of the building and he stops at the edge, the search-zone is reduced by only a little, but when he sets out again from the other side, he travels less far than he should, and thus the search-zone is reduced by a larger chunk (if the hostages really are close to the edge).
I thank the CodinGame team for this challenge, which yet again caused my neurons to overheat. One can’t ask for more.What’s more, I was able to perfect my knowledge of comics, since I now know that Gotham City has buildings of 8000 floors (test 8 of exercise 2)! When on IRC I learned that the CodinGame team wanted to read my code, and I was ashamed. Indeed, it was not commented and contained some useless ends of code and some debugging attachments (I really wanted this PS4!).
So, here’s a cleaned and commented version of my code (in English). The gist is the same as the one used for the competition, but I moved a section towards the function get_next() for readability (and less redundancy in the code).
import sys
W,H = [int(v) for v in raw_input().split()] int(raw_input()) # number of available jumps. We don't need that X0,Y0 = [int(v) for v in raw_input().split()]
X = X0 Y = Y0
TX = range(W) TY = range(H)
def set_warmer(X0,X,Y0,Y): """ Reduces available values in TX or TY Remaining values are closer to X than to X0 or closer to Y than to Y0 """ global TX,TY if X != X0: TX = [v for v in TX if abs(v-X)<abs(v-X0)] else: TY = [v for v in TY if abs(v-Y)<abs(v-Y0)]
def get_next(v, tab, vmax): """ Compute next coordinate from current one and available solutions v : Batman current position (X or Y) tab : available solutions (TX or TY) vmax : max possible position, we don't want to kill Batman """ res = tab[0]+tab[-1]-v
# Make sure res != v if v == res: res += 1 res = min(max(res,0),vmax)
# If we are currently on the border of the building, we half the distance if v==0 or v==vmax: res = (res+v)/2
# Make sure res != v if res==0: res=1 elif res==W-1: res -= 1 return res
while 1: # X and Y are new position # X0 and Y0 are previous position # TX and TY are remaining possible solutions # Read information from standard input line = raw_input()
# If we got the position, just move! if len(TX)==1 and TX[0]!=X: # little mistake here, I should have added X0 = X # this makes me lose 1 turn X=TX[0] print "%s %s" % (X,Y) continue if len(TY)==1 and TY[0]!=Y: Y=TY[0] print "%s %s" % (X,Y) continue
# Use input to reduce TX or TY if line == 'SAME': if X != X0: TX = [(X+X0)/2] else: TY = [(Y+Y0)/2] elif line == 'WARMER': set_warmer(X0,X,Y0,Y) elif line == 'COLDER': set_warmer(X,X0,Y,Y0)
# Update 'previous' values X0 = X Y0 = Y
# Compute new coordinates if len(TX)>1: X = get_next(X, TX, W-1) else: Y = get_next(Y, TY, H-1)
# Write new position to standard output print "%s %s" % (X,Y)--
MockingHawk’s Debrief:
(3rd place on the podium | France | C++ | 1:56:34)<
From the first seconds of the test and after reading the given example, I realized that a binary search – on the x and y axes simultaneously – was called for. I looked at the last test and saw that Batman had only 14 turns to play, which corresponds to the base 2 logarithm of 10,000. From there, without any more doubt, I began a search that based itself on the upper and lower limits of a zone where the bomb could be found. Thanks to the CG team for having colored this zone in the Debug mode!Each turn, the position of Batman is the average of the upper and lower limits on the two axes. Then the upper or lower limit becomes his position and the other limit remains unchanged. It is necessary to proceed as such as long as the result has not been found, which totally corresponds to a proper binary search.As far as my impressions are concerned, I found the first exercise interesting and I lament the relatively long time that I spent on it (45 minutes) because of uncertain reading of stdin for my first contest in C++.
Second puzzle
I approached this exercise with the feeling that I was already far behind for this challenge. After reading the instructions, I admit I was a little lost.
So I took a pen and paper and started drawing. After twenty minutes, I realized that it was only possible to have one coordinate vary at a time in order to be sure that any change was tied to the variable alone, a little like when you do experiments in natural sciences class in school.
Thinking back to school and looking at the examples in debug mode, I also remembered that it was the average of a segment that separates the points closer to one extremity from those closer to the other. From there, I understood that one could perform a binary search on one axis and then on the other while seeing to it that the average cuts as close as possible to the middle of the blue debug zone (which had the same role as in exercise 1). The complexity of such an algorithm is O(log W + log H) with W as width and H as height. This complexity was in accordance with the 30 turns allotted in the last test.
I was then convinced that the algorithm on which I had been reflecting for 40 minutes could work and I decided to implement it, in a similar manner to my method for exercise 1.
Conclusion
I would like to thank the entire CG team for this new and very interesting challenge. The exercises offered were difficult and asked for a great deal of preparatory analysis. I advise all of those who haven’t done the challenge to try to implement their own solution, because solving such a problem is always instructive.
Kameleono’s Debrief
(1st place in Scala | Brazil | Scala| 3:00:00)
For the first task, the relative direction gives me an indication as to where lies the remaining rectangular area the bombs could be in. I then jump right in the middle of this area to get the next clue.
Clearly my huge pattern matching (lines 23 to 52) is using lots of duplicate code, which I considered worth refactoring for a few seconds. But in a challenge context… working code is good enough to live with.
For the second task, the remaining rectangular area was still an option to me. Which it should not have been! A better choice would’ve be a polygon, in order to compute its center where it makes the most sense to jump to.
Take a look at what the jump method became… it’s a disgrace! And while line 78 got accidentally cut in the last few seconds of the challenge, its complete form did not help in improving any test. So sad!
The idea about marking the cells as “in” or “out” came from the visual clue in the example. Yet I did not notice the performance bottleneck it would become to individually mark each and every single cell during each iteration. Not to mention the fact that I managed to make it even more difficult by misnaming my function that discards a cell when moving further away from it.
Most effective would have been to keep the equation for the bisection of previous and current positions in order to later compute the center of the remaining polygon. But then it would be a whole different approach… which I did not think about while I was busy coding.
Final words: I have been enjoying the CodinGame challenges for one year now. I am impressed by the way each new challenge brings in a different class of problems. More impressive even, is the short time some developpers need to completely solve the challenges!