Как я Sberfight 2022 проходил на Swift

В 2021 году на просторах интернета случайно увидел Sber на geecko.com, тогда компания Sber проводила fight типа «староверы» против «новокодеров». (Простите за неточности, вспоминаю по памяти.)

И когда запустили конкурс Sberfight я уже автоматически попал в рассылку.

Я относительно молод в Swift и тренировка умений или же проверка навыков на скорость очень привлекла. А формат в стиле «Денди» поднимает давно забытое чувство детства. (Моей любимой игрой были «танчики», «контра» и «червяк Джим»- правда у друзей на «Сеге».)

Однако, первый неприятный сюрприз ждал в условиях конкурса — подсчет баллов. Оказывается подсчет баллов теперь осуществляется — 100 баллов за задание(при учете, что все тест кейсы положительные) и + за скорость(по формуле где Swift имеет коэффициент примерно 1.29, как и JS, а вот максимальный С# — 2). Всего 8 заданий — значит минимум 800 баллов без надбавок. А вот сколько за скорость? Ответ был найден быстро — только взглянув на турнирную таблицу (Топ-1 — примерно — 3400 баллов). То есть 2400 надбавка за скорость (предположим C# — значит в общем за Swift при таком же идеальном выполнении я получу — 2477 баллов). Тут-то интерес начал угасать.

А, эскиз победителей уже нарисовался.

Пройдя два задания и поняв, что быстрее отведенного времени я не успеваю, а значит надбавки за скорость нет. Я взглянул на обновленный топ и увидев (Топ-1 — 5500 баллов) моей грусти не было предела.

Так и закрыл я Sberfight до конца февраля, пока мне на почту не упало письмо от рекрутера Sber. (Что это была массовая рассылка — это понятно, но зачем за два задания из 8 для меня осталось вопросом.) Но такая напоминалка заинтриговала меня глянуть на лидеров и каким же было мое удивление, когда Топ 1 — стоял 3400 баллов. Понятно, кто-то нашел баг, накрутил себе баллов, а теперь все пофиксили. Вот тут интерес и разогрелся, увы оставалось два дня.

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

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

Тест #1

Задание:

Вывести номера тех чисел, которые будут самыми большими при увеличении их на K

func getResult(cash: [Int], k: Int) -> [Int] {     var tempArrOfThiefes: [Int] = []          for index in 0..<cash.count {         print("cash - ", cash[index])                  var tempArr: [Int] = []         for ygrek in 0..<cash.count {             if (cash[index]+k) > cash[ygrek] {                 tempArr.append(index)             }         }         print("temp arr count - ", tempArr.count)         if (tempArr.count + 1) >= cash.count {             print("index appended - ", index)             tempArrOfThiefes.append(index + 1 )             tempArr = []         }     }     return tempArrOfThiefes }  // Test #1 let x = [1,3,4,2] let k = 2 let res = getResult(cash: x, k: k) print(res)

Тест #2 (тут задание я так и не вспомнил)

 func getResult(nums: [Int], k: Int) -> Int {     if k == 0 {         return 0     }     var tempInt: Int = 0     var tempArr = nums     var tempK = k          repeat {          for index in 0..<tempArr.count{             if tempArr[index] <= tempK {                 tempArr[index] = 0                 tempArr.sort()                 tempK += 1                 tempInt += 1             }         }      } while (tempK < tempArr.min()!)               return tempInt }  // Test #1 let x = [1,2,3,4,5] let k = 1 let res = getResult(nums: x, k: k) print(res) 

Тест #3 (для данного теста на просторах Интернета нашел решение на Python, на которое пытался опираться)

Задание:

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

Ввод:

invited_list — количество приглашённых гостей, 0<invited_list<10

dislike_list — строчный массив неприятелей, [«1-2,3»] — означает, что гость под номером 1 не сядет с гостями 2 и 3

Вывод:

Boolean — возможно ли рассадить гостей так, чтобы они все были довольны

Пример:

invited_list = 4

dislike_list = [«1-2», «3-4»]

get_result(invited_list, dislike_list) = True // [1, 4, 2, 3]

Python (эргономичностью решения я восхитился, источник решения: https://www.cyberforum.ru/python-tasks/thread2943547.html)

def guests_seating( n, dis ):     lis = list( range(1, n + 1) )     bad_pairs = set()     for e in dis:         L, de, R = e.partition('-')         not_frends = set( int(x) for x in R.split(',') )         for nf in not_frends:             bad_pairs.add( frozenset( [int(L), nf] ) )     res = [ [x] for x in lis ]     flag = True     while flag:         flag = False         for x in res:             for y in lis:                 if frozenset([x[-1],y]) not in bad_pairs and y not in x:                     x.append(y)                     flag = True                     if len(x) == n:                         #return x                         return True     return False #============================================================================== n = 10 dis = '1-2,4,6,8 3-5,7,9 4-1,2,3 5-2,4 6-3'.split() print( guests_seating( n, dis ) )

func getResult(invitedList: Int, dislikeList: [String]) -> Bool {     if invitedList == 0 {         return true     } else if invitedList == 1 {         return true     }     let allGuest = [Int](1...invitedList)     print("allGuest created - ", allGuest)     var badPairs:[Int:[Int]] = [:]     for indexB in 0..<invitedList {         var tempBadPairs:[Int: [Int]] = [:]         for indexK in 0..<dislikeList.count {             let guestArr = dislikeList[indexK].components(separatedBy: "-")             let keyElement = Int(guestArr.first!)!             let dislikeElements = guestArr.last!.components(separatedBy: ",")             let valueElement = dislikeElements.map{Int($0)!}             tempBadPairs[keyElement] = valueElement         }         if tempBadPairs.keys.contains(indexB+1) {             let newValue = tempBadPairs[indexB+1]             badPairs[indexB+1] = newValue         } else {             badPairs[indexB+1] = [0]         }     }     print("Done well - ", badPairs)          var sortedGuests: [Int] = []     sortedGuests.append(1)     var flag = 0     while flag<invitedList {         flag += 1                  for indexQ in 2...badPairs.count {             print("x is - ", indexQ)             if !badPairs[sortedGuests.last!]!.contains(indexQ) {                 if !sortedGuests.contains(indexQ) {                     sortedGuests.append(indexQ)                     print("sortedGuests.append(x.key) - ", indexQ)                 }             }         }                  if sortedGuests.count == invitedList {             print("sorted guests - ", sortedGuests)             return true         }         print("sorted guests - ", sortedGuests)     }          return false }  // Test #1 let invited_list1 = 4 let dislike_list1 = ["1-2,3", "3-4"] let intT1 = getResult(invitedList: invited_list1, dislikeList: dislike_list1) print(intT1) // Test #2 let invited_list2 = 5 let dislike_list2 = ["1-2,3", "3-4,5", "2-3"] let intT2 = getResult(invitedList: invited_list2, dislikeList: dislike_list2) print(intT2)

Тест #4 (тут все тест кейсы сильно сопротивлялись 🙂 )

Задание:

Существует массив из N количества 3 видов букв — [«x», «x», «y», «z»]

Если буквы заменить на целые числа, то можно ли получить общую сумму в X число

Пример:

// Test #1

let sub_array = [«x», «x», «x», «y», «y»]

let k = 12

let result = getResult(sub_array, k)

print(result)

// = True

// Можно заменить x на 2, y на 3, тогда получится

//[2, 2, 2, 3, 3]

func getResult(_ subArray: [String], _ k: Int) -> Bool {     if subArray.count == 1 {         return true     }     if subArray.count > k {         return false     }     if subArray.count == k {         return true     }              var tempSetOfTypeLetters: Set<String> = []     var dictOfCountOfLetters: [String: Int] = [:]     subArray.forEach { str in         tempSetOfTypeLetters.insert(str)         if !dictOfCountOfLetters.keys.contains(str) {             dictOfCountOfLetters[str] = 1         } else {             dictOfCountOfLetters[str]! += 1         }     }     var totalCount: Int = 0     var tempArray: [Int] = []     for indexA in dictOfCountOfLetters {         tempArray.append(indexA.value)         totalCount = totalCount + indexA.value     }     tempArray = tempArray.sorted{$0>$1}     print("Well done - tempArray is - ", tempArray)      var tempCounter: Int = 0     while tempCounter < k {         tempCounter += 1         var tempArrOfInt:[Int] = []                  for indexE in 0..<tempArray.count-1 {             tempArrOfInt.append(tempArray[indexE] * tempCounter)             print("tempArrOfInt.append - ", tempArrOfInt)             if indexE >= 0 {                 print("<<<---->>>")                 print("indexE is - ", indexE)                 for indexY in 1..<k {                     var temp:[Int] = []                     temp.append(tempArray[indexE+1] * (tempCounter + indexY))                     print("temp appended - ", temp )                     if tempArray.count == 3 {                         print("tempArray.count == 3 - ", tempArray.count)                         for indexK in (indexY+1)..<k {                             temp.append(tempArray[2] * (tempCounter + indexK))                             print("temp appended - ", temp)                             var total = tempArrOfInt.first                             print("total 2.1 - ", total)                             temp.forEach{ total = total! + $0 }                             print("total 2.2 is - ", total as Any)                             if (k - total!) == 0 {                                 return true                             }                         }                     }                      print("temp - ", temp)                     var total = tempArrOfInt.first                     print("total 1.1 - ", total)                     temp.forEach{ total = total! + $0 }                     print("total is 1.2 - ", total as Any)                     if (k - total!) == 0 {                         return true                     }                 }             }         }     }     return false  }  // Test #1 let sub_array = ["x", "x", "x", "y", "y"] let k = 12 let result = getResult(sub_array, k) print(result) // = True // Можно заменить x на 2, y на 3, тогда получится //[2, 2, 2, 3, 3]  // Test #2 let sub_array2 = ["x", "x", "y", "y"] let k2 = 20 let result2 = getResult(sub_array2, k2) print(result2)  // Test #3 let sub_array4 = ["x", "x"] let k4 = 2 let result4 = getResult(sub_array4, k4) print(result4)  // Test #4 let sub_array5 = ["x", "x", "y"] let k5 = 4 let result5 = getResult(sub_array5, k5) print(result5)  // Test #5 let sub_array6 = ["x", "x", "y", "z"] let k6 = 24 let result6 = getResult(sub_array6, k6) print(result6)  // Test #6 let sub_array7 = ["x", "x", "y", "z"] let k7 = 34 let result7 = getResult(sub_array7, k7) print(result7)

Тест #5 (Тут я упустил, что убирать можно не только первые символы, но и в середине, из-за чего быстрее положенного все тест кейсы не прошел. На том и остановился…)

Задание:

 Дана строка s. Вы можете удалить из нее не более k символов. Определите максимально возможное количество совпадений символов с stringGoal, то есть совпадением считается s[i] = stringGoal[i]. Например, строка «agddb» совпадает с «gdda» только одним символом. Если убрать первый символ, тогда будет уже 3 совпадения — «gddb» «gdda».

Ввод:

 s — строка с символами, 0<length(s)<20

 k — максимальное количество удалений, 0<k<10

 stringGoal — строка для сравнения

 Вывод:

Integer — максимальное количество совпадений s[i] = stringGoal[i]

 Пример:

 s = «agdd»

 k = 1

 stringGoal = «gdd»

 getResult(s, k, stringGoal) = 3

extension String {     var length: Int {         return count     }     subscript (i: Int) -> String {         return self[i ..< i + 1]     }     func substring(fromIndex: Int) -> String {         return self[min(fromIndex, length) ..< length]     }     func substring(toIndex: Int) -> String {         return self[0 ..< max(0, toIndex)]     }     subscript (r: Range<Int>) -> String {         let range = Range(uncheckedBounds: (lower: max(0, min(length, r.lowerBound)),                                             upper: min(length, max(0, r.upperBound))))         let start = index(startIndex, offsetBy: range.lowerBound)         let end = index(start, offsetBy: range.upperBound - range.lowerBound)         return String(self[start ..< end])     } }  func getResult(_ s: String, _ k: Int, _ stringGoal: String) -> Int {     var maxCounterOfMatched: Int = 0 //  Первая попытка //  проходит Тестов 6 из 10     var flagFromPrefixToBody: Bool = false     var whileCounter: Int = 0     while whileCounter <= k {         var tempMainString: String = ""          if flagFromPrefixToBody == false {             tempMainString = s.substring(fromIndex: whileCounter)             print("do it 1")         } else {             var tempString = s             if tempString.count > (whileCounter+1) {                 let indexToDelete = tempString.firstIndex(of: Character(tempString[whileCounter+1]))!                 tempString.remove(at: indexToDelete)                 tempMainString = tempString             }             print("do it 2")         }         print("tempMainString is - ", tempMainString)          var counterOfMatched: Int = 0         for indexA in 0..<tempMainString.count {             if tempMainString[indexA] == stringGoal[indexA] {                 counterOfMatched += 1             }         }         print("compare results")         if maxCounterOfMatched < counterOfMatched {             maxCounterOfMatched = counterOfMatched         }         if whileCounter == k && flagFromPrefixToBody == false {             flagFromPrefixToBody = true             whileCounter = 0         }         whileCounter += 1     }     print("Part #1 finished, maxCounterOfMatched - ", maxCounterOfMatched)    //  Вторая попытка     print("<<---->>")     print("Part# 2")          for indexA in 0..<s.count {         print("do it 1")         for indexB in 0...k {             print("do it 3")             var tempString = s             let startIndex = tempString.index(tempString.startIndex, offsetBy: indexA)             //print("startIndex - ", startIndex)             guard let endIndex = tempString.index(tempString.startIndex, offsetBy: (indexA + indexB)) as? String.Index else {                 break             }             //print("endIndex - ", endIndex)             if startIndex >= endIndex {                 break             }             tempString.removeSubrange(startIndex...endIndex)             print("tempString - ", tempString)             print("do it 4")             var counterOfMatched: Int = 0             for indexC in 0..<tempString.count {                 if tempString[indexC] == stringGoal[indexC] {                     counterOfMatched += 1                 }             }             if maxCounterOfMatched < counterOfMatched {                 maxCounterOfMatched = counterOfMatched             }         }     }     /*      вторая часть проходит Тестов 6 из 10      */      return maxCounterOfMatched } // 1,2,3,6,7,8 // need - 4,5,9,10 // need - 3,7,8,10 // (stringGoal.count - 1,2,3,6,7,8)  // need - 2,6,7,8  let s = "agdd" let k = 1 let stringGoal = "gdd" let result = getResult(s, k, stringGoal) //= 3 print(result)  let s2 = "ababcde" let k2 = 3 let stringGoal2 = "abcde" let result2 = getResult(s2, k2, stringGoal2) //= 5 print(result2)   let s3 = "aqwerty" let k3 = 3 let stringGoal3 = "qwerty" let result3 = getResult(s3, k3, stringGoal3) print(result3)  // Test that fails let s4 = "aqawerty" let k4 = 3 let stringGoal4 = "qwerty" let result4 = getResult(s4, k4, stringGoal4) print(result4)