Problem 102 - F#

So, now that I had a day of solving a ridiculous problem in a ridiculous language, now I get a chance to do a reasonable problem in a somewhat reasonable language. F# is a weird blend of a mostly functional programming language with tons of impure features and some strangeness from the fact that it runs on the CLI and thus links to the same library functions as C#. In my previous use of F#, I was able to basically treat it as a dialect of ML, but this time around I got a chance to use a number of the strange impure features. The results were interesting, and everything basically worked out, even if it was a very odd mixing of paradigms. Anyway, the problem itself wasn't too difficult after ensuring that I could do file I/O, and spending a couple of minutes thinking about how to answer "point contained in triangle" questions. The below solution runs in about 50ms:

type Point = { x : float; y : float}

let mutable ans = 0
let mutable c = 0


let ell (A : Point) (B : Point) x = 
    (B.y - A.y) / (B.x - A.x) * (x - A.x) + A.y

let isValid (points : Point[]) i =
    let A = points.[(i + 1) % 3] in
    let B = points.[(i + 2) % 3] in
    let f = ell A B in
    let p = points.[i] in
    if (A.x = B.x) then
        (p.x > A.x) = (0.0 > A.x)
    else
        (p.y - (f p.x)) * (- (f 0.0)) > 0.0

for line in System.IO.File.ReadLines("triangles.txt") do
  let rawpoints = Array.map (fun s -> System.Double.Parse(s)) (line.Split(','))
  let points = Array.map (fun i -> { x = rawpoints.[i*2]; y = rawpoints.[i*2 + 1] } : Point ) [|0 .. 2|]

  ans <- ans + (if (Array.fold (fun b i  -> b && isValid points i) true [| 0 .. 2 |]) then 1 else 0)


printfn "%d" ans

Fjölnir - Problem 19

So, now that I am back to solving problems, I figured I needed to do something fun. I used Scratch, a blocks programming language, and then I did some mildly complicated stuff in Scala. Now, I am at a fairly difficult point of trying to push this challenge forward: the problems are getting actually difficult, and the number of reasonable languages is dwindling.

So, what do I do? I use a completely unreasonable language.

Fjölnir is a language developed in Iceland in the 1980s. All of the keywords are in Icelandic, the only documentation is in Iceland, and the only implementation is for MS-DOS.

The first difficulty for this problem was finding information: the only documentation other than a brief Wikipedia article is https://notendur.hi.is//~snorri/087133-03/fjolnir.pdf. Yes, that is a 180-page pdf written in Icelandic. I got a large amount of assistance from Dagur Ammendrup's 99-bottles solution at http://www.99-bottles-of-beer.net/language-fjoelnir-259.html, and all of the rest of the syntax I learned through arduous attempts at parsing Icelandic (luckily symbols and general knowledge of the structure of programs helped a lot here).

The last issue to address came from DOS. Now, running a DOS emulator isn't too hard, there are plenty in various repos. The difficulty is that DOS and unicode don't play well together. DOS uses a very peculiar text encoding: not UTF-8, but CP437. I didn't realize this at first (I don't just assume that things can't handle UTF-8). Once I realized this, I changed atom's encoding to CP437, but I still ran into issues, because CP437 doesn't map certain characters properly, so my code is even more nonsensical in its original DOS form than in the converted form presented below.

Hopefully for future problems I will be dealing with more reasonable issues, but I will say that this foray into the Icelandic CS community of the 1980s was pretty interesting: and now that the below program (which runs very quickly!) is done, I get a chance to use F# again, so we will see how that goes.

"e19" < main
{
    main ->
        stef(;)
        staðvær y,m,d,s
        stofn
            d := 2,
            s := 0,
            fyrir( y := 1; y <= 100; y := y + 1) lykkja
                fyrir( m := 0; m < 12; m := m + 1) lykkja
                    ef (m = 3) eða (m = 5) eða (m = 8) eða (m = 10) þá
                        d := (d  + 2) % 7,
                    annarsef (m = 1) þá
                        ef (y % 4 = 0) þá
                            d := (d + 1) % 7,
                        eflok
                    annars
                        d := (d + 3) % 7,
                    eflok,
                    ef (d = 0) þá
                        s := s + 1,
                    eflok
                lykkjulok,
            lykkjulok,
            skrifastreng(;"Solution\n"),
            skrifa(;s),
        stofnlok
}
*
"GRUNNUR"
;

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. I am looking into ways to express this information better so that I don't have to hide any 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
Fjölnir	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
Scratch	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	16,24,39,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
Scala	18,44,101
F#	19,102
P&P	1,5,6,8
P&P	15,25,28,69

Problem 101 in Scala

I worked out a solution to problem 101 first in Python, but it was difficult to port this solution to another language: I had need of numpy to solve linear systems of equations. After spending a while not wanting to do what needed to be done, I finally sat down and wrote a (not-entirely general) system of linear equations solver in Scala. Scala was a decent language for this, due to the existence of map operations, a very necessary BigInt class, and the ability to easily define and use a Rational class. I am sure that if I were more well versed in the ways of Scala I could have made this simpler, but oh well: I have a solution to the problem, my first new solution to a problem in many months, and it runs in under a second.

class Rational(n : BigInt, d: BigInt) {
    private def gcd(x: BigInt, y: BigInt): BigInt = {
        if (x == 0) y
        else if (x < 0) gcd(-x, y)
        else if (y < 0) -gcd(x, -y)
        else gcd(y % x, x)
    }
    private val g = gcd(n, d)

    val numer: BigInt = n/g
    val denom: BigInt = d/g
    def +(that: Rational) =
        new Rational(numer * that.denom + that.numer * denom, denom * that.denom)
    def -(that: Rational) =
        new Rational(numer * that.denom - that.numer * denom, denom * that.denom)
    def *(that: Rational) =
        new Rational(numer * that.numer, denom * that.denom)
    def *(that: BigInt) =
        new Rational(that * numer, denom);
    def /(that: Rational) =
        new Rational(numer * that.denom, denom * that.numer)
    def reciprocal() =
        new Rational(denom, numer)
    def ==(that: Rational) =
        (numer == that.numer && denom == that.denom)
}

object e101 {

    val one = BigInt(1)
    val u = Array(one, -one, one, -one, one, -one, one, -one, one, -one, one)

    def solve(matrix: Array[Array[Rational]]): Array[BigInt] = {
        for (i <- 0 to matrix.size - 1) {
            // Get leading 0s
            for (j <- 0 to (i - 1)) {
                matrix(i) = matrix(i).map(_ * matrix(i)(j).reciprocal)
                for (k <- j to matrix(i).size - 1) {
                    matrix(i)(k) = matrix(i)(k) - matrix(j)(k)
                }
            }
            //Get the 1 in front
            matrix(i) = matrix(i).map(_ * matrix(i)(i).reciprocal)
        }
        // We go farther than row reduction, and get something
        // that looks the identity
        // (We assume correctly our matrix is invertible)
        for (i <- 1 to matrix.size - 1) {
            val ii = matrix.size - i
            for (j <- 0 to ii - 1) {
                val m = matrix(j)(ii)
                for (k <- 0 to matrix(j).size - 1) {
                    matrix(j)(k) = matrix(j)(k) - m * matrix(ii)(k)
                }
            }
        }
        val t = matrix.transpose
        return t(matrix.size).map((x: Rational) => x.numer / x.denom)
    }

    //For row reduction, we need the augmented matrix with the sequence in the
    //right-hand column
    def getMatrix(seq: Array[BigInt]) : Array[Array[Rational]] = {
        val matrix : Array[Array[Rational]] = new Array(seq.size)
        for (i <- 0 to matrix.size - 1) {
            matrix(i) = new Array(seq.size + 1)
            for (j <- 0 to seq.size - 1) {
                matrix(i)(j) = new Rational(BigInt(i  + 1) pow j, 1)
            }
            matrix(i)(seq.size) = new Rational(seq(i), 1)
        }
        return matrix
    }

    def evalPoly(p: Array[BigInt], n: Int): BigInt = {
        var s = BigInt(0)
        for (i <- 0 to p.size - 1) {
            s += p(i) * (BigInt(n) pow i)
        }
        return s
    }

    def FIT(p: Array[BigInt]): BigInt = {
        for (i <- 1 to 11) {
            var nextVal = evalPoly(p, i)
            if (nextVal != evalPoly(u, i)) {
                return nextVal
            }
        }
        return 0
    }

    def main(args: Array[String]) = {
        var ans = BigInt(0)
        var seq: Array[BigInt] = new Array(0)
        for(i <- 1 to 10) {
            seq = seq :+ evalPoly(u, i)
            val p = solve(getMatrix(seq))
            val fit = FIT(p)
            ans += fit
        }
        println(ans)
    }
}