Автокликер Clickermann :: Форум
Основной раздел => Использование => Topic started by: Qwerry on July 03, 2017, 04:45:47 PM
-
Доброго времени суток)
Ситуация такая - изначально было N слов (каждое из которых написано с заглавной буквы). Их разбили на буквы, которые расставили в алфавитном порядке (ААаааббВвв...). Цель - по такому набору букв восстановить слова.
Пока что получилось написать скрипт, проверяющий соответствие нескольких предложенных слов указанному набору, с указанием какие буквы остались не использованными, а какие использовать не надо было.
А вот к созданию автоматического поиска вариантов по "словарю" (блокнот с 200+ слов нужной тематики), не знаю как подойти. Для полного несчастья словарь может не содержать пару искомых слов или, допустим, содержит нужное слово в другой форме, и потому боюсь просто полное соответствие не поможет, нужно также сохранение наиболее полных вариантов.
-
Пример текста.
-
Итак, допустим есть файл города.txt, по которому мы сверяем слова (40 строк):
[spoiler] Абакан
Абинск
1Адлер
Адыгейск
Азов
Алагир
1Алапаевск
Алдан
Александров
1Александровск
Алупка
Амурск
Анапа
Арзамас
Архангельск
Астрахань
Балашов
1Балтийск
Барнаул
Белгород
Березники
Благовещенск
Братск
Буденновск
Валаам
Верхоянск
Витим
1Владивосток
Владикавказ
Воркута
Выборг
Галич
Гдов
Геленджик
Горячинск
Губкин
Дзержинск
Дивногорск
Добрянка
Домодедово
[/spoiler]
Загаданы 5 слов из этого словаря (для наглядности нужные отметила 1), буквы которых сложили вместе и отсортировали по алфавиту, ну и перенесли в файл ГородаБуквы.txt :
[spoiler]
А А А а а а а а
Б
В в в в
д д д
е е е
и и
й
к к к к к
л л л л л
н
о о о
п
р р
с с с с с
т т
[/spoiler]
Трудность в том, что даже алгоритм правильный для поиска продумать не получается пока что.
К примеру, с первой попытки всяко ничего не выйдет (как минимум прога возьмет слово Александров вместо Александровска), но как показать, что надо повторно будет все делать, исследуя все возможные комбинации слов и пропуская те, которые уже были проверены?
Если брать логику и переменные с простой сверки, то начало видимо будет выглядеть так:
[spoiler]
$str_find=""
FOR($a=0,$a<15)
$a_find=strreadln("ГородаБуквы.txt",$a+1)
$str_find=STRCONCAT($str_find, $a_find)
END_CYC
$str_find=STRFILTER($str_find, " 1234567890.,-)", 0) //чищу от возможного хлама
print("Исходные буквы - ",$str_find)
print("Количество - ",STRLEN($str_find))
$check=0
$a_new=0
WHILE($check < 5)
$a_str_find = $str_find // чтоб не портить начальную строчку букв
UNDEFINE($Word_arr) // здесь будет лежать вариант ответов
FOR($a=$a_new,$a<40)
$a_check=STRFILTER(strreadln("города.txt",$a+1), " 1234567890.,-+)", 0)
print("слово ",$a_check)
$err=0
WHILE((STRLEN($a_check)>0)&($err=0))
$a_sim=STRCUT($a_check, 1, 1) //проверка букв
Print($a_sim)
$a_count= STRLEN(STRFILTER($a_str_find, $a_sim, 1)) - STRLEN(STRFILTER($a_check, $a_sim, 1))
IF($a_count<0) //не хватает символов
$err=1
$a_check=0
Print("не подходит")
END_IF
$a_check= STRFILTER($a_check, $a_sim, 0)
$a_new=$a+1 //после того, как слово проверено, надо продолжать с проверки следующего
WAITMS(500)
END_CYC
If($err=0)
Print("подходит")
ARRPUSH($Word_arr, $a_check) // добавить слово в массив
INC($check)
WHILE(STRLEN($a_check)>0) // убрать все буквы, составляющие слово, из общего списка
$a_sim=STRCUT($a_check, 1, 1)
$a_count= STRLEN(STRFILTER($a_str_find, $a_sim, 1)) - STRLEN(STRFILTER($a_check, $a_sim, 1))
$a_str_find= STRFILTER($a_str_find, $a_sim, 0)
FOR($a=0,$a<$a_count) //вернуть в общий список зря убранные буквы
$a_str_find= STRCONCAT($a_str_find, $a_sim)
END_CYC
$a_check= STRFILTER($a_check, $a_sim, 0)
END_CYC
print("Новые исходные буквы - ",$a_str_find)
$a_str_find= STRFILTER($a_str_find, $a_sim, 0)
FOR($a=0,$a<ARRSIZE($Word_arr))
Print($Word_arr[$a])
END_CYC
End_If
.............................
END_CYC
END_CYC
[/spoiler]
Кидаю ну совсем уж черновой вариант, работоспособность даже почти не проверена. Просто проблема не только в том, что не знаю Как написать, но и не очень представляю Что писать (логику программы).
-
Я - не академик ::) , конечно. Но и задача, как я понимаю - не научная, а развлекательная :)
Поэтому, позвольте поучаствовать мыслями ;)
Пять загаданных слов представляют собой НАБОР, состоящий из ОПРЕДЕЛЁННОГО КОЛИЧЕСТВА каждого вида символов.
Самое тупое,.. чисто "компьютерное" решение, основанное на использовании БЫСТРОДЕЙСТВИЯ техники - это механически перебрать комбинации из слов, которые не содержат букв, отсутствующих в Наборе. В итоге, количество каждой из разновидностей букв в Наборе и в проверяемых словах должно совпасть (не знаю, понятно ли я выражаюсь ::) )
-
Самое тупое,.. чисто "компьютерное" решение, основанное на использовании БЫСТРОДЕЙСТВИЯ техники) - это механически перебрать комбинации из слов ...
Внимание вопрос - почему именно это решение принципиально не появлялось у меня в голове? Зачем-то пыталась его заставить анализировать по одному слову - можно ли в текущую комбинацию впихнуть или нет ??? правда я в тот момент немножко зациклилась на теме - "а вдруг чего-то не окажется в "словаре"".
Фильтров по отсеву не совпадающих слов может быть много, какое их сочетание будет быстрым и правильным, покажет отладка.
Фильтровать можно:
1. по несовпадению заглавных букв.
2. по несуществующим буквам
3. по равенству числа букв в пяти словах и предложенном наборе букв
4 контрольный фильтр совпадение числа каждой имеющийся в списке буквы с числом букв в пяти словах.
возможно другие фильтры будут более эффективны.
Т.е по сути алгоритм следующий -
1. Анализ каждого слова на предмет букв, отсутствующих в наборе (с записью номеров строчек этих слов в исключения) = фильтр 1-2. Сравнение по количеству символов боюсь не подойдет - скорее всего в реальных ситуациях в словаре хотя бы одно слово будет отсутствовать. А если я в словарь добавлю в словарь последней строчкой пустоту, это сможет помочь в условии - взято 5 строчек, пусть какие-то буквы остались, но нет использования лишних букв?
2. Выбор первых 5 слов-не_исключений и сравнение с символами набора по числу использования каждой буквы. Тут тоже наиболее критично будет наличие лишних букв в словах (типа использования 7 "а" вместо 5) - при первой же такой ошибке идти дальше. Вероятно, номера проверяемых 5 строк-слов должны лежать в массиве? Или как лучше сделать?
-
... "а вдруг чего-то не окажется в "словаре"...
Я вот этот момент не понял ???
Всё выглядит, как развлекательная головоломка. А какое может быть развлечение, если задача изначально не имеет решения (нужное слово в принципе ОТСУТСТВУЕТ в списке) ???
...
Фильтровать можно:
...
3. по равенству числа букв в пяти словах и предложенном наборе букв
...
Вот... Именно этот вариант я и имел ввиду :)
-
И изначальной "головоломке" давался лишь список букв (для 20! слов) и тематика (т.е. словарь надо собрать самим). Отсюда вероятность того, что какого-то слова там не окажется. Но нахождение вариантов "Все слова кроме 1-2" и указание, из каких букв надо попробовать создать отсутствующие слова - тоже было бы хорошим результатом.
В общем, потому и перевела всё в чуть упрощенную задачку с городами. А вот совсем перестать мудрить и вспомнить про перебор (с правильно выбранными фильтрами) - не смогла)
Алгоритм готов:
1. анализ отдельных строк словаря, и запись в исключение тех, где есть несуществующие буквы
2. создание всех комбинаций(начиная с 1,2,3,4,5), не включающих строки-исключения или слова, уже использованные в этой комбинации (типа 1,1,1,1,1).
2.1.фильтр
2.2.отсеивание комбинаций с излишним использованием букв (4 "а", вместо имевшихся 3)
2.3. при появлении идеальной комбинации - выведение ее через через диалог.
2.4. ? при остатке лишних букв - ситуация отсутствия слова или использования близкого слова (в словаре есть Гора, а загадано Горная) - запись в лог для анализа человеком. Количество допустимых "отсутствующих" слов должна бы решаться добавлением пустых строк в "словарь".
В любом случае, с одной проблемой разобраться получилось, спасибо!
не очень представляю Что писать (логику программы)
А по поводу "Как писать" - буду уточнять по ходу дела.
-
А не скажите ли Вы (я серьёзно), зачем Вам эта задача?.. Неужели просто для развлечения?
(если не для развлечения, то почему инструментом решения выбран Clickermann?)
Спасибо... ::)
-
Если не стоит цель заново придумать велосипед, то для этой задачи проще использовать поиск регулярным выражением. В том же notepad.
-
А не скажите ли Вы (я серьёзно), зачем Вам эта задача?.. Неужели просто для развлечения?
(если не для развлечения, то почему инструментом решения выбран Clickermann?)
[spoiler=По большому счету - да, просто для развлечения)] Почему-то удобнее отвечать с конца)
Так получилось, что и в школе информатики особо не было (за исключением 5 класса, где мы обычно лишь в Марио резались, и 10-11, где максимум практиковались в использовании офиса и фотошопа), да и образование гуманитарное (отсюда порой совсем уж идиотские вопросы и ошибки)). В общем, программирование как-то прошло мимо меня. Но по факту же, оно оказалось для меня интересным. В общем, пока что обзавелась таким вот хобби :)
Clickermann довольно простой и имеет достаточно функционала, чтоб решать встречавшиеся мне задачи. Так что пытаться изучать какой-то другой язык прежде, чем минимально уберу ляпы и начну писать что-то дельное здесь - не вижу смысла. Наличие отладчика конечно манит, но и его отсутствие (как способ развития внимательности ;)) полезно.
А чтоб задачки были не из пальца, решила автоматизировать одну онлайн игрушку, учтя все моменты: миниигры (зумка, волк ловит яйца, еще парочка), особенности боев против разного количества соперников, адекватное поведение при бое в команде, автоответчик, ну и может какие еще мысли в голову придут. Заодно и с потоками можно будет поиграть)
А по задачке - чуточку надоело с постоянным IF_PICTURE_IN работать ;D А тут на глаза попался конкурс в духе "кто восстановит все слова". Вот и возникла мысль - а как написать что-то подходящее? [/spoiler]
-
Если не стоит цель заново придумать велосипед, то для этой задачи проще использовать поиск регулярным выражением. В том же notepad.
А если немножко подробнее?
В изобретатели велосипедов мне как-то рано, кататься бы научиться))
-
А не скажите ли Вы (я серьёзно), зачем Вам эта задача?.. Неужели просто для развлечения?
(если не для развлечения, то почему инструментом решения выбран Clickermann?)
По большому счету - да, просто для развлечения)...
Счастливая Вы ::) (честное слово)
А я - обожаю создавать устройства, берущие на себя работу человека (механик я).
В своей работе легко использовал потенциал вычислительной техники.
А вот теперь, когда ушёл работать на себя, торгуя валютой на Форексе, от нечего делать места себе не нахожу :-[ ...
Под рукой есть и Майкрософт Small Basic (вместе с расширением LitDev - прекраснейший по простоте и функциональности инструмент для непрограммиста, предпочитающего КОДИРОВАТЬ),.. и HiAsm (система графического программирования, позволяющая творить программы вообще без написания кода... и дающая возможность удобнейшим образом рисовать ЛОГИКУ программы), а ИНТЕРЕСНОЙ ЗАДАЧИ - ну хоть убей не попадается :'(
Вот и завидую всем людям, которые могут вот так вот взять - и начать "ковыряться" в абсолютно бесполезном деле, наслаждаясь процессом (как монахи в Шаолине :) )
Счастливая Вы...
-
Если не стоит цель заново придумать велосипед, то для этой задачи проще использовать поиск регулярным выражением. В том же notepad.
А если немножко подробнее?
1. Открываем в notepad файл с городами.
2. Поиск --> Найти.
3. Ставим галки: 'Учитывать регистр' и 'Регулярное выражение'.
4. В строку найти вставляем: ^[АБВавдеийклнопрст]+$
5. Жмём 'Искать далее'.
Будет найдено 8 городов, которые можно составить из данных букв. 8 это уже не 40 :) Если бы в самом кликере были регулярки, то вполне можно из 8 найти подходящие 5.
-
Вот и завидую всем людям, которые могут вот так вот взять - и начать "ковыряться" в абсолютно бесполезном деле, наслаждаясь процессом (как монахи в Шаолине :) )
Счастливая Вы...
Ковыряться в абсолютно бесполезном деле - вот это я запросто) Но для меня удовольствие не в самом погружении в некий процесс, а в достижения в нем задач и подзадач (можно и мелких)). Результат может быть значимым лишь для меня - научилась делать то, разобралась с этим, так еще и бонусом получила нечто, на работу чего посмотреть можно в реальном времени (отсюда и практика на игрушке). А для полного несчастья таких вот занятий вечно очередь выстраивается и часто съедают почти все свободное время
А вот теперь, когда ушёл работать на себя, торгуя валютой на Форексе, от нечего делать места себе не нахожу :-[ ...
ИНТЕРЕСНОЙ ЗАДАЧИ - ну хоть убей не попадается :'(
В общем, так и получается, что и мне тоже есть чему завидовать ::) Судя по поиску лишь одной задачи, разбрасывать интересы по мелочам не в ваших привычках и как раз вам и удаётся полностью погружаться в процесс))
Хотя все-таки хочу поделиться одним наблюдением: нередко из какой-то довольно банальной задачки может вытекать что-то куда более увлекательное. А потому иной раз стоит взяться за не слишком интересный проект - там вполне могут оказаться новые люди, новые знания, новые идеи и перспективы. Образно выражаясь, чтобы в лесу увидеть вершину далекой горы придется лезть на дерево.
-
Цитата: Qwerry
... иной раз стоит взяться за не слишком интересный проект - там вполне могут оказаться новые люди, новые знания, новые идеи и перспективы.
Совершенно с Вами солидарен :(
Где б его только взять,.. этот "не слишком интересный проект"?.. :(
-
Доброго времени суток)
Интересная тут у вас задачка. Мне тоже захотелось попробовать свои силы и написать скрипт. С условиями вроде всё понятно - они все находятся в файле "ГородаБуквы.txt", и все слова начинаются с заглавной буквы. На основе этого файла я сделал несколько фильтров, которые посчитал обязательными для поиска загаданных слов.
К сожалению точно угадать загаданные города у меня не получилось, но получился список городов, среди которых точно есть искомые. Другими словами - список из 40 городов удалось сократить до 9. Не велико достижение. :) И в этом списке, по причине простого везения, город Владивосток на 100% один из искомых (он единственный содержит букву "В"). На этом я и застрял. Если убрать из файла "ГородаБуквы.txt" набор букв "Владивосток" и повторить поиск, то ничего не меняется. Может кто подскажет решение, если оно вообще есть?
Файлы для теста во вложении.
[spoiler=Скрипт]//=============================== Подготовка ================================//
LOGCLEAR
TFREADARR("ГородаБуквы.txt", $arr_chars_tmp)
$arr_chars_tmp_size = ARRSIZE($arr_chars_tmp)
$chars_string = ""
FOR($n = 0, $n < $arr_chars_tmp_size)
$arr_chars_tmp[$n] = STRFILTER($arr_chars_tmp[$n], " ", 0)
$char = STRCUT($arr_chars_tmp[$n], 1, 1)
$charset = STRFILTER($arr_chars_tmp[$n], $char, 1)
//
IF($charset ! "")
ARRPUSH($arr_chars, $charset)
$chars_string = STRCONCAT($chars_string, $char)
END_IF
$charset = STRFILTER($arr_chars_tmp[$n], $char, 0)
//
IF($charset ! "")
ARRPUSH($arr_chars, $charset)
$chars_string = STRCONCAT($chars_string, STRCUT($charset, 1, 1))
END_IF
END_CYC
$max_item_length = STRLEN($chars_string) // максимальная длина слова
//--------------------------------
TFREADARR("Города.txt", $arr_list)
$arr_list_size = ARRSIZE($arr_list)
//=============================== Поиск слов ================================//
FOR($n = 0, $n < $arr_list_size)
$item_length = STRLEN($arr_list[$n])
IF( ($item_length < $max_item_length + 1) & ($item_length ! 0) ) // длина слова подходящая
IF(STRFILTER($arr_list[$n], $chars_string, 0) = "") // слово содержит только нужные символы
FOR($i = 0, $i < $arr_chars_size)
$chars_count = STRLEN($arr_chars[$i])
IF(STRLEN(STRFILTER($arr_list[$n], $arr_chars[$i], 0)) < $item_length - $chars_count) // не верное количество одинаковых символов
$i = $arr_chars_size
$discard = 1 // слово будет отброшено
END_IF
END_CYC
IF($discard = 0)
LOGWRITE ($arr_list[$n]) // подходящее слово, прошедшее все фильтры
ELSE
UNDEFINE($discard)
END_IF
END_IF
END_IF
END_CYC
HALT[/spoiler]
[spoiler=В логе:]
21:34:26 Адлер
21:34:26 Алапаевск
21:34:26 Алдан
21:34:26 Александров
21:34:26 Александровск
21:34:26 Анапа
21:34:26 Балтийск
21:34:26 Братск
21:34:26 Владивосток[/spoiler]
-
Может кто подскажет решение, если оно вообще есть?
Перебрать все варианты составления 5 городов из 9 возможных. Что-то вроде:
Адлер Алапаевск Алдан Александров Александровск
Адлер Алапаевск Алдан Александров Анапа
Адлер Алапаевск Алдан Александров Балтийск
и т. д.
Дальше подбираем вариант, который можно собрать из набора букв.
9! / ((9 - 5)! * 5!) = 126 вариантов (для справки: 5! - факториал числа, 1 * 2 * 3 * 4 * 5 = 120)
Да, не самый быстрый способ.
-
Перебрать все варианты составления 5 городов из 9 возможных. Что-то вроде:
Адлер Алапаевск Алдан Александров Александровск
Адлер Алапаевск Алдан Александров Анапа
Адлер Алапаевск Алдан Александров Балтийск
и т. д.
Дальше подбираем вариант, который можно собрать из набора букв.
9! / ((9 - 5)! * 5!) = 126 вариантов (для справки: 5! - факториал числа, 1 * 2 * 3 * 4 * 5 = 120)
Да, не самый быстрый способ.
Что то ничего не понятно. :-[ Зачем перебирать все варианты составления 5 городов из 9 возможных? По условию мы не знаем сколько слов нужно найти и какие это слова.
И зачем "подбирать вариант, который можно собрать из набора букв", если все 9 слов выбраны скриптом как раз потому, что они гарантированно могут быть собраны из данного набора букв, который нам дан в файле "ГородаБуквы.txt"? Определенно я чего то не вкуриваю(.
Как я понимаю - нужно из 9 слов выкинуть лишние, или доказать, что каждое слово выбрано правильно. Так например в случае с городом Владивосток, как я писал выше.
Можно например подобрать слова, сумма букв которых будет равна сумме букв в файле "ГородаБуквы.txt", но там тоже могут быть варианты, хотя вроде как верняк. :) Может это имелось ввиду под фразой "Перебрать все варианты составления 5 городов из 9 возможных"?
Надо пробовать короче, а если что, придумаем что нибудь)).
-
По условию мы не знаем сколько слов нужно найти и какие это слова.
Количество загаданных слов указано: 5.
Можно например подобрать слова, сумма букв которых будет равна сумме букв в файле "ГородаБуквы.txt"
Чтобы это сделать всё равно придётся перебрать все возможные варианты. Хотя этим можно отбросить часть вариантов, т. к. сравнить количество символов быстрее чем проверить можно ли составить слова из набора букв.
Список всех вариантов из 5 слов:
[spoiler]1. АдлерАлапаевскАлданАлександровАлександровск Символов в строке: 43
2. АдлерАлапаевскАлданАлександровАнапа Символов в строке: 35
3. АдлерАлапаевскАлданАлександровБалтийск Символов в строке: 38
4. АдлерАлапаевскАлданАлександровБратск Символов в строке: 36
5. АдлерАлапаевскАлданАлександровВладивосток Символов в строке: 41
6. АдлерАлапаевскАлданАлександровскАнапа Символов в строке: 37
7. АдлерАлапаевскАлданАлександровскБалтийск Символов в строке: 40
8. АдлерАлапаевскАлданАлександровскБратск Символов в строке: 38
9. АдлерАлапаевскАлданАлександровскВладивосток Символов в строке: 43
10. АдлерАлапаевскАлданАнапаБалтийск Символов в строке: 32
11. АдлерАлапаевскАлданАнапаБратск Символов в строке: 30
12. АдлерАлапаевскАлданАнапаВладивосток Символов в строке: 35
13. АдлерАлапаевскАлданБалтийскБратск Символов в строке: 33
14. АдлерАлапаевскАлданБалтийскВладивосток Символов в строке: 38
15. АдлерАлапаевскАлданБратскВладивосток Символов в строке: 36
16. АдлерАлапаевскАлександровАлександровскАнапа Символов в строке: 43
17. АдлерАлапаевскАлександровАлександровскБалтийск Символов в строке: 46
18. АдлерАлапаевскАлександровАлександровскБратск Символов в строке: 44
19. АдлерАлапаевскАлександровАлександровскВладивосток Символов в строке: 49
20. АдлерАлапаевскАлександровАнапаБалтийск Символов в строке: 38
21. АдлерАлапаевскАлександровАнапаБратск Символов в строке: 36
22. АдлерАлапаевскАлександровАнапаВладивосток Символов в строке: 41
23. АдлерАлапаевскАлександровБалтийскБратск Символов в строке: 39
24. АдлерАлапаевскАлександровБалтийскВладивосток Символов в строке: 44
25. АдлерАлапаевскАлександровБратскВладивосток Символов в строке: 42
26. АдлерАлапаевскАлександровскАнапаБалтийск Символов в строке: 40
27. АдлерАлапаевскАлександровскАнапаБратск Символов в строке: 38
28. АдлерАлапаевскАлександровскАнапаВладивосток Символов в строке: 43
29. АдлерАлапаевскАлександровскБалтийскБратск Символов в строке: 41
30. АдлерАлапаевскАлександровскБалтийскВладивосток Символов в строке: 46
31. АдлерАлапаевскАлександровскБратскВладивосток Символов в строке: 44
32. АдлерАлапаевскАнапаБалтийскБратск Символов в строке: 33
33. АдлерАлапаевскАнапаБалтийскВладивосток Символов в строке: 38
34. АдлерАлапаевскАнапаБратскВладивосток Символов в строке: 36
35. АдлерАлапаевскБалтийскБратскВладивосток Символов в строке: 39
36. АдлерАлданАлександровАлександровскАнапа Символов в строке: 39
37. АдлерАлданАлександровАлександровскБалтийск Символов в строке: 42
38. АдлерАлданАлександровАлександровскБратск Символов в строке: 40
39. АдлерАлданАлександровАлександровскВладивосток Символов в строке: 45
40. АдлерАлданАлександровАнапаБалтийск Символов в строке: 34
41. АдлерАлданАлександровАнапаБратск Символов в строке: 32
42. АдлерАлданАлександровАнапаВладивосток Символов в строке: 37
43. АдлерАлданАлександровБалтийскБратск Символов в строке: 35
44. АдлерАлданАлександровБалтийскВладивосток Символов в строке: 40
45. АдлерАлданАлександровБратскВладивосток Символов в строке: 38
46. АдлерАлданАлександровскАнапаБалтийск Символов в строке: 36
47. АдлерАлданАлександровскАнапаБратск Символов в строке: 34
48. АдлерАлданАлександровскАнапаВладивосток Символов в строке: 39
49. АдлерАлданАлександровскБалтийскБратск Символов в строке: 37
50. АдлерАлданАлександровскБалтийскВладивосток Символов в строке: 42
51. АдлерАлданАлександровскБратскВладивосток Символов в строке: 40
52. АдлерАлданАнапаБалтийскБратск Символов в строке: 29
53. АдлерАлданАнапаБалтийскВладивосток Символов в строке: 34
54. АдлерАлданАнапаБратскВладивосток Символов в строке: 32
55. АдлерАлданБалтийскБратскВладивосток Символов в строке: 35
56. АдлерАлександровАлександровскАнапаБалтийск Символов в строке: 42
57. АдлерАлександровАлександровскАнапаБратск Символов в строке: 40
58. АдлерАлександровАлександровскАнапаВладивосток Символов в строке: 45
59. АдлерАлександровАлександровскБалтийскБратск Символов в строке: 43
60. АдлерАлександровАлександровскБалтийскВладивосток Символов в строке: 48
61. АдлерАлександровАлександровскБратскВладивосток Символов в строке: 46
62. АдлерАлександровАнапаБалтийскБратск Символов в строке: 35
63. АдлерАлександровАнапаБалтийскВладивосток Символов в строке: 40
64. АдлерАлександровАнапаБратскВладивосток Символов в строке: 38
65. АдлерАлександровБалтийскБратскВладивосток Символов в строке: 41
66. АдлерАлександровскАнапаБалтийскБратск Символов в строке: 37
67. АдлерАлександровскАнапаБалтийскВладивосток Символов в строке: 42
68. АдлерАлександровскАнапаБратскВладивосток Символов в строке: 40
69. АдлерАлександровскБалтийскБратскВладивосток Символов в строке: 43
70. АдлерАнапаБалтийскБратскВладивосток Символов в строке: 35
71. АлапаевскАлданАлександровАлександровскАнапа Символов в строке: 43
72. АлапаевскАлданАлександровАлександровскБалтийск Символов в строке: 46
73. АлапаевскАлданАлександровАлександровскБратск Символов в строке: 44
74. АлапаевскАлданАлександровАлександровскВладивосток Символов в строке: 49
75. АлапаевскАлданАлександровАнапаБалтийск Символов в строке: 38
76. АлапаевскАлданАлександровАнапаБратск Символов в строке: 36
77. АлапаевскАлданАлександровАнапаВладивосток Символов в строке: 41
78. АлапаевскАлданАлександровБалтийскБратск Символов в строке: 39
79. АлапаевскАлданАлександровБалтийскВладивосток Символов в строке: 44
80. АлапаевскАлданАлександровБратскВладивосток Символов в строке: 42
81. АлапаевскАлданАлександровскАнапаБалтийск Символов в строке: 40
82. АлапаевскАлданАлександровскАнапаБратск Символов в строке: 38
83. АлапаевскАлданАлександровскАнапаВладивосток Символов в строке: 43
84. АлапаевскАлданАлександровскБалтийскБратск Символов в строке: 41
85. АлапаевскАлданАлександровскБалтийскВладивосток Символов в строке: 46
86. АлапаевскАлданАлександровскБратскВладивосток Символов в строке: 44
87. АлапаевскАлданАнапаБалтийскБратск Символов в строке: 33
88. АлапаевскАлданАнапаБалтийскВладивосток Символов в строке: 38
89. АлапаевскАлданАнапаБратскВладивосток Символов в строке: 36
90. АлапаевскАлданБалтийскБратскВладивосток Символов в строке: 39
91. АлапаевскАлександровАлександровскАнапаБалтийск Символов в строке: 46
92. АлапаевскАлександровАлександровскАнапаБратск Символов в строке: 44
93. АлапаевскАлександровАлександровскАнапаВладивосток Символов в строке: 49
94. АлапаевскАлександровАлександровскБалтийскБратск Символов в строке: 47
95. АлапаевскАлександровАлександровскБалтийскВладивосток Символов в строке: 52
96. АлапаевскАлександровАлександровскБратскВладивосток Символов в строке: 50
97. АлапаевскАлександровАнапаБалтийскБратск Символов в строке: 39
98. АлапаевскАлександровАнапаБалтийскВладивосток Символов в строке: 44
99. АлапаевскАлександровАнапаБратскВладивосток Символов в строке: 42
100. АлапаевскАлександровБалтийскБратскВладивосток Символов в строке: 45
101. АлапаевскАлександровскАнапаБалтийскБратск Символов в строке: 41
102. АлапаевскАлександровскАнапаБалтийскВладивосток Символов в строке: 46
103. АлапаевскАлександровскАнапаБратскВладивосток Символов в строке: 44
104. АлапаевскАлександровскБалтийскБратскВладивосток Символов в строке: 47
105. АлапаевскАнапаБалтийскБратскВладивосток Символов в строке: 39
106. АлданАлександровАлександровскАнапаБалтийск Символов в строке: 42
107. АлданАлександровАлександровскАнапаБратск Символов в строке: 40
108. АлданАлександровАлександровскАнапаВладивосток Символов в строке: 45
109. АлданАлександровАлександровскБалтийскБратск Символов в строке: 43
110. АлданАлександровАлександровскБалтийскВладивосток Символов в строке: 48
111. АлданАлександровАлександровскБратскВладивосток Символов в строке: 46
112. АлданАлександровАнапаБалтийскБратск Символов в строке: 35
113. АлданАлександровАнапаБалтийскВладивосток Символов в строке: 40
114. АлданАлександровАнапаБратскВладивосток Символов в строке: 38
115. АлданАлександровБалтийскБратскВладивосток Символов в строке: 41
116. АлданАлександровскАнапаБалтийскБратск Символов в строке: 37
117. АлданАлександровскАнапаБалтийскВладивосток Символов в строке: 42
118. АлданАлександровскАнапаБратскВладивосток Символов в строке: 40
119. АлданАлександровскБалтийскБратскВладивосток Символов в строке: 43
120. АлданАнапаБалтийскБратскВладивосток Символов в строке: 35
121. АлександровАлександровскАнапаБалтийскБратск Символов в строке: 43
122. АлександровАлександровскАнапаБалтийскВладивосток Символов в строке: 48
123. АлександровАлександровскАнапаБратскВладивосток Символов в строке: 46
124. АлександровАлександровскБалтийскБратскВладивосток Символов в строке: 49
125. АлександровАнапаБалтийскБратскВладивосток Символов в строке: 41
126. АлександровскАнапаБалтийскБратскВладивосток Символов в строке: 43[/spoiler]
Список вариантов, которые по количеству символов, соответствуют количеству символов из файла ГородаБуквы.txt (46 букв):
[spoiler]1. АдлерАлапаевскАлександровАлександровскБалтийск Символов в строке: 46
2. АдлерАлапаевскАлександровскБалтийскВладивосток Символов в строке: 46
3. АдлерАлександровАлександровскБратскВладивосток Символов в строке: 46
4. АлапаевскАлданАлександровАлександровскБалтийск Символов в строке: 46
5. АлапаевскАлданАлександровскБалтийскВладивосток Символов в строке: 46
6. АлапаевскАлександровАлександровскАнапаБалтийск Символов в строке: 46
7. АлапаевскАлександровскАнапаБалтийскВладивосток Символов в строке: 46
8. АлданАлександровАлександровскБратскВладивосток Символов в строке: 46
9. АлександровАлександровскАнапаБратскВладивосток Символов в строке: 46[/spoiler]
Из 9 вариантов выбрать 1 уже проще.
-
Загаданные слова:
Адлер
Алапаевск
Александровск
Балтийск
Владивосток
-
Спасибо за интерес к теме и ваши наработки) Задача пока актуальна, просто последние дни была занята.
Атеист, интересный вариант. А я поленилась делать отдельно строку символов и массив под отдельные символы ($arr_chars). Сразу шла вторая проверка - совпадение по количеству, в итоге, работало дольше.
Vir, спасибо) Но вот вопрос, а как удалось получить все варианты по 5 городов из 9?
Как понимаю, здесь речь о сочетаниях элементов из Н по К. Удалось найти - короткий алгоритм (http://forum.sources.ru/index.php?showtopic=330364) и с подробным объяснением, что и откуда берется (http://www.ie.tusur.ru/books/ProgDevelTech/Glava9/94.htm). Но перевести адекватно в код кликермана пока не вышло(
-
... как удалось получить все варианты по 5 городов из 9?
Получить 5 искомых городов из 9 пока не получилось. Это ответ на утверждение - "Количество загаданных слов указано: 5.", соответственно и названия городов нам известны из подсказки.
Мои достижения заканчиваются на том, что из файла "Города.txt" получен список из 9 городов, которые можно составить из имеющихся букв в файле "ГородаБуквы.txt". Так же было проверено, что количества одинаковых букв в файле "ГородаБуквы.txt" будет достаточно, чтобы собрать каждое из 9 слов в отдельности. Кстати, в моем скрипте есть ошибка в строке 33 (эта строка кода собиралась без учета дубликатов в переменной $chars_string и осталась такой после добавления фильтра дубликатов в строках 17 - 22), максимальная длина слова может быть больше.
Дальше всё только на уровне идей. Например можно выкинуть из списка девяти городов такие, которые содержат только одну букву в файле "ГородаБуквы.txt" и одновременно только одну букву в списке 9 городов. Это буквы "В" и "й". Соответственно города Владивосток и Балтийск. Стоит ли делать такой фильтр или нет непонятно. В другой задаче такой подход не сработает. Хотя такой фильтр неплохо бы иметь под рукой всегда. Выкинув 2 города из 9, мы укорачиваем строку $chars_string и при повторном использовании того же скрипта можем отфильтровать лишние города.
Или же лучше пойти путем, который предложил Vir - складывать слова, считать сумму символов и найти нужную комбинацию слов, которая должна быть равна сумме символов в файле "ГородаБуквы.txt"? Это безусловно нужно сделать, хотя такой подход тоже не всегда даст 100% результат.
Еще нужно определиться - известно ли нам количество искомых городов или нет, чтобы не путать друг друга.
Ситуация такая - изначально было N слов (каждое из которых написано с заглавной буквы).
В общем, видимо придется скомбинировать все идеи в одном скрипте, чтобы получился универсальный инструмент.
-
Еще нужно определиться - известно ли нам количество искомых городов или нет, чтобы не путать друг друга.
Количество искомых слов в принципе известно - оно равно количеству Заглавных букв в файле "ГородаБуквы.txt". Если задача содержала бы не города, слова всё равно писались бы с заглавной. Но вероятно мучить машину (вернее себя), заставляя ее отличать заглавные от строчных и высчитывать общее количество заглавных букв, не стоит. Можно считать, что оно известно и заполняется человеком.
[spoiler] Для программного подсчета Заглавных самая первая из возникших (пусть и откровенно неадекватная) идея: воспользоваться тем, что KEYSTRING("str") печатает текст без учета регистра. Т.е. строка1 (с заглавными) всего из-за пары строчек кода (хотя и за относительно долгое время, т.к. стандартная задержка между нажатиями 30мс) может превратиться в строку2 (тот же текст, но строчными). Создать строку3, содержащую лишь Заглавные буквы, и узнать ее длину не составит труда. [/spoiler]
Что касается идей и пути решения - фильтр на единственную в своем роде букву отличная стратегия (в особенности, когда необходимо найти города своим умом), но с учетом возможности использовать быстродействие компьютера, этот способ вряд ли будет основным. Без перебора комбинаций слов все равно не обойтись.
В общем, видимо придется скомбинировать все идеи в одном скрипте, чтобы получился универсальный инструмент.
Я только ЗА!
P.S.:Всё-таки странный я человек: пока не пожалуюсь "у меня что-то не получается!" - решение найти не могу, стоит пожаловаться - так мозги потихоньку просыпаются, начинаю понимать свои ошибки. В общем, проблема с "перевести адекватно в код кликермана" несколько сдвинулась с мёртвой точки.;D
-
Считает и выводит количество заглавных букв в буфере обмена:
PRINT("Заглавных букв - ",STRLEN(STRFILTER(FROMCLIP(),"АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЭЮЯ",1)))
HALT
-
Количество искомых слов в принципе известно - оно равно количеству Заглавных букв в файле "ГородаБуквы.txt".
Об этом я действительно не подумал, каюсь. :-\ Но это делает проект не универсальным и одноразовым, что наверное еще хуже.
-
Vir, спасибо) Но вот вопрос, а как удалось получить все варианты по 5 городов из 9?
Просто 5 вложенных циклов. Да, это не универсально, т. к. для другого количества слов придётся менять количество циклов. Надо будет посмотреть нормальный алгоритм.
Синтаксис кликермана не знаю, так что могу только схематично написать.
Чтобы было проще понять, будем считать что города это цифры от 1 до 9
arr = {1, 2, 3, 4, 5, 6, 7, 8, 9} // массив из слов
for i = 1, 9 // вместо 9 размер массива
for j = i + 1, 9 // чтобы предыдущий город не повторялся, каждый следующий цикл начинается со следующего слова
for k = j + 1, 9
for l = k + 1, 9
for m = l + 1, 9
log arr[i] arr[j] arr[k] arr[l] arr[m] // получим все возможные варианты из 5 слов
end
end
end
end
endИли же лучше пойти путем, который предложил Vir - складывать слова, считать сумму символов и найти нужную комбинацию слов, которая должна быть равна сумме символов в файле "ГородаБуквы.txt"? Это безусловно нужно сделать, хотя такой подход тоже не всегда даст 100% результат.
Вообще там остаётся только проверить можно ли составить из набора букв (46) строку из 46 букв. Т. е. копируем первый символ строки (строка из 5 городов), удаляем его из набора, копируем второй, удаляем из набора и т. д. Если какого символа в наборе не окажется, значит строка не подходит, проверяем следующую.
-
Вообще там остаётся только проверить можно ли составить из набора букв (46) строку из 46 букв. Т. е. копируем первый символ строки (строка из 5 городов), удаляем его из набора, копируем второй, удаляем из набора и т. д. Если какого символа в наборе не окажется, значит строка не подходит, проверяем следующую.
По моему это очень хорошая и верная идея, но это потребует на самом деле склеивать слова в строки. В подобных алгоритмах удобнее оперировать не самими данными из массива, а их индексами. В нашем случае это суммы букв, из которых состоят слова, то есть складывать (по большей части однозначные) цифры. Причем складывать при условии, что сумма не превысит 46. Если эти суммы отсортированы, то вычисление прерывается при первом превышении контрольной суммы 46, оставшиеся элементы не перебираются и начинается попытка собрать строку из других элементов. Но при таком маленьком объеме данных, потеря пары миллисекунд не существенна.
По поводу "получить все варианты по 5 городов из 9" - обсуждалось подобное здесь - http://crapware.aidf.org/forum/index.php?topic=2358.0
Тяжелая это вещь, либо действительно нужно найти/придумать другой алгоритм. Кстати, когда то я мусолил эту тему в голове недели две наверно, хотел придумать способ лучше, но так и не придумал... забыл. :)
Я все таки не поленился и попробовал найти нужные города после прохода своим скриптом. Первые одиночные буквы в файле "ГородаБуквы.txt" были "В" и "й", соответственно города Владивосток и Балтийск на 100% те что мы искали. После удаления из файла "ГородаБуквы.txt" символов "ВладивостокБалтийск" в нем появились еще одиночные буквы, которые указали на следующие искомые слова, с той же вероятностью 100%. Так все 5 городов были найдены, хотя и вручную. Знать заранее количество искомых городов не потребовалось. Написать такой алгоритм было бы наверно не сложно).
-
Доделала часть с сочетаниями) Решила сразу по универсальному (почти) алгоритму делать. Скину, может кому-то тоже пригодится.
[spoiler]
Из недостатков - не позволяет работать со слишком большими множествами (Сперва максимум был Combine(25,13)=5,2 млн комбинаций, сейчас всё переиграла и стало (75,20) = 803 167 998 497 864 960(комбинаций). Но это уже точно почти предел ;D
/////////////////составление создания сочетаний из Н по М //////Qwerry///////
SUB(fact,$n1,$m1) //пример - из 4 элементов по 2 fact(4,2)// дает $num=6 (комбинаций)
If(($n1=0)^($m1=0)^($n1=$m1))
$num=1
Else
$num= $m1+1
For($i=1,$i<$n1-$m1)
$num=$num*($m1+$i+1)/ ($n1-$m1-$i+1)
END_CYC
End_if
// Print("fact_num ",$m1," ",$n1, " = ",$num)
END_SUB
//
SUB(GenComb,$k2,$n2,$m2)
UNDEFINE($v)
$b=0
$k= $k2
$n=$n2
$m= $m2
While($n>0)
SWITCH($m)
CASE(0)
For($I=0, $i<$n)
ARRPUSH($V, 0)
End_cyc
$n=0
CASE($n)
For($I=0, $i<$n)
ARRPUSH($V, 1)
End_cyc
$n=0
DEFAULT
fact($n-1,$m)
$B= $num
If($k<$B+1)
ARRPUSH($V, 0)
Inc($n,-1)
else
ARRPUSH($V, 1)
Inc($k,-$b)
Inc($n,-1)
Inc($m,-1)
End_if
END_SWITCH
End_cyc
// $res=" " ///для проверки
// For($i=0,$i< ARRSIZE($v))
// $res=STRCONCAT($res, " ",$v[$i])
// End_Cyc
// Print(11-$k2," вариант из ", $n2, " по ",$m2, " - ", $res)
////////преобразование вектора $V(К Из n по m) в числа///////////////////////////////////
UNDEFINE($var)
$numb=1
For($i=$n2, $i>0,-1)
If($v[$n2-$i]=1)
ARRPUSH($Var, $N2-$i) // Или же ARRPUSH($Var,$N2-$i+1), если не для Массива используем
End_if
End_cyc
$result=$var[0]
For($b=1,$b<arrsize($var))
$result=strconcat($result,$var[$b])
End_cyc
print($result)
END_SUB
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
SUB(Combine, $par1, $par2) // $par1>$par2
fact($par1,$par2)
print("комбинаций - ",$Num)
$count= $Num
// UNDEFINE($combo)
For($aa=$count,$aa>0,-1)
GenComb($aa,$par1,$par2)
// $var[_] - массив, содержащий вариант № (элементы от [0] до [$par2])
// $result - строчка, с сочетанием № aa
//ARRPUSH($combo, $result) - Массив с сочетаниями в лексикографическом порядке
End_cyc
END_SUB
$time= $_ms
LogClear
Combine(5,3) // $par1>$par2
//Print(Arrsize( $combo))
Print("Time: ", $_ms-$time)
Halt
[/spoiler]
Поменяла фильтры - сперва проверка длины, дальше - сверка по буквам. В общем результат выглядит так.
[spoiler]17:51:58 Исходные буквы - АААаааааБВвввдддеееиийккккклллллнооопррссссстт
17:51:58 Заглавных букв - 5
17:51:58 Список букв АаБВвдеийклнопрст
17:51:58 31 из 40 - не подходит
17:51:58 9 - подходит!
17:51:58 Адлер, Алапаевск, Алдан, Александров, Александровск, Анапа, Балтийск, Братск, Владивосток
17:51:58 время: 166
17:51:58 комбинаций - 126
17:51:59 01468 - П О Д Х О Д И Т П О Л Н О С Т Ь Ю
17:51:59 АдлерАлапаевскАлександровскБалтийскВладивосток
17:51:59
17:52:01
17:52:01 ********************************************
17:52:01
17:52:01 Найден ответ: АдлерАлапаевскАлександровскБалтийскВладивосток
17:52:01 время: 3305
Или если с более мягкими условиями (На случай неполного совпадения формы загаданного и имеющегося в словаре слова) поиска, то так. С потенциальным отсутствием слова в словаре (правда для этого добавляла в словарь строчку с пробелами/подчеркиванием) - тоже в целом предлагает варианты.
17:58:49 Исходные буквы - АААаааааБВвввдддеееиийккккклллллнооопррссссстт
17:58:49 Заглавных букв - 5
17:58:49 Список букв АаБВвдеийклнопрст
17:58:49 31 из 40 - не подходит
17:58:49 9 - подходит!
17:58:49 Адлер, Алапаевск, Алдан, Александров, Александровск, Анапа, Балтийск, Братск, Владивосток
17:58:49 время: 135
17:58:49 комбинаций - 126
17:58:50 Частично подходит АдлерАлапаевскАлданБалтийскВладивосток
17:58:50 Неиспользованные буквы: ервсскко
17:58:50
17:58:50 Частично подходит АдлерАлапаевскАлданБратскВладивосток
17:58:50 Неиспользованные буквы: левссккиой
17:58:50
17:58:50 Частично подходит АдлерАлапаевскАлександровБалтийскВладивосток
17:58:50 Неиспользованные буквы: ск
17:58:50
17:58:50 01468 - П О Д Х О Д И Т П О Л Н О С Т Ь Ю
17:58:50 АдлерАлапаевскАлександровскБалтийскВладивосток
17:58:50
17:58:53
17:58:53 ********************************************
17:58:53
17:58:53 Найден ответ: АдлерАлапаевскАлександровскБалтийскВладивосток
17:58:53 время: 3557
[/spoiler]
В каком-то смысле программа готова. Всем огромное спасибо за идеи и помощь!
Правда, с тем, что задача может сильно разрастаться (в той, которая подтолкнула к мысли об скрипте, было 20 слов, ну или если брать те же 5 городов, но из более полного списка) - простым перебором не обойтись (особенно с учетом того, как сильно увеличивается число комбинаций буквально из-за 1-2 слов). Так что в итоге нужно будет чередовать механизмы подбора слов (по уникальным буквам, как-то оценивать распространенность буквы (если в списке букв лишь 2 а и 15 о, то слова с А и без О рассматриваются в последнюю очередь). Но это - по мере появления идей и возможностей)