1. Computing

Programming Challenge 67 - Build Loops

Competition Complete

By

Back three years ago, challenge 32 was one of those that attracted no entries. I think it's time to redo it but in a simpler form.

Back in the early 90s there was a computer puzzle called Loopz that was very addictive. You were given composite pieces (made up of single pieces horizontal, vertical and corners) and had to form loops on a board.

You never knew what piece was coming next and had only a certain time to play it before the next arrived. Once a loop was formed, it was removed from the board and the game continued. If you couldn't complete loops then you'd eventually put the pieces anywhere and soon run out of space.

You can watch a video of someone playing the NES (I think) version on Youtube.

The Challenge

There are six characters that are used to make up a loop. To make it easier to understand I've used the numbers from a numeric keypad

789
654
123

So 7,9,1 and 3 are the four corner chars (7 is top left, 3 is bottom right), 8 is the horizontal and 6 is the vertical. The 5.4 and 2 characters aren't used.

The simplest loop is :

79
13

A longer loop might look like this:

788889...
6....1889
6.......6
1889....6
...188883

A definition of a loop is a 2D set of chars touching horizontally or vertically that fits in the 18 x 7 grid which has a minimum of all four corners and satisfies the allowed chars rules below.

Allowed Char Rules For Forming Loops

These rules specify what characters are allowed next to each other to form a loop.

  • A 7 can be next to an 8 or 9 horizontally and 6 or 1 vertically.
  • A 1 can be next to an 8 or 3 horizontally 6 or 7 vertically.
  • A 9 can be next to an 8 or 7 horizontally 6 or 3 vertically.
  • A 3 can be next to an 8 or 1 horizontally 6 or 9 vertically.
  • An 8 can be next to a 1,3, 7, 8 or 9 horizontally.
  • A 6 can be next to a 1,3,6 7, or 9 vertically.

The playing area of 18 x 7 squares (same as in loopz) read a text file full of chars (from the same location as your exe) and place them to form loops.

Placing Chars

You can place a char in any location that is empty. After placing the char your code should attempt to detect if a loop has been placed. It's perfectly ok to place a char next to another char that would not form a loop like 37 or 11.

Your code cannot move a char once placed.

Detecting Loopz

You have to write a piece of code to detect a loop after your char is placed. That is when you place a char. If there is a continuous set of chars leading from it that follows the rules and leads asll the way back to the character you just placed. If there is a loop then after outputting the board to the output file (see below) your code must remove every character in that loop.

Erase Char

Occasionally, about 1 in 25 pieces will be * and by playing this on any char, if its a corner you remove it. If it's a length (i.e. 6 or 8) then you must remove all the adjacent 6s or 8. If there are 5 8s in a row then playing the * on any one of them removes all five.

Game Play and Scoring

You are provided with a text file full of chars in the same location as your exe called chars.txt. It consists of 10,000 chars made up of 7,9,1,3,6,8 and *.

Your program should repeatedly do the following:

  1. Read a char from the file. (Loading all into memory first is allowed)
  2. Place the char in any empty cell in the grid.
  3. Check if it formed a loop and if so add on points (see below) and clear every cell in the loop.
  4. If it couldn't place the character, stop.

Scoring Loops

Each loop generates a score = (length in chars) squared. You get 16 for the smallest 4 char loop as 4 x 4 = 16. The second example is 24 long so 24 x 24 = 576. Total these up and when your program can no longer place a char, print the total score.

Output

Please output a text file output.txt in the same loc as your exe called output.txt. Every time your program completes a loop, write the full block of 18 x 7 characters to the textfile *use a period for empty cells) before your program removes the loop. Before this is output, write a single number showing how many characters have been read and the total score.

Example Output

8 Total Score = 64
..................
....7889..........
....6889..........
..................
..................
..................
..................

This assumed that the first 8 characters could be placed like that which is most unlikely. There's no need to show where * removed the characters.

Winning Criteria

The highest total wins. Note there will be a different chars.txt used than the one given here. It should take no more than one minute to run.

Final Results

There were two entries and new entrant Fera Louca wins with an excellent score. Thanks to Mark Mammel. Boith took about the same time.

  1. Fera Louca() Result=157448, Time = 0.0260759 (Portugal)
  2. Mark Mammel(C++) Result=10368, Time = 0.02300324 (USA)

General Tips on Entering

This is a single page article with tips on things to do and not do when entering challenges. Please read it!

These tips contain code for C,C++ and C# (Not Go, yet) that can do very high precision timing.

Rules

This is for glory only. About.com does not permit prizes to be given.

Please submit your source code and the output file to the cplus@aboutguide.com?subject=Programming Contest 67 email address with the subject line Programming Contest 67.

It must compile with Open Watcom, Microsoft Visual C++ 2010/2012 Express Edition/Microsoft Visual Studio 2010/2012, CC386 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 Express Edition, GCC/G++ and any Google Go compiler. If it doesn't compile, it can't be run so is automatically disqualified.

Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is March 3, 2013.

The top ten entries in each challenge will be listed, judged on highest score and in the case of a draw, the fastest time. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.

  1. About.com
  2. Computing
  3. C / C++ / C#
  4. Programming Challenge List
  5. Programming Challenge 67 - Build Loops

©2014 About.com. All rights reserved.