BEGIN
[1:7] INT a := (1,2,5,10,20,50,100);
INT ways := 1;
PROC helper = (INT amountindex, inheritedamount) VOID:
BEGIN
INT current;
BOOL done := FALSE;
FOR i FROM 0 BY 1 TO 200 WHILE NOT done
DO
current := inheritedamount + (i * a[amountindex]);
IF current > 200
THEN done := TRUE
ELIF current = 200
THEN ways +:= 1;
done := TRUE
ELIF amountindex < 7
THEN helper(amountindex + 1, current)
FI
OD
END;
helper(1,0);
write((ways, new line))
END
Sunday, November 10, 2013
ALGOL 68 to re-do problem 31
Continuing with the trend of using more historical languages after using Pascal yesterday, I decided to use ALGOL 68 today, in order to re-solve problem 31 (so that I have a language I know as well as Javascript in order to solve problem 60, which seems a little annoying / I haven't ever solved it even in my prior Euler experience, so yeah, Javascript will be nice). Anyway, ALGOL 68 wasn't that bad to actually write code in...and a nice paper by Tannenbaum basically gave all the description I needed (http://maben.homeip.net/static/S100/research%20machines/software/algol/ACMSurveys0676-Tanenbaum.pdf), but I ran into a lot of issues not related to the actual writing of code...rather, I ran into issues with compilers. After taking a little while to find a compiler at all, I install ALGOL 68 Genie, which purports to be one of the better/more full compilers of ALGOL. Turns out it actually is a reasonably good compiler, but there was one large difference between the compiler and the Tannenbaum paper: Tanenbaum uses all lowercase words, and a68g requires all reserved word to be written in all caps. Once I discovered this, it wasn't much of an issue...but it took a long time to discover this. It wasn't documented particularly well anywhere, and the compiler errors related to using lower case words were utterly unhelpful (most looked like missing-semicolon errors)...but anyway, after getting past all of that, things were not too bad. Below is my solution which takes 27s to run...I imagine that is more due to the compiler not being the most efficient than because my code is actually slow.
Subscribe to:
Post Comments (Atom)
Your struggles remind me of when I discovered that the original "make" development tool on Unix required actual "tab characters" as prefixes... and also when I discovered python enforces white space at the start of each code line.
ReplyDeleteIf you check out Tannenbaum's paper, you will notice that certain tokens in the code are *bold*, one might think that this is only "syntax highlighting" and is used only during publication for readability, well it turns out it is called "stropping" and is actually used during coding, esp if you text editor supports bolding... c.f. https://en.wikipedia.org/wiki/Stropping_%28syntax%29#Examples_of_different_ALGOL_68_styles
It turns out that in Algol68 published code the "types/modes", operators and reserved words are to be *bolded* or _underlined_. But in the actual code these tokens are can be UPPERCASED or 'quoted'...
Strangely this convention half made it into python and into wiki-markup....
e.g. In python "special" tokens are written as "__main__"... even operators are available e.g. dir(123) yields __add__,__sub__, __mul__, __div__ & __pow__ etc
e.g. In wiki-markup works are bolded with repeated quotes: ''begin'' ~ ''end'' which is oh so similar to Algol68 stropping.
This other thing that throws contemporary coders is that Algol68's variable names may contain space. eg "number of spaces" instead of "CamelCaseClass", "mumblingalongt" or "using_under_scores". ¢ Spaces in variable names were also available in FORTRAN in the 1960s/70s/80s, so I assume Algol68 copied FORTRAN ¢
Long ago I was a student assistant at the University of Oklahoma Computing Service, and one semester a FORTRAN instructor gave his freshman charges this problem, save that it being the US, it was change for a dollar using US coinage. They all wrote the most inefficient possible nested DO loops that didn't use the current total to control how many iterations to use for the remaining denominations, and hence all went over the 30 second limit for the special XBATCH job class they had on the university's 370/158. I wrote a recursive version in Algol W that ran in 0.01 seconds, a coworker wrote a WATFIV version that ran in less (so it showed in the printout as taking 0.00 seconds), and our boss took the listings to the instructor and had a chat with him. I didn't save the listing, darn it, but recently I looked at the problem again. Here's an Algol 68 translation of the Haskell program I wrote, with denominations and amount changed to match the Project Euler problem:
ReplyDeleteBEGIN
PROC ways to make change = ([] INT denom, INT amount) INT :
BEGIN
IF amount = 0 THEN
1
ELIF LWB denom > UPB denom THEN
0
ELIF LWB denom = UPB denom THEN
(amount MOD denom[LWB denom] = 0 | 1 | 0)
ELSE
INT sum := 0;
FOR i FROM 0 BY denom[LWB denom] TO amount DO
sum +:= ways to make change(denom[LWB denom + 1:], amount - i)
OD;
sum
FI
END;
[] INT english denoms = (200, 100, 50, 20, 10, 5, 2, 1);
print((ways to make change(english denoms, 200), newline))
END
I hasten to add that this is far from the most efficient way to do it; it really wants memoization. The Rosetta Code page for it shows a truly spiffy Haskell version that I have yet to puzzle out the workings of.
Oops. I forgot to add that when I had the denominations in ascending order, it ate insane amounts of stack (I quit trying after I gave it a gigabyte!). With the denominations in descending order, it runs under Algol 68G in .15 seconds on my computer which has a 2.8GHz Athlon 64 Propus (kind of old technology these days).
ReplyDeleteNeville: you bring up some interesting facts I definitely did not know befire : this shows some of the interesting things that can be learned when using historical languages like this; maybe I will use some more if I have the free time to do so soon. And James: very interesting. I have considered at times looking into such trying to write the fastest programs possible approach to project euler, and trying to write blazingly fast code given the confines of various programming languages would certainly be an interesting task.
ReplyDelete