Problem 27, and Befunge, conquered

After solving many of the problems in the 20's with very little difficulty, I felt as though something was wrong...so when I saw that problem 27 would not be too hard to brute force with just a prime sieve and some simple calculations, I thought it was time to bring out one of the "big guns" in esoteric language land - Befunge. For the uninitiated, Befunge is a language which, to quote wikipedia, is "A worthy companion to INTERCAL, a computer language family which escapes the quotidian limitation of linear control flow and embraces program counters flying through multiple dimensions with exotic topologies." So, yeah - the basics of the language are that your programs are 2-dimensional instead of 1-dimensional, and control flow is directed with the operators >,<,^,v, |, and _. The first 4 direct the execution of your program in the indicated direction, and the other 2 change direction conditionally - down if the top element of the stack is 0, up otherwise, or left if nonzero, right otherwise. So yes, as indicated from those operators, this language is stack-based - which leads to some interesting interactions when code that has to be written backwards becomes easier to parse, on account of postfix notation becoming prefix notation - or maybe writing code in Befunge for 3 days has just made me go crazy, seeing as I can now read and write code that goes up, down, left, or right.

As though code that runs in whatever direction it feels like wasn't enough, Befunge has some other great little goodies that come with it - for one, there are no variables, but there is a method of data storage and retrieval - there is the 'p' command, which allows you to store an ascii character at a location in your source code, and the 'g' command, which allows you to access the ascii value of the character at a location in your source code...the syntax isn't too bad until you need variables with values over 256, which I then stored in two characters in base 256 notation. Storing a variable like this requires the following code:

pYY/***4444: pXX%***4444:<

where XX and YY are the locations where the variable is to be stored...note that the above code reads right to left...there was no place in my code where I performed this in a straight left to right line. Retrieval of the variable is then as simple as

XXgYYg4444****+

So with variable reading and writing so simple to perform, what could possibly go wrong?

Well, I often made mistakes accessing variables (is this variable stores at 0,1 or at 1,1 or...its hard to keep track, even though I did name the locations where I stored them to help a bit) Also, its very easy to misalign some arrows, and thus either enter an infinite loop or just do really funky unwanted stuff (the code is on the surface of a torus...if you go off one end, you loop around). Finally, debugging is very hard, as adding print statements requires reformatting of your code.

As though all this wasn't enough, in order to get my code to run in reasonable time, I needed a prime sieve that was at least a bit smarter than dividing by every single number from 2 to p-1...so, I wanted to divide up to sqrt(p). But, of course, Befunge doesn't have a square root function, so I had to implement my own version of Newton's method, and allocate some space in the lower-right hand corner of my code for it.

As a final aside - I ever so slightly broke my "the program must print the answer" rule for this one - in order to iterate over all candidate quadratic polynomials for this problem of the form n^2 + an + b, with |a| < 1000 and |b| < 1000, this program must be run twice, once for negative a, and once for positive a. However, once you know that the answer happens when a is negative, you can just run the negative version and get the answer every time...in about 45 seconds on my machine, despite the ridiculousness that is Befunge. My monstrous square of code is below (comments added for readers' sake, I did not include them originally) (Image below because I couldn't get the alignment right in the post...link to code in text form is here: https://dl.dropboxusercontent.com/u/34972177/PELC/e27comments.fun