#массивы #алгоритм #регулярные_выражения #головоломка
Доброго времени суток!
вводная часть
Наткнулся на головоломку в интернете. Представлена таблица в виде шестиугольника.
Каждая строка его определена регулярным выражением. Регулярное выражение определяет
какие данные в указанной строке могут содержаться. Поломал весь свой мозг, решая данную
головоломку, не выходило никак решение. Головоломка построена по принципу японских
кроссвордов. Все бы ничего, но таблица - шестиугольник!...
Психанув - решил написать программу которая полным перебором найдёт те буквы, которые
должны быть в ячейках.
собственно вопрос
Как получать строки из шестиугольной таблицы? Ну и как лучше её представлять в массиве?
Ссылка на задачку http://habrahabr.ru
Заранее спасибо за ваши советы.
Ззыж решение не прошу. Хочу сам решить :-)
UPD:
Нашел для себя решение с точки зрения формирования массива. По сути это будет следующая
таблица:
---3-3-3---
--3-2-2-3--
-3-2-1-2-3-
--3-2-2-3--
---3-3-3---
Где "-" - это пустое значение... Осталось дело за малым, написать алгоритм обхода
таблицы относительно сторон шестиугольника. Но думаю, это уже дело техники, раз идея
формирования таблицы придумана...
Может у кого лучше идея есть, по хранению данных, чтобы удобно их было анализировать?
Ответы
Ответ 1
Я немного соврал 3 года назад. Задача решается примерно за 20 минут. Я опишу только сам алгоритм, за ним будет следовать куча некрасивого кода почти без комментариев. Актуальный, полностью переработанный код с улучшениями и багфиксами можно найти на ГитХабе: https://github.com/ReinRaus/RegexCrossTool Итак, алгоритм: Проходим по всем регулярным выражениям и находим все конкретные символы в них. Это символьные классы [a-z] и одиночные символы abc. Игнорируем . и [^a-z]. Логика простая: если кроссворд имеет единственное решение, то все символы решения заданы конкретными классами, не отрицанием и не точкой. Полученный список символов используется для создания потом класса . и отрицания. Проходим по всем регулярным выражениям и находим в них символьные классы и одиночные символы r"\[\^?[a-z]+\]|[a-z]|\.", здесь нет поддержки метасимволов \w\d и.т.п. и символов кроме a-z, но это не сложно добавить, если сильно хочется. В данном кроссворде их нет. Пункт 2 выполняет функция getEntitys( regex ) Делаем замену найденных последовательностей на их экранированное представление с оберткой в несохраняющую группу. То есть вместо [^d-f] мы будем искать (?:[\[^d\-f\]) и в полном переборе будут фигурировать классы символов, а не конкретные символы Делаем полный перебор символьных классов в соответствии с длиной. checkEnt( entity, length ). Это означает выражение [a-z]?x?.* при длине 3 будет представлено массивом [ "[a-z]x.", "x..", "[a-z]..", "..." ] Это все возможные варианты для данного выражения в символьных классах. Оптимизация. Выражение #32 будет рассчитываться около 40 часов, поэтому была написана оптимизация для него. Общее время сократилось до 15 минут. Меня это устраивает, но за это время начал писать вторую оптимизацию, потом закомментировал. Может кому интересно. Результат работы пункта 4 сохраняем на жесткий диск. Нет смысла считать все это каждый раз. Создаем карту доски. Если интересно - Карта гексагональной доски Объединение. Проходим по результатам работы и создаем список символов, которые возможны для регулярного выражения в конкретных позициях. Это достигается объединением сетов полученных из преобразования символьных классов в сеты char2set( char ) Пересечение. Проходим по карте и находим пересечения сетов для каждой позиции поля кроссворда Фильтрация Фильтруем массив результата пункта 4 в соответствии с результатами пересечения, убираем те варианты из полного перебора, которые не соответствуют регулярным выражениям в той же ячейке кроссворда Делаем все снова начиная с пункта 7, пока фильтрация приносит плоды. Если фильтрация не сделала изменений, то данный алгоритм сделал все, что мог. Запускаем полный перебор для регулярных выражений, которые содержат обратные ссылки, потому что эти регулярные выражения раскрывались неэффективно. (.)\1* раскроется в ...... к примеру для длины 6 Оставляем только подходящие значения из полного перебора. Для успокоения души еще пару раз делаем пункты 7-10 Выводим результат Результат: 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"(?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." ) Более детальное описание алгоритмаОтвет 2
Не затрагивая детали перебора, лишь хранение структуры... Предлагаю ее описать через граф. Каждая сота содержит ссылку на три соседние - В, СЗ, ЮЗ, по направлению регулярок. Сами регулярки содержат ссылку на соответствующую ей первую соту. От стартовой ячейки регулярки X отшагаем в нужном направлении Y раз и получим значение данной соты. Для операций с сотами будет достаточно следующих функций: char getCell(char direction, int regex, int position)//получить значение char setCell(char direction, int regex, int position)//установить значение string getText(char direction, int regex)//получить текст для проверкиОтвет 3
Насколько я вижу, используются три оси, на каждой из осей указываются 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.
Комментариев нет:
Отправить комментарий