Fredags-quiz: Hvad gør denne linje Python-kode?

Er denne stump kode for uigennemskuelig for Version2's læsere?

state = [st for s in state for st in states[(s,letter)]]

Ja, det er måske en lidt hård start på en artikel, men hvorfor ikke bare begynde med det, denne fredags it-quiz handler om:

Afkod ovenstående linje Python-kode og strik en kortere løsning sammen.

Denne lille kodenød stammer fra bloggen A Geek With a Hat, der sender udfordringen i vejret med påskriften 'Strangest line of python you have ever seen'.

Om det også er den mærkeligste linje Python-kode, Version2's ærede læsere er stødt på, må komme an på en prøve.

Men på redaktionen er vi da enige om, at den pågældende linje kunne være skrevet mere selvforklarende, end tilfældet er.

Kodestumpen indgår i en implementering af en nondeterministisk tilstandsmaskine, som datalogerne vil genkende fra teorien om beregnelighed.

Hele implementeringen ser sådan ud (den omtalte kodestump ses i linje 9):

from optparse import OptionParser
from collections import defaultdict
 
def run(beseda):
       a, states = open("machine.txt") ,defaultdict(list)
       state, final= a.readline().split()[1:],a.readline().split()[1:]
       [states[(i.split()[0], i.split()[1])].append(i.split()[3]) for i in a]
       for letter in word:
               state = [st for s in state for st in states[(s,letter)]]
       return any(i in state for i in final)
 
print [(b,"YES") if run(b) else (b,"NO") for b in OptionParser().parse_args()[1]]

A Geek With a Hat udlover småkager til den person, der både kan forklare kodelinjens virkemåde og komme op med en løsning, der er kortere rent syntaksmæssigt.

Vi siger held og lykke og god weekend.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (9)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#1 Peter Stricker

Hmm, nu kender jeg ikke Python, men umiddelbart kunne det da godt ligne det, man i Haskell kender som en list comprehension over to lister. I givet fald skulle input funktionerne så være 'for s in state' i stedet for 's <- state' og tilsvarende for 'for st in states' i stedet for 'st <- states'.

Men jeg kan ikke lige gennemskue, hvordan '[(s, letter)]' så skulle kunne være et prædikat.

Anyways, et bud på samme udtryk i Haskell skulle så være: state = [ st | s <- state, st <- states, [(s, letter)]]. Det giver ikke rigtig mening.

  • 0
  • 0
#4 Mikkel Jans

den siger noget ala: "for hver 's' i 'state' find (s, letter) i 'states'"

for example

states = {('b', 1):'world', ('a',1):'hello'} state = ['a', 'b'] [st for s in state for st in states[(s,1)]] ['h', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd']

Ved ikke hvordan det skulles gøres kortere. Vil også mene at det er kort nok :)

Det tætteste jeg kan komme på er: itertools.chain(*(states[(s,1)] for s in state))

  • 1
  • 0
#5 Erik Cederstrand

Syntaksen for dobbelt list comprehension i Python er meget forvirrende og giver næsten altid ulæselig kode. Koden overskriver desuden state i et udtryk, hvor den gamle værdi bruges, hvilket bidrager til ulæseligheden.

En omskrivning (omend ikke kortere) kunne være:

new_state = []  
[new_state.extend(states[(s, letter)]) for s in state]  
state = new_state
  • 0
  • 0
#6 Torben Mogensen Blogger

Anyways, et bud på samme udtryk i Haskell skulle så være: state = [ st | s <- state, st <- states, [(s, letter)]]. Det giver ikke rigtig mening.

states er nok en tabel, og Python-udgaven er en tildeling, så Haskell-versionen bør nok være

newState = [ st | s <- state, st <- states[(s, letter)]]

som giver god mening: Find alle de tilstande, der kan nås fra tilstande i state med overgange på letter. Den eneste grund til, at den oprindelige Python-linje er svær at læse, er den mærkelige syntaks for list comprehensions.

En kortere Haskell-linje ville være

newState = [states[(s,letter)] | s <- state]

Så mon ikke en kortere Python-linje er

state = [states[(s,letter)] for s in state] ?

  • 0
  • 0
#8 Finn Aarup Nielsen

List comprehension er almindelige i Python til dannelse af lister. De ser ud til at være hurtigere end almindelige for-loops med 'append' eller 'extend'. Jeg har en lille test her: http://fnielsen.posterous.com/for-loops-numpy-and-python-optimization

List comprehension med dobbelt-for kan være forvirrende. De ser dog også ud til at være hurtigere end andre konstruktioner, se et eksempel med konvertering af lister af lister til en lang liste her: http://stackoverflow.com/questions/952914/making-a-flat-list-out-of-list...

  • 0
  • 0
Log ind eller Opret konto for at kommentere