Cogs

И в игру не играл, погуглил. оказалось все очень просто.

надо же, неужели каждый уровень можно пройти с 10 ходов?

Когда двигаешь целый ряд квадратиков разом, это засчитывается за один ход.

>так вот, какой смысл в этих уровнях тогда?

Сидеть месяцами дома, думать о прохождении.

>Когда двигаешь целый ряд квадратиков разом, это засчитывается за один ход.
да, я в курсе

Сидеть месяцами дома, думать о прохождении.

да уж, по-моему во всех таких играх, помимо основного прохождения, есть дрочево для хардкор задротов

> да уж, по-моему во всех таких играх, помимо основного прохождения, есть дрочево для хардкор задротов

С VVVVVV примерно та же фигня. Саму игру прошел часа за 3-4, включая 20 тринкетов, так теперь с тайм триалами дро^W бьюсь. Вот уж где хардкор так хардкор.

ох, к ней я пока не прикасался

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

ты звезды в Braid пробовал собирать? А у меня друг собрал все и таки увидел САМ эту долбанную альтернативную концовку - сказал «16 кружек кофе и три ночи»

>А у меня друг собрал все и таки увидел САМ эту долбанную альтернативную концовку

Во дает, я их даже найти не смог, не то что собрать.

я сам только одну достал и то мне рассказали как. А альтернативную концовку предпочел как и большинство посмотреть на тытрубе

Твой друг - лох. все звезды собираются за 5 часов (если не считать той укуренной за которой надо час на облаке стоять).

Поиграй в Spacechem. http://spacechemthegame.com/

Вот это головоломка!

>ты звезды в Braid пробовал собирать? А у меня друг собрал все и таки увидел САМ эту долбанную альтернативную концовку - сказал «16 кружек кофе и три ночи»
только начал играть, пока даже не курсе про звёзды, пазлы ток собираю

угу. Ти такой умный, да? Это если ЗНАТЬ где эти звезды находятся...

а это так сказать доп. фича - про нее некоторые игроки вообще не знают ;)

Нет, я не _такой_ умный. Я себе все мозги сломал пока не развернул у себя в голове все _три_ измерения. Единственное что я бодглядел на ютубе - это укуренное облако и еще более укуренную звезду из лобби.

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

>А вот пока ты придумаешь как там время извернуть...

лорчую. Я смотрел полное прохождение Braid с отвисшей челюстью. Потому что это пипец какая нереальщина X_X

с детства не любил эту головоломку. осилил решать только способом рандомных ходов :)

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

самое сложно (и долгое) - записать задачу, потом запускается прога и выдает решение.

если надо, могу выложить на какой-нибудь аналог пастебина или сюда :)

ну в данном случае это не совсем обычные пятнашки

неважные поля кодируются *, важные символами. так что можно задать, что куда надо перетащить. причем символы можно повторять, если элементы одинаковые.

а если важных элементов несколько (всмысле типов)?

короче вот.

решает небольшие задачи - на 4x4 после 27 ходов уже 4 гига не хватает :)

поэтому больлшие задачи разбиваются на несколько этапов - сначала ставится половина поля, потом остальная половина.

для примера приведено решение задачи Steam Crossing (после ракеты, где поле 4x4 и 2 шарика). первое - исходная задача (не решается сходу), далее первый этап с решением, потом второй этап.

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

можно это разбиение автоматизировать, но пока я это не сделал...

кстати, для записи задачи можно так сделать - сначала делается 2 одинаковых «поля» состоящих из звездочек (у источника отмечаем местоположение пустого поля @), потом по порядку смотрим какой элемент куда надо перенести - даем ему имя a, отмечаем на исходном поле и ставим куда надо его поставить на цели, потом b, c и т.д.

import sys,gc

# easiest is to spec task right here

a_col=4 # these should be set ot the size of a board
a_row=4
# NOTE: special characters: # - blocked cell for non rectangular fields
# * - any cell, in target matches anything
a_init = "a**d"+\
         "*A**"+\
         "cba*"+\
         "@**a"
a_tgt = ["**a*"+\
         "dbAc"+\
         "**a*"+\
         "**a*",]
# ^ initial task, does not solve in acceptable time/resources

# stage 1. move all unneeded things to the bottom 
a_init = "axxd"+\
         "xAxx"+\
         "cbax"+\
         "@xxa"
a_tgt = ["****"+\
         "****"+\
         "xxax"+\
         "xxax",]
# => RRRULULDLURDRRU

# stage 2. write down what we got from ^ and the top part of task
a_col=4
a_row=2
a_init = "a**d"+\
         "bcA@"
a_tgt = ["**a*"+\
         "dbAc",]
# => LULDRURDLULLDRRURDLULLDRU
# final solution - append to the first stage solution.

def i2cr(i):
    """ returns colon, row from index """
    global a_col, a_row
    if i < 0 or i >= a_col*a_row: raise Exception
    r,c = divmod(i,a_col)
    return c,r

def cr2i(c,r):
    global a_col, a_row
    if c >= a_col or r >= a_row or a_col < 0 or a_row < 0: raise Exception
    return r*a_col+c

def cmp_states(st):
    """ this checks if the state matches any of the targets.
    """
    global a_tgt
    r = []
    for tgt in a_tgt:
        matc = True
        for i in xrange(len(st)):
            tc = tgt[i]
            if tc == '*': continue
            elif tc != st[i]: 
                matc = False
                break
        if matc: 
            r.append(tgt)
    return r

def get_moves(st):
    """ from a state, determine available moves. 
        the actual move maker does not make these checks 
    """
    global a_col,a_row
    i = st.index('@')
    col,row = i2cr(i)
    r = []
    if row > 0 and st[cr2i(col,row-1)]!='#': r.append('U')
    if row <a_row-1 and st[cr2i(col,row+1)]!='#': r.append('D')
    if col > 0 and st[cr2i(col-1,row)]!='#': r.append('L')
    if col <a_col-1 and st[cr2i(col+1,row)]!='#': r.append('R')
    return r

def make_move(st,m):
    i = st.index('@')
    col,row = i2cr(i)
    if m == 'U':
        j = cr2i(col,row-1)
    elif m == 'D':
        j = cr2i(col,row+1)
    elif m == 'L':
        j = cr2i(col-1,row)
    elif m == 'R':
        j = cr2i(col+1,row)
    else:
        print m
        raise Exception
    # FIXME: add check for i,j,col,row within range
    x1 = st[:i]+st[j]+st[i+1:]
    return x1[:j]+st[i]+x1[j+1:] # FIXME: sort i,j and make 1 expression - should be faster


def main():
    global a_col,a_row,a_init
    ststop = {} # contains priorly processed states, string->True dict for faster search
    stprev = {} # this contains moves generated in previous iteration - value is moves history
    
    stprev[a_init] = ''
    mn = 0
    while True:
        print "move",mn,len(stprev),len(ststop)
        stcur = {} # moves being generated
        for st,mh in stprev.items():
            for m in get_moves(st):
                stn = make_move(st,m)
                u = cmp_states(stn)
                if u != []:
                    print "found",mh+m
                    print u
                    return
                if stcur.get(stn,-1) == -1 and stprev.get(stn,-1) == -1 and ststop.get(stn,-1) == -1:
                    stcur[stn] = mh+m
            ststop[stn]=True
        del stprev
        stprev = stcur
        mn +=1
        gc.collect()


if __name__ == '__main__': 
    main()

сори за поздний ответ
слушай, да ты гений, проверил скрипт на других левелах, всё работает :)
единственое есть пара вопросов
не понял, что значат в таблице символы «x»?
несколько этапов, это комментируем сначало stage 2, решаем stage 1, потом расскомментируем и решаем второй этап?
по идее, программа ищет кратчайший путь, если так, то она должна решать все задачи за 10 ходов(ведь их можно пройти за 10 ходов), ну если взять скажем первый уровень, то там требуется 13 ходов, учитывая повторения типа LLL и UU как один ход, почему так?
у питона есть библиотека pyopencl, возможно ли реализовать алгоритм с помощью неё, чтоб считать на видеокарте(для ускорения вычисления)?
а вообще, здорово сделал, спасибо, буду вникать в алгоритм :)