Python Solutions to [https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/ 99 Prolog Prolems].
Index TableOfContents(2)
Problems 1-6
André Roberge has a zip file with solutions to the first six problems, in Crunchy format: [http://crunchy.googlecode.com/files/first_6_of_99_problems.zip First six]
Problem 7: Flatten a nested list structure
Based on the standard library documentation:
from itertools import chain
def flatten(listOfLists):
return list(chain(*listOfLists))The suggested solution does not work for a list like the following:
a_list = [0, 1, [2, 3], 4, 5, [6, 7]]
as the argument name tries to imply, it only works for a list of lists, not a generic list of variously and mixedly nested lists and items. Here's a more general solution using the simple recursive approach:
def flatten(nestedList):
def aux(listOrItem):
if isinstance(listOrItem, list):
for elem in listOrItem:
for item in aux(elem):
yield item
else:
yield listOrItem
return list(aux(nestedList))This problem is also a good example of "recursion elimination": explicitly maintain a LIFO stack of what sublists are being expanded so as to avoid actual recursion. The rec-elim approach is usually faster and avoids issues with recursion depth limits. Here's a version that works when it's OK to dismantle the input argument -- for variety, I have it build the result into another list by calls to .append, instead of using yield in an auxliary generator and calling list() on it.
def flatten(nestedList):
result = []
stack = [nestedList]
while stack:
if isinstance(stack[-1], list):
try: stack.append(stack[-1].pop(0))
except IndexError: stack.pop() # remove now-empty sublist
else:
result.append(stack.pop())
return resultIf you're not allowed to dismantle the input argument, you can take a preliminary copy.deepcopy of it as the initial item in the stack, or you can "pay as you go" by doing shallow copies "at the last minute" when needed. Here's an example of the latter approach, with other little variants. Here, stack is always a list of non-empty sublists which are shallow copies of sublists from the initial argument (and so the sublists on the stack can always be dismantled with no problems) while leaves (non-list subitems) are always immediately appended to the result (this, btw, builds up the result in a reversed way, so a call to result.reverse becomes necessary).
def flatten(nestedList):
result = []
if not nestedList: return result
stack = [list(nestedList)]
while stack:
current = stack.pop()
next = current.pop()
if current: stack.append(current)
if isinstance(next, list):
if next: stack.append(list(next))
else: result.append(next)
result.reverse()
return result
Problem 8: Eliminate consecutive duplicates of list elements
from itertools import groupby
def compress(alist):
return [key for key, group in groupby(alist)]
Problem 9: Pack consecutive duplicates of list elements into sublists
from itertools import groupby
def pack(alist):
return [list(group) for key, group in groupby(alist)]
Problem 10: Run-length encoding of a list
from itertools import groupby
def encode(alist):
return [[len(list(group)), key] for key, group in groupby(alist)]
Problem 11: Modified run-length encoding
def encode_modified(alist):
def aux(lg):
if len(lg)>1: return [len(lg), lg[0]]
else: return lg[0]
return [aux(list(group)) for key, group in groupby(alist)]
Problem 12: Decode a run-length encoded list
def decode(alist):
def aux(g):
if isinstance(g, list): return [(g[1], range(g[0]))]
else: return [(g, [0])]
return [x for g in alist for x, R in aux(g) for i in R]
Problem 13: Run-length encoding of a list (direct solution)
def encode_direct(alist):
def aux(k, g):
l = sum(1 for x in g)
if l>1: return [l, k]
else: return k
return [aux(key, group) for key, group in groupby(alist)]
Problem 14: Duplicate the elements of a list
def dupli(L):
return [x for x in L for i in (1,2)]
Problem 15: Duplicate the elements of a list a given number of times
def dupli(L, N):
return [x for x in L for i in range(N)]
Problem 16: Drop every N'th element from a list
def drop(L, N):
return [x for i,x in enumerate(L) if i%N != N-1]
Problem 17: Split a list into two parts; the length of the first part is given
def split(L, N):
return L[:N], L[N:]
Problem 18: Extract a slice from a list
Given two indices, I and K, the slice is the list containing the elements between the I'th and K'th element of the original list (both limits included). Start counting the elements with 1.
def slice(L, I, K):
return L[I-1:K]
Problem 19: Rotate a list N places to the left
def rotate(L, N):
return L[N:] + L[:N]
Problem 20: Remove the K'th element from a list
def remove_at(L, N):
return L[N-1], L[:N-1] + L[N:]
Problem 21: Insert an element at a given position into a list
def insert_at(x, L, N):
return L[:N-1]+[x]+L[N-1:]
Problem 22: Create a list containing all integers within a given range
def irange(I, J):
return range(I, J+1)
Problem 23: Extract a given number of randomly selected elements from a list
import random
def rnd_select(L, N):
return random.sample(L, N)
Problem 24: Lotto: Draw N different random numbers from the set 1
import random
def rnd_select(N, M):
return random.sample(range(1, M+1), N)
Problem 25: Generate a random permutation of the elements of a list
import random
def rnd_permu(L):
return random.sample(L, len(L))
Problem 26: Generate the combinations of K distinct objects chosen from the N elements of a list
def combination(K, L):
if K<=0:
yield []
return
for i in range(len(L)):
thisone = L[i:i+1]
for another in combination(K-1, L[i+1:]):
yield thisone + another
Problem 27: Group the elements of a set into disjoint subsets
A natural recursive approach requires "temporarily modifying" certain things (the main list, the list of sublists, the list of counts of remaining lengths desired in the sublists); one way to express this is by the `with' statement and the "resource allocation is initialization" (RAII) idiom it enables...:
from __future__ import with_statement
import contextlib
import itertools
def group(alist, glens):
# entries in glens are ints >0 summing to len(alist)
assert all(g>0 for g in glens)
assert sum(glens) == len(alist)
# return the generator made by an auxliary function
return _g(alist, glens, [ [] for g in glens ])
#
# helpers: with-statement contexts for RAII idioms
#
@contextlib.contextmanager
def popping(L):
item = L.pop()
yield item
L.append(item)
@contextlib.contextmanager
def appending(L, item):
L.append(item)
yield L
L.pop()
@contextlib.contextmanager
def decrementing(L, index):
L[index] -= 1
yield L
L[index] += 1
#
# helper: auxiliary recursive generator function
#
def _g(L, rls, grps):
if sum(rls) == 0:
yield list(list(grp) for grp in grps)
return
with popping(L) as item:
for i, (rl, grp) in enumerate(itertools.izip(rls, grps)):
if rl > 0:
with appending(grp, item):
with decrementing(rls, i):
for filled in _g(L, rls, grps):
yield filledHowever, the Zen of Python says that "flat is better than nested", and, of course, we can express _g in a much flatter way by giving up the nesting, e.g. as follows:
#
# helper: auxiliary recursive generator function
#
def _g(L, rls, grps):
if sum(rls) == 0:
yield list(list(grp) for grp in grps)
return
item = L.pop()
for i, (rl, grp) in enumerate(itertools.izip(rls, grps)):
if rl == 0: continue
grp.append(item)
rls[i] -= 1
for filled in _g(L, rls, grps):
yield filled
rls[i] += 1
grp.pop()
L.append(item)Which is more readable? "Ai posteri l'ardua sentenza..."!-)
Problem 28: Sorting a list of lists according to length of sublists
def lsort(L):
return sorted(L, key=len)
from collections import defaultdict
def lfsort(L):
lencounts = defaultdict(int)
for sublist in L: lencounts[len(sublist)] += 1
def bylenfreq(sublist): return lencounts[len(sublist)]
return sorted(L, key=bylenfreq)Note: there is no problem 29 in the original problem set
Note: there is no problem 30 in the original problem set
Problem 31: Determine whether a given integer number is prime
TODO: add a solution for this problem.
Problem 46: Print a truth table for a logical expression of two variables
def table(expr):
"""
print truth table for logical expression
>>> table('and(A,or(A,B))')
A B and(A,or(A,B))
True True True
True False True
False True False
False False False
"""
# uppercase functions to avoid name clashes with
# python reserved words
def AND(a,b): return a and b
def NAND(a,b): return not (a and b)
def OR(a,b): return a or b
def NOR(a,b): return not (a or b)
def XOR(a,b): return a ^ b
def EQU(a,b): return not (a ^ b)
def IMP(a,b): return b if a else True
format = "%-5s %-5s %-5s"
print format % ('A','B',expr)
expr = compile(expr.upper(),'<expression>','eval')
for A in (True,False):
for B in (True, False):
print format % (A, B, eval(expr,locals()))