Roboter! Sammle diese Gurken!

10

Ich scheine mich in eine Art Essiggurke verwickelt zu haben. Buchstäblich. Ich habe ein paar Gurken auf den Boden fallen lassen und jetzt sind sie alle verstreut! Du musst mir helfen, sie alle zu sammeln. Oh, habe ich schon erwähnt, dass ich ein paar Roboter zur Verfügung habe? (Sie sind auch alle überall verstreut; ich bin wirklich schlecht darin, Dinge zu organisieren.)

Sie müssen Eingaben in Form von:

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

dh mehrzeiligen entweder ., P(Gurke) oder eine Ziffer (Roboter ID). (Sie können davon ausgehen, dass jede Zeile gleich lang und aufgefüllt ist ..) Sie können diese Zeilen als Array eingeben oder aus STDIN schlürfen oder eine durch Kommas getrennte einzelne Zeile einlesen oder eine Datei lesen oder alles tun, was Sie möchten nehme gerne die Eingabe.

Ihre Ausgabe muss in Form von nLinien erfolgen, wobei ndie höchste Roboter-ID angegeben ist. (Roboter-IDs beginnen immer ab 1.) Jede Zeile enthält den Pfad des Roboters, der aus den Buchstaben L(links), R(rechts), U(oben) und D(unten) besteht. Hier ist zum Beispiel eine Beispielausgabe für dieses Puzzle:

LLU
RDR
LRRR
D

Es kann auch sein

LLU RDR LRRR D

Oder

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

Oder ein beliebiges Format, solange Sie wissen, wie die Lösung aussehen soll.

Ihr Ziel ist es, die optimale Ausgabe zu finden, die die geringsten Schritte aufweist. Die Anzahl der Schritte wird als die größte Anzahl von Schritten aller Roboter gezählt. Zum Beispiel hatte das obige Beispiel 4 Schritte. Beachten Sie, dass es möglicherweise mehrere Lösungen gibt, Sie jedoch nur eine ausgeben müssen.

Wertung:

  • Ihr Programm wird mit jedem der 5 (zufällig generierten) Testfälle ausgeführt.
  • Sie müssen die Schritte aus jedem Lauf hinzufügen, und das ist Ihre Punktzahl.
  • Die niedrigste kumulative Gesamtpunktzahl gewinnt.
  • Sie können diese spezifischen Eingaben möglicherweise nicht fest codieren. Ihr Code sollte auch für andere Eingaben funktionieren.
  • Roboter können sich gegenseitig passieren.
  • Ihr Programm muss deterministisch sein, dh für jeden Lauf dieselbe Ausgabe. Sie können einen Zufallszahlengenerator verwenden, solange dieser gesetzt ist und plattformübergreifend dieselben Zahlen erzeugt.
  • Ihr Code muss für jede Eingabe innerhalb von 3 Minuten ausgeführt werden. (Am liebsten viel weniger.)
  • Bei einem Unentschieden gewinnen die meisten Upvotes.

Hier sind die Testfälle. Sie wurden zufällig mit einem kleinen Ruby-Skript generiert, das ich geschrieben habe.

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

Viel Glück und lass die Gurken nicht zu lange dort sitzen, sonst werden sie verderben!

Oh, und warum Gurken, fragst du?

Warum nicht?

code-challenge path-finding Türknauf
quelle
3
Es gibt keinen vernünftigen Weg, um zu zeigen, dass Sie tatsächlich die "optimale Ausgabe" gefunden haben, da dies im Wesentlichen ein Problem für reisende Verkäufer (Männer) ist und NP vollständig ist.
Wally
@ Wally Hmm, ist es? Vielleicht sollte jemand die Mindestschritte für den bereitgestellten Testfall finden, und dann können alle Antworten darauf basieren.
Türknauf
2
Der Testfall ist wahrscheinlich klein genug, um ein Minimum an roher Gewalt zu erzwingen - wenn jemand das tun wollte. Und / oder jeder, der antwortet, könnte sagen, was er für den Testfall bekommen hat, und Sie könnten andere Antworten benötigen, um mindestens diesem Minimum zu entsprechen.
Wally
3
Können sich Roboter gegenseitig passieren? Wenn nicht, wie lauten die zeitlichen Einschränkungen bei der Interpretation der Pfade?
Peter Taylor
1
@Gareth Das Problem dabei ist, dass die Ergebnisse erst bekannt werden, wenn die Testfälle aufgedeckt werden. Danach werden die Testfälle bereits angezeigt.
Türknauf

Antworten:

6

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

Roboter findet Gurken!

Okay, hier ist eine Basis, um die Leute mit dem folgenden super-naiven Algorithmus zum Laufen zu bringen:

  • Jeder Tick, jeder Roboter handelt in numerischer Reihenfolge und führt die folgenden Schritte aus:
    • Identifizieren Sie die nächstgelegene (Manhattan-Entfernung) Essiggurke, auf die kein anderer Roboter zielt.
    • Finden Sie heraus, zu welchen benachbarten Quadraten Sie sich bewegen können.
    • Wählen Sie eines dieser Quadrate aus und bevorzugen Sie Richtungen, die es näher an die ausgewählte Gurke bringen.

So sieht es für Testfall 1 aus:

Animiertes Beispiel für TC1

Das ist natürlich nicht sehr gut, aber es ist ein Anfang!

Code:

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

Nimmt Eingaben in STDIN genau im Format des Testfall-Codeblocks in der ursprünglichen Frage vor. Für diese Testfälle wird Folgendes gedruckt:

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

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

Ich habe noch keine Erfahrung mit Problemen mit reisenden Verkäufern, aber ich hatte ein bisschen Zeit, also dachte ich, ich würde es versuchen. Grundsätzlich wird versucht, jedem Bot bestimmte Gurken zuzuweisen, indem er durch einen Vorlauf läuft, bei dem sie nach denjenigen suchen, die ihnen am nächsten und am weitesten von den anderen entfernt sind. Es erzwingt dann die effizienteste Methode für jeden Bot, um seine zugewiesenen Gurken zu sammeln.

Ich habe wirklich keine Ahnung, wie praktikabel diese Methode ist, aber ich vermute, dass sie für größere Boards mit weniger Bots nicht gut funktioniert (das vierte Board dauert manchmal schon mehr als zwei Minuten).

Code:

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)

Ausgabe:

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
quelle