It was a really fun a contest (the graphics were impressive). Thanks to CG as always. I ended 19th and java 1st.
It was my first beam search and my first efficient use of timeout during a contest (i set the limit to 45ms and had almost no timeouts).
One thing that always puzzled me, in the beam search algorithm, was the sorting at the end of each turn (sorting possibly thousands of elements to only keep the 200 firsts appears to me like a possible loss of performance).
So to avoid sorting i had 3 arrays :
- one for the 200 ways i’d keep.
- one for the corresponding scores (sorted).
- one for the corresponding hashes.
For each new calculated way:
- if its score was greater than scores[0] (the lowest score) => i did a binary search in the score array.
- if it was found => i look for hashes with the same score (to prune duplicates).
- then eventually i add the way, score and hashcode in the arrays and shift down the lesser elements.
My ways were byte arrays :
[price sum, brew nb, round nb (repeat count as 1), ing0, ing1, ing2, ing3, action nb, idAction1, idAction2,…]
For the java users :
- I almost don’t use anymore List, Set, Map… I have small utilities to use array instead of collection (basically the first element of the array is the number of elements in the “list”). It avoids boxing/unboxing, the creation of “useless” objects (Integer, Byte…), to clear a “list” you only set the first element to 0…
- I always implement the @Neumann trick [JAVA] JVM memory issues in the first round : create a lot of objects then call the garbage collector. Otherwise even if i avoid object creation i always have GC timeouts.
PS: One small criticism, it was hard to make more than 2 complete submits the last sunday.