डायनेमिक प्रोग्रामिंग कोई काला जादू नहीं है

 (qsantos.fr)
2 पॉइंट द्वारा GN⁺ 2024-01-15 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Advent of Code 2023 Day 12 जैसे कई special cases वाले problems को भी, अगर वही sub-problems बार-बार हल होने वाला structure मिल जाए, तो dynamic programming से संभाला जा सकता है
  • मूल बात यह है कि recursion से problem को तोड़ने के बाद redundant calculations को memoization से घटाया जाए, और ज़रूरी values को dependency order में भरने वाली iterative calculation में बदला जाए
  • Fibonacci example में naive recursion f(1) को बार-बार evaluate करता है, लेकिन cache इस्तेमाल करने पर f(0) से f(n) तक सिर्फ n + 1 values evaluate करनी पड़ती हैं
  • Levenshtein distance और Advent of Code Day 12 दिखाते हैं कि string length और rule index जैसे state indices को cache key बनाकर recursive calls को array filling में कैसे बदला जाता है
  • dynamic programming सीखने से सिर्फ performance improvement ही नहीं, बल्कि algorithm की intermediate states और dependencies भी दिखती हैं, और memory optimization की गुंजाइश ढूंढना आसान हो जाता है

नाम थोड़ा उलझाने वाला है, लेकिन idea सरल है

  • “dynamic programming” नाम का आधुनिक “programming style” या “dynamic typing” जैसे अर्थों से सीधा संबंध नहीं है
  • इसका मूल मतलब है problem को छोटे, मिलते-जुलते problems में बांटना और उनके results को reuse करने वाली algorithm design approach
  • इसमें editorial note जोड़ा गया है कि ऐतिहासिक अर्थ में “programming” को आधार मानें तो यह expression समझ में आता है
  • शुरुआत आम तौर पर recursive function जैसी form से होती है, जहां problem को छोटे problems में decompose किया जाता है
  • जब वही sub-problems कई बार आते हैं, तो calculation results को store करके फिर से इस्तेमाल करने वाली caching की जरूरत स्वाभाविक रूप से पड़ती है

Fibonacci से caching और iteration में बदलना समझना

  • Fibonacci function f(n) = f(n - 1) + f(n - 2) से define होता है, और naive recursive implementation वही values बार-बार calculate करता है
  • f(1) वह value है जो final result में सचमुच add होती है, इसलिए f(n) बड़ा होने पर naive recursion की evaluation count भी तेजी से बढ़ती है
  • result को cache या memoize करने पर पहले से calculate किए गए f(4), f(3), f(2) को फिर calculate करने की जरूरत नहीं रहती
  • इस approach में f(0) से f(6) तक कुल 7 values ही evaluate होती हैं, और सामान्य रूप से यह घटकर n + 1 evaluations रह जाता है
  • एक कदम आगे बढ़कर, f(0), f(1) से शुरू करके required values को क्रम से भरें तो recursive calls खत्म हो जाती हैं
    • F[2] = F[1] + F[0]
    • F[3] = F[2] + F[1]
    • इसी तरह F[6] = 8 तक calculate किया जाता है
  • Fibonacci में पूरा array भी जरूरी नहीं; सिर्फ पिछली value और उससे पहले वाली value दो values रखना काफी है
  • यह flow mathematical definition से शुरू होकर iterative implementation तक जाने का systematic path दिखाता है

Edit distance example तक विस्तार

  • दो strings की edit distance वह minimum number of edits है जो एक string को दूसरी string में बदलने के लिए चाहिए
  • किस तरह के edits allow हैं, उसके हिसाब से problem बदल जाती है
    • सिर्फ character substitution allow हो तो Hamming distance
    • insertion और deletion भी allow हों तो Levenshtein distance
  • Levenshtein distance को दो strings A, B के आखिरी characters के आधार पर छोटे problems में बांटा जा सकता है
    • अगर आखिरी characters समान हों, तो दोनों characters को ignore करके बाकी strings की distance इस्तेमाल की जाती है
    • अगर आखिरी characters अलग हों, तो substitution, deletion, insertion में से minimum cost चुनी जाती है
    • अगर A खाली है, तो B के सभी characters insert करने होंगे, इसलिए cost b है
    • अगर B खाली है, तो A के सभी characters delete करने होंगे, इसलिए cost a है
  • इस definition को सीधे Python recursion में बदलें तो लंबी strings और अधिक differences वाली strings पर यह बहुत धीमा हो जाता है
  • Fibonacci में call tree हर step पर लगभग दो branches में बढ़ता था, जबकि यह recursion situation के अनुसार तीन branches में बढ़ सकता है
  • Python का functools.cache लगाने पर समान substring combinations के calculation results reuse किए जा सकते हैं
  • बेहतर implementation नए strings लगातार नहीं बनाती, बल्कि original strings A, B और substring lengths a, b ही pass करती है
  • आखिरी step में सीधे 2D cache array बनाया जाता है और उसे इस तरह order में भरा जाता है कि cache[a][b] = levenstein(A[:a], B[:b]) हो
  • iterative version a और b को 0 से string length तक iterate करता है, और पहले से भरी previous row और previous column की values refer करता है

Advent of Code 2023 Day 12 पर लागू करना

  • Advent of Code 2023 के 12 दिसंबर के problem में 1D nonogram solve करना होता है
  • example input .??..??...?##. 1,1,3 form में है, और ? या तो . या # हो सकता है
  • brute-force approach backtracking इस्तेमाल करती है, लेकिन question marks n हों तो 2^n candidates evaluate करने पड़ते हैं, इसलिए यह exponentially बढ़ती है
  • वही sub-problem repeat होने वाला structure दिखाई देता है
    • ..#..??...?##. (1),1,3
    • .#...??...?##. (1),1,3
    • पहले से processed prefix को हटा दें तो ये क्रमशः .??...?##. 1,3, ..??...?##. 1,3 जैसे लगभग एक जैसे problems बन जाते हैं
  • basic backtracking function conditions और rules लेकर possible arrangements की संख्या calculate करता है
    • अगर कोई rule बाकी नहीं है, तो देखता है कि remaining conditions में # है या नहीं
    • अगर कोई condition बाकी नहीं है, तो देखता है कि rules बाकी हैं या नहीं
    • current character . या ? हो, तो एक position आगे बढ़कर calculate करता है
    • current character # या ? हो, तो अगले rule size और separator condition की जांच करके next state में जाता है
  • Python में सिर्फ @cache लगाने से memoization apply किया जा सकता है
  • dynamic programming में बदलने के लिए string और rules को काटकर pass करने के बजाय, string offset i और rule offset j को state के रूप में इस्तेमाल किया जाता है
  • इसके बाद cache[i][j] सीधे बनाया जाता है, और indices को reverse order में भरने के तरीके से recursion को iterative calculation से replace किया जाता है
  • Rust implementation example लेख के अंदर Rust implementation link में दिया गया है

Cache को सीधे भरने पर क्या दिखता है

  • Advent of Code Day 12 का dynamic programming version memoization version से धीमा दिख सकता है
  • यह अंतर unoptimized Python implementation की वजह से होने की संभावना है
  • cache को सीधे construct करने पर यह ज्यादा अच्छी तरह दिखता है कि कौन-सी values सचमुच जरूरी हैं
  • Day 12 problem में dynamic programming version से पुष्टि होती है कि सिर्फ previous column की जरूरत है
  • इसलिए 2D array को previous column और current column दिखाने वाले दो 1D arrays में बदला जा सकता है

Practice problems और निष्कर्ष

  • dynamic programming मामूली चीज नहीं है, लेकिन ज्यादातर programmers के लिए पहुंच से बाहर technique भी नहीं है
  • problem को छोटे problems में बांटने का तरीका समझ लें, तो कई situations में सिर्फ memoization से भी naive implementation की तुलना में बड़ा सुधार मिल सकता है
  • और skill आने पर algorithm की एक पूरी family समझ में आती है, trade-offs बेहतर समझ आते हैं, और extra optimizations ढूंढे जा सकते हैं
  • practice के लिए ये problems सुझाए गए हैं
  • implementation के बाद benchmarking और profiling भूलनी नहीं चाहिए

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-01-15
Hacker News की राय

  • लेख में यह बात अच्छी लगी कि dynamic programming algorithm असल में recursion को cache करने का एक चतुर तरीका भर है। मेरे अनुभव में recursive solution को पहले ढूंढना dynamic programming solution खोजने का सबसे अच्छा starting point है, और एक बार वह मिल जाए तो memoization आसान होता है और बड़ी speed-up दे सकता है
    कभी-कभी यह bottom-up dynamic programming से भी तेज़ हो सकता है, क्योंकि यह सिर्फ़ वही solutions calculate करता है जिनकी सच में ज़रूरत होती है। मुख्य बात यह है कि call tree में subproblems बहुत हों तो भी ठीक है, लेकिन अलग-अलग subproblems की संख्या अपेक्षाकृत कम होनी चाहिए। जिस result की ज़रूरत सिर्फ़ एक बार है उसे cache करने का कोई मतलब नहीं, और असली मुश्किल original problem को पर्याप्त रूप से कम संख्या वाले अलग-अलग subproblems में बांटने में होती है

    • अलग-अलग subproblems की संख्या अपेक्षाकृत कम होनी चाहिए—यही मुख्य बात है। पूरा algorithm recursive है या iterative, यह secondary है, और dynamic programming आम तौर पर recursive algorithms में ज़्यादा साफ़ दिखती है
    • “dynamic programming recursion को cache करने का तरीका है” वाली व्याख्या मेरे लिए समझ का turning point बनी। कॉलेज में, शायद इसलिए कि उस समय procedural programming mainstream थी, textbook के bottom-up table भरने वाले examples जादू जैसे लगते थे
      practical तौर पर, tail-call elimination हमेशा लागू नहीं होता, इसलिए वैसा करना सही है, लेकिन काश पहले ज़्यादा intuitive तरीका—top-down recursive cache वाला viewpoint—सिखाया गया होता
    • जब पहली बार सीखा था, तो लगा कि अगर यह इतना fancy feature है तो इसे array memoization या call stack memoization कहना चाहिए था। मेरी राय में “dynamic programming” नाम किसी और बेहतर चीज़ के लिए बचाकर रखना चाहिए था
    • dynamic programming को सिर्फ़ memoized recursion मानना एक व्यापक गलतफहमी है। अगर ऐसे सीखा जाए तो 2D array भरने वाले type के dynamic programming problems समझना बहुत मुश्किल हो जाता है
      उदाहरण के लिए LeetCode की “Best Time to Buy and Sell Stock” series देखें, तो https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... जैसा problem array भरने के तरीके से कहीं ज़्यादा natural लगता है। मैंने इसे recursion से कभी solve नहीं किया, और यह भी ठीक से नहीं जानता कि इसका कोई natural recursive solution है या नहीं
      ऊपर वाला link III है, लेकिन पहली बार करने वाले के लिए पहले problem https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... से शुरू करना dynamic programming की अच्छी शुरुआत है
    • “dynamic programming बस caching/memoization है” कहना कुछ वैसा ही है जैसे कहना कि “investment बस कोई चीज़ खरीदकर बाद में बेच देना है”। technically यह कुछ हद तक सही हो सकता है, लेकिन विषय की जटिलता और कठिनाई को इतना ज़्यादा miss कर देता है कि insight देने के बजाय हास्यास्पद लग सकता है

  • “dynamic programming” नाम की उत्पत्ति इसके आविष्कारक Richard Bellman से हुई। 1950 में RAND में वे multi-stage decision-making process के लिए नाम खोज रहे थे, और कहा जाता है कि उस समय रक्षा मंत्री Wilson को “research” शब्द से लगभग रोगात्मक नफ़रत थी और “mathematics” शब्द से तो और भी बचना पड़ता था
    Bellman को RAND के भीतर ऐसा नाम चाहिए था जिससे Wilson और Air Force से यह बात छिपी रहे कि वे असल में mathematics कर रहे हैं। इसलिए, यह planning, decision-making और thinking से जुड़ा था, लेकिन “planning” कई कारणों से ठीक नहीं था, तो उन्होंने “programming” चुना; और multi-stage तथा time-varying concepts को शामिल करने के लिए classical physics में सटीक अर्थ वाले “dynamic” को जोड़ा
    उन्हें यह बात भी पसंद आई कि “dynamic” को adjective के रूप में negative sense में इस्तेमाल करना मुश्किल है, और यह ऐसा नाम था जिसका कोई congressman भी आसानी से विरोध नहीं कर सकता था, इसलिए उन्होंने अपनी गतिविधियों को समेटने वाले नाम के रूप में dynamic programming इस्तेमाल किया
    स्रोत: https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/in...

  • इस लेख का तरीका मुझे पसंद आया: पहले problem को recursively expose करना, फिर धीरे-धीरे caching जोड़ना, और अंत में cache size को जितना ज़रूरी हो उतना घटाना
    मैं अक्सर सीधे dynamic programming solution पर जाने की कोशिश में अटक जाता था, या उसे काम कराने के लिए ज़बरदस्ती बहुत मेहनत करता था। आगे से मैं खुद को step-by-step stages follow करने के लिए मजबूर करूंगा

    • मेरे अनुभव में dynamic programming को सीधे सिखाने पर वह puzzle जैसा लगता है। steps से गुजरते हुए यह समझाना कि table क्यों इस्तेमाल करते हैं, और फिर उस concept को caching से जोड़ना, समझ को कहीं बेहतर बना देता है

  • dynamic programming का एक शानदार application nucleotide/protein sequences का pairwise alignment है
    https://en.wikipedia.org/wiki/Sequence_alignment
    https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algor...
    https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...

    • मुझे लगता है कि ये algorithms bioinformatics/biology के सबसे महत्वपूर्ण algorithms में से कुछ हैं। इनका application scope बहुत व्यापक है

  • एक बहुत अच्छे algorithms प्रोफेसर थे, और वे UCLA में पढ़े हुए थे। Dynamic programming की उनकी क्लास शानदार थी: पहले वे ऐसे problem से शुरू करते थे जिसका simple solution exponential time complexity वाला होता था, फिर problem को छोटे problems में बाँटकर complexity को polynomial level तक घटाते थे, और फिर memoization लगाकर उसे linear तक गिरा देते थे
    काश याद होता कि उस समय उन्होंने कौन-से problems इस्तेमाल किए थे

    • संभावित उदाहरणों में Fibonacci sequence, coin change problem, 0/1 knapsack problem, matrix chain multiplication, longest common subsequence, longest increasing subsequence, Floyd-Warshall जैसे shortest path problems, और edit distance (Levenshtein distance) हैं
      ये सभी ऐसे representative examples हैं जहाँ naive solution inefficient होता है और dynamic programming से बहुत बड़ा improvement मिलता है
    • लेख में भी कुछ उदाहरण लिखे हैं, और ये lectures या practice में आम तौर पर दिखने वाले problems हैं। जैसे longest common subsequence, longest common substring, line warp, subset sum, partition, knapsack problem
      और उदाहरणों के लिए https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms... देख सकते हैं
    • दूसरों द्वारा बताए गए problems के अलावा, यह scheduling problem भी हो सकता था। उदाहरण के लिए time में overlap करने वाले N events, course timetable या CPU processes जैसी चीज़ों को throughput जैसे criteria के आधार पर optimize करने वाला problem
      जहाँ तक मुझे पता है, “इन दो courses को साथ में लेना होगा” जैसी special constraints जोड़ दी जाएँ तो यह ordinary dynamic programming से कहीं ज्यादा complex और handle करने में मुश्किल हो जाता है
    • क्या वे UCLA में Kang के under पढ़े थे?

  • लगता है original site traffic संभाल नहीं पा रही, इसलिए archive link छोड़ रहा हूँ
    https://web.archive.org/web/20240114111200/https://qsantos.f...

  • Dynamic programming की वजह से legal Go board positions की संख्या calculate की जा सकी, और वह value 171 अंकों की संख्या थी
    naive तरीके में n×n Go board की सभी possible positions देखने के लिए 3^(n^2) time लगता है, लेकिन dynamic programming effectively एक dimension हटा देता है और time complexity को O(n^5 * 5.4^n), space complexity को O(n * 5.4^n) तक घटा देता है
    https://tromp.github.io/go/legal.html
    https://tromp.github.io/go/gostate.pdf

  • “Dynamic Programming” नाम अटपटा लग सकता है, क्योंकि यहाँ programming का मतलब programming field नहीं है। इस case में इसका अर्थ linear programming की तरह optimization के करीब है
    Dynamic programming को discrete-time decision problems, यानी constraints के तहत \sum_t u_t(a_t) को maximize करने वाली optimal sequence {a_t} चुनने की method के रूप में देखा जा सकता है। यह value function V* को V*(t) = max_{a_t}{ u_t(a_t) + V*(t-1) } के रूप में define करके optimization problem की dimension को काफी घटा देता है

    • असल में नाम की official origin https://en.wikipedia.org/wiki/Dynamic_programming#History काफी मजेदार है। कहा जाता है कि Bellman को “dynamic” इसलिए पसंद था क्योंकि वह ऐसा adjective था जिसे negative sense में इस्तेमाल करना असंभव था, और उन्हें लगा कि यह ऐसा नाम है जिसका कोई सांसद भी विरोध नहीं कर सकेगा
    • जब दूसरे लोग “dynamic programming” शब्द इस्तेमाल करते हैं, तो कभी-कभी यह smart दिखने की show-off जैसा लगता है। असल में तो वे बस यह पहचानने का natural और intuitive approach इस्तेमाल कर रहे होते हैं कि problem को धीरे-धीरे छोटे subproblems में बाँटा जा सकता है, लेकिन कहते ऐसे हैं जैसे कोई special technique “use” की हो
    • यह दिलचस्प है कि पहले optimization problems जैसी किसी चीज़ को compute करना इस सोच में कहीं ज्यादा dominant था कि computers से क्या कराया जाएगा। आजकल ज्यादातर data storage, lookup और networking होती है, और अगर उसके अंदर computation हो भी तो आम तौर पर वह अच्छी तरह encapsulated लगता है
    • “optimization” शब्द भी इसी तरह misunderstanding पैदा करता है। एक बार “optimization” नाम की computer science class लेते हुए मैंने कुछ बिल्कुल अलग उम्मीद की थी
    • और पीछे जाएँ तो “programming” इस concept को accurately explain करता है। आज जिसे हम “programming” कहते हैं, वह असल में code writing है, और उसे functional, declarative, procedural जैसी programming की कई शाखाओं में बाँटा जा सकता है। उस umbrella के नीचे इससे कहीं ज्यादा चीजें आती हैं

  • “डायनेमिक प्रोग्रामिंग” सुनते ही अगर बस memoization समझ लिया जाए, तो क्या यह गलत होगा? शायद छूटा हुआ हिस्सा यह है कि memoization का उपयोग करने के लिए problem को समझदारी से हिस्सों में तोड़ना पड़ता है

    • Memoization एक ज्यादा सामान्य technique है। अक्सर यह बस इतना होता है कि पहले से calculate किए गए result को cache कर लिया जाए, ताकि बाद में फिर जरूरत पड़ने पर इस्तेमाल किया जा सके
      Dynamic programming systematic memoization के ज्यादा करीब है। इसमें धीरे-धीरे बड़े subproblems solve करके पूरे problem के solution तक पहुंचते हैं। “inductive algorithm” शब्द भी कुछ हद तक फिट बैठता है, क्योंकि typical dynamic programming algorithm असल में mathematical induction के proof जैसा ही होता है। अफसोस, उस term के पहले से दूसरे meanings हैं
    • मैं dynamic programming को ठीक इसी तरह पढ़ाता हूं। पहले recursively solve करते हैं, फिर memoization जोड़ते हैं। इसे top-down कहा जाता है
      इसके बाद देखते हैं कि recursion और memoization में overhead होता है, और table को bottom-up तरीके से बनाकर recursive calls हटाते हैं, तो dynamic programming बन जाती है
    • मेरे approach में memoization, dynamic programming के 3 steps में से step 2 है। Step 1 है recursive algorithm ढूंढना, step 2 memoization, step 3 इसे iterative/bottom-up बनाना, और अगर संभव हो तो 3b के रूप में space optimization करना
      Step 3 dynamic programming का सबसे characteristic हिस्सा है, लेकिन step 2 पर रुकने पर भी इसे dynamic programming कहा जा सकता है, ऐसा मुझे लगता है। बस यह जितना efficient हो सकता है, उतना नहीं होता। दूसरे शब्दों में, memoization caching है, और step 3 यह पूछना है कि क्या उस cache को पहले से भरने का कोई तरीका है
    • ऐसे dynamic programming solutions भी हैं जो memoization-based नहीं होते। उदाहरण के लिए, दो strings की longest common substring ढूंढने की समस्या में table के left और top cells की सिर्फ एक बार जरूरत पड़ती है, इसलिए memoization से ज्यादा मदद नहीं मिलती
      आम तौर पर, अगर subproblems बहुत overlap करते हैं और optimal subproblem पूरे optimal solution का हिस्सा बनना चाहिए, तो dynamic programming का मौका होता है। यह कहना कि सिर्फ memoization ही dynamic programming है, कुछ वैसा है जैसे कहना कि सिर्फ hash table ही abstract data type है
    • मेरे हिसाब से ऐसा सोचना गलत है। सबसे पहले, इसका obvious counterexample है कि memoization को dynamic programming के बाहर भी इस्तेमाल किया जा सकता है। उल्टा, ज्यादातर dynamic programming algorithms को इस तरह implement किया जा सकता है कि results को table में store किया जाए और बाद में उसी table से best answer ढूंढा जाए
      Memoization मूल रूप से algorithm को तेज बनाने की strategy है

  • इस साल Advent of Code पूरा करना मजेदार रहा। यह साफ था कि Day 1, खासकर Part 2, पिछले सालों की तुलना में कहीं ज्यादा कठिन था, और मैंने इसके बारे में https://blog.singleton.io/posts/2024-01-02-advent-of-code-20... पर भी लिखा, लेकिन सिर्फ मौजूदा 2022 stats और मौजूदा 2023 stats की तुलना करने से बात स्पष्ट नहीं होती। क्योंकि 2022 puzzles को solve करने के लिए लोगों के पास एक साल ज्यादा था
    14 जनवरी 2023 के 2022 stats https://web.archive.org/web/20230114172513/https://adventofc... निकालकर देखे, तो अंतर काफी बड़ा था। Part 2 completion stats https://blog.singleton.io/static/imgs-aoc23/completion.png plot करने पर Day 1 की शुरुआती group size मिलती-जुलती थी, लेकिन 2023, Day 15 तक 2022 से साफ तौर पर ज्यादा कठिन दिखता है
    Part 1 solve करके Part 2 solve न कर पाने वालों का ratio https://blog.singleton.io/static/imgs-aoc23/ratios.png भी 2023 में कई दिनों पर काफी ज्यादा है, और खासकर Day 5, Day 10, Day 12, और Day 22 Part 2 के कठिन होने की ओर इशारा करता है

    • शुरुआती Advent of Code मजेदार था, और बाद के हिस्से से पहले तक बड़े-बड़े techniques के बिना भी काम चल जाता था। बाद में यह ज्यादा कठिन और कम मजेदार हो गया, इसलिए मैंने छोड़ दिया और फिर हाथ नहीं लगाया
    • इस साल Advent of Code में समय की कमी के कारण ज्यादा आगे नहीं बढ़ पाया, लेकिन बाद में फिर से कोशिश कर सकता हूं
      हालांकि Day 5 Part 2 कितना कठिन था, यह देखकर हैरानी हुई। मैंने हार माने बिना solve कर लिया, लेकिन लगा कि शायद कोई obvious चीज छूट गई और मैंने बेवजह ज्यादा complex तरीके से solve कर दिया। यह जानकर राहत मिली कि वह वाकई थोड़ा challenging problem था
    • यह सिर्फ personal experience है, और शायद इसका असर भी हो कि मैंने अपनी usual language के बजाय दूसरी language में कोशिश की, लेकिन मेरे हिसाब से Day 1 Part 2 कठिन होने से ज्यादा problem description ठीक नहीं था
      उदाहरण के तौर पर two1nine, eightwothree, abcone2threexyz, xtwone3four, 4nineeightseven2, zoneight234, 7pqrstsixteen दिए गए थे, लेकिन oneight जैसा core example गायब था। ऐसे example के बिना यह ठीक-ठीक पता लगाना मुश्किल है कि values को कैसे replace करना चाहिए
    • इस चर्चा में जोड़ते हुए, मेरे पास date-wise progress देखने वाली script है। आखिरी दो columns देखने पर पता चलता है कि 2023, 2022 की तुलना में कितना बेरहम था, खासकर शुरुआती हिस्सा
      2022 में शुरुआती कुछ दिनों तक ज्यादातर लोग लगातार जुड़े रहे, कई दिनों में retention rate 80% से ऊपर था, और लगभग सभी ने दोनों parts solve किए। इसके उलट, 2023 के Day 1 में Part 1 solve करने वालों में से सिर्फ 76% ने Part 2 तक solve किया, और Day 3 व Day 5 पर कई लोगों ने छोड़ दिया
      दिलचस्प बात यह है कि आखिरी कुछ दिनों में यह इतना कम नहीं है, जिसे इस बात से समझाया जा सकता है कि 2023 का Advent of Code, 2022 की तुलना में ज्यादा हाल का है। मेरी व्याख्या यह है कि यह group ऐसे लोगों का है जो difficulty की परवाह किए बिना एक हद तक सभी challenges पार कर लेते हैं, और बाकी कई लोग जब महसूस करते हैं कि इसमें बहुत ज्यादा समय लग रहा है, तो छोड़ देते हैं