Задачка по программированию

  1. 3 г. назад

    Придумал задачу:
    Даны две пачки по несколько строк каждая, разной длины.
    Нужно найти самую короткую подстроку, которая присутствует во всех строках из первой пачки, но отсутствует во всех строках из второй пачки.
    Желательно наиболее простым для написания способом. Скорость работы и размер используемой памяти не важны.

    Ответы: (2) (38) (53) (54)
  2. Кто угадает какое практическое применение имеет эта задача, тому респект.

    Ответы: (39)
  3. webdev Желательно наиболее простым для написания способом

    Цикл в цикле.

    Ответы: (5)
  4. скулем можно пользоваться?

    Ответы: (4)
  5. 1Сергей скулем можно пользоваться?

    Можно

  6. Bumer Цикл в цикле.

    Только цикл в цикле? Или цикл в цикле в цикле?

    Ответы: (6)
  7. webdev Только цикл в цикле?

    только, куда больше. Отсортировал первую табличку и вперед.

  8. не, тут скорее регулярка понадобится. Хз, карочи

    Ответы: (9)
  9. Ладно бы, только строки. Но, все подстроки - это ппц

  10. 1Сергей не, тут скорее регулярка понадобится. Хз, карочи

    Это было бы круто. Но вряд ли

  11. рекурсия тут поможет

    Ответы: (11)
  12. 1Сергей рекурсия тут поможет

    Да хоть GOTO, главное написать программу.

  13. Дай пример пачек. И ответ по задаче.

  14. 1 пачка
    aaaa
    Aa
    Asd
    A

    2 пачка
    aa
    D
    As

    Ответы: (16) (20) (25) (28)
  15. а ответ какой?

    Ответы: (15)
  16. (14) ответ 42

  17. Для (13) ответ "aaa" Если регистр не имеет значения.

  18. Алгоритм такой берем первый символ из первой строки первой пачки, вычисляем хэш, вносим в список проверенных хэшей. Проверяем что этой подстроки нет в сумме строк второй пачки если нет то это искомая подстрока, иначе если там нашлась то расширяем подстроку до след. символа повторяем в цикле.

    Ответы: (21)
  19. Вычисление хэша нужно чтобы не дублировать поиск

  20. В чем отличие если в список вносить не хэш а просто строку?

    Ответы: (22)
  21. Для (13) ответа вообще нет, там неправильные пачки. Такое тоже бывает.
    Другой пример:

    1 пачка
    abaza
    Abaz
    bAzsd
    zbAz

    2 пачка
    aa
    D
    As

    Ответ: ba, потому что эта подстрока есть во всех строках первой пачки, но ее нет ни в одной строке второй пачки.
    baz тоже, но эта подстрока длиннее, поэтому правильный ответ ba.

    Ответы: (42) (43)
  22. Курильщик Алгоритм такой берем первый символ из первой строки первой пачки, вычисляем хэш, вносим в список проверенных хэшей. Проверяем что этой подстроки нет в сумме строк второй пачки если нет то это искомая подстрока, иначе если там нашлась то расширяем подстроку до след. символа повторяем в цикле.

    Искать в сумме строк нельзя, потому что подстрока может оказаться на соединении других строк, а это не считается.

  23. Hans В чем отличие если в список вносить не хэш а просто строку?

    Ни в чем, укурок пытается вас запутать неправильными примерами и условиями, саботирует мою ветку.

    Ответы: (24) (34)
  24. Ну в принципе не важно хотя и эту сумму строк легко подготовить вставив специальный символ, го не принципиально это

    Ответы: (26)
  25. (22) смит опять у тебя горячка.

    Ответы: (34)
  26. Почему "aaa" неправильный ответ для (13) ?

    Ответы: (28)
  27. Курильщик Ну в принципе не важно хотя и эту сумму строк легко подготовить вставив специальный символ, го не принципиально это

    Зачем слеплять строки и вставлять разделитель? Хотя дело твое, если так будет работать, пофигу как решать.

    Ответы: (33)
  28. А.. Во всех ну ок

    Ответы: (31)
  29. Курильщик Почему "aaa" неправильный ответ для (13) ?

    Потому что этой подстроки нет в каждой строке первой пачки.

    Ответы: (30)
  30. Тогда алгоритм чутка переделать надо, но не сильно

  31. (28) да

  32. Курильщик А.. Во всех ну ок

    В первой пачке должно быть во всех строках, во второй пачке не должно быть ни в какой строке.

  33. Перебор подстрок первой строки -- 2 цикла. Потом поиск во всех остальных. В принципе как курильщик и говорил.

  34. webdev Зачем слеплять строки и вставлять разделитель? Хотя дело твое, если так будет работать, пофигу как решать.

    Да это не принципиально

  35. Курильщик (22) смит опять у тебя горячка.

    Какая нафиг горячка? Я не бухаю с тех пор как бухло закончилось.

  36. Веб дев это не Смит. И не Паша.

    Ответы: (36) (37)
  37. 11.02.2021 23:35:55 отредактировано Курильщик

    (35) не может быть!

  38. Hans Веб дев это не Смит. И не Паша.

    Всем Без разницы ...

  39. 12.02.2021 08:52:05 отредактировано sda553

    webdev Желательно наиболее простым для написания способом. Скорость работы и размер используемой памяти не важны.

    Тогда просто перебирай все подстроки в первой пачке и ищи их во второй пачке. Вначале все подстроки размером в 1 символ, потом перебирай подстроки в 2 символа и тд.
    Алгоритм будет работать до второго пришествия, зато просто для написания и понятно.

    Ответы: (40)
  40. 12.02.2021 09:10:41 отредактировано sda553

    webdev Кто угадает какое практическое применение имеет эта задача, тому респект.

    Объяснять ламерам на понятном примере, что такое вложенные циклы

    Ответы: (41)
  41. sda553 Тогда просто перебирай все подстроки в первой пачке и ищи их во второй пачке. Вначале все подстроки размером в 1 символ, потом перебирай подстроки в 2 символа и тд.
    Алгоритм будет работать до второго пришествия, зато просто для написания и понятно.

    Да, можешь так. Этот вариант не противоречит условию

  42. sda553 Объяснять ламерам на понятном примере, что такое вложенные циклы

    Нет

  43. 1. ищем самую короткую строку из 1 пачки
    2. разбиваем ее на подстроки (по минимально возможному количеству символов, из примера (20) два символа)
    3. ищем каждую подстроку во всех строках первой пачки, если не нашли - выбрасываем
    4. если есть во всех строках 1 пачки ищем во второй, если есть - это наш ответ

    Ответы: (43)
  44. assa 1. ищем самую короткую строку из 1 пачки
    2. разбиваем ее на подстроки (по минимально возможному количеству символов, из примера (20) два символа)
    3. ищем каждую подстроку во всех строках первой пачки, если не нашли - выбрасываем
    4. если есть во всех строках 1 пачки ищем во второй, если есть - это наш ответ

    Можно так, вроде уже писали подобное.

  45. 12.02.2021 23:09:42 отредактировано webdev

    Так что, никто не смог написать прогу?
    Давайте упростим немного: можно найти не самую короткую подстроку, а все возможные подстроки, подходящие по условию.

    Ответы: (45) (46) (47)
  46. (44) желания нет. Я алгоритм "тысячи вложенных циклов изложил" тебе осталась тупая работа.

    Ответы: (47)
  47. webdev Так что, никто не смог написать прогу?
    Давайте упростим немного: можно найти не самую короткую подстроку, а все возможные подстроки, подходящие по условию.

    Чо за прогу, вроде про алгоритм речь шла.

    Ответы: (48)
  48. sda553 (44) желания нет. Я алгоритм "тысячи вложенных циклов изложил" тебе осталась тупая работа.

    Алгоритм любой дурак может сочинить, это очень легко. Задача была написать программу.

    Ответы: (49) (50)
  49. Курильщик Чо за прогу, вроде про алгоритм речь шла.

    Какой тогда в задаче смысл, если просто алгоритм писать? Это не интересно. Нужно написать программу. Простую и понятную. Можно даже красивую.

  50. 13.02.2021 03:40:43 отредактировано sda553

    (47) нет, все наоборот.Ну раз ты не в силах написать программу по разжеванному простому алгоритму, то попробуй какую нибудь задачу полегче

  51. webdev Алгоритм любой дурак может сочинить, это очень легко. Задача была написать программу.

    С чего ты взял что была такая задача?

    Ответы: (51)
  52. Курильщик С чего ты взял что была такая задача?

    С того что я ее придумал.

  53. Короче, написал прогу, без использования переменных, без циклов FOR NEXT, без условий, без прерываний программы.
    Единственное что не нравится, это использование внешних массивов внутри лямбда-функций, но видимо без этого не получится.

    Ответы: (53) (54)
  54. 14.02.2021 01:12:31 отредактировано sda553

    (52) ты не решил задачу из (0)
    Нужно простым способом, то есть с FOR NEXT, с условиями и тд

    Ответы: (54)
  55. sda553 (52) ты не решил задачу из (0)
    Нужно простым способом, то есть с FOR NEXT, с условиями и тд

    Решил, читай внимательнее, я же писал выше.

    Ответы: (55)
  56. webdev Решил, читай внимательнее, я же писал выше.

    Мы не видели твоего решения.

    Ответы: (56)
  57. Hans Мы не видели твоего решения.

    Пока не хочу выкладывать чтобы не мешать вам самим придумать красивое решение. А то посмотрите мое, и будете думать на основании его, а не своих идей.

    Ответы: (57) (58)
  58. 14.02.2021 19:16:47 отредактировано sda553

    (56) ты без ифов и циклов решил, по твоим словам, не принимается. Нужно по условию задачи наиболее простое решение. То есть, чтобы даже ламер его легко понял. А значит, нужны всякие ифы и циклы. Решай сначала

    Ответы: (58)
  59. sda553 (56) ты без ифов и циклов решил, по твоим словам, не принимается. Нужно по условию задачи наиболее простое решение. То есть, чтобы даже ламер его легко понял. А значит, нужны всякие ифы и циклы. Решай сначала

    Нет в задаче такого условия что с ифами и прочим говнокодом. Наоборот, желательно чтобы решение было красивым и понятным. Мое решение пока самое идеальное из возможных. Пробую ещё улучшить.

    Ответы: (60)
  60. Твое решение самое некрасивое и не идеальное из возможных. Ты даже алгоритм не сумел придумать.

    Ответы: (61)
  61. 14.02.2021 19:47:07 отредактировано sda553

    webdev Наоборот, желательно чтобы решение было красивым и понятным.

    Понятное решение имеет ифы и циклы. Классический структурированный код без извратов. Так что исправляй

    Ответы: (62)
  62. Курильщик Твое решение самое некрасивое и не идеальное из возможных. Ты даже алгоритм не сумел придумать.

    Тут ты сильно ошибаешься.

    Ответы: (64)
  63. sda553 Понятное решение имеет ифы и циклы.

    Не верно. Без ифов понятнее и красивее.

    Ответы: (63)
  64. (62) ты не справился

  65. (61) переделывай.

  66. Как только я сказал что первый решил задачу, так сразу закудахтали, стало стыдно что не осилили такую простенькую.

или зарегистрируйтесь чтобы ответить!