Wednesday, October 15, 2014

Implicit Function for a Teapot

I haven't been solving many Project Euler problems for a long time, because it turns out that there is a lot of schoolwork to do when you take 5 courses, all CS or MATH, all 300-level or higher.

Anyway, something cool from one of my classes, an implicit function for a teapot, written in GLSL, with possibly a couple helper functions not included here. I may port this to a ShaderToy and/or improve the function at some point, but for now, here it is, and here is a video showing off the results:
https://www.youtube.com/watch?v=DSgwaYSnfcQ
float smin(float a, float b, float blendRadius) {
    float c = saturate(0.5 + (b - a) * (0.5 / blendRadius));
    return lerp(b, a, c) - blendRadius * c * (1.0 - c);
}

float teapotDistance(vec3 X) {

    //Spout - this is the most complex part
    vec3 C = vec3(-1.6f, -3.0f, 0);

    //Radius gets thinner until the end of the spout where it grows very quickly
    //fatness of the base of the spout is not dealt with here: it is increased
    //by using a large blend radius with the body
    float r = 0.7f +-.7 * sin(max(X.x, 3.0f));
    r = (X.x > 3.0f ? r + sin(X.x - 3.0f) : r);
    float e = 3.0f;

    //rotate a cylinder constantly to make a spout
    mat3 rot = rotation(pi / 2 + 2 * sin(X.x / 5.0f), 0, 0);
    vec3 tX = rot * X;
    tX.x -= .5f;
    vec2 d = abs(vec2(length(tX.xz - C.xz), tX.y - C.y)) - vec2(r, e);

    //Subtract a box in order to flatten the top of the spout
    C = vec3(2, 4.5f, 0);
    vec3 b = vec3(5.0f, 6.0f, 2.0f) - C;
    vec3 d3 = abs(X - C) - b;
    float box = min(maxComponent(d3), 0) + length(max(d3, vec3(0)));
    float spout = max(min(maxComponent(d), 0) + length(max(d, vec2(0, 0))), -box);

    //Body is another warped cylinder: it has no rotation, but its radius varies
    //as a square cosine (this results in a smaller curvature than the sine used in the spout)
    r = 3.0f + square(cos(X.y / 2.5f));
    e = 2.3f;
    C = vec3(-2, 1.0f, 0);
    d = abs(vec2(length(X.xz - C.xz), X.y - C.y)) - vec2(r, e);
    float body = min(maxComponent(d), 0) + length(max(d, vec2(0, 0)));


    //The bottom of the teapot is another warped cylinder, it is made to agree with
    //the bottom of the body, but then it shrinks rapidly before being clamped in order
    //to make the flat bottom
    float y = max(X.y, -1.8f);
    r = 3.0f + square(cos(-1.3f / 2.5f)) - square((y + 1.3f) / (.5f));
    e = .8f;
    C = vec3(-2, -1.3f, 0);
    d = abs(vec2(length(X.xz - C.xz), X.y - C.y)) - vec2(r, e);
    float bottom = min(maxComponent(d), 0) + length(max(d, vec2(0, 0)));

    //The top lid of the teapot is very similar to the bottom,
    //except that the clamp happens later to make the shaft of the top handle
    y = min(X.y, 3.81f);
    r = 3.0f + square(cos(3.3f / 2.5f)) - square((y - 3.3f)) / .1f;
    e = 0.9f;
    C = vec3(-2, 3.3f, 0);
    d = abs(vec2(length(X.xz - C.xz), X.y - C.y)) - vec2(r, e);
    float top = min(maxComponent(d), 0) + length(max(d, vec2(0, 0)));

    //The top of the handle of the lid is formed by making a hemisphere
    //A hemisphere is made by intersecting a sphere with a box
    C = vec3(-2, 4.4f, 0);
    r = 0.6f;
    float toptop = length(X - C) - r;
    C = vec3(-2, 3.3f, 0);
    b = vec3(-1.0f, 4.4f, 2.0f) - C;
    d3 = abs(X - C) - b;
    float boxtop = min(maxComponent(d3), 0) + length(max(d3, vec3(0)));
    toptop = max(toptop, boxtop);
    
    //The handle is a warped torus: the center is moved up along the length of the
    //torus, causing the bend
    float R = 0.2f;
    r = 1.9f;
    C = vec3(-2.0f + X.x/2.0f, 1.0f, 0.0f);
    tX = X;
    tX.y += (X.x + 7.0f)/3.0f - 0.5f;
    float handle = length(vec2(length(tX.xy - C.xy) - r, tX.z - C.z)) - R;
    //We blend everything together, most blend factors are just small epsilons
    //However, the body/spout blend has a large radius to fatten the bottom

    return smin(toptop, smin(top, smin(bottom, smin(handle, smin(spout, body, 0.5f), 0.001f), 0.001f), 0.001f), 0.001f); 
}

Friday, August 22, 2014

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.

Friday, August 8, 2014

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

Thursday, August 7, 2014

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

     

Wednesday, August 6, 2014

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

Tuesday, August 5, 2014

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

Friday, August 1, 2014

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

Thursday, July 31, 2014

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

Wednesday, July 30, 2014

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;

Tuesday, July 29, 2014

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.

Saturday, July 26, 2014

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

Sunday, July 20, 2014

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

Saturday, July 19, 2014

Problem 79 - CIL, who needs high level languages?

After using Parrot Assembly and Java Bytecode, I figured I might as well continue my low level / "intermediate representation" language stint. CIL is the "Common Intermediate Language": it is essentially Java Bytecode for the .Net VM. So, programming in it was not too bad, maybe even a little bit nicer than Java Bytecode at times: one standard "call" method was nice instead of invokestatic, invokevirtual, etc. And most of the language is very similar to Java Bytecode - both are stack based, so they use very similar syntax. And the problem I chose to solve was pretty similar pro grammatically to problem 90 that I solved in Java Bytecode: both just involved lots of set operations, which are easy to express as ors, ands, etc (also, my code contains an xor, so clearly I am doing fancy stuff...). Also, CIL was nice as, though Java Bytecode exists only for Java, CIL is supposed to be able to support more than just C#, so there was no need in this case to create a class to wrap the main method in.

There was, however, one very important way in which programming in CIL was far less fun than Java Bytecode. I could not find as much good documentation, and the error messages are horrible. At least using mono (basically the open source .Net VM, while Microsoft also has one) there were essentially two errors one could get: "Unrecoverable Syntax Error" if an error happens at compile time, and "Invalid IL code" if the error happens at runtime. So, even though my code was basically correct very early (a couple of or's had to be changed to and's once I had things running...) Forgetting a single branch statement to go tho the top of a loop and a single pop instruction to clear the stack caused very hard to debug run time errors that took lots of "remove code until the error goes away" style debugging, which was not fun.

So basically, CIL is a fine stack-based assembly languages, as long as you don't cause any errors.
Also, it is worth noting that despite the title of this post...high level languages are actually quite nice. Variable names are really nice, even if I have gotten pretty good at remembering which register holds what variable.

Below code runs in 50ms on my machine.
.assembly extern mscorlib {}
.assembly e79 {}

.namespace E79 
{
    .method public static void main() cil managed
    {
        .entrypoint
        .maxstack 100
        .locals([0] int32[],
                [1] int32,
                [2] int32,
                [3] int32,
                [4] int32,
                [5] int32,
                [6] int32)
        ldc.i4 10
        newarr int32
        stloc.0
        ldc.i4.0
        stloc.3
        ldc.i4.0
        stloc.1
LOOP_INIT:
        ldloc.1
        ldloc.0
        ldlen
        bge OVERLOOP_INIT
        ldloc.0
        ldloc.1
        ldc.i4.0
        stelem.i4
        ldloc.1
        ldc.i4.1
        add
        stloc.1
        br LOOP_INIT
OVERLOOP_INIT:

LOOP_MAIN:
        call string [mscorlib]System.Console::ReadLine()
        dup
        brnull OVERLOOP_MAIN
        call int32 [mscorlib]System.Int32::Parse(string)
        stloc.2
        ldloc.2
        ldc.i4 100
        div
        stloc 4
        ldloc.2
        ldc.i4 10
        div
        ldc.i4 10
        rem
        stloc 5
        ldloc.2
        ldc.i4 10
        rem
        stloc 6
        ldloc.0
        ldloc 5
        ldloc.0
        ldloc 5
        ldelem.i4
        ldc.i4.1
        ldloc 4
        shl
        or
        stelem.i4
        ldloc.0
        ldloc 6
        ldloc.0
        ldloc 6
        ldelem.i4
        ldc.i4.1
        ldloc 5
        shl
        or
        ldc.i4.1
        ldloc 4
        shl
        or
        stelem.i4
        ldloc.3
        ldc.i4.1
        ldloc 4
        shl
        or
        ldc.i4.1
        ldloc 5
        shl
        or
        ldc.i4.1
        ldloc 6
        shl
        or
        stloc.3
        br LOOP_MAIN
OVERLOOP_MAIN:
        pop
        ldc.i4.0
        stloc 4
        ldc.i4.0
        stloc.1
LOOP_FINAL:
        ldloc.1
        ldc.i4 10
        bge OVERLOOP_FINAL
        ldloc.0
        ldloc.1
        ldelem.i4
        ldloc.3
        ldloc.1
        shr
        ldc.i4.1
        and
        ldc.i4.1
        xor
        or
        brzero IFPART
ELSEPART:
        ldloc.1
        ldc.i4.1
        add
        stloc.1
        br LOOP_FINAL
IFPART:
        ldloc 4
        ldc.i4 10 
        mul
        ldloc.1
        add
        stloc 4
        ldc.i4.1
        ldloc.1
        shl
        not
        ldloc.3
        and
        stloc.3
        ldc.i4.0
        stloc 5
LOOP_CLEAR:
        ldloc 5
        ldc.i4 10
        bge OVERLOOP_CLEAR
        ldloc.0
        ldloc 5
        ldloc.0
        ldloc 5
        ldelem.i4
        ldc.i4.1
        ldloc.1
        shl
        not
        and
        stelem.i4
        ldloc 5
        ldc.i4.1
        add
        stloc 5
        br LOOP_CLEAR
OVERLOOP_CLEAR:
        ldc.i4.0
        stloc.1
        br LOOP_FINAL
OVERLOOP_FINAL:
        ldloc.s 4
        call void [mscorlib]System.Console::WriteLine(int32)
        ret
    }
}

Monday, July 14, 2014

Problem 90 - Java Bytecode!

So, after solving problem 89 in Parrot Assembly, I claimed that I was interesting in trying out Java Bytecode. So, I did indeed use it. Turns out Java Bytecode is not exactly the world's most user friendly language to write in. Its not a standard assembly language, but is rather stack based, with some commands taking arguments directly, but most only directing with the stack, which makes things certainly different. Also, thank god I didn't have to invoke too many methods that weren't static in my own class...I wrote a helper function that is a wrapper for System.out.println, it was so frustrating to call it for debugging purposes!

Anyway, problem 90 was a rather simple problem, being capable of being expressed in terms of bitwise operations. Just lots of ors and ands and shifts, treating integers as sets, and iterating over all pairs of possible sets of {0...9}. This is only 1024 * 1024 =~ 1 million sets, and as the operations per pair of sets is exceedingly simple (and most can be thrown out very quickly for not having enough elements to represent a die), this was an entirely reasonable amount of work. Almost all the difficulty with this problem came from the problem, and not the language (well, the only problem related issue was me forgetting that, despite 6 and 9 being identified, a die could still have both, but I only forgot that exceedingly briefly, thanks to the example on the project euler page).

Anyway, below is my code...I would apologize for the lack of comments, as (I know) it makes it hard to read, but at least the ByteCode assembler I used didn't seem to have any syntax for allowing comments...so though unfortunate, it is what it is. Code runs in about 150ms, though it is notable that much of that is probably just starting up the JVM. Maybe my next language will be wonderfully low level again, or maybe I will go up to more sophisticated languages soon. Anyway, here is the beautiful code:
.class public e90
.super java/lang/Object

.method public static printInt(I)V
    .limit stack  100
    .limit locals 100
    getstatic     java/lang/System out Ljava/io/PrintStream;
    iload_0
    invokevirtual java/io/PrintStream println (I)V
    return
.end method

.method public static sixBitsSet(I)I
    .limit stack  100
    .limit locals 100
    iconst_1
    istore_1
    iconst_0
    istore_2
BITSETLOOP:
    iload_1
    iload_0
    if_icmpgt   BITSETLOOP_END
    iload_1
    iload_0
    iand
    ifeq        NOADD
    iinc        2 1
NOADD:
    iload_1
    iconst_1
    ishl
    istore_1
    goto        BITSETLOOP
BITSETLOOP_END:
    bipush      6
    iload_2
    if_icmpeq   RETURN_TRUE
    iconst_0
    ireturn
RETURN_TRUE:
    iconst_1
    ireturn
.end method
    
.method public static setContains(II)I
    .limit stack  100
    .limit locals 100
    iconst_1
    iload_1
    ishl
    iload_0
    iand
    ifgt        RETURN_SUCCESS
    iconst_0
    ireturn
RETURN_SUCCESS:
    iconst_1
    ireturn
.end method
          
.method public static check(III)I
    .limit stack  100
    .limit locals 100
    iload_0
    invokestatic e90/sixBitsSet(I)I
    iload_1
    invokestatic e90/sixBitsSet(I)I
    iadd
    iconst_2
    if_icmpne   RETURN_FAILURE
    iload_0
    sipush      512
    iand
    ifeq        SKIP_ADDSIX1
    iload_0
    sipush      64
    ior
    istore_0
SKIP_ADDSIX1:
    iload_1
    sipush      512
    iand
    ifeq        SKIP_ADDSIX2
    iload_1
    sipush      64
    ior
    istore_1
SKIP_ADDSIX2:
    iload_2
    bipush      10
    irem
    istore_3
    iload_3
    bipush      9
    if_icmpne   SKIP_SIXIFY
    bipush      6
    istore_3
SKIP_SIXIFY:
    iload_0
    iload_3
    invokestatic e90/setContains(II)I
    istore      4
    iload_1
    iload_3
    invokestatic e90/setContains(II)I
    istore      5
    iload_2
    bipush      10
    idiv
    istore_3
    iload_3
    bipush      9
    if_icmpne   SKIP_SIXIFY2
    bipush      6
    istore      3
SKIP_SIXIFY2:
    iload_0
    iload_3
    invokestatic e90/setContains(II)I
    istore      6
    iload_1
    iload_3
    invokestatic e90/setContains(II)I
    istore      7
    iload       4
    iload       7
    iand
    iload       5
    iload       6
    iand
    ior
    ireturn
RETURN_FAILURE:
    iconst_0
    ireturn        
.end method   
              
.method public static main : ([Ljava/lang/String;)V
    .limit stack  100
    .limit locals 100
    
    iconst_0
    istore      6
    bipush      9
    newarray    int
    astore      4        
    iconst_0    
    istore_0 
INITLOOP:
    iload_0
    bipush      9
    if_icmpge    INITLOOP_END
    aload       4
    iload_0
    iinc        0 1
    iload_0
    iload_0
    imul
    iastore
    goto        INITLOOP
INITLOOP_END:
    iconst_0
    istore_0
OUTERLOOP:      
    iload_0     
    sipush      1024
    if_icmpge   OUTERLOOP_END
    iload_0     
    istore_1    
INNERLOOP:      
    iload_1     
    sipush      1024
    if_icmpge   INNERLOOP_END
    iconst_0
    istore      5
INNERMOSTLOOP:
    iload       5
    bipush      9
    if_icmpge   INNERMOSTLOOP_END_SUCCESS
    iload_0
    iload_1
    aload       4
    iload       5
    iaload
    invokestatic e90/check(III)I
    ifeq        INNERMOSTLOOP_END_FAILURE
    iinc        5 1
    goto        INNERMOSTLOOP
INNERMOSTLOOP_END_SUCCESS:
    iinc        6 1
INNERMOSTLOOP_END_FAILURE:
    iinc        1 1
    goto        INNERLOOP
INNERLOOP_END:    
    iinc        0 1
    goto        OUTERLOOP
OUTERLOOP_END:
    iload       6
    invokestatic e90/printInt(I)V  
    return       
.end method