Программирование[10]

Grohuf написал 18 часов назад:

@VovaТак объяснения от гения-тиктокера будут?

Ты решил типо проигнорить мой выше где показано что ты ищешь по сути все время 0

Ок

Grohuf написал 17 часов назад:

и так получается, что изменяя параметры теста можно получать поразительные результаты

Жаль что ни одного "поразительного" результата ты не выложил

эээ

не совсем понял вопрос

ты просто последовательно (рекурсивно) генерируешь все варианты заполнения каждого сосуда каждым видом жидкости, попутно отбраковывая выкидывая комбинации которые не удовлетворяют условиям not allowed liquid и невозможности заполнить минимальный объем очередного сосуда, очередным типом жидкости (тк жидкость уже закончилась, а минимум >0).

Kant написал 14.08.2021 в 16:51:

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

Это всё правильно, только в большой компании может не работать ибо интервьюер вполне может быть плохим - много раз с этим сталкивался, даже когда тимлиды подбирал. А флоу людей за нужную вилку должен идти и в компании должен оставаться профит после прихода/ухода очередного. Так что корпоративная культура приёма faang и тех кто на них ориентируется (яндекс), она безусловно неидеальная, но понять почему её внедрили можно - ну и подготовиться через литкоды один раз в жизни в качестве гимнастики для ума не так страшно.

Drakonian написал 2 часа назад:

Задача:

А какое точное условие - нужно всю жидкость разлить, или чтобы в посудинах было как надо?

Drakonian написал 2 часа назад:

Задача:

Есть произвольное количество посудин с объемами, пусть это будет V1,V2,V3.. и т.д. У каждой емкости есть параметры Minimum Volume - сколько минимально ОБЯЗАТЕЛЬНО нужно заполнить жидкости, Maximum Volume сколько максимально можно заполнить жидкости и Not Allowed Liquids - список жидкостей которые нельзя наливать в конкретную посудину. 
Так же есть произвольное количество жидкостей L1,L2,L3 и т.д. с параметром Volume  - объем жидкости.

Жидкости нельзя перемешивать в посудинах.

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

 

Vessels

V1, min0, max10, L1 not allowed, L5 not allowed

V2, min3, max11

V3, min5, max20

 

Liquids

L1, volume9

L2, volume14

Нужно вернуть список всех возможных комбинаций, чтобы добиться максимального заполнения Liquid в Vessels, можно предположить что общий объем Vessels всегда больше чем общий объем Liquid.

 

Примеры возвращаемого результата:
V1, L2, volume10; V2, L2, volume4; V3, L1, volume9

V1 L2, volume3; V2, L2, volume11; V3, L1, volume9

V2, L1, volume9; V3, L2, volume14

задача довольно плотная, не вижу сходу быстрого решения

но врофел с того, что ты даже полный перебор организовать не смог, с учётом что тут всё в целых числах

(за 3 дня)

ну ты 8-ю симфонию слышал? неговносеточного шахматного соперника пробовал написать наверное?

Analjinn написал 22 минуты назад:

А какое точное условие - нужно всю жидкость разлить, или чтобы в посудинах было как надо?

на сколько я понял, важно вот это:

"Нужно вернуть список всех возможных комбинаций, чтобы добиться максимального заполнения Liquid в Vessels"

Это линейное программирование, можешь в Кормене почитать, с какой-то редакции там есть глава и там должно быть хорошо написано, ну или если наплевать, раз значения только целые -  лениво перебирай.

E1azor написал 14 минут назад:

задача довольно плотная, не вижу сходу быстрого решения

но врофел с того, что ты даже полный перебор организовать не смог, с учётом что тут всё в целых числах

(за 3 дня)

 

ну ты 8-ю симфонию слышал? неговносеточного шахматного соперника пробовал написать наверное?

 

 

так-то полный перебор смог, ты чем читал?

Analjinn написал 2 минуты назад:

Это линейное программирование, можешь в Кормене почитать, с какой-то редакции там есть глава и там должно быть хорошо написано, ну или если наплевать, раз значения только целые -  лениво перебирай.

Если ты про литраж, то там не целые, это Decimal 

Drakonian написал 7 минут назад:

так-то полный перебор смог, ты чем читал?

Drakonian написал 2 часа назад:

Я написал код который перебирает все возможные комбинации друг с другом и выдает этот результат, но я никак не могу задействовать условие что каждый Vessel у которого есть Minimum Volume больше нуля должен обязательно быть наполнен этим минимумом. (по сути берется жидкость, заливается по максимуму в vessel, если жидкость кончилась, берем следующую жидкость, если же посудина кончилась берем следующую посудину и так для всех возможных комбинаций посудин и жидкостей)

 

 

Вот самый простой пример входящих параметров которые у меня не правильно считаются:

Drakonian написал 9 минут назад:

Если ты про литраж, то там не целые, это Decimal 

хз что такое десцимал, то есть у тебя объёмы вещественные?

Полный перебор L и V без учета минимумов
 

а вообще это тебе задачка на подумать, раз ты буквы уже решил, отчитаешься об своем успехе потом

decimal: хранит десятичное дробное число. Если употребляется без десятичной запятой, имеет значение от ±1.0*10-28 до ±7.9228*1028, может хранить 28 знаков после запятой и занимает 16 байт. Представлен системным типом System.Decimal

нихуя тут программисты собрались, не знают что такое decimal

Drakonian написал 3 минуты назад:

а вообще это тебе задачка на подумать

Спасибо. Действительно интересная.

Drakonian написал 3 минуты назад:

Если употребляется без десятичной запятой

Что делает?

Drakonian написал 1 час назад:

Just.Doit написал 1 час назад:

Drakonian написал 2 часа назад:

мне почему-то показалось что эти доп. условия сильно меняют задачу и проще перебором
у меня просто входящих данных не будет много, поэтому полный перебор это вообще пох, это для реальных подсчетов на заводе, обычно там по 3-4 жидкостей и посудин. Думаю в самых редких случаях до 10;10

кста, больше кажется похоже на https://en.wikipedia.org/wiki/Dynamic_programming, хотя я на литкодах (кодилити) тоже этот класс задач сам не решал (вроде)

 

ну типа 

у тебя одному сосуду может соответствовать одна и только одна жидкость (либо он может быть пустым, если мин=0)

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

из всех комбинаций который минимально жизнеспособны можно проходить линейно и разливать попорядку остатки жидкостей до максимума, и потом искать вариации в которых минимальные остатки жикостей остались

(я начал было кодить в сообщении, но понял что для быстрого накида кода решение сложновато и идти в ИДЕ и нормально закодить решение - мотивации нет)

 

Правильно ли я понимаю, что кроме того что я перебираю все варианты со всеми мне еще нужно внутри этого перебора еще раз перебрать все со всем но только по некоторым валидным параметрам (разлив по минимуму и т.д.) ?
 

карчое я не выдержал и наговнокодил на скале алгоритм

кажется работает

думаю нихуя не понятно будет из кода, особенно тем кто не знаком со скалой, но переименовывать и пояснять мне пиздец как лень

ну и понятное дело это первое решение, которое дико не оптимально и по большому счету просто полный перебор

https://scastie.scala-lang.org/hiillJYWRheqLKdXxSq84Q

E1azor написал 7 минут назад:

у тебя объёмы вещественные?

Для тебя иррациональные 

GoldRobot написал 1 минуту назад:

Drakonian написал 5 минут назад:

Если употребляется без десятичной запятой

Что делает?

скопировал откуда-то

Just.Doit написал 1 минуту назад:

кажется работает

Нет

Just.Doit написал 1 час назад:

Drakonian написал 2 часа назад:

Just.Doit написал 2 часа назад:

Drakonian написал 3 часа назад:

мне почему-то показалось что эти доп. условия сильно меняют задачу и проще перебором
у меня просто входящих данных не будет много, поэтому полный перебор это вообще пох, это для реальных подсчетов на заводе, обычно там по 3-4 жидкостей и посудин. Думаю в самых редких случаях до 10;10

кста, больше кажется похоже на https://en.wikipedia.org/wiki/Dynamic_programming, хотя я на литкодах (кодилити) тоже этот класс задач сам не решал (вроде)

 

ну типа 

у тебя одному сосуду может соответствовать одна и только одна жидкость (либо он может быть пустым, если мин=0)

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

из всех комбинаций который минимально жизнеспособны можно проходить линейно и разливать попорядку остатки жидкостей до максимума, и потом искать вариации в которых минимальные остатки жикостей остались

(я начал было кодить в сообщении, но понял что для быстрого накида кода решение сложновато и идти в ИДЕ и нормально закодить решение - мотивации нет)

 

Показать больше  

Правильно ли я понимаю, что кроме того что я перебираю все варианты со всеми мне еще нужно внутри этого перебора еще раз перебрать все со всем но только по некоторым валидным параметрам (разлив по минимуму и т.д.) ?
 

карчое я не выдержал и наговнокодил на скале алгоритм

кажется работает

думаю нихуя не понятно будет из кода, особенно тем кто не знаком со скалой, но переименовывать и пояснять мне пиздец как лень

ну и понятное дело это первое решение, которое дико не оптимально и по большому счету просто полный перебор

https://scastie.scala-lang.org/hiillJYWRheqLKdXxSq84Q

 

 

респект, выглядит красиво, только результат выдает не правильный(

но вообще выглядит очень похоже

ну и конечно обидно что я потрачу больше времени на разбор скала синтаксиса и реализации нечто подобного в процедурном стиле чем на написание с 0 моего варианта 

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

ну давай начнём с формализации задачи, дружок

А это ведь отличное начало

То есть нужно найти матрицу NxM, такую, что суммы по строчкам и суммы по столбцам удовлетворяют заданным ограничениям.

Причём все элементы матрицы неотрицательные, и их общая сумма должна быть максимальна.

i -- номер посудины, j -- номер жидкости

Предлагаю сначала залить в каждую посудину минимум любой пока ещё доступной жидкости (если для очередной посудины все жидкости заняты, то пытаться перераспределить ранее залитые жидкости)

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

Ну а дальше уже сам.

Для начала можно найти некоторую хорошую группу изменений решения. Такую, что:

если есть некое решение X и любое изменение решения из группы Y не улучшает решение X, то решение X наилучшее. Хз есть ли такое Y, ну которое не очень жручее.

При этом одинаковые решения (с точки зрения суммы V_{ij}) тоже требуется вывести.

С другой стороры, можно решить эту задачу через альфа-бетта отсечение, критерием качества решения будет сумма всех элементов матрицы. Тогда придётся всего лишь свести непрерывность к дискретности (ну понятно, что для любого непрерывного диапозона решений есть наилучшее, тогда всё станет дискретным)