Project Euler is back up

Project Euler has been down for a while due to a security breach. However, it is now back up, so soon enough my account will again have data about my progress that is accurate, I will be able to know for sure which problems I did not solve on my prior account, and I will be able to post on the Project Euler forums.

My lack of any new progress has been a result of not only me reaching a difficult goal and deciding to take a little bit of a break, but also me traveling all over the place visiting family prior to the beginning of the upcoming academic year. I will probably solve at least one more problem before classes start, however.

100 Problems in a Year - Success

A year ago today, on August 8th, 2013, I began a hackathon where I decided to attempt something that seemed like a fun idea that had come over lunchtime conversations. Project Euler is fun, but (the early problems, especially if you have done them once before) fairly easy. Solving problems in esoteric languages would certainly make it more of a challenge...so, instead of picking one or two esoteric languages and sticking with them, why not just try to use as many languages as possible, forcing the use of more and more obscure languages?

During that hackathon, I reached my goal very exactly - just minutes before 24 hours had passed, I solved my 20th problem in my 20th program language.

After that hackathon, I decided to continue - sure, 20 problems in 20 languages wasn't the easiest thing in the world, but I already knew half or more of the languages that I had used, how long could I go using new languages? Would I run out of languages I would be able to learn? It seems that that was not the case, as I eventually reached a lofty goal of 50 problems, and now, almost by accident plus a small push at the end, I have solved 100 problems in nearly as many languages in a year.

So, I suppose this is a good time to reflect on things. This has been a very fun project, not only because it allowed me to dive back into Project Euler, which I hadn't done much of anything with for about a year at the time I started, due to running out of problems I felt as though I could solve (though many of those very problems I have solved in this challenge, with the advantages of more education and learning the lessons of going through in order to help me). And also, though I first thought that this project would mostly just lead to me learning a bunch of nonsense esoteric languages (and don't get me wrong, I have used Befunge, Whitespace, LOLCODE, and others, so that is definitely still happening), I have used a number of languages that actually are used a lot that I knew nothing about prior to this project (Ruby, Perl, D, and more like this).

However, I think more important than learning any one language in this project - and indeed, I am wary of using that term, many of the languages I have used for this blog I would not say I have "learned", I have only experimented with them briefly - I think more importantly this project has developed a skill of being able to learn languages quickly and think of solutions to problems in language-independent manners that has allowed me to often write a solution in an entirely new language the day I learn the language, even if that language is not highly similar to other languages, and often even "learning" more than one language a day. Further, switching languages so frequently has decreased the inertia I experience when switching languages. I remember last Spring when I often had to switch between Scala code I wrote for class and C++ code I wrote for G3D, I would often make silly mistakes, using syntax for one language in another (such as array access syntax arr(i) in Scala, arr[i] in C++). Though I often switch must more frequently now than I did then, I make far fewer mistakes of that kind than I did then. And indeed, switching more often is the case, though it doesn't seem crazy when I am doing it, it seems like a lot to write down that since Monday (and today is Friday)  I have written code in C++, Python, Moonscript, E, E#, Pike, Java, Kotlin, Mathematica, and Yeti.

I would definitely encourage anyone to try a challenge such as this themselves. Whether they are already fairly seasoned as I was and want to try using 100 languages, or just maybe solving project Euler rotating through 3-10 languages, this programming challenge has been a great learning experience. In addition to of course just being fun, a great distraction from actual sources of work, and occasionally leading to interesting mathematical insights (because yeah, there is that side to Project Euler too).

So, I have solved 100 Project Euler problems in all different languages in a year. Will I be able to do another 100 next year? I doubt it because of problems increasing in difficulty and languages getting slimmer and slimmer, but that's what I said at 50, so who knows.

Problem 100 - To the Moon(Script)

So, problem 100. After the flurry of work that was getting through problems 98 and 99, the work on this one was fairly unexciting. I expressed the problem in terms of a quadratic diophantine equation, observed that such things have been studied by mathematicians enough for methods to solve them to be widely available online, so then I solved my equation and wrote some short code that iterates through solutions until finding the one desired for this problem.

The language I used was Moonscript, which I don't have much to say about, as I haven't actually written much in it, as can be seen below. However, it was very easy to set up, which was nice after I failed to build two programming languages, this one just had an online compiler.

So yeah, this was my 100th problem. A reflective post is upcoming.

Code runs in about 378ms on the interwebs.

X0 = 1
Y0 = 1
while Y0 < 1000000000000
  X1 = 3*x0 + 2*Y0 - 2
  Y1 = 4*x0 + 3*Y0 - 3
  X0 = x1
  Y0 = Y1
 
print X0

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
Moonscript	100
P&P	1,5,6,8
P&P	15,25,28,69

Problem 99 - Mathematica. One more to the big 100

Mathematica is a language that many have been telling me to use for a long time. My aversion to it has mostly been because I was not sure whether it really counts as a programming language, or is it something else entirely? Well, I decided that I might as well succumb to common belief and say that it is a language, and problem 99 gave me a problem to solve in this language that was pretty appropriate for Mathematica. Processing relatively large data sets and doing somewhat high precision floating point arithmetic with logarithms? Sounds like a good place to use Mathematica to me.

I have used Mathematica very, very little in the past (twice for a physics class), but I had few difficulties with this problem. My only real difficulties were unfamiliarity with the user interface of Mathematica, and my inability to find any relative path for the data file (note for anyone deriving information about my filesystem from the absolute path, this problem was solved on a very infrequently used Windows partition of my laptop)

Hopefully tomorrow (or, oh, look at how late it is, later today), I will be ale to reach 100 with a yet to be determined language.

I didn't feel like figuring out how to do timing in Mathematica, but the below code runs pretty quickly on my machine.

ans = 0
maximum = 0
list = ReadList["C:\\Users\\Sam\\Desktop\\Euler\\base_exp.txt", Number]
For[i = 1, i <= Length[list], i = i + 2,
 next = Log[Part[list, i] * 1.0] * Part[list, i + 1] ;
 ans = If[next > maximum, (i + 1) / 2, ans];
 maximum = Max[next, maximum] ]
Print[ans]

Problem 98 - C++

Problem 98 was quite the problem. I know for a fact I have never solved it before, as I distinctly remember not being able to properly parse what the problem meant the first time I looked at it. Though this time I certainly knew what the problem was, this problem was no slouch to solve. This problem was a rare case of Project Euler problems where there is almost no complicated math going on at all, its all just a matter of figuring out how to best program a solution. And though I will say that programming this solution was a bit frustrating at times, it was pretty fun and I had a good time doing it.

My first issue was a very odd one - I was trying to use a words.txt I had probably downloaded for an earlier Euler problem, while looking at the version online to determine the format. The formats were different, so I got some segfaults reading the output.

The next issues were from thing just taking too long in the massive cluster of loops that you can see if you look at the problem. Putting lots of early termination conditions fixed this problem.

Next, I was faced with problems that were really weird to debug and I did not know what was going wrong. Turns out, the issue was I had a loop going backwards in a string thusly:
for (size_t i = str.size() - 1; i >= 0; --i). Though size_t might be the "proper" type for indexing a string or other container, it is not the proper type for comparison against 0. size_t's are unsigned, so i >= 0 is always true, and --i causes underflow and this loop goes on for a while (I saw a while, not infinitely, as the issue was that this was in the getStrMapping loop, which has an earlier termination condition, which, when in an infinite loop, is always hit!).

After that, the problems were relatively small.

So, despite a lot of bumps in the road, this was a pretty fun problem. I ended up using a lot of C++ standard library data structures and other features, which was nice, not only because I have been writing a lot of C++ code for the Data Structures class I am TAing this upcoming fall, so I was well practiced/this was further practice, but also this problem is finally a nice C++ entry for this blog that is distinctly not just C.

Also worth noting is that my solution to this problem ended up having far more comments than my average solution. Maybe this is a result of pent-up frustration with languages that I don't even know the comment syntax in, or maybe I commented because I was just having so much fun, or maybe this problem was just so mentally stimulating that I had to comment, or maybe the length of time I spent on this problem caused me to go insane with an insanity whose symptoms include commenting your code. But anyway, here is my solution to problem 98:

Code runs in .2s on my machine (.6s if I dont compile with g++ -O3)

#include <stdio.h>
#include <vector>
#include <string>
#include <cmath>
#include <unordered_map>
#include <algorithm>
// --note: requires compilation with g++ -std=c++11
//
// Some of my other C++ solutions were basically written in C
// I think the includes above probe that that is not the case for this problem

void getSquaresOfSize(int size, std::vector<long>& squares) {
    squares.clear();
    long low = (long) ceil(sqrt(pow(10.0, size - 1.0)));
    long high= (long) ceil(sqrt(pow(10.0, size)));
    for (long i = low; i < high; ++i) {
        squares.push_back(i * i);
    } 
}

// Get mapping of string, and return whether it is valid
bool getStrMapping(const std::string& str, long square, std::unordered_map<char, int>& map) {
    map.clear();
    //std::unordered_map <int, char> invmap;
    //^this was dumb
    char invmap[10];
    // ? for a debug print test, not just to be cute
    for (size_t i = 0; i < 10; ++i) { invmap[i] = '?'; }
    // Back-to-front to agree with easy order of grabbing digits
    // int because unsigned size_t will underflow and i >= 0 will always return true!
    for (int i = int(str.size() - 1); i >= 0; --i) {
        int digit = square % 10;
        if (invmap[digit] != '?' && invmap[digit] != str[i]) {
            return false;
        }
        invmap[digit] = str[i];
        map[str[i]] = digit;
        square /= 10;
    }
    return true;
}

// A return value of 0 indicates there is no square anagram with the mapping
// any other return value is the square produced by a mapping
// this method assumes anagram-ness
long squareMatch(const std::string& str, const std::unordered_map <char, int>& map) {
    long maybeSquare = 0;
    for (size_t i = 0; i < str.size(); ++i) {
        if ( i == 0 && map.at(str[i]) == 0) {
            //Will produce a number with a leading 0!
            return 0;
        }
        maybeSquare = (maybeSquare * 10) + map.at(str[i]);
    }
    long root = (long)round(sqrt((long double)maybeSquare));
    if (root * root == maybeSquare) {
        return maybeSquare;
    } else {
        return 0;
    }
}

// Thank you stack overflow and the standard library
// http://stackoverflow.com/questions/18267407/check-whether-two-strings-are-anagrams-c
// note pass-by-value important here
bool isAnagram(std::string s1, std::string s2) {
    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    return s1 == s2;

}
long max(long x, long y) { return x > y ? x : y; }

void getAnagrams(const std::string& str, const std::vector<std::string>& strings,
        int start, std::vector<std::string>& anagrams) {
    anagrams.clear();
    for (size_t i = start; i < strings.size(); ++i) {
        if (i != 0 && isAnagram(str, strings[i])) {
            anagrams.push_back(strings[i]);
        }
    }
}

long maxAnagramForSize(int size, const std::vector<std::string>& strings) {
    std::vector<long> squares;
    if (strings.size() < 2) {
        //abort early as not to compute stupidly large squares
        return 0;
    }
    getSquaresOfSize(size, squares);
    std::unordered_map<char, int> map;
    long maxFound = 0;
    //This mass of loops doesn't look scary at all
    std::vector<std::string> anagrams;
    for (size_t i = 0; i < strings.size(); ++i) {
        getAnagrams(strings[i], strings, i+1, anagrams);
        if (anagrams.size() > 0) {
            for (size_t j = 0; j < squares.size(); ++j) {
                if (getStrMapping(strings[i], squares[j], map)) {
                    for (size_t k = 0; k < anagrams.size(); ++k) {
                        long match = squareMatch(anagrams[k], map);
                        if (match > 0) {
                            maxFound = max( max(maxFound, match), squares[j]);
                        }
                    }
                }
            }
        }
    }
    return maxFound;
}

int main (int argc, char ** argv) {
    
    std::vector<std::vector<std::string> > strings;
    // Overestimate max length
    strings.resize(20);
    for (size_t i = 0; i < strings.size(); ++i) {
        strings[i].resize(0);
    }
    char* word = NULL;
    size_t length;
    while (getdelim(&word, &length, ',', stdin) > 0) {
        const std::string& s = word;
        //pesky quotes
        const std::string realS = s.substr(1, s.size() - 3);
        strings[realS.size()].push_back(realS);
    }
    long ans = 0;
    for (size_t i = strings.size() - 1; i > 0; --i) {
        ans = maxAnagramForSize(i, strings[i]);
        if (ans > 0) {
            //Clearly an n-digit number is larger than a
            //k < n digit number
            break;
        }
    }
    printf("%ld\n", ans);
    return 0; 
}

Problem 94 - Yeti

I am moving in on the final stretch. I have a solution to problem 99 in reserve that I am waiting to post until I finish 98, so once I finish 98, there will be just one problem, number 100, left for me to solve in order to reach that big 3 digit goal. So, for problem 94, I dove again into the "fledgling language list" I found on google and found a language called Yeti. It claims to have functional syntax based on ML, but I think it has much more flexible syntax, and it runs on the JVM, which helped make the installation process nice and short (even if the executable didn't work, I could run the jar fine). This problem was a not-too-difficult transition over from C++, especially as the language has a few things that make it really good for scientific / Euler style computing (built-in sqrt function and high precision arithmetic - I am especially impressed with the high precision arithmetic, as this is built on the JVM, so it seems the developers did not take the easy way out and just use Java primitives for everything) and now I will get ready to use C++ on problem 98, which looks like it might be nontrivial, though also hopefully not too hard.

Solution runs in about 5s on my machine.

contribution x = (
    var c = 0;
    temp1 = 3 * x * x - (2 * x) - 1;
    root1 = int(sqrt(temp1));
    c := if root1 * root1 == temp1 then
        3 * x + 1 + c
    else
        c
    fi;
    temp2 = 3 * x * x + (2 * x) - 1;
    root2 = int(sqrt(temp2));
    c := if root2 * root2 == temp2 then
        3 * x - 1 + c
    else
        c
    fi;
    c;);

var ans = 0;
var i   = 3;
i * 3 < 1000000000 loop (
    ans := ans + contribution(i);
    i := i + 2;
);
println(ans);

     

Problem 96 - Java

So, Problem 96 involves solving Sudoku puzzles. I honestly had a lot more difficulty with this problem than I needed to. Among my issues were trying to be fancier than necessary. Only doing the "first step" of logical deduction is entirely sufficient before going into guess and check, and my attempts at implementing the guess and check were truly ugly prior to coming across the somewhat nice/clean recursion that I ended up with. I think a lot of my issue with this problem is just that I moved from trying to do this in Pike, where I had crazy ideas that were limited by the language's data structures, so then I tried to use those same structures in Java because, why not, Java is object oriented, while in the end simplicity won. (Basically for a long time I had a stack of boards that was hard to manage, rather than just having stack-like stuff done through recursion).

My final issue with this problem was a very stupid one. I kept trying to debug errors because my output was clearly wrong, far less than what the correct answer would have to look like. Turns out adding three digits together is very different from concatenating them together. And now that this rather frustrating problem is done, hopefully the next 3 to get to 100 won't be too bad.

Solution runs in about .5s on my machine.

import java.util.*;

//Because you can't have arrays of Generics
//Because Java is silly
class HashSetInteger extends HashSet<Integer> { }

public class e96 {

public static int[][] copyArray(int[][] arr) {
    int ret[][] = new int[arr.length][arr[0].length];
    for (int i = 0; i < arr.length; ++i) {
        for (int j = 0; j < arr.length; ++j) {
            ret[i][j] = arr[i][j];
        }
    }
    return ret;
}

public static void printBoard(int[][] board) {
    for (int i = 0; i < board.length; ++i) {
        for (int j = 0; j < board.length; ++j) {
            System.out.print(board[i][j]);
        }
        System.out.println();
    }
    System.out.println();
}

public static int solveBoard(int[][] board) {
    HashSetInteger[][] notes = new HashSetInteger[9][9];
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            notes[i][j] = new HashSetInteger();
            for (int k = 1; k <= 9; ++k) {
                notes[i][j].add(k);
            }
        }
    }

    boolean changed      = false;
    boolean allSet       = true;
    boolean secondChanges = true;
    do {
        changed = false;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == 0) {
                    for (int k = 0; k < 9; ++k) {
                        notes[i][j].remove(board[i][k]);
                        notes[i][j].remove(board[k][j]);
                        int startx = (i / 3) * 3;
                        int starty = (j / 3) * 3;
                        notes[i][j].remove(board[startx+(k%3)][starty+(k/3)]);
                    }
                    if (notes[i][j].size() == 1) {
                        for (Integer ger : notes[i][j]) {
                            board[i][j] = ger;
                        }
                        changed = true;
                    } else if (notes[i][j].size() == 0) {
                        return 0;
                    } else {
                        allSet = false;
                    }
                }
            }
        }
        secondChanges =  (!changed && !secondChanges);
    } while (changed || secondChanges);
    
    if (allSet) {
        return board[0][0]*100 + board[0][1]*10 + board[0][2];
    } else {
        int ret = 0;
        do {
        int[][] oldBoard = copyArray(board);
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == 0) {
                    if (notes[i][j].size() == 0) {
                        return 0;
                    }
                    for (Integer ger : notes[i][j]) {
                        board[i][j] = ger;
                        notes[i][j].remove(ger);
                        break;
                    }
                    i = 9;
                    j = 9;
                }
            }
        }
        ret   = solveBoard(board);
        board = oldBoard;
        } while (ret == 0);
        return ret;
    }
}

public static void main(String[] args) {
    int ans = 0;
    //we pass sudoku.txt through stdin
    //even though I guess it would be about as easy
    //to just past it to this scanner, huh?
    Scanner scan = new Scanner(System.in);
    scan.useDelimiter("");
    for (int i = 0; i < 50; ++i) {
        int[][] board = new int[9][9];
        scan.nextLine();
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                String s = scan.next();
                board[r][c] = Integer.parseInt(s);
            }
            scan.nextLine();
        }
        ans += solveBoard(board);
    }
    System.out.println(ans);
}

}

Problem 91 - Kotlin

I haven't used Kotlin in a very long time...the last time I used it was for problem 26. However, as it is basically a "Java with syntactic sugar" language, it was not too hard to use (especially as I had been writing my solution to Java before freeing it up on this problem with Kotlin). Really the main annoyance with Kotlin is that I have never managed to actually install it on my computer, so I have to use their online demo, which really is not that huge of an annoyance at all. Code runs in some relatively short amount of time that I couldn't really time because, yeah, online demo:

import java.util.Collections.*

fun min (x: Int, y: Int): Int {
  if (x < y) {
    return x;
  } else {
    return y;
  }
}

fun main(args : Array<String>) {
    var ans: Int = 0;
    var B: Int = 50 + 1;
    for (P1 in 1..((B*B) - 1)) {
        for (P2: Int in (P1+1)..((B*B - 1))) {
            var x1: Int = P1 / B;
            var y1: Int = P1 % B;
            var x2: Int = P2 / B;
            var y2: Int = P2 % B;
            var 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
                var num: Int   = y1 * (y1 - y2);
                var denom: Int = x1 * (x1 - x2);
                if (denom != 0) {
                    var ratio: Int = num / denom;
                    var rem: Int   = num % denom;
                    if ((ratio == -1) && (rem == 0)) {
                      ++ans;
                    }
                }
                num   = y2 * (y2 - y1);
                denom = x2 * (x2 - x1);
                if ((ans == oldans) && denom != 0) {
                    var ratio: Int = num / denom;
                    var rem: Int   = num % denom;
                    if ((ratio == -1) && (rem == 0)) {
                        ++ans;
                    }
                }
            }
        }
    }
    System.out.println(ans);
}

Problem 26 - E#

So, E#...It's a fairly simple language with common curly brace syntax. However, I wouldn't call it quite the greatest language in the world. Things started looking not-the-best when I checked out the svn repository only to see that it was only in its second revision. Then, the E# source didn't actually compile, and I need to change a few headers in order to get it to do so. After that came trying to learn the language. As I said, the syntax was pretty simple and easy to pick up, but the "doc" folder of the distribution consists of just 9 short examples, with some comments. And then...the slowness. I wrote up solutions to 97, 91, and 53 in E#, hoping to get something done, but the language is so slow that things that are instant in python might take an hour in this language.

When I finally chose to solve problem 26 in E#, things started looking grim, as re-implementing my previous solution took over 10 minutes to search less than half of the space. However, I then realized that you can eliminate most of the search space in the problem by counting from the top down rather than the bottom up. Even with this time saving...it has to check fewer than 1000 things for each of fewer than 20 elements...I still couldn't technically get under a minute, but I got close enough on my not blazingly fast machine that I am willing to call this problem solved. Code runs in about 1m21s on my machine.

ans = 0;
clength = 0;
for (d = 999; d > clength; --d) {
    rems = list.new(0);
    r = 1;
    i = 0;
    while (r != 0) {
        r = (r * 10) % d;
        for (j = 0; j < i; ++j) {
            if (rems.get(j) == r) {
                r = 0;
                j = i;
            }
        }
        if (r != 0) {
            
            rems.append(r);
            i += 1;
        }
    }
    if (clength < i) {
        ans = d;
        clength = i;
    }
}

stdout.println(ans);

Lots of difficulties, but here is problem 97

I am trying to get a lot of problems done - I have done 95 problems, and this Saturday, August 9th, will mark the 1-year anniversary of the hackathon when I began this blog. My goal is to try to get to 100 problems solved by then. The past couple of days, I have hit a couple of road blocks in moving towards that goal. First, I tried to solve problem 96 (Sudoku puzzles) in  language called Pike, but ran into issues with Pike seemingly not agreeing with its own language spec. I am now working on a Java solution to 96, but still have to work out details. I then decide to move beyond problem 96 and look at problem 97. I found a language called E# that seemed like a pretty solid language, but it was SLOW. slower than Io, which I complained about being slow a while ago. We are talking at least 2 orders of magnitude slower than Python slow. It was slow. So, despite writing solutions to problem 97 and a couple of others in E#, I was not able to find a problem which E# could solve in a human time-scale. So, as not to have nothing to show for the past couple of days, here is my solution to problem 97 in Pike. It's not super exciting, not even super optimized (I could go a few powers of two at a time, instead of just multiplying by 2). But, here we go. Code runs in about 10s on my machine.

int main() {
    array(int) digits = ({3, 3, 4, 8, 2, 0, 0, 0, 0, 0});

    
    for (int n = 0; n < 7830457; ++n) {
        int carry = 0;
        for (int i = 0; i < 10; ++i) {
            int prod = (digits[i] * 2) + carry;
            carry = prod / 10;
            digits[i] = prod % 10;
        }
    }
    digits[0]++;
    for (int i = 9; i >= 0; --i) {
        Stdio.stdout->printf("%d", digits[i]);
    }
    Stdio.stdout->printf("\n");
}

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