Uljahn: 100k символов
wlesavo: ну на питоне полностью правильное отсечение невозможно сделать, ну по крайней мере там сам алгоритм надо оптимизировать а не реализацию
wlesavo: сам все хочу на плюсах сделать, но руки не доходят как-то
wlesavo: 376 на питоне это прямо очень достойно конечно, там человек явно что-то знает
wlesavo: у меня там сейчас что-то типа жадной эволюции для 7+
Uljahn: https://baguzin.ru/wp/razrabotka-optimalnoj-strategii-ig/
Uljahn: вот тут более-менее научный подход
vrabosh: а что такое жадная эволюция?
я код сейчас оптимизировал, что 7 выполняется за 14 ходов, а 8 за 26 и тесты все прохожу..
vrabosh: это я простым алгоритмом сделал, где отсекаю, просто код оптимизировал и тайминг запихнул.. вот так
vrabosh: while (time.time() - st) < 0.05 and isg:
guess, isg, i = find_guess(allGuess, cntAG, found)
cntAG += i
vrabosh: с длины 9 придется другой алгоритм писать. Хотелось одинм все сделать. Пойду статью прочту, может там идеи дадут
Uljahn: там идея в том, как оценивать информационную ёмкость вариантов отсечения
tutubalin: для 10 цифр количество коров вообще не имеет значения
wlesavo: vrabosh ну типа делаем разные догадки, со слабыми изменениями и постепенно увеличиваем количество быков
MadKnight: vrabosh я не понял условия
tutubalin: через битовые маски легко комбинации записывать
tutubalin: и самое главное - очень быстро сравнивать
MadKnight: tutubalin так что ему нужно-то?
vrabosh: def find_guess(allGuess, cntAG, found): http://chat.codingame.com/pastebin/f9a643ce-2c5a-4fd0-952c-7fec3ccede72
vrabosh: MadKnight я хочу чтобы этот скрипт пока дойде то return мог млн раз пройтись
vrabosh: allGuess - дофига записей, в found до 20 допустим, и длина previous_guess десять
vrabosh: в 50мс уложиться)
tutubalin: нельзя объять необъятное
uralbek: vsem privet
MadKnight: vrabosh суть задания-то в чём?
alopikon: https://www.codingame.com/ide/puzzle/bulls-and-cows-2
MadKnight: vrabosh почему бы просто не сохранить все результаты за все ходы и разобрать их сразу объединёнными?
vrabosh: не понял тебя, что имеешь введу
vrabosh: да, чтото вообще не могу придумать эффективный для питона алгоритм для этой задачи, тот который есть и то подсмотрел и просто оптимизировал его по скорости и конкретно под эти быки и коровы
tutubalin: для N=10 там более 3 миллионов вариантов в начале
tutubalin: на питоне просто так все не проверить
MadKnight: нене
MadKnight: я имел ввиду - в процессе как ты делаешь ходы, ты собираешь статистику, и уже из неё пытаешься что-то вычислить
MadKnight: а стартовые ходы можно каким-нить алгоритмом задать общие
tutubalin: стартовые то да. но вот потом надо найти список валидных комбинаций
tutubalin: а для этого надо все возможные комбинации пропустить через первые ходы
tutubalin: либо использовать монтекарлу, и искать не все комбинации, а только некоторые
MadKnight: или скрестить как-то с qsort
MadKnight: причём не параллельным
MadKnight: можно в начале 10 ходов потратить на варианты типа 00000000 111111111 и тд
MadKnight: чтобы узнать общую статистику по цифрам
MadKnight: узнаешь сколько каждой цифры в числе
MadKnight: потом просто перебирай каждую цифру по очерди
MadKnight: из этого числа
MadKnight: сначала узнаёшь все расположения единичек
alopikon: не, не если можно было одинаковые цифры можно было решить очень просто за 6 * лог(n/2) операций
MadKnight: а точно
MadKnight: -забыл что разные
MadKnight: ну так сделай обычный QSort с заменой 2 цифр и тестом на изменение в положительную или отрицательную сторону
MadKnight: можешь прям qsort и вызвать
MadKnight: а в лямбду передать вывод и затем чтение результата
MadKnight: из каких цифр состоит это число?
MadKnight: от 0 до n ?
MadKnight: хотя не, тут bubble sort
MadKnight: alopikon или чё там?
alopikon: как понимаю основная трудность это убедиться то что ты не ломаешь счёт с прошлого state
tutubalin: если проверять 11111, 22222, 33333
tutubalin: то ты потратишь 10 ходов на выяснения малополезной информации
MadKnight: не, эт я думал что цифры могут повторяться
MadKnight: alopikon типа стараться по частям подбирать
MadKnight: tutubalin так а в чём сложность-то?
MadKnight: можно же по одной цифре вообще проверять
MadKnight: можно же просто подобрать все места для всех 10 цифр
MadKnight: перебором отдельных цифр
MadKnight: а, или у вас сумма за все 10 тестов?
alopikon: ну там чем меньше ходов тем лучше тем более как ты будешь по одной цифре проверять в начале? и чтобы попасть на первое место тебе нужно где-то 30 ходов для каждого n
MadKnight: тогда ок
tutubalin: сложность в том, что это задача на оптимизацию. чем меньше попыток, тем круче
MadKnight: да я чёт думал что только за n=10 очки
MadKnight: мы заливать-то можем варианты с повторяющимися цифрами?
MadKnight: всмысле на вывод подавать
alopikon: нет
alopikon: в этом-то и сложность
MadKnight: да не так всё плохо
Uljahn: первая цифра - точно не ноль
MadKnight: Automaton2000 мы должны придумать ответный троллинг
Automaton2000: там как раз на этот угол и отклоняет
Uljahn: единственный подход - менять местами группы цифр, только вот как их выбирать...
MadKnight: сначала каждую пару
MadKnight: потом каждые 0123
MadKnight: строишь таблицу
MadKnight: зависимостей результата от поданного примера
Uljahn: я ещё пробовал сдвиги внутри подгрупп
MadKnight: там вроде возможно вот так:
MadKnight: 10 попыток на числа начинающиеся с i, где каждая цифра на 1 больше предыдущей либо 0
MadKnight: 1234567890
2345678901
....
MadKnight: дальше ещё 10 попыток на то же самое, но каждые 2 цифры меняешь местами
MadKnight: дальше у тебя будет достаточно информации чтобы вычислить точные позиции цифр, но там будет 5 цифр на 5 мест
MadKnight: хотя стоп, я всё ещё думаю о варианте что у нас цифры могут повторяться
vrabosh: я начал пробовать делать, менять местами цифры, начиная с первой.. но чтото накосячил с ифами.. и забил.. надо будет потом заного сделать
MadKnight: в общем я криво сформулировал итог этих 20 тестов, там на самом деле лучше
MadKnight: и не переставлять местами
MadKnight: а
MadKnight: 325476....
MadKnight: хотя стоп, без разницы
MadKnight: крч 20 ходов, и мы сделали разделение на лево и право, как в qsort
MadKnight: дальше делаем то же для 5ти х2 раза
MadKnight: +20 шагов
MadKnight: а дальше - для 2 и для 3
MadKnight: по 2 раза
MadKnight: 1 + 5(?) раз х2
MadKnight: погнали, изи 56 ходов на 10
MadKnight: tutubalin ты ещё тут?
tutubalin: ага
MadKnight: чё думаешь об этом методе?
tutubalin: 20 ходов - это прям очень дофига
tutubalin: там неопределённость примерно 22 бита
tutubalin: но за каждый ход получаешь больше двух бит
tutubalin: (если решать оптимально)
MadKnight: это как так неопределённость посчитали?
MadKnight: и что это означает?
MadKnight: типа число всех перестановок7
tutubalin: перестановок 3 миллиона. все равновероятные
tutubalin: log2(3e6) ~= 22
MadKnight: понял, 22 значит что можно 22 раза делить общее число возможных решений на 2 до тех пор, пока не дойдём до верного решения
MadKnight: и что по хорошему бы за каждый ход делить их на 4
tutubalin: но можно делить не на 2
MadKnight: ну вот на сколько оно делится если залить сначала 123...890 а потом 3254769810 ?
MadKnight: а, у нас же число правильных ответов
MadKnight: я почоему-то юзал только разницу с предыдущим результатом
MadKnight: хорошо, мы идём вверх с 0123 пока не найдём true>0
MadKnight: тогда делимся пополам, кидая половину цифр в области, где они выдавали 0, и узнаём, какие из 5 цифр правильны
MadKnight: дальше так же тестим 2 и 3
MadKnight: хммм не, слишком долго опять
MadKnight: не будем их отделять
tutubalin: тут выше ссылку на годную статью давали
tutubalin: там хорошо объясняется, как правильно делить
tutubalin: суть в том, на наш запрос вариантов ответов может быть очень много от 0:0 до 4:4
tutubalin: каждому из ответов соответствует множество возможных вариантов
tutubalin: вот нам надо найти такой вопрос, что в худшем случае количество вариантов было минимальным
MadKnight: так с этим-то и понятно
MadKnight: именно этим я щас и занимаюсь
MadKnight: в точности в таком понимании
MadKnight: тыж программист-олимпиадник
MadKnight: разбиение задач на математику - это норма
MadKnight: ну в начале нам полобому надо собрать какую-то информацию
MadKnight: в начале полюбому идём с 0123 вверх
MadKnight: хорошо, в начале мы проходим до 10 итераций с 0132 вверх, строя таблицу
MadKnight: потом берём любую диагональ где не 0, и поднимаем все нечётные числа на 2
MadKnight: итог - у нас есть ответ для этих же 5 чисел, у нас есть ответ для этих же других чисел, и у нас есть общий ответ
MadKnight: отсюда мы узнаём range числа правильных цифр в каждой из 4 диагоналей по 5
MadKnight: и что эти range'ы взаимосвязаны
MadKnight: дальше делаем так же но с разделением на 2 3 2 3
MadKnight: (всм что у каждой нечётной мы все цифры на 1 повышаем)
MadKnight: так стоп, это же до сих пор не включает остальных цифр
MadKnight: нет, я хотел дальше не так
MadKnight: дальше мы берём другую диагональ с >0, которую мы можем разделить на 2 3 2 3 так, чтобы эта статистика синхронилась с нашей статистикой по 5 5
MadKnight: и когда мы дойдём до 1 1 1 1....
MadKnight: мы узнаем точно положения всех цифр, участвоваших в распределении общего результата на куски - а к тому времени принять участие у нас успеют все цифры
MadKnight: и всё <20 итераций
MadKnight: tutubalin чёнить понял?
MadKnight: vrabosh а ты ещё тут?
uralbek: vsem privet
