To qualify for the competition, you must turn in a compiler which correctly compiles and runs the publicly available Tigris programs (note that a program such as OutOfBounds.tig is bugged; thus, here the correct runtime behavior is to return the correct error code).
The compilers which qualify will be run on further tests, which are not made publicly available until after the deadline, and they will be exposed to a time trial of the generated code for a Tigris program which solves the following problem:
The four distant relatives Leo, Onca, Pardus, and Tigris got together in a neutral country to discuss the problem of inferior species in their territories, including mud-bloods such as ligers and tigons. They made a secret alliance with a cruel trapper who would provide them with huge cages. The gang of four would then apprehend unwanted creatures in their areas and place them in the cages for the trapper to transport to a slaughter house. Then the pelts would be sold for profit and the gang of four would receive their share and look forward to an existence in unbelievable luxury.
Together the gang of four has made a list of all the unwanted inhabitants of their areas. For each creature, they have noted their weight and the value of their coat. Knowing that in total, the cages and transportation devices can handle 600 tons, the gang of four wants to compute which animals from the list to capture in order to maximize their profit. They decide to write a program for the ancient computer they have access to in the Bengal Jungle. The computer is so old that it is 86400 times slower than the computers at IMADA. The unmatched greediness of the gang of four means that they cannot agree to start their operation before they have computed the optimal selection.
Intelligence information has revealed the plan to your agency. In fact, you have their program on microfilm. Your boss has a plan to move forces into the area to protect the endangered species. However, it will take a month to get it organized in this distant wilderness. Your boss has asked you to find out whether or not he will in fact have a whole month before the bloodshed begins.
The program on the microfilm has been scanned into the file "Knapsack.tig". Go save the world...
Through the tests described above, we evaluate the correctness and efficiency of the compilers, and this will lead to the selection of the Compiler of the Year. The winner group will be announced on the course home page. There will be a small prize, but you are primarily competing for the honor.
If you want to make extensions which are time-consuming at
runtime (runtime checks for out-of-bounds, etc.),
you may equip your compiler with the ability to recognize an option
-x such that as default your compiler runs with the
time-consuming code, but with an option, these can be