Роботы! Соберите эти соленья!

10

Я, кажется, попал в засолку. Буквально. Я бросил на пол кучу солений, и теперь они разбросаны! Мне нужно, чтобы ты помог мне собрать их всех. О, я упоминал, что у меня в команде куча роботов? (Они также разбросаны повсюду; я очень плохо организовываю вещи.)

Вы должны принять участие в виде:

P.......
..1..2..
.......P
........
P3PP...4
.......P

то есть, несколько строк либо ., P(рассол), или цифра (ID робота). (Вы можете предположить, что каждая строка имеет одинаковую длину и дополнена ..) Вы можете вводить эти строки в виде массива, либо вводить из STDIN, либо читать в отдельной строке через запятую, либо читать файл, либо делать все, что захотите. хотел бы принять участие.

Ваш вывод должен быть в виде nлиний, где nнаходится самый высокий идентификатор робота. (Идентификаторы робота всегда будут последовательными, начиная с 1.) Каждая строка будет содержать путь робота, образованный из букв L(слева), R(справа), U(вверх) и D(вниз). Например, вот пример выходных данных для этой загадки:

LLU
RDR
LRRR
D

Это также может быть

LLU RDR LRRR D

Или

["LLU","RDR","LRRR","D"]

Или любой формат, который вы хотите, если вы можете сказать, каким должно быть решение.

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

Подсчет очков:

  • Ваша программа будет запущена с каждым из 5 (случайно сгенерированных) тестовых случаев.
  • Вы должны добавить шаги каждого запуска, и это будет ваш счет.
  • Наименьший общий, совокупный счет выиграет.
  • Вы не можете жестко кодировать для этих конкретных входов. Ваш код также должен работать для любого другого ввода.
  • Роботы могут проходить друг через друга.
  • Ваша программа должна быть детерминированной, т.е. один и тот же вывод для каждого запуска. Вы можете использовать генератор случайных чисел, если он засеян и постоянно генерирует одинаковые числа кроссплатформенных.
  • Ваш код должен быть запущен в течение 3 минут для каждого из входов. (Желательно намного меньше.)
  • В случае ничьей победит большинство противников.

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

P.......1.
..........
P.....P...
..P.......
....P2....
...P.P....
.PP..P....
....P....P
PPPP....3.
.P..P.P..P

....P.....
P....1....
.P.....PP.
.PP....PP.
.2.P.P....
..P....P..
.P........
.....P.P..
P.....P...
.3.P.P....

..P..P..P.
..1....P.P
..........
.......2P.
...P....P3
.P...PP..P
.......P.P
..P..P..PP
..P.4P..P.
.......P..

..P...P...
.....P....
PPPP...P..
..P.......
...P......
.......P.1
.P..P....P
P2PP......
.P..P.....
..........

......PP.P
.P1..P.P..
......PP..
P..P....2.
.P.P3.....
....4..P..
.......PP.
..P5......
P.....P...
....PPP..P

Удачи, и не позволяйте соленым там сидеть слишком долго, иначе они испортятся!

Ох, а почему соленья, спросите вы?

Почему бы нет?

code-challenge path-finding Дверная ручка
источник
3
Нет никакого разумного способа показать, что вы действительно нашли «оптимальный результат», так как это, по сути, проблема коммивояжера (мужчины) и NP завершена.
Wally
@ Уолли Хм, да? Возможно, кто-то должен найти минимальные шаги для предоставленного тестового примера, и тогда все ответы могут быть основаны на этом.
Дверная ручка
2
Тестовый пример, вероятно, достаточно мал, чтобы перебрать силу как минимум - если кто-то хотел это сделать. И / или каждый, кто отвечает, может рассказать, что они получили за тестовый пример, и вам могут потребоваться другие ответы, чтобы хотя бы соответствовать этому минимуму.
Wally
3
Могут ли роботы проходить друг через друга? Если нет, каковы временные ограничения при интерпретации путей?
Питер Тейлор
1
@Gareth Проблема в том, что результаты не будут известны до тех пор, пока не будут обнаружены тестовые случаи, а затем после представления уже будут видны тестовые случаи.
дверная ручка

Ответы:

6

Рубин, 15 + 26 + 17 + 26 + 17 = 101

Робот находит соленья!

Хорошо, вот базовый уровень, чтобы начать людей, используя следующий супер наивный алгоритм:

  • Каждый тик, каждый робот будет действовать в числовом порядке, выполняя следующие шаги:
    • Определите ближайший (манхэттенское расстояние) рассол, на который не нацелены никакие другие роботы.
    • Выясните, какие соседние квадраты доступны для перемещения.
    • Выберите один из этих квадратов, предпочитая направления, которые приближают его к выбранному рассолу.

Вот как это выглядит для Test Case # 1:

Анимированный пример для TC1

Очевидно, это не очень хорошо, но это начало!

Код:

Tile = Struct.new(:world, :tile, :x, :y) do
    def passable?
        tile =~ /\.|P/
    end

    def manhattan_to other
        (self.x - other.x).abs + (self.y - other.y).abs
    end

    def directions_to other
        directions = []
        directions << ?U if self.y > other.y
        directions << ?D if self.y < other.y
        directions << ?L if self.x > other.x
        directions << ?R if self.x < other.x
        directions
    end

    def one_step direction
        nx,ny = case direction
            when ?U then [self.x, self.y - 1]
            when ?D then [self.x, self.y + 1]
            when ?L then [self.x - 1, self.y]
            when ?R then [self.x + 1, self.y]
        end

        self.world[nx,ny]
    end

    def move direction
        destination = one_step(direction)
        raise "can't move there" unless destination && destination.passable?

        destination.tile, self.tile = self.tile, ?.
    end
end

class World
    DIRECTIONS = %w(U D L R)

    def initialize s
        @board = s.split.map.with_index { |l,y| l.chars.map.with_index { |c,x| Tile.new(self, c, x, y) }}
        @width = @board[0].length
    end

    def [] x,y
        y >= 0 && x >= 0 && y < @board.size && x < @board[y].size && @board[y][x]
    end

    def robots
        tiles_of_type(/[0-9]/).sort_by { |t| t.tile }
    end

    def pickles
        tiles_of_type ?P
    end

    def tiles_of_type type
        @board.flatten.select { |t| type === t.tile }
    end

    def inspect
        @board.map { |l| l.map { |t| t.tile }*'' }*?\n
    end
end

gets(nil).split("\n\n").each do |input|
    w = World.new(input)
    steps = Hash[w.robots.map { |r| [r.tile, []] }]
    while (pickles_remaining = w.pickles).size > 0
        current_targets = Hash.new(0)

        w.robots.each do |r|
            target_pickle = pickles_remaining.min_by { |p| [current_targets[p], r.manhattan_to(p)] }

            possible_moves = World::DIRECTIONS.select { |d| t = r.one_step(d); t && t.passable? }
            raise "can't move anywhere" if possible_moves.empty?

            direction = (r.directions_to(target_pickle) & possible_moves).first || possible_moves[0]

            current_targets[target_pickle] += 1
            steps[r.tile] << direction
            r.move(direction)
        end
    end

    puts steps.values.map &:join
    p steps.values.map { |v| v.size }.max
end

Вводит данные в STDIN в точном формате кодового блока тестового примера в исходном вопросе. Вот что он печатает для этих тестов:

DDLLDLLLLULLUUD
LDLRRDDLDLLLLDR
URDDLLLLLULLUUL
15
ULDLDDLDRRRURRURDDDDDDDLLL
UUULDDRDRRRURRURDLDDDDLDLL
ULUURURRDDRRRRUUUDDDDLDLLL
26
URRRDRUDDDDLLLDLL
RUUUDLRRDDDLLLDLL
LDRDDLDDLLLLLLLUU
RUUURDRDDLLLLLUUU
17
DULLUUUUULDLDLLLLLDDRUUUUR
UDLRRRURDDLLLUUUUURDRUUUUD
26
LDDLDUUDDDUDDDDDR
ULUULDDDDDRDRDDDR
LULLDUUDDDRDRDDDR
UUUURDUURRRRDDDDD
LDLLUDDRRRRRRUDRR
17
Пол Престиж
источник
1

Python, 16 + 15 + 14 + 20 + 12 = 77

У меня действительно нет никакого опыта работы с проблемами типа коммивояжера, но у меня было немного времени, поэтому я решил попробовать. В основном он пытается выделить каждому боту определенные огурцы, пройдя его предварительным ходом, где они выбирают тех, кто ближе к ним и самый дальний от других. Затем он перебирает наиболее эффективный способ для каждого бота собирать выделенные ему соленья.

Я действительно понятия не имею, насколько жизнеспособен этот метод, но я подозреваю, что он не будет работать хорошо для больших плат с меньшим количеством ботов (четвертая доска уже иногда занимает более двух минут).

Код:

def parse_input(string):
    pickles = []
    size = len(string) - string.count('\n')
    poses = [None] * (size - string.count('.') - string.count('P'))
    for y,line in enumerate(string.strip().split('\n')):
        for x,char in enumerate(line):
            if char == '.':
                continue
            elif char == 'P':
                pickles.append((x,y))
            else:
                poses[int(char)-1] = (x,y)
    return pickles, poses

def move((px,py),(tx,ty)):
    if (px,py) == (tx,ty):
        return (px,py)
    dx = tx-px
    dy = ty-py
    if abs(dx) <= abs(dy):
        if dy < 0:
            return (px,py-1)
        else:
            return (px,py+1)
    else:
        if dx < 0:
            return (px-1,py)
        else:
            return (px+1,py)

def distance(pos, pickle):
    return abs(pos[0]-pickle[0]) + abs(pos[1]-pickle[1])

def calc_closest(pickles,poses,index):
    distances = [[distance(pos,pickle) for pickle in pickles] for pos in poses]
    dist_diffs = []
    for i, pickle_dists in enumerate(distances):
        dist_diffs.append([])
        for j, dist in enumerate(pickle_dists):
            other = [d[j] for d in distances[:i]+distances[i+1:]]
            dist_diffs[-1].append(min(other)-dist)

    sorted = pickles[:]
    sorted.sort(key = lambda ppos: -dist_diffs[index][pickles.index(ppos)])
    return sorted

def find_best(items,level):
    if level == 0:
        best = (None, None)
        for rv, rest in find_best(items[1:],level+1):
            val = distance(items[0],rest[0]) + rv
            if best[0] == None or val < best[0]:
                best = (val, [items[0]] + rest)
        return best

    if len(items) == 1:
        return [(0,items[:])]

    size = len(items)
    bests = []
    for i in range(size):
        best = (None, None)
        for rv, rest in find_best(items[:i]+items[i+1:],level+1):
            val = distance(items[i],rest[0]) + rv
            if best[0] == None or val < best[0]:
                best = (val, [items[i]] + rest)
        if best[0] != None:
            bests.append(best)
    return bests

def find_best_order(pos,pickles):
    if pickles == []:
        return 0,[]
    best = find_best([pos]+pickles,0)
    return best

def walk_path(pos,path):
    history = ''
    while path:
        npos = move(pos, path[0])
        if npos == path[0]:
            path.remove(path[0])

        if npos[0] < pos[0]:
            history += 'L'
        elif npos[0] > pos[0]:
            history += 'R'
        elif npos[1] < pos[1]:
            history += 'U'
        elif npos[1] > pos[1]:
            history += 'D'
        pos = npos
    return history

def find_paths(input_str):
    pickles, poses = parse_input(input_str)                 ## Parse input string and stuff
    orig_pickles = pickles[:]
    orig_poses = poses[:]
    numbots = len(poses)

    to_collect = [[] for i in range(numbots)]               ## Will make a list of the pickles each bot should go after
    waiting = [True] * numbots
    targets = [None] * numbots
    while pickles:
        while True in waiting:                              ## If any bots are waiting for a new target
            index = waiting.index(True)
            closest = calc_closest(pickles,poses,index)     ## Prioritizes next pickle choice based upon how close they are RELATIVE to other bots
            tar = closest[0]

            n = 0
            while tar in targets[:index]+targets[index+1:]:                 ## Don't target the same pickle!
                other_i = (targets[:index]+targets[index+1:]).index(tar)
                dist_s = distance(poses[index],tar)
                dist_o = distance(poses[other_i],tar)
                if dist_s < dist_o:
                    waiting[other_i] = True
                    break

                n += 1
                if len(closest) <= n:
                    waiting[index] = False
                    break
                tar = closest[n]

            targets[index] = tar
            waiting[index] = False      

        for i in range(numbots):                            ## Move everything toward targets  (this means that later target calculations will not be based on the original position)
            npos = move(poses[i], targets[i])
            if npos != poses[i]:
                poses[i] = npos
            if npos in pickles:
                to_collect[i].append(npos)
                pickles.remove(npos)
                for t, target in enumerate(targets):
                    if target == npos:
                        waiting[t] = True               

    paths = []
    sizes = []

    for i,pickle_group in enumerate(to_collect):                    ## Lastly brute force the most efficient way for each bot to collect its allotted pickles
        size,path = find_best_order(orig_poses[i],pickle_group)
        sizes.append(size)
        paths.append(path)
    return max(sizes), [walk_path(orig_poses[i],paths[i]) for i in range(numbots)]

def collect_pickles(boards):
    ## Collect Pickles!
    total = 0
    for i,board in enumerate(boards):
        result = find_paths(board)
        total += result[0]
        print "Board "+str(i)+": ("+ str(result[0]) +")\n"
        for i,h in enumerate(result[1]):
            print '\tBot'+str(i+1)+': '+h
        print

    print "Total Score: " + str(total)

boards = """
P.......1.
..........
P.....P...
..P.......
....P2....
...P.P....
.PP..P....
....P....P
PPPP....3.
.P..P.P..P

....P.....
P....1....
.P.....PP.
.PP....PP.
.2.P.P....
..P....P..
.P........
.....P.P..
P.....P...
.3.P.P....

..P..P..P.
..1....P.P
..........
.......2P.
...P....P3
.P...PP..P
.......P.P
..P..P..PP
..P.4P..P.
.......P..

..P...P...
.....P....
PPPP...P..
..P.......
...P......
.......P.1
.P..P....P
P2PP......
.P..P.....
..........

......PP.P
.P1..P.P..
......PP..
P..P....2.
.P.P3.....
....4..P..
.......PP.
..P5......
P.....P...
....PPP..P
""".split('\n\n')

collect_pickles(boards)

Вывод:

Board 0: (16)

    Bot1: DLDLLLLDLLULUU
    Bot2: LDLDLLDDLDRURRDR
    Bot3: URDDLLLULULURU

Board 1: (15)

    Bot1: ULRDRDRRDLDDLUL
    Bot2: DDURURULLUUL
    Bot3: ULRRDRRRURULRR

Board 2: (14)

    Bot1: URRRDDDDDRLLUL
    Bot2: UUURDRDDLD
    Bot3: DDDLDDLUUU
    Bot4: RULLLDUUUL

Board 3: (20)

    Bot1: DLULUUUUULDLLLULDDD
    Bot2: LURDDURRDRUUUULUULLL

Board 4: (12)

    Bot1: LDDLDR
    Bot2: ULUULRRR
    Bot3: LUURURDR
    Bot4: RRRDRDDDR
    Bot5: LLDLRRRDRRRU

Total Score: 77
KSab
источник