Results 1 to 10 of 13

Thread: Beginners Programming Challenge no.19

Hybrid View

  1. #1
    Join Date
    Aug 2005
    Location
    Sweden
    Beans
    407

    Beginners Programming Challenge no.19

    Beginners Programming Challenge no.19
    Since I won the 18th challenge I have tried to come up with the next one,
    hoping it will be challenging without being insurmountable:

    Crossword creator helper
    Description
    Creating crosswords (crossword example in post 3) is a difficult task, and a program to help out can speed up the process. It is your task to write the program following the specifications:

    The program will read data from a file with the following format:

    • One line with one number denoting the width in cells of the crossword
    • One line with one number denoting the height in cells of the crossword
    • Multiple lines containing X,Y,D,W where
      • X and Y are numbers signifying the position where the 'question cell' responsible for the word is placed (0,0 is the upper left corner)
      • D is the direction of the word--signified by one letter, either h (horizontal) or v (vertical)
      • W is a word (containing only lowercaze a-z)

    So the input 0,0,h,foobar means that #foobar is placed in the upper left corner of the crossword, where # is the little question box hinting at the word foobar.

    Constraints
    • A cell may contain a single letter or a '#' signifying that it is used by a question box, or be unused '.'
    • A question cell (#) may be overlapped by another question cell (eg for a word in a different direction)
    • The resulting crossword should be printed
    • Upon discovering an impossible word placement the input parsing should stop and the crossword so far should be printed. The impossible word cells should be marked with '$' and the word and position should be printed. (see example 2)
    • If the placement coordinate of the word is outside the crossword this should be printed (see example 3) but no dollar signs are needed,
    • If the placement coordinate is inside the crossword, but the word would stick out, this should be printed, but the parts inside should be marked with $ (see example 4)


    Example Input/Output
    1) Valid
    Input:
    Code:
    8
    6
    1,2,h,car
    3,0,v,bar
    4,1,v,rose
    2,3,h,robot
    1,2,v,dog
    Output:
    Code:
    ...#....
    ...b#...
    .#car...
    .d#robot
    .o..s...
    .g..e...
    2) Invalid word
    Input:
    Code:
    8
    6
    1,2,h,car
    3,0,v,bar
    4,1,v,rose
    2,3,h,fruit
    1,2,v,dog
    Output:
    Code:
    ...#....
    ...b#...
    .#car...
    .#$ro$$.
    ....s...
    ....e...
    Horizontal word 'fruit' can not start from cell 3,2 (letter mismatch)
    3) Invalid word placement
    Input:
    Code:
    8
    6
    1,2,h,car
    3,0,v,bar
    4,100,v,rose
    2,3,h,fruit
    1,2,v,dog
    Output:
    Code:
    ...#....
    ...b....
    .#car...
    ...r....
    ........
    ........
    Vertical word 'rose' can not start from cell 4,100 (out of bounds)
    4) Invalid word size
    Input:
    Code:
    8
    6
    1,2,h,car
    3,0,v,bar
    4,1,v,rosebud
    2,3,h,robot
    1,2,v,dog
    Output:
    Code:
    ...#....
    ...b#...
    .#car...
    ...r$...
    ....$...
    ....$...
    Vertical word 'rosebud' can not start from 4,1 (size mismatch)
    Judgement criteria
    The judgement criteria pretty standard, the program has to work,
    code should be readable, it has to be your code, etc. etc...

    Entries accepted until and including 2011-04-24

    Best of luck.
    Last edited by red_Marvin; March 24th, 2011 at 03:06 AM.
    Don't peach linux. Melon it!

  2. #2
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginners Programming Challenge no.19

    Just a thought - the type of crosswords they do in sweden is different from what's common in most other places. Most American and British people are used to having the clues numbered and appear off the board. I was a bit confused by this until I did some wikipedia research.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  3. #3
    Join Date
    Aug 2005
    Location
    Sweden
    Beans
    407

    Re: Beginners Programming Challenge no.19

    I see, well we have these numbered ones here in Sweden too, but the one linked below is the most common.

    To clarify, the kind of crossword I think of is a simplified version of
    the one shown here http://en.wikipedia.org/wiki/File:Sc...%C3%A4tsel.jpg and here http://www.ordkultur.se/happydivers/...-svds-korsord/
    (ignore the arrows, in the contest version here, goes straightly east or south from the clue box)

    Not analyzing too hard, I think you can think of the numbered kind too but i.e. one where all words begin with a #.
    Last edited by red_Marvin; March 24th, 2011 at 03:14 AM.
    Don't peach linux. Melon it!

  4. #4
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginners Programming Challenge no.19

    Quote Originally Posted by red_Marvin View Post
    Not analyzing too hard, I think you can think of the numbered kind too but i.e. one where all words begin with a #.
    Alright... does that mean this is a typo?

    Code:
     012345
    0...#....
    1...b#...
    2.#car...
    3.d#robot
    4.o..s...
     .g..e...
    "bar" appears to start at (3, 0) and "robot" is at (2, 3) instead of (3, 2). Also, are words allowed to span off the edge of the board? You specified the dimensions as 6x5, but are allowing words to go out to 8x6.
    Last edited by schauerlich; March 24th, 2011 at 02:43 AM.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  5. #5
    Join Date
    Aug 2005
    Location
    Sweden
    Beans
    407

    Re: Beginners Programming Challenge no.19

    You are correct, they are errors.
    Only words fitting inside the predefined rectangle are allowed.
    I will update original post.

    ...updated, new rules and examples added.
    Last edited by red_Marvin; March 24th, 2011 at 03:05 AM.
    Don't peach linux. Melon it!

  6. #6
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginners Programming Challenge no.19

    The error reporting isn't quite the same, but I believe it works.

    PHP Code:
    import copy
    import sys

    class PlacementError(Exception):
        
    pass


    # from http://code.activestate.com/recipes/410687-transposing-a-list-of-lists-with-different-lengths/
    def transposed(lists):
        if 
    not lists:
            return []
        return 
    map(lambda *row: list(row), *lists)


    class 
    Board(object):
        
    def __init__(selfxy):
            
    self.blank "."
            
    self.board = [[self.blank for i in range(x)] for j in range(y)]


        
    def place(selfxydirectionword):
            if 
    >= len(self.board[0]) or >= len(self.board):
                
    raise PlacementError("Cannot place '%s' at (%d, %d) - out of bounds" % (wordxy))

            
    word "#" word
            
    if direction == "h":
                
    self.board self._place_horizontal(xyword)
            
    elif direction == "v":
                
    self.board self._place_vertical(xyword)
            else:
                
    raise ValueError("direction is not 'h' or 'v'")


        
    def _place_horizontal(selfxywordboard=None):
            if 
    board is None:
                
    board copy.deepcopy(self.board)
           
            
    edge len(word)

            if 
    edge len(board[0]):
                
    raise PlacementError("word goes off board: '%s'" % (word))
            
            for 
    i in range(xedge):
                try:
                    if 
    board[y][i] == self.blank:
                        
    board[y][i] = word[x]
                    
    elif board[y][i] == word[x]:
                        
    pass
                    
    else:
                        
    raise PlacementError("something's in the way ('%s', y=%d, i=%d)" % (wordyi))
                
    except IndexError:
                    
    raise PlacementError("off the edge ('%s', y=%d, i=%d)" % (wordyi))
            
            return 
    board


        def _place_vertical
    (selfxyword):
            return 
    transposed(self._place_horizontal(yxwordtransposed(self.board)))


        
    def __repr__(self):
            return 
    "\n".join("".join(self.board[j][i] for i in range(len(self.board[0])))  for j in range(len(self.board)))


    if 
    __name__ == "__main__":
        
    inf open(sys.argv[1], "r")

        
    lines inf.readlines()

        
    board Board(int(lines[0]), int(lines[1]))

        for 
    line in lines[2:]:
            
    args map(lambda xx.strip(), line.split(","))
            
    args = [int(args[0]), int(args[1])] + args[2:]

            try:
                
    board.place(*args)
            
    except PlacementError as e:
                print 
    board
                
    print e
                sys
    .exit(1)

        print 
    board 
    Last edited by schauerlich; March 25th, 2011 at 10:45 PM.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  7. #7
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginners Programming Challenge no.19

    Well, looks like I've got some stiff competition.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

  8. #8
    Join Date
    Aug 2005
    Location
    Sweden
    Beans
    407

    Re: Beginners Programming Challenge no.19

    Indeed, I'm halfway through a forth implementation 'just because', but I won't finish it on time, if at all, and it would be outside the competition anyway.

    Five hours and thirtyseven minutes left of the competition people!

    It would be good to know if the abundance of competitors are caused by lack of time, or if the challenge was too hard. "Beginner" can mean a lot of things.
    Last edited by red_Marvin; April 24th, 2011 at 09:42 PM. Reason: spelling, horrid horrid spelling.
    Don't peach linux. Melon it!

  9. #9
    Join Date
    Aug 2005
    Location
    Sweden
    Beans
    407

    Re: Beginners Programming Challenge no.19

    As the time for submissions are now over, I can now declare schauerlich to be the winner of this contest.

    Congratulations, and hoping that your no.20 Challenge to be will attract more participants.
    Don't peach linux. Melon it!

  10. #10
    Join Date
    Apr 2007
    Location
    NorCal
    Beans
    1,149
    Distro
    Ubuntu 10.04 Lucid Lynx

    Re: Beginners Programming Challenge no.19

    Quote Originally Posted by red_Marvin View Post
    As the time for submissions are now over, I can now declare schauerlich to be the winner of this contest.

    Congratulations, and hoping that your no.20 Challenge to be will attract more participants.
    Woot! Victory by default!

    I should have the next challenge up in a day or two, once I think of it.
    Posting code? Use the [code] or [php] tags.
    I don't care, I'm still free. You can't take the sky from me.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •