Author Topic: Из заданных букв составить слова  (Read 10960 times)

0 Members and 1 Guest are viewing this topic.

Qwerry

  • Активный участник
  • ***
  • Posts: 117
    • View Profile
Доброго времени суток)
Ситуация такая - изначально было N слов (каждое из которых написано с заглавной буквы). Их разбили на буквы, которые расставили в алфавитном порядке (ААаааббВвв...). Цель - по такому набору букв восстановить слова.

Пока что получилось написать скрипт, проверяющий соответствие нескольких предложенных слов указанному набору, с указанием какие буквы остались не использованными, а какие использовать не надо было.
А вот к созданию автоматического поиска вариантов по "словарю" (блокнот с 200+ слов нужной тематики), не знаю как подойти.  Для полного несчастья словарь может не содержать пару искомых слов или, допустим, содержит нужное слово в другой форме, и потому боюсь просто полное соответствие не поможет, нужно также сохранение наиболее полных вариантов.

Oraven

  • Супермодератор
  • Герой форума
  • *
  • Posts: 3685
  • Котэ
    • View Profile
Re: Из заданных букв составить слова
« Reply #1 on: July 03, 2017, 05:41:50 PM »
Пример текста.

Qwerry

  • Активный участник
  • ***
  • Posts: 117
    • View Profile
Re: Из заданных букв составить слова
« Reply #2 on: July 03, 2017, 10:12:59 PM »
Итак, допустим есть файл города.txt, по которому мы сверяем слова (40 строк):
[spoiler] Абакан
Абинск
1Адлер
Адыгейск
Азов
Алагир
1Алапаевск
Алдан
Александров   
1Александровск
Алупка
Амурск
Анапа
Арзамас
Архангельск
Астрахань
Балашов
1Балтийск
Барнаул
Белгород
Березники
Благовещенск
Братск
Буденновск
Валаам
Верхоянск
Витим
1Владивосток
Владикавказ
Воркута   
Выборг
Галич
Гдов   
Геленджик
Горячинск
Губкин
Дзержинск
Дивногорск
Добрянка
Домодедово
[/spoiler]

Загаданы 5 слов из этого словаря (для наглядности нужные отметила 1), буквы которых сложили вместе и отсортировали по алфавиту, ну и перенесли в файл ГородаБуквы.txt :
[spoiler]
А А А а а а а а
Б
В в в в
д д д
е е е
и и
й
к к к к к
л л л л л
н
о о о
п
р р
с с с с с
т т
[/spoiler]

Трудность в том, что даже алгоритм правильный для поиска продумать не получается пока что.
К примеру, с первой попытки всяко ничего не выйдет (как минимум прога возьмет слово Александров вместо Александровска), но как показать, что надо повторно будет все делать, исследуя все возможные комбинации слов и пропуская те, которые уже были проверены? 
Если брать логику и переменные с простой сверки, то начало видимо будет выглядеть так:

[spoiler]
Code: (clickermann) [Select]
$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]
Кидаю ну совсем уж черновой вариант, работоспособность даже почти не проверена. Просто проблема не только в том, что не знаю Как написать, но и не очень представляю Что писать (логику программы).

Evgenij_M

  • Освоившийся
  • **
  • Posts: 58
    • View Profile
Re: Из заданных букв составить слова
« Reply #3 on: July 03, 2017, 11:00:06 PM »
Я - не академик  ::) , конечно. Но и задача, как я понимаю - не научная, а развлекательная  :)
Поэтому, позвольте поучаствовать мыслями  ;)

Пять загаданных слов представляют собой НАБОР, состоящий из ОПРЕДЕЛЁННОГО КОЛИЧЕСТВА каждого вида символов.
Самое тупое,.. чисто "компьютерное" решение, основанное на использовании БЫСТРОДЕЙСТВИЯ техники - это механически перебрать комбинации из слов, которые не содержат букв, отсутствующих в Наборе. В итоге, количество каждой из разновидностей букв в Наборе и в проверяемых словах должно совпасть (не знаю, понятно ли я выражаюсь  ::) )

Qwerry

  • Активный участник
  • ***
  • Posts: 117
    • View Profile
Re: Из заданных букв составить слова
« Reply #4 on: July 04, 2017, 01:00:09 AM »
Самое тупое,.. чисто "компьютерное" решение, основанное на использовании БЫСТРОДЕЙСТВИЯ техники) - это механически перебрать комбинации из слов ...
Внимание вопрос - почему именно это решение принципиально не появлялось у меня в голове? Зачем-то пыталась его заставить анализировать по одному слову - можно ли в текущую комбинацию впихнуть или нет ??? правда я в тот момент немножко зациклилась на теме - "а вдруг чего-то не окажется в "словаре"".

Фильтров по отсеву не совпадающих слов может быть много, какое их сочетание будет быстрым и правильным, покажет отладка.
Фильтровать можно:
1.  по несовпадению заглавных букв.
2. по несуществующим буквам
3. по равенству числа букв в пяти словах и предложенном наборе букв
4 контрольный фильтр совпадение числа каждой имеющийся в списке буквы с числом букв в пяти словах.
возможно другие фильтры будут более эффективны.

Т.е по сути алгоритм следующий -
1. Анализ каждого слова на предмет букв,  отсутствующих в наборе (с записью номеров строчек этих слов  в исключения) = фильтр 1-2. Сравнение по количеству символов боюсь не подойдет - скорее всего в реальных ситуациях в словаре хотя бы одно слово будет отсутствовать.  А если я в словарь добавлю в словарь  последней строчкой пустоту, это сможет помочь в условии - взято 5 строчек, пусть какие-то буквы остались, но нет использования лишних букв?
2. Выбор первых 5 слов-не_исключений и сравнение с символами набора по числу использования каждой буквы. Тут тоже наиболее  критично будет наличие лишних букв в словах (типа использования 7 "а" вместо 5) - при первой же такой ошибке идти дальше.  Вероятно, номера проверяемых 5 строк-слов должны лежать в массиве? Или как лучше сделать?

Evgenij_M

  • Освоившийся
  • **
  • Posts: 58
    • View Profile
Re: Из заданных букв составить слова
« Reply #5 on: July 04, 2017, 08:13:11 AM »
... "а вдруг чего-то не окажется в "словаре"...

Я вот этот момент не понял  ???
Всё выглядит, как развлекательная головоломка. А какое может быть развлечение, если задача изначально не имеет решения (нужное слово в принципе ОТСУТСТВУЕТ в списке)  ???


...
Фильтровать можно:
...
3. по равенству числа букв в пяти словах и предложенном наборе букв
...

Вот... Именно этот вариант я и имел ввиду  :)

Qwerry

  • Активный участник
  • ***
  • Posts: 117
    • View Profile
Re: Из заданных букв составить слова
« Reply #6 on: July 04, 2017, 12:37:05 PM »
И изначальной "головоломке" давался лишь список букв (для 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. ? при остатке лишних букв   - ситуация отсутствия слова или использования близкого слова (в словаре есть Гора, а загадано Горная) - запись в лог для анализа человеком. Количество допустимых "отсутствующих" слов должна бы решаться добавлением пустых строк в "словарь".

В любом случае, с одной проблемой разобраться получилось, спасибо!
Quote
не очень представляю Что писать (логику программы)
А по поводу "Как писать" -  буду уточнять по ходу дела.

Evgenij_M

  • Освоившийся
  • **
  • Posts: 58
    • View Profile
Re: Из заданных букв составить слова
« Reply #7 on: July 04, 2017, 01:05:57 PM »
А не скажите ли Вы (я серьёзно), зачем Вам эта задача?.. Неужели просто для развлечения?

(если не для развлечения, то почему инструментом решения выбран Clickermann?)

Спасибо...  ::)

Vir

  • Зашел в гости
  • *
  • Posts: 12
    • View Profile
Re: Из заданных букв составить слова
« Reply #8 on: July 04, 2017, 02:24:54 PM »
Если не стоит цель заново придумать велосипед, то для этой задачи проще использовать поиск регулярным выражением. В том же notepad.

Qwerry

  • Активный участник
  • ***
  • Posts: 117
    • View Profile
Re: Из заданных букв составить слова
« Reply #9 on: July 04, 2017, 03:54:10 PM »
А не скажите ли Вы (я серьёзно), зачем Вам эта задача?.. Неужели просто для развлечения?

(если не для развлечения, то почему инструментом решения выбран Clickermann?)
[spoiler=По большому счету  - да, просто для развлечения)] Почему-то удобнее отвечать с конца)
Так получилось, что и в школе информатики особо не было (за исключением 5 класса, где мы обычно лишь в Марио резались, и 10-11, где максимум практиковались в использовании офиса и фотошопа), да и образование гуманитарное (отсюда порой совсем уж идиотские вопросы и ошибки)). В общем, программирование как-то прошло мимо меня. Но по факту же, оно оказалось для меня интересным. В общем, пока что обзавелась таким вот хобби :)
Clickermann довольно простой и имеет достаточно функционала, чтоб решать встречавшиеся мне задачи. Так что пытаться изучать какой-то другой язык прежде, чем минимально уберу ляпы и начну писать что-то дельное здесь - не вижу смысла. Наличие отладчика конечно манит, но и его отсутствие (как способ развития внимательности ;)) полезно. 
А чтоб задачки были не из пальца, решила автоматизировать одну онлайн игрушку, учтя все моменты: миниигры (зумка, волк ловит яйца, еще парочка), особенности боев против разного количества соперников, адекватное поведение при бое в команде, автоответчик,  ну и может  какие еще мысли в голову придут.  Заодно и  с потоками можно будет поиграть)

А по задачке - чуточку надоело с  постоянным IF_PICTURE_IN работать ;D А тут на глаза попался конкурс в духе "кто восстановит все слова". Вот и возникла мысль - а как написать что-то подходящее? [/spoiler]
« Last Edit: July 04, 2017, 04:06:18 PM by Qwerry »

Qwerry

  • Активный участник
  • ***
  • Posts: 117
    • View Profile
Re: Из заданных букв составить слова
« Reply #10 on: July 04, 2017, 04:18:11 PM »
Если не стоит цель заново придумать велосипед, то для этой задачи проще использовать поиск регулярным выражением. В том же notepad.
А если немножко подробнее?
В изобретатели велосипедов мне как-то рано, кататься бы научиться))

Evgenij_M

  • Освоившийся
  • **
  • Posts: 58
    • View Profile
Re: Из заданных букв составить слова
« Reply #11 on: July 04, 2017, 07:21:28 PM »
А не скажите ли Вы (я серьёзно), зачем Вам эта задача?.. Неужели просто для развлечения?

(если не для развлечения, то почему инструментом решения выбран Clickermann?)
По большому счету  - да, просто для развлечения)...

Счастливая Вы  ::) (честное слово)
А я - обожаю создавать устройства, берущие на себя работу человека  (механик я).
В своей работе легко использовал потенциал вычислительной техники.

А вот теперь, когда ушёл работать на себя, торгуя валютой на Форексе, от нечего делать места себе не нахожу  :-[ ...
Под рукой есть и Майкрософт Small Basic (вместе с расширением LitDev - прекраснейший по простоте и функциональности инструмент для непрограммиста, предпочитающего КОДИРОВАТЬ),.. и HiAsm (система графического программирования, позволяющая творить программы вообще без написания кода... и дающая возможность удобнейшим образом рисовать ЛОГИКУ программы), а ИНТЕРЕСНОЙ ЗАДАЧИ - ну хоть убей не попадается  :'(

Вот и завидую всем людям, которые могут вот так вот взять - и начать "ковыряться" в абсолютно бесполезном деле, наслаждаясь процессом (как монахи в Шаолине  :) )

Счастливая Вы...
« Last Edit: July 04, 2017, 07:27:42 PM by Evgenij_M »

Vir

  • Зашел в гости
  • *
  • Posts: 12
    • View Profile
Re: Из заданных букв составить слова
« Reply #12 on: July 05, 2017, 02:22:03 AM »
Quote
Если не стоит цель заново придумать велосипед, то для этой задачи проще использовать поиск регулярным выражением. В том же notepad.
А если немножко подробнее?
1. Открываем в notepad файл с городами.
2. Поиск --> Найти.
3. Ставим галки:  'Учитывать регистр' и 'Регулярное выражение'.
4. В строку найти вставляем: ^[АБВавдеийклнопрст]+$
5. Жмём 'Искать далее'.
Будет найдено 8 городов, которые можно составить из данных букв. 8 это уже не 40 :) Если бы в самом кликере были регулярки, то вполне можно из 8 найти подходящие 5.

Qwerry

  • Активный участник
  • ***
  • Posts: 117
    • View Profile
Re: Из заданных букв составить слова
« Reply #13 on: July 05, 2017, 09:11:22 PM »
Вот и завидую всем людям, которые могут вот так вот взять - и начать "ковыряться" в абсолютно бесполезном деле, наслаждаясь процессом (как монахи в Шаолине  :) )

Счастливая Вы...
Ковыряться в абсолютно бесполезном деле - вот это я запросто) Но для меня удовольствие не в самом погружении в некий процесс, а в достижения в нем задач и подзадач (можно и мелких)). Результат может быть значимым лишь для меня - научилась делать то, разобралась с этим, так еще и бонусом получила нечто, на работу чего посмотреть можно в реальном времени (отсюда и практика на игрушке). А для полного несчастья таких вот занятий вечно очередь выстраивается и часто съедают почти все свободное время

А вот теперь, когда ушёл работать на себя, торгуя валютой на Форексе, от нечего делать места себе не нахожу  :-[ ...
ИНТЕРЕСНОЙ ЗАДАЧИ - ну хоть убей не попадается  :'(

В общем, так и получается, что и мне тоже есть чему завидовать ::) Судя по поиску лишь одной задачи, разбрасывать интересы по мелочам не в ваших привычках и как раз вам и удаётся полностью погружаться в процесс))
Хотя все-таки хочу поделиться одним наблюдением:  нередко из какой-то довольно банальной задачки  может вытекать что-то куда более увлекательное. А потому иной раз стоит взяться за не слишком интересный проект -  там вполне могут оказаться новые люди, новые знания, новые идеи и перспективы.  Образно выражаясь, чтобы в лесу увидеть вершину далекой горы придется лезть на дерево.

Evgenij_M

  • Освоившийся
  • **
  • Posts: 58
    • View Profile
Re: Из заданных букв составить слова
« Reply #14 on: July 05, 2017, 10:27:09 PM »
Цитата: Qwerry
Quote
... иной раз стоит взяться за не слишком интересный проект -  там вполне могут оказаться новые люди, новые знания, новые идеи и перспективы.

Совершенно с Вами солидарен  :(
Где б его только взять,.. этот "не слишком интересный проект"?..  :(