Это Fortnightly Challenge # 6 . Тема: Языковой дизайн

Есть чат для этой задачи. Присоединяйтесь к нам, если вы хотите обсудить идеи!

А сейчас нечто соверешнно другое...

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

Соревнование

Вы должны разработать язык сопоставления с образцом, который позволяет описывать двумерные узоры в блоках текста. Режим работы вашего языка будет похож на регулярные выражения (хотя ваш язык не должен иметь ничего общего с регулярным выражением иначе):

• В качестве ввода вы получите прямоугольный блок текста. Можно предположить, что текст состоит только из печатаемых символов ASCII (от 0x20 до 0x7E), а также из новых строк (0x0A) для разделения строк сетки.
• Если в соответствии с описанием шаблона можно найти совпадение как любое подмножество этого блока текста, это совпадение должно быть возвращено или напечатано. Если совпадение может быть не прямоугольным, оно должно быть дополнено прямоугольной областью с некоторым зарезервированным символом. Если имеется несколько действительных совпадений, вы можете решить, как выбрать возвращаемое совпадение (наибольшее, наименьшее, первое и т. Д.).

Для некоторых приложений может быть полезно, если ваша реализация может возвращать позицию соответствия вместо самого соответствия, но это не является обязательным требованием.

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

Ваш ответ должен содержать:

• Описание языка.
• Рабочая реализация . Это может быть программа или набор функций / классов на выбранном вами языке.
• Вы должны продемонстрировать свой язык, показав, как его можно использовать для решения приведенных ниже примеров . Ваш язык не обязательно должен соответствовать всем, но вы должны соответствовать как минимум 8 из них. Если ваш язык может сделать что-то необычное, о чем мы не подумали, не стесняйтесь включать это.

Если ваш ответ основан на существующих идеях, это нормально, но, пожалуйста, отметьте, где это необходимо.

расширения

Выше описан минимум, которому должна удовлетворять действительная заявка. Однако некоторые обобщения могут сделать такой язык сопоставления с образцом еще более полезным, включая, но не ограничиваясь:

• Возможность привязать шаблон к одному или нескольким ребрам, чтобы можно было проверить, имеет ли вся входная область определенный шаблон.
• Производить все матчи вместо одного. Вы можете выбрать семантику перекрывающихся совпадений.
• Принимая непрямоугольный текст в качестве ввода.
• Позволяет шаблонам указывать непрямоугольные совпадения. В таком случае вывод должен быть дополнен прямоугольником с некоторым зарезервированным символом.
• Позволяет шаблонам указывать совпадения с отверстиями.
• Разрешение несмежных совпадений, например, двух символов с определенным смещением.
• Легкая спецификация вращений и отражений.
• При желании циклически обрабатывать ввод как цилиндр или тор, так что противоположные края считаются смежными.

счет

Основная цель этой задачи состоит в том, чтобы создать эффективный язык сопоставления с образцом 2D, который потенциально может быть использован в будущем. Таким образом, система подсчета очков, такая как «кратчайшая объединенная длина для решения примеров», приведет к жесткому кодированию определенных функций за счет общего удобства использования. Поэтому мы решили, что этот вызов лучше всего проводить как конкурс популярности. Представление с большинством чистых голосов выигрывает. Хотя мы не можем заставить людей голосовать, вот несколько рекомендаций о том, что избиратели должны в идеале искать:

• Выразительность. Может ли язык решить множество проблем, даже помимо примеров, представленных в этом вопросе? Поддерживает ли он какие-либо из предложенных расширений?
• Читаемость. Насколько интуитивно понятна запись (по крайней мере, для людей, которые знают основной синтаксис)?
• Golfitude. Это все еще CodeGolf.SE. Для целей этого сайта, конечно, было бы неплохо иметь соответствующий язык, которому требуется совсем немного кода для описания шаблона.

Примеры задач

В следующем фрагменте стека показано 16 примеров проблем, с которыми мог бы справиться двумерный язык сопоставления с образцом. Каждый пример содержит краткое описание проблемы и затем обычно сопровождается одним входным примером, где может быть найдено совпадение, и одним примером, где не может быть найдено совпадение (если применимо).

Как указано выше, ваш язык должен быть в состоянии решить 8 из этих проблем. Все это необязательно, но, конечно, должно увеличить количество голосов, которые вы получаете.

body{font-family:'Helvetica Neue',Arial,sans-serif;color:#444;font-size:13px;width:500px;line-height:1.3}h3{font-size:16px!important;line-height:1.2em!important;margin-bottom:1.2em}code{white-space:pre-wrap;padding:1px 5px;font-family:'Droid Sans Mono',Consolas,Menlo,Monaco,Lucida Console,Liberation Mono,DejaVu Sans Mono,Bitstream Vera Sans Mono,Courier New,monospace,serif;color:#222;background:#eee}p code{padding:1px 5px}pre{overflow:auto;width:auto;width:480px !ie7;max-height:600px;font-family:'Droid Sans Mono',Consolas,Menlo,Monaco,Lucida Console,Liberation Mono,DejaVu Sans Mono,Bitstream Vera Sans Mono,Courier New,monospace,serif;margin-bottom:10px;padding:5px;background:#eee;border-left:2px dotted #ccc;font-size:12px}pre code{white-space:inherit;padding:0;background:0 0}

<h3>Problem 1 - Finding Chessboards</h3><p>Match any rectangular subregion, at least 3 columns wide and 3 rows tall, which consists of alternating <code>#</code> and <code>_</code>. The top left corner may be either of those two characters.</p><p><strong>Match</strong></p><pre><code>~______~&#10;~##_#_#~&#10;~#_#_##~&#10;~##_#_#~&#10;~______~&#10;</code></pre><p>(There's an alternating 4x3 region in the centre. The match could be either that or either of its two 3x3 subregions.)</p><p><strong>No match</strong></p><pre><code>#_##&#10;_#_#&#10;__#_&#10;#_#_&#10;#_#_&#10;</code></pre><p>(Contains two 3x2 regions, but no alternating 3x3 region.)</p><h3>Problem 2 - Verifying Chessboards</h3><p>Match the entire input, provided all of it consists of alternating <code>#</code> and <code>_</code>. It may start with either of those two characters.</p><p><strong>Match</strong></p><pre><code>_#_#_#_#&#10;#_#_#_#_&#10;_#_#_#_#&#10;</code></pre><p><strong>No match</strong></p><pre><code>_#_#_#__&#10;__#_#_#_&#10;_#_#_#__&#10;</code></pre><h3>Problem 3 - Detect a Rectangle of Digits</h3><p>Match a rectangle (at least 2x2) consisting only of digits and no other characters.</p><p><strong>Match</strong></p><pre><code>hbrewvgr&#10;18774gwe&#10;84502vgv&#10;19844f22&#10;crfegc77&#10;</code></pre><p>You should match either the 5 wide by 3 tall rectangle (or any subset thereof) or the 2 by 2 rectangle.</p><p><strong>No Match</strong></p><pre><code>uv88wn000&#10;vgr88vg0w&#10;v888wrvg7&#10;vvg88wv77&#10;</code></pre><p>There are no rectangles of digits.</p><h3>Problem 4 - Finding a Word in a Word Search</h3><p>Match the smallest rectangular region containing containing the word "GOLF" in any orientation (horizontal, vertical, diagonal, forwards or backwards). If your language supports non-rectangular matches, you may also match diagonal words without the surrounding rectangle.</p><p><strong>Match</strong></p><pre><code>INOWCEF&#10;IFWNOPH&#10;VULUHGY&#10;GUYOIGI&#10;YTFUGYG&#10;FTGYIOO&#10;</code></pre><p>"GOLF" is found backwards along an upper-left to bottom-right diagonal. This is the region containing it:</p><pre><code>FWNO&#10;ULUH&#10;UYOI&#10;TFUG&#10;</code></pre><p><strong>No Match</strong></p><pre><code>BHTGIVUHSR&#10;BWEVYWHBWB&#10;BHTWBYTWYB&#10;</code></pre><p>("GOLF" cannot be found anywhere.)</p><h3>Problem 5 - Detect Square Inputs</h3><p>Match the entire input if it is a square block of characters.</p><p><strong>Match</strong></p><pre><code>qwerty&#10;asdfgh&#10;zx vbn&#10;uiop[]&#10;`1234 &#10;67890-&#10;</code></pre><p>There are six lines, each of which contains six characters, even though two characters are spaces.</p><p><strong>No Match</strong></p><pre><code>   hello&#10;   world&#10;</code></pre><p>The two lines don't each contain two characters.</p><h3>Problem 6 - Find Gliders in a Game of Life</h3><p>In Conway's <a href=http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life rel=nofollow>Game of Life</a> one of the most popular and simple patterns is the <a href=http://www.conwaylife.com/wiki/Glider rel=nofollow>glider</a>. There are two different stages in a glider's life cycle:</p><pre><code>##         ##&#10;# #  and  ##&#10;#           #&#10;</code></pre><p>Of course, the Game of Life is invariant under rotation and reflection, so in total there are 16 different shapes which resemble a glider at some stage.</p><p>Given input consisting only of <code>#</code> and spaces, match a 3x3 block containing a glider in any orientation. Spaces are significant! (Due to the conditions in the surrounding 5x5 layer, these matches might not be actual gliders, but don't worry about that.)</p><p><strong>Match</strong></p><pre><code>##   #  &#10;  # ##  &#10;#   # # &#10;# #     &#10;##   ###&#10;   # #  &#10; #    # &#10;</code></pre><p>This contains three gliders - top right corner, bottom right corner and left centre.</p><p><strong>No match</strong></p><pre><code>##   # &#10;  # ###&#10;##  # #&#10;# #    &#10;##  ###&#10;</code></pre><h3>Problem 7 - Match Nether Portals</h3><p>Based on <a href=http://codegolf.stackexchange.com/questions/45488/nether-portal-detection>this challenge</a> by Calvin's Hobbies.</p><p>In the game of Minecraft, players can construct inter-dimensional portals using blocks of obsidian arranged into a rectangular frame. Given a 2D slice of the world, match a Nether portal. A valid Nether portal is a rectangle of empty space (<code>.</code>) surrounded on all sides by obsidian (<code>X</code>). The rectangle of space can be from 2 wide by 3 tall to 22 wide by 22 tall. Corners don't matter.</p><p><strong>Match</strong></p><pre><code>....X......&#10;.XXXXXX.XX.&#10;...X...X...&#10;.X.X...XXX.&#10;...X...X.X.&#10;.XXX...X.X.&#10;X..XXXXX.X.&#10;</code></pre><p>This is a 3 wide by 4 tall portal.</p><p><strong>No Match</strong></p><pre><code>XX..XXXX&#10;XX..X..X&#10;XX..X..X&#10;..X.X..X&#10;.X..X.XX&#10;</code></pre><p>This is almost a 2 wide by 3 tall portal, but one obsidian block is missing from the bottom.</p><h3>Problem 8 - Minecraft Chest Placement</h3><p>Based on <a href=http://codegolf.stackexchange.com/q/45720/8478>this challenge</a> by Calvin's Hobbies.</p><p>For this problem, returning the position of the match might be more useful than returning the actual match. "Adjacent" refers only to neighbours in four orthogonal directions. You're given a grid of <code>.</code> (empty cell) and <code>C</code> (chest). Two adjacent chests are considered a "double chest". You should match valid positions for placing additional chests. An empty cell is valid as long as it not adjacent to a double chest or two normal chests. Taking the example from the linked challenge, if the input is</p><pre><code>.......C..&#10;...C..C...&#10;.........C&#10;.CC...CC..&#10;..........&#10;</code></pre><p>the pattern should match the cell marked by <code>*</code> in the following grid:</p><pre><code>******.C**&#10;***C**C.**&#10;*..***..*C&#10;.CC.*.CC.*&#10;*..***..**&#10;</code></pre><h3>Problem 9 - Horizontal and Vertical Alignment</h3><p>Match a part of a column or row if it contains two or more <code>#</code> characters. As an extension, you could return the index of the column or row. If your language supports non-contiguous matches, match <em>only</em> the two <code>#</code>, not the row/column in between.</p><p><strong>Match</strong></p><pre><code>.,.,.,.#.,&#10;,.,#,.,.,.&#10;.,.,.,.,.,&#10;,.,.,.,.,.&#10;.,.#.,##.,&#10;,.,.,.,.,.&#10;</code></pre><p>There are 5 possible matches, three horizontal or two vertical. The horizontal matches are <code>#.,#</code>, <code>##</code>, and <code>#.,##</code>. The vertical matches are <code>#,.#</code> and <code>#.,.#</code>. The language can match any one or more of those.</p><p><strong>No Match</strong></p><pre><code>.,.#.,.,&#10;,.,.,.#.&#10;.,#,.,.,&#10;,.,.,.,#&#10;.#.,.,.,&#10;,.,.#.,.&#10;#,.,.,.,&#10;,.,.,#,.&#10;</code></pre><p>This is also a solution to the Eight Queens problem.</p><h3>Problem 10 - Collinear Points</h3><p>Match a set of three <code>#</code>s that are in a straight line, which can have any orientation, not necessarily horizontal or vertical (i.e. it could be diagonal are long knight's move steps). If your language supports non-contiguous matches, match <em>only</em> the three <code>#</code>, not the characters in between.</p><p><strong>Match</strong></p><pre><code>........&#10;#..#..#.&#10;...#....&#10;#.......&#10;...#....&#10;</code></pre><p>There are three possible matches. They are: the second row, the fourth column, and a diagonal line across 7 columns and 3 rows.</p><p><strong>No Match</strong></p><pre><code>.#..#&#10;#..#.&#10;#....&#10;..#.#&#10;</code></pre><p>There are no collinear <code>#</code>s in this input.</p><h3>Problem 11 - Verify Prelude Syntax</h3><p><a href=http://esolangs.org/wiki/Prelude rel=nofollow>Prelude</a> is an esoteric language, which has very few, but unusual, restrictions on what constitutes a valid program. Any block of printable ASCII text is valid provided that:</p><ul><li>Every column of text contains at most one of <code>(</code> and <code>)</code>.</li><li>Ignoring their vertical position, the <code>(</code> and <code>)</code> are balanced. Each <code>(</code> and be paired with exactly one <code>)</code> to the right of it, and vice-versa.</li></ul><p>The pattern should match any valid Prelude program and fail to match invalid programs.</p><p><strong>Match</strong></p><pre><code>?1-(v  #1)-             &#10;1   0v ^(#    0)(1+0)#)!&#10;    (#)  ^#1-(0 #       &#10;</code></pre><p><strong>No match</strong></p><pre><code>#(#(##)##)##(&#10;)##(##(##)#)#&#10;</code></pre><p>For more examples, see <a href=http://codegolf.stackexchange.com/q/47239/8478>this challenge</a>.</p><h3>Problem 12 - Avoid the Letter Q</h3><p>Match any 4x4 square of characters that does not contain the letter <code>Q</code> or <code>q</code>.</p><p><strong>Match</strong></p><pre><code>bhtklkwt&#10;qlwQklqw&#10;vtvlwktv&#10;kQtwkvkl&#10;vtwlkvQk&#10;vnvevwvx&#10;</code></pre><p>There is one 4x4 square that does not contain any Qs. This is</p><pre><code>vlwk&#10;twkv&#10;wlkv&#10;vevw&#10;</code></pre><p><strong>No Match</strong></p><pre><code>zxvcmn&#10;xcvncn&#10;mnQxcv&#10;xcvmnx&#10;azvmne&#10;</code></pre><p>The single <code>Q</code> in the center prevents any matches from being formed.</p><h3>Problem 13 - Diamond Mining</h3><p>Locate a diamond in a field of characters. Diamonds are rotated squares formed by the characters <code>/\X</code>. Each corner of the diamond is formed by an <code>X</code>, and the corners are connected in lines formed by <code>\</code> or <code>/</code>, where each side is the same length. A diamond of size 0 has no <code>/\</code> sides. As an extension, you can return all of the diamonds in the field, return only the diamond's characters, and/or return the size of the diamond found.</p><p><strong>Match</strong></p><pre><code>...X......X....&#10;../.\..../.\...&#10;./.X.\..X...X..&#10;X.X.X.XX.\./.\.&#10;.\.X.//.\.X...X&#10;..\./X...X.\./.&#10;.X.X..\./...X..&#10;X.X....X.......&#10;.X.............&#10;</code></pre><p>There are 6 different diamonds in this field. Two are size 0, three are size 1, and one is size 2. Notice how diamonds can overlap parts or nest.  You should be able to match diamonds of any size up to a reasonably high limit.</p><p><strong>No Match</strong></p><pre><code>.X......./....&#10;.\....X.......&#10;...X.\.\...X..&#10;..X.\...\.X.\.&#10;...X.X...X.\.X&#10;../X\...\...X.&#10;.X...\.\..X...&#10;..\./.X....X..&#10;...X..../.....&#10;</code></pre><p>No diamonds are found here.</p><h3>Problem 14 - Matching Crosses</h3><p>We'll define a cross as a rectangular region, which has been sliced into a (not necessarily regular) grid of 3x3 subregions. The four corner regions are filled with <code>.</code> whereas the other five regions are filled with <code>#</code>.</p><p><strong>Match</strong></p><pre><code>.......&#10;.###...&#10;######.&#10;######.&#10;.###...&#10;.###...&#10;.###.#.&#10;....###&#10;.....#.&#10;</code></pre><p>There is the small cross in the lower right corner, and the large cross yields 5 potential matches: the top and left arms will always have length 1, but the right and bottom arms can each either have length 1 or 2 - in addition the bottom arm can have length 3 if the right arm has length 1. Note that the full large cross cannot be matched because the top of the small cross would protrude into the lower right region.</p><p><strong>No Match</strong></p><pre><code>.######.&#10;...##...&#10;...##...&#10;........&#10;</code></pre><p>Each arm must have length of at least 1.</p><h3>Problem 15 - Match a Word in a Boggle Board</h3><p><a href=http://en.wikipedia.org/wiki/Boggle rel=nofollow>Boggle</a> is a bit like a word search, except that you change direction after each letter. Given a block of text, if it contains the word <code>panama</code> (<em>case-insensitive!</em>) according to the Boggle rules, match the smallest rectangle containing it. You may decide whether single letters can be reused or not. If your language can handle both, show it off! If you allow letters to be reused you can also choose if a letter can be used twice in a row (i.e. whether staying on the same cell is a valid move). If your language supports non-rectangular matches, match <em>only</em> the word.</p><p><strong>Match without reusing letters</strong></p><pre><code>EmYPhNuy&#10;AaaKVsjL&#10;onlGviCw&#10;DdOgFrRn&#10;ISeHZmqc&#10;zMUkBGJQ&#10;</code></pre><p>(There's a snaking <code>panamA</code> or <code>panAma</code> towards the upper left corner, depending on the order it's matched in.)</p><p><strong>Match with reusing letters</strong></p><pre><code>ExYPhNuy&#10;AfEKVsjL&#10;oblGviCw&#10;DdOgArRn&#10;ISepnmqc&#10;zMUkBGJQ&#10;</code></pre><p>(There's a <code>pAnAmA</code> towards the lower right corner, where all three <code>A</code> are the same.)</p><p><strong>No Match</strong></p><pre><code>BpbrzTHY&#10;mAJVRLuF&#10;jyXSPknK&#10;hoeGcsEl&#10;QCZagNMI&#10;dvUOqixt&#10;</code></pre><h3>Problem 16 - Wrap around the Edges</h3><p>Match a rectangle of <code>#</code>, at 3x3 in size, which may wrap around the edges of the input.</p><p><strong>Match</strong></p><pre><code>#..##&#10;#..##&#10;.....&#10;#..##&#10;</code></pre><p>(The 9 <code>#</code> form exactly one 3x3 region if you consider the edges to be adjacent.)</p><p><strong>No Match</strong></p><pre><code>...##&#10;#..##&#10;#..##&#10;#..#.&#10;</code></pre>&#10;

(Нет, вам не нужно читать этот HTML-код. Нажмите кнопку «Выполнить фрагмент кода», чтобы он был аккуратно отображен вашим браузером, который затем вы также можете просмотреть в полноэкранном режиме.)

SnakeEx

Решает 15/16 проблем до сих пор!

Онлайн переводчик ! - Полная спецификация языка - Javascript Source

Идея этого языка состоит в том, чтобы определить «змей», которые перемещаются по тексту, проверяя символы, используя синтаксис, подобный регулярному выражению.

Программа в SnakeEx состоит из списка определений для змей, использующих различные последовательности команд. Змеи могут порождать других змей, используя эти определения, и именно здесь SnakeEx получает большую часть своей мощности - мы можем сопоставлять ветвящиеся структуры и даже делать рекурсию (см. Пример Paren Matching).

Каждая программа по сути будет выглядеть как набор регулярных выражений, но с добавлением команд направления формы, <dir>которые изменяют направление змеи, и вызова команд формы, {label<dir>params}которые порождают больше змей.

Для точки входа интерпретатор порождает одну змею, используя первое определение, двигаясь вправо.

Это не очень кратко, но очень мощно и (я думаю) довольно читабельно.

Обновления

• Поменял! не логично и ~ не отмечать совпадения
• Добавлено <!>для решения коллинеарного
• Решенные Соответствующие Кресты
• Решил шахматные доски менее страшным способом
• Добавлен синтаксис ограниченного закрытия %{min,max}
• Добавлен пример рекурсии

Решения

15 решено, 1 в процессе

Вы можете легко опробовать эти программы с помощью онлайн-переводчика, указанного выше!

Проблема 1 - Поиск шахматных досок

m:{v<R>2}{h<>1}
v:{c<L>A1}+
h:{c<R>A2}+
c:_?(#_)+#?

Для подробного ознакомления начните с Задачи 3.

Проблема 2 - Проверка шахматных досок

m:{v<R>2}{h<>1}
v:${c<L>A1}+$
h:${c<R>A2}+$
c:$_?(#_)+#?$

Завершение книги соответствующими змеями с символом «за пределами» $- один из способов заставить программу соответствовать только всему вводу.

Проблема 3 - Определить прямоугольник цифр

m:{c<R>A1}%{2,}
c:[0-9]%{2,}

В mзмее двигается прямо, порождая на минимум 2 змея ( %{2,}это замыкание означает «2 в бесконечность») , используя определение с ( c) и перемещением вправо ( <R>), или , вернее , вниз в данном случае, поскольку все направления по отношению к текущей змеи. Параметр A- сахар, который просто указывает, что нерестовая змея должна двигаться после вызова. 1Параметр , как мы ограничиваем совпадение прямоугольников - число параметры ставит змей «группа». Матч не засчитывается, если все змеи в одной группе не проходят одно и то же расстояние.

Задача 4 - Поиск слова в поиске слов

m:<*>GOLF

Команда направления <*>указывает, что змея должна поворачиваться в любом диагональном или ортогональном направлении. Затем он ищет простое регулярное выражение.

Задача 5 - Определить квадратные входы

m:{v<R>1}{h<>1}
v:${c<L>A1}+$
h:${c<R>A1}+$
c:$.+$

Ключ здесь - специальный символ $, который соответствует, только если змея выходит за пределы. Мы порождаем горизонтальную змею и вертикальную; каждый из них порождает больше змей, поскольку он проходит вдоль края, и все они находятся в одной группе и должны иметь одинаковую длину.

Задача 6 - Найти планеры в игре жизни

m:<+>[({l1<R>A}{l2<R>A}{l3<R>})({l1<L>A}{l2<L>A}{l3<L>})]
l1:##\.
l2:[(#\.)(\.#)]#
l3:#\.\.

mначинается в любом из четырех ортогональных направлений ( <+>), достигая поворота. Затем он выглядит влево или вправо для трех рядов по порядку, достигая отражения.

(Обратите внимание, что я заменил пробелы точками только потому, что текстовые области HTML, используемые в моем интерпретаторе, кажутся глупыми, если в них несколько пробелов подряд)

Задача 7 - Подходим порталы Пустоты

m:{e<R>A1}{d<R>A1}%{2,22}{e<R>1}
e:~.X%{3,22}~.
d:X\.+X

В mзмее двигается прямо, порождая змею , чтобы проверить левый край, 2-22 змея , чтобы проверить средние колонны, и , наконец , змею , чтобы проверить правый край. ~Оператор указывает на то, что все , что следует должны быть проверены , но не должны быть помечены как часть решения.

Ограниченные замыкания теперь позволяют нам полностью и правильно решить эту проблему!

Задача 8 - Размещение сундуков Minecraft

m:~{s<>}~!{d<+>}\.
s:<+>.<BR>([$\.]<R>)%{3}
d:.<+>CC

Здесь мы используем логический not ( !), который соответствует тогда и только тогда, когда следующий токен ничего не соответствует. Объявление dобнаруживает двойной сундук в определенном направлении, поэтому !{d<+>}убедитесь, что в любом ортогональном направлении нет двойных сундуков. sперемещается в маленький ромб вокруг текущего квадрата, проверяя, что по крайней мере 3 из этих мест либо пустые, либо находятся вне поля. Трейлинг, \.наконец, соответствует квадрату, предполагая, что все предыдущие условия выполнены.

Задача 9 - Горизонтальное и вертикальное выравнивание

m:<R>?#~.*#

Змея mможет повернуть направо ( <R>?) перед соответствием последовательности. .подстановочный знак, как в регулярных выражениях.

Задача 10 - Коллинеарные точки

m:<!>#~.*#~.*#

С добавлением <!>направления, мы можем решить это сейчас! <!>это как, <+>но вместо того, чтобы разветвляться в четырех направлениях, оно разветвляется во всех возможных направлениях.

Задача 12 - Избегайте буквы Q

m:{h<R>A}%{4}
h:[^Qq]%{4}

Просто порождает 4 змей, каждый из которых ищет четыре символа, которые не являются буквой Q.

Задача 13 - Алмазодобыча

m:{tl<RB>1}{tr<RF>1}
tl:X/*{bl<L>1}X
tr:X\\*{br<R>1}X
bl:X\\*X
br:X/*X

Это довольно опрятно. mпорождает двух змей, одна идет спиной направо, а другая - вперед. Каждый из них следует за косой чертой к X, затем порождает другую змею под прямым углом к ​​ее текущему направлению, которое следует за косой чертой к нижней X.

Задача 14 - Соответствие крестов

m:{a<R>A}+{b<R>A}+{a<R>A}+
a:{e<>P1}{c<>P2}{e<>P3}
b:{c<>P1}{c<>P2}{c<>P3}
e:\.+
c:#+

Вот первый раз, когда я использовал Pпараметр iggyback. Обычно змеи независимы, но если вы делаете вызов с этим параметром, вызывающая змея будет перемещаться вместе с вызываемым абонентом. Поэтому e2можно проверить последовательность «.», Затем последовательность «#», затем другую последовательность «.», И сделать так, чтобы они были отдельными вызовами, чтобы мы могли сгруппировать их с «1», «2» и «3». , заставляя их длины совпадать.

Задача 15 - Подберите слово на доске

m{I}:<*>p<*>a<*>n<*>a<*>m<*>a

Просто, если многословно. IПараметр указывает нечувствительность к регистру (мы можем указать параметры как в определениях, так и в вызовах). Змея поворачивается в любом направлении, соответствует персонажу, снова поворачивается и так далее.

m{EI}:<*>p<*>a<*>n<*>a<*>m<*>a

Это версия без повторного использования символов. Параметр Exclusive запрещает змее сопоставлять любые символы, которые уже были отмечены, так же, как следы слизи feersum.

Задача 16 - Обернуть края

m{W}:{c<R>WA}%{3}
c:###

WПараметр позволяет змею обертке , когда он работает вне границ. У нас также есть Hи Vразрешить только горизонтальную или вертикальную упаковку.

Extra - Maze Solver

m{E}:$(<P>\.)+$

Решает лабиринт ASCII, где пройденный этаж - периоды. В <P>означает направление вперед, влево или вправо (сахар для [<F><L><R>]).

Extra - Paren Matching

m:\(~{r<>P}\)
r:[^\(\)]*(\({r<>P}\))?[^\(\)]*

Еще не выяснили, как делать прелюдию, но вот первый шаг! Здесь я использую rзмею рекурсивно, чтобы сопоставить соответствующие скобки, проверяя, нет ли между ними непревзойденных скобок.

Extra - ASCII Topology: подсчет циклов

Slip, Python 3.4 ( Github wiki , онлайн-переводчик )

Как и в представлении feersum, оно также основано на обходе сетки, но, как и в представлении CarpetPython, оно основано на регулярных выражениях. Как-то похоже, что мне удалось занять золотую середину.

Есть довольно много нереализованных функций, которые я хочу добавить, поэтому, где это уместно, я отмечал, что я собираюсь делать, когда у меня будет время.

Обновления

(См. Страницу Github для подробных новостей)

• 5 апреля 2015 : теперь у Slip есть онлайн-переводчик ! Это все еще на ранних стадиях, поэтому может быть несколько ошибок.

• 5 апреля 2015 : обновление эффективности! Теперь порталы нижнего уровня намного быстрее (2 с). Также было несколько изменений синтаксиса, так что не забудьте проверить вики. Групповая нумерация также исправлена.

У скольжения есть указатель совпадения, который начинается с определенного квадрата и первоначально направлен вправо. Когда сопоставляется символ, указатель перемещается вперед в текущем направлении (хотя реализация не делает вещи точно в этом порядке).

Направление указателя матча может быть установлено в определенное направление с ^<digit>, где ^0, ^1, ^2..., ^7установить указатель на N, NE, E, ..., NW соответственно (идет по часовой стрелке).

Также доступны следующие ярлыки:

• ^* проверяет все 8 ортогональных или диагональных направлений,
• ^+ проверяет все 4 ортогональных направления.

(План на будущее: разрешить установку произвольных направлений, например, (1, 2)для движения рыцаря)

Например ( Задача 4 - Поиск слова в поиске слова ),

^*GOLF

пробует все 8 ортогональных или диагональных направлений, ища слово «ГОЛЬФ». По умолчанию Slip пробует все возможные начальные квадраты и возвращает по одному результату от каждого, отфильтровывая дубликаты, поэтому сетка похожа на

GOLF
O
L
FLOG

возвращает только верхнюю и нижнюю строки как совпадающие (поскольку верхняя строка и левый столбец «ГОЛЬФ» начинаются с одного квадрата). Чтобы получить все совпадения, oможно использовать режим совпадения совпадений.

Аналогично ( задача 15 - сопоставить слово на доске Boggle ),

p^*a^*n^*a^*m^*a

спички panama, пытаясь в другом направлении каждый раз. Используйте iфлаг для нечувствительности к регистру. Slip по умолчанию использует символы, но это можно переключить с помощью rфлага no-repeat.

(План на будущее: модификатор режима поиска, который автоматически проверяет наборы направлений после каждого перемещения, поэтому повторение ^*не требуется)

Направление указателя Спичечного также может быть повернуты на 90 градусов влево или вправо с <или >соответственно. Например,

 `#`#< `#<  <`#<`#

ищет шаблон

  #
## 
 ##

глядя в следующем порядке:

765
894
123

Это позволяет нам решить проблему 6 - Найти планеры с

^+(`#`# >`# > `#>`#> |`#`# <`# < `#<`#< | `#`#> `#>  >`#>`#| `#`#< `#<  <`#<`#)

где части 1 и 2 кодируют формы планера, а части 3 и 4 кодируют их отраженные аналоги.

Обратите внимание, что Slip использует backtick `для экранирования. Это потому, что у Slip есть другая форма движения, которая дает языку его имя - команда slip. /скользит указатель совпадения ортогонально влево, а \указатель совпадения ортогонально вправо.

Например,

abc   ghi
   def

может быть сопоставлено abc\def/ghi.

Хотя это не особенно полезно само по себе, проскальзывание становится более важным в сочетании со (?| <regex> )стационарной группой, которая действует как подходящая перспектива. Регулярное выражение внутри сопоставляется, затем в конце его положение и направление указателя совпадения сбрасываются в состояние перед стационарной группой.

Например,

abc
def
ghi

может быть сопоставлено с (?|abc)\(?|def)\(?|ghi).

Точно так же проблема 12 - Избегайте буквы Q можно решить с помощью

%(\(?|[^qQ]{4})){4}

где %- команда отсутствия скольжения, чтобы остановить \активацию первого .

Slip также имеет утверждение длины (?_(<group num>) <regex> ), которое соответствует регулярному выражению внутри, только если его длина совпадения равна длине данной группы num.

Например, проблема 13 - добыча алмазов может быть легко решена с помощью

^1X(`/*)X>(?_(1)`\*)X>(?_(1)`/*)X>(?_(1)`\*)

который сначала пытается соответствовать верхней левой стороне алмаза, а затем утверждает, что остальные три стороны имеют одинаковую длину.

(Запуск с vфлагом для подробного вывода)

Match found in rectangle: (8, 0), (12, 4)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (0, 0), (6, 6)
   X
  / \
 /   \
X     X
 \   /
  \ /
   X

Match found in rectangle: (2, 2), (4, 4)
 X
X X
 X

Match found in rectangle: (10, 2), (14, 6)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (5, 3), (9, 7)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (0, 6), (2, 8)
 X
X X
 X

Гольф-альтернатива

^1X(`/*)(X>(?_(1)`\*)X>(?_(1)`/*)){2}

который соответствует первой стороне дважды.

Многие другие проблемы могут быть решены с помощью проскальзывания, стационарных групп и утверждений длины:

Задача 14 - Соответствие крестов:

(?|(`.+)(`#+)(`.+))(\(?|(?_(2)`.+)(?_(3)`#+)(?_(4)`.+)))*(\(?|(?_(2)`#+)(?_(3)`#+)(?_(4)`#+)))+(\(?|(?_(2)`.+)(?_(3)`#+)(?_(4)`.+)))+

Как только вы фиксируете ширину .s и #s в первом ряду, он просто сползает вниз.

Выход:

Match found in rectangle: (0, 1), (5, 5)
.###..
######
######
.###..
.###..

Match found in rectangle: (4, 6), (6, 8)
.#.
###
.#.

Этот, вероятно, можно сыграть в гольф с небольшой рекурсией, как только я разберусь с несколькими ошибками.

Задача 3 - Определить прямоугольник из цифр:

(?|`d`d+)(\(?|(?_(1)`d+)))+

Сопоставьте верхний ряд из двух или более цифр, затем убедитесь, что каждая строка ниже имеет одинаковую длину. `dпредопределенный символьный класс, эквивалентный [0-9].

Обратите внимание, что это находит все совпадения .

Задача 7 - Сопоставить нижние порталы:

(?|.X{2,22}.)\((?|(?_(1)X`.+X))\){3,22}(?_(1).X+.)

что выводит, для верхнего примера в оригинальном потоке :

Match found in rectangle: (2, 1), (5, 5)
XXXX
X..X
X..X
X..X
XXXX

Match found in rectangle: (9, 1), (14, 5)
.XXXX.
X....X
X....X
X....X
.XXXX.

Match found in rectangle: (13, 4), (17, 8)
.XXXX
X...X
X...X
X...X
.XXX.

Наконец, некоторые другие функции Slip включают в себя:

• $0, $1, $2, ..., $7закрепите северный край, северо-восточный угол, восточный край и т. д., $+закрепите любой край и $*закрепите любой угол.
• $сопровождаемый символом нижнего регистра устанавливает привязку в текущей позиции, которая может позже соответствовать $последующему соответствующему символу верхнего регистра, например, $aи $A.
• # переключает флаг отсутствия движения, который останавливает движение указателя совпадения после следующего совпадения.
• ,соответствует символу, подобному символу ., но не добавляет его к выводу, что позволяет выполнять несмежные совпадения, но при этом может быть распознано (?_()).

... и более. Там действительно слишком много, чтобы перечислить на этой странице.

Другие проблемы

Задача 1 - Нахождение шахматной доски:

(?|`#?(`_`#)+`_?)(?_(1)(?|...+))(\(?_(1)(?|`#?(`_`#)+`_?$a)))+<(?|`#?(`_`#)+`_?)(?_(9)(?|...+))(\(?_(9)(?|`#?(`_`#)+`_?)))+$A

Две проблемы шахматной доски, конечно, не являются сильной стороной Слип. Мы подбираем верхний ряд, затем проверяем, что он имеет длину не менее 3 и чередуется между #и _, затем проскальзываем и сопоставляем последующие строки. К концу $aякорь должен быть в правом нижнем углу шахматной доски.

Затем мы поворачиваем налево и повторяем для столбцов, убедившись, что мы совпадаем $Aв конце.

Задача 2 - Проверка шахматных досок:

$7%(\(?|`_?(`#`_)*`#?$2))+$5<%(\(?|`_?(`#`_)*`#?$0))+$3

Как и в предыдущей задаче, мы проверяем правильность каждой строки, затем поворачиваем влево и делаем то же самое для столбцов. Якоря используются для проверки соответствия всей доски.

Задача 9 - Горизонтальное и вертикальное выравнивание:

>?`#,*`#

Мы применяем необязательно? квантификатор команды >поворота, чтобы мы соответствовали либо вправо, либо вниз. Мы находим все 5 в примере с oперекрывающимся режимом, но только 4 без него #.,##и #.,#начинаем с той же позиции.

Задача 10 - Коллинеарные точки

^+`#(?|(,*)<(,*))(((?_(2),*)<(?_(3),*),>)+#`#){2}

Подберите #затем несколько горизонтальных и несколько вертикальных символов, затем повторите до второго #и повторите до третьего #.

Задача 5 - Обнаружение прямоугольных входов:

$7.(.*)>(?_(1).*)$3>((?|.*)\)*

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

Задача 8 - Размещение сундуков Minecraft:

`.^+(($^|(?|`.))>){3}($^|`.|C<(($^|(?|`.))>){3})

Запустите с pфлагом, чтобы получить позиции каждого матча. $^является якорем, который соответствует, если следующий шаг выведет указатель соответствия за пределы.

Сначала мы Совпадение ., а затем проверить , что мы окружены три .с / границами, то убеждается , что четвёртое окружающий квадрат также ./ граница или одна грудь (проверив его окружающие квадраты).

Проблема 11 - Проверьте синтаксис Prelude :

$7>%(/(?|[^()]+$4)(?1)?|/(?|[^()]*`([^()]*$4)(?1)?/(?|[^()]*`)[^()]*$4)(?1)?)$1

Сделал несколько попыток, но я думаю, что это правильно. Здесь мы используем рекурсию, которая имеет тот же синтаксис, что и PCRE.

Этот подход требует, чтобы вход был прямоугольным, но как только я получу непрямоугольное соответствие, это предположение не понадобится.

Вот тот же подход, игра в гольф с большей рекурсией:

$7>%((/(?|([^()]*)$4)|/(?|(?4)`((?3))(?1)?/(?|(?4)`)(?3)))*)$1

Задача 16 - Оберните края:

%(\(?|`#{3})){3}

(Примечание: упаковка еще не была отправлена ​​онлайн-переводчику)

Это требует флаг обтекания w. Технически, начальная буква %для не проскальзывания не обязательна, но тогда совпадение будет считаться начиная с квадрата выше.

Задача EX 1 - Решатель лабиринта:

S(^+`.)*^+E

Проблема из комментария BMac в чате . Используйте rфлаг для режима без повтора, чтобы указатель совпадения не застревал при движении вперед и назад.

Задача EX 2 - Распознавание лиц :

(?|O(,*),(?_(2),*)O)(?_(2)(\(?|,))*)\(?|,(?_(2),*)O)(?_(2)(\(?|,))*)\`\(?_(2)`_*)`_(?_(2)`_*)`/

Обратите внимание, что я сопоставляю только лица, а не очищаю. Обратите внимание, что вопрос содержит символы евро, которые должны быть заменены некоторыми печатными ASCII для работы.

PMA / Улитки (C ++)

Я представляю язык как улитки, перемещающиеся по сетке и выполняющие команды. Улитки оставляют след слизи на каждом квадрате, по которому они двигаются, что по умолчанию приводит к тому, что квадрат впоследствии становится несопоставимым. Совпадение считается успешным, если достигнут конец списка команд.

Сейчас достаточно операторов, поэтому нам понадобится список приоритетов, чтобы отслеживать их. Операции разрешаются в следующем порядке:

1. Внутри групп ( ) [ ]
2. Разбить чередующийся символ |
3. Оцените все слева от `группы
4. Квантификаторы [m],[n]иn
5. Утверждения = !
6. конкатенация

Интерпретатор написан на C ++. Бедный исходный код можно найти здесь .

Проблема 4: поиск слова

Программа

z\G\O\L\F

достаточно, чтобы получить истинное или ложное значение того, найдено ли слово. z(одна из 15 абсолютных или относительных команд направления) совпадает в любом октилинеарном направлении. Несколько последовательных команд направления объединяются. Например ruldy, будет почти эквивалентно z, поскольку это команды для вправо, вверх, влево, вниз и любого диагонального направления. Тем не менее, направления будут проверены в другом порядке. Первый соответствующий символ всегда тот, с которого начинается улитка, независимо от направления. \<персонаж> соответствует одному буквенному символу.

Стратегия по умолчанию состоит в том, чтобы попробовать шаблон в каждом квадрате в ограничительной рамке выровненного по левому краю ввода и вывести количество совпадений. Если булево значение 1или 0требуется, можно использовать следующую программу:

?
z\G\O\L\F

Если в исходном файле есть хотя бы одна новая строка, первая строка рассматривается как параметры для первоначального преобразования ввода в прямоугольную форму. ?Опция печатает 0 или 1 в зависимости от того, есть ли матч в любом месте.

Проблема 15: ошеломить

После реализации чередования теперь возможно решить Boggle. Было бы лучше использовать сопоставление без учета регистра для этого, но его реализация не является моим высшим приоритетом.

\p|\P)z(\a|\A)z{\n|\N)z{\a|\A}z(\m|\M)z(\a|\A

|работает точно так же, как 1-мерное регулярное выражение. Для группировки есть две подходящие пары разделителей, а именно ()и {}. Закрывающая скобка закроет все открытые группы противоположного типа, которые стоят между ним и ближайшими того же типа. Например, после {({{), только самая левая группа остается открытой. Как видите, непревзойденные символы группировки по краям неявно закрыты. Есть еще одна группирующая команда, в `которую я сейчас не буду вдаваться.

Задача 8: Сундуки Майнкрафта

Программа печатает количество действительных мест размещения сундуков. Это был первый раз, когда мне пришлось играть в гольф, и он несколько раз уменьшил количество моих байтов (17).

\.!(o\C)2o(!\Cw)3

• \. буквально соответствует точке в начальной точке матча.
• !(o\C)2эквивалентно тому, !((o\C)2)что количественное определение имеет более высокий приоритет, чем утверждение. <atom> <number>значит повторять <atom>точно <number>раз. oповорачивает улитку в любом ортогональном направлении. !это отрицательное утверждение. Таким образом, эта часть проверяет отсутствие смежного двойного сундука.
• o поворачивается в каком-то ортогональном направлении.
  • (!\Cw)3утверждает, что нет Cперед улиткой, а затем поворачивается против часовой стрелки, 3 раза.

Проблема 2: Проверка шахматных досок

&
\#!(o^_)|\_!(o^#

&Опция устанавливает выход программы в 1случае , если совпадение найдено на все позиции, и в 0противном случае. ^cсоответствует символу, которого нет c, эквивалентно [^c]регулярному выражению. В целом, программа означает: «Печать 1», если в каждой позиции в ограничивающем прямоугольнике ввода есть или то, #которое не является ортогонально смежным с символом, который не является _, или то, _которое не является ортогонально смежным с символом, который является нет #; в противном случае 0.

Класс Re2d, Python 2

Обновление: добавлена ​​проблема "9. Выравнивание".

Мой подход заключается в использовании модуля Python re для поиска и сопоставления. Класс Re2d подготавливает текст для обработки, выполняет функции re и форматирует результаты для вывода.

Обратите внимание, что это не совсем новый язык - это стандартный язык регулярных выражений, проецируемый в 2 измерения с добавленными флагами для дополнительных 2D-режимов.

Класс имеет следующее использование:

re2dobject = Re2d(<horizontal pattern>, [<vertical pattern>], [<flags>])

Оба шаблона являются стандартными линейными текстовыми шаблонами RE. Если вертикальный шаблон не указан, класс также будет использовать горизонтальный шаблон для сопоставления по вертикали. Флаги являются стандартными RE-флагами с некоторыми 2D-расширениями.

тестирование

1. Finding chessboards
Chessboard pattern at (2, 1, 4, 3)

print '\n1. Finding chessboards'
reob1 = Re2d('#(_#)+_?|_(#_)+#?')
found = reob1.search('~______~\n~##_#_#~\n~#_#_##~\n~##_#_#~\n~______~')
print 'Chessboard pattern at', found
assert not reob1.search('#_##\n_#_#\n__#_\n#_#_\n#_#_')

Метод поиска нашел шахматную фигуру и возвращает позицию с четырьмя кортежами. Кортеж имеет x,yпозицию первого символа матча и область совпадения width, height. Дан только один шаблон, поэтому он будет использоваться для горизонтального и вертикального соответствия.

2. Verifying chessboards
Is chess? True

print '\n2. Verifying chessboards'
reob2 = Re2d('^#(_#)*_?|_(#_)*#?$')
print 'Is chess?', reob2.match('_#_#_#_#\n#_#_#_#_\n_#_#_#_#')
assert not reob2.match('_#_#_#__\n__#_#_#_\n_#_#_#__')

Шахматная доска была проверена методом соответствия, который возвращает логическое значение. Обратите внимание , что ^и $начальная и конечные символы должны соответствовать всему тексту.

3. Rectangle of digits
Found: [(0, 1, 5, 3), (1, 1, 4, 3), (2, 1, 3, 3), (3, 1, 2, 3), (0, 2, 5, 2), (1, 2, 4, 2), (2, 2, 3, 2), (3, 2, 2, 2), (6, 3, 2, 2)]
Not found: None

print '\n3. Rectangle of digits'
reob3 = Re2d(r'\d\d+', flags=MULTIFIND)
print 'Found:', reob3.search('hbrewvgr\n18774gwe\n84502vgv\n19844f22\ncrfegc77')
print 'Not found:', reob3.search('uv88wn000\nvgr88vg0w\nv888wrvg7\nvvg88wv77')

Теперь мы используем MULTIFINDфлаг, чтобы вернуть все возможные совпадения для блока из 2+ цифр. Метод находит 9 возможных совпадений. Обратите внимание, что они могут перекрываться.

4. Word search (orthogonal only)
Words: [(0, 0, 4, 1), (0, 3, 4, 1), (3, 3, -4, -1), (3, 2, -4, -1), (3, 0, -4, -1)] [(0, 0, 1, 4), (3, 0, 1, 4), (3, 3, -1, -4), (0, 3, -1, -4)]
Words: ['SNUG', 'WOLF', 'FLOW', 'LORE', 'GUNS'] ['S\nT\nE\nW', 'G\nO\nL\nF', 'F\nL\nO\nG', 'W\nE\nT\nS']
No words: [] []

print '\n4. Word search (orthogonal only)'
words = 'GOLF|GUNS|WOLF|FLOW|LORE|WETS|STEW|FLOG|SNUG'
flags = HORFLIP | VERFLIP | MULTIFIND
reob4a, reob4b = Re2d(words, '.', flags), Re2d('.', words, flags)
matching = 'SNUG\nTEQO\nEROL\nWOLF'
nomatch = 'ABCD\nEFGH\nIJKL\nMNOP'
print 'Words:', reob4a.search(matching), reob4b.search(matching)
print 'Words:', reob4a.findall(matching), reob4b.findall(matching)
print 'No words:', reob4a.findall(nomatch), reob4b.findall(nomatch)

Этот тест показывает использование вертикального и горизонтального переворачивания. Это позволяет сопоставлять слова, которые являются обратными. Диагональные слова не поддерживаются. MULTIFINDФлаг позволяет использовать несколько матчей перекрывающихся во всех 4 -х направлениях. Метод findall использует поиск, чтобы найти соответствующие поля, а затем извлекает соответствующие блоки текста. Обратите внимание, что при поиске используются отрицательные значения ширины и / или высоты для совпадений в обратном направлении. Слова в вертикальном направлении имеют символы новой строки - это согласуется с концепцией блоков 2D-символов.

7. Calvins portals
Portals found: [(3, 1, 5, 6)]
Portal not found None

print '\n7. Calvins portals'
reob7 = Re2d(r'X\.{2,22}X|.X{2,22}.', r'X\.{3,22}X|.X{3,22}.', MULTIFIND)
yes = '....X......\n.XXXXXX.XX.\n...X...X...\n.X.X...XXX.\n...X...X.X.\n.XXX...X.X.\nX..XXXXX.X.'
no = 'XX..XXXX\nXX..X..X\nXX..X..X\n..X.X..X\n.X..X.XX'
print 'Portals found:', reob7.search(yes)
print 'Portal not found', reob7.search(no)

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

9. Alignment
Found: ['#.,##', '##'] ['#\n.\n,\n.\n#', '#\n,\n.\n#']
Found: [(3, 4, 5, 1), (6, 4, 2, 1)] [(7, 0, 1, 5), (3, 1, 1, 4)]
Not found: None None

print '\n9. Alignment'
reob9a = Re2d(r'#.*#', r'.', MULTIFIND)
reob9b = Re2d(r'.', r'#.*#', MULTIFIND)
matching = '.,.,.,.#.,\n,.,#,.,.,.\n.,.,.,.,.,\n,.,.,.,.,.\n.,.#.,##.,\n,.,.,.,.,.'
nomatch = '.,.#.,.,\n,.,.,.#.\n.,#,.,.,\n,.,.,.,#\n.#.,.,.,\n,.,.#.,.\n#,.,.,.,\n,.,.,#,.'
print 'Found:', reob9a.findall(matching), reob9b.findall(matching)
print 'Found:', reob9a.search(matching), reob9b.search(matching)
print 'Not found:', reob9a.search(nomatch), reob9b.search(nomatch)

Этот набор из 2 поисков находит 2 вертикальных и 2 горизонтальных совпадения, но не может найти встроенную #.,#строку.

10. Collinear Points (orthogonal only)
Found: [(0, 1, 7, 1)] [(3, 1, 1, 4)]
Not found: None None

print '\n10. Collinear Points (orthogonal only)'
matching = '........\n#..#..#.\n...#....\n#.......\n...#....'
nomatch = '.#..#\n#..#.\n#....\n..#.#'
reob10h = Re2d(r'#.*#.*#', '.')
reob10v = Re2d('.', r'#.*#.*#')
flags = MULTIFIND
print 'Found:', reob10h.search(matching, flags), reob10v.search(matching, flags)
print 'Not found:', reob10h.search(nomatch, flags), reob10v.search(nomatch, flags)

Здесь мы используем 2 поиска, чтобы найти совпадения в обоих направлениях. Он может найти несколько ортогональных совпадений, но этот подход не поддерживает диагональные совпадения.

12. Avoid qQ
Found: (2, 2, 4, 4)
Not found: None

print '\n12. Avoid qQ'
reob12 = Re2d('[^qQ]{4,4}')
print 'Found:', reob12.search('bhtklkwt\nqlwQklqw\nvtvlwktv\nkQtwkvkl\nvtwlkvQk\nvnvevwvx')
print 'Not found:', reob12.search('zxvcmn\nxcvncn\nmnQxcv\nxcvmnx\nazvmne')

Этот поиск находит первое совпадение.

13. Diamond Mining
.X.
X.X
.X.

.X.
X.X
.X.

..X..
./.\.
X...X
.\./.
\.X..

..X..
./.\.
X...X
.\./.
..X..

.XX.\
//.\.
X...X
.\./.
..X..

...X...
../.\..
./.X.\.
X.X.X.X
.\.X.//
..\./X.
.X.X..\

Diamonds: [(2, 2, 3, 3), (0, 6, 3, 3)] [(8, 0, 5, 5), (10, 2, 5, 5), (5, 3, 5, 5)] [(0, 0, 7, 7)]
Not found: None None None

print '\n13. Diamond Mining'
reob13a = Re2d(r'.X.|X.X', flags=MULTIFIND)
reob13b = Re2d(r'..X..|./.\\.|X...X|.\\./.', flags=MULTIFIND)
reob13c = Re2d(r'...X...|../.\\..|./...\\.|X.....X|.\\.../.|..\\./..', flags=MULTIFIND)
match = '''
...X......X....
../.\..../.\...
./.X.\..X...X..
X.X.X.XX.\./.\.
.\.X.//.\.X...X
..\./X...X.\./.
.X.X..\./...X..
X.X....X.......
.X.............
'''.strip().replace(' ', '')
nomatch = '''
.X......./....
.\....X.......
...X.\.\...X..
..X.\...\.X.\.
...X.X...X.\.X
../X\...\...X.
.X...\.\..X...
..\./.X....X..
...X..../.....
'''.strip().replace(' ', '')
for diamond in reob13a.findall(match)+reob13b.findall(match)+reob13c.findall(match):
    print diamond+'\n'
print 'Diamonds:', reob13a.search(match), reob13b.search(match), reob13c.search(match)
print 'Not found:', reob13a.search(nomatch), reob13b.search(nomatch), reob13c.search(nomatch)

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

Код Python 2

import sys
import re

DEBUG = re.DEBUG
IGNORECASE = re.IGNORECASE
LOCALE = re.LOCALE
UNICODE = re.UNICODE
VERBOSE = re.VERBOSE
MULTIFIND = 1<<11
ROTATED = 1<<12     # not implemented
HORFLIP = 1<<13
VERFLIP = 1<<14
WRAPAROUND = 1<<15  # not implemented

class Re2d(object):
    def __init__(self, horpattern, verpattern=None, flags=0):
        self.horpattern = horpattern
        self.verpattern = verpattern if verpattern != None else horpattern
        self.flags = flags

    def checkblock(self, block, flags):
        'Return a position if block matches H and V patterns'
        length = []
        for y in range(len(block)):
            match = re.match(self.horpattern, block[y], flags)
            if match:
                length.append(len(match.group(0)))
            else:
                break
        if not length:
            return None
        width = min(length)
        height = len(length)
        length = []
        for x in range(width):
            column = ''.join(row[x] for row in block[:height])
            match = re.match(self.verpattern, column, flags)
            if match:
                matchlen = len(match.group(0))
                length.append(matchlen)
            else:
                break
        if not length:
            return None
        height = min(length)
        width = len(length)
        # if smaller, verify with RECURSIVE checkblock call:
        if height != len(block) or width != len(block[0]):
            newblock = [row[:width] for row in block[:height]]
            newsize = self.checkblock(newblock, flags)
            return newsize
        return width, height

    def mkviews(self, text, flags):
        'Return views of text block from flip/rotate flags, inc inverse f()'
        # TODO add ROTATED to generate more views
        width = len(text[0])
        height = len(text)
        views = [(text, lambda x,y,w,h: (x,y,w,h))]
        if flags & HORFLIP and flags & VERFLIP:
            flip2text = [row[::-1] for row in text[::-1]]
            flip2func = lambda x,y,w,h: (width-1-x, height-1-y, -w, -h)
            views.append( (flip2text, flip2func) )
        elif flags & HORFLIP:
            hortext = [row[::-1] for row in text]
            horfunc = lambda x,y,w,h: (width-1-x, y, -w, h)
            views.append( (hortext, horfunc) )
        elif flags & VERFLIP:
            vertext = text[::-1]
            verfunc = lambda x,y,w,h: (x, height-1-y, w, -h)
            views.append( (vertext, verfunc) )
        return views

    def searchview(self, textview, flags=0):
        'Return matching textview positions or None'
        result = []
        for y in range(len(textview)):
            testtext = textview[y:]
            for x in range(len(testtext[0])):
                size = self.checkblock([row[x:] for row in testtext], flags)
                if size:
                    found = (x, y, size[0], size[1])
                    if flags & MULTIFIND:
                        result.append(found)
                    else:
                        return found
        return result if result else None

    def search(self, text, flags=0):
        'Return matching text positions or None'
        flags = self.flags | flags
        text = text.split('\n') if type(text) == str else text
        result = []
        for textview, invview in self.mkviews(text, flags):
            found = self.searchview(textview, flags)
            if found:
                if flags & MULTIFIND:
                    result.extend(invview(*f) for f in found)
                else:
                    return invview(*found)
        return result if result else None

    def findall(self, text, flags=0):
        'Return matching text blocks or None'
        flags = self.flags | flags
        strmode = (type(text) == str)
        text = text.split('\n') if type(text) == str else text
        result = []
        positions = self.search(text, flags)
        if not positions:
            return [] if flags & MULTIFIND else None
        if not flags & MULTIFIND:
            positions = [positions]
        for x0,y0,w,h in positions:
            if y0+h >= 0:
                lines = text[y0 : y0+h : cmp(h,0)]
            else:
                lines = text[y0 : : cmp(h,0)]
            if x0+w >= 0:
                block = [row[x0 : x0+w : cmp(w,0)] for row in lines]
            else:
                block = [row[x0 : : cmp(w,0)] for row in lines]
            result.append(block)
        if strmode:
            result = ['\n'.join(rows) for rows in result]
        if flags & MULTIFIND:
            return result
        else:
            return result[0]

    def match(self, text, flags=0):
        'Return True if whole text matches the patterns'
        flags = self.flags | flags
        text = text.split('\n') if type(text) == str else text
        for textview, invview in self.mkviews(text, flags):
            size = self.checkblock(textview, flags)
            if size:
                return True
        return False

Грайм , Хаскелл

Введение

Grime основан на булевых грамматиках . Основная идея состоит в том, чтобы создать прямоугольные шаблоны из меньших компонентов и проверить, найдены ли они во входной матрице. Пока что Grime поддерживает только прямоугольные совпадения и более или менее элегантно решает как минимум 11 задач.

РЕДАКТИРОВАТЬ: Исправлены кресты (спасибо DLosc за обнаружение ошибки), и добавил добычу алмазов.

EDIT2: добавлены классы персонажей, вдохновленные классами Slip. Также изменился синтаксис флагов опций, улучшен синтаксический анализатор выражений и добавлена ​​проблема без Q.

EDIT3: Реализованы ограничения размера и добавлена ​​проблема порталов Nether.

использование

Программа Grime называется грамматикой , и правильное расширение файла для грамматики .gr, хотя это не применяется. Грамматика оценивается как

runhaskell grime.hs [options] grammarfile matrixfile

где matrixfileфайл, содержащий матрицу символов. Например, грамматика цифр будет оцениваться как

runhaskell grime.hs digits.gr digit-matrix

Для дополнительной скорости я рекомендую компилировать файл с оптимизацией:

ghc -O2 grime.hs
./grime digits.gr digit-matrix

По умолчанию интерпретатор печатает первое найденное совпадение, но это можно контролировать с помощью флажков опции:

• -e: сопоставлять только всю матрицу, печатать 1для совпадения и 0без совпадения.
• -n: вывести количество совпадений или всю матрицу, если -eона также указана.
• -a: распечатать все совпадения.
• -p: также распечатать позиции матчей в формате (x,y,w,h).
• -s: не печатайте сами спички.
• -d: вывести отладочную информацию.

Параметры также можно указать в грамматике, вставив их перед любой строкой и добавив запятую ,(примеры приведены ниже).

Синтаксис и семантика

Грамматика Грайма состоит из одного или нескольких определений , каждое на отдельной строке. Каждый из них определяет значение нетерминала , и один из них должен определять анонимный уровень для нетерминала . Синтаксис определения либо N=Eили E, где Nэто заглавная буква и Eявляется выражением .

Выражения построены следующим образом.

• Любой символ с экранированием \соответствует любому 1x1прямоугольнику, содержащему этот символ.
• . соответствует любому отдельному символу.
• $соответствует 1x1прямоугольнику вне матрицы символов.
• _ соответствует любому прямоугольнику нулевой ширины или высоты.
• Предварительно определенные группы символов являются dИГИТ, uppercase, lowercase, alphabetic, альфа numeric и symbol.
• Новые классы символов могут быть определены синтаксисом [a-prt-w,d-gu]. Буквы слева включены, а справа - исключены, поэтому они точно соответствуют буквам abchijklmnoprtvw. Если левая сторона пуста, она должна содержать все символы. Запятая может быть опущена, если правая сторона пуста. Символы [],-\должны быть экранированы \.
• Неэкранированная заглавная буква является нетерминальной и соответствует выражению, которое ей присвоено.
• Если Pи Qявляются выражениями, то PQэто просто их горизонтальная конкатенация и P/Qвертикальная конкатенация Pсверху.
• P+один или несколько Ps выровнены по горизонтали и P/+одинаково выровнены по вертикали.
• Булевы операции обозначены P|Q, P&Qи P!.
• P?является сокращением для P|_, P*для P+|_и P/*для P/+|_.
• P#соответствует любому прямоугольнику, который содержит совпадение P.
• P{a-b,c-d}, Где abcdнеотрицательные целые числа, является ограничение размера на P. Если Pэто символьный класс, то выражение соответствует любому mxnпрямоугольнику, содержащему только те символы, при условии, что mмежду aи bвключительно, и nмежду cи dвключительно. В других случаях выражение соответствует любому прямоугольнику, который имеет правильный размер и Pтакже соответствует. Если aили cопущены, они принимаются 0, и если bили dопущены, они бесконечны. Если дефис между aи bопущен, то мы используем одно и то же число для обоих концов интервала. Если весьc-dчасть опущена, обе оси ограничены. Чтобы уточнить, {-b}эквивалентно {0-b,0-b}и {a-,c}эквивалентно {a-infinity,c-c}.

Примечания

Грайм допускает парадоксальные определения, например, A=A!с неопределенным поведением. Однако они не вызовут сбоев или бесконечных циклов.

Grime поддерживает непрямоугольные входы; строки просто выровнены по левому краю, а промежутки можно сопоставить с помощью $.

В будущем я хотел бы реализовать следующее:

• Более быстрое соответствие. В настоящее время интерпретатор не учитывает тот факт, что, например, .могут соответствовать только 1x1прямоугольники. Пока он не найдет совпадение, он пробует все прямоугольники всех размеров по порядку, мгновенно терпя неудачу для каждого из них.
• Операции поворота и отражения, для поиска слова и задач планера.

• Непрямоугольные совпадения с использованием контекстов , которые были бы полезны в задаче Boggle. Например, Pv(Q>R)означает Pс нижним контекстом ( Qс правым контекстом R). Это будет соответствовать L-образным образцам

  PPP
  PPP
  QQQRRRR
  QQQRRRR
  QQQRRRR
  

Задачи

Дано примерно в порядке сложности.

Прямоугольник цифр

d{2-}

Это просто: прямоугольник с цифрами размером как минимум 2x2.

Нет д или в

[,qQ]{4}

Это почти так же просто, как первый; теперь у нас есть более ограниченный размер и пользовательский класс символов.

Горизонтальное и вертикальное выравнивание

\#.*\#|\#/./*/\#

Теперь у нас есть несколько сбежавших персонажей. По сути, это соответствует одному #, затем любому количеству любых символов #, либо по горизонтали, либо по вертикали.

Определить квадратные входы

S=.|S./+/.+
e,S

Эта грамматика очень проста, она в основном определяет, что квадрат является либо 1x1прямоугольником, либо меньшим квадратом с одним столбцом, прикрепленным к его правому краю, и одним рядом, прикрепленным к нижней части этого. Обратите внимание также на eопцию перед нетерминалом верхнего уровня, которая включает полную проверку ввода.

Поиск слова в поиске слова

G=\G
O=\O
L=\L
F=\F
GOLF|FLOG|G/O/L/F|F/L/O/G|G.../.O../..L./...F|...G/..O./.L../F...|F.../.L../..O./...G|...F/..L./.O../G...

Это ужасно, поскольку у Грайма нет операций по вращению или отражению. Это также очень медленно, так как Grime не знает , что матчи могут быть только размер 4x1, 1x4или 4x4.

Проблему планера можно решить аналогичным образом, но мне лень это записывать.

Порталы Пустоты

.\X+./\X/+\.{2-22,3-22}\X/+/.\X+.

С оператором ограничения размера это не так сложно. Средняя часть \.{2-22,3-22}соответствует любому прямоугольнику .правильных размеров, а затем мы просто добавляем столбцы Xs с обеих сторон и прикрепляем ряды Xs с игнорируемыми концами вверху и внизу.

Соответствующие кресты

E=\.+/+
F=\#+/+
EFE/F/EFE&(E/F/E)F(E/F/E)

Здесь мы имеем соединение (логическое И) двух выражений. Нетерминал Eсоответствует непустому прямоугольнику .s и Fнепустому прямоугольнику #s. Левая сторона соединения соответствует прямоугольникам типа

...####..
...####..
...####..
#########
#########
.....##..
.....##..

где мы EFEна вершине, то F, а потом еще EFEраз. Правая сторона соответствует транспонированию этих, поэтому мы получаем именно кресты.

Добыча алмазов

C=./+
T=\X|CTC/\/.+\\
B=\X|\\.+\//CBC
CTC/\X.+\X/CBC

Нетерминал C- это сокращение для любого 1xnстолбца. Верхняя половина алмаза совпадает с T: это либо один X, либо другой, Tокруженный столбцом с обеих сторон, и ряд /[something]\ниже этого. Bсовпадает с нижней частью алмаза таким же образом, и нетерминал верхнего уровня - это просто ряд формы X[something]Xмежду верхней половиной и нижней половиной.

В поисках шахматных досок

(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]{3-}

Правая сторона [#_]{3-}соответствует любому 3x3или большему прямоугольнику #s и _s, в то время как левая сторона гарантирует, что он не содержит двух соседних #s или _s.

Проверочные шахматные доски

e,(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]+/+

Это в основном то же самое, что и выше, за исключением того, что мы можем сопоставить любой непустой прямоугольник, но нужно использовать eфлаг для полной проверки ввода.

Проверьте синтаксис Prelude

A=[,()]/*
P=A*|P(A/\(/A)P(A/\)/A)P
e,P

Это, наверное, самая интересная грамматика на сегодняшний день. Нетерминал Aсоответствует любому столбцу, не содержащему (или ), и Pсоответствует либо некоторому числу As, либо двум соответствующим скобкам, между которыми и вне которых больше Ps.

TMARL

Язык соответствия шаблонов и распознавания

Описание

Мой переводчик занимает 24K символов ( фрагменты кода занимают символы? ), Поэтому полное описание можно найти здесь .

Самое приятное: переводчик написан на Javascript, то есть вы можете попробовать его прямо здесь!

var reservedOutsideInput = "\u0007";
var templateChar = "$"
function run(){
    var program = getCode();
    evaluate(program,{},{})
}

function getCode(){
    return document.getElementById('code-area').value;
}

//3 types of objects - templates, match arrays, and integers
function evaluate(program, variables,referenceObject){
    variables["I"] = {};
    variables["I"].value = getInput().split("\n");
    variables["I"].type = "array";
    var lines = program.split("\n");
    var argumentExpected = null;
    var jumpTo = null;
    for(var l = 0; l<lines.length; l++){
        if(!!jumpTo){
            l = jumpTo.line;
        }
        var line = lines[l];
        if(line[0] === templateChar){
            //next few lines is a template
            var template = findTemplate(lines,l);
            
            if(argumentExpected !== null){
                argumentExpected(template);
            }else{
                referenceObject.value = template;
                referenceObject.type = "template";
            }
            l += template.length - 1;
        }else{
            var i = 0;
            if(!!jumpTo){
                i = jumpTo.index;
                jumpTo = null;
            }
            while(i < line.length){
                var character = line[i];
                if(character === "P"){
                    output(referenceObject);
                    argumentExpected = null;
                }else if(character === "R"){
                    argumentExpected = function(arg){
                        referenceObject.value = rotate(referenceObject.value,arg);
                        referenceObject.type = "template";
                    };
                }else if(character === "M"){
                    referenceObject.value = mirror(referenceObject.value);
                    referenceObject.type = "template"
                    argumentExpected = null;
                }else if(character === "^"){
                    if(referenceObject.type === "int"){
                        argumentExpected = function(num){
                            referenceObject.value = Math.pow(referenceObject.value,num);
                            referenceObject.type = "int";
                        }
                    }else{
                        argumentExpected = function(template){
                            referenceObject.value = appendVertically(referenceObject.value,template,true);
                            referenceObject.type = "template";
                        }
                    }
                }else if(character === "v"){
                    argumentExpected = function(template){
                        referenceObject.value = appendVertically(referenceObject.value,template,false);
                        referenceObject.type = "template";
                    }
                }else if(character === "<"){
                    argumentExpected = function(template){
                        referenceObject.value = appendHorizontally(referenceObject.value,template, true);
                        referenceObject.type = "template";
                    }
                }else if(character === ">"){
                    argumentExpected = function(template){
                        referenceObject.value = appendHorizontally(referenceObject.value,template, false);
                        referenceObject.type = "template";
                    }
                }else if(character === "&"){
                    argumentExpected = function(searchArg){
                        referenceObject.value = referenceObject.value.concat(searchArg);
                        referenceObject.type = "search"
                    }
                }else if(character === "*"){
                    if(referenceObject.type === "int"){
                        argumentExpected = function(num){
                            referenceObject.value*=num;
                            referenceObject.type = "int";
                        }
                    }else{
                        argumentExpected = function(num){
                            referenceObject.value = multiply(referenceObject.value,num);
                            referenceObject.type = "template";
                        }
                    }
                }else if(character === "+"){
                    argumentExpected = function(num){
                        referenceObject.value+=num;
                        referenceObject.type = "int";
                    }
                }else if(character === "-"){
                    argumentExpected = function(num){
                        referenceObject.value-=num;
                        referenceObject.type = "int";
                    }
                }else if(character === "/"){
                    argumentExpected = function(num){
                        referenceObject.value = referenceObject.value / num;
                        referenceObject.type = "int";
                    }
                }else if(character === "%"){
                    argumentExpected = function(num){
                        referenceObject.value = referenceObject.value % num;
                        referenceObject.type = "int";
                    }
                }else if(character === "!"){
                    if(referenceObject.value === 0){
                        referenceObject.value = 1;
                    }else{
                        referenceObject.value = 0;
                    }
                    referenceObject.type = "int";
                }else if(character === "~"){
                    argumentExpected = function(num){
                        var original = copyTemplate(referenceObject.value);
                        while(num > 1){
                            referenceObject.value = appendHorizontally(referenceObject.value,original,true);
                            num--;
                        }
                        referenceObject.type = "template";
                    }
                }else if(character === "L"){
                    referenceObject.value = referenceObject.value.length;
                    referenceObject.type = "int";
                }else if(character === "S"){
                    argumentExpected = function(num){
                        var firstOnly = true;
                        var anyRotation = true;
                        if(num >= 4){firstOnly = false;}
                        else{firstOnly = true;}
                        if(num%2 === 0){anyRotation = true;}
                        else{anyRotation = false;}
                        referenceObject.value = search(getInput(),referenceObject.value, 
                            anyRotation,firstOnly);
                            
                        if(firstOnly){referenceObject.type = "match"}
                        else{referenceObject.type = "search";}
                    }
                }else if(character === "G"){
                    argumentExpected = function(num){
                        if(referenceObject.type === "search"){
                            referenceObject.value = referenceObject.value[num];
                            referenceObject.type = "match"
                        }else if(referenceObject.type === "match"){
                            if(num === 0){
                                referenceObject.value = referenceObject.value.x;
                                referenceObject.type = "int"
                            }
                            if(num === 1){
                                referenceObject.value = referenceObject.value.y;
                                referenceObject.type = "int";
                            }
                            if(num === 2){
                                referenceObject.value = referenceObject.value.match;
                                referenceObject.type = "2darray"
                            }
                        }else if(referenceObject.type === "array"){
                            referenceObject.value = referenceObject.value[num];
                            referenceObject.type = "string";
                        }else if(referenceObject.type === "string"){
                            referenceObject.value = referenceObject.value.charAt(num);
                            referenceObject.type = "char";
                        }
                    }
                }else if(character === "("){
                    var parenthese = getParentheses(lines, l, i);
                    var temp = evaluate(parenthese.content,variables,{});
                    if(!!argumentExpected){
                        argumentExpected(temp.value);
                    }else{
                        referenceObject.value = temp.value;
                        referenceObject.type = temp.type;
                    }
                    //keep the program in the loop to catch the jump
                    l--;
                    jumpTo = {line: parenthese.lineEnd, index: parenthese.indexEnd};
                    break;
                }else{
                    if(character < '0' || character > '9'){
                        if(!!variables[character]){
                            //the variable exists
                            if(argumentExpected !== null){
                                argumentExpected(variables[character].value);
                            }else{
                                referenceObject.value = variables[character].value;
                                referenceObject.type = variables[character].type;
                            }
                        }else{
                            variables[character] = {};
                            variables[character].value = cloneReference(referenceObject);
                            variables[character].type = referenceObject.type;
                        }
                    }else{
                        //character must be argument (its a number)
                        if(argumentExpected !== null){
                            argumentExpected(parseFloat(character));
                        }else{
                            referenceObject.value = parseFloat(character);
                            referenceObject.type = "int";
                        }
                    }
                    
                }
                i++;
            }
        }
    }
    return referenceObject;
}

function cloneReference(referenceObject){
    var newObject = {};
    if(referenceObject.type === "template"){
        newObject = copyTemplate(referenceObject.value);
    }
    if(referenceObject.type === "2darray"){
        newObject = copy2D(referenceObject.value);
    }
    if(referenceObject.type === "int"){
        newObject = referenceObject.value;
    }
    if(referenceObject.type === "search"){
        newObject = [];
        for(var i=0;i<referenceObject.value.length;i++){
            newObject.push({x:referenceObject.value[i].x,y:referenceObject.value[i].y,match:referenceObject.value.match});
        }
    }
    if(referenceObject.type === "match"){
        newObject = {x:referenceObject.value.x,y:referenceObject.value.y,match:referenceObject.value.match}
    }
    if(referenceObject.type === "string"){
        newObject = referenceObject.value;
    }
    if(referenceObject.type === "array"){
        newObject = copy(referenceObject.value);
    }
    if(referenceObject.type === "char"){
        newObject = referenceObject.value;
    }
    return newObject;
}

//returns {content, lineEnd, indexEnd}
function getParentheses(lines, line, index){
    var pointer = {line:line, index:index};
    var stack = [1];
    var content = "";
    while(stack.length > 0){
        pointer.index++;
        if(lines[pointer.line].length === pointer.index){
            pointer.line++;
            pointer.index = 0;
            content+="\n";
        }
        var character = lines[pointer.line].charAt(pointer.index);
        if(character === '('){
            stack.push(1);
        }
        if(character === ')'){
            stack.pop();
        }
        content += character;
    }
    pointer.index++;
    if(lines[pointer.line].length === pointer.index){
        pointer.line++;
        pointer.index = 0;
        content+="\n";
    }
    content = content.substring(0, content.length-1);
    return {content:content, lineEnd:pointer.line, indexEnd:pointer.index};
}

function getInput(){
    return document.getElementById("input").value;
}

function search(input, t, anyRotation, first){
    var inputArray = input.split("\n");
    processInput(inputArray);
    
    var possibleTemps = [t];
    if(anyRotation){
        possibleTemps.push(copyTemplate(rotate(t,1)));
        possibleTemps.push(copyTemplate(rotate(t,2)));
        possibleTemps.push(copyTemplate(rotate(t,3)));
    }
    var matches = [];
    for(var v = 0; v < possibleTemps.length; v++){
        var template = possibleTemps[v];
        for(var y = 0; y < inputArray.length; y++){
            for(var x = 0; x < inputArray[y].length; x++){
                var good = true;
                var match = matchTemplate(template);
                for(var ty = 0; ty < template.length; ty++){
                    for(var tx = 0; tx < template[ty].length; tx++){
                        var inputChar = null;
                        if(!!inputArray[y+ty]){
                            if(!!inputArray[y+ty][x+tx]){
                                inputChar = inputArray[y+ty][x+tx];
                            }
                        }
                        if(!charMatch(template[ty][tx],inputChar)){
                            good = false;
                        }else{
                            match[ty][tx] = inputChar;
                        }
                    }
                }
                if(good){
                    if(first){return {x:x,y:y,match:match}}
                    matches.push({x:x,y:y,match:match})
                }
            }
        }
    }
    return matches;
}

function processInput(inputArray){
    //add 'bell' character to outsides for edge recognition
    var filledTop = Array.apply(null, new Array(inputArray[0].length))
        .map(String.prototype.valueOf,reservedOutsideInput);
    var filledBottom = Array.apply(null, new Array(inputArray[inputArray.length-1].length))
        .map(String.prototype.valueOf,reservedOutsideInput);
    for(var row = 0; row < inputArray.length; row++){
        inputArray[row] = inputArray[row].split("");
        inputArray[row].splice(0,0,reservedOutsideInput);
        inputArray[row].push(reservedOutsideInput);
    }
    inputArray.splice(0,0,filledTop);
    inputArray.push(filledBottom);
}

function charMatch(templateC,inputChar){
    if(templateC.inCharClass === false && templateC.options[0] === "*" 
        && templateC.escaped === false){
        return true;
    }
    if(templateC.inCharClass === false && templateC.options[0] === "D" 
        && templateC.escaped === false){
        return inputChar >= '0' && inputChar <= '9'
    }
    if(templateC.inCharClass === false && templateC.options[0] === "L" 
        && templateC.escaped === false){
        return "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".indexOf(inputChar) > -1;
    }
    if(templateC.inCharClass === false && templateC.options[0] === "U" 
        && templateC.escaped === false){
        return "ABCDEFGHIJKLMNOPQRSTUVWXYZ".indexOf(inputChar) > -1;
    }
    if(templateC.inCharClass === false && templateC.options[0] === "l" 
        && templateC.escaped === false){
        return "abcdefghijklmnopqrstuvwxyz".indexOf(inputChar) > -1;
    }
    if(templateC.inCharClass === false && templateC.options[0] === "%" 
        && templateC.escaped === false){
        return inputChar === reservedOutsideInput;
    }
    if(templateC.options.indexOf('%') === -1 && inputChar === reservedOutsideInput){
        return false;
    }
    var good = false;
    if(templateC.not){
        good = true;
    }
    for(var i=0;i<templateC.options.length;i++){
        var option = templateC.options[i];
        console.log(templateC.not + ","+templateC.options)
        if(templateC.not && option === inputChar){
            good = false;
        }
        if(templateC.not === false && option === inputChar){
            good = true;
        }
    }
    return good;
    
}

function multiply(template, num){
    var original = copyTemplate(template);
    while(num > 1){
        template = template.concat(original);
        num--;
    }
    return template;
}

function copyTemplate(template){
    var newTemp = [];
    for(var y = 0; y< template.length; y++){
        newTemp[y] = [];
        for(var x = 0; x < template[y].length;x++){
            newTemp[y][x] = copyChar(template[y][x]);
        }
    }
    return newTemp;
}

function copyChar(character){
    return {not:character.not,options:copy(character.options),escaped:character.escaped,inCharClass:character.inCharClass};
}

function rotate(template,amount){
    while(amount > 0){
        var temp = box(template);
        var newTemplate = [];
        for(var x = 0; x < temp[0].length; x++){
            newTemplate[x] = [];
            for(var y = 0; y < temp.length; y++){
                newTemplate[x][temp.length-y-1] = temp[y][x];
            }
        }
        template = copyTemplate(newTemplate);
        amount--;
    }
    return template;
}

function box(template){
    var maxWidth = 0;
    var maxHeight = template.length;
    for(var y = 0; y < template.length;y++){
        if(template[y].length > maxWidth){maxWidth = template[y].length;}
    }
    var newTemplate = [];
    for(var row = 0 ; row < template.length; row++){
        newTemplate[row] = [];
        for(var x = 0; x < template[row].length;x++){
            newTemplate[row][x] = copyChar(template[row][x]);
        }
        while(newTemplate[row].length < maxWidth){
            newTemplate[row].push({not:false,inCharClass:false,options:["*"],escaped:false});
        }
    }
    return newTemplate;
}

//t1 over t2
function appendVertically(t1, t2, t1OnTop){
    var newTemplate = [];
    if(!t1OnTop){
        newTemplate = copyTemplate(t2).concat(copyTemplate(t1));
    }else{
        newTemplate = copyTemplate(t1).concat(copyTemplate(t2));
    }
    return newTemplate;
}

function appendHorizontally(t1, t2, t1OnLeft){
    var maxWidthT1 = 0;
    var maxWidthT2 = 0;
    for(var row=0;row<t1.length;row++){
        if(t1[row].length > maxWidthT1){maxWidthT1 = t1[row].length;}
    }
    for(var row2 = 0; row2 < t2.length;row2++){
        if(t2[row2].length > maxWidthT2){maxWidthT2 = t2[row2].length;}
    }
    var newTemplate = [];
    for(var r=0;r<Math.max(t1.length,t2.length);r++){
        newTemplate[r] = [];
        if(t1OnLeft){
            if(!!t1[r]){
                newTemplate[r] = newTemplate[r].concat(copyCharArray(t1[r]));
            }
            if(!!t2[r]){
                while(newTemplate[r].length < maxWidthT1){
                    newTemplate[r].push({not:false,inCharClass:false,options:["*"],escaped:false});
                }
                newTemplate[r] = newTemplate[r].concat(copyCharArray(t2[r]))
            }
        }else{
            if(!!t2[r]){
                newTemplate[r] = newTemplate[r].concat(copyCharArray(t2[r]));
            }
            if(!!t1[r]){
                while(newTemplate[r].length < maxWidthT2){
                    newTemplate[r].push({not:false,inCharClass:false,options:["*"],escaped:false});
                }
                newTemplate[r] = newTemplate[r].concat(copyCharArray(t1[r]))
            }
        }
    }
    return newTemplate;
}

function copyCharArray(array){
    var newArray = [];
    for(var i = 0; i<array.length;i++){
        newArray.push(copyChar(array[i]));
    }
    return newArray;
}

function mirror(template){
    template = box(template);
    for(var row = 0; row < template.length; row++){
        template[row].reverse();
    }
    return template;
}

function copy(array){
    var newArray = [];
    for(var i=0;i<array.length;i++){
        newArray.push(array[i].slice())
    }
    return newArray;
}

function copy2D(array){
    var newArray = [];
    for(var i=0;i<array.length;i++){
        newArray.push(copy(array[i]));
    }
    return newArray;
}

function matchTemplate(template){
    var result = [];
    for(var y=0;y<template.length;y++){
        result[y]=[];
        for(var x=0;x<template[y].length;x++){
            result[y][x] = template[y][x].options[0];
        }
    }
    return result;
}

//finds the template in the code and returns a template object
function findTemplate(lines,lineNum){
    var start = lineNum;
    while(lineNum < lines.length && lines[lineNum].indexOf(templateChar) > -1){lineNum++}
    var end = lineNum - 1;
    var templateArray = [];
    for(var l = start; l<=end; l++){
        var subArray = [];
        var line = lines[l];
        var started = false;
        for(var i = 0; i<line.length;i++){
            if(started){
                var character = line[i];
                var real = {};
                real.escaped = false;
                real.options = [];
                real.inCharClass = false;
                real.not = false;
                if(character === "["){
                    var content = getCharClass(line,i);
                    if(content.charAt(0) === "^"){
                        real.not = true;
                        real.inCharClass = true;
                        content =  content.substring(1,content.length);
                    }
                    for(var j = 0; j<content.length;j++){
                        real.options.push(content.charAt(j));
                    }
                    i+=content.length+1;
                    if(real.not){i++;}
                }else if(character === "\\"){
                    real.options.push(line[i+1]);
                    real.escaped = true;
                    i++;
                }else{
                    real.options.push(character);
                }
                subArray[subArray.length] = real;
            }
            if(line[i] === templateChar && started === false){started = true;}
        }
        templateArray[templateArray.length] = subArray;
    }
    return templateArray;
}

function getCharClass(line, index){
    var stack = [1];
    var pointer = index;
    var content = "";
    while(stack.length > 0 && pointer < line.length+1){
        pointer++;
        if(line[pointer] === ']'){
            stack.pop();
        }
        if(line[pointer] === '['){
            stack.push(1);
        }
        content+=line[pointer];
    }
    content = content.substring(0,content.length-1);
    return content;
}

function output(object){
    if(object === undefined){
        realOutput("undefined");
    }
    else if(object.type === "template"){
        for(var i = 0; i<object.value.length;i++){
            var result = "";
            result+=templateChar;
            for(var k = 0; k < object.value[i].length;k++){
                result+=object.value[i][k].options[0];
            }
            realOutput(result);
        }
    }else if(object.type === "search"){
        for(var a = 0; a < object.value.length; a++){
            realOutput("[x: "+object.value[a].x+", y: "+object.value[a].y+
                ", match: "+object.value[a].match+"]");
        }
    }else if(object.type === "match"){
        realOutput("x: "+object.value.x+", y: "+object.value.y+
                ", match: "+object.value.match);
    }else if(object.type === "2darray"){
        for(var h = 0; h<object.value.length;h++){
            var temp = ""
            for(var b = 0; b < object.value[h].length; b++){
                temp += object.value[h][b];
            }
            realOutput(temp);
        }
    }else{
        realOutput(object.value);
    }
}

function realOutput(text){
    document.getElementById("output").value += text+"\n";
}
function clearOutput(){
    document.getElementById("output").value = "";
}