I was playing around with a PEG parser to do what you wanted (and may post that as a separate answer later) when I noticed that there's a very simple algorithm that does a remarkably good job with common forms of numbers in English, Spanish, and German, at the very least.
Working with English for example, you need a dictionary that maps words to values in the obvious way:
"one" -> 1, "two" -> 2, ... "twenty" -> 20,
"dozen" -> 12, "score" -> 20, ...
"hundred" -> 100, "thousand" -> 1000, "million" -> 1000000
...and so forth
The algorithm is just:
total = 0
prior = null
for each word w
v <- value(w) or next if no value defined
prior <- case
when prior is null: v
when prior > v: prior+v
else prior*v
else
if w in {thousand,million,billion,trillion...}
total <- total + prior
prior <- null
total = total + prior unless prior is null
For example, this progresses as follows:
total prior v unconsumed string
0 _ four score and seven
4 score and seven
0 4
20 and seven
0 80
_ seven
0 80
7
0 87
87
total prior v unconsumed string
0 _ two million four hundred twelve thousand eight hundred seven
2 million four hundred twelve thousand eight hundred seven
0 2
1000000 four hundred twelve thousand eight hundred seven
2000000 _
4 hundred twelve thousand eight hundred seven
2000000 4
100 twelve thousand eight hundred seven
2000000 400
12 thousand eight hundred seven
2000000 412
1000 eight hundred seven
2000000 412000
1000 eight hundred seven
2412000 _
8 hundred seven
2412000 8
100 seven
2412000 800
7
2412000 807
2412807
And so on. I'm not saying it's perfect, but for a quick and dirty it does quite well.
Addressing your specific list on edit:
- cardinal/nominal or ordinal: "one" and "first" -- just put them in the dictionary
- english/british: "fourty"/"forty" -- ditto
- hundreds/thousands:
2100 -> "twenty one hundred" and also "two thousand and one hundred" -- works as is
- separators: "eleven hundred fifty two", but also "elevenhundred fiftytwo" or "eleven-hundred fifty-two" and whatnot -- just define "next word" to be the longest prefix that matches a defined word, or up to the next non-word if none do, for a start
- colloqialisms: "thirty-something" -- works
- fragments: 'one third', 'two fifths' -- uh, not yet...
- common names: 'a dozen', 'half' -- works; you can even do things like "a half dozen"
Number 6 is the only one I don't have a ready answer for, and that's because of the ambiguity between ordinals and fractions (in English at least) added to the fact that my last cup of coffee was many hours ago.
Perl, 166 160 characters
Perl, 251 248 246 222 214 208 203 201 193 190 180 176 173 170 166 --> 160 chars.
Solution had 166 strokes when this contest ended, but A. Rex has found a couple ways to shave off 6 more characters:
s!.!$t{$s++}=$&!ge,$s=$r+=99for<>;%d='>.^1<2v3'=~/./g;($r)=grep$d|=$d{$t{$_}},%t;
{$_=$t{$r+=(1,-99,-1,99)[$d^=3*/\\/+m</>]};/[\/\\ ]/&&redo}die/x/?true:false,$/
The first line loads the input into %t
, a table of the board where $t{99*i+j}
holds the character at row i,column j. Then,
%d=split//,'>.^1<2v3' ; ($r)=grep{$d|=$d{$t{$_}}}%t
it searches the elements of %t
for a character that matches > ^ <
or v
, and simultaneously sets $d
to a value between 0 and 3 that indicates the initial direction of the laser beam.
At the beginning of each iteration in the main loop, we update $d
if the beam is currently on a mirror. XOR'ing by 3 gives the correct behavior for a \
mirror and XOR'ing by 1 gives the correct behavior for a /
mirror.
$d^=3*/\\/+m</>
Next, the current position $r
is updated accoring to the current direction.
$r+=(1,-99,-1,99)[$d] ; $_ = $t{$r}
We assign the character at the current position to $_
to make convenient use of the match operators.
/[\/\\ ]/ && redo
Continue if we are on a blank space or a mirror character. Otherwise we terminate true
if we are on the target ($_ =~ /x/
) and false
otherwise.
Limitation: may not work on problems with more than 99 columns. This limitation could be removed at the expense of 3 more characters,
Best Answer
Ok, I think it's time for my own implementation in Windows BATCH script (should work on Windows 2000 or later).
Here is the code:
This is the test script I used:
And this is the output I got from my test script:
If I could find some more names of large numbers, the script would support even bigger numbers. Currently, though, the script will work with all numbers from -(10^66-1) to (10^66-1).
I have to mention, that I had a lot of fun solving this in BATCH. :)