15
\$\begingroup\$

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'
\$\endgroup\$
  • 1
    \$\begingroup\$ For the last test case, why isn't The five boxing wizards jump quickly returned? \$\endgroup\$ – Blue May 17 '16 at 7:04
  • 1
    \$\begingroup\$ For the second case, are you allowed the space preceding the Q? It doesn't add to the letter count. \$\endgroup\$ – Neil May 17 '16 at 9:04
  • 2
    \$\begingroup\$ @muddyfish Because it has 31 letters, whereas the expected output has only 26. \$\endgroup\$ – Martin Ender May 17 '16 at 12:03
  • 4
    \$\begingroup\$ Nice first question! \$\endgroup\$ – Rɪᴋᴇʀ May 17 '16 at 14:16
  • 2
    \$\begingroup\$ Yep. No reason it shouldn't be. Taking the "true" minimum's in the spirit of the question, but it's not necessary. \$\endgroup\$ – Reecer6 May 17 '16 at 22:35

10 Answers 10

6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You seem to not have updated the code in the first code block. Also !-GrT0 is shorter for the filter condition, I believe. I also think you do need the l to make the sort work properly. \$\endgroup\$ – FryAmTheEggman May 17 '16 at 17:56
  • \$\begingroup\$ Oh, I misspoke, I meant the link. In your link you still have the l, and without it you get different results. I believe the problem is repeated letters, but I'm not 100% sure. \$\endgroup\$ – FryAmTheEggman May 17 '16 at 18:21
  • \$\begingroup\$ So it does matter - and thanks for the optimization! \$\endgroup\$ – Blue May 17 '16 at 18:23
3
\$\begingroup\$

Pyth - 22 bytes

\o/ FGITW!

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

Test Suite.

\$\endgroup\$
2
\$\begingroup\$

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}
\$\endgroup\$
2
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ Can you not use [r=l="",...s].map((_,b,a)=>? \$\endgroup\$ – Neil May 17 '16 at 7:48
  • \$\begingroup\$ @Neil Thanks, I always forget about the third parameter in the map function. \$\endgroup\$ – user81655 May 17 '16 at 8:03
  • \$\begingroup\$ I think @edc65 can beat this though, I merged the code for his exploded substrings with that for his pangram tester and ended up with a 134 byte function. \$\endgroup\$ – Neil May 17 '16 at 16:35
  • \$\begingroup\$ My best is 142 so far \$\endgroup\$ – edc65 May 17 '16 at 22:43
  • \$\begingroup\$ Sadly I didn't think to save it and my PC crashed so now I don't know what I had; the best I can do now is 138 bytes. \$\endgroup\$ – Neil May 18 '16 at 19:27
2
\$\begingroup\$

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 , not . ;-)

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.')
\$\endgroup\$
  • \$\begingroup\$ Don't think .upper() is needed in the key function. \$\endgroup\$ – RootTwo May 19 '16 at 19:34
  • \$\begingroup\$ @RootTwo Oops, yup, you're right. Thanks. \$\endgroup\$ – Morgan Thrapp May 19 '16 at 19:34
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.