I wonder if anyone would care to provide a clue to this enthusistic
noob: This problem was originally devised to compare C++ solutions to
Java, but then Erann Gat offered it as a Lisp competition, and Peter
Norvig provided a solution and some more commentary. Various other
scripting languages have had a go at it, too.
I thought it would have a very elegant solution in Oz, using the
relational style of CMT's chapter 9 - rather than doing it the boring
old functional way - and indeed it does. It barely took me longer than
Norvig to formulate the basic idea (instead of 10x longer, as I
expected!!), so I thought, we-hay, now we're cooking. Trouble is, it
doesn't work. :(
The idea is basically to use a given dictionary to encode phone numbers
into words, where each key corresponds to some letters (in the old US
style, not like today's mobiles, I might add). So, thinking I would do
it in the style of Prolog, I saw the main loop as the equivalent of
something like
encode([],[])
encode(Numbers,W|Words):-
split(First,Rest,Numbers),
corresponds(First,W),
encode(Rest,Words).
where split works a bit like the non-deterministic append/3 but
backwards, e.g. splitting "string" into
«string-''/strin-g/stri-ng/str-ing/st-ring/s-tring», and then working
recursively. corresponds/2 just checks the number-string for a match in
the dictionary.
What makes the problem a wee bit more interesting, is a few extra rules.
For instance, if a word can't be found starting with a certain number,
it is OK to use the number itself in place of the first letter.
Further, if we have just done so, we cannot do so again in immediate
succession, i.e. digits can't follow each other in the code. So "1 jon
blogs" is OK but "1 9 on blogs" (assuming j is coded by 9) isn't; "1 jo
4 blogs" is OK (n:4); 1 jon 2 logs"(b:2) is not a valid coding because
there COULD have been a word (blogs) in place of the "2" (this is the
other rule).
Sorry this is not too clear but can see the links for full description,
elsewhere.
In the end, my main Oz parsing routine looked sumat like this
proc {Encode NumberStr Words PrevIsNum}
First Rest Word WList CurrIsNum
FoundWord = {NewCell false} %***
in
choice
NumberStr = nil
Words = nil
[]
Words = Word|WList
{Splitter First Rest NumberStr} % recursively split the word
choice
% a word for this number seq. does exist
{Corresp First Word}
CurrIsNum = false
{Assign FoundWord true} %***
[]
% there was no word, use the single digit
{Length First 1}
% check that we are not following a digit
PrevIsNum = false
{Access FoundWord false} %***
First = Word
CurrIsNum = true
end
{Encode Rest WList CurrIsNum} % Recursive Call
end
end
This is then invoked with something like...
fun{GetAllEncodings NumStr}
proc{Encd Words} {Encode NumStr Words false} end
in
{SearchAll Encd}
end
Now, the program parses and converts the numbers correctly, and it also
takes account of the "no two digits in a row" rule correctly.
What it DOESN'T do, is stop the "digit" branch of the choice, as it
should if a word has already been found at that position. I tried to
implement this by setting a Cell (FoundWord) at the beginning of each
call to {Encode N L B} I set it to "false" and then assign it as
"true" if a word value IS found, as marked *** above (hey, I know this
isn't concurrent or anything, I'm trying to crawl before I start running
:) )
The statement {Access FoundWord false} always succeeds, whereas I
expected it to fail if a word had already been found, since then it
would have been assigned to "true".
Which makes me wonder if I have copletely failed to understand the
scoping - as I see it FoundWord should ba available anywhere inside the
Encode call, even inside the nested choices.....
If anyone feels like helping I would very much appreciate it, I would
also happily upload it as an exapmle if none of the "old hands" sees any
screaming errors. I think it is much more elegant than the Lisp
equivalent, not quite as elegant as the Prolog, but then you pay for
Prolog through all the _normal_ stuff it CAN'T do....
=====
My Code:
http://aegean.pwp.blueyonder.co.uk/store/tel.oz
http://aegean.pwp.blueyonder.co.uk/store/dict.txt (data)
(You may notice that I added a Pos variable to the call. This was when
I thought I'd try using a global Dictionary instead of a Cell. I was
informed by the system that I can't assign to a global dict from inside
a local proc! ho-hum)
Peter Norvig's Lisp version
http://www.norvig.com/java-lisp.html
The Erann Gat Lisp challenge.
http://alvin.jpl.nasa.gov/gat/ftp/study.txt
(I couldn't reach this site, which is a pity because the clearest
problem description is here. I'll try find it elsewhere, or scan-upload
my hardcopy,if anyone asks)
Cheers All
Alex
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
