# source:applications/trunk/UGPSummerSchool2008/src/Alien.rf@3840

Last change on this file since 3840 was 3840, checked in by yura, 12 years ago
• Program text for Alien.
• Property svn:eol-style set to `native`
• Property svn:keywords set to `"Author Date Id Revision"`
File size: 3.0 KB
Line
2//
3// Problem
4//
5// The decimal numeral system is composed of ten digits, which we represent as
6// "0123456789" (the digits in a system are written from lowest to highest).
7// Imagine you have discovered an alien numeral system composed of some number
8// of digits, which may or may not be the same as those used in decimal. For
9// example, if the alien numeral system were represented as "oF8", then the
10// numbers one through ten would be (F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF).
11// We would like to be able to work with numbers in arbitrary alien systems.
12// More generally, we want to be able to convert an arbitrary number that's
13// written in one alien system into a second alien system.
14//
15// Input
16//
17// The first line of input gives the number of cases, N. N test cases follow.
18// Each case is a line formatted as
19//
20//     alien_number source_language target_language
21//
22// Each language will be represented by a list of its digits, ordered from
23// lowest to highest value. No digit will be repeated in any representation,
24// all digits in the alien number will be present in the source language, and
25// the first digit of the alien number will not be the lowest valued digit of
26// the source language (in other words, the alien numbers have no leading
27// zeroes). Each digit will either be a number 0-9, an uppercase or lowercase
28// letter, or one of the following symbols !"#\$%&'()*+,-./:;<=>?@[\]^_`{|}~
29//
30// Output
31//
32// For each test case, output one line containing "Case #x: " followed by the
33// alien number translated from the source language to the target language.
34//
35// Limits
36//
37// 1 <= N <= 100.
38//
39// Small dataset
40//
41// 1 <= num digits in alien_number <= 4,
42// 2 <= num digits in source_language <= 10,
43// 2 <= num digits in target_language <= 10.
44//
45// Large dataset
46//
47// 1 <= alien_number (in decimal) <= 1000000000,
48// 2 <= num digits in source_language <= 94,
49// 2 <= num digits in target_language <= 94.
50//
51// Sample
52//
53// Input
54//
55// 4
56// 9 0123456789 oF8
57// Foo oF8 0123456789
58// 13 0123456789abcdef 01
59// CODE O!CDE? A?JM!.
60//
61// Output
62//
63// Case #1: Foo
64// Case #2: 9
65// Case #3: 10011
66// Case #4: JAM!
67
68\$module Alien;
69
70\$use StdIO Access Arithm Dos;
71
72\$func ToInt (e.system) (e.number) = s.int;
73
74ToInt (e.system) (e.number) =
75        <Length e.system> :: s.base,
76        0 e.number \$iter {
77                e.number : s.d e.number2 = e.system : e.head s.d e.tail,
79        } :: s.int e.number, e.number :, s.int;
80
81\$func FromInt e.system s.int = e.number;
82
83FromInt e.system s.int =
84        <Length e.system> :: s.base,
85        <DivRem s.int s.base> :: s.quo s.rem,
86        { s.quo : 0 = ; <FromInt e.system s.quo>;} :: ex,
87        ex <L s.rem e.system >;
88
89\$func Main = e;
90
91Main = <Channel> :: s.in, <Channel> :: s.out,
92        <OpenFile s.in <Arg 1> "R">,
93        <OpenFile s.out <Arg 2> "W">,