Обход ячеек таблицы в виде шестиугольника параллельно каждой его из его сторон

pincher1519

Доброго времени суток!

вводная часть

Наткнулся на головоломку в интернете. Представлена таблица в виде шестиугольника. Каждая строка его определена регулярным выражением. Регулярное выражение определяет какие данные в указанной строке могут содержаться. Поломал весь свой мозг, решая данную головоломку, не выходило никак решение. Головоломка построена по принципу японских кроссвордов. Все бы ничего, но таблица - шестиугольник!...

Психанув - решил написать программу которая полным перебором найдёт те буквы, которые должны быть в ячейках.

собственно вопрос

Как получать строки из шестиугольной таблицы? Ну и как лучше её представлять в массиве?

Ссылка на задачку http://habrahabr.ru

Заранее спасибо за ваши советы.

Ззыж решение не прошу. Хочу сам решить :-)

UPD:

Нашел для себя решение с точки зрения формирования массива. По сути это будет следующая таблица:

---3-3-3---
--3-2-2-3--
-3-2-1-2-3-
--3-2-2-3--
---3-3-3---

Где "-" - это пустое значение... Осталось дело за малым, написать алгоритм обхода таблицы относительно сторон шестиугольника. Но думаю, это уже дело техники, раз идея формирования таблицы придумана...

Может у кого лучше идея есть, по хранению данных, чтобы удобно их было анализировать?

3 ответа

pincher1519

Я немного соврал 3 года назад. Задача решается примерно за 20 минут. Я опишу только сам алгоритм, за ним будет следовать куча некрасивого кода почти без комментариев. Актуальный, полностью переработанный код с улучшениями и багфиксами можно найти на ГитХабе: https://github.com/ReinRaus/RegexCrossTool

Итак, алгоритм:

  1. Проходим по всем регулярным выражениям и находим все конкретные символы в них. Это символьные классы [a-z] и одиночные символы abc. Игнорируем . и [^a-z]. Логика простая: если кроссворд имеет единственное решение, то все символы решения заданы конкретными классами, не отрицанием и не точкой. Полученный список символов используется для создания потом класса . и отрицания.
  2. Проходим по всем регулярным выражениям и находим в них символьные классы и одиночные символы r"\[\^?[a-z]+\]|[a-z]|\.", здесь нет поддержки метасимволов \w\d и.т.п. и символов кроме a-z, но это не сложно добавить, если сильно хочется. В данном кроссворде их нет. Пункт 2 выполняет функция getEntitys( regex )
  3. Делаем замену найденных последовательностей на их экранированное представление с оберткой в несохраняющую группу. То есть вместо [^d-f] мы будем искать (?:[\[^d\-f\]) и в полном переборе будут фигурировать классы символов, а не конкретные символы
  4. Делаем полный перебор символьных классов в соответствии с длиной. checkEnt( entity, length ). Это означает выражение [a-z]?x?.* при длине 3 будет представлено массивом [ "[a-z]x.", "x..", "[a-z]..", "..." ] Это все возможные варианты для данного выражения в символьных классах.
  5. Оптимизация. Выражение #32 будет рассчитываться около 40 часов, поэтому была написана оптимизация для него. Общее время сократилось до 15 минут. Меня это устраивает, но за это время начал писать вторую оптимизацию, потом закомментировал. Может кому интересно.
  6. Результат работы пункта 4 сохраняем на жесткий диск. Нет смысла считать все это каждый раз.
  7. Создаем карту доски. Если интересно - Карта гексагональной доски
  8. Объединение. Проходим по результатам работы и создаем список символов, которые возможны для регулярного выражения в конкретных позициях. Это достигается объединением сетов полученных из преобразования символьных классов в сеты char2set( char )
  9. Пересечение. Проходим по карте и находим пересечения сетов для каждой позиции поля кроссворда
  10. Фильтрация Фильтруем массив результата пункта 4 в соответствии с результатами пересечения, убираем те варианты из полного перебора, которые не соответствуют регулярным выражениям в той же ячейке кроссворда
  11. Делаем все снова начиная с пункта 7, пока фильтрация приносит плоды. Если фильтрация не сделала изменений, то данный алгоритм сделал все, что мог.
  12. Запускаем полный перебор для регулярных выражений, которые содержат обратные ссылки, потому что эти регулярные выражения раскрывались неэффективно. (.)\1* раскроется в ...... к примеру для длины 6
  13. Оставляем только подходящие значения из полного перебора.
  14. Для успокоения души еще пару раз делаем пункты 7-10
  15. Выводим результат

Результат:

n h p e h a s         
     d i o m o m t h        
    f o x n x a x p h       
   m m o m m m m r h h      
  m c x n m m c r x e m     
 c m c c c c m m m m m m    
h r x r c m i i i h x l s   
 o r e o r e o r e o r e    
  v c x c c h h m x c c     
   r r r r h h h r r u      
    n c x d x e x l e       
     r r d d m m m m        
      g c c h h c c         

Total time: 408.3628809452057 sec.

sota.py

def dim1( k, n, d ):
    y = k
    x = abs( k - d + 1) + 2 * n
    return [ y, x ]

def dim2( k, n, d ):
    t = k-d+1
    y = n
    if t>0: y+= t
    x = abs( 1-d )+2*k-n
    if t>0: x-= t
    return [ y, x ]

def dim3( k, n, d ):
    t1 = k - d + 1
    t2 = d - k - 1
    y = n
    if t2>0: y+=t2
    x = k + n
    if t1>0: x+=t1
    return [ y, x ]

def pushToRes( y, x, d, val, res, dimens ):
    ind = y*4*d+x
    if ( not ind in res.keys() ): res[ind] = {}
    res[ind][ dimens ] = val

def pushToRes2( y, x, d, val, res, dimens ):
    global lens
    ind = y*4*d+x
    index = (dimens-1)*(2*d-1)+val[0]
    if dimens==3: val[1] = lens[val[0]]-val[1]-1
    val = [ index, val[1] ]
    if ( not ind in res.keys() ): res[ind] = {}
    res[ind][ dimens ] = val

res = {}
d= 7
lens = list(range(d,2*d))+list(range(2*d-2,d-1,-1)) # d=3, lens = [3,4,5,4,3]

for i in range( 0, 2*d-1 ):
    for j in range( lens[i] ):
        d1 = dim1( i, j ,d )
        d2 = dim2( i, j ,d )
        d3 = dim3( i, j ,d )
        pushToRes2( d1[0], d1[1], d, [i,j], res, 1 )
        pushToRes2( d2[0], d2[1], d, [i,j], res, 2 )
        pushToRes2( d3[0], d3[1], d, [i,j], res, 3 )

maps = res
#print( res )
print( len( res ) )
x = list(res.keys())
x.sort()
res2 = [ res[i] for i in x ]
#print( res2 )
#print( str( res2 ).replace( "{", "Array(").replace( ":", "=>").replace( "}", ")") )

resudoku.py

import sota, re, pickle, os, time
reChars = r"\[\^?[a-z]+\]|[a-z]|\."
reCharsC = re.compile( reChars, re.I )

def getEntitys( regex ):
    def repl( m ):
        return "(?:"+re.escape( m.group(0) )+")"
    res = reCharsC.findall( regex )
    regex2 = reCharsC.sub( repl, regex )
    regex2 = "^" + regex2 + "$"
    res = list( set( res ) )
    return [ regex, re.compile( regex2, re.I), res ]

def getAllRe():
    return [
        r".*H.*H.*",            # 0
        r"(DI|NS|TH|OM)*",      # 1 
        r"F.*[AO].*[AO].*",     # 2
        r"(O|RHH|MM)*",         # 3
        r".*",                  # 4
        r"C*MC(CCC|MM)*",       # 5
        r"[^C]*[^R]*III.*",     # 6
        r"(...?)\1*",           # 7
        r"([^X]|XCC)*",         # 8
        r"(RR|HHH)*.?",         # 9
        r"N.*X.X.X.*E",         # 10
        r"R*D*M*",              # 11
        r".(C|HH)*",            # 12

        r"(ND|ET|IN)[^X]*",     # 13
        r"[CHMNOR]*I[CHMNOR]*", # 14
        r"P+(..)\1.*",          # 15
        r"(E|CR|MN)*",          # 16
        r"([^MC]|MM|CC)*",      # 17
        r"[AM]*CM(RC)*R?",      # 18
        r".*",                  # 19
        r".*PRR.*DDC.*",        # 20
        r"(HHX|[^HX])*",        # 21
        r"([^EMC]|EM)*",        # 22
        r".*OXR.*",             # 23
        r".*LR.*RL.*",          # 24
        r".*SE.*UE.*",          # 25

        r".*G.*V.*H.*",         # 26
        r"[CR]*",               # 27
        r".*XEXM*",             # 28
        r".*DD.*CCM.*",         # 29
        r".*XHCR.*X.*",         # 30
        r".*(.)(.)(.)(.)\4\3\2\1.*", # 31
        r".*(IN|SE|HI)",        # 32
        r"[^C]*MMM[^C]*",       # 33
        r".*(.)C\1X\1.*",       # 34
        r"[CEIMU]*OH[AEMOR]*",  # 35
        r"(RX|[^R])*",          # 36
        r"[^M]*M[^M]*",         # 37
        r"(S|MM|HHH)*"          # 38
    ]

def getFullABC():
    result = set()
    for i in getAllRe():
        for j in reCharsC.findall( i ):
            if not re.match( r"\[\^", j ) and not j == ".":
                result = result.union( char2set( j ) )
    return result

allLen =   [7,8,9,10,11,12,13,12,11,10,9,8,7,
            7,8,9,10,11,12,13,12,11,10,9,8,7,
            7,8,9,10,11,12,13,12,11,10,9,8,7]

def optimization( ent, length ):
    result = []
    # оптимизация - альтернатива в конце строки одной длины
    result1 = []
    reCh = r"(?:"+reChars+")+"
    re1 = r"\((?:"+reCh+r"\|)+"+reCh+r"\)$"
    opt1 = re.findall(re1, ent[0], re.I)
    if len( opt1 ) > 0:
        opt1 = opt1[0].replace( "(", "" ).replace( ")", "" )
        parts = opt1.split( "|" )
        count = list( set( [ len( re.findall( reChars, i, re.I ) ) for i in parts ] ) )
        if len( count ) == 1:
            count = count[0]
            left = re.sub( re1, "", ent[0], flags=re.I )
            result1 = checkEnt( getEntitys( left ), length-count )
            for i in result1:
                for j in parts:
                    result.append( i + j )
    # несколько символов подряд (в строке нет скобок)
##    result2 = []
##    if not re.search( r"[()]", ent[0] ):
##        grp = re.findall( r"(?<!--[\[])[a-z]{2,}(?![\]*+?{])", ent[0], re.I )
##        if len( grp ) -->0 :
##            ent2 = getEntitys( ent[0].replace( grp[0], "#", 1 ) )
##            ent2[0].replace( "#", "(?:"+grp[0]+")" )
##            ent2[1] = re.compile( "^"+ent2[0]+"$", re.I )
##            ent2[2].append( grp[0] )
##            print( ent, "\n", ent2 )
    if len( result ) > 0: return result
    return None

def checkEnt( ent, length ):
    optim = optimization( ent, length )
    if optim: return optim
    result = []
    maxv = len( ent[2] )
    if maxv == 1:
        result.append( ent[2][0]*length )
    else:
        counter = [0]*(length+1)
        label = 0
        print( ent[0] )
        iterCounter = 1
        while counter[length] == 0:
            text = ""
            for i in range( length ):
                text+= ent[2][ counter[i] ]
            if ent[1].match( text ):
                #print( text )
                result.append( text )

            counter[label]+= 1
            while counter[label] == maxv:
                label+=1
                counter[label]+= 1
            while label>0:
                label-=1
                counter[label] = 0
            if iterCounter % 10000000 == 0:
                print( iterCounter )
            iterCounter+=1
    return result

res22 = []
counter=0
reBack = [ i for i in range( len(getAllRe()) ) if re.search("\\\\\\d", getAllRe()[i] ) ]
#reBack.reverse()
print( reBack )
dump = "dump22.txt"
if os.path.isfile( dump ):
    with open( dump, "rb" ) as rfile:
        res22 = pickle.load( rfile )
        print( dump, "loaded." )
else:
    for i in getAllRe():
        res22.append( checkEnt( getEntitys( i ), allLen[counter] ) )
        counter+=1
    with open( dump, "wb" ) as rfile:
        pickle.dump( res22, rfile )

#print( checkEnt( getEntitys( getAllRe()[8] ), 6 ) )

def char2set( char ):
    char=char.lower()
    result = None
    def convDiap( diap ):
        return re.sub( r"([a-z])\-([a-z])", repl, diap, flags=re.I )
    def repl( m ): # d-h -> defgh
        res = ""
        for i in range( ord( m.group(1) ), ord( m.group(2) )+1 ):
            res+= chr( i )
        return res
    char = char.replace( ".", "[a-z]" )
    char = convDiap( char )
    if re.fullmatch( "[a-z]", char, re.I ):
        result = set( [char] )
    elif re.fullmatch( r"\[[a-z]+\]", char, re.I ):
        result = set( char.replace( "[", "" ).replace( "]", "" ) )
    elif re.fullmatch( r"\[\^[a-z]+\]", char, re.I ):
        result = set( char.replace( "[", "" ).replace( "]", "" ).replace( "^", "" ) )
        result = fullABC - result
    return result

def unionDiaps( diaps ):
    # перебираем все варианты и делаем сеты конкретных символов в конкретных позициях
    result = [None]*len(diaps)
    for i in range( len(diaps) ): # перебор наборов вариантов
        sets = [ set() ] * allLen[i]
        for j in diaps[i]: # конкретные варианты
            chars = reCharsC.findall( j )
            for k in range( len(chars) ):
                sets[k] = sets[k].union( char2set( chars[k] ) )
        result[i] = sets
        #print( diaps[i], result[i] )
    return result

def intersectMapping( diaps ):
    for i in sota.maps:
        res = None
        text = ""
        for j in sota.maps[i]: # пересечения в соответствии с картой
            iRe  = sota.maps[i][j][0]
            iPos = sota.maps[i][j][1]
            text+= str( diaps[iRe][iPos] )+"\n"
            if res == None:
                res = diaps[iRe][iPos].copy()
            else:
                res = res & diaps[iRe][iPos]
        for j in sota.maps[i]: # записываем результат пересечений обратно 
            iRe  = sota.maps[i][j][0]
            iPos = sota.maps[i][j][1]
            if len( res ) ==0: print( diaps[iRe][iPos] )
            diaps[iRe][iPos] = res.copy()
        text+="inter: "+str(res)+"\n"
        #print( text )
        if len( res ) == 0:
            for j in sota.maps[i]: # записываем результат пересечений обратно 
                iRe  = sota.maps[i][j][0]
                iPos = sota.maps[i][j][1]
                print( "null set", iRe, iPos )
            print()
    return diaps

def filterDiaps( diaps, intersect ):
    changed = False
    for i in range( len(diaps) ):
        toDel = []
        for k in range( len( diaps[i] ) ):
            ch = reCharsC.findall( diaps[i][k] )
            mark = False
            for j in range( len( ch ) ):
                ls = "".join( list( intersect[i][j] ) )
                if not re.search( ch[j], ls, re.I ): mark = True
                #print( k, diaps[i][k], ch[j], ls, mark )
            if mark: toDel.append( k )
        if len( toDel ) > 0:
            changed = True
            toDel.reverse()
            for k in toDel: del diaps[i][k]
            #print( diaps[i], intersect[i] )
    return changed

def checkReBack( intersect, diaps ):
    for i in reBack:
        text = ""
        counter = 0
        sets = []
        maxs = []
        for j in intersect[i]:
            if len( j ) == 1:
                text+= list( j )[0]
            else:
                text+= "("+str(counter)+ ")"
                sets.append( list( j ) )
                maxs.append( len( j ) )
                counter+= 1

        iters = 1
        for j in maxs: iters*= j
        if iters>limitBack: continue # долго не значит, что поможет
        maxs.append( 0 )
        length = len( sets )
        counter = [0]*(length+2)
        label = 0
        iterCounter = 1
        result = []
        while counter[length] == 0:
            text2 = text
            for j in range( length ):
                text2= text2.replace( "("+str(j)+")", sets[j][ counter[j] ], 1 )
            if re.fullmatch( getAllRe()[i], text2, re.I ):
                result.append( text2 )

            counter[label]+= 1
            while counter[label] == maxs[label]:
                label+=1
                counter[label]+= 1
            while label>0:
                label-=1
                counter[label] = 0
            if iterCounter % 10000000 == 0:
                print( iterCounter )
            iterCounter+=1
        diaps[i] = result

fullABC = getFullABC()
print( fullABC )

t1 = time.time()
limitBack = 1000000000000 # к сожалению так
changed = True
count = 0
countUn = 0
while changed or countUn < 5:
    union = unionDiaps( res22 )
    intersect = intersectMapping( union )
    changed = filterDiaps( res22, intersect )
    if countUn  == 2:
        checkReBack( intersect, res22 )
    if not changed:
        countUn+=1
    else:
        countUn = 0
    count+= 1
    print( count )

for y in range( sota.d*2-1 ):
    for x in range( sota.d * 4 ):
        if y*4*sota.d+x in sota.maps.keys():
            val = sota.maps[ y*4*sota.d+x ][1]
            if len( intersect[val[0]][val[1]] ) == 1:
                print ( list( intersect[val[0]][val[1]])[0], end="" )
            else:
                print( "*", end="" )
        else:
            print( " ", end="" )
    print()

print( "\nTotal time:", time.time()-t1, "sec." )

Более детальное описание алгоритма


pincher1519

Не затрагивая детали перебора, лишь хранение структуры... Предлагаю ее описать через граф.

Каждая сота содержит ссылку на три соседние - В, СЗ, ЮЗ, по направлению регулярок. Сами регулярки содержат ссылку на соответствующую ей первую соту. От стартовой ячейки регулярки X отшагаем в нужном направлении Y раз и получим значение данной соты. Для операций с сотами будет достаточно следующих функций:

char   getCell(char direction, int regex, int position)//получить значение
char   setCell(char direction, int regex, int position)//установить значение
string getText(char direction, int regex)//получить текст для проверки


pincher1519

Насколько я вижу, используются три оси, на каждой из осей указываются 13 различных значений, то есть можно использовать трёхмерный массив с координатами [0..12, 0..12, 0..12], или [1..13, 1..13, 1..13], или даже [-6..+6, -6..+6, -6..+6], если Ваш язык позволяет отрицательные границы массивов.

При этом, поскольку координаты всё-таки двумерные, а не трёхмерные, любая третья координата зависит от двух остальных. Например, если координаты заданы диапазоном [0..12], то можно воспользоваться формулой x + y + z = 12. Заметим, что не для любой пары x и y от 0 до 12 существует значение z от 0 до 12.

licensed under cc by-sa 3.0 with attribution.