Thursday, May 22, 2014

Problem 55 - Elixir (I should get back to finals)

So, I am in the middle of finals period and have one final exam left to take, so clearly today was the perfect day to solve another Project Euler problem in the morning. I have a solution written down in Python for problem 86 that I am ready to port to another language, but its the kind of thing that I want to have a very nice and capable language to have to port into. So, I decided to free up Squirrel (which will mean that next time I use it, I will have used Squirrel 4 times). I had used Squirrel for Problem 55, which is on finding Lycherel numbers. Elixir is a functional language (with some OO features) that runs on the Erlang VM. So, it was a very good language for solving Problem 55, as reversing lists, checking for palindromes, etc are very natural things to do in a functional programming language. Anyway, Elixir was a pretty nice language: most of my issues came from practical use issues, not from the language (I had to install a newer version of Erlang, which I had to compile from source, so I now have both Erlang 1.5 and 1.7 on my machine, then for some reason the elixir scripts didn't like being run from outside of the bin directory...little stuff like that). The language itself is a functional programming language with pretty nice syntax. Perhaps the most annoying thing was how verbose the pattern matching syntax is, but there might be a better way that I just did not bother to learn. Because I compiled the code to a .beam file then ran the ans() function from the interpreter to get the answer, I don't have very good timing information, but this definitely runs in <1s:
defmodule E55 do
    def lrev(lst) when length(lst) == 0 do
        []
    end

    def lrev(lst) do
        lrev(tl(lst)) ++ [hd(lst)]
    end

    def numrev(x) do
        numrevHelper(x, 0)
    end

    def numrevHelper(0, r) do
        r
    end

    def numrevHelper(x, r) do
        numrevHelper(div(x,10), r*10 + rem(x,10))
    end

    def digits(x) when x == 0 do
        []
    end

    def digits(x) do
        digits(div(x, 10)) ++ [rem(x, 10)]
    end

    def isNumPalindrome(x) do
        isListPalindrome(digits(x))
    end

    def isListPalindrome(lst) when length(lst) < 2 do
        true
    end

    def isListPalindrome(lst) do
        isListPalindromeHelper(lst, lrev(lst), div(length(lst), 2), 0)
    end

    def isListPalindromeHelper(lst, tsl, target, k) when k >= target do
        true
    end
    
    def isListPalindromeHelper(lst, tsl, target, k) do
        if hd(lst) == hd(tsl) do
            isListPalindromeHelper(tl(lst),tl(tsl),target,k+1)
        else
            false
        end
    end

    def isLycherel(x) do
        isLycherelHelper(x, 0)
    end

    def isLycherelHelper(x, i) when i >= 50 do
        true
    end

    def isLycherelHelper(x, i) do
        y = x + numrev(x)
        if isNumPalindrome(y) do
            false
        else
            isLycherelHelper(y, i+1)
        end
    end

    def ans() do
        ansHelper(0, 1)
    end

    def ansHelper(acc, i) when i >= 10000 do
        acc
    end

    def ansHelper(acc, i) do
        if isLycherel(i) do
            ansHelper(1+acc,1+i)
        else
            ansHelper(acc,1+i)
        end
    end
end 

1 comment:

  1. This got featured on the Elixir Foundation's Newsletter, http://us3.campaign-archive.com/?u=2c36695b74400d6399fb3fa1a&id=af8dafd6d5. Thank you those who work there for seeing this and spreading the word!

    ReplyDelete