# Problem-1 : Trimorphic.
 
def trimorphic?(n)
    def check(n, c)
        n == 0 || (n%10 == c%10 && check(n/10, c/10))
    end
    n = n.abs
    check(n, n**3)
end
 
100.times do |i|
    if trimorphic?(i)
        printf("%-6d : %d\n", i**3, i)
    end
end
 
# Problem-2 : Pendulum.
 
def pendulum_1(s)
    r = []
    s.chars.sort!.each_with_index do |x, i|
        r.public_send(i.even? ? :unshift : :push, x)
    end
    r.join
end
 
def pendulum_2(s)
    n = s.size
    m = (n+1) / 2
    r = []
    s.chars.sort!.each_with_index do |x, i|
        j = i / 2
        r[i.even? ? m-j-1 : m+j] = x
    end
    r.join
end
 
def pendulum_3(s)
    t = s.chars.sort!
    l, r = t.drop(1).partition.each_with_index {|_, i| i.odd?}
    (l.reverse + t.take(1) + r).join
end
 
def pendulum_4(s)
    l, r = (1...s.size).partition{|x| x.even?}
    s.chars.sort!.values_at(*l.reverse, 0, *r).join
end
 
# ..
 
def test(f)
    ss = ["", "a", "ba", "bca", "computer", "science"]
    rs = ["", "a", "ab", "cab", "tpmceoru", "sieccen"]
 
    ss.zip(rs) do |s, r|
        s = f.call(s)
        if s != r
            puts " Failed: expected `#{r}' got `#{s}'"
            return
        end
    end
    puts " Passed"
end
 
def time(f)
    def choices(pool, n)
        n.times.map{pool[rand(pool.size)]}
    end
 
    symbols = (32..126).map(&:chr) # printable
    elapsed = 0
 
    16.times do |i|
        s = choices(symbols, 2**i).join
        t = Time.now
        f.call(s)
        elapsed += Time.now - t
    end
    printf(" Elapsed: %.6f\n", elapsed)
end
 
fs = [
    method(:pendulum_1),
    method(:pendulum_2),
    method(:pendulum_3),
    method(:pendulum_4)
]
 
fs.each do |f|
    puts f.name
    test(f)
    time(f)
end

IyBQcm9ibGVtLTEgOiBUcmltb3JwaGljLgoKZGVmIHRyaW1vcnBoaWM/KG4pCiAgICBkZWYgY2hlY2sobiwgYykKICAgICAgICBuID09IDAgfHwgKG4lMTAgPT0gYyUxMCAmJiBjaGVjayhuLzEwLCBjLzEwKSkKICAgIGVuZAogICAgbiA9IG4uYWJzCiAgICBjaGVjayhuLCBuKiozKQplbmQKCjEwMC50aW1lcyBkbyB8aXwKICAgIGlmIHRyaW1vcnBoaWM/KGkpCiAgICAgICAgcHJpbnRmKCIlLTZkIDogJWRcbiIsIGkqKjMsIGkpCiAgICBlbmQKZW5kCgojIFByb2JsZW0tMiA6IFBlbmR1bHVtLgoKZGVmIHBlbmR1bHVtXzEocykKICAgIHIgPSBbXQogICAgcy5jaGFycy5zb3J0IS5lYWNoX3dpdGhfaW5kZXggZG8gfHgsIGl8CiAgICAgICAgci5wdWJsaWNfc2VuZChpLmV2ZW4/ID8gOnVuc2hpZnQgOiA6cHVzaCwgeCkKICAgIGVuZAogICAgci5qb2luCmVuZAoKZGVmIHBlbmR1bHVtXzIocykKICAgIG4gPSBzLnNpemUKICAgIG0gPSAobisxKSAvIDIKICAgIHIgPSBbXQogICAgcy5jaGFycy5zb3J0IS5lYWNoX3dpdGhfaW5kZXggZG8gfHgsIGl8CiAgICAgICAgaiA9IGkgLyAyCiAgICAgICAgcltpLmV2ZW4/ID8gbS1qLTEgOiBtK2pdID0geAogICAgZW5kCiAgICByLmpvaW4KZW5kCgpkZWYgcGVuZHVsdW1fMyhzKQogICAgdCA9IHMuY2hhcnMuc29ydCEKICAgIGwsIHIgPSB0LmRyb3AoMSkucGFydGl0aW9uLmVhY2hfd2l0aF9pbmRleCB7fF8sIGl8IGkub2RkP30KICAgIChsLnJldmVyc2UgKyB0LnRha2UoMSkgKyByKS5qb2luCmVuZAoKZGVmIHBlbmR1bHVtXzQocykKICAgIGwsIHIgPSAoMS4uLnMuc2l6ZSkucGFydGl0aW9ue3x4fCB4LmV2ZW4/fQogICAgcy5jaGFycy5zb3J0IS52YWx1ZXNfYXQoKmwucmV2ZXJzZSwgMCwgKnIpLmpvaW4KZW5kCgojIC4uCgpkZWYgdGVzdChmKQogICAgc3MgPSBbIiIsICJhIiwgImJhIiwgImJjYSIsICJjb21wdXRlciIsICJzY2llbmNlIl0KICAgIHJzID0gWyIiLCAiYSIsICJhYiIsICJjYWIiLCAidHBtY2VvcnUiLCAic2llY2NlbiJdCgogICAgc3MuemlwKHJzKSBkbyB8cywgcnwKICAgICAgICBzID0gZi5jYWxsKHMpCiAgICAgICAgaWYgcyAhPSByCiAgICAgICAgICAgIHB1dHMgIiBGYWlsZWQ6IGV4cGVjdGVkIGAje3J9JyBnb3QgYCN7c30nIgogICAgICAgICAgICByZXR1cm4KICAgICAgICBlbmQKICAgIGVuZAogICAgcHV0cyAiIFBhc3NlZCIKZW5kCgpkZWYgdGltZShmKQogICAgZGVmIGNob2ljZXMocG9vbCwgbikKICAgICAgICBuLnRpbWVzLm1hcHtwb29sW3JhbmQocG9vbC5zaXplKV19CiAgICBlbmQKCiAgICBzeW1ib2xzID0gKDMyLi4xMjYpLm1hcCgmOmNocikgIyBwcmludGFibGUKICAgIGVsYXBzZWQgPSAwCgogICAgMTYudGltZXMgZG8gfGl8CiAgICAgICAgcyA9IGNob2ljZXMoc3ltYm9scywgMioqaSkuam9pbgogICAgICAgIHQgPSBUaW1lLm5vdwogICAgICAgIGYuY2FsbChzKQogICAgICAgIGVsYXBzZWQgKz0gVGltZS5ub3cgLSB0CiAgICBlbmQKICAgIHByaW50ZigiIEVsYXBzZWQ6ICUuNmZcbiIsIGVsYXBzZWQpCmVuZAoKZnMgPSBbCiAgICBtZXRob2QoOnBlbmR1bHVtXzEpLAogICAgbWV0aG9kKDpwZW5kdWx1bV8yKSwKICAgIG1ldGhvZCg6cGVuZHVsdW1fMyksCiAgICBtZXRob2QoOnBlbmR1bHVtXzQpCl0KCmZzLmVhY2ggZG8gfGZ8CiAgICBwdXRzIGYubmFtZQogICAgdGVzdChmKQogICAgdGltZShmKQplbmQ=