C# Задача: Калкулатор с повреден екран

Условието

Най-общо това е задача, в която имаме екран на калкулатор, който може да показва до 18 цифри включително. За визуализирането на всяка цифра се използва 7-сегментен дисплей, но някои от сегментите на дисплеите са изгорели и не светят.

7-сегментен дисплей

 Ако на входа се подаде това, което се вижда на екрана на калкулатора: 
- броя на 7-сегментните дисплей ( т.е. броя на цифрите ) и 
- състоянието на всеки един от сегментите на съответния дисплей (свети =„1“ или  „0“= не свети – независимо от причината изключен или изгорял), 
то задачата е да се определи, кои са възможните числа (поредици от цифри), които калкулаторът би могъл да показва в този момент.

Например, ако е дадено че има само един 7-сегментен дисплей и нито един сегмент от него не свети, то е възможно той да показва всяка една цифра (ако всички сегменти са изгорели – ние просто не я виждаме).

Целта е, като резултат да се изведе броя възможните числа показвани от калкулатора  (при зададеното състояние на сегментите), както и списък от тези числа сортирани в нарастващ ред.

Пълното условие на задачата можете да намерите тук.

Решението

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

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

Решението можете да намерите тук.

Идеята

За да предположим, коя цифра показва някой от 7-сегментните дисплеи , ние ще проверяваме кой сегмент със сигурност не трябва да свети, за да е възможна визуализацията на дадена цифра.

digits

За тази цел първоначално ще ни трябва да знаем за всяка цифра от 0 до 9,  кои сегменти не трябва да работят, за да може тя да се визуализира. Например за да се визуализира „0“ със сигурност сегмент „G“ от картинката не трябва да работи ( и дали другите сегменти от дисплея работят или не няма никакво значение).

Коментари по решението

За да си запишем входа ще използваме двумерен масив (от байтове) digits , който ще съдържа нули или единици в зависимост от това дали даден сегмент свети или не.

Ние последователно ще поставяме всички възможни цифри на съответната позиция до момента в който приключим и със всички дисплеи,  като започнем от последния дисплей (т.е. от този показващ единиците).  

Нека да сме определили, че за дисплея показващ единиците възможните цифри са

 „0“ и „8“.

Ако дисплеят е само един това ще са и нашите решения.

Ако обаче имаме още дисплей (за десетиците, за стотиците и т.н.) трябва да продължим. Следва да проверим, кои цифри могат да стоят на позицията на десетиците (предходния дисплей) – нека те да са „1“ и „2“. Тогава, за да получим решението ще трябва последователно да ги поставим  на мястото на десетиците ( пред вече получения резултат за единиците). Така за примерните цифри ще получим следните възможни решения:

1 0 ; 1 8 ;

2 0 ; 2 8 ;

Ако имаме още един дисплей (за стотиците), и за него сме получили, че е възможно той да показва „0“ и „8“ , то възможните показвани числа от калкулатора биха били :

0 1 0 ;  0 1 8  ;  0 2 0 ; 0 2 8 ;  (получени от вмъкването на „0“ преди предходния резултат)

8 1 0 ;  8 1 8  ;  8 2 0 ; 8 2 8 ; (получени от вмъкването на „8“ преди предходния резултат)

Както забелязвате, всеки път броя на възможните за показване числа се увеличава толкова пъти, колкото е броя на възможните за показване цифри от текущия дисплей.

Получените комбинации ще пазим в един List <string> result.  В този пример в началото той ще има два елемента:

result[0] = „0“ и

result[1] = „8“

Когато добавим и втория дисплей, елементите на List <string> result ще са:

result[0] = „0“;  

result[1] = „8“;  

-----------------------------

result[2] = „10“ ;        ( „1“+ result[0] )

result[3] = „18“ ;        ( „1“+ result[1] )

result[4] = „20“  ;       ( „2“+ result[0] )

result[5] = „28“ ;        ( „2“+ result[1] )

В моето решение е работено със стрингове и за получаване на новите елементи е използван StringBuilder, но ако предпочитате да работите с числа то текущата цифра трябва да се умножи по 1, 10, 100 и т.н. в зависимост от това дали е на позиция на единиците, десетиците, стотиците … и последователно да се събере с предходните резултати.

Вижда се, че това което ни трябва са само елементи от result[2]  до result[5] вкл. , така че или трябва да изтрием предходните или да използваме допълнителна  променлива (startIndex), която пази индекса, от който започва нашето решение.

В решението, което предлагам излишните елементи не се премахват, с цел да се спести процесорно време (което е най-оскъдния ресурс според условието на тази задача), за сметка на използване на малко повече памет.

Остана само да отпечатаме получения резултат, като незабравяме да започнем от индекса пазен в нарочната променлива, а броя комбинации ще бъде броя на елементите в списъка, които са решение на нашата задача, т. е. броя елементи от стартовия индекс до последния елемент вкл.

Готово. J

Какво всъщност направихме и защо успяхме да минимизираме времето за изпълнение на програмата:

• Правихме предположения за цифрите на база на неработещите сегменти на всеки дисплей - това са само девет проверки за всеки дисплей ( 8 винаги е възможна цифра); 
• Записвахме полученото в List <string> result , без да премахваме ненужните елементи от него – за да не губим време за пренареждане на списъка;
• 3апочнахме да четем числата отзад напред, за да не губим процесорно време и ресурси за сортирането им.
• Лесно определихме броя на комбинациите – като разлика от дължината на списъка и индекса на първия елемент от него, който е решение на задачата.