Submit All submissions Best solutions PDF Back to list

PROG0571 - Pangrammatic window

A pangram is a sentence that contains every letter of the alphabet at least once. For some the challenge has always been to come up with pangrams that are as short as possible. Short pangrams in English are quite difficult to come up with and tend to use uncommon words, because the English language uses some letters (especially vowels) much more frequently than others. The archetypical "artificial" sentence of 35 letters that is often used as an example of an English pangram is

The quick brown fox jumps over the lazy dog.

Others believe that these constructed pangrams are too contrived, and search published works for pangrammatic windows. These are stretches naturally occurring text that contain of the letters of the alphabet at least once. For a long time, the shortest known window in a published work was found in Lillie de Hegermann-Lindencrone's 1912 book In the Courts of Memory, which contains the following excerpt.

I sang, and thought I sang very well; but he just looked up into my face with a very quizzical expression, and said, 'How long have you been singing, Mademoiselle?'

The stretch of text that has been marked in yellow is a pangrammatic window containing 56 letters. This is already quite short, but can we do better? In 2012 a 42-letter example was discovered in Piers Anthony's 2003 novel Cube Route.

"We are all from Xanth," Cube said quickly. "Just visiting Phaze. We just want to find the dragon."

In 2014, Jesse Sheidlower wrote a bot called PangramTweets that listens to Twitter messages and automatically retweets them if they are pangrams. Inspired by this, Google software engineer Malcolm Rowe set out to search first Project Gutenberg and then the entire Internet for the shortest possible window. Remarkably he found one of only 36 letters in a review of the film Magnolia by Todd Ramlow for PopMatters.

Further, fractal geometries are replicated on a human level in the production of certain ‘types’ of subjectivity: for example, aging kid quiz show whiz Donnie Smith (William H. Macy) and up and coming kid quiz show whiz Stanley Spector (Jeremy Blackman) are connected (or, perhaps, being cloned) in ways they couldn’t possibly imagine. 

On his blog, Row wrote: "I'm pretty impressed by this result. It's only one letter longer than "The quick brown fox …", and while that's not the shortest possible pangram by far, it is one of the more coherent ones."

Assignment

  • Write a function pangram that takes a string as its argument. The function must return a Boolean value that indicates whether or not the given string is a pangram.
  • Write a function window that takes a string as its argument. The function must return the text of the shortest pangrammatic window that can be found in the given string. The length of a pangrammatic window is measured as the length of the substring, not as the number of letters in that substring. In case the given string should contain multiple shortest pangrammatic windows, the text of the leftmost occurrence of a shortest pangrammatic window must be returned. In case the given string contains no pangrammatic windows, the function must return the value None.

Example

>>> pangram('The quick brown fox jumps over the lazy dog.')
True
>>> pangram('The quick brown fox jumped over the lazy dog.')
False

>>> window('The quick brown fox jumps over the lazy dog.')
'quick brown fox jumps over the lazy dog'
>>> window('The quick brown fox jumped over the lazy dog.')
>>> window("I sang, and thought I sang very well; but he just looked up into my face with a very quizzical expression, and said, 'How long have you been singing, Mademoiselle?' ")
'g very well; but he just looked up into my face with a very quizzical ex'
>>> window("'We are all from Xanth,' Cube said quickly. 'Just visiting Phaze. We just want to find the dragon.'")
"from Xanth,' Cube said quickly. 'Just visiting Phaze. W"
>>> window("Further, fractal geometries are replicated on a human level in the production of certain 'types' of subjectivity: for example, aging kid quiz show whiz Donnie Smith (William H. Macy) and up and coming kid quiz show whiz Stanley Spector (Jeremy Blackman) are connected (or, perhaps, being cloned) in ways they couldn’t possibly imagine.")
'bjectivity: for example, aging kid quiz show'

Resources

  • Chaikin (2006). Joaquin Through the Pangram Window. Word Ways 39(2), 17-37.
  • Irvine SA (2012). A 42-letter Pangrammatic Window. Word Ways 45, 313–316.
  • Keith M (2002). New Record Pangrammatic Windows. Word Ways 35(4), article 2.
  • Keith M (2006). Sub-60-Letter Pangrammatic Windows. Word Ways 39(1), article 2.
  • Pearson AC (1907). The Twentieth Century Standard Puzzle Book. London: George Routledge & Sons, LTD., New York: E.P. Dutton & co.
  • Rowe M (2014). Pangrams on the Web.

Een pangram is een zin waarin alle letters van het alfabet voorkomen. Voor sommigen bestaat de uitdaging erin om een zo kort mogelijk zin te construeren die aan deze voorwaarde voldoet. De archetyptische "kunstmatige" zin van 35 letters die vaak als voorbeeld van een pangram gebruikt wordt is

The quick brown fox jumps over the lazy dog.

Anderen vinden dan weer dat geconstrueerde pangrammen veel te gekunsteld zijn, en gaan in bestaande werken op zoek naar zo kort mogelijk pangrammatische vensters. Dit zijn stukken van een natuurlijke tekst waarin alle letters van het alfabet voorkomen. Zo bevat het boek In the Courts of Memory van Lillie de Hegermann-Lindencrone uit 1912 het volgende fragment.

I sang, and thought I sang very well; but he just looked up into my face with a very quizzical expression, and said, 'How long have you been singing, Mademoiselle?'

De passage die we gemarkeerd hebben is een pangrammatisch venster bestaande uit 56 letters. Dit is al vrij kort en was lange tijd het kortste gekende venster in een gepubliceerd werk. Maar kan het nog korter? In 2012 werd een pangrammatisch venster van 42 letters teruggevonden in de roman Cube Route van Piers Anthony uit 2003.

"We are all from Xanth," Cube said quickly. "Just visiting Phaze. We just want to find the dragon."

In 2014 schreef Jesse Sheidlower een bot PangramTweets die naar Twitter-berichten luistert en deze automatisch retweet als het pangrammen zijn. Hieruit haalde Malcolm Rowe — een software engineer bij Google — zijn inspiratie om eerst Project Gutenberg en daarna bij uitbreiding het volledige Internet te doorzoeken naar het kortst mogelijke venster. Hij vond er een van 36 letters in een review van de film Magnolia die Todd Ramlow had geschreven voor PopMatters.

Further, fractal geometries are replicated on a human level in the production of certain ‘types’ of subjectivity: for example, aging kid quiz show whiz Donnie Smith (William H. Macy) and up and coming kid quiz show whiz Stanley Spector (Jeremy Blackman) are connected (or, perhaps, being cloned) in ways they couldn’t possibly imagine. 

Op zijn blog schreef Rowe hierover: "I'm pretty impressed by this result. It's only one letter longer than "The quick brown fox …", and while that's not the shortest possible pangram by far, it is one of the more coherent ones."

Opgave

  • Schrijf een functie pangram waaraan een string moet doorgegeven worden. De functie moet een Booleaanse waarde teruggeven die aangeeft of de gegeven string een pangram is.
  • Schrijf een functie venster waaraan een string moet doorgegeven worden. De functie moet de tekst van het kortst mogelijke pangrammatische venster teruggeven dat in de gegeven string kan gevonden worden. Hierbij wordt de lengte van een pangrammatisch venster geteld als de lengte van de substring, en dus niet als het aantal letters in die substring. Als de gegeven string meerdere kortste vensters zou bevatten, dan moet de tekst uit het meest linkse van deze vensters teruggegeven worden. Als de gegeven string geen pangrammatische vensters bevat, dan moet de functie de waarde None teruggeven.

Voorbeeld

>>> pangram('The quick brown fox jumps over the lazy dog.')
True
>>> pangram('The quick brown fox jumped over the lazy dog.')
False

>>> venster('The quick brown fox jumps over the lazy dog.')
'quick brown fox jumps over the lazy dog'
>>> venster("I sang, and thought I sang very well; but he just looked up into my face with a very quizzical expression, and said, 'How long have you been singing, Mademoiselle?' ")
'g very well; but he just looked up into my face with a very quizzical ex'
>>> venster("'We are all from Xanth,' Cube said quickly. 'Just visiting Phaze. We just want to find the dragon.'")
"from Xanth,' Cube said quickly. 'Just visiting Phaze. W"
>>> venster("Further, fractal geometries are replicated on a human level in the production of certain 'types' of subjectivity: for example, aging kid quiz show whiz Donnie Smith (William H. Macy) and up and coming kid quiz show whiz Stanley Spector (Jeremy Blackman) are connected (or, perhaps, being cloned) in ways they couldn’t possibly imagine.")
'bjectivity: for example, aging kid quiz show'

Bronnen

  • Chaikin (2006). Joaquin Through the Pangram Window. Word Ways 39(2), 17-37.
  • Irvine SA (2012). A 42-letter Pangrammatic Window. Word Ways 45, 313–316.
  • Keith M (2002). New Record Pangrammatic Windows. Word Ways 35(4), article 2.
  • Keith M (2006). Sub-60-Letter Pangrammatic Windows. Word Ways 39(1), article 2.
  • Pearson AC (1907). The Twentieth Century Standard Puzzle Book. London: George Routledge & Sons, LTD., New York: E.P. Dutton & co.
  • Rowe M (2014). Pangrams on the Web.
Submit solution!
Added by:Peter Dawyndt
Date:2015-10-09
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.