Rosetta Code/Tasks without examples

From Rosetta Code
Rosetta Code/Tasks without examples is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A RosettaCode contributor is going on a long journey.

To ease the boredom of a long flight he takes his favourite programming language manual and a list of RosettaCode tasks,   but there's a catch:   the tasks have to be description only and not include all the solutions already supplied by other programmers.


Task



D

import std.algorithm;
import std.net.curl;
import std.range;
import std.regex;
import std.stdio;
import std.string;

void process(string base, string task) {
    auto re2 = ctRegex!`</?[^>]*>`;

    auto page = base ~ task;
    auto content = get(page);

    string prefix = `using any language you may know.</div>`;
    auto beg = content.indexOf(prefix);
    auto end = content.indexOf(`<div id="toc"`, beg);
    auto snippet = content[beg + prefix.length .. end];
    writeln(replaceAll(snippet, re2, ``));

    writeln("#####################################################");
}

void main() {
    auto pattern = ctRegex!`<li><a href="/wiki/(.*?)"`;

    auto content = get("http://rosettacode.org/wiki/Category:Programming_Tasks");

    string[] tasks;
    foreach (m; matchAll(content, pattern)) {
        tasks ~= m[1].idup;
    }

    auto base = "http://rosettacode.org/wiki/";
    tasks.take(3).each!(task => process(base, task));
}
Output:
There are 100 doors in a row that are all initially closed.
You make 100 passes by the doors.
The first time through, visit every door and  toggle  the door  (if the door is closed,  open it;   if it is open,  close it).
The second time, only visit every 2nd door   (door #2, #4, #6, ...),   and toggle it.
The third time, visit every 3rd door   (door #3, #6, #9, ...), etc,   until you only visit the 100th door.


Task

Answer the question:   what state are the doors in after the last pass?   Which are open, which are closed?

Alternate:
As noted in this page's   discussion page,   the only doors that remain open are those whose numbers are perfect squares.
Opening only those doors is an   optimization   that may also be expressed;
however, as should be obvious, this defeats the intent of comparing implementations across programming languages.



#####################################################



The Problem

 100 prisoners are individually numbered 1 to 100
 A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
 Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
 Prisoners start outside the room
 They can decide some strategy before any enter the room.
 Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
 A prisoner can open no more than 50 drawers.
 A prisoner tries to find his own number.
 A prisoner finding his own number is then held apart from the others.
 If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand.


The task

 Simulate several thousand instances of the game where the prisoners randomly open drawers
 Simulate several thousand instances of the game where the prisoners use the optimal strategy mentioned in the Wikipedia article, of:
 First opening the drawer whose outside number is his prisoner number.
 If the card within has his number then he succeeds otherwise he opens the drawer with the same number as that of the revealed card. (until he opens his maximum).

Show and compare the computed probabilities of success for the two strategies, here, on this page.


References

 The unbelievable solution to the 100 prisoner puzzle standupmaths (Video).
 wp:100 prisoners problem
 100 Prisoners Escape Puzzle DataGenetics.
 Random permutation statistics#One hundred prisoners on Wikipedia.



#####################################################




Task

Implement the Fifteen Puzzle Game.

The   15-puzzle   is also known as:

   Fifteen Puzzle
   Gem Puzzle
   Boss Puzzle
   Game of Fifteen
   Mystic Square
   14-15 Puzzle
   and many others.


Related Tasks

   15 Puzzle Solver
   16 Puzzle Game



#####################################################

Go

package main

import (
    "fmt"
    "html"
    "io/ioutil"
    "net/http"
    "regexp"
    "strings"
    "time"
)

func main() {    
    ex := `<li><a href="/wiki/(.*?)"`
    re := regexp.MustCompile(ex)
    page := "http://rosettacode.org/wiki/Category:Programming_Tasks"
    resp, _ := http.Get(page)
    body, _ := ioutil.ReadAll(resp.Body)
    matches := re.FindAllStringSubmatch(string(body), -1)
    resp.Body.Close()
    tasks := make([]string, len(matches))
    for i, match := range matches {
        tasks[i] = match[1]
    }
    const base = "http://rosettacode.org/wiki/"
    const limit = 3 // number of tasks to print out
    ex = `(?s)using any language you may know.</div>(.*?)<div id="toc"`
    ex2 := `</?[^>]*>` // to remove all tags including links
    re = regexp.MustCompile(ex)
    re2 := regexp.MustCompile(ex2)
    for i, task := range tasks {
        page = base + task
        resp, _ = http.Get(page)
        body, _ = ioutil.ReadAll(resp.Body)
        match := re.FindStringSubmatch(string(body))
        resp.Body.Close()
        text := html.UnescapeString(re2.ReplaceAllLiteralString(match[1], ""))
        fmt.Println(strings.Replace(task, "_", " ", -1), "\n", text)
        if i == limit-1 {
            break
        }
        time.Sleep(5 * time.Second) // wait 5 seconds before processing next task
    }
}
Output:

Text rather than HTML:

100 doors 
 
There are 100 doors in a row that are all initially closed.
You make 100 passes by the doors.
The first time through, visit every door and  toggle  the door  (if the door is closed,  open it;   if it is open,  close it).
The second time, only visit every 2nd door   (door #2, #4, #6, ...),   and toggle it.
The third time, visit every 3rd door   (door #3, #6, #9, ...), etc,   until you only visit the 100th door.


Task

Answer the question:   what state are the doors in after the last pass?   Which are open, which are closed?

Alternate:
As noted in this page's   discussion page,   the only doors that remain open are those whose numbers are perfect squares.
Opening only those doors is an   optimization   that may also be expressed;
however, as should be obvious, this defeats the intent of comparing implementations across programming languages.



15 Puzzle Game 
 
 


Task

Implement the Fifteen Puzzle Game.

The   15-puzzle   is also known as:

   Fifteen Puzzle
   Gem Puzzle
   Boss Puzzle
   Game of Fifteen
   Mystic Square
   14-15 Puzzle
   and many others.


Related Tasks

   15 Puzzle Solver
   16 Puzzle Game



15 puzzle solver 
 
Your task is to write a program that finds a solution in the fewest moves possible single moves to a random Fifteen Puzzle Game.
For this task you will be using the following puzzle:

15 14  1  6
 9 11  4 12
 0 10  7  3
13  8  5  2


Solution: 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0

The output must show the moves' directions, like so: left, left, left, down, right... and so on.
There are two solutions, of fifty-two moves:
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd
see: Pretty Print of Optimal Solution
Finding either one, or both is an acceptable result.

Extra credit.
Solve the following problem:

  0 12  9 13
 15 11 10 14
  3  7  2  5
  4  8  6  1



Related Task

 15 puzzle game
 A* search algorithm

Java

Translation of: Kotlin
import java.io.IOException;
import java.net.URI;
import java.net.URISyntaxException;
import java.net.http.HttpClient;
import java.net.http.HttpRequest;
import java.net.http.HttpResponse;
import java.time.Duration;
import java.util.ArrayList;
import java.util.regex.Pattern;

public class TasksWithoutExamples {
    private static String readPage(HttpClient client, URI uri) throws IOException, InterruptedException {
        var request = HttpRequest.newBuilder()
            .GET()
            .uri(uri)
            .timeout(Duration.ofSeconds(5))
            .setHeader("accept", "text/html")
            .build();

        var response = client.send(request, HttpResponse.BodyHandlers.ofString());
        return response.body();
    }

    private static void process(HttpClient client, String base, String task) {
        try {
            var re = Pattern.compile(".*using any language you may know.</div>(.*?)<div id=\"toc\".*", Pattern.DOTALL + Pattern.MULTILINE);
            var re2 = Pattern.compile("</?[^>]*>");

            var page = base + task;
            String body = readPage(client, new URI(page));

            var matcher = re.matcher(body);
            if (matcher.matches()) {
                var group = matcher.group(1);
                var m2 = re2.matcher(group);
                var text = m2.replaceAll("");
                System.out.println(text);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) throws URISyntaxException, IOException, InterruptedException {
        var re = Pattern.compile("<li><a href=\"/wiki/(.*?)\"", Pattern.DOTALL + Pattern.MULTILINE);

        var client = HttpClient.newBuilder()
            .version(HttpClient.Version.HTTP_1_1)
            .followRedirects(HttpClient.Redirect.NORMAL)
            .connectTimeout(Duration.ofSeconds(5))
            .build();

        var uri = new URI("http", "rosettacode.org", "/wiki/Category:Programming_Tasks", "");
        var body = readPage(client, uri);
        var matcher = re.matcher(body);

        var tasks = new ArrayList<String>();
        while (matcher.find()) {
            tasks.add(matcher.group(1));
        }

        var base = "http://rosettacode.org/wiki/";
        var limit = 3L;

        tasks.stream().limit(limit).forEach(task -> process(client, base, task));
    }
}

Julia

Translation of: Go
using HTTP

function gettaskdescriptions(numtoprint = 3)    
    page = "http://rosettacode.org/wiki/Category:Programming_Tasks"
    body = String(HTTP.get(page).body)
    tasks = [m.captures[1] for m in eachmatch(r"<li><a href=\"/wiki/([^\"]+)\"", body)]
    base = "http://rosettacode.org/wiki/"
    for (i, task) in enumerate(tasks)
        page = base * task
        body = String(HTTP.get(page).body)
        m = match(r"using any language you may know.</div>(.+)<div id=\"toc\""s, body)
        m != nothing && println(replace(m.captures[1], r"<[^>]*>"s => ""), "\n", "="^60, "\n")
        i >= numtoprint && break
        sleep(rand(3:7))   # wait 5 +/- 2 seconds before processing next task
    end
end

gettaskdescriptions()

Kotlin

import java.net.URI
import java.net.http.HttpClient
import java.net.http.HttpRequest
import java.net.http.HttpResponse
import java.time.Duration
import java.util.regex.Pattern

fun readPage(client: HttpClient, uri: URI): String {
    val request = HttpRequest.newBuilder()
        .GET()
        .uri(uri)
        .timeout(Duration.ofSeconds(5))
        .setHeader("accept", "text/html")
        .build()

    val response = client.send(request, HttpResponse.BodyHandlers.ofString())
    return response.body()
}

fun main() {
    var re = Pattern.compile("<li><a href=\"/wiki/(.*?)\"", Pattern.DOTALL + Pattern.MULTILINE)

    val client = HttpClient.newBuilder()
        .version(HttpClient.Version.HTTP_1_1)
        .followRedirects(HttpClient.Redirect.NORMAL)
        .connectTimeout(Duration.ofSeconds(5))
        .build()

    val uri = URI("http", "rosettacode.org", "/wiki/Category:Programming_Tasks", "")
    var body = readPage(client, uri)
    var matcher = re.matcher(body)

    val tasks = mutableListOf<String>()
    while (matcher.find()) {
        tasks.add(matcher.group(1))
    }

    val base = "http://rosettacode.org/wiki/"
    val limit = 3L
    re = Pattern.compile(".*using any language you may know.</div>(.*?)<div id=\"toc\".*", Pattern.DOTALL + Pattern.MULTILINE)
    val re2 = Pattern.compile("</?[^>]*>")
    for (task in tasks.stream().limit(limit)) {
        val page = base + task
        body = readPage(client, URI(page))

        matcher = re.matcher(body)
        if (matcher.matches()) {
            val group = matcher.group(1)
            val m2 = re2.matcher(group)
            val text = m2.replaceAll("")
            println(text)
        }
    }
}

Nim

Translation of: Go
import htmlparser, httpclient, os, re, strutils, xmltree

let re1 = re("""<li><a href="/wiki/(.*?)"""")
const Page = "http://rosettacode.org/wiki/Category:Programming_Tasks"
var client = newHttpClient()

# Find tasks.
var body = client.getContent(Page)
var tasks: seq[string]
var start = 0
while true:
  var matches: array[1, string]
  start = body.find(re1, matches, start) + 1
  if start == 0: break
  if not matches[0].startsWith("Category:"):
    tasks.add matches[0]

const Base = "http://rosettacode.org/wiki/"
const Limit = 3   # number of tasks to print out.
let re2 = re("""(?s)using any language you may know.</div>(.*?)<mw:tocplace>""")
for i, task in tasks:
  var matches: array[2, string]
  let page = Base & task
  body = client.getContent(page)
  if body.find(re2, matches) < 0:
    raise newException(ValueError, "unable to find pattern in page.")
  let xmlnode = matches[0].parseHtml()  # Build an XML tree from the HTML.
  echo task.replace('_', ' ')
  echo xmlnode.innerText()              # Echo the tree as text.
  if i == Limit - 1: break
  os.sleep(5000)    # Wait 5 seconds before processing next task.
Output:
100 doors

There are 100 doors in a row that are all initially closed.
You make 100 passes by the doors.
The first time through, visit every door and  toggle  the door  (if the door is closed,  open it;   if it is open,  close it).
The second time, only visit every 2nd door   (door #2, #4, #6, ...),   and toggle it.
The third time, visit every 3rd door   (door #3, #6, #9, ...), etc,   until you only visit the 100th door.


Task

Answer the question:   what state are the doors in after the last pass?   Which are open, which are closed?

Alternate:
As noted in this page's   discussion page,   the only doors that remain open are those whose numbers are perfect squares.
Opening only those doors is an   optimization   that may also be expressed;
however, as should be obvious, this defeats the intent of comparing implementations across programming languages.



100 prisoners



The Problem

 100 prisoners are individually numbered 1 to 100
 A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
 Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
 Prisoners start outside the room
 They can decide some strategy before any enter the room.
 Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
 A prisoner can open no more than 50 drawers.
 A prisoner tries to find his own number.
 A prisoner finding his own number is then held apart from the others.
 If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand. 


The task

 Simulate several thousand instances of the game where the prisoners randomly open drawers
 Simulate several thousand instances of the game where the prisoners use the optimal strategy mentioned in the Wikipedia article, of:
 First opening the drawer whose outside number is his prisoner number.
 If the card within has his number then he succeeds otherwise he opens the drawer with the same number as that of the revealed card. (until he opens his maximum).

Show and compare the computed probabilities of success for the two strategies, here, on this page.


References

 The unbelievable solution to the 100 prisoner puzzle standupmaths (Video).
 wp:100 prisoners problem
 100 Prisoners Escape Puzzle DataGenetics.
 Random permutation statistics#One hundred prisoners on Wikipedia.



15 puzzle game

 


Task

Implement the Fifteen Puzzle Game.

The   15-puzzle   is also known as:

   Fifteen Puzzle
   Gem Puzzle
   Boss Puzzle
   Game of Fifteen
   Mystic Square
   14-15 Puzzle
   and some others.


Related Tasks

   15 Puzzle Solver
   16 Puzzle Game

Perl

Slice and dice the HTML. Output is as for the other examples.

use strict;
use warnings;

use LWP::UserAgent;
my $ua = LWP::UserAgent->new;

# get list of task titles
my $html  = $ua->request( HTTP::Request->new( GET => 'http://rosettacode.org/wiki/Category:Programming_Tasks'))->content;
my @tasks = $html =~ m#<li><a href="/wiki/(.*?)"#g;

# download tasks, and extract task descriptions
for my $title (@tasks) {
    my $html = $ua->request( HTTP::Request->new( GET => "http://rosettacode.org/wiki/$title" ))->content;
    my($task_at_hand) = $html =~ m#using any language you may know.</div>(.*?)<div id="toc"#s;
    print "$title\n$task_at_hand\n\n";
    sleep 10; # so you have time to read each task...
}

Phix

Since downloading all the pages can be very slow, this uses a cache. Limiting by "Phix" fairly obviously speeds it up tenfold :-)
Output similar to zkl, I assume the first four constants are self-explanatory.

Library: Phix/libcurl
-- demo\rosetta\Tasks_without_examples.exw
without js -- (libcurl, file i/o, peek, progress..)
constant output_html = false,
         include_drafts = true,
         summary = true,
         notlang = "Phix" -- or "" (ie a zero length string) for all

include rosettacode_cache.e -- see Rosetta_Code/Count_examples#Phix

function extract_tasks()
    if get_file_type("rc_cache")!=FILETYPE_DIRECTORY then
        if not create_directory("rc_cache") then
            crash("cannot create rc_cache directory")
        end if
    end if
    -- extract tasks from eg `<li><a href="/wiki/100_doors"`
    sequence tasks = dewiki(open_category("Programming_Tasks"))
    if include_drafts then
        tasks &= dewiki(open_category("Draft_Programming_Tasks"))
    end if
    if length(notlang) then
        -- filter already done in specified language
        string langurl = "http://rosettacode.org/wiki/Category:"&notlang
        sequence done = dewiki(open_download(notlang&".htm",langurl))
        integer k = 0
        for i=1 to length(tasks) do
            if not find(tasks[i],done) then
                k += 1
                tasks[k] = tasks[i]
            end if
        end for
        tasks = tasks[1..k]
        done = {}
    end if
    if not summary then
        -- replace with contents
        for i=1 to length(tasks) do
            string ti = tasks[i],
                   url = sprintf("http://rosettacode.org/wiki/%s",{ti}),
                   contents = open_download(ti&".htm",url)
            integer start = match(`</div>`,contents,match(`<div class="infobox"`,contents))+length(`</div>`)
            integer finish = match(`<div id="toc"`,contents,start)-1
            -- ... but draft tasks with too few languages have no toc:
            if finish=-1 then finish = match(`<h2>`,contents,start)-1 end if
            -- ... and if no languages at all, use the footer:
            if finish=-1 then finish = match(`</div><div class="printfooter">`,contents,start)-1 end if
            if finish=-1 then ?9/0 end if
            contents = contents[start..finish]
            ti = substitute(ti,"_"," ")
            if not match("<b>"&ti&"</b>",contents) then
                -- (ps: I refuse to panic over the occasional replicated header...)
                contents = sprintf("<h3>%s</h3>%s",{ti,contents})
            end if
            tasks[i] = contents
            if get_key()=#1B then exit end if
        end for
    end if
    curl_cleanup()
    return tasks
end function

constant html_header = """
<!DOCTYPE html>
<html lang="en">
 <head>
  <meta charset="utf-8" />
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
  <title>Rosettacode Tasks without examples</title>
 </head>
 <body>
  <h2>Rosettacode Tasks without examples</h2>
  Generated %s, %d entries<br>
  <br>
""",
         html_footer = """
 </body>
</html>
"""

sequence results = extract_tasks()
if output_html then
    integer fn = open("Tasks_Without_Examples.html","w")
    printf(fn,html_header,{format_timedate(date()),length(results)})
    for i=1 to length(results) do
        printf(fn,"%s<br>\n",html_clean(results[i]))
    end for
    puts(fn,html_footer)
    close(fn)
else
    progress("")
    for i=1 to length(results) do
        printf(1,"%s\n",html_clean(results[i]))
    end for
end if
printf(1,"%d tasks\n",length(results))

?"done"
{} = wait_key()

Raku

(formerly Perl 6)

Works with: Rakudo version 2017.10
use HTTP::UserAgent;
use Gumbo;

my $ua = HTTP::UserAgent.new;
my $taskfile = './RC_tasks.html';

# Get list of Tasks
say "Updating Programming_Tasks list...";
my $page   = "https://rosettacode.org/wiki/Category:Programming_Tasks";
my $html   = $ua.get($page).content;
my $xmldoc = parse-html($html, :TAG<div>, :id<mw-pages>);
my @tasks  = parse-html($xmldoc[0].Str, :TAG<li>).Str.comb( /'/wiki/' <-["]>+ / )».substr(6); #"
my $f      = open("./RC_Programming_Tasks.txt", :w)  or die "$!\n";
note "Writing Programming_Tasks file...";
$f.print( @tasks.join("\n") );
$f.close;

sleep .5;

for 'Programming_Tasks' -> $category
{ # Scrape info from each page.

    note "Loading $category file...";
    note "Retreiving tasks...";
    my @entries = "./RC_{$category}.txt".IO.slurp.lines;

    for @entries -> $title {
        note $title;

        # Get the raw page
        my $html = $ua.get: "https://rosettacode.org/wiki/{$title}";

        # Filter out the actual task description
        $html.content ~~ m|'<div id="mw-content-text" lang="en" dir="ltr" class="mw-content-ltr"><div'
                            .+? 'using any language you may know.</div>' (.+?) '<div id="toc"'|;

        my $task = cleanup $0.Str;

        # save to a file
        my $fh = $taskfile.IO.open :a;

        $fh.put: "<hr>\n     $title\n<hr>\n$task";

        $fh.close;

        sleep 3; # Don't pound the server
    }
}

sub cleanup ( $string ) {
    $string.subst( /^.+ '</div>'/, '' )
}
Abridged sample output:

    100_doors

There are 100 doors in a row that are all initially closed.

You make 100 <a href="/wiki/Rosetta_Code:Multiple_passes" title="Rosetta Code:Multiple passes">passes</a> by the doors.

The first time through, visit every door and  toggle  the door  (if the door is closed,  open it;   if it is open,  close it).

The second time, only visit every 2nd door   (door #2, #4, #6, ...),   and toggle it.

The third time, visit every 3rd door   (door #3, #6, #9, ...), etc,   until you only visit the 100th door.


Task

Answer the question:   what state are the doors in after the last pass?   Which are open, which are closed?


<a href="/wiki/Rosetta_Code:Extra_credit" title="Rosetta Code:Extra credit">Alternate</a>: As noted in this page's   <a href="/wiki/Talk:100_doors" title="Talk:100 doors">discussion page</a>,   the only doors that remain open are those whose numbers are perfect squares.

Opening only those doors is an   <a href="/wiki/Rosetta_Code:Optimization" title="Rosetta Code:Optimization">optimization</a>   that may also be expressed;

however, as should be obvious, this defeats the intent of comparing implementations across programming languages.


    15_Puzzle_Game

Task

Implement the <a href="http://en.wikipedia.org/wiki/15_puzzle" class="extiw" title="wp:15 puzzle">Fifteen Puzzle Game</a>.

Related Task
  • <a href="/wiki/15_puzzle_solver" title="15 puzzle solver">15 Puzzle Solver</a>




    15_puzzle_solver

Your task is to write a program that finds a solution in the fewest single moves (no multimoves) possible to a random <a href="http://en.wikipedia.org/wiki/15_puzzle" class="extiw" title="wp:15 puzzle">Fifteen Puzzle Game</a>.
For this task you will be using the following puzzle:

15 14  1  6
 9 11  4 12
 0 10  7  3
13  8  5  2


Solution:
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  0

The output must show the moves' directions, like so: left, left, left, down, right... and so on.
There are 2 solutions with 52 moves:
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd
finding either one, or both is an acceptable result.
see: <a rel="nofollow" class="external text" href="http://www.rosettacode.org/wiki/15_puzzle_solver/Optimal_solution">Pretty Print of Optimal Solution</a>

Extra credit.

Solve the following problem:

  0 12  9 13
 15 11 10 14
  3  7  2  5
  4  8  6  1


Related Task
  • <a href="/wiki/15_Puzzle_Game" title="15 Puzzle Game">15 puzzle game</a>



...and so on...

VBScript

Uses Internet Explorer (v9 and above) to traverse the DOM in the list page and subsequent task pages. Echoes title and href to the console. Outputs files containing html.

Could output text by retrieving innerText instead of innerHTML in Slurp().

Option Explicit

Dim oIE : Set oIE = CreateObject("InternetExplorer.Application")

Dim oFSO : Set oFSO = CreateObject("Scripting.FileSystemObject")

Dim oRE : Set oRE = New RegExp
oRE.Pattern = "class=[" & Chr(34) & "'](.*?)[" & Chr(34) & "']" 
oRE.IgnoreCase = True

oIE.Navigate "http://rosettacode.org/wiki/Category:Programming_Tasks"
While oIE.Busy
	WScript.Sleep 100
Wend

Dim oDoc : Set oDoc = oIE.Document
Dim oDict : Set oDict = CreateObject("Scripting.Dictionary")

' build a dictionary of anchors
Dim oAnchor
Dim oAnchors : Set oAnchors = oDoc.getElementById("mw-pages").getElementsByTagName("a")
For Each oAnchor In oAnchors
	oDict.Add oAnchor.innerText, oAnchor.href
Next

'traverse the dictionary of anchors
Dim aKeys : aKeys = oDict.Keys()
Dim aKey
For Each aKey In aKeys
	Slurp aKey, oDict(aKey)
Next

oIE.Quit

Function Slurp(sTitle, sHref)
	WScript.Echo sTitle, sHref
	
	oIE.Navigate sHref
	While oIE.Busy
		WScript.Sleep 100
	Wend
	
	Dim oDoc : Set oDoc = oIE.Document
	
	Dim oStart : Set oStart = oDoc.getElementsByClassName("infobox")(0)
	Dim oCursor : Set oCursor = oStart
	Dim sDescription : sDescription = vbNullString
	Dim oThere 
	Dim iErr
	
	Do While oCursor.tagName <> "TABLE" And oCursor.id <> "toc"
		Set oThere = oCursor
		sDescription = sDescription & oThere.innerHTML & vbNewLine
		On Error Resume Next 
		Set oCursor = oCursor.nextElementSibling
		iErr = Err.Number
		On Error Goto 0
		If iErr <> 0 Then
			Exit Do
		End If
	Loop
	
	dim sTitle2
	sTitle2 = Replace(sTitle,"/","_")
	sTitle2 = Replace(sTitle2,Chr(34),"'")
	sTitle2 = Replace(sTitle2,"*",".")
	
	Dim oHandle : Set oHandle = oFSO.CreateTextFile(sTitle2 & ".htm", True, True)
	oHandle.Write "<a href='" & sHref & "'>" & sTitle & "</a><br><br>"
	oHandle.Write sDescription
	oHandle.Close
	
	oIE.Stop

End Function

Wren

Library: libcurl
Library: Wren-pattern

An embedded program so we can use the libcurl library.

/* Rosetta_Code_Tasks_without_examples.wren */

import "./pattern" for Pattern

var CURLOPT_URL = 10002
var CURLOPT_FOLLOWLOCATION = 52
var CURLOPT_WRITEFUNCTION = 20011
var CURLOPT_WRITEDATA = 10001

foreign class Buffer {
    construct new() {}  // C will allocate buffer of a suitable size

    foreign value       // returns buffer contents as a string
}

foreign class Curl {
    construct easyInit() {}

    foreign easySetOpt(opt, param)

    foreign easyPerform()

    foreign easyCleanup()
}

var curl = Curl.easyInit()

var getContent = Fn.new { |url|
    var buffer = Buffer.new()
    curl.easySetOpt(CURLOPT_URL, url)
    curl.easySetOpt(CURLOPT_FOLLOWLOCATION, 1)
    curl.easySetOpt(CURLOPT_WRITEFUNCTION, 0)  // write function to be supplied by C
    curl.easySetOpt(CURLOPT_WRITEDATA, buffer)
    curl.easyPerform()
    return buffer.value
}

var unescs = [
    ["_", " "],
    ["\%252B", "+"],
    ["\%27", "'"],
    ["\%C3\%A9", "é"],
    ["\%E2\%80\%93", "–"],
    ["\%22", "\""],
    ["\%C3\%B6", "ö"],
    ["\%E2\%80\%99", "’"],
    ["\%C3\%A8", "è"],
    ["\%C5\%91", "ő"],
]

var unescape = Fn.new { |text|
    for (u in unescs) text = text.replace(u[0], u[1])
    return text
}

var url = "https://rosettacode.org/wiki/Category:Programming_Tasks"
var content = getContent.call(url)
var p1 = Pattern.new("<li><a href/=\"//wiki//[+1^\"]\"")
var p2 = Pattern.new("<~//+0^>>")
var matches = p1.findAll(content)
var tasks = matches.map { |m| m.capsText[0] }.toList
for (task in tasks.take(3)) {  // just show the first 3 say
    var taskUrl = "https://rosettacode.org/wiki/" + task
    var html = getContent.call(taskUrl)
    var text = "using any language you may know.</div>"
    var start = html.indexOf(text)
    var end = html.indexOf("<meta property=\"mw:PageProp/toc\" />")
    html = html[start + text.count...end]
    text = p2.replaceAll(html, "").replace("&#160;", "").trim()
    var title = unescape.call(task)
    System.print("\n****** %(title) ******\n")
    System.print(text)
}


which we embed in the following C program, build and run.

/* gcc Rosetta_Code_Tasks_without_examples.c -o Rosetta_Code_Tasks_without_examples -lcurl -lwren -lm  */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <curl/curl.h>
#include "wren.h"

struct MemoryStruct {
    char *memory;
    size_t size;
};

/* C <=> Wren interface functions */

static size_t WriteMemoryCallback(void *contents, size_t size, size_t nmemb, void *userp) {
    size_t realsize = size * nmemb;
    struct MemoryStruct *mem = (struct MemoryStruct *)userp;
 
    char *ptr = realloc(mem->memory, mem->size + realsize + 1);
    if(!ptr) {
        /* out of memory! */
        printf("not enough memory (realloc returned NULL)\n");
        return 0;
    }

    mem->memory = ptr;
    memcpy(&(mem->memory[mem->size]), contents, realsize);
    mem->size += realsize;
    mem->memory[mem->size] = 0;
    return realsize;
}

void C_bufferAllocate(WrenVM* vm) {
    struct MemoryStruct *ms = (struct MemoryStruct *)wrenSetSlotNewForeign(vm, 0, 0, sizeof(struct MemoryStruct));
    ms->memory = malloc(1);
    ms->size = 0;
}

void C_bufferFinalize(void* data) {
    struct MemoryStruct *ms = (struct MemoryStruct *)data;
    free(ms->memory);
}

void C_curlAllocate(WrenVM* vm) {
    CURL** pcurl = (CURL**)wrenSetSlotNewForeign(vm, 0, 0, sizeof(CURL*));
    *pcurl = curl_easy_init();
}

void C_value(WrenVM* vm) {
    struct MemoryStruct *ms = (struct MemoryStruct *)wrenGetSlotForeign(vm, 0);
    wrenSetSlotString(vm, 0, ms->memory);
}

void C_easyPerform(WrenVM* vm) {
    CURL* curl = *(CURL**)wrenGetSlotForeign(vm, 0);
    curl_easy_perform(curl);
}

void C_easyCleanup(WrenVM* vm) {
    CURL* curl = *(CURL**)wrenGetSlotForeign(vm, 0);
    curl_easy_cleanup(curl);
}

void C_easySetOpt(WrenVM* vm) {
    CURL* curl = *(CURL**)wrenGetSlotForeign(vm, 0);
    CURLoption opt = (CURLoption)wrenGetSlotDouble(vm, 1);
    if (opt < 10000) {
        long lparam = (long)wrenGetSlotDouble(vm, 2);
        curl_easy_setopt(curl, opt, lparam);
    } else if (opt < 20000) {
        if (opt == CURLOPT_WRITEDATA) {
            struct MemoryStruct *ms = (struct MemoryStruct *)wrenGetSlotForeign(vm, 2);
            curl_easy_setopt(curl, opt, (void *)ms);
        } else if (opt == CURLOPT_URL) {
            const char *url = wrenGetSlotString(vm, 2);
            curl_easy_setopt(curl, opt, url);
        }
    } else if (opt < 30000) {
        if (opt == CURLOPT_WRITEFUNCTION) {
            curl_easy_setopt(curl, opt, &WriteMemoryCallback);
        }
    }
}

WrenForeignClassMethods bindForeignClass(WrenVM* vm, const char* module, const char* className) {
    WrenForeignClassMethods methods;
    methods.allocate = NULL;
    methods.finalize = NULL;
    if (strcmp(module, "main") == 0) {
        if (strcmp(className, "Buffer") == 0) {
            methods.allocate = C_bufferAllocate;
            methods.finalize = C_bufferFinalize;
        } else if (strcmp(className, "Curl") == 0) {
            methods.allocate = C_curlAllocate;
        }
    }
    return methods;
}

WrenForeignMethodFn bindForeignMethod(
    WrenVM* vm,
    const char* module,
    const char* className,
    bool isStatic,
    const char* signature) {
    if (strcmp(module, "main") == 0) {
        if (strcmp(className, "Buffer") == 0) {
            if (!isStatic && strcmp(signature, "value") == 0)           return C_value;
        } else if (strcmp(className, "Curl") == 0) {
            if (!isStatic && strcmp(signature, "easySetOpt(_,_)") == 0) return C_easySetOpt;
            if (!isStatic && strcmp(signature, "easyPerform()") == 0)   return C_easyPerform;
            if (!isStatic && strcmp(signature, "easyCleanup()") == 0)   return C_easyCleanup;
        }
    }
    return NULL;
}

static void writeFn(WrenVM* vm, const char* text) {
    printf("%s", text);
}

void errorFn(WrenVM* vm, WrenErrorType errorType, const char* module, const int line, const char* msg) {
    switch (errorType) {
        case WREN_ERROR_COMPILE:
            printf("[%s line %d] [Error] %s\n", module, line, msg);
            break;
        case WREN_ERROR_STACK_TRACE:
            printf("[%s line %d] in %s\n", module, line, msg);
            break;
        case WREN_ERROR_RUNTIME:
            printf("[Runtime Error] %s\n", msg);
            break;
    }
}

char *readFile(const char *fileName) {
    FILE *f = fopen(fileName, "r");
    fseek(f, 0, SEEK_END);
    long fsize = ftell(f);
    rewind(f);
    char *script = malloc(fsize + 1);
    fread(script, 1, fsize, f);
    fclose(f);
    script[fsize] = 0;
    return script;
}

static void loadModuleComplete(WrenVM* vm, const char* module, WrenLoadModuleResult result) {
    if( result.source) free((void*)result.source);
}

WrenLoadModuleResult loadModule(WrenVM* vm, const char* name) {
    WrenLoadModuleResult result = {0};
    if (strcmp(name, "random") != 0 && strcmp(name, "meta") != 0) {
        result.onComplete = loadModuleComplete;
        char fullName[strlen(name) + 6];
        strcpy(fullName, name);
        strcat(fullName, ".wren");
        result.source = readFile(fullName);
    }
    return result;
}

int main(int argc, char **argv) {
    WrenConfiguration config;
    wrenInitConfiguration(&config);
    config.writeFn = &writeFn;
    config.errorFn = &errorFn;
    config.bindForeignClassFn = &bindForeignClass;
    config.bindForeignMethodFn = &bindForeignMethod;
    config.loadModuleFn = &loadModule;
    WrenVM* vm = wrenNewVM(&config);
    const char* module = "main";
    const char* fileName = "Rosetta_Code_Tasks_without_examples.wren";
    char *script = readFile(fileName);
    WrenInterpretResult result = wrenInterpret(vm, module, script);
    switch (result) {
        case WREN_RESULT_COMPILE_ERROR:
            printf("Compile Error!\n");
            break;
        case WREN_RESULT_RUNTIME_ERROR:
            printf("Runtime Error!\n");
            break;
        case WREN_RESULT_SUCCESS:
            break;
    }
    wrenFreeVM(vm);
    free(script);
    return 0;
}
Output:

Just showing the first 3 tasks.

****** 100 doors ******

There are 100 doors in a row that are all initially closed. 
You make 100 passes by the doors. 
The first time through, visit every door and toggle the door (if the door is closed, open it;  if it is open, close it). 
The second time, only visit every 2nd door  (door #2, #4, #6, ...),  and toggle it.  
The third time, visit every 3rd door  (door #3, #6, #9, ...), etc,  until you only visit the 100th door.


Task

Answer the question:  what state are the doors in after the last pass?  Which are open, which are closed?

Alternate:  
As noted in this page's  discussion page,  the only doors that remain open are those whose numbers are perfect squares.
Opening only those doors is an  optimization  that may also be expressed; 
however, as should be obvious, this defeats the intent of comparing implementations across programming languages.

****** 100 prisoners ******

The Problem

100 prisoners are individually numbered 1 to 100
A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
Prisoners start outside the room
They can decide some strategy before any enter the room.
Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
A prisoner can open no more than 50 drawers.
A prisoner tries to find his own number.
A prisoner finding his own number is then held apart from the others.
If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand.


The task

Simulate several thousand instances of the game where the prisoners randomly open drawers
Simulate several thousand instances of the game where the prisoners use the optimal strategy mentioned in the Wikipedia article, of:
First opening the drawer whose outside number is his prisoner number.
If the card within has his number then he succeeds otherwise he opens the drawer with the same number as that of the revealed card. (until he opens his maximum).

Show and compare the computed probabilities of success for the two strategies, here, on this page.


References

The unbelievable solution to the 100 prisoner puzzle standupmaths (Video).
wp:100 prisoners problem
100 Prisoners Escape Puzzle DataGenetics.
Random permutation statistics#One hundred prisoners on Wikipedia.

****** 15 puzzle game ******

Task

Implement the Fifteen Puzzle Game.

The  15-puzzle  is also known as: 

 Fifteen Puzzle
 Gem Puzzle
 Boss Puzzle
 Game of Fifteen
 Mystic Square
 14-15 Puzzle
 and some others.


Related Tasks

 15 Puzzle Solver
 16 Puzzle Game

zkl

This is a bit of a twist on the task: Programmer wants to know which tasks have not been implimeted by their favorite language.

Uses libraries cURL and YAJL (yet another json library).

var [const] CURL=Import("zklCurl"), YAJL=Import("zklYAJL")[0];

fcn getTasks(language){
   continueValue,tasks,curl := "",Data(0,String), CURL();  // "nm\0nm\0...."
   do{	// eg 5 times
      page:=curl.get(("http://rosettacode.org/mw/api.php?"
         "action=query&cmlimit=500"
	 "&format=json"
	 "&list=categorymembers"
	 "&cmtitle=Category:%s"
	 "&cmcontinue=%s").fmt(language,continueValue),Void);
      page=page[0];  // get HTML body
      json:=YAJL().write(page).close();
      json["query"]["categorymembers"].pump(tasks,T("get","title"));
      continueValue=json.find("continue") #{continue : -||,cmcontinue:page|954|19)}
          .toList()	# ( ("continue","-||"), ("cmcontinue","page|954|19") )
	  .apply("concat","=").concat("&"); # continue=-||&cmcontinue=page|954|19
   }while(continueValue);
   tasks
}

var allTasks  =getTasks.future("Programming_Tasks");	    // thread
var draftTasks=getTasks.future("Draft_Programming_Tasks");  // thread
var tasks     =getTasks.future(lang);		  	    // thread

fcn newTasks{
   langTasks:=tasks.pump(Dictionary().add.fp1(Void)); // { "Semordnilap":Void }
   unimplementedTasks:=allTasks.filter('!(langTasks.holds))
             .extend(draftTasks.filter('!(langTasks.holds)));
#if 0
   unimplementedTasks.pump(List()).sort().pump(Console.println);
#else  // this next part is very very slow, useless, can't find a wikimedia api
       // and the amount of information is pretty overwhelming
   curl:=CURL();
   foreach task in (unimplementedTasks.pump(List()).sort()){
      // some task names have a / in them, can't url encode: "Active Directory/Connect"
      page:="https://rosettacode.org/wiki/" + task.replace(" ","_");
      page:=curl.get(page)[0];  // sloooow
      s,s := page.find("\"infobox\""), page.find("<p>",s);
      if(not (e:=page.find("<div id=\"toc\"",s))) e:=page.find("</p>",s);
      println("<h2>%s</h2>\n%s\n<hr>".fmt(task,page[s,e-s].text));
   }
#endif
}

newTasks();
Concise Output:
$ zkl rs_tasks_without.zkl 
15 Puzzle Game
15 puzzle solver
2048
ASCII art diagram converter
AVL tree
Ackermann function
...
Verbose Output:

15 Puzzle Game

Implement the <a href="http://en.wikipedia.org/wiki/15_puzzle" class="extiw" title="wp:15 puzzle">Fifteen Puzzle Game</a>.

Related Task
  • <a href="/wiki/15_puzzle_solver" title="15 puzzle solver">15 Puzzle Solver</a>




15 puzzle solver

Your task is to write a program that finds a solution in the fewest moves possible single moves to a random <a href="http://en.wikipedia.org/wiki/15_puzzle" class="extiw" title="wp:15 puzzle">Fifteen Puzzle Game</a>.
For this task you will be using the following puzzle:

15 14 1 6

9 11  4 12
0 10  7  3

13 8 5 2


Solution:

1  2  3  4
5  6  7  8
9 10 11 12

13 14 15 0

The output must show the moves' directions, like so: left, left, left, down, right... and so on.
There are 2 solutions with 52 moves:
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd
finding either one, or both is an acceptable result.
see: <a rel="nofollow" class="external text" href="http://www.rosettacode.org/wiki/15_puzzle_solver/Optimal_solution">Pretty Print of Optimal Solution</a>

Extra credit.

Solve the following problem:

 0 12  9 13
15 11 10 14
 3  7  2  5
 4  8  6  1


Related Task
  • <a href="/wiki/15_Puzzle_Game" title="15 Puzzle Game">15 puzzle game</a>
  • <a href="/wiki/A*_search_algorithm" title="A* search algorithm">A* search algorithm</a>




2048

The rules are that on each turn the player must choose a direction (up, down, left or right) and all tiles move as far as possible in that direction, some more than others. Two adjacent tiles (in that direction only) with matching numbers combine into one bearing the sum of those numbers. A move is valid when at least one tile can be moved, if only by combination. A new tile with the value of 2 is spawned at the end of each turn at a randomly chosen empty square, if there is one. To win the player must create a tile with the number 2048. The player lo ses if no valid moves are possible.

The name comes from the popular open-source implementation of this game mechanic, <a rel="nofollow" class="external text" href="https://gabrielecirulli.github.io/2048/">2048</a>.

Requirements:

and so on