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