Код Гольф: узнайте ascii art коробки - PullRequest
Новая
       32

Код Гольф: узнайте ascii art коробки

13 голосов
/ 10 сентября 2010

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

  • Подойдет любой тривиально конвертируемый формат ввода или вывода (например, char **, список строк, строки на стандартном вводе; список из четырех целых, структура, фиксированное количество +/- для размера;и т.д.).
  • Аналогично, вывод не обязательно должен быть в каком-то определенном порядке.
  • Вам не нужно ничего полезного для неверного ввода или неправильных прямоугольников, но вы не должны создавать корректно выглядящие координаты дляПрямоугольник, которого нет во входных данных.
  • Нет двух действительных прямоугольников с общим + (хотя + может появляться не только как часть прямоугольника)
  • Можно предположить, что все прямоугольники находятся наминимум 3x3: каждая сторона имеет - или |.

Примеры: 

"        "
"  +-+ | "
"  | | \-"
"  +-+   "
(2,1;3,3)

"+--+  +--+"
"|  |  |  |"
"+--+  +--+"
(0,0;4,3), (6,0;4,3)

"  +---+  "
"->|...|  "
"  +---+  "
(2,0;5,3)

"+-+ +--+  +--+"
"| | |  |  |  |"
"+-+ |  |  + -+"
"    |  |      "
"    +--+  +-+ "
"  +--+    |   "
"  +--+    +-+ "
(0,0;3,3), (4,0;4,5) # (2,5;4,2) is fine, but not needed

Ответы [ 10 ]

7 голосов
/ 14 сентября 2010

Perl, 167 165 159 символов

( 156 символов , если вы не учитываете slurping stdin для @a, просто удалите последние 3 символа и назначьтесписок строк, представляющих ваш ввод для @a)

Получает ввод из stdin.Новые строки не значимы, добавлены для удобства чтения.Обратите внимание на использование оператора +++; P 

map{$l=$i++;while($c=/\+-+\+/g){$w=$+[0]-2-($x=$-[0]);
$c++while$a[$l+$c]=~/^.{$x}\|.{$w}\|/;
print"($x,$l;",$w+2,",$c)\n"if$a[$c+++$l]=~/^.{$x}\+-{$w}\+/}}@a=<>

Будьте либеральны в том, что вы принимаете версию, 170 символов 

map{$l=$i++;while($c=/\+-*\+/g){pos=-1+pos;$w=$+[0]-2-($x=$-[0]);
$c++while$a[$l+$c]=~/^.{$x}\|.{$w}\|/;
print"($x,$l;",$w+2,",$c)\n"if$a[$c+++$l]=~/^.{$x}\+-{$w}\+/}}@a=<>

Будьте консервативны в том, что вы принимаете, 177 символов 

map{$l=$i++;while($c=/\+-+\+/g){$w=$+[0]-2-($x=$-[0]);
$c++while$a[$l+$c]=~/^.{$x}\|.{$w}\|/;print
"($x,$l;",$w+2,",$c)\n"if$c>1&&$a[$c+++$l]=~s/^(.{$x})\+(-{$w})\+/$1v$2v/}}@a=<>

Комментируемая версия: 

@a=<>;          # slurp stdin into an array of lines
$l=0;           # start counting lines from zero
map{            # for each line
    while(/\+-+\+/g){               # match all box tops
            $c=1;                           # initialize height

            # x coordinate, width of box - sides
            $w=$+[0]-2-($x=$-[0]);

            # increment height while there are inner parts
            # of a box with x and w coinciding with last top
            # (look into next lines of array)
            $c++  while $a[$l+$c]=~/^.{$x}\|.{$w}\|/;

            # if there is a box bottom on line + height
            # with coinciding x and w, print coords
            # (after incrementing height)
            print "($x,$l;",$w+2,",$c)\n"  
                    if $a[$c+++$l]=~/^.{$x}\+-{$w}\+/
    }
    $l++    # line++
}@a

Мега тестовый кейс: 

+--+  +-+ +-+  +++   +---+   +-+  +-+-+  +-++-+
|SO|  | | | |  +++   |+-+|   | |  | | |  | || |
+--+  +-+-+-+  +++   ||+||   +-+  +-+-+  +-++-+
        | |          |+-+|   | |
      +-+-+-+        +---+   +-+
      | | | |
      +-+ +-+


++ +-+ ++     +-+   +- + +--+ +--+ +--+
|| +-+ ++   +-+-+   |  | |  | |    |  |
++          | |     |  | |  | |  |    |
            +-+     +--+ + -+ +--+ +--+
6 голосов
/ 13 сентября 2010

Perl - 223 222 216

Версия для игры в гольф (новые строки не имеют значения): 

$y=0;sub k{$s=$-[0];"($s,%i;".($+[0]-$s).",%i)"}while(<>){while(/\+-+\+/g){
if(exists$h{&k}){push@o,sprintf k,@{$h{&k}};delete$h{&k}}else{$h{&k}=[$y,2]}}
while(/\|.+?\|/g){++${$h{&k}}[1]if exists$h{&k}}++$y}print"@o\n"

Старая версия для игры в гольф: 

# y starts at line zero.
$y = 0;

# Abuse Perl's dynamic scoping rules
# to get a key for the hash of current rectangles,
# which indexes rectangles by x and width,
# and is also used as a format string.
sub k {

    # The start of the current match.
    $s = $-[0];

    # $+[0] is the end of the current match,
    # so subtract the beginning to get the width.
    "($s,%i;" . ($+[0] - $s) . ",%i)"

}

# Read lines from STDIN.
while (<>) {

    # Get all rectangle tops and bottoms in this line.
    while (/\+-+\+/g) {

        # If line is a bottom:
        if (exists $h{&k}) {

            # Add to output list and remove from current.
            push @o, sprintf k, @{$h{&k}};
            delete $h{&k}

        # If line is a top:
        } else {

            # Add rectangle to current.
            $h{&k} = [$y, 2]

        }

    }

    # Get all rectangle sides in this line.
    while (/\|.+?\|/g) {

        # Increment the height of the corresponding
        # rectangle, if one exists.
        ++${$h{&k}}[1] if exists $h{&k}

    }

    # Keep track of the current line.
    ++$y

}

# Print output.
print join", ",@o

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

   +--+  +--+
|  |  |  |  |
   +--+  +--+

Неправильно выдается высота 2 дляи то и другое.Это связано с тем, что шаблон /\|.+?\|/g начинает поиск с начала строки.У кого-нибудь есть предложения, как это исправить?

6 голосов
/ 11 сентября 2010

Рубин - 306 260 245 228 168 

# 228 chars
g=->(s,u='-'){o=[];s.scan(/\+#{u}+\+/){o<<[$`,$`+$&].map(&:size)};o}
b=t.map{|i|i.split''}.transpose.map{|s|g[s*'','\|']}
(1...t.size).map{|i|i.times{|j|(g[t[i]]&g[t[j]]).map{|x,y|p [x,j,y-x,i-j+1]if(b[x]&b[y-1]&[[j,i+1]])[0]}}}

производит 

[0, 0, 3, 3]
[4, 1, 4, 3]
[10, 3, 3, 3]

для t = 

["+-+       +--+",
"| | +--+  |  |",
"+-+ |  |  + -+",
"    +--+  +-+ ",
"  +--+    | | ",
"  +--+    +-+ "]

Объяснение: 

# function returns info about all inclusions of "+---+" in string
# "  +--+ +-+" -> [[2,5],[7,9]]
g=->(s,u='-'){o=[];s.scan(/\+#{u}+\+/){o<<[$`,$`+$&].map(&:size)};o}

# mapping transposed input with this function
b=t.map{|i|i.split''}.transpose.map{|s|g[s*'','\|']}
# earlier here was also mapping original input, but later was merged with "analyse"

# "analyse"
# take each pair of lines
(1...t.size).map{|i|i.times{|j|
    # find horizontal sides of the same length on the same positions
    (g[t[i]]&g[t[j]]).map{|x,y|
        # make output if there are correct vertical sides
        p [x,j,y-x,i-j+1]if(b[x]&b[y-1]&[[j,i+1]])[0]
    }
}}

# yeah, some strange +/-1 magick included ,.)

И более простое решение на 168 символов! 

t.size.times{|i|t[0].size.times{|j|i.times{|k|j.times{|l|p [l,k,j-l+1,i-k+1]if
t[k..i].map{|m|m[j]+m[l]}*''=~/^\+\+\|+\+\+$/&&t[i][l..j]+t[k][l..j]=~/^(\+-+\+){2}$/}}}}
5 голосов
/ 30 сентября 2010

JavaScript - 156 символов *

Также на http://jsfiddle.net/eR5ee/4/ ( только нажмите ссылку, если используется Firefox или Chrome) или http://jsfiddle.net/eR5ee/5/ (адаптировано для Safariи Opera): 

var A = [
    "+-+ +--+  +--+",
    "| | |  |  |  |",
    "+-+ |  |  + -+",
    "    |  |      ",
    "    +--+  +-+ ",
    "  +--+    |   ",
    "  +--+    +-+ "
    ]; // not counted

for(y=A.length;--y;)for(;m=/\+-*\+/g(A[y]);){
for(w=m[0].length,z=y;A[--z][x=m.index]+A[z][x+w-1]=="||";);
/^\+-*\+$/(A[z].substr(x,w))&&alert([x,z,w,y-z+1])}
  • Исключая символы новой строки и пробельные символы, которые совершенно не нужны.
  • Очевидно, Firefox и Chrome сохраняют последний индекс первого регулярного выражения.Требуется еще четыре символа, чтобы вывести Safari и Opera из бесконечного цикла.Чтобы заставить Internet Explorer работать, понадобилось еще четырнадцать символов, чтобы исправить и вышеперечисленное, и ошибку «Ожидается функция».По-видимому, «... метод exec регулярного выражения может быть вызван ... косвенно (с regexp(str))» (цитируется в документации Mozilla) не относится к IE.

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

Порядок чисел в каждом окне оповещения (что соответствует прямоугольнику): left , top , width , height .Код выдает ошибку, если прямоугольник выходит за пределы вершины, но все необходимые координаты уже выведены (из спецификации: «Вам не нужно ( sic ) ничего полезного для неправильного ввода или неправильных прямоугольников).. ")

Поскольку большинство основных веб-браузеров реализуют тег canvas, в еще нескольких строках кода возможно рисование обнаруженных прямоугольников на экране.http://jsfiddle.net/MquqM/6/ работает во всех браузерах, кроме Internet Explorer и Opera.

Редактирование: устранено ненужное назначение переменных. Редактирование 2: избегайте выдачи ошибок при полностью допустимом вводе (--y вместо y--),уточнить конкретные случаи, код обрабатывает

4 голосов
/ 15 сентября 2010

C ( 204 186 символов) 

    #include<stdio.h>
    char H=7,W=14,*S =
    "+-+ +--+  +--+"
    "| | |  |  |  |"
    "+-+ |  |  + -+"
    "    |  |      "
    "    +--+  +-+ "
    "  +--+    |   "
    "  +--+    +-+ ";
    void main(){
#define F(a,r,t)if(*c==43){while(*(c+=a)==r);t}
char*c,*o,*e=S;while(*(c=e++))
F(1,45,F(W,'|',o=c;F(-1,45,F(-W,'|',c==e-1?
printf("%i,%i %i,%i\n",(c-S)%W,(c-S)/W,(o-c)%W+1,(o-c)/W+1):0;))))
    }

Количество символов - это тело main (). Этот код будет проходить строку с e , пока не достигнет верхнего левого угла потенциального прямоугольника. Затем он проверит края с помощью c и с помощью o , чтобы отследить нижний правый угол.

Вывод программы: 

0,0 3,3
4,0 4,5
2,5 4,2
3 голосов
/ 19 января 2011

Python 2.6 (251 символ)

Я немного опоздал, во всяком случае, повеселился.Python, используя регулярные выражения.Чтобы сохранить оператор print и остаться короче, чем у Fredb219, он ничего не напечатает, если вы запустите его как скрипт, но если в интерпретаторе вводить по одной строке за раз, это покажет результат.Не очень надежный, он не будет обрабатывать вложенные блоки и в большинстве случаев более сложный, чем те, которые дает DavidX.Не закончил тестирование, но я думаю, что он может показывать результаты в неправильном порядке, если происходит что-то «странное». 

import re
l,a,o=s.index("\n")+1,re.finditer,sorted
o(o(set((m.start(),m.end())for m in a(r'\+-* *-*\+',s)for n in a(r'\|.+\|',s)if(m.start()%l,m.end()%l)==(n.start()%l,n.end()%l)if m.start()+l==n.start()or m.start()-l==n.start())),key=lambda x:x[0]%l)

Ввод - одна строка, строки (все одинаковой длины), разделенные новой строкойперсонаж.Результатами являются срезы строк сверху и снизу для каждого «хорошего» прямоугольника, начиная сверху слева.Это также позволяет «сломанные» коробки (то есть с некоторым пространством в середине одной стороны, не без одной целой стороны).Это был просто способ исправить нежелательное поведение, создав много новых побочных эффектов!:-)

ввод: 

>>>s = """+-+ +--+  +--+
| | |  |  |  |
+-+ |  |  + -+
    |  |      
    +--+  +-+ 
  +--+    |   
  +--+    +-+ """

или: 

>>>s = "+-+ +--+  +--+\n| | |  |  |  |\n+-+ |  |  + -+\n    |  |      \n    +--+  +-+ \n  +--+    | \n  +--+    +-+ "

затем: 

>>>import re
>>>l,a,o=s.index("\n")+1,re.finditer,sorted
>>>o(o(set((m.start(),m.end())for m in a(r'\+-* *-*\+',s)for n in a(r'\|.+?\|',s)if(m.start()%l,m.end()%l)==(n.start()%l,n.end()%l)if m.start()+l==n.start()or m.start()-l==n.start())),key=lambda x:x[0]%l)

вывод: 

[(0, 3), (30, 33), (4, 8), (64, 68), (10, 14), (40, 44)]

т. (0,3) верх 1-го ящика (30,33) дно того же ящика, (4,8) верх второго ящика и т. Д.

3 голосов
/ 13 сентября 2010

Python 2.6 - 287 263 254 

a = [
    "+-+ +--+  +--+",
    "| | |  |  |  |",
    "+-+ |  |  + -+",
    "    |  |      ",
    "    +--+  +-+ ",
    "  +--+    |   ",
    "  +--+    +-+ "
    ]

l=len
r=range
w,h=l(a[0]),l(a)
[(x,y,u,v)for x in r(0,w)for y in r(0,h)for u in r(x+2,w)for v in r(y+2,h)if a[y][x]==a[v][x]==a[y][u]==a[v][u]=='+' and a[y][x+1:u]+a[v][x+1:u]=="-"*2*(u-x-1)and l([c for c in r(y+1,v-y)if a[c][x]==a[c][u]=='|'])==v-y-1]

оценивается в: 

[(0, 0, 3, 3), (4, 0, 4, 5)]
3 голосов
/ 11 сентября 2010

Scala 2.8 - 283 273 269 257 

val a = Seq(
    "+-+ +--+  +--+",
    "| | |  |  |  |",
    "+-+ |  |  + -+",
    "    |  |      ",
    "    +--+  +-+ ",
    "  +--+    |   ",
    "  +--+    +-+ "
  )

// begin golf count
val (w,h) = (a(0).size-1,a.size-1)
for (
  x <- 0 to w;
  y <- 0 to h;
  u <- x+2 to w;
  v <- y+2 to h;
  if Set(a(y)(x),a(v)(x),a(y)(u),a(v)(u)) == Set(43)
  && (x+1 to u-1).forall(t => (a(y)(t)<<8|a(v)(t)) == 11565)
  && (y+1 to v-1).forall(t => (a(t)(x)<<8|a(t)(u)) == 31868)
) yield (x,y,u-x+1,v-y+1)
// end golf count

оценивается в: 

Vector((0,0,3,3), (4,0,4,5))

Выражение for соответствует ответу (объект Vector), поэтому я учел только эту часть (удаленные пробелы). Дайте мне знать, если это правильный способ подсчета.

Как это работает

Координаты всех возможных прямоугольников (фактически, только> = 3x3) генерируются выражением for. Эти координаты фильтруются путем поиска +, - и | по краям и углам всех прямоугольников (if часть выражения for).

2 голосов
/ 13 сентября 2010

XQuery (304 символа)

Вот мое решение: 

declare variable $i external;let$w:=string-length($i[1]),$h:=count($i)for$y in 1 to$h,$x in 1 to$w,$w in 2 to$w+1 -$x,$h in 1 to$h where min(for$r in (0,$h),$s in 1 to$h return (matches(substring($i[$y+$r],$x,$w),'^\+-*\+$'),matches(substring($i[$y+$s],$x,$w),'^|.*|$')))return ($x -1,$y -1,$w,$h+1,'')

Вы можете запустить это (с XQSharp ), установив для переменной $iбыть строками ввода 

>XQuery boxes.xq "i=('  +-+','+-+-+','| |  ','+-+  ')" !method=text

2 0 3 2  0 1 3 3

Полагаю, можно утверждать, что declare variable $i external; просто настраивает ввод и поэтому не добавляет к счету, в этом случае 275 символов

2 голосов
/ 10 сентября 2010

F #, 297 символов

Какая-то хромая, но простая. 

let F a=
 for x=0 to Array2D.length1 a-1 do
  for y=0 to Array2D.length2 a-1 do
  if a.[x,y]='+' then
   let mutable i,j=x+1,y+1
   while a.[i,y]<>'+' do i<-i+1
   while a.[x,j]<>'+' do j<-j+1
   printfn"(%d,%d;%d,%d)"x y (i-x+1)(j-y+1)
   a.[i,y]<-' '
   a.[x,j]<-' '
   a.[i,j]<-' '

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

...