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:
Wednesday, November 25, 2015
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:
Problem | File | Bytes |
2 | e2.hs | 237 |
3 | e3.cat | 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 |
Problem | File | Bytes |
16 | e16.py | 76 |
17 | e17.elm | 1667 |
18 | e18.scala | 798 |
19 | e19.pl | 542 |
20 | e20.e | 393 |
21 | e21.sq | 578 |
22 | e22.d | 380 |
23 | e23.ceylon | 1061 |
24 | e24.j | 14 |
26 | e26.es | 480 |
Total | 20 Files | 16289 |
Problem | File | Bytes |
2 | eg2.hs | 114 |
3 | eg3.cat | 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 |
Problem | File | Bytes |
16 | e16.py | 76 |
17 | e17.elm | 1667 |
18 | e18.scala | 798 |
19 | e19.pl | 542 |
20 | e20.e | 393 |
21 | e21.sq | 578 |
22 | e22.d | 380 |
23 | e23.ceylon | 1061 |
24 | e24.j | 14 |
26 | e26.es | 480 |
Total | 20 Files | 15502 |
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 soon...one 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 | e3.cat | 143 |
4 | e4.f | 153 |
7 | e7.ps | 350 |
9 | e9.arnoldc | 2213 |
10 | e10.lol | 687 |
11 | e11.io | 1917 |
12 | e12.go | 356 |
13 | e13.st | 5133 |
14 | e14.clj | 219 |
16 | e16.bas | 391 |
17 | e17.elm | 1165 |
18 | e18.pl | 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 | e26.es | 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) 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
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) } }
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:
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:
Subscribe to:
Posts (Atom)