Форум Flasher.ru

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)
-   Флейм (http://www.flasher.ru/forum/forumdisplay.php?f=53)
-   -   Задачка (http://www.flasher.ru/forum/showthread.php?t=181615)

wvxvw 27.06.2012 20:00
Задачка
 
Предлагаю, на мой взгляд, интересную задачку. Не обязательно решать на AS, хоть на чем. Поэтому и в общем.

Задача заключается в следующем:
- нужно разбить содержание массива / списка / стека и т.п. на колонки. При чем, в исходной коллекции элементы упорядочены по какому угодно принципу. Для наглядности я буду использовать цифры, но это может быть что угодно.
Разбить нужно таким образом, чтобы максимально заполнить все колонки. Колонки нужно заполнять вертикально последовательно элементами из коллекции. Например:

[1, 2, 3, 4, 5, 6, 7]

разбив на 5 колонок получим:

|1| |3| |5| |6| |7|
|2| |4|

Естественно, количество элементов и колонок могут быть произвольными.

Да, еще, конечно, важное условие: колонки должны быть максимально уравновешены, т.е. вариант когда все элементы - (количество колонок - 1) складываются в первую колонку, а оставшиеся - во все остальные не проходит.

Aquahawk 27.06.2012 20:35
что-то мне тут Беллман мерещится, но сходу так не соображу. На буратину с яблоками чем-то похоже.

Astraport 27.06.2012 22:56
Интересно. А мне что-то из расчетов поверхностного натяжения:)

silin 27.06.2012 23:15
а вот взять по-простому и рассовать, не ?
Код AS3:
var i:int, j:int, k:int;

var data:Array = [1, 2, 3, 4, 5, 6, 7];

var res:Array = [];

 

var w:int = 5;

var len:int = data.length;

var h:int = Math.ceil(len / w);

 

for (i = 0; i < h; i++) res[i] = [];

 

k = 0;

for (j = 0; j < w; j++) 

{

 

        for (i = 0; i < h ; i++) 

        {

 

                res[i][j] = data[k++];

                if (--len < w - j) break;

        }

}

 

for (i = 0; i < h; i++) trace(res[i]);

wvxvw 28.06.2012 02:21
Есть один неприятный момент, который разрушает чувство прекрасного в этом коде :) когда количество элементов делится нацело на количество колонок - 1, получается что в предпоследней колонке на один элемент меньше чем у остальных, а в последней всего один элемент. Например, когда data = [1, 2, 3, 4, 5, 6, 7, 8, 9], w = 4. В таком случае хотелось бы одну колонку делать выше остальных, а не вразнобой :)

iNils 28.06.2012 02:26
Цитата:
В таком случае хотелось бы одну колонку делать выше остальных, а не вразнобой
Пример?:)

Psycho Tiger 28.06.2012 12:35
Что-то сложность не понятна: вот как silin сделал, в чем подвох?

Hauts 28.06.2012 12:41
Артём, там подвох в том, что колонки набираются последовательно и при некоторых случаях последняя колонка будет с одним элементом, в то время, как все остальные с 4-мя, например. Нужно, чтобы все колонки набирались равномерно ровно до тех пор, пока не останутся последние элементы.

Проще проиллюстрировать:
Код:
1,4,7,9
2,5,8
3,6
Код:
1,4,6,8
2,5,7,9
3
Больше часа пробую такое запрогать, сложновато и заманчиво :)

Добавлено через 1 час 23 минуты
У меня пока что так получилось (наверняка с ошибками):
Код AS3:
var data:Array = [1,2,3,4,5,6,7,8,9];

var w:int = 4;

var res:Array = [];

var rows:int = Math.ceil(data.length / w);

var endCount:int = data.length % w;

var i:int = 0;

var j:int = 0;

var k:int = 0;

var pos:int = 0;

 

for (i = 0; i < rows + 10; i++) {

        res[i] = [];

}

for (k = 0; k < data.length; k ++) {

        pos = k % rows;

        if (pos == rows - 1) {

                j++;

        }

        if (j > endCount && endCount != 0) {

                pos = k % (rows - 1); // Вот тут косяк :(

        }

        res[pos].push(data[k]);

}

for (i = 0; i < rows; i++) {

        trace(res[i]);

}

wvxvw 28.06.2012 14:48
Код AS3:
package

{

        import flash.display.Sprite;

 

        public class PrintColumns extends Sprite

        {

                /**

                 * http://stackoverflow.com/questions/1...-into-x-colums

                 */

                public function PrintColumns()

                {

                        super();

                        trace(printColumns([1, 2, 3, 4, 5, 6, 7, 8, 9], 4));

                }

 

                private function printArray(source:Array):String

                {

                        return source.join(" ") + "\n";

                }

 

                private function printColumns(source:Array, numColumns:int):String

                {

                        var output:String = "";

                        var columns:Array = new Array(numColumns);

                        var printPositions:Array = new Array(numColumns);

                        var printed:Array;

                        var i:int;

                        var columnLength:int = Math.ceil(source.length / numColumns);

                        var printedAlready:int;

                        var nextBunch:int;

 

                        printPositions[0] = 0;

                        while (i < numColumns)

                        {

                                if (source.length - (printedAlready + columnLength) < numColumns - i)

                                        nextBunch = columnLength - 1;

                                else nextBunch = columnLength;

                                printPositions[i + 1] = printedAlready + nextBunch;

                                columns[i] = printPositions[i + 1] - printPositions[i];

                                printedAlready += nextBunch;

                                i++;

                        }

                        i = 0;

                        printed = new Array(numColumns);

                        while (i < columnLength)

                        {

                                for (var j:int = 0; j < numColumns; j++)

                                {

                                        if (columns[j])

                                        {

                                                printed[j] = source[printPositions[j]];

                                                printPositions[j]++;

                                                columns[j]--;

                                        }

                                        else printed[j] = " ";

                                }

                                output += printArray(printed);

                                i++;

                        }

                        return output;

                }

        }

}
По поводу примера, ну вот, собственно, смысл тот же, что и у silin'a и работает так же. В распечатке получаем:
Код:
1 4 7 9
2 5 8
3 6
а хотелось бы:
Код:
1 4 6 8
2 5 7 9
3
т.е. чтобы только одна колонка максимум, отличалась по высоте от других.

ПС. Алгоритм такой потому что это адаптация со списков, и не хотелось во время распечаток много памяти ис пользовать. Но разница не существенная.

Psycho Tiger 28.06.2012 15:37
Код AS3:
                private function init(e:Event = null):void {

                        removeEventListener(Event.ADDED_TO_STAGE, init);

                        var txt:TextField=new TextField();

                        txt.autoSize = TextFieldAutoSize.LEFT;

                        txt.multiline=true;

 

                        var input:Array = [1,2,3,4,5,6,7,8,9];

                        const lines:int = 4;

 

                        var length:int = input.length;

                        var itemsInLine:int = length / lines;

                        var outfit:int = length - itemsInLine * lines;

                        var result:Array = [];

                        var c:int = 0;

                        var m:int = 0;

                        while (c < length){

                                result[m] = [];

                                for (var i:int = 0; i < itemsInLine; i++) result[m].push(input[c++]);

                                if (outfit-- > 0) result[m].push(input[c++]);

                                m++;

                        }

 

                        for (var k:int = 0; k<result.length; k++){

                                txt.appendText(result[k]+"\n")

                        }

                        addChild(txt);

                }

-De- 28.06.2012 15:42
Народ, вы чо?
Код AS3:
var data:Array = [1, 2, 3, 4, 5, 6, 7];

var res:Array = [];

var w:int = 5;

var minInCols:int = int(data.length / w);

var rest:int = data.length%w;

var curNum:int = 0;

for(var i:int = 0; i < w; ++i) {

        var to:int = minInCols;

        if(i < rest)

                to += 1;

        res.push([]);

        for(var j:int = 0; j < to; ++j) {

                res[i].push(curNum);

                ++curNum;

        }

}
UPD: о, Тигра вродь считай такое же запилил)

wvxvw 28.06.2012 16:37
Хехе, все не так просто!
Изначальный (мой) вариант делает C + ceiling(N/C) * C итераций. Где C - количество колонок, а N - количество элементов в массиве который нужно распечатать. Кроме того, space-state complexity (тета) равна 3 * C, а в предложенных вариантах - это C + N, что практически всегда будет больше.

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

Код AS3:
package

{

        import flash.display.Sprite;

 

        public class PrintColumns extends Sprite

        {

                /**

                 * http://stackoverflow.com/questions/1...-into-x-colums

                 */

                public function PrintColumns()

                {

                        super();

                        trace(printColumns([1, 2, 3, 4, 5, 6, 7, 8, 9], 4));

                        trace(printColumns2([1, 2, 3, 4, 5, 6, 7, 8, 9], 4));

                }

 

                private function printArray(source:Array):String

                {

                        return source.join(" ") + "\n";

                }

 

                private function mapconcat(arrays:Array, delimiter:String):String

                {

                        var result:String = "";

                        var args:Array = new Array(arrays.length);

                        var printed:Array;

 

                        for (var i:int = 0; i < arrays[0].length; i++)

                        {

                                for (var j:int = 0; j < arrays.length; j++)

                                {

                                        printed = arrays[j];

                                        if (printed.length > i) args[j] = printed[i];

                                        else args[j] = "";

                                }

                                result += delimiter + args.join(" ");

                        }

                        return result.substr(delimiter.length);

                }

 

                private function printColumns2(input:Array, lines:int):String

                {

                        var length:int = input.length;

                        var itemsInLine:int = length / lines;

                        var outfit:int = length - itemsInLine * lines;

                        var result:Array = [];

                        var c:int;

                        var m:int;

                        var output:String = "";

 

                        while (c < length)

                        {

                                result[m] = [];

                                for (var i:int = 0; i < itemsInLine; i++) result[m].push(input[c++]);

                                if (outfit-- > 0) result[m].push(input[c++]);

                                m++;

                        }

 

                        return mapconcat(result, "\n");

                }

 

                private function printColumns(source:Array, numColumns:int):String

                {

                        var output:String = "";

                        var columns:Array = new Array(numColumns);

                        var printPositions:Array = new Array(numColumns);

                        var printed:Array;

                        var i:int;

                        var columnLength:int = Math.ceil(source.length / numColumns);

                        var printedAlready:int;

                        var nextBunch:int;

 

                        printPositions[0] = 0;

                        while (i < numColumns)

                        {

                                if (source.length - (printedAlready + columnLength) < numColumns - i)

                                        nextBunch = columnLength - 1;

                                else nextBunch = columnLength;

                                printPositions[i + 1] = printedAlready + nextBunch;

                                columns[i] = printPositions[i + 1] - printPositions[i];

                                printedAlready += nextBunch;

                                i++;

                        }

                        i = 0;

                        printed = new Array(numColumns);

                        while (i < columnLength)

                        {

                                for (var j:int = 0; j < numColumns; j++)

                                {

                                        if (columns[j])

                                        {

                                                printed[j] = source[printPositions[j]];

                                                printPositions[j]++;

                                                columns[j]--;

                                        }

                                        else printed[j] = " ";

                                }

                                output += printArray(printed);

                                i++;

                        }

                        return output;

                }

        }

}

Psycho Tiger 28.06.2012 16:44
В каком-то методе mapconcat они набираются. Надо на выходе String сформатировать? Почему это форматирование не зашить в алгоритм, чтобы не гонять через Array?

wvxvw 28.06.2012 17:17
Нет, mapconcat не при чем. У тебя когда ты формируешь колонки ты проходишь по всему списку / массиву оригинальных значений (т.е. продвигаешься на каждой итерации на 1 элемент вперед). Но для алгиритма это не обязательно (т.е. даже вредно) потомо что можно продвигаться по формуле:
floor(N/C) + f(mod(N,C) - i)

где i - счетчик цикла, а f - функция которая возвращает 0 для негативных значений или 0 и 1 для позитивных значений.

-De- 28.06.2012 17:36
++ медленнее /, mod, -?

Psycho Tiger 28.06.2012 17:56
Цитата:
по всему списку / массиву оригинальных значений (т.е. продвигаешься на каждой итерации на 1 элемент вперед).
А как иначе? Надо вытащить каждый элемент входной последовательности. И в примере за одно "тело" цикла я двигаюсь или на 2, или на 3, но по сути это инлайн-цикла в теле )

wvxvw 28.06.2012 18:53
Ну вот я и говорю, что можно иначе. Т.е. не нужно пересчитывать все элементы, можно splice()'ить по нужному числу - т.как мы можем просчитать размер который нужно отрезать по формуле, вметсто того, чтобы считать по одному и ждать пока условие не выполнится ;)

Т.е. в цикле вместо for (i = 0; i < length; i++) можно сделать
for (i = 0; i < length; i += stepSize())

где setpSize() = минимальная высота колонки + (если израсходован весь остаток от последнего ряда, то 0, иначе 1).

Для списков длиной в несколько миллионов, которые нужно разбить на 5-10 колонок выигрыш будет существенный ;)

Psycho Tiger 28.06.2012 19:31
Суть то не меняется. Вот вариант с splice'ом:
Код AS3:
                private function init(e:Event = null):void {

                        removeEventListener(Event.ADDED_TO_STAGE, init);

                        var txt:TextField=new TextField();

                        txt.autoSize = TextFieldAutoSize.LEFT;

                        txt.multiline=true;

 

                        var input:Array = [1,2,3,4,5,6,7,8,9];

                        const lines:int = 4;

 

                        var length:int = input.length;

                        var itemsInLine:int = length / lines;

                        var outfit:int = length - itemsInLine * lines;

                        var result:Array = [];

                        var c:int = 0;

                        while (c < length){

                                var g:int = outfit-- > 0 ? itemsInLine + 1 : itemsInLine;

                                result.push(input.splice(0, g))

                                c+=itemsInLine;

                        }

 

                        for (var k:int = 0; k<result.length; k++){

                                txt.appendText(result[k]+"\n")

                        }

                        addChild(txt);

                }

wvxvw 28.06.2012 22:15
Ну, понятно, что если результат тот же, то суть не меняется. Я же не говорил, что не правельно, просто не оптимально. Ну и для больших распечаток дублировать весь массив в памяти тоже как бы не хорошо (можно обойтись памятью 2 * количество колонок), (в первом массиве хранить отступы в исходный массив, откуда печатаем, а во втором - высоту каждой колонки).

Я почему запостил: я когда только столкнулся, то подумал, что задача вообще тривиальная, а оказалось не совсем. Вот подумал, что будет интересно решить.

silin 28.06.2012 22:38
Цитата:
Сообщение от wvxvw (Сообщение 1086355)
Например, когда data = [1, 2, 3, 4, 5, 6, 7, 8, 9], w = 4. В таком случае хотелось бы одну колонку делать выше остальных, а не вразнобой :)
ну так какбе другие\дополнительные условия
а распихать все равно можно по простому (вроде бы :))
Код AS3:
var i:int, j:int, k:int;

var data:Array = [1, 2, 3, 4, 5, 6, 7, 8, 9];

var res:Array = [];

 

var w:int = 4;

var len:int = data.length;

var h:int = Math.ceil(len / w);

 

 

for (i = 0; i < h; i++) res[i] = [];

 

k = 0;

for (j = 0; j < w; j++) 

{

 

        for (i = 0; i < h ; i++) 

        {

 

                res[i][j] = data[k++];

 

                // уместится ли остаток в прямоугольник

                if (len-- <= (w - j - 1) * (h - 1) + 1) break;

 

                // уместится ли в строку

                //if (--len < w - j) break;

        }

}

 

for (i = 0; i < h; i++) trace(res[i]);


Часовой пояс GMT +4, время: 04:47.

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.