Temukan rentang nilai True dalam daftar

26

Tantangan:

Tulis fungsi atau program yang menerima daftar nilai boolean dan kembalikan semua rentang True.

Kasus uji:

f [F]                               = []
f [T]                               = [[0,0]]
f [T,T,F,T]                         = [[0,1],[3,3]]
f [F,T,T,F,F,T,T,T]                 = [[1,2],[5,7]]
f [F,T,T,F,F,F,T,T,T,T]             = [[1,2],[6,9]]
f [T,T,F,F,F,T,T,T,T,T,T,T,T,T,T,F] = [[0,1],[5,14]]
f [F,F,T,T,F,F,F,F,F,F,F,F,T,T,T,T,T,T,T,T,F,F,F,F,F,F,F,F,F,F,F,F,F,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,T,T] = [[2,3],[12,19],[33,54],[93,94]]

Aturan:

  • Anda dapat memilih bagaimana input dikodekan, misalnya daftar, array, string, dll.
  • Keluaran harus dikodekan sebagai suka-suka daftar-suka atau string yang menunjukkan seperti itu, jadi array, daftar, tupel, matriks, vektor, dll.
  • Nilai boolean harus dikodekan sebagai konstanta, tetapi jika tidak konversi sederhana T / F ke konstanta yang diinginkan diperbolehkan
  • EDIT: eval atau serupa selama runtime IS diizinkan.
  • Jangan lupa untuk menjelaskan bagaimana input diteruskan ke program / fungsi dan berikan input / output untuk kasus uji
  • Konversi ke format input yang diinginkan tidak dihitung
  • Celah standar tidak diijinkan
  • Jika bahasa Anda memiliki fungsi untuk melakukan ini, itu tidak diizinkan
  • Saya tidak akan menerima kiriman saya sendiri
  • EDIT: Format output fleksibel. Jika tidak mencetak daftar atau serupa, nilai rentang harus dipisahkan oleh satu karakter non-numerik dan rentang terpisah juga.

Mencetak:

  • Skor dalam byte, kecuali tidak sesuai dengan bahasa Anda (seperti codels di Piet)
  • Skor terendah menang

Ada sedikit fleksibilitas dalam input dan output, tetapi solusi di mana T / F diganti dengan fungsi yang melakukan semua pekerjaan tidak diizinkan.

Debugging:

Jika Anda menulis milik Anda di Haskell atau dapat memanggilnya dari Haskell, berikut ini akan memeriksa fungsi / program Anda:

import Test.QuickCheck

tf = cycle [True,False]
gen l = foldl (++) [] $ map (\i -> [tf!!i | x<-[1..i]]) l
putIn (a,b) l = zipWith (||) l [(a <= p) && (p <= b) | p <- [0..length l]]
putAllIn rs len = foldr putIn [False|i<-[1..len]] rs
main = print $ quickCheck (check functionNameGoesHere)
Michael Klein
sumber
1
Saya mungkin melewatkan sesuatu, tetapi saya tidak melihat deskripsi tentang bagaimana kisaran diwakili dalam output.
Peter Taylor
1
Bisakah output diindeks 1?
LegionMammal978
Bisakah rentang menjadi setengah eksklusif?
lirtosiast
1
@ LegionMammal978 Hanya jika bahasa default Anda adalah 1-diindeks, misalnya Mathematica
Michael Klein
@ThomasKwa Tidak, yang tampaknya terlalu berbeda untuk kasus "tepi"
Michael Klein

Jawaban:

7

Pyth, 17 16 byte

fT.b*Y,~+ZNtZrQ8

Menggunakan beberapa sihir penghitung post-assign yang mewah bersama dengan enkode run run.

Mengambil input sebagai array 0s dan 1s, mis [1, 1, 0, 1, 0]. Output seperti dalam tantangan, mis [[0, 1], [3, 3]].

Test Suite

orlp
sumber
Saya menambahkan test suite. Jika hasil edit disetujui dan tidak ada yang masuk, Anda memiliki jawaban yang paling singkat.
Michael Klein
9

Pyth, 18 byte

CxR.:++~Zkz02_B_`T

Suite uji

True diwakili sebagai 1, False as 0.

Kisaran diwakili secara inklusif.

isaacg
sumber
Bisakah Anda menambahkan penjelasan?
lirtosiast
Tentu, kapan saja.
isaacg
7

Retina , 82 34 27 byte

\b(?<=(.)*_?)
$#1
_+

S_`:

Baris kosong harus berisi satu spasi.

Input adalah string flat _untuk true dan :false. Output adalah pasangan yang dipisahkan oleh ruang, masing-masing pada garis yang terpisah.

Cobalah online.

Penjelasan

Golf berat dari 82 ke 27 byte dimungkinkan oleh pilihan cerdas representasi benar dan salah. Saya telah memilih karakter kata,_ ,, (yang bukan digit) untuk karakter true dan non-word :,, (yang tidak perlu keluar) untuk false. Itu memungkinkan saya mendeteksi ujung rentang sebagai batas kata.

\b(?<=(.)*_?)
$#1

Kami mencocokkan batas kata. Kami ingin mengganti batas itu dengan indeks nilai kebenaran yang sesuai. Pada prinsipnya itu cukup mudah dengan $#fitur terbaru Retina , yang menghitung jumlah tangkapan suatu kelompok. Kami cukup menangkap setiap karakter di depan posisi itu menjadi grup. Dengan menghitung karakter-karakter itu kita mendapatkan posisi. Satu-satunya tangkapan adalah bahwa ujung kisaran mati oleh satu sekarang. Kami sebenarnya ingin indeks karakter di depan pertandingan. Itu juga mudah diperbaiki dengan mencocokkan opsional _yang tidak ditangkap, sehingga melewatkan satu karakter ketika kita berada di akhir rentang.

_+
<space>

Sekarang kami mengganti semua proses garis bawah dengan spasi. Artinya, kami menyisipkan ruang antara awal dan akhir setiap rentang, sambil menyingkirkan garis bawah.

S_`:

Itu meninggalkan titik dua (dan kita masih harus memisahkan pasangan). Kami melakukannya dengan memisahkan seluruh string menjadi garis-garis di sekitar setiap titik dua. The Saktif modus membagi, dan _Menekan segmen yang kosong sehingga tidak mendapatkan ton baris kosong ketika kita memiliki berjalan dari titik dua.

Martin Ender
sumber
5

Python 2, 69 byte

p=i=0
for x in input()+[0]:
 if x-p:b=x<p;print`i-b`+';'*b,
 p=x;i+=1

Contoh output:

2 3; 7 16; 18 18;

Pendekatan langsung, tanpa built-in. Melacak nilai saat ini xdan nilai sebelumnya p. Ketika ini berbeda, kami telah beralih menjalankan. Saat beralih 0ke 1, mencetak indeks saat ini i. Saat beralih1 ke 0, mencetak indeks saat ini minus satu diikuti dengan tanda titik koma.

Sangat ifbau. Mungkin rekursi akan lebih baik,

Tidak
sumber
5

MATL , 17 18 20 byte

j'T+'1X32X34$2#XX

Menggunakan versi saat ini (9.1.0) dari bahasa / kompiler.

Input adalah string yang berisi karakter Tdan F. Output adalah tabel dua baris, di mana setiap kolom menunjukkan rentang menggunakan 1-indeks, yang merupakan bahasa default.

Terima kasih kepada Stewie Griffin karena menghapus 2 byte.

Contoh

>> matl
 > j'T+'1X32X34$2#XX
 >
> FTTFFFTTTT
2 7
3 10

Penjelasan

Ini didasarkan pada ekspresi reguler yang sederhana:

j         % input string
'T+'      % regular expression: match one or more `T` in a row
1X3       % predefined string literal: 'start'
2X3       % predefined string literal: 'end'
4$2#XX    % regexp with 4 inputs (all the above) and 2 outputs (start and end indices)
          % implicitly display start and end indices
Luis Mendo
sumber
4

Oktaf, 43 Bytes

@(x)reshape(find(diff([0,x,0])),2,[])-[1;2]

find(diff([0,x,0]))menemukan semua posisi di mana array input berubah antara true dan false. Dengan membentuk kembali ini menjadi matriks 2-oleh-n kita mencapai dua hal: Perubahan dari benar ke salah, dan dari salah ke benar dibagi menjadi dua baris. Ini memungkinkan untuk mengurangi 1 dan 2 dari masing-masing baris tersebut. Mengurangkan 1 dari baris satu diperlukan karena Oktaf diindeks 1, bukan diindeks nol. Mengurangkan 2 dari baris dua diperlukan karena find(diff())menemukan posisi nilai salah pertama, sementara kita menginginkan nilai sebenarnya terakhir. Bagian pengurangan hanya mungkin dalam Oktaf, tidak dalam MATLAB.

F=0;T=1;
x=[F,F,T,T,F,F,F,F,F,F,F,F,T,T,T,T,T,T,T,T,F,F,F,F,F,F,F,F,F,F,F,F,F,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,T,T]

reshape(find(diff([0,x,0])),2,[])-[1;2]
ans =    
    2   12   33   93
    3   19   54   94

x=[T,T,F,F,F,T,T,T,T,T,T,T,T,T,T,F]
reshape(find(diff([0,x,0])),2,[])-[1;2]
ans =    
    0    5
    1   14
Stewie Griffin
sumber
1
Penggunaan penyiaran yang bagus!
Luis Mendo
4

CJam, 27 25 byte

0qe`{~~{+}{1$+:X(]pX}?}/;

Mengharapkan input seperti TTFTFT. Cobalah online .

Penjelasan

0                               Push 0, to kick off index
qe`                             Push input and run length encode
                                e.g. FFFFTTTFT -> [[4 'F] [3 'T] [1 'F] [1 'T]]
{                 }/            For each pair in the RLE...
 ~                                Unwrap the pair
  ~                               Evaluate T -> 0 (falsy), F -> 15 (truthy)
   { }{         }?                 Ternary based on T/F
    +                                If 'F: add count to index
       1$+:X(]pX                     If 'T: output inclusive range, updating index
;                               Discard the remaining index at the top of the stack
Sp3000
sumber
4

Japt, 34 31 25 byte

Mencoba pendekatan baru benar-benar berhasil kali ini.

V=[]Ur"T+"@Vp[YY-1+Xl]};V

Cobalah online!

Input adalah string dengan Funtuk falsedan Tuntuk true. Output adalah array array; representasi string membuatnya terlihat seperti array tunggal.

Bagaimana itu bekerja

          // Implicit: U = input string
V=[]      // Set V to an empty array. (Why don't I have a variable pre-defined to this? :P)
Ur"T+"    // Take each group of one or more "T"s in the input,
@         // and map each matched string X and its index Y to:
Vp[       //  Push the following to an array in V:
Y         //   Y,
Y-1+Xl    //   Y - 1 + X.length.
]};       //  This pushes the inclusive start and end of the string to V.
V         // Implicit: output last expression

Catatan: Saya sekarang melihat bahwa beberapa orang telah menemukan algoritma ini, tetapi saya menemukannya secara mandiri.

Versi yang tidak bersaing, 22 byte

;Ur"T+"@Ap[YY-1+Xl]};A

Dalam komit GitHub terbaru , saya telah menambahkan fitur baru: seorang pemimpin ;menetapkan variabel A-J,Lke nilai yang berbeda. Adiatur ke array kosong, sehingga menghilangkan kebutuhan untuk membuatnya secara manual.

Produksi ETH
sumber
3

Haskell, 74 byte

import Data.Lists
map(\l->(fst$l!!0,fst$last l)).wordsBy(not.snd).zip[0..]

Contoh penggunaan: map(\l->(fst$l!!0,fst$last l)).wordsBy(not.snd).zip[0..] $ [True,False,True,True,False]-> [(0,0),(2,3)].

Bagaimana itu bekerja:

                               -- example input: [True,False,True,True,False]

zip[0..]                       -- pair each element of the input with it's index
                               -- -> [(0,True),(1,False),(2,True),(3,True),(4,False)]
wordsBy(not.snd)               -- split at "False" values into a list of lists
                               -- -> [[(0,True)],[(2,True),(3,True)]]
map                            -- for every element of this list
   (\l->(fst$l!!0,fst$last l)) -- take the first element of the first pair and the
                               -- first element of the last pair
                               -- -> [(0,0),(2,3)]
nimi
sumber
3

J, 26 byte

[:I.&.|:3(<`[/,]`>/)\0,,&0

Ini adalah kata kerja monadik tanpa nama (fungsi unary) yang mengembalikan array 2D atau bilangan bulat. Ini digunakan sebagai berikut.

  f =: [:I.&.|:3(<`[/,]`>/)\0,,&0
  f 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0
0  1
5 14

Penjelasan

[:I.&.|:3(<`[/,]`>/)\0,,&0
                       ,&0  Append 0 to input
                     0,     then prepend 0.
        3(         )\       For each 3-element sublist (a b c):
               ]`>/           Compute b>c
          <`[/                Compute a<b
              ,               Concatenate them
                            Now we have a 2D array with 1's on left (right) column
                            indicating starts (ends) or 1-runs.
[:I.&.|:                    Transpose, get indices of 1's on each row, transpose back.
Zgarb
sumber
3

Ruby, 39

->s{s.scan(/T+/){p$`.size..s=~/.#$'$/}}

Doa contoh:

2.2.3 :266 > f=->s{s.scan(/T+/){p$`.size..s=~/.#$'$/}}
 => #<Proc:0x007fe8c5b4a2e8@(irb):266 (lambda)> 
2.2.3 :267 > f["TTFTTFTTTFT"]
0..1
3..4
6..8
10..10

The ..adalah bagaimana Ruby mewakili rentang inklusif.

Satu hal yang menarik di sini adalah bagaimana saya mendapatkan indeks akhir kisaran. Itu aneh. Saya secara dinamis membuat ekspresi reguler yang cocok dengan karakter terakhir dari rentang, dan kemudian semua karakter berikutnya dan akhir string untuk memaksa kecocokan yang benar. Lalu saya gunakan =~untuk mendapatkan indeks regex itu di string asli.

Curiga mungkin ada cara yang lebih pendek untuk melakukan ini di Ruby menggunakan flag -naF.

histokrat
sumber
2

JavaScript (ES6), 59

Fungsi anonim, input sebagai string Tdan F, mengembalikan output sebagai array array

x=>x.replace(/T+/g,(a,i)=>o.push([i,a.length+i-1]),o=[])&&o

UJI

f=x=>x.replace(/T+/g,(a,i)=>o.push([i,a.length+i-1]),o=[])&&o

// TEST

arrayOut=a=>`[${a.map(e=>e.map?arrayOut(e):e).join`,`}]`

console.log=x=>O.textContent+=x+'\n'

;[
  'F','T','TTFT','FTTFFTTT','FTTFFFTTTT','TTFFFTTTTTTTTTTF',
  'FFTTFFFFFFFFTTTTTTTTFFFFFFFFFFFFFTTTTTTTTTTTTTTTTTTTTTTFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFTT'
].forEach(t=>console.log(t+'\n'+arrayOut(f(t))+'\n'))
<pre id=O></pre>

edc65
sumber
Wow, saya baru saja datang dengan solusi yang sama di Japt dan akan menerjemahkannya ke JS. Nice one :)
ETHproductions
2

π”Όπ•Šπ•„π•šπ•Ÿ, 18 karakter / 28 byte

Γ―Δ§`T+`,β†ͺα΅–[_,$Ꝉ+‑_]

Try it here (Firefox only).

Penjelasan

Γ―Δ§`T+`,β†ͺα΅–[_,$Ꝉ+‑_] // implicit: Γ―=input
Γ―Δ§`T+`,            // for each T-sequence...
       β†ͺα΅–[_,$Ꝉ+‑_] // push [start index of sequence, end index of sequence] to the stack
                   // implicit stack output
Mama Fun Roll
sumber
2

Haskell, 62 byte

f l|s<-zip3[0..](0:l)$l++[0]=zip[i|(i,0,1)<-s][i-1|(i,1,0)<-s]

Dibawa sebagai input daftar 0 dan 1.

Diberikan daftar l, padukan dengan 0 di kedua sisi dan menghitung daftar pasangan berurut yang diindeks. Sebagai contoh

l = [1,1,0]
s = [(0,0,1),(1,1,1),(2,1,0),(3,0,0)]

Kemudian, ekstrak indeks yang sesuai dengan elemen berturut-turut (0,1)dan (1,0), yang merupakan awal dari blok 0 dan 1, kurangi 1 dari awal 0 untuk mendapatkan ujung 1, dan ritsleting hasilnya.

Tidak
sumber
Wow, itu menekuk sintaks lebih dari yang saya pikir Haskell akan ambil. Apakah ini setara dengan "fl = let s = zip3 [0 ..] (0: l) (l ++ [0]) dalam zip [i | (i, 0,1) <- s] [i-1 | (i , 1,0) <- s] "?
Michael Klein
1
@MichaelKlein Ya, saya belajar tentang cara mengikat penjaga dari nimi di sini . Ini juga setara dengan ikatan-via-lambda yang lebih panjang f l=(\s->zip[i|(i,0,1)<-s][i-1|(i,1,0)<-s])$zip3[0..](0:l)$l++[0].
xnor
2

Pyth, 19 18 byte

m-VdU2cx1aV+ZQ+QZ2

Penjelasan:

             implicit: Q=input
m            map lambda d:
  -V         Vectorized subtraction by [0,1]
     d
     U2     
c            split every 2 elements
  x            find all indexes of
    1          1s
    aV         in vectorized xor:
       +ZQ     Q with a 0 on the front
       +QZ     Q with a 0 on the end
  2

Coba di sini .

lirtosiast
sumber
2

Perl, 47 byte

s/F*(T*)(T)F*/[$-[0],$+[1]],/g;chop$_;$_="[$_]"

Dengan opsi perlrun berikut -lpe:

$ perl -lpe's/F*(T*)(T)F*/[$-[0],$+[1]],/g;chop$_;$_="[$_]"' <<< 'TTFFFTTTTTTTTTTF'
[[0,1],[5,14]]

Alternatif tempat output dipisahkan garis (34 byte):

$ perl -pE's/F*(T*)(T)F*/$-[0] $+[1]\n/g;chomp' <<< TTFFFTTTTTTTTTTF
0 1
5 15
andlrc
sumber
1

Python 2, 108 byte

l=input();l+=[0];o=[];s=k=0
for i,j in enumerate(l):s=j*~k*i or s;~j*l[i-1]and o.append([s,i-1]);k=j
print o

Kasus uji:

$ python2 rangesinlists2.py
[0]
[]
$ python2 rangesinlists2.py
[-1]
[[0, 0]]
$ python2 rangesinlists2.py
[-1,-1,0,-1]
[[0, 1], [3, 3]]
$ python2 rangesinlists2.py
[0,-1,-1,0,0,-1,-1,-1]
[[1, 2], [5, 7]]
$ python2 rangesinlists2.py
[0,-1,-1,0,0,0,-1,-1,-1,-1]
[[1, 2], [6, 9]]
$ python2 rangesinlists2.py
[-1,-1,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0]
[[0, 1], [5, 14]]
$ python2 rangesinlists2.py
[0,0,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1]
[[2, 3], [12, 19], [33, 54], [93, 94]]

Tentunya ada solusi yang lebih pendek dari ini, tetapi berhasil.

kuintopia
sumber
1

Haskell: 123 byte (Contoh, tidak bisa menang)

f l=[(s,e)|let m=length l-1,let r=[0..m],s<-r,e<-r,and[l!!x|x<-[s..e]],s<=e,let(#)p=not$l!!p,s==0||(#)(s-1),e==m||(#)(e+1)]

Kurang bermain golf:

f l = [(start,end) | start <- [0..max], end <- [0..max], allTrue start end, start <= end, notBelow start, notAbove end]
  where
    max = (length l) - 1
    allTrue s e = and (subList s e)
    subList s e = [l !! i | i <- [s,e]]
    notBelow  s = (s == 0) || (not (l !! (s-1)))
    notAbove  e = (s == m) || (not (l !! (e+1)))
Michael Klein
sumber
Bahkan ketika tidak bermain golf: allTrue s e = and (subList s e)atau mungkin allTrue = (and.) . sublist.
nimi
Oke, untuk alasan yang saya tidak ingat, saya pikir itu lebih "jelas" ketika saya ungolfing ... (Diedit)
Michael Klein
1
Oh, tentu saja, pendapat berbeda tentang apa yang "jelas". Saya juga berpikir all (==True) (subList s e)sangat jelas.
nimi
1

CJam, 30 byte

0l~0++2ewee{1=$2,=},{~0=-}%2/`

Input sebagai array gaya CJam dari 0s dan 1s. Output sebagai array gaya CJam.

Jalankan semua test case. (Mengurus konversi format input.)

Martin Ender
sumber
1

Japt, 27 byte

A=[];Ur"T+"@Ap[YXl +Β΄Y]};AΒ·

Pasti ada cara untuk bermain golf ini ...

Bagaimanapun, itu sama dengan jawaban π”Όπ•Šπ•„π•šπ•Ÿ saya.

Mama Fun Roll
sumber
Wow, saya baru saja membuat solusi ini sendiri .... Algoritma yang bagus!
ETHproductions
1

APL, 17 karakter

{(↑,β†‘βˆ˜βŠ–)Β¨β΅βŠ‚β΅Γ—β³β΄β΅}

Di βŽ•IO←0dan βŽ•ML←3. Dalam Bahasa Inggris:

  • ⍡×⍳⍴⍡: nol elemen-elemen dari vektor indeks selama argumen di mana argumen itu salah
  • β΅βŠ‚: potong pada awal setiap menjalankan kebenaran dan buang yang salah
  • (↑,β†‘βˆ˜βŠ–)Β¨: ambil elemen pertama dan terakhir dari setiap subarray
lstefano
sumber
0

PowerShell, 82 byte

("$args"|sls 't+'-A).Matches|%{if($_){'{0},{1}'-f$_.Index,($_.Index+$_.Length-1)}}

Solusi Regex, menggunakan properti objek MatchInfo .

Contoh

PS > .\BoolRange.ps1 'F'


PS > .\BoolRange.ps1 'T'
0,0

PS > .\BoolRange.ps1 'TTFFFTTTTTTTTTTF'
0,1
5,14
beatcracker
sumber
0

Mathematica, 45 byte

SequencePosition[#,{True..},Overlaps->False]&

Tidak terlalu menarik; menggunakan builtin.

A Simmons
sumber
0

Clojure, 109 karakter

#(first(reduce(fn[[r i]p](let[e(+(count p)i)][(if(first p)(conj r[i(dec e)])r)e]))[[]0](partition-by not %)))

Hal pertama yang terlintas di pikiran saya, berdasarkan reduce dan partition-by.

Kotak uji sederhana (peta Tke truedan Fke false):

(def f #(first(reduce(fn[[r i]p](let[e(+(count p)i)][(if(first p)(conj r[i(dec e)])r)e]))[[]0](partition-by not %))))
(f (map #(= 'T %) '[F,T,T,F,F,T,T,T]))
NikoNyrh
sumber