## Thursday, April 16, 2015

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

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

```

## Wednesday, April 15, 2015

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

```

## Tuesday, April 14, 2015

### 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) {
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)
}
}
```