Vladimir "Dair" Lebedev-Schmidthof (dair_spb) wrote,
Vladimir "Dair" Lebedev-Schmidthof
dair_spb

Дневник по уши деревянного программиста

или Задачка в качестве тестовой. Ради садизма дать собеседуемому листочек, ручку и час времени.


C++.

Есть std::string, в котором (внезапно) набор вполне печатных символов в кодировке UTF-8. Положим, что "Войну и Мир" туда никто не передаёт и строка не больше, скажем, килобайта. Но это в том смысле, что кэшировать на диск ничего не надо.

Есть сторонняя функция size_t stringWidth(const std::string& s), которая умеет возвращать ширину переданной строки в неких попугаях. Попугаи отличны от байт и кол-ва символов в строке. Но функция довольно честная и на две одинаковых строки заведомо даст два одинаковых результата. На пустую строку выдаст гарантированно 0. (От voyevodsky) Также выполняется условие, что stringWidth подстроки не больше stringWidth строки.

Специальным образом обрабатывается символ '|' — по условию задачи считается, что это место возможного переноса слов. Этот символ сам в результат не попадает никогда.

Задача: написать функцию std::string formatString(const std::string& source, size_t width), которая бы "вписывала" строку source в ширину width, расставляя по необходимости переносы.
Т.е., для каждой строки в результирующем тексте выполняется правило stringWidth(line) <= width.

Если встретился перенос строки ('\n') — начинаем новую строчку
Строчку можно разрывать по вполне логичным правилам: по пробелам и по символам '|', при этом вместо символа '|' надо вставить символ переноса (для простоты — дефис, '-').
Если же длинное слово не влезает в рамки ну никак, то можно рвать его по максимальному кол-ву влезающих символов без всяких символов переноса.

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

Пример:
stringWidth() возвращает тупо кол-во букв (не байт):

Исходная строка:
Россий|ская власть уме|ет поль|зо|вать|ся не толь|ко кну|том.
Ес|ли что, мы и пря|ни|ком мо|жем уе|бать.


Результат вызова formatString(str, 10):
Российская
власть
умеет
пользо-
ваться не
только
кнутом.
Если что,
мы и пря-
ником мо-
жем уе-
бать.



Целый день мучаюсь, не могу придумать, как по-человечески сделать.
Tags: software development
Subscribe

  • Шалом

    Планирую посетить Святую Землю с визитом в конце октября–начале ноября. Всем, простите, кагалом, т.е., с женой и двумями детями. Жить планирую на…

  • Отпуск 2.0: Земля Обетованная (планирование)

    Израильтяне или сочувствующие есть? Как из аэропорта Бен-Гурион добраться до города Эйлат? Самолёт дорого, автобус долго (6 часов). Упоминаются…

  • Загород на велике

    Хочу построить маршрут для велосипедной загородной прогулки. Длиной километров в 50, типа на весь день. От станции электрички до станции электрички.…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 27 comments

  • Шалом

    Планирую посетить Святую Землю с визитом в конце октября–начале ноября. Всем, простите, кагалом, т.е., с женой и двумями детями. Жить планирую на…

  • Отпуск 2.0: Земля Обетованная (планирование)

    Израильтяне или сочувствующие есть? Как из аэропорта Бен-Гурион добраться до города Эйлат? Самолёт дорого, автобус долго (6 часов). Упоминаются…

  • Загород на велике

    Хочу построить маршрут для велосипедной загородной прогулки. Длиной километров в 50, типа на весь день. От станции электрички до станции электрички.…