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 
1// http://code.google.com/codejam/contest
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,
78                        <Add <Mult s.int s.base> <Length e.head>> e.number2;           
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">,
94        <ReadLineCh s.in> : e,
95        1 $iter {
96                <ReadLineCh s.in> : ex, <WriteLn ex>, ex: e.n ' ' e.inf ' ' e.outf,
97                        <PrintLnCh s.out 'Case #'s.i': '<FromInt e.outf <ToInt (e.inf) (e.n)>>>,
98                        <Add s.i 1>;
99                <CloseChannel s.in> <CloseChannel s.out><Exit 0>, -1;
100        } :: s.i, $fail;
Note: See TracBrowser for help on using the repository browser.