Robôs! Colete esses picles!

10

Parece que me meti em confusão. Literalmente. Deixei cair um monte de picles no chão e agora estão todos espalhados! Preciso que você me ajude a coletar todos eles. Ah, eu mencionei que tenho um monte de robôs sob meu comando? (Eles também estão espalhados por todo o lugar; sou muito ruim em organizar as coisas.)

Você deve receber informações na forma de:

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

isto é, várias linhas de ambos ., P(salmoura), ou um dígito (identificação do robô). (Você pode supor que cada linha tenha o mesmo comprimento, preenchida com ..) Você pode inserir essas linhas como uma matriz ou usar o STDIN ou ler em uma única linha separada por vírgula ou ler um arquivo ou fazer o que quiser gostaria de receber a entrada.

Sua saída deve estar na forma de nlinhas, onde né o ID do robô mais alto. (As IDs do robô sempre serão sequenciais, começando em 1.) Cada linha conterá o caminho do robô, formado pelas letras L(esquerda), R(direita), U(para cima) e D(para baixo). Por exemplo, aqui está um exemplo de saída para esse quebra-cabeça:

LLU
RDR
LRRR
D

Também pode ser

LLU RDR LRRR D

Ou

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

Ou qualquer formato que você desejar, desde que você saiba qual deve ser a solução.

Seu objetivo é encontrar a saída ideal, que é a que tem menos etapas. A quantidade de etapas é contada como a maior quantidade de etapas de todos os robôs. Por exemplo, o exemplo acima teve 4 etapas. Observe que pode haver várias soluções, mas você só precisa produzir uma.

Pontuação:

  • Seu programa será executado com cada um dos 5 casos de teste (gerados aleatoriamente).
  • Você deve adicionar as etapas de cada execução, e essa será sua pontuação.
  • A pontuação total e cumulativa mais baixa vencerá.
  • Você não pode codificar para essas entradas específicas. Seu código também deve funcionar para qualquer outra entrada.
  • Os robôs podem passar um pelo outro.
  • Seu programa deve ser determinístico, ou seja, a mesma saída para cada execução. Você pode usar um gerador de números aleatórios, desde que seja semeado e produza consistentemente os mesmos números em várias plataformas.
  • Seu código deve ser executado dentro de 3 minutos para cada uma das entradas. (De preferência, muito menos.)
  • Em caso de empate, a maioria dos votos positivos vencerá.

Aqui estão os casos de teste. Eles foram gerados aleatoriamente com um pequeno script Ruby que escrevi.

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

Boa sorte, e não deixe os picles ficarem lá por muito tempo, ou eles estragam!

Ah, e por que picles, você pergunta?

Por que não?

code-challenge path-finding Maçaneta da porta
fonte
3
Não há uma maneira razoável de mostrar que você realmente encontrou a "saída ideal", pois esse é essencialmente um problema do vendedor ambulante (homens) e é NP completo.
Wally
@Wally Hmm, é? Talvez alguém deva encontrar as etapas mínimas para o caso de teste fornecido e todas as respostas podem basear-se nisso.
Maçaneta
2
O caso de teste é provavelmente pequeno o suficiente para força bruta no mínimo - se alguém quiser fazer isso. E / ou todos que responderem poderiam dizer o que obtiveram para o caso de teste e você pode precisar de outras respostas para, pelo menos, corresponder a esse mínimo.
Wally
3
Os robôs podem passar um pelo outro? Caso contrário, quais são as restrições de tempo na interpretação dos caminhos?
Peter Taylor
11
@Gareth O problema é que as pontuações não serão conhecidas até que as caixas de teste sejam reveladas e, depois disso, as submissões depois disso já verão as caixas de teste.
Maçaneta

Respostas:

6

Ruby, 15 + 26 + 17 + 26 + 17 = 101

Robô encontra picles!

Ok, aqui está uma linha de base para iniciar as pessoas, usando o seguinte algoritmo super ingênuo:

  • Cada tick, cada robô atuará em ordem numérica, executando as seguintes etapas:
    • Identifique o pickle mais próximo (distância de Manhattan) que nenhum outro robô está mirando.
    • Descobrir quais quadrados adjacentes estão disponíveis para mover.
    • Escolha um desses quadrados, preferindo direções que o aproximem do pickle selecionado.

Aqui está o que parece para o Caso de Teste 1:

Exemplo animado para TC1

Obviamente, isso não é muito bom, mas é um começo!

Código:

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

Insere STDIN exatamente no formato do bloco de código do caso de teste na pergunta original. Aqui está o que é impresso para esses casos de teste:

DDLLDLLLLULLUUD
LDLRRDDLDLLLLDR
URDDLLLLLULLUUL
15
ULDLDDLDRRRURRURDDDDDDDLLL
UUULDDRDRRRURRURDLDDDDLDLL
ULUURURRDDRRRRUUUDDDDLDLLL
26
URRRDRUDDDDLLLDLL
RUUUDLRRDDDLLLDLL
LDRDDLDDLLLLLLLUU
RUUURDRDDLLLLLUUU
17
DULLUUUUULDLDLLLLLDDRUUUUR
UDLRRRURDDLLLUUUUURDRUUUUD
26
LDDLDUUDDDUDDDDDR
ULUULDDDDDRDRDDDR
LULLDUUDDDRDRDDDR
UUUURDUURRRRDDDDD
LDLLUDDRRRRRRUDRR
17
Paul Prestidge
fonte
1

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

Eu realmente não tenho nenhuma experiência anterior com problemas do tipo vendedor ambulante, mas eu tinha um pouco de tempo em minhas mãos, então pensei em tentar. Basicamente, ele tenta atribuir a cada bot certos picles, percorrendo-o por uma corrida preliminar, onde eles buscam os mais próximos e os mais distantes dos outros. Em seguida, força bruta a maneira mais eficiente de cada bot coletar seus pickles alocados.

Realmente não tenho ideia de quão viável esse método é, mas suspeito que não funcionaria bem para placas maiores com menos bots (a quarta placa já leva algumas vezes mais de dois minutos).

Código:

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)

Resultado:

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
fonte