Let's play a game, pals. Challenge 3

[TheQuirk]

Next one.

Next challenge:

You have a chessboard. On the chessboard, there is a white knight and a
black pawn. Disregarding all the rules except the ones that
concern the movement of knights and pawns, the computer must calculate
if it's possible for the knight to stop the pawn from reacing the first

row, and if so, on which (earliest) move. The knight can stop the pawn in two
ways--either by eating it, or by moving right in front of it. If the pawn
takes the knight (I like to use the term "eats"), then the knight fails
to stop the pawn. The knight moves first.

I/O:
The program must read the starting positions for the pieces from a
file called "input.txt". It should be in the following format:

a4
d7

Where the first line represents the knight's location, and the second
line represents the pawn's location.

Once the program finishes its calculations, it must output the result
to "output.txt" with a number representing the number of moves. If
it's impossible to stop the pawn, then the program should outout the
number zero into "output.txt".

By the way, maybe I should post every challenge in a seperate thread? That would probably be a bit easier to read + easier to reference in the future.

Edit: Hints are available on AIM.

[KernelPanic]

By the way, maybe I should post every challenge in a seperate thread? That would probably be a bit easier to read + easier to reference in the future.

Yes.
In fact, did it for you.

[Pathos]

I'm going to use cin/cout instead.

And I should do my homework first.

[worker201]

I'm going to use cin/cout instead.

Unless things have changed ALOT since I used C++, reading from a textfile and writing to a textfile is not that hard.

Quirk, where are you getting this shit from?  Some textbook?  Maybe I want to read this book...
Right now, I am reading a barely comprehensible book about infinite sets and Cantor.  Much fun.

[TheQuirk]

I got the first two challenges from an old Soviet book; this one I had to solve in class. The formatting is screwed up because I copy-pasted it from an email.

If you want a book, get "Programming Challenges" by Steven S. Skiene and Miguel A. Revilla. I haven't gotten very far into it, but it seems to be pretty good. If you don't want to make the same mistake I made--pay for stuff you can easily get online for free--just search Google for "informatics olympiad problems" and the like. Online programming competitions also contain a lot of programming problems (some solved, some unsolved).

[TheQuirk]

If no one wants to solve this one I can post a solution in Python and then offer another challenge.

[TheQuirk]

My solution:

Code: [Select]

from sys import exit

f = file("input.txt")
horseloc = f.readline()[:-1] # White, first move.
pawnloc = f.readline() # Black.
f.close()
alphavalue = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7}

horseloc = [(alphavalue[horseloc[0]], int(horseloc[1]) - 1)]
pawnloc = (alphavalue[pawnloc[0]], int(pawnloc[1]) - 1)

#
# Functions for checking if the game is over, and, if so, exiting.
#

def finish():
    f = file("output.txt", "w")
    f.write(str(movecount))
    f.close()
    print "Done. Check output.txt for the solution."

def check():
    global movecount
    isdone = bool(0)
    for mustang in horseloc:
        if mustang == pawnloc: # Checks if a horse ate the pawn.
            isdone = bool(1)
        if (pawnloc[0] == mustang[0]) and (pawnloc[1] - 1 == mustang[1]):
            isdone = bool(1) # Checks if the a is blocking the pawn's path.
        if pawnloc[1] == 0: # Checks if the pawn reached n0.
            isdone = bool(1)
            movecount = 0
        if isdone == bool(1): # Checks if the game is over because of one of the above reasons.
            finish()
            exit()
    return isdone

#
# Functions for moving around the board.
# cleanuphorse(): Removes repeating values caused by various paths that lead to identical locations on the board.
# movehorse(): Moves the horse (or, rather, horses) around the board and removes the old locations from the board.
# movepawn(): Moves the pawn around. Also eats the horse if it's in the pawn's hit range.
#

def cleanuphorse():
    for mustang in horseloc[:]:
        if horseloc.count(mustang) > 1:
            horseloc.pop(horseloc.index(mustang))

def movehorse():
    for mustang in horseloc[:]:
        global horseloc
        if mustang[1] <= 5:
            if mustang[0] <= 6:
                horseloc.append((mustang[0] + 1, mustang[1] + 2))
            if mustang[0] >= 1:
                horseloc.append((mustang[0] - 1, mustang[1] + 2))
        if mustang[1] >= 2:
            if mustang[0] <= 6:
                horseloc.append((mustang[0] + 1, mustang[1] - 2))
            if mustang[0] >= 1:
                horseloc.append((mustang[0] - 1, mustang[1] - 2))
        if mustang[1] <= 6:
            if mustang[0] <= 5:
                horseloc.append((mustang[0] + 2, mustang[1] + 1))
            if mustang[0] >= 2:
                horseloc.append((mustang[0] - 2, mustang[1] + 1))
        if mustang[1] >= 1:
            if mustang[0] <= 5:
                horseloc.append((mustang[0] + 2, mustang[1] - 1))
            if mustang[0] >= 2:
                horseloc.append((mustang[0] - 2, mustang[1] -1))
        horseloc.pop(horseloc.index(mustang))
    global movecount
    movecount = movecount + 1
    cleanuphorse()
    check()

def movepawn():
    for mustang in horseloc[:]:
        if ((pawnloc[0] - 1 == mustang[0]) and (pawnloc[1] - 1 == mustang[1])) or ((pawnloc[0] + 1 == mustang[1]) and (pawnloc[1] - 1 == mustang[1])):
            horseloc.pop(horseloc.index(mustang))
    global pawnloc
    pawnloc = (pawnloc[0], pawnloc[1] - 1)
    check()

movecount = 0

check()

for n in range(1, 15):
    if n % 2 != 0:
        movehorse()
    if n % 2 == 0:
        movepawn()

I think I could've done a bit better with how I called all of the functions (call them from within the loop), but it works, so I'm not complaining.

[worker201]

Strive for elegance.