Вход | Регистрация
 
Информационные технологии :: Математика и алгоритмы

Очередная задачка с codewars

Очередная задачка с codewars
Я
   Kassern
 
26.12.20 - 13:02
Добрый день форумчане. Вам скучно и одиноко, тогда у меня есть задачка для вас! Время от времени прохожу задачки на codewars на питоне/джаве чисто ради интереса.
Нашел вот такую задачку, кому интересно может попробовать решить в 1с. Хотелось бы увидеть красивый, читаемый код без лишних циклов/переменных.
Дан n x n массив, верните элементы массива, расположенные от самых внешних элементов к среднему элементу, перемещаясь по часовой стрелке.
Наглядный пример https://www.haan.lu/files/2513/8347/2456/snail.png
Массив= [[1,2,3],
         [8,9,4],
         [7,6,5]]
Результат = Массив [1,2,3,4,5,6,7,8,9]
Проще говоря надо написать функцию ПолучитьМассивПоЗмейке(ДвумерныйМассив) которая вернет одномерный массив с элементами в нужном порядке.
   acht
 
1 - 26.12.20 - 13:11
(0) Вам скучно и одиноко
Не, чувак, это тебе - скучно и одиноко. Все кончится опять твоим вяленьким "вечерком сравню по времени выполнения", как в Оптимальное решение задачки
   Ненавижу 1С
 
2 - 26.12.20 - 13:15
(0) в случае четного n почему начало отсчёта берётся так как на рисунке?
   Ненавижу 1С
 
3 - 26.12.20 - 13:17
(2) а не... Там наоборот внутрь идут
   Kassern
 
4 - 26.12.20 - 13:19
(1) Только что проверил ваш код, немного замотался на наделе, при большом массиве покупателей ответ ваш код дает не верный и выполняется дольше. Отпишусь в том посте о результатах.
   Вафель
 
5 - 26.12.20 - 13:20
вообще по идее можно в 1 цикле сделать
   Kassern
 
6 - 26.12.20 - 13:20
(3) совершенно верно с внешних элементов во внутрь по часовой стрелке
   Kassern
 
7 - 26.12.20 - 13:21
(5) хотелось бы увидеть этот один цикл) у меня так не получилось
   Ненавижу 1С
 
8 - 26.12.20 - 13:23
Ну короче, там всё время два прохода одной длины. Потом длина уменьшается на 1. Между проходами поворот. В первый раз три прохода.
   acht
 
9 - 26.12.20 - 13:26
(4) >  при большом массиве покупателей
О. А давай-ка ты и для этой задачи, превентивно, какие-нибудь условия озвучишь.
   Kassern
 
10 - 26.12.20 - 13:31
(9) Лучше это писать в той  ветке. По существу " Ваша задача - написать функцию для расчета общего времени, необходимого для обслуживания всех клиентов! " ваш код при данном массиве покупателей и касс дал не верный результат. Пример с 6тью кассами и заданным порядком покупателей я написал лишь для лучшего понимания задачи подсчета времени, не более того.
   Kassern
 
11 - 26.12.20 - 13:33
(10) так же и здесь пример написан лишь для понимания задачки, матрица может быть и 10на10
   acht
 
12 - 26.12.20 - 13:38
(11) Не пойдет. Я сейчас напишу тебе красивое и быстрое решение на каких-нибудь битовых операциях и услышу в ответ нудятину "а вот оно на больших размерностях..."
   acht
 
13 - 26.12.20 - 13:40
(7) https://www.haikson.com/programmirovanie/zapolnenie-dvumernoj-matritsyi-po-spirali/
Заменяешь присвоение a[i][j] = k; на вывод этого a[i][j] и все
   Kassern
 
14 - 26.12.20 - 13:42
(13) А если не гуглить, а самому попытаться найти решение? Это ведь задачки, как раз развивать мышление.
   Kassern
 
15 - 26.12.20 - 13:44
(14) я когда ее прорешивал у меня вот такой код получился, он и близко не идеальный, но рабочий:
def snail(snail_map):
    result=[];
    array_len=len(snail_map);
    if array_len==0 or len(snail_map[0])==0:
        return result;
    array_vektor=[];
    for i in range(array_len):
        if i==0:
            array_vektor.append(array_len);
        else:
            array_vektor.append(array_len-i);
            array_vektor.append(array_len-i);
    index=0;
    left_index=0;
    right_index=array_len-1;
    for v in array_vektor:
        if index==0:
            array=snail_map[left_index];
            for i in range(v):
                k=i+left_index;
                result.append(array[k]);
        if index==1:        
            for i in range(v):
                k=i+1+left_index;
                array=snail_map[k];
                result.append(array[array_len-1-left_index]);
        if index==2:
            array=snail_map[right_index];
            for i in range(v):
                k=array_len-i-2-left_index;
                result.append(array[k]);
        if index==3:
            for i in range(v):
                k=array_len-i-2-left_index;
                array=snail_map[k];
                result.append(array[0+left_index]);
        index+=1;
        if index>3:
            index=0;
            left_index+=1;
            right_index-=1;
    return result;
   Kassern
 
16 - 26.12.20 - 13:46
(15) я более чем уверен что можно в 1с куда красивее это дело решить
   Salimbek
 
17 - 26.12.20 - 13:47
инициализируем
delta=1

x=-1
y=0
lxy=n
  
крутим цикл
while (lxy>0){
  for(i=0;i<lxy;i++){
    x+=delta
    print Массив[x,y]
  }
  lxy--
  if(lxy>0){
    for(i=0;i<lxy;i++){
      y+=delta
      print Массив[x,y]
    }
  }
  delta=-delta
}
   Salimbek
 
18 - 26.12.20 - 13:50
+(17) Хотя if не нужен, все равно в цикл не зайдет
   RomanYS
 
19 - 26.12.20 - 14:19
Запрос = Новый Запрос;
    Запрос.Текст =
    "ВЫБРАТЬ 1 КАК x, 0 КАК y
    |ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ    0, 1
    |ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ    -1, 0
    |ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ    0, -1";
    
    Векторы = Запрос.Выполнить().Выгрузить();
    
    Слоев = Цел(N/2);
    
    НомерЯчейки = 0;
    Для Слой = 1 По Слоев Цикл
        Тек = Новый Структура("x,y", Слой, Слой);
        Для каждого Направление Из Векторы Цикл
            Для инд = 1 По N+1-2*Слой  Цикл
                НомерЯчейки = НомерЯчейки + 1;
                ТД.Область(тек.y, тек.x).Текст = НомерЯчейки;
                тек.x = тек.x + Направление.x;
                тек.y = тек.y + Направление.y;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;
    
    Если N%2=1 Тогда
        НомерЯчейки = НомерЯчейки + 1;
        ТД.Область((N+1)/2, (N+1)/2).Текст = НомерЯчейки;
    КонецЕсли;
   Kassern
 
20 - 26.12.20 - 14:33
(19) прикольное решение, рисует в табличном документе числа в виде змейки. Только вот нужно обратное, уже готовый вложенный массив обойти и получить числа в нужном порядке в виде массива. Скорее всего нужно немного подправить ваш код и он это сделает. Например заполнить табдок начальными массивами, а потом в массив получить текст из ячеек в вашем цикле.
   RomanYS
 
21 - 26.12.20 - 14:38
(20) Да, конечно нужно одну строку поменять
ТД.Область(тек.y, тек.x).Текст = НомерЯчейки;
на
МассивЛинейный[НомерЯчейки-1] = МассивКвадратный[тек.y-1][тек.x-1];//вомзожно x и y нужно поменять местами

Хотелось без "если" обойтись, но не получилось)
   ДедМорроз
 
22 - 26.12.20 - 14:55
Самый простой вариант - создаём массив битов,равный нашему массиву.
Когда проходим точку,то устанавливаем бит.
Далее,определяем смещение по x и y для перехода в следующую точку.
Прежде чем шагнуть,проверяем,а не занята ли она,если занята,то меняем вектор смещения поворотом по часовой стрелке.
Когда сразу после поворота снова будет занято,то мы прошли весь массив.
   Конструктор1С
 
23 - 26.12.20 - 15:20
(15) вот зачем писать такой стрёмный код? Хотя бы разбей метод на подметоды
   Kassern
 
24 - 26.12.20 - 15:25
(23) Писал на время и не особо парился за красоту, сам принцип был интересен. Да и питон для меня в новинку, только начал изучать.
   Kassern
 
25 - 26.12.20 - 15:27
(23) вот тебе красивый код:
def snail(array):
    ret = []
    if array and array[0]:
        size = len(array)
        for n in xrange((size + 1) // 2):
            for x in xrange(n, size - n):
                ret.append(array[n][x])
            for y in xrange(1 + n, size - n):
                ret.append(array[y][-1 - n])
            for x in xrange(2 + n, size - n + 1):
                ret.append(array[-1 - n][-x])
            for y in xrange(2 + n, size - n):
                ret.append(array[-y][n])
    return ret
   Конструктор1С
 
26 - 26.12.20 - 16:48
(25) код стал короче, но не стал понятнее. Низачот
   Вафель
 
27 - 26.12.20 - 18:35
тут 4 цикла по ребрам и 1 общий цикл по числу кругов
   Garykom
 
28 - 26.12.20 - 18:40
(0) Простейший КА же
   Garykom
 
29 - 26.12.20 - 18:46
(28)+ Две переменные нужны номер шага и направление исполнителя и текущие координаты x, y
Изначально шаг = 0, направление 1 (принимаем что 0 - вверх, 1 вправо, 2 вниз, 3 влево), координаты 0,0 левый верхний угол
Далее на каждом шагу считываем текущее значение x,y из массива, если можно то перемещаемся на 1 шаг в текущем направлении, пройденную ячейку массива помечаем как то (можно новым массив NxN завести или в текущий нечто писать)
Если упираемся в "стену" (границы массива или уже пройденное значение) то сначала поворот на 90 по часовой а затем уже шаг перед, если и там стена то снова поворот
Как уже некуда идти после поворотов то стоп
   Cthulhu
 
30 - 27.12.20 - 02:16
[1с]
// хехе... вариант вообще без циклов )))
Функция ПолучитьМассивПоЗмейке( ДвуМерныйМассив , Знач ТекНомерКруга = -1, Знач ТекСтрока = -1, Знач ТекСтолбец = -1 , ТекущийСписокЗначений = Неопределено )
    Если ТекНомерКруга < 0 Тогда
        ТекущийСписокЗначений = Новый СписокЗначений;
        Возврат ПолучитьМассивПоЗмейке(ДвуМерныйМассив,0,0,0,ТекущийСписокЗначений);
    КонецЕсли;
    ТекИндексМин = ТекНомерКруга;
    ТекИндексМакс = ДвуМерныйМассив.ВГраница()-ТекИндексМин;
    ТекущийСписокЗначений.Добавить( ДвуМерныйМассив[ТекСтрока][ТекСтолбец] );
    Если ТекНомерКруга < ДвуМерныйМассив.ВГраница()/2 Тогда
        Если ТекСтрока = ТекИндексМин Тогда
            Если ТекСтолбец < ТекИндексМакс Тогда
                ТекСтолбец = ТекСтолбец + 1;
            Иначе
                ТекСтрока = ТекСтрока + 1;
            КонецЕсли;
        ИначеЕсли ТекСтолбец = ТекИндексМакс Тогда
            Если ТекСтрока < ТекИндексМакс Тогда
                ТекСтрока = ТекСтрока + 1;
            Иначе
                ТекСтолбец = ТекСтолбец - 1;
            КонецЕсли;
        ИначеЕсли ТекСтрока = ТекИндексМакс Тогда
            Если ТекСтолбец > ТекИндексМин Тогда
                ТекСтолбец = ТекСтолбец - 1;
            ИначеЕсли ТекСтрока - 1 >ТекИндексМин Тогда
                ТекСтрока = ТекСтрока - 1;
            Иначе
                Возврат ТекущийСписокЗначений.ВыгрузитьЗначения();
            КонецЕсли;
        ИначеЕсли ТекСтолбец = ТекИндексМин Тогда
            Если ТекСтрока > ТекИндексМин + 1 Тогда
                ТекСтрока = ТекСтрока - 1;
            ИначеЕсли ТекНомерКруга < ДвуМерныйМассив.ВГраница()/2 Тогда
                ТекНомерКруга = ТекНомерКруга + 1;
                ТекСтрока = ТекНомерКруга;
                ТекСтолбец = ТекНомерКруга;
            Иначе
                Возврат ТекущийСписокЗначений.ВыгрузитьЗначения();
            КонецЕсли;
        КонецЕсли;
        Возврат ПолучитьМассивПоЗмейке( ДвуМерныйМассив , ТекНомерКруга , ТекСтрока, ТекСтолбец, ТекущийСписокЗначений);
    КонецЕсли;
    Возврат ТекущийСписокЗначений.ВыгрузитьЗначения();
КонецФункции //ПолучитьМассивПоЗмейке
[/1с]
 
 Рекламное место пустует
   Конструктор1С
 
31 - 27.12.20 - 05:16
(30) эм... Хуже такого кода разве что вот такой:
https://www.govnokod.ru/1777

и мозг сломаешь, пытаясь понять логику работы кода, и для трудновыявляемых ошибок благодатная среда
   Документовед
 
32 - 27.12.20 - 08:07
Процедура ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник)
    
    
    Для НомВысота = 1 по ВысотаМасива Цикл
        ТекСтрока = "";
        Для НомДлина = 1 по ДлинаМасива Цикл
            
            ТекЗначСтр = СокрЛП(МассивИсточник[НомДлина - 1][НомВысота - 1]);
            
            ТекСтрока = ТекСтрока + ЛЕв("          ", 5 - СтрДлина(ТекЗначСтр))+  ТекЗначСтр +"; ";
        КонецЦикла;
        Сообщить(ТекСтрока);
    КонецЦикла;
    
    
КонецПроцедуры


Процедура ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат)
    
    
        ТекСтрока = "";
        Для НомДлина = 1 по ДлинаМасива*ВысотаМасива Цикл
            
            ТекЗначСтр = СокрЛП(МассивРезультат[НомДлина - 1]);
            
            ТекСтрока = ТекСтрока + ЛЕв("          ", 5 - СтрДлина(ТекЗначСтр))+  ТекЗначСтр +"; ";
        КонецЦикла;
        Сообщить(ТекСтрока);
    
    
    
КонецПроцедуры



ДлинаМасива = 5;
ВысотаМасива = 5;


МассивИсточник = Новый Массив(ДлинаМасива, ВысотаМасива);

МассивРезультат = Новый Массив(ДлинаМасива * ВысотаМасива);


НаправлениеДвиженияГоризнотальное = Истина;

ТекСтолбец = 0;
ТекСтрока = 1;

НаправлениеДвиженияПоДлине = 1;
НаправлениеДвиженияПоВысоте = 1;

ПройденоКолец = 0;


Для НомПП = 1 По  ДлинаМасива * ВысотаМасива Цикл
    Если НаправлениеДвиженияГоризнотальное Тогда
        
        ТекСтолбец = ТекСтолбец + НаправлениеДвиженияПоДлине;
        
        
        Если (НаправлениеДвиженияПоДлине > 0 и ТекСтолбец = ДлинаМасива - ПройденоКолец ) или
            (НаправлениеДвиженияПоДлине < 0 и ТекСтолбец = 1 + ПройденоКолец)
            
            Тогда
            НаправлениеДвиженияГоризнотальное = не НаправлениеДвиженияГоризнотальное;
            
            НаправлениеДвиженияПоДлине = - НаправлениеДвиженияПоДлине;
            
            Если НаправлениеДвиженияПоДлине >0 ТОгда
                ПройденоКолец = ПройденоКолец +1;
            КонецЕСли;
        КонецЕСли;
    Иначе
        ТекСтрока = ТекСтрока + НаправлениеДвиженияПоВысоте;
        
        Если  (НаправлениеДвиженияПоВысоте > 0 и ТекСтрока = ВысотаМасива - ПройденоКолец ) или
            (НаправлениеДвиженияПоВысоте < 0 и ТекСтрока = 1 + ПройденоКолец)
            
            Тогда
            НаправлениеДвиженияГоризнотальное = не НаправлениеДвиженияГоризнотальное;
            
            НаправлениеДвиженияПоВысоте = - НаправлениеДвиженияПоВысоте;
            
        КонецЕСли;
    КонецЕСли;
    
    МассивИсточник[ТекСтолбец - 1][ТекСтрока - 1] = НомПП;
    
    
    МассивРезультат[ДлинаМасива * ВысотаМасива - НомПП] = НомПП;
КонецЦикла;

ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник);

Сообщить(" ");

ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат);
   Доктор Манхэттен
 
33 - 27.12.20 - 09:29
(0) Решение на JS. Проверка граничных условий получилась довольно длинная, вынес в отдельные функции checkX и checkY:

function snail(a) {
    let x = -1, y = dy = 0, dx = 1, res = [], n = a.length;
    const checkX = () => dx === 0 || x + dx !== (dx > 0 ? n - y : n - y - 2);
    const checkY = () => dy === 0 || y + dy !== (dy > 0 ? x + 1 : x);

    do {
        do {
            res.push(a[y += dy][x += dx]);
        } while(checkX() && checkY());
        [dy, dx] = [dx, -dy];
    } while (checkX() && checkY())
    
    return res;
}
   Доктор Манхэттен
 
34 - 27.12.20 - 09:37
+(33) Заметьте, без каких-либо счетчиков циклов. Чистая логика. Сам себе решил усложнить задачу, иначе слишком легко и не интересно
   Документовед
 
35 - 27.12.20 - 09:57
С рекурсией





Процедура ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник)
    
    
    Для НомВысота = 1 по ВысотаМасива Цикл
        ТекСтрока = "";
        Для НомДлина = 1 по ДлинаМасива Цикл
            
            ТекЗначСтр = СокрЛП(МассивИсточник[НомДлина - 1][НомВысота - 1]);
            
            ТекСтрока = ТекСтрока + ЛЕв("          ", 5 - СтрДлина(ТекЗначСтр))+  ТекЗначСтр +"; ";
        КонецЦикла;
        Сообщить(ТекСтрока);
    КонецЦикла;
    
    
КонецПроцедуры


Процедура ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат)
    
    
    ТекСтрока = "";
    Для НомДлина = 1 по ДлинаМасива*ВысотаМасива Цикл
        
        ТекЗначСтр = СокрЛП(МассивРезультат[НомДлина - 1]);
        
        ТекСтрока = ТекСтрока + ЛЕв("          ", 5 - СтрДлина(ТекЗначСтр))+  ТекЗначСтр +"; ";
    КонецЦикла;
    Сообщить(ТекСтрока);
    
    
    
КонецПроцедуры



Процедура ЗаполнитьПолниМассив(МассивИсточник, МассивРезультат = Неопределено, НомПП = 0, струкДвижения = Неопределено, ПройденоКолец = 0, ИмяТекКоординаты = "ТекСтолбец", ИмяТекГраницы = "ДлинаМасива", НаправлениеДвижения = 1)
    
    Если  НомПП >  струкДвижения.ВысотаМасива * струкДвижения.ДлинаМасива Тогда
        Возврат;
    КонецЕСли;
    
    
    струкДвижения[ИмяТекКоординаты] = струкДвижения[ИмяТекКоординаты] + НаправлениеДвижения;
    
    Если  (НаправлениеДвижения > 0 и струкДвижения[ИмяТекКоординаты] = струкДвижения[ИмяТекГраницы] - ПройденоКолец ) или
        (НаправлениеДвижения < 0 и струкДвижения[ИмяТекКоординаты] = 1 + ПройденоКолец) Тогда
        
        
        Если  ИмяТекКоординаты = "ТекСтрока" Тогда
            НаправлениеДвижения = - НаправлениеДвижения;
            Если  НаправлениеДвижения > 0 Тогда
                ПройденоКолец = ПройденоКолец +1;
                струкДвижения.ТекСтолбец = струкДвижения.ТекСтолбец + 1;
                струкДвижения.ТекСтрока = струкДвижения.ТекСтрока + 1;
                
            КонецЕСли;
        КонецЕСли;
        
        ИмяТекКоординаты = ?(ИмяТекКоординаты = "ТекСтолбец", "ТекСтрока", "ТекСтолбец" );
        ИмяТекГраницы = ?(ИмяТекГраницы = "ДлинаМасива", "ВысотаМасива", "ДлинаМасива" );
    КонецЕСли;
    
    МассивИсточник[струкДвижения.ТекСтолбец - 1][струкДвижения.ТекСтрока - 1] = НомПП;
    
    МассивРезультат[струкДвижения.ДлинаМасива * струкДвижения.ВысотаМасива - НомПП] = МассивИсточник[струкДвижения.ТекСтолбец - 1][струкДвижения.ТекСтрока - 1];
    
    
    ЗаполнитьПолниМассив(МассивИсточник, МассивРезультат, НомПП+ 1, струкДвижения, ПройденоКолец,
    ИмяТекКоординаты, ИмяТекГраницы,
    НаправлениеДвижения)    
    
    
КонецПроцедуры



Функция ПолучитьМассивПоЗмейке(МассивИсточник)
    
    
    
    струкДвижения = Новый Структура;
    струкДвижения.Вставить("ТекСтолбец", 0);
    струкДвижения.Вставить("ТекСтрока", 1);
    
    струкДвижения.Вставить("ВысотаМасива", 0);
    струкДвижения.Вставить("ДлинаМасива", 0);
    
    Попытка
        струкДвижения.ВысотаМасива = МассивИсточник.Количество();
        струкДвижения.ДлинаМасива = МассивИсточник[0].Количество();
    Исключение
        Сообщить("Чёт, не похоже на двумерный массив.");
        Возврат Новый Массив(1);
    КонецПопытки;
    
    МассивРезультат = Новый Массив(струкДвижения.ДлинаМасива * струкДвижения.ВысотаМасива);
    
    НомПП = 1;
    
    ЗаполнитьПолниМассив(МассивИсточник, МассивРезультат, 1, струкДвижения, 0,
    "ТекСтолбец", "ДлинаМасива",     1);    
    
    Возврат  МассивРезультат;
    
КонецФункции


ДлинаМасива = 5;
ВысотаМасива = 5;


МассивИсточник = Новый Массив(ДлинаМасива, ВысотаМасива);

МассивРезультат = ПолучитьМассивПоЗмейке(МассивИсточник);


ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник);

Сообщить(" ");

ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат);
   Документовед
 
36 - 27.12.20 - 10:08
(35) Поправка


        струкДвижения.ДлинаМасива = МассивИсточник.Количество();
        струкДвижения.ВысотаМасива = МассивИсточник[0].Количество();
   DrHiHi
 
37 - 27.12.20 - 14:08
еще вариант автокода))

    Массив = ПолучитьМассив(); // задаваемый массив
    хмакс = Массив.ВГраница();
    умакс = хмакс;
    хмин = 0;
    умин = 0;
    угол = 0;
    х = 0;
    у = 0;
    МассивРезультат = Новый Массив;
    Пока Истина Цикл
        МассивРезультат.Добавить(Массив[у][х]);
        Если угол = 0 Тогда
            Если х = хмакс Тогда
                угол = 1;
                умин = умин + 1;
                у = умин;
            Иначе
                х = х + 1;
            КонецЕсли;
        ИначеЕсли угол = 1 Тогда
            Если у = умакс Тогда
                угол = 2;
                хмакс = хмакс - 1;
                х = хмакс;
            Иначе
                у = у + 1;
            КонецЕсли;
        ИначеЕсли угол = 2 Тогда
            Если х = хмин Тогда
                угол = 3;
                умакс = умакс - 1;
                у = умакс;
            Иначе
                х = х - 1;
            КонецЕсли;
        ИначеЕсли угол = 3 Тогда
            Если у = умин Тогда
                угол = 0;
                хмин = хмин + 1;
                х = хмин;
            Иначе
                у = у - 1;
            КонецЕсли;
        КонецЕсли;
        Если умин > умакс
            Или хмин > хмакс Тогда
            Прервать;
        КонецЕсли;
    КонецЦикла;
   Cthulhu
 
38 - 27.12.20 - 14:11
(31) спасибо ваше мнение очень важно для нас (с) lol
если мозгов не хватает понять обычную рекурсию и элементарную арифметику - так работайте над собой а не нойте про говнокод. )))
   Конструктор1С
 
39 - 27.12.20 - 19:09
(38) 一个小气的财主叫他的仆人去买酒,但是没有给他钱。仆人说:“老爷,没有钱怎么能够买酒呢?”财主生气地说:“用钱买酒谁不会?不用钱买到酒才算真的能干呢!”
过了一会儿,仆人拿着空瓶子回来了。主人大骂:“你叫我喝什么?”仆人说:“瓶子里没有酒,谁不会喝!要是能从空瓶子里喝出酒来,那才算真的能干呢!”

если мозгов нет понять иероглифы, так работайте над собой. Код пишется для людей, а не для компилятора. Хороший код должен быть максимально линейным и понятным. А не состоять из шарад в виде рекурсий
   Конструктор1С
 
40 - 27.12.20 - 19:15
Всё просто. Допустим, написал ты 100 строк кода. Другому программисту нужно внести небольшие изменения в этот код:

- если программист за 2 минуты понял всю логику кода и сразу же нашел место правки - у тебя хороший код
- если программисту понадобилось полчаса ползать с отладчиком по твоему коду - у тебя дрянной код
   bolder
 
41 - 27.12.20 - 19:18
Код в (30) и (37) выдает ошибку даже на массиве 3×3.Можно дальше не смотреть.
   Salimbek
 
42 - 27.12.20 - 20:46
(41) А в (17)?
   Cthulhu
 
43 - 27.12.20 - 20:58
(41): врете, код в (30) скопирован из рабочей обработки и не дает ошибок.
жду извинений.
   bolder
 
44 - 27.12.20 - 21:21
(43) Извиняюсь, код (30) правильно работает до массивов 40x40, даже меньше. Код (37) работает без проблем и на массиве 100x100.Что впрочем и понятно - нерекурсивный.Можно написать еще проще.
   acht
 
45 - 27.12.20 - 21:33
(0) Это вот то самое, что ты хотел добиться - локального срачика?
   bolder
 
46 - 27.12.20 - 22:14
(42) (17)Работает, но наоборот - против часовой стрелки раскручивает.
   Salimbek
 
47 - 28.12.20 - 00:42
(46) А... ясно, Массив[x,y] - неправильно, надо везде поменять на Массив[y,x] - первым идет номер слоя (т.е. координата y), а вторым - позиция элемента в этом слое (т.е. координата x)
   Доктор Манхэттен
 
48 - 28.12.20 - 02:19
(44) >> Код (37) работает без проблем и на массиве 100x100

Как-то слабовато. Щас проверил код из (33), на массиве 10000х10000 отработал за несколько секунд в браузере Эдж. В Хроме или в Ноде должен еще быстрее.
   Доктор Манхэттен
 
49 - 28.12.20 - 05:51
Немного оптимизировал по времени выполнения
Максимальный размер массива получился 46340 х 46340, выборал исходя из размера занимаемой памяти, чтобы входной и выходной массивы были примерно по 2 гигабайта. Браузер не дает выделять больше памяти.

На тестовом массиве функция выполняется за пол минуты в Microsoft Edge. В хроме не пробовал, лень устанавливать. Проверьте у кого есть.

function snail(a) {
    let x = -1, y = dy = resIndex = 0, dx = 1;
    const n = a.length;
    const res = new Uint8Array(n * n);

    for (let l = n - .5; l; l -= .5) {
        for (let i = 0; i < l; i++)
            res[resIndex++] = a[y += dy][x += dx];
        [dy, dx] = [dx, -dy];
    };

    return res;
}
   Kassern
 
50 - 28.12.20 - 09:06
(45) Я лишь хотел поделиться интересной на мой взгляд задачкой, не более. Я вообще удивлен, что столько людей так же заинтересовались и попробовали решить. Всем спасибо
   mikecool
 
51 - 28.12.20 - 09:12
»
   mikecool
 
52 - 28.12.20 - 09:13
+51 ограничение - память 65535, время - 1000мс
   Доктор Манхэттен
 
53 - 28.12.20 - 09:42
(52) >> количество селений (1 <= n <= 100000)
>> ограничение - память 65535
>> Для хранения ответа используйте список, где индекс будет номером селения

Что-то тут не сходится...
   mikecool
 
54 - 28.12.20 - 10:01
(53) вот тут я хз, но мое решение работает, только по времени исполнения ошибку выдает...
   Salimbek
 
55 - 28.12.20 - 15:13
(51) А как делал?

Если идти по подсказке, то:
1) сортируем список селений и бомбоубежищ
2) Допустим мы рассмотрели селение i, и для него нашли ближайшее убежище j. Теперь берем следующее селение i+1 и для него надо быстро найти ближайшее бомбоубежище. Оно будет либо полученное на предыдущем шаге (j), либо какое-то из последующих (j...n)
3) Используем Метод половинного деления, т.е. берем середину нашего отрезка k=(j+n)/2 и смотрим - селение находится ближе или дальше этой середины. Если ближе, то рассматриваем диапазон (j...k), если дальше, то диапазон (k...n).
P.S. Мне лениво разбираться, когда остается 1-2 элемента, поэтому если в выборке осталось менее 5 элементов, то я делаю просто полный перебор, все равно это выгоднее, чем перебирать все 100000 элементов.
   fisher
 
56 - 28.12.20 - 16:40
(49) Норм. В (17) почти тоже самое, но у тебя доведено. Вероятно, оптимальный вариант. Только пляски с 0.5 - ну, такое... Вкусовщина, но лично я не одобрям.
   bolder
 
57 - 28.12.20 - 18:51
(48) Хм..Как то тоже слабовато.Массив 100000x 100000 ( 10 в 10 степени ячеек) основное время - заполнение первоначального массива. Сама процедура, без вывода результата ;-) - мгновенно.
Полное время 1 минута 47 с.
А сколько времени в браeзере занимает вывод массива 40000x40000?
   Доктор Манхэттен
 
58 - 29.12.20 - 00:00
(56) 0.5 мне тоже не очень, можно было заменить на какой-то флаг и добавить пару условий и дополнительных действий, но это мало влияет, так что не стал.
   Доктор Манхэттен
 
59 - 29.12.20 - 00:06
(57) Странно. У меня первоначальный массив заполнялся гораздо быстрее чем основная процедура. Ты как заполнял?
Вывод массива в браузер не происходит, не стал это оформлять в какой-то формат или HTML. Результат выполнения функции возвращается в консоль, его можно посмотреть в виде массива в удобном виде.
   Доктор Манхэттен
 
60 - 29.12.20 - 00:06
100000x100000 - мгновенно? Не верю что-то.
 
 Рекламное место пустует
   _DAle_
 
61 - 29.12.20 - 00:10
(55) В третьем пункте не нужен двоичный поиск. Нужно просто для каждого селения i двигать вправо j пока расстояние между селением i и бомбоубежищем j уменьшается.
   Доктор Манхэттен
 
62 - 29.12.20 - 01:43
(61) В самой задаче уже все расписано как ее делать. Так не интересно.
   Salimbek
 
63 - 29.12.20 - 07:58
(61) Ну... автор этой темы в (54) говорит, что у него не проходит алгоритм по времени.
   Доктор Манхэттен
 
64 - 29.12.20 - 08:36
(63) Проверил этот алгоритм на JS в браузере, результат вполне быстрый, ~200 миллисекунд на максимальных размерах массивов:

function bomb(cities, vaults) {
    const [ sortedCities, sortedVaults ] = [ cities, vaults ].map(coords => Object.entries(coords).sort((a, b) => a[1] - b[1]))
    let vaultIndex = 0;
    const vaultsCount = vaults.length;
    const ret = new Uint32Array(cities.length);

    sortedCities.map(city => {
        const cityCoord = city[1];
        let closestDisd = Math.abs(cityCoord - sortedVaults[vaultIndex][1]);
        let nextDist;
        while (vaultIndex + 1 < vaultsCount && (nextDist = Math.abs(cityCoord - sortedVaults[vaultIndex + 1][1])) < closestDisd) {
            vaultIndex++;
            closestDisd = nextDist;
        }
        ret[city[0]] = +sortedVaults[vaultIndex][0] + 1;
    });

    return ret;
}

Причем самая долгая операция - это сортировка в самой первой строке: ~180 миллисекунд.
Основной цикл выполняется в среднем за 20-25 миллисекунд.
   Доктор Манхэттен
 
65 - 29.12.20 - 08:41
Как я понимаю, суть задачи - это написать свою более быструю функцию сортировки. В ней как раз узкое место. Но мы, конечно, этого делать не будем, потому что это уже делали на лабораторных работах в ВУЗе, ничего интересного, все уже давно придумано.
   _DAle_
 
66 - 29.12.20 - 10:51
(63) Да, но судя по всему у него как-то не так реализован последний шаг, потому что и вариант с двоичным поиском, и вариант с просто продвижением второго указателя (который практически полностью описан в самом условии) должны быть достаточны для такого размера входных данных. Более того с этими двумя вариантами самым затратным шагом будет все равно является сортировка.

Почему я сказал, что двоичный поиск не нужен. Смотрите, если мы делаем двоичный поиск для каждого селения, то сложность этой части алгоритма в худшем случае (а при решении таких задачек нас ведь интересует именно худший случай в отличие от реальной жизни) будет O(n*log(m)), сложность варианта с продвижением второго указателя - O(n+m), так как мы идем всегда только вправо и за весь внешний цикл в худшем случае просто пройдем весь массив бомбоубежищ. Второй вариант при данных ограничениях будет быстрее. Вариант с двоичным поиском имеет, конечно, право на существование, когда m на порядки больше n, тогда мы исключаем линейную зависимость от количества бомбоубежищ. Но все это довольно бесполезно анализировать, когда у нас первый шаг - это сортировка обоих массивов, которая уже сама по себе будет иметь сложность O(n*log(n) + m*log(m)), что и будет являться самой затратной по времени частью алгоритма.

Вообще, эта задачка - достаточно классический пример two pointers technique. И ее основной смысл обычно в демонстрации этой незамысловатой техники.


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.