KenKen لغز addends:يبعث من جديد على (تصحيح) غير متكررة الخوارزمية

Question

هذا السؤال يتعلق أجزاء KenKen ساحة اللاتينية الألغاز التي أطلب منك أن تجد جميع التوليفات الممكنة من ncells الأرقام مع قيم x مثل هذا 1 <= x <= maxval و x(1) + ...+ x(ncells) = targetsum.بعد اختبار العديد من أكثر واعدة إجابات ، أنا ذاهب إلى جائزة الجواب-جائزة لينارت Regebro لأن:

1. روتين حياته مثل الألغام (+-5%) ،

2. وأشار إلى أن بلدي الأصلي روتين خطأ في مكان ما ، مما أدى لي أن أرى ما كان يحاول القيام به.شكرا لينارت.

chrispy ساهم خوارزمية التي يبدو يعادل لينارت لكن 5 ساعات في وقت لاحق ، سوو أولا إلى سلك يحصل عليه.

ملاحظة:أليكس مارتيلي هو البدائي خوارزمية العودية هو مثال على جعل كل تركيبة ممكنة و رمي كل منهم في غربال ورؤية التي تذهب من خلال الثقوب.هذا النهج يأخذ 20 مرة أطول من لينارت أو الألغام.(جاك المدخلات إلى max_val = 100, n_cells = 5, target_sum = 250 و على بلدي مربع 18 ثانية مقابل8+ دقيقة.) الأخلاقية:لا تولد كل تركيبة ممكنة جيدة.

ملاحظة أخرى:لينارت و الروتين توليد نفس الإجابات في نفس الترتيب.هم في الواقع نفس الخوارزمية ينظر إليه من زوايا مختلفة?أنا لا أعرف.

شيء ما يحدث لي.إذا قمت بفرز الإجابات ، بدءا ، مع (8,8,2,1,1) وتنتهي مع (4,4,4,4,4) (ما تحصل عليه مع max_val=8, n_cells=5, target_sum=20) ، سلسلة الأشكال نوع من "أبطأ النسب" ، أول من يجري "الساخنة" و آخر "البارد" أكبر عدد ممكن من المراحل في بين.هذا هو ذات الصلة إلى "إعلامية الكون"?ما هو سليم متري من أجل النظر في ذلك ؟ هل هناك خوارزمية التي يبدو أنها تركيبات التنازلي (أو الصاعد) أمر من الحرارة ؟ (هذا لا بقدر ما أستطيع أن أرى ، على الرغم من انها قريبة على مسافات قصيرة ، وتبحث في تطبيع الأمراض المنقولة جنسيا.dev.)

وهنا الثعبان الروتينية:

#!/usr/bin/env python
#filename: makeAddCombos.07.py -- stripped for StackOverflow

def initialize_combo( max_val, n_cells, target_sum):
    """returns combo
    Starting from left, fills combo to max_val or an intermediate value from 1 up.  
    E.g.:  Given max_val = 5, n_cells=4, target_sum = 11, creates [5,4,1,1].
    """
    combo = []
    #Put 1 in each cell.
    combo += [1] * n_cells
    need = target_sum - sum(combo)
    #Fill as many cells as possible to max_val.
    n_full_cells = need //(max_val - 1)
    top_up = max_val - 1
    for i in range( n_full_cells): combo[i] += top_up
    need = target_sum - sum(combo)
    # Then add the rest to next item.
    if need > 0:
        combo[n_full_cells] += need
    return combo
#def initialize_combo()

def scrunch_left( combo):
    """returns (new_combo,done)
    done   Boolean; if True, ignore new_combo, all done;
            if Falso, new_combo is valid.

    Starts a new combo list.  Scanning from right to left, looks for first
    element at least 2 greater than right-end element.  
    If one is found, decrements it, then scrunches all available counts on its
    right up against its right-hand side.  Returns the modified combo.
    If none found, (that is, either no step or single step of 1), process
    done.
    """
    new_combo = []
    right_end = combo[-1]
    length = len(combo)
    c_range = range(length-1, -1, -1)
    found_step_gt_1 = False
    for index in c_range:
        value = combo[index]
        if (value - right_end) > 1:
            found_step_gt_1 = True
            break
    if not found_step_gt_1:
        return ( new_combo,True)

    if index > 0:
        new_combo += combo[:index]
    ceil = combo[index] - 1
    new_combo += [ceil]
    new_combo += [1] * ((length - 1) - index)
    need = sum(combo[index:]) - sum(new_combo[index:])
    fill_height = ceil - 1
    ndivf = need // fill_height
    nmodf = need % fill_height
    if ndivf > 0:
        for j in range(index + 1, index + ndivf + 1):
            new_combo[j] += fill_height
    if nmodf > 0:
        new_combo[index + ndivf + 1] += nmodf
    return (new_combo, False)
#def scrunch_left()

def make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum):
    """
    Build combos, list of tuples of 2 or more addends.
    """
    combo = initialize_combo( max_val, n_cells, target_sum)
    combos.append( tuple( combo))
    while True:
        (combo, done) = scrunch_left( combo)
        if done:
            break
        else:
            combos.append( tuple( combo))
    return combos
#def make_combos_n_cells_ge_two()

if __name__ == '__main__':

    combos = []
    max_val     = 8
    n_cells     = 5
    target_sum  = 20
    if n_cells == 1: combos.append( (target_sum,))
    else:
        combos = make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum)
    import pprint
    pprint.pprint( combos)

Answer 1

أولا وقبل كل شيء ، أود أن استخدام أسماء المتغيرات التي تعني شيئا ، بحيث رمز يحصل مفهومة.ثم بعد فهمت المشكلة واضح انها مشكلة متكررة ، كما مرة واحدة كنت قد اخترت رقم واحد ، فإن مسألة إيجاد القيم الممكنة لبقية الساحات هي بالضبط نفس المشكلة لكن مع قيم مختلفة في.

لذلك أود أن تفعل ذلك من هذا القبيل:

from __future__ import division
from math import ceil

def make_combos(max_val,target_sum,n_cells):
    combos = []
    # The highest possible value of the next cell is whatever is 
    # largest of the max_val, or the target_sum minus the number 
    # of remaining cells (as you can't enter 0).
    highest = min(max_val, target_sum - n_cells + 1)
    # The lowest is the lowest number you can have that will add upp to 
    # target_sum if you multiply it with n_cells.
    lowest = int(ceil(target_sum/n_cells))
    for x in range(highest, lowest-1, -1):
        if n_cells == 1: # This is the last cell, no more recursion.
            combos.append((x,))
            break
        # Recurse to get the next cell:
        # Set the max to x (or we'll get duplicates like
        # (6,3,2,1) and (6,2,3,1), which is pointless.
        # Reduce the target_sum with x to keep the sum correct.
        # Reduce the number of cells with 1.
        for combo in make_combos(x, target_sum-x, n_cells-1):
            combos.append((x,)+combo)
    return combos

if __name__ == '__main__':
    import pprint
    # And by using pprint the output gets easier to read
    pprint.pprint(make_combos( 6,12,4))

أنا أيضا لاحظت أن الحل الخاص بك لا يزال يبدو عربات التي تجرها الدواب.القيم max_val=8, target_sum=20 and n_cells=5 التعليمات البرمجية الخاصة بك لا تجد الحل (8,6,4,1,1,), ، على سبيل المثال.أنا لست متأكدا إذا كان هذا يعني أنني قد غاب عن القاعدة في هذا أم لا, ولكن كما فهمت القواعد التي ينبغي أن يكون خيارا صالحا.

هنا هو نسخة باستخدام مولدات, ينقذ زوجين من الخطوط ، و الذاكرة إذا كانت القيم هي كبيرة حقا ، ولكن كما العودية, مولدات يمكن أن تكون صعبة "على".

from __future__ import division
from math import ceil

def make_combos(max_val,target_sum,n_cells):
    highest = min(max_val, target_sum - n_cells + 1)
    lowest = int(ceil(target_sum/n_cells))
    for x in xrange(highest, lowest-1, -1):
        if n_cells == 1:
            yield (x,)
            break
        for combo in make_combos(x, target_sum-x, n_cells-1):
            yield (x,)+combo

if __name__ == '__main__':
    import pprint
    pprint.pprint(list(make_combos( 6,12,4)))

Answer 2

خوارزمية الخاص بك تبدو جيدة للوهلة الأولى, و أنا لا أعتقد OO أو لغة أخرى من شأنها تحسين التعليمات البرمجية.لا أستطيع أن أقول إذا العودية من شأنه أن يساعد ولكن أنا معجب غير متكررة النهج.أراهن أنه كان من الصعب الحصول على العمل و من الصعب قراءة لكنه على الأرجح أكثر كفاءة و هو بالتأكيد ذكي جدا.أن نكون صادقين لم أكن تحليل الخوارزمية في التفاصيل ولكن يبدو بالتأكيد مثل ما أخذت فترة طويلة للحصول على العمل بشكل صحيح.أراهن أن هناك الكثير من-قبل-1 أخطاء غريبة الحالات حافة كان عليك أن تفكر من خلال ؟

في ضوء كل ذلك, كل ما حاولت فعله هو جدا تصل التعليمات البرمجية الخاصة بك بقدر ما استطيع عن طريق استبدال العديد من C-isms مع أكثر الاصطلاحية الثعبان-isms.في كثير من الأحيان ما يتطلب حلقة في ج يمكن القيام به في سطر واحد في بيثون.أيضا حاولت إعادة تسمية الأمور إلى متابعة الثعبان اصطلاحات تسمية أفضل و تنظيف التعليقات قليلا.أتمنى أن لا تسيء إلى أي من التغييرات.يمكنك أن تأخذ ما تريد وتترك الباقي.:-)

وهنا يلاحظ أخذت كما عملت:

• تغيير التعليمات البرمجية التي تهيئة tmp إلى مجموعة من 1 إلى أكثر الاصطلاحية tmp = [1] * n_cells.
• تغيرت for حلقة هذا يلخص tmp_sum إلى الاصطلاحية sum(tmp).
• ثم استبدال جميع الحلقات مع tmp = <list> + <list> بطانة واحدة.
• انتقلت raise doneException إلى init_tmp_new_ceiling و حصلت على التخلص من succeeded العلم.
• الاختيار في init_tmp_new_ceiling في الواقع يبدو لا لزوم لها.إزالته فقط raiseتبقى في make_combos_n_cells, لذلك أنا فقط غيرت تلك العادية يعود انخفض doneException تماما.
• تطبيع مزيج من 4 مساحات 8 مساحات المسافة البادئة.
• إزالة لا لزوم لها بين قوسين حول if شروط الحجز.
• tmp[p2] - tmp[p1] == 0 هو نفس الشيء tmp[p2] == tmp[p1].
• تغيرت while True: if new_ceiling_flag: break إلى while not new_ceiling_flag.
• أنت لا تحتاج إلى تهيئة المتغيرات 0 في أعلى الوظائف.
• إزالة combos قائمة تغيرت وظيفة yield لها الصفوف كما أنها يتم إنشاؤها.
• سميت tmp إلى combo.
• سميت new_ceiling_flag إلى ceiling_changed.

وهنا رمز لاطلاعكم:

def initial_combo(ceiling=5, target_sum=13, num_cells=4):
    """
    Returns a list of possible addends, probably to be modified further.
    Starts a new combo list, then, starting from left, fills items to ceiling
    or intermediate between 1 and ceiling or just 1.  E.g.:
    Given ceiling = 5, target_sum = 13, num_cells = 4: creates [5,5,2,1].
    """
    num_full_cells = (target_sum - num_cells) // (ceiling - 1)

    combo = [ceiling] * num_full_cells \
          + [1]       * (num_cells - num_full_cells)

    if num_cells > num_full_cells:
        combo[num_full_cells] += target_sum - sum(combo)

    return combo

def all_combos(ceiling, target_sum, num_cells):
    # p0   points at the rightmost item and moves left under some conditions
    # p1   starts out at rightmost items and steps left
    # p2   starts out immediately to the left of p1 and steps left as p1 does
    #      So, combo[p2] and combo[p1] always point at a pair of adjacent items.
    # d    combo[p2] - combo[p1]; immediate difference
    # cd   combo[p2] - combo[p0]; cumulative difference

    # The ceiling decreases by 1 each iteration.
    while True:
        combo = initial_combo(ceiling, target_sum, num_cells)
        yield tuple(combo)

        ceiling_changed = False

        # Generate all of the remaining combos with this ceiling.
        while not ceiling_changed:
            p2, p1, p0 = -2, -1, -1

            while combo[p2] == combo[p1] and abs(p2) <= num_cells:
                # 3,3,3,3
                if abs(p2) == num_cells:
                    return

                p2 -= 1
                p1 -= 1
                p0 -= 1

            cd = 0

            # slide_ptrs_left loop
            while abs(p2) <= num_cells:
                d   = combo[p2] - combo[p1]
                cd += d

                # 5,5,3,3 or 5,5,4,3
                if cd > 1:
                    if abs(p2) < num_cells:
                        # 5,5,3,3 --> 5,4,4,3
                        if d > 1:
                            combo[p2] -= 1
                            combo[p1] += 1
                        # d == 1; 5,5,4,3 --> 5,4,4,4
                        else:
                            combo[p2] -= 1
                            combo[p0] += 1

                        yield tuple(combo)

                    # abs(p2) == num_cells; 5,4,4,3
                    else:
                        ceiling -= 1
                        ceiling_changed = True

                    # Resume at make_combo_same_ceiling while
                    # and follow branch.
                    break

                # 4,3,3,3 or 4,4,3,3
                elif cd == 1:
                    if abs(p2) == num_cells:
                        return

                    p1 -= 1
                    p2 -= 1

if __name__ == '__main__':
    print list(all_combos(ceiling=6, target_sum=12, num_cells=4))

Answer 3

هنا هو أبسط حل العودية التي أستطيع أن أفكر في أن "تجد كل مزيج ممكن من الأرقام ن مع قيم x مثل هذا 1 <= x <= max_val و x(1) + ...+ x(n) = الهدف".أنا النامية من الصفر.وهنا نسخة دون أي تحسين في البساطة:

def apcnx(n, max_val, target, xsofar=(), sumsofar=0):
  if n==0:
    if sumsofar==target:
      yield xsofar
    return

  if xsofar:
    minx = xsofar[-1] - 1
  else:
    minx = 0

  for x in xrange(minx, max_val):
    for xposs in apcnx(n-1, max_val, target, xsofar + (x+1,), sumsofar+x+1):
      yield xposs

for xs in apcnx(4, 6, 12):
  print xs

حالة قاعدة n==0 (حيث أننا لا يمكن أن تسفر عن أي أرقام أكثر) أما العائد tuple حتى الآن إذا استوفى الشرط أو لا شيء ، ثم ينتهي (العوائد).

إذا كنت من المفترض أن العائد أطول الصفوف مما كنا قد بنيت حتى الآن ، if/else يتأكد لدينا سوى العائد غير يتناقص الصفوف ، لتجنب تكرار (هل قلت "الجمع" بدلا من "التقليب").

على for يحاول كل الاحتمالات "هذا" البند الحلقات أكثر ما-انخفاض اسفل مستوى العودية لا يزال قادرا على العائد.

الإخراج أراه هو:

(1, 1, 4, 6)
(1, 1, 5, 5)
(1, 2, 3, 6)
(1, 2, 4, 5)
(1, 3, 3, 5)
(1, 3, 4, 4)
(2, 2, 2, 6)
(2, 2, 3, 5)
(2, 2, 4, 4)
(2, 3, 3, 4)
(3, 3, 3, 3)

الذي يبدو الصحيح.

هناك ملايين التحسينات الممكنة ، ولكن ، تذكر:

الأولى تجعل من العمل ، ثم جعله سريع

أنا يتفق مع كينت بيك صحيح سمة هذا الاقتباس في "الثعبان باختصار" وأخبرني أنه حصل عليه من والده الذي عمل في الواقع لا علاقة لها بالبرمجة;-).

في هذه الحالة, يبدو لي أن القضية الأساسية هي فهم ماذا يحدث أي التحسين قد تتداخل ، لذلك أنا كل "بسيطة ومفهومة";يمكننا إذا!, تحسين الجوارب قبالة مرة واحدة OP يؤكد أنها يمكن فهم ما يجري في هذا محض ، غير محسن نسخة!

Answer 4

آسف أن أقول الكود طويل و لا سيما للقراءة.إذا يمكنك محاولة لتلخيص ذلك بطريقة ما, ربما شخص يمكن أن تساعدك على كتابة ذلك بوضوح أكثر.

أما عن المشكلة نفسها ، فكرتي الأولى هي استخدام العودية.(كل ما أعرفه أنك بالفعل تفعل ذلك.مرة أخرى آسف على عدم قدرتي على قراءة التعليمات البرمجية الخاصة بك.) التفكير في الطريقة التي يمكن أن تقلل من مشكلة إلى أصغر أسهل نسخة من نفس المشكلة مرارا وتكرارا, حتى يكون لديك تافهة الحال مع إجابة بسيطة جدا.

إلى أن يكون قليلا أكثر واقعية ، لديك هذه المعلمات الثلاث ، max_val, target_sum ، n_cells.يمكنك تعيين واحد من تلك الأرقام إلى بعض قيمة خاصة ، في أجل تعطيك بسيط للغاية المشكلة لا تتطلب التفكير في كل شيء ؟ بمجرد الانتهاء من ذلك, يمكن أن تقلل من الصعب قليلا نسخة من مشكلة إلى حل بالفعل ؟

تحرير:هنا هو قانون بلدي.أنا لا أحب الطريقة دي الازدواجية.أنا متأكد من أن هناك أكثر Pythonic الطريق.كما أنه يسمح باستخدام نفس الرقم مرتين في مزيج واحد.إلى التراجع عن هذا السلوك فقط تأخذ بها خط if n not in numlist:.لست متأكدا إذا كان هذا هو الصحيح تماما ، ولكن يبدو أن العمل هو (IMHO) أكثر قابلية للقراءة.يمكنك بسهولة إضافة التحفيظ و من المحتمل أن تؤدي إلى تسريع قليلا جدا.

def get_combos(max_val, target, n_cells):
    if target <= 0:
        return []
    if n_cells is 1:
        if target > max_val:
            return []
        else:
            return [[target]]
    else:
        combos = []
        for n in range(1, max_val+1, 1):
            for numlist in get_combos(max_val, target-n, n_cells-1):
                if n not in numlist:
                    combos.append(numlist + [n])
        return combos

def deduplicate(combos):
    for numlist in combos:
        numlist.sort()
    answer = [tuple(numlist) for numlist in combos]
    return set(answer)

def kenken(max_val, target, n_cells):
    return deduplicate(get_combos(max_val, target, n_cells))

Answer 5

أولا وقبل كل شيء, أنا تعلم بايثون نفسي حتى هذا الحل لن يكون كبيرا ولكن هذا هو مجرد محاولة في حل هذا.لقد حاولت حلها بشكل متكرر و أعتقد العودية لن يكون الحل المثالي لهذا النوع من المشكلة على الرغم من أن العودية الحل قد لا يكون هذا واحد:

def GetFactors(maxVal, noOfCells, targetSum):
    l = []
    while(maxVal != 0):
        remCells = noOfCells - 1
        if(remCells > 2):
            retList = GetFactors(maxVal, remCells, targetSum - maxVal)
            #Append the returned List to the original List
            #But first, add the maxVal to the start of every elem of returned list.
            for i in retList:
                i.insert(0, maxVal)
            l.extend(retList)

        else:
            remTotal = targetSum - maxVal
            for i in range(1, remTotal/2 + 1):
                itemToInsert = remTotal - i;
                if (i > maxVal or itemToInsert > maxVal):
                    continue
                l.append([maxVal, i, remTotal - i])
        maxVal -= 1
    return l



if __name__ == "__main__":
    l = GetFactors(5, 5, 15)
    print l

Answer 6

هنا حل بسيط في C/C++:

const int max = 6;
int sol[N_CELLS];

void enum_solutions(int target, int n, int min) {
  if (target == 0 && n == 0)
    report_solution(); /* sol[0]..sol[N_CELLS-1] is a solution */
  if (target <= 0 || n == 0) return; /* nothing further to explore */
  sol[n - 1] = min; /* remember */
  for (int i = min; i <= max; i++)
    enum_solutions(target - i, n - 1, i);
}

enum_solutions(12, 4, 1);

Answer 7

قليلا الحمل والولادة, ولكن لا يزال قد تساعد في البرمجة kenken.

لقد حصلت على نتائج جيدة باستخدام DLX algorhitm لحل قاتل سودوكو (جدا simmilar كما KenKen وقد أقفاص ، ولكن فقط مبالغ).استغرق الأمر أقل من الثانية بالنسبة لمعظم المشاكل و تم تنفيذه في لغة MATLAB.

مرجع هذا المنتدى http://www.setbb.com/phpbb/viewtopic.php?t=1274&highlight=&mforum=sudoku

قاتل سودوكو "نظرة على ويكيبيديا ، غير قادر بعد فرط الرابط" دمت الاطر

Answer 8

هنا هي ساذجة ، ولكن مقتضبة ، الحل باستخدام المولدات الكهربائية:

def descending(v):
  """Decide if a square contains values in descending order"""
  return list(reversed(v)) == sorted(v)

def latinSquares(max_val, target_sum, n_cells):
  """Return all descending n_cells-dimensional squares,
     no cell larger than max_val, sum equal to target_sum."""
  possibilities = itertools.product(range(1,max_val+1),repeat=n_cells)
  for square in possibilities:
    if descending(square) and sum(square) == target_sum:
      yield square

أنا يمكن أن يكون الأمثل هذا الكود مباشرة تعداد قائمة تنازلي شبكات, ولكن أجد itertools.المنتج أكثر وضوحا لأول تمرير الحل.وأخيرا استدعاء الدالة:

for m in latinSquares(6, 12, 4):
  print m

Answer 9

و هنا آخر العودية, مولد القائم على الحل ، ولكن هذه المرة باستخدام بعض الرياضيات البسيطة لحساب يتراوح في كل خطوة ، تحاشي التكرار:

def latinSquares(max_val, target_sum, n_cells):
  if n_cells == 1:
    assert(max_val >= target_sum >= 1)
    return ((target_sum,),)
  else:
    lower_bound = max(-(-target_sum / n_cells), 1)
    upper_bound = min(max_val, target_sum - n_cells + 1)
    assert(lower_bound <= upper_bound)
    return ((v,) + w for v in xrange(upper_bound, lower_bound - 1, -1)
                     for w in latinSquares(v, target_sum - v, n_cells - 1))

هذا الرمز سوف تفشل مع AssertionError إذا كنت توريد المعلمات التي من المستحيل أن ترضي;هذا هو أحد الآثار الجانبية من "صحة معيار" أننا لم نفعل غير ضرورية العودية.إذا كنت لا تريد أن الآثار الجانبية ، وإزالة التأكيدات.

لاحظ استخدام -(-x/y) إلى الجولة بعد الانقسام.قد يكون هناك أكثر pythonic طريقة كتابة ذلك.نلاحظ أيضا أنا باستخدام مولد التعبير بدلا من العائد.

for m in latinSquares(6,12,4):
  print m