Shortest Pangrammatic Window

Question

A pangram is a sentence or excerpt which contains all twenty-six letters of the alphabet, as is demonstrated in this code golf challenge. However, a pangrammatic window is a pangram in the form of some segment of text, which may end or begin halfway through a word, found somewhere within a larger work. These naturally occur everywhere, being proper subsets of true pangrams, so just verifying if something contains a pangrammatic window would be boring and also it was previously done.

So, we're interested in finding the smallest one there is in a given piece of text based on its letter length! In the shortest possible code in bytes, of course, to fit the theme.

Rules and Guidelines

• Receive a string as the input and return the string of the smallest pangrammatic window in the input if there is one. If there is not, return either a Boolean False or an empty string.
• Whether a string is a pangrammatic window or not is case-insensitive and only depends on the 26 letters, not any punctuation or numbers or other odd symbols.
• Similarly, a pangrammatic window's letter length is the total number of how many appearances of letters occur in it alone, and not simply the number of every character. The returned value must be smallest based on this count. We're linguists, after all, not programmers.
• An output of a pangrammatic window must, however, must be an exact substring of the input, containing the same capitalization and punctuation, etc.
• If there are multiple shortest pangrammatic windows of the same letter length, return any one of them.

Test Cases

'This isn't a pangram.'
==> False

'Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).'
==> 'Quick-Brown-Fox (the one who jumped over some lazy ig'

'"The five boxing wizards jump quickly." stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" he shouted to the heavens.'
==> 'ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ'

Answer 1

Pyth, 20 16 14 bytes

hol@GNf!-GrT0.:

Explanation:

             .: - substrings of input()
      f!-GrT0   - filter to ones which contain the alphabet
 ol@GN          - sort by number of alphabetical chars
h               - ^[0]

      f!-GrT0   - filter(lambda T:V, substrings)
          rT0   -    T.lower()
        -G      -   alphabet-^
       !        -  not ^

 o              - sort(^, lambda N:V)
   @GN          -   filter_presence(alphabet, N)
  l             -  len(^)

Try it here!

When there isn't a correct solution, the program exits with an error with no output to stdout.

Answer 2

Pyth - 22 bytes

\o/ FGITW!

h+ol@GrNZf}GS{rTZ.:z)k

Test Suite.

Answer 3

Ruby, 100 bytes

Returns nil if no window is found.

->s{r=0..s.size
(r.map{|i|s[i,r.find{|j|(?a..?z).all?{|c|s[i,j]=~/#{c}/i}}||0]}-['']).min_by &:size}

Answer 4

JavaScript (ES6), 139 138 136 bytes

s=>[r=l="",...s].map((_,b,a)=>a.map((c,i)=>i>b&&(t+=c,z=parseInt(c,36))>9&&(v++,n+=!m[z],m[z]=n<26||l&&v>l||(r=t,l=v)),t=m=[],v=n=0))&&r

Saved 2 bytes thanks to @Neil!

Indented

var solution =

s=>
  [r=l="",...s].map((_,b,a)=> // b = index of start of window to check
    a.map((c,i)=>
      i>b&&(
        t+=c,
        z=parseInt(c,36)
      )>9&&(
        v++,
        n+=!m[z],
        m[z]=
          n<26||
          v>l&&l||(
            r=t,
            l=v
          )
      ),
      t=m=[],
      v=n=0
    )
  )
  &&r

<textarea cols="70" rows="6" id="input">Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).</textarea><br /><button onclick="result.textContent=solution(input.value)">Go</button><pre id="result"></pre>

Answer 5

PowerShell v2+, 218 bytes

param($a)$z=@{};(0..($b=$a.length-1)|%{($i=$_)..$b|%{-join$a[$i..$_]}})|%{$y=$_;$j=1;65..90|%{$j*=$y.ToUpper().IndexOf([char]$_)+1};if($j){$z[($y-replace'[^A-Za-z]').Length]=$y}}
($z.GetEnumerator()|sort Name)[0].Value

Yeah, so substring manipulation (there aren't any built-ins) isn't really PowerShell's strong suit...

We take input param($a) and set a new empty hashtable $z. This will be our storage of candidate pangrammatic substrings.

Using a slight modification of my code from Exploded Substrings, we construct all substrings of the input. Yep, even one-character punctuation-only substrings. This is code-golf, not fastest-code. ;-)

All of those substrings are encapsulated in parens and piped into another loop with |%{...}. We temporarily set $y to our current substring, set a helper counter $j, and start another loop 65..90|%{...}, conveniently over the ASCII char codes for capital letters. Each inner loop, we take $y, make it all uppercase, and pull out the .IndexOf that particular char. Since this will return -1 if not found, we +1 the result before multiplying it into $j. This ensures that if any one character isn't found, $j will equal zero.

Which is exactly what the if is all about. If $j is non-zero, that means that every letter was found at least once in the substring $y, so we need to add that to our candidate pool. We do so by taking $y and -replaceing every non-letter with nothing, which gets us the letter-length of that substring. We use that as the index into hashtable $z and store $y at that index. This has the quirk of overwriting substrings of the same letter-length with the one that occurs "furthest" in the original string, but that's allowed by the rules, since we're only concerned about letter-length.

Finally, we need to sort through $z and pull out the smallest. We have to use the .GetEnumerator call in order to sort on the objects inside $z, then sort those on Name (i.e., the length index from above), selecting the [0]th one (i.e., the shortest), and outputting its .Value (i.e., the substring). If no such substring fits, this will toss an error (Cannot index into a null array) when it tries to index into $z, and output nothing, which is falsey in PowerShell. (the third test case below has an explicit cast as [bool] to show this)

Test Cases

PS C:\Tools\Scripts> .\golfing\shortest-pangrammatic-window.ps1 '"The five boxing wizards jump quickly." stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" he shouted to the heavens.'
ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" 

PS C:\Tools\Scripts> .\golfing\shortest-pangrammatic-window.ps1 'Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).'
Quick-Brown-Fox (the one who jumped over some lazy ig

PS C:\Tools\Scripts> [bool](.\golfing\shortest-pangrammatic-window.ps1 "This isn't a pangram.")
Cannot index into a null array.
At C:\Tools\Scripts\golfing\shortest-pangrammatic-window.ps1:2 char:1
+ ($z.GetEnumerator()|sort Name)[0].Value
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    + CategoryInfo          : InvalidOperation: (:) [], RuntimeException
    + FullyQualifiedErrorId : NullArray

False

Answer 6

Haskell, 180 bytes

This was hard, but really fun without imports.

l=['a'..'z']
u=['A'..'Z']
f&[]=[];f&x=x:f&f x
g#h=(.g).h.g
f x|v<-[y|y<-(tail&)=<<(init&x),and$zipWith((`elem`y)#(||))l u]=last$[]:[z|z<-v,all((length.filter(`elem`l++u))#(<=)$z)v]

Much less golfed:

lowerCase = ['a'..'z']
upperCase = ['A'..'Z']

f & x = takeWhile (not . null) $ iterate f x

(#) = flip on

subStrings x = (tail &) =<< (init & x)

pangram p = and $ zipWith ((`elem` p) # (||)) lowerCase upperCase

leqLetters x y = (length . filter (`elem` lowerCase ++ upperCase)) # (<=)

fewestLetters xs = [ x | x <- xs, all (leqLetters x) xs]

safeHead [] = ""
safeHead xs = head xs

f x = safeHead . fewestLetters . filter pangram . subStrings

Surprise, surprise: it's really slow.

Answer 7

Oracle SQL 11.2, 461 bytes

WITH s AS (SELECT SUBSTR(:1,LEVEL,1)c,LEVEL p FROM DUAL CONNECT BY LEVEL<=LENGTH(:1)),v(s,f,l)AS(SELECT c,p,p FROM s UNION ALL SELECT s||c,f,p FROM v,s WHERE p=l+1),c AS(SELECT CHR(96+LEVEL)c FROM DUAL CONNECT BY LEVEL<27),a AS(SELECT LISTAGG(c)WITHIN GROUP(ORDER BY 1) a FROM c)SELECT MIN(s)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s)-NVL(LENGTH(TRANSLATE(LOWER(s),' '||a,' ')),0))FROM(SELECT s,f,SUM(SIGN(INSTR(LOWER(s),c)))x FROM v,c GROUP BY s,f),a WHERE x=26;

Un-golfed

WITH s AS (SELECT SUBSTR(:1,LEVEL,1)c,LEVEL p FROM DUAL CONNECT BY LEVEL<=LENGTH(:1))
,v(s,f,l) AS
(
  SELECT c,p,p FROM s
  UNION ALL
  SELECT s||c,f,p FROM v,s WHERE p=l+1 
)
,c AS(SELECT CHR(96+LEVEL)c FROM DUAL CONNECT BY LEVEL<27)
,a AS(SELECT LISTAGG(c)WITHIN GROUP(ORDER BY 1) a FROM c)
SELECT MIN(s)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s)-NVL(LENGTH(TRANSLATE(LOWER(s),' '||a,' ')),0))
FROM(SELECT s,f,SUM(SIGN(INSTR(LOWER(s),c)))x FROM v,c GROUP BY s,f),a
WHERE x=26

The s view splits the input in characters and also returns the position of each character.

The recursive view v returns every substring of the input
s is the substring
f the position of the first character of the substring
l the position of the last character added to the current substring

The c view returns the alphabet, one letter at a time

The a view returns the alphabet concatenated as a single string

SELECT s,f,SUM(SIGN(INSTR(LOWER(s),c))
Returns for each substring the number of distinct letters present in it
INSTR returns the pos of a letter in the substring, 0 if not present
SIGN returns 1 if pos > 0, 0 if pos = 0

WHERE x=26
Filters the substring containing the whole alphabet

TRANSLATE(LOWER(s),' '||a,' ')
Deletes every letter from the substring

LENGTH(s)-NVL(LENGTH(TRANSLATE(LOWER(s),' '||a,' ')
Length in letters is the length of the substring minus the length of the subtring without letters

SELECT MIN(s)KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s)-NVL(LENGTH(TRANSLATE(LOWER(s),' '||a,' ')),0))
Keeps only the substring with the smaller letter count.
If there is more than one, the first one, sorted as strings ascending, is kept

Answer 8

Python 3, 171, 167, 163, 157, 149 bytes.

Saved 4 bytes thanks to DSM.
Saved 8 bytes thanks to RootTwo.

lambda x,r=range:min([x[i:j]for i in r(len(x))for j in r(len(x))if{*map(chr,r(65,91))}<={*x[i:j].upper()}]or' ',key=lambda y:sum(map(str.isalpha,y)))

Having to sort based on the number of letters is killing me.

Test cases:

assert f("This isn't a pangram.") == ' '
assert f("Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).") == ' Quick-Brown-Fox (the one who jumped over some lazy ig', f("Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).")
assert f('"The five boxing wizards jump quickly." stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" he shouted to the heavens.') == '. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ', f('"The five boxing wizards jump quickly." stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" he shouted to the heavens.')

Answer 9

PowerShell (v4), 198 156 bytes

param($s)
-join(@(1..($y=$s.Length)|%{$w=$_
0..$y|%{(,@($s[$_..($_+$w)]))}}|?{($_-match'[a-z]'|sort -U).Count-eq26}|sort -Pr {($_-match'[a-z]').count})[0])


# Previous 198 byte golf
$a,$b,$c=@(1..($s="$args").Length|%{$w=$_
0..($s.Length-$w)|%{if((($t=$s[$_..($_+$w)]-match'[a-z]')|sort -u).Count-eq26){(,@($t.Length,$_,$w))}}}|sort -pr{$_[0]})[0]
(-join($s[$b..($b+$c)]),'')[!$a]

Test Cases

PS C:\> .\PangramWindow.ps1 "This isn't a pangram."


PS C:\> .\PangramWindow.ps1 'Everyone knows about that infamous Quick-Brown-Fox (the one who jumped over some lazy ignoramus of a dog so many years ago).'
Quick-Brown-Fox (the one who jumped over some lazy ig

PS C:\> .\PangramWindow.ps1 '"The five boxing wizards jump quickly." stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. "ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!" he shouted to the heavens.'
ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!

---

Ungolfed explanation of the original

It's a brute-force nested loop which makes sliding windows of all sizes:

.SubString(0, 1) -> slide window over the string
.SubString(0, 2) -> slide window over the string
..
.SubString(0, string.Length) -> slide window over the string

For each window, it filters for only letters (case insensitive regex matching by default), runs the remaining characters through a unique filter, checks if there are 26 unique characters as the pangram test.

All windows with pangrams are turned into triplets of (number of letters including dupes, start index, window length including punctuation), which get sorted to find the shortest by overall character count, the first one is picked, and the output string built from that.

There's a lot of indexing outside the bounds of the string, which PowerShell usefully returns $null for, instead of throwing exceptions.

NB. the new 156 byte one is the same approach, but rewritten to use the pipeline a lot more.

$string = "$args"

# increasing window widths, outer loop
$allPangramWindows =  foreach ($windowWidth in 1..$string.Length) {

    # sliding windows over string, inner loop
    0..($string.Length - $windowWidth) | ForEach {

        # slice window out of string, returns a char array
        $tmp = $string[$_..($_+$windowWidth)]

        # filter the char array to drop not-letters
        $tmp = $tmp -match '[a-z]'

        # Drop duplicate letters
        $tmpNoDupes = $tmp | sort -Unique

        # If we're left with a 26 character array, this is a pangrammatic window. Output
        # a PowerShell-style tuple of count of letters, start index, width.
        if($tmpNoDupes.Count -eq 26){
            (,@($tmp.Length,$_,$windowWidth))
        }
    }
}

# Force the result into an array (to handle no-results), sort it
# by the first element (num of letters in the window, total)
$allPangramWindows = @( $allPangramWindows | sort -Property {$_[0]} )

# take element 0, a window with the fewest letters
$windowCharCount, $windowStart, $WindowEnd = $allPangramWindows[0]

# uses the results to find the original string with punctuation and whitespace
if ($windowLen) {
    $string[$windowStart..($windowStart + $windowLen)] -join ''
}

NB. not sure the ungolfed version works, because I didn't write that then golf it, it's just for exposition.

Answer 10

Julia, 111,110,108 96 bytes

!S=minimum(['A':'Z'⊆(r=S[i:j])|>uppercase ? sum(isletter,r) : Inf,r]
for i=(k=keys(S)),j=k)[2]

Attempt This Online!

• credits to @MarcMush: 96 bytes
• my first attack: 108 bytes

It returns "" for falsy cases; very ineffective (both for time and for memory); it does not optimize for window size/length - only the letter length is considered

Answer 11

Haskell, 123 bytes

import Data.Lists
import Data.Char
h x=take 1$sortOn((1<$).filter isAlpha)[e|e<-powerslice x,['a'..'z']\\map toLower e==""]

Defines a function h, which returns the empty list if there's no pangrammatic window or a one element list with the minimum window. Usage example:

*Main>  h "'The five boxing wizards jump quickly.' stated Johnny, before beginning to recite the alphabet with a bunch of semicolons in the middle. 'ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ!' he shouted to the heavens."
[". 'ABCDEFGHI;;;;;;;;;;;;;;;JKLMNOPQRSTUVWXYZ"]

How it works:

          [e|e<-powerslice x                  ]  -- for all continuous subsequences
                                                 -- e of the input  
                ,['a'..'z']\\map toLower e==""   -- keep those where the list
                                                 -- difference with all letters is
                                                 -- empty, i.e. every letter appears
                                                 -- at least once
    sortOn((1<$).filter isAlpha)                 -- sort all remaining lists on
                                                 -- their length after removing all
                                                 -- non-letters -> (1<$) see below
take 1                                           -- take the first, i.e. the minimum


calculating the length of a list: we're not interested in the length itself, but
in the relative order of the length. (1<$) replaces each element in a list with
the number 1, e.g. "abc" -> "111", "abcd" -> "1111", etc. Such '1'-strings have
the same order as the length of the original list. One byte saved!

Answer 12

05AB1E, 13 bytes

ŒʒlêAå}éΣág}н

Try it online or verify all test cases.

Or alternatively with just a sort-by without filter:

ŒéΣláDêAQig]н

Try it online or verify all test cases.

Both output an empty string as falsey. (Could have been 12 bytes if we would be allowed to output -1 as falsey with ŒéΣág}.ΔlêAå.)

Explanation:

Π      # Get all substrings of the (implicit) input-string
 ʒ      # Filter this list by:
  l     #  Convert the current substring to lowercase
   ê    #  Uniquify and sort all characters in the string
    A   #  Push "abcdefghijklmnopqrstuvwxyz"
     å  #  Check if the lowercase alphabet is in the uniquify-sorted substring
 }é     # After the filter: sort any remaining substrings from shortest to longest
   Σ    # Then sort it again by:
    á   #  Leave just all the letters of the substring
     g  #  Pop and push the length for the amount of letters
   }н   # After the sort-by: pop and leave just the first
        # (or an empty string if the list is empty)
        # (which is output implicitly as result)

Π          # Get all substrings of the (implicit) input-string
 é          # Sort them by length (shortest to longest)
  Σ         # Then sort it again by:
   l        #  Convert the current substring to lowercase
    á       #  Leave just all the letters of the substring
     D      #  Duplicate it
      ê     #  Uniquify and sort all characters in the letters in the string
       AQi  #  Pop, and if it's equal to the lowercase alphabet:
          g #   Pop and push the length for the amount of letters
  ]         # Close both the if-statement and sort-by
            # (note, integers are always sorted before strings, even if there are
            # digits in the input-string)
   н        # Pop and leave just the first result
            # (or an empty string if the list is empty)
            # (which is output implicitly as result)