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.

#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)))

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;
    }
}

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.

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.

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

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");
    

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];
}

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