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

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

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

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) { // 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) } }

Subscribe to:
Posts (Atom)