I posted this problem a little while ago on the site I used to run, and it proved to be an interesting one that resulted in quite a large collection of solutions from the posters. So here it is again.
Your job is to write a program that generates a text-based ruler. For a clearer definition of what I mean, see the little text pic below:
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The user of the program must be able to specify a couple of parameters: those being the height of the ruler and the number of sections in the ruler (at the top level). In the above example, the values would be 6 and 2 respectively. Another example, using the values 3 and 3 would result in:
| | | | | | | | | | | |||||||||||||
The only other thing that you have to do is make sure that your solution uses recursion instead of iteration. Feel free to use any language you want, you can write to screen or to file, it’s your call. But you must use recursion.
I look forward to seeing your responses. 
Happy coding!
October 13, 2006
Try the following (no formatting, just copied and pasted from VS):
using System; namespace Sandbox { /// /// Summary description for Class1. /// public class Ruler { public const char SPACE_CHAR = ' '; public const char RULE_CHAR = '|'; static void Main(string [] args) { // Simple check of the number of arguments. if (args.Length != 2) { Console.WriteLine("Please specify height, then number of sections."); return; } // Assuming that the arguments are correct integers. int height = int.Parse(args[0]); int numSections = int.Parse(args[1]); DisplayOutput(height, numSections); Console.ReadLine(); } /// /// Display output for the ruler from the given level down. /// /// Current height on the ruler. /// Number of sections to display. private static void DisplayOutput(int height, int numSections) { /* Distance between rules just happens to be 2^(height - 1) - 1. * This is because of the relationship between the number of * sections and the height. As you go up a level, distance to the * next section doubles. As we are going down, it halves. The * -1 is because we are not including the next rule in our * character count. */ // TODO: Get rid of the explicit cast and replace with something better. int distance = (int) Math.Pow(2, height - 1) - 1; Console.WriteLine(CreateDisplayLine(distance, numSections)); if (height == 1) { // Bottom level, nothing more to do. return; } // Number of sections doubles as you down each level. DisplayOutput(height - 1, numSections * 2); } /// /// Generate a line to be displayed. /// /// Distance between sections. /// Number of sections still to be /// generated. /// String containing the line to be displayed. private static string CreateDisplayLine(int distance, int numSectionsLeft) { if (numSectionsLeft == 0) { // No more sections, so we can add the last rule. return RULE_CHAR.ToString(); } // Add a section and generate additonal ones. return RULE_CHAR.ToString() + new String(SPACE_CHAR, distance) + CreateDisplayLine(distance, numSectionsLeft - 1); } } }October 13, 2006
Erm…I don’t really have the time to do this, but for some reason I can’t hold myself back. Before I start though, there are a few puzzling things in your examples above that don’t quite gel with me. Firstly, your 5 and 2 ruler has the correct number of sections it seems at the top level, and then recursively downwards as expected, but it looks like it’s height is actually 6? Your second 3 and 3 ruler looks to have the correct height (3), but only has 3 sections at top level, and then doesn’t follow the same pattern recursively downwards, but instead jumps to 2 sections per level instead of 3? Am I missing something here?
October 13, 2006
Sorry, I meant 6×2 in the first example (fixed in post). The 3×3 one is bang on how it should be
October 13, 2006
You say this is a 3 by 3:
but I say this is a 3 by 3:
I’m not sure what ruler pattern you’re talking about, but I do believe I’ve just shown you another way to do a 3 by 3, which you said was impossible. I also think my way is more in keeping with the recursive nature of this problem. As you can see, mine sticks to sections of 3 (the stipulated number of sections) all the way down. Yours goes from 3 sections up top, and then defaults to two sections for the rest of the levels no matter what the stipulated number of sections should be.
I know you said that the section number applies to the top level, but surely if you want to handle this problem using recursion, the pattern should be somewhat recursive and not jump around with “hard-coded” numbers of sections as you traverse the algorithm to produce the lower parts of the ruler?
I might be in for a generous helping of humble pie if you can prove me wrong, but then again..it IS your challenge, so you could just say I am wrong and tell me to get on with the solution
Either way, I’m sure it can be solved using recursion…
October 13, 2006
Rubbish! Looked ok in fixed width fonts
October 13, 2006
I fixed it for ya
Yes that’s another way of doing it, but that’s not what the spec says
October 13, 2006
hurrumph!
October 13, 2006
This is about as dirty as it gets
But I like dirty! Below you’ll find a C++ solution to the problem. I’ve hidden in by default so that you can choose not to look at it yet if you don’t want to.
#include <iostream> #include <math.h> void DrawRuler(int width, int row, int col) { if(row > 0) { std::cout << (col % (int)::pow(2.0, row) == 1 ? '|' : ' '); if(col == width) { std::cout << std::endl; DrawRuler(width, row - 1, 1); } else { DrawRuler(width, row, col + 1); } } } int main(int argc, char* argv[]) { // assume args are fine. (can't be arsed validating) int height = ::atoi(argv[1]); int sections = ::atoi(argv[2]); DrawRuler((int)::pow(2.0, height) * sections + 1, height, 1); }October 14, 2006
Come on people, we’ve only had one submission so far!
BTW, thanks for the post Taufiq
October 25, 2006
OJ is a Madura suckin’ girlie man
using System; namespace RecursiveRuler { class Program { static void Main(string[] args) { double height = GetUserNumericInput("Enter the height of the ruler:"); double numberOfSections = GetUserNumericInput("Enter the number of sections:"); DisplayRecursiveRulerLevel(height, numberOfSections); Console.Out.WriteLine("Press the 'Enter' key to exit"); Console.In.ReadLine(); } /* * Displays a particular 'level' of the ruler */ private static void DisplayRecursiveRulerLevel(double height, double numberOfSections) { if (height > 0) { double markerSpacing = Math.Pow(2, height); for (double sectionCount = 0; sectionCount < numberOfSections; sectionCount++) { for (double index = 0; index < markerSpacing; index++) { Console.Out.Write(index == 0 ? '|': ' '); } } Console.Out.WriteLine('|'); DisplayRecursiveRulerLevel(height - 1, numberOfSections * 2); } } /* * Prompts the user for a numeric input */ private static double GetUserNumericInput(string promptMessage) { bool numericValueEntered = false; double userInput = 0; while (numericValueEntered == false) { try { // Get the numeric value entered by the user Console.Out.WriteLine(promptMessage); userInput = Double.Parse(Console.In.ReadLine()); numericValueEntered = true; } catch { Console.Out.WriteLine("Please enter a numeric value."); } } return userInput; } } }October 25, 2006
Madura Tea for the win!
November 16, 2006
Aw, missed this challenge when it was posted…