Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 5
×

ChatGPT проти LeetCode: як алгоритм справляється з LeetCode-задачами різної складності

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Всім привіт, мене звати Олександр, я — Software Engineer. Нещодавно я спробував використати ChatGPT для вирішення завдань з LeetCode і хочу розповісти про цей досвід.

Для нетерплячих скажу одразу — ChatGPT не вивозить.

Чат хто? ЖеПеТе?

Для тих хто не чув: у листопаді 2022 компанія OpenAI випустила чат-бот, який може відповідати майже на будь-які запитання та навіть писати код. Ось, наприклад, я попросив ChatGPT написати простеньку Java-програму:

Якщо порівнювати з Google, то замість списку посилань на інші сторінки, де ми в цілому можемо знайти точно таку ж відповідь, ChatGPT зразу видає конкретно те, що потрібно. Це дуже зручно, особливо коли світ рухається настільки швидко, що переглядати десятки сайтів для того, щоб зробити щось дуже просте, зовсім немає часу.

Після релізу ChatGPT я багато разів чув, що він замінить програмістів, і мені стало цікаво наскільки це реально. А оскільки шлях до програміста у (F|M)AANG лежить через LeetCode, то я вирішив перевірити, як у ChatGPT з написанням алгоритмів.

Декілька слів про LeetCode

Якщо подивитися на список завдань з алгоритмів на LeetCode, то можна помітити, що кожного тижня додається 4 нових задачі, зазвичай це Easy, Medium, Medium і Hard. Так відбувається, тому що 4 нових завдання спочатку потрапляють у LeetCode Contest, який проходить кожної суботи, а вже після контесту ці завдання додаються до загального списку.

Також є задачі, які додаються поза контестом, але вони зазвичай доступні тільки тим, у кого є LeetCode Premium. Ось, наприклад, як виглядає 29-та сторінка із задачами на алгоритми:

Думаю, що було б логічно спробувати, ніби ChatGPT пише код під час LeetCode Contest і протестувати його завданнями, які були на одному з контестів у серпні 2020 року:

Легке завдання на знаходження трьох послідовно не парних чисел

Відкриваємо 1550. Three Consecutive Odds і, не вигадуючи нічого особливого, просто копіюємо опис у блокнот, додавши спочатку «Please write algorithm in Java to solve a problem below»:

Далі закидуємо цей текст у ChatGPT:

Копіюємо те, що видав ChatGPT назад у LeetCode та сабмітимо. LeetCode без питань приймає рішення, яке видав ChatGPT:

В цілому, я і очікував, що з легкою задачкою проблем не буде.

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

З 1551. Minimum Operations to Make Array Equal робимо все те саме, що робили з попередньої задачею, але потрібно бути уважнішими, бо якщо копіювати цифри, які записані як X у ступені Y, наприклад, 10 у 4 ступені,

то у блокнот це копіюється як 104:

В принципі це не біда, просто трошки коригуємо такі моменти прямо у блокноті, далі закидуємо у ChatGPT, копіюємо рішення назад у LeetCode й перевіряємо. Тут нас спіткає невдача — тепер жоден з тест кейсів не проходить:

Йдемо просити ChatGPT виправити рішення:

Але з оновленої версії також не проходить жоден з тест-кейсів:

Не будемо більше мучити ChatGPT цією задачкою і рухаємося далі.

Середнячок на знаходження магнітної сили між двома м’ячами

Відкриваємо 1552. Magnetic Force Between Two Balls і зразу ж стикаємося з маленькою проблемою. У описі завдання є зображення, а ChatGPT наразі розуміє тільки текст

Можливо, це і є причиною того, що алгоритм, який видає ChatGPT не проходить один із тест-кейсів:

Даємо ChatGPT ще один шанс і вуаля. З другої спроби він таки видає алгоритм, який приймає LeetCode:

Хард на знаходження мінімальної кількість днів для поїдання N апельсинів

Те, що ChatGPT не впорається з важкою задачею 1553. Minimum Number of Days to Eat N Oranges я був впевнений. І тут, на диво, вже з першої спроби алгоритм проходить всі тест-кейси.

Намагаємося сабмітити, але бачимо, що LeetCode не приймає алгоритм, бо він «їсть» дуже багато пам’яті:

Декілька разів просимо ChatGPT це виправити, але все марно, і важке завдання йому все ж таки не дається.

Висновки

В цілому, ChatGPT — класна штука, але навряд чи він би пройшов співбесіду у (F|M)AANG. З іншого боку його дуже зручно використовувати, якщо потрібно накидати якийсь boilerplate код і вже далі з ним працювати.

👍ПодобаєтьсяСподобалось11
До обраногоВ обраному1
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Коментар порушує правила спільноти і видалений модераторами.

Кому цікаво, записав відео, де я роблю приблизно те саме що і у статті👇
ChatGPT против LeetCode. Решаем задачки с LeetCode при помощи ChatGPT
ChatGPT vs LeetCode. Solving LeetCode problems with ChatGPT

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

Write a python function that takes an array and returns any integer not equal to length of the array.

Напиши функцію на мові програмування python, яка приймає масив та повертає довільне ціле, яке не співпадає з довжиною масива. То замість len(nums) + 1 ми отримаємо...

Here’s one way to do it using a for loop:
def find_disappeared_number(nums):
    for i in range(len(nums)):
        index = abs(nums[i]) - 1
        nums[index] = -abs(nums[index])
    
    for i in range(len(nums)):
        if nums[i] > 0:
            return i + 1
    return len(nums) + 1

This function takes advantage of the fact that the elements in the input array are positive integers within the range 1 to len(nums). By flipping the sign of the element at index abs(nums[i]) - 1, we can keep track of which numbers have appeared in the array. The final loop then returns the first positive index, which represents the missing number.

Якби у риб було хутро, то там би жили блохи, а блохи це...

ChatGPT наразі не користується пошуком в інтернеті ...

Вфн не шукає в реальному часі. Але він раніше проіндексував інтернет і зберіг собі свій гігантський масив інформації. Тому це майєе правда. Він знає те на що є відповідь в інтернеті

З ваших слів, виходить, що ChatGPT просто шукає відповіді в інтернеті, але я не думаю що він працює саме так ...

Ось гарний коментар на цю тему dou.ua/...​rums/topic/41748/#2563297

З ваших слів, виходить, що ChatGPT просто шукає відповіді в інтернеті

Ні, було написано, що він навчався на масиві даних, що є в інтернеті. Ніякого reinforcement learning, коли система сама генерую дані, на яких потім навчається, немає. Одна з властивостей нейромережі же ассоциативна пам’ять. Зазвичай, якщо подати на вхід нейромережі приклад дкякого класу, який був вітсутній у навчальній виборці, то якість передбання суттєво знижається.

Наприклад, шахова програма LeelaChess, яка використовую нейромережу, грає проти програми Stockfish на рівних. Але, якщо в початковій позиції поміняти слонів та коней місцями, то LeelaChess починає грати значно слабкіше. Чому? Тому що в процесі навчання майже не виникали позиції з цієї розстановки, тому ходи-кандидати вибираються гірше, якість гри падає.

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

То замість len(nums) + 1 ми отримаємо...
return len(nums) + 1

Ну почти

Як на мене, це випадково співпало. До того ж взагалі розв’язок може бути return -1. Нейромережа виплюнула правильне рішення, але іншої задачі: знайти відсутнє число у масиві. Задачі, яка дуже поширена в інтернеті. Просто якщо у масиві усі числа від 0 до nums присутні, то звісно, що треба повертати len(nums) + 1.

і це ще велика «поблажка» для ChatGPT

логічно спробувати, ніби ChatGPT пише код під час LeetCode Contest і протестувати його завданнями, які були на одному з контестів у серпні 2020 року:

логічно спробувати його на одному з поточних контестів, де задачки не гугляться. Він примудряється не вивозити задачки, рішення яких вже були доступні на дату індексації. Але для бойлерплейту так прикольно. З однієї сторони. З іншою я вже вангую, що в деяких проектах вирішать, що бляха, воно ж генерує все, то нащо нам застосовувати якісь патерни. ще щось, давайте захерачимо все просто так, як нам згенерує.

Десь щось приблизно таке саме я колись чув про Automatic Reference Counting

Ахаха, такое говорили как раз про garbage collector, но когда ябл презентовала ARC вместо GC, все макокодеры выдохнули с облегчением.

логічно спробувати його на одному з поточних контестів

Все буде, але не все так просто, бо не хочеться отримати заблокований аккаунт у leetcode ...

Тобто у майбутньому нас чекає багато boilerplate коду, який ніхто не буде оптимізувати, бо головна причина оптимізації це в лом його писати та правити?

Там потом на этом говнокоде другие бредогенераторы обучаться будут, искусственно-интеллектуальная-многоножка

Нарешті буде на кого написання тестів скинути.

І прийщов старець до молодого, але розумного і каже йому:
— Скажи мені, в чому істина?
І відповів йому молодий:
— Спочатку було слово і слово було штучний ітелект.

Десятки років пробуєм автоматизувати роботу програмістів, а роботи все більше і більше. Тепер доведется ще і ШІ бавити. Думав матимеш легке життя? Більшість програм написано? Ага. На тобі утікання памяті. На тобі нетворк оверхед. На тобі висячі процесори. На тобі бази даних, що не витримують 1_000_000 транзакцій. На тоді лівлок і старвейшин. Життя біль. Бійся, ШІ, бійся. Ті всі задачі, і до тебе прийдуть, а відповідь буде одна: «іт депендс».

Бойлерплейт писати саме то, що потрібно 👍

Якщо це write-only-код, то так. Принаймні до того часу, поки він не навчиться в тому самому коді баги виправляти

Вопрос времени, отсчет пошел.

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

Він же проіндексував інтернет, де напевно ця задача обговорювалася з прикладами коду

його можна попросити поміняти тип данних або добавити якусь унікальну фічу в алгоритм і такого вже в інтернеті не буде.
Але він це зробе

Він же проіндексував інтернет, де напевно ця задача обговорювалася з прикладами коду

Працює на нових задачах, інколи навіть дуже добре.
Я думаю Ви не розумієте як працює ChatGPT. Перед тим як спекулювати:
www.youtube.com/watch?v=kCc8FmEb1nY

Правильно, бо ChatGPT не просто шукає розв’язання задачі у Google, а саме вирішує її. Тому не важливо нова задачка чи стара, він все одно буде намагатися її вирішити, і результат буде таким же як описано у статті ...

Краще приклад нової задачі та реакція GPT :-)

Як на мене, то якщо чатгпт зможе згідно запита видавати вичерпне, настроюване, а також відфільтроване (якщо треба) по вказаним ознакам перелічення елементів деякого класу та зберігати контекст то це й буде сама дієва допомога для працюючих із будь якою документацією. Тобто ось якого хелпу/гуглу я хочу від інтернетів.
Наприклад, ось найпростіший запит «видай мені абетку польскої мови, перші десять букв»
І це він виконує.
Але чого він (тобто чатгпт) лізе до реалізації мілких деталей? Там сам чорт ногу зломить.
Чатгпт це классифікатор. Вішати на нього все — не буде ефективно.
У випадку даної статі: чатугпт потрібно було видавати схеми алгоритмів на словах, а не писати сам код. До того ж, важливо до коду було додавати звідки він — бо це відповідальність та авторство. Без цих, коли впаде літак начатгптовому коді, то хто буде винен?
P.S.
mc.today/...​ta-ne-perekruchuye-fakti
А ось вони вирішили пруф лінки додавати.

завданнями, які були на одному з контестів у серпні 2020 року

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

И какой шанс того, что чатгпт не тренировали на этих задачах?
надо было же попробовать задачи которые появились после 2021

В целом согласен, но если допустить, что ChatGPT тренировали в том числе и на задачках с LeetCode, то почему он с трудом решает задачки за 2020 год? 🧐 ...

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

Новые задачи выкладывают каждую неделю, попробуйте на тех, что выложат на этой.

Перш за все дякую за цікавий аналіз і факти, подруге я дещо здивований тому скільки ChatGPT зміг зробити правильно. Але нажаль, або на щастя, в тій же web розробці люди не вирішують подобних задач і задчі які треба вирішити вони здебільшого не про те як написати код, а про те як правильно сформулювати те що треба зробити виходячи з бізнес-вимог. А вже далі дійсно йде більш меньш рутина.
Так що всі заклики до того що треба кидати айтішку бо ChatGPT прийшов, то дійсно передчасно, але використовувати це як існтрумент який може пришвидшити і спростити роботу, то мабуть в найближчому майбутньому вже буде можливо. Точніше навіть не ChatGPT як такий, а буде безліч інструментів, бо OpenAI довели що наразі це вже можливо.

Якщо він буде вирішувати якісь заурядні задачі, то вай нот? Будуть програмісти швидше писати код — будуть швидше виходити продукти, буде швидше розвиватися ринок ІТ, бо швидше будуть з’являтися нові проблеми :)
Це просто змінить темп роботи, а не замінить програмістів, бо він чат лише створює класи, а не продукти.

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

Цікаво б спробувати цей ЧГ(пт) саме в такому аспекті — чи може він адекватно перекладати з «бізнес-мови» на «мову розробників»?

Ну якби задачі важкої складності і багато хто з людей не вивозить )

Так він же ж не звичайна людина, а тіпа штучний інтелект ...

Підписатись на коментарі