100, The 3n+1 Problem

Start Your Engines

I was recently introduced to the Online Judge where not only are there pages and pages of logic problems to solve but there is also a means to have your solutions evaluated for correctness. I’ve been looking for an outlet to my desire to code but the stuff I come up with on my own is pretty trivial. I want some means of excersising my skills in logic and writing code, because I’ve finally realized that I actually enjoy writing code and solving problems but I don’t know what makes a good problem. So far I’ve chosen to write my solutions in ANSI-C because I’ve always enjoyed the control I have and so far the problems have been simple enough that higher level language functionality is not neccessary. To date I’ve successfully finished the first problem and am well on my way to finishing the second one.

The Problem

The full description of the problem can be read elsewhere so I won’t go into great detail here. Basically what the problem is asking for is to find the total number of cycles for each integer value between and including two integers input by a user. The 3n+1 problem is an unsolved mathmatical proof but the problem I needed to code is only to interate the cycles invovled. The problem description has the pseudo code for the algorithm being evaluated. So overall the logic is pretty limited, this first problem is really there to get the submitter to think about how to handle the input/output methods correctly based on the automatic evaluation engine you submit code to.

My first submission failed because I didn’t properly format my code in ANSI-C, stupid me forgot that while the double-slash // works in GCC it is not ANSI-C so step one was to fix my comments to be syntactically correct. I then had to tweak the I/O of the program because while I was sure I was generating the correct answers they were not in the correct output method to be checked by the judge so they were wrong. After looking through an example of how others handled the input I followed suite and used scanf and it came back correct. I would argue though that using scanf, while functional, is not the correct way to handle input. From a security stand point it is very dangerous because there is no way to limit the data taken in from STDIN. So after submitting a valid solution I went back and made it run with safe input. I’m figuring I’ll have to do that for all the programs I submit.

The Solution

I’ve put my solutions on my Github page under the UVa-Submissions repository. This way I can keep track of the versions and be able to see working and none working submissions and then also see any modifications I make after the working submissions are accepted.

The modified code to my solution can be found over here. This code will not validate against the judge since I’ve secured the input method and made the output flow more sane than what the accepted solution required. I guess I should probably keep two versions of the source, one as the accepted solution and one as the corrected solution.