Rosetta Code:Village Pump/Suggest a programming task

From Rosetta Code
< Rosetta Code:Village Pump
Revision as of 18:48, 26 July 2010 by MikeMol (talk | contribs) (→‎Mathematical Operations: decimal/binary conversion)

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.)

When making a request, please place it in the Unsorted section.

When reviewing requests, please help sort them into the categories farther down, based on the category descriptions.

Incomplete

General

User Output - text#C++
  • an encryption program
    • What sort of encryption? We've already got tasks for using SSL connections (e.g., Client-Authenticated HTTPS Request) so maybe you're after message-level encryption? Perhaps a simple DES implementation would be apt. (The advantage of that is that it is not particularly strong itself, and so doesn't run close to the legal issues in this area, but points the way towards real production encryption.) –Donal Fellows 09:17, 20 January 2010 (UTC)
  • Monads
  • Coroutines/Generators
  • Sentinel value -- What values are commonly used for sentinel purposes. (This may end up beyond language comparison and delve into protocols) --Short Circuit 18:09, 9 June 2009 (UTC)
    • Perhaps Null should be generalized to cover this? --Kevin Reid 21:27, 29 August 2009 (UTC)
  • Applying a list of functions to a value. (As different from applying a function to a list of values.)Rahul 21:23, 9 December 2008 (UTC)
See First-class functions --Paddy3118 15:34, 24 February 2009 (UTC)
Not entirely appropriate. Nothing prevents one from having a list of function pointers in C or C++ to apply to the same pointer or reference to the value in question. However, there appears to be significant discussion whether C is even appropriate in the task you link to. --Short Circuit 07:52, 25 February 2009 (UTC)
Could this be added to Comparing two integers? --Mwn3d 07:28, 21 December 2007 (MST)
Type-variant rather suggests dynamic polymorphism, i.e., when the specific type of the value (and the value itself) depends on the type tag of the object. MS VARIANT is rather a different thing. It is a union, a container type which content depends on the value of the constraint. This is also a form polymorphism, but different, a dynamically constrained type. The type of the object does not vary. A similar case represents unbounded array, which size depends on the actual bounds (the constraint). (Granted, MS VARIANT serves the purpose of dynamic polymorphism, but that is merely because MS wished to keep it conform to non-OO languages.) --Dmitry-kazakov 13:24, 9 April 2009 (UTC)
  • I don't know where this should go, but it would be great to have a use comparison of regular expressions 187.37.58.35 18:40, 3 November 2009 (UTC)
Is this close? --Mwn3d 20:22, 3 November 2009 (UTC)
Probably not quite what he's looking for. Different regex implementations (i.e. .Net's, Perl's, sed, Visual Studio's, etc.) have different extensions and escape sequences. It's likely he's looking for a comparison as though each variant of regex were treated as being distinct languages. Accessing the implementation is one thing, but performing various supported operations is another. --Michael Mol 21:50, 3 November 2009 (UTC)
POSIX specifies two levels of regular expressions, and then there's additional levels beyond that (c.f. Perl and PCRE). There's also a lot of disagreement between different camps here over the type of automaton that should be used in the implementation. It's a mess to be honest (as extensions beyond POSIX EREs aren't standardized). Because of that, if you're going to delve deeper into REs, I advise picking one of the POSIX levels and explicitly stating that that level only be supported. –Donal Fellows 23:03, 3 November 2009 (UTC)
yea in a long term it would be great to have something like Michael Mol said but that's a very nice start, thanks 187.37.58.35 14:39, 4 November 2009 (UTC)
UPDATE: now I noticed this page Regular_expression_matching is there for quite a time, but I didn't found it in the 'by Task' link, that's why I posted, also searching by "Regular expression" in the search box results nothing.. 187.37.58.35 16:17, 4 November 2009 (UTC)
That task is listed under Text processing on the Solutions by Task page. You can also look at Category:Programming Tasks to see a list with no sub-categories. I can set up a redirect from "Regular expressions" for now, though it seems like we need more tasks to cover REs. --Mwn3d 16:20, 4 November 2009 (UTC)
  • Simple, common requirements for 3D animation, including running an operation consistently N times per second, generate and draw basic geometric shapes like spheres, cubes and cylinders, load and display a point mesh and apply a texture to a quad. I'll host any desired data on the server. --Michael Mol 08:29, 13 November 2009 (UTC)
  • Produce an SVG showing a cumulative distribution function - on the x axis show the number of programming tasks completed, on the y scale show the proportion of programming languages on rosetta code that have completed less than or equal to that number of tasks. Maybe also plot the cdf of some standard distribution on the graph as well. (Weibull?) --Rldrenth 00:43, 22 December 2009 (UTC)
  • An example of lexical and dynamic variable binding in various languages. For example, in lisp the let construct and also let with variables declared as special would be useful to see this in other languages, such as Tcl and Python. WilliamKF 18:03, 4 January 2010 (UTC)
  • Modules. This basic syntax task would cover C's #include, Objective-C's #import, Python's import, Java's package/import, etc. It would also cover symbol visibility control in compilation units (private/public, static/export, etc.).

Games

  • Connect Four (or more) with variable and standard game board (6 rows, 7 columns)
    - but watch for trade mark violations etc --Paddy3118 17:33, 29 April 2009 (UTC)
    O.K., the games can be called The Captain's Mistress", because that is the original, much older verson of the "Connect Four" (which was "invented" and copyrighted in 1974 by Milton Bradley, according to the Wikipedia.) --Borisbaran 12:33, 3 May 2009 (UTC)
    Then why not dots-and-crosses (five-in-a-line): discovered a site which call it this way, but I played it when I was eight y.o., and surely it's a very old game people played with paper and a pen long before anyone thought to register a copyright or what on it; instead of different colors, we can use a cross and a dot, and this is the name I knew it: "puntini e crocette" (dots and crosses)... But I think the interesting part would be to program the A.I. opponent... --ShinTakezou 14:07, 5 May 2009 (UTC)
    Reading it better... It's Gomoku! (But a paper can be like a board bigger than 19×19) --ShinTakezou 14:10, 5 May 2009 (UTC)
  • Dots and Boxes is quite a fun game to do, especially since the game has been around for ages and its strategies have been well studied. It's also quite easy to do just the GUI parts of the game, making a simple game for two players. —Dkf 12:15, 18 May 2009 (UTC)
    More possibilities are von Neumann and Langton cellular automata. They're not really games as such, but they're certainly interesting in similar ways. —Donal Fellows 14:58, 9 August 2009 (UTC)
  • Magic square: a program that could compute a magic square of any size, whether odd, doubly-even, or singly even.

Database / Network

  • Simple DB connection and queries.
  • Certificate-authenticated SSL.
  • Secure Socket Layer.
  • Simple command line client for XMPP (Extensible Messaging and Presence Protocol) .

Data organization and encoding

System calls

  • Copy a directory tree recursively
    • On a local filesystem
    • With an option to specify files or folder to exclude
  • Open a named pipe
  • Demonstrate use of a foreign function interface to call a C-routine or library function

Mathematical Operations

  • Church encoding and computation with Church numerals
  • Euler's method for approximating solutions to differential equations
  • Symbolic differentiation. [1] [2]
  • Gauss-Algorithm
  • Take a decimal representation of a number, and show binary, octal and hex representations of that number. Optionally, take binary, octal and/or hex representations of numbers, and show their decimal representation.

Image Processing

  • Line Detection
Use the Hough transform to detect lines in an image. The Hough transform maps points in -space to points in -space.
Umm, that's a somewhat unhelpful description. The transform maps each point in to the average color of the pixels on that line in -space (where the line corresponds to points of the form ). The idea is that where there is a line in the original image, it corresponds to a bright (or dark, depending on the color of the background field) spot; by applying a suitable filter to the results of the transform, it is possible to extract the locations of the lines in the original image. –Donal Fellows 11:04, 21 January 2010 (UTC)
It's now Hough transform, though still a draft right now. Comments and improvements welcome! –Donal Fellows 16:30, 21 January 2010 (UTC)
It's looking better. We should come up with an image that can be used to test the examples. Ahhh - Inkscape can generate PNG images. Draw an image containg several line segments, or a polygon using Inkscape. That may be the ticket. --Rldrenth 18:23, 21 January 2010 (UTC)
Tarted it all up. I think it's now looking good enough to be a full {{task}}, so I've converted it to be one. –Donal Fellows 14:13, 22 January 2010 (UTC)
And it's the first link posted over here. :) --Michael Mol 17:09, 22 January 2010 (UTC)

Color Spaces

  • Conversion from sRGB to HSL, HSV and CMYK.
That would not be Color Space conversion. You can not convert a color space into a color model. sRGB is a color space that uses RGB color model. HSL, HSV and CMYK are color models. Maybe you mean color model conversion? However, conversion to CMYK requires information about the inks, paper and printing device used. In practice, it requires color space conversion, too. --PauliKL 15:29, 2 December 2009 (UTC)

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)

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)

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)

Unsorted

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

  • Should we have a task that demonstrates how some languages do boolean shortcutting and some don't? --Axtens 08:41, 22 March 2010 (UTC)
    • No. A task that specific is just gloating. What educational value would it have? Boolean short-circuiting is an important characteristic of operators, but IMO it's too small to be of interest by itself. —Kevin Reid 10:31, 22 March 2010 (UTC)
    • Maybe if the task was worded as "Set a variable V to the result of funca() and funcb(), where both functions return a boolean result. Only ever call funcb() if funca() returns True. Use boolean short circuiting if your language supports it"? --Paddy3118 16:33, 24 July 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.
  • 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)
  • Bignums: Either demonstrate the bignum support already in the language or write bignum support for the language. --Axtens 03:26, 12 February 2010 (UTC)
    There are already some tasks that do this on the side (e.g., Hamming numbers) but it would be nice to break this out into a separate task. –Donal Fellows 08:54, 12 February 2010 (UTC)
I have just added Arbitrary-precision integers (included). I did not call it Bignum because wp doesn't and I thought Bignum may not be as descriptive. Maybe Bignum integers (included) could be made to refer to it. (That way around). --Paddy3118 07:00, 13 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)

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.

  • I think Stooge Sort would be a great example of how a simple sorting algorithm can still have very bad performance. It also gives a good example of recursion.—Michael Chrisco15:50, 23 March 2010
Done: Stooge sort --Mwn3d 05:01, 24 July 2010 (UTC)

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)
Retrieved from "https://rosettacode.org/wiki/Rosetta_Code:Village_Pump/Suggest_a_programming_task?oldid=4472"