Jump to content


Check out our Community Blogs

Hignar

Member Since 26 May 2009
Offline Last Active Apr 22 2012 10:41 AM
-----

#514967 cleaning ubuntu off my machine

Posted by Hignar on 11 October 2009 - 03:17 AM

It'll be in /boot/grub/menu.lst on your Ubuntu partition. You'll need to use the liveCD to boot into Ubuntu and mount your external hdd. You can then copy the menu.lst file to your windows partition so you can access it in vista.
  • -1


#503417 I can't figure out why my recursive palindrome doesn't work

Posted by Hignar on 28 August 2009 - 02:45 PM

Your second function doesn't work either, it just tests if the first and last character is the same.

The problem with your first function is that you are passing j++ back into the function. As j++ returns j and then increments you are actually passing j=0 back into the function. You can see this by using the following code

char testPalindrome (char sentence1[], int NumCharts, int j)
{
    if (j >= NumCharts/2)
       return 'T';
    else if (sentence1[NumCharts-1 -j]!= sentence1[j])
       return 'F';
    else
       [b]cout << "Using j =  " << j << endl;[/b]
       return testPalindrome ( sentence1,NumCharts,j++);
}

You'll just get a repeating message of "Using j = 0" until the error occurs.

if you change the call to the function to
return testPalindrome ( sentence1,NumCharts,++j);
j will be incremented and then passed back to the function giving the desired result.
  • -1


#485462 [cryptography / python] Caesar Shift encryption

Posted by Hignar on 18 July 2009 - 12:05 PM

I've been reading a book about cryptography recently. The book in question is "The Code Book - A Secret History of Codes and Code-Breaking" by Simon Singh (Amazon link). While there is no programming content in the book it covers the ideas needed to be able to come up with your own programs.

Unfortunately, there isn't a lot of 'heavy' programming needed to encrypt and decrypt messages using simple methods. Code-breaking is where the serious programming comes into play. I hope to cover code-breaking in a tutorial in a little while!

The first type of encryption that is covered in the book is known as a Caesar shift (so called due to its use by Julius Caesar).

The Caesar shift is a substitute cypher where each letter in a message is replaced with a letter a predetermined number of steps down the alphabet.

For example if we use a shift of 3 we get the following substitutions

Plain: 	abcdefghijklmnopqrstuvwxyz
Cipher:	defghijklmnopqrstuvwxyzabc

Thus the message "this is a message" would be translated to "wklv lv d phvvdjh".

In order to write a program that will encrypt a message we have to first produce the cipher alphabet based on the desired number of steps.

stdalph = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
crypalph = []

After asking the user to enter the desired number of steps we can fill the cipher alphabet using modular arithmetic. Assuming a shift of 3, we want the first entry of crypalph to be 'd', the second to be 'e' and so on until we have crypalph[25] = c.

shift = 3
for x in range(0,26):
  crypalph.append(stdalph[(x+shift)%26])

Now, given a message (either entered by the user or read from a file), we need to substitute each letter in the message with the corresponding letter from the cipher alphabet. This method of encryption only substitute the letters in the message (although it can clearly be extended to cover punctuation marks and white space) so we need to decide what to do with punctuation etc. One answer is to simply leave the punctuation in place. This method is the least secure as the punctuation marks could give anyone who intercepts the message additional clues to help crack the code. The second option is to remove all punctuation and white space.

Although the second method is more secure I have opted to use the first method as it allows me to use a nice feature of python. In order to determine whether or not to substitute an individual character we need to know if it's a letter of the alphabet or not. Thus all we have to do is see if each character is in stdalph. As python evaluates all none zero integers as true and zero as false we can use the count() function to return the number of times a character is in stdalph i.e. 1 for a letter of the alphabet and 0 for any other punctuation etc.

So the encrypt the message all we have to do is loop through the message a character at a time and make the substitution where necessary.

message = 'this is a message'
cryptmessage =''

for x in message:
  if stdalph.count(x):
    cryptmessage += crypalph[stdalph.index(x.lower())]
  else:
    cryptmessage += x

print cryptmessage

gives the output:

wklv lv d phvvdjh

Due to the simple nature of the encryption, decryption works in exactly the same way.

cryptmessage ='wklv lv d phvvdjh'
message = ''

for x in cryptmessage:
  if stdalph.count(x):
    message += stdalph[crypalph.index(x)]
  else:
    message += x

print message

Giving the output
this is a message

Unfortunately the Caesar shift isn't a very secure method of encryption. With only 26 possible cipher alphabets (one of which is just the standard alphabet) it wouldn't take very long for someone to try each possible shift value and decipher the message. The strength of the cipher can be improved by the use of a keyword. Using the keyword "Codecall" we can produce a cipher alphabet as follows:

1) Remove duplicate letters from the keyword giving us "codeal"
2) Place the new keyword at the start of the cipher alphabet
3) Fill the remainder of the cipher alphabet with the letters of the alphabet in order starting with the letter after the last letter of the keyword, excluding those used in the keyword.

Thus, the cipher alphabet for the keyword "codecall" would be

Plain: 	abcdefghijklmnopqrstuvwxyz
Cipher:	codealmnpqrstuvwxyzbfghijk

Given the vast number of possible keywords or keyphrases that could be used a brute force attack on the encrypted message would take much longer than if a simple Caesar shift was used.

I hope to produce a further tutorial on the use of keywords and using cryptanalysis to break codes when the keyword or phrase isn't known.
  • 5


#477258 [python] tic-tac-toe

Posted by Hignar on 26 June 2009 - 01:39 PM

Tic-tac-toe seems to be a popular tutorial for a lot of the other languages on this site so I thought I'd put one together for python.

I've only been learning python for a few weeks so it's likely that there will be some errors but I thought that this would be a good tutorial to help taking people learning the language from the point where they are typing out short examples to thinking about how to put together a larger program.

This is something that I hadn't really done before, so there may be better ways to approach it but this is how I got to my final program.

To start off with I decided to make a simple noughts and crosses (tic-tac-toe) game. I didn't want to complicate it by trying to learn GUI programming at the same time so it's entirely command line based.

First thing I did was work out what parts the program would need. Clearly we'd still need to be able to display the game board. Using a nested list seemed to make sense to me as we can display each row on a seperate line to produce a 3x3 board. We'd also need a way to fill the board in turns and finally we need to check after each turn whether there is a winning line for the player who just took a turn or see if the game is drawn. To make the game easier to follow the board should be reprinted after each turn. Players also need to be identified as 'X' and 'O'. This will help with the checkwin function later on.

The basic outline of the program looks like this
def checkwin(player):
  #code for checking for a winning line

def printboard():
  print board[0]
  print board[1]
  print board[2]

#initialise an empty board
board = [['-','-','-'],['-','-','-'],['-','-','-']]
player1 = 'X'
player2 = 'O'
win = False

#game loop
while(win == False):
  #code for player one's turn
  printboard()
  checkwin(player1)

  #code for player two's turn
  printboard()
  checkwin(player2)


So, first thing to do is enable us to fill the board. The easiest way to do this is to ask each player to select the row and column where they want to place their mark. I decided to take this code out of the main loop and define a function that could be applied to either player.

#code for player's turn
def playerturn(player):
  print "%s's turn" % player1
  print "Select column [1-3]: ",
  col = int(raw_input()) - 1
  print "Select row [1-3]: ",
  row = int(raw_input()) - 1
  board[row][col] = player

While this works there is no way to stop players overwriting previous moves so we need to code a check to see if it is a valid move and to loop the function until a valid move is given.

#code for player's turn
def playerturn(player):
  print "%s's turn" % player
  turn = 1
  while(turn)
    print "Select column [1-3]: ",
    col = int(raw_input()) - 1
    print "Select row [1-3]: ",
    row = int(raw_input()) - 1
    #check if move is allowed
    if board[row][col] == 'X' or board[row][col] == 'O'
      print "Already taken!"
    else
      board[row][col] = player
      turn = 0

So we can now print and fill the board. All that's left is to check for a winning line so we need to define the checkwin function. There are four ways to produce a winning line. A horizontal line, a vertical line, a diagonal line from left to right and a diagonal line from right to left. We need to check for each, but once a winning line is found there is no need for the check to continue.

def checkwin(player):
  #loop through rows and columns
  for c in range(0,3):
    #check for horizontal line
    if board[c][0] == player and board[c][1] == player and board[c][2] == player:
      print "*********\n\n%s wins\n\n*********" % player
      playerwin = True
      return playerwin
    #check for vertical line
    elif board[0][c] == player and board[1][c] == player and board[2][c] == player:
      print "*********\n\n%s wins\n\n*********" % player
      playerwin = True
      return playerwin
    #check for diagonal win (left to right)
    elif board[0][0] == player and board[1][1] == player and board[2][2] == player:
      print "*********\n\n%s wins\n\n*********" % player
      playerwin = True
      return playerwin
    #check for diagonal win (right to left)
    elif board[0][2] == player and board[1][1] == player and board[2][0] == player:
      print "*********\n\n%s wins\n\n*********" % player
      playerwin = True
      return playerwin
  else:
    playerwin = False
    return playerwin


So with these elements we should be able to put together a functional (if buggy) game. The only other thing needed is a way to check for a draw. As there are only 9 moves available we can count the number of turns taken and declare a draw when there are no further moves available. Also as a draw is only possible after an odd number of turns we only need to check for a draw after the first players turn.

The final code for our game is as follows


def checkwin(player):
  #loop through rows and columns
  for c in range(0,3):
    #check for horizontal line
    if board[c][0] == player and board[c][1] == player and board[c][2] == player:
      print "*********\n\n%s wins\n\n*********" % player
      playerwin = True
      return playerwin
    #check for vertical line
    elif board[0][c] == player and board[1][c] == player and board[2][c] == player:
      print "*********\n\n%s wins\n\n*********" % player
      playerwin = True
      return playerwin
    #check for diagonal win (left to right)
    elif board[0][0] == player and board[1][1] == player and board[2][2] == player:
      print "*********\n\n%s wins\n\n*********" % player
      playerwin = True
      return playerwin
    #check for diagonal win (right to left)
    elif board[0][2] == player and board[1][1] == player and board[2][0] == player:
      print "*********\n\n%s wins\n\n*********" % player
      playerwin = True
      return playerwin
  else:
    playerwin = False
    return playerwin

#code for player's turn
def playerturn(player):
  print "%s's turn" % player
  turn = 1
  while(turn):
    print "Select column [1-3]: ",
    col = int(raw_input()) - 1
    print "Select row [1-3]: ",
    row = int(raw_input()) - 1
    if board[row][col] == 'X' or board[row][col] == 'O':
      print "Already taken!"
    else:
      board[row][col] = player
      turn = 0

def printboard():
  print board[0]
  print board[1]
  print board[2]

#initialise an empty board
board = [['-','-','-'],['-','-','-'],['-','-','-']]
player1 = 'X'
player2 = 'O'
win = False
turns = 0

#game loop
#print empty board to start program
printboard()
while(win == False):
  playerturn(player1)
  turns += 1
  printboard()
  if checkwin(player1) == True: break
  if turns == 9:
    print "This game is a draw!"
    break

  playerturn(player2)
  turns += 1
  printboard()
  checkwin(player2)
  if checkwin(player2) == True: break

While the game runs and works there is clearly room for improvement. The most obvious area is error checking. As it stands any value can be entered for the moves and anything other than the numbers 1-3 produce an error. I was surprised just how much checking is needed for the game to be fully functional.

If there is any interest I will improve the game to include error checking in a further tutorial.
  • 1


Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download