第6回東大京大コードゴルフ大会

hypertorus.rb

def search(size)
    dir = 1
    mem = {}
    pos = 0
    id = 0

    mem[0] = 0
    id += 1

    loop do
        pos ^= dir
        if pos >= (1 << size)
            puts "out"
            return mem
        end
        if mem[pos] == :<
            dir <<= 1
        elsif mem[pos] == :>
            dir >>= 1
        elsif mem[pos] == nil
            if mem[pos ^ dir] == :< && mem[pos ^ (dir << 1)] == nil && (dir << 1) < (1 << size)
                mem[pos] = id
                id += 1
            elsif mem[pos ^ dir] == :> && mem[pos ^ (dir >> 1)] == nil && (dir >> 1) > 0
                mem[pos] = id
                id += 1
            else
                if (dir << 1) < (1 << size)
                    mem[pos] = :<
                    dir <<= 1
                elsif (dir >> 1) > 0
                    mem[pos] = :>
                    dir >>= 1
                else
                    break
                end
            end
        else
            break
        end
    end
    return mem
end

# size = 10
# search(size).sort.each do |k, v|
#     puts "#{k.to_s(2).rjust(size)} #{v}"
# end

# p search(9).values.filter{|v|v.is_a? Integer}.max


def main
    code = "1r1+/rr:r~r:r=@-*-wrr"
    size = 9
    mem = search(size)
    gen = "." * (1 << size)
    mem.each do |i, id|
        if id.is_a? Integer
            gen[i] = code[id] || "."
        elsif id.is_a? Symbol
            gen[i] = id.to_s
        end
    end
    print gen
end
main