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 року:

Easy 1550. Three Consecutive Odds,
Medium 1551. Minimum Operations to Make Array Equal,
Medium 1552. Magnetic Force Between Two Balls,
Hard 1553. Minimum Number of Days to Eat N Oranges.

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

Відкриваємо 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 код і вже далі з ним працювати.

Теми: ChatGPT, LeetCode, tech

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

Ctrl + Enter

Andrew Sevastianov 01.02.2023 12:44

А ось колекція epic fails від CharGPT

Відповісти

Підтримати

Oleksandr Kyetov Software Engineer в Shopify Inc. 31.01.2023 17:10

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

Andrew Sevastianov 31.01.2023 13:22

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

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.

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

Oleksandr Kyetov Software Engineer в Shopify Inc. 31.01.2023 16:45

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

Andrew Sevastianov

Roman Gelembjuk Software Team Lead в Nasuni 31.01.2023 16:54

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

Oleksandr Kyetov

Oleksandr Kyetov Software Engineer в Shopify Inc. 31.01.2023 17:00

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

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

Roman Gelembjuk

Andrew Sevastianov 31.01.2023 17:25

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

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

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

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

Dmytro Strukov Software Engineer 31.01.2023 17:30

Достаточно почитать сайт, а не смотреть двухчасовое видео 😁

We trained this model using Reinforcement Learning from Human Feedback (RLHF), using the same methods as InstructGPT, but with slight differences in the data collection setup. We trained an initial model using supervised fine-tuning: human AI trainers provided conversations in which they played both sides—the user and an AI assistant. We gave the trainers access to model-written suggestions to help them compose their responses. We mixed this new dialogue dataset with the InstructGPT dataset, which we transformed into a dialogue format.

openai.com/blog/chatgpt

Уставший архитектор 31.01.2023 21:28

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

return len(nums) + 1

Ну почти

Andrew Sevastianov 01.02.2023 12:37

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

Уставший архитектор

VL Software Engineer в Google 30.01.2023 12:08

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

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

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

Paul Taykalo Software Engineer в MacPaw 30.01.2023 14:22

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

Уставший архитектор 30.01.2023 19:45

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

Paul Taykalo

Oleksandr Kyetov Software Engineer в Shopify Inc. 30.01.2023 15:45

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

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

Andrew Sevastianov 31.01.2023 13:24

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

Уставший архитектор 31.01.2023 21:34

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

Sydorenko Oleg 27.01.2023 20:57

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

Sydorenko Oleg 27.01.2023 20:55

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

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

Максим Шелигін Software Engineer в SoftServe 27.01.2023 11:36

Джун, недорого.

Oleksandr Kyetov Software Engineer в Shopify Inc. 27.01.2023 15:58

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

Максим Шелигін

Іван Цимбалюк C++ Developer в GlobalLogic 02.02.2023 10:45

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

Ktulxy 27.01.2023 00:32

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

Evgeniy Berlog Team Lead в Luxoft 27.01.2023 17:39

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

Ktulxy

Illia Khabibrakhmanov SSE 28.01.2023 16:38

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

Evgeniy Berlog

Oleksandr Nazararenko 30.01.2023 14:31

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

Illia Khabibrakhmanov

Ac 31.01.2023 04:07

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

Oleksandr Kyetov Software Engineer в Shopify Inc. 31.01.2023 16:53

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

Andrew Sevastianov 31.01.2023 17:35

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

Олег Дорожко 26.01.2023 20:54

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

Уставший архитектор 26.01.2023 17:50

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

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

Oleksandr Kyetov Software Engineer в Shopify Inc. 26.01.2023 17:59

И какой шанс того, что чатгпт не тренировали на этих задачах?

надо было же попробовать задачи которые появились после 2021

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

Уставший архитектор 26.01.2023 18:18

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

Artyom Krivokrisenko 26.01.2023 21:50

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

Dmytro Brahinets Delivery lead в Uinno 26.01.2023 15:27

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

Opacare Angelus 26.01.2023 23:50

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

Dmytro Brahinets

Volodymyr Yefremov PHP/Vue.js dev в Reiziger consulting 01.02.2023 00:01

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

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

Artem Duk Java Developer в SoftServe 26.01.2023 15:17

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

Oleksandr Kyetov Software Engineer в Shopify Inc. 27.01.2023 21:55

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

Artem Duk