#lang racket (define (digits x) (if (< x 10) 1 (add1 (digits (quotient x 10))))) (define (nth-conv n) (define (help m) (if (= m 1) 1/2 (/ 1 (+ 2 (help (sub1 m)))))) (add1 (help n))) (define (topheavy r) (if (> (digits (numerator r)) (digits (denominator r))) 1 0)) (foldr + 0 (map (λ (x) (topheavy (nth-conv x))) (build-list 1000 add1)))
Sunday, October 27, 2013
Problem 57 - Racket
After struggling with trying to use C# to solve Problem 57, I realized that Racket was perfect for it. Racket is a language that I am very familiar with, it is fairly easy to program in (being a dialect of Lisp), and it has native support for arbitrary precision rational numbers...making it perfect for solving Problem 57, which involves keeping track of rational numbers with very large numerators and denominators. After my failed C# attempt had a 50 line Rational struct and was going to get larger and more unwieldy, I finally came to my senses and wrote the below script in Racket, which runs in about half a second.
Problem 26 - resolved in C#
I started trying to solve the problem that I am up to, problem 57, in C#, as I realized it was a pretty nice language that I had yet to use. However, I soon discovered that I had chosen the wrong language. After struggling with trying to write a rational class and then even contemplating writing my own BigInteger class, I realized that I knew that there was a better way to solve problem 57, and that was with Racket. More on that in the next post, this post just has my fairly unexciting C# code, which is actually (I think, very subjectively) cleaner than the Racket I originally wrote to solve problem 26 (which involves finding the denominator d < 1000 such that 1 / d has the largest cycle).
public class Euler26 { public static int biggestCycle(int d) { int[] rems = new int[1000]; int r = 1; int i = 0; while (r != 0) { r = (r * 10) % d; for (int j = 0; j < i; ++j) { if (rems[j] == r) { return i; } } rems[i++] = r; } return i; } public static int Main(string[] args) { int ans = 0; for (int d = 1; d < 1000; ++d) { ans = ans < biggestCycle(d) ? d : ans; } System.Console.WriteLine(ans); return 0; } }
Tuesday, October 22, 2013
Brainfuck is open again
I have known for quite a while that problems 1 and 6, which I solved with brainfuck and the very bf-like Ook! were not very hard to solve with pencil, paper and a calculator, putting them into the "solvable analytically" category. I finally admitted now and wrote up pencil and paper solutions that are linked to in the progress table...and this means that I am somewhat obligated to solve another problem in brainFuck.
Sunday, October 20, 2013
2000 pageviews!
Another big milestone reached, progress is being made. Somehow, every time I think I have exhausted the set of reasonable languages for use, more keep creeping up, so I have no intent on stopping.
Saturday, October 19, 2013
Progress
This table records all of the languages I have used on this challenge, along with which problems have been solved in which challenge. The statement of the problems can all be found on Project Euler, and my solutions are described in this blog, as well as being linked to from the table below. This table keeps growing, and keeps getting pushed lower and lower in the blog, so I keep reprinting it. The links all lead to postings of the code on github: so if you wanted all of the code, you could clone the whole repository (https://github.com/drsam94/PELC).
BrainFuck | 1* |
Haskell | 2*,37 |
J | 3*,24*,35 |
Ruby | 4*,30*,56 |
Whenever | 2,5* |
Ook! | 6* |
Racket | 7*,26*,57 |
K | 8*,30 |
Javascript | 9*,31* |
sML | 10*,42 |
PHP | 11 |
Go | 12*,32 |
cLisp | 13 |
C | 48*,50 |
Fortran95 | 3,15* |
Python | 16*,24*,39 |
ELM | 17*,48 |
Scala | 18*,44 |
Perl | 19 |
Java | 20 |
FALSE | 4 |
Squirrel | 21*,52*,55 |
D | 22 |
Ceylon | 23 |
Postscript | 7 |
Befunge | 27 |
Boo | 29 |
Frink | 16 |
Forth | 9 |
Shakespeare | 12 |
Bash | 33 |
Batch | 34 |
Whitespace | 36 |
LOLCODE | 10 |
Lua | 38 |
Erlang | 24 |
Rust | 40 |
Ada | 41 |
Clojure | 14 |
Coffeescript | 43 |
Prolog | 18 |
R | 45 |
Julia | 46 |
x86-64 | 47 |
INTERCAL | 17 |
OCaml | 49 |
COBOL | 21 |
Cobra | 51 |
C++ | 14*,53 |
APL | 52 |
Chapel | 54 |
C# | 26*, 59 |
WARM | 58 |
Kotlin | 26 |
Pascal | 61 |
ALGOL68 | 31 |
Analytic | 1,5,6,8 |
Analytic | 15,25,28 |
Problem 56 - Ruby
Solving problem 30 in K opened up Ruby for use again. Though Ruby is not a language I have terribly much experience with (indeed, I have only used it as part of this project), it is still pretty nice, and it makes solving Problem 56 relatively easy, as it supports (arbitrary? at least very large) precision integer arithmetic: enough to store 99^99 in a variable with no problem. Here is my solution to this problem in Ruby. I am sure there is room for improvement: this solution takes 2 seconds to run, but nonetheless, it only took a minute or two to write, so its fine.
def digisum(x) ret = 0 (1..(x.to_s.length)).each {|i| ret += (x % (10 ** i)) / (10 ** (i - 1)) } return ret end ans = 0 (1..99).each {|a| (1..99).each {|b| dsum = digisum(a ** b) ans = dsum > ans ? dsum : ans } } printf("%d\n",ans)
Problem 30 - K
K is an array-based programming language much like APL or J. I have struggled with it in the past as it was difficult to find reasonable documentation, and most of the implementations of it are not free (not free as in beer or speech). However, this time around, I did find an open source implementation (called Kona), and I found a nice reference sheet from a company that makes a not-so-open implementation (http://www.kx.com/technical/contribs/mikep/ReferenceCard.PDF). Anyway, after finding such a reference, this problem was not too hard in K - I chose it as it maps pretty easily to array programming, and at this point, I am decent enough with J and APL that picking up K wasn't too bad. Below is the "traditional" form of the program, as any proper code written in a language related to APL should not be understood by anyone other than its author. The version I wrote first, with names for functions and separated into more than one line is here: https://github.com/drsam94/PELC/blob/master/e30human.k. The version in one line with no unnecessary whitespace always has more impact though (the result is stored in a variable so the answer can be read after loading the file in the K console).
ans:+/{x*(x={+/{x^5}'{(x%100000 10000 1000 100 10 1)!'10}x}x)}'100_!354294
Thursday, October 17, 2013
Problem 55 - Squirrel
I have been using Squirrel a lot recently...it is a nice language, and it just happens that I seem to always use it in places where I choose to replace it very quickly. Anywhere, here is my latest squirrel problem. Problem 55 involves finding candidate lychrel numbers: A lychrel number is one which, if you repeatedly add the reverse of a number to itself, yields a palindrome. Now, no one has proved that any number is actually lychrel in base 10, however, there are many numbers which all the world's computing power has never been able to prove non-lychrel. This problem tasks one to find all such numbers under 10000, given that it will not take more than 50 iterations to reach a palindrome. Attempting to do this in Squirrel led to overflow in the 64-bit integers available....luckily, assuming that any number that could cause integer overflow was lychrel led to the correct result. Here is my code, runs in ~.166ms.
function rev(x) { local r = 0; while (x > 0) { r = r*10 + x%10; x /= 10; } return r; } function digits(x) { local arr = []; while (x > 0) { arr.append(x % 10); x /= 10; } return arr; } function isPalindrome(x) { local digs = digits(x); for (local i = 0; i < (digs.len() + 1) / 2; ++i) { if (digs[i] != digs[digs.len() - i - 1]) { return false; } } return true; } function isLycherel(x) { for (local i = 0; i < 50; ++i) { x += rev(x); if (x < 0) { return true; } if (isPalindrome(x)) { return false; } } return true; } local ans = 0; for (local i = 1; i < 10000; ++i) { if (isLycherel(i)) { ++ans; } } print(ans + "\n");
Tuesday, October 15, 2013
Problem 54 - Chapel
Chapel is a language, currently very much in Beta (based on all the documentation...but I don't know why a beta version would take on such a high version number as 1.7), which has as its main purpose in life concurrent and parallel programming. While my solution in Chapel doesn't entirely ignore this (the forall statements below are executed in parallel, if I read the documentation correctly), it also doesn't make much use of it. So, at least ignoring those features, Chapel is a fairly nice, simple language, and I trust its concurrent features are nice too. The most frustrating thing I encountered in the language was that by default array indexing starts at 1 (though you can index arrays over any domain), and that to access a character at position i in string s, the syntax is s.substring(i)...which is not what I would guess would be what substring would do at first glance. Anyway, here is the code which looks through a file with a thousand poker hands and gives how many times player 1 won.
use Sort; var line: string = read(string); var ans: int = 0; const D: domain(1) = (0..4); var hand1: [D] string; var hand2: [D] string; //Chapel has no nice way to test for EOF, so I added END //to the end of the file. while line != "END" { hand1[0] = line; for i in 1..4 do hand1[i] = read(string); for i in D do hand2[i] = read(string); if handValue(hand1) > handValue(hand2) { ans += 1; } else if handValue(hand1) == handValue(hand2) { if higherCards(hand1, hand2) == 1 then ans += 1; } line = read(string); } writeln(ans: string); proc higherCards(hand1: [D] string, hand2: [D] string): int { var vals1: [D] int; var vals2: [D] int; forall i in D { vals1[i] = toNumber(hand1[i].substring(1)); vals2[i] = toNumber(hand2[i].substring(1)); } BubbleSort(vals1); BubbleSort(vals2); for i in D { if vals1[4 - i] > vals2[4 - i] then return 1; if vals1[4 - i] < vals2[4 - i] then return 2; } return 1; } proc toNumber(num: string): int { if num == "T" then return 8; if num == "J" then return 9; if num == "Q" then return 10; if num == "K" then return 11; if num == "A" then return 12; return (num: int) - 2; } proc handValue(hand: [D] string): int { var suits: [D] string; var vals: [D] int; var isStraight: bool = false; var isFlush: bool = false; forall i in D { suits[i] = hand[i].substring(2); vals[i] = toNumber(hand[i].substring(1)); } BubbleSort(vals); if vals[0] + 1 == vals[1] && vals[1] + 1 == vals[2] && vals[2] + 1 == vals[3] && vals[3] + 1 == vals[4] then isStraight = true; if suits[0] == suits[1] && suits[1] == suits[2] && suits[2] == suits[3] && suits[3] == suits[4] then isFlush = true; if isFlush && isStraight then return 104; if (vals[0] == vals[1] && vals[1] == vals[2] && vals[2] == vals[3]) || (vals[1] == vals[2] && vals[2] == vals[3] && vals[3] == vals[4]) then return 91 + vals[2]; if (vals[0] == vals[1] && vals[2] == vals[3] && vals[3] == vals[4]) || (vals[0] == vals[1] && vals[1] == vals[2] && vals[3] == vals[4]) then return 78 + vals[2]; if isFlush then return 65; if isStraight then return 52; if (vals[0] == vals[1] && vals[1] == vals[2]) || (vals[1] == vals[2] && vals[2] == vals[3]) || (vals[2] == vals[3] && vals[3] == vals[4]) then return 39 + vals[2]; if (vals[0] == vals[1] && vals[2] == vals[3]) || (vals[0] == vals[1] && vals[3] == vals[4]) || (vals[1] == vals[2] && vals[3] == vals[4]) then return 26 + max(vals[1], vals[2]); if vals[0] == vals[1] || vals[1] == vals[2] then return 13 + vals[1]; if vals[2] == vals[3] || vals[3] == vals[4] then return 13 + vals[3]; return vals[4]; }
Monday, October 14, 2013
Problem 52, now in APL
So, APL is an interesting. It is quite an old language, having secured for itself the excellent title of "A Programming Language." It is the language off of which J, which I like so much, is based, so it seemed only proper that I finally getting around to solving a problem in it. I ran into quite a few difficulties related to lack of decent, findable documentation, but once I could actually find out how to do things in APL, it wasn't that bad, and from here forward I would be relatively capable of writing code in APL. For those who don't know, one main cause of APL's lack of popularity is its heavy reliance on non-ASCII characters. Comments start with a ⍝, the and operator is ∧, division is performed with an actual ÷, function definitions begin with a ∇ - all sorts of fun characters that no one really wants to deal with. However, once I set up my keyboard, it wasn't too bad, and it can be kind of fun getting to, for example, actually write ← for assignment. Anyway, here is my code, which has now, yet again, freed up Squirrel for use.
∇Z ← sd x l← 10 10 10 10 10 10 d← l⊤ x Z← d[⍋d] ∇ ∇Y ← ans x s← sd x Y← (s,s,s,s,s) ≡ ((sd 2×x), (sd 3×x), (sd 4×x), (sd 5×x), (sd 6×x)) ∇ ⍝ Look only up to largest 6-digit candidate (ans ¨ ⍳166666) ⍳ 1 )OFF
Sunday, October 13, 2013
I solved a problem that was new for me
I just checked my old, pre-language challenge Project Euler account. Turns out I had never solved problem 51 on there. I actually have missed a few in the 51-100 range, so, at long last, some of the problems I will be solving will be truly new to me (though to be honest, it had been so long since I had done most of the other problems that I hardly recalled anything).
Problem 53 - C++, now considered separate from C
When I started this challenge, I considered C and C++ to be the same language as one is a subset of the other. This was reasonable at the time, especially as I began this challenge as a timed challenge with a fixed goal, and didn't want to make it too easy for myself by allowing me to use almost all languages I knew. However, now that I am around problem 53, and have experienced extreme similarities between various languages, I think that it is fair to call C and C++ distinct languages: clearly they are distinct, as C++ has so many features not in C, even though most short C++ programs look almost identical to C programs. So, here is my solution to problem 53: the problem was easy enough that I probably didn't need to use C++, but I thought I wanted to get this distinction out of the way before I needed it. The solution runs in 2ms.
Also, for this problem, I finally made a nice script to automate a large part of my work process: before I manually copied files from a working directory to the git repository and then committed, then opened up a GUI text editor to copy and paste. Now, that whole process is automated into a single script (I won't bother posting a link to the script as its mostly just a bunch of cp, cd, and git commands that are very dependent on my personal directory setup). However, I think it is worth noting my discovery of xclip, a nice program that allows copy text to the clipboard from the command line. For example, in order to paste the code for this problem below, I added in my script: cat $1 | xclip -sel clip, and now whenever I add one of my files to the git repository, I also get a copy of the file on my clipboard. Fun stuff.
Also, for this problem, I finally made a nice script to automate a large part of my work process: before I manually copied files from a working directory to the git repository and then committed, then opened up a GUI text editor to copy and paste. Now, that whole process is automated into a single script (I won't bother posting a link to the script as its mostly just a bunch of cp, cd, and git commands that are very dependent on my personal directory setup). However, I think it is worth noting my discovery of xclip, a nice program that allows copy text to the clipboard from the command line. For example, in order to paste the code for this problem below, I added in my script: cat $1 | xclip -sel clip, and now whenever I add one of my files to the git repository, I also get a copy of the file on my clipboard. Fun stuff.
#include<stdio.h> int fac(int n) { return n < 2 ? 1 : n * fac(n - 1); } bool isncrbig(int n, int r) { //we calculate very carefully to avoid //overflow, and will return true as soon //as we see a number > 1000000 int denom = fac(r); long rest = n; for (int i = n - 1; i > (n - r); --i) { rest *= i; if (rest / denom > 1000000) { return true; } } return false; } int main() { int min_r = 10; int ans = 0; for (int n = 23; n <= 100; ++n) { while (isncrbig(n, min_r - 1)) { --min_r; } ans += n - (2*min_r) + 1; } printf("%d\n", ans); return 0; }
Friday, October 11, 2013
Problem 52 - Squirrel
Squirrel is a nice C-like language with curly braces.
Problem 52 was not terribly hard to begin with.
My solution runs in .646s.
Squirrels are cool.
I am in the middle of writing my own esolang based on them that may eventually come to fruition, but alas, Squirrel is not as arcane as that language plans to be.
Problem 52 was not terribly hard to begin with.
My solution runs in .646s.
Squirrels are cool.
I am in the middle of writing my own esolang based on them that may eventually come to fruition, but alas, Squirrel is not as arcane as that language plans to be.
function digits(x) { local arr = []; while (x > 0) { arr.append(x % 10); x /= 10; } return arr; } function arePermuts(x, y) { local xdigs = digits(x); local ydigs = digits(y); xdigs.sort(@(a,b) a <=> b); ydigs.sort(@(a,b) a <=> b); if (xdigs.len() == ydigs.len()) { for (local i = 0; i < xdigs.len(); ++i) { if (xdigs[i] != ydigs[i]) { return false; } } return true; } return false; } function mag(x) { if (x < 10) { return 10; } else { return 10 * mag(x / 10); } } local n = 1; for(;;) { if (mag(n) < mag(6*n)) { n = mag(n); } else { if (arePermuts(n, 2*n) && arePermuts(2*n, 3*n) && arePermuts(3*n, 4*n) && arePermuts(4*n, 5*n) && arePermuts(5*n, 6*n)) { print(n + "\n"); break; } else { n += 1; } } }
Problem 51 - Cobra
Cobra is, surprisingly, a language based on Python, but with lots of other exciting stuff like optional static typing, generics, and more object-orientedness (all code must be wrapped in a class with a main method...as such all functions are methods of a class, and need to be called with a preceding . as shorthand for this. - forgetting that . was the source of all my errors in this problem). Anyway, despite a few quirks that took getting used to, it was almost as nice to work with as Python, so it didn't take too hard to solve this relatively hard problem (though it took a change to a smart approach to solve: iterating over all primes is very slow, so instead I iterate over 'masks' to make primes out of [the problem is to find what prime is the smallest prime that generates 8 primes if you replace some digits of the number with the same digit for 0..9]. Now I have moved past 50, and between this problem and my memory, the problems do start to get moderately hard from here on out. I imagine I won't be writing too many new solutions in new languages for too much longer, as the supply of nice, easy-to-learn languages is constantly dwindling. I do still have Squirrel around as an option though, and I think that I will allow C++ and C# to be options in the future, instead of lumping them into the same 'language' as C.
runs in .1s
class E51 def numDigits(x as int) as int if x < 10 return 1 else return 1 + .numDigits(x // 10) def isPrime(p as int) as bool if p < 2 or p % 2 == 0 return p == 2 n = 3 while n*n <= p if p % n == 0 return false n += 2 return true def numPrimesSameChange2(p as int) as int digs = .numDigits(p) + 2 count as int = 0 ans = 0 for i in 0:digs-1 for j in i+1:digs tcount as int = 0 b = (p % (10 ** i)) + (p // (10 ** i)) * (10 ** (i+1)) b = (b % (10 ** j)) + (b // (10 ** j)) * (10 ** (j+1)) seenOne = false tempans = 0 for k in 0:10 if .numDigits(b) < .numDigits(10 ** j) and k == 0 #cant have leading 0s continue if .isPrime(b + k*(10 ** i + 10 ** j)) tcount += 1 if not seenOne tempans = (b + k*(10 ** i + 10 ** j)) seenOne = true if tcount > count count = tcount ans = tempans if count == 8 print ans return count def numPrimesSameChange3(p as int) as int digs = .numDigits(p) + 3 count as int = 0 ans = 0 for i in 0:digs-2 for j in i+1:digs-1 for k in j+1:digs tcount as int = 0 b = (p % (10 ** i)) + (p // (10 ** i)) * (10 ** (i+1)) b = (b % (10 ** j)) + (b // (10 ** j)) * (10 ** (j+1)) b = (b % (10 ** k)) + (b // (10 ** k)) * (10 ** (k+1)) seenOne = false tempans = 0 for l in 0:10 if .numDigits(b) < .numDigits(10 ** k) and l == 0 #cant have leading 0s continue if .isPrime(b + l*(10 ** i + 10 ** j + 10 ** k)) tcount += 1 if not seenOne tempans = (b + l*(10 ** i + 10 ** j + 10 ** k)) seenOne = true if tcount > count count = tcount ans = tempans if count == 8 print ans return count def main for p in 10:10000 if .numPrimesSameChange3(p) >= 8 or .numPrimesSameChange2(p) >= 8 break
Problem 21 Redux - COBOL
In the past, I considered trying COBOL out once or twice, and always came against dead ends. This time, however, hardened through experiences with Assembly and INTERCAL, everything worked out fairly well. Despite COBOL certainly not being the most user-friendly language, by reading enough examples and such on the internet I managed to gain a good enough sense of it to convert my solution to problem 21 that I wrote in Squirrel to COBOL. Now, I have Squirrel free, and it will certainly get some use (with a name like Squirrel and C-like syntax, its pretty good), and more importantly, now I shouldn't have to touch COBOL ever again. Though there are plenty of older languages like ALGOL out there for me to try.
IDENTIFICATION DIVISION. PROGRAM-ID. Euler21. DATA DIVISION. WORKING-STORAGE SECTION. 01 LoopCount PIC S99999 VALUE ZEROS. 01 LoopCount2 PIC S99999 VALUE ZEROS. 01 Result PIC S99999 VALUE ZEROS. 01 Temp PIC S99999 VALUE ZEROS. 01 Temp2 PIC S99999 VALUE ZEROS. 01 X PIC S99999 VALUE ZEROS. 01 SQRX PIC S99999 VALUE ZEROS. 01 ANS PIC S99999 VALUE ZEROS. PROCEDURE DIVISION. Begin. PERFORM mainLoopBody WITH TEST AFTER VARYING LoopCount2 From 3 By 1 UNTIL LoopCount2 Equal 9999. DISPLAY ANS. STOP RUN. sumOfDivisors. SUBTRACT Result FROM Result. ADD 1 TO Result. COMPUTE SQRX = FUNCTION SQRT (X). MULTIPLY SQRX BY SQRX GIVING Temp. IF Temp EQUAL X THEN ADD SQRX TO Result END-IF. SUBTRACT 2 FROM SQRX. PERFORM LoopBody WITH TEST AFTER VARYING LoopCount FROM 2 BY 1 UNTIL LoopCount GREATER THAN SQRX. LoopBody. COMPUTE Temp = FUNCTION MOD (X LoopCount). IF Temp EQUAL ZERO THEN ADD LoopCount to Result DIVIDE X By LoopCount GIVING TEMP ADD Temp to Result END-IF. mainLoopBody. COMPUTE X = LoopCount2. PERFORM sumOfDivisors. COMPUTE Temp2 = Result. COMPUTE X = Temp2. PERFORM sumOfDivisors. IF LoopCount2 NOT EQUAL Temp2 THEN IF LoopCount2 EQUAL Result THEN ADD LoopCount2 to ANS END-IF END-IF.
Wednesday, October 9, 2013
Progress
This table records all of the languages I have used on this challenge, along with which problems have been solved in which challenge. The statement of the problems can all be found on Project Euler, and my solutions are described in this blog, as well as being linked to from the table below. This table keeps growing, and keeps getting pushed lower and lower in the blog, so I keep reprinting it. The links all lead to postings of the code on github: so if you wanted all of the code, you could clone the whole repository.
BrainFuck | 1 |
Haskell | 2*,37 |
J | 3*,24*,35 |
Ruby | 4*,30*,56 |
Whenever | 2,5* |
Ook! | 6 |
Racket | 7*,26 |
K | 8*,30 |
Javascript | 9*,31 |
sML | 10*,42 |
PHP | 11 |
Go | 12*,32 |
cLisp | 13 |
C | 48*,50 |
Fortran95 | 3,15* |
Python | 16*,24*,39 |
ELM | 17*,48 |
Scala | 18*,44 |
Perl | 19 |
Java | 20 |
FALSE | 4 |
Squirrel | 21*,52*,55 |
D | 22 |
Ceylon | 23 |
Postscript | 7 |
Befunge | 27 |
Boo | 29 |
Frink | 16 |
Forth | 9 |
Shakespeare | 12 |
Bash | 33 |
Batch | 34 |
Whitespace | 36 |
LOLCODE | 10 |
Lua | 38 |
Erlang | 24 |
Rust | 40 |
Ada | 41 |
Clojure | 14 |
Coffeescript | 43 |
Prolog | 18 |
R | 45 |
Julia | 46 |
x86 | 47 |
INTERCAL | 17 |
OCaml | 49 |
COBOL | 21 |
Cobra | 51 |
C++ | 14*,53 |
APL | 52 |
Chapel | 54 |
Analytic | 5,8,15 |
Analytic | 25,28 |
50 Problems solved (the latest in C)
After a little under 2 months working through this Project Euler Language Challenge, I have solved my 50th problem. This last problem itself was not particularly hard, as I freed up C in order to make it be not so hard, but this landmark means a couple of things:
- Problems will start getting harder, so I may be solving problems with less frequency
- I will need to expand to a class of languages I have tried to avoid as much as possible: really old languages like ALGOL and COBOL (and anything that is spelled in all-caps).
- I have reached 'Level 2' on Project Euler (which just means I get a fancy little check mark on my profile page, and the satisfaction of being in the top 7.45% of users).
Also, I decided that, to mark this occasion, I would move all of my code from Dropbox, which just seems like a very informal place to be hosting code, to github, which seems far more legitimate, plus offers a viewer with syntax highlighting for more languages than just Java. I will continue inlining the code here, but the links from the table will now all point to github.
Anyway, here is my code for problem 50, and hopefully I will solve 50 more in due time.
#include<stdio.h> #include<stdlib.h> int isPrime(int n) { if (n < 2 || n % 2 == 0) { return n == 2; } int i = 3; for (i = 3; i*i <= n; ++i) { if (n % i == 0) { return 0; } } return 1; } int partialSum(int* arr, int begin, int end) { int sum = 0; int i; for (i = begin; i < end; ++i) { sum += arr[i]; } return sum; } int main(int argc, char** argv) { int ans = 0; int chainLength = 1; //78498 = pi^-1(1000000) int* primes = (int*)malloc(78498 * sizeof(int)); int i = 2; int c = 0; //make list of primes for (i = 0; i < 1000000; ++i) { if (isPrime(i)) { primes[c] = i; ++c; } } int j; for (i = 0; i < 78498; ++i) { for (j = i+chainLength; j < 78498; ++j) { int temp = partialSum(primes,i,j); if (temp > 1000000) { break; } if (isPrime(temp)) { ans = temp > ans ? temp : ans; chainLength = j - i; } } } printf("%d\n",ans); return 0; }
Tuesday, October 8, 2013
Problem 48 - ELM
Problem 50 is drawing ever nearer, and with it, dreams of reaching level 2 and a nice round number. But I think I will like to use a familiar language to solve problem 50, but no super-familiar language was left open...so I decided to redo problem 48, which I recently did in C for the sake of expediency, but was simple enough that it only took a few minutes for me to write up a solution in ELM, which was freed up by my recent usage of INTERCAL. So, soon enough, problem 50 will be solved. When I solve problem 50, I will also switch over all of my files from dropbox to github; the repository is already made and the files are there, changing the links will be the only major hassle.
ans a i = if i > 1000 then a else (ans (mod ((subans i 1 i) + a) 10000000000) (i + 1)) subans a j i = if j == i then a else (subans (mod (a * i) 10000000000) (j + 1) i) main = asText (ans 0 1)
Monday, October 7, 2013
Problem 49 - OCaml
So, functional languages are great and all, but this problem wasn't the most fun to do in a functional language / OCaml was a bit more annoying to work with than other functional languages (or maybe I just had less patience for it than others / needed to do something more complex my first time using it). But anyway, I got a pretty reasonable program written that solves Problem 49 in about .06 seconds, so not much to complain about. Here is the program, in all of its glory...Looking back, I think 90% of my annoyance with OCaml is the need to write List.map, etc for all the list operations that are so common in functional languages. But anyway, I digress.
open Printf let dlist y = let rec digilist x l = if x < 10 then x :: l else (digilist (x / 10) ((x mod 10) :: l)) in digilist y [];; let cdigs y = let rec concatdigits l x = if l = [] then x else concatdigits (List.tl l) (x * 10 + (List.hd l)) in concatdigits y 0;; let isPrime x = let rec checkPrime y n = if n * n > y then true else if y mod n = 0 then false else checkPrime y (n +1) in checkPrime x 2;; let rec rem x l = if l = [] then [] else if (List.hd l) = x then (List.tl l) else (List.hd l) :: (rem x (List.tl l));; let rec permuts elems = if (List.tl elems) = [] then [[List.hd elems]] else List.concat (List.map (fun (x) -> (List.map (fun (l) -> x :: l) (permuts (rem x elems)))) elems);; let rec validArith n perms = let rec helper n2 dif rest = if rest = [] then [] else if (List.hd rest) - n2 = dif then n :: n2 :: [List.hd rest] else helper n2 dif (List.tl rest) in if (List.length perms) = 1 then [] else let help = helper (List.hd perms) ((List.hd perms) - n) (List.tl perms) in if List.length help = 3 then help else validArith n (List.tl perms);; let rec compress = function | a :: (b :: _ as t) -> if a = b then compress t else a :: compress t | smaller -> smaller;; let rec findans n = if n = 10000 then [] else if isPrime n then let pperms = (List.filter (fun (z) -> z >= n) (compress (List.sort (fun x y -> x - y) (List.filter isPrime (List.map cdigs (permuts (dlist n))))))) in if (List.length pperms) >= 3 && (n != 1487) && (List.length (validArith (List.hd pperms) (List.tl pperms)) = 3) then validArith (List.hd pperms) (List.tl pperms) else findans (n + 1) else findans (n + 1);; List.iter (printf "%d") (findans 1100); print_string "\n"
Tuesday, October 1, 2013
INTERCAL - Doing Problem 17, the hard way
There are a lot of crazy languages out there. Most of the crazier languages I have used were invented sometime in the last decade, by crazy people who wanted to see what would be hard to write a compiler for or just to have fun, etc, etc. INTERCAL is not like those languages. INTERCAL was written in 1972 at Princeton in order to be as different from other languages as possible. I will admit that I took a wimpy approach to INTERCAL: the language has two binary operators, mingle ($), which makes a 32-bit value out of 2 16-bit values and alternating the digits, and select (~) which takes the bits of the right value where the left has 1's and shifts all those to the right to form a number. I did not put up with these or the unary or, and + xor, which operate on alternating digits. Instead, I used the standard libraries. With the Standard libraries, Adding two numbers is as simple as a DO (1509) NEXT instruction while the numbers you want to add are in :1 and :2 (those being variable names).
Anyway, despite ignoring those variables, there were plenty of difficulties. INTERCAL has no ifs, no gotos, no most anything that is in any other language. There are only NEXT instructions which push instructions onto a call stack, where they can be manipulated with FORGET or RESUME, and, of course, everyone's favorite, COME FROM (the opposite of GO TO, which is not in the language).
So, with all of these fun things to keep up with, there are some even more fun things in INTERCAL: the errors. Among the compile and run time errors I had to solve while writing this program were
THE NEXT STACK RUPTURES. ALL DIE. OH, THE EMBARRASSMENT!
WHAT BASE AND/OR LANGUAGE INCLUDES 23?
RANDOM COMPILER BUG
PROGRAM HAS GOTTEN LOST ON THE WAY TO WHO KNOWS WHERE
PROGRAM HAS DISAPPEARED INTO THE BLACK LAGOON
THROW STICK BEFORE RETRIEVING!
YOU MUST LIKE THIS LABEL A LOT!
PROGRAMMER IS INSUFFICIENTLY POLITE
And that isn't even all of them. The last one has a particularly good story: all INTERCAL commands must be prefixed with either DO, PLEASE, or PLEASE DO. Put too many PLEASEs, you get an error for being overly polite, too few, insufficiently polite: the programmer must remember to keep a delicate balance.
This INTERCAL program is the result of about 4 days of working with the language, with varying degrees of effort on those days. This is not only the first and longest INTERCAL program I have written, but it is actually as of now the longest Project Euler solution I have written. This solution opens up ELM, the language I previously solved problem 17 in, so be on the lookout for the next appearance of that functional language that compiles to html and Javascript.
Anyway, despite ignoring those variables, there were plenty of difficulties. INTERCAL has no ifs, no gotos, no most anything that is in any other language. There are only NEXT instructions which push instructions onto a call stack, where they can be manipulated with FORGET or RESUME, and, of course, everyone's favorite, COME FROM (the opposite of GO TO, which is not in the language).
So, with all of these fun things to keep up with, there are some even more fun things in INTERCAL: the errors. Among the compile and run time errors I had to solve while writing this program were
THE NEXT STACK RUPTURES. ALL DIE. OH, THE EMBARRASSMENT!
WHAT BASE AND/OR LANGUAGE INCLUDES 23?
RANDOM COMPILER BUG
PROGRAM HAS GOTTEN LOST ON THE WAY TO WHO KNOWS WHERE
PROGRAM HAS DISAPPEARED INTO THE BLACK LAGOON
THROW STICK BEFORE RETRIEVING!
YOU MUST LIKE THIS LABEL A LOT!
PROGRAMMER IS INSUFFICIENTLY POLITE
And that isn't even all of them. The last one has a particularly good story: all INTERCAL commands must be prefixed with either DO, PLEASE, or PLEASE DO. Put too many PLEASEs, you get an error for being overly polite, too few, insufficiently polite: the programmer must remember to keep a delicate balance.
This INTERCAL program is the result of about 4 days of working with the language, with varying degrees of effort on those days. This is not only the first and longest INTERCAL program I have written, but it is actually as of now the longest Project Euler solution I have written. This solution opens up ELM, the language I previously solved problem 17 in, so be on the lookout for the next appearance of that functional language that compiles to html and Javascript.
(3) DO NOT GIVE UP (2000) PLEASE NOTE THIS IS A MODULUS FUNCTION DO STASH :1 + :2 + :196 DO (1550) NEXT DO :196 <- :1 PLEASE DO :1 <- :3 DO (1540) NEXT DO :197 <- :2 PLEASE DO :1 <- :196 DO :2 <- :3 DO (1510) NEXT DO RETRIEVE :1 + :2 + :196 PLEASE RESUME #1 (2010) PLEASE DO NOTE THIS FCN GIVES SINGLE DIGIT LETTERS DO NOTE :2 <- LETTERS(:1) DO STASH :1 + :3 + :4 (19) DO (18) NEXT (29) DO :2 <- #4 (18) DO (17) NEXT (28) PLEASE DO :2 <- #5 (17) DO (16) NEXT (27) DO :2 <- #5 (16) DO (15) NEXT (26) PLEASE DO :2 <- #3 (15) DO (14) NEXT (25) DO :2 <- #4 (14) DO (13) NEXT (24) DO :2 <- #4 (13) PLEASE DO (12) NEXT (23) DO :2 <- #5 (12) DO (11) NEXT (22) DO :2 <- #3 (11) DO (10) NEXT (21) DO :2 <- #3 (10) DO (100) NEXT (20) DO :2 <- #0 (100) PLEASE DO :2 <- #1 DO (1509) NEXT DO :1 <- :3 PLEASE RESUME :1 DO COME FROM (29) DO COME FROM (28) DO COME FROM (27) PLEASE DO COME FROM (26) DO COME FROM (25) DO COME FROM (24) DO COME FROM (23) DO COME FROM (22) DO COME FROM (21) DO COME FROM (20) DO :4 <- :2 DO :2 <- :1 DO :1 <- #10 DO (1510) NEXT DO :2 <- :4 PLEASE DO FORGET :3 DO NOT RETRIEVE :1 + :3 + :4 PLEASE RESUME #1 (2020) DO NOTE THIS FCN GIVES TWO DIGIT LETTERS DO NOTE :2 <- LETTERS(:1) PLEASE STASH :1 + :3 + :4 + :5 + :6 + :7 + :14 (39) DO (38) NEXT (49) DO :5 <- #6 (38) DO (37) NEXT (48) DO :5 <- #6 (37) DO (36) NEXT (47) PLEASE DO :5 <- #7 (36) DO (35) NEXT (46) DO :5 <- #5 (35) DO (34) NEXT (45) DO :5 <- #5 (34) DO (33) NEXT (44) PLEASE DO :5 <- #5 (33) DO (32) NEXT (43) DO :5 <- #6 (32) DO (31) NEXT (42) PLEASE DO :5 <- #6 (31) DO (30) NEXT (41) DO (2030) NEXT (30) DO (200) NEXT (40) DO :5 <- #0 (200) PLEASE DO :2 <- #10 DO :14 <- :1 DO (1550) NEXT DO :1 <- :3 DO :2 <- #1 DO (1509) NEXT DO :7 <- :3 PLEASE RESUME :7 DO COME FROM (49) DO COME FROM (48) DO COME FROM (47) DO COME FROM (46) DO COME FROM (45) PLEASE DO COME FROM (44) DO COME FROM (43) DO COME FROM (42) DO COME FROM (40) PLEASE DO :1 <- :14 DO :2 <- #10 DO (2000) NEXT PLEASE DO :1 <- :3 DO (2010) NEXT DO :1 <- :5 DO (1509) NEXT PLEASE DO COME FROM (41) DO :6 <- :3 DO :2 <- :7 DO :1 <- #10 PLEASE DO (1510) NEXT DO FORGET :3 DO :2 <- :6 DO RETRIEVE :1 + :3 + :4 + :5 + :6 + :7 + :14 PLEASE RESUME #1 (2030) DO NOTE THIS IS THE TEENS FUNCTION DO NOTE :3 <- LETTERS(:14) DO STASH :1 + :2 + :5 + :6 (59) DO (58) NEXT (69) DO :6 <- #8 (58) DO (57) NEXT (68) DO :6 <- #8 (57) DO (56) NEXT (67) DO :6 <- #9 (56) DO (55) NEXT (66) PLEASE DO :6 <- #7 (55) DO (54) NEXT (65) DO :6 <- #7 (54) DO (53) NEXT (64) DO :6 <- #8 (53) DO (52) NEXT (63) DO :6 <- #8 (52) DO (51) NEXT (62) PLEASE DO :6 <- #6 (51) DO (50) NEXT (61) DO :6 <- #6 (50) DO (300) NEXT (60) DO :6 <- #3 (300) DO :1 <- :14 DO :2 <- #10 PLEASE DO (2000) NEXT DO :1 <- :3 DO :2 <- #1 DO (1509) NEXT PLEASE RESUME :3 DO COME FROM (69) DO COME FROM (68) DO COME FROM (67) DO COME FROM (66) DO COME FROM (65) PLEASE DO COME FROM (64) DO COME FROM (63) DO COME FROM (62) DO COME FROM (61) PLEASE DO COME FROM (60) DO :2 <- :3 DO :1 <- #10 DO (1510) NEXT DO FORGET :3 PLEASE DO :3 <- :6 DO RETRIEVE :1 + :2 + :5 + :6 PLEASE RESUME #1 (2040) PLEASE DO NOTE THIS IS THE EVERYTHING FCN DO NOTE :6 <- LETTERS(:1) DO STASH :1 + :2 + :3 + :5 + :7 DO :5 <- :1 (101) DO (102) NEXT (111) DO NOT GIVE UP (102) DO (103) NEXT DO FORGET #1 PLEASE DO :1 <- :5 DO (2020) NEXT (112) DO :6 <- :2 (103) PLEASE DO :1 <- :5 DO :2 <- #100 DO (1550) NEXT DO :1 <- :3 DO :2 <- :3 DO (1550) NEXT PLEASE DO :1 <- :3 DO :2 <- #1 DO (1509) NEXT DO RESUME :3 DO COME FROM (111) DO :1 <- :5 DO :2 <- #100 DO (1550) NEXT DO :1 <- :3 PLEASE DO (2010) NEXT DO :6 <- :2 DO :1 <- :6 DO :2 <- #7 DO (1509) NEXT PLEASE DO :6 <- :3 (90) DO (91) NEXT DO :1 <- :6 DO :2 <- #3 DO (1509) NEXT PLEASE DO :6 <- :3 DO :1 <- :5 DO :2 <- #100 DO (2000) NEXT DO :1 <- :3 DO (2020) NEXT PLEASE DO :1 <- :6 DO (1509) NEXT (96) DO :6 <- :3 (91) DO (92) NEXT (95) DO FORGET #1 (92) DO :1 <- :5 DO :2 <- #100 DO (2000) NEXT DO :1 <- :3 PLEASE DO :2 <- :3 DO (1550) NEXT DO :1 <- :3 DO :2 <- #1 PLEASE DO (1509) NEXT DO RESUME :3 DO COME FROM (95) DO COME FROM (96) DO COME FROM (112) DO RETRIEVE :1 + :2 + :3 + :5 + :7 PLEASE RESUME #1 DO NOTE THIS IS MAIN DO COME FROM (3) DO :206 <- #11 DO :205 <- #1 (70) DO (71) NEXT (80) DO READ OUT :206 (71) DO (72) NEXT PLEASE DO :1 <- :205 DO (2040) NEXT DO :1 <- :205 PLEASE DO :2 <- #1 DO (1509) NEXT DO :205 <- :3 PLEASE DO :1 <- :6 DO :2 <- :206 DO (1509) NEXT DO :206 <- :3 PLEASE DO FORGET #2 DO (70) NEXT (72) DO :1 <- :205 DO :2 <- #1000 DO (1550) NEXT PLEASE DO :1 <- :3 DO :2 <- #1 DO (1509) NEXT PLEASE RESUME :3 DO COME FROM (80) PLEASE DO GIVE UP
Subscribe to:
Posts (Atom)