Забавная задачка попалась на интервью в Гетко.

[baton]

Забавная задачка попалась на интервью в Гетко.
Отыскать количество 10-ти шаговых последовательностей хода конем по доске следующей формы.(image 1)


Условия:
1. Первый шаг может быть сделан на любую клетку.
2. Последуюший шаг должен быть обязательно ход конем.
3. В 10 символьной последовательности могут быть только 2 гласные.
Приводится пример ходов конем:
(image 2)


Выслал решение на Python и Java (http://forum.privet.com/download/file.p ... w&id=46598).

Получил от них ответ:

Code Program Review: Not very fast, not OO, not particularly succinct, no unit tests.

Вопрос в студию: Как еше более кратко (succinct) можно написать решение, да еше используя OO?

Все что короче работает медленнее и ну никак не понятнее. Вот решение из 2-х строк на Питоне:

Code: Select all

kseq = lambda (y,x,vl,sl, refs): 0 if vl<0 else (0 if ((y,x) in [(0,0),(0,4),(1,3),(2,4)]) and vl==0 else 1) if sl==1 else sum([kseq((r[0],r[1],vl-1,sl-1, refs)) for r in refs[y][x] if ((y,x) in [(0,0),(0,4),(1,3),(2,4)])]+[kseq((r[0],r[1],vl,sl-1, refs)) for r in refs[y][x] if not ((y,x) in [(0,0),(0,4),(1,3),(2,4)])])
print sum([sum(row) for row in [[kseq((y,x,2,10,[[[(iy+k[0],jx+k[1]) for k in ((-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(-1,-2),(1,-2)) if (jx+k[1]>=0 and jx+k[1]<5) and (iy+k[0]>=0 and iy+k[0]<4) and not ((iy+k[0],jx+k[1]) in [(3,0),(3,4)]) ] for jx in range(0,5) ] for iy in range(0,4)])) for x in range(0,5) if not ((y,x) in [(3,0),(3,4)])] for y in range(0,4)]])

Работает в 3 раза медленнее. Или я не понимаю что такое succinct..

[crypto5]

Интересно как можно проюнит тестировать последнее решение?
И читабельность сомнительна

А исходное действительно выглядит как то слишком сложным.

[crypto5]

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

Code: Select all

import java.util.LinkedList;
import java.util.List;


public class Kings {
	static int n = 5, m = 4;
	static int moves[][] = {{-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}};
	static List<String> r = new LinkedList<String>();
	static char syms[][] = {{'a', 'b', 'c', 'd', 'e'},
			{'f', 'g', 'h', 'i', 'j'},
			{'k', 'l', 'm', 'n', 'o'},
			{'*', '1', '2', '3', '*'}};
	static String nSyms = "bcdfghjklmn";
	
	public static void main(String[] args) {
		for(int i = 0; i < n; i ++)
			for(int j = 0; j < m; j ++)
				if(getSym(i, j) != 0) find("" + getSym(i, j), 0, i, j, 0);
		System.out.println("r = " + r);
	}

	private static void find(String s, int deep, int x, int y, int nsyms) {
		if(nSyms.indexOf(s.charAt(s.length() - 1)) != -1) nsyms ++;
		if(nsyms == 3)  return;
		if(deep == 9) {
			r.add(s);
			return;
		}
		for(int i = 0; i < moves.length; i ++) {
			char c = getSym(x + moves[i][0], y + moves[i][1]);
			if(c != 0)
				find(s + c, deep + 1, x + moves[i][0], y + moves[i][1], nsyms);
		}
	}
	
	static char getSym(int x, int y) {
		if(x < 0 || x >= n || y < 0 || y >= m || syms[y][x] == '*') 
			return 0;
		else 
			return syms[y][x];
	}
}

Юнит тестами, ОО и стрингбуферами не заморачивался.

[Flying Hen]

На пройденные клетки можно возвращаться?
Вообще можно сразу написать таблицу возможных перемещений типа (A,H),(A,L),(B,I),(B,K),(B,M) и т.д. и забыть про геометрию, а дальше depth first traversal по этой таблице.

[baton]

Да , на пройденныр клетки можно возвращаться

При последовалельности длиной 1 и 0 гласных ответ 14,
2 гласные оответ 18
мой ответ при последовательности длиной 10 и 2 гласных : 1013398
(похоже правильный)

Спасибо за пример!!
а сколько времени у вас заняло его написать?

[crypto5]

Да , на пройденныр клетки можно возвращаться

При последовалельности длиной 1 и 0 гласных ответ 14,
2 гласные оответ 18
мой ответ при последовательности длиной 10 и 2 гласных : 1013398
(похоже правильный)

Спасибо за пример!!
а сколько времени у вас заняло его написать?

Минут 10-15, сказывается то что я летом активно готовился писать алгоритмы для собеседобаний.
Но у меня там ошибка, в массиве nSyms должны быть гласные а не согласные, а так мои ответы совпадают.

[baton]

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

удачи :_)

[ddv]

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

[crypto5]

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

Да, отличная идея, похоже на динамическое программирование.

[Abappy]

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

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

[Abappy]

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

удачи :_)

сколько минут в день?

[ddv]

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

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

[Abappy]

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

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

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

Конечно, "в общем случае" можно построить пример, в котором из параметров по первому и второму куску нельзя высчитать "общие" параметры, но это ж экзотика

[ddv]

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

Заполнять то она может быть и будет с трудом (потому что это тогда под нее нужно динамически выделять память и придется делать функцию или для внешнего ее освобождения или функцию возвращающую размер структуры), а вот кто будет ее использовать??? Другая функция которая будет часть проверять по начальной строке, а вторая по структуре....вообщем интерфейст разрастется как минимум 2 дополнительные функции и ....Вообщем будет намного сложнее, делать и поддерживать, а выигрышь минимальный.