Temukan jalannya!

10

Anda harus menulis program atau fungsi.

Input adalah 'peta' angka. Anda dapat memilih untuk mengambil peta sebagai string dengan karakter baris baru ( \n) atau array string 2D.

Semua peta adalah 5 karakter dengan 5 karakter, dan karakter selalu berupa digit lebih besar dari 0 atau spasi.

Berikut ini contoh peta:

12 45
11233
  233
    1
2 899

Tugas Anda adalah menemukan komponen yang terhubung di peta. Komponen yang valid adalah serangkaian setidaknya tiga digit identik yang terhubung secara horizontal dan / atau vertikal ( bukan diagonal ) ( bukan spasi ). Anda kemudian perlu mengganti karakter dari komponen terhubung yang valid dengan xs dan mencetak atau mengembalikan hasil itu.

Jadi, output untuk contoh di atas adalah:

x2 45
xx2xx
  2xx
    1
2 899

Berikut ini adalah test case lainnya (terima kasih kepada Martin Ender):

Input:
2   3
    4
 1  5
111 6
11  7

Output:
2   3
    4
 x  5
xxx 6
xx  7

Ini adalah kode golf sehingga kode terpendek dalam byte menang!

Daniel
sumber
Apakah built-in diizinkan?
Ioannes
@ Joannes, ya.
Daniel

Jawaban:

1

JavaScript (ES6), 171 161 139 137 136 133 132 byte

f=(a,i=0)=>(F=i=>" "<c&&a[i]===c&&(a[i]=n,1+F(i-1)+F(i+1)+F(i-6)+F(i+6)),n=1,c=a[i],n=F(i)>2?"x":c,c=1,F(i),i>28?a:f(a,++i+(i%6>4)))
<!-- this HTML included just for testing --><textarea rows=5 cols=6 oninput="document.querySelector`pre`.innerHTML=this.value.length==29?f([...this.value]).join``:'invalid input'">12 45&#10;11233&#10;  233&#10;    1&#10;2 899</textarea><br/><pre></pre>

Ini adalah terjemahan dari jawaban Python saya. I / O sebagai array karakter.

Sayang sekali tidak ada cara efisien untuk melakukan sum...

PurkkaKoodari
sumber
5

Python 3, 238 237 200 199 192 181 byte

def f(a,i=0):F=lambda i,n,c:29>i>=0!=" "!=a[i]==c!=n and(a.__setitem__(i,n)or-~sum(F(i+j,n,c)for j in[-1,1,-6,6]));j=i+i//5;F(j,[a[j],"x"][2<F(j,1,a[j])],1);i>23or f(a,i+1);return a

Menentukan fungsi f(a)yang mengambil input sebagai array karakter dan mengembalikan array yang sama dimodifikasi. ( Susunan karakter dapat diterima sebagai string secara default. )

Tidak diganggu dengan penjelasan

Kode yang dimodifikasi bersifat rekursif, tetapi berfungsi sama.

# The main function; fills all continuous nonempty areas of size >= 3 in array
# with x's. Both modifies and returns array.
def findpaths(array):
    # Fills a continuous area of curr_char in array with new_char, starting
    # from index. Returns the number of cells affected.
    def floodfill(index, new_char, curr_char):
        if (0 <= index < 29                   # Check that the position is in bounds
                and (index + 1) % 6 != 0      # Don't fill newlines
                and array[index] != " "       # Don't fill empty cells
                and array[index] == curr_char # Don't fill over other characters
                and curr_char != new_char):   # Don't fill already filled-in cells
            array[index] = new_char # Fill current position
            return (1 # Add neighboring cells' results, plus 1 for this cell
                    + floodfill(index + 1, new_char, curr_char)  # Next char
                    + floodfill(index - 1, new_char, curr_char)  # Previous char
                    + floodfill(index + 6, new_char, curr_char)  # Next line
                    + floodfill(index - 6, new_char, curr_char)) # Previous line
        return 0 # Nothing was filled. The golfed solution returns False here,
                 # but that's coerced to 0 when adding.

    for i in range(25): # Loop through the 25 cells
        i += i // 5 # Accommodate for newlines in input
        curr_char = array[i] # Get the cell's contents
        # Fill the area from the cell with dummies
        area_size = floodfill(i, 1, curr_char)
        # Convert dummies to "x" if area was large enough, back to original otherwise
        fill_char = "x" if 2 < area_size else curr_char
        floodfill(i, fill_char, 1)
    return array
PurkkaKoodari
sumber
2 byte mati untuk mengalahkan solusi Mathematica ...
FlipTack
1
@ Lipatan Ya. Saya tidak berpikir itu terjadi hari ini, tapi saya menerjemahkan ini ke JS dan itu terlihat menjanjikan.
PurkkaKoodari
3

Ruby, 304 byte

def b(s,i)
  @v=[]
  b2(s,i,s[i])
end
def b2(s,i,c)
  if(0...s.size)===i&&s[i]==c&&!@v[i]
    @v[i]=s[i]='x'
    [1,-1,6,-6].each{|j|b2(s,i+j,c)}
  end
  s
end
def f(s)
  z = s.dup
  ps = ->(i){b(z.dup,i).scan('x').size}
  (0...s.size).each{|i|b(s, i)if ![' ',"\n"].include?(s[i])&&ps.call(i)>2}
  s
end

contoh penggunaan:

puts f(File.read("map.txt"))

kode menggunakan kembali metode 'blot' untuk menghitung panjang jalur.

variabel / metode:

  • f (s): berfungsi untuk mengonversi string peta, mengembalikan peta baru dengan 'x's
  • ps (i): ukuran jalur dari indeks peta i (di mana x = i% 6, y = i / 6)
  • s: string masukan, garis peta dipisahkan oleh "\ n"
  • z: salinan string input
  • b (s, i): fungsi 'blot': menulis 'x' dari indeks peta i di atas paths
  • @v: larik 'dikunjungi'

Cobalah penjelasan yang lebih terperinci:

buat salinan string input, yang kami gunakan untuk menemukan panjang jalur dari titik tertentu di peta.

z = s.dup

mendefinisikan fungsi anonim 'ps' (panjang jalur) (lambda) yang mengambil indeks peta i sebagai argumen. mengembalikan panjang jalan dari titik itu. ia melakukan ini dengan memanggil metode 'b' (blot) untuk memasukkan x pada salinan peta asli dan kemudian menghitung jumlah x dalam string yang dikembalikan.

  ps = ->(i){b(z.dup,i).scan('x').size}

bagian berikut ini mengulangi setiap karakter dalam peta (indeks i, karakter s [i]). ia memanggil fungsi 'b' (blot) pada posisi peta i jika panjang jalur dari posisi i lebih besar dari 2, dan jika itu bukan spasi atau karakter baris baru.

  (0...s.size).each { |i|
     b(s, i) if ![' ',"\n"].include?(s[i]) && ps.call(i) > 2
  }

fungsi b (blot) mengambil string peta dan indeks sebagai argumen. ini menginisialisasi @v (array yang dikunjungi) dan memanggil fungsi pembantu b2.

def b(s,i)
  @v=[]
  b2(s,i,s[i])
end

fungsi b2 mengambil string peta, posisi peta (i), dan karakter di jalur saat ini (c). itu menyebut dirinya secara rekursif untuk mengganti bagian digit yang terhubung dengan karakter 'x'. mengembalikan string input (ini agar fungsi ps dapat memanggil pemindaian () pada nilai kembali).

pernyataan if ini memeriksa bahwa posisi peta (i) yang diberikan adalah dalam batas-batas string (0 ... s.ukuran) dan bahwa karakter pada s [i] sama dengan karakter awal. juga @v [i] diperiksa untuk menghindari rekursi tak terbatas.

if(0...s.size) === i && s[i] == c && !@v[i]

ini adalah bit yang menggantikan karakter pada index (i) dengan karakter 'x'. itu juga menandai indeks itu sebagai dikunjungi.

@v[i] = s[i] = 'x'

ini adalah di mana b2 menyebut dirinya secara rekursif mencari jalan. i + 1 adalah satu karakter ke kanan, i-1 adalah satu karakter ke kiri, i + 6 adalah satu baris ke bawah (5 digit + 1 baris baru = 6 karakter), i-6 adalah satu baris ke atas.

[1,-1,6,-6].each { |j| b2(s, i+j, c) }
Andrew
sumber
1

C (Ansi), 243 233 179 188 Bytes

Golf:

#define O o[1][l]
x,n,l,L;r(o,l)char**o;{if(!(l>L|l<0|O<47|O!=x))n++,O++,r(o,l-1),r(o,l+6),r(o,l-6),r(o,l+1),n>2?O='x':O--;}main(g,o)char**o;{for(;(L=30)>l;l++)n=0,x=O,r(o,l);puts(o[1]);}

Dengan Anotasi:

#define O o[1][l]
x,n,l,L;      /*-------------------------- Globals*/
r(o,l)char**o;{ /*------------------------ Recursive Function*/
    if(!(l>L|l<0|O<47|O!=x)) /*----------- if this cell is valid(in
                                              range, is a number, is the 
                                              same as the parent number*/
    n++,     /*--------------------------- Increment count*/
    O++,     /*--------------------------- Increment character to mark*/
    r(o,l-1),  /*------------------------- Recurse left*/
    r(o,l+6),  /*------------------------- Recurse down*/
    r(o,l-6),  /*------------------------- Recurse down*/
    r(o,l+1),  /*------------------------- Recurse right*/
    n>2?O='x':O--;  /*---------------------If greater than 3, replace with x, else decrement character*/ 
}          /*----------------------------- Return*/

main(g,o)char**o;{ /*--------------------- Main*/
    for(;l<(L=30);l++){ /*---------------- For entire string and set L*/
        n=0;
        x=O;        /*-------------------- set counter to 0*/
        r(o,l); /*------------------------ Recurse*/
    } /*---------------------------------- End While*/
    puts(o[1]); /*------------------------ Print*/

}

Memasukkan:

Harapkan baris baru di awal dan akhir string.

Input Contoh:

./findPaths "
12 45
11233
  233
    1
2 899
"

Contoh Output:

x2 45
xx2xx
  2xx
    1
2 899

Memperbarui

Membuat grid diperbaiki memungkinkan saya untuk mencukur hampir 60 byte.

dj0wns
sumber
Saya kira saya dapat menyimpan seperti 22 karakter jika saya mengubahnya ke ukuran peta perbaikan - Saya akan mengubah itu jika saya menemukan hal lain yang ingin saya ubah
dj0wns
1

Mathematica, 180 byte

(f=Flatten@#;p=Partition)[If[Tr[1^VertexComponent[r~Graph~Cases[##&@@p[#,2,1]&/@Join[g=p[r,5],g],{a_,b_}/;(A=f[[a]])==f[[b]]&&A!=" ":>a<->b],#]]<3,f[[#]],"x"]&/@(r=Range@25),5]&

Penjelasan:

(f=Flatten@#;p=Partition)[
  If[
    Tr[1^VertexComponent[
        r~Graph~Cases[
          ##&@@p[#,2,1]&/@Join[g=p[r,5],g],
          {a_,b_}/;(A=f[[a]])==f[[b]]&&A!=" ":>a<->b
        ],
        #
      ]]<3,
    f[[#]],
    "x"
  ]&/@(r=Range@25),
  5
]&

Fungsi murni yang menerima 5x5array. adalah karakter penggunaan pribadi 3 byte yang U+F3C7mewakili operator transpos postfix \[Transpose].

(f=Flatten@#;p=Partition): Ratakan daftar input dan simpan di f. Set p = Partitiondan kembalikan.

g=p[r,5]: Array {{1,2,3,4,5}, ..., {21,22,23,24,25}}(ini karena rdisetel ke Range@25).

Join[g=p[r,5],g]: daftar baris dan kolom g.

p[#,2,1]&: Fungsi murni yang memecah daftar #menjadi daftar panjang 2dengan tumpang tindih 1; yaitu, daftar pasangan yang berdekatan di #.

##&@@p[#,2,1]&: Sama seperti di atas kecuali ia mengembalikan a Sequence.

##&@@p[#,2,1]&/@Join[g=p[r,5],g]: Memetakan fungsi sebelumnya dari baris dan kolom guntuk mendapatkan daftar semua entri yang berdekatan di g. Naluriku mengatakan ada cara yang lebih pendek untuk melakukan ini.

r~Graph~Cases[...]: Grafik yang simpulnya adalah bilangan bulat 1, ..., 25dan ujung-ujungnya adalah tepi antara entri yang berdekatan gyang memiliki entri terkait yang sama dalam array input (selain " ")

{a_,b_}/;(A=f[[a]])==f[[b]]&&A!=" ": Pola yang cocok {a,b}sehingga f[[a]] == f[[b]](nilai yang sama dalam array input) dan yang tidak sama dengan " ". Setel A = f[[a]]untuk menyimpan 1byte.

...:>a<->b: Ganti setiap kecocokan dengan ujung yang tidak terarah dari a ke b.

VertexComponent: Mengembalikan komponen yang terhubung dari argumen kedua (titik) di argumen pertama (grafik).

Tr[1^VertexComponent[...]]: Ukuran komponen yang terhubung. Menghemat 1byte dari Length@VertexComponent[...].

If[Tr[...]<3,f[[#]],"x"]&: Fungsi Pure yang mengambil sebuah entri #di g. Jika ukuran komponen yang terhubung kurang dari 3, ganti dengan entri yang sesuai di input. Kalau tidak, ganti dengan "x".

(f=Flatten@#;p=Partition)[...,5]: Dan akhirnya membentuk kembali hasilnya menjadi sebuah 5x5array.

ngenisis
sumber
0

Clojure, 188 byte

Ini cukup luar biasa: D

#(apply str(map-indexed(fn[i v](if((set(flatten(for[m(range 30)](let[n(for[p[-1 -6 1 6]:when(=(get %(+ m p)0)((set"123456789")(% m)))](+ m p))](if(< 1(count n))(conj n m)[])))))i)\x v))%))

Disebut seperti ini (dibutuhkan 1D vektor karakter):

(def f #(apply str(...))

(print (str "\n" (f (vec (str "12 45\n"
                              "11233\n"
                              "  233\n"
                              "    1\n"
                              "2 899\n")))))

(print (str "\n" (f (vec (str "2   3\n"
                              "    4\n"
                              " 1  5\n"
                              "111 6\n"
                              "11  7\n")))))

Terlalu malas untuk ungolf itu tetapi pada dasarnya for[m(range 30)]mengunjungi setiap indeks dan untuk setiap indeks bagian dalam let[n(for[p[-1 -6 1 6]...(+ m p))]membuat daftar elemen 0 sampai 4 yang daftar lokasi yang memiliki nilai yang sama (1 - 9) sebagai lokasi tengah. Jika lebih dari 1 tetangga cocok dengan bagian tengah itu berarti bahwa semua ini membentuk sebuah cluster, sehingga lokasi tersebut ditambahkan ke set yang digunakan di (if((set(flatten(...)))i). Jika indeks iditemukan dari himpunan maka \xdipancarkan dan nilai aslinya sebaliknya. Itu :when( ... )cukup menarik ...

NikoNyrh
sumber