Bisakah Anda menghitung jumlah persegi panjang?

21

Salah satu hiburan matematika favorit saya adalah menggambar kotak persegi panjang, kemudian menemukan semua persegi panjang yang terlihat di kotak itu. Di sini, ambil pertanyaan ini, dan usahakan sendiri!

Bisakah Anda menghitung jumlah persegi panjang?

+-----+-----+-----+-----+
|     |     |     |     |
|     |     |     |     |
+-----+-----+-----+-----+
|     |     |     |     |
|     |     |     |     |
+-----+-----+-----+-----+
|     |     |     |     |
|     |     |     |     |
+-----+-----+-----+-----+
|     |     |     |     |
|     |     |     |     |
+-----+-----+-----+-----+

Jumlah total persegi panjang untuk ini 4 x 4 papan minichess persis

100

Apakah Anda benar?

Matematika terkait: Berapa banyak persegi panjang yang ada pada kotak-kotak 8 × 8?

Tantangan

Tulis fungsi / program terpendek yang menghitung jumlah persegi panjang yang terlihat pada kisi / gambar non-toroidal .

Tantangan terkait: Hitung Persegi Panjang Unik! , Temukan jumlah persegi panjang dalam array byte 2D .

Masukkan format

Fungsi atau program Anda dapat memilih untuk bekerja dengan input berbasis teks atau input grafis.

Input berbasis teks

Kisi-kisi akan berupa kisi ASCII m -by- n ( m rows, n kolom) yang terdiri dari karakter berikut:

  • ruang,
  • - untuk bagian segmen garis horizontal,
  • | untuk bagian segmen garis vertikal, dan
  • + untuk sudut.

Anda dapat memperkenalkan kisi ASCII ini sebagai input / argumen ke program / fungsi Anda dalam bentuk

  • string tunggal dibatasi oleh jeda baris,
  • string tanpa baris baru tetapi dengan satu atau dua bilangan bulat yang mengkode dimensi grid, atau
  • berbagai string.

Catatan: Input berbasis teks mengandung setidaknya 1 baris dan setidaknya 1 kolom.

Input Grafis

Atau, kisi-kisi dikodekan sebagai gambar PNG hitam-putih dengan lebar 5 * n piksel dan tinggi 5 * m piksel. Setiap gambar terdiri dari 5 px * 5 px blok yang sesuai dengan input ASCII dengan:

  • Spasi dikonversi menjadi blok putih. Blok-blok ini disebut blok spasi .
  • Segmen dan sudut garis dikonversi ke blok non- putih. Pixel tengah blok semacam itu berwarna hitam.
  • Sunting: Jika dua sudut (dalam input ASCII) dihubungkan oleh segmen garis, pusat blok yang sesuai (dalam input grafis) juga harus dihubungkan oleh garis hitam.

Ini berarti bahwa setiap blok hanya dapat dipilih Harap abaikan batas biru. (Klik di sini untuk gambar yang lebih besar) .

Catatan: Batas biru hanya untuk tujuan ilustrasi. Input grafis minimal 5 px lebar dan 5 px tinggi. Anda dapat mengonversi input grafis ke gambar monokrom apa pun, yang berpotensi berupa format file gambar lainnya). Jika Anda memilih untuk mengonversi, sebutkan dalam jawabannya. Tidak ada penalti untuk konversi.

Format output

Jika Anda menulis sebuah program, program tersebut harus menampilkan angka non-negatif yang menunjukkan jumlah total persegi panjang dalam input.

Jika Anda menulis fungsi, itu juga harus mengembalikan angka non-negatif yang menunjukkan jumlah persegi panjang dalam input.

Contoh Kasus

Kasus 1, Grafik: Kasus 1( 30 px * 30 px), ASCII: ( 6 baris, 6 cols)

+--+  
|  |  
| ++-+
+-++ |
  |  |
  +--+

Output yang diharapkan: 3

Kasus 2, Grafik: Kasus 2( 20 px * 20 px), ASCII: ( 4 baris, 4 cols)

++-+
|+++
+++|
+-++

Output yang diharapkan: 6

Kasus 3, Grafik: Kasus 3( 55 px * 40 px), ASCII: ( 8 baris, 11 cols)

  +++--+   
+-+++  |   
|  |  ++--+
+--+--++ ++
      |  ||
      |  ||
++    +--++
++         

Output yang diharapkan: 9

Kasus 4, Grafik: Kasus 4( 120 px * 65 px), ASCII: ( 13 baris, 24 cols)

+--+--+ +--+  +--+  +--+
|  |  | |  |  |  |  |  |
+--+--+ |  |  |  |  |  |
|  |  | +--+--+--+--+--+
+--+--+    |  |  |  |   
           |  |  |  | ++
+-+-+-+-+  +--+  +--+ ++
| | | | |
+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+

Output yang diharapkan: 243

Kasus 5, Graphic: Kasus 5( 5 px * 5 . Px Ya, itu adalah di sana!), ASCII: Hanya satu ruang.

Output yang diharapkan: 0

Kasus 6, Grafik: Kasus 6( 35 px * 20 px), ASCII: ( 4 baris, 7 cols)

+--+--+
|++|++|
|++|++|
+--+--+

Output yang diharapkan: 5

Asumsi

Untuk membuat hidup lebih mudah, Anda dijamin bahwa:

  • Dengan menjadi non-toroidal , kisi tidak membungkus secara horizontal atau vertikal.
  • Tidak ada ujung yang longgar, misalnya +--- atau +- -+. Semua segmen garis memiliki dua ujung.
  • Dua garis yang bertemu +harus berpotongan satu sama lain pada saat itu.
  • Anda tidak perlu khawatir tentang input yang tidak valid.

Aturan terhadap celah standar berlaku. Harap perlakukan kotak sebagai persegi panjang. Secara opsional, Anda bisa menghapus spasi tambahan di setiap baris kisi.

Ini adalah , jadi buat entri Anda sesingkat mungkin. Solusi berbasis teks dan grafis akan bersaing bersama.

Papan peringkat

Frenzy Li
sumber
Apakah bitmap monokrom diizinkan?
user202729
@ user202729 Ya. Jika Anda memilih untuk bekerja dengan gambar non-PNG, sebutkan dalam jawaban.
Frenzy Li
Apakah ini input yang valid? (Sudut persegi panjang menyentuh batas persegi panjang yang lebih besar.) Jika demikian, pertimbangkan untuk menambahkannya sebagai kotak uji.
Zgarb
@ Zgarb Ini adalah input yang valid. Saya akan mengedit posting juga.
Frenzy Li
Apakah ada alasan Anda menempatkan output yang diharapkan dalam spoiler? Sepertinya hanya membuat verifikasi kode Anda sedikit lebih menjengkelkan.
FryAmTheEggman

Jawaban:

4

Grime , 31 28 byte

T=\+[+\-]*\+/[+|]/+$
n`T&To2

Cobalah online!

Mengambil input dalam format ASCII.

Penjelasan

Sintaksis Grime sangat dekat dengan ekspresi reguler. Setiap baris mendefinisikan pola yang mungkin cocok atau tidak cocok dengan persegi panjang karakter. Tcocok dengan persegi panjang yang baris atas dan kolom kiri terlihat valid.

T=\+[+\-]*\+/[+|]/+$
T=                    Define T as
  \+[+\-]*\+          a row that matches this regex
            /         and below that
             [+|]/+   a column of + or |
                   $  with anything to its right.

Baris kedua adalah "program utama".

n`T&To2
n`       Print number of rectangles that match
  T      the pattern T
   &     and
    To2  T rotated 180 degrees.
Zgarb
sumber
6

JavaScript (ES6), 176 171 byte

g=a=>Math.max(...b=a.map(a=>a.length))-Math.min(...b)?``:f(a);f=
a=>a.map((b,i)=>[...b].map((_,j)=>n+=a.join`
`.split(eval(`/\\+(?=[-+]{${j}}\\+[^]{${l=b.length+~j}}([|+].{${j}}[|+][^]{${l}}){${i}}\\+[-+]{${j}}\\+)/`)).length>>1),n=0)|n
<textarea rows=8 cols=8 oninput=o.textContent=g(this.value.split`\n`)></textarea><pre id=o>

Mengambil input sebagai array string dengan panjang yang sama. Penjelasan: Membuat serangkaian ekspresi reguler yang cocok dengan persegi panjang dari semua lebar dan tinggi yang mungkin (dan beberapa lebar dan tinggi yang tidak mungkin, tapi itulah kode golf untuk Anda) dan menghitung berapa banyak pertandingan yang mereka hasilkan. Karena ada grup penangkap di regexp, splitpengembalian 2n+1untukn pertandingan, jadi saya benar menggeser dengan 1 untuk mendapatkan jumlah pertandingan, karena itu menghemat satu byte lebih dari membuat grup tidak menangkap.

Neil
sumber
Hmm, cuplikan kode tidak berfungsi untuk saya [Firefox 54.0.1 (32bit) atau Chrome 60.0.3112.90 (64bit) keduanya di Windows (64bit)].
Jonathan Allan
Cuplikan Ini tidak berfungsi di Safari [Mac (64bit)].
Tn. Xcoder
2
Tampaknya kita harus menempelkan hal-hal ke dalam area teks. Jumlah karakter per baris yang sama diperlukan.
Frenzy Li
Ah, begitu, tempat bagus @FrenzyLi!
Jonathan Allan
4

J , 103 95 86 80 76 70 byte

[:+/@,]*/@('-|++'*/@(e.,&'+')~&>]({.,{:)&.>@;|:;{.;{:);._3"$~2+$#:i.@$

Cobalah online!

Mengambil input sebagai array string dengan spasi tambahan (sehingga setiap string memiliki ukuran yang sama). Menggunakan operator subarray penuh;._3 untuk beralih di setiap ukuran subarray yang mungkin lebih besar dari 2 x 2, dan menghitung subarrays yang merupakan persegi panjang yang valid. Menyelesaikan semua test case hampir secara instan.

mil
sumber
1
@FrenzyLi Terima kasih. Fungsi menerima input sebagai larik string, tetapi saya menyandikan setiap larik sebagai string datar yang dibentuk kembali menjadi larik sebelum saya menyimpannya di setiap variabel untuk digunakan sebagai argumen untuk fungsi tersebut.
mil
Ahh ... Terima kasih atas penjelasannya.
Frenzy Li
@miles bagus. ketika Anda mengatakan input sebagai array string, apakah setiap baris input 1 menyengat?
Jonah
@Jonah Strings di J hanyalah array dari chars, jadi inputnya sebenarnya adalah array 2d chars.
mil
3

Mathematica, 136 134 132 byte

S=Tr@*Flatten;S@Table[1-Sign@S@{d[[{i,j},k;;l]],d[[i;;j,{k,l}]]},{i,($=Length)[d=ImageData@#]},{j,i+1,$@d},{k,w=$@#&@@d},{l,k+1,w}]&

Penggunaan: (untuk versi 136-byte yang lama, tetapi versi yang baru pada dasarnya identik)

_

catatan:

  • Ini berjalan dalam waktu O (m 2 n 2 maks (m, n)), jadi hanya gunakan input kecil.
  • Meskipun ini seharusnya bekerja dengan gambar biner, ternyata bisa bekerja dengan gambar non-biner. (tetapi hitam harus identik nol)
  • Grafik tidak harus dibangun dengan blok 5x5, blok bisa lebih kecil.
  • @*baru dalam versi 10. Dalam versi yang lebih lama, gunakan Tr~Composition~Flattensebagai ganti Tr@*Flatten.
pengguna202729
sumber
Versi MMA mana ini? Di 9.0, ia merespons dengan"Tr@" cannot be followed by "*Flatten".
Frenzy Li
1
@FrenzyLi 10.0. Ya, @*(singkatan untuk Composition) adalah baru dalam versi 10.
user202729
1
Kenapa kamu tidak pakai saja RectangleCount[]?
MCMastery
2
@MCMastery Mathematica terkenal memiliki banyak built-in, tetapi tidak yang satu ini.
user202729
@ user202729 lol ya, im jk
MCMastery
2

Jelly ,  60 53 52 51  50 byte

ÑFQe⁹ṚẆ;W¤
Ḣ,Ṫ
=”+ÇÇ€Ạȧ1ŀ
Zç⁾+-ȧç⁾+|$
Ẇ;"/€Ẇ€Ç€€FS

Program lengkap yang menerima daftar string (baris dengan panjang yang sama) dan mencetak hitungan.

Cobalah online!
... atau untuk kemudahan copy & paste penggunaan input ini program penuh (dengan byte tambahan untuk garis split)
- perhatikan garis yang diperlukan untuk mengandung spasi tambahan untuk program untuk berfungsi dengan benar sekalipun.

Bagaimana?

ÑFQe⁹ṚẆ;W¤   - Link 1, sidesAreValid?: list of lists, area; list allowedSideCharacters
Ñ            - call the next link (2) as a monad (get the sides in question
             -   note: these sides do not include the corners since the area was modified
             -   to not include the other sides by the first call to link 2 inside link 3.
 F           - flatten into a single list
  Q          - de-duplicate (unique characters)
         ¤   - nilad followed by link(s) as a nilad:
    ⁹        -   right argument (either "+-"                or "+|"               )
     Ṛ       -   reverse        (either "-+"                or "|+"               )
      Ẇ      -   all sublists   (either ["-","+","-+"]      or ["|","+","|+"]     )
        W    -   wrap           (either ["+-"]              or ["+|"]             )
       ;     -   concatenate    (either ["-","+","-+","+-"] or ["|","+","|+","+|"])
   e         - exists in?

Ḣ,Ṫ          - Link 2, topAndTail helper: list
Ḣ            - head (get the first element and modify the list)
  Ṫ          - tail (get the last element and modify the list)
 ,           - pair (the elements together)

=”+ÇÇ€Ạȧ1ŀ   - Link 3, isPartlyValid?: list of lists, area; list allowedSideCharacters
=”+          - equal to '+'? (vectorises across the whole area, 1 if so, 0 otherwise)
   Ç         - call the last link (2) as a monad (gets the values for two edges)
    Ç€       - call the last link (2) as a monad for €ach (...values for the four corners)
      Ạ      - all? (all corners are '+' 1 if so, 0 if not)
        1ŀ   - call link number 1 as a dyad with sideCharacters as the right argument
             -    ...and the modified area on the left
       ȧ     - logical and (both all corners are '+' and the sides in question look right)

Zç⁾+-ȧç⁾+|$  - Link 4, isValidSquare?: list of lists, area
Z            - transpose
 ç⁾+-        - call the last link (3) as a dyad with right argument "+-"
          $  - last two links as a monad:
      ç⁾+|   -   call the last link (3) as a dyad with right argument "+|"
     ȧ       - logical and (1 if so 0 otherwise)

Ẇ;"/€Ẇ€Ç€€FS - Main Link: list of lists of characters, rows
Ẇ            - all sublists (= all non-zero length runs of rows)
   /€        - reduce €ach by:
  "          -   zip with:
 ;           -     concatenation (= all non-zero length vertical edges)
     Ẇ€      - all sublists for €ach (= all possible areas)
       Ç€€   - call the last link (4) as a monad for €ach for €ach (for each area)
          F  - flatten
           S - sum
Jonathan Allan
sumber
2

Tergelincir , 32 29 byte

$a([+`-]*`+>[+`|]*`+>){2}$A

Cobalah online!

27 byte kode + 2 byte untuk ndan oflag. Mengambil input dalam format yang sama dengan yang disediakan dalam pertanyaan (yaitu blok baris yang dibatasi baris baru).

notjagan
sumber
2

Haskell, 180 167 166 byte

l=length
a%b=[a..b-1]
h c a g b=all(`elem`c)$g<$>[a..b]
f s|(#)<-(!!).(s!!)=sum[1|y<-1%l s,x<-1%l(s!!0),i<-0%y,j<-0%x,h"+|"i(#x)y,h"+-"j(y#)x,h"+|"i(#j)y,h"+-"j(i#)x]

Cobalah online!

Pergi melalui semua posisi sudut yang mungkin dengan empat loop bersarang dan periksa apakah semua karakter pada garis di antara mereka terdiri dari +-(horizontal) atau +|(vertikal).

nimi
sumber
1

Jelly , 41 39 34 33 byte

,Z;.ị$⁺€ḟ€"⁾-|Fḟ”+
ẆḊÐfZ€µ⁺€ẎÇÐḟL

Cobalah online! atau Lihat semua case.

Berdasarkan jawaban saya di J.

Penjelasan

,Z;.ị$⁺€ḟ€"⁾-|Fḟ”+  Helper. Input: 2d array of characters
 Z                  Transpose
,                   Pair
  ;                   Concatenate with
     $                The tail and head
   .ị                   Select at index 0.5 -> Select at index 0 and 1
                        Jelly uses 1-based modular indexing, so
                        0 means to select the tail
      ⁺€              Repeat on each - This selects the last and first rows,
                      last and first columns, and the 4 corners
           ⁾-|       The string array ['-', '|']
          "          Vectorize
        ḟ€             Filter each
              F      Flatten
                ”+   The character '+'
               ḟ

ẆḊÐfZ€µ⁺€ẎÇÐḟL  Main. Input: 2d array of characters
      µ         Combine into a monad
Ẇ                 Generate all sublists
  Ðf              Filter for the values that are truthy (non-empty)
 Ḋ                  Dequeue
    Z€            Transpose each
       ⁺€       Repeat on each
         Ẏ      Tighten, join all lists on the next depth
          ÇÐḟ   Discard the values where executing the helper returns truthy
             L  Length
mil
sumber
Sekarang akhirnya mulai merasa pendek kompetitif pada 34 byte.
mil