def edit_ad(url):
    room = Room.query.filter_by(urlname=url).first()
    if not room and room.user == g.user:
        abort(404)
    if room.dead or get_days_ago(room.created_at) > OLD_DAYS.days:
        abort(404)
    occupied = Occupied.query.filter_by(space=room.occupieds).order_by("created_at").first()
    if occupied and get_days_ago(occupied.created_at) > OCCUPIED_DAYS.days:
        abort(404)
    if room.is_available:
        form = AvailableAdForm()
    else:
        form = WantedAdForm()
    form.starting.flags.is_date = True
    if request.method == "GET":
        form.process(obj=room)
        if room.is_available:
            form.room_pref.data = factorize(room.room_pref)
        else:
            form.room_type.data = factorize(room.room_type)
        form.email.data = g.user.email
    elif form.validate_on_submit():
        if room.is_available:
            form.room_pref.data = product(form.room_pref.data)
        else:
            form.room_type.data = product(form.room_type.data)
        form.populate_obj(room)
        db.session.commit()
        return redirect(url_for("view_ad", url=room.urlname))
    return render_template("autoform.html", form=form, title="Edit advertisement", submit="Save")

def post_ad(state="available"):
    is_available = state == "available"
    if is_available:
        form = AvailableAdForm()
    else:
        form = WantedAdForm()
    form.starting.flags.is_date = True
    if request.method == "GET":
        form.email.data = g.user.email
    if form.validate_on_submit():
        room = Room(user=g.user, is_available=is_available)
        if room.is_available:
            form.room_pref.data = product(form.room_pref.data)
        else:
            form.room_type.data = product(form.room_type.data)
        form.populate_obj(room)
        room.urlname = str(uuid4())[:8]
        db.session.add(room)
        db.session.commit()

        # Search for matching rooms
        rooms_distance = Room.search_rooms(room)
        # Send emails to interested users
        for r, distance in rooms_distance:
            if room.is_available:  # ad poster is looking for a person
                send_email_found_room(r.user, room, distance)
            else:  # ad poster is looking for a room.
                send_email_found_person(r.user, room, distance)

        flash("Your ad has been posted!", category="info")
        return render_template("found.html", room=room, rooms_distance=rooms_distance)
    return render_template("autoform.html", form=form, title="Post a new advertisement", submit="Post ad")

def baseline_KL(real_data, fake_data):
    """
    Calculate the Kullback-Leibler divergence from the null hypothesis (sample nouns and verbs according to frequency) to two sets of data
    :param real_data: first set of tuples
    :param fake_data: second set of tuples
    :return: (real KLs, fake KLs), each for (SVO, SV, VO) subsets
    """
    real_prob = separate_prob(real_data)
    fake_prob = separate_prob(fake_data)
    
    noun_prob = pred_freq * noun_mask / pred_freq[nouns].sum()
    verb_prob = pred_freq * verb_mask / pred_freq[verbs].sum()
    both_prob = noun_prob + verb_prob
    
    real_match = [{tup: product(both_prob[p] for p in tup)
                   for tup in c}
                  for c in real_prob]
    fake_match = [{tup: product(both_prob[p] for p in tup)
                   for tup in c}
                  for c in fake_prob]
    
    real_KL = [KL(real_prob[i], real_match[i]) for i in range(3)]
    fake_KL = [KL(fake_prob[i], fake_match[i]) for i in range(3)]

    return real_KL, fake_KL
    

def cell_likelihood(reads,ps):
    points = sorted(concat(reads))
    G = len(ps)
    if not 0 in points:
        points.append(0)
    if not G in points:
        points.append(G)
    read_complements = [(stop)]
    return product([product(1-p for p in ps[start:stop]) for (start,stop) in reads])

def productGen( matrix ):
    n = 20
    for i in xrange( n ):
        for j in xrange( n ):
            V, Vb = j <= 16, j >= 3
            H, Hb = i <= 16, i >= 3
            if V:
                yield product( matrix[ i ][ j + k ] for k in xrange( 4 ) )
            if H:
                yield product( matrix[ i + k ][ j ] for k in xrange( 4 ) )
            if H and V:
                yield product( matrix[ i + k ][ j + k ] for k in xrange( 4 ) )
            if Hb and V:
                yield product( matrix[ i - k ][ j + k ] for k in xrange( 4 ) )

 def _weight_variable(shape, name):
     # If shape is [5, 5, 20, 32], then each of the 32 output planes
     # has 5 * 5 * 20 inputs.
     number_inputs_added = utils.product(shape[:-1])
     stddev = 1 / math.sqrt(number_inputs_added)
     # http://neuralnetworksanddeeplearning.com/chap3.html#weight_initialization
     return tf.Variable(tf.truncated_normal(shape, stddev=stddev), name=name)

def diagonal_left_right_max(A, length):
  M = len(A)
  N = len(A[0])
  prods = [[0 for j in range(N-length)] for i in range(M-length)]
  for i in range(M-length):
    for j in range(N-length):
      prods[i][j] = product(A[i+x][j+x] for x in range(length))
  return max(max(row) for row in prods)

def horizontal_max(A, length):
  M = len(A)
  N = len(A[0])
  prods = [[0 for j in range(N-length)] for i in range(M)]
  for i in range(M):
    for j in range(N-length):
      prods[i][j] = product(A[i][j:j+length])
  return max(max(row) for row in prods)

def get_lcm(l):
    factor_lists = [get_prime_factors(e) for e in l]
    factors = get_factor_set(factor_lists)
    d = defaultdict(int)
    for factor in factors:
        for fl in factor_lists:
            if fl.count(factor) > d[factor]:
                d[factor] = fl.count(factor)
    return product([k**v for k,v in d.items()])

 def propensity(self, stoich_vector, rate_constant):
     choices = [choose(x_j, -v_j) for x_j, v_j in zip(self.state, stoich_vector) if v_j < 0]
     # print choices
     propensity = rate_constant * product(choices)
     # print "state:",self.state,"stoich:",stoich_vector,"rate const:",rate_constant,"prop:",propensity
     if propensity < 0:
         print "propensity less than zero:", stoich_vector, rate_constant
         raise Exception
     return propensity

def do( N ):
    ways = ( choose( 25, N )
             * product( xrange( 75, 100 - N ) )
             * fact( 75 ) )

    all = fact( 100 )
    ret = ways * 10 ** 50 / all
    import sys
    print >>sys.stderr, (ret, N)
    return ret

def main():
    N = 12000
    mps, results = [maxint for i in xrange(N - 1)], set()
    for x in xrange(4, 2 * N + 1):
        for factors in factorizations(x):
            k = len(factors) + product(factors) - sum(factors)
            if k > 1 and k <= N:
                mps[k - 2] = min(mps[k - 2], x)
    for number in mps:
        results.add(number)
    print sum(results)

def make_onehot(feature, planes):
    onehot_features = np.zeros(feature.shape + (planes,), dtype=np.uint8)
    capped = np.minimum(feature, planes)
    onehot_index_offsets = np.arange(0, product(
        onehot_features.shape), planes) + capped.ravel()
    # A 0 is encoded as [0,0,0,0], not [1,0,0,0], so we'll
    # filter out any offsets that are a multiple of $planes
    # A 1 is encoded as [1,0,0,0], not [0,1,0,0], so subtract 1 from offsets
    nonzero_elements = (capped != 0).ravel()
    nonzero_index_offsets = onehot_index_offsets[nonzero_elements] - 1
    onehot_features.ravel()[nonzero_index_offsets] = 1
    return onehot_features

def factorizations(x):
    factorization, listes = factors(x), [[x]]
    for n_factors in range(1, len(factorization)):
        for combination in combinations(factorization, n_factors):
            p = product(combination)
            for facto in factorizations(x / p):
                liste = [p]
                liste.extend(facto)
                liste = sorted(liste)
                if liste not in listes:
                    listes.append(liste)
    return listes

def compare_KL(model, real_data, fake_data, samples=(100,100,100), **kwargs):
    """
    Approximately calculate the Kullback-Leibler divergence from the model to two sets of data
    :param model: the sem-func model
    :param real_data: first set of tuples
    :param fake_data: second set of tuples
    :param samples: number of samples to draw, for: SVO, SV, VO graphs
    :return: (real KLs, fake KLs), each for (SVO, SV, VO) subsets
    """
    # Get sample probabilities from the data
    real_prob = separate_prob(real_data)
    fake_prob = separate_prob(fake_data)
    
    # Initialise counts for generated samples
    real_match = [{tup: 0 for tup in c} for c in real_prob]
    fake_match = [{tup: 0 for tup in c} for c in fake_prob]
    
    # Sample from the model
    sampler = [model.sample_background_svo, model.sample_background_sv, model.sample_background_vo]
    
    for i in range(3):
        # Sample entities for each graph configuration
        for ents in sampler[i](samples=samples[i], **kwargs):
            # For the sampled entities, find the distribution over predicates
            pred_dist = [model.pred_dist(e) for e in ents]
            # Add the probability that this sample would generate the observed predicates
            for preds in real_match[i]:
                real_match[i][preds] += product(pred_dist[j][p] for j,p in enumerate(preds))
            for preds in fake_match[i]:
                fake_match[i][preds] += product(pred_dist[j][p] for j,p in enumerate(preds))
        # Average the probabilities
        for preds in real_match[i]:
            real_match[i][preds] /= samples[i]
        for preds in fake_match[i]:
            fake_match[i][preds] /= samples[i]
    
    real_KL = [KL(real_prob[i], real_match[i]) for i in range(3)]
    fake_KL = [KL(fake_prob[i], fake_match[i]) for i in range(3)]

    return real_KL, fake_KL

def index(request):
    values_strings = request.GET.getlist('values')
    try:
        values_ints = map(int, values_strings)
    except ValueError as e:
        err_result = {'details': str(e) }
        err_result.update(ERROR_MSG_INVALID_INPUT)
        json_output = json.dumps(err_result)
        return HttpResponse(json_output, status=400)
    vsum = sum(values_ints)
    vproduct = product(values_ints)
    json_output = json.dumps({'sum': vsum, 'product': vproduct})
    return HttpResponse(json_output)

def markov_blanket_sample(X, e, bn):
    """Return a sample from P(X | mb) where mb denotes that the
    variables in the Markov blanket of X take their values from event
    e (which must assign a value to each). The Markov blanket of X is
    X's parents, children, and children's parents."""
    Xnode = bn.variable_node(X)
    Q = ProbDist(X)
    for xi in bn.variable_values(X):
        ei = extend(e, X, xi)
        # [Equation 14.12:]
        Q[xi] = Xnode.p(xi, e) * product(Yj.p(ei[Yj.variable], ei)
                                         for Yj in Xnode.children)
    # (assuming a Boolean variable here)
    return probability(Q.normalize()[True])

 def bayes(self, party, party_tweets, sample_freq_list):
     prob_of_party = len(party_tweets) / len(self.tweets)
     feature_probs = []
     # iterate over every word (boolean flag)
     for i in xrange(0, len(sample_freq_list)):
         # P(A|B) = P(B|A) * P(A) / P(B)
         # P(match|party) = P(party|match) * P(match) / P(party)
         #                = P(match)
         # because we're only looking at the party's tweets
         matching_fn = lambda test_tweet: test_tweet.freq_list[i] == sample_freq_list[i]
         matching_tweets = filter(matching_fn, party_tweets)
         probability = len(matching_tweets) / len(party_tweets)
         feature_probs.append(probability)
     combined = prob_of_party * utils.product(feature_probs)
     return combined

def statistical_mutual_information(ngram, text):
    """
    Return the probability of all the terms of the ngram to appear together.
    Do we may consider the stop_words ?
    """
    candidates = [(k, v) for k, v in enumerate(ngram) if normalize_token(v) not in stop_words \
                  and not v.isdigit() and len(v) > 1]
    alone_count = {}
    if len(candidates) == 0: return 0.1
    for candidate in candidates:
        next = candidates.index(candidate) < len(candidates) - 1 \
               and candidates[candidates.index(candidate) + 1] \
               or None
        previous = candidates.index(candidate) > 0 \
               and candidates[candidates.index(candidate) - 1] \
               or None
        alone_count[candidate] = 0
        indexes = [ idx for idx, value in enumerate(text) if value == candidate[1] ]
        for idx in indexes:
            if next is not None:
                positions_diff = next[0] - candidate[0]
                if idx >= len(text) - (positions_diff + 1) \
                   or not text[idx+positions_diff] == next[1]:
                    #we are close end of text, next can't be found
                    alone_count[candidate] += 1
            if previous is not None:
                positions_diff = candidate[0] - previous[0]
                if idx < positions_diff \
                   or not text[idx-positions_diff] == previous[1]:
                    #we are close beggin of text, preivous can't be found
                    alone_count[candidate] += 1
    res = [v for k,v in alone_count.items()]
#    print [v for v in alone_count.items()]
    if 0 in res:
        return 1
    else:
        return product([1.0 * len(ngram) / (len(ngram) + v) for v in res])

def original_solution():
    """ original_solution took 584.394 ms
              584.394 ms (write is_int inline instead of as a function call)
              741.234 ms (build a table of funcs instead of eval inline)
            13419.094 ms (intuition: solution won't have a 0 in it (useless!))
            20296.724 ms (intuition: solution needs to have 1 in it)
            50730.742 ms (save list of all operator combos instead of dynamic generation)
            51467.405 ms (format instead of 3 string replaces)
            53080.543 ms (essential set of combos)
            91008.076 ms (initial)
        The answer (original) is: 1258
    """
    # all possible combinations of operators
    olist = [p for p in product(['+', '-', '*', '/'], repeat=3)] 
    # all possible parenthesizations
    combos = ['(a %c (b %c c)) %c d', '((a %c b) %c c) %c d', 'a %c (b %c (c %c d))', 'a %c ((b %c c) %c d)', '(a %c b) %c (c %c d)']
    # all possible functions
    funcs = [eval('lambda a,b,c,d : %s' % (c % o)) for c in combos for o in olist]  
    
    m, answer = 0, ''
    for numbers in combinations(xrange(1, 10), 4):
        if not 1 in numbers: continue # intuition about requirements for solution
        outcomes = set()
        for a,b,c,d in permutations(numbers):
            for f in funcs:
                try:
                    n = f(a,b,c,d)
                    if 0 < n and int(n) == n:
                        outcomes.add(n)
                except ZeroDivisionError:
                    pass
        lcr = largest_continuous_range(sorted(outcomes)) #lcr = largest_continuous_range_new(outcomes)
        if m < lcr:
            m, answer = lcr, ''.join(map(str, numbers))
            print 'new max: %d from %s' % (m, answer)
    return answer