Problem 95 - Ruby

After solving problem 56 in Linotte, I freed up Ruby, a language plenty of people have good things to say about but which I have only used in my life for solving the Project Euler problems for this challenge I have used it for. Problem 95 was a pretty fun problem, involving a lot of kind of neat techniques for making sure you find all "amicable chains" and trying to repeat as little computation as possible. Ruby was a pretty solid language for solving this problem, though my solution runs in a not-terribly fast time. I am deciding to be ok with this because I don't think Ruby is really the fastest of languages, and my run time is still within reasonable bounds. I may come back later and fix things up a bit, but for now the below solution works without being too flashy and runs in about 4min on my machine.

def divisorsum(x)
    ret = 1
    (2..x).each {|i|
        if (i * i > x)
            break
        end
        if (x % i == 0)
            ret += i + (x / i)
        end
    }
    return ret
end

amChainLength = Array.new(size = 1000001, obj = 0)
maxCLength = 0
ans = 0
(4..1000000).each {|i|
    chain = [i]
    nextElem = i
    while (nextElem < 1000000 and amChainLength[nextElem] == 0)
        nextElem = divisorsum(nextElem)
        if (chain.include? nextElem)
            atIndex = chain.index(nextElem)
            (0..(atIndex - 1)).each{ |ind|
                amChainLength[chain[ind]] = 1
            }
            subl = chain.length - atIndex
            minElem = nextElem
            (atIndex..(chain.length - 1)).each{ |ind|
                amChainLength[chain[ind]] = 1
                minElem = [minElem, chain[ind]].min
            }
            if (subl > maxCLength)
                maxCLength = subl
                ans = minElem
            end
        elsif (nextElem > 1000000)
            chain.each {|elem| amChainLength[elem] = 1}
        end
      
        chain <<= nextElem
    end
    # If we hit something that made us end prematurely:
    if (amChainLength[i] == 0)
        chain.each {|elem| amChainLength[elem] = 1}
    end
}
printf("%d\n", ans)

Problem 56 - J'utilisais Linotte pour cette probleme

I have used a number of different programming languages by now. All sorts of different paradigms, different models of computation, different weird twists. However, in one feature, all languages that I have used have fallen into one of two groups: purely symbolic languages and English-based languages. None of the languages that I have used have had syntax based on another language. Despite the existence of plenty of non-English languages in this world, not too many non-English programming languages are very popular. However, today I came across some. I decided to try my hand at Linotte, as it was in French, a language that I took for 5 years (that is 3 years of middle school plus two of high school, so not as impressive as it may seem), but more important than that, Linotte, unlike many of the other non-English languages, was in a language using the Latin alphabet, and didn't stop development over a decade ago.

Using Linotte was surprisingly easy, it has a very C-like syntax, other than using a lot of French words. This was a pretty fun language to use, and I may try to use other similar languages in the future. The only real difficulty I had with Linotte is commented below - its division operator seemed to not work :( .

I wrote and ran my Linotte code in an IDE that came with the language (which was useful mostly because of code examples to copy accents from), so I don't have precise timing information, but the below code runs in a pretty short amount of time on my machine.

/** Je parle le français juste un peu*/
 
globale
i est un nombre
j est un nombre
p est un nombre
t est un nombre
somme est un nombre
résponse est un nombre valant 0
E56:

début
    ~ précision 0
    pour i de 1 à 99, lis
        pour j de 1 à 99, lis
            p vaut i puiss j
            somme vaut 0
            tant que p > 0, lis
                t vaut p mod 10
                somme vaut somme + t
                /* division seems impossible */
                p vaut entier (p * 0.1)
            ferme
            si somme > résponse, lis
                résponse vaut somme
            ferme
        ferme
    ferme
    Affiche résponse

Progress

Below is the table of my progress on this Language Challenge. The numbers below link to my code for the solution, statements of the problems can be found on projecteuler.net. A * indicates a language that was used at some point but has yet to be reused to solve anything, and P&P denotes the problems that have been solved with pencil and paper, no coding necessary. The rightmost number is the problem I am actually using a language for - the numbers to the left are problems I solved previously in the language but then used other languages to free the language up again. This table is starting to get quite large, and hard to fit in a post. The below table is actually mixing a small bit of information - to fit everything, I shortened the Python section. I also solved 16,24, and 39 in Python. I am looking into ways to express this information better so that I don't have to hide any more information from the table.

BrainFuck	1*
Ook!	6*
Whenever	5,2
Cat	3
FALSE	4
GLSL	7
ArnoldC	9
LOLCODE	10
Io	11
Shakespeare	12
Smalltalk	13
Clojure	14
BASIC	16
INTERCAL	17
WIND	18
F#	19
E	20
COBOL	21
SwiftScript	22
Ceylon	23
Erlang	24
E#	26
Befunge	27
Boo	29
K	8,30
ALGOL68	31
Go	12,32
Bash	33
Batch	34
ChucK	35
Whitespace	36
Haskell	2,37

Lua	38
Gosu	39
Rust	40
Ada	41
sML	10,42
Coffeescript	43
Scala	18,44
Rexx	45
Julia	46
x86-64	47
ELM	17,48
OCaml	49
Postscript	7,50
Cobra	51
APL	52
EEL	53
Chapel	54
Elixir	55
Linotte	56
Racket	7,26,57
WARM	58
C#	26,59
Javascript	9,31,60
Pascal	61
cLisp	13,62
Rebol	63
Tcl	64
Dart	63,65
Python	65,66
Prolog	18,67
Fantom	68
Perl	19,70

Processing	71
J	3,24,35,69,72
Groovy	73
Genie	74
Vala	75
Forth	9,76
Hack	77
R	45,78
CIL	79
Frink	16,80
Dogescript	81
Fortran95	3,15,82
Zimbu	83
Red	84
Idris	85
Squirrel	21,52,55,86
D	22,87
C	48,50,88
PASM	89
JavaBC	90
Kotlin	26,91
X10	92
PHP	11,93
Yeti	94
Ruby	4,40,56,95
Java	20,79,91,96
Pike	97
C++	14,53,94,98
Mathematica	99
P&P	1,5,6,8
P&P	15,25,28,69

Problem 94 - C++

I had a solution to problem 94 written up in EEL pretty quickly before running into 32-bit integer limitations. Therefore, it was not too hard to then port my solution to C++, especially seeing as I am extremely familiar with the language. Problem 94 was a very different type of problem from the last many. Problems 89-93 seemed to all pretty much be problems of knowing how to enumerate a space. Problem 94 was almost entirely a "do some math to dramatically simplify the problem, then brute force it" approach. The below code probably makes absolutely no sense at first glance, but accompanied by the small page of math that motivated it, this was a nice little problem. Looking at the shortness and simplicity of the below code makes me think I may be resolving this to free up C++ once again in the near future.

Code runs in about 3s on my machine.

#include<stdio.h>
#include<cmath>

long contribution(long x) {
    long c = 0;
    // x as smaller side:
    long temp = 3 * x * x - (2 * x) - 1;
    long root = (long)sqrt((double)temp);
    if (root * root == temp) {
        c += 3 * x + 1;
    }
    // x as larger side:
    temp = 3 * x * x + (2 * x) - 1;
    root = (long)sqrt((double)temp);
    if (root * root == temp) {
        c += 3 * x - 1;
    }
    return c;
}
int main(int argc, char ** argv) {
    long ans = 0;
    //repeated side must be odd
    for (long i = 3; i * 3 < 1000000000; i+=2) {
        ans += contribution(i);
    }
    printf("%ld\n", ans);
    return 0;
}

Problem 53 - EEL

So, the next problem I have to solve is problem 94. 94 didn't seem like it would be too hard, so I put my hand into the bag of languages that is a list of languages on Wikipedia, and pulled out EEL as a language to use. EEL (Extensible Embeddable Language) wasn't too hard to pick up how to use, having a very C-like syntax, though it has next to no documentation, which made things a bit hard. And indeed, the lack of documentation caused me to run into an issue. Problem 94 involves some arithmetic that occasionally goes outside the bounds of 32-bit integer arithmetic (indeed, it involves the squares of rather large 32-bit integers, which could stretch to be around 64-bits). However, EEL only has 32-bit integers, so my attempt at using it to solve problem 94 was cut short.

I may have been able to still do 94 in EEL though, for the same reason I was able to do the problem I ended up using it for - I seem to have used C++ to solve problem 53  a while ago. However, I am not entirely sure why I hadn't redone the problem more recently, as problem 53 was rather simple to solve. The below code is pretty much a translation of my previous C++ code, which was not too hard to do after having just played around in EEL trying to get problem 94 working. The most notable things about the code below are that it follows EEL coding style, giving the curly-braces-get-their-own-line syntax I don't use very often, and one very important part of the below program: The * 1.0. This coerces to a real number, because EEL only supports 32-bit integers, and only supports 64-bit floating point numbers, because why not?

Below code runs in about 8ms (EEL seems to be a fairly fast language, even though it runs on its own VM).

export function main<args>
{
    function fac(n)
    {
        if (n < 2)
        {
            return 1;
        }
        else
        {
            return n * fac(n - 1);
        }
    }

    function isncrbig(n, r)
    {
        local denom = fac(r);
        //very important 1.0 converts to a real;
        //EEL only has 32 bit ints and only has 
        //64 bit reals.
        local rest = n * 1.0;
        local i = n - 1;
        while (i > (n - r))
        {
            rest = rest * i;
            if (rest / denom > 1000000)
            {
                return true;
            }
            i = i - 1;
        }
        return false;
    }

    local min_r = 10;
    local ans = 0;
    local n = 23;
    while (n <= 100)
    {
        while (isncrbig(n, min_r - 1))
        {
            min_r = min_r - 1;
        }
        ans = ans + n - (2 * min_r) + 1;
        n = n + 1;
    }
    print(ans);
    print("\n");
    return 0;
}

Problem 93 - PHP

After freeing up PHP with Io, the natural next step was to use PHP to solve problem 93. Now, I am not a huge fan of PHP, but this solution was not too hard to type up. My issues with this problem ended up being hard to fix, but very interesting mistakes. The first big mistake was not noticing that in the statement of the problem, divisions were supposed to be floating point divisions, not integer divisions. (I assumed because we had integer inputs and were only considering integer outputs that the integers would be integer divisions, but assuming that division is integer division is almost always wrong in a math context). My next issue ended up being a very weird issue that basically boils down to "don't assume a language feature exists." In many languages, and most recently in Io, if x is a floating point number, then x % 1 (where % is the modulus operator), returns the floating point portion of a number. I used this operator to test for a whether a number was probably an integer, being off only because of floating point error. So, to check for whether a number was an "integer", I had the line of code if ($n % 1 == 0), and I was surprised when this did not fix my issues, and started trying to hunt down other issues. However, it turns out that, in PHP, $n % 1 returns 0 even if $n is floating point. Therefore, this test that I had placed my trust in was doing absolutely nothing. Replacing the test with one that actually tested what I want then gave me the correct answer, ending a long struggle to answer this problem.

Answer runs in about 12s on my machine (thank god I didn't try to stick with Io.)

<?php
function fac($x) {
    return $x < 2 ? 1 : $x * fac($x - 1);
}

#Nth Lexicographic permutation fcn,
#taken from my solutions to many other
#problems
function NthLP($n, $p, $rem) {
    if (count($rem) == 1) {
        $p[] = $rem[0];
        return $p;
    }
    $k = fac(count($rem) - 1);
    $timesDivided = (int) ($n / $k);
    $p[] = $rem[$timesDivided];
    array_splice($rem,$timesDivided, 1);
    return NthLP($n % $k, $p, $rem);
}

function digits($num) {
    $ret = array();
    while ($num > 0) {
        $ret[] = ($num % 10);
        $num = (int) ($num / 10);
    }
    return array_reverse($ret);
}

#abstraction for calling operations by number
function op($x, $y, $op) {
    if (is_infinite($x) || is_infinite($y)) { 
        return INF; 
    }
    switch($op) {
    case 0:
        return $x * $y;
    case 1:
        return $x - $y;
    case 2:
        return $y == 0 ? INF : ($x / $y);
    case 3:
        return $x + $y;
    default:
        return 3025;
    }
}

#index encodes the permutation of digits,
#parenthization, and operands,
#as a sort of multi-base number
function getNum($dlist, $index) {
    $permut = $index % 24;
    $index  = (int) ($index / 24);
    $parenth= $index % 5;
    $index  = (int) ($index / 5);
    $op1    = $index % 4;
    $index  = (int) ($index / 4);
    $op2    = $index % 4;
    $index  = (int) ($index / 4);
    $op3    = $index % 4;
    $d      = NthLP($permut, array(), $dlist);
    switch($parenth) {
    case 0:
        return op( op( $d[0], $d[1], $op1), op($d[2], $d[3], $op3), $op2);
    case 1:
        return op( $d[0], op($d[1], op($d[2], $d[3], $op3), $op2), $op1);
    case 2:
        return op( $d[0], op( op($d[1], $d[2], $op2), $d[3], $op3), $op1);
    case 3:
        return op( op( $d[0], op( $d[1], $d[2], $op2), $op1), $d[3], $op3);
    case 4:
        return op( op( op( $d[0], $d[1], $op1), $d[2], $op2), $d[3], $op3);
    default:
        return 3025;
    }
}

#So apparently PHP passes arrays by value
#scary
function setBit($lst, $n) {
    #test for integer-ness
    if (($n - (int)$n) < 0.01) {
        $n = (int) $n;
        $lst[(int) ($n / 32)] |= 1 << ($n % 32);
    }
    return $lst;
}

function countConsec($lst) {
    $count = 0;
    for ($k = 1; $k < 3024; $k++) {
        if ((($lst[(int) ($k / 32)] >> ($k % 32)) & 1) == 1) {
            $count += 1;
        } else {
            return $count;
        }
    }
    return $count;
}

function numConsec($x) {
    $digs = digits($x);
    if (!((count($digs) == 4) && ($digs[0] < $digs[1]) &&
        ($digs[1] < $digs[2]) && ($digs[2] < $digs[3]))) {
            return 0;
    }
    $results = array_fill(0, (int) (3024 / 32), 0);
    for ($i = 0; $i < (5 * 4 * 4 * 4 * 24); $i++) {
        $next = getNum($digs, $i);
        if ($next > 0 && $next < 3024) {
           $results = setBit($results, $next);
        }
    }
    return countConsec($results);
}

$soln = 1234;
$maxConsec = 0;
for($i = 1234; $i <= 6789; $i++) {
    $num = numConsec($i);
    if ($num > $maxConsec) {
        $maxConsec = $num;
        $soln = $i;
    }
}
var_dump($soln);
?>

Problem 11 - Io

After writing up a somewhat full solution to Problem 93 in Io, I found out that that solution was far, far too slow to run. Thus, I looked for a much, much simpler problem that I could solve in Io in order to free up another language for 93. Problem 11 was a good choice, as the problem is quite simple, other than requiring working with a 2-dimensional array, which is very doable in Io. So, I replaced my old PHP solution from a long time ago with an Io solution. This was mostly an easy matter of translating, nothing special. Solution runs in about 0.1s on my machine (for what it's worth, my PHP solution runs in about 1/5 of the time, and of course that is worth very little on these time scales).

matrix := list(list( 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8),
    list(49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0),
    list(81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65),
    list(52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,36,91),
    list(22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80),
    list(24,47,32,60,99, 3,45, 2,44,75,33,53,78,36,84,20,35,17,12,50),
    list(32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70),
    list(67,26,20,68, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21),
    list(24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72),
    list(21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95),
    list(78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92),
    list(16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57),
    list(86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58),
    list(19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40),
    list( 4,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66),
    list(88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69),
    list( 4,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36),
    list(20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16),
    list(20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54),
    list( 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48));

max := method(x, y, if(x > y, x, y))

maxProd := 0;
bound := matrix size;
for (i, 0, bound - 1,
    for (j, 0, bound - 1,
    (i + 3 < bound) ifTrue (maxProd := max((matrix at(i) at(j)) * 
    (matrix at(i+1) at(j)) * (matrix at(i+2) at (j)) * (matrix at(i+3) at(j)), maxProd));
    (j + 3 < bound) ifTrue (maxProd := max((matrix at(i) at(j)) * 
    (matrix at(i) at(j+1)) * (matrix at(i) at (j+2)) * (matrix at(i) at(j+3)), maxProd));
    (i + 3 < bound and j + 3 < bound) ifTrue (maxProd := max((matrix at(i) at(j)) * 
    (matrix at(i+1) at(j+1)) * (matrix at(i+2) at (j+2)) * (matrix at(i+3) at(j+3)), maxProd));
    (i + 3 < bound and j > 2) ifTrue (maxProd := max((matrix at(i) at(j)) * 
    (matrix at(i+1) at(j-1)) * (matrix at(i+2) at (j-2)) * (matrix at(i+3) at(j-3)), maxProd));                   
    )
)

maxProd print;

Progress on Problem 93-ish, slow languages are fun.

I spent much of this evening coding up a solution to problem 93 in the Io programming languages. After I went through fixing all of the various errors that I had because of not getting the at-times confusing or just odd syntax right, I tried running my program, and it ran, and ran, and ran giving no answer. Turns out, it takes about 15 seconds for it to test just 10 of the couple thousand cases it has to check. After observing this, I decided to run a bit of a test to see just how slow the language is. As I had done all of my work with sieve timing before, that seemed like a good example of something I could code up quickly to test. A prime sieve to find all primes less than 100000 takes about 6.5 seconds to run in Io. That can be compared to about 10ms in C, and primes less than a million took too long for me to wait for in Io (more than a minute), and takes about .1s in C. So, this test showed me that Io could be expected to be at least 600 times slower than C code - and that's assuming no operations are particularly slow, such as array accesses, etc. So, based on this result, I think I will have to retire Io as the language for 93, and instead use it to solve an earlier problem, and use another language on 93. Though I must say, a 600x + slowdown compared to C is kind of impressive, and a sign that it will be hard to solve anything in close to a minute in this language.

Problem 92 - X10

So, working on another problem. I found X10 through yet another google search, this time specifically for languages that run on the JVM, because why not. X10 is an object oriented languages developed by IBM that, yes, runs on the JVM. I ended up accidentally installing an IDE for x10 from the website (x10dt apparently means "X10 developer tools" which means "an IDE for X10"), so I used that instead of just using a command line compiler, and the IDEs copious red lines resultsd in all my errors being caught while I was writing, meaning that my pace of writing was slowed down. Overall the language wasn't too hard to pick up, having very Java-like syntax, though actually its Javaness led to my first bit of confusion...not knowing to use the new operator...but other than silly things like that, I had working code relatively quickly.

After I had working code, there were still issues. The code ran slowly, and it took me about 5 minutes to figure out how to stop execution of code in the IDE (pressing "run" again only made it run the program twice concurrently!) And in addition pressing run does not auto-save, which took a while to notice. The last big issue was an interesting one...I was accidentally allocating the "prev" array each time through the loop, which turns out to have been incredibly costly. After I moved to allocating it once instead of ten million times, my code's execution time went from about 5 minutes to do 10% of the search space to almost instant (I say almost instant because, again, IDE, so I don't have real timing data). Anyway, my X10 code is below:

(Small indents because I wrote it in the IDE which seems to have unfortunately used tabs instead of spaces).

public class e92 {

 public static def getBit(r:Rail[Long], x:Long) {
  val index    = x / 64;
  val subIndex = x % 64;
  return ((r(index) >> subIndex) & 1) == 1;
 }
 
 public static def setBit(r:Rail[Long], x:Long) {
  val index    = x / 64;
  val subIndex = x % 64;
  r(index) = r(index) | (1L << subIndex);
 }
 
 public static def nextTerm(x: Long) {
  var c:Long = x;
  var s:Long = 0;
  while (c > 0) {
   s += (c % 10) * (c % 10);
   c /= 10;
  }
  return s;
 }
    public static def main(Rail[String]) {
     // Pair of arrays for memoizing to store
     // if we have info, and if it goes to 89
        var isSet:Rail[Long] = new Rail[Long](10000000 / 64);
        isSet.fill(0);
        var is89:Rail[Long]  = new Rail[Long](10000000 / 64);
        is89.fill(0);
        setBit(isSet, 1);
        setBit(isSet, 89);
        setBit(is89, 89);
        var ans:Long = 1;
        var prev:Rail[Long] = new Rail[Long](100000);
        for (i in 1..9999999) {
         var pLength:Long = 0;
         var c:Long = i;
         while (! getBit(isSet, c)) {
          prev(pLength) = c;
          pLength      += 1;
          c = nextTerm(c);
         }
         var was89:Boolean = getBit(is89, c);
         for (j in 0..(pLength - 1)) {
          setBit(isSet, prev(j));
          if (was89) {
           setBit(is89, prev(j));
           ans += 1;
          }
         }
        }
        Console.OUT.println(ans);
    }
}

Problem 91 - Java

After freeing up Java, I decided to use it. Problem 91 was not particularly hard (most of the recent problems have mostly been a matter o knowing how to enumerate the answer space well, and how to check for the answer easily arithmetically), so I actually did not intend to use a language as useful as Java on it. However, Java was available, and the first two languages I tried I ran into difficulties with (I may use them eventually, but Factor documentation was not very useful, and Dylan is having difficulties building on my machine).

Also, solving 91 in Java results in the nice phenomenon of using Java Byecode and Java to solve consecutive problems. Anyway, the main difficulty I experienced trying to solve this problem was me accidentally expressing the condition for perpendicularity incorrectly. I accidentally took the reciprocal twice, causing me to be checking if slopes were negatives, instead of negative reciprocals. other than that and other small issues, this was not the hardest of problems.

Runs in about .15s on my machine.

public class e91 {

    public static int min (int x, int y) {
        return x < y ? x : y;
    }

    public static void main(String[] args) {

        int ans = 0;
        final int B = 50 + 1;
        for (int P1 = 1; P1 < B*B; ++P1) {
            for (int P2 = P1 + 1; P2 < B*B; ++P2) {
                int x1 = P1 / B;
                int y1 = P1 % B;
                int x2 = P2 / B;
                int y2 = P2 % B;
                int oldans = ans; 
                if(min(x1, x2) == 0 && min(y1, y2) == 0) {
                    //Right Angle at origin
                    ++ans;
                } else if ((y1 == y2) && (x1 == 0 || x2 == 0)) {
                    //undef slope, check explicitly
                    ++ans;
                } else if ((x1 == x2) && (y1 == 0 || y2 == 0)) {
                    //same
                    ++ans;
                } else {
                    //Negative reciprocals => right angle
                    int num   = y1 * (y1 - y2);
                    int denom = x1 * (x1 - x2);
                    if (denom != 0) {
                        int ratio = num / denom;
                        int rem   = num % denom;
                        ans += (ratio == -1 && rem == 0) ? 1 : 0;
                    }
                    if (ans == oldans) {
                        num   = y2 * (y2 - y1);
                        denom = x2 * (x2 - x1);
                        if (denom != 0) {
                            int ratio = num / denom;
                            int rem   = num % denom;
                            ans += (ratio == -1 && rem == 0) ? 1 : 0;
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}