Couple of things in the last few months

Since last posting to the blog, I have moved from problem 106 on to problem 109, in the following steps:

A notable point about the sort of problems now: after getting through the series of problems which were all about a similar concept and were thus annoying to solve in different languages due to not being able to take advantage of redundancies, the next few problems are all completely independent, but the difficulty of problems in the hundreds is definitely getting to the point where high-enough level constructs are desired that to use a very weak programming language that feels like writing in assembly or worse is very tedious. With that said, here were the steps:

After using C++TMP on problem 50, I was free to use postscript again. Turned out that despite me being relatively familiar with writing programs in the language, I didn't feel like it was expressive enough to tackle 107 directly, so I used it to solve problem 38. This in turn freed up Lua, which I used to solve problem 107. For the next problem, I found about about dc, the predecessor to bc, and with my postscript-thinking hat still on, it was pretty easy to use to solve problem 14. This then freed up Clojure, which after clearing up some cobwebs in my head about how it and other lisp-like languages worked wasn't too hard for problem 108.

Then for a while I didn't find any languages or problems that piqued my interest, but then I looked at the fledgling language list, which is a great source for neat things to use, though more than half the languages there either don't have compilers or have compilers so funky that I spent some time trying to set them up and failed. I found the C2 programming language, which is basically an attempt at packaging C with a lot of syntactic sugar and a module-based build system. Some of the ideas about the build system seemed neat, but don't really apply at the scale of a project euler problem. The sugars are mostly actually sweet though, so it was a fairly fun language to use to solve 109, and I made a conscious effort to try out a number of new language features without being ridiculous.

Updated table is still at https://github.com/drsam94/PELC

Making more progress with some pseudo-languages

I decided to solve a few more problems. After I used Smalltalk on 104, I entered into the thick of a bunch of annoying problems that are all very closely related, which is supposed to be convenient because you can reuse code, but isn't convenient for me. I found some languages to solve these problems. I solved 105 in Swift (which was a pain to setup...) and I solved 106 in Typescript (which I am willing to call it's own language even if it's basically just annotated Javascript). Then I decided to try something off the wall, and I solved problem 50 using exclusively C++ Template Metaprogramming. My solution actually causes gcc to segfault when run on the necessary input size, but I decided that it was logically sound enough to let be. Now I have freed up postscript, which should be a reasonable enough language to try to do some stuff moving forward with.

Current table:

https://github.com/drsam94/PELC/blob/master/README.md

Solved a problem, possibly moving off of blog

I obviously haven't written much on this blog in a very long time. But I decided to go back and actually solve another problem today. I used a simple Awk script to solve problem 13, and in turn used Smalltalk to solve problem 104. I would not say Smalltalk is anywhere close to my favorite language, but it wasn't the worse to use.

Because my code highlighting tool broke and I probably won't have thee enthusiasm to maintain this blog, going forward I will probably only make changes to the github page for this project, https://github.com/drsam94/PELC , where a less-broken and up-to-date table with easy links to all the problems will be posted.

Broken Posts and 0 progress

I haven't posted anything on this blog for a rather long time; I haven't necessarily abandoned the core project, but nonetheless I doubt much progress will be made on it any time soon; languages are getting hard to find.

I have been playing around more with some of the code golf things, but that really distracts from the purpose of this blog.

However, I just checked and learned that the script I had been using for syntax highlighting is no longer hosted online in the place that I was running it from, so...I will look into trying to solve that issue so that the code in all my old posts looks less horrible. In other news, if I am not going to be posting for a long time, might as well make sure the main attraction is front and center: 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.

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
Ajsone	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
Python	16,24,39,65,66,60
Pascal	61
cLisp	13,62
Rebol	63
Tcl	64
Dart	63,65
Haskell	2,37,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
Javascript	9,31,60,103
P&P	1,5,6,8
P&P	15,25,28,69

Oops -- 60 and 103 swap

 I messed up last time and posted my non-working python solution to problem 103 instead of my working Javascript solution.

Working Javascript solution:

function sum(A) {
    var s = 0;
    for (var i = 0; i < A.length; ++i) {
        s += A[i]
    }
    return s
}

function powerSumSet(A) {
    sums = []
    maxes = []
    mins = []
    for (var i = 0; i < A.length; ++i) {
        maxes.push(0);
        mins.push(Infinity)
    }
    for (var i = 0; i < (1 << A.length); ++i) {
        nextSet = getSubSet(i, A)
        nextSum = sum(nextSet)
        if (sums.indexOf(nextSum) < 0) {
            sums.push(nextSum)
        }
        maxes[nextSet.length] = Math.max(maxes[nextSet.length], nextSum)
        mins[nextSet.length] = Math.min(mins[nextSet.length], nextSum)
    }
    return [sums, maxes, mins]
}

function getSubSet(s, set) {
    a = []
    k = 0
    while (s != 0) {
        if ((s & 1) == 1) a.push(set[k])
        k += 1
        s >>= 1
    }
    return a
}

function hasProp(s) {
    data = powerSumSet(s.slice(0, s.length - 1))
    sumset = data[0]
    maxes = data[1]
    mins  = data[2]
    for (var i = 0; i < maxes.length; ++i) {
        if (mins[i] <= s[s.length - 1] + maxes[i - 2]) {
            return false
        }
    }
    for (var i = 0; i < sumset.length; ++i) {
        if (sumset.indexOf(sumset[i] + s[s.length -1 ]) >= 0) {
            return false
        }
    }
    return true
}

// Returns the optimal set of size K, subject to compatibility with rest
var minsum = 256
function opt(K, rest) {
    if (K == 0) return rest
    var nextElem = (rest.length > 0 ? (rest[rest.length -1] + 1) : 1)
    var optimum = []
    while (minsum > sum(rest) + K * nextElem) {
        var nextSet = rest.slice(0, rest.length)
        nextSet.push(nextElem)
        if (hasProp(nextSet)) {
            var test = opt(K - 1, nextSet)
            if (test.length > 0 && sum(test) <= minsum) {
                minsum = sum(test)
                optimum = test
            }
        }
        nextElem += 1
    }
    return optimum
}
console.log(opt(7, []).join(""));

Python solution to 60, in order to offset things:

def isPrime(x):
    if x < 2:
        return False
    elif x % 2 == 0:
        return x == 2
    i = 3
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

def mag(x):
    return 10 if x < 10 else  10 * mag(x // 10)

def concat(x, y):
    return x * mag(y) + y

def getPrimes(N):
    return [x for x in range(N+1) if isPrime(x)]

def satisfies(p,s):
    return all(isPrime(concat(e, p)) and isPrime(concat(p, e)) for e in s)

primes = getPrimes(10000)

def finishSet(s, target, start):
    if len(s) == 5:
        test = sum(s)
        return test if test < target else target
    else:
        for i in range(start, len(primes)):
            p = primes[i]
            if satisfies(p,s):
                cset = s[:]
                cset.append(p)
                test = finishSet(cset,target,i)
                if test < target:
                    target = test
                    break
        return target

print(finishSet([],10000000,0))

Problem 103 -- Something happened

A long time ago, I decided to solve the few problems beyond the boundary of where I had worked. Problem 103, though it has been a while, I recall being a bit annoying, especially as the whole computation ended up only confirming that the given heuristic they have, which isn't true in general, still would have solved this problem. But oh well, here is what I did. A lot of bit-shifting silliness for efficient set implementations (and efficiently iterating over sets with a certain number of elements out of the universe).

N = 47
K = 7

def F(c):
    a = c & -c
    b = a + c
    return (((b ^ c) >> 2)//a) | b

def getSet(s):
    a = []
    k = 1
    while s != 0:
        if (s & 1) == 1: a.append(k)
        k += 1
        s >>= 1
    return a

def getSubSet(s, set):
    a = []
    k = 0
    while s != 0:
        if (s & 1) == 1: a.append(set[k])
        k += 1
        s >>= 1
    return a

S = sum

def hasProp(set):
    if (set[1] < K): return False

    for i in range(1, K//2):
        if S(set[0:i+1]) <= S(set[K-1:K]):
            return False

    for n in range(1, len(set)):
        s = (1 << n) - 1
        while s < (1 << len(set)) - 1:
            A = getSubSet(s, set)
            for m in range(n, len(set)):
                t = (1 << m) - 1
                while t < (1 << len(set)) - 1:
                    B = getSubSet(t, set);
                    if ((S(A) == S(B)) or ((m > n)  and (S(A) >  S(B)))) and (A != B):
                        return False
                    t = F(t)
            s = F(s)
    return True

minsum = 115 + (7 * 19)
minset = []
s = (1 << K) - 1
while s < (1 << N) - 1:
    sp = getSet(s)
    #print(sp)
    SUM = S(sp)
    if SUM < minsum and hasProp(sp):
        minset = sp
        minsum = SUM
    s = F(s)
print(minset)

Problem 66 -- Haskell, Continued Fractions, and Precision

In theory, problem 66 shouldn't have been very hard for me. I am currently taking a class on Continued Fractions, and Problem 66 involves finding solutions to a Pell's Equation, which involves computing convergents of Continuted Fractions. And indeed, implementing the algorithm for computing continued fraction expansions was not all that hard for me, as I had done it in Python as a way to simplify my work for a problem set just a couple days earlier.

However, for this problem, I found that in order to apply the algorithm accurately, more than the standard amounts of Double and Int precision were necessary. So, I had to use a FixedPoint package to give me access to 128-bit Integers and 256-bit fixed fractions. The use of these custom data types increased the runtime to about 2 minutes on my machine, but it's still fairly reasonable.

And now that I have "freed up Python", a solution I wrote a while ago will be able to cause the first forward momentum on problems in a long time.

import Data.List
import Data.FixedPoint
import Debug.Trace
-- Replace Double with Rational or with FixedPoint
cfr :: FixedPoint256256 -> (Int -> Int128)

cfr = repindex . cfr_helper

repindex :: ([Int128], Int) -> Int -> Int128

repindex (coeffs, rep) index
    | index < (length coeffs) = coeffs !! index
    | otherwise = coeffs !! (rep + ((index - (rep)) `mod` ((length coeffs) - rep)))

cfr_helper :: FixedPoint256256 -> ([Int128], Int)

cfr_helper alpha = let a0 = floor alpha in
                     let alpha1 = alpha - (fromIntegral a0) in
                       cfr_rec alpha1 [a0, floor (1.0/alpha1)] [alpha1]

cfr_rec :: FixedPoint256256 -> [Int128] -> [FixedPoint256256] -> ([Int128], Int)

gauss_map :: FixedPoint256256 -> FixedPoint256256

gauss_map alpha = (1.0 / alpha) - (fromIntegral (floor(1.0 / alpha)))

fuzzyIndex :: FixedPoint256256 -> [FixedPoint256256] -> Maybe Int

fuzzyIndex _ [] = Nothing
fuzzyIndex x (y:ys)
    | abs(x - y) < 1e-5 = Just 0
    | otherwise = case (fuzzyIndex x ys) of
        Just i  -> Just (i + 1)
        Nothing -> Nothing

cfr_rec alpha0 as alphas = let alpha1 = gauss_map(alpha0) in
    case fuzzyIndex alpha1 alphas of
        Just i  -> (as,i+1)
        Nothing -> cfr_rec alpha1 (as ++ [floor(1.0 / alpha1)]) (alphas ++ [alpha1])

min_soln :: Int -> (Int128,Int)
min_soln d = let coeffs = ((cfr . sqrt' . fromIntegral) d) in
        min_soln_rec d (coeffs) (coeffs 0) 1 1 0 1

min_soln_rec :: Int -> (Int -> Int128) -> Int128 -> Int128 -> Int128 -> Int128 -> Int -> (Int128,Int)

min_soln_rec d coeffs p1 q1 p0 q0 n = let an = coeffs n in
    let (pn,qn) = (p1 * an + p0, q1 * an + q0) in
        if (pn^2 - (fromIntegral d)*qn^2) == 1 then (pn,d)
        else min_soln_rec d coeffs pn qn p1 q1 (n+1)

maxSoln :: (Int128,Int) -> (Int128,Int) -> (Int128,Int)
maxSoln (x1,d1) (x2,d2)
    | x1 > x2 = (x1,d1)
    | otherwise = (x2,d2)

ans :: Int -> Int

isNotSquare :: Int -> Bool

isNotSquare x = let xx = fromIntegral x in (floor (sqrt xx))^2 /= (floor xx)

ans b = snd . foldr maxSoln (0,0) $ map min_soln $ filter isNotSquare [1..b]

main = putStrLn $ show $ ans 1000

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.

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
Ajsone	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
Python	16,24,39,65,66,60
Pascal	61
cLisp	13,62
Rebol	63
Tcl	64
Dart	63,65
Haskell	2,37,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
Javascript	9,31,60,103
P&P	1,5,6,8
P&P	15,25,28,69

Returning to Language Challenge: a Pyrrhic Victory

After a very long Hiatus, I decided to continue the language challenge at least a little bit farther. I found a few pretty wacky languages that want using, so I figured I would return to this challenge to test things out.

For my first returning problem, I used the language Ajsone - an acronym for "Abusing JSON Esolang" - the idea is that it's a language whose grammar is just JSON, but which is a full-fledged programming language when interpreted. The language wasn't too hard to deal with after getting over it's quirks -- essentially, keys and values that are strings starting with "=" have special meaning, and are used for all variable reading and function evaluation. The problems with this language all came from the interpreter (no offense, Alok Menghrajani, who designed the language: https://quaxio.com/ajsone/) -- there were very unuseful error messages, there is by default a stack-size limit of 100, which I removed, but the main issue that because it's a simple interpreter written in JS, it is terribly slow. Therefore, I am declaring this problem a "Pyrrhic Victory", as I have written a solution which I have essentially confirmed through testing would give the right answer, but it might take a couple days for the program to run. But anyway, problem 37 has now been redone, which frees up Haskell for future use.

{
    "%" : {
        "a" : "=in1",
        "b" : "=in2",
        "quotient" : {"=/" : {}},
        "iquot" : {"=|" : {"in1" : "=quotient", "in2" : 0}},
        "itake" : {"=*" : {"in1" : "=iquot", "in2" : "=b"}},
        "res"   : {"=-" : {"in1" : "=a", "in2" : "=itake"}}
    },
    "arrify" : {
        "=if" : {
            "cond" : { "===" : { "in1" : 0, "in2" : "=n"}},
            "then" : "=_arr",
            "else" : {
                "last_digit" : {"=%" : { "in1" : "=n", "in2" : 10}},
                "_temp" : "=_arr",
                "_t" : {"=arr.prepend" : { "e" : "=last_digit", "arr" : "=_temp" }},
                "_n" : {"=|" : {"in1" : {"=/" : {"in1" : "=n", "in2" : 10}}, "in2": 0}},
                "=arrify" : {"n" : "=_n", "_arr" : "=_t"}
            }
        }
    },
    "deArrify" : {
        "Length" : {"=arr.len": {"arr": "=inputArr"}},
        "=if" : {
            "cond" : {"===": {"in1" : "=Length", "in2" : "=__i"}},
            "then" : "=acc",
            "else" : {
                "_acc" : {"=*" : {"in1" : "=acc", "in2" : 10}},
                "nextDigit" : {"=arr.at" : {"arr" : "=inputArr", "offset" : "=__i"}},
                "__acc" : {"=+" : {"in1": "=_acc", "in2" : "=nextDigit"}},
                "nextIdx" : {"=+" : {"in1" : "=__i", "in2" : 1}},
                "=deArrify" : {"acc" : "=__acc", "__i" : "=nextIdx"}
            }
        }
    },
    "isprime" : {
        "even?" : {"=%" : { "in1" : "=n", "in2" : 2}},
        "=if" : {
            "cond" : {"===" : {"in1" : "=even?", "in2" : 0}},
            "then" : {"===" : {"in1" : "=n", "in2" : 2}},
            "else" : {
                "ip2" : {"=+" : {"in1" : "=_i", "in2" : 1}},
                "=if" : {
                    "sq" : {"=*" : {"in1": "=_i", "in2": "=_i"}},
                    "cond" : {"=<=": {"in1": "=sq", "in2": "=n"}},
                    "then" : {
                        "=if" : {
                            "remainder" : {"=%": {"in1" : "=n", "in2" : "=_i"}},
                            "cond" : {"===": {"in1": "=remainder", "in2" : 0}},
                            "then" : false,
                            "else" : {
                                "=isprime" : {"_i" : "=ip2"}
                            }
                        }
                    },
                    "else" : {"=>=" : {"in1" : "=n", "in2" : 2}}
                }
            }
        }
    },
    "slice" : {
        "=if" : {
            "cond" : {"===": {"in1" : "=start", "in2": "=end"}},
            "then" : "=acc",
            "else" : {
                "elem" : {"=arr.at": {"arr": "=list", "offset": "=start"}},
                "_acc" : {"=arr.append": {"arr": "=acc", "e" : "=elem"}},
                "sp1"  : {"=+": {"in1": "=start", "in2": 1}},
                "=slice" : {"start" : "=sp1", "acc" : "=_acc"}
            }
        }
    },
    "hasprop" : {
        "len" : {"=arr.len": {"arr": "=array"}},
        "=if" : {
            "cond" : {"===": {"in1": "=idx", "in2": "=len"}},
            "then" : true,
            "else" : {
                "_ip1" : {"=+": {"in1" : "=idx", "in2" : 1}},
                "firstSlice" : {"=slice": {"list" : "=array", "start" : 0, "end" : "=_ip1", "acc" : []}},
                "secondSlice": {"=slice": {"list" : "=array", "start" : "=idx", "end" : "=len", "acc" : []}},
                "guardedIsPrime" : {
                    "=if" : {
                        "_len" : {"=arr.len": {"arr": "=inSlice"}},
                        "cond" : {"===" : {"in1" : "=_len", "in2" : 0}},
                        "then" : true,
                        "else" : {
                            "N" : {"=deArrify" : {"inputArr" : "=inSlice", "__i" : 0, "acc" : 0}},
                            "res" : {"=isprime" : {"_i" : 3, "n" : "=N"}}
                        }
                    }
                },
                "firstPrime" : {"=guardedIsPrime" : {"inSlice" : "=firstSlice"}},
                "secondPrime" : {"=guardedIsPrime" : {"inSlice" : "=secondSlice"}},
                "=if" : {
                    "cond" : {"=&&" : {"in1": "=firstPrime", "in2" : "=secondPrime"}},
                    "then" : {"=hasprop" : {"idx" : "=_ip1"}},
                    "else" : false
                }
            }
        }
    },
    "computeAns" : {
        "=if" : {
            "cond" : {"===": {"in1" : "=count", "in2": 11}},
            "then" : "=sum",
            "else" : {
                "ar" : {"=arrify" : {"n" : "=num", "_arr" : []}},
                "=if" : {
                    "front" : {"=arr.at": {"arr" : "=ar", "offset" : 0}},
                    "is9"   : {"===" : {"in1": "=front", "in2" : 9}},
                    "cond"  : {"=isprime" : {"n" : "=front", "_i" : 3}},
                    "then" : {
                        "=if" : {
                            "np2"  : {"=+": {"in1" : "=num", "in2": 2}},
                            "cond" : {"=hasprop" : {"array" : "=ar", "idx" : 0}},
                            "then" : {
                                "sum_" : {"=+": {"in1" : "=sum", "in2": "=num"}},
                                "count_" : {"=+": {"in1": "=count", "in2" : 1}},
                                "=computeAns" : {"num" : "=np2", "sum" : "=sum_", "count" : "=count_"}
                            },
                            "else" : {
                                "=computeAns" : {"num" : "=np2"}
                            }
                        }
                    },
                    "else" : {
                        "=if" : {
                            "cond" : "=is9",
                            "ll" : {"=arr.len" : {"arr" : "=ar"}},
                            "last" : {"=slice" : {"list" : "=ar", "start" : 1, "end" : "=ll", "acc" : []}},
                            "then" : {
                                "last_" : {"=arr.prepend" : {"arr" : "=last", "e" : 3}},
                                "last__" : {"=arr.prepend" : {"arr" : "=last_", "e" : 2}},
                                "newNum" : {"=deArrify" : {"inputArr" : "=last__", "__i" : 0, "acc" : 0}},
                                "=computeAns" : {"num" : "=newNum"}
                            },
                            "else" : {
                                "incFront" : {"=+": {"in1" : "=front", "in2" : 1}},
                                "slast_" : {"=arr.prepend" : {"arr": "=last", "e" : "=incFront"}},
                                "nNum" : {"=deArrify" : {"inputArr" : "=slast_", "__i" : 0, "acc" : 0}},
                                "=computeAns" : {"num" : "=nNum"}
                            }
                        }
                    }
                }
            }
        }
    },
    "=computeAns" : {"num" : 11, "count" : 0, "sum" : 0}
}

Updates to golf

So, I considered to further my code golfing, and have now gotten the first 30 problems of project euler done with some pretty minimal code. Golf is fun. Will I return to language challenge type stuff soon? Maybe.

Problem	File	Bytes
1	e1.py	47
2	e2.py	52
3	e3.py	57
4	e4.py	77
5	e5.py	57
6	e6.py	50
7	e7.py	83
8	e8.py	110
9	e9.py	88
10	e10.py	79
11	e11.py	242
12	e12.py	78
13	e13.py	41
14	e14.py	99
15	e15.py	54
16	e16.py	34
17	e17.py	176
18	e18.py	135
19	e19.py	134

Problem	File	Bytes
20	e20.py	55
21	e21.py	99
22	e22.py	106
23	e23.py	167
24	e24.py	122
25	e25.py	73
26	e26.py	114
27	e27.py	168
28	e28.py	58
29	e29.py	56
30	e30.py	73
31	e31.py	102
32	e32.py	103
33	e33.py	159
34	e34.py	103
35	e35.py	150
36	e36.py	80
37	e37.py	189
38	e38.py	150
Total	38 Files	3820

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:

Problem	File	Bytes
1	e1.py	47
2	e2.py	52
3	e3.py	57
4	e4.py	77
5	e5.py	57
6	e6.py	50
7	e7.py	83
8	e8.py	110
9	e9.py	88
10	e10.py	79
11	e11.py	268
12	e12.py	78

Problem	File	Bytes
13	e13.py	41
14	e14.py	105
15	e15.py	54
16	e16.py	34
17	e17.py	180
18	e18.py	147
19	e19.py	135
20	e20.py	64
21	e21.py	99
22	e22.py	106
23	e23.py	177
Total	23 Files	2188

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.

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

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

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