Pull to refresh

Comments 87

Интересная задачка. Правда она больше подойдет тем, кто пишет под микроконтроллеры (решение проблемы при недостатки памяти). PHP все-же язык другого направления.
Честно не понял комментария.
А где ограничения по памяти?
По сути, задача вообще без ограничений.
Можно запоминать только последнее место, а не весь пройденный путь. Или я это условие придумал?

У вас есть:

  • direction — куда черепашка Галя шла в прошлый раз. 'north' — на север, 'south' — на юг, 'west' — на запад, 'east' — на восток
  • north — что на севере: 1 — стена, 2 — вход, 3 — выход, 0 — пусто
  • south — что на юге: 1 — стена, 2 — вход, 3 — выход, 0 — пусто
  • west — что на западе: 1 — стена, 2 — вход, 3 — выход, 0 — пусто
  • east — что на востоке: 1 — стена, 2 — вход, 3 — выход, 0 — пусто
  • goo — сколько говна мышонка Васи в данной клетке

goo — воплне себе возможность хранить произвольное число в клетке.
Но стоимость инкремента этой клетки — 1 ход.
>Как я ищу PHP-программиста
>Напишите код на JаvaScript

Да вы что? И говно не в тему мне кажется.
PHP-программист?
Не можешь сделать элементарную функцию на JavaScript?
У меня для тебя плохие новости.
Тест не для того, чтоб код посмотреть. Написать нормальный код прямо на собеседовании сможет далеко не каждый.
PHP-программист?
Не умеешь верстать под ie?
Вон из профессии.
Вопрос в способности мыслить. Да и причем тут верстка?
Она тут так же причем как и javascript.
Нет не так же. Верстка != программирование в том виде как пхп или javascript.
Занудство, вы сами подумайте, вы приходите устраиваться на работу, и вам сходу дают задание на другом языке про говно. Я бы сразу подумал что тут и верстать под ие придется, и сайты контентом наполнять.
А нафига вы нужны если думать не умеете? А чтобы обсудить как и что придется делать как раз собеседование и создано.
То есть, по Вашей логике пилот, обязан уметь содержать самолёт в технически исправном состоянии? А если он в этого не умеет или не хочет, то значитцо и думать он не умеет?
Не обрадую Вас, но да.
Перед вылетом экипаж проверяет техническое состояние самолета.
И принимает решение Go/No Go.
Только так.
Ну это любой водитель должен перед поездкой проверять своё авто, хотя бы на наличие колёс. Но согласитесь проверить или уметь починять это не одно и то же.
Не все видят разницу в императивных и декларативных языках.
В общем-то, не все из здешних супер-php-программистов даже поймут мою фразу.
UFO just landed and posted this here
Не вай? Вай, вай, вай…
т.е вы хотите чтобы вам javascript'ер писал код на PHP в стиле javascript, смею вас заверить, у него это не получиться. Это вообще абсолютно разные языки и мышление для них разное нужно. Не удивительно, что вы до сих пор, не нашли по такой задачке PHP программиста.
Разное мышление? Для Javascript? Да вы что! А мужики-то и не знали…
1. Вы ищете PHP-программиста, но заставляете его писать код на JS, аргументируя это способностью мыслить. Я же ищу таксиста, но на испытательный срок посажу его за грузовик, агрументируя тем, что только неудачники не могут водить грузовик — какая разница, баранка-то одна, и педалей столько же.

2. Для каких таких целей вы ищете PHP-программиста, если вы проверяете только способность составлять алгоритмы? А как же стиль кодирования? А знание структурного / модульного / объектно-ориентированного программирования? А опыт работы с чужими исходными кодами и программными продуктами? А еще туева хуча всего, что должно относиться именно к PHP-программисту, а не к эникейщику все-в-одном, который и дизайн нарисует, и страничку сверстает, и фреймворк прикрутит, и модули CMS допилит, и nginx поднимет, и базу данных оптимизирует…
Еще наверняка эту задачу очень быстро решит школьник олимпиадник без опыта работы вообще.
Естественно. Кстати говоря, ограничение на JS еще больше мешает. Соискатель лишается двух категорий людей: великолепных PHP-программистов, которые по разным причинам не выучили JS, и великолепных анализаторов-синтезаторов алгоритмов, которые просто не знают нужный соискателю язык (это к вопросу, для каких целей он ищет человека — алгоритмы поиска пути писать или внутреннюю CMS на основе какого-нить фреймворка забабахать).
Я это все к тому, что выбор подобных приоритетов отсева мне не ясен. Я бы, если бы искал PHP-программиста, сначала отсеял бы тех, кто PHP не знает (и уж точно не проверкой на знание JS или способностью писать на псевдокоде). Затем… Надо думать, зачем он мне нужен. Если для серверной части игрушки, то да, может пару олимпиадных задачек бы и взял, но только не на сию минуту решить, а дал бы время подумать. Если мне нужно поддерживать то, что уже написано, я бы расспросил про то, работал ли человек раньше с чужим кодом, с посторонними библиотеками (фреймворками, CMS etc), и, в конце концов, показал бы пару кусков кода, который он будет поддерживать, с несколькими вопросами, которые позволят оценить, смог ли он понять идею.
Но это же никак не проверка на знание PHP, JS и даже умения писать на псевдокоде. Хотя великолепные представители двух категорий из комментария выше должны уметь написать if (statement)…
По этой логике задача «Сколько настройщиков фортепиано в Сан-Франциско?» из области музыки.

Человек, считающий себя программистом, должен понимать как решать такие задачи. А решение конкретно этой программист должен просто вспомнить.

Ну а фреймворки с CMSками — само собой. Только вот научиться по туториалу на фреймворке писать — неделя. А научиться думать — кому как повезёт :)

Я тоже сначала хотел написать комментарий, что автор наверное не доиграл в детстве в Денди и т.д. Но вспомнил, как буквально на днях столкнулся с человеком, который знает популярные фреймворки и CMSки. А задача определить, входит ли текущее время в заданный интервал поставила его в тупик (не смог сообразать как записать if когда начальное время интервала больше конечного, например 20:00-6:00).

В общем, думаю подобные задачки на интервью очень даже не дурная практика.
Причина подобных споров в понимании слова «программист» и «программирование». Очень часто программистов просят сделать что-то, не входящее в их область компетенции, хотя на первый взгляд кажется, что это очевидно. Даже если отбросить верстку, web-серверы etc и ограничиться тупо написанием кода на PHP, «программирование» начнется где-то на «переписывание с блок-схемы на PHP» и закончится на «переделывание SQL-запросов для оптимизации работы БД-сервера», «создание архитектуры модульной компоненто-ориентированной CMS» и «написание серверной логики MMORPG».

Ставьте задачу поиска сотрудника конкретней.
В принципе, я с вами всеми (обе (всего обе?) стороны спора) в какой-то мере согласен — с одной стороны, если программист будет тупить при малейшем отклонении идеи алгоритма от плана, то вряд ли он будет продуктивен, а с другой, если вы ищете человека, который может ВСЕ, то готовьтесь к тому, что либо он запросит очень много (и будет прав), либо будет знать везде по чуть-чуть, либо и то, и другое (обычно так и делают (^_^) менталитет-с…).
Судя по кеглю нужен дальнозоркий :)
Ура! Вы умеете просматривать и отлаживать код. Это уже много.
Судя по комментариям выше: PHP-программист — это отдельная ветвь в развитии программистов, умеющая строго кодить на PHP.
Но у задачи существуют и правильные решения.
Вспомнилось как в 3 классе на укнц решали задачки, там на русском писали что-то типа, пока справа стена двигаться вверх. Так нам основы алгоритмов рассказывали.
Нужно просто двигаться как можно левее:
if (direction == 0)
{
  if (east == 0) 
    result =  'east';
  else if (west == 0)
    result =  'west';
  else if (north == 0)
    result = 'north';
  else if (south== 0)
    result = 'south';
}

if (direction == 'north')
{
if (west == 0)
result = 'west';
else if (north == 0)
result = 'north';
else if (east == 0)
result = 'east';
else if (south == 0)
result = 'south';

}

if (direction == 'east')
{
if (north == 0)
result = 'north';
else if (east == 0)
result = 'east';
else if (south == 0)
result = 'south';
else if (west== 0)
result = 'west';

}

if (direction == 'south')
{
if (east == 0)
result = 'east';
else if (south == 0)
result = 'south';
else if (west == 0)
result = 'west';
else if (north== 0)
result = 'north';

}

if (direction == 'west')
{
if (south == 0)
result = 'south';
else if (west== 0)
result = 'west';
else if (north == 0)
result = 'north';
else if (east== 0)
result = 'east';

}

if (west == 3)
result = 'west';
else if (south== 3)
result = 'south';
else if (north== 3)
result = 'north';
else if (east== 3)
result = 'east';
UFO just landed and posted this here
Теоретически не будет работать, если выход внутри некоторого цикла обхода,
но судя по картинкам здесь выход всегда прижат к правой стене и данная проблема не актуальна.
Таки да, такая проблема существует. Именно для этого мышонок может откладывать экскременты, и, таки да, для этого варианта построителя лабиринтов это не актуально, так что достаточно просто правила левой руки.

Ну и представленый выше вариант красотой и лаконичностью как-то не очень отличается.
Вот что я отвечал OLS'у в личку на разумный комментарий о том, что в текущей реализации сложно отслеживать вершины лабиринта, т.к. нет события, что прошлый ход мы уже были здесь:
Даже хотел сделать пометить и пойти, но понял, что за 3 часа (делал это вечером, сонный за день, вернее за ночь, до собеседования) не смогу сделать генерацию и представление многомерных лабиринтов. А в рамках двухмерного лабиринта помечать клетки вообще не надо. Особенно когда нет задачи сделать оптимальный маршрут и прочее.
В общем, говно для прикола и некоторой путаницы.
Зато можно путь трэкать.
У лабиринта выход всегда должен быть в стенке.
Писать код ищущий выход там где его не может быть — пустая трата времени.

При других условиях задачи — возможно без этого не обойтись, а тут это лишнее.
Да, а почему вы негативно относитесь к рабочим заданиям?
Не всегда есть легкие и простые задачи, которые понятно как делать.
А предлагать человеку поделать что-то что ему будет скучно, а мне не нужно — как-то неправильно.
Прошу прощения, возможно я что-то упустил, но повторюсь — зачем вам нужен PHP-программист непосредственно в работе? Вы его посадите в уголок и будете давать «легкие» задачки «напиши алгоритм поиска пути черепашки на JS», или же дадите время освоиться, а потом включите в работу над текущими/новыми проектами? Не боитесь нанять человека, в которого вы вложите деньги не только на бессмысленный труд (потому что еще ничего не умеет), но и на учебу, а в результате он уйдет в другое место?
Подобные задачки решал ещё в 7-м классе. Единственное, что тогда это были полноценные программки, а не stateless-функции. Полагаю, что это для первичного отсева совсем уж никаких кандидатов? Я, помнится, на текущее место работы тоже делал детское задание — клиент-серверное приложение, где клиент шлёт на сервер простенькие XML-файлы, а сервер просто вытаскивал из них пару полей и записывал в PostgreSQL. Как мне потом объяснили, это чтобы не тратить время на собеседования с совсем уж откровенной школотой.
Полагал, что так.
Вначале думал предложить написать простенькое MVC приложение без Framework'ов, которое делает какую-нибудь полезную вещь. Но понял, что некоторые «знающие MVC» не могут даже перевести аббревиатуру.
Вот теперь меня пугают еще и комментарии выше. Особенно вкупе со статистикой по сайту (я трэкаю нажатие на кнопку Беги, Галя, беги). На каждую 1000 не прошедших 20 прошедших. Это немного пугает.
Правило правой руки (правило Тессея, мышь Шеннона и прочее) люди, видимо, не знают, но это нормально. Плохо, что не все пытаются думать над универсальным решением.
В общем, видимо в итоге мне придется долго искать человека, но снизить планку я не могу, т.к. проектов много, а нас очень мало и надо не только программировать, но и задачи вовне ставить и трудозатраты оценивать.
А я вам скажу, почему так происходит. Потому что дебажить алгоритм в вашей импровизированной IDE невозможно в принципе другими способами, кроме как прямым нажатием на «Беги, Лоли, Беги!!!». Сделайте кнопку «Debug», сделайте брейкпоинты, в конце концов еть же онлайн-IDE для редактирования HTML/CSS/JS — ну что же вы так, издеваетесь над людьми, ограничивая их всего одной кнопкой и элементом textarea?
Возможно, я чего не понимаю. Но если делать универсальный алгоритм, то как отличить то, что мышка нагадила только что и то, что она это сделала несколько шагов назад? Было бы понятно, если бы в случае, если мы прошлый ход гадили, в текущем ходе direction обнулялся. Но направление сохраняется с последнего перемещения (а не хода). Вы уверены, что тут нет ошибки?

P.S. я понимаю, что многие решают по правилу правой или левой руки и оно работает. Но это только потому, что лабиринты подходящие для такого решение, а об этом в условии ничего нет. Или выявить эту закономерность на основе рисунка алгоритма, проанализировав 100500 вариантов и сделать предположение, на основе этих вариантов, это тоже одно из требований для решения этой задачи?
Хотя, фиксированные позиции входа и выхода позволяют говорить о том, что всегда будет работать правило руки, но зачем тогда возможность гадить? как отвлекающая внимание?
Выше было объяснение. Просто не дописан алгоритм генерации лабиринтов до «кондиции», когда точка выхода будет внутри замкнутого пути и правило Тесея не сработает.
Каюсь, это я не довел до ума. Выше есть мой ответ OLS'у, где я написал, почему.
И да, вход и выход всегда на одном месте и эти места около стенок.
Более того, всегда есть гарантированный путь, который можно увидеть в коде.
Я, может быть, как нибудь доведу игру до ума. Но тогда она станет игрой, а не тестом на 5-20 минут.
Эх, убил 2 часа, пытаясь решить задачу не пользуясь правилом руки (чтобы работал во всех случаях)…

Идея с программированием «робота» онлайн на js хорошая, жаль ошибка в возвращаемых данных (сохранение направления последнего перемещения, а не хода) подпортила картину.
Ну давайте подправлю так, как Вам хочется, чтоб проверить алгоритм. :)
Что Вы хотите сохранять?
Я хочу, чтобы когда я отложил личинку, на следующий ход в direction был 0 или пусто так, как мы никуда не двигались. Ну в смысле, не то, чтобы я хочу, это один из вариантов, при которых я решение нашел сразу и быстро.
По логике, если в direction предыдущее направление — после хода с откладыванием фекалийного маркера направление должно сохраняться.
Кажется, это не поможет. Расширил мозги черепашке Гале. Теперь она помнит не только куда шла, но и что делала.
Т.е. direction — это направление движения, но появился last_move в котором может быть jaw
Этого, по идее, должно хватить на все.
Но алгоритм генерации лабиринта не допиливал. Может позже.
Спасибо. Да, только обнуление направления не работает, с вашими правками получилось.
По идее, все просто. Правило левой руки + откладывание личинки в каждой клетке + проверка, есть ли уже личинка там, куда мы пришли.

Попозже усядусь, попробую допилить свой алгоритм.
попробуйте решить;) откладывание в каждой клетке это как-то не очень оптимально, учитывая, что откладывание занимает целый ход. Но, судя по всему, в текущей версии, это все равно не поможет.
Попробую, но пока-что занят своим GUI, так что не обещаю сразу.
А что мешает научить черепашку правилу одной руки?
Гавно нужно чтобы знать что черепашка в этой клетке уже была?
Мои 5 копеек:

var args = {
    "north": north,
    "east": east,
    "south": south,
    "west": west
}

var movement = new Array (
    "north",
    "east",
    "south",
    "west"
);

 for(a in movement) {
     if(direction == movement[a]) { 
          // Вот здесь можно значительно красивее, да. Но для наглядности оставил как есть.
          var tmpA = movement.slice(0, a-1);
          var tmpB = movement.slice(a-1, movement.length);
          movement = tmpB.concat(tmpA); 
          break;
     } 
 }

for(a in movement) {
    if(args[movement[a]] != 1) {
        result = movement[a];
        break;
    }
}


В случае, если выход находится внутри замкнутого пути — нужно запилить в эту функцию отброс фекалий и проверку на их существование. Но, как показал анализ генератора лабиринтов — выход всегда прижат к стене.
Не получится ничего запилить, вы не отличите только что поставленную какашку от той, что поставили когда-то.
Наличие фекалий нужно проверять до откладывания. И если фекалии есть — возвращаться в предыдущую клетку.
Ну вы всегда будете возвращаться в предыдущую клетку, во время установки фекалии, значит. Я фекалии ставлю на перекрестках. И черепаха бегает от одного перекрестка до другого и назад (в бесконечном цикле).
Да, именно об этом я писал топикстартеру в личку.
но вы можете узнать количество какашек.
Оно ничего не даст. Раньше нельзя было отличить только что поставленную какашку от старой. Теперь можно, в функцию новый параметр добавили и задача нормально решается.
Что-то вы странное хотите.
Дайте ему незначительный кусок рабочей задачи — сразу поймете как он ее будет решать.
Ах система чрезмерно секретная, что нельзя даже про 1 класс из нее спросить? Ну тогда не забудьте спросить анкетные данные у соискателя до третьего колена, поинтересуейтесь где была его прабабушка в 17-м году, и непременно предложите пройти тест на детекторе лжи.

По-поему, вы слишком заморачиваете и себя, и кандидата — и поэтому не можете найти.
PHP-программисты пишут JS-код, повсюду говно и раздирание мышонка… Автор, наверное, не совсем здоров.
Ну, не знаю можно ли нарисовать короче, но я решил так:
====================
var cardinal_directions = ['north','east','south','west','jaw'];
var i, last, visible, z, m;
for(i=0; i<4; i++) if (cardinal_directions[i]==last_move) last=i;
visible=[north, east, south, west, east];

z=1; selection: while(z--) {

for(i=0; i<4; i++) if (visible[i]==3) { result=i; way=1; break selection; }

for(m=(last-1)%4,i=0; i<4; i++,m=(m+1)%4) if (visible[m]==0) { result=m; break selection; }

result = Math.round( Math.random() * 5 );

} // selection block
result = cardinal_directions[ result ];
====================
Ваш код не проходит вот такие места:
image
Да, я прогнал в функции поворота, уже заметил, но было только 10 минут утром.
Проблема в том, что в яваскрипте отрицательный модуль — отрицательный :)
Поэтому через плюс считать надо.
Да и от бреков избавился лишних.

Правильное решение:
==========================
var cardinal_directions = ['north','east','south','west','jaw'];
var i, last=1, visible, z, m;

for(i=0; i<4; i++) if (cardinal_directions[i]==last_move) last=i;
visible=[north, east, south, west];

for(m=(last+2)%4,i=0; i<4; i++,m=(m+3)%4) {
if (visible[m]==0) result=m;
}

for(i=0; i<4; i++) if (visible[i]==3) result=i;
console.log(visible, last, result, m, i);

result = cardinal_directions[ result ];
==========================
А я вот довёл черепашку до оргазма конечной точки, но ничего не произошло.
Может я чего-то не учёл?
хм. переформатировал код и всё получилось…
Если кому интересно, то вот моё решение:

var moves = ['west', 'north', 'east', 'south', 'west', 'north', 'east'];

var start  = 1;

if (direction)
{
	for (var i=1; i<5; i++)
	{
		if (direction == moves[i])
		{
			start = i-1; 
			break;
		}
	}
}

for (var i = start; i < start+4; i++)
{
	if  (eval(moves[i]) == 0 || eval(moves[i]) == 3)
	{
		result = moves[i];
		break;
	}
}
Умирает, если в начале, над точкой выхода, есть одна свободная клетка.
Да, вы правы, этот момент действительно имеет место быть. Решается заменой строчки
if  (eval(moves[i]) == 0 || eval(moves[i]) == 3)


на
if  (eval(moves[i]) != 1)

А вот и оптимизированный мною вариант (чего-то никак не отпустит меня эта задача)

var moves = ['west', 'north', 'east', 'south', 'west', 'north', 'east'];
var pos=(direction)? moves.indexOf(direction, 1)-1: 1
while(eval(result=moves[pos++]) == 1);
Как-то так (сам сишник, JS почти не знаю):

var cardinal_directions = ['north','east','south','west','jaw'];
var env = [ north, east, south, west, 0];
var i;

for (i = 0; i < 4; ++i) {
  if (env[i] == 3)
    break;
}
if (i == 4) {
  for (i = 0; i < 5; ++i) {
    if (cardinal_directions[i] == direction)
      break;
  } 
  i = i % 5;

  var right = (i + 1) % 4;
  if (env[right] == 0) {
    if (!goo) {
      i = 4;
    } else {
      i = right;
    } 
  } 
  while (i < 4 && env[i] == 1) {
    i = (i + 3) % 4;
  } 
}
result = cardinal_directions[i];
Самое интересное решение, которое я «нашел» на просторах Internet для своей задачки сделал kurokikaze и опубликовал здесь.
Я рад, что пока не все считают выше своего достоинства думать. Иногда даже не над «нужной» задачей, а просто ради интереса. Говорю, как могу, спасибо тем, кто прошел.
В свою очередь, как могу, от души выражаю вам благодарность за эту задачку.
Расписать 2 строчки кода в 30 надо иметь талант :)

result=cardinal_directions[(cardinal_directions.indexOf(direction)+3)%4];
while(eval(result)%3) result=cardinal_directions[(cardinal_directions.indexOf(result)+1)%4];
Похоже, в погоне за оптимизацией вы не учли один момент (как и я с самого начала) :)
Покликайте на кнопку «новый лабиринт» до тех пор, пока стартовая позиция не будет вот такой:

***
*  **
*# 
****


и попробуйте запустить :)
Ну OK, замените в условии %3 на ==1. Смысл же моего поста не в этом.
Хотя и так возможно зацикливание в начале. Тогда нужно вместо этого начальное направление на юг задать. Справа от входа, как я вижу, всегда есть свободные поля.
Sign up to leave a comment.

Articles