鱼C论坛Python精英挑战赛（第三季02期）

jerryxjr1220 · 发表于 2017-9-11 11:56:35

本帖最后由 jerryxjr1220 于 2017-9-17 23:34 编辑

第三届鱼C论坛精英挑战赛开赛咯！为了增加趣味性，本届比赛增加了“新玩法”-- “押宝玩法”，“竞猜玩法”和“擂主玩法”。

规则：

1. 押宝玩法：进入“押宝”竞猜帖，购买主题（5鱼币）参与“押宝”，最终“押宝”获胜者将平分奖池的奖金并额外获取10鱼币奖励。猜错者将不返还“押宝”的鱼币。若本届比赛无人“押宝”成功，奖金将累计到下次比赛。

2. 竞猜玩法：直接在比赛帖的下方进行投票，凡事“竞赛”获胜者，将奖励5鱼币。竞猜无门槛，人人都可以参与。竞猜以后，请在本帖留个言，方便领取奖励。

3. 擂主玩法：上一期挑战成功的鱼油成为挑战赛的擂主，擂主有优先权提议下一期的赛题，一届挑战赛共分5期，同一届中当擂主最长的鱼油有额外奖励。

本期擂主：@小锟

本期赛题：算法题

题目：无穷序列中的位置

在由“123456789101112131415...”开始的无穷序列中，“456”在该序列中的位置是3（第一位的序号为0）。
相同的，“789”在该序列中的位置就是6。
那么“454”在该序列中的位置呢？由于该序列是无穷序列，可以一直拓展下去，所以当序列拓展到...434445464748...时，就可以发现“454”在该序列的第79位。
同理，“91”在该序列的第8位；“9100”在该序列的第188位。
“123456798”在该序列的第1000000071位。
“123459876”在该序列的第1000027773位。

请设计一个函数findposition(n), 输出n在该无穷序列中的位置。
def findposition(n):
"Your code here"
return index_of_the_string_with_starting_of_n
备注：输出位数可能会超过10亿位，注意运算效率。

要求：

程序运算正确，执行效率最高的即为获胜者。

竞猜：
“910000000”在该序列的第几位？

比赛截止日期：9月16日24时，竞猜和押宝截止日期为9月15日

@小甲鱼 @冬雪雪冬 @～风介～ @SixPy

SixPy · 发表于 2017-9-11 11:59:51

gunjang · 发表于 2017-9-11 17:20:06

本帖最后由 gunjang 于 2017-9-13 17:01 编辑

我能说答案是68888888（选项3）吗。。。555无法投票
该问题分成两个部分，找出数字x的位置和把序列分成连续的x,x+1,x+2...
第一个很简单，因为1-9共9个数字长度为1,10-99共90个数字长度为2。。。很有规律
第二个如果是普通的连续序列，或者只是长度为1的序列，还好判断，但是考虑到99100序列中截取的部分如9100就很难,故采用通配符？*代表1个和多个字符进行匹配。。。（正则表达式水平不够，大神应该可以直接用regex进行模式判断吧），容易出错，还缺少测试代码。。
凑合吧

#http://bbs.fishc.com/thread-96256-1-1.html
import math
def get10nindex(n):
        r = 0
        for i in range(1, n+1):
                r += (10**i - 10**(i-1)) * i
        return r

def getXindex(x):
        n = int(math.log10(x))
        return get10nindex(n) + (x-10**n-1+1)*(n+1)

#Wildcard: question mark(?): one character
#star(*) any number of characters
def match(source, startindex, x):
        #return True or False and startindex
        x = str(x)
        for i in range(len(x)):
                if source[startindex+i] == '?':
                        continue
                if source[startindex+i] == '*':
                        return True, len(source)
                if source[startindex+i] != x[i]:
                        return False, 0
        return True, startindex+len(x)

#9932 ==> 3199,3200 => 3199,3
def trymatch(newseq, sublen, qmcnt):
        #9932 => ..9932* => ..99  , 32*  => ??00, 32* #99+1=100[1:3]
        a = '?'*qmcnt+str(int(newseq[qmcnt:sublen])+1)[qmcnt-sublen:]#[:sublen-qmcnt]
        b = newseq[sublen:]
        #exp: a,b=99,100,have difficent length
        print('trymath', a,'vs',b)
        r = ''
        for i in range(sublen):
                if a[i] == b[i]:
                        r += a[i]
                else:
                        if a[i]=='?':
                                r += b[i]
                        elif b[i] == '*':
                                return True, r+a[i:]
                        else:
                                return False, ''
        return True, r

def getMinXinSequence(sequence):
        sequence = str(sequence)
        x = int(sequence)
        offset = 0
        if len(sequence) == 1:
                return x, offset
        if len(sequence) == 2:
                #56 78 => 5 7
                if int(sequence[1]) == int(sequence[0])+1:
                        return int(sequence[0]), 0
                #53 =>3|53|6 or 53|54
                t = (x%10)*10 + x//10
                if x < t:
                        return x, 0
                else:
                        return t, 1

        #length >= 3
        #wildchar
        #. match one char/digit
        #* match any chars/digits
        for sublen in range(1, len(sequence)+1):
                for qmcnt in range(sublen):
                        newseq = '?'*qmcnt + sequence + '*'
                        if qmcnt == 0:
                                if sublen == len(sequence): #n=sequence
                                        continue
                                n = int(sequence[:sublen])
                                index = sublen
                                while True:
                                        n += 1
                                        matched, index = match(newseq, index, n)
                                        if not matched:
                                                break
                                        else:
                                                if index >= len(sequence):
                                                        return int(sequence[:sublen]), 0 # matched
                        else:
                                if len(sequence) + qmcnt > 2*sublen:
                                        n = int(sequence[sublen-qmcnt:sublen-qmcnt+sublen])
                                        #check prev number
                                        matched, index        = match(newseq, 0, n-1)
                                        if not matched:
                                                continue
                                        index = sublen-qmcnt+sublen
                                        t = n
                                        while True:
                                                t += 1
                                                matched, index        = match(sequence, index, t)
                                                if not matched:
                                                        break
                                                else:
                                                        if index >= len(sequence):
                                                                return n-1, qmcnt # matched
                                else:
                                        #too complex ,such as 23|4523|46  =>2345, 2346
                                        #1|2312|4 or 12|312|4 => 123,124 qmcnt=1,2, sublen=3
                                        # 129,130(2913)
                                        matched, secondnum = trymatch(newseq, sublen, qmcnt)
                                        if matched:
                                                n = int(secondnum)-1
                                                if x < n:
                                                        return x, 0
                                                else:
                                                        return n, qmcnt
        return x, offset


def findposition(n):
    minx, offset = getMinXinSequence(n)
    return getXindex(minx)+offset

# print(5, getMinXinSequence('5'))        
# print(12345, getMinXinSequence('12345'))
# print(122123124, getMinXinSequence('122123124'))
# print(122123124126, getMinXinSequence('122123124126'))
# print(54, getMinXinSequence('54'))        #45 , 1
# print(56, getMinXinSequence('56'))        #5,incorrect
# t1 = '122123124' #==> 122
# print(t1[2:], getMinXinSequence(t1[2:])) #==> 122,2

# print(312, getMinXinSequence('312')) #==> 123,124 => 123,2
#print(9932, getMinXinSequence('9932')) #==> 3199,3200 => 3199,3 or 2|993,2|994
#print(9931, getMinXinSequence('9931')) #==> 3199,3200 => 3199,3 or 1|993,1|994

#print(45, getXindex(45)) #79
#print(123456798, getXindex(123456798)) #1000000071
#print(123459876, getXindex(123459876)) #1000027773

#print(findposition(789)) #6
#print(findposition(454)) #79
#print(getXindex(10000000)-1) #
print(findposition(9100)) #9100=>99,100=>99,1=>189

小锟 · 发表于 2017-9-12 11:33:19

本帖最后由小锟于 2017-9-16 16:15 编辑

9100这个地方特殊点太多，9991000用了re
798100101.这地方理不清，我只能用查找rfind找，有可能有bug的问题，具体已经注释

import re

def findposition(a):
    a = str(a)
    index = -1
    #length = len(a)
    if a not in '12345678910':
        fina = 0
        x = lambda i: i * 9 * (10 ** (i - 1))

        if '91' in a:
            #print(a)
            patter = re.compile(r'(.*?)([9][9]*)([1][0]*)(.*)')
            result = re.findall(patter, a)
            #print(result)
            result9 = result[0][1]
            result0 = result[0][2]
            result_9 = result[0][0]
            result_0 = result[0][3]
            maxnum = max(int(result9), int(result0))
            if (not result_9) and (not result_0):
                #maxnum = max(int(result9), int(result0))
             #   print(maxnum)
                a = str(maxnum)
                if '9' not in a:
                    fina = len(result9)
                #index = a.find('910')
                #a,fina= a[index + 1:],len(a[: index + 1])
                #fina = len(a[: index + 1])
            else:
                #可能有bug的地方
                txt = ''.join([str(i) for i in list(range(1,maxnum*10))])
                index = txt.rfind(a)





        length = len(a)
        s = 0
        for i in range(1, length):
            s += x(i)
        s += (int(a) - 10 ** (length - 1)) * length
        return s - fina if index == -1 else index
    return '12345678910'.find(a[0])



print(findposition(123456798))
print(findposition(98991000))
print(findposition(798991001011))
print(findposition(698991001011))
print(findposition(910000000))
print(findposition(991))

最后测试了下，发现连续数过不了测试 11121314

小剑剑 · 发表于 2017-9-13 14:03:19

本帖最后由小剑剑于 2017-9-14 13:21 编辑

'''
    对于无穷序列12345678910111213....（Infi）
    给出任意的字符串（s），返回它在无穷序列第一次出现的索引
    
    思路：
        1 s由至少3个数的不同部分组成
        从s的左边开始假设第一个完整的数字为x位
        再遍历每一个可能的开始位置
        返回这个数字，和偏移量
        2 有两部分组成

'''

def func(s):
    l=len(s)
    '''
        处理第一个字符为0的情况
    '''
    if s[0]!='0':#第一个不是零,则最多可以去int(s)
        answer=(int(s),0)
    else:#第一个是零,则最多可以去int('1'+s)
        answer=(int('1'+s),-1)
    nl=1
    '''
    下面这部分为第一中情况，当s第一位是完整数字的第一位时有可能会是两个部分组成但是没影响
    '''
    while nl<l:
        for i in range(nl):
            if i+nl<l:
                #数字首位不能为0
                iszero=False
                for j in range(i,l,nl):
                    if s[j]=='0':
                        iszero=True
                        break
                #有数字首位为0跳过
                if iszero:
                    continue
                f=int(s[i:i+nl])
                if i and str(f-1)[-1:-1*i:-1]!=s[i-1::-1]:
                    continue
                nums=s[0:i+nl]
                t=f
                while len(nums)<l:
                    t+=1
                    nums+=str(t)
                if (nums[0:l]==s) and (f<answer[0]):
                    answer=(f,i)
        nl+=1
    '''
    下面是情况2
    '''
    # if(l&1) and (int(s[0:l//2])+1)==int(s[l//2:l]):#处理前后两个数的长度不一样的的情况 即9999 10000
    if '1' in s and s[0]=='9':
        temp=s.index('1')
        subs=s[0:temp]
        exnine=True
        for i in '123456780':#前面只有9
            if i in subs:
                exnine=False
                break
        if  exnine:
            for i in '123456789':#后面只有0或者没有
                if i in s[temp+1:]:
                    exnine=False
                    break
        if exnine :
            if (l-temp-1)<=temp:
                tempanswer=(int(s[0:temp])+1,temp)
            else:
                tempanswer=(int(s[temp:]),temp)
            if tempanswer[0]<answer[0]:
                answer=tempanswer
            return answer
    #排除9999100000的情况后，奇数偶数的nl最小值不一样
    if(l&1):
        nl=l//2+1
    else:
        nl=l//2
    #nl一直取值到l
    while nl<l:
        #第一个数字向前偏移的范围为0~2nl-L
        for i in range(2*nl-l+1):
            if (s[nl-i]=='0'):
                continue
            h=int(s[0:nl-i])#前面一部分
            h+=1#加一之后这部分和下一个数字的对应位的数字一样
            x=l-nl#x 为交叉位
            if str(h)[0:x]==s[l-x:l]:#第一个数交叉部分在前面 第二个在后面 交叉部分相同则数字符合
                t=int(s[nl-i:l-x]+s[0:nl-i])+1#组合出数字
                if (t<answer[0]):
                    answer=(t,nl-i)
        nl+=1
    if len(str(answer[0]))<l:
        return answer
    #数字长为l时
    for i in range(1,l):
        if s[i]=='0':
            continue
        if i<len(str(int(s[0:i])+1)):
            tempanswer=(int(s[i:])*10**i,i)
        else:
            tempanswer=(int(s[i:]+s[0:i]),i)
        if answer[0]>tempanswer[0]:
            answer=tempanswer
    return answer



def func2(answer):
    num=answer[0]
    l=len(str(num))
    count=0
    for i in range(0,l-1):
        count+=9*10**i*(i+1)
    count+=(num-10**(l-1))*(l)
    return count-answer[1]

def findposition(n):
    print(func2(func(str(n))))

感觉这种思路太繁琐

小剑剑 · 发表于 2017-9-14 13:20:35

发现个bug，改了一下，辛苦大大再测一次了

jerryxjr1220 · 发表于 2017-9-14 14:23:24

小剑剑发表于 2017-9-14 13:20
发现个bug，改了一下，辛苦大大再测一次了

截止日期前，你们可以随意改，之后统一测试。

gunjang · 发表于 2017-9-14 17:10:59

本帖最后由 gunjang 于 2017-9-14 21:18 编辑

重新修改下，原来有不少bug，修复了同一个序列有多个解和进位的问题

#http://bbs.fishc.com/thread-96256-1-1.html
import math
def get10nindex(n):
        r = 0
        for i in range(1, n+1):
                r += (10**i - 10**(i-1)) * i
        return r

def getXindex(x):
        n = int(math.log10(x))
        return get10nindex(n) + (x-10**n-1+1)*(n+1)

#Wildcard: question mark(?): one character
#star(*) any number of characters
def match(source, index, x):
        #return True or False and next index
        x = str(x)
        for i in range(len(x)):
                if source[index+i] == '?':
                        continue
                if source[index+i] == '*':
                        return True, len(source)
                if source[index+i] != x[i]:
                        return False, 0
        return True, index+len(x)

def matchContinueN(source, index, x):
        while True:
                matched, index = match(source, index, x)
                if not matched:
                        return False
                else:
                        if index >= len(source)-1: #matched
                                return True
                x += 1

#9932 ==> 3199,3200 => 3199,2
def trymatch(newseq, sublen, qmcnt):
        #9932 => ..9932* => ..99  , 32*  => ??00, 32* #99+1=100[1:3]
        a = '?'*qmcnt+str(int(newseq[qmcnt:sublen])+1)[qmcnt-sublen:]#[:sublen-qmcnt]
        b = newseq[sublen:]
        #exp: a,b=99,100,have difficent length
        r = ''
        for i in range(sublen):
                if a[i] == b[i]:
                        r += a[i]
                else:
                        if a[i]=='?':
                                r += b[i]
                        elif b[i] == '*':
                                return True, r+a[i:]
                        else:
                                return False, ''
        return True, r

def getMinXinSequence(sequence): #return minx and offset(sometimes x is incomplete)
        sequence = str(sequence)
        x = int(sequence)
        offset = 0
        if len(sequence) == 1:
                return x, offset

        #length >= 2
        founded = False        
        for sublen in range(1, len(sequence)+1):
                #2312 have five continue Arrays
                #123,124 2231,2232  1223,1224  3122,3123  2312
                # ^^ ^^   ^^^ ^       ^^ ^^       ^ ^^^   ^^^^
                #123 is minimum
                for qmcnt in range(sublen): #qustion mark count
                        #wildchar
                        #? match one char/digit
                        #* match any chars/digits
                        newseq = '?'*qmcnt + sequence + '*'
                        if qmcnt == 0:
                                if sublen == len(sequence): #n=sequence
                                        minx = x
                                        offset = 0
                                        founded = True
                                        continue

                                n = int(sequence[:sublen])
                                if matchContinueN(newseq, sublen, n+1):
                                        if not founded:
                                                minx = n
                                        else:
                                                minx = min(n, minx)
                                        offset = 0                                                                
                                        founded = True

                        else:
                                if len(sequence) + qmcnt > 2*sublen:
                                        #second number
                                        n = int(sequence[sublen-qmcnt: sublen-qmcnt+sublen])
                                        if matchContinueN(newseq, 0, n-1):
                                                if not founded:
                                                        minx = n-1
                                                else:
                                                        minx = min(n-1, minx)
                                                offset = qmcnt                                                                
                                                founded = True

                                else:
                                        #too complex ,such as 23|4523|46  =>2345, 2346
                                        #1|2312|4 or 12|312|4 => 123,124 qmcnt=1,2, sublen=3
                                        # 129,130(2913)
                                        #9100 => 99,100=>offset =1 but return 2
                                        matched, secondnum = trymatch(newseq, sublen, qmcnt)
                                        if matched:
                                                n = int(secondnum)-1
                                                if not founded:
                                                        minx = n
                                                else:
                                                        minx = min(n, minx)
                                                offset = len(str(n))-(sublen-qmcnt) #not return n, qmcnt,because #(9100) 99,100,the sublen is 2,3, qmcnt is 2 but offset is 1
                                                founded = True                                                
                if founded:
                        return minx, offset

def findposition(n):
    minx, offset = getMinXinSequence(n)
    #print(minx, offset)
    return getXindex(minx)+offset

print(9100, findposition(9100)) #9100=>99,100=>99,1=>188

print(getMinXinSequence(2312)) #123,1
print(getMinXinSequence(99100101))
print(getMinXinSequence(99))

SixPy · 发表于 2017-9-17 09:59:05

凑个热闹~
先发个低效版

import itertools as itr

def findposition(n):
    s = str(n)
    l = len(s)
    ls=''
    for i in itr.count(1):
        i = str(i)
        ls += i
        try:
            idx = ls.index(s, -(l+len(i)))
            if idx>-1:
                return idx
        except:
            pass

SixPy · 发表于 2017-9-17 12:44:14

高效率版
匆忙之作，有点乱~

import re

def 单体(n):
    i = len(str(n))
    sm = sum(9*10**x*(x+1)for x in range(i-1))
    a = n-10**(i-1)
    idx = sm+a*i
    return idx

def 验证(i, n, s):
    ln = len(s)
    lst = [str(i)for i in range(n-ln//i-1, n+ln//i+1)]
    tmp = ''.join(lst)
    try:
        ix = tmp.index(s)
    except ValueError:
        return None
    
    idx = 单体(int(lst[0])) + ix
    return idx

def 跨段(s):
    rslt = re.findall('(9+)(10*)', s)
    if len(rslt)==1:
        i,n = max(((len(x),int(x))for x in rslt[0]), key=lambda t:t[1])
        idx = 验证(i, n, s)
        if idx is not None:
            return idx

def 等差1(s):
    for i in range(2,len(s)):
        rslt = re.findall(r'(?=(\d{%d})(\d{%d}))' %(i,i), s)
        if rslt:
            for n,m in rslt:
                if int(m)-int(n) == 1:
                    idx = 验证(i, int(n), s)
                    if idx is not None:
                        return idx


def 同数(s):
    rslt = re.findall(r'(?=(([1-9])\d+?)\2)', s)
    if rslt:
        for n,m in rslt:
            idx = 验证(len(n), int(n), s)
            if idx is not None:
                return idx
    

def findposition(n):
    "Your code here"
    s = str(n)
    try:
        return ''.join(str(i)for i in range(1, 110)).index(s)
    except ValueError:
        pass
    
    return 跨段(s) or 等差1(s) or 同数(s) or 单体(n)

if __name__ == '__main__':
    loc = {
        '123456798': 1000000071,
        '9100': 188,
        '123459876': 1000027773,
        '456': 3,
        '91': 8,
        '789': 6,
        '454': 79,
        '910000000':68888888,
        '9100009':5348889
    }

    data = [456, 789, 91, 454, 9100, 123456798, 123459876, 910000000, 9100009]
    for n in data:
        print(n,findposition(n), loc.get(str(n), None),sep=', ')

结果：

456, 3, 3
789, 6, 6
91, 8, 8
454, 79, 79
9100, 188, 188
123456798, 1000000071, 1000000071
123459876, 1000027773, 1000027773
910000000, 68888888, 68888888
9100009, 5348889, 5348889

账号		自动登录	找回密码
密码			立即注册

[技术交流] 鱼C论坛Python精英挑战赛（第三季02期）

本帖被以下淘专辑推荐:

评分

评分

点评

评分

点评

点评