Нарисуйте индексированный фрактал

14

Вступление

В этом вызове матрица 2 × 2 индексируется следующим образом:

0 1
2 3

Мы определяем семейство фрактально-подобных паттернов F(L), где список Lдлин nэтих индексов F(L)имеет размер .2n-1 × 2n-1

  • Если L == [], то F(L)это шаблон 1 × 1 #.
  • Если L != [], то F(L)строится следующим образом. Позвольте Pбыть шаблоном, полученным из Lс удаленным первым элементом. Возьмите четыре сетки размера, заполненные точками , и замените индексированную сетку на шаблон . Затем склейте сетки, используя один слой хешей между ними. Вот диаграммы для четырех случаев:2n-1-1 × 2n-1-1.L[0]P#

    L[0]==0  L[0]==1  L[0]==2  L[0]==3
       #...  ...#     ...#...  ...#...
    [P]#...  ...#[P]  ...#...  ...#...
       #...  ...#     ...#...  ...#...
    #######  #######  #######  #######
    ...#...  ...#...     #...  ...#   
    ...#...  ...#...  [P]#...  ...#[P]
    ...#...  ...#...     #...  ...#   
    

пример

Рассмотрим вход L = [2,0]. Начнем с сетки 1 × 1 #и пройдем Lсправа. Самый правый элемент 0, поэтому мы берем четыре копии сетки 1 × 1 ., заменяем первую на #и склеиваем их вместе с хешами. Это приводит к сетке 3 × 3

##.
###
.#.

Следующий элемент 2, поэтому мы берем четыре копии сетки 3 × 3 .s и заменяем третий на сетку выше. Четыре сетки

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

и склеивание их вместе с #s результатов в сетке 7 × 7

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

Это наш окончательный результат.

вход

Ваш вклад представляет собой список Lиндексов 0, 1, 2, 3. Вы можете принять его как список целых чисел или строку цифр. Обратите внимание, что он может быть пустым и содержать дубликаты. ДлинаL не более 5.

Выход

Ваш вывод является шаблоном F(L) в виде строки с разделителями новой строки.

Правила и оценки

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

Контрольные примеры

[]
#

[0]
##.
###
.#.

[3]
.#.
###
.##

[2,0]
...#...
...#...
...#...
#######
##.#...
####...
.#.#...

[1,1]
...#.##
...####
...#.#.
#######
...#...
...#...
...#...

[1,2,0]
.......#...#...
.......#...#...
.......#...#...
.......########
.......###.#...
.......#####...
.......#.#.#...
###############
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......

[3,3,1]
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
###############
.......#...#...
.......#...#...
.......#...#...
.......########
.......#...#.##
.......#...####
.......#...#.#.

[0,1,2,3]
.......#...#...#...............
.......#...#...#...............
.......#...#...#...............
.......#########...............
.......#.#.#...#...............
.......#####...#...............
.......#.###...#...............
################...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
.......#.......#...............
###############################
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............
...............#...............

[0,0,1,2,3]
.......#...#...#...............#...............................
.......#...#...#...............#...............................
.......#...#...#...............#...............................
.......#########...............#...............................
.......#.#.#...#...............#...............................
.......#####...#...............#...............................
.......#.###...#...............#...............................
################...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
.......#.......#...............#...............................
################################...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
...............#...............#...............................
###############################################################
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
...............................#...............................
Zgarb
источник
В вашем примере, почему вы начинаете с сетки 1x1 #? L !=[]в этом примере, поскольку он имеет 1 или более элементов. Означает ли это , что F (L) является всегда# на первом?
Р. Кап
2
@ R.Kap Хорошо, пример не очень понятен. Определение является рекурсивным, поэтому L = [2,0]вы отсекаете голову и смотрите на шаблон F([0]), затем отсекаете голову [0]и смотрите на шаблон F([]), который является сеткой 1x1 #. Затем вы используете отрубленный индекс 0для построения шаблона 3х3, а затем используете отрубленный индекс 2для построения шаблона 7х7. Чтобы ответить на ваш вопрос: да, вы всегда начинаете с сетки 1x1, так как это базовый случай рекурсии.
Згарб

Ответы:

6

CJam, 59 47 43 41 40 байт

Спасибо Sp3000 за сохранение 1 байта.

Sal~W%{_Bff|a4*I@t2/{zSf*z}:F%F}fI3ff+N*

Проверьте это здесь.

объяснение

Немного устарел. Исправлю позже.

Все переупорядочения списков 4D вызывают у меня головокружение ...

Этот код реализует спецификацию в буквальном смысле, используя итерационный алгоритм из раздела примеров вместо его рекурсивного определения. Один из главных трюков игры в гольф заключается в том, что я использую пробелы вместо #вычислений и заменяю их только #в конце, что упрощает код в одном месте и позволяет использовать Sвместо '#или "#"в нескольких.

Sa       e# Push [" "], i.e. a 1x1 grid containing only a space as the
         e# initial fractal.
l~       e# Read and evaluate input.
W%       e# Reverse the list.
{        e# For each list element, assigning the element to variable I...
  _      e#   Duplicate the grid.
  Eff|   e#   Map (OR 14) over each character in the grid, turning spaces into
         e#   periods and leaving periods unchanged.
  a4*    e#   Create an array with four copies of this cleared grid.
  I@t    e#   Replace the Ith element in this list with the previous grid.
  2/     e#   Split this array into a 2x2 grid of subgrids...
         e#   Now it's getting a bit weird... we've got 4 dimensions now, which are:
         e#    - Rows of the 2x2 meta-grid.
         e#    - Cells in each row of the 2x2 meta-grid (i.e. subgrids).
         e#    - Rows of each subgrid.
         e#    - Characters in each row of each subgrid.
  :z     e#   Transpose each outer row, i.e. swap dimensions 2 and 3.
         e#   We've now got in each row of the meta-grid, a list of pairs of
         e#   corresponding rows of the subgrids.
  Sff*   e#   Join those pairs of rows with a single space each. We're now down
         e#   to three dimensions:
         e#    - Rows of the 2x2 meta-grid.
         e#    - Rows of each 1x2 block of the meta-grid.
         e#    - Characters in each row of those blocks.
  :z     e#   Transpose the blocks, i.e. turn the 1x2 blocks into a list of
         e#   columns of their characters.
  z      e#   Transpose the outer grid, i.e. turn it into a list of pairs of
         e#   corresponding columns in the two 1x2 blocks.
  Sf*    e#   Join each pair of columns with a single space. We've now got the
         e#   new grid we're looking for, but it's a list of columns, i.e. transposed.
  z      e#   Fix that by transposing the entire grid once more.
}I
N*       e# Join the rows of the grid with linefeeds.
S'#er    e# Replace all spaces with #.
Мартин Эндер
источник
3

MATL , 42 41 байт

'.#'4:He!XIiP"Iq@=wX*1X@WZ(l5MY(]3Lt3$)Q)

Попробуйте онлайн!

объяснение

Это работает итеративно, используя продукт Kronecker для расширения массива в каждой итерации. Массив построен с 0и 1вместо .и# , и в конце они заменяются соответствующими символами.

Будет столько итераций, сколько и размера ввода. Ввод обрабатывается справа налево. Индекс итерации начинается с1 .

Используя пример в задаче, с вводом [2,0], массив инициализируется как

1 2
3 4

Это соответствует начальному 1(# ), расширенной на одну строку и один столбец, назначение которых будет ясно позже. Значения в этих столбцах не важны, так как они будут перезаписаны; они могут быть одинаково:

1 1
1 1

На каждой итерации существующий массив умножается по Кронекеру на массив 2 × 2 с нулем один, который содержится 1в позиции, указанной текущей записью ввода, и 0в других записях. В примере на итерации i = 1, так как самая правая входная запись0 массив с нулем один

1 0
0 0

и произведение Кронекера этих двух массивов

 1 1 0 0
 1 1 0 0
 0 0 0 0
 0 0 0 0

Далее строка и столбец с индексом 2^i заполняются таковыми:

 1 1 0 0
 1 1 1 1
 0 1 0 0
 0 1 0 0

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

На итерации i = 2, поскольку текущее входное значение содержит 2указанный выше массив, умножается на Кронекера

0 0
1 0

который дает

 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 1 1 0 0 0 0 0 0
 1 1 1 1 0 0 0 0
 0 1 0 0 0 0 0 0
 0 1 0 0 0 0 0 0

Заполнение 2^iстроки и столбца единицами дает

 0 0 0 1 0 0 0 0
 0 0 0 1 0 0 0 0
 0 0 0 1 0 0 0 0
 1 1 1 1 1 1 1 1
 1 1 0 1 0 0 0 0
 1 1 1 1 0 0 0 0
 0 1 0 1 0 0 0 0
 0 1 0 1 0 0 0 0

Поскольку это последняя итерация, лишняя строка и столбец удаляются:

 0 0 0 1 0 0 0
 0 0 0 1 0 0 0
 0 0 0 1 0 0 0
 1 1 1 1 1 1 1
 1 1 0 1 0 0 0
 1 1 1 1 0 0 0
 0 1 0 1 0 0 0

и замена символов выполняется для получения окончательного результата:

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

Подробное описание кода приведено ниже:

'.#'      % Push this string. Will be indexed into
4:He!     % Push 2×2 array [1 2; 3 4]
XI        % Copy it into clipboard I
iP        % Input array and reverse it
"         % For each entry of the reversed input
  I       %   Push [1 2; 3 4] from clipboard I
  q       %   Subtract 1 to yield [0 1; 2 3]
  @=      %   Compare with current entry of the input. Gives 2×2 array
          %   with an entry equal to `1` and the rest `0`
  wX*     %   Swap. Kronecker product
  1       %   Push 1
  X@      %   Push iteration index, i
  W       %   Compute 2^i
  Z(      %   Write 1 into column 2^i
  l       %   Push 1
  5M      %   Push 2^i again
  Y(      %   Write 1 into row 2^i
]         % End for each
3Lt       % Push [1, -1j] (corresponding to index 1:end-1) twice
3$)       % Apply index. Removes last row and column
Q         % Add 1. Gives an array of values 1 and 2
)         % Index into initial string
Луис Мендо
источник
2

Haskell, 123 122 байта

unlines.foldr(#)["#"]
n#p=zipWith(++)(r++h:t)$('#':)<$>u++h:s where b='.'<$p<$p;h='#'<$p;(r:s:t:u:_)=drop n$cycle[p,b,b,b]

Пример использования:

*Main> putStr $ (unlines.foldr(#)["#"]) [2,3,1]
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
###############
...#...#.......
...#...#.......
...#...#.......
########.......
...#.###.......
...#####.......
...#.#.#.......

Как это устроено:

                ["#"]      -- starting with "#" 
        foldr(#)           -- fold the function # from the right into the input
unlines                    -- and join the result with newlines

n#p=                       -- helper function #
                           -- n: next index, p: fractal so far
    zipWith(++)            -- join the left and right part elementwise
       (r++h:t)            -- left part
       ('#':) <$> u++h:s   -- right part (prepend '#' to each line for vertical
                           -- separator

                           -- helper
b='.'<$p<$p                -- b is a blank square of the same size as p
h='#'<$p                   -- h is a line of '#' of the same length as p
(r:s:t:u:_)=               -- drop the first n elements of the infinite
    drop n$cycle[p,b,b,b]  --   list [p,b,b,b,p,b,b,b,p,b,b,b,...] and
                           --   assign the next 4 element to r,s,t,u.
                           --   As r,s,t,u are always inserted at the
                           --   same position in the fractal, we get the
                           --   variants by assigning different values.
Ними
источник
1

JavaScript (ES6), 171 152 байта

([d,...a],h=`#`,r=`replace`)=>d<4?(s=f(a)[r](/.+/g,s=>(t=s[r](/./g,`.`),d&1?t+h+s:s+h+t)),t=s[r](/.+/g,w=t+h+t),w=`
${w[r](/./g,h)}
`,d&2?t+w+s:s+w+t):h

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

Нил
источник
1

Рубин, 143 134 байта

Анонимная функция.

1 байт, сохраненный перестановкой первой строки. 6 байтов сохраняются путем изменения пути z от формулы к таблице. 2 байта сохранены за счет исключения varable w.

->a{r=-1+u=2<<a.size
s=(?.*r+$/)*r
a<<0
z=r*u/2-1
a.each{|i|r/=2
(-r..r).each{|j|s[z+j]=s[z+j*u]=?#}
z+=-r/2*[u+1,u-1,1-u,-u-1][i]}
s}

Неуправляемый в тестовой программе

f=->a{
  r=w=(u=2<<a.size)-1        #w=length of line excluding newline, u=length of line including newline.
  s=(?.*w+$/)*w              #initialize string s with w rows of w dots terminated by newlines.
  z=w*u/2-1                  #z is the centre of the fractal
  a<<0                       #add a dummy value to the end of a
  a.each{|i|                 #for each element in a
    r/=2                     #r is the radius of the current iteration: ....15,7,3,1
    (-r..r).each{|j|         #for j=-r to r
      s[z+j]=s[z+j*u]=?#     #overwrite . with #, forming horizontal and vertical lines
    }
    z+=-r/2*(u+1)+           #move z to centre of upper left quarter (where it should be if i=0)
      i%2*(q=r+1)+           #move across if i=1,3
      i/2%2*q*u              #and down if i=2,3  
  }
s}                           #return string

puts $/,f[[]]

puts $/,f[[0]]

puts $/,f[[3]]

puts $/,f[[2,0]]

puts $/,f[[1,1]]

puts $/,f[[1,2,0]]

puts $/,f[[3,3,1]]

puts $/,f[[0,1,2,3]]

puts $/,f[[0,0,1,2,3]]
Уровень реки St
источник
0

Рубин, 150 байт

Анонимная функция. Использует рекурсивный вызов для создания списка строк, по одной строке на строку, а затем соединяет их все вместе в конце.

->i{f=->l{s=2**l.size-1;g=[[?.*s]*s]*4;m=->x,y{x.zip(y).map{|a,b|a+?#+b}}
s<1?[?#]:(g[l.shift]=f[l];m[*g[0,2]]+[?#*(2*s+1)]+m[*g[2,2]])}
f[i].join"
"}
Значение чернил
источник
0

Python 3.5, 1151 байт:

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

def x(s):
 y=[''];l=['#'];k=[' ']
 for z in s[::-1]:y.append(z)
 y=y[::-1]
 for h in range(len(y)):
  if y[-1]!='':u=(int(y.pop())&3)
  else:u=y.pop()
  if len(l)<2:k.append(u);p=((2**(len(k)-1))-1);l.append((('.'*p+'#'+'.'*p+'\n')*p)+'#'*((p*2)+1)+'\n'+(('.'*p+'#'+'.'*p+'\n')*p))
  else:
   if len(l)>2:del l[0]
   p=((2**(len(k)-1))-1);a=[[_+i for i in range(p)]for _ in range(len(l[1]))if _%((p*2)+2)==0 and _!=(((p*2)+2)*(p))];b=[[_+i for i in range(p)]for _ in range(len(l[1]))if _%(int(((p*2)+2)/2))==0 and _!=(int(((p*2)+2)/2)*((p)*2))and _ not in[g for i in a for g in i]];W=[g for i in a[:len(a)-(int(len(a)/2)):1]for g in i];B=[g for i in b[:len(b)-(int(len(b)/2)):1]for g in i];C=[g for i in a[len(a)-(int(len(a)/2)):len(a):1]for g in i];T=[g for i in b[len(b)-(int(len(b)/2)):len(b):1]for g in i];f=list(l[1])
   for i in list(''.join(l[0].split())):
    if u==0:f[W[0]]=i;del W[0]
    elif u==1:f[B[0]]=i;del B[0]
    elif u==2:f[C[0]]=i;del C[0]
    elif u==3:f[T[0]]=i;del T[0]
   del l[0];k.append(u);p=((2**(len(k)-1))-1);l.append(''.join(f));l.append((('.'*p+'#'+'.'*p+'\n')*p)+'#'*((p*2)+1)+'\n'+(('.'*p+'#'+'.'*p+'\n')*p))
 print(l[-2])

Довольно наивный способ сделать это, но, тем не менее, в настоящее время работает отлично и, как вы можете видеть, не использует никаких внешних модулей / библиотек. Кроме того, он может взять на пути более чем на 5 пунктов в предоставленном списке sбез потери точности (то есть, если ваше оборудование может справиться с этим). Он удовлетворяет всем требованиям, и я не мог быть счастливее с тем, что получил. :)

Теперь он может принимать не только любое число в диапазоне в 0=>3качестве любого из значений, но и любое число , период, благодаря &побитовому оператору! Вы можете прочитать больше о них здесь . Теперь, например, так [4,4,1,2,3]как список ввода такой же, как [0,0,1,2,3].

Примечание: ввод должен быть представлен в виде списка

Разгромленный с объяснением:

def x(s):
 # Create 3 lists:
 # `y` is for the values of `s` (the list provided) and an empty element for the 
 # first pattern
 # `l` is reserved for the pattersn created through each item in list `y`
 # `k` is created for the value of `p` which is the main value through which the 
 # pattern is created.
 y=[''];l=['#'];k=[' ']
 # Reverse s, and then add each element from `s` to `y` 
 # (in addition to the empty element) 
 for z in s[::-1]:
     y.append(z)
 # `y` should now equal the list created, but reversed
 # If not reversed, then, if, for instance, the input is `0,1,2` and list `y` 
 # therefore contains `'',2,1,0`, the empty element will be called at the end, 
 # which is NOT what we want.
 y=y[::-1]
 # The main loop; will be iterated through the length of `y` number of times
 for h in range(len(y)):
  # Here is where each element from the end of `y` is recieved as `u` for 
  # use in the pattern in each iteration.
  # As you can also see, a bitwise operator (`&`) is used here so that 
  # ALL numbers can be accepted. Not just those in the range `0-4`.     
  # However, that will happen only if the value of y[-1] (the last elment in y) is 
  # NOT ''.
  if y[-1]!='':
      u=(int(y.pop())&3)
  else:
      u=y.pop()
  # If the length of list `l` is less than 2 
  # (which means it only contains `#`), then do the following:
  if len(l)<2:
      # Append `u` to `k`
      k.append(u)
      # Use the length of `k` as `n` in the operation `(2^(n-1)-1)` to get the 
      # length of the dot filled part of the new pattern.
      p=((2**(len(k)-1))-1)
      # Add that pattern to the list (currently empty, 
      # i.e. containing no other pattern in any other quadrant)
      l.append((('.'*p+'#'+'.'*p+'\n')*p)+'#'*((p*2)+1)+'\n'+(('.'*p+'#'+'.'*p+'\n')*p))
  # Now, if the length of l is >=2, do the following:
  else:
   # If the length of l is >2, then delete the first element in list `l` 
   # (this will happen only once, when the `#` is still the first element)
   if len(l)>2:
       del l[0]
   # Again, use the length of `k` as `n` in the operation `(2^(n-1)-1)`
   # to get the length of the dot filled part of the pattern.
   p=((2**(len(k)-1))-1)
   # Create a list with all the index values of all the dot elements on the left hand 
   # side of the grid l[-1], and the index value + i where i is every integer in 
   # the range `0-p` (this way, it will create lists within a list, each 
   # which contain `p` number of integers, which are all indexes of all the dots on 
   # the very left side of the grid) 
   a=[[_+i for i in range(p)]for _ in range(len(l[1]))if _%((p
      *2)+2)==0 and _!=(((p*2)+2)*(p))]
   # Create another list with all the index values of the dots using the same 
   # strategy as above, but this time, those in the right half of the grid. 
   b=[[_+i for i in range(p)]for _ in range(len(l[1]))if _%(int(((p*2)+2)/2))==0 
      and _!=(int(((p*2)+2)/2)*((p)*2))and _ not in[g for i in a for g in i]]
   # Create 4 lists, each containing index values specific to each of the 
   # 4 quadrants of the grid.
   # W is the list, based on A, containing all the indexes for the 1st quadrant of 
   # the grid in l[-1] containing dots (index 0 in the grid)
   W=[g for i in a[:len(a)-(int(len(a)/2)):1]for g in i]
   # B is the list, this time based on b, containing all indexes for the 2nd 
   # dot-filled quadrant of the grid l[-1] (index 1 in the grid)
   B=[g for i in b[:len(b)-(int(len(b)/2)):1]for g in i]
   # C is the list, also, like W, based on a, containg all the index values for 
   # the 3rd dot-filled quadrant of the grid in l[-1] (index 2 in the grid)
   C=[g for i in a[len(a)-(int(len(a)/2)):len(a):1]for g in i]
   # T is the final list, which, also like B, is based on b, and contains all the 
   # index values for the final (4th) dot-filled quadrant of the grid in l[-1] 
   T=[g for i in b[len(b)-(int(len(b)/2)):len(b):1]for g in i];f=list(l[1])
   # Finally, in this `for` loop, utilize all the above lists to create the new 
   # pattern, using the last two elements in list `l`, where each character of grid 
   # l[-2] (the second to last element) is added to the correct index of grid l[-1] 
   # based on the value of `u`
   for i in list(''.join(l[0].split())):
    if u==0:
        f[W[0]]=i
        del W[0]
    elif u==1:
        f[B[0]]=i
        del B[0]
    elif u==2:
        f[C[0]]=i
        del C[0]
    elif u==3:
        f[T[0]]=i
        del T[0]
   # Delete the very first element of `l`, as it is now not needed anymore
   del l[0]
   # Append `u` to list`k` at the end of the loop this time
   k.append(u)
   # Update the value of `p` with the new value of length(k)
   p=((2**(len(k)-1))-1)
   # Append the new patter created from the for-loop above to list `l`
   l.append(''.join(f))
   # Append a new, empty pattern to list `l` for use in the next iteration
   l.append((('.'*p+'#'+'.'*p+'\n')*p)+'#'*((p*2)+1)+'\n'+(('.'*p+'#'+'.'*p+'\n')*p))
 # When the above main loop is all finished, print out the second-to-last elment in 
 # list `l` as the very last element is the new, empty grid created just in case 
 # there is another iteration
 print(l[-2])

Более широкое и визуально привлекательное объяснение:

Для более широкого и визуально привлекательного объяснения рассмотрим второй раз, когда проходим через «главный» цикл в приведенном выше коде, в котором находится входной список [0,2]. В этом случае элементы в «основном» списке lбудут:

.#.
###
##.

и

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

и список yбудет содержать только 0. Используя преимущества индексации последнего элемента сетки в Python l[-1], мы можем пометить самые левые элементы сетки следующим образом:

 0 ...#...\n 7        
 8 ...#...\n 15
16 ...#...\n 23
   #######\n <- Ignore this as it is nothing but `#`s and a new line
32 ...#...\n 39
40 ...#...\n 47
48 ...#...\n 55

Какой шаблон вы видите? Каждый индекс в левой части сетки кратен 8, и, поскольку, используя уравнение, 2^(n-1)-1дает длину каждого сегмента точек в сетке, мы можем ((2^(n-1)-1)*2)+2найти длину верхнего края сетки в целом. (+2, чтобы включить середину #и \nв конце). Мы можем использовать это уравнение, которое мы будем вызывать, iчтобы найти значения индекса каждого элемента в левой части сетки любого размера, создав список и добавив в список каждое целое число, которое мы будем называть _, в диапазоне 0=>length of grid l[-1], такой, что этот элемент является кратным i, И также таким, _который НЕ равен i*(2^(n-1)-1), так что мы можем исключить средний сегмент#s отделяет верхнюю половину от нижней. Но нам нужны ВСЕ элементы с точками слева, а не только элементы с левой стороны. Что ж, есть исправление, и это было бы просто добавить в список список, содержащий i+hгде h - каждое целое число в диапазоне 0=>2^(n-1)каждый раз, когда значение из диапазона 0=>length of grid l[-1]добавляется в список, так что каждый раз будет столько же значений, добавленных в список, сколько длина одного квадранта точек. И это список a.

Но как насчет точек на правой половине? Что ж, давайте посмотрим на индексацию по-другому:

   0 ...# 4  ...\n 7        
   8 ...# 12 ...\n 15
  16 ...# 20 ...\n 23
     #######\n <- Ignore this as it is nothing but `#`s and a new line
  32 ...# 36 ...\n 39
  40 ...# 44 ...\n 47
  48 ...# 52 ...\n 55

          ^
          | 

          These are the values we are looking at now

Как видите, значения в середине - это те, которые нам нужны, так как они являются началом индекса каждого сегмента точек в правой части сетки. Теперь, что здесь за образец? Ну, если это уже недостаточно очевидно, то теперь все средние значения кратны i/2! Имея эту информацию, мы теперь можем создать другой список, bк которому умножаются i/2множители из диапазона 0=>length of grid l[-1], так что каждое целое число из этого диапазона, которое мы снова назовем _, НЕ равно (i/2)*(p*2)исключению строки# s, отделяющей верхнюю часть и нижние половины, И такие, что _ уже нет в списке a, так как нам действительно не нужны 8,16,32 и т. д. в спискеb, И теперь, опять же, нам нужны не только эти конкретные индексы. Мы хотим, чтобы ВСЕ символы точек были на правой стороне сетки. Ну, так же, как мы сделали в списке a, здесь мы также можем добавить в список, где находится каждое целое число в диапазоне .b списки,_+hh0=>2^(n-1)

Теперь у нас есть оба списка aи bупакованы и готовы к работе. Как бы мы собрали их сейчас? Здесь списки W, T, Gи Cвходите. Они будут держать индексы для каждого конкретного квадранта точек в сетке l[-1]. Например, давайте зарезервируем list Wкак список для всех индексов, равных квадранту 1 (index 0) сетки. В этом списке мы добавили бы первые 2^(n-1)списки из списка a, так как список aсодержит все индексы для точек в левой половине сетки, а затем разделили их все так, чтобы Wтеперь они содержали (2^(n-1))*(2^(n-1))элементы. Мы сделали бы то же самое для списка T, но с той разницей, Tчто содержали бы элементы из спискаb , так какTзарезервирован для квадранта 2 (индекс 1). Список Gбудет таким же, как список W, за исключением того, что он будет содержать остальные элементы из списка a, а список Cбудет таким же, как список T, за исключением того, что теперь он содержит остальные элементы из списка b. Вот и все! Теперь у нас есть значения индекса для каждого квадранта, содержащего точки в сетке, все разделены на четыре списка, соответствующих каждому квадранту. Теперь мы можем использовать эти 4 списка (W, T, G, C), чтобы сообщить программе, какие символы следует заменить в сетке l[-1]каждым символом из сетки l[0], которая является самым первым элементом списка l. Поскольку значение 0здесь, оно заменит все точки в первом квадранте (индекс 0) l[0]списком использования сеткиW,

Поэтому мы наконец имеем следующее:

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

Уф! Долгий процесс, не правда ли? Тем не менее, он работает отлично, и, опять же, я не мог быть счастливее. :)

Р. Кап
источник