Wyzwanie:

Napisz funkcję lub program, który akceptuje listę wartości boolowskich i zwraca wszystkie zakresy wartości True.

Przypadki testowe:

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]]

Zasady:

• Możesz wybrać sposób kodowania danych wejściowych, np. Listę, tablicę, ciąg znaków itp.
• Dane wyjściowe muszą być zakodowane jako lista podobnych do list lub ciąg pokazujący takie, więc tablice, listy, krotki, macierze, wektory itp.
• Wartości boolowskie muszą być kodowane jako stałe, ale w przeciwnym razie dozwolona jest dowolna prosta konwersja T / F na pożądane stałe
• EDYCJA: ewaluacja lub podobne w czasie wykonywania jest dozwolone.
• Nie zapomnij wyjaśnić, w jaki sposób dane wejściowe są przekazywane do programu / funkcji i podaj dane wejściowe / wyjściowe dla przypadków testowych
• Konwersja do żądanego formatu wejściowego nie jest liczona
• Standardowe luki są niedozwolone
• Jeśli Twój język ma taką funkcję, jest to niedozwolone
• Nie zaakceptuję własnego zgłoszenia
• EDYCJA: Format wyjściowy jest elastyczny. Jeśli nie jest drukowana lista lub podobne, wartości zakresu muszą być oddzielone jednym znakiem nienumerycznym i oddzielnymi zakresami.

Punktacja:

• Wynik jest w bajtach, chyba że jest niezgodny z Twoim językiem (np. Kodery w języku Piet)
• Najniższy wynik wygrywa

Istnieje duża elastyczność wejścia i wyjścia, ale rozwiązania, w których T / F są zastępowane funkcjami wykonującymi całą pracę, są niedozwolone.

Debugowanie:

Jeśli piszesz swój w Haskell lub możesz wywołać go z Haskell, następujące funkcje sprawdzą twoją funkcję / program:

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)

Pyth, 17 16 bajtów

fT.b*Y,~+ZNtZrQ8

Wykorzystuje trochę fantazji po przypisaniu magii kontrowania wraz z kodowaniem długości przebiegu.

Pobiera dane wejściowe jako tablicę 0s i 1s, np [1, 1, 0, 1, 0]. Wyniki jak w wyzwaniu, np [[0, 1], [3, 3]].

Pakiet testowy

Pyth, 18 bajtów

CxR.:++~Zkz02_B_`T

Zestaw testowy

Prawda jest reprezentowana jako 1, Fałsz jako 0.

Zakresy są reprezentowane łącznie.

Retina , 82 34 27 bajtów

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

S_`:

Pusty wiersz powinien zawierać pojedynczą spację.

Dane wejściowe są ciągiem płaskim _dla wartości prawda i :fałsz. Wyjście to pary rozdzielone spacjami, każda w osobnym wierszu.

Wypróbuj online.

Wyjaśnienie

Ciężki golf od 82 do 27 bajtów był możliwy dzięki sprytnemu wyborowi reprezentacji prawdy i fałszu. Wybrałem znak słowny _, (który nie jest cyfrą) dla prawdy, i znak niebędący słowem :, (który nie wymaga ucieczki) dla fałszu. To pozwala mi wykryć końce zakresów jako granice słów.

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

Dopasowujemy granicę słów. Chcemy zastąpić tę granicę odpowiednim indeksem prawdziwej wartości. Zasadniczo jest to dość łatwe dzięki najnowszej $#funkcji Retiny , która zlicza liczbę przechwyceń grupy. Po prostu łapiemy każdą postać przed tą pozycją do grupy. Licząc te postacie, otrzymujemy pozycję. Jedynym haczykiem jest to, że końce zasięgu są teraz wyłączone o jeden. Chcemy indeks postaci przed meczem. Można to również łatwo naprawić poprzez opcjonalne dopasowanie tego, _co nie zostało schwytane, pomijając w ten sposób jedną postać, gdy jesteśmy na końcu zakresu.

_+
<space>

Teraz zastępujemy wszystkie serie znaków podkreślenia spacją. Oznacza to, że wstawiamy spację między początkiem i końcem każdego zakresu, jednocześnie usuwając podkreślenia.

S_`:

Pozostawia to dwukropek (i nadal musimy rozdzielić pary). Robimy to, dzieląc cały ciąg na linie wokół każdego jelita grubego. Te Ssubstancje czynne trybie podziału, a _pomijanie pustych segmentów tak, że nie dostają mnóstwo pustych wierszy, gdy mamy serie dwukropkami.

Python 2, 69 bajtów

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

Przykładowe dane wyjściowe:

2 3; 7 16; 18 18;

Bezpośrednie podejście, bez wbudowanych. Śledzi bieżącą wartość xi poprzednią wartość p. Kiedy są różne, zmieniliśmy biegi. Po przełączeniu 0na 1drukuje bieżący indeks i. Po przełączeniu 1na 0drukuje bieżący indeks minus jeden, a następnie średnik.

ifJest dość śmierdząca. Może rekurencja byłaby lepsza,

MATL , 17 18 20 bajtów

j'T+'1X32X34$2#XX

Korzysta z bieżącej wersji (9.1.0) języka / kompilatora.

Dane wejściowe to ciąg znaków zawierający znaki Ti F. Dane wyjściowe to dwuwierszowa tabela, w której każda kolumna wskazuje zakres przy użyciu indeksowania 1, który jest domyślnym językiem.

Dzięki Stewie Griffin za usunięcie 2 bajtów.

Przykład

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

Wyjaśnienie

Opiera się na prostym wyrażeniu regularnym:

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

Oktawa, 43 bajtów

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

find(diff([0,x,0]))znajduje wszystkie pozycje, w których tablica wejściowa zmienia się między true a false. Przekształcając to w macierz 2 na n, osiągamy dwie rzeczy: zmiany z prawdy na fałsz i z fałszu na prawdę są podzielone na dwa rzędy. Umożliwia to odjęcie 1 i 2 od każdego z tych wierszy. Odejmowanie 1 od pierwszego wiersza jest konieczne, ponieważ Octave ma indeks 1, a nie zero. Odejmowanie 2 z drugiego wiersza jest konieczne, ponieważ find(diff())znajduje pozycję pierwszej fałszywej wartości, a my chcemy ostatnią prawdziwą wartość. Część odejmowania jest możliwa tylko w Octave, a nie w 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

CJam, 27 25 bajtów

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

Oczekuje danych wejściowych takich jak TTFTFT. Wypróbuj online .

Wyjaśnienie

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

Japt, 34 31 25 bajtów

Tym razem wypróbowanie nowego podejścia naprawdę się sprawdziło.

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

Wypróbuj online!

Dane wejściowe to ciąg znaków Ffor falsei Tfor true. Dane wyjściowe to tablica tablic; reprezentacja ciągu sprawia, że ​​wygląda jak pojedyncza tablica.

Jak to działa

          // 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

Uwaga: teraz widzę, że kilka osób wymyśliło już ten algorytm, ale odkryłem go niezależnie.

Wersja niekonkurencyjna, 22 bajty

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

W najnowszym zatwierdzeniu GitHub dodałem nową funkcję: interlinia ;ustawia zmienne A-J,Lna różne wartości. Ajest ustawiony na pustą tablicę, co eliminuje potrzebę jego ręcznego tworzenia.

Haskell, 74 bajty

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

Przykład użycia: map(\l->(fst$l!!0,fst$last l)).wordsBy(not.snd).zip[0..] $ [True,False,True,True,False]-> [(0,0),(2,3)].

Jak to działa:

                               -- 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)]

J, 26 bajtów

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

Jest to bezimienny czasownik monadyczny (funkcja jednoargumentowa), który zwraca tablicę 2D lub liczby całkowite. Używa się go w następujący sposób.

  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

Wyjaśnienie

[: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.

Ruby, 39 lat

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

Przykładowe wywołanie:

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

Tak ..Ruby reprezentuje zakresy włączające.

Jedną interesującą rzeczą jest to, jak uzyskać indeks końca zakresu. To dziwne. Dynamicznie tworzę wyrażenie regularne, które pasuje do ostatniego znaku zakresu, a następnie wszystkie kolejne znaki i koniec łańcucha, aby wymusić prawidłowe dopasowanie. Następnie używam, =~aby uzyskać indeks tego wyrażenia regularnego w oryginalnym ciągu.

Podejrzewam, że może być krótszy sposób na to w Ruby przy użyciu flag -naF.

JavaScript (ES6), 59

Funkcja anonimowa, wprowadzana jako ciąg znaków Ti Fzwracająca dane wyjściowe jako tablicę tablic

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

TEST

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>

𝔼𝕊𝕄𝕚𝕟, 18 znaków / 28 bajtów

ïħ`T+`,↪ᵖ[_,$Ꝉ+‡_]

Try it here (Firefox only).

Wyjaśnienie

ïħ`T+`,↪ᵖ[_,$Ꝉ+‡_] // implicit: ï=input
ïħ`T+`,            // for each T-sequence...
       ↪ᵖ[_,$Ꝉ+‡_] // push [start index of sequence, end index of sequence] to the stack
                   // implicit stack output

Haskell, 62 bajty

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

Pobiera na wejściu listę zer i jedynek.

Biorąc pod uwagę listę l, uzupełnia ją 0 po obu stronach i oblicza indeksowaną listę kolejnych par. Na przykład

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

Następnie wyodrębnij indeksy odpowiadające kolejnym elementom (0,1)i (1,0), które są początkami bloków 0 i 1, odejmując 1 od początków 0, aby uzyskać końce 1, i pomiń wyniki.

Pyth, 19 18 bajtów

m-VdU2cx1aV+ZQ+QZ2

Wyjaśnienie:

             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

Wypróbuj tutaj .

Perl, 47 bajtów

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

Dzięki następującym opcjom Perlrun -lpe:

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

Alternatywnie, gdy wyjście jest oddzielone wierszem (34 bajty):

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

Python 2, 108 bajtów

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

Przypadki testowe:

$ 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]]

Z pewnością istnieje krótsze rozwiązanie, ale działa.

Haskell: 123 bajty (przykład, nie można wygrać)

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)]

Mniej golfa:

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)))

CJam, 30 bajtów

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

Wprowadź jako tablicę 0s i 1s w stylu CJam . Wyjście jako tablica par w stylu CJam.

Uruchom wszystkie przypadki testowe. (Zajmuje się konwersją formatów wejściowych.)

Japt, 27 bajtów

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

Musi istnieć sposób na grę w golfa ...

W każdym razie jest to to samo co moja odpowiedź.

APL, 17 znaków

{(↑,↑∘⊖)¨⍵⊂⍵×⍳⍴⍵}

W ⎕IO←0i ⎕ML←3. Po angielsku:

• ⍵×⍳⍴⍵: wyzeruj elementy wektora indeksu, dopóki argument, w którym argument jest fałszywy
• ⍵⊂: wytnij na początku każdego ciągu prawd i wyrzuć fałsz
• (↑,↑∘⊖)¨: weź pierwszy i ostatni element każdej podtablicy

PowerShell, 82 bajty

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

Rozwiązanie Regex, używając właściwości obiektu MatchInfo .

Przykład

PS > .\BoolRange.ps1 'F'


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

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

Mathematica, 45 bajtów

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

Niezbyt interesujące; używa wbudowanego.

Clojure, 109 znaków

#(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 %)))

Pierwsza rzecz, jaka przyszła mi do głowy, oparta na reducei partition-by.

Prosty przypadek testowy (mapy Tdo truei Fna 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]))