Internet Problem Solving Contest

IPSC 2007

Solution to Problem E – Enhancing IPSC Rules

The main task in this problem is in recognizing the pictures of rock, paper and scissors (let us call them symbols for short). The easy problem can be quickly solved by hand. The hard problem can too be done by hand, but it takes a lot of time and errors can be made easily. Writing a program would be more efficient.

After an examination of the pictures and their dimensions we can easily see that each round is in a white rectangle of 120x80 pixels and that there are about 20 kinds of symbols up to 50x50 in size at random positions either in the left or in the right half. Because of the white background, the size and position of each symbol can be determined just by looking for topmost, bottommost, leftmost and rightmost non-white pixel in each half.

The most straightforward option would be to extract samples of each kind of symbols and then try to match the others to one of them. Unfortunately all copies of a symbol were not exactly the same, either because of the JPEG compression which the pictures obviously underwent or because they were sometimes blurred a bit. However the number of distinct types is not very large or the matching can be done a bit fuzzily.

The matching can be also more easily done by checking just the size of the symbols and few pixels inside. And computer graphics gurus could see a lot of other characteristics that could be used to differentiate between the symbols. There are even some simple enough for mere mortals like us to understand.

The rocks are very dark and large (when counting non-white pixels). The papers are large too, but when counting only darker pixels they usually amounted to very little (except maybe the one paper that has a relatively pronounced shadow). The scissors are somewhere in the middle, usually half black/grey and half bright colors. So one of the simplest ways is to count the darker pixels, maybe playing with the threshold between dark and white.