Thursday February 14, 2008 Alphametic Solver in C
|
At the last library book sale in Saratoga, I bought a copy of an old Journal of Recreational Mathemetics magazine for a quarter. Near the back were several alphametic problems. |
I decided to see if there were any freely available programs around to solve this type of puzzle.
There is a nice online solver by Truman Collins which looks like it's been there for at least 10 years.
I also found a version in C written a couple of years ago by Anuj Prateek and Upendra Singh.
(Update: The alphametic puzzle solver is not written by Prateek and Singh. The original code is by Naoyuki Tamura. See this post (and its comments) for more details.)
At the moment, it just does alphametic addition problems. If I had to guess, I'd say this was one of their first C programs and possibly done because of school work. The formatting and indentation was lousy and there were a load of things that newcomers to C do (such as returns at the end of functions when they aren't needed and two printf statements where one would do). But Burridge's Rules of Programming are:
- Get it working.
- Get it better.
- Get it faster/smaller.
and they've already done #1 so this wasn't a big deal.
But to try to understand it, I decided to tidy it up. I made the following changes:
- Changed the program name from "crypt" to "alphametic". There is already a "crypt" program on my machine.
- Added a bunch of newlines, consistent formatting and four space indentation to make the code more readable.
- Removed all Tabs. Repeat after me, tabs are evil.
- Included the .h file contents in the single .c source file.
- Included the README file contents in the single .c source file.
- Removed the Makefile and added a comment at the top to tell people how to do a simple compile.
- Rearranged the order of the various routines so that function prototypes aren't needed.
- Removed #include lines that weren't needed.
- Adjusted so that there was a single statement per line.
- Removed the useless calls to "system("cls") and the initial bogus gets call.
- Adjusted the initial message that's displayed, to add the line:
"\nTYPE 'HELP' FOR HELP\n". - Added a simple "> " prompt at the start of each line where the program wants input, so you at least have an idea that you are required to enter something.
The new self-contained single source file is here. There are lots of other places where the code could be improved (like adding comments and better string handling), but I stopped there.
After looking at this, I'm convinced that it's just crying out to be converted to something like Python. The setjmp/longjmp code would naturally become try/except clauses and raising an exception. Some of the other routines that are several lines long would be simple one-liners in Python.
Hopefully I'll have some more time soon to try this, and also expand it so that it solves other alphametic puzzles apart from addition.
( Feb 14 2008, 07:39:11 AM PST ) [Listen] Permalink Comments [7]
Comments are closed for this entry.
![[ Registered ]](http://www.diarist.net/registry/button.gif ){kind=small}
So the general rule is that the more trivial something is, the more people like arguing about it (commenting styles, tabs vs spaces).
But I've never seen a good argument for why people should use spaces for indentation. To me, that should get the same sort of mocking that someone would get if they made their webpage a giant png file.
Posted by Andy on February 14, 2008 at 10:40 PM PST #
Hi Andy,
You mean "why use spaces instead of Tabs?"
The argument for me is simply that you can't
be certain the size of the Tab (i.e. the
equivalent number of spaces). I've got mine set
to 8 spaces. Others have 4 or 2 (or maybe even
something else). Therefore if you use Tabs with
code, some people are going to see the wrong
formatting and indentation.
Now you're probably thinking that nowadays folks
should be putting something in their code like:
/*
Local Variables:
mode: c
c-basic-offset: 4
End:
*/
But not everybody uses emacs (or other tools
that understand this).
It's simpler to just use spaces (or not, if you
are Prateek and Singh).
Posted by Rich Burridge on February 15, 2008 at 07:34 AM PST #
But I myself use different tab widths on different computers. On my laptop with a smaller screen, I use a tab width of 2 spaces. On my desktop with a larger screen I use a tab width of 3.
The "wrong formatting and indentation" is something which depends on the constraints of the display device, and the preferences of the user. Give an example of a file with tabs for indentation where the formatting messes up with a different tab size.
Posted by Andy on February 15, 2008 at 05:05 PM PST #
> Give an example of a file with tabs for
> indentation where the formatting messes
> up with a different tab size.
Any Python source file which has 4 space
indentation and where the developer wrote
it expecting a Tab to be 8 spaces.
Posted by Rich Burridge on February 15, 2008 at 05:20 PM PST #
That's an example of a file with spaces for indentation.
When I write a file using tabs for indentation, I make no assumptions about the width of the tabs, and there don't seem to be any problems. What exactly is the problem have?
Posted by Andy on February 16, 2008 at 05:42 PM PST #
http://mail.python.org/pipermail/python-list/2003-January/183758.html
He says it much more eloquently then I ever could.
Posted by Rich Burridge on February 16, 2008 at 06:15 PM PST #
Such a good holy war :)
All of his arguments are variants of "someone will come along and use spaces" (The first batch of arguments assume the user has an editor that inserts spaces instead of tabs... the problem here is the spaces, not the tabs. The second is in assuming that the editors auto-indent replaces spaces with tabs, which is a bug, and doesn't happen in the editor I use (gedit)).
His first argument could easily be turned around the other way: "Don't use spaces, because if someone comes along and uses tab to line things up, then it screws everything up". The second argument doesn't matter if you fix the bug.
I think I'll call it quits here, unless something new comes into the discussion :)
Posted by Andy on February 19, 2008 at 04:11 AM PST #