Rosetta Code:Village Pump/Suggest a programming task

From Rosetta Code

So you want to see a problem solved? If you're not comfortable creating the task page yourself, feel free to edit this page, and describe the problem below. (To edit this page, click the "edit" tab at the top.) You also might want to check out the draft tasks to see if someone has already suggested one and partially produced the page; if so, just help them out by supplying what's needed to take the page from draft to full task.

When making a request, please place it in the Unsorted section. Also, feel free to review the others that are already here; help sort them into the other categories, based on the category descriptions. (If we need another category or two, you can create them.)

Incomplete

General

  • Zipping sequences (calculating their convolution) and unzipping
  • Date Calculations
    • Calculate Self-describing numbers
    • Calculate age given a birthdate
    • Calculate number of [years|days|hours|minutes|seconds] since some date or time
    • Calculate difference between two times
    • Sum a time and a time interval
    • Calculate day of week given a date
    • Calculate day of month given a date
    • Calculate day of year given a date
    • Calculate [first|second|third|fourth|last] [Sunday|Monday|Tuesday|Wednesday|Thursday|Friday|Saturday] of month
    • Calculate number of [Sundays|Mondays|Tuesdays|Wednesdays|Thursdays|Fridays|Saturdays] in a given month or year
    • Display a date in various formats
  • Show creation, element insertion, element removal and enumeration of a "set" type that enforces constraints as described here. (An invariant analog would be nice as well.)
  • The Object oriented category is missing a lot of the basics like calling a method.
  • Explicit implementation of various design patterns
    • Multiple dispatch (aka multimethods)
      • Written in such a way that languages don't necessarily have to use multi-methods if they don't have them? --Paddy3118 19:46, 23 July 2010 (UTC)
        • I'd be in favor of that. I've written that one myself. --Michael Mol 02:43, 24 July 2010 (UTC)
  • Closures
  • an encryption program
    • What s

API-specific

  • Provide a SOAP server function

Library-specific

  • Create a COM client (with early binding) (particularly with GCC/MinGW) (if possible under Winelib in linux is also interesting)

Implementation-specific

Language-specific

Duck typing specifically my DuckDecoy Example? --Paddy3118 18:28, 5 May 2009 (UTC)

The example is a bit confusing, but I think it's marking the difference between classes as true types and classes as patterns (with method invocations as message sends), yes? –Donal Fellows 08:22, 3 January 2010 (UTC)

A language called LC3 is a great tool for students wishing to learn assembly and wish to see what is actually in the RAM space. It is extremely simple. I think a language page would be worth the trouble. I have a few old examples that I can add in this language. --Michael Chrisco 12:35, 26 July 2010

Project level

If possible, find ways to break these into smaller tasks which can ultimately be assembled into the final project.

Super Simple p2p network

Could be done with FIFOs for streams, and a constant number of clients. Needs to be more specific regarding what it does. --Short Circuit 22:28, 6 December 2007 (MST)
probably means some thing like this http://ansuz.sooke.bc.ca/software/molester/molester. To make it suitable for rc the restrictions need to be spelt out - i.e. fixing the protocol and discovery mechanisms Rahul 20:24, 7 October 2008 (UTC)

A table-based native code assembler

implement a table-based native code (macro?) assembler in various HLLs

Stateful behavior simulation

Demonstrate discrete event simulation and stateful behaviour by simulating a simple pick-and-place or storage/retrieval system robot. The robot would be given commands to retrieve from location A and place into location B. The robot would in turn command its 4 motors in sequence in order to accomplish the task. The amount of time that a motor runs would be dependant on the distance required to move. A scheduler would be set up to generate callback events to the motors at proper times to indicate their motion was complete. The complete specification of this task would be somewhat involved. --Rldrenth 18:09, 20 January 2009 (UTC)

This needs to be simplified/clarified from requiring "four motors" to having three commands, "set velocity forward/back", "no-op" and "claw open/close".
Subsequently, it can be divided into four parts:
  1. Call a function at a constant interval
  2. Create a function which reads from a primary queue containing simple commands and a secondary queue containing complex commands, processing exactly one of these commands, and then calls the state update function.
  3. Create a function that converts a complex command "starting from x1, pick up at x2 and drop at x3" to one of the three simple commands
  4. Create a function that updates the state (velocity and position) based on the currently executing command.

In the interest of simplicity, it can be assumed that the program may terminate once the secondary queue is empty, that the robot has a constant velocity either forward or backward, and that the velocity and position values at termination are irrelevant. --Short Circuit 05:40, 19 May 2009 (UTC)

Unit test framework

Demonstrate the use of a unit test framework for your language

Is Test a function a suitable demonstration? –Donal Fellows 11:41, 26 February 2010 (UTC)

Simple Shell

Execute system commands, pipes, I/O redirection, command history, custom PATH variable, etc. --CheesyPuffs144 01:44, 9 August 2009 (UTC)

Prolog interpreter

The Prolog's syntax looks incredibly simple, and I'm wondering how difficult it would be to write a prolog interpreter in various langauges. --Michael Mol 08:21, 13 November 2009 (UTC)

Interesting and relevant suggestion, Michael. Many such projects exist for reference, including Norvig's in "Paradigms of Artificial Intelligence Programming," Paul Graham's in "On Lisp," the interpreter that is part of Poplog, and PyPy's. User:qu1j0t3

Prolog's syntax seems relatively simple, when compared with some other languages, but I do not think it is "incredibly simple". For example, it has three distinct syntaxes for function calls, three different kinds of operators (prefix, infix and postfix), operator precedence, various forms of control flow syntax, and so on... --Rdm 02:16, 3 September 2010 (UTC)
Even though Prolog's syntax is simple, there is a rather elaborate parser necessary (including redefining operators and precedence, IIRC) plus the runtime operation of Prolog is rather complicated to implement (SWI-Prolog for example is quite a large project), this would only be feasible if you define a subset of Prolog (e.g. only logical terms). --AlexLehm 10:30, 28 October 2011 (UTC)
Edinburgh Prolog standard has rather elaborate character definition syntax. Prolog parser is anything but trivial. WillNess 08:43, 2 December 2011 (UTC)

Compact Whitespace interpreter

Implement a whitespace interpreter such that the program used to implement it is as small as possible while still correctly implementing whitespace

Unsorted

Place new items here, if it's unclear where they belong.

See this IRC discussion for more information -- Erik Siers 05:46, 21 November 2011 (UTC)
  • Perlin Noise, Simplex Noise, Worley Noise implementations

http://en.wikipedia.org/wiki/Perlin_noise http://en.wikipedia.org/wiki/Simplex_noise http://en.wikipedia.org/wiki/Worley_noise https://gist.github.com/304522 http://libnoise.sourceforge.net/

  • Perlin Noise, Simplex Noise, Worley Noise implementations for tiling system in video games or other media
  • Thread safe circular buffer: Using mutexes or semaphores to conduct thread safe and robust read and writes from a circular buffer.
  • Phonecode: Given a list of words, and a telephone number, find all possible encodings of that telephone number by words. This task has already been used in a few comparative studies of language performance and productivity, for example [1]
Thanks so much for that link! I had read the paper some time ago but I probably have the link on an old hard drive somewhere...
You have to remember though, that the aims of RC are very different to the authors of that paper and any task would have to be written for RC. If anyone has the number to a cold-calling firm, we could find the most appropriate phrase for their number ;-) or maybe not. --Paddy3118 08:15, 7 May 2011 (UTC)
Here's an easy one. The phone number to the White House switch board: 202-456-1414. Nothing specific or political intended here; it's just a published, public number. I do like the task idea, though. --Michael Mol 13:15, 8 May 2011 (UTC)
  • Project Euler problems
  • I suggest implementations of various maze generation algorithms, such as Recursive Division or Prim's Algorithm. A website that already does this for Python can be found here: http://weblog.jamisbuck.org--Intercoder 12:57, 7 March 2011 (UTC)
  • My suggestion is for a unicode interpretation task. Specifically, specifying the encode eg utf-8, the task should provide a small file of text (or the data to programmer could be bytes of data instead). The task should be to depict (interpret) the data in a number of forms, for instance text, binary,hex. This would highlight features of some languages for handling Unicode and gain the user related xperience with parsing strings, string-numeric conversion, etc (I did see http://rosettacode.org/wiki/Character_codes)--Billymac00 02:21, 3 January 2011 (UTC)
  • Breadth-first search (BFS). Given an n-ary tree, enumerate all the leaves of the tree in breadth-first, left-to-right order and collect them into a list.
Isn't most of that captured in Tree traversal? --Paddy3118 14:58, 3 November 2010 (UTC)
  • Particle Swarm Optimization (PSO) implementation. A test case would be something like finding the global minimum of the banana function using PSO. An optional addition to the task would be to implement the algorithm using concurrency/parallelization techniques. The task is inherently parallel. --Treefall 23:32, 30 August 2010 (UTC)
  • Financial functions. E.g. Future Value, Present Value, Nominal declining balance depreciation, Straight line depreciation, Uneven internal rate of return, Weibull analysis, T-Bill Discount ... and the list goes on. Examples: the value of time --Axtens 14:29, 20 March 2010 (UTC)
  • Not sure where to put this, but could we prefix all the statistics-related tasks with "Statistics/"? All the average and means are bunched up together but poor old standard deviation is an outlier. --Axtens 05:21, 24 February 2010 (UTC)
  • Put all examples of a given language into a single page/file for easy reference, some extra comments differentiating where examples begin and start. That would be really nice, users can do a pdf print of the page:)
The page would be too long. --Paddy3118 15:06, 26 February 2010 (UTC)
That's something that's been discussed on and off for a couple years. The key problem is logically dividing examples, moving them to a separate area, and using transclusion to pull them back. I created a "Example" wiki namespace specifically for the purpose. --Michael Mol 15:59, 26 February 2010 (UTC)
  • Concise code/expressiveness: Not exactly a task but: for a given language and task measure the code size(preferably excluding comments), then compare to all other languages that have completed that task. list the percentile rank of this language+task's code next to the task name. For a given language, average all its percentile ranks and list next to language name in the main list.
Any measure of concision would need a metric for both code size and code clarity. Your proposed measurement of just code size would lead to code "golfing". I think it is better for the examples to be written as idiomatic examples of a language that either fulfils the entirety of a task description, or at least states what is missing. --Paddy3118 03:25, 1 September 2010 (UTC)
Agreed. While code golf is sometimes awe-inspiring, it's typically of horribly low value because it leads to things that people can't read. We're not exploring the Kolmogorov Complexity of a problem, we're showing how a task should be done in many languages (i.e., with good style; making code the way we'd like it to be if we encountered it). –Donal Fellows 09:59, 1 September 2010 (UTC)
  • Seeing as we have GCD (greatest common divisor), how about LCM (lowest common multiple), HCF (highest common factor), and Chebyshev function. --Axtens 09:21, 17 February 2010 (UTC)
    • Isn't HCF the same thing as GCD? --164.67.235.79 09:45, 17 February 2010 (UTC)
      • (blush) oops, so it is. --Axtens 11:56, 17 February 2010 (UTC)
  • Sets: AddToSet, RemoveFromSet, IsSubset etc. VBScript would have to construct something. Other languages have it already. --Axtens 07:11, 11 February 2010 (UTC)
  • non-JSON serialisation (what Tcl does, for instance, writing data out to a text file that can then be 'source'd at another time.) --Axtens 02:48, 10 February 2010 (UTC)
  • File creation time (there is already File modification time, which can be used for File access time with atime instead of mtime, but there's nothing in utime.h for creation time )
  • Add the other Soundex variants to the Soundex task or create separate tasks for each of them. --Axtens 07:27, 4 April 2010 (UTC)
  • Given wp:cron I suggest a three part task:
    1. Parse a simplified crontab (no ranges or asterisks)
    2. Issue the commands in the simplified crontab at the appropriate times
    3. Handle a standard crontab with ranges and asterisks
    I'd have created the task already but that all my code is still on paper. --Axtens 14:21, 20 April 2010 (UTC)
  • wp:Gray code. Specifically, construct and n-bit Gray Code that satisfies the restrictions for the Beckett-Gray code, or show that no such code exists (3-bit and 4-bit happen to fall under the "can't satisfy" set, for example). A task like this is interesting for it being Gray Code, and for the matching against the Beckett-Gray code being accelerable by languages with good support for concurrency, and more easily expressed by languages which express data set problems. (All the details required for solving this problem are on the WP page) --Michael Mol 12:34, 19 May 2010 (UTC)
This sounds like it would be more appropriate for Project Euler than Rosetta Code: How many useful programming projects really need an implementation of a Becket-Gray search? And, how much would a typical programmer learn about translation by studying such implementations? --Rdm 14:11, 19 May 2010 (UTC)
I never thought of RC as about studying translation. The closest to that is studying unfamiliar languages by seeing a task implemented in a familiar one. Project Euler focuses on implement before observation, where RC is geared more towards observation, and implementation if nobody's already provided it. Apart from being an interesting curiosity (you'd be surprised how many people who actually stick around and look at code came in on curiosity pages like Ethiopian Multiplication and Quine; come for the show, stick around and contribute code), the task I described allows code langauges to exercise dataset manipulation and idiomatic examples of concurrency, the latter of which, at least, doesn't have much presence on the site. --Michael Mol 18:31, 19 May 2010 (UTC)
But a Beckett Gray search has only one interesting case (5 bits wide). The 6 bit wide case takes 15+ hours which makes testing a 6 bit solution for accuracy problematic, the 0, 1 and 2 bit cases are trivial, and the 3 and 4 bit cases are not doable (and what does it mean to "show that no such code exists"? Is reporting that the last value in the found sequence has 3 bits set sufficient?). [And, if my implementation is correct that 5 bit case has 16 distinct valid results -- and each of them has 120 permutations all of which are valid for a total of 1920 different, valid 5 bit beckett gray codes.] --Rdm 19:57, 19 May 2010 (UTC)
The 6-bit-wide case discussed on the WP page indicates that a full search of the data set takes 15 hours, but doesn't indicate the hardware, language or techniques used to find it. See Lucas-Lehmer test for another task that takes a while to run. When originally written, it specified to allow the program to run until it found M47, which wasn't even known at the time. NevilleDNZ apparently has a sense of humor.
There are multiple possible solutions for the 5-bit and 6-bit cases, but only one (but no necessarily any particular one) needs to be found. Conveniently, this is one of those problems where verifying that a solution is valid is easier than finding the solution in the first place; the way I'd expect it to be written is generate gray codes/foreach gray code check for satisfying Beckett restrictions/display first satisfier found and terminate. A final, redundant validity check would be to verify that the presented sequence is a gray code, and that the presented sequence satisfies the Beckett restriction.
By "show that no such code exists," I meant prove that there is no 3-bit or 4-bit Beckett-Gray code; there may gray codes, but there are no gray codes in that space that satisfy the additional constraints placed by the Beckett playwright. If the entire problem space is searched without a found solution, then either there is no solution, or the searching program is in error. in the generate->check(terminate) pipeline, if the generator runs dry without the check ever succeeding, then it's been shown that no example exists.
Going back, you don't need to show all BG codes for a number of bits, but show at least one if any exist, or show none if none exist. At least, that's what I had in mind when I suggested the task. --Michael Mol 03:20, 20 May 2010 (UTC)
  • I suppose that the RPG task is to demonstrate how to implement a domain-specific language, yes? If not, then perhaps cook up a task that demonstrates one.
RCRPG/Perl was the result of me scratching a nostalgic itch while stuck in bed sick one weekend. I didn't have a deeper goal than that. --Michael Mol 09:33, 20 June 2010 (UTC)
  • A task designed to require a large amount of processing, tuned to allow lower level languages like C to find the solution in a reasonable amount of time (like one or two minutes) and higher level languages like Python to be too much slow for the job.
You may not get the answer you were expecting as the idiomatic Python solution might be to add this to the C solution then call the C from Python using that wrapper generator. Their are several toolsets around that use Python as a wrapper around existing C and Fortran libraries and allow the easy wrapping of C routines. --Paddy3118 05:53, 23 November 2010 (UTC)
This Python solution is acceptable. The point of this task is not to keep Python out of the page, but to show how various languages face a computation-heavy task.
See Ackermann function where the extremely compute intensive function needs bigints and other optimisations to get to larger answers. On that page, the C version might be compute intensive, but inefficient compared to the Python one.
  • A task demonstrating how to write a PHP extension DLL (or .so) ... hmmm ... that can only be done in C and Delphi so far. Maybe that's too much of an ask. --Axtens
  • Building a suffix tree (possibly followed by a generalized suffix tree). If the tree is built in linear time, then many string problems can be solved efficiently. for example finding the longest common substring between two strings becomes linear rather than polynomial through a DP method.
  • Use Canny edge detection to find edges in an image. This could, in turn, be a pre-filter for a Hough transform which then allows extraction of coordinates (ρ,θ) of significant edge lines within the image. --Coderjoe 10:39, 10 August 2010 (UTC)
  • Well since I created the bead sort using addition, I would love to see other work being done with it. Perhaps other language implementations on this sorting algorithm. Or improvements to my original sudo code or implamentation. I should note that the sorting algorithm I created is not "true" to the exact nature of Bead sort but it does work like one would expect from such a solution. It probably should be named Using addition (as gravity) for Bead sort or something similar. --MichaelChrisco 11:03, 22 August 2010 (UTC)
See File IO. Actually, I've been watching the analytics data closely over the last week, and that task has seen a large number of hits from a link on the relevant StackOverflow page. --Michael Mol 18:37, 27 August 2010 (UTC)
It probably means that people come on this site to learn and copy code, it's positive. But the File IO Task is very simple. A similar but a bit more complex task may be added.
Well, the StackOverflow case looks rather unique. IIRC, they already had a code golf/chrestomathy section on their site (We've often gotten referral hits from SO in "how do I do X" or "how do I do X in Y" questions, and I've seen mention of "move it to the SO wiki" before.), and the big deal with that task involves the social structure and politics of the appropriateness of the posted SO question, its closing and its temporary deletion. Also, it's inappropriate to copy content from places like SO if that copying violates Rosetta Code:Copyrights. --Michael Mol 03:23, 29 August 2010 (UTC)
I hope I havent stepped on anyones toes here but I've been trying to get the reddit community interested in the site. The more eyeballs, the more chances of good code and tasks (and donations wink wink). IO tasks could be done with blocks, bits, and implementing different database models. I dont know about the language of such a task (like implement SQL or something) but it would be interesting.--MichaelChrisco 00:16, 29 August 2010 (UTC)
Hey, you're not stepping on anyone's toes there. I prefer word-of-mouth to any other form of advertisement I could get. :) --Michael Mol 03:23, 29 August 2010 (UTC)
  • WebP container and conversion from JPEG (or whatever other format you'd like).
Try Longest common subsequence too. --Paddy3118 22:32, 16 February 2011 (UTC)
  • Execute a program written in Piet. --ThAlEdison 19:13, 11 March 2011 (UTC)
  • Read the name of a task and the name of a programming language from standard input, and put an implementation of the task in that programming language on standard output. Ideally, N tasks and M programming languages should require O(N+M) lines of source code rather than O(N*M). --Johnicholas 11:04, 18 March 2011 (UTC)
  • In object-oriented programming, show how a subclass's constructor can explicitly pass arguments to its superclass's constructor to initialize its base object (instance of the superclass). --98.210.210.193 09:02, 29 March 2011 (UTC)
  • Remove some elements from a mutable collection while iterating through it, based on some condition of the element. Related to Filter, but modifying the existing collection rather than creating a new one. This is a challenging task, because removing the element you are currently iterating over, may affect the iteration itself (changes indexes / affects iterators). --208.80.119.67 19:32, 5 April 2011 (UTC)
This is an Anti-pattern. Why code it? --Paddy3118 19:57, 5 April 2011 (UTC)
Perhaps the original commenter overspecified. Make it less specific? Call it Set filter. --Michael Mol 20:16, 5 April 2011 (UTC)
Some languages provide this operation, exactly as the original commenter specified. Common Lisp has delete-if-not, Factor has filter!, and Ruby has Array#select!. Java hackers might implement this with java.util.Iterator.remove() from Java API. I added this task as an option to Filter, along with code for Factor and Ruby. (The page already had Common Lisp.) --Kernigh 01:55, 6 April 2011 (UTC)
  • Create a program to reseed the Linux Kernel's pseudo random number generator through /dev/urandom with random bytes fetched from [2] A PERL implementation can be found in the Ubuntu repositories in the package named reseed
  • Show how to print a file in a portable way (for instance with GTK) --François Fabien 21 mai 2011
  • Cyclic Redundancy Check (CRC)
  • Get title of window under cursor 82.83.239.135 19:45, 1 October 2011 (UTC)
  • Hash-join
The hash join algorithm is very useful in the development of a relational database systems. The task consists in implementing the following algorithm and provinduing a simple reproducible example: The records of files R and S are both hashed to the same hash file, using the same hashing function on the join attributes A of R and B of S as hash keys. A single pass through the file with fewer records (say, R) hashes its records to the hash file buckets. A single pass through the other file (S) then hashes each of its records to the appropriate bucket, where the record is combined with all matching records from R.
    • the following three items could be in a category like program checking or program verification(or whatever this is called)
  • Programming by contract/Design by contract

Some languages support Design by contract as part of the language (e.g. Eiffel) or via libraries or language extensions (cofoja, gcontracts, C#), I think it would be useful to have a simple (probably incorrect) implementation of a task and the contracts that exhibit the programming mistake. --AlexLehm 09:01, 28 October 2011 (UTC)

  • Assert
  • Unit Tests
1  2  3  4
5  8  9  10
6  11 13 14
7  12 15 16

if the input is 5 then the output will be 

1  2  3  4  5
6  10 11 12 13
7  14 17 18 19
8  15 20 22 23
9  16 21 24 24

Insufficient information

These task suggestions do not have sufficient information to allow the creation of a task. This section will be cleaned out periodically, but these may inspire the creation of other tasks in the mean time.

Design patterns

Scope modifiers? --Mwn3d 19:57, 27 November 2009 (UTC)
Looks like a poor match to me. –Donal Fellows 08:02, 3 January 2010 (UTC)

Recently Completed

If a task has been completed, move the request to this category. Add a link to the task page, and sign (add --~~~~) to the request. Completed tasks more than a week old should be removed from the list.

Discuss

  • Querying devices for certain SNMP values and output reponses to .html or .txt-file.
    • Used for:
      • generating webpage where helpdesk can view the VLAN of a user-port
      • querying forwarding database of switch / ARP-table of router
    • Can be extended:
      • with config file for: device list, SNMP-values to interrogate, SNMP community strings, ...
      • support for SNMPv3
      • generating history reports: what mac-address has been on this port, when has a change been made, ...
    • Wanted to do this myself for a long time already using Python or Ruby, but not making a lot of progress. Any help or suggestion would be welcome.
This should probably be split into Query SNMP server and Retrieve configuration setting (for an application, not the SNMP server). There are already tasks for outputting to a file. --Short Circuit 23:43, 16 February 2008 (MST)
  • Win interface... C++ calls to Fortran F90/95 Source Code ... and back...
This should be as trivial as Call function in shared library, if the Fortran code has been compiled into a shared library. (Regardless of OS) --Short Circuit 23:43, 16 February 2008 (MST)
Serialization and deserialization are extremely common programming tasks, and there are a fair number of open formats for the purpose. Serialization and deserialization should probably get their own category under Category:Solutions by Programming Task. Additionally, json.org has a list of existing JSON implementations, sorted by language, to refer to. This should be a very quick thing to implement for JSON. Other formats that should be considered are XML and binary (packed) formats. --Short Circuit 04:38, 20 June 2009 (UTC)
  • Parsing RFC 4180 compliant CSV
    • Should take into account escaping of commas, quotes and newline characters
  • Dynamic Object Oriented tasks
    • I was looking through some of the existing task examples
and started thinking about them in terms of proofs of concept in a larger framework of dynamically extending objects, classes, methods, etc.. It seems to me that tasks that allowed for more dynamic object manipulation like:
  • Add a variable/method to a class runtime
  • Add a method to a class instance at runtime

would be useful to that end. I was thinking that doing these as small proof of concepts rather than trying to build some kind of big framework would be most useful. Now since I'm not a heavy user of OO, I might go overboard here and was wondering what others might think. --Dgamey 17:38, 27 December 2011 (UTC)

Retrieved from "https://rosettacode.org/wiki/Rosetta_Code:Village_Pump/Suggest_a_programming_task?oldid=4647"