Programming challenges

[phillip1882]

so far commodorejohn is the only one who has submitted code.
come on guys! get on it!

[Jplus]

I started working on a solution but have been very busy with other things. I still want to finish my solution, but it's probably going to be the second half of February.

[phillip1882]

Jplus, did you get my code submissions for additional sorts?

[Jplus]

I did! I will grade them. I'm going to close submissions at the same time as your challenge, i.e., March 1.

[phillip1882]

so i'm changing the rules slightly, you have to win more than 50 of your rounds compared to your opponent for a win, otherwise its a draw.

[Jplus]

To myself and any other participants who have not submitted their solutions for round 2 yet: let's not forget this time!

[Jplus]

I submitted a solution!

[phillip1882]

ok somitomi still hasn't submitted anything, and commadorejohn has submitted 3.

[phillip1882]

ok time limit has been reached. here are the results.
first up, commodorejohn.
he wrote 3 algorithms that are pseudo random number generators, and thus giving him a negative badge for not following the spirit of the game.
but one of his submissions played very well, and was clear and concise.

Code: Select all

def primesin(i, mymoves, myopp):
    a = math.sin(math.radians(i * 173))
    b = math.sin(math.radians(i * 113))
    d = a + b
    if d >= 0.4:
        return 1
    if d <= -0.4:
        return 2
    return 0

this had 2.5 wins the most of any algorithm, and 7688 round wins, also the most
here are his other submissions, and how they faired.

Code: Select all

def primes(i, mymoves, myopp):
    a = i * 23
    b = i * 37
    d = a ^ b
    z = (d & 2) | ((d & 128) >> 7)
    while z == 3:
        d >>= 1
        z = (d & 2) | ((d & 128) >> 7)
    return z

1 match, 7349.5 round wins

Code: Select all

def determinism(i, mymoves, myopp):
    bits = 0                        # assume nothing
    for x in myopp:                 # carefully study the opponent's moves
        z = x + 1                   # consider the value of nothing
        for y in range(0, 2):       # handle each bit with care
            bits <<= 1              # do a little dance
            bits |= (z & 1)         # make a little love
            z >>= 1                 # get down tonight
            if bits & 65536:        # if it's heads,
                bits ^= 10410       # take a shot
        bits &= 65535               # all things in moderation
    z = (bits >> 14) & 3            # plan our move carefully
    while z == 3:                   # but if it's illegal,
        bits <<= 2                  # continue planning
        z = (bits >> 14) & 3        # until we arrive at the correct answer
    return z

1.5 match, 7507 round wins
next up, Jplus.
his algorithm tries to use the accuracy of his current guesses for the next guess. surprisingly, it faired poorly. here's the code and result.

Code: Select all

import math
__doc__ = '''
Submission for round 2 of the "Programming challenges" forum game,
organized by phillip1882 at ramenchef.net/nxf.

Author: Jplus

Usage: at the start of each match, create a new instance of the final
strategy:

    playAsJplus = JplusStrategy()

This instance can be called at every turn, as specified in the task
description:

    next_move = playAsJplus(i, mymoves, myopp)
'''

from operator import itemgetter, methodcaller

ROCK, PAPER, SCISSORS = 0, 1, 2
LOSS, TIE, WIN = 2, 0, 1
ROUND_MISMATCH_MESSAGE = '''
The round number is less than the expected round number. Did you
create a new instance of the strategy before starting the match?
'''


def outcome(ours, theirs):
    """ Given our and their moves, what is the outcome for us? """
    return (ours - theirs) % 3


def beat(theirs):
    """ Given their move, what should be played to beat it? """
    return (theirs + 1) % 3


def blank_tally():
    """ Empty frequency table for initializing a tally. """
    return {ROCK: 0, PAPER: 0, SCISSORS: 0}


def most_frequent(tally):
    """ Given a frequency table, return the most prevalent move. """
    return max(tally.items(), key=itemgetter(1))[0]


class Strategy(object):
    """
    Base class for playing strategies.

    A strategy is initialized once for each match and can then be called as a
    function for each turn. The call signature is (round_number,
    opponent_moves, own_moves), as specified in the challenge description of
    round 2. The use of a callable class instance instead of a bare function
    makes it possible to build the opponent model incrementally, so that moves
    can be decided efficiently even after many turns.

    A child class must at least define a predict method, which attempts to
    guess what the opponent will play. This method takes no arguments and
    should base its answer purely on an internal model, however simple. The
    move that ends up being played is always beat(self.predict()).

    Optionally, child classes may also override the observe method in order to
    build their internal model. This method takes two arguments: the opponent's
    move in the previous turn, and the own move in the previous turn. Any
    return vaue is ignored.

    All playing strategies keep track of how many turns they have seen and how
    accurate their prediction of the opponent's moves has been so far. This is
    taking care of automatically in the __call__ method.
    """

    def __init__(self):
        self.turn = 0
        self.score = 0

    def __call__(self, round, their_history, our_history):
        assert round == self.turn, ROUND_MISMATCH_MESSAGE
        theirs, ours = [],[]
        if round > 0:
            theirs, ours = their_history[-1], our_history[-1]
            self.observe(theirs, ours)
            previous_result = outcome(ours, theirs)
            if previous_result == LOSS:
                self.score -= 1
            elif previous_result == WIN:
                self.score += 1
        guess = theirs
        self.turn += 1
        if round == 0:
           return 0
        return beat(guess)

    def weighted_call(self, round, their_history, our_history):
        move = self(round, their_history, our_history)
        return self.accuracy(), move

    def observe(self, theirs, ours):
        pass

    def accuracy(self):
        if self.turn < 1:
            return 0
        return self.score / self.turn

    def arbitrary(self):
        return self.turn % 3


def reflect(base):
    """ Given a statistical strategy, return a strategy that counters it. """
    class Reflective(base):
        def observe(self, theirs, ours):
            super().observe(ours, theirs)

        def predict(self):
            their_prediction = super().predict()
            return beat(their_prediction)

    Reflective.__name__ += base.__name__
    return Reflective


class MarkovChain(Strategy):
    """
    Base the move on a pattern frequency analysis of the opponent.
    """

    def __init__(self, stride=4):
        super().__init__()
        self.stride = stride
        self.window = ()
        self.tally = {}

    def observe(self, theirs, ours):
        if self.turn >= self.stride:
            tally = self.tally.get(self.window, blank_tally())
            tally[theirs] += 1
            self.tally[self.window] = tally
            self.window = (*self.window[1:], theirs)
        else:
            self.window = (*self.window, theirs)

    def predict(self):
        tally = self.tally.get(self.window)
        if tally is None:
            return self.arbitrary()
        return most_frequent(tally)


ReflectiveMarkovChain = reflect(MarkovChain)


class JplusStrategy(Strategy):
    """ Counter both of the above strategies. """

    def __init__(self):
        super().__init__()
        self.candidates = [
            MarkovChain(),
            ReflectiveMarkovChain(),
        ]

    def __call__(self, round, their, our):
        # Update this strategy's accuracy, ignoring the prediction.
        super().__call__(round, their, our)
        # Defer the actual move to the best performing candidate.
        forward = methodcaller('weighted_call', round, their, our)
        return max(map(forward, self.candidates), key=itemgetter(0))[1]

    def predict(self):
        pass

1 match win, 7455.5 round wins.

[phillip1882]

if you would like to try running the tournament, here's my code for doing so.

Code: Select all

def runTourney():
   Left =["primesin","playAsJplus"]
   Right =[ "determinism", "primes"]
   cycle = 0
   totalWins ={"determinism": 0, "primesin":0, "primes":0,"playAsJplus":0}
   totalRounds = {"primesin":0, "primes":0, "determinism": 0, "playAsJplus":0}

   while cycle < 2*len(Left)-1:
      for i in range(0,len(Left)):
         print(Left[i],Right[i])
         if Left[i] == "playAsJplus" or Right[i] =="playAsJplus":
             playAsJplus = JplusStrategy()
         mymovesPlay1 = []
         mymovesPlay2 = []
         wins = []
         if Left[i] == "BYE" or Right[i] == "BYE":
            continue
         for j in range(0,5000):
            if j == 0:
               result1 = eval(Left[i]+"(0 ,[], [])")
               result2 = eval(Right[i]+"(0 ,[], [])")
               if result1 =="R":
                  result1 = 0
               if result1 =="P":
                  result1 = 1
               if result1 =="S":
                  result1 = 2
               if result2 =="R":
                  result2 = 0
               if result2 =="P":
                  result2 = 1
               if result2 =="S":
                  result2 = 2
               mymovesPlay1 += [result1]
               mymovesPlay2 += [result2]
               if result1 == result2:
                  wins +=[0.5,0.5]
                  totalWins[Left[i]]+= 0.5
                  totalWins[Right[i]]+= 0.5
               elif (result1 +1)%3 == result2:
                  wins += [0,1]
                  totalWins[Right[i]]+= 1
               else:
                  wins += [1,0] 
                  totalWins[Left[i]]+= 1
               continue
            result1 = eval(Left[i]+"("+str(j)+","+"mymovesPlay1, mymovesPlay2)")
            result2 = eval(Right[i]+"("+str(j)+","+"mymovesPlay2, mymovesPlay1)")
            if result1 =="R":
               result1 = 0
            if result1 =="P":
               result1 = 1
            if result1 =="S":
               result1 = 2
            if result2 =="R":
               result2 = 0
            if result2 =="P":
               result2 = 1
            if result2 =="S":
               result2 = 2
            mymovesPlay1 += [result1]
            mymovesPlay2 += [result2]
            if result1 == result2:
               wins[0] += 0.5
               wins[1] += 0.5
               totalWins[Left[i]]+= 0.5
               totalWins[Right[i]]+= 0.5
            elif (result1 +1)%3 == result2:
               wins[1] += 1
               totalWins[Right[i]]+= 1
            else:
               wins[0] += 1 
               totalWins[Left[i]]+= 1
            
         if wins[0] > wins[1]+50:
            totalRounds[Left[i]]+= 1
         elif wins[0]+50 < wins[1]:
            totalRounds[Right[i]] +=1
         else:
            totalRounds[Left[i]]+= 0.5
            totalRounds[Right[i]] +=0.5
      value = Left.pop(1)
      Right.insert(0,value)
      value = Right.pop(-1)
      Left += [value]
      cycle += 1
   print(totalRounds)
   print(totalWins)
runTourney()

[Jplus]

I assumed that my opponent would play nonrandom. Given that my only opponents played random, I am not surprised that my solution faired poorly.

Edit to add: here is the full version of my solution, which includes code that was not strictly necessary for the submission. It includes some simple nonrandom strategies that I tested mine against. You can also try playing live against my solution; it is actually quite strong against a human. To do so, just save the code as jplus.py and then run "python3 jplus.py".

Spoiler (Show/Hide)

Code: Select all

__doc__ = '''
Submission for round 2 of the "Programming challenges" forum game,
organized by phillip1882 at ramenchef.net/nxf.

Author: Jplus

Usage: at the start of each match, create a new instance of the final
strategy:

    playAsJplus = JplusStrategy()

This instance can be called at every turn, as specified in the task
description:

    next_move = playAsJplus(i, mymoves, myopp)
'''

from operator import itemgetter, methodcaller

ROCK, PAPER, SCISSORS = 0, 1, 2
LOSS, TIE, WIN = 2, 0, 1
INTERPRETATION = {
    'r': ROCK,
    'p': PAPER,
    's': SCISSORS,
    '0': ROCK,
    '1': PAPER,
    '2': SCISSORS,
}
REPRESENTATION = ['rock', 'paper', 'scissors']
ROUND_MISMATCH_MESSAGE = '''
The round number is less than the expected round number. Did you
create a new instance of the strategy before starting the match?
'''


def outcome(ours, theirs):
    """ Given our and their moves, what is the outcome for us? """
    return (ours - theirs) % 3


def beat(theirs):
    """ Given their move, what should be played to beat it? """
    return (theirs + 1) % 3


def beaten(ours):
    """ Given our move, what opponent move would have been beaten? """
    return (ours - 1) % 3


def same(value):
    """ An identity function. """
    return value


def blank_tally():
    """ Empty frequency table for initializing a tally. """
    return {ROCK: 0, PAPER: 0, SCISSORS: 0}


def most_frequent(tally):
    """ Given a frequency table, return the most prevalent move. """
    return max(tally.items(), key=itemgetter(1))[0]


class Strategy(object):
    """
    Base class for playing strategies.

    A strategy is initialized once for each match and can then be called as a
    function for each turn. The call signature is (round_number,
    opponent_moves, own_moves), as specified in the challenge description of
    round 2. The use of a callable class instance instead of a bare function
    makes it possible to build the opponent model incrementally, so that moves
    can be decided efficiently even after many turns.

    A child class must at least define a predict method, which attempts to
    guess what the opponent will play. This method takes no arguments and
    should base its answer purely on an internal model, however simple. The
    move that ends up being played is always beat(self.predict()).

    Optionally, child classes may also override the observe method in order to
    build their internal model. This method takes two arguments: the opponent's
    move in the previous turn, and the own move in the previous turn. Any
    return vaue is ignored.

    All playing strategies keep track of how many turns they have seen and how
    accurate their prediction of the opponent's moves has been so far. This is
    taking care of automatically in the __call__ method.
    """

    def __init__(self):
        self.turn = 0
        self.score = 0

    def __call__(self, round, their_history, our_history):
        assert round == self.turn, ROUND_MISMATCH_MESSAGE
        if round > 0:
            theirs, ours = their_history[-1], our_history[-1]
            self.observe(theirs, ours)
            previous_result = outcome(ours, theirs)
            if previous_result == LOSS:
                self.score -= 1
            elif previous_result == WIN:
                self.score += 1
        guess = self.predict()
        self.turn += 1
        return beat(guess)

    def weighted_call(self, round, their_history, our_history):
        move = self(round, their_history, our_history)
        return self.accuracy(), move

    def observe(self, theirs, ours):
        pass

    def accuracy(self):
        if self.turn < 1:
            return 0
        return self.score / self.turn

    def arbitrary(self):
        return self.turn % 3


def reflect(base):
    """ Given a statistical strategy, return a strategy that counters it. """
    class Reflective(base):
        def observe(self, theirs, ours):
            super().observe(ours, theirs)

        def predict(self):
            their_prediction = super().predict()
            return beat(their_prediction)

    Reflective.__name__ += base.__name__
    return Reflective


class Constant(Strategy):
    """ A strategy that always repeats the same arbitrary move. """

    def __init__(self, move=ROCK):
        super().__init__()
        self.prediction = beaten(move)

    def predict(self):
        return self.prediction


class AntiConstant(Strategy):
    """ Assume that the opponent is biased towards a particular move. """

    def __init__(self):
        super().__init__()
        self.tally = blank_tally()

    def observe(self, theirs, ours):
        self.tally[theirs] += 1

    def predict(self):
        return most_frequent(self.tally)


ReflectiveAntiConstant = reflect(AntiConstant)


class Rotate(Strategy):
    """ A strategy that rotates through the possible moves. """

    def __init__(self, first=ROCK, retrograde=False):
        super().__init__()
        self.first = first
        self.retrograde = retrograde

    def predict(self):
        current = self.turn % 3
        if current > 0 and self.retrograde:
            current = 3 - current
        shifted = (current + self.first) % 3
        return beaten(shifted)


class AntiRotate(Strategy):
    """ Assume that the opponent cycles through the possible moves. """

    def __init__(self):
        super().__init__()
        self.tally = blank_tally()
        self.previous = None

    def observe(self, theirs, ours):
        if self.previous is not None:
            offset = outcome(theirs, self.previous)
            self.tally[offset] += 1
        self.previous = theirs

    def predict(self):
        previous = self.previous
        if previous is None:
            return self.arbitrary()
        offset = most_frequent(self.tally)
        return (previous + offset) % 3


ReflectiveAntiRotate = reflect(AntiRotate)


class Reactive(Strategy):
    """ Respond to the opponent's previous move by a fixed offset. """

    def __init__(self, initial=ROCK, offset=same):
        super().__init__()
        self.previous = offset(offset(initial))
        self.offset = offset

    def observe(self, theirs, ours):
        self.previous = theirs

    def predict(self):
        intended_move = self.offset(self.previous)
        return beaten(intended_move)


class AntiReactive(AntiRotate):
    """ Assume that the opponent responds to our moves by a fixed offset. """

    def observe(self, theirs, ours):
        if self.previous:
            offset = outcome(theirs, self.previous)
            self.tally[offset] += 1
        # A subtle but crucial difference with AntiRotate
        self.previous = ours


ReflectiveAntiReactive = reflect(AntiReactive)


class Human(Strategy):
    """ Represent a human player by asking for input. """

    def observe(self, theirs, ours):
        self.previous = theirs

    def predict(self):
        if hasattr(self, 'previous'):
            print('Opponent\'s move:', REPRESENTATION[self.previous])
        move = INTERPRETATION[input('Your move: ').strip().lower()[0]]
        return beaten(move)


class MarkovChain(Strategy):
    """
    Base the move on a pattern frequency analysis of the opponent.

    Defeats all of the above strategies.
    """

    def __init__(self, stride=4):
        super().__init__()
        self.stride = stride
        self.window = ()
        self.tally = {}

    def observe(self, theirs, ours):
        if self.turn >= self.stride:
            tally = self.tally.get(self.window, blank_tally())
            tally[theirs] += 1
            self.tally[self.window] = tally
            self.window = (*self.window[1:], theirs)
        else:
            self.window = (*self.window, theirs)

    def predict(self):
        tally = self.tally.get(self.window)
        if tally is None:
            return self.arbitrary()
        return most_frequent(tally)


ReflectiveMarkovChain = reflect(MarkovChain)


class JplusStrategy(Strategy):
    """ Counter all of the above strategies. """

    def __init__(self):
        super().__init__()
        self.candidates = [
            MarkovChain(),
            ReflectiveMarkovChain(),
        ]

    def __call__(self, round, their, our):
        # Update this strategy's accuracy, ignoring the prediction.
        super().__call__(round, their, our)
        # Defer the actual move to the best performing candidate.
        forward = methodcaller('weighted_call', round, their, our)
        return max(map(forward, self.candidates), key=itemgetter(0))[1]

    def predict(self):
        # This method needs to be defined, but we never actually use the value.
        return ROCK


def play_match(player1, player2):
    """ Run a match between two strategy instances. """
    moves1, moves2 = [], []
    for round in range(5000):
        try:
            move1 = player1(round, moves2, moves1)
            move2 = player2(round, moves1, moves2)
            moves1.append(move1)
            moves2.append(move2)
        except KeyboardInterrupt:
            break
    return moves1, moves2


def print_match(player1, player2, moves1, moves2):
    """ Show the results of a match to stdout. """
    print('Player 1 accuracy:', player1.accuracy())
    print('Player 2 accuracy:', player2.accuracy())
    print()
    for round, (move1, move2) in enumerate(zip(moves1, moves2)):
        if round == 60:
            break
        show1 = REPRESENTATION[move1]
        show2 = REPRESENTATION[move2]
        print('{}: {}, {}'.format(round, show1, show2))


# Run the module to try the strategy against yourself!
if __name__ == '__main__':
    opponent = Human()
    self = JplusStrategy()
    moves = play_match(opponent, self)
    print_match(opponent, self, *moves)

[phillip1882]

I'm eager to see my sort functions evaluated. and the next challenge.

[phillip1882]

jplus? you there?

[Jplus]

I'm here! I've been very busy but I will post the grades of the new submissions for challenge 1 tonight.

I don't mind organizing the next challenge, but I don't have one ready, so if someone else would like to go, please do!

[Jplus]

Regardless of who's hosting the next challenge: what kind of challenge would we like next? Mazes? Calculations? Battles? Mystery?

[phillip1882]

yeah i was thinking maze next challenge.

[Jplus]

commodorejohn, somitomi, would you also like to participate if we do mazes next? Perhaps Freddino18?

Would phillip1882 or anyone else like to host?

If I'm going to host and we're doing mazes, I want at least three other participants. Also, it is likely that multiple weeks will pass before I have programmed enough to be able to give a clear description of the challenge.

[commodorejohn]

I'm interested. Is this maze generation, or maze solving?

[somitomi]

I'd like to, but given my track record so far I'm not sure I should make any promises. I've been struggling to find the spare time and energy for these sort of things since I stopped being a university freeloader.

[Jplus]

I'm interested. Is this maze generation, or maze solving?

What would you prefer?

I'd like to, but given my track record so far I'm not sure I should make any promises. I've been struggling to find the spare time and energy for these sort of things since I stopped being a university freeloader.

If we could somehow make the game less time-consuming, would that help you?

Also, which programming language(s) would work for you?

[commodorejohn]

Easy, just curious.

[Jplus]

Did you mean you prefer something easy? Or did you rather mean something like "take it easy"?

[somitomi]

If we could somehow make the game less time-consuming, would that help you?

Also, which programming language(s) would work for you?

I couldn't be bothered to put a sorting algorithm together for the first round, I'm not sure you could make it quicker without losing the... challenge aspect of the challenge.
Most of the coding I did over the years was in C#, but I also know a little C

[phillip1882]

If I'm going to host and we're doing mazes, I want at least three other participants. Also, it is likely that multiple weeks will pass before I have programmed enough to be able to give a clear description of the challenge.

i'm not quite sure how you would evaluate a maze generation algorithm, what you would give badges for. maybe number of dead ends?

[commodorejohn]

Did you mean you prefer something easy? Or did you rather mean something like "take it easy"?

"I am easy" (colloq. "I don't care.") Coulda been clearer.