Alexandroppolus,
видел и ваше решение, сколько времени ушло? |
j0hnik,
Да не помню уже. Я на прогулке вспомнил задачу, придумал решение. Что любопытно, как-то сразу возникла мысль, что тут n*ln должно быть, хотя от n^2 никак не получалось уйти. Но я с расчетом на возможный упорядоченный входной массив делал, потому не через дерево, его балансировать бы пришлось. Кстати, хочу свою кату запилить, есть одна забавная идея ) |
Цитата:
|
j0hnik,
даны переменные: a = randomShuffle([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) - массив из 10 разных чисел 0..9, в неизвестном порядке k - неизвестное целое число в пределах 0..9 написать выражение, которое находит позицию числа k в массиве a, используя как можно меньше различных символов (минимизируем не длину выражения, а именно разные символы, т.е. в строке "aaaaabbbbbb" только 2 разных символа) a.indexOf(k) - решение, но тут разных символов 12, а можно меньше Ответ по замыслу должен быть в виде строки, например, "a.indexOf(k)", которую можно будет подставить в Function('a', 'k', 'return ' + str) и получить функцию. |
Alexandroppolus,
и во сколько разных символов надо уложиться? |
j0hnik,
всего 4 :) |
Alexandroppolus,
4 это весь внутренний код функции?
function fn(k){
// 4
}
пустые символы считаются? |
j0hnik,
Нет, 4 - это только в самом выражении.
function f(a, k) {
return expr;
}
Учитывается только то что в этом expr - между пробелом и ; |
имя функции в один символ, полагаю не просто так?
|
j0hnik,
Имя функции, в общем, значения не имеет. Фиксированы только имена переменных a и k - массив и искомое число. Состав и длина массива тоже известны, но порядок элементов может быть любой. Попробую написать более формально. Требуется только выражение в виде строки: var str = ... Проверяется тип (typeof str === 'string') и символы (new Set(str).size <= 4) Потом будет создана функция
var indexOf = new Function('a', 'k', 'return ' + str);
и проверена для разных данных. Например: var str = 'a.indexOf(k)'; - работает правильно, но не проходит по ограничению. var str = '1'; - вписывается в лимит, но иногда работает неверно. |
var a = [6,3,1,4,2,7,5,0,9,8], k = 7;
function f(a, k) {
return a[a[a[k]]];
}
console.log(f(a,k));
|
j0hnik,
Если в массиве поменять 7 местами, например, с 5 или 8, неправильно работает. Надо для любого массива и любого k |
Alexandroppolus,
что-то из этой же серии только с большей вложенностью? символов слишком мало чтобы еще что-то конструировать |
Цитата:
var a = [6,3,1,4,2,7,5,0,9,8], k = 7;
function f(a, k) {
return a[a[a[a[a[a[a[a[a[a[a[k]]]]]]]]]]];
}
alert(f(a,k));
var a = [6,3,1,4,2,7,5,0,9,8], k = 7;
function f(a, k) {
return a[a[a[a[a[a[a[a[a[a[a[k]]]]]]]]]]];
}
alert(f(a,k));
var a = [6,3,1,4,2,7,8,0,9,5], k = 4;
function f(a, k) {
return a[a[a[a[a[a[a[a[a[a[a[k]]]]]]]]]]];
}
alert(f(a,k));
var a = [6,3,1,4,2,7,5,0,9,8], k = 9;
function f(a, k) {
return a[a[a[a[a[a[a[a[a[a[a[k]]]]]]]]]]];
}
alert(f(a,k));
|
Dilettante_Pro,
var a = [0,1,2,3,4,5,6,7,8,9];
a.sort(_=>Math.random() - 0.5);
function f(a, k) {
return a[a[a[a[a[a[a[a[a[a[a[k]]]]]]]]]]]+'-'+a.indexOf(k);
}
var i = 10;
while(i--) console.log(f(a,i));
вот вам тестер! |
j0hnik,
Да, на некоторых данных врет...
var n = 0;
for(var j = 0; j< 100; j++) {
var a = [0,1,2,3,4,5,6,7,8,9];
a.sort(_=>Math.random() - 0.5);
function f(a, k) {
return a[a[a[a[a[a[a[a[a[a[a[k]]]]]]]]]]] == a.indexOf(k);
}
console.log(a);
var i = 10;
while(i--) n += f(a,i)?1:0;
}
console.log(n/10);
Но процент правильных ответов на удивление высок - 70-80%. |
Цитата:
|
var result = [];
var max = 0, maxm = 0;
var str = "a[k]";
for(var m = 0;m < 1000;m++) {
var n = 0;
str = "a[" + str + "]";
var f = new Function('a', 'k', 'return ' + str + ' == a.indexOf(k);');
for(var j = 0; j< 100; j++) {
var a = [0,1,2,3,4,5,6,7,8,9];
a.sort(_=>Math.random() - 0.5);
var i = 10;
while(i--) n += f(a,i)?1:0;
}
if(max< n) { max = n; maxm = m +1;}
}
console.log(max/10, maxm);
Больше 90% правильных ответов дают уровни вложенности 118, 238, 358, 478 - с переменным первенством между ними. 97.3%, 98.2% - 838 Более высоких уровней достичь не удалось - переполняется call stack |
Цитата:
|
Dilettante_Pro,
838 это слишком для кодварс, такая городьба, видимо решение немного другое. |
Цитата:
function reverse (a, b = []) {
const [head, ...tail] = a
return tail.length
? reverse(tail, [head, ...b])
: [head, ...b]
}
alert(reverse([1,2,3,4,5]))
до 19 символов не сокращал, не интересно :) |
Цитата:
1 - a 2 - k 3 - [ 4 - ] - и все. Чтобы использовать что-то другое, надо выкидывать что-то из этого. Кроме индексных кавычек выбрасывать нечего... А без них ничего не остается. |
Цитата:
|
Цитата:
|
Я выбрал символы !+[], но пока не понятно как вызывать функцию и написать "x", но уже могу определять числа (включая NaN и Infinity), некоторые строки и имитацию круглых скобок...
|
Вот. 4 символа f(a)
var a = [];
var f = function(a) { return a.indexOf(a[10]); }
var str = 'f(a)';
alert(new Set(str).size);
var ff = new Function('a','k','return ' + str);
for(var j = 0; j< 100; j++) {
var i = 10;
while(i--) {
a = [0,1,2,3,4,5,6,7,8,9];
a.sort(_=>Math.random() - 0.5);
a.push(i);
// console.log(a);
console.log(ff(a,i), a.indexOf(i))
};
}
|
Цитата:
|
мдэ... выяснилась забавная деталь - на V8 моё решение не работает )
проверял зачем-то в ФФ, ИЕ, а вот в хроме не удосужился. Таки да, из-за переполнения стека Цитата:
да и работать должно в пустой песочнице, в которую не добавляются свои функции |
Цитата:
Цитата:
|
мода на кодварс :)
вызывать alert`Hello Word!` резать строку console.log([...'string']) клонировать
var clonedObj = {...obj};
ПК становятся быстрей, код медленнее (баланс называется) :) |
6Ку
на входе массив вида [ 1, 8, 4, 4, 6, 1, 8 ] числа целые, от 1 до 2^31, в котором нужно найти уникальный элемент и вернуть его. массивы большие важна скорость. https://www.codewars.com/kata/find-t...ain/javascript findUnique([1, 8, 4, 4, 6, 1, 8]) //6; findUnique([ 1234567 ]) //1234567; findUnique([ 1, 4, 4, 5, 5, 3, 3, 2, 2 ])// 1; findUnique([ 2, 2, 5, 5, 4, 3, 3, 1, 1 ])// 4; findUnique([ 3, 5, 5, 4, 4, 3, 2, 2, 9 ])// 9; |
Мне больше нравится вариант с двумя уникальными числами.
j0hnik, ты, кстати, не написал, что тут числа целые, от 0 до 2^31 |
Alexandroppolus,
дополнил |
https://www.codewars.com/kata/gerrymander-solver
Веселая задачка по мотивам этой их американской избирательной системы. Есть квадрат 5х5, в каждой ячейке по одному избирателю, 10 из них за тебя, 15 против, нет воздержавшихся. Надо разбить квадрат на 5 областей (по 5 избирателей в каждой области), чтобы одержать победу в трех областях. Области должны быть "связными", т.е. всю область можно обойти, только пересекая границы соседних ячеек в ней (соседние - значит имеют общую сторону). Для какого-то расклада решения может не быть, тогда вернуть null |
6к
простенькая, под чай. Дан отсортированный массив целых чисел в котором нужно найти наименьший индекс который равен значению ( arr[index] == index ) если такого индекса нет, вернуть -1 Ваш алгоритм должен быть очень эффективным. Примеры: вход: [-8,0,2,5] выход: 2, поскольку массив arr[2] == 2 вход: [-1,0,3,6] выход: -1 для тестов будет использоваться Стартовые (коротенькие массивы) и для проверки производительности массивы длинной 200 000 Количество испытаний: 1 000 https://www.codewars.com/kata/elemen...ain/javascript |
j0hnik,
опять забыл важное условие :) числа в массиве не повторяются, все разные а в целом сразу понятно куда копать - двоичный (или даже интерполяционный) поиск, a[i] >= i - смотрим влево, a[i] < i - вправо |
Alexandroppolus,
1 цикл находит нужную тысячу второй нужный индекс. и по скорости этого уже достаточно т.к 6к. |
Цитата:
function indexEqualsValue(a)
{
var max = a.length;
var min = 0;
var i;
while (min != max) {
i = Math.floor((max + min)/2);
if (a[i] > i) max = i;
else if (a[i] < i) min = i + 1;
else if (i && a[i-1] == i-1) max = i;
else return i
}
return -1
}
var i = indexEqualsValue([-8,0,2,5])
alert(i);//2
i = indexEqualsValue([-1,0,3,6])
alert(i);//-1
i = indexEqualsValue([0,1,2,3])
alert(i);//0
i = indexEqualsValue([-3,0,1,3,10])
alert(i);//3
|
рони,
Хорошие решение |
если кому интересно #112 пост
решение
function findUnique(numbers) {
return numbers.reduce((a, b) => a ^ b);
}
|
| Часовой пояс GMT +3, время: 19:09. |