Code golf: игра в города

[@kolpeex]

А новая строка считается за два символа, за один или смотря какая нотация (Windows — \r\n, Mac — \r)?

[@karlicos]

По идее, вообще не должны считать, но все равно присоединяюсь к вопросу)

[@volinrok]

Для простоты — переводы строк считаются за один символ. Подправил задание.

[@ainu]

Как мне ответили, считаются все символы, но результат можно обфусцицировать, например.

[@general]

«Спортивное программирование» приучает писать программы в одну строчку, без комментариев, и с именами переменных типа a, b, c…

Да здравствует наше спортивное программирование, самое Бессмысленное и беспощадное программирование в мире.
Ничему не удивляюсь.

[@Logonoff]

Сколько раз участвовал — всегда находил время назвать переменную не «a», а скажем «rVect». Да и строчек мы не жалели, не вижу ничего страшного в двух-трех пустых строчках для визуального разделения кода на блоки)

[@ilBEastli]

В данном случае «спортивное» != «быстрое». Это к вопросу о времени.
Пустые строки == дополнительные символы, которые позволят сопернику обойти твое решение.
Суть конкурса состоит в компактности кода — любыми доступными средствами.

[@Namelles_One]

Собссно, ничто не мешает написать адекватно, а потом применять какой-нить обфускатор кода — вот вам и сжатый результать без лишних букв)

[@Shark]

Иногда руками можно написать решение меньшее, чем выдаст обфускатор.

[@olegchir]

также как в биатлоне есть элемент гонки и элемент стрельбы, в этом конкурсе есть элемент программирования и элемент обфускации.

предлагаю в будущем сделать чемпионат по обфускации, и сделать спортивную обфускацию частью олимпийских игр.

[@Nakilon]

И шахматы 5-минутки тоже бессмысленны, и бегать 100 метров зачем, если лучше бегать сорок, например, на рыбалку.
Спорт просто не для вас ,.)

[@Nicolette]

Традиционно термин «спортивное программирование» не используется для задач, в которых размер кода является решающим фактором. Такие задачи называются Code Golf, как указано в заголовке, и относятся к другому классу. Спортивное программирование, конечно, учит некоторым нехорошим вещам, но, поверьте, не этой.

[@xtender]

Оно приучает думать. И оптимизировать именно по заданным факторам. Это не значит, что нужно применять факторы, которые к данной задаче совсем не относятся.

[@maovrn]

Пока выполнял задание, словил море фана. Просто заменить переменные на a, b, c мало. Надо еще алгоритм отшлифовать, отсечь все лишнее и даже извратить код, но оптимизировать по заданному фактору. Первая версия моей программы занимала порядка 900 байт, заменив переменные и убрав отступы, получил 450 — и вот тут началось самое интересное. На заключительном этапе радуешься уже каждому сэкономленному символу, полученному в ходе углубленного чтения манов и экспериментов.
Стандартная функция занимает 8 символов, регулярка 7, и хоть с регуляркой ничерта не понятно — смело заменяем чтобы сэкономить символ. А здесь можно извращенно использовать ту же функцию, что и строчкой выше — кода немного прибавляется, но теперь можно написать алиас для функции и выиграть еще один символ.

[@bdmalex]

Играл в города, когда был маленький.
Для подготовки пользовался почтовым справочником по населённым пунктам Советского Союза…
Там был такой козырный населённый пункт для данной игры: ЫНТАЛЫ
(правда в какой уже республике я уже и не припомню..)…

Поэтому практически всех своих соперников я бил в 2 захода…
1 вариант) Выпадает слово на «А». Называешь АПАТИТЫ… кирдык, победа! 1:0
2 вариант) Получаешь «АПАТИТЫ», отвечаешь «ЫНТАЛЫ»(!)...2:0

После чего, играть становилось неинтересно...:)…

[@barmaley_exe]

Гугл подсказал, что это в Казахстане.
И он же подкинул ссылку:
botinok.co.il/node/41315
Кто бы знал, что городов на Ы так много немало.

[@teplorod]

«Ыспарта».
Мне кажется, турки что-то подозревают.

[@qmax]

а мне больше нравится ru.wikipedia.org/wiki/Ытык-Кюёль

[@blo]

первое слово выбирается в порядке алфавита?

[@gribunin]

Очевидно нет: в примере [Калининград, Вологда, Алматы, Дмитров, Архангельск, Тобольск, Краков] в качестве правильного ответа дано [Архангельск, Краков, Вологда, Алматы, Тобольск, Калининград, Дмитров], а в случае выбора первого слова по алфавиту, первым словом было бы «Алматы», а не «Архангельск».

[@volinrok]

Нет, первым может быть любое слово. Более того — важно первое слово выбрать так, чтобы в итоге задействовать все города.

[@eschava]

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

[@volinrok]

Это самое тонкое место. Очевидно, что одни языки имеют преимущество над другими. Идеальным решением было бы выбрать один язык или проводить соревнование отдельно для каждого языка. И то и другое не очень практично.

[@mefcorvi]

На практике на C#+Linq достаточно длинная программа получается, имхо лучше какой-нибудь функциональный нетипизированный скриптовый язык с изотерическим синтаксисом. Какой-нибудь J :-)

[@hlomzik]

Да, тут забавное недоразумение.
Условие автору стоило бы причесать и дополнить (например, про ввод-вывод и собственные ЯП).

[@el777]

> зато в питоне обязательно нужно переноситься на следующую строку
не обязательно.
Инструкции в одной строке можно разделять точкой с запятой. Я очень часто это использую в консоли.

$ cat 1.py
print 123; print 456; print 789

$ python 1.py
123
456
789

[@ilBEastli]

Пользы в данном случае никакой: вы потратили сэкономленный символ (перевод строки) на «точку с запятой». А в примере еще и + «пробел».
> переводы строк считаются за один символ

Да и пару циклов таким образом будет реализовать тяжеловато.

[@el777]

Это пример. Тоже самое можно использовать на более глубоком уровне вложенности, когда можно сэкономить по 4-5 табов в каждой строке

[@hlomzik]

Разделитель команд должен быть почти в любом языке, так что тут как раз вполне минимальная запись. Сэкономленные символы здесь — табуляции.

[@iv_s]

Есть ли ограничения по языкам программирования и по времени исполнения программы?

[@grey_one]

«4. Если вы используете экзотический язык программирования — подскажите организаторам где можно скачать компилятор.»
Про время в правилах нет ничего.

[@volinrok]

Ограничений по языкам нет. Время работы программы неограниченно.

Реально примеры будут короткие, до десятка слов, поэтому время здесь некритично.

[@Kenas]

поясните, «Использовать предпоследнюю букву можно только в том случае, если нет слов, начинающихся с последней буквы.»

ответы

[Дмитров, Вологда, Архангельск, Калининград, Далматово, Владивосток, Краков]

и

[Далматово, Вологда, Архангельск, Калининград, Дмитров, Владивосток, Краков]

не равнозначны?

тоесть сперва нужно 100% использовать совпадения по последней букве?

[@ZerocooL_m]

* Далматово, Вологда

А города Орел не существует типа?

Если уж «6. Выборка будет составлена так, что решение всегда существует. » то будте добры выбирать так чтобы это были честная игра в города.

[@Kenas]

Причём тут город Орёл и мой вопрос?

[@teplorod]

«Далматово» заканчивается на «О», а в приведенном Вами примере после этого города идет «Вологда». Т.е. ваша последовательность имеет ошибку.

[@hlomzik]

Можно использовать только города из предложенного массива.

[@teplorod]

Я выше несколько ступил, это правда. Однако, никто пока не знает, какой будет массив. Если в нем будет Орел, то предпоследнюю букву можно использовать только в том случае, если города на последнюю закончились. Т.е. если «Орел» не «вышел», то «Далматово, Вологда» — неверная последовательность.

И есть вопрос к организаторам:

неправильное решение, переход Вологда-Дмитров недопустим
[Архангельск, Калининград, Далматово, Вологда, Дмитров, Владивосток, Краков]

Почему переход недопустим?
На букву «А» города кончились, предпоследняя буква в слове «Вологда» — Д. Где нарушение правил?

[@hlomzik]

Да, и это уже тоже сказали.

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

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

[@hlomzik]

И с чего это у нас Архангельск должен быть первым, если мы можем вставить его после Вологды?

[@0lorin]

Дмитров, Вологда, Архангельск, Краков, Владивосток, Калининград, Далматово

[@teplorod]

Хм, я должно быть, чего-то не понимаю. Если цепочка начинается со слова «Архангельск» и он в массиве один на букву А, то как это они не кончились?

[@hlomzik]

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

[@hlomzik]

Цитирование, бессмысленное и беспощадное. К чему вы это написали?

Я же ориентировался на пост по ссылке, на аскдеве. Если вам действительно интересна задача, то стоит туда перейти.

По поводу «Человека» — как же это он будет задавать тон, если у нас есть на входе цепочка городов, на выходе цепочка городов, соответствующая условию, и чёрный ящик внутри?

[@teplorod]

Вы меня не поняли. Это не страшно, попробуем еще раз:

В приведенном примере цепочка следующая:
Архангельск, Калининград, Далматово, Вологда, Дмитров, Владивосток, Краков
Цепочка в примере является завершенной, т.е. включает в себя весь массив.
Организатор конкурса говорит, что такая цепочка неправильная.
Переход Вологда-Дмитров недопустим.

Вы считаете, что после «Вологда» должен быть город на букву А.
Но в ДАННОЙ цепочке он уже использован, он стоит на первом месте, мы не можем использовать его дважды.

Вы же пишете:
На «А» города как раз не кончились, потому что первое слово в последовательности должно быть хорошо выбрано, для оптимальной цепочки.

Но в данном примере они таки кончились, и после Вологда- должен идти Дмитров. Потому что д — предпоследняя буква.

[@hlomzik]

Не поняли вы. Это не результат, это кандидат в результаты. Т.е. одна из всех возможных цепочек. При этом по какому-то стечению обстоятельств (я же не знаю ваш алгоритм) на первом месте оказался Архангельск. Однако он не может быть результатом, потому что использована предпоследняя буква Вологды, когда может быть использована последняя (вас же не затруднит переставить слова?).
Соответственно, стоит продолжать поиск решения, пока не будет полного удовлетворения условиям.

[@teplorod]

Давайте по-простому: «Архангельск» можно использовать два раза? Если нет, то в той цепочке, которая начинается с города «Архангельск» второго города на «А» быть не может, раз его в массиве нету.

[@hlomzik]

Да, не может быть.
И именно поэтому этот вариант цепочки не может быть ответом, нужно искать другие перестановки.

[@volinrok]

Эти варианты равнозначны. Скажем если нет городов на букву О, то вместо Далматово везде используем Далматов, а на каком месте он будет — непринципиально.

[@maovrn]

>На вход подается массив…
Каким образом это происходит? Надо читать список из stdin, из файла, предлагать пользователю ввести список поэлементно или еще как-то?
Можно ли выбрать наиболее удобный способ ввода и описать как именно подавать?

[@volinrok]

Код чтения или инициализации массива не учитывается, делайте как вам удобно.

Пример:

a=['Калининград', 'Вологда', 'Алматы', 'Дмитров', 'Архангельск', 'Тобольск', 'Краков'];

____

for(i in a)…

Код до черты не учитывается при подсчете.

[@Nakilon]

Т.е. я так понимаю, организаторы сами посмотрят, где у вас основной код и посчитают именно его?
А можно ли, чтобы весь код был обрамлен в map{....} и все, или же нужно присвоить рез-тат какой-то переменной, типа y=map{...}? Или можно написать print map{...}?
Как-то не очень понял условия ( лучше бы классически подавали на вход слова через заданный разделитель, и требовали вывод через него же.

[@spiritedflow]

Вопрос по выводу данных:
puts s a,a
Это вывод данных, т.е. не считается, или надо разделить:
r=s a,a
# Вывод
puts r


То же самое и про инициализацию. Можно ли во время чтения перевести все в маленький регистр или перевод уже надо делать в коде?

P.S.: Кто-нибудь сделал <100 байт?

[@burdakovd]

> 4. Если вы используете экзотический язык программирования — подскажите организаторам где можно
> скачать компилятор.

Можно написать компилятор языка, имеющего только один оператор «q», который решает данную задачу

По аналогии с ru.wikipedia.org/wiki/HQ9%2B

[@olegchir]

Собственно, я это и хотел сделать в самом начале, just for lulz.
Даже начал писать инструкцию :)

Через пятнадцать минут унылого наблюдения за ползунком устанавливающейся MSVS2010 степень жестокости и бессмысленности накрыла и перешла все границы… пришлось сдаться. Я слишком слаб для спортивного программирования, жалкий неудачник.

Идея была в том, чтобы создать грамматику на AntLR (чтобы топикстартер не смог уже отказаться, что это настоящий компилятор, хоть и с очень простой грамматикой), потом в качестве кода, генерируемого интерпретатором сделать короткую программу на чистом Си, и откомпилировав через MSVS получить полноценный компилятор языка, умеющего аж одну команду «q».

Вот начало инструкции, вплоть до составления грамматики.
Истинные фанаты могут продолжить дело дальше, осталось совсем ничего: написать действительную реализацию команды Q на Си и генерацию этого Си-кода в java-методе GorodaStrategy.play()

Прочитать инструкцию в txt-формате можно здесь:
sites.google.com/site/olegchirchir/data/instant-codegolf.txt

[@ainu]

На любом существующем языке программирования, разве не так?

[@olegchir]

public interface City {
public String getName();
public String setName();
public String getVerboseName();

public Integer getSomeStrangeFlag(int OhShi);
}

public interface CitySet {
public City addCity(City: city);
public City removeCity(City: city);
public Integer reset();
public City getNextCity();
}

public interface Game {
public String getGameName();
public String setGameName();
public String getVerboseName();

public GameStrategy getGameStrategy();
public GameStrategy setGameStrategy();
public String explainGameStrategy();

public Integer startGame();
}

public interface GameStrategy {
public CitySet setCitySet(CitySet citySet);
public Integer process();
public CitySet getResult();
public Integer getProcessState();
}

Друзья! Постойте, не сдавайте задание! Я щаз по быстрому реализую, и тогда-то посмотрим, кто первый!

[@valergrad]

К сожалению perl не знаю, а на любом другом языке участвовать к codegolf по-моему бессмысленно ( из популярных).

[@Nakilon]

Руби и Питон, естественно.

[@Hanhe]

у питона как минимум — необходимы табуляции, на сколько я знаю. А каждая табуляция — доп. символ…

[@divbyzero]

Занимательная такая задачка.
Решил и получилось где-то 366-367 байт, если всё решение сбить в одну строку. Реализация на php.

По примеру нашлось два решения:
[Дмитров, Вологда, Архангельск, Краков, Владивосток, Калининград, Далматово]
[Дмитров, Владивосток, Краков, Вологда, Архангельск, Калининград, Далматово]

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

[@itspoma]

ага, на брейнфанке ;)

[@eschava]

этот язык не развлечение, а нецензурное слово

[@CrazyViper]

Решений на самом деле получилось больше:
1. [«дмитров»,«вологда»,«архангельск»,«калининград»,«далматово»,«владивосток»,«краков»]
2. [«дмитров»,«вологда»,«архангельск»,«краков»,«владивосток»,«калининград»,«далматово»]
3. [«дмитров»,«владивосток»,«калининград»,«далматово»,«вологда»,«архангельск»,«краков»]
4. [«дмитров»,«владивосток»,«краков»,«вологда»,«архангельск»,«калининград»,«далматово»]
5. [«далматово»,«вологда»,«архангельск»,«калининград»,«дмитров»,«владивосток»,«краков»]
6. [«далматово»,«вологда»,«архангельск»,«краков»,«владивосток»,«калининград»,«дмитров»]
7. [«далматово»,«владивосток»,«калининград»,«дмитров»,«вологда»,«архангельск»,«краков»]
8. [«далматово»,«владивосток»,«краков»,«вологда»,«архангельск»,«калининград»,«дмитров»]

И судя по всему они все правильные.

[@ilBEastli]

«далматово»,«владивосток»
«далматово»,«вологда»
и т.д.

Ну неверные это цепочки, понимаете?
Предпоследнюю букву можно использовать, если нет «чистого» решения.

[@CrazyViper]

Предпоследнюю букву можно использовать, если нет «чистого» решения

Вроде как в правилах написано:

спользовать предпоследнюю букву можно только в том случае, если нет слов, начинающихся с последней буквы

[@ilBEastli]

Посмотрите пример в посте:
> неправильное решение, переход Вологда-Дмитров недопустим

[@CrazyViper]

потому что есть [Вологда, Архангельск]

[@0x13h]

раз нет ограничения на языки программирования — пишем свой компилятор. Тогда потенциально исполняемый код может занимать 1 байт.

[@volinrok]

В этом случае мы будем анализировать алгоритм заложенный в компилятор :)

[@hlomzik]

Ненене, так нельзя :)
Лучше добавьте условие вроде наличия статьи об языке в википедии больше месяца.

[@dimka_kravchuk]

Программисты на J явно вне конкуренции.

[@Shark]

Пролог или Эрланг тоже неплохо бы подошли на роль решателя такого. Не слишком быстро, но ооочень компактно.

[@Levsha100]

Ассемблерщики и паскалевцы значит в пролете…

[@Levsha100]

А что если я напишу свой ограниченный язык программирования?
Напишу интерпретатор, а у самого языка будет только одна функция- "@", которая высчитывает вашу задачу?
P.S. Директивы препроцессора считаются за код?

[@olegchir]

по первому пункту (до постскриптума): habrahabr.ru/blogs/sport_programming/93993/#comment_2856509

[@itspoma]

у тебя пожалуй самый глупый вопрос.
на askdev все подробно написано: на входе слова разделенные через ",", на выходе тоже слова, тоже чекер кому, который подходят под правила игри города.

[@itspoma]

дурак математика не поймет, как бы по поставили задачу =(

[@barkalov]

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

ну, 1984, слабо?

[@BullDER]

А куда ответ выводить?
В консоль или в файл?

[@itspoma]

4. Если вы используете экзотический язык программирования — подскажите организаторам где можно скачать компилятор.

ща пойду свой компилятор склепаю под игру «города», и длина моего кода будет 1 байт, берете?)
подправляйте правила, что ли ;)

[@Nakilon]

Вспоминая твой коммент habrahabr.ru/blogs/sport_programming/93993/#comment_2856866
Ты и правда тут самый умный, и незачем тебе даже читать комменты выше )))

[@Alex_MIPT]

А что, время исполнения кода не учитывается?
Почему-то первой мыслью было составить граф и найти гамильтонов цикл…

[@m1kola]

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

[@neptune]

А если нет слов и на вторую букву с конца? Брать следующую итд?

[@hlomzik]

Говорят, что тесты будут составлены таким образом, что такого не случится.

[@Zitrix]

говорят, в каждом будет, как минимум, одно правильное решение.

и, не к Вам персонально, а в целом: ну, блин, никто в города не играл чтоли?

[@Zitrix]

*в каждом тесте будет

[@hlomzik]

Да почему-то упёрлись в фиксированность первого города в цепочке. С условием всё очень ясно.

[@spiritedflow]

Какая кодировка входных данных? Один байт, или два или utf-8 это для некоторых языков важно ;)

[@ilBEastli]

Любая. Как вам будет удобнее.
Пруф

[@pomkaster]

А можно писать на некомпилируемом, а интерпретиремом?

[@Zitrix]

не знаю можно ли, но я написал :)

[@spiritedflow]

Надо ли обрабатывать случаи, когда на последнюю букву в списке город есть, но это сам город и больше никого?

Например: [Самара, Курганинск]

Сдается мне, что некоторая часть учавствующих программ посчитает, что надо смотреть на последнюю «к» и не найдет решения.

[@hlomzik]

Эм… какой-то странный вопрос.
[Курганинск, Самара] однозначно и без недоразумений.

[@spiritedflow]

А как определяется последнюю букву надо использовать или предпоследнюю на каждом шаге рекурсии?

Если по только тем городам, которые еще в данной ветке рекурсии не обрабатывались, то можно попасть на ошибку «Вологда-Дмитров» из топика. Там нужно смотреть «а» не смотря на то, что Архангельска в остатке уже нет.

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

[@hlomzik]

Простите, но именно на эти вопросы и нужно ответить испытуемым :)

[@Homakov]

На SQL можно?

[@spiritedflow]

А чем это не язык? Structured Query Language. Хотел бы я посмотреть решение на нём :)

[@ZerocooL_m]

python 206(((
меньше не получается…

попробую на выходных пролог вспомнить)

[@spiritedflow]

Там есть питон 176, интересно будет посмотреть :)

[@ZerocooL_m]

дада, а еще 145 на прологе)

[@ainu]

Не могу не смолчать.

Если я заархивирую свой алгоритм, это будет считаться (т.е. в коде будет зазипованная строка, которую я потом unzip'ить/eval'ить буду)? :) – SSoft 13 часов назад

такое не пройдет, обфускатором можно, но код должен быть похож на код все-таки

Уверен, процент решений накрылся из за своеобразной трактовки администрацией собственных правил.
Сейчас описаний «правильных» обфускаторов нет. Но при проверке такие будут. Вот так то.

[@hlomzik]

Ага, странный ответ. Допустимо должно быть всё, хоть даже зипованные исходники; другое дело, что впихнуть архивированный исходник и unzip в сотню байт (а стоит именно на это ориентироваться) вряд ли можно будет.

[@ivv]

да любой используйте, главное чтобы небыло eval(unzip('sdjkjcxcbsdhksjdhajsd')), код типа $a=$b*$c[0];$v=$g и тп, все же более похож на код.

Проблема с зипованием, в том, что теряется всякая наглядность, кому будет интересно такое смотреть? у нас цель ведь не только отдать приз, а и оставить что-то интересное, а вот наглядный код это интересно, хоть и програнный обфускатором.

[@Infthi]

java 291(((

[@Captcha]

Думаю, у перлокодеров преемущество перед остальными =)

[@Captcha]

>преИмущество
конечно же.