Конкурс по програмиране "Изместване"

Здрасти,

Чета аз днес във вестник Компютри, че започва нов конкурс по програмиране. И гледам, че първа награда е 1000лв, втора 500, трета 300. Отделно щели да бъдат раздадени и поощрителни награди. Проверих и в старият форум на Балабанов и гледам вече е публикувал условието:

[линк]


Условието на задачата е много кратко и ясно. Това е много хубаво.

Веднага се срещам за едно решение с пълно обхождане и вероятно ще публикувам такова скоро, защото това няма да пречи на участниците, но може да им бъде полезно като база за сравнение..

Поздрави
Лук

П.С. Имам една забележка по името. Името на конкурса "Изместване" е неправилно избрано според мен. По-правилно ми се струва "Движение със завъртане и подпъхване отзад", но така пък е малко дълго.

Задачата изглежда интересна. Само това ме притеснява:

Тестовите примери ще бъдат така подбрани, че целевото състояние да бъде винаги достижимо от изходното. Решенията ще бъдат оцени по точкова система в като от значение е броят ходове и времето за изпълнение на програмата.

Ако не публикуват максимално разрешено време за работа, няма да участвам!

Ако не публикуват максимално разрешено време за работа, няма да участвам!

Не. Мисля, че дадено максимално време за работа само би усложнило нещата. Така е по-ясно, правиш най-бързата програма и оставяш всички далече назад.

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

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

Знаеш ли, че ти повдигаш напълно легитимен въпрос.

Решенията ще бъдат оцени по точкова система в като от значение е броят ходове и времето за изпълнение на програмата.

Тук имаме пространство с 2 измерения, брой ходове и скорост. Ясно е, че броят ходове трябва да е малък и времето трябва да е малко, но каква е формулата на точковата система?

Това може да се окаже важно за алгоритъма. Ще пиша на Балабанов в другия форум да видим какво ще измисли.

Мисля си, че при тези задачи важността е в следния ред:

1. Има ли решение?
2. Ако има решение то единствено ли е?
3. Ако не е единствено кое е оптималното решение?
4. Ако има оптимално решение то колко бързо ще бъде намерено?

1. Че има решение е гарантирано от условието.
2. Очевидно винаго когато има решение има повече от едно решение.
3. Това е въпросът!
4. По важно е как точно бързината ще бъде оценена.

Защо ли имам странното усещане че тези които реализират задачата на .net ще са с предимство.

Кое те навежда на тези размисли?

Оптимизацията от страна на М$ и улесняването на програмиста :)

Ами пиши и ти на .NET. Никой нема да ти дава бонус точки за език.

Ама аз пак не разбрах с какво .Нет решение ще има предимство?

Не самото решение а програмистите защото са улеснени с много.Навремето нямаше такива неща пишеш задачките на Ц/Ц++,Паскал и ако журито са самоубийци Жаба толкова :)

Аз пак не разбрах, в случая с какво програмистите на .Net са по-улеснени в сравнение на да кажем Java?

Е ок де жабата не трябваше да я споменавам ама доста време М$ го мислеха това .нет и затова имаше само жаба.жаба програмистите и те са улеснени

Следва точно решение на задачата на Python:

clone = lambda m: [ x[:] for x in [y[:] for y in m] ] # deepcopy



def R( m, k, d=-1):                 #rotate right

    o= clone(m)

    o[k] = [ m[k][(a+d)%len(o[k])] for a in range(len(o[k]))]

    return o

    

def L( m, k): return R(m,k,1)       #rotate left



def U( m, k, d=1):                  #rotate up

    o= clone(m)

    for a in range(len(o)):

        o[a][k]=m[(a+d)%len(o)][k]

    return o

    

def D( m, k): return U(m,k,-1)      #rotate down



def gen(m, m_goal, (F1, F2), D,queue):

    """ generate all 1 move next states from current state m using F1,F2"""

    for x in range(D):

            for F in (F1, F2):

                cmd=F.__name__ + str(x+1)

                next = F(m, x)

                if m == m_goal:     # solved!!!

                    print >> open("SHIFTING.OUT","w"), " ".join(queue[0][1])

                    return True

                queue.append( (next, queue[0][1] + [cmd] ) )



def solve(m, m_goal, M, N ):

    """solve by breadth first searching all posibilities."""

    queue=[ (m, []) ]; 

    while True:

        if gen(m, m_goal, (U,D), M, queue):

            return

        if gen(m, m_goal, (L,R), N, queue):

            return

        del queue[0]

        m = queue[0][0]



if __name__ == "__main__":        

    lines = open("SHIFTING.INP").readlines()

    M,N,C = map(int, lines[0].split())

    m=[]; m_goal=[]

    for a in lines[1:N+1]:

        m.append( map(int, a.split()) )

    for a in lines[N+1:]:

        m_goal.append( map(int, a.split()) )

    

    solve( m, m_goal, M,N)

Пояснения:

Решението е малко дълго. Цели 50 реда. И сам не знам защо съм писал толкова много.

Това е напълно валидно решение и ако намеря начин да го направя на exe може и да участвам, затова никой да не мисли, че може да прати това на конкурса вместо мен.

Този алгоритъм намира най-краткото решение ГАРАНТИРАНО. Затова ако участвам никой няма шанс да ме бие по тази точка.

За ваше щастие този алгоритъм е малко бавен и затруднява компютъра дори и за простият пример от матрица 3 на 4.

Така че не се отчайвайте.

Поздрави,
Лук

Ще се радваме да участваш, та дори и да е в категорията най-екзотично решение.

Пич, що не вземеш да си направиш едни блог и там да евангизираш на тема Питон?! Може и да си намериш редовни читатели...

Е, що бе???
питона си е един от добрите езици.
няма нищо лошо човека да си го използва.
Така като го гледам е от доста високо ниво.
аз попринцип програмирам на с. Ама то си е играчка.
е ся примерно тая задача може да се разглежда като намиране на най-къс път в граф.
На питон е 50 реда. А на с колко ли ше е?
Езика, който най-много го уважавам, е Математика.
В него има толкова много вградени структури и функции, че просто няма база за сравнение.
Чакай и да дам примерно един бърз пример:
колко код трябва за да изчислите числото пи до 10^6?
Ето колко:

N[pi,10^6]

Това е!
(само да не кажат ся хората, че съм казал че езиците от не толкова високо ниво не стават. Просто аз съм мързелив и обичам да пиша по-малко. :№ )