Wednesday, November 25, 2015

A Change of Rules in Golf

So, I have basically abandoned the Project Euler Language Challenge project for now it seems. I also didn't have the enthusiasm to get started on the Code Golf version of the PELC. However, over the last few days I have been bored and decided to do some code golf only in python. I have solved the first 23 problems in some very minimal python, and I find it very fun to 'play code golf', trying to squeeze out every last bit of code possible. Below is a chart of my progress:
1 47
2 52
3 57
4 77
5 57
6 50
7 83
8 110
9 88
10 79
11 268
12 78
13 41
14 105
15 54
16 34
17 180
18 147
19 135
20 64
21 99
22 106
23 177
Total23 Files2188

Wednesday, September 2, 2015

Code Golf progress.

After my last post, I noticed a few things. One, the process I am planning to engage in seems to be generally called "Code Golf". Second, a number of the problems I gave before were actually not even the best solutions I had. Third, "Character count" isn't a great measure either, so I will be using the most accurate and universal measure I can think of for now, which is size in memory of the files. Now that I have decided that I will be doing a code golf challenge with Project Euler subject to the one-problem-per-language constraint, I have gone through and chosen my most efficient solutions, which gave the following results:
2 e2.hs 237
3 181
4 e4.f 156
7 e7.rkt 267
9 e9.fs 449
10 e10.sml 762
11 e11.php 2252
12 e12.go 589
13 e13.lisp 5135
14 e14.js 272
16 76
17 e17.elm 1667
18 e18.scala 798
19 542
20 e20.e 393
21 e21.sq 578
22 e22.d 380
23 e23.ceylon 1061
24 e24.j 14
26 480
Total20 Files16289

2 eg2.hs 114
3 162
4 e4.f 156
7 eg7.rkt 182
9 eg9.fs 333
10 eg10.sml 318
11 e11.php 2252
12 e12.go 589
13 e13.lisp 5135
14 e14.js 272
16 76
17 e17.elm 1667
18 e18.scala 798
19 542
20 e20.e 393
21 e21.sq 578
22 e22.d 380
23 e23.ceylon 1061
24 e24.j 14
26 480
Total20 Files15502
The first table is where I was after just choosing short files. The second table is where I now am after starting to minify some of my solutions (the minified solutions are named "eg", for "euler golf"). I will hopefully finish minifying the solutions in this chart soon.

Monday, August 3, 2015

A New Challenge: Character Count Challenge

So, as anyone who has read this blog would probably have noticed, I haven't been solving many problems recently. I actually have written up solutions to a few problems beyond what is on this blog, but I haven't been able to port them to more esoteric languages. I think I have realized that at around the point where I am (a bit past 100), the problems are starting to actually be somewhat challenging from a mathematical / programming standpoint, and trying to squeeze things into different languages is just more effort than its worth (for example, I wrote a linear equation solver in Scale for problem 101...) a lot of later problems assume you are capable of code reuse from previous problems, and as we don't have that, things can start getting pretty crazy to try to keep hopping from language to language. So, without further ado, to introduce what I am planning on doing next. I decided to try to find some sort od secondary way of having fun with Project Euler, and I decided on trying to minimize the amount of code I need. In particular, I initially planned on trying to minimize lines of code accross multiple problems (and thus there would be a challenge to pick the right language for the right problem to minimize LOC), but I realized that Lines of code is a terrible, erratic, difficult to measure properly measure, so I am going to try a much finer measure, which is number of characters used total. Also, for now, I don't really want to deal with trying to optimize the lines of code in all 100 problems I have solved, so I decided on a reasonable strting point: try to minimize the characters to solve the first 20 problems. And because it seels silly solving problems that can easily be solved by hand, I am using the first 20 non-Pencil and Paper solved problems. For now, I am just putting up a blog post with my current character counts on the first 20 problems based on my past work, and I will try to work on shrinking it soon. I will also need to decide on some ways to codify this of the big issues is languages where I used inlining data instead of File I/O, but I will find a good way of counting after I actually get into the challenge. Also, I am ignoring whitespace. (And therefore Whitespace will be a banned language...)
2 e2.we 331
3 143
4 e4.f 153
7 350
9 e9.arnoldc 2213
10 687
11 1917
12 e12.go 356
13 5133
14 e14.clj 219
16 e16.bas 391
17 e17.elm 1165
18 828
19 e19.fjo 323
20 e20.e 251
21 e21.cbl 999
22 e22.d 242
23 e23.ceylon 527
24 e24.erl 342
26 218

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)
        (p.y - (f p.x)) * (- (f 0.0)) > 0.0

for line in System.IO.File.ReadLines("triangles.txt") do
  let rawpoints = (fun s -> System.Double.Parse(s)) (line.Split(','))
  let points = (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 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, 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 ->
        staðvær y,m,d,s
            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,
                        d := (d + 3) % 7,
                    ef (d = 0) þá
                        s := s + 1,

Tuesday, April 14, 2015


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 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
ArnoldC 9
Io 11
Shakespeare 12
Smalltalk 13
Clojure 14
Fjölnir 19
E 20
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
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
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

Friday, March 20, 2015

(After a VERY long Hiatus) Problem 44 in Scratch!

I have taken quite the long break from solving Project Euler problems and posting on this blog, but as Spring Break is coming up, I decided that now would be the perfect time to try to solve some problems, possibly using some languages that I have seen in the time since I was last solving.

Problem 101 happens to be quite hard; I have a solution, but it is in Python and uses numpy for some non-trivial linear algebra calculations, so it might take a little while for me to get a challenge-legal solution to it.

So, I decided to instead work on an easier problem, in a "fun" programming language, so I decided to use Scratch: a Blocks Programming Language courtesy of some people at MIT, which is intended mainly to teach young kids to program. As such, it is not exactly a powerhouse in terms of abstraction or performance, but it worked for this problem.

Using a Blocks programming language was certainly interesting. The main issues I ran into were

1) Figuring out where things are/how to do things in terms of the UI, which took a bit of time (though this probably could have been alleviated by watching a tutorial, it didn't take more than 5-10 minutes for me to get things by feeling around).

2)  Having to navigate back and forth through the UI in order to do seemingly trivial things: maybe there are some advanced shortcuts or something. But as I interpret it, in order to make "If a + b = 2" you need to open the controls tab, and grab an if block, then grab the operators tab, and grab an = block and drag it into the if block, then grab a + block and drag it into the left hand side (being careful not to accidentally place it incorrectly and replace the = block), and then you have to go to the data tab and click and drag both a and b into their respective circles, and then you have to write in a 2. That is a lot of steps and involves going through at least 3 tabs and click-and-dragging 4 things, which is a lot of work for what in most programming languages is about 7 characters of typing.

3) Dealing with lack of abstraction: Every variable has to be global (no local variables in functions), and "functions" can't return anything, so I had to use global variables for their return values.

But anyway, I have a solution, it works, and it meows when it is done, so I am happy.

PS: my table-making script is on another computer, so I will update the table soon, but not now.

A picture of my program is below: