Internet Problem Solving Contest

• Input data set – E

The Institute for Promoting Social Change is building the world’s first Artificial Intelligence. To make sure the AI won’t decide to eradicate humanity, it will be programmed to make humans happy. But first, the AI must be able to actually recognize human emotions. We probably don’t want an AI which thinks that humans are happy when they are screaming and frantically running around. You have been tasked with fixing this deficiency by programming the AI’s empathy system.

Problem specification

Your task is simple: Write a program that will process a photo of a human being and determine whether the person is happy, sad, pensive, or surprised.

This problem is special. Usually, you get all input data, you can write a program in any programming language, and you only submit the computed output data, not your source code. This task is the exact opposite. You only submit source code – specifically, a program written in the Lua 5.2 language. (See below for an introduction.) We will run this program on our test cases and tell you the results.

Your program won’t have OS access, so input and output will happen through global variables. The input is a 128 × 128 photograph. Each pixel has three color channels (red, green, and blue) stored as integers between 0 and 255, inclusive. The photo will be in a 128 × 128 × 3 array named image. Lua arrays are indexed from 1, so for example, the blue value of the bottom left pixel will be in image[128][1][3].

After recognizing the human’s emotion, your program must set the variable answer to the number 1 if it’s happy, 2 if it’s sad, 3 if it’s pensive and 4 if it’s surprised.

Limits

The libraries and functions named debug.debug, io, math.random, math.randomseed, os, package, print and require have been removed. Other functions that try to read files will fail.

Our data set consists of 200 photographs. We will sequentially run your program on every photo. Every execution must use under 512 MB of memory, and the whole process must take less than 15 seconds. If your program exceeds these limits, or causes a syntax or runtime error, you will receive a message detailing what happened.

If the program produces an answer on all 200 images without causing any errors, we will then check which answers are correct, and tell you the detailed results. The program doesn’t have to answer everything correctly to be accepted. In the easy subproblem E1, the number of correct answers must be at least 60, while in the hard subproblem E2, it must be at least 190. (In other words, the accuracy of your program must be at least 30% for the easy subproblem, and at least 95% for the hard subproblem.)

Both subproblems use the same image set. The only difference is in the acceptance threshold.

You can make 20 submissions per subproblem instead of the usual 10.

Testing your program

We have given you the first 12 of the 200 photos that comprise our data set. The other photos are similar, so you can use them to check if your program is working correctly. If you have Lua installed and your program is named myprogram.lua, you can test it with this command:

lua -l image001 -l myprogram -e "print(answer)"

If you can’t install Lua, you can use the on-line interpreter at repl.it. Copy and paste the contents of image001.lua and myprogram.lua to the editor on the left, then add print(answer), and press the Run button in the middle. Note that repl.it is very slow (it actually compiles the Lua virtual machine from C to JavaScript), and it uses Lua version 5.1 instead of 5.2. But if your program works in repl.it, it will likely also work on our servers.

Introduction to Lua

If you don’t know the Lua language, here’s a quick introduction:

• Variables: foo_bar = a + b
• Literals: nil, true, false, 123, 0xFF, "a string"
• Arithmetic: 1+2 == 3, 1-2 == -1, 2*3 == 6, 1/2 == 0.5, 6%5 == 1, 2^3 == 8
• Comparison: a == b, a ~= b, a < b, a <= b, a > b, a >= b
• Logic: a and b, a or b, not a (note that nil and false are considered false, while everything else is considered true – including 0 and "")
• Math: math.abs(x), math.floor(x), math.max(a, b, c, d), math.pi, etc.
• Binary: bit32.band(a, b), bit32.bor(a, b), bit32.bnot(a), bit32.bxor(a, b), etc.
• “If” statement: if cond then ... elseif cond then ... else ... end
• “While” loop: while cond do ... end
• Numeric “for” loop: for i = 1, 128 do ... end
• Functions: function some_name(a, b, c) local d = 7; return a + d; end
• Local variables (in functions and control structures): local l = 123
• Arrays (tables): arr[idx] (indexed from 1), { 1, 2, 3 } (new array), #arr (array length)
• Comments: --[[ multiple lines ]], -- until end of line
• Newlines and semicolons are optional: a = 1 b = 2 + 3 c = 4 * 5

For more details, refer to the Lua manual and the language grammar, or other on-line resources – though you probably won’t need most parts.

Example

Your submission could look like this:

num_bright_pixels = 0
for y = 1, 128 do
  for x = 1, 128 do
    if image[y][x][1] + image[y][x][2] + image[y][x][3] > 600 then
      num_bright_pixels = num_bright_pixels + 1
    end
  end
end

if num_bright_pixels > 2000 then
  answer = 1   -- bright photos are happy
else
  answer = 2   -- dark photos are sad
end

This is a valid program that produces an answer for each image. But the answers aren’t correct, so you’d receive this response:

Wrong answer: Only 47 answers are correct.
1 is right, 2 is right, 2 is wrong, 1 is wrong, 1 is wrong, ...

The program correctly identified that the first person (image001) is happy and the second person (image002) is sad, but it can’t tell that the third person is happy, the fourth person is surprised, etc.