Дело в том, что в TS как раз есть полнота по Тьюрингу, а у вас сказано — подмножество языка. Вот я и спросил — сохранилась она или нет в вашем подмножестве.
Про бинарный поиск на самом деле хороший вопрос. Банальный, но хороший.
Джун первым делом отсортирует массив, тем самым сделает трудоёмкость O(N log N), что в log N раз трудоёмче линейного поиска.
Сеньор же сперва уточнит, как гарантируется, что массив отсортирован, что делать, если в массиве есть одинаковые элементы, ищем ли мы по значению элемента или по значению поля и т.д. А уже потом с закрытыми глазами напишет на любом известном человечеству языке, хоть на Malbolge.
Потом (уже после написания статьи) я попробовал внедрять их парно. Не помогло. Не знаю почему, но формулы с () и ?: долго не живут. Возможно, просто конкретно для этой задачи они не особо нужны.
Когда получен новый рекорд. То есть хранится некий глобальный лучший результат (минимальный loss). Как только появляется формула лучше (у который loss ниже), она выводится.
Просто обычно формула-лидер достаточно долго держится в топе, и первоначально, когда я просто выводил лучшую формулу в каждом поколении, получал сотни одинаковых строк. Поэтому просто удалил "дубли", теперь выводится только когда действительно есть какие-то подвижки.
Согласен, оценочная функция очень важна. Если говорить о настольных играх, то там есть чит: можно вообще не задавать оценочную функцию, а подбирать её налету с помощью MCTS. Я об этом когда-то писал.
Можно применять не только для настольных игр, а вообще для поиска в дереве, где есть понятия "успех" и "провал".
Правда, если применить MCTS в этой задаче, то и генетический алгоритм уже станет не нужен.
Уже подобное рассматривалось в статье, только там было 3/x.
При x=0 получаем деление на ноль, но из-за битовых операций превращается в ноль.
При x=1 получаем 2.
При x=2 получаем 1.
При x>2 получаем дробное число меньше единицы, которое из-за битовых операций становится нулём.
Таким образом для всех месяцев получаем:
0 2 1 0 0 0 0 0 0 0 0 0
2/x^30
Предыдущее ксорим с 30. Получаем:
30 28 31 30 30 30 30 30 30 30 30 30
Прелесть XOR в том, что в феврале он работает как минус, а в марте — как плюс.
Тут уже несколько совпадений с ожидаемыми ответами, но самое важное — попали в февраль. Это главный смысл этой части — сделать 28 дней в феврале.
7>x
Можно записать и как x<7.
До июля каждый чётный месяц (если нумеровать с нуля) имеет 31 день. В августе эта закономерность инвертируется — теперь уже нечётные месяцы имеют 31 день.
Соответственно, это выражение даёт или true (с января по июль), или false (с августа по декабрь). Из-за последующих битовых операций это превратиться или в 1, или в 0.
1 1 1 1 1 1 1 0 0 0 0 0
x
На первый взгляд кажется, что мы здесь полностью берём значение x, но на самом деле важен только младший бит. Так как число 30 в двоичном виде выглядит как 11110, то позже старшие биты "растворятся" в этих единичках.
По сути, тут мы просто смотрим на чётность номера месяца, который, как уже говорилось, нужен для чередования месяцев с 31 днём.
0 1 0 1 0 1 0 1 0 1 0 1
x^7>x
Как уже говорилось, условие преобразуется в 0 или 1, а у икса важен только младший бит. Таким образом, здесь просто инвертируется младший бит, если месяц до июля включительно. В итоге получаем 1 строго для тех месяцев, в которых 31 день.
1 0 1 0 1 0 1 1 0 1 0 1
2/x^30|x^7>x
Совмещаем результаты:
30 28 31 30 30 30 30 30 30 30 30 30
1 0 1 0 1 0 1 1 0 1 0 1
То есть просто добавляем один день тем месяцам, в которых 31 день, и не меняем остальные. Так как используется не плюс, а побитовый OR, то на март (в котором и так уже правильный ответ) это никак не влияет.
По поводу обратной польской (венгерской) записи согласен, но это больше подходит для языков, где нет встроенного eval. На самом деле я когда-то проводил такой же эксперимент на Java, и там как раз использовал ОПЗ. Причём, у меня в реализации была "багофича". Дело в том, что операторы — это один символ, а число — это несколько цифр. Для простоты я решил сделать, что цифра — это тоже операция, которая берёт с вершины стека число, умножает его на 10 и прибавляет соответствующую цифру. Например, "123" — это поместить в стек 1, затем дописать к нему 2, затем дописать к нему 3. Фича была в том, что, например "x1" получалась корректной записью и означала x*10+1. Разумеется, эволюция начала во всю эксплуатировать это фичу.
В первых вариантах всё-таки причина "застоя" именно в том, что был ограниченный инструментарий. Это было лучшее, что можно было получить с теми операциями. Ну или, возможно, что-то лучше и возможно, но крайне маловероятно. Это примерно как с нейронками, когда количество слоёв/параметров недостаточно для решения задачи — обучение остановится на достаточно высоком loss, просто потому, что сделать лучше принципиально невозможно, если модель недостаточно большая.
4. Согласен )
Помню, была модель эволюции, кажется, называлась Pool, где можно было задавать критерии "красоты" для организмов: более быстрые, или более сложные, или наоборот более медленные и т.д. И можно было прямо в процессе менять и видеть, как постепенно средний состав организмов меняется.
Тут скорее наоборот — не чем бы решить эту задачу, а на какую бы задачу применить генетический алгоритм.
Помимо этого я увлекаюсь codegolf, и периодически возникает необходимость найти какую-нибудь нечеловечески короткую формулу, а полный перебор — это слишком долго.
Почему бы в качестве loss функции не взять просто количество неправильных ответов, от 0 до 12?
Это замедлит эволюцию, потому что все формулы, выдающие 12 неверных ответов, будут иметь одинаковую оценку. Например, y = 42 и y = 9000 одинаково плохи — 12 неправильных ответов. В какую сторону двигаться, чтобы улучшить — неизвестно.
Получится блуждание в темноте, которое рано или поздно (но медленнее, чем через LSE) дойдёт до y = 31, то есть 5 неправильных ответов, и любая мутация будет ухудшать результат. Эволюция остановится.
Вот что-то такое и хотел изначально сделать. Чтобы и растения, которые фотосинтезом питаются, и животные, которые бегать умеют, в идеале — чтобы получились многоклеточные, где каждая клетка имеет специализацию, но работают сообща.
Дело в том, что в TS как раз есть полнота по Тьюрингу, а у вас сказано — подмножество языка. Вот я и спросил — сохранилась она или нет в вашем подмножестве.
И ещё вопрос: в JS/TS тип number — это float64. Сохраняется ли это у вас, или есть возможность использовать целочисленные типы?
Круто! Давно мечтал о чём-то таком.
Вопрос: а система типов TS у вас всё ещё обладает полнотой по Тьюрингу?
Про бинарный поиск на самом деле хороший вопрос. Банальный, но хороший.
Джун первым делом отсортирует массив, тем самым сделает трудоёмкость O(N log N), что в log N раз трудоёмче линейного поиска.
Сеньор же сперва уточнит, как гарантируется, что массив отсортирован, что делать, если в массиве есть одинаковые элементы, ищем ли мы по значению элемента или по значению поля и т.д. А уже потом с закрытыми глазами напишет на любом известном человечеству языке, хоть на Malbolge.
Надо запретить фуры
Я тоже спидтестом смотрел, куда какая скорость. Потому и запрещают.
Не будет возможности самому проверять — придётся верить официальной версии.
И это плохо
Потом (уже после написания статьи) я попробовал внедрять их парно. Не помогло. Не знаю почему, но формулы с () и ?: долго не живут. Возможно, просто конкретно для этой задачи они не особо нужны.
Когда получен новый рекорд. То есть хранится некий глобальный лучший результат (минимальный loss). Как только появляется формула лучше (у который loss ниже), она выводится.
Просто обычно формула-лидер достаточно долго держится в топе, и первоначально, когда я просто выводил лучшую формулу в каждом поколении, получал сотни одинаковых строк. Поэтому просто удалил "дубли", теперь выводится только когда действительно есть какие-то подвижки.
Согласен, оценочная функция очень важна. Если говорить о настольных играх, то там есть чит: можно вообще не задавать оценочную функцию, а подбирать её налету с помощью MCTS. Я об этом когда-то писал.
Можно применять не только для настольных игр, а вообще для поиска в дереве, где есть понятия "успех" и "провал".
Правда, если применить MCTS в этой задаче, то и генетический алгоритм уже станет не нужен.
По порядку:
Уже подобное рассматривалось в статье, только там было 3/x.
При x=0 получаем деление на ноль, но из-за битовых операций превращается в ноль.
При x=1 получаем 2.
При x=2 получаем 1.
При x>2 получаем дробное число меньше единицы, которое из-за битовых операций становится нулём.
Таким образом для всех месяцев получаем:
0 2 1 0 0 0 0 0 0 0 0 0Предыдущее ксорим с 30. Получаем:
30 28 31 30 30 30 30 30 30 30 30 30Прелесть XOR в том, что в феврале он работает как минус, а в марте — как плюс.
Тут уже несколько совпадений с ожидаемыми ответами, но самое важное — попали в февраль. Это главный смысл этой части — сделать 28 дней в феврале.
Можно записать и как
x<7.До июля каждый чётный месяц (если нумеровать с нуля) имеет 31 день. В августе эта закономерность инвертируется — теперь уже нечётные месяцы имеют 31 день.
Соответственно, это выражение даёт или
true(с января по июль), илиfalse(с августа по декабрь). Из-за последующих битовых операций это превратиться или в 1, или в 0.1 1 1 1 1 1 1 0 0 0 0 0На первый взгляд кажется, что мы здесь полностью берём значение
x, но на самом деле важен только младший бит. Так как число30в двоичном виде выглядит как11110, то позже старшие биты "растворятся" в этих единичках.По сути, тут мы просто смотрим на чётность номера месяца, который, как уже говорилось, нужен для чередования месяцев с 31 днём.
0 1 0 1 0 1 0 1 0 1 0 1Как уже говорилось, условие преобразуется в 0 или 1, а у икса важен только младший бит. Таким образом, здесь просто инвертируется младший бит, если месяц до июля включительно. В итоге получаем 1 строго для тех месяцев, в которых 31 день.
1 0 1 0 1 0 1 1 0 1 0 1Совмещаем результаты:
30 28 31 30 30 30 30 30 30 30 30 301 0 1 0 1 0 1 1 0 1 0 1То есть просто добавляем один день тем месяцам, в которых 31 день, и не меняем остальные. Так как используется не плюс, а побитовый OR, то на март (в котором и так уже правильный ответ) это никак не влияет.
Как-то так ;)
По поводу обратной польской (венгерской) записи согласен, но это больше подходит для языков, где нет встроенного eval. На самом деле я когда-то проводил такой же эксперимент на Java, и там как раз использовал ОПЗ. Причём, у меня в реализации была "багофича". Дело в том, что операторы — это один символ, а число — это несколько цифр. Для простоты я решил сделать, что цифра — это тоже операция, которая берёт с вершины стека число, умножает его на 10 и прибавляет соответствующую цифру. Например, "123" — это поместить в стек 1, затем дописать к нему 2, затем дописать к нему 3. Фича была в том, что, например "x1" получалась корректной записью и означала x*10+1. Разумеется, эволюция начала во всю эксплуатировать это фичу.
В первых вариантах всё-таки причина "застоя" именно в том, что был ограниченный инструментарий. Это было лучшее, что можно было получить с теми операциями. Ну или, возможно, что-то лучше и возможно, но крайне маловероятно. Это примерно как с нейронками, когда количество слоёв/параметров недостаточно для решения задачи — обучение остановится на достаточно высоком loss, просто потому, что сделать лучше принципиально невозможно, если модель недостаточно большая.
4. Согласен )
Помню, была модель эволюции, кажется, называлась Pool, где можно было задавать критерии "красоты" для организмов: более быстрые, или более сложные, или наоборот более медленные и т.д. И можно было прямо в процессе менять и видеть, как постепенно средний состав организмов меняется.
Интересный подход к февралю. Я пошёл в лоб: 31-(x==1)*3.
Тут скорее наоборот — не чем бы решить эту задачу, а на какую бы задачу применить генетический алгоритм.
Помимо этого я увлекаюсь codegolf, и периодически возникает необходимость найти какую-нибудь нечеловечески короткую формулу, а полный перебор — это слишком долго.
Сперва хотел выложить на github, но так как писалось очень поспешно, получилось не особо красиво )
Если будет время подчистить — обязательно выложу.
Видел этот пример когда-то давно, и он тоже меня вдохновлял.
О, я что-то подобное видел, только там не на колёсах, а ногами должно было научиться ходить и даже прыгать.
Это замедлит эволюцию, потому что все формулы, выдающие 12 неверных ответов, будут иметь одинаковую оценку. Например, y = 42 и y = 9000 одинаково плохи — 12 неправильных ответов. В какую сторону двигаться, чтобы улучшить — неизвестно.
Получится блуждание в темноте, которое рано или поздно (но медленнее, чем через LSE) дойдёт до y = 31, то есть 5 неправильных ответов, и любая мутация будет ухудшать результат. Эволюция остановится.
Спасибо, о переводе во float как-то не подумал. Это вообще не сложно, просто мысль такая не возникла. Действительно, решило бы проблему.
Вот что-то такое и хотел изначально сделать. Чтобы и растения, которые фотосинтезом питаются, и животные, которые бегать умеют, в идеале — чтобы получились многоклеточные, где каждая клетка имеет специализацию, но работают сообща.
Пока не получилось, увы )