Problem 48 - Quickly done in C

I am supposed to be writing a paper for a class. I got about 3 sentences done of it, so it seemed like a good time to take a break and solve a project Euler problem. This problem was quite easy, and I used C for the sake of expediency and ease, but I would not be too surprised if I come back soon and redo this problem in a pretty crazy language - 64 bit integers, modulus, multiplication, and control structures are really all that is needed to solve this problem in the blink of an eye. (well, 16ms, which I imagine is less than the time it takes to blink an eye).

#include <stdio.h>

int main(int argc, char** argv) {
    const unsigned long long BIG  = 10000000000;
    unsigned long long ans       = 0;
    unsigned long long summand   = 0;
    unsigned long long i;
    unsigned long long j;
    for (i = 1; i <= 1000; ++i) {
        summand = i;
        for (j = 1; j < i; ++ j) {
            summand *= i;
            summand %= BIG;
        }
        ans += summand;
        ans %= BIG;
    }
    printf("%lld\n",ans);
}

Problem 47 - x86 assembly

Yesterday I wrote my first x86 assembly code for one of my cs classes, and after finishing the assignment, rather than being exhausted from the effort or frustration or anything else, I had a feeling of satisfaction, having found working in assembly somewhat fun (at least at the relatively small scales I am still working at). So, as not to let that fun end, I decided to use x86 assembly on a Project Euler problem, and, as luck would have it, the problem I was up to, problem 47, was one that was not particular hard (for me, at least) to write in assembly - no need for copious variables, arrays, or any other sort of high-level language features that I would not be able to deal with. I am starting to think that all the drudgery with esoteric and otherwise dumb languages that I have had to put up with in the last month has made me immune to frustrations with programming languages or having too many difficulties switching between modes of computation - after learning how to write whitespace well, assembly is hardly a challenge, even if imul is implemented in a really stupid manner. Anyway, without further ado, here is my code, which runs in about .6s (to see the answer, I call e47 and use printf from a C program - the extra linking, etc that would be required to do this without touching C seemed unnecessary).

    .text
    .globl  isPrime
    .type   isPrime,@function
isPrime:
    pushq   %rbx
    pushq   %r12
    pushq   %r13
    pushq   %r14
    pushq   %r15
    movl    %edi,%ebx   # ebx = n
    cmpl    $2,%ebx     # n < 2
    jl      finif       # return 0
    movl    %ebx,%eax   # temp = 2
    andl    $1,%eax     # temp&= 1
    cmpl    $0,%eax     # n % 2 == 0
    je      finic       # return n == 2
    movl    $3,%r12d    # i = 3
loop:
    movq    $0,%rdx     # clear rdx for mul
    movl    %r12d,%eax  # put i in eax for mul
    imull   %r12d       # eax = i * i
    cmpl    %ebx,%eax   # i * i <= n
    jg      overloop
    movq    $0,%rdx     # clear rdx for div
    movl    %ebx,%eax   # put n in eax for div
    idivl   %r12d       # edx = n % i
    cmpl    $0,%edx     # n % i == 0
    je      finif       # return 0
    addl    $2,%r12d    # i+=2
    jmp     loop
overloop:
    movq    $1,%rax     # return 1
    jmp     fini
finif:
    movq    $0,%rax     # return 0
    jmp     fini
finic:
    cmpl    $2,%ebx     # n == 2
    jne     finif
    movq    $1,%rax     # return 1
fini:
    popq    %r15
    popq    %r14
    popq    %r13
    popq    %r12
    popq    %rbx   
    ret
    .size   isPrime,.-isPrime

    .text
    .globl  pfc
    .type   pfc,@function
pfc:
    pushq   %rbx
    pushq   %r12
    pushq   %r13
    pushq   %r14
    pushq   %r15
    movl    %edi,%ebx   # ebx = n
    movl    $0,%r13d    # fc  = 0
    movl    $2,%r12d    # i = 2
loop2:
    movl    %ebx,%edi   # n is param 1
    call    isPrime     # isPrime(n)
    cmpl    $1,%eax     # if true
    je      finish
    cmpl    $3,%r13d    # if fc is 3 and not prime, return false
    je      finishFalse
    movq    $0,%rdx     # clear rdx for div
    movl    %ebx,%eax   # put n in eax for div
    idivl   %r12d       # eax: n%i, edx: n/i
    cmpl    $0,%edx     # n%i == 0
    jne     overif
    movl    %eax,%ebx   # n /= i
    incl    %r13d       # fc++
divloop:                # perform extra divisions of the factor
    movq    $0,%rdx     # clear rdx for division
    movl    %ebx,%eax   # put n in eax for div
    idivl   %r12d       # compute division again
    cmpl    $0,%edx     # n%i == 0
    jne     overdivloop
    movl    %eax,%ebx   # n /= i
    movl    %ebx,%edi   # n is param 1
    call    isPrime     # we must recheck primality here
    cmpl    $1,%eax     # if isPrime
    je      finish
    cmpl    $1,%ebx     # if 1
    je      finish
    jmp     divloop
overdivloop:
overif:
    incl    %r12d       # i++
    jmp     loop2
overloop2:
finish:
    cmpl    $3,%r13d    # fc == 3
    je      finishTrue
finishFalse:
    movq    $0,%rax  
    jmp     veryend
finishTrue:
    movq    $1,%rax
veryend:
    popq    %r15
    popq    %r14
    popq    %r13
    popq    %r12
    popq    %rbx   
    ret
    .size pfc,.-pfc
    
    .text
    .globl  e47
    .type   e47,@function
e47:
    pushq   %rbx
    pushq   %r12
    pushq   %r13
    pushq   %r14
    pushq   %r15
    movl    $210,%ebx   # N = 210 (lowest possible num)
    movl    $0,%r12d    # count = 0
loop3:
    movl    %ebx,%edi   # N is param 1
    call    pfc
    cmpl    $1,%eax     # pfc(N) == 1
    jne     elsepart
    incl    %r12d       # count++
    cmpl    $1,%r12d    # count == 1
    jne     overif2
    movl    %ebx,%r13d  # r13d = first in seq
overif2:
    cmpl    $4,%r12d    # count == 4
    je      thefinish   # we are done
    jmp     overif3
elsepart:
    movl    $0,%r12d    # clear the count
overif3:
    incl    %ebx
    jmp     loop3
thefinish:
    movl    %r13d,%eax
    popq    %r15
    popq    %r14
    popq    %r13
    popq    %r12
    popq    %rbx   
    ret
    
    .size e47,.-e47

Problem 46 - Julia

I haven't solved a problem in a esoteric language too recently - rest assured, I am sure I will move back to esolangs soon, INTERCAL beckons. For now, however, there are still some entirely reasonable languages left for me to take advantage of. Most recently, I have used Julia - a language apparently designed like MATLAB and R with mathematical computation in mind, and like so many other languages I have used recently (especially with the stark contrast from things like Whitespace not too long ago), it was a very easy language to pick up and use for something not too bad like this. This problem involved Goldbach's "other" conjecture which conjectured that every odd composite was the sum of a prime and two times a square; this program disproves that conjecture in a handful of seconds.

function isPrime(x)
    if x < 2 || x % 2 == 0
        return x == 2
    end
    i = 3
    while i * i <= x
        if x % i == 0
            return false
        end
        i += 1
    end
    return true
end

primes = [2]
for i = 3:10000
    if isPrime(i)
        primes = [primes..., i]
    end
end

squares = [0]
for i = 1:1000
    squares = [squares..., i * i]
end

x = 7
while true
    gotans = false
    for p in primes
        done = false
        if p > x
            println(x)
            gotans = true
            break
        end
        for s in squares
            if x == p + 2*s
                done = true
                break
            end
            if p + 2*s > x
                break
            end
        end
        if done
            break
        end
    end
    if gotans
        break
    end
    x += 2
end

Problem 45 - R

Believe it or not, there are still real programming languages that I have yet to use, and among them was R, a language specifically designed for mathematical/statistical analysis, and thus a language that is pretty well suited to Project Euler. Didn't have too many problems with this one - the biggest issue was having to realize that a "double" is a double-precision integer (like a long in C), because I needed those for this.

hex <- function(n) n*(2*n-1)

isPent <- function(p) {
    root <- as.double(sqrt(24*p + 1))
    (root * root == 24*p + 1) && ((root + 1) %% 6 == 0)
}

for (i in 144:30000) {
    h <- hex(i)
    if (isPent(h)) {
        print(h)
        break
    }
}

Problem 44 - Scala

I solved problem 44 in Scala, after just having freed it up with Prolog. This problem was relatively easy, so I didn't really need to bring in Scala, which is relatively one of the "big guns" (being a language that I am pretty familiar with), but I wanted to get another problem done and move as quickly as possible towards number 50. This solution very well may be replaced by a solution in a more difficult language soon.

object e44 {
  def min(x : Int, y : Int) : Int = if (x < y) x else y

  def isPent(p : Int) : Boolean = {
    val root =  math.sqrt(24 * p + 1).asInstanceOf[Int]
    return (root * root == 24*p + 1) && ((root + 1)% 6 == 0)
  }

  def pent(n : Int) : Int = n * (3 * n - 1) / 2

  def main(args: Array[String]) {
    var D = 1000000000
    var p1 = 0
    var p2 = 0
    for (i <- 1 to 10000) {
      for (j <- (i+1) to 10000) {
        p1 = pent(i)
        p2 = pent(j)
        if (isPent(p1 + p2) && isPent(p2 - p1)) {
          D = min(D, p2 - p1)
        }
      }
    }
    println(D)
  }
}

Introduction

I am Sam Donow, a Sophomore at Williams College, and this is my blog for a language challenge of mine related to Project Euler.

There are now 50 posts on this blog, and the introductory post explaining what I am doing is way at the bottom, so I feel as though I ought to restate what I am doing.

Project Euler is a collection of increasingly difficult mathematical problems which are expected to require computers to solve. People are drawn to Project Euler for various reasons - mental stimulation, interest in the mathematics of the problems, a wish for something to do when learning a new programming language, etc. My goal is to solve as many of the problems in as many different languages as possible. At the time of this writing, I have solved 43 problems in almost as many language (why "almost as many" will be explained below). I plan on going for as long as I can - there are a LOT of programming languages out there, and whenever it seems like I might be running out of reasonable new languages to use, something that I had forgotten before springs up.

The challenge began as part of a 24-hackathon, where I attempted to and succeeded at solving 20 problems in 20 different languages. Since then, it has continued for over a month of non-continuous work. Below are some of the formal rules I have set down for myself, in the form that I am currently following.

• In order to make the challenge well-defined, I must have a well-defined metric of difference for languages. For this metric, I consider different revisions of a language to all be the same - so Fortran 95 is the same as Fortran 77, Java 7 is the same as Java 5, etc. In the past I have considered other languages, like C and C++ as the same for my purposes, but I will likely reverse that soon due to them being no more similar than some other language pairs.
• I can re-solve problems I have already solved in a different language, and reuse the language that I originally used to solve the first problem. The reason for this rule is to promote me solving problems frequently - If I think I may eventually solve problem 44 in INTERCAL, then  without this rule I would have to wait until I had the time to learn and use INTERCAL, but with this language, I can solve numerous problems in relatively easy languages frequently, and then every once and a while go back and use a crazy language.

And those are basically the rules. I am still going through the problems, and still having tons of fun discovering and using new/old/crazy languages. Just today I solved a problem in Prolog, and now I am only 7 problems away from having solved 50, which would bring my profile to level 2 and put it in the 92nd percentile of Project Euler users, despite the fact that most (all?) of the other users have not solved problems under the crazy restrictions I am solving them under.

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.

BrainFuck	1
Haskell	2*,37
J	3*,24*,35
Ruby	4*,30
Whenever	2,5*
Ook!	6
Racket	7*,26
K	8*
Javascript	9*,31
sML	10*,42
PHP	11
Go	12*,32
cLisp	13
C/C++	14*,48*,50
Fortran95	3,15*
Python	16*,24*,39

ELM	17*,48
Scala	18*,44
Perl	19
Java	20
FALSE	4
Squirrel	21
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
Analytic	5,8,15
Analytic	25,28

Problem 18 redo - Prolog

I used Prolog briefly a long time ago, around the time that I first got into Project Euler and solved programs in Scheme, but it has been a very long time, and I never did anything vaguely useful with it. So, now I decided to use it for a Project Euler problem. I didn't have very fond memories of my brief foray into Prolog, but after solving this problem in Prolog, I have found that it can actually be a pretty nice language, and I may want to use it for some future problems. It is certainly very different from most other languages, being a logical language and all, calculating through inferences on and trees and such, but it worked out in the end.

My first solution to this problem in Prolog accidentally ended up having exponential complexity and took a couple minutes to run, but this solution below runs in less than a milisecond (it requires Prolog to perform only 799 inferences). Solving this problem in Prolog freed up Scala, but now I would not be surprised if some time down the line I use some sillier language for this problem and recover Prolog.

getRow(R, Row) :-
nth0(R, [[75],
 [95,64],
 [17,47,82],
 [18,35,87,10],
 [20,4,82,47,65],
 [19,1,23,75,3,34],
 [88,2,77,73,7,63,67],
 [99,65,4,28,6,16,70,92],
 [41,41,26,56,83,40,80,70,33],
 [41,48,72,33,47,32,37,16,94,29],
 [53,71,44,65,25,43,91,52,97,51,14],
 [70,11,33,28,77,73,17,78,39,68,17,57],
 [91,71,52,38,17,14,91,43,58,50,27,29,48],
 [63,66,4,68,89,53,67,30,73,16,69,87,40,31],
 [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]], Row).

max(X, Y, Y) :- Y >= X.
max(X, Y, X) :- X >= Y.

prepend([], Z, [Z]).
prepend([X|Y], Z, [Z,X|Y]).

combineRows([X, Y], [Z], Row) :-
    XZ is X + Z,
    YZ is Y + Z,
    max(XZ, YZ, N),
    prepend([], N, Row).

combineRows([X,Y|T1], [Z|T2], Row) :-
    XZ is X + Z,
    YZ is Y + Z,
    max(XZ, YZ, N),
    combineRows([Y|T1], T2, Tail),
    prepend(Tail, N, Row).

ans(14, W) :- getRow(14, W).
ans(N, W)  :-
    N1 is N + 1,
    getRow(N, Top),
    ans(N1, Bottom),
    combineRows(Bottom, Top, W).

%% Command to Find the Answer:
e18(W) :- ans(0, List),
    nth0(0, List, W).

Problem 43 - Coffeescript

Another language that falls in the "fairly boring" category. I can tell that there are nicer ways to do this problem, but most nice ways are a lot harder than the easy way, but the easy way is only easy in a language with nice features like arrays. So, as it is the middle of the week and I should probably spend most of my time on classwork, I decided to go the easy way on this problem - maybe I will go the hard way some time later. I used Coffeescript for this problem, a language that compiles to javascript but which is in some ways nicer for some things according to its proponents - it wasn't too hard a language to use, even if it does have some strange features.

Anyway, here is the coffeescript code (oh what a creative name that was...)

concatDigits = (digits) ->
    sum = 0
    for i in digits
        do(i) ->
            sum = sum*10 + i
    return sum


hasProperty = (digits) ->
    if (concatDigits(digits[1..3]) % 2 is 0 and 
       concatDigits(digits[2..4]) % 3 is 0 and
       concatDigits(digits[3..5]) % 5 is 0 and
       concatDigits(digits[4..6]) % 7 is 0 and
       concatDigits(digits[5..7]) % 11 is 0 and
       concatDigits(digits[6..8]) % 13 is 0 and
       concatDigits(digits[7..])  % 17 is 0)
        concatDigits(digits)
    else
        0
    
fac = (x) => if x < 2 then 1 else x * fac(x - 1)
NthLP = (N, p, rem) ->
    if rem.length == 1 then return p.concat(rem)
    k = fac(rem.length - 1)
    index = Math.floor(N / k)
    p.push(rem[index])
    rem = if index is 0
            rem[1..]
          else if index is rem.length - 1
            rem[..-2]
          else 
            rem[..index-1].concat(rem[index+1..])
    return NthLP(N % k, p, rem)

sum = 0
i = 0
while i < fac(10)
    digits = NthLP(i, [], j for j in [0..9])
    sum += hasProperty(digits)
    i += 1
console.log(sum)

Problem 14 redo - Clojure

Given the fact that I can mostly only find time to solve Euler problems on weekends, I thought it would be a shame to have only done two problems this weekend, so I squeezed in another. Problem 43 looks a little bit daunting to jump into with a hard-to-use language, so I decided to free up a nice language from a while ago that I may or may not use directly for problem 43, but which will certainly be useful to have free - C (or C++, I have been considering them "the same" for my purposes, but now that I am expanding this challenge out so far..maybe I will allow the two to be used separately).

Anyway, I used C back in the initial 24 hour hackathon stage of this challenge for a rather easy problem involving collatz sequences - I used it during the "home stretch" when I had about as many language I knew left as problems left to solve. I decided to noq resolve this problem in clojure. Clojure turns out to be a pretty nice functional language...for whatever reason I had difficulties starting with it before, but now that I know that it is not too different from most lisps/schemes, I may eventually reclaim and reuse it. But anyway, here is my solution to problem 14 in Clojure (runs in about 15s...but Clojure runs in the JVM and does not seem to be fast by any stretch of the imagination).

(defn collatz-count [n c]
    (if (= 1 n) (+ c 1)
        (if (= 0 (mod n 2)) (collatz-count (/ n 2) (+ c 1))
            (collatz-count (+ (* 3 n) 1) (+ c 1)))))

(defn mmax [x y] (if (< (first x) (first y)) y x))

(println (second (reduce mmax (map #(list (collatz-count % 0) %) (range 1 1000000))))) 

Problem 42 - sML

I still had sML free from a while ago, and it is a language that I like and know what I am doing in, so it was a good break from a brief attempt to learn COBOL. Below is my solution for problem 42 in sML (runs in about .1s)

open TextIO
open String

val ins = TextIO.openIn "words.txt";
fun getLines s =
  case (TextIO.inputLine s) of
       SOME line => line :: (getLines s) 
     | NONE      => [];
 
fun wv (c :: cs) = if c = #"\n" then 0 
                   else ord(c) - 64 + wv(cs)
  | wv nil = 0;

 
fun wordVal s = wv(explode s);
 
(* The String package overrides map...so here is a map function *)
fun map f (x ::xs) = (f x) :: (map f xs)
  | map f nil      = nil;

fun tri n = n * (n + 1) div 2

fun contains(y, (x::xs)) = if y = x then 1 else contains(y,xs)
  | contains(y, nil)     = 0

val tris = map tri [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
foldr op+ 0 (map (fn x => contains(wordVal x, tris)) (getLines ins));

Problem 41 - Ada

So, after writing the post yesterday of all the languages that I have yet to use, I decided to use Ada to solve problem 41. I am pretty sure that the first time I solved this problem (way back when I allowed myself to use whatever language I felt like), I solved it the "dumb" way - that is, checking for primes, and then checking if those primes were pandigital or not (the problem asks for the greatest pandigital prime). This time, I solved it the much smarter way, which is to iterate over pandigitals in order to find primes (there are 409114 panditials < 1e10, and there are 50847534 primes). For the record, I do know that the method below is still slightly dumb - instead of iterating from the smallest pandigitals to the largest, and printing the last pandigital found, it would be faster to begin the search at the largest pandigital and stop the program as soon as I found the first pandigital...but oh well, my solution already runs in .6s, so I am not going to bother with that optimization.

One thing this problem taught me unrelated to Ada and primes and pandigitals is that the need to rewrite utilities is definitely going to continue to be a very annoying part of solving these problems in different languages. Of the four helper functions defined in my Ada solutions, 3 (all but concatDigits) had been written before in some other language for some other problem. But, just as I have had to write prime sieves in so many different languages, so will I have to repeat functions like "Nth lexicographic Permutation" as I jump from language to language.

With that said, without further ado, here is my solution in Ada to Project Euler problem 41.

with Ada.Text_IO; use Ada.Text_IO;
procedure e41 is
subtype Number is Long_Long_Integer range 0 .. 1000000000;
type Digit_Array is array (Positive range <>) of Number;
function isPrime (n: in Number) return Boolean is
    i : Number := 3;
begin
    if n <= 2 then
        return n = 2;
    end if;

    while i * i <= n loop
        if n mod i = 0 then
            return false;
        end if;
        i := i + 1;
    end loop;
    return true;
end isPrime;

function fac(n: in Number) return Number is
begin
    if n < 2 then
        return 1;
    end if;
    return n * fac(n - 1);
end fac;

function concatDigits(dig: Digit_Array) return Number is
begin
    if dig'Length = 1 then
        return dig(1);
    else
        return dig(dig'Last) + 10 * concatDigits(dig(dig'First .. dig'Last - 1));
    end if;
end concatDigits;

-- we iterate over n-digit pandigitals, as there are
-- 409114 n-digit pandigitals and
-- 50847534 primes that would be candidtates
-- Thus, we need the following method to find these pandigitals:
function NthLP (n: in Number; p, r: in Digit_Array) return Number is
    k : Number;
    index: Integer;
    r1: Digit_Array (1 .. r'Last - 1);
begin
    if r'Length = 1 then
        return concatDigits(p & r);
    end if;
    k := fac(r'Length - 1);
    index := Integer((n/k) + 1);
    if index = r'First then
        r1 := r(r'First + 1 .. r'Last);
    elsif index = r'Last then
        r1 := r(r'First .. r'Last - 1);
    else 
        r1 := r(r'First .. index - 1) & r(index + 1 .. r'Last);
    end if;
    return NthLP( n mod k, p & r(index), r1);
end NthLP;


dig : Digit_Array (1 .. 9) := (1, 2, 3, 4, 5, 6, 7, 8, 9);
p   : Digit_Array (1 .. 0) := (others => 0);
i: Integer;
j: Number;
cap: Number;
maxPrime: Number;
num: Number;
begin
    i := 3;
    while i <= 9 loop
        cap := fac(Number(i));
        j := 0;
        while j < cap loop
            num := NthLP(j, p, dig(1 .. i));
            if isPrime(num) then
               --as we are going in order of Lexicographic
               --permutations, this must be the largest
               maxPrime := num;
            end if;
            j := j + 1;
        end loop;
        i := i + 1;
    end loop;
    Put_Line(Long_Long_Integer'Image(maxPrime));
end e41;

1000 Pageviews!

As of today, this blog has gotten 1000 page views! I am very glad to see that this has proved at least marginally popular, and though this whole being a student thing has gotten in the way of solving problems in the last few days, I hope to be able to produce more solution in more crazy languages in order to reach the next fairly major milestone - 50 problems solved, which would place my progress in the 92.5th percentile of project Euler users, despite my crazy methodologies.

I have been for a while considering that I might be forced by morals to stop posting my code because Project Euler's policy is generally against dissemination of solutions...However, in about 30 seconds of searching I found someone else who publicly posted thoughts and solutions on problems up to 146...so I will not be breaking any new ground and releasing code that should not be seen for a long, long time...and anyway, if you really want to take my Shakespeare code in order to "solve" a problem, you haven't really gained anything, have you?

For reference, the following are all languages that exist somewhere on my "to-use" list:

OCaml
x86 assembly
COBOL
BASIC
Ada
Delphi
Pascal
TCL
Smalltalk (I actually used this in CS334...shows how much I liked it that I have yet to use it)
APL (I'm having difficulty finding a good compiler for some reason...)
C--

And those are just the "real" languages. Some really awesome esolangs I hope to use:
Piet
ZOMBIE
ChucK (not an esolang, but thinking of a way of "printing an answer" from this language, if possible, might be interesting)
Fugue (I might need to compose this with ChucK...)
GLSL (also not an esolang, but again, "printing an answer" in it is pretty crazy)
Java2k
Kanji Code

So, needless to say...there are a lot more languages out there, and a lot more PE problems, so will probably continue doing this for a while.

The real reason why I needed to write a shakespeare compiler

So, in order to validate my Shakespeare compiler, I decided to check whether I could compile all of the example programs included in the compiler I originally downloaded: I remember in that initial download, the compiler failed when compiling the two included fibonacci programs...turns out that the compiler was not wrong in failing to compile these, the programs themselves were improper Shakespeare! I certainly do not regret writing my own compiler...I have yet to test whether indeed the original compiler I downloaded does work, but I do know that mine works very well, and I may try to improve it to add some new features to the language.

So, for anyone interested in the technical reasons why the fibonacci program is not compleable, here is the example fibonacci.spl that comes with the standard Shakespeare compiler:

By Peter Nillius 2001-08-31
nillius at nada dot kth dot se

Fibonacci's numbers.

Romeo, a lover with an accumulative memory.
Juliet, a beautiful but domineering woman.
Ulysses, a spaceman.


                    Act I: A Minimalistic Play.

                    Scene I: Juliet Sets Things Straight.

[Enter Romeo and Juliet]

Juliet:
 You are nothing. Remember yourself.
 You are the difference between nothing and a pig.
 Open your heart!

[Exit Romeo]

[Enter Ulysses]

Juliet:
 You are the twice the square of the product of an stinking
 goat and a fat pig. Speak your mind!


[Exit Ulysses]

[Enter Romeo]

Romeo:
 You are me.

Juliet:
 Recall your inner most fears. You are the sum of me and thyself. 
 Are you better than nothing?

Romeo:
 If not, we shall proceed to scene IV.

Juliet:
 Open your heart! Remember me.
 
[Exit Romeo]


[Enter Ulysses]

Juliet:
 Speak thy mind! 

Ulysses:
 We must return to Scene II.


[Exeunt]

First I would like to note that all is not for nought - trying to compile this alerted me to an issue in my compiler: it now has support for multi-line titles (This has yet to be commited to git...but it will probably eventually)
 But the issues are:
 1) The declarations cannot parse correctly - neither "lover" nor "spaceman" are acceptable nouns in the included wordlists, but I added them after seeing this.
 2) The real reason why no Shakespeare compiler could correctly compile this code: There are lines saying "we shall proceed to scene IV" and "We must return to Scene II" - with those not familiar with Shakespeare syntax, these statements mean "goto scene IV" and "goto scene II" - but scenes are just lables, declared with lines like the "Scene I: Juliet Sets Things Straight." in the above program - but there are no scenes II and IV declared, so these goto statements are attempting to jump to labels that do not exist!

So, there are many, many things wrong with the examples in the default shakespeare compiler...I do not know now whether that compiler does work on the other examples, but I do know that mine does.

This ends my digression, both from the main point of this blog and from the homework I am supposed to be doing.

Another multiple of 10:: Rust for Problem 40

So, I decided to use Rust for problem 40, because it seemed like a fun and reasonable curly brace language that I had yet to use: This problem turned out to be pretty easy to code up (after doing all the work on paper to figure out a reasonable function for d_n, the nth digit of the concatenation of the natural numbers), so I very well may be replacing this at some point and getting to use Rust again. But anyway, Rust was nice after I cleaned up my hard drive so that I could actually install it, and here is my Rust code for Problem 40 - 40 Problems down, only 10 away from having solved 50 problems in ~50 languages (and thus only 10 away until my account levels up to level 2 on PE).

fn exp(b: int, e: int) -> int {
    if e == 0 {
        1
    } else {
        b * exp(b, e - 1)
    }
}

fn getDigit(x: int, n: int, k: int) -> int  {
    if n == k - 1 {
        x % 10
    } else {
        getDigit(x / 10, n, k - 1)
    }
}

/**The minimum n such that d_n indexes into a k-digit number*/
fn min_n(k: int) -> int {
    let mut i = 1;
    let mut sum = 0;
    while i < k {
      sum += i * exp(10, i -1);
      i += 1;
    }
    1 + (9 * sum)
}

fn d_n(n: int) -> int {
    let mut min = 1;
    let mut k = 1;
    while min_n(k) <= n {
        min = min_n(k);
        k += 1
    }
    k -= 1;
    let numIndex  = (n - min) / k;
    let digiIndex = (n - min) % k;
    getDigit(exp(10, k - 1) + numIndex, digiIndex, k)
}
fn main() {
    let mut prod = 1;
    let mut n = 1;
    while n <= 1000000 {
        prod *= d_n(n);
        n    *= 10;
    }
    println(fmt!("%d", prod));
}

Plans for Rust

I plan on using Rust (http://www.rust-lang.org/) for problem 40 - I have already read plenty of documentation and worked out the necessary algorithms on paper. However, after spending about 20 minutes trying to install rust, it overfilled my hard drive, causing my computer to crash and on reboot to be unable to go past the console. So, I will need to try to find the room on my computer (or some other computer) before actually getting a solution running.

Problem 39 done; Erlang used (on 24)

Project Euler Problem #39 asks for the perimeter p <= 1000 which maximiaxes the number of right triangles with integer side lengths which have that perimeter. The best solution I could think of for this problem involved using a table / dictionary data structure, so I decided to use a language that has such a data structure built-in: Python. Now, this is the 3rd problem I have solved in Python (actually more if you were to count the problems I wrote code in Python in to check my other solution...) So I had to replace my most recent use of Python, which was on problem 24. For problem 24, I once used J because it made the problem absolutely trivial, then I used Python because I used J somewhere else and needed a quick replacement. This time around I used Erlang, and essentially just transcribed my answer from Python to Erlang - this was non-trivial as Erlang is structured differently (it is functional, and all), but nonetheless it was not too difficult.

Solution to Problem 24 in Erlang:

-module(e24).
-module(e24).
-on_load(e24/0).

fac(0) -> 1;
fac(N) -> N * fac(N - 1).


list_ref(0, [Head|_]) -> Head;
list_ref(X, [_|Tail]) -> list_ref(X - 1, Tail).

nthLP(N, P, Rem) ->
    if
        length(Rem) == 1 ->
            P ++ Rem;
        true ->
            K    = fac(9 - length(P)),
            Elem = list_ref(trunc(N / K), Rem),
            
            nthLP(N rem  K, P ++ [Elem], Rem -- [Elem])
    end.
e24() -> io:format("~B~B~B~B~B~B~B~B~B~B~n", 
    nthLP(999999, [], [0,1,2,3,4,5,6,7,8,9])).

Solution to Problem 39 in Python:

import math

sols = {}
for a in range(2,500):
    for b in range(a, 500):
        c2 = a ** 2 + b ** 2
        c  = int(math.sqrt(c2))
        if c2 == c * c:
            p = a + b + c
            if p <= 1000:
                if p in sols.keys():
                    sols[p] += 1
                else:
                    sols[p]  = 1

ans = 0
maxsols = 0
for p in sols.keys():
    if maxsols < sols[p]:
        ans = p
        maxsols = sols[p]
print ans

Progress

Again, this table was no longer on the front page, and as it allows to see everything I have done at a glance, here it is again:
Here is a table which maps out which languages I used on which problems, complete with links to my code for each problem. The statement of the Nth problem can be accessed at projecteuler.net/problem=N . A * indicates a solution that has been replaced by a solution in another language or an analytic solution.

BrainFuck	1
Haskell	2*, 37
J	3*, 24*, 35
Ruby	4*, 30
Whenever	2, 5*
Ook!	6
Racket	7*, 26
K	8*
Javascript	9*, 31
sML	10*, 42
PHP	11
Go	12*, 32
cLisp	13
C/C++	14*

Fortran95	3, 15*
Python	16*, 24*, 39
ELM	17
Scala	18
Perl	19
Java	20
FALSE	4
Squirrel	21
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
Analytic	5,8,15
Analytic	25, 28

Problem 38 - Lua

I haven't used a new, normal language in a while, but I was looking through lists of popular languages and realized that I had yet to write any code in Lua (in my life, not only for this challenge) - so, I decided to rectify that (runs in .1s):

function oom (x)
    if x < 10 then return 0
    else return 1 + oom (x / 10) 
    end
end

function getDigits(x)
    a = {}
    cap = oom(x) + 1  
    for n = 1, cap do
        a[n] = x % 10
        x = math.floor (x / 10)
    end
    return a
end

function isPandigital (x)
    digits = getDigits(x)
    table.sort(digits)
    for i = 1, #digits do
        if digits[i] ~= i then return false end
    end
    return true
end

--returns the largest pandigital number
--formed by concatenating x * (1,2,..n)
--for some n - if no such num exists,
--returns 0
function pandigVal (x)
    i = 1
    pan = 0
    while oom(pan) < 8 do
        num = i * x
        pan = pan * (10 ^ (oom(num) + 1)) + num
        i = i + 1
    end
    if not isPandigital(pan) then return 0
    else return pan
    end
end

max = 0
j = 1
while j < 10000 do
    max = math.max(max, pandigVal(j))
    j = j + 1
end
print(max)

Shakespeare Compiler update

I fixed some issues with the Shakespeare compiler I wrote earlier in order to use the Shakespeare programming language, the two fixes are that:

-Declarations that span multiple lines will be parsed correctly and not cause errors
and
-Variable names must be Shakespearean (that is, must be included in character.wordlist), so while "Romeo, a young man." is a legal declaration, "Batman, a young man" is no longer legal.

The updated version can still be found on GitHub at https://github.com/drsam94/Spl/

Problem 37 - using Haskell for real

I used Haskell once before, on Problem #2 (and that was my first ever use of Haskell), but after replacing problem 2 with Whenever, I have had Haskell as an available language for quite a while. Problem 37, like so many other problems, requires a prime sieve - I considered using sML at first because I just recovered it and I had already written a sieve, but then I decided that reusing a previously written sieve just did not feel right by the standards of this challenge. So, I used Haskell, which I had wanted to learn more thoroughly anyway, and which has similar enough syntax to ML that I could base my Haskell sieve on the ML one.
Here is my code (re: the squareRoot function: I know Haskell has a sqrt function, but I had a type error I didn't quit understand when trying to use (floor (sqrt n))...and then I have written so many Netwon's method sqrt functions in the last couple weeks that I felt it would be easier to write another than to solve the issue)

squareRootHelper n xn = let xn1 = div (xn + (div n xn)) 2 
                        in if or [xn == xn1, xn == xn1 +1] 
                             then min xn xn1 
                             else squareRootHelper n xn1
squareRoot x = squareRootHelper x (div x 2)

--isPrime method for making a list of primes
isPrime x lst = and(map (\n -> if n == 0 then False else True) (map (\n -> mod x n) lst))
--isPrime method for checking whether a number is prime after you already have a full list
primeCheck x lst = elem x lst

primes n  = if n <= 10 then [2,3,5,7] else 
                        let root = squareRoot n in
                        let lst = primes(root) 
                        in lst ++ (filter (\x -> isPrime x lst) (take (n - root) [root..])) 

--yes I probably should have implemented isTruncLeft/Right with currying and such...oh well
tright 0 = []
tright x = x : tright(div x 10)
isTruncRight p plst = and (map (\x -> primeCheck x plst) (tright p))

magnitude x = if x < 10 then 1
                        else 10 * (magnitude(div x 10))
tleft 0 = []
tleft x = x : tleft(mod x (magnitude x))
isTruncLeft p plst = and (map (\x -> primeCheck x plst) (tleft p))

main = let lst = primes 800000 in
       putStrLn( show (foldr (+) 0 (filter (\x -> and [isTruncRight x lst, isTruncLeft x lst]) (filter (\x -> x > 10) lst))))

LOLCODE - Problem 10 Redo

Most programming languages have some sort of an inspiration. FORTRAN was inspired by a want to TRANslate FORmulas, LISP was designed for LISt Processing, Whitespace was inspired by having too much to drink one night, BrainFuck was inspired by a wish to make a minimal Turing-complete language...and also to make a very obfuscated language. But yesterday, I programmed in a language inspired by these:

LOLCODE is a wonderful language, where programs are written in a language that would be very familiar to one of these cats, which of course should always be the target audience for a program. Anyhow, I decided to resolve Problem 10 in LOLCODE - my solution runs in about 15 minutes, which is unfortunately long, but I am pretty sure that this is mostly due to aspects of the language not being implemented very efficiently, because similar prime sieves generally run more quickly in other languages. The most unfortunate aspect of that 15 minutes wait is that when I ran it for the first time, I discovered that the answer was greater than 2³¹, which is the greatest value that can be stored in a NUMBR in lolcode. To remedy this, I store the answer as two base 10,000,000 digits, which then when concatenated form the correct answer (notably this would require some fanciness to accommodate for leading zeroes in the one's place...but luckily there were no leading 0's in this case.) Now, without further ado, my LOLCODE solution (which has now opened up ML for later use)

CAN HAS STDIO?
HAI 1.3

I HAS A TOTAL ITZ 2
I HAS A TOTALM ITZ 0
I HAS A P ITZ 3
I HAS A N
IM IN YR NUMS
    N R 2
    BTW NEWTON'S METHOD FOR SQRT
    I HAS A XN
    XN R QUOSHUNT OF P AN 2
    I HAS A XN1
    IM IN YR LOOP
        XN1 R QUOSHUNT OF SUM OF XN AN QUOSHUNT OF P AN XN AN 2
        EITHER OF BOTH SAEM XN AN XN1 AN BOTH SAEM XN AN SUM OF XN1 AN 1
        O RLY?
            YA RLY
                GTFO
            NO WAI
                XN R XN1
        OIC
    IM OUTTA YR LOOP

    I HAS A CAP ITZ SMALLR OF XN AN XN1
    IM IN YR TEST
        BOTH SAEM 0 AN MOD OF P AN N
        O RLY?
            YA RLY
                GTFO
        OIC
        DIFFRINT N AN SMALLR OF N AN CAP
        O RLY?
            YA RLY
                BTW ANSWER IS REALLY BIG SO WE REPRESENT IT
                BTW IN BASE 1000000
                TOTAL R SUM OF TOTAL AN P
                BOTH SAEM TOTAL AN BIGGR OF TOTAL AN 10000000
                O RLY?
                    YA RLY
                        TOTAL R DIFF OF TOTAL AN 10000000
                        TOTALM R SUM OF TOTALM AN 1
                OIC
                GTFO
        OIC
        N R SUM OF N AN 1

    IM OUTTA YR TEST
    BOTH SAEM P AN 1999999
    O RLY?
        YA RLY
            GTFO
        NO WAI
            P R SUM OF P AN 2
    OIC
IM OUTTA YR NUMS
VISIBLE ":{TOTALM}:{TOTAL}"
KTHXBYE

Problem 36 - Done in Whitespace

As my last post described, Whitespace is a pretty reasonable language, who needs characters other than space, tab, and newline, anyway? Not me certainly! I below is my solution to Problem 36 in Whitespace...as well as a link that shows how I actually wrote this: essentially I described every action in pseudo code so I knew exactly what each section of whitespace was doing...if it wasn't for all those copious comments, there would be no way that I would have every finished. Also, it is worth noting that I configured vim to let me see $ for newline, ^I for indent, and ~ for space...were it not for that help in visualization, things would have been just a bit harder.
https://dl.dropboxusercontent.com/u/34972177/PELC/e36.ws

Starting to work with Whitespace

I have decided to tackle problem 36 with the Whitespace Programming Language. For the uninitiated, it is a programming language where the only legal characters are space, tab, and newline. So,it is just a little hard to work with. I have started doing work on problem 36, but I have a while to go...the problem involves finding palindromes, so I am pretty sure I will want an order of magnitude method (so that it is possible to easily compute "first digit equals last digit", etc - no strings in Whitespace). I have that done at least, below is the code for the [base 10] order of magnitude method: I will need a base 2 one eventually, but thats a pretty easy change...well, not entirely trivial because variables aren't exactly a walk in the park, but not too bad either. The code also includes it running on a test case of 64. I don't think this post will preserve whitespace, so https://dl.dropboxusercontent.com/u/34972177/PELC/e36Real.ws

Problem 35 & a redo of 24: A new use of J and a replacement

My last use of J was for problem 24, where the solution in J was trivial: the problem asked for the 1000000th Lexicographic permutation of the digits 0-9, and that is just a primitive feature of the language...

999999 A.i.10

done, solved in J. While this is certainly a big "bang for my buck" use of J, I felt as though I ought to use it for something fancier...mostly just because I wanted a chance to actually use J again. So, I decided to take on problem 35 - problem 35 asks for the count of circular primes below 1000000 (circular primes being numbers all of whose rotations are prime) This seemed perfect for J, as rotations of lists are also primitives (the nth rotation of list m is just n |. m). So, armed with this and a nice way of converting lists to integers and integers to lists (list to integer is 10#. ; integer to list is 10&#.^:_1), and the very nice primitive isprime function (1 p: x returns 1 if x is prime, 0 otherwise), I wrote a nice little solution: sadly not a one liner as I couldn't figure out how to make f an implicit function, but a 2 liner isn't too bad (and it runs in about 3s; I had it running in about 90 before I realized I was iterating over all integers less than 1 million when I ought to just iterate over primes)

f =: 3 : '*./ 1 p: 10#.(1 (|.&((10&#.^:_1)y))\ i.#((10&#.^:_1)y))'
+/ f"0 p:i.(p:^:_1) 1e6

Now, I have a solution to problem 35 in J, and I needed to in turn write a non-J solution to 24. I considered learning assembly for this one...but assembly language looks hard, so I decided to skip it for now and just write a nice, quick, easy solution in a familiar language that can always be swapped out later: I solved problem 24 in python.

def fac(x):
    return 1 if x < 2 else x * fac(x-1)

#p is the list of predetermined digits (in order)
#rem is the list of digits left
def NthLP(N, p, rem):
    if len(rem) == 1:
        return p + rem
    numDigits = len(p)
    k = fac(9 - numDigits)
    timesDivided = int(N / k)
    p.append(rem[timesDivided])
    rem.remove(p[-1])
    return NthLP09(N % k, p, rem)

digits = NthLP09(int(999999), [], [i for i in range(0,10)])
s = ""
for d in digits:
    s += str(d)
print s