# Copyright (c) 2009 Tim Freeman
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.
#
# (This is the standard MIT License, copied from
# http://www.opensource.org/licenses/mit-license.php on 24 Apr 2007.)

from physics import Speed_prior_explanation
from compile_and_run import compile_and_run
from compile import turing_program, turing_compile
from constants import left, right, end, done, truncate
from turing_tape import turing_tape, binarytape
from machine import turing, empty_tape
from speed_prior import Speed_prior
from answerer import next_video_frame, predict_video, \
     answer_questions_npbug, PastMoment, QuestionAnswer, \
     predicts_npbug, two_hypothesis_generator, predict_qna, \
     predicts_nonpbug, answer_questions_nonpbug
from test_util import assert_equals, expect_exception, assert_in
from mpmath import mpf

from answerer import dict_to_tuple, sequence_to_dict
assert dict_to_tuple({"a": 3, "b": 4}) in  \
       [(("a",3), ("b", 4)), (("b", 4), ("a",3))]
 
assert sequence_to_dict((("a",3), ("b", 4)),) == {"a": 3, "b": 4}

# constant_hypothesis(n) works when n is 0 or 1.  It returns the speed
# prior hypothesis that predicts that the video frame will always be
# one bit, specifically n.
# We have to return a tuple consisting of the new state (which can be
# empty) and the predicted video frame.
# Thus our output tape has to be:
#    cell3:0 cell2:c # The bit c, with a 0 bloating it because it's in a tuple
#    cell1:1 cell0:0 # Tuple separator
#    <empty new state>
# where I labelled the tape cells with the name of the state in the
# Turing machine below that writes the cell.
impossible = (truncate, right, "impossible")

def constant_hypothesis_absyn(c):
    return turing_program(
        "cell0",
        cell0={end: (0, left, "cell1"), (0, 1): impossible},
        cell1={end: (1, left, "cell2"), (0, 1): impossible},
        cell2={end: (c, left, "cell3"), (0, 1): impossible},
        cell3={end: (0, left, "done"), (0, 1): impossible},
        done={end: done, (0, 1): impossible},
        # Error handling.  Truncating when we are off the right end of
        # the tape provokes an error.
        impossible={(0,1,end): impossible})

def constant_hypothesis(c):
    return Speed_prior(logtime=3, absyn=constant_hypothesis_absyn(c))

h0 = constant_hypothesis(0)
h1 = constant_hypothesis(1)

assert_equals(h0.run(empty_tape), binarytape("0010"))
assert_equals(h1.run(empty_tape), binarytape("0110"))

t0 = binarytape("0")
t1 = binarytape("1")
assert_equals(next_video_frame(h0, [t0]), t0)
assert_equals(next_video_frame(h0, []), t0)
assert_equals(next_video_frame(h1, []), t1)
assert_equals(next_video_frame(h1, [t1,t1,t1]), t1)
assert_equals(next_video_frame(h0, [t0,t0,t0,t0]), t0)
expect_exception(lambda: next_video_frame(h0, [t0,t0,t1,t0]))
expect_exception(lambda: next_video_frame(h1, [t0]))

# flip_hypothesis works when n is 0 or 1.  It returns a speed prior
# hypothesis that says the bit that is the video frame will alternate
# between the values 0 and 1, starting with the value n.
# We'll use the state to track the prediction we made last time.
# The input tape is the previous state.  If it is <b>, where b is 0 or 1, 
# then our output is:
#    cell5:0 cell4b:1-b # The predicted frame of video
#    cell3b:1 cell2b:0  # Tuple separator
#    cell1b:0 cell0:1-b # The new state
# where I labelled the tape cells with the names of the states that
# generate them.  cell3b, for example, is an abbreviation for two
# states, cell30 and cell31.
# 
# If our input is the empty tape, we have to have the same output
# except b is 1-n.
def flip_hypothesis(n):
    other = 1 - n
    if n == 0:
        firstcell = "cell11"
    else:
        assert n == 1
        firstcell = "cell10"
    impossible = (truncate, right, "impossible")
    return Speed_prior(logtime=4, absyn=turing_program(
        "cell0",
        cell0={0:(1, left, "cell10"), 1:(0, left, "cell11"),
               # The first time, the state is empty, and we have to
               # look at n to decide where to go.
               end:(n, left, firstcell)},
        cell10={end:(0, left, "cell20"), (0, 1): impossible},
        cell11={end:(0, left, "cell21"), (0, 1): impossible},
        cell20={end:(0, left, "cell30"), (0, 1): impossible},
        cell21={end:(0, left, "cell31"), (0, 1): impossible},
        cell30={end:(1, left, "cell40"), (0, 1): impossible},
        cell31={end:(1, left, "cell41"), (0, 1): impossible},
        cell40={end:(1, left, "cell5"), (0, 1): impossible},
        cell41={end:(0, left, "cell5"), (0, 1): impossible},
        cell5={end:(0, left, "done"), (0, 1): impossible},
        done={end:done, (0, 1): impossible},
        impossible={(0,1,end): impossible}))

f0 = flip_hypothesis(0)
assert_equals(f0.run(binarytape("")), binarytape("001000"))
assert_equals(f0.run(binarytape("0")), binarytape("011001"))
assert_equals(f0.run(binarytape("1")), binarytape("001000"))

f1 = flip_hypothesis(1)
assert_equals(f1.run(binarytape("")), binarytape("011001"))
assert_equals(f1.run(binarytape("1")), binarytape("001000"))
assert_equals(f1.run(binarytape("0")), binarytape("011001"))

assert_equals(next_video_frame(f0, []), t0)
assert_equals(next_video_frame(f1, []), t1)
assert_equals(next_video_frame(f0, [t0]), t1)
assert_equals(next_video_frame(f0, [t0, t1, t0]), t1)
expect_exception(lambda: next_video_frame(f0, [t0,t0,t1,t0]))

hypotheses = [h0, h1, f0, f1]

def sham_generator_from_list(l):
    def sham_generator(size):
        return [h for h in l if h.size() == size]
    return sham_generator

sham_generator = sham_generator_from_list(hypotheses)

epsilon = mpf(2)**-500

assert_equals(predict_video([], epsilon, sham_generator),
              {t0: mpf('0.5'), t1: mpf('0.5')})
d = predict_video([t1, t0], epsilon, sham_generator)
assert t1 in d
assert t0 not in d
# The next one loops because our sham generator never returns anything
# that matches.
#print predict_video([t1, t0, t0], epsilon, sham_generator)

# Exercise the prefix check.
h0plusjunk_absyn = constant_hypothesis_absyn(0)
# The states are alphabetized before they are compiled,
# except the start state is always first.  Thus it is important
# that zjunk is alphabetically after all of the states already present
# in constant_hypothesis_absyn(0).
h0plusjunk_absyn.states["zjunk"] = {(0,1,end): impossible}
h0plusjunk = Speed_prior(logtime=3, absyn=h0plusjunk_absyn)
assert h0.is_prefix(h0plusjunk)
assert not h0plusjunk.is_prefix(h0)
assert not h0.is_prefix(h1)
assert not h1.is_prefix(h0plusjunk)
# It's also a prefix if we keep the program the same and let it run longer.
h0plusjunk2 = Speed_prior(logtime=4, absyn=constant_hypothesis_absyn(0))
assert h0.is_prefix(h0plusjunk2)
assert not h0plusjunk2.is_prefix(h0)

from speed_prior import prefix_in
assert prefix_in([h0, h1], h0)
assert prefix_in([h0, h1], h0plusjunk)
assert prefix_in([h0, h1], h0plusjunk2)
assert not prefix_in([h0plusjunk, h1, f1], h0)

newhypotheses = [h0plusjunk2, h0plusjunk]
sham_generator_2 = sham_generator_from_list(hypotheses + newhypotheses)
# Because of the prefix check, the extra possible hypotheses doesn't change
# the result.
assert_equals(predict_video([], epsilon, sham_generator)[t0],
              predict_video([], epsilon, sham_generator_2)[t0])
# Control experiment, so we don't accidentally pass if the limited
# precision of our floating point numbers causes things to be the same
# when they shouldn't be.

# impossible2 isn't as good an impossible state as impossible, since
# it will grow the tape forever instead of failing by truncating past
# the right end.  However, we don't reach it in these tests, and the
# time limit for turing programs is low anyway, so it doesn't matter.
impossible2 = (truncate, left, "impossible")
h0p_absyn = constant_hypothesis_absyn(0)
h0p_absyn.states["impossible"] = {(0, 1, end): impossible2}
h0p = Speed_prior(logtime=3, absyn=h0p_absyn)
# The impossible state is never reached, so h0p behaves the same as
# h0, but it isn't a prefix.
assert not h0.is_prefix(h0p)
assert not h0p.is_prefix(h0)
assert not h0p.is_prefix(h0plusjunk)
assert not h0p.is_prefix(h0plusjunk2)
hypothesesp = [h0p, h1, f0, f1]
sham_generator_3 = sham_generator_from_list(hypothesesp)
sham_generator_4 = sham_generator_from_list(hypothesesp + newhypotheses)
# The prefix check doesn't happen, so they should be different.
assert predict_video([], epsilon, sham_generator_3)[t0] != \
              predict_video([], epsilon, sham_generator_4)[t0]

# Exercise answer_questions_npbug.
# Need to devise some physics and question/answer pairs that
# illustrate the novice philosopher bug.

# We saw two frames of video: <1> and then <0>.
# There are four equally likely hypotheses concerning the physics:

# Two hypotheses claiming it alternates, <1> <0> <1> <0> ... .  One
# represents the state as the last frame of video seen, and one
# represents the state as the current frame of video seen.

# The other two hypothesis will predict that <1> <0> <0> <0> ...,
# where the rest are all <0> and the first state is an execption.
# Adjust things so these two hypotheses have the same complexity as
# the previously mentioned two, and these two hypotheses are different
# from each other.

# This is contrived so the next bit has 50% estimated probability of
# being 0 and 50% estimated probability of being 1.

# For question answering, we only have one question, and it means
# "What will be the next frame of video?".  We'll have four
# hypotheses: one that returns the current state, one that returns the
# complement of the current state (with some added complexity), and
# two that predict always 0 when faced with the
# first-frame-is-an-exception physics but make no prediction when
# presented with either alternating-frame physics.

# To ensure they make no prediction when presented with either
# alternating-frame physics, make them fail if they see that the state
# is 1.

# We ask the question for the timestep number 0, and the correct
# answer is <0>.

# Given these hypotheses, the right guess about the future answer to
# the question is 50% 0 and 50% 1, and the version with the novice
# philosopher bug should get it wrong.

# We need to have another bit in the representation of the state
# so we can get rid of the hypotheses for answering questions that are
# meant to pertain to the constant physics version.  This is in cells
# 2 and 3.
# Initially, b is 1.
#    cell7:0 cell6b:1-b # The predicted frame of video
#    cell5b:1 cell4b:0  # Tuple separator
#    cell3b:0 cell2b:0  # Label saying it's toggling.
#    cell1b:0 cell0:1-b # The new state
physics_simple = Speed_prior(logtime=4, absyn=turing_program(
        "cell0",
        cell0={0:(1, left, "cell10"), 1:(0, left, "cell11"),
               # The first time, the state is empty.
               end:(1, left, "cell10")},
        cell10={(end, 0):(0, left, "cell20"), 1: impossible},
        cell11={(end, 0):(0, left, "cell21"), 1: impossible},
        cell20={end:(0, left, "cell30"), (0, 1): impossible},
        cell21={end:(0, left, "cell31"), (0, 1): impossible},
        cell30={end:(0, left, "cell40"), (0, 1): impossible},
        cell31={end:(0, left, "cell41"), (0, 1): impossible},
        cell40={end:(0, left, "cell50"), (0, 1): impossible},
        cell41={end:(0, left, "cell51"), (0, 1): impossible},
        cell50={end:(1, left, "cell60"), (0, 1): impossible},
        cell51={end:(1, left, "cell61"), (0, 1): impossible},
        cell60={end:(1, left, "cell7"), (0, 1): impossible},
        cell61={end:(0, left, "cell7"), (0, 1): impossible},
        cell7={end:(0, left, "done"), (0, 1): impossible},
        done={end:done, (0, 1): impossible},
        impossible={(0,1,end): impossible}))
assert_equals(physics_simple.run(binarytape("")), binarytape("01100001"))
assert_equals(physics_simple.run(binarytape("01")), binarytape("00100000"))
assert_equals(predict_video([t1,t0,t1,t0], epsilon,
                            sham_generator_from_list([physics_simple])),
              {t1: 1.0})

# Like physics_simple, except the internal state has the bit flipped.
# Initially, b is 0.
#    cell7:0 cell6b:b   # The predicted frame of video
#    cell5b:1 cell4b:0  # Tuple separator
#    cell3b:0 cell2b:0  # Label saying it's toggling.
#    cell1b:0 cell0:1-b # The new state
physics_swapped = Speed_prior(logtime=4, absyn=turing_program(
        "cell0",
        cell0={0:(1, left, "cell10"), 1:(0, left, "cell11"),
               # The first time, the state is empty.
               end:(0, left, "cell11")},
        cell10={(end, 0):(0, left, "cell20"), 1: impossible},
        cell11={(end, 0):(0, left, "cell21"), 1: impossible},
        cell20={end:(0, left, "cell30"), (0, 1): impossible},
        cell21={end:(0, left, "cell31"), (0, 1): impossible},
        cell30={end:(0, left, "cell40"), (0, 1): impossible},
        cell31={end:(0, left, "cell41"), (0, 1): impossible},
        cell40={end:(0, left, "cell50"), (0, 1): impossible},
        cell41={end:(0, left, "cell51"), (0, 1): impossible},
        cell50={end:(1, left, "cell60"), (0, 1): impossible},
        cell51={end:(1, left, "cell61"), (0, 1): impossible},
        cell60={end:(0, left, "cell7"), (0, 1): impossible},
        cell61={end:(1, left, "cell7"), (0, 1): impossible},
        cell7={end:(0, left, "done"), (0, 1): impossible},
        done={end:done, (0, 1): impossible},
        impossible={(0,1,end): impossible}))
assert_equals(physics_swapped.run(binarytape("")), binarytape("01100000"))
assert_equals(physics_swapped.run(binarytape("00")), binarytape("00100001"))
assert_equals(predict_video([t1,t0,t1,t0], epsilon,
                            sham_generator_from_list([physics_swapped])),
              {t1: 1.0})
assert_equals(physics_swapped.measure(), physics_simple.measure())

# Predict t1, t0, t0, t0, t0, ...
# If the tape is empty, give <1> for the video and put a <0> as the
# state.
# That is, return:
#   cell7:0(tuple pad) cell6e:1(video)
#   cell5e:1 cell4e:0(two bits of tuple separator)
#   cell3e:0(tuple pad) cell2e:1(label saying it's constant)
#   cell1e:0(tuple pad) cell0:0(new state)
# If the tape is not empty, give <0> for the video and <0> as the state.
# That is, return:
#   cell7:0(tuple pad) cell60:0(video)
#   cell50:1 cell40:0(two bits of tuple separator)
#   cell30:0(tuple pad) cell20:1(label saying it's constant)
#   cell10:0(tuple pad) cell0:0(new state)
# I want two of these, and I want them to have the same measure as
# physics_simple.
def gen_physics_constant(garbagebit):
    return Speed_prior(logtime=4, absyn=turing_program(
        "cell0",
        cell0={0:(0, left, "cell10"), end:(0, left, "cell1e"), 1:impossible},
        cell10={1:(0, left, "cell20"), (0, end): impossible},
        cell1e={end:(0, left, "cell2e"), (0, 1): impossible},
        cell20={end:(1, left, "cell30"), (0, 1): impossible},
        cell2e={end:(1, left, "cell3e"), (0, 1): impossible},
        cell30={end:(0, left, "cell40"), (0, 1): impossible},
        cell3e={end:(0, left, "cell4e"), (0, 1): impossible},
        cell40={end:(0, left, "cell50"), (0, 1): impossible},
        cell4e={end:(0, left, "cell5e"), (0, 1): impossible},
        cell50={end:(1, left, "cell60"), (0, 1): impossible},
        cell5e={end:(1, left, "cell6e"), (0, 1): impossible},
        cell60={end:(0, left, "cell7"), (0, 1): impossible},
        cell6e={end:(1, left, "cell7"), (0, 1): impossible},
        cell7={end:(0, left, "done"),
               # Make use of garbagebit so we have two different hypotheses.
               0: (garbagebit, right, "impossible"),
               1: impossible},
        done={end:done, (0, 1): impossible},
        impossible={(0,1,end): impossible}))

physics_constant_0 = gen_physics_constant(0)
physics_constant_1 = gen_physics_constant(1)
assert_equals(physics_constant_0.run(binarytape("")), binarytape("01100100"))
assert_equals(physics_constant_0.run(binarytape("10")), binarytape("00100100"))
assert_equals(predict_video([t1,t0,t0,t0], epsilon,
                            sham_generator_from_list([physics_constant_0])),
              {t0: 1.0})
assert_equals(predict_video([t1,t0,t0,t0], epsilon,
                            sham_generator_from_list([physics_constant_1])),
              {t0: 1.0})
assert physics_constant_0 != physics_constant_1
assert not physics_constant_0.is_prefix(physics_constant_1)
assert not physics_constant_1.is_prefix(physics_constant_0)
assert_equals(physics_constant_0.measure(), physics_constant_1.measure())
assert_equals(physics_constant_0.measure(), physics_simple.measure())

physics_npbug_generator = sham_generator_from_list([
    physics_constant_0, physics_constant_1, physics_simple, physics_swapped])

# The two probabilities for the next possible one-bit predictions should be
# equal to 0.5.
assert_equals(predict_video([t1, t0], epsilon, physics_npbug_generator),
              {t0: 0.5, t1: 0.5})

# We only support one question: "What is the next frame of video?"
# So if we're predicting alternation, and we ask after seeing <1> <0>,
# the correct answer is <1>.

# question_simple answers it correctly if our physics is physics_simple.
# The input will be a tuple with the question and the state:
#    <don't care what the question is> (But it should have tuple padding interspersed)
#    1 0 (tuple separator)
#    0 cell2:0 (tuple padding and label saying it's toggling)
#    cell1:0 start:<state>
# The state we're given is the state after the physics updates it, so
# the correct answer to the question is just the state.
question_simple = Speed_prior(logtime=3, absyn=turing_program(
    "start",
    start={0:(1, left, "cell1"), 1:(0, left, "cell1"), end: impossible},
    cell1={0:(0, left, "cell2"), (1, end): impossible},
    cell2={0:(truncate, right, "cell1again"), (1, end): impossible},
    cell1again={0:(truncate, right, "done"), (1, end): impossible},
    done={(0, 1):done, end: impossible},
    impossible={(0, 1, end): impossible}))
assert_equals(question_simple.run(binarytape("01010100000")), t1)
assert_equals(question_simple.run(binarytape("10101100001")), t0)
# Next two should fail because the bit says it's a constant physics
# state, not a toggling physics state.
assert_in("Truncate when past right",
          expect_exception(lambda:question_simple.run(binarytape("01010100100"))))
assert_in("Truncate when past right",
          expect_exception(lambda:question_simple.run(binarytape("10101100101"))))
def sham_pair_generator(pairs):
    def sham_generator(size):
        return [Speed_prior_explanation(explanations=p)
                for p in pairs if p[0].size() + p[1].size() == size]
    return sham_generator
history = [PastMoment(video=t1,
                      qa=[QuestionAnswer(question=empty_tape,
                                         answer=t0)]),
           PastMoment(video=t0, qa=[])]
simple_qa_explanation = Speed_prior_explanation(
    explanations=(physics_simple, question_simple))
assert_equals(predicts_npbug(simple_qa_explanation, history, empty_tape), t1)

# Require it to predict a video of t0 when it won't.
history0 = [PastMoment(video=t0,
                      qa=[QuestionAnswer(question=empty_tape, answer=t0)]),
           PastMoment(video=t0, qa=[])]
assert_in("Bad prediction of the video",
          str(expect_exception(lambda:predicts_npbug(simple_qa_explanation,
                                                     history0, empty_tape))))

# Put t1 as an answer when it won't match.
history1 = [PastMoment(video=t1,
                      qa=[QuestionAnswer(question=empty_tape, answer=t1)]),
           PastMoment(video=t0, qa=[])]
assert_in("Bad answer to a question",
          str(expect_exception(lambda:predicts_npbug(simple_qa_explanation,
                                                     history1, empty_tape))))

def exercise_answer_npbug(pairs):
    generator = sham_pair_generator(pairs)
    return answer_questions_npbug(history, question=binarytape(""),
                                     epsilon=epsilon,
                                     generator=generator)

assert_equals(exercise_answer_npbug([(physics_simple, question_simple)]),
              {t1: 1.0})

question_swapped = Speed_prior(logtime=3, absyn=turing_program(
    "start",
    start={0:(0, left, "cell1"), 1:(1, left, "cell1"), end: impossible},
    cell1={0:(0, left, "cell2"), (1, end): impossible},
    cell2={0:(truncate, right, "cell1again"), (1, end): impossible},
    cell1again={0:(truncate, right, "done"), (1, end): impossible},
    # Pad the simplicity.
    junk={(end,0,1): impossible}, 
    done={(0, 1):done, end: impossible},
    impossible={(0, 1, end): impossible}))
question_swapped_unpadded = Speed_prior(logtime=3, absyn=turing_program(
    "start",
    start={0:(0, left, "cell1"), 1:(1, left, "cell1"), end: impossible},
    cell1={0:(0, left, "cell2"), (1, end): impossible},
    cell2={0:(truncate, right, "cell1again"), (1, end): impossible},
    cell1again={0:(truncate, right, "done"), (1, end): impossible},
    done={(0, 1):done, end: impossible},
    impossible={(0, 1, end): impossible}))
assert question_swapped.measure() < question_simple.measure()
# They shouldn't be prefixes of each other because they behave
# differently.  But it's good to check.
assert not question_swapped.is_prefix(question_simple)
assert not question_simple.is_prefix(question_swapped)
assert_equals(question_swapped.run(binarytape("010101000")), t0)
assert_equals(question_swapped.run(binarytape("101011001")), t1)
assert_equals(predicts_npbug(Speed_prior_explanation(
    explanations=(physics_swapped, question_swapped)),
                             history, empty_tape),
              t1)
assert_equals(exercise_answer_npbug([(physics_simple, question_simple),
                                     (physics_swapped, question_swapped)]),
              {t1: 1.0})

# The input to question_constant_1 is a tuple with the question and
# the state:
#    <don't care what the question is>
#    1 0 (tuple separator)
#    0 cell2:1 (tuple padding and saying it's constant)
#    cell1:0 start:0
# and the output should be just <0>.
# But pad this so it has the same simplicity as question_simple.
def question_constant_prior(garbagebit):
    return Speed_prior(logtime=3, absyn=turing_program(
    "start",
    start={0:(0, left, "cell1"), (1, end): impossible},
    cell1={0:(0, left, "cell2"), (1, end): impossible},
    # garbagebit inserted and then truncated.
    cell2={1:(garbagebit, right, "cell1again"), (0, end): impossible},
    cell1again={0:(truncate, right, done), (1, end): impossible},
    done={(0, 1): done, end: impossible},
    impossible={(0, 1, end): impossible}))
question_constant_1 = question_constant_prior(1)
question_constant_0 = question_constant_prior(0)
def check_question_constant(qc):
    assert_equals(qc.run(binarytape("101010100100")), t0)
    # Check that we refuse to answer questions in a toggling physics state.
    assert_in("Truncate when past right",
              expect_exception(lambda:qc.run(binarytape("01010100000"))))
    # Check that we fail when the state gets set to 1.  Shouldn't happen.
    assert_in("Truncate when past right",
              expect_exception(lambda:qc.run(binarytape("01010100101"))))
    assert_equals(qc.measure(), question_simple.measure())
check_question_constant(question_constant_1)
check_question_constant(question_constant_0)
assert question_constant_1 != question_constant_0
assert_equals(exercise_answer_npbug([(physics_constant_1, question_constant_1),
                                     (physics_constant_0, question_constant_0)]),
             {t0: 1.0})

# Control experiment.  If we don't pad question_swapped, then we
# conclude equal probabilites for both answers.
assert_equals(exercise_answer_npbug([(physics_constant_1, question_constant_1),
                                     (physics_constant_0, question_constant_0),
                                     (physics_simple, question_simple),
                                     (physics_swapped, question_swapped_unpadded)]),
              {t0: 0.5, t1: 0.5})

# Just because the questions are harder doesn't make the reality less likely.
bugproof = exercise_answer_npbug([(physics_constant_1, question_constant_1),
                                  (physics_constant_0, question_constant_0),
                                  (physics_simple, question_simple),
                                  (physics_swapped, question_swapped)])
assert bugproof[t0] > 0.66
assert bugproof[t1] < 0.34

# Test two_hypothesis_generator
l = two_hypothesis_generator(3)
assert_in([Speed_prior(logtime=0, program_length=0, program=0L),
           Speed_prior(logtime=0, program_length=3, program=6L)],
          l)
assert [Speed_prior(logtime=0, program_length=1, program=0L),
           Speed_prior(logtime=0, program_length=3, program=6L)] \
           not in l

# Test predict_qna
assert_equals(
    predict_qna(question_simple, history, empty_tape, physics_simple),
    t1)
assert_in("Bad answer for a question",
          str(expect_exception(lambda:predict_qna(
    question_swapped, history, empty_tape, physics_simple))))

# Test predicts_nonpbug
assert_in("Bad prediction of the video",
          str(expect_exception(lambda:predicts_nonpbug(
    h0, history, empty_tape, epsilon))))

assert_equals(predicts_nonpbug(physics_simple, history, empty_tape, epsilon,
                               question_generator=sham_generator_from_list(
    [question_simple])),
              ((t1, 1.0),))

# Test answer_questions_nonpbug
def question_nonpbug_generator(question_swapped):
    return sham_generator_from_list([question_constant_1, question_constant_0,
                                     question_simple, question_swapped])

# Control
assert_equals(answer_questions_nonpbug(
    history, question=binarytape(""),
    epsilon=epsilon,
    question_generator=question_nonpbug_generator(question_swapped_unpadded),
    physics_generator=physics_npbug_generator),
              {t0: 0.5, t1: 0.5})

# Experiment.  This is the real test.  We can pad the entropy of a
# hypothesis about answering questions without changing the apparent
# probability of the corresponding world.
assert_equals(answer_questions_nonpbug(
    history, question=binarytape(""),
    epsilon=epsilon,
    question_generator=question_nonpbug_generator(question_swapped),
    physics_generator=physics_npbug_generator),
              {t0: 0.5, t1: 0.5})