Solusi optimal untuk pergi ke sudut yang berlawanan dari persegi panjang

13

Tugas Anda adalah menulis sebuah program yang menemukan jumlah gerakan optimal yang diperlukan untuk mendapatkan dari sudut kiri bawah persegi panjang ke sudut kanan atas yang berseberangan.

Program Anda akan menerima input sebagai pasangan yang dipesan (width, height). Ini akan menjadi dimensi persegi panjang yang akan Anda kerjakan. Program Anda akan membuat ASCII-art dari solusi (gunakan .untuk kotak kosong dan #untuk bagian dari solusi, Xuntuk memulai kotak) dan menghitung jumlah gerakan yang diperlukan untuk mencapai titik akhir. Pergerakan diagonal tidak diizinkan. Jika ada beberapa solusi, pilih satu untuk di-output.

Program terpendek dalam byte menang.

Contoh

Memasukkan: (4, 5)

Keluaran:

..##
..#.
.##.
.#..
X#..

Pindahkan hitungan: 7

ericw31415
sumber
Jadi haruskah output mengandung jumlah #"solusi optimal" (yang merupakan solusi yang tidak pernah bergerak ke kiri atau ke bawah) juga?
Martin Ender
12
"Maaf, ini pertanyaan golf-kode pertamaku jadi aku tidak pandai membuat ini." Izinkan saya merekomendasikan kotak pasir tempat Anda dapat memposting ide tantangan dan menerima umpan balik sebelum mempostingnya di utama. Dan selamat datang di PPCG! :)
Martin Ender
@ MartinBüttner Ya, jumlah langkah pada dasarnya adalah jumlah #karena tidak masuk akal untuk pergi ke kiri atau ke bawah.
ericw31415
Apakah boleh memisahkan masing-masing karakter dengan spasi?
Biru
1
Apakah kita harus menampilkan hitungan langkah DAN seni ascii? Bagaimana seharusnya seharusnya bentuk outputnya?
James

Jawaban:

0

05AB1E , 27 24 byte

Kode:

+Í,¹<'.×'#¶J²<×'X'#¹<×J,

Penjelasan:

+                         # Add the length and the height.
 Í                        # Decrease by two.
  ,                       # Print this value with a newline.
   ¹<'.×                  # Take the first input, decrease by 1 and multiply with ".".
        '#¶               # Push a "#"-character and a newline character.
           J              # Join the string.
            ²<            # Take the second input and decrease by 1.
              ×           # Multiply the joined string with this value.
               'X         # Push the "X"-character.
                 '#¹<×J   # Multiply the "#"-character with (first input - 1).
                       ,  # Pop and print with a newline.

Cobalah online! . Menggunakan pengodean CP-1252 .

Adnan
sumber
Apa perbedaan antara byte dan karakter?
Leaky Nun
2
@ KennyLau Saya selalu lupa menyebutkan bahwa dalam posting saya ... 05AB1E menggunakan pengkodean CP-1252, setiap karakter yang digunakan dalam kode di sini adalah 1 byte.
Adnan
3

Retina , 54 53 byte

\d+
$*.
S_`(?<=(.+)¶.*).|\D
T`.`#`.¶|.*$
:m-1=`^#
X
#

Mengambil input yang dipisahkan oleh umpan baris dan menampilkan kisi solusi diikuti oleh jumlah langkah.

Cobalah online!

Penjelasan

\d+
$*.

Ubah kedua bilangan bulat menjadi banyak ., yaitu konversikan menjadi unary.

S_`(?<=(.+)¶.*).|\D

Ini membangun kisi .s, dengan mencocokkan masing-masing .di ketinggian unary dan menangkap representasi lebar unary. The Smengaktifkan mode split yang mengembalikan string ditangkap, dan |\Ddan _bersama-sama memastikan bahwa segala sesuatu yang lain dihapus dari string.

T`.`#`.¶|.*$

Ini mengubah karakter terakhir dari setiap baris serta seluruh baris terakhir menjadi #s.

:m-1=`^#
X

Ini menggunakan satu ton opsi untuk mengkonversi hanya yang pertama #di baris terakhir ke X(kita perlu memastikan bahwa hanya baris terakhir yang terpengaruh karena lebar-1 input). mmengaktifkan mode multi-line yang ^cocok dengan awal baris. -1=memberitahu Retina untuk melakukan penggantian hanya pada pertandingan terakhir. Akhirnya, :nonaktifkan mode diam standar sehingga grid dicetak ke STDOUT sebagai hasil antara.

#

Akhirnya, kita cukup menghitung angka #dalam string, yang sesuai dengan jumlah gerakan.

Martin Ender
sumber
Mungkin built-in harus ditambahkan ke retina untuk dikonversi ke unary.
Cyoce
3

Pyke, 26 byte

DtQ+RtF; Q\.*t\#+)\X\#Qt*+

Coba di sini


Atau 34 byte yang tidak kompetitif, tambahkan apply node dengan ast)

jUa]Dm!X|RZjht]q+".#X"R@)Fs
);jmts

Coba di sini!

Atau 30 byte jika spasi diizinkan sebagai bantalan

jUa]Dm!X|RZjht]q+".#X"R@)Pjmts
Biru
sumber
Mengapa ini tidak kompetitif?
Leaky Nun
3
Saya mengubah bahasa setelah tantangan diposting
Biru
@muddyfish Galat server internal saat Anda mengklik coba di sini
Insane
@ Insane memperbaiki bug (semoga) Tes internal untuk waktu gagal setiap kali hari berubah.
Biru
2

Pyth, 32 29 24 byte

AtMQVH+*\.G\#;+\X*\#G+GH

Cobalah online!

Input sampel:

(4, 5)

Output sampel:

...#
...#
...#
...#
X###
7

Bagaimana itu bekerja:

AtMQVH+*\.G\#;+\X*\#G+GH
                           assign('Q',eval_input())
AtMQ                       assign('[G,H]',Pmap(lambda d:tail(d),Q))
    VH       ;             for N in range(H):
      +*\.G\#                  implicit_print(plus(times(".",G),"#"))
              +\X*\#G      implicit_print(plus("X",times("#",G)))
                     +GH   implicit_print(plus(G,H))

Upaya sebelumnya:

JthQK@Q1+*++*\.J\#btK+\X*\#Jt+JK

Cobalah online!

Input sampel:

(4, 5)

Output sampel:

...#
...#
...#
...#
X###
7

Bagaimana itu bekerja:

JthQK@Q1+*++*\.J\#btK+\X*\#Jt+JK
                                 assign('Q',eval_input())        --Q is now an official pair of numbers (4, 5)
JthQ                             assign("J",decrement(first(Q))) --gets the first element, and then take 1 from it, and assign it to J
    K@Q1                         assign("K",lookup(Q,1))         --K is now the second element (count from 0) of the pair.
        +            +\X*\#J     concat(-----------------------------------------------------------,concat("X",times("#",J)))
         *         tK                   repeat(--------------------------------------,decrement(K))
          +       b                            concat(-------------------------,"\n")
           +    \#                                    concat(-------------,"#")
            *\.J                                             repeat(".",J)
                            t+JK decrement(add(J,K)) <--- auto-print
Biarawati Bocor
sumber
@ MartinBüttner Mungkin Anda bisa membantu saya bermain golf ini?
Leaky Nun
@ KennyLau Saya tidak tahu Pyth ...
Martin Ender
@ MartinBüttner Cukup memalukan bagi Pyth untuk dikalahkan, kan
Leaky Nun
Anda dapat menggabungkan dua tugas pertama dengan AtMQ. Ini menetapkan dua nilai ke Gdan H.
Jakube
1

CJam, 35 33 byte

q~\(_2$(+p'.*a*'#f+)W%_"X#"era+N*

Mengambil input dalam bentuk width heightdan menampilkan jumlah langkah pada baris pertama, diikuti oleh kisi solusi.

Uji di sini.

Ini juga berfungsi untuk jumlah byte yang sama:

q~\('.*a*'#f+)W%_"X#"era+N*_'#e=p
Martin Ender
sumber
Belum melihat solusi CJam dalam beberapa saat.
Cyoce
2
@Cyoce Anda harus terlihat lebih keras. ;)
Martin Ender
1

Ruby, 48 byte

Ini adalah fungsi anonim, yang menurut meta post ini dapat diterima kecuali pertanyaannya menyatakan "program lengkap." Saya biasanya tidak terlalu jago tentang hal ini tetapi masalahnya sangat sederhana dan melakukan suatu program akan meningkatkan% skor secara signifikan.

Input adalah dua argumen. Nilai kembali adalah array yang berisi string seni ASCII dan jumlah #dalam path.

->w,h{[(?.*(w-=1)+'#
')*(h-=1)+?X+?#*w,w+h]}

Dalam program uji

f=->w,h{[(?.*(w-=1)+'#
')*(h-=1)+?X+?#*w,w+h]}

puts f[4,5]

Keluaran

...#
...#
...#
...#
X###
7

Itu hanya serangkaian h-1 baris w-1 dots, diikuti oleh a #dan baris baru. Saya meletakkannya #di bagian akhir untuk menggunakan satu #\nliteral untuk keduanya #dan baris baru (kode tersebut berisi baris baru yang sebenarnya dan bukan urutan keluar.) Baris terakhir kemudian Xdiikuti oleh w-1 #.

Itu lebih pendek untuk mengurangi nilai-nilai w dan h selama generasi seni ASCII, sehingga perhitungan akhir sederhana w+h.

Level River St
sumber
1

JavaScript (ES6), 60 byte

w=>h=>--w+--h+`
${"."[r="repeat"](w)}#`[r](h)+`
X`+"#"[r](w)

Pemakaian

f(4)(5)

7
...#
...#
...#
...#
X###
pengguna81655
sumber
1

MATL , 28 26 25 byte

+qq35IMwX"46 5Lt4$(88HG(c

EDIT (10 Juni 2016): tautan di bawah ini mencakup modifikasi ( 5Ldigantikan oleh IL) untuk beradaptasi dengan perubahan dalam bahasa

Cobalah online!

Penjelasan

+       % take two inputs. Add them
qq      % subtract 2
35      % push ASCII for '#'
IMw     % push the two inputs again. Swap them
X"      % 2D char array of '#'  repeated as indicated by inputs
46      % push ASCII for '.'
5Lt4$(  % fill all but last and row columns with that
88HG(   % fill 88 (ASCII for 'X') at linear index given by second input
c       % convert to char
Luis Mendo
sumber
0

Scala, 118 byte

(w:Int,h:Int)=>{print(Array.fill(h-1,w-1)('.')map(new String(_))mkString("","#\n","#\nX"));Seq.fill(w-1)(print("#"))}


(w:Int,h:Int)=>{...}           //define a function with 2 Ints as parameters
print(                        //print ...   
  Array.fill(h-1,w-1)('.')    //an array of arrays with dimensions (h-1,w-1)
                              //and fill it with a dot
  map(new String(_))          //map each inner array of chars to a string
  mkString("","#\n","#\nX")   //create a string from the array, with
                              //an empty string before the array,
                              //"#\n" as a seperator between the elements
                              //and "#\nX" at the end   
);
Seq.fill(w-1)(print("#"))     //w-1 times print "#"
corvus_192
sumber
0

Haskell, 64 byte

c!n=c<$[2..n]
w#h=unlines$('.'!w++"#")!h++['X':'#'!w,show$w+h-2]

Contoh penggunaan:

*Main> putStr $ 4 # 5
...#
...#
...#
...#
X###
7

Bagaimana itu bekerja:

c!n = c <$ [2..n]                       -- helper function: make (n-1) copies of c

                                        -- main function
                     !h                 -- (h-1) times
       ('.'!w ++ "#")                   --    (w-1) dots and a hash sign
                       ++[      ,     ] -- followed by
                          'X' : '#'!w   --    an 'X' and (w-1) hash signs
                            show$w+h-2  --    and the number of steps
unlines                                 -- join everything with newlines in-between
nimi
sumber
0

Java, 137 132 byte

w->h->{String s="";int i=0,j;for(;i<h;i++){for(j=1;j<w;j++)s+=".";s+="#\n";}s+="X";for(j=1;j<w;j++)s+=".";s+="\n"+(w+h-2);return s;}
Biarawati Bocor
sumber
Jawa bukan lelucon persis ...
ericw31415
s + = bukannya s = s + akan menghemat beberapa byte
Biru
0

Lua, 81 byte

Cobalah online!

Golf:

w,h=(...)print((("."):rep(w-1).."#\n"):rep(h-1).."X"..("#"):rep(w-1))print(w+h-2)

Tidak Disatukan:

w,h=4,5
print((("."):rep(w-1).."#\n"):rep(h-1).."X"..("#"):rep(w-1))
print(w+h-2)
Biarawati Bocor
sumber
0

Python, 48.

lambda w,h:('.'*(w-1)+'#\n')*(h-1)+'X'+'#'*(w-1)

Untuk menggunakannya, tambahkan f=sebelum baris di atas dan panggil seperti ini:

f(4, 5)

Hasil:

...#
...#
...#
...#
X###
shooqie
sumber