Miserable programming contest questions

Miserable programming contest questions

Have you ever been to a programming contest? I have... multiple times. Despite cranking away just as hard as I could, my team never won. We came close a bunch of times but never made it to first place. I guess that's just as well, since the prizes were some math nerdery like those backwards calculators which used RPN, and those just make my head hurt.

I still have all of the source code from our attempts. I also managed to scrape together most of the problems. Some of them were easy. Most of them were not.

One problem was to print a giant "F". They give you a size and you have to render a huge letter F on the screen from asterisk characters. It has to be that many rows tall and wide. Obviously, this means drawing a vertical line and a horizontal line, but you also have to draw the cross bar of that letter as well. They tell you how to handle this: the middle bar should either be in the middle or just above it if that's not possible.

I think they further added that the size would always be greater than 4 and you didn't have to accept smaller numbers.

This one was simple enough. It was the sort of stuff I used to do back on my C-64 and VIC-20. Get the size, get the middle, then start a loop from 1 to size. On the first row and middle row, print "size" * chars. On every other row, print just one. That's it. We got this one just fine.

Another problem was a validator for alphanumeric data. They referred to them as "license plates" and gave some rules. They can be either three capital letters followed by 3 or 4 digits, or 4 capital letters followed by 3 digits. Anything else is invalid.

Looking at this now, in 2013, I go "oh, that's a regex". However, way back at the time, I knew of no such things. That sort of magic did not exist in my DOS and Turbo Pascal and QuickBASIC world. My solution reflects my ignorance. First, I do a simple length check, since I can throw out anything which isn't either 6 or 7 characters long.

Next, I start a breathtaking (in the bad way) series of nested conditionals. It looks like this:

if (ord(plate[1] >= 65) and (ord(plate[1]) <= 90) then
  if (ord(plate[2] >= 65) and (ord(plate[2]) <= 90) then

That's testing for something between A and Z (inclusive) using the ASCII values. It does this three times, then looks for matching values between 48 and 57 (0 - 9). If it gets what it wants, then it says "valid". Then there's another block where it looks for that fourth character possibly being A-Z, and then tests for three more digits. That's also "valid". Anything else gets "not valid".

I imagine this could be done with a shell script that does a read, an echo piped into egrep with the appropriate regex, and a exit-code test to echo the right thing.

However, because it was possible through the stupid brute-force method, we managed to submit it successfully.

It started getting harder. They moved into the "mathy" stuff.

This problem has them providing 8 numbers representing 4 (x, y) coordinates for two ditches. You have to tell where they intersect, and if so, where they intersect. They also mentioned that "they are guaranteed to not be vertical or parallel", and I'm sure that means something to the people who intuitively "get" this, but it meant nothing to me.

What's weird is that despite having no understanding of this problem either then or now, I have source code on my disk here which apparently solves the problem. I guess my teammate was sufficiently skilled in the dark arts of coordinate wrangling to tell me what to do. I'm lucky he was there with me, since by myself I would have been totally stuck on this one.

There's a lot of weird stuff in here. First I read in the four endpoints of ditch 1, then the four endpoints of ditch 2, this gives me d1end[1-4] and d2end[1-4]. Then it starts doing all kinds of crazy things. If d2end1 is greater than d2end3, then we swap them.

Then the tests start. If not (this) and (this) or (this) and (this), then "ni". In this case, that's not a shrubbery reference, but rather a call to a function which says "no intersection". This goes on for a while, with more and more tests.

After that, there are more swaps, and even more tests. They get bigger and bigger. Finally, down at the bottom of all of this, there's a call to "is" which just prints "intersection". The problem is that I see a bunch of debug scaffolding and nothing which would actually print the intersection. This implies we never completed it.

The last problem with any source code on my drive is all about massive numbers. They wanted you to raise 2 to a given power, and then return a given digit from it. If the power was 16 and the digit was 2, then the result would be 5, since 2^16 is 65536 and the second digit in that number is 5.

I'm pretty sure I knew about the basic limitations of the numeric types in my programming language of choice and knew it wouldn't be able to handle a bunch of crazy-big numbers. The code fragment left over on my old archive directory just asks for the input and starts doing something screwy with the "requested digit" value. I think maybe my math-clued partner had some idea involving reducing the workload based on which digit they requested, but it's been lost to the sands of time.

That's the last problem we attempted. There were several more in the contest, however, but we didn't even touch them. I did find the list of problems at some point so I can share what they are even though I have nothing in the way of code to show for it.

This one is like a one-dimensional Othello board. There are two players, each with their own color. On each turn, a player can place a single piece, and then it's the other player's turn. You can put a piece on any open spot. When your placement totally surrounds those of your opponent, they all become yours.

They provide some examples for this. If the board size is 5 and the board is "BW_WB", playing a B at 3 will turn the board into "BBBBB". The game is over and blue (B) is the winner.

If the board size is 6 and the board is "B_W_WB", playing a B at 4 makes it into "B_WBBB". The W at #3 wasn't surrounded and thus doesn't flip.

They give you the board size and the moves the players will make, starting with blue. You need to provide the final board as a string of Bs and Ws and tell who won and with how many pieces. Ties should also be reported.

Given that there's not even a hint of code for this thing, I'm going to guess we took one look at this, made some kind of "yeah right" meme face and flipped to the next page.

The final problem is completely nuts as far as I'm concerned. They introduce these "new integers" where they are a pair of positive integers like (7, 11).

Then they say the sum (a+b)+(c,d) is defined as (a+c,b+d), or:

(1,2) + (3,4) = (1+3, 2+4) = (4,6)

The product (a,b)*(c,d) is defined as (ac+2bd,ad+bc), or:

(1,2) * (3,4) = (1*3+2*2*4, 1*4+2*3) = (19,10)

The pound (a,b)#(c,d) is defined as (a,d), or:

(1,2) # (3,4) = (1,4)

It goes on like this. Next they say it's postfix/RPN (see, there's the head-hurting calculator business again...) where normal integers are separated by spaces and the operators follow operands. Your program has to take a line of ordinary integers and print the resulting "new integer".

-1 means +, -2 means *, -3 means # and 0 means = (evaluate the expression).

Then they provide a whole bunch of examples and sample runs I really don't want to key in.

If that 1D Othello-ish thing made me do a meme face, I can't imagine what my reaction to this must have looked like. I'm pretty sure I responded to this by saying to my teammate, "hey, want to see this thing I downloaded the other day?", and then we started messing with random junk on my machine.

That is, I think we ran out the clock doing things other than tearing our hair out for some dumb programming contest problems.