# DM01 F98, ugeseddel 5
#
# Eksamen 1997.juni

# opg 1a)

def rempar(A):
  xi,xj = 0,1
  for i in range(len(A)-1):
    for j in range(i+1,len(A)):
      if abs(A[i]-A[j]) < abs(A[xi]-A[xj]):
	xi,xj = i,j
  x,y = A[xi],A[xj]
  del A[xj],A[xi]
  return (x,y)

# en anden måde at gøre det på:
def rempar2(A):
  A.sort()
  xi = 0
  for i in range(1,len(A)-1):
    if A[i+1]-A[i] < A[xi+1]-A[xi]:
      xi = i
  x,y = A[xi],A[xi+1]
  del A[xi:xi+2]
  return (x,y)
  

# opg 1b)

# Rekursiv udgave
def remseqR(s):
  if len(s) <= 1:
    return s[:]
  else:
    if s[0] == s[1]:
      return remseqR(s[1:])
    else:
      return [s[0]] + remseqR(s[1:])

# Ikke-rekursiv (iterativ) udgave
def remseqI(s):
  t = s[:]
  i = 0
  while i < len(t)-1:
    if t[i] == t[i+1]:
      del t[i]
    else:
      i = i + 1
  return t


# opg 2a)

# Til KasseType kan bruges tupler sammen med
rumf, vaegt = 0,1
# således at kt[rumf] = rumfanget af en kasse
# Til Forsendelse kan bruges en liste af KasseType

def accept(f, R, V):
  if len(f) == 0:
    return R >= 0 and V >= 0
  else:
    kasse = f[0]
    return accept(f[1:], R-kasse[rumf], V-kasse[vaegt])


# opg 2b)

def grd(emner, R, V):
  if emner == []:
    return []
  else:
    if accept([emner[0]], R, V):
      return [emner[0]] + grd(emner[1:], R-emner[0][rumf], V-emner[0][vaegt])
    else:
      return grd(emner[1:], R, V)

# 3b)

# Til WhiskyType bruges igen tupler med:
navn, kar = 0,1
# hvor w[kar] er en liste af {0,1}
# Til KlasseType bruges igen tupler med:
elm, antal, middel = 0,1,2
# og hvor elm implementeres som en liste af WhiskyType,
# mens middel implementeres som en liste af tal

def forening(K,L):
  # jeg forudsætter, at K og L er disjunkte klasser
  ny_elm   = K[elm]   + L[elm]
  ny_antal = K[antal] + L[antal]
  ny_middel = []
  for i in range(68):
    ny_middel.append( (K[antal] * K[middel][i] + L[antal] * L[middel][i])/ \
		             (K[antal] + L[antal]))

  return (ny_elm, ny_antal, ny_middel)


# 3c)

from math import sqrt

def afstand(K,L):
  sum = 0

  for i in range(68):
    sum = sum + (K[middel][i] - L[middel][i])**2

  return sqrt(sum)


# 3d)

# Igen kan typen Klassedeling implementeres som en liste af klasseType

def start_inddeling(W):
  si = []
  for w in W:
    si.append(([w],1,w[kar]))
  return s


# 3f)

def step(W):
  if len(W) > 1:
    w1, w2 = W[0], W[1]

    for i in range(len(W)):
      for j in range(i+1,len(W)):
	if afstand(W[i],W[j]) < afstand(w1,w2):
	  w1,w2 = W[i],W[j]

    W.remove(w1)
    W.remove(w2)
    W.append(forening(w1,w2))

  return W


# 3g)

def klassifikation(W):
  K = start_inddeling(W)
  
  while len(K) >= 2:
    step(K)

  return K