Mark Schnitzius (schnitzi@eustis.cs.ucf.edu) has started and runs the Internet Conciseness Contest. The contest is designed to provide an outlet for recreational programming. The contest accepts programs only in Ansi C. Scores are based on the number of tokens in a program. The lower the score the better.
Mark is up to Round number 4. Below is the problems from each round.
Problem #1 — Range Arithmetic
Scientists modeling physical systems often need to perform arithmetic involving numbers which are not precisely specified. For instance, if the pressure in a tank is known to be greater than or equal to twenty and less than twenty-five, and this pressure increases by an amount greater than one but less than or equal to three, the resulting pressure will be greater than twenty-one but less than twenty-eight. This equation could be represented as:
[20,25)+(1,3]=(21,28)
Notice here that the square brackets “[ ]” mean that the endpoint is included, while the round brackets “()” mean that it is not. Your job is to write a program which reads in simple range arithmetic expressions and produces the correct results.
INPUT FORMAT:
There will be one simple expression per line in the following format:
<range1><operator><range2>
where operator is one of “+” (addition), “-” (subtraction), and “*” (multiplication). You will not need to worry about division in this problem, as it presents some trickiness (especially when dividing by a range which includes zero).
The ranges will be in this format:
<left-delimeter><int1><comma><int2><right-delimeter>
where
<left-delimeter> is "[" or "("
<int1> is the integer denoting the low end of the range
<int2> is the integer denoting the high end of the range
<right-delimeter> is "]" or ")"
<int1> is guaranteed to be LESS THAN <int2>. There will be no spaces or extra characters in the input.
OUTPUT FORMAT:
For each line of input, echo the expression that you read in, followed an equals sign, followed by the range that represents the result of the expression, in the same range format specified above.
SAMPLE INPUT:
[20,25)+(1,3]
(4,5)*(1,2]
[9,10]-[3,4)
(-4,2)*[2,3)
[-2,2]*(-2,2)
[-2,2]*[-2,2)
SAMPLE OUTPUT:
[20,25)+(1,3]=(21,28)
(4,5)*(1,2]=(4,10)
[9,10]-[3,4)=(5,7]
(-4,2)*[2,3)=(-12,6)
[-2,2]*(-2,2)=(-4,4)
[-2,2]*[-2,2)=[-4,4]
Problem #2 — TARGET NUMBERS
Consider the numbers 1, 2, and 3. If you combine them using ordinary operators (+,-,*,/), possibly adding parentheses, they can be made to equal a number of different values:
1+2-3 = 0
3*2+1 = 7
(2+1)*3 = 9
The Problem:
You are to write a program that, given a set of integers and a target integer, produces an arithmatic expression equaling the target value which uses ALL of the integers in the input set. You may use all of the above-mentioned operators. The precedence of the operators is defined as follows:
'*' equals '/' greater than '+' equals '-'
Hence, all multiplications and divisions are done first (left to right) before the additions and subtractions (which are also left to right). You may need to include parentheses in your expression, but ADD NO MORE THAN ARE NECESSARY.
Input Format:
YOUR PROGRAM MUST BE ABLE TO ACCEPT MULTIPLE DATA SETS. I will redirect a file containing judge data into your program, so your program must accept input from stdin. Each data set consists of three lines. The first line will contain a single integer <n> where 2 <= n <= 5. The second line will contain <n> POSITIVE integers separated by spaces, which represent the set of integers you have to work with. The third line will contain an integer (POSITIVE or NEGATIVE) which is the value you are targeting.
Output Format:
For each data set, output (to stdout) an expression which equals the target number and uses EVERY integer in the input set, followed by an equal sign, followed by the target number. If it is not possible to generate the target number from the set of integers, output the line ‘TARGET NUMBER UNREACHABLE’.
Sample Input:
3
1 2 3
0
3
1 2 3
9
5
1 1 0 5 23
-13
3
1 1 1
8
3
10 5 13
26
5
2 2 2 2 2
20
Sample Output:
2+1-3=0
(1+2)*3=9
5*(1+1)-23+0=-13
TARGET NUMBER UNREACHABLE
10/5*13=26
((2+2)*2+2)*2=20
Before you ask, here are some other points:
- There may be more than one way to generate a target value. Print out only one — it does not matter which, as long as the expression is well-formed and generates the correct target value without using more parentheses than are needed for that expression (there may be other expressions equaling the target number which use fewer parentheses, but as long as there are no extraneous parentheses in the expression you output, that is okay).
- Only use the ‘/’ in a situation where it will divide evenly. For example, if you are given the numbers 3, 2 and 2 with a target of 3, the equation ‘3/2*2=3’ is incorrect, while ‘2/2*3=3’ is okay.
- You may not add a unary ‘-‘ to a number or expression to negate it. Combine the numbers using the four operators in a binary fashion only.
- Do not combine numbers by concatenating their digit strings. That is, do not combine a 5 and a 7 into 57.
Problem #3 — “Maximum Products”
Here’s a problem that sounds deceptively simple, but a lot of subtlety is involved in making it concise.
The Problem:
Given a long string of digits, insert a ‘*’ into it so that the product formed is maximal.
The input file consists of multiple lines of input. Each input line contains an n-digit number in columns 1 through n (1 < n <= 35). There will be no leading zeros in the input. Your output should be the original digit string with the ‘*’ inserted, followed by an equal sign, followed by the resulting product. Leading zeros on any of the numbers that you output are not allowed. If more than one answer is possible for a given input, print any one.
Sample input:
12343
10000000
333
10001
1122334455667788998877665544332211
Sample output:
123*43=5289
1000000*0=0
33*3=99
1000*1=1000
1122334455667788*998877665544332211=
1121074821037408888890148523519268
The Problem #4 — Minesweeper
This problem was adapted from the Windows game called ‘Minesweeper’. Those of you familiar with the game need to pay close attention, as there are some differences.
Consider the following 5×5 square grid:
----*
-----
*----
*----
-*---
The asterisks on this grid represent ‘mines’. The matrix that would result as a sweep of this grid would look like this:
00011
11011
22000
33100
22100
Here, a number <n> in row <i> column <j> means that there <n> are mines adjacent to (or directly at) row <i> column <j>. Your program is to read in matrices representing sweeps of a mine field and produce a map showing the likely locations of mines.
Input Format:
There will be multiple data sets. Each data set will start with a single integer n (1 <= n <= 10) on a line by itself. The next n lines will each contain n columns of single-digit integers representing the n by n matrix that is the minesweep of the field.
Output Format:
For each data set, output an n by n grid with asterisks showing the probable location of mines and minus signs as ‘safe’ locations as implied by the minesweep matrix that you read in. Print a blank line after each grid. If more than one answer is possible for a given input set, output any one answer. There is guaranteed to be at least one correct solution for any input set.
PLEASE NOTE: A straight ‘generate-all-possible-combinations- and-test’ approach will not likely finish within the 5 minute time limit.
Sample Input:
5
00011
11011
22000
33100
22100
10
0011100111
0011100111
0000111000
0000111000
0000111000
0012210000
0013320011
0013320022
1101110022
1100000011
Sample Output:
----*
-----
*----
*----
-*---
---*----*-
----------
----------
-----*----
----------
----------
---**-----
----*----*
---------*
*---------
In round 1, Mark was not using a program to count tokens but used something like the number of characters, so programs were submitted that were very unreadable. I tried to running the winner of round 1 using C68. It compiled fine, but did not run right. I’ve included it below for those that might want take a shot at decyphering this program.
Round 1 winner
#define Z(Y,X) if (X & h[2]) \
do {i=a[f^=g^=1] Y a[g+2]; W(<,c,b) W(>,d,e)} while (
f|g);
#define W(V,U,T) if (f & g | i V U | i==U & !T)
U=1,T=h[f]&h[g+3]&16;
a[4],b,c,d,e,f,g;
char h[5];
main(i,j)
{
while(gets(j))
{
Z(*,sscanf(j,"%c%d,%d%3c%d,%d%c",h,a,a+1,h+1,a+2,
a+3,h+4))
Z(+,1)
Z(-,4)
printf("%s=%c%d,%d%c\n",j,b ? 91:40,c,d,e ?
93:41);
}
}
I found the round 3 problem to the be most interesting. My first thought was to try to find a way to solve it without using the brute force method. I thought a binary search might work when I noticed that the answer would tend to gravitate to the center, but there were cases where the answer would be at one end (like 1000*1).
Here is my first attempt the program.
100 INPUT "Enter Number: ";in$
110 LET position = 0
120 LET greatest = 0
130 IF LEN(in$)=0 OR LEN(in$)=1 THEN
140 PRINT "Bad Value"
150 STOP
160 END IF
170 IF LEN(in$) = 2 THEN
180 PRINT in$(1);"*";in$(2)
190 STOP
200 END IF
210 FOR x = 1 TO LEN(in$)-1
220 y = in$(1 TO x)
230 z = in$(x+1 TO )
240 total = y * z
250 IF total > greatest THEN
260 position = x
270 greatest = total
280 END IF
290 END FOR x
300 PRINT in$(1 TO position);"*";in$(position+1 TO )
By looking at the program, I was able to whittle it down at bit, but at the sacrifice of neatness and it’s readability. Here is the second version.
100 INPUT "Enter Number: ";in$
110 position = 0
120 greatest = 0
130 IF LEN(in$)=0 OR LEN(in$)=1 THEN PRINT "Bad Value" : STOP
140 IF LEN(in$) = 2 THEN PRINT in$(1);"*";in$(2): STOP
150 FOR x = 1 TO LEN(in$)-1
160 IF (in$(1 TO x) * in$(x+1 TO )) > greatest THEN
position = x : greatest = in$(1 TO x) * in$(x+1 TO)
170 END FOR x
180 PRINT in$(1 TO position);"*";in$(position+1 TO )