1729 @ ウィキ

Arrow


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

  • rna->imageのfillはピクセルをグラフと見て、グラフの探索で実装すると再帰オバーフローしなくなるらしい・・・、ぜんぜん気づかなかった・・・ -- (kt3k) 2007-07-24 14:03:00
  • dna->rnaの文字列変換はstringではなくてropeというデータ型を使うと、まともな時間で計算終了できるようになるらしい・・・、そんなのぜんぜん知らないし・・・ -- (kt3k) 2007-07-24 14:12:26
  • やっぱり最初に書いて消されてる文字列はヒントだったのか、しかしそこから、出てくるRNAの解釈がちゃんと描画できなかった、やっぱりfillのバグで何かおかしかったのかなぁ・・・、dna->rnaはセルフチェック通ってたので、dna->rnaは遅くてもバグは無かったはず・・・ -- (kt3k) 2007-07-24 14:14:48
  • REPAIR GUIDE出たー。というかヒント文字列の写し間違いだった。とてつもなく悔しい・・・、 -- (kt3k) 2007-07-24 14:23:46
  • みんなの感想ページ面白すぎw -- (kt3k) 2007-07-24 14:33:54
  • FIELD REPAIRコードはprefix分かっても例によってdna->rnaの解析が終わらない。 -- (kt3k) 2007-07-24 14:45:42
  • python ropeとかpython fingerstringで検索しても何も出てこないし・・・、誰かレシピかいてないかなぁ・・・、 -- (kt3k) 2007-07-24 14:46:49
  • なぜか2ページ目が出てこない・・・ -- (kt3k) 2007-07-24 16:20:46
  • fillのバグ動作は解消。スピードは遅いままだけど、fill自体そんなに重要じゃなさそうなので、とりあえこれでいいや・・・ thanks to http://stonecode.svnrepository.com/icfp2007/trac.cgi/browser/lib/rna_interpreter.rb -- (kt3k) 2007-07-25 05:50:33
  • fill、今のところ600x600を全部塗るのに5秒ぐらいかかってる気がするけど、mspaintで同じだけのマスをfillするとき、明らかに0.数秒単位しかかかってない・・・、なにかいい工夫があるはず -- (kt3k) 2007-07-26 20:22:08
名前:
コメント:

すべてのコメントを見る

def raw_nat( dna ):
    r = 0
    for c in dna[::-1]:
        if c == 'C': r*=2; r+=1
        else: r*=2
    return r

def raw_consts( dna ):
    i = 0
    l = len(dna)
    res = ''
    while i<l:
        c = dna[i]
        if c == 'C': res+= 'I'; i+=1
        elif c == 'F': res+= 'C'; i+=1
        elif c == 'P': res+= 'F'; i+=1
        elif c == 'I': res += 'P'; i+=2
    return res

def quote( dna ):
    res = ''
    for c in dna:
        if c == 'I': res += 'C'
        elif c == 'C': res += 'F'
        elif c == 'F': res += 'P'
        else: res += 'IC'
    return res

def asnat( n ):
    if n == 0: return 'P'
    elif n%2 == 0: return 'I' + asnat(n/2)
    else: return 'C' + asnat(n/2)

class DNA(object):
    def __init__( _, dna ):
        _.rna = []
        _.dna = dna
        _.c = 0
        _.i = 0
    def execute( _ ):
        while 1:
            print 'iteration '+str(_.c)
            print 'dna =',_.dna[_.i:_.i+10]+'...','('+str(len(_.dna)), 'bases)'
            pattern = _.pattern()
            print 'patern =', ''.join(pattern)
            template = _.template()
            print 'template =', ''.join(template)
            _.matchreplace(pattern,template)
            print 'len(rna) =', len(_.rna)
            print
            _.c += 1
    def pattern( _ ):
        pattern = []
        level = 0
        while 1:
            dna = _.dna[_.i:_.i+3]
            if dna.startswith('C'): _.i+=1; pattern.append('I')
            elif dna.startswith('F'): _.i+=1; pattern.append('C')
            elif dna.startswith('P'): _.i+=1; pattern.append('F')
            elif dna.startswith('IC'): _.i+=2; pattern.append('P')
            elif dna.startswith('IP'): _.i+=2; pattern.append('!'+_.nat())
            elif dna.startswith('IF'): _.i+=3; pattern.append('?'+_.consts())
            elif dna.startswith('IIP'): _.i+=3; pattern.append('('); level += 1
            elif dna.startswith('IIC') or dna.startswith('IIF'):
                _.i+=3
                if level == 0:
                    return pattern
                else:
                    pattern.append(')')
                    level -= 1
            elif dna.startswith('III'): _.rna.append(_.dna[_.i+3:_.i+10]); _.i+=10
            else: _.finish()
    def template( _ ):
        template = []
        while 1:
            dna = _.dna[_.i:_.i+3]
            if dna.startswith('C'): _.i+=1; template.append('I')
            elif dna.startswith('F'): _.i+=1; template.append('C')
            elif dna.startswith('P'): _.i+=1; template.append('F')
            elif dna.startswith('IC'): _.i+=2; template.append('P')
            elif dna.startswith('IF') or dna.startswith('IP'): _.i+=2; template.append('/'+_.nat()+'_'+_.nat())
            elif dna.startswith('IIC') or dna.startswith('IIF'): _.i+=3; return template
            elif dna.startswith('IIP'): _.i+=3; template.append('A'+_.nat())
            elif dna.startswith('III'): _.rna.append(_.dna[_.i+3:_.i+10]); _.i+=10
            else: _.finish()
    def finish( _ ):
        open('endo.rna','w').write('\n'.join(_.rna))
        raise Exception('execution complete, ' + str(len(_.rna)) + ' rna commands')
    def matchreplace( _, pattern, template ):
        e = []
        j = 0
        c = []
        for p in pattern:
            if p in 'ICFP':
                if _.dna[_.i+j] == p: j+=1
                else: _.dna = _.dna[_.i:]; print 'match failed at pattern', p; _.i=0; return
            elif p.startswith('!'):
                j += int(p[1:])
                if _.i + j >= len(_.dna): _.dna = _.dna[_.i:]; _.i=0; print 'match failed at pattern', p; return
            elif p.startswith('?'):
                try:
                    find = _.dna[_.i+j:].index(p[1:])
                    print p,'found at',find
                    j += find + len(p) -1
                except:
                    _.dna = _.dna[_.i:]; _.i=0; print 'match failed at pattern', p; return
            elif p == '(': c.append(j)
            elif p == ')': e.append(_.dna[_.i+c.pop():_.i+j])
        else:
            print 'successful match of length', sum(map(len,e))
            #for i,d in enumerate(e): print 'e['+str(i)+'] = ' + d[:10] + '... (' + str(len(d)) + ' bases)'
            _.dna = _.replace(template, e) + _.dna[_.i+j:]
            _.i = 0
    def replace( _, template, e ):
        r = ''
        for t in template:
            if t in 'ICFP': r += t
            elif t.startswith('/'):
                level, n = map(int,t[1:].split('_'))
                if n < len(e): r += _.protect(level, e[n])
            elif t.startswith('A'):
                n = int(t[1:])
                if n < len(e): r += asnat(len(e[n]))
                else: r += asnat(0)
        return r
    def nat( _ ):
        try:
            p = _.dna[_.i:].find('P')
        except:
            _.finish()
        dna = _.dna[_.i:_.i+p]
        _.i+=p+1
        return str(raw_nat(dna))
    def consts( _ ):
        f = _.dna[_.i:].index
        try:
            p = min([f('IF'),f('IP'),f('II')])
        except:
            _.finish()
        dna = _.dna[_.i:_.i+p]
        _.i+=p
        return raw_consts(dna)
    def protect( _, level, d ):
        if level == 0: return d
        else: return _.protect(level-1,quote(d))

if __name__ == '__main__':
    import sys
    print sys.argv[1]
    try: prefix = open(sys.argv[1]).read()
    except IOError: prefix = ''
    endo = open('endo.dna').read()
    DNA(prefix+endo).execute()

import os

class VM(object):
    def __init__( _, rna ):
        _.bucket = Bucket()
        _.pos = Pos()
        _.mark = Pos()
        _.bitmaps = [Bitmap()]
        _.rna = rna
    def currentPixel( _ ):
        return _.bucket.currentPixel()
    def build( _ ):
        for r in _.rna:
            if r == 'PIPIIIC': _.bucket.addColor(0,0,0)
            elif r == 'PIPIIIP': _.bucket.addColor(255,0,0)
            elif r == 'PIPIICC': _.bucket.addColor(0,255,0)
            elif r == 'PIPIICF': _.bucket.addColor(255,255,0)
            elif r == 'PIPIICP': _.bucket.addColor(0,0,255)
            elif r == 'PIPIIFC': _.bucket.addColor(255,0,255)
            elif r == 'PIPIIFF': _.bucket.addColor(0,255,255)
            elif r == 'PIPIIPC': _.bucket.addColor(255,255,255)
            elif r == 'PIPIIPF': _.bucket.addOpac(0)
            elif r == 'PIPIIPP': _.bucket.addOpac(255)
            elif r == 'PIIPICP': _.bucket.reset()
            elif r == 'PIIIIIP': _.pos.move()
            elif r == 'PCCCCCP': _.pos.turnCounterClockwise()
            elif r == 'PFFFFFP': _.pos.turnClockwise()
            elif r == 'PCCIFFP': _.mark.mark(_.pos.pos())
            elif r == 'PFFICCP': _.bitmaps[0].line(_.pos.pos(), _.mark.pos(), _.currentPixel())
            elif r == 'PIIPIIP': _.bitmaps[0].tryfill(_.pos.pos(), _.currentPixel())
            elif r == 'PCCPFFP': _.addBitmap(Bitmap())
            elif r == 'PFFPCCP': _.compose()
            elif r == 'PFFICCF': _.clip()
            else: pass
    def compose( _ ):
        if len(_.bitmaps) >= 2:
            a = _.bitmaps.pop(0)
            b = _.bitmaps.pop(0)
            _.addBitmap(b.compose(a))
    def clip( _ ):
        if len(_.bitmaps) >= 2:
            a = _.bitmaps.pop(0)
            b = _.bitmaps.pop(0)
            _.addBitmap(b.clip(a))
    def addBitmap( _, bitmap ):
        if len(_.bitmaps) < 10:
            _.bitmaps = [bitmap] + _.bitmaps

class Pos(object):
    def __init__( _ ):
        _.x = 0
        _.y = 0
        _.dir = 0 # 0:East 1:South 2:West 3:North
    def move( _ ):
        if _.dir == 0: _.x = (_.x + 1) % 600
        elif _.dir == 2: _.x = (_.x - 1) % 600
        elif _.dir == 1: _.y = (_.y + 1) % 600
        elif _.dir == 3: _.y = (_.y - 1) % 600
    def turnClockwise( _ ):
        _.dir = (_.dir + 1) % 4
    def turnCounterClockwise( _ ):
        _.dir = (_.dir - 1) % 4
    def mark( _, pos ):
        _.x, _.y = pos
    def pos( _ ):
        return _.x, _.y

class Bucket(object):
    def __init__( _ ):
        _.reset()
    def reset( _ ):
        _.r = _.g =_.b = _.o = _.c_num = _.o_num = 0
    def currentPixel( _ ):
        r = g = b = 0
        o = 255
        if _.c_num:
            r = _.r / _.c_num
            g = _.g / _.c_num
            b = _.b / _.c_num
        if _.o_num:
            o = _.o / _.o_num
        return r*o/255, g*o/255, b*o/255, o
    def addColor( _, *color ):
        r, g, b = color
        _.r += r
        _.g += g
        _.b += b
        _.c_num += 1
    def addOpac( _, opac ):
        _.o += opac
        _.o_num += 1
    def __str__( _ ):
        return str(_.currentPixel())

class Bitmap(object):
    def __init__( _ ):
        _.bitmap = [[(0,0,0,0)for x in xrange(600)]for x in xrange(600)]
    def __str__( _ ):
        ppm = ''
        for raw in _.bitmap:
            try:
             ppm += ''.join('%c%c%c'%(r,g,b)for r,g,b,a in raw)
            except:print raw
        return 'P6 600 600 255 ' + ppm
    def setPixel( _, pos, pixel ):
        x, y = pos
        _.bitmap[y][x] = pixel
    def getPixel( _, pos ):
        x, y = pos
        return _.bitmap[y][x]
    def line( _, pos0, pos1, pixel ):
        x0, y0 = pos0
        x1, y1 = pos1
        dx, dy = x1 - x0, y1 - y0
        d = max([abs(dx), abs(dy)])
        c = dx*dy <= 0
        x = d*x0 + (d - c)/2
        y = d*y0 + (d - c)/2
        for i in xrange(d):
            _.setPixel((x/d, y/d), pixel)
            x+=dx
            y+=dy
        _.setPixel((x1, y1), pixel)
    def tryfill( _, pos, pixel):
        old = _.getPixel(pos)
        if old != pixel:
            print pos,old,pixel
            _.fill(pos, pixel, old)
    def fill( _, pos, pixel, initial ):
        positions = [pos]
        a=0
        for pos in positions:
            if _.getPixel(pos) == initial:
                _.setPixel(pos, pixel)
                x, y = pos
                a+=1
                if a%100==0:print a
                if x>0  : positions.append((x-1,y))
                if x<599: positions.append((x+1,y))
                if y>0  : positions.append((x,y-1))
                if y<599: positions.append((x,y+1))
    def compose( _, a ):
        for x in xrange(600):
            for y in xrange(600):
                r0,g0,b0,a0 = _.bitmap[y][x]
                r1,g1,b1,a1 = a.bitmap[y][x]
                _.bitmap[y][x] = (r1 + r0*(255 - a1)/255,
                                  g1 + g0*(255 - a1)/255,
                                  b1 + b0*(255 - a1)/255,
                                  a1 + a0*(255 - a1)/255)
        return _
    def clip( _, a ):
        for x in xrange(600):
            for y in xrange(600):
                r0,g0,b0,a0 = _.bitmap[y][x]
                r1,g1,b1,a1 = a.bitmap[y][x]
                _.bitmap[y][x] = (r0*(a1/255),
                                  g0*(a1/255),
                                  b0*(a1/255),
                                  a0*(a1/255))
        return _

if __name__ == '__main__':
    import sys
    print sys.argv[1]
    rna = open(sys.argv[1]).read().split()
    vm = VM(rna)
    vm.build()
    print vm.bitmaps[0].bitmap[0][:10]
    print vm.bitmaps[0].bitmap[1][:10]
    open('test2.ppm','w').write(str(vm.bitmaps[0]))
    os.system('convert test2.ppm test2.png')