Comments 57
может быть не прав, вечер уже, устал, но 5 позиций по 10 значений в каждой это разве не 100 тысяч комбинаций? Миллион, если не ошибаюсь, 6 позиций.
С помощью пяти десятичных разрядов можно задать числа от 0 (00 000) до 99 999 --- 100 000 чисел.
А, публикация странноватая какая-то.
Оказывается (ВДРУГ!) к концу статьи, что необходимо использовать все данные в задаче...
Удивительное дело, понимаешь. Кто бы мог предположить!
Да вы правы очепятка моя - поправил)
Предположим простейший вариант. Все адреса в списке - это разные квартиры в одном и том же доме. Т.е. все поля кроме последнего - одинаковые для всех записей, а последнее поле (номер квартиры) - отличается у всех записей (тупо числа до 1 до 100).
Ваш алгоритм на этом посыплется, шанс угадать упадет до 10%, вместо 100%.
Как впрочем и другие.
Я не к тому то алгоритм плох, а к тому, что нужно понимать зону его применимости. И аккуратнее обращаться со словами типа "гарантированный результат", "абсолютная угадываемость" и пр.
так вроде бы по 10 значений в позиции?
диапазон 0–49 на пять категорий по 10 чисел в каждой:
0–9 – условные коды стран,
10–19 – коды городов,
20–29 – улицы,
30–39 – номера домов,
40–49 – номера квартир.
так вроде бы по 10 значений в позиции?
Про такое ограничение в условии ничего не сказано.
условия задачи кратко и ясно:
Есть список из 100 адресов. Каждый адрес состоит из 5 параметров: страна, город, улица, номер дома, номер квартиры.
Программа случайно загадывает один адрес из этого списка.
У пользователя есть до 10 попыток угадать адрес.
В каждой попытке пользователь называет один из 100 адресов и спрашивает: «Правильно ли я угадал?».
Если адрес не совпадает с загаданным, программа не сообщает, какие именно поля не угаданы. Вместо этого она возвращает подсказку: число от 0 до 5 – сколько параметров из пяти совпало, или -1 (минус один), если не совпало ничего.
Цель – разработать алгоритм, который гарантированно найдет загаданный адрес не более чем за 10 попыток, используя числа совпавших параметров как подсказки.
если больше 10 значений у поля, то гарантированного решения не будет - как писали выше, представим случай когда все поля совпадают а одно поле (или несколько) имеют больше 10 значений и секретная комбинация среди них.
впечатление что условие написано не точно так как в коде и описании решения в поле до 10 значений.
подозреваю что в условии значения в полях не повторяются, тогда делением множества можно шагов за 5-6 в среднем найти решение.
нерешаемо к примеру ни когда 100 квартир, а все остальные параметры совпадают, и когда 10 стран и 10 квартир и все остальные параметры совпадают, так как повторы не дают подсказки и не соответственно не уменьшают выборку
когда 10 стран и 10 квартир и все остальные параметры совпадают, так как повторы не дают подсказки и не соответственно не уменьшают выборку
Нет. Уменьшают.
Так как мы заранее знаем все адреса - то каждый запрос будет отсекать все варианты с этой страной и квартирой. А значит максимум за 10 запросов - можно найти ответ, надо только, по возможности, не повторяться и со страной и с квартирой.
А вот когда в каком то поле вариантов больше 10 - тогда да, гарантировать нельзя. И тут либо автор ошибся в условии, либо задача в том и состоит чтобы только максимизировать вероятность верного ответа.
Но гадать смысла нет. И к решению автора у меня вопросов нет (кроме того что 4-й этап лишний, но тут автор просто хотел показать течение мысли). Вопросы к точности и категоричности в утверждениях.
Неправда. Давайте построим такой же контрпример!
Пусть у нас первые четыре компоненты - по 10 уникальных значений, а пятая - все 100 (сквозная нумерация всех адресов).
Четыре компоненты задают 4-значные десятичные числа, то есть, там возможна 1000 вариантов. Но чисел всего 100 штук.
Любой запрос даст нам либо ответ "5" (полное совпадение), либо - от 0 до 3. Ответ "4" не может быть, так как это означало бы, что либо пятая компонента совпала, а какая-то другая нет, либо четыре первых совпали, а пятая нет, то есть, сломана сквозная нумерация.
Поэтому пятую компоненту можно просто исключить из рассмотрения, и свести задачу к "угадай 4-значный адрес".
Предположим, что "угадай 5-значный адрес (строго десятичный) за 10 попыток" - заведомо решаемая задача.
В таком случае берём наши 4-значные адреса и добавляем к ним хаотично пятые цифры. Мы свели задачу к известной. Следовательно, "угадай 4-значный адрес" также заведомо решаемая.
Следовательно, существуют наборы адресов со 100 уникальными квартирами, для которых решение всё ещё есть.
Если адреса с точностью до дома уникальны - решение (видимо) есть
Если адрес с точностью до дома одинаков для всех - решения точно нет
Эти две границы можно, наверное, ещё как-то сузить.
Нет тут числа просто для простоты решения - что бы не городить объекты вида Страна Город и тд, Очевидно что страна и город будут всегда разные и т.д. тоест в каждом разряде аналогично свои уникальные 10 цифр.
Вы пишите -
"подозреваю что в условии значения в полях не повторяются, тогда делением множества можно шагов за 5-6 в среднем найти решение."
- данный алгоритм имеет среднее арефметическое 5.7 - поделитесь своим решением ?
Да абсолютно верно
заходит QA в бар и заказывает один из 100 сортов пива
Да действительно дополнил условие - каждая разрядность = 10, Алгоритм выдержит любую комбинацию адресов согласно условиям задачи, сможем легко проверить код я выложил на Гит хаб!
В ручную вобъем ваш вариант.
Правда я не совсем понял - что у вас за вариант такой)
Смотрите числа это просто для упрощения, аналоги городов, стран, улиц ну и там где дома и кв уже не аналоги получается)
И по условию задачи каждый из пяти разрядов имеет не более 10 вариантов, а вы пишите - "тупо числа до 1 до 100"
Это вы как бутто в двоичный код 10ричную систем пихаете)
И по данной задаче тут так и есть что - "гарантированный результат", "абсолютная угадываемость" взяв 100 комбинаций из возможных 100 000 .
а если бы разрядность была 100 то это было бы 100x100x100x100x100 = 10 000 000 000 комбинаций
Эммм... А почему бы не пойти таким путём.
Пусть у нас есть метрика d(a,b) - расстояние Хэмминга между двумя адресами-кортежами.
Изначально множество адресов S состоит из всех 100 штук.
Для каждого адреса a из S строим табличку: H[a][m] = {b : d(a,b) = m}
Выбираем такой адрес a1, для которого разбиение на классы эквивалентности по расстоянию до него наиболее равномерно. (Ну понятно, что для любого a, H[a][5] = {a}, поэтому этот класс мы учитывать не будем).
Делаем пробу a1, получаем расстояние m1, получаем подмножество S1 = H[a1][m].
Для каждого адреса из S (не из S1) снова строим табличку H1[a][m] = {b in S1 : d(a,b) = m}.
Проще говоря, оставляем в классах в H только те, что лежат в S1. Ключами по-прежнему являются все адреса.
Опять же, выбираем такой a2, для которого разбиение на классы в H1 наиболее равномерно.
Делаем пробу a2, и так далее.
Здесь как с корзиной в хешмапе - поиск упирается в нее - если размер корзины больше оставшихся ходов на 2, решения нет.
Если есть подмножества у которых 4 совпадения и больше 10 значений, то придется делать перебор и гарантированного решения нет (первый ход сгорает, остается 9, для 11 и больше значений с 4 совпадениями решения нет).
К примеру дома с 11 квартирами.Или 11 стран с одинаковым адресом.
Аналогично с наборами с 3 совпадениями - там достаточно по 10 и 10 дубликатов - первый ход сгорает на 3 совпадения, второй ход на выяснение оставшейся корзины из 10 значений, 8 ходов недостаточно для перебора из 10, приехали с гарантией.
Ну мы же вроде договорились, что задача без заподлянок в виде 11 адресов, отличающихся в единственной компоненте.
Смысл выбора пробы по наиболее равномерному распределению размеров классов - в том, чтобы как можно сильнее сузить пространство в самом худшем случае. И неважно, этот худший случай "не совпало ничего" или "совпало 3 из 5". А не выбирать такую пробу, у которой именно класс "не совпало ничего" самый большой.
В принципе, можно запустить моделирование. Взяли какую-то стратегию и применили её ко всем 100 адресам. Если вписались в ограничение в 10 попыток, - это дерево решений считаем удачным. Если для каких-то веток дерево слишком высокое, то находим узел, из которого растут высокие ветки, и делаем в нём другую пробу (следующую по предпочтению в нашей стратегии). И убеждаемся, разумеется, что классы эквивалентности там получаются другие, иначе смысла нет менять шило на мыло. Да, в худшем случае это NP-полная задача.
Непонятные условия - откуда то миллион вариантов выполз в тексте, с другой стороны там же по десять значений в параметре в тексте и в коде, что дает 100 тысяч комбинаций, ничего не сказано про совпадающие значения как в полях одного типа (номер дома, квартиры и тд) и разных типов (к примеру значения номеров дома и квартир могут совпадать). К примеру в Ирландии дома не нумеруются, бывает такое а имеют имена. Хорошо еще индекса нет - в России и США он цифровой к примеру а в Канаде и Британии буквенно цифровой.
Может быть автор прояснит условия?
Да соря условие дополнил - по гит хабу очевидно было но тут тоже дописал что на разряд комбинация из 10 вариантов
(немножко накосячил: результат пробы - это величина, противоположная расстоянию Хэмминга, то есть, "5" соответствует расстоянию 0, все компоненты равны)
Мой алгоритм дает среднее арефметическое 5.7 попыток на игру. Если ваш сможет снизить этот показатель будет просто великолепно, немного сложно к пониманию по одному тексту,
если будет возможность киньте ссылку на гит хаб - я бы с интересом посмотрел, потому что звучит впечатлительно) Спасибо
Есть такая детская игра называется "эврика" (куча их клонов). Смысл такой: на скрытом поле выставляем 4 разноцветных фишки. Второй должен их угадать. Выставляя разные комбинации, а загадавший сбоку черными и белыми фишками "говорит" угадал ли позицию и цвет. Для 8 цветов и 4 фишек, гарантированно угадывается за 5 шагов. И больше чем в половине случаев за 4 шага. Что характерно, для 5 фишек это соотношении сохраняется, просто за 4 шага угадываешь немного реже.
У вас конечно чуть сложней, не показывается позиция где произошло угадывание. Но как только увидел описание задачи, сразу вспомнил про игру.
Это у нас "быки и коровы" получаются, современный вариант? :)
Вот и выросло поколение, не читавшее Гика :)
Ещё их называли пики и фамы (но это уже как бы по гиковски). Но там правила намного интереснее, а число попыток меньшее. Тут просто пять параметров, а там 10 возможных объектов (числа от 0 до 9) и их 5 (насколько я помню - 5, не 4) позиций. На уроках, подпольно, проводились турниры. В лучшем случае можно было отгадать за 3-4 попытки, а при огромном везении, но крайне редко - за две.
А откуда взялся диапазон 0-49 ? Почему не 0-99 ? Ведь если дается 100 записей, то и значений в диапазоне может быть 100.
Я тоже не понял откуда именно 0-49. В условиях вообще ничего не сказано какой диапазон адресов есть. Те. сказано только что даётся 100 рандомных адреса .
Т.о условный город у нас может быть из множества всевозможных городов мира, улицы так же. Те у них диапазон в числах условный может быть от 0 до 100000+ только в одном параметре. Общее сочетание 5 параметров считай стремится к бесконечности.
Соответственно, может быть случай, когда все адреса в списке уникальные, те обсолютно каждый адрес ни одним параметром не совпадает с друг с другом. Тогда любая попытка вычислить адрес по весу идёт мимо, ибо вес у всех всегда будет идентичный на любой из попыток угадать.
10 Стра= от 0 до 9
10 Городов = 10 до 19
и т.д.
просто так удобнее, можно было за место этого создать реальных 10 объектов стран и т.д.
Ai в нике автора указывает на источник статьи.
Списки, эмоджи-маркеры и прочие em-dash в наличии.
Галюцинации начинаются прямо с заголовка, который никто из комментаторов не читал. Что за 1 000 000$? Почему он не упоминается в статье? Почему заголовок не является согласованным предложением?
"Краткие и ясные" условия не являются ни ясными (в каком случае в ответ пользователю возвращается число 0, к примеру?), ни полными (автор начинает выдумывать дополнительные условия и вводить ограничения).
Расстрелять. Из крупнокалиберного пулемета.
Доброго вечерочка) Стоп АI смотрите - вам не один АI на данный момент не один хороший такого вот плана алгоритм не когда не выдаст- они пока что так делать не умеют!!!!
Готов поспорить - спросите у любого эксперта по AI.
Мне очень нравиться AI он облегчает рутину,
но само ядро всю самую сложную логику пока делает исключительно человек!
Так что все решение было сделано мною лично!!!
Оформление текста - да я надиктовывал - ибо глупо писать такие большие текста - когда есть возможности облегчит этот труд.
Если у вас какие то сомнения в моей компетентности касаемо алгоритмов - можем провести с вами алгоритмический дуэль я только за)! Хорошего вечера будьте добрее)
Глядишь и фейковые монетки за два взвешивания искать научится
На 5 пункте условия задачи подумал, что эта задача является неким подобием сапера
Че так сразу сливать то. Человек ошибся, всякое бывает. Первая статья. А уже заминусили и отхабрили. Можно было просто подсказать, направить, а не так
Если все адреса полностью разные, с вероятностью 9/10 10 раз получишь -1.
Зы. Ну чуть меньше вероятность, не важно.
На 10-й попытке (если до неё дело вообще дошло) алгоритм делает следующее: перебирает все оставшиеся кандидаты и проверяет их на соответствие всем меткам правды. Кандидат должен удовлетворять каждому условию: скажем, с первой меткой у него должно совпадать ровно столько-то элементов, со второй – ровно столько-то, и т.д. По сути, мы ищем комбинацию, которая одновременно даст ровно нужное число совпадений со всеми нашими предыдущими запросами.
А вот тут не понял. Зачем это нужно если на каждом предыдущем шаге все адреса которые не подходят по совпадениям убираются? В списке адресов должны быть только те что подходят под всё прошлые метки правды иначе они бы были удалены, нет?
Да, я тоже заметил. В целом мог просто делать фильтр по k совпадениям на каждом шагу. Хотя не знаю всегда будет не хуже 10 шагов или нет. Худший случай, который я видел, это когда 3 слота имеют одинаковые значения, а остальные 2 имеют все возможные 10x10 комбинации. Это требует 10 угадываний. В статье вроде и нет строгого доказательства, что алгоритм решит за 10 ходов, для этого надо либо перебирать все варианты (что вероятно нереалистично), либо математически доказать. В принципе задача похожа на мой решатель игры mastermind. Там схожий алгоритм по k совпадениям.
Есть такие редкие случае что конце все таки остаются адреса, как пример - все 9 попыток по 2 угадывания, в таком случае к концу может остаться 5- 7 или даже 10 комбинаций.
Редкие случаи но они бывают
Немного не понял, чем отличается когда ничего не попало 0, от ничего не совпало -1
Очень много вопросов к условию задачи и его интерпретации автором.
Как уже писали, откуда взялось допущение, что разных стран, разных городов, улиц, домов и квартир по десять штук, а не сто? Условия не запрещают всем адресам быть разными квартирами в одном доме. И почему для их обозначения были использованы странные массивы вместо пятизначных чисел, где цифры - это соответствующие компоненты.
Если не угадано ни одного компонента, что вернётся в ответе - 0 или -1?
Конкретно в пунктах - да, дописал условия на один разряд - 10 вариантов.
Хотя в описание решения и по коду это видно)
Вы пишите - Условия не запрещают всем адресам быть разными квартирами в одном доме
Вообще без проблем не запрещают, это будет тогда 10 домов т.к. комбинаций 100 а квартир всего 10
-1 возвращает код при нулевом совпадении
мы сознательно взяли самые "популярные" элементы, чтобы в случае неудачи одним махом отсечь максимальное количество
Не наоборот ли, "непопулярные"?
Второе, так и не въехал в условия задачи. Судя по финальному шагу: разве на эти условия SAT solver натравить не получится? Была когда-то статья на Хабре про алгоритмически-логическое решение судоку.
PS: Картинки - это хорошо, многие пренебрегают их использованием, чтобы ясно донести суть мышления. Но чем их верстать в paint, лучше взять draw.io или вообще голый SVG. И отдельно подумать о незрячих пользователях.
Не наоборот ли, "непопулярные"? - нет именно так как я указал в статье!
Мы же берем комбинацию с самым большим весом - то есть наполняющие ее числа встречаются очень часто в данном списке.
Но чем их верстать в paint, лучше взять draw.io или вообще голый SVG. И отдельно подумать о незрячих пользователях. - хорошо спасибо за наводку - буду осваивать данные проги)
Не понравилась задача. Непонятно зачем дают подсказку из 100 вариантов, фактически раскрывая весь алгоритм решения.
Если адрес не совпадает с загаданным, программа не сообщает, какие именно поля не угаданы. Вместо этого она возвращает подсказку: число от 0 до 5 – сколько параметров из пяти совпало, или -1 (минус один), если не совпало ничего.
А в чём разница между -1 и 0 в данной ситуации?
Опустим моменты с вечно несходящимися цифрами (например 0,01% при 1000 запусков: до 10 попытки добралалась одна десятая одного запуска?) и на то, что текст выглядит крайне похожим на нейронку (опять, может быть что угодно, может человек так пишет).
Но давайте остановимся на самом простом: расширим задачу до поиска среди всех 100 000 вариантов (а не миллиона, как кто-то нашептал автору, потерявшему какой-либо символ степени в моменте с 10^6). Вопрос простой: можно ли найти требуемый адрес и если можно то как?
Ответ на первый вопрос: да. Ответ на второй вопрос дал сам автор (правда не до конца и сам этого не понял).
В чем суть метода? Мы делим для каждого из 100 000 адресов оставшиеся по группам с количеством совпадений частей равным 0, 1, 2, 3 и 4. Тогда берем для начала абсолютно случайный адрес (можно брать каждый раз даже первый адрес из доступных). Пусть нам система вернула 0, в таком случае у нас останется 9^5=59049 вариантов неподходящих ответов. Соответвенно следующий адрес берем из этих вариантов, сохраняя список всех возможных адресов отдельно.
На следующем ходу мы опять взяв любой адрес из оставшихся доступных сокращаем список (оставляем только элементы, встречающиеся в обоих списках, а также убираем текущий адрес, если он случайно попал в этот список). Тогда к десятому ходу у нас в худшем случае останется лишь один адрес (худший случай - ни разу не угадали ни одной компоненты => для каждой из пяти компонент были использованы 9 вариантов из 10 => остается только один вариант суммарного адреса).
Это звучит похоже на "Шаг 5" у автора за тем исключением, что в данном варианте уменьшение списка происходит всегда, а не
начиная примерно с 3-й или 4-й попытки, когда накопилось хоть немного информации
Одна эта фраза напрочь убивает решение автора при поиске загаданного адреса среди всех (случайное повторение одного и того же значения, которое не входит в загаданный адрес).
Доброго дня!
например 0,01% при 1000 запусков: до 10 попытки добралалась одна десятая одного запуска? - Конкретно я делал выборки по 100 000 и по 1 000 000 - код же есть убедитесь сами) Все написано максимально просто
Опустим моменты с словом - добралалась ))))
Я надиктовывал в микрофон аи - что бы самому столько не писать. Но покажите мне такую нейронку которая такие алгоритмы решает ??)) Все решение лично мое)
искать из всех возможных комбинаций 100 000 идея прикольная - но это уже другая задача и тут будет другой подход)
начиная примерно с 3-й или 4-й попытки, когда накопилось хоть немного информации
Одна эта фраза напрочь убивает решение автора при поиске загаданного адреса среди всех (случайное повторение одного и того же значения, которое не входит в загаданный адрес).
Что за повторение не понимаю, возможно не совсем понятно написал в тексте откроте код на гит хабе и проверьте все ок)
Алгоритмическая угадайка от Google: 1 000 000$ как я решил задачу и улучшил свой алгоритм трижды