Robot! Kumpulkan acar ini!

10

Saya sepertinya membuat acar. Secara harfiah. Saya menjatuhkan banyak acar di lantai dan sekarang mereka semua bertebaran! Saya membutuhkan Anda untuk membantu saya mengumpulkan semuanya. Oh, apakah saya menyebutkan saya memiliki banyak robot atas perintah saya? (Mereka juga tersebar di mana-mana; Aku benar-benar buruk dalam mengatur hal-hal.)

Anda harus mengambil input dalam bentuk:

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

yaitu, beberapa baris baik ., P(acar), atau digit (ID robot). (Anda dapat mengasumsikan bahwa setiap baris memiliki panjang yang sama, diisi dengan ..) Anda dapat memasukkan baris-baris ini sebagai array, atau menyeruput dari STDIN, atau membaca dalam baris tunggal yang dipisahkan koma, atau membaca file, atau melakukan apa pun yang Anda mau suka mengambil input.

Output Anda harus dalam bentuk ngaris, di mana nID robot tertinggi. (ID robot akan selalu berurutan mulai dari 1.) Setiap baris akan berisi jalur robot, dibentuk dari huruf L(kiri), R(kanan), U(atas), dan D(bawah). Sebagai contoh, inilah contoh output untuk teka-teki itu:

LLU
RDR
LRRR
D

Bisa juga begitu

LLU RDR LRRR D

Atau

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

Atau format apa pun yang Anda inginkan, selama Anda bisa tahu apa solusi yang seharusnya.

Tujuan Anda adalah untuk menemukan output optimal, yang merupakan langkah yang paling sedikit. Jumlah langkah dihitung sebagai jumlah langkah terbesar dari semua robot. Misalnya, contoh di atas memiliki 4 langkah. Perhatikan bahwa mungkin ada beberapa solusi, tetapi Anda hanya perlu menghasilkan satu.

Mencetak:

  • Program Anda akan dijalankan dengan masing-masing dari 5 kasus pengujian (dihasilkan secara acak).
  • Anda harus menambahkan langkah-langkah dari setiap lari, dan itu akan menjadi skor Anda.
  • Total skor kumulatif terendah akan menang.
  • Anda mungkin tidak membuat hard-code untuk input spesifik ini. Kode Anda juga harus berfungsi untuk input lainnya.
  • Robot dapat saling melewati.
  • Program Anda harus deterministik, yaitu keluaran yang sama untuk setiap proses. Anda dapat menggunakan generator angka acak, asalkan diunggulkan dan secara konsisten menghasilkan bilangan lintas platform yang sama.
  • Kode Anda harus berjalan dalam 3 menit untuk setiap input. (Lebih disukai lebih sedikit.)
  • Dalam hal seri, sebagian besar upvotes akan menang.

Berikut ini adalah contoh-contoh tesnya. Mereka dihasilkan secara acak dengan skrip Ruby kecil yang saya tulis.

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

Semoga beruntung, dan jangan biarkan acar terlalu lama di sana, atau mereka akan rusak!

Oh, dan mengapa acar, Anda bertanya?

Kenapa tidak?

code-challenge path-finding Gagang pintu
sumber
3
Tidak ada cara yang masuk akal untuk menunjukkan bahwa Anda benar-benar menemukan "output optimal" karena ini pada dasarnya adalah masalah salesman keliling (pria) dan NP lengkap.
Wally
@ Sebenarnya Hmm, benar? Mungkin seseorang harus menemukan langkah-langkah minimum untuk test case yang disediakan, dan kemudian semua jawaban dapat didasarkan pada itu.
Gagang Pintu
2
Kasing uji mungkin cukup kecil untuk memberi kekuatan minimum - jika seseorang ingin melakukan itu. Dan / atau setiap orang yang menjawab bisa memberi tahu apa yang mereka dapatkan untuk kasus uji dan Anda bisa meminta jawaban lain untuk setidaknya cocok dengan minimum itu.
Wally
3
Bisakah robot saling melewati? Jika tidak, apa batasan waktu untuk menafsirkan jalur?
Peter Taylor
1
@ Gareth Masalah dengan itu adalah bahwa skor tidak akan diketahui sampai testcases terungkap, dan kemudian pengiriman setelah itu sudah akan melihat testcases.
Gagang Pintu

Jawaban:

6

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

Robot Menemukan Acar!

Oke, inilah garis dasar untuk memulai orang, menggunakan algoritma super-naif berikut:

  • Setiap centang, setiap robot akan bertindak dalam urutan angka, melakukan langkah-langkah berikut:
    • Identifikasi acar terdekat (jarak Manhattan) yang tidak ditargetkan oleh robot lain.
    • Cari tahu kotak yang berdekatan yang tersedia untuk dipindahkan.
    • Pilih salah satu kotak itu, lebih memilih arah yang mendekatkannya ke acar yang dipilih.

Begini tampilannya untuk Test Case # 1:

Contoh animasi untuk TC1

Jelas ini tidak terlalu bagus tapi ini awal!

Kode:

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

Mengambil input pada STDIN persis dalam format blok kode kasus uji pada pertanyaan awal. Inilah yang dicetak untuk kasus uji tersebut:

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

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

Saya tidak benar-benar memiliki pengalaman sebelumnya untuk masalah tipe salesman keliling tetapi saya punya sedikit waktu di tangan saya jadi saya pikir saya akan mencobanya. Ini pada dasarnya mencoba untuk membagikan masing-masing bot acar tertentu dengan berjalan itu meskipun menjalankan awal di mana mereka pergi untuk yang paling dekat dengan mereka dan terjauh dari yang lain. Itu kemudian brute-memaksa cara paling efisien untuk setiap bot untuk mengumpulkan acar yang diberikan.

Saya benar-benar tidak tahu betapa layaknya metode ini, tetapi saya menduga itu tidak akan bekerja dengan baik untuk papan yang lebih besar dengan bot yang lebih sedikit (papan keempat kadang-kadang membutuhkan waktu lebih dari dua menit).

Kode:

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)

Keluaran:

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
sumber