project-euler / Lua / 036.lua

package.path = package.path .. ";" .. "/home/taylor/Programs/Libraries/Lua/?.lua"
require "list"

-- nothing to do with television
-- it's a palindromic bit string
pbs = {data = {}}
mt = {}
-- NOTE: leading zeros don't count,
-- but it's easier for the sake of computation
-- to supply them here and filter them out
-- at some later time
mt.__index = function (t, k)
    if t.data[k] == nil then
        if k == 1 then
            -- base case
            t.data[k] = {"0", "1"}
        elseif k == 2 then
            -- base case
            t.data[k] = {"00", "11"}
        else
            t.data[k] = {}
            for _, v in ipairs(t[k - 2]) do
                t.data[k][#t.data[k] + 1] = "0" .. v .. "0"
                t.data[k][#t.data[k] + 1] = "1" .. v .. "1"
            end
        end
    end
    return t.data[k]
end
setmetatable(pbs, mt)

function bitstring2number(s)
    local x = 0
    for i = s:len(), 1, -1 do
        if s:sub(i, i) == "1" then
            x = x + 2^(s:len() - i)
        end
    end
    return x
end

function ispalindrome(s)
    for i = 1, math.floor(s:len()) do
        if s:sub(i, i) ~= s:sub(s:len() + 1 - i, s:len() + 1 - i) then
            return false
        end
    end
    return true
end

local sum = 0
-- need 20 bits to represent 1,000,000
for i = 1, 20 do
    for _, v in ipairs(pbs[i]) do
        if v:sub(1, 1) == "1" then
            local n = bitstring2number(v)
            if ispalindrome(tostring(n)) then
                print("Found one: " .. n)
                sum = sum + n
            end
        end
    end
end

print("Sum = " .. sum)
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.