# Question
Title: Determine Tic-Tac-Toe winner (round based)
Let's play some code-golf!

The challenge is to find the winner of a game of Tic-Tac-Toe.

This has been done many times by giving a board that has one clear winner but here is the twist:

The cells are numbered like this:

```
1|2|3
-+-+-
4|5|6
-+-+-
7|8|9

```

You get an array of exactly 9 moves like that:

```
{3, 5, 6, 7, 9, 8, 1, 2, 3}

```

This is parsed as follows:

* Player 1 marks cell 3
* Player 2 marks cell 5
* Player 1 marks cell 6
* Player 2 marks cell 7
* Player 1 marks cell 9
* **Player 1 has won**

Note: The game does not stop after one player has won, it may happen that the losing player manages to get three in a row after the winning player, but only the first win counts.

Your job is now to get 9 numbers as input and output the winning player and the round in which the win occured. If no one wins, output something constant of your choice. You can receive input and provide output through any standard mean / format.

Have fun!

Some more examples as requested:

```
{2,3,4,5,6,7,1,8,9} => Player 2 wins in round 6
{1,2,4,5,6,7,3,8,9} => Player 2 wins in round 8
{1,2,3,5,4,7,6,8,9} => Player 2 wins in round 8

```

# Answer
> 8 votes
# Retina, 114 bytes

```
(.)(.)
$1O$2X
^
123;;456;;789¶X
{`(.)(.*¶)(.)\1
$3$2
}`.*(.)(.)*\1(?<-2>.)*(?(2)(?!))\1.*¶(..)*
$1$#3
.*¶
T
T`d`Rd

```

Try it online! Based on my answer to Tic-Tac-Toe - X or O?. Outputs `X<N>` if the first player wins after `N` turns, `O<N>` if the second player wins, `T` if neither wins. Explanation:

```
(.)(.)
$1O$2X
^
123;;456;;789¶X

```

Creates an internal board, and also marks each move with the player whose move it is.

```
{`(.)(.*¶)(.)\1
$3$2

```

Applies a move.

```
}`.*(.)(.)*\1(?<-2>.)*(?(2)(?!))\1.*¶(..)*
$1$#3

```

Searches for a win, and if one is found, then replace the board with the winner and the number of remaining moves.

```
.*¶
T

```

If the moves are exhausted and nobody has won then the game is a tie.

```
T`d`Rd

```

Calculate the number of the round from the number of remaining moves.

# Answer
> 6 votes
# MATL, 39 bytes

```
3:g&+XIx"IX@oXK@(XIt!yXdyPXd&hK=Aa?KX@.

```

Output is

* `1` and `R`, in separate lines, if user 1 wins in round *R*;
* `0` and `R`, in separate lines, if user 2 wins in round *R*;
* empty if no one wins.

Try it online! Or verify all test cases.

### Explanation

```
3:       % Push [1 2 3]
g        % Convert to logical. Gives [true true true]
&+       % Matrix of all pairs of additions. Gives a 3×3 matrix, which represents
         % the board in its initial state, namely all cells contain 2. This value
         % means "cell not used yet". 1 will represent "cell marked by user 1",
         % and 0 will represent "cell marked by user 2"
XI       % Copy into clipboard I
x        % Delete
"        % Implicit input: array with moves. For each move
  I      %   Push current board state
  X@     %   Push iteration index (starting at 1), that is, current round number
  o      %   Modulo 2: gives 1 or 0. This represents the current user
  XK     %   Copy into clipboard K
  @      %   Push current move ((that is, cell index)
  (      %   Write user identifier (1 or 0) into that cell. Cells are indexed
         %   linearly in column-major order. So the board is transposed compared
         %   to that in the challenge, but that is unimportant
  XI     %   Copy updated board into clipboard I
  t!     %   Duplicate and transpose
  y      %   Duplicate from below: push copy of board
  Xd     %   Extract main diagonal as a 3×1 vector
  y      %   Duplicate from below: push copy of transposed board
  PXd    %   Flip vertically and extract main diagonal. This is the anti-diagonal
         %   of the board
  &h     %   Concatenate stack horizontally. This concatenates the board (3×3),
         %   transposed board (3×3), main diagonal (3×1 vector) and anti-diagonal
         %   (3×1) into an 3×8 matrix
  K=     %   Push current user identifier. Test for equality with each entry of the
         %   3×8 matrix
  A      %   For each column, this gives true if all its entries are true. Note
         %   that the first three columns in the 3×8 matrix are the board columns;
         %   the next three are the board rows; and the last two columns are the
         %   main diagonal and anti-diagonal. The result is a 1×8 vector
  a      %   True if any entry is true, meaning the current user has won
  ?      %   If true
    K    %     Push current user identifier
    X@   %     Push current round number
    .    %     Break for loop
         %   Implicit end
         % Implicit end
         % Implicit display

```

# Answer
> 5 votes
# Javascript (ES6), 130 bytes

```
m=>m.reduce((l,n,i)=>l||(b[n-1]=p=i%2+1,"012,345,678,036,147,258,048,246".replace(/\d/g,m=>b[m]).match(""+p+p+p)&&[p,i+1]),0,b=[])

```

```
f=m=>m.reduce((l,n,i)=>l||(b[n-1]=p=i%2+1,"012,345,678,036,147,258,048,246".replace(/\d/g,m=>b[m]).match(""+p+p+p)&&[p,i+1]),0,b=[])
console.log(JSON.stringify(f([3,5,6,7,9,8,1,2,3])))
console.log(JSON.stringify(f([2,3,4,5,6,7,1,8,9])))
console.log(JSON.stringify(f([1,2,4,5,6,7,3,8,9])))
console.log(JSON.stringify(f([1,2,3,5,4,7,6,8,9])))
```

## Explanation

```
m=>m.reduce((l,n,i)=>               // Reduce the input array with n as the current move
  l||(                              //  If there is already a winner, return it
  b[n-1]=p=i%2+1,                   //  Set the cell at b[n-1] to the current player p
  "012,345,678,036,147,258,048,246" //  For every digit in the list of possible rows:
    .replace(/\d/g,m=>b[m])         //   Replace it with the player at the cell
    .match(""+p+p+p)                //  If any of the rows is filled with p:
      &&[p,i+1]                     //   Return [p, current move]
),0,b=[])

```

# Answer
> 4 votes
# Java (OpenJDK 8), 445 bytes

```
int[] t(int[]m){int[][]f=new int[3][3];boolean z=false;for(int i=0;i<9;i++){f[m[i]%3][m[i]/3]=z?2:1;if(f[m[i]%3][0]==(z?2:1)&&f[m[i]%3][1]==(z?2:1)&&f[m[i]%3][2]==(z?2:1)||f[0][m[i]/3]==(z?2:1)&&f[1][m[i]/3]==(z?2:1)&&f[2][m[i]/3]==(z?2:1)||m[i]%3+m[i]/3==2&&f[0][2]==(z?2:1)&&f[1][1]==(z?2:1)&&f[2][0]==(z?2:1)||m[i]%3==m[i]/3&&f[0][0]==(z?2:1)&&f[1][1]==(z?2:1)&&f[2][2]==(z?2:1)){return(new int[]{(z?2:1),++i});}z=!z;}return(new int[]{0,0});}

```

Try it online!

Return value {1,8} means that player 1 won in round 8. Return value {0,0} means draw.

# Answer
> 2 votes
# Kotlin, 236 bytes

```
i.foldIndexed(l()to l()){o,(a,b),p->fun f(i:(Int)->Int)=b.groupBy(i).any{(_,v)->v.size>2}
if(f{(it-1)/3}|| f{it%3}|| listOf(l(1,5,9),l(3,5,7)).any{b.containsAll(it)}){return p%2+1 to o}
b to a+p}.let{null}
fun l(vararg l:Int)=l.toList()

```

## Beautified

```
    i.foldIndexed(l() to l()) { o, (a, b), p ->
        fun f(i: (Int) -> Int) = b.groupBy(i).any { (_, v) -> v.size > 2 }
        if (f { (it - 1) / 3 } || f { it % 3 } || listOf(l(1, 5, 9), l(3, 5, 7)).any { b.containsAll(it) }) {
            return p % 2 + 1 to o
        }
        b to a + p
    }.let { null }
fun l(vararg l:Int)= l.toList()

```

## Test

```
fun f(i: List<Int>): Pair<Int, Int>? =
i.foldIndexed(l()to l()){o,(a,b),p->fun f(i:(Int)->Int)=b.groupBy(i).any{(_,v)->v.size>2}
if(f{(it-1)/3}|| f{it%3}|| listOf(l(1,5,9),l(3,5,7)).any{b.containsAll(it)}){return p%2+1 to o}
b to a+p}.let{null}
fun l(vararg l:Int)=l.toList()

data class Test(val moves: List<Int>, val winner: Int, val move: Int)

val tests = listOf(
        Test(listOf(3, 5, 6, 7, 9, 8, 1, 2, 3), 1, 5),
        Test(listOf(2, 3, 4, 5, 6, 7, 1, 8, 9), 2, 6),
        Test(listOf(1, 2, 4, 5, 6, 7, 3, 8, 9), 2, 8),
        Test(listOf(1, 2, 3, 5, 4, 7, 6, 8, 9), 2, 8)
)

fun main(args: Array<String>) {
    tests.forEach { (input, winner, move) ->
        val result = f(input)
        if (result != winner to move) {
            throw AssertionError("$input ${winner to move} $result")
        }
    }
}

```

## TIO

TryItOnline

# Answer
> 1 votes
# Python 2, 170 bytes

```
q=map(input().index,range(1,10))
z=zip(*[iter(q)]*3)
o='',
for l in[q[2:7:2],q[::4]]+z+zip(*z):
 r=[n%2for n in l];y=all(r)*2+1-any(r)
 if y:o+=[max(l)+1,y],
print min(o)

```

Try it online! or Try all test cases

```
#swap cell number / turn
q=map(input().index,range(1,10))
#split in 3 parts (rows)
z=zip(*[iter(q)]*3)
#starting value for the list with the results
#since string are "greater" than lists, this will
#be the output value when there is a draw
o='',
#iterate over diagonals, rows and columns
for l in[q[2:7:2],q[::4]]+z+zip(*z):
 #use %2 to separate between player 1 and 2
 r=[n%2 for n in l]
 #store in y the value of the player if the trio is a valid win, 0 otherwise
 #it's a win if all moves are from the same player
 y=all(r)*2+1-any(r)
 #if y has a valid player, add the highest turn of the trio, and the player to o
 if y:o+=[max(l)+1,y],
#output the smaller turn of the valid winning trios
print min(o)

```

# Answer
> 1 votes
# Jelly, 38 bytes

```
;⁵s2ZṬḤ2¦SṖs3µ,ṚJị"$€;;ZEÐfṀḢµ$ƤµTḢ,ị¥

```

Try it online!

Player 1 win: `[round, 1]`
Player 2 win: `[round, 2]`
Tie: `[0, 0]`

# Answer
> 1 votes
## Python 3.6+, 137 bytes

```
n=m=c=z=0
for a in input():m+=1<<~-int(a);c+=1;z=z or f'{c&1}:{c}'*any(m&t==t for t in[7,56,448,73,146,292,273,84]);n,m=m,n
print(z or-1)

```

Output format is `winner number:round` or `-1` for a tie. Player 2 is `0` Player 1 is `1`. Input in the form of a undeliminated string of 1-indexed square numbers.

# Answer
> 1 votes
# Jelly, 35 bytes

```
9s3,ZU$$;ŒD$€Ẏf€⁸L€3e
s2ZÇƤ€ZFTḢ;Ḃ$

```

A monadic link taking a list of the moves and returning a list, `[move, player]` where the players are identified as `1` (first to act) and `0` (second to act).

**Try it online!**

### How?

```
9s3,ZU$$;ŒD$€Ẏf€⁸L€3e - Link 1: any winning play?: list of player's moves:
9s3                   - (range of) nine split into threes = [[1,2,3],[4,5,6],[7,8,9]]
       $              - last two links as a monad:
      $               -   last two links as a monad:
    Z                 -     transpose = [[1,4,7],[2,5,8],[3,6,9]]
     U                -     upend     = [[7,4,1],[8,5,2],[9,6,3]]
   ,                  -  pair = [[[1,2,3],[4,5,6],[7,8,9]],[[7,4,1],[8,5,2],[9,6,3]]]
           $€         - last two links as a monad for €ach:
         ŒD           -   diagonals = [[1,5,9],[2,6],[3],[7],[4,8]] or [[7,5,3],[4,2],[1],[9],[8,6]]
        ;             -  concatenate = [[1,2,3],[4,5,6],[7,8,9],[1,5,9],[2,6],[3],[7],[4,8]] or [[7,4,1],[8,5,2],[9,6,3],[7,5,3],[4,2],[1],[9],[8,6]]
             Ẏ        - tighten = [[1,2,3],[4,5,6],[7,8,9],[1,5,9],[2,6],[3],[7],[4,8],[7,4,1],[8,5,2],[9,6,3],[7,5,3],[4,2],[1],[9],[8,6]]
                      -    i.e.:    row1    row2    row3    diag\   x     x   x   x     col1    col2    col3    diag/   x     x   x   x
                      -    where x's are not long enough to matter for the rest...
                ⁸     - chain's left argument, list of player's moves
              f€      - filter to keep those moves for €ach of those lists to the left
                 L€   - length of €ach result
                   3e - 3 exists in that? (i.e. were any length 3 when filtered down to only moves made?)

s2ZÇƤ€ZFTḢ;Ḃ$ - Main link: list of the moves  e.g. [2,3,4,5,6,7,1,8,9]
s2            - split into twos                    [[2,3],[4,5],[6,7],[1,8],[9]]
  Z           - transpose                          [[2,4,6,1,9],[3,5,7,8]]
    Ƥ€        - for Ƥrefixes of €ach:
   Ç          -   call last link (1) as a monad     [0,0,0,0,0] [0,0,1,1]
      Z       - transpose                          [[0,0],[0,0],[0,1],[0,1],[0]]
       F      - flatten                            [0,0,0,0,0,1,0,1,0]
        T     - truthy indices                     [          6   8  ]
         Ḣ    - head (if empty yields 0)           6
            $ - last two links as a monad:
           Ḃ  -   modulo by 2 (evens are player 2) 0
          ;   -   concatenate                      [6,0]

```

# Answer
> 0 votes
# Clean, ~~244~~ ... 220 bytes

```
import StdEnv
f[a,b]i#k= \l=or[and[isMember(c+n)(take i l)\\c<-:"123147159357"%(j,j+2)]\\j<-[0,3..9]&h<-:"\0\0",n<-[h-h,h,h+h]]
|k a=(1,i*2-1)|i>4=(0,0)|k b=(2,i*2)=f[a,b](i+1)
@l=f(map(map((!!)l))[[0,2..8],[1,3..7]])1

```

Try it online!

The string iterated into `h` contains nonprintables, and is equivalent to `"\003\001\000\000"`.

# Answer
> 0 votes
# Python 2, ~~140~~ ~~136~~ 134 bytes

```
lambda a,i=0:i<9and(any(set(a[i%2:i+1:2])>=set(map(int,t))for t in'123 456 789 147 258 369 159 357'.split())and(i%2+1,i+1)or f(a,i+1))

```

Try it online!

EDIT: 4 bytes + 2 bytes thx to Eric the Outgolfer.

Outputs a tuple (playerNumber, roundNumber) or False if there is no winner.

# Answer
> 0 votes
# Python 2, 168 bytes

```
import itertools as z
f=lambda g:next(([i%2+1,i+1]for i in range(9) if any(c for c in z.combinations([[0,6,1,8,7,5,3,2,9,4][j]for j in g[i%2:i+1:2]],3)if sum(c)==15)),0)

```

Outputs (player,round) or 0 for a tie.

Maps the game onto a 3-by-3 magic square and looks for sets of 3 Os or Xs that sum to 15.

---
Tags: code-golf, tic-tac-toe
---


title: Case-fold German

text:
# Question
Title: Case-fold German
### Given a German string and an indication of a case (lower/upper/title), fold the string to that case.

## Specifications

1. Input will consist only of `a``z` plus `äöüß-,.;:!?'"` in uppercase and/or lowercase.
2. The target case may be taken as any three unique values (please specify what they are) of a consistent type; either three characters, or three numbers, or three bit patterns. (Other formats are currently not allowed to prevent "outsourcing" the answer to the case specification. Comment if you think that an additional format should be allowed.)
3. Titlecase means uppercase everything except letters that follow a letter (letters are `a``z` plus `äöüß`).

## Gotchas

1. When `ß` needs to be uppercase, it must become . Some case-folding built-ins and libraries do not do this.
2. When `ß` needs to be titlecase, it must become `Ss`. Some case-folding built-ins and libraries do not do this.
3. `ss` may occur in the text, and should never be converted to `ß` or .

## Examples

Upper case `die Räder sagen "ßß ss" für dich, wegen des Öls!`
is `DIE RÄDER SAGEN "ẞẞ SS" FÜR DICH, WEGEN DES ÖLS!`

Lower case `die Räder sagen "ßß ss" für dich, wegen des Öls!`
is `die räder sagen "ßß ss" für dich, wegen des öls!`

Title case `die Räder sagen "ßß ss" für dich, wegen des Öls!`
is `Die Räder Sagen "Ssß Ss" Für Dich, Wegen Des Öls!`

# Answer
> 6 votes
# Japt, ~~42~~ 40 bytes

*Saved 2 bytes thanks to @Oliver*

```
r'ßQ=7838d)u mV,@W¦vW=X ?Xv :X¥Q?"Ss":Xu

```

Whew, that took quite some effort. Input is the string to convert, and a single character: `u` for uppercase, `v` for lowercase, `m` for title case.

Test it online!

# Answer
> 4 votes
# Python 3, 92 bytes

```
lambda s,c:[str.lower,str.upper,str.title][c](s.replace("ẞ","ß").replace("ß"*c,"ẞ"*c))

```

Try it online!

# Answer
> 3 votes
# Jelly, 50 bytes

```
⁽ñWỌ”ß;y⁸Œu
Ñ⁾SsÇ⁼?€1¦”ß
Œl
Çe€“Ġẹṇṣ‘ỌÇ;Øa¤Œg⁸ṁ⁹Ŀ€

```

Try it online!

Full program.

Phew, this took much time to golf...

Argument 1: String (may need to be escaped)
Argument 2: `1` for uppercase, `2` for title case, `3` for lowercase.

# Answer
> 3 votes
# 05AB1E, 23 bytes

Uses **0** = lower, **1** = upper, **2** = title

```
•^ŠX•4ôçIiR}`:"lu™"¹è.V

```

Try it online!

# Answer
> 1 votes
# Clean, ~~649~~ ~~279~~ ~~275~~ ~~274~~ 246 bytes

Yes, that's ~~123~~ ~~122~~ 94 bytes of imports, which is already longer than every other answer.

```
from StdList import++,map,flatten
import StdLib,StdInt,StdBool,Text.Unicode,Text.Unicode.UChar
$ =fromInt
? =isAlpha
^ =toUpper
@0s=map^s
@1s=map toLower s
@2s=flatten(map(\[h:t]=if($223==h||h> $999)[$83,$115][^h]++ @1t)(groupBy(\a b= ?a== ?b)s))

```

Try it online!

Defines the function `@`, taking an `Int` and a `UString`, and returning a `UString`.
Conveniently, `UString` (Clean's default way of handling Unicode), is just a type alias for `[Int]` \- which is a list of `Int` containing unicode codepoints of the characters in the string.
*Inconveniently*, `Text.Unicode.UChar` is really long, and I can't `import StdEnv` because the definitions in `StdChar` conflict with the definitions in `Text.Unicode.UChar` (as they are not intended for use together).

The three values are 0, 1, and 2 for Upper, Lower, and Title case.

---
Tags: code-golf, string, natural-language, alphabet, text-processing
---


# Question
Title: Debunking Stroustrup's debunking of the myth “C++ is for large, complicated, programs only”
Stroustrup has recently posted a series of posts debunking popular myths about C++. The fifth myth is: “C++ is for large, complicated, programs only”. To debunk it, he wrote a simple C++ program **downloading a web page and extracting links from it**. Here it is:

```
#include <string>
#include <set>
#include <iostream>
#include <sstream>
#include <regex>
#include <boost/asio.hpp>

using namespace std;

set<string> get_strings(istream& is, regex pat)
{
    set<string> res;
    smatch m;
    for (string s; getline(is, s);)  // read a line
        if (regex_search(s, m, pat))
            res.insert(m[0]);              // save match in set
    return res;
}

void connect_to_file(iostream& s, const string& server, const string& file)
// open a connection to server and open an attach file to s
// skip headers
{
    if (!s)
        throw runtime_error{ "can't connect\n" };

    // Request to read the file from the server:
    s << "GET " << "http://" + server + "/" + file << " HTTP/1.0\r\n";
    s << "Host: " << server << "\r\n";
    s << "Accept: */*\r\n";
    s << "Connection: close\r\n\r\n";

    // Check that the response is OK:
    string http_version;
    unsigned int status_code;
    s >> http_version >> status_code;

    string status_message;
    getline(s, status_message);
    if (!s || http_version.substr(0, 5) != "HTTP/")
        throw runtime_error{ "Invalid response\n" };

    if (status_code != 200)
        throw runtime_error{ "Response returned with status code" };

    // Discard the response headers, which are terminated by a blank line:
    string header;
    while (getline(s, header) && header != "\r")
        ;
}

int main()
{
    try {
        string server = "www.stroustrup.com";
        boost::asio::ip::tcp::iostream s{ server, "http" };  // make a connection
        connect_to_file(s, server, "C++.html");    // check and open file

        regex pat{ R"((http://)?www([./#\+-]\w*)+)" }; // URL
        for (auto x : get_strings(s, pat))    // look for URLs
            cout << x << '\n';
    }
    catch (std::exception& e) {
        std::cout << "Exception: " << e.what() << "\n";
        return 1;
    }
}

```

Let's show Stroustrup what **small and readable** program actually is.

1. Download `http://www.stroustrup.com/C++.html`
2. List all links:

```
 http://www-h.eng.cam.ac.uk/help/tpl/languages/C++.html
 http://www.accu.org
 http://www.artima.co/cppsource
 http://www.boost.org
 ...

```

You can use any language, but no third-party libraries are allowed.

# Winner

C++ answer won by votes, but it relies on a semi-third-party library (which is disallowed by rules), and, along with another close competitor Bash, relies on a hacked together HTTP client (it won't work with HTTPS, gzip, redirects etc.). So **Wolfram** is a clear winner. Another solution which comes close in terms of size and readability is PowerShell (with improvement from comments), but it hasn't received much attention. Mainstream languages (Python, C#) came pretty close too.

# Comment on subjectivity

The most upvoted answer (C++) at the moment votes were counted was **disqualified for not following the rules** listed here in the question. There's nothing subjective about it. The second most upvoted question at that moment (Wolfram) was declared winner. The third answer's (Bash) "disqualification" is subjective, but it's **irrelevant** as the answer didn't win by votes at any point in time. You can consider it a comment if you like. Furthermore, right now the Wolfram answer is the most upvoted answer, the accepted one, and is declared winner, which means there's zero debate or subjectivity.

# Answer
> 119 votes
# Wolfram

This feels like complete cheating

```
Import["http://www.stroustrup.com/C++.html", "Hyperlinks"]

```

So just add some honest parsing on top

```
Cases[
 Import["http://www.stroustrup.com/C++.html", "XMLObject"],
 XMLElement["a", {___, "href" -> link_, ___}, ___] :>
  link /; StringMatchQ[link, RegularExpression["((http://)?www([./#\\+-]\\w*)+)"]]
, Infinity]

```

# Answer
> 114 votes
# C++

```
#include <boost/asio.hpp>
#include <regex>
#include <iostream>
int main() {
    std::string server = "www.stroustrup.com";
    std::string request = "GET http://" + server + "/C++.html HTTP/1.0\r\nHost: " + server + "\r\n\r\n";
    boost::asio::ip::tcp::iostream s{server, "http"};
    s << request;
    std::regex pat{R"((http://)?www([./#\+-]\w*)+)"};
    std::smatch m;
    for (std::string l; getline(s, l);)
        if (std::regex_search(l, m, pat))
            std::cout << m[0] << "\n";
}

```

The main shortcoming is the awkward nature of boost::asio, I'm sure it can be even shorter with a better library.

# Answer
> 88 votes
# Pure Bash on Linux/OS X (no external utilities)

HTTP client software is notoriously bloated. We don't want those kinds of dependencies. Instead we can push the appropriate headers down a TCP stream and read the result. No need to call archaic utilities like grep or sed to parse the result.

```
domain="www.stroustrup.com"
path="C++.html"
exec 3<> /dev/tcp/$domain/80
printf "GET /$path HTTP/1.1\r\nhost: %s\r\nConnection: close\r\n\r\n" "$domain" >&3
while read -u3; do
    if [[ "$REPLY" =~ http://[^\"]* ]]; then
        printf '%s\n' "$BASH_REMATCH"
    fi
done

```

Meh - I suppose it could be more readable...

# Answer
> 66 votes
# Python 2

```
import urllib2 as u, re
s = "http://www.stroustrup.com/C++.html"
w = u.urlopen(s)
h = w.read()
l = re.findall('"((http)s?://.*?)"', h)
print l

```

Lame, but works

# Answer
> 53 votes
# C#

```
using System;
using System.Net;
using System.Text.RegularExpressions;

string html = new WebClient().DownloadString("http://www.stroustrup.com/C++.html");
foreach (Match match in Regex.Matches(html, @"https?://[^""]+"))
    Console.WriteLine(match);

```

# Answer
> 52 votes
# "No third-party" is a fallacy

I think the "no third-party" assumption is a fallacy. And is a specific fallacy that afflicts C++ developers, since it's so hard to make reusable code in C++. When you are developing anything at all, even if it's a small script, you will always make use of whatever pieces of reusable code are available to you.

The thing is, in languages like Perl, Python, Ruby (to name a few), reusing someone else's code is not only easy, but it is how most people actually write code most of the time.

C++, with its nearly impossible-to-maintain-compatible-ABI-requirements makes that a much tougher job, you end up with a project like Boost, which is a monstrous repository of code and very little composability outside it.

## A CPAN example

Just for the fun of it, here goes a CPAN-based example, with proper parsing of the html, instead of trying to use regex to parse html

```
#!/usr/bin/perl
use HTML::LinkExtor;
sub callback {
   my ($tag, %links) = @_;
   print map { "$_\n" } values %links
}
$p = HTML::LinkExtor->new(\&callback, "http://www.stroustrup.com/C++.html");

```

# Answer
> 46 votes
# UNIX shell

```
lynx -dump http://www.stroustrup.com/C++.html | grep -o '\w*://.*'

```

Also finds an `ftp://` link :)

Another way, without relying on `://` syntax:

```
lynx -dump -listonly http://www.stroustrup.com/C++.html | sed -n 's/^[ 0-9.]\+//p'

```

# Answer
> 44 votes
# CSS 3

```
* {
  margin: 0;
  padding: 0;
}
*:not(a) {
  font: 0/0 monospace;
  color: transparent;
  background: transparent !important;
}
a {
  content: "";
}
a[href*="://"]::after {
  content: attr(href);
  float: left;
  clear: left;
  display: block;
  font: 12px monospace;
  color: black;
}

```

This code can be used as a user style to display only absolute links on a page in an unformatted list. It may not work correctly if your browser enforces minimum font size.

It works correctly with `http://www.stroustrup.com/C++.html` (note `!important` on `background`). In order to work on other pages with more styles, it must be extended (reset more properties, mark properties as important etc.).

Alternative version which includes relative links except intrapage links starting with hashes (it relies on a hard-coded absolute link, unfortunately):

```
* {
  margin: 0;
  padding: 0;
}
*:not(a) {
  font: 0/0 monospace;
  color: transparent;
  background: transparent !important;
  float: none !important;
  width: auto !important;
  border: none !important;
}
a {
  content: "";
}
a::after {
  display: none;
}
a:not([href^="#"])::after {
  content: attr(href);
  float: left;
  clear: left;
  display: block;
  font: 12px monospace;
  color: black;
}
a:not([href*="://"])::after {
  content: "http://www.stroustrup.com/" attr(href);
}

```

# Answer
> 37 votes
# Clojure

```
(->> (slurp "http://www.stroustrup.com")
     (re-seq #"(?:http://)?www(?:[./#\+-]\w*)+"))

```

# Answer
> 33 votes
## Emacs Lisp

```
(with-current-buffer (url-retrieve-synchronously "http://www.stroustrup.com/C++.html")
  (while (re-search-forward "https?://[^\\\"]*")
    (print (match-string 0))))

```

# Answer
> 28 votes
**Scala**

```
"""\"(https?://.*?)\"""".r.findAllIn(scala.io.Source.fromURL("http://www.stroustrup.com/C++.html").mkString).foreach(println)

```

# Answer
> 25 votes
# PHP 5

```
<?php
preg_match_all('/"(https?:\/\/.*?)"/',file_get_contents('http://www.stroustrup.com/C++.html'),$m);
print_r($m[1]);

```

# Answer
> 23 votes
## PowerShell

Text search for all fully-qualified URLs (including JavaScript, CSS, etc.):

```
[string[]][regex]::Matches((iwr "http://www.stroustrup.com/C++.html"), '\w+://[^"]+')

```

Or to get links in anchor tags only (includes relative URLs):

```
(iwr "http://www.stroustrup.com/C++.html").Links | %{ $_.href }

```

Shorter versions from comments:

```
(iwr "http://www.stroustrup.com/C++.html").Links.href

```

```
(iwr "http://www.stroustrup.com/C++.html").Links.href-match":"

```

# Answer
> 23 votes
# D

```
import std.net.curl, std.stdio;
import std.algorithm, std.regex;

void main() {
foreach(_;byLine("http://www.stroustrup.com/C++.html")
    .map!((a)=>a.matchAll(regex(`<a.*?href="(.*)"`)))
    .filter!("a")){ writeln(_.front[1]); }
}

```

# Answer
> 21 votes
# Node.js

```
var http = require('http');

http.get('http://www.stroustrup.com/C++.html', function (res) {
    var data = '';
    res.on('data', function (d) {
        data += d;
    }).on('end', function () {
        console.log(data.match(/"https?:\/\/.*?"/g));
    }).setEncoding('utf8');
});

```

# Answer
> 21 votes
# Haskell

Some troubles with `"\w"` in Text.Regex.Posix

```
import Network.HTTP
import Text.Regex.Posix
pattern = "((http://)?www([./#\\+-][a-zA-Z]*)+)"
site = "http://www.stroustrup.com/C++.html"

main = do
    file <- getResponseBody =<< simpleHTTP (getRequest site)
    let result = getAllTextMatches $ file =~ pattern
    putStr $ unlines result -- looks nicer

```

# Answer
> 19 votes
# Ruby

```
require 'net/http'
result = Net::HTTP.get(URI.parse('http://www.stroustrup.com/C++.html'))
result.scan(/"((http)s?://.*?)"/)

```

# Answer
> 18 votes
# PHP

As far as I can tell, most modern PHP installations come with DOM processing, so here's one that actually traverses the anchors inside the HTML:

```
foreach (@DOMDocument::loadHTMLFile('http://stroustrup.com/C++.html')->getElementsByTagName('a') as $a) {
    if (in_array(parse_url($url = $a->getAttribute('href'), PHP_URL_SCHEME), ['http', 'https'], true)) {
        echo $url, PHP_EOL;
    }
}

```

The inner loop could be shortened to:

```
preg_match('~^https?://~', $url = $a->getAttribute('href')) && printf("%s\n", $url);

```

# Answer
> 14 votes
# Unix Shell

```
wget -q -O - http://www.stroustrup.com/C++.html | sed -n '/http:/s/.*href="\([^"]*\)".*/\1/p' | sort

```

Though i have to admit this doesn't work if there's more than one link on a line.

# Answer
> 14 votes
# Java

```
import java.util.regex.*;
class M{
    public static void main(String[]v)throws Throwable{
        Matcher m = Pattern.compile( "\"((http)s?://.*?)\"" )
            .matcher(
                 new Scanner(
                         new URL( "http://www.stroustrup.com/C++.html" )
                             .openStream(),
                         "UTF-8")
                     .useDelimiter("\\A")
                     .next());
        while(m.find())
            System.out.println(m.group());
    }
}

```

# Answer
> 11 votes
# Groovy

```
"http://www.stroustrup.com/C++.html".toURL().text.findAll(/https?:\/\/[^"]+/).each{println it}

```

# Answer
> 11 votes
# SQL (SQL Anywhere 16)

## Define a stored procedure to fetch the web page

```
CREATE OR REPLACE PROCEDURE CPPWebPage()
URL 'http://www.stroustrup.com/C++.html'
TYPE 'HTTP';

```

## Produce the result set using a single query

```
SELECT REGEXP_SUBSTR(Value,'"https?://[^""]+"',1,row_num) AS Link
FROM (SELECT Value FROM CPPWebPage() WITH (Attribute LONG VARCHAR, Value LONG VARCHAR)
      WHERE Attribute = 'Body') WebPage,
      sa_rowgenerator( 1, 256 )
WHERE Link IS NOT NULL;

```

Limitations: This produces up to 256 links. If more links exist, then bump up the 256 to an appropriate value.

# Answer
> 10 votes
# CoffeeScript / NodeJS

```
require('http').get 'http://www.stroustrup.com/C++.html', (r) ->
    dt = '';
    r.on 'data', (d) -> dt += d
    r.on 'end' , (d) -> console.log dt.match /"((http)s?:\/\/.*?)"/g

```

# Answer
> 9 votes
## Perl

```
use LWP;
use feature 'say';

my $agent = new LWP::UserAgent();
my $response = $agent->get('http://www.stroustrup.com/C++.html');

say for $response->content =~ m<"(https?://.+?)">g;

```

# Answer
> 9 votes
# R

```
html<-paste(readLines("http://www.stroustrup.com/C++.html"),collapse="\n")
regmatches(html,gregexpr("http[^([:blank:]|\\\"|<|&|#\n\r)]+",html))

```

...although R is written mainly in C... so probably a few lines of C code behind those 2 lines of R code.

# Answer
> 8 votes
**Objective-C**

```
NSString *s;
for (id m in [[NSRegularExpression regularExpressionWithPattern:@"\"((http)s?://.*?)\"" options:0 error:nil] matchesInString:(s=[NSString stringWithContentsOfURL:[NSURL URLWithString:@"http://www.stroustrup.com/C++.html"]])]){
    NSLog(@"%@",[s substringWithRange:[m range]]);
}

```

# Answer
> 7 votes
# Go

```
package main

import (
    "fmt"
    "io/ioutil"
    "net/http"
    "os"
    "regexp"
)

func main() {
    resp, err := http.Get("http://www.stroustrup.com/C++.html")
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }
    defer resp.Body.Close()
    data, _ := ioutil.ReadAll(resp.Body)
    results := regexp.MustCompile(`https?://[^""]+`).FindAll(data, -1)
    for _, row := range results {
        fmt.Println(string(row))
    }
}

```

**P.S.** this code reads entire source into memory, so consider using `regexp.FindReaderIndex` to search in stream, that'll make the app bulletproof.

# Answer
> 7 votes
## Tcl

```
package require http
set html [http::data [http::geturl http://www.stroustrup.com/C++.html]]
puts [join [regexp -inline -all {(?:http://)?www(?:[./#\+-]\w*)+} $html] \n]

```

# Answer
> 6 votes
# CJam

CJam does not have regex so I had to use a different approach in this one:

```
"http://www.stroustrup.com/C++.html"g''/'"*'"/(;2%{_"http://"#!\"https://"#!e|},N*

```

I first convert all `'` to `"`, then I split on all `"`, take every alternative string and then finally filter that list for strings starting with `http://` or `https://`. After that, simply print each filtered string on a new line.

Try it using the Java interpreter like

```
java -jar cjam-0.6.2.jar file.cjam

```

where file.cjam has the contents of the code above.

# Answer
> 6 votes
# F#

This code could be far shorter but I would write something like this if I ever expected to have to read or use this code again so it has many unnecessary type annotations. It demonstrates the use of an active pattern *MatchValue* to enable pattern-matching against the standard CLR type *Match*

```
open System.Net

let (|MatchValue|) (reMatch: Match) : string = reMatch.Value

let getHtml (uri : string) : string =
    use webClient = WebClient() in
        let html : string = webClient.DownloadString(uri)
        html

let getLinks (uri : string) : string list =
    let html : string = getHtml uri
    let matches : MatchCollection = Regex.Matches(html, @"https?://[^""]+")
    let links = [ for MatchValue reMatch in matches do yield reMatch ]
    links

let links = getLinks "http://www.stroustrup.com/C++.html"
for link in links do
    Console.WriteLine(link)

```

**Edit** I made getLinks its own function

# Answer
> 6 votes
# Rebol

```
parse read http://www.stroustrup.com/C++.html [
    any [
        thru {<a href="} copy link to {"} (print to-string link)
    ]
]

```

# Answer
> 5 votes
# Delphi

```
program Links;
{$APPTYPE CONSOLE}
{$R *.res}
uses
  System.SysUtils, idHTTP, RegularExpressions;
var
  client: TidHTTP;
  match : TMatch;
begin
  client := TidHTTP.Create;
  try
    match := TRegEx.Create('<a(.*)href="(.*)">(.*)<\/a>', [roIgnoreCase, roMultiline])
      .match(client.Get('http://www.stroustrup.com/C++.html'));
    with match do
      while Success do
      begin
        if Groups.Count >= 3 then
          if copy(lowercase(Groups[2].Value), 1, 4) = 'http' then
              writeln(Groups[2].Value);
        match := NextMatch;
      end;
  finally
    client.Free;
  end;
end.

```

This would work in (I suppose) Delphi XE and later. It requires no component other than those that are already installed in a default setup (namedly indy and regular expressions). Even tho delphi is quite close to C++ in general structure, I guess this task turned out to be a bit shorter.

# Answer
> 4 votes
# Ruby

Another Ruby solution:

```
require 'open-uri'
open('http://www.stroustrup.com/C++.html', 'r:iso-8859-1:utf-8') do |f|
  puts f.read.scan(%r{"(https?://www[^"]*)"}).sort
end

```

# Answer
> 4 votes
# MATLAB

Is quite straightforward with urlread and regexp:

```
url = 'http://www.stroustrup.com/C++.html';
links = regexp(urlread(url), '<a href="http://([^"]*\.*)">', 'tokens');

```

# Answer
> 4 votes
# Scala

```
object Downloader extends App {
    val s = io.Source.fromURL("http://www.stroustrup.com/C++.html", "iso-8859-1").mkString // load URL to String
    val regex = """((http://)?www([./#\+-]\w*)+)""".r                                      // create and compile regexp
    println(regex.findAllIn(s).mkString("\n"))                                             // print matches
}

```

# Answer
> 4 votes
# F#

```
open System.Net
open System.Text.RegularExpressions

let html = (new WebClient()).DownloadString("http://www.stroustrup.com/C++.html") in
    Regex.Matches(html, @"https?://[^""]+") |> Seq.cast<Match> |> Seq.iter (printfn "%A")

```

Taken from the C# version.

# Answer
> 4 votes
# SmallTalk (Pharo 3)

> Hurray for \[\]! Also, we should totally add a Smalltalk version ;)

@Bersaelor at Objective-C answer.

I know basics of Smalltalk - syntax of language and some tutorials. I decide that it's good place for practice. I have already installed Pharo 3.0.

> but no third-party libraries are allowed

Okay. On downloaded image I found Zinc-HTTP and regex packages. Probably I should read about "third-party" meaning.

So, code:

```
(ZnClient new get: 'http://www.stroustrup.com/C++.html')
   regex: '((http\://)?www([./#+-]\w*)+)' matchesDo: [ :x | Transcript show: String cr, x ].

```

Code with exception handlings:

```
|response|
[
response := (ZnClient new url: 'http://www.stroustrup.com/C++.html'; get; response).
response isSuccess
  ifFalse: [ Transcript show: 'Bad status : ', (response status asString) ]
  ifTrue:  [ response contents regex: '((http\://)?www([./#+-]\w*)+)' matchesDo:
           [ :x | Transcript show: String cr, x ]]
]
    on: NameLookupFailure do: [ Transcript show: 'Connection problem...' ].

```

If you try to check me out you will get an exception. Something like `UTF8EncoderException: errorIllegalLeadingByte`. The first thing I thought that the package pretty outdated. But then realized that it downloads other sites well. Then I thought it is not always well copes with utf8. In debug received byte = 150 (1001 0110) - it's bad if it is the first byte in sequence. I spent a some time on the localization error (moved up in call stack and found parsed line). So:

> Lang.Next'14 Keynote: What � if anything � have we learned from C++? A 68 minute talk incl. Q&A.

You should see here squares or diamonds with question marks, depending on your browser. Trap from Stroustrup. At best, I had to write an exception handler in the package at the point where the line is created. But i just comment exception call and return `?` character.

Also in code which calc the sequence length I return 1 in place of exception call (seems browsers does same).

P.S. some notes about Pharo (if anyone interested):

* Too much GUI
* Frendly for beginners.
* Nice package searching
* Nice highlighting and code autocompletion (not nice enough for serios IDE like IDEA but better than what I saw a few years ago in the same Pharo). Autocompletion sometimes trying deduce type - very thankless job.
* Very chaotic GUI. At IDE we used to see tiled windows system, but there is only floating litle windows.
* Where is imports, namespaces? There are many entities already. Is never a collision occurs?

# Answer
> 4 votes
# Vimscript

```
function! Cpp()
    " grab the page in a new buffer in a new window in a new tab page
    tabedit http://www.stroustrup.com/C++.html

    " delete all lines that don't contain at least one 'http' hyperlink
    v/"http/d

    " only keep the hyperlink on every line
    %s/^.\+="\([^"]\+\)".\+$/\1
endfunction

```

# Answer
> 3 votes
**JS/jQuery**

```
$.get('http://www.stroustrup.com/C++.html',{},function(s){
    $(s).find('a').each(function() {
        console.log($(this).attr('href'))
    })
})

```

# Answer
> 3 votes
# Python 2

I don't like using regex on HTML for established reasons, so here's an ungolfed HTMLParser approach:

```
from HTMLParser import HTMLParser
import urllib2 as u

class LinkFinder(HTMLParser):
    def handle_starttag(self, tag, attrs):
        if tag=='a':
            attrdct = dict(attrs)  # attrs is a list of ('key', 'value') tuples
            if 'href' in attrdct:
                href = attrdct['href']
                print href

url = "http://www.stroustrup.com/C++.html"
contents = u.urlopen(url).read()
LinkFinder().feed(contents)

```

Note this also gives local links such as `index.html` and anchors à la `#learning`. If you only want absolute links, prepend `print href` by

```
                if ':/' in href:  # also handles ftp, https etc.
                    print href

```

while for only omitting the anchors, use

```
                if !href.startswith('#'):
                    print href

```

# Answer
> 3 votes
# Lua

Here's a lua solution complete with error checking and duplicate URL elimination like Stroustrups's C++ version.

Just made it in under 10 lines

```
local http, urlunique = require 'socket.http', {}

local body, resp, _, respmsg = http.request "http://www.stroustrup.com/C++.html"
assert(resp == 200, respmsg or resp)
for each in body:gmatch 'https?://[^%s<>"]+' do
  if not urlunique[each] then
    urlunique[each] = true
    print(each)
    end end

```

Here's another version using `string.gsub` fitting in just 6 lines!

```
local http, urlunique = require 'socket.http', {}

local body, resp, _, respmsg = http.request "http://www.stroustrup.com/C++.html"
assert(resp == 200, respmsg or resp)
body:gsub ('https?://[^%s<>"]+', function(r) urlunique[r] = true end)
for url in pairs(urlunique) do print(url) end

```

# Answer
> 3 votes
# VBScript in Windows Script Host

That is, if this is stored in `links.vbs` file, run it via `cscript /nologo links.vbs`.

```
sub writeline( s ): WScript.StdOut.WriteLine s : end sub
function re( s ): set re = new RegExp: re.pattern = s: re.global = true: end function

set http = createobject( "Msxml2.XMLHTTP" )
http.open "GET", "http://www.stroustrup.com/C++.html", false: http.send
set links = re( "\w+://[^\""]+" ).execute( http.responseText )
for each link in links: writeline( link ): next

```

---

**Addendum:**

While the above lists all full links, which seems to be the goal, Stroustrup’s code additionally pares it down to ***unique* links**, and here’s a version that does that:

```
sub writeline( s ): WScript.StdOut.WriteLine s : end sub
function re( s ): set re = new RegExp: re.pattern = s: re.global = true: end function

set http = createobject( "Msxml2.XMLHTTP" )
http.open "GET", "http://www.stroustrup.com/C++.html", false: http.send
set links = re( "\w+://[^\""]+" ).execute( http.responseText )

set unique_links = createobject( "Scripting.Dictionary" )
on error resume next
for each link in links: unique_links.add ucase(link), link & "": next
for each link in unique_links.items(): writeline( link ): next

```

This reduces the number of output lines from 81 to 77.

# Answer
> 3 votes
# **Rust**

Here is Rust solution:

```
extern crate reqwest;
extern crate select;
extern crate regex;

use select::document::Document;
use select::predicate::Name;
use regex::Regex;

fn main() {
    scrape_links("http://www.stroustrup.com/C++.html");
}

fn scrape_links(url: &str) {
    let resp = reqwest::get(url).unwrap();
    assert!(resp.status().is_success());
    let re = Regex::new(r"((http://)?www([./#\+-]\w*)+)").unwrap();
    Document::from_read(resp)
        .unwrap()
        .find(Name("a"))
        .filter_map(|n| n.attr("href"))
        .filter(|text| re.is_match(text))
        .for_each(|x| println!("{}", x));
}

```

# Answer
> 2 votes
# R

I'm super new to regex so I gave this my best shot... any improvements appreciated!

```
grep("(http)s?://.*?", readLines("http://www.stroustrup.com/C++.html"), value = T)

```

`readLines()` just dumps the HTML source into a character vector. I then used `grep()` to find the URLs. The problem I ran into was that HTML element tags as well as corresponding link text were included in the output. `substring()` could be used to trim some of them I guess but it wouldn't work in all cases. If anyone knows a better way please let me know - especially if I could use a better regex.

# Answer
> 2 votes
# Python 2.7

Some readable Python code.

```
import urllib2
import re
page = urllib2.urlopen("http://www.stroustrup.com/C++.html").read()
for link in re.findall('"(http[s]?://.*?)"', page):
    print link

```

# Answer
> 2 votes
# (C++)--

## *aka C*

I'm suprised no one has done C yet. The code is nice and clean.

linkfetch.c:

```
#include "inet_utils.h"
main(){
  char* SITE="www.stroustrup.com";
  char* PAGE="C++.html";
  char* REGX="((http://)?www([./#\\+-]\\w*)+)";
  int s = connect_to(SITE);
  FILE* f = fetch_page(s,SITE,PAGE);
  if (f) list_matches(f,REGX);
  else return printf("Can't fetch page %s/%s\n",SITE,PAGE);
  fclose(f); close(s);
}

```

That is, clean assuming you also write these simple utiliies:

inet\_utils.h

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <netdb.h>
#include <regex.h>

#define SZ 1024 //good default buffer size
#define ERROR(s) (puts(s)&&0)
#define VP(e) ((void*)(long)(e))

inline int connect_to(char* w){
  //:returns socket connected to website w.
  struct sockaddr_in a;
  int s=socket(AF_INET, SOCK_STREAM, 0);                       // make socket
  struct hostent* h = gethostbyname(w);                        // lookup host
  if (!h) return ERROR("No Such Host");                        // check err
  a.sin_family=AF_INET;                                        // set ip address
  a.sin_port=htons(80);                                        // port 80
  memcpy(&a.sin_addr.s_addr, h->h_addr, h->h_length);          // of host
  if (connect(s,(struct sockaddr*)&a,sizeof(a))<0)             // connect
    return ERROR("can't connect");                             // handle error
  return s;                                                    // return socket
}

inline FILE* fetch_page(int s, char*w, char* p){
  //:returns open file handle for page p from site w connected to socket s

  FILE*f=fopen("/tmp/wcache","w+");                   // create cache file
  size_t n; char*b=malloc(SZ);                        // allocate temp buffer
  if (!s||!f||!b) return VP(ERROR("Resource Error")); // check for errors
  sprintf(b,                                          // compose request
          "GET / HTTP/1.0\r\nHost:%s\r\nAccept:*/*\r\nConnection:close\r\n\r\n",
          w);
  send(s,b,strlen(b),0);                         // send request
  while ((n=recv(s,b,SZ,0))>0)                   // receive response
    fwrite(b,1,n,f);                             // write it to cache file
  fseek(f,n=0,SEEK_SET);                         // read from beginnng
  fgets(b,SZ,f);                                 // look at first line
  if (!f||strncmp(strtok(b," "),"HTTP/",5))      // is it http?
    return VP(ERROR("Invalid Response"));        // error if not
  if (atoi(strtok(0," "))!=200)                  // check good status code
    return VP(ERROR("Bad Status Code"));         // error if not
  while (getline(&b,&n,f)>=0 && *b!='\r');       // skip headers upto blank line
  free(b);                                       // cleanup
  return f;                                      // return open handle
}

inline void list_matches(FILE* f, char* regx){
  //prints all strings from f which match regx
  regex_t r;
  size_t n = SZ; char*b=malloc(n);               // temp buffer
  if (regcomp(&r,regx,REG_NOSUB|REG_EXTENDED))   // compile regex
    puts("invalid regex");                       // handle error
  else while (getline(&b,&n,f)>0)                // fetch line
         if (!regexec(&r,b,0,0,0))               // check match
           puts(b);                              // show match
  regfree(&r); free(b);                          // cleanup
}

```

It compiles without warnings on out-of-the-box gcc (version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5) )

# Answer
> 2 votes
# Swift (2.2)

> What? Please write the Swift version. That square bracket nonsense is hurting my eyes :)

Mister Smith on the Objective-C answer.

```
let x = try!NSString(contentsOfURL:NSURL(string:"http://www.stroustrup.com/C++.html")!,encoding:4)
for y in try!NSRegularExpression(pattern:"\"((http)s?://.*?)\"",options:[]).matchesInString(x as String,options:[],range:NSMakeRange(0,x.length)){print(x.substringWithRange(y.range))}

```

Ungolfed:

```
let url = NSURL(string: "http://www.stroustrup.com/C++.html")!
let html = try! NSString(contentsOfURL: url, encoding: NSUTF8StringEncoding)
let regex = try! NSRegularExpression(pattern: "\"((http)s?://.*?)\"", options: [])
let results = regex.matchesInString(html as String, options: [], range: NSMakeRange(0, html.length))
for result in results {
    print(html.substringWithRange(result.range))
}

```

Assumes Foundation has been implicitly imported.

I can't access the original page for some reason, so this was tested with the Google Cached version: http://webcache.googleusercontent.com/search?q=cache:USk4BseSofcJ:www.stroustrup.com/C%2B%2B.html+&cd=1&hl=en&ct=clnk&gl=us

282 bytes. Slightly shorter than the 292 byte Objective-C answer. I'm falling back onto Foundation APIs, so there may be room for improvement by using pure Swift types. The Cocoa APIs have also changed since the Objective-C answer was posted.

`stringWithContentsOfURL:` has been deprecated on `NSString` in favor of `stringWithContentsOfURL:encoding:error:`. We lose some bytes on the `encoding` parameter, but gain some back because the `ErrorPointer` is no longer passed in with Swift. The function now `throws` its `NSError` so instead, I'm using `try!` to force the execution of the `NSString` and `NSRegularExpression` initializers. I also save some bytes by passing the raw value `4` as the value of the `encoding` parameter instead of the constant `NSUTF8StringEncoding`. 19 bytes saved. But I lose some bytes by having to pass in an empty array (`[]`) instead of `0` to represent no options. 2 bytes lost there. I also lose two bytes for every variable declaration since Swift requires whitespace characters on either side of the `=` character.

I lose 10 bytes by having to cast the `NSString` as a Swift `String` when calling `matchesInString`. This is required because I'm using the `NSString` method `contentsOfURL` to get the web page HTML, but the `NSRegularExpression` method `matchesInString` takes in a Swift `String` as a parameter. The implicit conversion between `NSString` and `String` isn't available here, so I am forced to use `as` to explicitly convert the types.

Interestingly enough `matchesInString` has not been completely converted to use Swift types. It still requires its `range` parameter to be an `NSRange` struct instead of a Swift `Range<String>`. I have to fall back and use `NSMakeRange` to create the range of the string. I could save 4 bytes by using `x.characters.indices` of type `Range<String.CharacterView.Index>` instead, but Swift `Range` structs are not compatible with Foundation `NSRange` structs. Additionally, if `x` were a Swift `String`, I might be able to save a few bytes by replacing `substringWithRange` with a subscript on `String`. I haven't found a great way to do that yet, as creating two `Index` structs is currently longer than using `substringWithRange`.

# Answer
> 1 votes
# ColdFusion

(using the same regex that Stroustrup uses)

```
<cfhttp url="http://www.stroustrup.com/C++.html" result="response" />
<cfif response.statusCode does not contain "200">
    <cfset writeOutput("Error getting the page: #response.statusCode#") />
<cfelse>
    <cftry>
        <cfset htmlLinks = REMatchNoCase("((http://)?www([./#\+-]w*)+)",response.fileContent) />
        <cfdump var="#htmlLinks#" />
    <cfcatch>
        <cfset writeOutput("There was a problem: #cfcatch.message# #cfcatch.detail#") />
    </cfcatch>
    </cftry>
</cfelse>

```

# Answer
> 1 votes
# XQuery

HTML should be something similar to XML, so why not use langauges designed for this job?

If the page would've been "real" XHTML, we could run a query as beautiful as

```
doc("http://www.stroustrup.com/C++.html")//a/@href/data()

```

As this is crappy, broken HTML, let's use the BaseX-specific HTML parser (BaseX is an XQuery implementation):

```
html:parse(fetch:binary("http://www.stroustrup.com/C++.html"))//a/@href/data()

```

If limiting to URLs starting with `http:` is a must, lets do it:

```
html:parse(fetch:binary("http://www.stroustrup.com/C++.html"))//a/@href[starts-with(., 'http:')]/data()

```

*Disclaimer: I am somewhat affiliated with the BaseX team as I wrote some code during my thesis. This would've been the tool of my choice for that kind of task, anyway. Other XQuery implementations provide similar HTML parsing capabilities, but I don't know their XQuery extensions by heart.*

# Answer
> 1 votes
## Bash + AWK

```
wget -q -O http://www.stroustrup.com/C++.html \
|awk '/((http:\/\/)?www([./#\+-]\w*)+)/ {print gensub(/.*((http:\/\/)?www([./#\+-]\w*)+).*/,"\\1","g")}'

```

I know it probably misses a few URLs, but I chosen to use the same regex than the original Stroustrup's code, so this should returns the same output than the original piece of code.

It may be possible to add some CR to make it more visible but I don't have a Linux available ATM for testing it works... (tested on Windows)

Here is a "clean" version of the AWK part:

```
/((http:\/\/)?www([./#\+-]\w*)+)/ {
    print gensub(/.*((http:\/\/)?www([./#\+-]\w*)+).*/,"\\1","g")
}

```

# Answer
> 1 votes
# PHP 4.3+ / 5.0+

I know there are 2 different answers regarding PHP, but I'm going to show here a similar aproach, using nothing but standard functions.

For this, you will need to have the following on a file named `php.ini` ON THE SAME DIRECTORY:

```
allow_url_fopen= On
allow_url_include= On

```

THAT PART IS IMPORTANT!
In case you can't change (didn't worked with XAMPP), you have a default `php.ini` file on the PHP installation folder.
Changing the values will solve it.
Remember to restart apache after.

Since this isn't , I made my code somewhat readable.

Here it is:

```
ob_start(); //creates an output buffer

//now we 'include' the file, which will output the source code.
include 'http://www.stroustrup.com/C++.html';

$html = ob_get_clean(); //stores the output buffer and closes it

$offset = 0; //initial offset to search
$links = array(); //will contain all links

//while a link is found
while($pos = strpos($html, 'href="http', $offset))
{
    //look for the closing "
    $end = strpos($html, '"', $pos + 7);
    //take it from the string, store it into the array
    $links[] = substr($html, $pos + 6, ($end - $pos) - 6);
    //increase the offset, so it doesn't find the same link again
    $offset = $end + 1;
}

print_r($links); //spits it out, with the output buffer closed

```

I've added some comments to try to explain the code.

No regex used or DOM parsers: only pure hard-cold string manipulation.

For this to work in other pages, you must be sure that the values of the property `href` are between `""`, or it will fail.

# Answer
> 1 votes
# F#

```
do
  use client = new System.Net.WebClient()
  let html = client.DownloadString "http://www.stroustrup.com/C++.html"
  System.Text.RegularExpressions.Regex.Matches(html, @"https?://[^""]+")
  |> Seq.cast<System.Text.RegularExpressions.Match>
  |> Seq.iter (printfn "%O")

```

# Answer
> 0 votes
# CSS - idea

In Firefox, for example, for any page you are on, you can go to Tools | Web Developer | Style Editor, and use CSS to display anchors only:

```
* {display:none;}
a {display:block;}

```

However, the above *will not* work because `display` of parent elements overrides children.

Still working on a CSS solution, but suggestions welcome!

# Answer
> 0 votes
## C++/U++

Here is the U++ (which is 'another' C++ library, slightly different approach from boost) version:

```
#include <Core/Core.h>
#include <plugin/pcre/Pcre.h>

using namespace Upp;

CONSOLE_APP_MAIN
{
    String s = ToCharset(CHARSET_UTF8, HttpRequest("http://www.stroustrup.com/C++.html").Execute(),
                         CHARSET_ISO8859_1);
    RegExp x("href *= *\"(.*?)\"");
    while(x.GlobalMatch(s))
        Cout() << x.GetStrings()[0] << "\n";
}

```

(BTW, funny how most versions here are IMO not implementing the original specification: extract all links. There are many links on that page that do not start with http...)

# Answer
> 0 votes
# Lua

More concise, without checking for errors or unique URLs: In readable...

```
http = require 'socket.http'
page = http.request 'http://www.stroustrup.com/C++.html'
page:gsub('http://www[%w./#\\+-]+', print)

```

...and less-readable...

```
require'socket.http'.request'http://www.stroustrup.com/C++.html':gsub('http://www[%w./#\\+-]+',print)

```

# Answer
> 0 votes
# Javascript / DOM

```
var r = new XMLHttpRequest();
r.open('GET', 'http://www.stroustrup.com/C++.html', false);
r.send(null);
var div = document.createElement('div');
div.innerHTML = r.response;
[].slice.call(div.getElementsByTagName('a')).forEach( function(a) {
  if (a.href && a.getAttribute('href').charAt(0) != '#') console.log(a.href);
} );

```

(Tested in the Google Chrome javascript console.)

Of course, CORS blocks this by default - but its easy to disable CORS in Google Chrome for development purposes.

# Answer
> -1 votes
# Bash

```
 GET http://www.stroustrup.com/C++.html | grep -o "https\?://[^ \"]\+

```

needs libwww-perl and grep packages :)

---
Tags: popularity-contest, parsing, regular-expression, internet
---


title: Is it a Rubik's Cube?

text:
# Question
Title: Is it a Rubik's Cube?
A venerated pass time of pedants is to point out that pictures of "Rubik's Cubes" (on t-shirts, posters etc.) are not actually solvable.

The first thing that should be checked is that the cube is made up of the right pieces. To be solvable a cube needs six colors each with nine squares. The cube also needs each edge and corner unit (these are the smaller cubes that make up the cube) to be unique. Not only must they be unique but if two center pieces are opposite each other no edge or corner piece can contain both of those colors.

Once you have a cube that is made up of all the right pieces you still need to verify it can be solvable. There are a couple of rules here, so I'll defer to an expert to explain them, the spoiler below explains how we can do this. If you are interested in solving the problem on your own you don't need to visit the site to understand or participate in this challenge.

> Linked explanation

Your task is to take a pattern as input and determine if it is in fact a solvable Rubik's cube. To be solvable there must be a way to perform valid moves on a cube so that the cube has only one color on each face (and the different faces have different colors). Most Rubik's cubes have a standard coloring (White is opposite Yellow, etc.) you may not assume that the solve state follows this particular coloring.

A valid move is either the clockwise or anti-clockwise rotation of a single face of the cube. With the rotation of the face of the cube any squares bordering the face are rotated as well, staying connected to the face they were previously touching.

# IO

You may take the cube in any reasonable manner. If your language has some builtin "cube-face" type, good for you, that is fine as input, other wise you can take a 2D array of the net, of the cube, 1 3 by 3 lists for each face. Just be reasonable. If you want to know if a specific format is acceptable comment or ping me in chat and I will add to the challenge to state its validity.

Your input format need only support up to 9 possible colors.

For output this is a decision problem so you should output one constant value for "Yes, this is a valid Rubik's cube" and one different constant value for "No, this is not a valid Rubiks cube".

---

This is so answers will be scored in bytes with less bytes being better.

# Test Cases

Here are test cases. They are formatted as the net of a cube with each square as a single letter. Different letters represent different colors. Any more testcases can be added upon request.

## Solvable

```
   RRR
   RRR
   RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
   YYY
   YYY
   YYY

   GRR
   GRR
   ORW
WWRBWYBOOGGY
GGRBWGYBBOOO
OOGRWGYWWRBB
   WYO
   YYB
   YYB

```

## Unsolvable

```
   RRR
   RRR
   RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWYWBBBOOO
   YWY
   YYY
   YYY

   RRR
   RRR
   RRR
GGGWWWBBBOOO
GGGWWWBBBOOO
GGGWWWBBBOOO
   YWY
   YYY
   YYY

   RRR
   RRR
   GGG
GGYWYWRBBOBO
GGYWWWROBOOO
GGYWWWRBBOOO
   BBB
   YWY
   YYY

   RRW
   RRW
   GGG
GGYWWYEOBROO
GGYWWYEBBROO
GGOWWYWBBROO
   BBB
   YYW
   YYO

```

# Answer
# Cubically, ~~1664~~ ~~1631~~ 1089 bytes

```
⇒FD2F'R'D2RUR'D2RFD2F'U'
⇒Ff1F'
⇒LFf1F'L'
⇒F'f1F
⇒F2f1F2
⇒L'F2f1F2L
⇒D'F'f1FD
⇒LR'FLR'DLR'B2L'RDL'RFL'RU2
⇒LFf8F'L'
⇒R'F'f8FR
⇒Ff8F'
⇒F'f8F
⇒ULU'f8UL'U'
⇒U'R'Uf8U'RU
⇒F2f8F2
⇒Df15D'
⇒D'f15D
⇒D2f15D2
⇒UF2UF2D'L2B2U'B2DL2F2D2B2D2F2
⇒U'DL2UD'B2
⇒UF2UF2D'L2B2D'R2UR2F2D2B2U2B2
⇒BL'BU2D2F'RF'U2D2
⇒LD'F2U'B2U'RU2R'F2R2F2D'R2DF2D
⇒B2URB2D2B2RB2U'D'L2D'B2
⇒B2LF'U'B2UFL'R2B2U'D2L2D'B2U
⇒B2RB2D2B2RB2U'L2UD'F2U'F2B2
⇒D2R'FUB2U'F'RU2B2D'F2R2UF2UF2
⇒B2R2U'L'D2B2U2R'U2R2F2L2R2UR2
⇒D2L'B2U2F2RUL2U'F2R2U'R2U2F2DL2D'
⇒UB2U'L2DL2B2DB2D'B2
⇒BR'BL2B'RBL2B2
⇒UF2B2U'F2B2U'F2L2R2B2R2
⇒R2U'F2DR2UF2D'R2DF2R2D'F2
⇒U'F2DF2UL2F2DL2DF2L2D2F2
⇒U2D'L2U'F2L2U'B2L2R2U'L2B2
⇒F2D'R2U2L2B2UF2L2U2F2L2UF2R2
⇒[f1]3
⇒[f2f37]3
⇒[f3f38]3
⇒[f4f39]3
⇒[f5f40]3
⇒[f6f41]3
⇒[f7f42]3
⇒[f8f43]2
⇒[f9f44]2
⇒[f10f45]2
⇒[f11f46]2
⇒[f12f47]2
⇒[f13f48]2
⇒[f14f49]2
⇒[f15f50]2
⇒[f16f51]2
⇒[f17f52]2
⇒[f18f53]2
⇒[f19f54]2
⇒[f20f55]3
⇒[f21f56]4
⇒[f22f57]5
⇒[f23f58]6
⇒[f24f59]7
⇒[f25f60]8
⇒[f26f61]9
⇒[f27f62]9[f27f62]2
⇒[f28f63]9[f28f63]3
⇒[f29f64]9[f29f64]4
⇒[f30f65]2
⇒[f31f66]3
⇒[f32f67]4
⇒[f33f68]5
⇒[f34f69]6
⇒[f35f70]7
rs[f36f71]8

```

**Output if solvable: `Solved!`**
**Output if unsolvable: (empty, no output)**

Input should be formatted as a Cubically cube-dump (see the `Debug` section). This was explicitly allowed by the OP.

# Explanation

This program takes the approach of using a Devil's Algorithm to iterate over every possible state of the cube in the same group as the solved cube. If the cube is solvable, it will be solved at some point before the algorithm has finished (assuming the algorithm I used works properly).

Every line beginning with  (0x84 in Cubically's codepage) is a function definition; these functions build off of each other to make up the actual Devil's Algorithm. The first line to be executed is the last one:

```
rs[f36f71]8

```

`r` reads a cube from stdin and sets the memory cube to it. `s` puts the interpreter into "solvemode", which means that it exits and prints `Solved!` if the cube becomes solved (after being unsolved) at any point. The rest of the commands (which simply repeat `f36f71` 8 times) correspond to the final algorithm at the bottom of the linked page:

```
(D) = (CP) = (CPT8) = [(CPC8)(CPT7)]8 (3,847,762,288,469,010,006,992 moves)

(D) is the Devil's Algorithm. If you apply it to the cube, it will be solved at some point before you have done the algorithm once. As you can see, it is terribly long, nearly a thousand times more moves than there are possible positions.

```

# How can I run it?

You can try it online, but that link doesn't work. TIO will almost definitely time out before this algorithm finishes (the maximum runtime for an interpreter is 60 seconds). If the cube is not solvable, this algorithm will take up to 11 million years for Cubically to finish (at ~15.2 million moves per second, which is what my Cloud9 IDE gets).

~~Additionally, you need a *lot* of memory to perform 3 sextillion moves. Cubically can perform about 4 million moves per second, but the process will most likely be killed due to overcommitted memory. It dies after 15 seconds on my VM with 512MB of memory.~~ Why should performing moves on an already-allocated flat array cost memory? Found a memory leak (or twenty) and fixed it.

Here is a much more readable version that behaves the same way.

### But I really want to see that it works!

The first actual move that is executed in this devil's algorithm is `F2`, so the quickest cube to solve would be one scrambled with `F2`:

```
   000
   000
   555
113222133444
113222133444
113222133444
   000
   555
   555

```

This indeed executes in 0.007 seconds on TIO.

# How can this be improved?

There are certainly more devil's algorithms; I've found one that uses less than a thirtieth of the moves this one does. However, that would come at the cost of several thousand bytes (around 100MB more) and several dozen hours of converting a complex Hamiltonian circuit to Cubically code.

It's also possible to remove some of the functions and put them straight in the loop at the bottom. However, I'm going to sacrifice some bytes for some readability.

Additionally, I'm considering a modification of Cubically's looping behavior so that I can more easily repeat algorithms 7 or 8 times (instead of just hard-coding them with the function calls repeated 7 or 8 times in the source). Or I'll work some magic out with the notepad, and golf this using more loops.

Note that I will continue to optimize anything possible in the interpreter, so this may work on an average PC sometime in the future!

---

# Cubically, 2 bytes

```
r▦

```

I like the above answer better so I'm adding this as an alternate solution. This runs in under a second, as opposed to a few million years.

```
r    read cube from standard in
 ▦   and solve it

```

**Output if the cube is solvable:** (nothing)
**Output if the cube is unsolvable:** `Error: The cube has reached an unsolvable state.`
> 15 votes

# Answer
# APL (Dyalog Classic), ~~190~~ 174 bytes

```
{∧/~∊(×1 2 3|+.-⌿↑⊃∘⍋¨¨¨a)({2|≢∪{⍵⌊⍵[⍵]}⍣≡⍵,0}¨⍳⌿↑⌽b)((∪≢∩)¨/b←(⊃∘⍋⌽⊢)¨¨¨a),6≢≢∪⊃⊃a←{c←4⍴⊂⍬⋄c[+/1≠i],←(≠/×i←↑⍳3⍴3){⊂⌽⍣⍺⊢⍵~' '}¨,⌿(3|∘.+⍨⍳3)⍉⍤¯1↑1 0 1\⍵⋄1↓c}¨⍵(3 3∘⍴¨1 1∘⌷¨⍵)}

```

Try it online!

The argument is a 3x2 matrix (row0: front back, row1: left right, row2: up down) of 3x3 character matrices. Returns 1 for a solvable Rubik's cube, 0 otherwise.

In the TIO link, function `t`, which is not included in the character count, reads 9 lines of input, converts them from the default input format (a net) to the required 3x2 x 3x3 matrix, calls the solution and prints OK if the result is as expected.

The algorithm splits the given cube into 26 cubies - strings of length 3 (corners), 2 (edges), and 1 (centres). It also generates the 26 cubies of a solved cube with the same 6 central cubies. All of the following criteria must be met:

* there are no duplicates among the 6 centres
* the sets of given/solved cubies match, up to rotation - e.g. consider `'WBR'` and `'BRW'` the same cubie, but not `'BWR'`
* the parities of both the corner permutation and the edge permutation are even
* the modulo-3 sum of corner rotation indices (e.g. taking the "smallest" letter `B` as a reference point we have: `'BRW'→0`, `'WBR'→1`, `'RWB'→2`) match between the given and solved cubes; same for the corners modulo 2
> 6 votes

---
Tags: code-golf, decision-problem, geometry, rubiks-cube
---


# Question
Title: Minimise the count of prime factors through insertion
Given two positive integers **A** and **B**, return the position **p** that *minimises* the number of prime factors (counting multiplicities) of the resulting integer, when **B** is *inserted* in **A** at **p**.

For example, given **A = 1234** and **B = 32**, these are the possible insertions (with **p** being 0-indexed) and the corresponding information about their prime factors:

```
p | Result | Prime factors         | Ω(N) / Count

0 | 321234 | [2, 3, 37, 1447]      | 4
1 | 132234 | [2, 3, 22039]         | 3
2 | 123234 | [2, 3, 19, 23, 47]    | 5
3 | 123324 | [2, 2, 3, 43, 239]    | 5
4 | 123432 | [2, 2, 2, 3, 37, 139] | 6

```

You can see that the result has a minimal number of prime factors, 3, when **p** is 1. So in this particular case, you should output **1**.

### Specs

* If there are multiple positions **p** that minimise the result, you can choose to output all of them or any one of them.
* You may choose 0-indexing or 1-indexing for **p**, but this choice must be consistent.
* **A** and **B** can be taken as integers, strings or lists of digits.
* You can compete in any programming language and can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default. This is code-golf, so the shortest submission (scored in bytes) wins!

### Test cases

```
A, B -> p (0-indexed) / p (1-indexed)

1234, 32           -> 1 / 2
3456, 3            -> 4 / 5
378, 1824          -> 0 / 1
1824, 378          -> 4 / 5
67, 267            -> Any or all among: [1, 2] / [2, 3]
435, 1             -> Any or all among: [1, 2, 3] / [2, 3, 4]
378100, 1878980901 -> Any or all among: [5, 6] / [6, 7]

```

For convenience, here is a list of tuples representing each pair of inputs:

```
[(1234, 32), (3456, 3), (378, 1824), (1824, 378), (67, 267), (435, 1), (378100, 1878980901)]

```

# Answer
> 8 votes
# Husk, 16 bytes

```
§◄öLpr§·++⁰↑↓oΘŀ

```

Expects input as strings, try it online!

### Explanation

```
§◄(öLpr§·++⁰↑↓)(Θŀ)  -- input A implicit, B as ⁰ (example "1234" and "32")
§ (           )(  )  -- apply A to the two functions and ..
  (ö          )      --   | "suppose we have an argument N" (eg. 2)
  (    §      )      --   | fork A and ..
  (         ↑ )      --     | take N: "12"
  (          ↓)      --     | drop N: "34"
  (     ·++⁰  )      --   | .. join the result by B: "123234"
  (   r       )      --   | read: 123234
  (  p        )      --   | prime factors: [2,3,19,23,47]
  ( L         )      --   | length: 5
  (öLpr§·++⁰↑↓)      --   : function taking N and returning number of factors
                            in the constructed number
               ( ŀ)  --   | range [1..length A]
               (Θ )  --   | prepend 0
               (Θŀ)  --   : [0,1,2,3,4]
 ◄                   -- .. using the generated function find the min over range

```

# Answer
> 7 votes
# MATL, 25 bytes

```
sh"2GX@q:&)1GwhhUYfn]v&X<

```

Inputs are strings in reverse order. Output is 1-based. If there is a tie the lowest position is output.

Try it online! Or verify all test cases.

### Explanation

```
s         % Implicitly input B as a string. Sum (of code points). Gives a number
h         % Implicitly input A as a string. Concatenate. Gives a string of length
          % N+1, where N is the length of A
"         % For each (that is, do N+1 times)
  2G      %   Push second input
  X@      %   Push 1-based iteration index
  q       %   Subtract 1
  :       %   Range from 1 to that. Gives [] in the first iteration, [1] in
          %   the second, ..., [1 2 ... N] in the last
  &)      %   Two-output indexing. Gives a substring with the selected elements,
          %   and then a substring with the remaining elements
  1G      %   Push first input
  whh     %   Swap and concatenate twice. This builds the string with B inserted
          %   in A at position given by the iteration index minus 1
  U       %   Convert to string
  Yf      %   Prime factors
  n       %   Number of elements
]         % End
v         % Concatenate stack vertically
&X<       % 1-based index of minimum. Implicitly display

```

# Answer
> 6 votes
# Pyth, ~~20~~ ~~13~~ 11 bytes

```
.mlPsXbQzhl

```

Try it online

### Explanation

```
.mlPsXbQzhl
.m    b         Find the minimum value...
         hl     ... over the indices [0, ..., len(first input)]...
  lP            ... of the number of prime factors...
    sX Qz       ... of the second input inserted into the first.

```

# Answer
> 3 votes
# Jelly, 21 bytes

```
D©L‘Ṭœṗ¥€®żF¥€VÆfL€NM

```

Try it online!

-1 thanks to Mr. Xcoder.

Returns all possible positions.

# Answer
> 3 votes
# Japt, ~~22~~ 21 bytes

This felt far too long as I was writing it up but, looking at some of the other solutions, it actually seems somewhat competitive. Still, there's probably a bit of room for improvement - The `cNq)` in particular is annoying me. Explanation to follow.

Takes the first input as a string and the second as either an integer or a string. Result is 0-indexed and will return the first index if there are multiple solutions.

```
ÊÆiYVÃcNq)®°k Ê
b@e¨X

```

Try it

---

## Explanation

```
      :Implicit input of string U and integer V.
Ê     :Get the length of U.
Æ     :Generate an array of the range [0,length) and map over each element returning ...
iYV   :  U with V inserted at index Y.
Ã     :End mapping
c     :Append ...
Nq    :  The array of inputs joined to a string.
®     :Map over the array.
°     :Postfix increment - casts the current element to an integer.
k     :Get the prime divisors.
Ê     :Get the length.
\n    :The newline allows the array above to be assigned to variable U.
b     :Get the first index in U that returns true ...
@     :  when passed through a function that ...
e     :    checks that every element in U...
¨     :    is greater than or equal to...
X     :    the current element.
      : Implicit output of resulting integer.

```

# Answer
> 2 votes
# PowerShell, 228 bytes

```
param($a,$b)function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}
$p=@{};,"$b$a"+(0..($x=$a.length-2)|%{-join($a[0..$_++]+$b+$a[$_..($x+1)])})+"$a$b"|%{$p[$i++]=(f $_).count};($p.GetEnumerator()|sort value)[0].Name

```

Try it online!

*(Seems long / golfing suggestions welcome. Also times out on TIO for the last test case, but the algorithm should work for that case without issue.)*

PowerShell doesn't have any prime factorization built-ins, so this borrows code from my answer on Prime Factors Buddies. That's the first line's `function` declaration.

We take input `$a,$b` and then set `$p` to be an empty hashtable. Next we take the string `$b$a`, turn it into a singleton array with the comma-operator `,`, and array-concatenate that with *stuff*. The *stuff* is a loop through `$a`, inserting `$b` at every point, finally array-concatenated with `$a$b`.

At this point, we have an array of `$b` inserted at every point in `$a`. We then send that array through a for loop `|%{...}`. Each iteration, we insert into our hashtable at position `$i++` the `.count` of how many prime factors `f` that particular element `$_` has.

Finally, we `sort` the hashtable based on `value`s, take the `0`th one thereof, and select its `Name` (i.e., the `$i` of the index). That's left on the pipeline and output is implicit.

# Answer
> 2 votes
# 05AB1E, ~~27~~ 21 bytes

```
ηõ¸ì¹.sRõ¸«)øεIýÒg}Wk

```

Try it online!

It returns the lowest 0-indexed *p*.

Thanks to @Emigna for -6 bytes !

### Explanation

```
ηõ¸ì                  # Push the prefixes of A with a leading empty string -- [, 1, 12, 123, 1234]
    ¹.sRõ¸«)          # Push the suffixes of A with a tailing empty space. -- [1234, 123, 12, 1, ]
            ø         # Zip the prefixes and suffixes
             ε    }   # Map each pair with...
              IýÒg    # Push B, join prefix - B - suffix, map with number of primes
                   Wk # Push the index of the minimum p

```

# Answer
> 2 votes
# 05AB1E, 18 bytes

```
gƒ¹õ«N¹g‚£IýÒg})Wk

```

Try it online!

# Answer
> 1 votes
# Python 2, ~~165~~ 146 bytes

```
O=lambda n:n>1and-~O(n/min(d for d in range(2,n+1)if n%d<1))
def f(A,B):L=[int(A[:j]+B+A[j:])for j in range(len(A)+1)];print L.index(min(L,key=O))

```

Try it online!

# Answer
> 1 votes
# Clean, ~~165~~ ... 154 bytes

```
import StdEnv,StdLib
@n h#d=hd[i\\i<-[2..h]|h rem i<1]
|d<h= @(n+1)(h/d)=n
?a b=snd(hd(sort[(@0(toInt(a%(0,i-1)+++b+++a%(i,size a))),i)\\i<-[0..size a]]))

```

Try it online!

# Answer
> 0 votes
# Jelly, 16 bytes

```
;ṭJœṖ€$j€¥VÆfẈNM

```

Try it online!

Takes `A` as a list of digits and returns all 1-indices

## How it works

```
;ṭJœṖ€$j€¥VÆfẈNM - Main link. Takes A on the left and B on the right
;                - Concatenate B to the end of A
         ¥       - Group the previous 2 links into a dyad f(A, B):
      $          -   Group the previous 2 links into a monad g(A):
  J              -     Indices of A; [1, 2, ..., len(A)]
     €           -     Over each index:
   œṖ            -       Partition A at that index
        €        -   Over each partition:
       j         -     Join with B
 ṭ               - Append the concatenated number to the end of this list
          V      - Evaluate each as a number
           Æf    - Calculate the prime factors of each
             ẈN  - Get the lengths of each and negate
               M - Indices of maximal elements, which gives the minimal indices when negated

```

# Answer
> 0 votes
# JavaScript (ES6), 120 bytes

Takes input as 2 strings. Returns a 0-indexed position.

```
f=(a,b,i=0,m=a)=>a[i>>1]?f(a,b,i+1,eval('for(n=a.slice(0,i)+b+a.slice(i),x=k=2;k<n;n%k?k++:n/=x++&&k);x')<m?(r=i,x):m):r

```

### Test cases

```
f=(a,b,i=0,m=a)=>a[i>>1]?f(a,b,i+1,eval('for(n=a.slice(0,i)+b+a.slice(i),x=k=2;k<n;n%k?k++:n/=x++&&k);x')<m?(r=i,x):m):r

console.log(f('1234','32'))   // 1
console.log(f('3456','3'))    // 4
console.log(f('378','1824'))  // 0
console.log(f('1824','378'))  // 4
console.log(f('67','267'))    // 1
console.log(f('435','1'))     // 1
```

# Answer
> 0 votes
# Python 3, 128 bytes

0-indexed; takes in strings as parameters. -6 bytes thanks to Jonathan Frech.

```
from sympy.ntheory import*
def f(n,m):a=[sum(factorint(int(n[:i]+m+n[i:])).values())for i in range(len(n)+1)];return a.index(min(a))

```

# Answer
> 0 votes
# J, 60 Bytes

```
4 :'(i.<./)#@q:>".@(,(":y)&,)&.>/"1({.;}.)&(":x)"0 i.>:#":x'

```

Explicit dyad. Takes B on the right, A on the left.

0-indexed output.

Might be possible to improve by not using boxes.

### Explanation:

```
  4 :'(i.<./)#@q:>".@(,(":x)&,)&.>/"1({.;}.)&(":y)"0 i.>:#":y'  | Whole program
  4 :'                                                       '  | Define an explicit dyad
                                                     i.>:#":y   | Integers from 0 to length of y
                                                  "0            | To each element
                                     ({.;}.)&(":y)              | Split y at the given index (result is boxed)
                     (,(":x)&,)&.>/"1                           | Put x inbetween, as a string
                  ".@                                           | Evaluate
                 >                                              | Unbox, makes list
             #@q:                                               | Number of prime factors of each
      (i.>./)                                                   | Index of the minimum

```

# Answer
> 0 votes
**Python, 122 bytes**

```
f=lambda n,i=2:n>1and(n%i and f(n,i+1)or 1+f(n/i,i))
g=lambda A,B:min(range(len(A)+1),key=lambda p:f(int(A[:p]+B+A[p:])))

```

In practice, this exceeds the default max recursion depth pretty quickly.

---
Tags: code-golf, number-theory, primes, integer
---


title: Loop It

text:
# Question
Title: Loop It
> Note: The title of this question should be "Loop It", but because title needs to be at least 15 characters, there are some invisible spaces. This note is such that the challenge can be searched for.

---

### Challenge

Given a finite list of unique integral points in the plane, find a polygon whose vertices are exactly those points, which does not self intersect.

### Details

* As input you can take e.g. two lists with each the x- and y-coordinates or a list of pairs.
* The input list contains at least 3 points.
* Note that this means there is never a unique solution.
* The list of inputs is can be assumed to be not co-linear (the points cannot be contained in one line), this means there actually is such a non-self-intersecting polygon.
* The angles at each vertex is arbitrary, this includes 180°.
* For an input of length `n`, the output should be a permutation `(p1,p2,p3,...,pn)` of `(1,2,3,...,n)` where the `k`-th entry `pk` represents the `p`-th point in the input list. This means we have a line from `p1` to `p2`, a line from `p2` to `p3` etc, as well as a line from `pn` to `p1`. (You can also use the 0-based indices.) **Alternatively** you can just output the list of input points in the right order.

### Examples

Let's say we have the points `[(0,0),(0,1),(1,0),(-1,0),(0,-1)]` and we want to represent following path:

This means we would output the list `[5,1,4,2,3]`

Here some more suggestion to try (I recommend looking at the corresponding plots to verify the goals.)

```
Triangle
[(0,0),(0,1),(1,0)]

S-Curve
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(2,0),(2,1),(2,2),(2,3),(2,4),(3,4),(4,0),(4,1),(4,2),(4,3),(4,4)]

L-Shape
[(4,0),(1,0),(3,0),(0,0),(2,0),(0,1)]

Menger Sponge
[(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(9,1),(10,1),(11,1),(12,1),(13,1),(14,1),(15,1),(16,1),(17,1),(18,1),(19,1),(20,1),(21,1),(22,1),(23,1),(24,1),(25,1),(26,1),(27,1),(1,2),(3,2),(4,2),(6,2),(7,2),(9,2),(10,2),(12,2),(13,2),(15,2),(16,2),(18,2),(19,2),(21,2),(22,2),(24,2),(25,2),(27,2),(1,3),(2,3),(3,3),(4,3),(5,3),(6,3),(7,3),(8,3),(9,3),(10,3),(11,3),(12,3),(13,3),(14,3),(15,3),(16,3),(17,3),(18,3),(19,3),(20,3),(21,3),(22,3),(23,3),(24,3),(25,3),(26,3),(27,3),(1,4),(2,4),(3,4),(7,4),(8,4),(9,4),(10,4),(11,4),(12,4),(16,4),(17,4),(18,4),(19,4),(20,4),(21,4),(25,4),(26,4),(27,4),(1,5),(3,5),(7,5),(9,5),(10,5),(12,5),(16,5),(18,5),(19,5),(21,5),(25,5),(27,5),(1,6),(2,6),(3,6),(7,6),(8,6),(9,6),(10,6),(11,6),(12,6),(16,6),(17,6),(18,6),(19,6),(20,6),(21,6),(25,6),(26,6),(27,6),(1,7),(2,7),(3,7),(4,7),(5,7),(6,7),(7,7),(8,7),(9,7),(10,7),(11,7),(12,7),(13,7),(14,7),(15,7),(16,7),(17,7),(18,7),(19,7),(20,7),(21,7),(22,7),(23,7),(24,7),(25,7),(26,7),(27,7),(1,8),(3,8),(4,8),(6,8),(7,8),(9,8),(10,8),(12,8),(13,8),(15,8),(16,8),(18,8),(19,8),(21,8),(22,8),(24,8),(25,8),(27,8),(1,9),(2,9),(3,9),(4,9),(5,9),(6,9),(7,9),(8,9),(9,9),(10,9),(11,9),(12,9),(13,9),(14,9),(15,9),(16,9),(17,9),(18,9),(19,9),(20,9),(21,9),(22,9),(23,9),(24,9),(25,9),(26,9),(27,9),(1,10),(2,10),(3,10),(4,10),(5,10),(6,10),(7,10),(8,10),(9,10),(19,10),(20,10),(21,10),(22,10),(23,10),(24,10),(25,10),(26,10),(27,10),(1,11),(3,11),(4,11),(6,11),(7,11),(9,11),(19,11),(21,11),(22,11),(24,11),(25,11),(27,11),(1,12),(2,12),(3,12),(4,12),(5,12),(6,12),(7,12),(8,12),(9,12),(19,12),(20,12),(21,12),(22,12),(23,12),(24,12),(25,12),(26,12),(27,12),(1,13),(2,13),(3,13),(7,13),(8,13),(9,13),(19,13),(20,13),(21,13),(25,13),(26,13),(27,13),(1,14),(3,14),(7,14),(9,14),(19,14),(21,14),(25,14),(27,14),(1,15),(2,15),(3,15),(7,15),(8,15),(9,15),(19,15),(20,15),(21,15),(25,15),(26,15),(27,15),(1,16),(2,16),(3,16),(4,16),(5,16),(6,16),(7,16),(8,16),(9,16),(19,16),(20,16),(21,16),(22,16),(23,16),(24,16),(25,16),(26,16),(27,16),(1,17),(3,17),(4,17),(6,17),(7,17),(9,17),(19,17),(21,17),(22,17),(24,17),(25,17),(27,17),(1,18),(2,18),(3,18),(4,18),(5,18),(6,18),(7,18),(8,18),(9,18),(19,18),(20,18),(21,18),(22,18),(23,18),(24,18),(25,18),(26,18),(27,18),(1,19),(2,19),(3,19),(4,19),(5,19),(6,19),(7,19),(8,19),(9,19),(10,19),(11,19),(12,19),(13,19),(14,19),(15,19),(16,19),(17,19),(18,19),(19,19),(20,19),(21,19),(22,19),(23,19),(24,19),(25,19),(26,19),(27,19),(1,20),(3,20),(4,20),(6,20),(7,20),(9,20),(10,20),(12,20),(13,20),(15,20),(16,20),(18,20),(19,20),(21,20),(22,20),(24,20),(25,20),(27,20),(1,21),(2,21),(3,21),(4,21),(5,21),(6,21),(7,21),(8,21),(9,21),(10,21),(11,21),(12,21),(13,21),(14,21),(15,21),(16,21),(17,21),(18,21),(19,21),(20,21),(21,21),(22,21),(23,21),(24,21),(25,21),(26,21),(27,21),(1,22),(2,22),(3,22),(7,22),(8,22),(9,22),(10,22),(11,22),(12,22),(16,22),(17,22),(18,22),(19,22),(20,22),(21,22),(25,22),(26,22),(27,22),(1,23),(3,23),(7,23),(9,23),(10,23),(12,23),(16,23),(18,23),(19,23),(21,23),(25,23),(27,23),(1,24),(2,24),(3,24),(7,24),(8,24),(9,24),(10,24),(11,24),(12,24),(16,24),(17,24),(18,24),(19,24),(20,24),(21,24),(25,24),(26,24),(27,24),(1,25),(2,25),(3,25),(4,25),(5,25),(6,25),(7,25),(8,25),(9,25),(10,25),(11,25),(12,25),(13,25),(14,25),(15,25),(16,25),(17,25),(18,25),(19,25),(20,25),(21,25),(22,25),(23,25),(24,25),(25,25),(26,25),(27,25),(1,26),(3,26),(4,26),(6,26),(7,26),(9,26),(10,26),(12,26),(13,26),(15,26),(16,26),(18,26),(19,26),(21,26),(22,26),(24,26),(25,26),(27,26),(1,27),(2,27),(3,27),(4,27),(5,27),(6,27),(7,27),(8,27),(9,27),(10,27),(11,27),(12,27),(13,27),(14,27),(15,27),(16,27),(17,27),(18,27),(19,27),(20,27),(21,27),(22,27),(23,27),(24,27),(25,27),(26,27),(27,27)]

```

# Answer
## Mathematica ~~29~~ 28 Bytes

`FindShortestTour` (16 Bytes) does the trick but delivers some extraneous info not asked for (the path length, and a return to the starting point).

```
Most@*Last@*FindShortestTour

```

gives just the answer ( -1 byte thanks to @user202729 )

To visualize, use `Graphics@Line[g[[%]]]`, where `%` is the permutation found above and g is the original point list.

Here is the visualization of the solution for the Menger Sponge:

Here is a solution on a 1000 random points:

The key here is knowing that the shortest tour or traveling salesman problem solution will never yield intersections when Euclidean distance is used as the metric. One of the steps to localize a solution and ensure optimality is to remove such intersections.
> 10 votes

# Answer
# JavaScript (ES6), ~~365~~ 341 bytes

Without any built-in, this turned out to be much longer than I expected. Many bytes are spent detecting collinear overlapping segments.

Takes input as an array of `[x,y]` coordinates. Returns a permutation of the input.

```
f=(a,p=[],o=([p,P],[q,Q],[r,R])=>Math.sign((S=[(p>q?r<q|r>p:r<p|r>q)|(P>Q?R<Q|R>P:R<P|R>Q),...S],Q-P)*(r-q)-(q-p)*(R-Q)))=>[...p,p[0]].some((A,i,P)=>P.some((C,j)=>j>i+1&&P[++j+!i]&&[E=o(A,B=P[i+1],C,S=[]),F=o(A,B,D=P[j]),G=o(C,D,A),H=o(C,D,B)].some(v=>!v&!S.pop())|E!=F&G!=H))?0:a[0]?a.some((_,i)=>r=f(b=[...a],p.concat(b.splice(i,1))))&&r:p

```

### Demo

This snippet logs the output and draws the corresponding path in a canvas.

```
f=(a,p=[],o=([p,P],[q,Q],[r,R])=>Math.sign((S=[(p>q?r<q|r>p:r<p|r>q)|(P>Q?R<Q|R>P:R<P|R>Q),...S],Q-P)*(r-q)-(q-p)*(R-Q)))=>[...p,p[0]].some((A,i,P)=>P.some((C,j)=>j>i+1&&P[++j+!i]&&[E=o(A,B=P[i+1],C,S=[]),F=o(A,B,D=P[j]),G=o(C,D,A),H=o(C,D,B)].some(v=>!v&!S.pop())|E!=F&G!=H))?0:a[0]?a.some((_,i)=>r=f(b=[...a],p.concat(b.splice(i,1))))&&r:p

draw(f([[0,0],[0,1],[1,0]]), 1, 1)
draw(f([[0,0],[0,1],[1,0],[-1,0],[0,-1]]), 61, 21)
draw(f([[4,0],[1,0],[3,0],[0,0],[2,0],[0,1]]), 101, 1)

function draw(a, dx, dy) {
  console.log(JSON.stringify(a));

  ctx = C.getContext('2d');
  ctx.beginPath();
  [...a, a[0]].forEach(p => ctx.lineTo(p[0] * 20 + dx, p[1] * 20 + dy));
  ctx.stroke();
}
```

```
<canvas id=C></canvas>
```

### How?

Here is the structure of the main recursive function **f()**, leaving aside the intersection testing code for now:

```
f = (a, p = []) =>                    // a = array of points, p = current path
  [...p,                              // build a closed path array P[] by adding the first
         p[0]]                        // point at the end of p[]
  .some((A, i, P) =>                  // for each point A at position i in P:
    P.some((C, j) =>                  //   for each point C at position j in P:
      j > i + 1 &&                    //     test whether C is at least 2 positions after A
      P[++j +                         //     and C is not the last point
              !i] &&                  //     and i > 0 or C is not the penultimate point
      intersection(                   //     and there's an intersection between
        A, P[i + 1], C, P[j]          //     the segments (A, P[i + 1]) and (C, P[j + 1])
      )                               //     (j was incremented above)
    )                                 //   end of inner some()
  ) ?                                 // end of outer some(); if truthy:
    0                                 //   discard this path by stopping recursion
  :                                   // else:
    a[0] ?                            //   if there's at least one remaining point:
      a.some((_, i) =>                //     for each remaining point at position i:
        r = f(                        //       do a recursive call with:
          b = [...a],                 //         a copy b[] of a[] without a[i] and
          p.concat(b.splice(i, 1)))   //         the extracted point added to the path
      ) && r                          //     end of some(); return the result, if any
    :                                 //   else:
      p                               //     this is a valid path: return it

```

Below is the detail of the **intersection()** test. This page provides a comprehensive explanation about the algorithm used.

```
[                                     // build an array containing:
  E = o(A, B = P[i + 1], C, S = []),  //   E = test of (A, B, C) (+ initialization of S[])
  F = o(A, B, D = P[j]),              //   F = test of (A, B, D)
  G = o(C, D, A),                     //   G = test of (C, D, A)
  H = o(C, D, B)                      //   H = test of (C, D, B)
]                                     //
.some(v =>                            // the segments are collinear and overlapping if:
  !v &                                //   any value above is 0
  !S.pop()                            //   and the corresponding entry in S[] is falsy
) |                                   // the segments intersect if:
E != F & G != H                       //   E is not equal to F and G is not equal to H

```

Finally, here is the definition of the helper function **o()**:

```
o = (                                             // given three points represented by
  [p, P], [q, Q], [r, R]                          // a lowercase letter for x
) =>                                              // and an uppercase letter for y:
  Math.sign(                                      //
    (                                             //   1) prepend to the array S[]
      S = [                                       //      a boolean which is true if the
        (p > q ? r < q | r > p : r < p | r > q) | //      segment (P, Q) would not contain
        (P > Q ? R < Q | R > P : R < P | R > Q),  //      the point R, assuming that the
        ...S                                      //      3 points are collinear
      ],                                          //
                                                  //   2) return the orientation of P, Q, R:
      Q - P                                       //        -1 = counterclockwise
    ) * (r - q) - (q - p) * (R - Q)               //         0 = collinear
  )                                               //        +1 = clockwise

```
> 6 votes

# Answer
# APL (Dyalog Classic), ~~42~~ 38 bytes

```
{⍋(⍪,(|z)×¯1*⊢=⌈/)12○z←0j1⊥¨⍵-⍵[⊃⍋↑⍵]}

```

Try it online!

Input is a list of coordinate pairs. Output is a 0-based permutation.

is the list of points - the argument to `{ }`

`⍵[⊃⍋↑⍵]` is the leftmost-lowest point

`⍵-` translates all points so that leftmost-lowest is at the origin of the coordinate system

`0j1` the imaginary unit i=sqrt(-1)

`0j1⊥¨` decodes the coordinates as if digits in a base-i number system - i.e. turns (x,y) into a complex number ix+y

`z←` assign to `z`

`12○` computes the complex numbers' arguments, a.k.a. theta angles, or APL circular function 12

`(⍪,(|z)×¯1*⊢=⌈/)` is a train that computes a boolean mask of where the angles are at a maximum (`⊢=⌈/`), turns the 0 1 in the mask into 1 ¯1 by raising ¯1 to the corresponding power (`¯1*`), multiplies by the magnitudes of the complex numbers `|z`, and concatenates that to the right (`,`) of a tall thin 1-column matrix () of the angles.

grade - returns the permutation that would sort the rows of the matrix lexicographically in ascending order
> 5 votes

---
Tags: code-golf, geometry, combinatorics, permutations
---


# Question
Title: Integer triangles with perimeter less than n
# Definition

An "integer triangle" is one with integer coordinates. For example the following triangle is an integer triangle:

```
(0, 0), (0, 1), (1, 2) with perimeter 1 + sqrt(2) + sqrt(5) ≈ 4.650.

```

# Task

The goal of this challenge is to count all integer triangles (up to congruence) with perimeter less than n.

# Input and Output

The argument will be given as an integer, and the output should be the number of triangles with perimeter strictly less than the argument.

# Examples

The smallest integer triangle by perimeter is congruent to

```
(0, 0), (0, 1), (1, 0) which has perimeter 2 + sqrt(2) ≈ 3.414

```

The next smallest are:

```
(0, 0), (0, 1), (1, 2) with perimeter 1 + sqrt(2) + sqrt(5) ≈ 4.650,
(0, 0), (0, 2), (1, 1) with perimeter 2 + 2sqrt(2)          ≈ 4.828,
(0, 0), (0, 2), (1, 0) with perimeter 3 + sqrt(5)           ≈ 5.236, and
(0, 0), (1, 2), (2, 1) with perimeter sqrt(2) + 2sqrt(5)    ≈ 5.886

```

Test cases:

```
a(1) = 0
a(2) = 0
a(3) = 0
a(4) = 1
a(5) = 3
a(6) = 5
a(7) = 11
a(8) = 18
a(9) = 29
a(10) = 44
a(12) = 94
a(20) = 738
a(30) = 3756
a(40) = 11875

```

I have coordinates for each of the triangles in this Gist.

# Warnings

Notice that two non-congruent triangles can have the same perimeter:

```
(0, 0), (0, 3), (3, 0) and (0, 0), (0, 1), (3, 4) both have perimeter 6 + 3sqrt(2).

```

Also keep in mind that the inequality is *strict*; the 3-4-5 pythagorean triangle should be counted by a(13), not a(12).

# Scoring

This is —the shortest code wins!

# Answer
# Jelly, ~~28~~ ~~27~~ ~~25~~ 23 bytes

```
pḶŒcÆḊÐfḅı;I$€AṢ€QS€<¹S

```

Try it online!

### How it works

```
pḶŒcÆḊÐfḅı;I$€AṢ€QS€<¹S  Main link. Argument: n

 Ḷ                       Unlength; yield [0,...,n-1].
p                        Take the Cartesian product of [1,...,n] and [0,...,n-1].
  Œc                     Take all combinations of the resulting pairs.
                         The result are of the form [[a, b], [c, d]].
    ÆḊÐf                 Filter by determinant; keep only pairs of pairs for which
                         the determinant (ad - bc) is non-zero, i.e., those such
                         that [0, 0], [a, b], and [c, d] are not collinear.
        ḅı               Convert each pair [a, b] from base i (imaginary unit) to
                         integer, mapping it to ai + b.
             €           For each pair of complex numbers [p, q]:
          ;I$              append their forward differences, yielding [p, q, p-q].
              A          Take the absolute value of each resulting complex number.
               Ṣ€        Sort each resulting array of side lengths.
                 Q       Unique; remove duplicates.
                  S€     Take the sum of each array, computing the perimeters.
                    <¹   Compare them with n.
                      S  Take the sum of the resulting Booleans.

```
> 7 votes

# Answer
# Jelly,  ~~38~~  33 bytes

-1 thanks to Erik the Outgolfer (invert `SP¬+÷/E$` by using `SẠ>÷/E$` and use `ÇÐf` rather than `ÇÐḟ`) -1 thanks to Mr. Xcoder (no need to flatten prior to the sort)
-2 thanks to Mr. Xcoder (`S<¥Ðf³L` -\> `S€<³S`)
-1 stealing a trick from an earlier revision of Dennis's answer (`ṗ2’Œc` -\> `p`⁺’` \- more redundant cases but golfier!)

```
SẠ>÷/E$
p`⁺’ÇÐfµ_/ṭ⁸²S€Ṣµ€Q½S€<³S

```

A full program taking an integer and printing the result.

**Try it online!** (too slow to complete test cases 20+ in under 60s)

### How?

```
SẠ>÷/E$ - Link 1, straightLineFromOrigin?: coordinates       i.e. [[a,b],[c,d]]
S       - sum                                                     [a+c,b+d]
 Ạ       - all? (0 if either of a+c or b+d are 0 otherwise 1)      all([a+c,b+d])
      $ - last two links as a monad:
   ÷/   -   reduce by division                                    [a÷c,b÷d]
     E  -   all equal?  (i.e. 1 if on a non-axial straight line)  a÷c==b÷d
  >     - greater than? (i.e. 1 if not on any line, 0 otherwise)  all([a+c,b+d])>(a÷c==b÷d)

p`⁺’ÇÐḟµ_/ṭ⁸²S€Ṣµ€Q½S€<³S - Main link: integer, n
p`                        - Cartesian product of implicit range(n) with itself
  ⁺                       - repeat (Cartesian product of that result with itself)
   ’                      - decrement (vectorises)
                          -  - i.e. all non-negative lattice point pairs up to x,y=n-1
     Ðf                   - filter keep only if:
    Ç                     -   call last link (1) as a monad
       µ         µ€       - monadic chain for €ach:
        _/                -   reduce with subtraction i.e. [a-c,b-d]
           ⁸              -   chain's left argument, [[a,b],[c,d]]
          ṭ               -   tack                   [[a,b],[c,d],[c-a,d-b]]
            ²             -   square (vectorises)    [[a²,b²],[c²,d²],[(c-a)²,(d-b)²]]
             S€           -   sum €ach               [[a²+b²],[c²+d²],[(c-a)²+(d-b)²]]
                          -    - i.e. the squares of the triangle's edge lengths
               Ṣ          -   sort
                  Q       - de-duplicate (get one of each congruent set of triangles)
                   ½      - square root (vectorises)  - get sides from squares of sides
                    S€    - sum €ach
                       ³  - program's 3rd argument, n
                      <   - less than?
                        S -   sum (number of such triangles)
                          - implicit print

```
> 4 votes

# Answer
# JavaScript (ES7), 157 bytes

```
f=(n,i=n**4,o={})=>i--&&([p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),!o[k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&a+b+c<n&&(o[k]=P*q!=p*Q))+f(n,i,o)

```

### Test cases

Only small values can be computed with the default stack size of most JS engines.

```
f=(n,i=n**4,o={})=>i--&&([p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),!o[k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&a+b+c<n&&(o[k]=P*q!=p*Q))+f(n,i,o)

;[
  1,  // 0
  2,  // 0
  3,  // 0
  4,  // 1
  5,  // 3
  6,  // 5
  7,  // 11
  8,  // 18
  9   // 29
]
.forEach(n => console.log('a(' + n + ') = ' + f(n)))
```

---

# Non-recursive version, 165 bytes

```
n=>[...Array(n**4)].reduce((x,_,i,o)=>x+=!o[[p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&(o[k]=P*q!=p*Q)&a+b+c<n,0)

```

### Test cases

This version also works for **a(30)** and **a(40)**, but that would take too much time for the snippet.

```
let f =

n=>[...Array(n**4)].reduce((x,_,i,o)=>x+=!o[[p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&(o[k]=P*q!=p*Q)&a+b+c<n,0)

;[
  1,  // 0
  2,  // 0
  3,  // 0
  4,  // 1
  5,  // 3
  6,  // 5
  7,  // 11
  8,  // 18
  9,  // 29
  10, // 44
  12, // 94
  20  // 738
]
.forEach(n => console.log('a(' + n + ') = ' + f(n)))
```
> 3 votes

# Answer
# Julia 0.6, 135 bytes

Iterate over possible non-origin points to make up the triangle, represent them as complex numbers, sort the square lengths and keep them in a set to check for congruence. Avoids colinear points by checking that the angle between their complex numbers is nonzero. Then it returns the length of the set. It's shorter to use the lengths directly, but you get the wrong answer for `a(40)`. The solution is too slow to reach run `a(40)` because of a deprecation warning, so I have a link to a faster version as well.

```
n->(q=Set();for x=0:n,y=1:n,a=1:n,b=0:n
r=x+y*im
t=a+b*im
g=sort(abs2.([r,t,r-t]))
sum(√g)<n&&angle(r/t)>0&&push!(q,g)
end;length(q))

```

Try it online!

Faster, longer version with deprecation avoided. Try it online! Uses `sqrt.(g)` in place of deprecated `√g` for elementwise square root.
> 2 votes

# Answer
# Clean, ~~227~~ ... 143 bytes

```
import StdEnv
@n#l=[0.0..n]
=sum[1\\p<-removeDup[sort(map(sqrt o\[u,v]=u*u+v*v)[[a-i,b-j],[a,b],[i,j]])\\a<-l,b<-l,i<-l,j<-l|a*j<>i*b]|sum p<n]

```

Try it online!

Detects congruent triangles via comparing the three values which sum to make the perimeter, and colinear points by verifying that the two smallest such values do not sum to the third.

Here's a version that uses a faster, more memory-heavy, approach: Try it online!
> 1 votes

---
Tags: code-golf, sequence, geometry, combinatorics
---