По идее nemerle неплохой язык для таких задач. Но у меня решение получается в 240 символов. Хотя даже пхп там догоняют до 220. А кто-то и 140 выдал.
Вобщем если кто-то сможет улучшить — велкам, я уже устал Производительность побоку, входные данные там обещают несколько десятков городов, это решение выдерживает несколько сотен.
def inp = [
"Калининград", "Вологда", "Далматово", "Дмитров", "Архангельск", "Владивосток", "Краков", "Волгоград",
];
def test(r, x)
{
r.Filter(inp.Map(s => ToLower(s[0])).Contains(_)).Last() == ToLower(x[0])
}
def reorder(valid, head, tail)
{
| (_, [], []) => valid.Rev()
| ([], _, x :: tail) =>
match (reorder([x], head, tail))
{
| [] => reorder([], x :: head, tail)
| x => x
}
| (r :: _, head, x :: tail) when test(r, x) =>
reorder(x :: valid, [], head + tail)
| (_, _, x :: tail) => reorder(valid, x :: head, tail)
| _ =>
[]
}
def right = reorder([], [], inp);
match (right)
{
| [] => WriteLine("err");
| _ => WriteLine($"$right");
}
Естественно чтобы получить 240 байт надо убрать все пробелы и перейти на односимвольные переменные.
var list = ["kaliningrad", "vologda", "almaty", "dmitrov", "arhangelsk", "tobolsk", "krakov"];
let search(t, l, w, i) {
on u, x::xs, _, _ -> x[0] == w[i] ? {list = t+xs; x } : search(x::u, xs, w, i)
on _ -> search([], t+l, w, i - 1)
}
var p = "a";
[ for (e in list) p = search([], list, p, p.length - 1) ]
132
Немерлевский вариант можно, я думаю, в таком же ключе написать.
Здравствуйте, Ziaw, Вы писали:
Z>По идее nemerle неплохой язык для таких задач.
Я так не думаю. По сравнению с С# и Java — да, а вообще нет. По очень многим причинам Nemerle далеко не самый краткий язык, особенно когда речь идет о таких небольших программах. Т.к. основной критерий для этого конкурса — размер исходного кода, то видимо для таких "задач" лучше подходят языки типа J/K/APL.
Z>Но у меня решение получается в 240 символов. Хотя даже пхп там догоняют до 220. А кто-то и 140 выдал.
Сильно меньше на Nemerle не получится.
Моя лучшая попытка:
using Nemerle.Utility; // нужно для IEnumerable.Filterdef lst = ["Kaliningrad", "vologda", "almaty", "dmitrov", "arhangelsk", "tobolsk", "krakov"].Map(_.ToLower());
// копипаст из кода Ziaw, мне ничего короче придумать не удалосьdef last_letter(c){ c.Filter(lst.Map(x=>x[0]).Contains(_)).Last }
mutable res = [];
def search(sol, l)
{
if (l is [])
res = sol :: res
else
foreach(x in l)
when (x[0] == last_letter(sol.Last))
search(sol+[x], l.Remove(x))
}
lst.Iter(t=>search([t], lst.Remove(t)));
System.Console.WriteLine(res.Head)
На первый взгляд вроде бы работает правильно и находит все решения. Первоначальный вариант был менее императивным, но в погоне за краткостью родился именно такой код.
Здравствуйте, Ziaw, Вы писали:
Z>Напиши =) Не буду же я твой вариант постить на конкурс. Не ради приза даже, просто если там победит немерл — будет здорово.
Вот как-то так:
mutable lst = ["kaliningrad", "vologda", "almaty", "dmitrov", "arhangelsk", "tobolsk", "krakov"];
def search(l, w, i) {
| (x::xs, _, _) => if (x[0] == w[i]) {lst=lst.Remove(x); x } else search(xs, w, i)
| _ => search(lst, w, i - 1)
}
mutable p = "a";
$[ { p = search(lst, p, p.Length - 1); p } | e in lst]
Здравствуйте, Воронков Василий, Вы писали:
Z>>Только тут вроде ошибка, он будет искать город с последей буквы, потом с предпоследней, потом со второй сзади, так?
ВВ>Да, вроде так и должно быть?
Нет, только последняя или предпоследняя если в исходном списке нет городов на последнюю.
ВВ>Только мне непонятно по какому принципу должен первый город выбираться. Выбираю первый на "а".
Задача найти любой валидный маршрут, по условию он существует.
Здравствуйте, Ziaw, Вы писали:
Z>hardcase навел меня на некий Z>конкурс
Z>По идее nemerle неплохой язык для таких задач. Но у меня решение получается в 240 символов. Хотя даже пхп там догоняют до 220. А кто-то и 140 выдал. Z>Вобщем если кто-то сможет улучшить — велкам, я уже устал Производительность побоку, входные данные там обещают несколько десятков городов, это решение выдерживает несколько сотен.
Да легко Только у нее нет решения. Никакую из букв тут откинуть нельзя. Достаточно взглянуть на первые 5 городов. Если добавить еще один город "BA" — решение находится за 55мс с решением, 60 без.
Здравствуйте, Ziaw, Вы писали:
Z>Здравствуйте, _DAle_, Вы писали:
_DA>>Интересно, вот 25 городов: ["AB", "BA", "BC", "CB", "ABA", "ACA", "ADA", "AEA", "AFA", "AGA", "AHA", "AIA", "AJA", "AKA", "ALA", "AMA", "ANA", "AOA", "APA", "AQA", "ARA", "ASA", "ATA", "AUA", "AVA"]. Выдерживает?
Z>Да легко Только у нее нет решения. Никакую из букв тут откинуть нельзя. Достаточно взглянуть на первые 5 городов. Если добавить еще один город "BA" — решение находится за 55мс с решением, 60 без.
Как это нет решения? AB BC CB BA а дальше в любом порядке. Может мы по-разному понимаем условие?
Здравствуйте, _DAle_, Вы писали:
_DA>Как это нет решения? AB BC CB BA а дальше в любом порядке. Может мы по-разному понимаем условие?
Ага, туплю чего то Нашел у себя багу, заодно чуть уменьшил алгоритм. Тупым перебором тут не ограничиться, примерно 15 городов еще выдерживается, потом квдратичная сложность заруливает. Интересно, насколько каверзные примеры там будут? Наверное тупой перебор просто не пройдет в финал
Здравствуйте, Ziaw, Вы писали:
Z>Здравствуйте, Ziaw, Вы писали:
Z>>потом квдратичная сложность заруливает.
Z>Или факториал... туплю все туплю.
Мне почему-то кажется, что организаторы конкурса не в курсе, что за задачу они вообще дали И тесты такие они вряд ли будут придумывать. Так что, думаю, переборное решение — это то, чего ждут организаторы.
Здравствуйте, _DAle_, Вы писали:
_DA>Мне почему-то кажется, что организаторы конкурса не в курсе, что за задачу они вообще дали И тесты такие они вряд ли будут придумывать. Так что, думаю, переборное решение — это то, чего ждут организаторы.
=) Интересно. А как можно оптимизировать?
Я вижу оптимизацию в поиске множеств без решения. Или просто запоминании их по мере отсечения для каждой начальной буквы.
Еще один вариант в постепенном выстраивании "однозначных" цепочек, только тут маленько не хватает мозгов, чтобы понять не будет ли данная задача сложнее исходной.
Здравствуйте, Ziaw, Вы писали:
Z>Здравствуйте, _DAle_, Вы писали:
_DA>>Мне почему-то кажется, что организаторы конкурса не в курсе, что за задачу они вообще дали И тесты такие они вряд ли будут придумывать. Так что, думаю, переборное решение — это то, чего ждут организаторы.
Z>=) Интересно. А как можно оптимизировать? Z>Я вижу оптимизацию в поиске множеств без решения. Или просто запоминании их по мере отсечения для каждой начальной буквы. Z>Еще один вариант в постепенном выстраивании "однозначных" цепочек, только тут маленько не хватает мозгов, чтобы понять не будет ли данная задача сложнее исходной.
Строим ориентированный граф. Вершины — символы алфавита, ребра — это названия городов. То есть для "Алматы" (при отсутствии городов на Ы) будет ребро между вершинами А и Т. Остается найти эйлеров путь в этом графе. Делается это со сложностью O(n), где n — количество наших городов-ребер.
Здравствуйте, Ziaw, Вы писали:
Z>>>Только тут вроде ошибка, он будет искать город с последей буквы, потом с предпоследней, потом со второй сзади, так? ВВ>>Да, вроде так и должно быть? Z>Нет, только последняя или предпоследняя если в исходном списке нет городов на последнюю.
А где ты там такое увидел? Они пишут: "Прошу учесть во внимание что города на букву Ы в данном списке нет, поэтому далее поиск идет по предыдущей букве." По идее логика такая — если нет города на эту букву, то берем предыдущую и пр. Вроде как это вполне соответствует правилам самой игры Города.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, Ziaw, Вы писали:
Z>>>>Только тут вроде ошибка, он будет искать город с последей буквы, потом с предпоследней, потом со второй сзади, так? ВВ>>>Да, вроде так и должно быть? Z>>Нет, только последняя или предпоследняя если в исходном списке нет городов на последнюю.
ВВ>А где ты там такое увидел? Они пишут: "Прошу учесть во внимание что города на букву Ы в данном списке нет, поэтому далее поиск идет по предыдущей букве." По идее логика такая — если нет города на эту букву, то берем предыдущую и пр. Вроде как это вполне соответствует правилам самой игры Города.
Увидел в каментах, но важно не это, а то, что буквы нет во всем списке, а не только в остатке. Либо я не так понял логику твоего поиска.
Здравствуйте, Ziaw, Вы писали:
ВВ>>А где ты там такое увидел? Они пишут: "Прошу учесть во внимание что города на букву Ы в данном списке нет, поэтому далее поиск идет по предыдущей букве." По идее логика такая — если нет города на эту букву, то берем предыдущую и пр. Вроде как это вполне соответствует правилам самой игры Города. Z>Увидел в каментах, но важно не это, а то, что буквы нет во всем списке, а не только в остатке. Либо я не так понял логику твоего поиска.
Не понял, что значит нет во всем списке? Ты в игру-то играл? По идее один и тот же город нельзя называть два раза, т.е. как только он у нас заматчился — выкидываем его из списка и игнорируем в дальнейшем. Поэтому учитываться всегда должен только остаток, как я понимаю.
А по производительности вы тут зря обсуждение затеяли. Там таких условий нет. Важно, чтобы в принципе работало + самый короткий код. По сути это конкурс говнокода
К тому же даже мой первоначальный вариант на интерпретируемом языке на 2х десятков городов работает без времени.
Здравствуйте, Ziaw, Вы писали:
ВВ>>А где ты там такое увидел? Они пишут: "Прошу учесть во внимание что города на букву Ы в данном списке нет, поэтому далее поиск идет по предыдущей букве." По идее логика такая — если нет города на эту букву, то берем предыдущую и пр. Вроде как это вполне соответствует правилам самой игры Города. Z>Увидел в каментах, но важно не это, а то, что буквы нет во всем списке, а не только в остатке. Либо я не так понял логику твоего поиска.
Да, уточню — у меня поиск всегда производится по всему списку за минусом уже выбранных городов.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Здравствуйте, Ziaw, Вы писали:
ВВ>>>А где ты там такое увидел? Они пишут: "Прошу учесть во внимание что города на букву Ы в данном списке нет, поэтому далее поиск идет по предыдущей букве." По идее логика такая — если нет города на эту букву, то берем предыдущую и пр. Вроде как это вполне соответствует правилам самой игры Города. Z>>Увидел в каментах, но важно не это, а то, что буквы нет во всем списке, а не только в остатке. Либо я не так понял логику твоего поиска.
ВВ>Не понял, что значит нет во всем списке? Ты в игру-то играл? По идее один и тот же город нельзя называть два раза, т.е. как только он у нас заматчился — выкидываем его из списка и игнорируем в дальнейшем. Поэтому учитываться всегда должен только остаток, как я понимаю.
Честно говоря, я уже запутался какие там правила По ходу они изменились в процессе обсуждения. Но я сомневаюсь, что автор предполагал использование эйлерового цикла.
Я уверен, что не предполагал. Он там в комментариях удивляется тому, что решения могут долго работать А с формулировкой со всякими предпоследними буквами автор явно перемудрил, надо было быть проще и просто всегда гарантировать существование ответа с последними буквами. Да и сказать, что городов не может быть больше 20, тогда никаких бы дополнительных вопросов к нему не возникало.
Производительность побоку, входные данные там обещают несколько десятков городов, это решение выдерживает несколько сотен.
Только у нее нет решения. Никакую из букв тут откинуть нельзя. Достаточно взглянуть на первые 5 городов. Если добавить еще один город "BA" — решение находится за 55мс с решением, 60 без.
По идее один и тот же город нельзя называть два раза, т.е. как только он у нас заматчился — выкидываем его из списка и игнорируем в дальнейшем. Поэтому учитываться всегда должен только остаток, как я понимаю.
