|
Quick Links
New to Algorithms?
New to IRC? IRC Clients IRC Servers Enter #algos at irc.freenode.net |
Introduction #Algos @ Freenode is an Algorithm Discussion Channel, and to provide some "fun besides the service", we invite everybody to program on these Tasks. You can /join #algos, discuss algorithm, talk about it generally and so on. If you like, you send the Operators of the Channel your source-code - If the community think the code is really good, we will upload it here ( if its Open Source ;) ). task01: "Symbolic AI". Write a short parser for some basic, syntaxed inputed strings. The code must answer the questions the user asks him. Click Here For Details task02: A table with 1 million records. {name char[25], phone char[15]} (Real Life Phone Directory). We need to develop a program to store that struct in memory and perform sort (name) and look ups in that table. code should do the job fast (+3) and use the least amount of memory (+1). Click here for Details You have been given the job of writing a simple symbolic AI processor, which will be told some facts, and asked some questions. The AI processor must then try its hardest to answer the questions. Fortunately, these facts and questions relate only to specific individuals, who are in groups (collective nouns) which perform actions (verbs) on other groups. The grammar used is very simple: there are two types of statements and one type of question, and all nouns are made plural through the expedient of adding an s. Each line of the input contains either a simgle sentence or a blank. The end of the input is indicated by a line whose first character is a #. Each sentence has one of the following forms: 1. A statement of the form "as v bs.",where a and b are nouns and v is a verb. This means that everything of type a does v to everything of type b. 2. A statement of the form "a is a b.", where a and b are nouns. This means that the particular individual a is of type b. 3. A question of the form "Does a v b?", where a and b are nouns and v is a verb. This asks whether the individual a does the action v to the individual b. Lines are up to 80 characters long. Words are up to 40 characters long and may consist of upper and lower case letters, although all searching is done case-insensitively. There may be more than one space between words, but there are never any spaces between words and the punctuation marks at the end of each sentence. Allow for up to 100 facts in the input. For each question in the input, print a single line contains "Yes.". If the preceding input implies that the question is true, and "no" otherwise. Sample input: Fluffy is a Dog Hub is a Fluffy Bobo is a Hub wuher is a Cat Hut is a wuher John is a Hut Dogs eat Cats. Does Hub eat Hut? Does John eat Fluffy? #Output: yes no See Posted Solutions- Try to improve and post better solutions. (The Posted solutions are Open Source) We have a medium sized database (1 Million Records) of (name char(25), number(15)) consisting of entries from a real life phone directory. The name consists of alphabets and the number is plain number. +30-482-4928282 is represented as just 00304824928282. The names are case insensitive. Now you need to develop a program which can sort the database, store it and perform lookups on it. The aim is to get maximum speed while using minimum/low memory storage. (Also implement insert record and update record functionality) Speed is weighted +3 and memory usage is weighted +1. Thus a 10% improvement (increase) in speed is better than 29% improvement (decrease) in memory space requirement. The test input file shall be made available soon. (Till then try to implement your own and if you are able to make a 1 Million Records data store of real life names and numbers ... post it to us) Sascha "lantis" Retzki, speaking for the team |
News 23 May 2004
20 May 2004
08 May 2004
07 May 2004
|