Страницы

Поиск по вопросам

понедельник, 25 ноября 2019 г.

Обход двумерного массива спиралью по часовой стрелке 


Задача соревнования:

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





Пример 4x4:

На входе есть двумерный массив:

entryArray = [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]]


На выходе одномерный массив после обхода:

exitArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


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



Определение победителей:

Победитель будет определен по следующим параметрам:


Наименьшее количество символов кода
Количество голосов 
Не более 2 правок после первого данного ответа


Ответ автора не учитывается при выборе победителя. 

Победитель определится через 2 недели (26 октября). 

Просьба указывать язык в заголовке ответа и количество символов минифицированно
функции через запятую.



Хотелось бы увидеть решения на Ruby, Haskell, Scala и до бесконечности.
Большое спасибо за вашу активность!



Вывод победителей:



execute("ru.stackoverflow.com", "892196");
.cssload-container,.cssload-cube{width:97px;height:97px;transform-style:preserve-3d}.cssload-container,.cssload-cube,.cssload-half1,.cssload-half2{transform-style:preserve-3d}.cssload-container{position:relative;margin:23p
84px;perspective:292px}.cssload-cube{animation:cube 11.5s forwards infinite;transform-origin:cente
49px}.cssload-half1,.cssload-s1{top:0;transform-origin:50% 100%}.cssload-half1{height:39px;position:absolute;animation:half-fol
11.5s forwards infinite}.cssload-side{width:19px;height:19px;background:#ddd;position:absolute}.cssload-s1{left:39px;animation:s1an
11.5s forwards infinite}.cssload-s2,.cssload-s3,.cssload-s4{left:39px;transform-origin:50
0}.cssload-s2{top:19px;animation:s2ani 11.5s forwards infinite}.cssload-s3{top:39px;animation:s3an
11.5s forwards infinite}.cssload-s4{top:58px;animation:s4ani 11.5s forwards infinite}.cssload-s5{left:19px;top:19px;transform-origin:100
50%;animation:s5ani 11.5s forwards infinite}.cssload-s6{left:58px;top:39px;transform-origin:
50%;animation:s6ani 11.5s forwards infinite}@keyframes cube{0%,30%{transform:rotateX(0)}40%{transform:rotateX(45deg
rotateY(0) rotate(45deg)}60%{transform:rotateX(60deg) rotateY(0) rotate(45deg)}65%,70%{transform:rotateX(60deg
rotate(45deg) rotate(180deg)}75%,80%{transform:rotateX(60deg) rotate(45deg) rotate(1turn)}90%{transform:rotateX(0
rotate(0) rotate(0)}}@keyframes s1ani{0%{opacity:1;transform:translateY(0);background:#ddd}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(-90deg);background:#ddd}90%{transform:rotateX(-90deg)}}@keyframes s2ani{0%{opacity:0;transform:rotateX(-179deg)}10%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%,80%{background:#b4b4b4}65%{opacity:1;background:#b4b4b4}90%{opacity:1}to{opacity:0}}@keyframes s3ani{0%,10%{opacity:0;transform:rotateX(-179deg)}20%,90%{opacity:1;transform:rotateX(0)}40%{background:#ddd}45%{background:#969696}to{opacity:0}}@keyframes s4ani{0%,20%{opacity:0;transform:rotateX(-179deg)}10%,to{opacity:0}30%{opacity:1;transform:rotateX(0)}40%{transform:rotateX(0);background:#ddd}50%{transform:rotateX(90deg);background:#b4b4b4}80%{background:#b4b4b4}90%{opacity:1;transform:rotateX(90deg)}}@keyframes s5ani{0%,10%{opacity:0;transform:rotateY(-179deg)}20%{opacity:1;background:#ddd;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(90deg)}55%{background:#ddd}60%{background:#c8c8c8}90%{transform:rotateY(90deg);opacity:1}to{opacity:0}}@keyframes s6ani{0%,20%{opacity:0;transform:rotateY(179deg)}30%{opacity:1;transform:rotateY(0)}40%{transform:rotateY(0)}50%{transform:rotateY(-90deg);background:#ddd}60%,80%{background:#c8c8c8}90%{opacity:1;transform:rotateY(-90deg)}to{opacity:0}}@keyframes half-fold{0%,50%{transform:rotateX(0)}60%,90%{transform:rotateX(-90deg)}}
Итоги соревнования: 1 место Андрей NOP с ответом на Haskell в 40 байт 2 место Yauhen с ответом на Ruby в 59 байт 3 место Let's say Pie с ответом на JavaScript в 81 байт Всем большое спасибо за участие, все замечания будут учтены для последующих конкурсов.


Ответы

Ответ 1


Haskell, 40

s[]=[];s(h:t)=h++(s$reverse$transpose t)


Решение эксплуатирует всё ту же идею отрезания первой строки от матрицы и поворота оставшегося куска против часовой стрелки.

https://ideone.com/FHeJAx


Ответ 2


Python, 88 65 60

f=lambda m:m and m.pop(0)+f([list(x)for x in zip(*m)][::-1])


Первый раз пишу на Python, поэтому пока не знаю приемов для сокращения (длины) кода.

Возникла следующая идея: берем матрицу, отрезаем от нее первую строку, оставшуюс
часть поворачиваем против часовой стрелки на 90 градусов и рекурсивно применяем этот же алгоритм. В итоге потребовалось лишь выбрать ЯП, умеющий такие операции из коробки, им оказался Python ¯\_(ツ)_/¯

https://ideone.com/5qasui

Бонусом — алгоритм работает с любыми прямоугольными матрицами (не только с квадратными).


Ответ 3


Из-за этого, гм... требования "кто меньше" рождаются вот такие монстры...

C++, 155 байт

232 байта

#define c(i,j) )std::cout<>;void s(M&m,int h){int i,n=m.size(),k=n-h-1;if(n>2*h){for(i=h;i<=k;c(h,i++)for(i=h+1;i<=k;c(i++,k)for(i=k-1;i>=h;c(k,i--)for(i=k-1;i>h;c(i--,h)s(m,h+1);}}


Если разрешить (и не считать) достаточно стандартное 

using namespace std;


то получим 217 байт...

Вот тест для четного и нечетного N: https://ideone.com/OEHTLS

Если надо именно запихнуть в массив - на 14 байт больше:

#define c(i,j) )v.push_back(m[i][j]);
using V=std::vector;
using M=std::vector;void s(M&m,V&v,int h){int i,n=m.size(),k=n-h-1;if(n>2*h){for(i=h;i<=k;c(h,i++)for(i=h+1;i<=k;c(i++,k)for(i=k-1;i>=h;c(k,i--)for(i=k-1;i>h;c(i--,h)s(m,v,h+1);}}


Первое дозволенное изменение :) для запихивания в массив

230 байт 

#define c(k,r,c) for(i=0;i;void s(std::vector&m,V&v,int h){int r=h,c=h,i,n=m.size(),k=n-2*h-1;if(!k)c(1,r,c)else if(k>0){c(k,r,c++)c(k,r++,c)c(k,r,c--)c(k,r--,c)s(m,v,h+1);}}


Проверка - https://ideone.com/86YkY4

Второе дозволенное изменение

Как с оптимизацией - менять надо алгоритм. Меняем... получаем 196 байт. 

using V=std::vector;void s(std::vector&m,V&v,int n,int h){int r=h,c=h,i=0,j,l=n-2*h-1;if(l>-1){do{v.push_back(m[r][c]);l?(j=i/l)<1?c++:j<2?r++:j<3?c--:r--:l;}while(++i<4*l);s(m,v,n,h+1);}}


https://ideone.com/rDXdbh

Но менять-то можно не только алгоритм, но и используемую структуру данных! Перейде
к int**, благо условие задачи ничего не говорит о том, как именно следует создавать массив. Тогда мы получаем окончательное решение в 155 байт

void s(int**m,int*v,int n,int h){int r=h,c=h,i=0,j,l=n-2*h-1;if(l>-1){do{*v++=m[r][c];l?(j=i/l)<1?c++:j<2?r++:j<3?c--:r--:l;}while(++i<4*l);s(m,v,n,h+1);}}


https://ideone.com/vukXQG

для которого просто надо готовить входной массив несколько иначе.

На этом, пожалуй, и остановимся.

P.S. Вообще-то в таких соревнованиях нужны какие-то иные правила... Потому что одн
дело - писать алгоритм с нуля и другое, немного утрируя - вызвать готовую библиотечную функцию. Или использовать более "краткий" язык - опять же, утрируя, представим язык, в котором инкремент выглядит исключительно как summation(a,1) и никак иначе :(


Ответ 4


Python 2, 60 59 байт

Решил разбавить немного python'ом. 

Логика как у @Андрей NOP, но код короче:

def f(a):return list(a[0])+f(zip(*a[1:])[::-1])if a else []




Подтверждение:

https://ideone.com/4Xmy7W



Небольшое добавление:

Пример выше реализован для Python второй версии. Для того чтобы функция работал
должным образом в 3 версии нужно обернуть zip в list: list(zip(...)). Разница в том, что во второй версии zip возвращает список, а в третьей возвращает итерируемый объект.


Ответ 5


JS, 125 символов

function f(a){for(var b=[];a.length;)b.push(...a.shift()),a.map(c=>b.push(c.pop())),a.reverse().map(c=>c.reverse());return b}




Доказательство корректности:



function spiralRound(entryArray) {
  var exitArray = [];
  //Повторяем действие пока entryArray не останентся пустым
  while (entryArray.length) {
    //Добавление в exitArray первого вложенного массива из entryArray. 
    //shift() возвращает первый вложенный массив и удаляет его из entryArray.
    exitArray.push(...entryArray.shift());
 
    //Добавляем в exitArray каждый последний элемент из каждого оставщегося массива в entryArray.
    //pop() возвращает последний элемент массива и удаляет его из исходного 
    entryArray.map(row => exitArray.push(row.pop()));
 
    //Разворачиваем оставщийся массив на 180 градусов
    entryArray.reverse().map(row => row.reverse());
  }
  //Возвращаем результат
  return exitArray;
}

let testArray = [];
console.log("0x0:" + spiralRound(testArray));

testArray = [
  [1]
];
console.log("1x1:" + spiralRound(testArray));

testArray = [
  [1, 2],
  [3, 4]
];
console.log("2x2:" + spiralRound(testArray));

testArray = [
  [1, 2, 3, 4],
  [12, 13, 14, 5],
  [11, 16, 15, 6],
  [10, 9, 8, 7]
]
console.log("4x4:" + spiralRound(testArray));

testArray = [
  [1, 2, 3, 4, 12, 13, 14, 5, 7, 8],
  [1, 2, 3, 4, 12, 13, 14, 5, 7, 8],
  [1, 2, 3, 4, 12, 13, 14, 5, 7, 8],
  [1, 2, 3, 4, 12, 13, 14, 5, 7, 8],
  [1, 2, 3, 4, 12, 13, 14, 5, 7, 8],
  [1, 2, 3, 4, 12, 13, 14, 5, 7, 8],
  [1, 2, 3, 4, 12, 13, 14, 5, 7, 8],
  [1, 2, 3, 4, 12, 13, 14, 5, 7, 8],
  [1, 2, 3, 4, 12, 13, 14, 5, 7, 8],
  [1, 2, 3, 4, 12, 13, 14, 5, 7, 8],
]
console.log("10x10:" + spiralRound(testArray));


Ответ 6


Ruby, 61 59

def f(a) a.empty? ? [] : a.shift+f(a.transpose.reverse) end


https://ideone.com/SYmf7W


Ответ 7


C#, 320 280

static int[]f(int[,]a){var r=new List();var n=a.GetLength(0);int j=-1,i=0;boo
h=true;bool d=false;int c=0;int p=n;int max=n;for(var cnt=1;cnt<=a.Length;cnt++){i=h?i:!d?++i:--i;j=!h?j:!d?++j:--j;p--;r.Add(a[i,j]);if(p<=0){h=!h;if((c+1)%2==0){d=!d;}if(cnt==n||c>1&&(c+1)%2!=0){--max;}p=max;c++;}}return r.ToArray();}


Потестить можно вот тут на deck.net



int[]F(int[,]a){var n=a.GetLength(0);var r=new int[n*n];int j=-1,i=0;var h=true;va
d=!h;int o=0;int p=n;intm=n;for(varc=1;c<=a.Length;c++){p--;r[c-1]=a[h?i:!d?++i:--i,!h?j:!d?++j:--j];if(p<=0&&a.Length!=2){h=!h;if((o+1)%2==0)d=!d;if(c==n||o>1&&(o+1)%2!=0)--m;p=m;o++;}}return r;}


Внес небольшие исправления не меняя алгоритм, что бы уменьшить длину кода

Потестить можно вот тут на deck.net



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

Вроде бы, это должно быть эффективно нежеле алгоритмы, через повороты матриц, которые ИМХО будут не так эффективны на больших матрицах.


Ответ 8


PHP 7.4, 124

$f=fn($a,$f)=>$a?[...array_shift($a),...$f(array_reverse($a?next($a)?array_map(null,...$a):array_chunk($a[0],1):$a),$f)]:$a;


https://3v4l.org/JDGfH


Ответ 9


JS, 133 байта (125 если допустимо убрать let)

let f=e=>{let t=[],f=r=0,h=-1,n=l=e[0].length;for(;n;)f?f<2?r++:f<3?h--:r--:h++,t.push(e[r][h]),--l||(f%2||n--,f=++f%4,l=n);return t}


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

Тесты прилагаются; для N от 0 до 4.



let f = a => {
  let
  R = [], // result

  // directions
  // 0 - right
  // 1 - down
  // 2 - left
  // 3 - up
  d =

  r = 0, // row (y)
  c = -1, // col (x)

  L = // row (col) length
  l = // local length
  a[0].length;

  for (;L;) { // while (L) {
    !d    ? c++ : // if (d === 0) { c++; }
    d < 2 ? r++ : // else if (d === 1) { r++; }
    d < 3 ? c-- : // else if (d === 2) { c--; }
    r--;          // else { r--; }

    R.push(a[r][c]);

    --l || (        // if (--l === 0) {
      d % 2 || L--, //   if (d === 0 || d === 2) { L--; }
      d = ++d % 4,  //   if (++d > 3) { d = 0; }
      l = L
    )               // }
  }

  return R;
};


let tests = [];
tests.push(
  [
    [[]],
    []
  ]
);
tests.push(
  [
    [[1]],
    [1]
  ]
);
tests.push(
  [
    [
      [1, 2],
      [4, 3]
    ],
    [1, 2, 3, 4]
  ]
);
tests.push(
  [
    [
      ["a", "b"],
      ["d", "c"]
    ],
    ["a", "b", "c", "d"]
  ]
);
tests.push(
  [
    [
      [1, 2, 3],
      [8, 9, 4],
      [7, 6, 5]
    ],
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
  ]
);
tests.push(
  [
    [
      [ 1,  2,  3, 4],
      [12, 13, 14, 5],
      [11, 16, 15, 6],
      [10,  9,  8, 7]
    ],
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
  ]
);

for (let expected, actual, i = 0; i < tests.length; i++) {
  expected = tests[i][1].join(", ");
  actual = f(tests[i][0]).join(", ");
  if (expected === actual) {
    console.log(`${i}: OK`);
  } else {
    console.log(`${i}: FAIL`);
    console.log(`expected: [${expected}]`);
    console.log(`actual: [${actual}]`);
  }
}


Ответ 10


C, 193 191 178 175 байт

int f(int n,int a[][n],int*b){int d=0,j=0,k=0,s=0,m=n-1,f=0;for(int i=0;i
Ответ 11


JS, 121 107 81

f=b=>b[0]?[...b.shift(),...f(b[0]?b[0].map((d,e)=>b.map(g=>g[e])).reverse():b)]:b


Правка без изменения алгоритма, с  учетом замечаний и предложений @Андрей NOP. Функцию переделал в лямбду, а также заменил b.length на b[0], и [] заменил на b.

Демо:



f = b => b[0] 
    ? [...b.shift(), ...f(b[0] ? b[0].map((d, e) => b.map(g => g[e])).reverse() : b)] 
    : b

console.log([
    [], 
    [[1]], 
    [[1, 2], [4, 3]], 
    [[1, 2, 3], [8, 9, 4], [7, 6, 5]], 
    [[1, 2, 3, 4], [12, 13, 14, 5], [11, 16, 15, 6], [10, 9, 8, 7]], 
    [[1, 2, 3, 4], [10, 11, 12, 5],[9, 8, 7, 6]] 
].map(f))


Ответ 12


Java, 300

Сделано по первому алгоритму из моего ответа, оставленного ранее.

static int[] f(int a[][]){int i,d=0,k=0,l=0,n=a[0].length,m=a.length;int[]r=new int[m*n];if(a==null)retur
r;while(k=l;--i)r[d++]=a[m-1][i];m--;if(l=k;--i)r[d++]=a[i][l];l++;}return r;}


https://ideone.com/SvEX11


Ответ 13


C#, 202 153 341 байт

void Spiral(int[,]a){int n=a.GetLength(0);int c=n;int v=-n;int s=-1;do{v=-1*v/n;for(in
i=0; i0);}


Проверить код можно на deck.net

Первое исправление

Уменьшил код за счет методов расширения: 153 байт

Проверить код можно на deck.net

Второе исправление
Размер кода 341 байт

Учтены замечания @Андрей NOP

Int32[] Spiral_Min(Int32[,]arr){Listlist=new List();Int32 n=arr.GetLength(0);Int3
count=n;Int32 value=-n;Int32 sum=-1;do{value=-1*value/n;for(Int32 i=0;i0);return list.ToArray();}


Проверить код можно на deck.net


Ответ 14


JS, 156

function g(n,u){b.push(a[n][u]),a[n][u]=null,!a[n][u+1]||0!=n&&a[n-1][u]||g(n,++u),a[n+1]&&a[n+1][u]&&g(++n,u),a[n][u-1]&&g(n,--u),0
Ответ 15


PHP, 225 байт

function f(array $a):array{if(empty($a))return [];$r=$a[0];$l=count($r);$x=$l-1;$y=$i=0;$s=[[0,1],[-1,0],[0,-1],[1,0]];for(;$l>0;$l-=$i++%2){for($j=$l-1;$j>0;$j--){$x+=$s[$i%4][0];$y+=$s[$i%4][1];$r[]=$a[$y][$x];}}return $r;}




Пример:

https://ideone.com/xdZo8E


Ответ 16


JavaScript, 256 символов

function z(b){var c=b.length;if(0==c)return[];if(1==c)return b[0];var d=b[0].slice(0,-1),e=b.slice(0,-1).map(i=>i[c-1]),f=b[c-1].slice(1).reverse(),g=b.slice(1).map(i=>i[0]).reverse(),h=b.slice(1,-1).map(i=>i.slice(1,-1));return[].concat(d,e,f,g,z(h))}


Рабочий пример:


function func(array) {
  var size = array.length;

  if (size == 0)
    return [];

  if (size == 1)
    return array[0];

  var top = array[0].slice(0, -1);
  var right = array.slice(0, -1).map(a => a[size - 1]);
  var bottom = array[size - 1].slice(1).reverse();
  var left = array.slice(1).map(a => a[0]).reverse();
  var inner = array.slice(1, -1).map(a => a.slice(1, -1));

  return [].concat(top, right, bottom, left, func(inner));
}

entryArray = [
  [1, 2, 3, 4],
  [12, 13, 14, 5],
  [11, 16, 15, 6],
  [10, 9, 8, 7]
];

console.log(func(entryArray));


Ответ 17


JavaScript, 252 байта

function f(b){var c=b.length;if(0==c)return[];if(1==c)return b[0];var d=b[0].slice(0,-1),e=b.slice(0,-1).map(j=>j[c-1]),g=b[c-1].slice(1).reverse(),h=b.slice(1).map(j=>j[0]).reverse(),i=b.slice(1,-1).map(j=>j.slice(1,-1));return[].concat(d,e,g,h,f(i))}




Подтверждение корректности:



function f(array) {
  var size = array.length;

  if (size == 0)
    return [];

  if (size == 1)
    return array[0];

  var top = array[0].slice(0, -1);
  var right = array.slice(0, -1).map(a => a[size - 1]);
  var bottom = array[size - 1].slice(1).reverse();
  var left = array.slice(1).map(a => a[0]).reverse();
  var inner = array.slice(1, -1).map(a => a.slice(1, -1));

  return [].concat(top, right, bottom, left, f(inner));
}

console.log(f([]))
console.log(f([
  [1]
]))
console.log(f([
  [1, 2],
  [3, 4]
]))
console.log(f([
  [1, 2, 3, 4],
  [12, 13, 14, 5],
  [11, 16, 15, 6],
  [10, 9, 8, 7]
]));


Ответ 18


C++, 216 bytes

void F(int**v,int*o,int S){int s=0,i=0;--S;while(S>0){for(int c=s;c<=S;++c)o[i++]=v[s][c];for(in
c=s+1;c<=S;++c)o[i++]=v[c][S];for(int c=S-1;c>=s;--c)o[i++]=v[S][c];for(int c=S-1;c>=s+1;--c)o[i++]=v[c][s];--S;++s;}}


Простой и интуитивный алгоритм без рекурсии или поворотов.

Развернутая реализация для демонстрации алгоритма:

void spiral_traverse(const std::vector>& v) {
    int size = v[0].size();
    int start = 0, end = size - 1;
    while (end > 0) {
        for (int c = start; c <= end; ++c) {
            std::cout << v[start][c] << ' ';
        }
        for (int c = start + 1; c <= end; ++c) {
            std::cout << v[c][end] << ' ';
        }
        for (int c = end - 1; c >= start; --c) {
            std::cout << v[end][c] << ' ';
        }
        for (int c = end - 1; c >= start + 1; --c) {
            std::cout << v[c][start] << ' ';
        }
        --end; ++start;
    }
}


ideone

Автор: на
Ярлыки: , , , , ,

Комментариев нет:

Отправить комментарий

Подписаться на: Комментарии к сообщению (Atom)