Wednesday, August 24, 2016

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

Monday, February 29, 2016

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

Friday, February 26, 2016

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

Friday, February 5, 2016

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

Sunday, January 17, 2016

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.
ProblemFileBytes
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
ProblemFileBytes
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
Total38 Files3820