Pull to refresh

Comments 56

Хабр стал невыносим -не дает поставить плюсик за Вашу публикацию. Газу, говорит, веселящего у меня не хватает…
Юный c++ программист плачет во мне от числа копирований объектов в приведенной реализации.
То есть, «умное решение» это «тупое решение», но написанное не на for-ах, а на функциях обработки коллекций (foreach, map, ...). Ну ок.
Оно ещё не дописано, будет следующая часть. А «умность» будет заключаться в том, что мы избавимся от кучи проверок, которые были вынуждены писать в форах, за счет правильной работы со списками и текущим состоянием.
А лексикографический порядок разве тут существенен?
Просто алгоритм с протаскиванием числа по строке, при правильной реализации особенно на C/С++, будет быстрее, я гарантирую. = )

habrahabr.ru/post/260111
Ага, и, как говорилось в первом же абзаце, все эти монады — просто другой способ выразить в коде то, что может быть выражено и без них.
У меня монады ассоциируются с философией Лейбница.
Да, все-таки оверхед в решении на C++ достаточно высок. Оригинальное решение на Хаскеле очень элегантное.
Хотя как лабораторная задача это весьма интересно.
Такую задачу можно решить одним циклом с std::next_permutation(...) и простой проверкой правильности ответа.

Приведите, пожалуйста, пример задачи (подозреваю, что она будет довольно «промышленной»), которую действительно есть смысл решать с помощью монад на С++, причем без сильного оверхеда. Еще лучше, если у вас уже был такой опыт.
Да, с помощью next_permutation эта задачка решается на C++ в 4 строчки. Но при этом такое решение минимум в 5 раз медленнее варианта со списками (типа того, что я привёл ниже), т.к. делает много ненужной работы.
потому что нет двух таких четырёхзначных чисел, которые бы при сложении дали бы число большее 19998

Странные рассуждения у автора. Пытается сократить код, обобщить его. А примеры приводит совсем конкретные. Строго говоря, при сложении всегда в старший разряд переносится максимум 1.
Каждая буква соответствует цифре от 0 до 9.

Из этого совсем не следует того что разные буквы не могут иметь одно численное значение. И вообще корявый способ решения. Сейчас поиграюсь и возможно приведу и без всяких монад адекватный способ.
Извините, что без монад :)
/*
 *   s e n d
 * + m o r e
 * ---------
 * m o n e y
 *
 */

bool digits[10] = {0};
char letters[8] = {'s', 'e', 'n', 'd', 'm', 'o', 'r', 'y'};
int result[8] = {};
int& s = result[0];
int& e = result[1];
int& n = result[2];
int& d = result[3];
int& m = result[4];
int& o = result[5];
int& r = result[6];
int& y = result[7];

void print()
{
    cout << "  " << s << " " << e << " " << n << " " << d << endl;
    cout << "+ " << m << " " << o << " " << r << " " << e << endl;
    cout << "---------" << endl;
    cout << m << " " << o << " " << n << " " << e << " " << y << endl;
}

bool solve(int letter)
{
    if (letter == sizeof(letters)) {
        if (m == 0 || s == 0)
            return false;
        bool solved =
                (((s * 10 + e) * 10 + n) * 10 + d)
                +
                (((m * 10 + o) * 10 + r) * 10 + e)
                ==
                ((((m * 10 + o) * 10 + n) * 10 + e) *10 + y);
        return solved;
    }

    for (int i = 0; i < 10; i++) {
        if (digits[i]) continue;
        digits[i] = 1;
        result[letter] = i;
        if (solve(letter + 1))
            return true;
        digits[i] = 0;
    }
    return false;
}

int main()
{
    if (solve(0)) {
        print();
    }
    return 0;
}
Как-то по стилю больше на С похоже
Извините, что без классов ))
Дело не в классах, а в глобальных переменных и странных функциях с побочными эффектами.

P.S. Я, конечно же, понимаю, что это просто решение задачи и вы не стремились создать сверхсопровождаемый код ) Просто обратилось внимание на это.
экспертная система на бумажке дала рез на 5-ой итерации, почувствовал себя нужным
Такую за сколько решите: до+фа=ага?
Только сейчас составил.
Три шага, двадцать четыре варианта решения, бумажка в отличие от оригинальной задачи не требуется. Несерьёзно.
На нормальном C++ можно легко написать вариант со списками без всяких монад:
constexpr array<uint8_t, 10> digits={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

class task{
	uint8_t s, e, n, d, m, o, r, y;
	bool _ok=false;
	auto to_int(initializer_list<uint8_t> l) {return accumulate(l.begin(), l.end(), 0, [](unsigned sum, uint8_t d){return sum*10+d;});}
public:
	auto ok() {return _ok;}
	auto order() {return tie(s, e, n, d, m, o, r, y);}
	void check() {_ok=m!=0&&s!=0&&(to_int({s,e,n,d})+to_int({m,o,r,e})==to_int({m,o,n,e,y}));}
	void print()
	{
		if(ok()) cout<<' '<<to_int({s,e,n,d})<<"\n+"<<to_int({m,o,r,e})<<"\n-----\n"<<to_int({m,o,n,e,y})<<endl;
		else cout<<"there is no solution"<<endl;
	}
};

template<size_t N=digits.size()> auto solve(task t=task(), const array<uint8_t, N>& ds=digits)
{
	for(auto d: ds){
		get<digits.size()-N>(t.order())=d;
		array<uint8_t, N-1> new_ds;
		remove_copy(ds.begin(), ds.end(), new_ds.begin(), d);
		auto r=solve(t, new_ds);
		if(r.ok()) return r;
	}
	return t;
}
template<>auto solve(task t, const array<uint8_t, digits.size()-tuple_size<decltype(t.order())>::value>&) {t.check(); return t;}

int main() {solve().print();}


Причём его можно будет безопасно распараллелить в одну строчку. Это я к тому, что обычно называют главным бонусом ФП стиля. Хотя в данной задачке это естественно не требуется, так что в принципе можно сделать передачу task'a по ссылке и получить чуть большую эффективность, но тогда это будет уже не готовый к распараллеливанию код.
Вот этот вариант мне гораздо больше нравится.
А я вот на python накодил:
ten = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}

def rang(c, sendmory):
  if len(sendmory) < 8:
    for i in (ten^c):
      if len(sendmory) == 4 and i == 0: # это чтобы не было кучи ложных решений с нулём в начале слова 'more'
	continue
      rang(c^{i}, sendmory+str(i))
  else:
    k = {i:[] for i in range(8)}
    for i in range(8):
      k[i] = int(sendmory[i])
    if (k[0]*1000+k[1]*100+k[2]*10+k[3]+k[4]*1000+k[5]*100+k[6]*10+k[1]) == (k[4]*10000+k[5]*1000+k[2]*100+k[1]*10+k[7]):
      print ' '+sendmory[0:4]+'\n+'+sendmory[4:7]+sendmory[1]+'\n-----\n'+sendmory[4:6]+sendmory[2]+sendmory[1]+sendmory[7]+'\n'+sendmory
c = set({})
rang(c, '')

Почему-то решение выводит на последних секундах из полутора минут ;)
Не надо городить каскады, масштабируется легко.
Подозреваю, что кто-то из вышекомментировавших уже писал подобное, но C++ почти не понимаю, честно писал сам.
P.S. Имена переменных беру от фонаря, да и вообще я не программист, просто поделиться захотелось…
Я данный код на Питоне ещё не разбирал, но сразу хочу сказать, что «полторы минуты» — это просто беспредел какой-то. ) Если что, код выше (который на C++) исполняется 3,5 миллисекунды.
Складывается ощущение, что для каждой статьи обязательно найдется человек, который сочтет своим долгом показать, как «это» делается на Python.
Ну в принципе давно известно, что чем ниже к железу, тем быстрее. Слегка оптимизировать и уже полминуты:
ten = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}

def rang(c, sendmory):
  if len(sendmory) < 8:
    for i in (ten^c):
      if (len(sendmory) == 4 or len(sendmory) == 0) and i == 0:
	continue
      rang(c^{i}, sendmory+str(i))
  else:
    if (int(sendmory[0:4])+int(sendmory[4:7]+sendmory[1]))==int(sendmory[4:6]+sendmory[2]+sendmory[1]+sendmory[7]): 
      print ' '+sendmory[0:4]+'\n+'+sendmory[4:7]+sendmory[1]+'\n-----\n'+sendmory[4:6]+sendmory[2]+sendmory[1]+sendmory[7]+'\n'+sendmory
c = set({})
rang(c, '')

Это я уже подсмотрел в код amosk'а (не в Ваш, тот дюже зубодробительный). А вначале я и под кат не ходил, набросал пару вариантов, один выложил.
Зато кратко и наглядно — если не считать кучи срезов в конце, всё можно разъяснить на пальцах.

2 dcc0: а Вы бы хотели, чтобы «это» делали на ассемблере? Или ничего не писали, кроме того, что Вам лично интересно? Так не бывает…
Я периодически брал чужие решения на Python и разбирал — так и научился быдлокодить, для дома хватает. Пора отдавать долги. Или Вы считаете, что я маньяк Python и желаю разжечь холивар? Увы, нет. Инструмент, как инструмент.
Полминуты??? Вот этот вот код??? Это что же у вас за компьютер такой? ))) У меня этот ваш пример исполняется 4 секунды на обычном Питоне и 0,1 секунды на PyPy.

Кстати, если пытаться сделать на Питоне наиболее близкую аналогию моему коду, то этот ваш пример надо чуть подправить:
def rang(c={1, 2, 3, 4, 5, 6, 7, 8, 9, 0}, sendmory=''):
	if len(sendmory)<8:
		for i in (c):
			if i==0 and (len(sendmory)==4 or len(sendmory)==0): continue
			rang(c-{i}, sendmory+str(i))
	else:
		if int(sendmory[0:4])+int(sendmory[4:7]+sendmory[1])==int(sendmory[4:6]+sendmory[2]+sendmory[1]+sendmory[7]):
			print ' '+sendmory[0:4]+'\n+'+sendmory[4:7]+sendmory[1]+'\n-----\n'+sendmory[4:6]+sendmory[2]+sendmory[1]+sendmory[7]
rang()

Получается и внешне попроще и выполняется чуть лучше — 3,2 секунды на обычном Питоне. Хотя до результатов C++ конечно же всё равно огромная пропасть, даже с PyPy.
Обычный ноут четырехлетней давности, нечищенный ни разу. Во избежание перегрева переведен на 'powersave' :]]

Да, Ваш вариант выгадал еще 4 секунды у меня, примерно пропорционально. Что ж, когда соберусь изучать C++, начну с Вашего примера, хоть и страшно смотреть. Главное — что алгоритм я знаю, а остальное дело техники.
Лично меня интересует максимально понятное и краткое описание алгоритма или метода естественным языком, можно с картинками :)
А его конкретная реализация — это некая частность, которая может быть кому-то интересна, а кому-то нет.

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

gist.github.com/alexander-irbis/34828a5e9dc41940f506

При этом, самый читабельный вариант на удивление оказывается и самым быстрым
В случае Питона скорость — это довольно неоднозначное понятие. К примеру ваш код (test_dict) исполняется на моём компьютере за 0,33 секунды — казалось бы намного (в 10 раз!) лучше результата кода freuser'a. Однако, если мы запустим тоже самое с помощью PyPy, то ваш код исполнится за 0,14 секунды, что ощутимо медленнее чем у freuser'a (там было 0,1 секунды). Так какой же вариант считать самым быстрым? )
Не стоит забывать, что кроме всего прочего ещё важна и версия интерпретатора и возможности процессора и насколько транслятор PyPy эффективно под процессор подстраивается.

Одним из вопиющих примеров разницы между вторым и третьим питоном, возмутившим меня в своё время, является range: xrange во втором обрабатывается раза в три (плюс/минус лапоть) быстрее range в третьем (и это касается и pypy).

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

Я там ещё один вариант добавил, которым эта задача на самом деле™ должна решаться и он «рвёт шаблоны» о производительности python и pypy (по крайней мере на моей машине) — интерпретатор обгоняет компилятор в пять раз.

Добавил вариант freuser и прогнал тесты через второй. Очень интересный результат в pypy2. Похоже сказывается его лучшая оптимизированность.

Ну и решение в десяток строчек против четырёх десятков — всё-таки, как ни крути, красиво.
Особенно интересно обратить внимание на вот этот результат:

1.324 sec; test_freuser_ft_alex
0.118 sec; test_freuser_ft_alex_2

Я специально проверил результат поменяв порядок выполнения функций, но нет, всё стабильно.

Различия между функциями минимальны и я ожидал бы, что _2 будет работать чуть дольше (как это и происходит в других версиях), но внезапно. В то же время у Вас, я так понимаю вполне оптимально выполнился код первого варианта?
Не очень понял кто такие test_freuser_ft_alex и test_freuser_ft_alex_2 — в исходниках такого нет. Но если речь о каких-то примерах из данной темки, то я уже озвучивал все цифры измерений в комментариях выше.
Прошу прощения, затерялось ))
Обновил код.
А ну ОК, мои результаты в Python:
   0.012 sec;   test_z_interval
   0.327 sec;   test_dict
   0.606 sec;   test_list2
   0.683 sec;   test_list
   0.744 sec;   test_obj
   3.389 sec;   test_freuser_ft_alex_2
   3.436 sec;   test_freuser_ft_alex

и в PyPy:
   0.059 sec;   test_z_interval
   0.067 sec;   test_freuser_ft_alex_2
   0.138 sec;   test_dict
   0.159 sec;   test_list
   0.162 sec;   test_list2
   0.168 sec;   test_obj
   0.748 sec;   test_freuser_ft_alex

Ну и слабая оптимизация test_freuser_ft_alex в PyPy не особо удивительна, т.к. вы тут переделали её в генератор, а такие вещи (там же внутри по сути сопрограмма) неудобны для оптимизатора. Так что ничего странного, не то что с test_z_interval, где действительно нетривиальная ситуация.
Дело в том, что как раз переделанная в генератор в PyPy отработала быстрее, чем полностью аналогичная без генератора. Но тут на самом деле удивляться нечему: просто выскользнуло из внимания, что без генератора нет механизма завершения выполнения и алгоритм выполняет бессмысленный перебор всех оставшихся вариантов. Из-за этого получается сильно заниженный результат. И вот тут как раз возникает другой парадокс: почему в CPython одинаковое время выполнения?
А, ну да, у меня просто измерение времени было внутри главного if'a (перед print'ом), поэтому я разницу с yield не замечал.

А разница там потому, что в PyPy оказывается почему-то используется другой алгоритм обхода элементов множества. В PyPy обходит как есть, начиная с конца. А в Python'e сортирует и обходит с начала. И соответственно если в Питоне у нас попадание происходит на 2002675 варианте (из 2085787), то в PyPy на 116139. «Исправляется» это всё просто: достаточно поменять c={1, 2, 3, 4, 5, 6, 7, 8, 9, 0} на c={0, 9, 8, 7, 6, 5, 4, 3, 2, 1} и результаты генератора в PyPy вернутся к норме — станут одинаково тормозными. )))

P.S. Кстати, судя по всему значительная часть крутой оптимизации PyPy, выявленной в данном обсуждение, на самом деле заключалось в случайном попадание на более выгодную начальную последовательность. )))

P.P.S. Поставил изначальную обратную последовательность в C++ код и повеселился от времени вычисления в 0,13 мс. Мда, всё же данную задачку можно использовать как тест, только если потребовать искать все возможные решения (чтобы код просмотрел все варианты).
И кстати говоря проблему непонятного поведения test_z_interval в PyPy это тоже объясняет. ))) Правда там ещё надо убрать sorted (зачем оно там вообще было?) и можно полюбоваться на миллисекундные результаты и для Питона. Правда это всё несерьёзно уже — нельзя так измерять. Надо требовать выдачу всех возможных комбинаций. )
Изначально sorted ставились для однозначности порядка вычисления и сравнения разных интерпретаторов и механизмов работы с памятью в python. Поскольку порядок играет роль, то в случае использования несортированного множества (set), при каждом запуске порядок элементов в множестве различается, задача найти единственное решение даёт достаточно широкий разброс времени выполнения от долей секунды до десятков секунд и это лишает смысла сравнение.

Вытаскивание m на первое место — это как заметил freuser — действительно «жульничество», но это уже в самой статье обсуждённый вариант — m равна единице и ничему иному и это ускоряет перебор на порядок; постановка её на первое место — автоматически делает её единицей. Если продолжить идти путём жульничества, то мы изначально сразу знаем m, s и o и уже только это сокращает тупой перебор в 720 раз. А если идти до конца, то, как тут выше в комментариях справедливо заметили, всё значительно проще решается на бумажке.
Прошу прощения за поздний комментарий, текучка заела, добрался посмотреть Ваш код только сегодня.
А ведь Вы слегка сжульничали — мой вариант считает все комбинации и выходит после полного перебора, а Ваши мало того, что считают до первого попадания, так еще и ставят 'm' в начало, так что она вообще в переборе не участвует (она ведь равна 1 в ответе, вот уже почти десятикратный выигрыш). Сам перебор не бессмысленный, вполне может быть несколько вариантов ответа, как и не быть ни одного. Если принять, что 'm' может быть 0, то их вообще 24 штук, но тогда условие избыточно (хотя математически верно и задача в принципе решена).
Переделал все подпрограммки с вашего git вместо return на print и добавил return после цикла for (чтобы не ломать счётчик времени), и вот результат (сами цифры не важны, это у меня интерпретатор в Альте кривой какой-то, главное — соразмерность друг с другом):
0.213 sec; test_z_interval
24.966 sec; test_freuser_ft_alex
26.392 sec; test_freuser_ft_alex_2
33.635 sec; test_dict
48.476 sec; test_list2
53.504 sec; test_list
58.025 sec; test_obj
Видите, если не считать z_interval, все остальные медленнее. А то я прямо уважать себя перестал — мало того, что Ваши алгоритмы не понял сразу, особенно z_interval, так еще и мой самый медленный.
test_freuser_ft_alex_2 — это как раз был вариант доработанный до выхода сразу при нахождении первого ответа. Про жульничество я написал чуть выше — это «жульничество» сразу напрашивается на оптимизацию, как только обнаруживается, что разный порядок обработки даёт разную скорость и разница существенна нахождения единственного ответа. test_interval — это уже окончательно оптимизированный вариант.

«А то я прямо уважать себя перестал» — нет, вот это Вы зря, у Вас очень красивое решение, задействующее сильные стороны Python. В любом случае, значительно большая часть времени уходит на написание самого алгоритма, а выполняется он, несопоставимо быстрее даже в самом медленном варианте. Я потратил значительно больше времени на написание, поскольку занимался исследованием эффективности работы самого интерпретатора и наглядности кода при этом и данная задача просто оказалась «в тему».

К сожалению как оптимизировать Ваш вариант мне слёту в голову не пришло, а надо было просто немного уделить этому внимание. Вот новый вариант

gist.github.com/alexander-irbis/34828a5e9dc41940f506

test_freuser_ft_alex_3 — это дополненная «жульничеством» с m функция. В PyPy этот вариант лидирует с отрывом.

Ещё интересно взглянуть на результат test_dict_str2int — это первоначальный вариант, который я использовал, пока не обнаружил, что преобразование из строки в число — это дорого.
test_freuser_ft_alex_2 — это как раз был вариант доработанный до выхода сразу при нахождении первого ответа.
И он отличался от первого на секунды (у Вас на десятые доли), потому что ответ в последних рядах :(
test_freuser_ft_alex_3 — это дополненная «жульничеством» с m функция. В PyPy этот вариант лидирует с отрывом. Ещё интересно взглянуть на результат test_dict_str2int — это первоначальный вариант, который я использовал, пока не обнаружил, что преобразование из строки в число — это дорого.
Ну вот, другое дело — хотя действительно, эти переходы int<->str и обратно всё равно малину портят.
Вот вариант без конвертации (по мотивам Вашего кода — вместо строки список)
def test_freuser_3():
  ten = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}

  def rang(c, msendory):
    if len(msendory) < 8:
      for i in (c):
	if len(msendory) == 0 and i == 0:
	  continue
	msendory.append(i)
	rang(c-{i}, msendory)
	msendory.remove(i)
    else:
      if (msendory[1]*1000+msendory[2]*100+msendory[3]*10+msendory[4]+msendory[0]*1000+msendory[5]*100+msendory[6]*10+msendory[2]) == (msendory[0]*10000+msendory[5]*1000+msendory[3]*100+msendory[2]*10+msendory[7]): print msendory
  rang(ten, [])
  return (-1, -1, -1)
За счет отказа от переходов выигрыш при полном переборе почти вдвое:
0.241 sec; test_z_interval
17.102 sec; test_freuser_3
29.788 sec; test_freuser_ft_alex
34.081 sec; test_dict
35.521 sec; test_freuser_ft_alex_2
52.696 sec; test_list2
53.344 sec; test_list
68.790 sec; test_obj
90.478 sec; test_dict_str2int
а при оптимальном (m вначале и остановка при первом ответе) на четверть от freuser_ft_alex_3:
0.102 sec; test_z_interval
2.196 sec; test_freuser_3
2.841 sec; test_freuser_ft_alex_3
3.233 sec; test_dict
4.949 sec; test_list2
5.634 sec; test_list
6.043 sec; test_obj
7.438 sec; test_dict_str2int
27.013 sec; test_freuser_ft_alex_2
Интересно, в Pypy он догонит z_interval или нет? (Кстати, не могу понять, почему при полном переборе z_interval аж 8 раз дает ответ — depth ведь равно пяти. На каждую букву словаря, что ли).
Боюсь, ещё оптимизировать некуда. Как говорится, постояв на вершине, надо с неё спускаться и лезть на следующую.
Да, вариант test_z_interval исполняется у меня за 13 миллисекунд, но я не вижу смысла сравнивать эту цифру с остальными. Потому как это не другая запись того же алгоритма, а совсем другой алгоритм с дополнительной проверкой, отбрасывающей большинство веток перебора. Т.е. если скажем закодировать этот же алгоритм на C++, то там будут вообще микросекунды. )))

А вот то, что этот код исполняется на PyPy даже дольше, действительно весьма забавно. ))) Но тут думаю все вопросы к авторам PyPy.
test_z_interval был интересен именно в контексте обсуждения «ну и что же считать самым быстрым». Всё относительно. Озвученные Вами результаты остальных тестов сильно не совпадают с полученными мною (и я говорю не об абсолютных числах), это хорошая тема для исследования и лишнее напоминание о бессмысленности преждевременной оптимизиации.

Сравнивать время исполнения с языками типа C++ бессмысленно, но когда время исполнения — в любом случае меньше секунды, значительно интереснее сравнивать трудозатраты программиста, которые для решения этой задачи явно не сопоставимы с затратами машинного времени и оптимизация требуется именно для них.

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

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

Upd. А собственно уже не ждём )
Сравнивать время исполнения с языками типа C++ бессмысленно, но когда время исполнения — в любом случае меньше секунды, значительно интереснее сравнивать трудозатраты программиста, которые для решения этой задачи явно не сопоставимы с затратами машинного времени и оптимизация требуется именно для них.

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

Но даже если забыть о таких задачах, то всё равно быстродействие инструмента позволяет некоторые любопытные вещи. К примеру в данном случае мы можем написать тупейший (но зато короткий и простой) код на C++ вида (да, это опять же получается слегка другой алгоритм):
	array<int, 10> res;
	int& s = res[0]; int& e = res[1]; int& n = res[2]; int& d = res[3]; int& m = res[4]; int& o = res[5]; int& r = res[6]; int& y = res[7];
	iota(res.begin(), res.end(), 0);
	auto to_int=[](initializer_list<int> l) {return accumulate(l.begin(), l.end(), 0, [](unsigned sum,int d){return sum*10+d;});};
    do{
		if(m!=0&&s!=0&&(to_int({s,e,n,d})+to_int({m,o,r,e})==to_int({m,o,n,e,y}))){
			cout<<' '<<to_int({s,e,n,d})<<'\n'<<'+'<<to_int({m,o,r,e})<<'\n'<<"-----"<<'\n'<<to_int({m,o,n,e,y})<<endl;
			break;
		}
    } while(next_permutation(res.begin(), res.end()));

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

На Питоне тоже можно написать такой же тупой код (itertools.permutations у нас имеется), но он будет исполняться неприлично долго. Можно даже ускорить его благодаря наличию itertools.combinations, но всё равно это несравнимые числа.

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

Да, сама статья про монады вообще не интересная вышла. В реальности в современных императивных языках монады не особо нужны. Но всё же есть парочка полезных применений, типа конвейеров (Boost.Range) или продолжений (future.then(...)). Однако автор ничего не сказал про них, а вместо этого привёл пример отлично решающийся без всяких монад, обосновав это классической словесной чепухой в стиле фанатов ФП. В общем общение в комментариях к этой статье было на порядок интереснее самой статьи. )))
Согласен, когда мы не упираемся в зависимость от медленных механизмов вроде диска или сети — это преимущество действительно сильно. И есть задачи не решаемые без выжимания всей производительности. Но, если будет зависимость от дорогих или медленных ресурсов, вперёд всё равно вырвутся «красивый» стиль и язык, позволяющие коду быть лаконичным и понятным (специально не делаю никаких выводов и допущений о единственно верном стиле и языке на все времена)
Попробуйте решить эту задачу с помощью реализации самопального пролога на С++. Интересно на это взглянуть.
Не знаю что за самопальные прологи на C++ имеются в виду. Но на обычном Прологе решение данной задачки записывается в 3 строчки. И считается около 0,7 секунды.
Чуть подправил его. Стало 4 строчки и 0,2 секунды. )))
to_int(D5,D4,D3,D2,D1, R):- R is D5*10000+D4*1000+D3*100+D2*10+D1.
solve(_, S:E:N:D:M:O:R:Y:r):- !,
	S=\=0, M=\=0, to_int(0,S,E,N,D, Send), to_int(0,M,O,R,E, More), to_int(M,O,N,E,Y, Money), Money is Send+More,
	write(' '), writeln(Send), write('+'), writeln(More), writeln('-----'), writeln(Money).
solve(L, R):- member(N, L), delete(L, N, L1), solve(L1, N:R).
solve:- numlist(0, 9, L), solve(L, r).
Брутфорс на лиспе выглядит примерно так же.
(defn as-num [& digits] (apply + (map * (reverse digits) (iterate (partial * 10) 1))))
(some (fn [[s e n d m o r y]] 
        (and (pos? s) (pos? m) (let [send (as-num s e n d) more (as-num m o r e) money (as-num m o n e y)] 
                                 (when (= (+ send more) money) (println send \+ more \= money)))))
      (clojure.math.combinatorics/permutations [0 1 2 3 4 5 6 7 8 9]))
Как вариант наверное можно использовать ленивые комбинации и перестановки. На D выглядит так (nextPermutation — библиотечная функция, combinations — темплейт c rosettacode):
void main() {
    foreach (c; [0,1,2,3,4,5,6,7,8,9].combinations(8)) {
        do {
            // sendmory = c
            auto m = c[4];
            if ( m == 0 )
                continue;
            auto s = c[0]; auto e = c[1]; auto n = c[2]; auto d = c[3];
            auto o = c[5]; auto r = c[6]; auto y = c[7];
            if ( [s,e,n,d].to_int + [m,o,r,e].to_int == [m,o,n,e,y].to_int )
                write(c);
        } while (c.nextPermutation!"a<b");
    }
}


Предлагаю вариант на перле:
Скрытый текст
#!/usr/bin/perl -w
use Time::HiRes qw(gettimeofday tv_interval);

@list = ([0,0],[1,0],[2,0],[3,0],[4,0],[5,0],[6,0],[7,0],[8,0],[9,0]);
sub clear
{
  foreach my $i (@list)
  {
    $i->[1] = 0;
  }
}
sub get
{
  my $idx = int(rand(scalar @list));
  while($list[$idx]->[1] == 1) 
  {
    $idx++;
    $idx = 0 if ($idx >= scalar @list);
  }
  $list[$idx]->[1] = 1;
  return $list[$idx]->[0];
}
sub a2i
{
  my ($a) = @_;
  my $s = 0;
  my $r = 1;
  for( my $v = scalar @$a - 1; $v >= 0; $v -= 1)
  {
    $s += $a->[$v] * $r;
    $r *= 10; 
  }
  return $s;
}
sub check 
{
  my ($a, $b, $c) = @_;
  my $r = a2i($c) == (a2i($b) + a2i($a));
  #print_sol($a, $b, $c);
  return $r;
}
sub print_int 
{
  my ($r) = @_; 
  my $s = ''; 
  foreach my $i (@$r) {$s .= "$i";}
  return $s;
}
sub print_sol 
{
  my ($a, $b, $c) = @_;
  print print_int($a). ' + '.print_int($b).' = '. print_int($c)."\n" ;
}

my $t0      = [gettimeofday()];
my ($a, $b, $c);
do
{
  do
  {
    clear();
    $a = [get(), get(), get(), get()];
    $b = [get(), get(), get(), $a->[1]];
    $c = [$b->[0], $b->[1], $a->[2], $b->[3], get()];
  }
  while ($a->[0] == 0 || $b->[0] == 0 || $c->[0] == 0);
}
while(check($a, $b, $c) == 0);
print_sol($a, $b, $c);
print 'Time spent: '. tv_interval($t0)."\n";


В принципе можно и компактнее, но зато так — понятнее. Единственная проблема, если решения нет, программа этого не поймет.
На практике получается так:
9567 + 1085 = 10652
Time spent: 0.056124
Интересно, какие результаты в среднем будут при случайном перемешивании массива, так как ищем одну перестановку, то не должно быть долго?!

<?php $begin_time = time() - 1272000000 + floatval(microtime()); $a=array(1,2,3,4,5,6,7,8,9,10); $b=array(7,1,3,5,4,6,2,8,10,9); $i=0; while ($i != 3628800) { shuffle($a); if ($a==$b) { print_r($a); break; } $i++; } $end_time = time() - 1272000000 + floatval(microtime()) - $begin_time; echo $end_time;$begin_time = time() - 1272000000 + floatval(microtime()); ?>

Выдает результаты для 3 попыток: 0.056333005428314, 0.26838698983192,
1.1526199877262.
+ Время на сложение и подстановку символов.
Правда, однозначной гарнтии с первой попытки получить, наверное, нет.
Но в среднем проваливается каждая 3-я попытка.

Смотря что Вы имеете в виду «долго». Минимальный результат — миллисекунды или меньше, сколько там нужно, когда цифры ложатся ровно на свои места, максимальный — время полного перебора, когда перебор не завершается нахождением первого найденного ответа, когда удачной является последняя комбинация в переборе.
Sign up to leave a comment.