Пишу программу составления школьных расписаний на Лисп, уже на первом этапе возникли трудности

Здравствуйте, пишу в качестве выпускного проекта программу составления расписаний на Лиспе, при этом испытываю большие сложности с самого начала, в голове практически пусто.
Начать решил с функции проверки расписания на корректность, при этом само расписание представил так:
В корневом списке содержатся классы. Каждый класс - это тоже список. Первым в нем идет номер класса, за ним буква. дальше подряд идут дни.
Каждый день - тоже список. И содержит он ряд описаний уроков. Описание урока (какая неожиданность) - и на этот раз список. Первым в нем идет строка с названием предмета, дальше имя учителя и в конце номер аудитории.
В каждом классе дни начинаются с одного и того-же, и уроки каждый день с одного и того-же. Вся эта мишура списков - суть есть таблица, и для проверки нужно проверить, не ведут ли учителя уроки у разных классов или не занят ли один кабинет сразу несколькими классами.
С чего мне начать? Если бы у всех классов каждый день было одно и тоже количество уроков, было бы проще (тут напрашивается мысль про выравнивание).

0

Сообщение от Regrin1 С чего мне начать?

- рекомендую чуть упростить исходный список:

1) код класса изображать атомом 1A, 2Б (это же Лисп!)
2) непонятно, почему списки уроков каждого класса искусственно разбиты на пары...

После очевидной переработки получим что-то вроде:

А теперь составим список пар вида (Учитель номер-урока):

Запустим и получим:

Дальше - проще. Нужно проверить, нет ли у какого-либо учителя повторения номера урока...

2

Catstail, Спасибо! Отвечу на вопросы:
1) Я понимаю, но проблема в том, что потом нужно будет проверять, какой номер параллели (я ведь правильно применяю термин?) и соответствует ли полученная нагрузка СанПиНам. Или потом отделять числовую часть от буквенной?
2)Разбиты на пары они потому, что я привел такие примеры, где класс учится два дня по два урока. У вас получилось, что классы учатся один день четыре урока.

0

Сообщение от Regrin1 класс учится два дня по два урока

- ну и сделайте список таким:

Естественно, код придется переработать.

0

Сообщение от Regrin1 испытываю большие сложности

Я бы каждый учебный класс сделал отдельным определением/функцией.

1A

==>
'(("математика" "Мария Ивановна" 210)
("русский" "Мария Ивановна" 210)
("физкультура" "Иван Иванович" 102)
("литература" "Румиль" 210))

****
2A - по аналогии

==>
'("русский"
"Мария Ивановна"
210)

***
Для lisp просто сделайте через defun

1

Сообщение от Regrin1 С чего мне начать?

Продумайте, какие сущности у вас в программе, и что с ними можно делать. Думайте как расписание. Будьте расписанием. Например, "урок" может характеризоваться такими параметрами как "кабинет", "класс", "номер в сетке уроков", "час", "учитель". Соответственно, вам нужны какие-то функции навроде lesson-room, lesson-form и т. п. Нужна и функция, создающая урок. Может быть, после этого расписание может оказаться просто списком уроков.

Не зацикливайтесь на списках. Хотя вы можете использовать списки для представления расписания, расписание не есть списки. Вы встаёте на традиционный путь процедурного программирования, о котором много предупреждений: зафиксировать представление данных и плясать от этого представления. Проблема в том, что если представление меняется, то обслуживающий его код становится мусором, и приходится начинать сначала. Не говоря о том, что код становится хуже читаемым, потому что сначала приходится в голове перевести язык предметной области на язык представления и понять, что делается с представлением. (Хороший пример - код функции check в https://www.cyberforum.ru/post15658886.html. В нём нет ни единого слова, специфического для расписаний, это код для списков. Поэтому нужно хорошо держать в голове соответствие между списками и расписаниями, чтобы понять, что он делает. Что характерно, при изменении представления код требует переработки, при этом нужно держать в голове два двухсторонних соответствия: старое списочное представление ↔ расписание ↔ новое списочное представление.) Поэтому в наше время люди стараются не работать непосредственно с представлением. (В частности, эта идея является одной из базовых идей ООП.) Нет нужды держать эти соответствия в голове, если они могут быть выражены в коде. Не надо запоминать, что "car - это на самом деле название предмета". Просто пишете lesson-subject, и всё. Уже сам стандарт лиспа учит нас, что использовать представление - это нормально, но не отменяет пользы специфического словаря. Как известно, в лиспе нет списков, а есть конс-ячейки, и списки реализуются цепочками конс-ячеек. Функции first и rest ничем не отличаются от, соответственно, car и cdr, но они существуют, потому что для списка осмыслено брать "первый элемент" и "остальные элементы", и эта осмысленность не опирается на странные низкоуровневые по происхождению сокращения.

По поводу реализации.

Не старайтесь засунуть все данные в одну таблицу. Например, учитель - это человек. С ним могут быть ассоциированы разные данные - имя-отчество, возможно, телефон, почта, емейл. Причём эта ассоциация может меняться со временем. Совершенно нет нужды совать это всё в расписание. Достаточно поместить туда ID учителя. В качестве ID имеет смысл использовать что-то попроще - по крайней мере, не массив символов, коим является строка. При разработке удобно пользоваться символами, в более разработанной программе могут оказаться удобнее номера, потому что их удобно хранить вне программы (например, в электронной таблице) и (что, по-моему, существенней) автоматически присваивать новые номера новым учителям. Переход на идентификаторы-числа не отразится на программе, если вы не будете сравнивать идентификаторы с помощью eq. А имя-отчество будут в другой таблице, которая будет связывать ID и фамилию, имя, отчество - уже записанные строками. Это будет и чище, и, предвижу, позволит сэкономить на #'string=.

В принципе, можно подумать о том, насколько вы хотите сделать программу объектно-ориентированной, в самом широком смысле. Объект - это сущность, обладающая идентичностью. Есть ли идентичность в вашей предметной области? Осмыслено ли выражение "тот же самый урок"? Не "абсолютно такой же", а "тот же самый"? Пока у вас в программе это никак не ловится, ср.
Списки выглядят одинаково, но это не один и тот же список, а два похожих. В принципе, лисп имеет давнюю объектно-ориентированную традицию: я говорю не о CLOS и его предшественниках, а об использовании для моделирования сущностей с идентичностью (для которых будет естественным термин "тот же самый").

3

Сообщение от chessman2 Для lisp просто сделайте через defun

; А можно так, вариант для CLISP

=>
"welcome to CLISP online ide from JDoodle.com"
(("математика" "Мария Ивановна" 210) ("русский" "Мария Ивановна" 210)
("физкультура" "Иван Иванович" 102) ("литература" "Румиль" 210))
""
"Второй урок в 1А классе"
("русский" "Мария Ивановна" 210)

1

Во, вот это уже в некотором роде ООП. Расписание для 1A - конкретный объект.

С точки зрения стиля там нужно defparameter вместо setq и ушки желательно: *1A*.

1

Я бы сделал как хеш-таблицу где ключ - это номер аудитории, значение - список. Потом добавлял бы по ключу значения в список - ФИО препода и предмет, который он ведёт. Например, если Иван Петрович ведёт историю в 210 аудитории, то добавляем его по этому ключу в хеш-таблицу.
Всё что потом остаётся - это пробежаться по таблице.

1

helter, Очень интересный комментарий. Пожалуйста, разъясните ещё на простых примерах, у вас получилось написать довольно полезный текст, спасибо! Прошу поподробнее рассказать про то, как я могу углубиться в процедурное программирование и как этого избежать.

0

Плохо не процедурное программирование само по себе, а отсутствие того, что в сикпе называют абстракция данных.

Например, человек. Предположим, у человека есть ID, имя, фамилия, емейл. То есть "человек" заключает в себе несколько свойств. Смысл абстракции данных состоит в том, что вы не говорите себе, что "человек есть список, у которого на первом месте записан ID, на втором - имя, на третьем - фамилия, на четвёртом - емейл", а говорите "человек есть штука, к которой я могу применить функцию person-id и получить ID, функцией person-name получить имя, функцией person-surname получить фамилию, функцией person-email получить емейл". Если "человек" объединяет четыре свойства, то с ним совершенно естественно ассоциируются четыре функции-акцессора, которые вынимают эти куски информации. Тот факт, что человека можно реализовать по-разному, никак не влияет на принципиальное существование этих функций-акцессоров. Человек - это чёрная коробка, из которой функциями можно доставать интересующую информацию.

Наряду с функциями-акцессорами нужна функция-конструктор, чтобы эти чёрные коробки откуда-то могли появиться в программе. В данном случае это может быть make-person, которая по ID, имени и т. п. будет возвращать человека.

Таким образом, у вас есть набор из пяти функций, которых достаточно для работы с человеком:
конструктор:
make-person
акцессоры:
person-id
person-name
person-surname
person-email

Реализации человека могут быть самыми разными. Например, в виде списка, структурой, хеш-таблицей, классом. Возможные списковые реализации:
Каждой из этих реализаций соответствуют разные реализации пяти перечисленных выше функций. Если мы, например, выбираем первую списковую реализацию, то person-name - это синоним second (который, в свою времени, является синонимом функции cadr для цепочек конс-ячеек общего вида). Эти реализации "по долгу службы" используют списковые функции, потому что в этом их назначение: установить соответствие между списковым представлением и абстрактными свойствами. Однако вне этих реализаций списковые функции к людям применять не надо, потому что человек не список.

Задача: посчитать, сколько в заданном списке Иванов. Решение:
Это решение отражает логику "человека", а логика не должна ничего знать о реализации. Реализация для логики неважна. Поэтому решение, естественно, не зависит от реализации. Идея независимости в программировании повсюду. "Прибивание гвоздями" уменьшает ценность кода.

Абстракцию данных можно развивать и дальше, и там до настоящего ООП уже недалеко.

Абстракция данных не непреложное правило или закон, а просто приём разработки. Индустрия в целом уже наступала на грабли злоупотребления "сырыми данными". Но иногда можно и зафиксировать реализацию. Например, в CL список - это цепочка конс-ячеек определённого вида, и это вряд ли когда-то изменится. Первый элемент списка всегда можно будет получить функцией car. Это "исключение" базируется на десятилетиях использования и высеченном в камне стандарте.

3

helter, Очень хорошо! Ваши разъяснения крайне интересны. Как вы думаете, имеет ли смысл применять тут CLOS? Проект все таки учебный и нужен для допуска к ЕГЭ (Рубикон пройден, и поменять проект мне врядли дозволят). Что будет полезнее, применять абстракции просто объявляя функции, или через CLOS?

0

Думаю, можно и без CLOSа. Хотя, честно говоря, я не очень понимаю, что эта программа должна будет в конечном счёте делать. Неужели расписание составлять?

Сообщение от Regrin1 Не могли бы вы посмотреть его код?

Обязательно посмотрю!

0

Сообщение от helter Цитата Сообщение от Regrin1 Посмотреть сообщение Проект все таки учебный и нужен для допуска к ЕГЭ Не моё дело, но неужели школьников заставляют писать неслабые программы на лиспе для допуска к экзамену? :o

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

0

Сообщение от Regrin1 И программа должна именно составлять расписания!

Тогда вопрос номер один - как? Какие бывают алгоритмы составления расписаний? Я, честно говоря, затрудняюсь оценить комбинаторную сложность этой задачи и не представляю других способов её решения, кроме перебора. (Например, поиск в глубину: если часть сетки уже заполнена и нельзя заполнить следующую ячейку, то откатываем последнюю ячейку и заполняем её другим уроком и т. п.) Взлетит или нет - вопрос. Может, взлетит?

Добавлено через 30 минут
По поводу моделирования я подумал - наверно, я бы плясал от урока без привязки к сетке расписания. Например, в 11А нагрузка 10 часов математики в неделю, 2 часа литературы и т. п. - тогда создать 10 объектов - уроков математики, 2 объекта - литература и т. п. А составление расписание - это распределение объектов по сетке. Таким образом, каждый урок "знает" свой класс, предмет, учителя и, скорее всего, знает кабинет.

2

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

4

Ну, если поиск в глубину ничего не найдёт, например, за миллион итераций, я умываю руки. Одно дело - программирование, другое - алгоритмы.

0

helter, ну тут не только в итерациях дело. Допустим у нас есть 30 аудиторий и 100 учителей и надо составить расписание так, чтобы уроки одних учителей в конкретных аудиториях не накладывались на другие. Количество возможных комбинаций уже велико. Плюс нужно учитывать разные аспекты, вроде окон между занятиями, методических дней тд. То есть нужно учитывать много факторов и хранить огромное число состояний.

0

Сообщение от sodda Составление расписаний - это очень сложная задача. А если это крупное учебное заведение, то практически невыполнимое

Уже решали эту задачу, так что теоретически она выполнима:
http://www.mnogosmenka.ru/pilikov/timetable.htm
http://www.mnogosmenka.ru/pilikov/school.htm
От меня ведь никто не требует коммерческого продукта.

0

К счастью, я не знаю, что такое методические дни. В моём представлении состояние, грубо говоря, одно - заполненная часть расписания. Проверок расписания на валидность может быть сколько угодно, но каждая из них сводится к предикату "сломалось ли расписание после заполнения следующей ячейки?". Эти предикаты могут смотреть, какой учитель ведёт урок, в каком кабинете и т. п., потому что такие данные ассоциированы с уроками. Две проверки или двадцать две - дело техники.

А меня пугает комбинаторная сложность. Там же факториалы лезут ото всюду. Грубо говоря, пусть у класса 30 часов в неделю - это 30! перестановок. Пусть, например, 20 классов - это 30!^²⁰ комбинаций. Очень много. Любая программа обработает микроскопическую часть этого пространства. Конечно, поиск по графу за раз отбраковывает целый подграф, но всё равно стандартные алгоритмы, такие, как поиск в глубину, никак не заточены конкретно под расписания, то есть в определённом смысле "тупые". И, по-моему, единственная надежда на то, что валидные расписания плотно натыканы в пространстве комбинаций.

0