example - algorithm tutorial



হ্যাঙ্গম্যানের অসুবিধা স্তরগুলির জন্য "সহজ", "মাঝারি" বা "হার্ড" হিসাবে শব্দের শ্রেণিবদ্ধকরণের জন্য অ্যালগরিদম। (8)

একটি হ্যাঙ্গম্যান গেমের জন্য কোনও শব্দটির "অসুবিধা" নির্ধারণ করার জন্য একটি ভাল অ্যালগরিদম কী, যাতে কোনও নির্দিষ্ট অসুবিধা স্তরটি মেলে এমন শব্দ নির্বাচন করতে পারে?

অসুবিধা প্রয়োজনীয় অনুমানগুলির সাথে সম্পর্কিত বলে মনে হবে, অক্ষরের ব্যবহার সম্পর্কিত আপেক্ষিক ফ্রিকোয়েন্সি (যেমন অনেক অস্বাভাবিক অক্ষর সহ শব্দগুলি অনুমান করা কঠিন হতে পারে), এবং সম্ভাব্য শব্দটির দৈর্ঘ্য।

এছাড়াও কিছু বিষয়গত কারণের জন্য (প্রচেষ্টার জন্য) ক্ষতিপূরণ দেওয়া হয়েছে, যেমন শব্দটি প্লেয়ারের শব্দভাণ্ডারের সম্ভাবনা রয়েছে এবং এটি স্বীকৃত হতে পারে, তালিকাবদ্ধ ফ্রিকোয়েন্সিগুলির উপর ভিত্তি করে একটি অনুমান কৌশল থেকে সরে যাওয়ার অনুমতি দেয় পরিচিত মেলা শব্দ।

আমার জন্য এখন চেষ্টা রুবি নিচে। শ্রেণীকরণ উন্নত কিভাবে কোন পরামর্শ?

def classify_word(w)
  n = w.chars.to_a.uniq.length # Num. unique chars in w
  if n < 5 and w.length > 4
    return WordDifficulty::Easy
  end
  if n > w.length / 2
    return WordDifficulty::Hard
  else
    return WordDifficulty::Medium
  end
end

আমি একটি হ্যাংম্যান খেলা লিখছি আমি আমার বাচ্চাদের খেলতে চাই; আমি "হোমওয়ার্ক" করার চেষ্টা করার চেয়ে পুরনো, তাই প্রশ্নটি এত কম ভোট পেয়েছে কেন হতে পারে ... শব্দগুলি বড় শব্দ ডেটাবেসে থেকে এলোমেলোভাবে টানা হয়েছে, যা অনেক অস্পষ্ট শব্দ অন্তর্ভুক্ত করে এবং অসুবিধা স্তর দ্বারা ফিল্টার করা হচ্ছে শব্দ জন্য নির্ধারিত।

https://ffff65535.com


1। পরিচিতি

এখানে এই পদ্ধতিটি পদ্ধতিগত ভাবে পৌঁছানোর উপায় এখানে: যদি আপনার অ্যালগরিদম হ্যাঙ্গম্যানের সাথে ভালভাবে অভিনয় করে তবে আপনি প্রতিটি শব্দটির ভুল অনুমানের সংখ্যাটি নিতে পারেন যা আপনার শব্দটি অনুমান করার সময় আপনার প্রোগ্রামটি গ্রহণ করবে।

2. হ্যাংম্যান কৌশল ছাড়া

অন্য কিছু উত্তর ও মতামতগুলিতে অন্তর্ভূক্ত একটি ধারণা রয়েছে যে, দ্রাবকটির সর্বোত্তম কৌশল ইংরেজিতে অক্ষরের ফ্রিকোয়েন্সি বা কিছু সংস্থার শব্দের ফ্রিকোয়েন্সিতে তাদের সিদ্ধান্তগুলি বজায় রাখতে হবে। এটি একটি প্রলোভনসঙ্কুল ধারণা, কিন্তু এটা বেশ সঠিক নয়। সলভারটি সবচেয়ে ভাল কাজ করে যদি সেটটার দ্বারা নির্বাচিত শব্দগুলির বন্টন সঠিকভাবে মডেল করে এবং একটি মানব সেটার ভালভাবে তাদের বিরক্তিকরতা বা ঘন ঘন ব্যবহৃত অক্ষরগুলি এড়িয়ে চলার মাধ্যমে শব্দ নির্বাচন করে। উদাহরণস্বরূপ, যদিও ইংরাজিতে সবচেয়ে ঘন ঘন ব্যবহার করা চিঠিটি যদিও JUGFUL সর্বদা JUGFUL , SYZYGY , ZYTHUM এবং ZYTHUM শব্দগুলি থেকে চয়ন করে, তবে নিখুঁত ZYTHUM E অনুমান করে শুরু হয় না!

সেটার মডেলিংয়ের সর্বোত্তম পদ্ধতি প্রেক্ষাপটে নির্ভর করে, তবে আমি অনুমান করি যে কোন ধরনের বেইসিয়ান আবেশিক অনুমান একটি প্রসঙ্গে ভাল কাজ করবে যেখানে solver একই সেট্টারের বিরুদ্ধে অনেকগুলি গেম খেলতে পারে, বা অনুরূপ সেটারগুলির গোষ্ঠীর বিরুদ্ধে।

3. একটি হ্যাংম্যান অ্যালগরিদম

এখানে আমি খুব ভাল (কিন্তু নিখুঁত থেকে দূরে) একটি solver রূপরেখা করব। এটি একটি নির্দিষ্ট অভিধান থেকে অভিন্নভাবে শব্দ নির্বাচন হিসাবে সেটার মডেল। এটি একটি লোভী অ্যালগরিদম : প্রতিটি পর্যায়ে এটি এমন অক্ষরটি অনুমান করে যা মিসের সংখ্যা কমিয়ে দেয়, অর্থাৎ, এমন শব্দ যা অনুমান ধারণ করে না। উদাহরণস্বরূপ, যদি কোন অনুমান এতদূর সম্ভব না হয় এবং সম্ভাব্য শব্দগুলি DEED , DEAD এবং DARE তবে:

  • যদি আপনি D বা E অনুমান করেন তবে কোনও মিস নেই;
  • যদি আপনি অনুমান করেন, একটি মিস ( DEED ) আছে;
  • যদি আপনি R অনুমান করেন তবে দুটি মিস ( DEED এবং DEAD ) রয়েছে;
  • যদি আপনি অন্য কোন চিঠি অনুমান, তিনটি মিস আছে।

সুতরাং D বা E এই পরিস্থিতিতে একটি ভাল অনুমান।

( কর্নেল প্যানিককে মন্তব্য করার জন্য ধন্যবাদ যে সঠিক অনুমানগুলি হানম্যানের মধ্যে বিনামূল্যে আছে-আমি সম্পূর্ণভাবে আমার প্রথম প্রচেষ্টাতে ভুলে গেছি!)

4. বাস্তবায়ন

এখানে Python এই অ্যালগরিদম একটি বাস্তবায়ন:

from collections import defaultdict
from string import ascii_lowercase

def partition(guess, words):
    """Apply the single letter 'guess' to the sequence 'words' and return
    a dictionary mapping the pattern of occurrences of 'guess' in a
    word to the list of words with that pattern.

    >>> words = 'deed even eyes mews peep star'.split()
    >>> sorted(list(partition('e', words).items()))
    [(0, ['star']), (2, ['mews']), (5, ['even', 'eyes']), (6, ['deed', 'peep'])]

    """
    result = defaultdict(list)
    for word in words:
        key = sum(1 << i for i, letter in enumerate(word) if letter == guess)
        result[key].append(word)
    return result

def guess_cost(guess, words):
    """Return the cost of a guess, namely the number of words that don't
    contain the guess.

    >>> words = 'deed even eyes mews peep star'.split()
    >>> guess_cost('e', words)
    1
    >>> guess_cost('s', words)
    3

    """
    return sum(guess not in word for word in words)

def word_guesses(words, wrong = 0, letters = ''):
    """Given the collection 'words' that match all letters guessed so far,
    generate tuples (wrong, nguesses, word, guesses) where
    'word' is the word that was guessed;
    'guesses' is the sequence of letters guessed;
    'wrong' is the number of these guesses that were wrong;
    'nguesses' is len(guesses).

    >>> words = 'deed even eyes heel mere peep star'.split()
    >>> from pprint import pprint
    >>> pprint(sorted(word_guesses(words)))
    [(0, 1, 'mere', 'e'),
     (0, 2, 'deed', 'ed'),
     (0, 2, 'even', 'en'),
     (1, 1, 'star', 'e'),
     (1, 2, 'eyes', 'en'),
     (1, 3, 'heel', 'edh'),
     (2, 3, 'peep', 'edh')]

    """
    if len(words) == 1:
        yield wrong, len(letters), words[0], letters
        return
    best_guess = min((g for g in ascii_lowercase if g not in letters),
                     key = lambda g:guess_cost(g, words))
    best_partition = partition(best_guess, words)
    letters += best_guess
    for pattern, words in best_partition.items():
        for guess in word_guesses(words, wrong + (pattern == 0), letters):
            yield guess

5. উদাহরণ ফলাফল

এই কৌশল ব্যবহার করে সংগ্রহের প্রতিটি শব্দ অনুমান করার অসুবিধাটি মূল্যায়ন করা সম্ভব। এখানে আমি আমার সিস্টেম অভিধানে ছয় অক্ষর শব্দ বিবেচনা করি:

>>> words = [w.strip() for w in open('/usr/share/dict/words') if w.lower() == w]
>>> six_letter_words = set(w for w in words if len(w) == 6)
>>> len(six_letter_words)
15066
>>> results = sorted(word_guesses(six_letter_words))

এই অভিধানে অনুমান করার সবচেয়ে সহজ শব্দ (একসঙ্গে আনুমানিক অনুমানের জন্য প্রয়োজনীয় অনুমানের ক্রম অনুসারে) নিম্নরূপ:

>>> from pprint import pprint
>>> pprint(results[:10])
[(0, 1, 'eelery', 'e'),
 (0, 2, 'coneen', 'en'),
 (0, 2, 'earlet', 'er'),
 (0, 2, 'earner', 'er'),
 (0, 2, 'edgrew', 'er'),
 (0, 2, 'eerily', 'el'),
 (0, 2, 'egence', 'eg'),
 (0, 2, 'eleven', 'el'),
 (0, 2, 'enaena', 'en'),
 (0, 2, 'ennead', 'en')]

এবং সবচেয়ে কঠিন শব্দ এই হয়:

>>> pprint(results[-10:])
[(12, 16, 'buzzer', 'eraoiutlnsmdbcfg'),
 (12, 16, 'cuffer', 'eraoiutlnsmdbpgc'),
 (12, 16, 'jugger', 'eraoiutlnsmdbpgh'),
 (12, 16, 'pugger', 'eraoiutlnsmdbpcf'),
 (12, 16, 'suddle', 'eaioulbrdcfghmnp'),
 (12, 16, 'yucker', 'eraoiutlnsmdbpgc'),
 (12, 16, 'zipper', 'eraoinltsdgcbpjk'),
 (12, 17, 'tuzzle', 'eaioulbrdcgszmnpt'),
 (13, 16, 'wuzzer', 'eraoiutlnsmdbpgc'),
 (13, 17, 'wuzzle', 'eaioulbrdcgszmnpt')]

কারণ এইগুলি কঠিন কারণ আপনি -UZZLE অনুমান করার -UZZLE , আপনার এখনও সাত সম্ভাবনার বাকি রয়েছে:

>>> ' '.join(sorted(w for w in six_letter_words if w.endswith('uzzle')))
'buzzle guzzle muzzle nuzzle puzzle tuzzle wuzzle'

6. ওয়ার্ডলিস্ট পছন্দ

অবশ্যই আপনার বাচ্চাদের জন্য ওয়ার্ডলিস্টগুলি প্রস্তুত করার সময় আপনি আপনার কম্পিউটারের সিস্টেম অভিধানের সাথে শুরু করবেন না, আপনি যে শব্দগুলির কথা জানেন সেগুলির একটি তালিকা দিয়ে শুরু করুন। উদাহরণস্বরূপ, আপনি বিভিন্ন ইংরেজী কর্পোরেশনের সবচেয়ে ঘন ঘন ব্যবহৃত শব্দগুলির উইকিপিডিয়াগুলির তালিকাগুলিতে নজর রাখতে পারেন।

উদাহরণস্বরূপ, ২006 সালের প্রজেক্ট গুটেনবার্গের 10,000 প্রচলিত শব্দগুলিতে 1,700 ছয় অক্ষরের শব্দগুলির মধ্যে সবচেয়ে কঠিন দশটি হল:

[(6, 10, 'losing', 'eaoignvwch'),
 (6, 10, 'monkey', 'erdstaoync'),
 (6, 10, 'pulled', 'erdaioupfh'),
 (6, 10, 'slaves', 'erdsacthkl'),
 (6, 10, 'supper', 'eriaoubsfm'),
 (6, 11, 'hunter', 'eriaoubshng'),
 (6, 11, 'nought', 'eaoiustghbf'),
 (6, 11, 'wounds', 'eaoiusdnhpr'),
 (6, 11, 'wright', 'eaoithglrbf'),
 (7, 10, 'soames', 'erdsacthkl')]

(সোমেস ফোর্সাইট জন গালসওয়ারি দ্বারা ফোর্সাইট সাগা একটি চরিত্র, শব্দ তালিকাটি নিম্ন-ক্ষেত্রে রূপান্তরিত করা হয়েছে, তাই আমার পক্ষে দ্রুত নামগুলি দ্রুত অপসারণ করা সম্ভব ছিল না।)


আপনি একটি শব্দ অসুবিধা অনুমান করতে মন্টে কার্লো পদ্ধতি ব্যবহার করতে পারেন:

  • প্রতিটি সময় একটি র্যান্ডম চিঠি অনুমান করে একটি গেমকে সিমুলেট করুন, আপনার লক্ষ্য ভাষাতে অক্ষরের ফ্রিকোয়েন্সি দ্বারা ওজন করুন, এবং আপনার এলোমেলোভাবে প্লেয়ারটিকে কোনও সমাধানতে পৌঁছাতে কত অনুমান করেছে তা গণনা করুন। মনে রাখবেন যেহেতু প্রতিটি অনুমান একটি অক্ষর নির্মূল করে, এই প্রক্রিয়াটি সীমাবদ্ধ, এবং এটি 1 থেকে 26 পর্যন্ত একটি সংখ্যা প্রদান করে।
  • এই প্রক্রিয়ার পুনরাবৃত্তি করুন 2*N বার, যেখানে N আপনার শব্দে অনন্য অক্ষরের সংখ্যা,
  • 2*N রান ফলাফল গড় দ্বারা স্কোর গণনা,
  • জটিলতা স্তর নির্ধারণ করুন: দশেরও কম স্কোর একটি সহজ শব্দ নির্দেশ করে এবং 16 নম্বরের উপরে স্কোরগুলি একটি কঠিন শব্দ নির্দেশ করে; সব কিছু মাঝারি।

আমি একটি অ্যালগরিদম নির্মাণের ধারণা পছন্দ করি যা ব্যবহারকারীদের উপর নির্ভর করে শিখতে এবং পরিবর্তন করে। শুরুতে, আপনি তালিকার সাথে আসা কোনও অ্যালগরিদম প্রয়োগ করতে পারেন, যেহেতু আরো লোকেরা খেলাটি খেলেন, আপনি অনুমানের সংখ্যা (যা ক্রমাগত ট্র্যাক এবং গণনা করা হয় তার উপর নির্ভর করে) )। এটি জটিল কিন্তু জনপ্রিয় শব্দগুলির সমস্যাগুলিকে কঠিন রেটিং দেওয়া থেকে বিরত রাখে তবে মানুষের কাছে সুপরিচিত।


এটা করতে! শব্দ বিরুদ্ধে hangman খেলুন। গণনা কত লাগে (অর্থাত ভুল অনুমান) এটা বীট লাগে।

আপনি খেলার একটি কৌশল প্রয়োজন হবে। এখানে একটি মানুষের (ISH) কৌশল। অভিধান থেকে, এমন সব শব্দগুলি হ্রাস করুন যেগুলি এতদূর প্রকাশ করে না। অবশিষ্ট শব্দ মধ্যে সবচেয়ে ঘন অক্ষর অনুমান।

যদি আপনার কৌশলটি র্যান্ডমাইজড হয় তবে আপনি পরিমাপের প্রত্যাশিত সংখ্যা হিসাবে আপনার পরিমাপ সংজ্ঞায়িত করতে পারেন এবং অভিজ্ঞতার অনুমান করতে পারেন।

আমি কয়েক বছর আগে একটি হ্যাংম্যান বট থেকে, আরেকটি নির্ধারক কৌশল। অনুমানটি ভুলের ক্ষেত্রে অবশিষ্ট শব্দগুলির সংখ্যা কমিয়ে দেয় এমন অক্ষরটি অনুমান করুন (অর্থাত্ সবচেয়ে খারাপ ক্ষেত্রে অপটিমাইজ করুন)। আজ আমি খুব যান্ত্রিক হতে এই কৌশল অপছন্দ, আমি উপরে এক পছন্দ।


কিছুক্ষণ আগে আমি সুস্পষ্ট অ্যালগরিদম ব্যবহার করে একটি হ্যাংম্যান সলভার লিখেছিলাম: সকল সম্ভাব্য শব্দের প্রাথমিক অভিধান দেওয়া হয়েছে, প্রতিটি পালাতে আমরা অভিধানে থাকা বেশিরভাগ শব্দগুলিতে যে অক্ষরটি পড়ে থাকি তা চয়ন করুন, তারপরে অ-মিলযুক্ত শব্দগুলি মুছে ফেলুন প্রতিক্রিয়া) অভিধান থেকে।

অ্যালগরিদম এটির মতো সহজতর নয়, কারণ প্রায়ই অভিধানে শব্দগুলির একই সংখ্যায় কয়েকটি অক্ষর থাকে। এই ক্ষেত্রে, অক্ষরের পছন্দটি একটি শব্দটির জন্য কত অনুমানের প্রয়োজন তা উল্লেখযোগ্য পার্থক্য করতে পারে। আমরা সর্বোচ্চ মেনুটি বেছে নিয়েছি যেখানে সেই চিঠিটি বসানো সম্পর্কে (যদি প্রকৃতপক্ষে শব্দটি থাকে তবে) তথ্য সম্পর্কিত সর্বাধিক তথ্য দেয় (সর্বাধিক তথ্য এনট্রপি সহ চিঠি)। উদাহরণস্বরূপ, যদি দুটি সম্ভাব্য সম্ভাব্য শব্দ 'এনসাইক্লোপিডিয়া' এবং 'এনসাইক্লোপিডিক' হয়, তাহলে 'সি' অক্ষরটি ই, এন, ই, এল, ও, পি, ই, ডি, আই হিসাবে প্রদর্শিত হওয়ার একই সম্ভাবনা রয়েছে (অর্থাৎ এটি শব্দটিতে নিশ্চিত হওয়া), তবে আমাদের প্রথমে 'c' সম্পর্কে জিজ্ঞাসা করা উচিত কারণ এটির একটি অজানা তথ্য এনট্রপি রয়েছে।

উত্স (সি ++, জিপিএল) here

এই সমস্ত ফলাফল শব্দগুলির একটি তালিকা, প্রতিটির জন্য প্রয়োজনীয় অনুমানের সংখ্যা: difficulty.txt .txt (630KB)। এই অ্যালগরিদমটির জন্য সবচেয়ে কঠিন শব্দটি "ইচ্ছাকৃত" (14 অনুপস্থিত অনুমান সহ); আমি এবং দ্বিগুণ এল খুব দ্রুত অনুমান করা হয়, তবে তারপরে বিকল্পগুলিতে বিল, ডিল, ভরা, গিল, পাহাড়, হত্যা, কল, পিল, রিল, অব, উইল, এবং তারপরে বিকল্পের মধ্যে প্রতিটি অক্ষর অনুমান করা হয় চালু করুন। কিছুক্ষন counterintuitively, দীর্ঘ শব্দ অনেক বেশি দ্রুত অনুমান করা হয় (সেখানে থেকে তাদের চয়ন করতে পারে না শুধু আছে)।

অবশ্যই, হ্যাংম্যানের মানব খেলা, মনোবিজ্ঞান (এবং শব্দভাণ্ডারের বিস্তৃতি) এই অ্যালগরিদম অ্যাকাউন্টের চেয়ে অনেক বেশি ভূমিকা পালন করে ...


পূর্ববর্তী একই বিষয় সম্পর্কে একই আলোচনা: ইংরেজি শব্দ অসুবিধা নির্ধারণ করুন

আমি লিঙ্কটি শেষে উত্তরটি পছন্দ করি ^। একটি বাচ্চাদের hangman খেলা জন্য, শুধু Scrabble মত একটি পদ্ধতি প্রয়োগ করুন।

প্রতিটি অক্ষর একটি পয়েন্ট মান বরাদ্দ করুন, তারপর শুধু অক্ষর যোগ করুন।


শব্দটির স্বরবর্ণের অভাব, অনন্য অক্ষরের সংখ্যা এবং প্রতিটি অক্ষরের সাধারণতার উপর ভিত্তি করে স্কোর গণনা করা একটি সত্যিকারের সহজ উপায়:

letters = 'etaoinshrdlcumwfgypbvkjxqz'
vowels = set('aeiou')

def difficulty(word):
    unique = set(word)
    positions = sum(letters.index(c) for c in word)

    return len(word) * len(unique) * (7 - len(unique & vowels)) * positions

words = ['the', 'potato', 'school', 'egypt', 'floccinaucinihilipilification']

for word in words:
    print difficulty(word), word

এবং আউটপুট:

432 the
3360 potato
7200 school
7800 egypt
194271 floccinaucinihilipilification

তারপরে আপনি এই শব্দটি স্কোর করতে পারেন:

        score < 2000   # Easy
 2000 < score < 10000  # Medium
10000 < score          # Hard

শব্দের একটি তালিকা দিয়ে শুরু করুন এবং প্রতিটি একের জন্য গুগল অনুসন্ধান চালু করুন। হিট সংখ্যাটি শব্দটির অসুবিধাগুলির একটি (মোটা) প্রক্সি হিসাবে পরিবেশন করা যাক।

একটি পরিমার্জিত সংস্করণে আপনি থিসোরাসের উপর ভিত্তি করে সম্পর্কযুক্ত একটি শব্দের ভিত্তিতে গ্রুপ শব্দগুলি চাইবেন এবং Google অনুসন্ধানগুলির ফলাফল গণনা করে একটি বিভাগের সবচেয়ে কঠিন শব্দ নির্ধারণ করবেন।

এন-গ্র্যামের ধারণাকে গ্রহণ করা এক ধাপ এগিয়ে, শব্দটির অসুবিধা গদ্যের তার শব্দের ফ্রিকোয়েন্সি দ্বারা রেট করা যেতে পারে। অবশ্যই, শব্দের পরিসংখ্যান মানের উপর নির্ভর করে। সম্ভবত আপনি লেক্সেম এবং ফাংশন শব্দের (ডিস্ট্রিননার্স, সংযোজন ইত্যাদি) এর মধ্যে পার্থক্য করতে হবে এবং ওয়ার্ডের শব্দের সংখ্যার দ্বারা সাধারণকরণ করতে হবে (যেমন আমি লিখি ওভারকিলের মত মনে হয় ...)।