ВНИМАНИЕ: Конкурс для начинающих!!!

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Давно как-то говорили, вроде все были за, я обещал тему замутить, да как-то "замутилось" всё... В общем, не прошло и полгода, и я таки выполняю обещание ...

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

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

Аппаратная среда: Ардуино UNO или любой её клон (включая Nano и т.п.) на ATMega328 с частотой 16МГц.

Среда программирования: без ограничений.

Идея задачи появилась при просмотре вот этого лота. Как видите, там представлены несимметричные гаечные ключи. При этом, некоторые размеры присутствуют в единственном экземпляре (например, 6 или 11). Некоторые в двух, например, 13 есть в ключах 12-13 и 13-15. А некоторые, так и в трёх (например, 8 есть в 6-8, 8-9 и 8-10). Хочется купить самый дешёвый из возможных наборов ключей в котором были бы представлены ВСЁ размеры хотя бы по разу.

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

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

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

Срок представления работ на конкурс до 30 ноября включительно. 

Для примера я подготовил "скелет" такой программы. Здесь ключ задаётся структурой Spanner, а набор ключей массивом spanners. В массив введены данные из того лота с али.
//
//	Тип данных для хранения ключа
//
struct Spanner : public Printable {
	uint32_t price;// цена в копейках
	uint8_t size1;	// размер 1
	uint8_t size2;	// размер 2
	bool included; // если true, то включается в результирующий набор

	// 
	//	Изначально считаем, что все ключи включены в результат, а потом ненужные исключим.
	//	Можно наоборот - изначально всё исключить (написать "ini = true" в след. строке)
	//	Или задавать каждому индивидуально в 4-ом параметре конструктора (только нафига?)
	//
	Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const bool ini = true) 
		:  price(p), size1(s1), size2(s2), included(ini) {}
	
	size_t printTo(Print & p) const {
		size_t res = p.print(size1);
		res += p.print('-');
		res += p.print(size2);
		res += p.print(": ");
		res += printPrice(p, price);
		return res;
	}
	
	static size_t printPrice(Print & p, const uint32_t priceCop) {
		size_t res = p.print(priceCop / 100);
		res += p.print(" руб. ");
		res += p.print(priceCop % 100);
		res += p.print(" коп.");
		return res;
	}
};

//
//	Массив всех ключей
//
static Spanner spanners[] = {
    {6, 8 , 38208},
    {8, 9 , 41520},
    {8, 10, 43054},
    {9, 11, 49597},
    {10, 12, 51455},
    {12, 13, 56544},
    {12, 14, 57675},
    {13, 15, 62845},
    {14, 15, 61714},
    {14, 17, 70276},
    {16, 17, 76496},
    {16, 18, 81989},
    {17, 19, 82312},
    {18, 19, 82877},
    {19, 22, 110826},
    {22, 24, 145560},
    {24, 27, 171570}
};
static constexpr uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);

//
//	Эта функция вычисляет оптимальный набор ключей
//	и устанваливает поле included в true для ключей,
//	которые попадают в решение, и false для ключей,
//	которые не попадают в решение.
//
void doCalculations(void) {
	// здесь производятся все вычисления и устанавливаются
	//	значеия флагов included для каждого ключа.
	//	Поскольку мы здесь ничего не делаем, 
	//	все included останутся true, как были изначально
}

//
//	Функция печатает результирующий
//	набор ключей и его стоимость
//
void printResults(void) {
	Serial.println("Ключи");
	uint32_t total = 0;
	for (uint8_t i = 0; i < totalSpanners; i++) {
		if (spanners[i].included) {
			Serial.print(i + 1);
			Serial.print(". ");
			Serial.println(spanners[i]);
			total += spanners[i].price;
		}
	}
	Serial.print("Стоимость набора: ");
	Spanner::printPrice(Serial, total);
	Serial.println();
}

void setup(void) {
	Serial.begin(9600);
	const uint32_t start = millis();
	doCalculations();
	const uint32_t duration = millis() - start;
	printResults();
	Serial.print("Время расчёта: ");
	Serial.print(duration);
	Serial.println(" миллисекунд");
}

void loop(void) {}	

Можете использовать этот скелет и дописывать самостоятельно только вычисления. По сути тут осталось дописать функцию "doCalculations" вместо которой у меня стоит заглушка.

Призовой фонд: автор правильно работающей программы, показавшей наилучшее время получит приз - вот такую плату. Если при этом он еще и побьёт по времени моё решение (которое я планирую выложить после 30 ноября для разбора теми, кто не смог написать сам), то он получит дополнительный приз от меня лично.

Если конкурс окажется успешным (будут участники), возможно договоримся и сделаем его регулярным

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

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

wdrakula
wdrakula аватар
Offline
Зарегистрирован: 15.03.2016

А вот если аккаунт участника с одного IP с старым программистом, то это кто будет отслеживать? ;))

sadman41
Онлайн
Зарегистрирован: 19.10.2016

Интересно - зачем начинающему такая плата...

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

sadman41 пишет:

Интересно - зачем начинающему такая плата...

вот отвечу, ардуиной сына не заинтересовал, а вот к СТМу он благожелательно относится, ждёт, когда допилят среду, говорит, что скоро, подвижки есть, хотя и на стм ничего еще не написал, даже диодом не помаргал, я хоть генератор Димакса пытался сделать, да и диодом моргал )))

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

wdrakula пишет:

А вот если аккаунт участника с одного IP с старым программистом, то это кто будет отслеживать? ;))

Никто. У нас, например, полгорода практически на одном IP-шнике. Так что, если на это смотреть, то я, покойный Ворота и, если не обознался, то и ещё как минимум один участник - все клоняры друг друга!

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

sadman41 пишет:

Интересно - зачем начинающему такая плата...

Как раз начинающему ... это Вам она не нужна, а ему ... ну, вот придётся блинк на целых три диода написать ... или даже на четыре ... это ж ни в какую мегу не полезет!

b707
Онлайн
Зарегистрирован: 26.05.2017

ЕвгенийП пишет:

Так что, если на это смотреть, то я, покойный Ворота и, если не обознался, то и ещё как минимум один участник - все клоняры друг друга!

Ворота? :( Давно?

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

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

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

ЕвгенийП пишет:

 то я, покойный Ворота и, если не обознался, то и ещё как минимум один участник - все клоняры друг друга!

О_О Как так...  :( 

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

ua6em пишет:

понятно, что 9 ключей

Восемь, вроде.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

b707 пишет:

Ворота? :( Давно?

30.09

FoxJone
Offline
Зарегистрирован: 19.04.2019

ЕвгенийП пишет:
Участвовать может любой, кто не зарабатывает и никогда не зарабатывал программированием, т.е. программисты - любители.

Это оголтелый расизм и дискриминация! Я буду жаловаться в Спортлото!

(это я подписался на посмотреть чем закончится)

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

ЕвгенийП пишет:

ua6em пишет:

понятно, что 9 ключей

Восемь, вроде.

да не вроде, а точно 8, первое полусовершенное число

kalapanga
Offline
Зарегистрирован: 23.10.2016

ua6em пишет:

точно 8, первое полусовершенное число

Первое полусовершенное - это 6

mixail844
Offline
Зарегистрирован: 30.04.2012

ua6em пишет:

sadman41 пишет:

Интересно - зачем начинающему такая плата...

вот отвечу, ардуиной сына не заинтересовал, а вот к СТМу он благожелательно относится, ждёт, когда допилят среду, говорит, что скоро, подвижки есть, хотя и на стм ничего еще не написал, даже диодом не помаргал, я хоть генератор Димакса пытался сделать, да и диодом моргал )))

 

ээээм какую среду ? Arduino IDE ? 
писать для Nucleo в среде Ардуино , это какой то изврат
во первых есть mbed 
во вторых есть Atollic TrueStudio и CubeIDE полноценные среды разработки с отладчиками и кучей фишек Eclipse . 
если уж браться за Nucleo то сразу "по-взрослому"
Green
Offline
Зарегистрирован: 01.10.2015

ЕвгенийП пишет:

30.09


Тоска.(((

andriano
andriano аватар
Offline
Зарегистрирован: 20.06.2015

ЕвгенийП пишет:

...покойный Ворота...

Это что, пока я больше месяца по госпиталям болтался, у нас невосполнимые потери?

 

PS. Володя был человеком военным, а у военных принято помнить об ушедших товарищах. Я за то, чтобы разместить некролог в "Отвлеченных темах".

bwn
Offline
Зарегистрирован: 25.08.2014

andriano пишет:

PS. Володя был человеком военным, а у военных принято помнить об ушедших товарищах. Я за то, чтобы разместить некролог в "Отвлеченных темах".

Поддерживаю.

kolyn
Offline
Зарегистрирован: 18.01.2019

ЕвгенийП пишет:

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

Удалил вопрос, согласно Вашего условия может.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

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

Ладно, давай примем по маленькой, земля ему пухом.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kolyn пишет:

 согласно Вашего условия может.

Да, я как-то невнимателен был, когда отвечал.

b707
Онлайн
Зарегистрирован: 26.05.2017

ЕвгенийП пишет:

Ладно, давай примем по маленькой, земля ему пухом.

"... так лучше, чем от водки и от простуд..."

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Это, да.

xDriver
xDriver аватар
Offline
Зарегистрирован: 14.08.2015

во блин, О_О, ладно... не чокаясь...

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

Помяну. Светлый был человек, фулюган Всея Руси. 

Ulliss
Offline
Зарегистрирован: 16.09.2019

а можно сперва дам ответ, а потом опишу решение...

по моим прикидкам (из вводных массива) останется 8 ключей на сумму 6.367,66

b707
Онлайн
Зарегистрирован: 26.05.2017

Ulliss пишет:

а можно сперва дам ответ, а потом опишу решение...

внимательнее смотрим условия конкурса - важен не только сам ответ, но и скорость работы программы. Поэтому цифра без кода смысла не имеет.

wdrakula
wdrakula аватар
Offline
Зарегистрирован: 15.03.2016

Я напишу комментарий. Я ж математик, "Не могу молчать!".

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

;))))))

mixail844
Offline
Зарегистрирован: 30.04.2012

wdrakula пишет:

Я напишу комментарий. Я ж математик, "Не могу молчать!".

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

;))))))

 

круто ,я когда попытался решить , сразу о теории графов подумал , даже что то рисовал в тетрадке. интересная задачка
 
кмк , не только самый дешевый маршрут , но так же и гамильтонов != полный набор , 
полный набор ,в том смысле что полбый набор не исключает повторений . ну а гамильтонов это конечно в идеале 
 
ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

wdrakula пишет:

Я напишу комментарий. Я ж математик, "Не могу молчать!".

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

;))))))

во во, это точно, у меня пример из Вирта не заработал, точнее я с ним не справился

kolyn
Offline
Зарегистрирован: 18.01.2019

wdrakula пишет:

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

;))))))

Если б не этот пост, никогда не узнал бы, что "изобрел" метод поиска в ширину. 0_0

Если разберусь с читерским кодом Е.П. (так, по простому, как раз для новичков написан), может и решу :| Например в 4-й строке что за Принтабля? Ни где найти не могу(

                            4  public Printable 

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

kolyn пишет:

Если разберусь с читерским кодом Е.П. (так, по простому, как раз для новичков написан), может и решу :| Например в 4-й строке что за Принтабля? Ни где найти не могу(

                            4  public Printable 

на чистом русском языке вроде как печатаемое )))

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Ulliss пишет:

а можно сперва дам ответ, а потом опишу решение...

по моим прикидкам (из вводных массива) останется 8 ключей на сумму 6.367,66

Про восемь я уже писал выше. Смысл в программе.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kolyn пишет:
что за Принтабля?

Ни где найти не могу(

Это потому, что "ни где" не искал. Если в окне поиска нашего форума (в правом верхнем углу) набрать это слово, то первый же результат ведёт на тему, где всё разжёвано.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

kolyn пишет:
с читерским кодом Е.П. (так, по простому, как раз для новичков написан)

Уж, как умею.

Видел фильм "Ржевский против наполеона"? Там ржевскому приказывают выдавать себя за женщину и так, чтобы все поверили, а он спрашивает:"Так это что ж, мне теперь кобылу криво парковать? Я не умею!"

kolyn
Offline
Зарегистрирован: 18.01.2019

Простие, искал Гугл и Яндекс, я их просил) А вутренний поиск - не додумался.

А от "ни где" вез де  прям покраснел.

 

kolyn
Offline
Зарегистрирован: 18.01.2019

Сегодня дедлайн, если не ошибаюсь. Пытается кто-нибудь поучаствовать?

Я лично еще трепыхаюсь, но близок к "ниасилил". 

kolyn
Offline
Зарегистрирован: 18.01.2019

Евгений Петрович, не томите, публикуйте ответ.

Я неделю за компьютером провел безвылазно, на все дела забил, жена печень выгрызла, чемодан мне паковать начала;)

b707
Онлайн
Зарегистрирован: 26.05.2017

kolyn пишет:

Сегодня дедлайн, если не ошибаюсь.

ошибаетесь.

С вашей внимательностью вам трудно в программировании придется :)

kolyn
Offline
Зарегистрирован: 18.01.2019

b707 пишет:

С вашей внимательностью вам трудно в программировании придется :)

 

30.10. 2020 в 23:59:59 последний срок. В чем я ошибся?)

kolyn
Offline
Зарегистрирован: 18.01.2019

kolyn пишет:

b707 пишет:

С вашей внимательностью вам трудно в программировании придется :)

 

30.10. 2020 в 23:59:59 последний срок. В чем я ошибся?)

Ноября!!!!! Вы правы!

 

AndreyD
Offline
Зарегистрирован: 07.10.2018

Есть мысли, но как реализовать в коде не хватает знаний:

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

2. Минимальное количество ключей в наборе будет равно половине от количества размеров. Ну или +1, если нечётное.

3. Перебираем все комбинации ключей от числа половины размеров до максимального количества ключей.

а) откидываем набор, если у него нет всех размеров.

б) если есть все размеры, сравниваем сумму, если меньше то запоминаем.

 

Между 2 и 3 пунктом можно "зафиксировать" ключи, которые попадут в набор по любому, это ключи у которых размер встречается только один раз, а перебирать уже оставшиеся.

 

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Метод Британского музея? Ну, что ж, достойно. Можете оценить количество вариантов для перебора?

AndreyD
Offline
Зарегистрирован: 07.10.2018

Для вашего набора 89846 комбинаций. Это без последнего предложения про выбор явных ключей. Точнее для любого набора с 16-ю размерами.

AndreyD
Offline
Зарегистрирован: 07.10.2018

ЕвгенийП пишет:

Метод Британского музея?

Я больше про брутфорс подумал, хотя это получается примерно одно и тоже.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

Не знаю новомоднего словечка "брутфорс". Медод британского музей - это другое название метода полного перебора.

ЕвгенийП
ЕвгенийП аватар
Offline
Зарегистрирован: 25.05.2015

AndreyD пишет:

Для вашего набора 89846 комбинаций. Это без последнего предложения про выбор явных ключей. Точнее для любого набора с 16-ю размерами.

Сомневаюсь, но проверять не буду 

AndreyD
Offline
Зарегистрирован: 07.10.2018

ЕвгенийП пишет:

Не знаю новомоднего словечка "брутфорс". Медод британского музей - это другое название метода полного перебора.

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

AndreyD
Offline
Зарегистрирован: 07.10.2018

ЕвгенийП пишет:

Сомневаюсь, но проверять не буду 

Ну может кто-нибудь захочет проверить. ссыль

Количество комбинаций равно сумме всех значений, когда n=17, а k изменяется от 8 до 17.

ua6em
ua6em аватар
Offline
Зарегистрирован: 17.08.2016

у ключа есть ещё и тело, к примеру с одной стороны на 112 а с другой 7 )))