text:
Plumbing Random Paths
Write a program or function that takes in three integers, a width w, a height h, and a step count s. You will be drawing a non-self-intersecting random walk s steps long on a 5*w by 5*h pixel image where every 5 by 5 pixel cell is either empty (pure beige) or one of these twelve simple "pipes":

The image above is enlarged to show detail. Here are the pipes at actual size:

(The gray lines are just to separate the pipe types.)
The random walk will be a single continuous pipe path that starts at one pipe endpoint (one of the bottom four pipe types) and ends at another pipe endpoint.
Start with an empty w by h grid and randomly choose one cell to be the starting point. Then randomly choose one of the four directions to start in and draw the corresponding pipe endpoint. This starting cell marks the first step in your walk and every time you draw a new cell or overwrite an existing one it counts as another step taken.
Now, repeatedly, randomly choose to go right, left, or straight, drawing the appropriate pipe cell if the direction chosen is valid. Backtrack and re-choose if a direction is not valid until the complete s step path is formed. The path should end with a pipe endpoint, which might be anywhere on the grid, depending on the course the path took.
It is very important to note that only the two straight pipe cells can be overwritten, and only by the straight pipe cell of the opposite orientation, the result being an intersection cell. Otherwise, all pipes must be placed in empty cells.
When an intersection is drawn, the part of the path that is further along from the starting cell should be drawn on top.
It is up to you whether or not the grid has periodic boundary conditions (PBC), i.e. whether a pipe exiting one side of the grid will come out on the other side. Without PBC the grid boundary counts as a barrier that you can run into just like other pipes.
Special Cases

When s is 0 no pipes should be drawn and the output should be a blank 5*w by 5*h image (i.e. all beige).
When s is 1 a single pipe stub
 (Actual size: )
should be drawn at the randomly chosen starting cell.

Other Details

You may assume that s is at most w*h so a path will always be possible. (Though longer paths are possible due to intersections.)
w and h will always be positive.
All random choices must be uniformly random. e.g. you shouldn't avoid making intersections when they are possible even if it makes the problem easier. Pseudo-random number generators are allowed.
Any three visually distinct colors may be used in place of the black, blue, and beige.
Your output images may be enlarged so that they are really 5*w*k by 5*h*k pixels where k is a positive integer. (Enlarging any examples you post is advised even if your k is 1.)
Any common lossless image file format may be used and the image may be saved to a file, displayed, or spewed raw to stdout.

The shortest code in bytes wins.
Examples
(All enlarged by 500%.)
If the input is w=2, h=1, s=0 then the output will always be:

If the input is w=2, h=1, s=1 then the output will be one of these images with equal chance:

If the input is w=2, h=1, s=2 then the output will be

or possibly

if the grid is assumed to have PBC.
(Note that starting the path like  would make a second step impossible.)

Here are some possible outputs for w=3, h=2, s=6, assuming PBC:

Here is a possible output for w=3, h=3, s=9, assuming PBC:

Notice that the path didn't need to cover all the cells due to the intersection counting as two steps. Also, we can deduce that the corner endpoint was the starting cell since the intersection overpass must have been drawn afterwards. Thus we can infer the sequence of random choices that were made:
start at top left, facing east
go straight
go right
go right
go right
go straight
go left
go right
end

Finally, here are examples of w=4, h=5, s=20 and w=4, h=5, s=16:

The whole idea is just a random walk, right?

Row 2: You will be drawing a non-self-intersecting random walk ... is it self-intersecting or not?

@ChristianIrwan Well not really. Random walks can usually double back on themselves, or not intersect themselves at all. This is a unique case since intersections are made but they don't count as retracing the same ground. And yes this could be in an ascii-art format or something but I like the idea of making nice looking images.

@edc65 That is kinda contradictory I'll grant you. I mean that the path never re-walks a pipe it had already walked. The pipe intersections contain two distinct steps of the path that are allowed to occupy the same cell. I can edit the question if this notion is unclear.

@Calvin'sHobbies Still, the graphic output thingie is not the main part, why don't we can do a output in normal way?

@ChristianIrwan What way would that be exactly?

Using ascii and map those 12 picture into 11 ascii (The intersection cells is merged)

@ChristianIrwan I already answered that when I said "And yes this could be in an ascii-art format or something but I like the idea of making nice looking images." I choose not to involve ascii-art.

@Calvin'sHobbies Then which picture format should the program produce, is PBM suffice?

@ChristianIrwan Yes

Are "knots" allowed?

@aditsu The random walk will be a single continuous pipe path that starts at one pipe endpoint (one of the bottom four pipe types) and ends at another pipe endpoint so mathematical knots are not permitted, due to being closed loops.

When an intersection is drawn, the part of the path that is further along from the starting cell should be drawn on top. This excludes everyday (non-mathematical) knots, which require going under and over. Pipes can only ever go over, never under the previous pipework.

Do all possible outputs need to have the same probability? Or just non-zero probability? I think equal probability is tricky because non-intersecting paths can be generated in 2 ways, and also the possible choices at each step don't carry the same "weight".

@aditsu non-zero probability is fine

Can the path start or end at an intersection? That doesn't seem to appear in the 12 possible cases you listed.

@aditsu No, it should not.

CJam, 274
q~:K;:B;:A;{0aA*aB*:M5*5f*:I;K{[Bmr:QAmr:P]5f*:R;3Ym*{R.+:)2{1$0=I=2$W=@tI@0=@t:I;}:F~}/R2f+1FK({MQ=P=:EY4mr:D#&1{{MQMQ=PE2D#+tt:M;}:G~7,1>[W0_1_0_W]2/D=:Off*{[QP]5f*2f+.+_:H1F_OW%.+2FOW%.m2F}/H2FO~P+:P;Q+:Q;MQ=P=:E_5YD2%-*=!JK2-=+*1{D2+4%:D;G}?}?}fJ]}0?}g'P2NA5*SI,N2NI:+N*

Try it online
Uses PBC, outputs in PGM format. You can remove the :+ near the end to get a nicer visual output in the browser.
It's very slow for larger input, especially if the step count is close to the area.
Example result for input 4 3 10 (scaled 500%):

Brief explanation:
The general approach is:

repeat all the following steps until successful:
initialize 2 matrices: one recording which sides are being used in each cell, and one for the image
if s=0, we're done, else:
pick a random cell and draw a square, then do the following s-1 times:
pick a random direction; if that side is already used, fail and start over
mark the side as used and draw the actual pipe in the image (drawing 3 adjacent lines of length 6, starting right "after" the center pixel of the current cell, then adding a dot to cap the end of the pipe)
update the current position (moving to the next cell)
check if the cell is empty or it's a valid crossing; if not, fail and start over
mark the side in the opposite direction as used in this cell, then continue the loop

QBasic, 517 516 bytes
RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
1CLS
IF s=0GOTO 9
x=5*INT(RND*w)
y=5*INT(RND*h)
GOSUB 7
FOR k=1TO s-1
r=INT(RND*4)+1
a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)=0GOTO 1
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
9IF c GOTO 1
END
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN

Takes w, h, and s from user input, comma-separated.
Output is drawn on the screen. While the program is searching for a solution, you may see partial solutions flickering past.
Does not use periodic boundary conditions. I found it easier to draw and test for connecting pipes without having to worry about half of the pipe being on one side of the grid and half on the other.

The approach here is to try a random direction at each step and start over from the beginning if it results in an invalid move. We draw the pipes as the directions are decided, and use POINT to test points on the screen for our validity conditions. A move is valid if it doesn't go outside the boundaries of the grid and:

The moved-to cell is empty; or
Both

The moved-to cell contains a pipe going straight through, either horizontally or vertically, and
The new pipe section does not double up an existing pipe section

Like aditsu's CJam answer, this code is very slow, and can be mind-numbingly slow if s is a significant fraction of w*h. On my QB64 setup, it comes up with an answer for 5,5,19 fairly promptly, but takes longer than I was willing to wait on 5,5,20.
If you want to run larger/more densely packed examples, here's my original approach using a depth-first search. It's much more efficient, at the cost of a whopping 300 extra bytes.
RANDOMIZE TIMER
SCREEN 9
INPUT w,h,s
DIM t(s),m(s)
0
FOR z=1TO s
t(z)=-1
NEXT
i=5*INT(RND*w)
j=5*INT(RND*h)
k=1
1CLS
IF s=0GOTO 9
x=i
y=j
GOSUB 7
FOR z=1TO k-1
r=m(z)
GOSUB 6
x=a
y=b
GOSUB 7
o=1AND r
p=x-2+3*o-5*(r=2)
q=y+1-3*o-5*(r=1)
u=p+3-o
v=q+2+o
LINE(p,q)-(u,v),7,B
LINE(p+o,q+1-o)-(u-o,v-1+o),1
NEXT
IF c*(k=s)THEN k=k-1:GOTO 1 ELSE IF k=s GOTO 9
IF k<1GOTO 0
IF t(k)>=0GOTO 4
t(k)=0
f=30
WHILE f
r=INT(RND*4)+1
IF f AND 2^r THEN t(k)=t(k)*5+r:f=f-2^r
WEND
4r=t(k)MOD 5
m(k)=r
t(k)=t(k)\5
GOSUB 6
c=(POINT(a,b+2)*POINT(a+4,b+2)+POINT(a+2,b)*POINT(a+2,b+4))*(0=POINT((a+x)\2+2,(b+y)\2+2))
IF((0=POINT(a+2,b+2))+c)*(a>=0)*(b>=0)*(a<5*w)*(b<5*h)THEN k=k+1 ELSE IF t(k)>0GOTO 4 ELSE t(k)=-1:k=k-1
GOTO 1
6a=x+5*((r=2)-(r=4))
b=y+5*((r=1)-(r=3))
RETURN
7LINE(x+1,y+1)-(x+3,y+3),7,B
PSET(x+2,y+2),1
RETURN
9

Example output for inputs 10, 10, 100, actual size:
A still fancier version can be found in this gist. Besides being ungolfed and thoroughly commented, it scales up the output by a constant factor and allows for a set delay between steps, enabling you to watch the DFS algorithm at work. Here's an example run:


text:
Symmetric boolean functions as Zhegalkin polynomials
Let \$\mathbb{B} = \mathbb{Z}_2 = \{0, 1\}\$ be the set of booleans. A symmetric boolean function in \$n\$ arguments is a function \$f_S : \mathbb{B}^n \to \mathbb{B}\$ that checks if the number of its true arguments is in \$S\$, i. e. a function \$f_S\$ such that
$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = \left(\sum_{1 \le  i \le n}\alpha_{i}\right) \in S$$
or equivalently
$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = |\{ i : \alpha_i \}| \in S. $$
These functions are called symmetric boolean function because they are all the boolean function that do not depend on argument order.
The set of boolean numbers forms a field, conventionally denoted \$GF(2)\$, where multiplication is logical and (\$\wedge\$) and addition is exclusive or (\$\oplus\$). This field has the properties that \$-\alpha = \alpha\$, \$\alpha / \beta = \alpha \wedge \beta\$ (for all \$\beta \neq 0\$), \$\alpha \oplus \alpha = 0\$ and \$\alpha \wedge \alpha = \alpha\$ for all \$\alpha\$ in addition to the field properties. For convenience, I am going to write \$\oplus\$ as \$+\$ and leave out \$\wedge\$ in the next paragraphs. For example, I will write \$\alpha \oplus \beta \oplus \alpha \wedge \beta\$ as \$\alpha + \beta + \alpha\beta\$.
Every boolean function can be expressed as a polynomial over the field of boolean numbers. Such a polynomial is called a Zhegalkin polynomial, the representation is canonical, i. e. there is exactly one polynomial that represents a given boolean function. Here are some examples for boolean functions and their corresponding Zhegalkin polynomials:

\$\alpha \vee \beta = \alpha + \beta + \alpha\beta\$
\$\alpha \wedge \neg\beta = \alpha + \alpha\beta\$
\$(\alpha \to \beta) \oplus \gamma = 1 + \alpha +  \gamma + \alpha\beta\$
\$\neg(\alpha \wedge \beta) \vee \gamma = 1 + \alpha\beta + \alpha\beta\gamma\$
\$f_{\{1, 4\}}(\alpha, \beta, \gamma, \delta) = \alpha + \beta + \gamma + \delta + \alpha\beta\gamma + \alpha\beta\delta + \alpha\gamma\delta + \beta\gamma\delta + \alpha\beta\gamma\delta\$
where the triple terms \$(\alpha\beta\gamma + \alpha\beta\delta + \alpha\gamma\delta + \beta\gamma\delta)\$ are required because otherwise we would have \$f(1,1,1,0) = 1\$, and \$3 \not\in \{1, 4\}\$.

One observation we can make is that due to symmetry, the Zhegalkin polynomial for a symmetric boolean function always has the form
$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = \sum_{i \in T_{S,n}}t_{n,i}$$
where \$\sum\$ denotes summation with exclusive or and \$t_{n, i}\$ is the sum of all product terms that use \$i\$ out of the \$n\$ arguments to \$f_S\$ and \$T_{S,n} \subseteq \{0, 1, \ldots, n\}\$ is a set describing those \$t_{n, i}\$ we need to construct \$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n)\$. Here are some examples for \$t_{n, i}\$ so you can get an idea what they look like:

\$t_{4, 1} = \alpha + \beta + \gamma + \delta\$
\$t_{3, 2} = \alpha\beta + \alpha\gamma + \beta\gamma\$
\$t_{4, 4} = \alpha\beta\gamma\delta\$
for all \$n\$: \$t_{n, 0} = 1\$

We can thus describe an \$f_S\$ in \$n\$ arguments completely by \$n\$ and \$T_{S, n}\$. Here are some test cases:

\$T_{\{1, 4\}, 4} = \{1, 3, 4\}\$
\$T_{\{2, 3, 4\}, 4} = \{2, 4\}\$
\$T_{\{2\}, 4} = \{2, 3\}\$
\$T_{\{1, 2\}, 2} = \{1, 2\}\$ (logical or)
\$T_{\{2, 3\}, 3} = \{2\}\$ (median function)

The task in this challenge is to compute \$T_{S, n}\$ given \$S\$ and \$n\$. You can choose an appropriate input and output format as you like. This challenge is code-golf, the shortest solution in octets wins. As a special constraint, your solution must run in polynomial time \$O(n^k)\$ where \$n\$ is the \$n\$ from the input.

I think T_{2, 3}, 3 should be {2}.

@alephalpha Of course.

@alephalpha: what about if x1=x2=x3=True? Then f{2}(x1,x2,x3) should be False, but sum(t_n,i), for i in {T_{2,3]}} = sum(t_n,i) for i in {2} = t_3,2 = x1 * x2 + x1 * x3 + x2 * x3 = T * T + T * T + T * T = T. Or am i misunderstanding the notation here?

@njnnja T_{2,3},3 describes f{2,3}(x1,x2,x3), not f{2}(x1,x2,x3). I hope this clears up your misunderstanding.

@PeterTaylor No. If α = β = γ = 1 and δ = 0 you would get 1 + 1 + 1 + 0 + 1∧1∧1∧0 = 1 which is wrong for f_{1, 4} as 3 is not in {1, 4}. I admit the description is a bit ambiguous: In the first paragraph (and only there), ∑ denotes a sum over integers, not over booleans.

Is my input format valid?

@ThomasKwa I would rather if you either only received the set as a bitmap or if you received the set as its elements and a length, but I didn't specify an input format so it's pretty much fine. Could you write down how your solution works?

Dyalog APL, 15 bytes
{2|⍺⌹⍉∘.!⍨0,⍳⍵}

Matrix division, basically. Takes input like 0 0 1 1 1 {2|⍺⌹⍉∘.!⍨0,⍳⍵} 4 for T4({2,3,4}).
{              }        Dyadic function:
              ⍵         Right argument          4
             ⍳          Index vector            1 2 3 4
           0,           Append 0                0 1 2 3 4
      ∘.                Outer product           ——————————
          ⍨             |With itself              1 0 0 0
        !               |By binomial coeff.       2 1 0 0
     ⍉                  Matrix transpose          3 3 1 0
                        Result at this step: ->   4 6 4 1
   ⍺                    Left argument
    ⌹                   Matrix division (A⌹B is A^-1 B, not A B^-1)
                        (implicitly converts ⍺ to column vector)
 2|                     Modulo 2

Since the transposed matrix of binomial coefficients is lower triangular with determinant 1, its inverse will only contain integers. So to matrix-divide over F2 we can just matrix-divide over the reals, then mod by 2.
Matrix division is an O(n^3) operation, and calculating each of the O(N^2) binomial coefficients is well below O(n^3), so this runs in O(N^5).
Try it on TryAPL.

Neato! I expected nothing less than this from APL.

R, 115 bytes
function(S,n)which(abs(solve(sapply(1:n,function(k)(sapply(1:n,function(j)choose(j,k)%%2))),is.element(1:n,S)))==1)

The key is realizing that the sum of t's that evaluate to a T value is just the choose function. A slightly ungolfed version that doesn't calculate in polynomial time is below, but illustrates the derivation of the t's a little better (just run the middle line).
function(S,n)which(abs(solve(
sapply(1:n,function(k)(sapply(1:n,function(j)sum(apply(combn(c(rep(T,j),rep(F,max(0,k-j))),k),2,all))%%2))),
is.element(1:n,S)))==1)

Are you sure choose(j,k) computes in polynomial time? I doubt that since the binomials grow exponentially.

The binomials grow exponentially in n, but the number of digits goes linearly. You mean polynomial time in n, not polynomial time in log n (size of input), right?

The golfed version does. The ungolfed version expands all the necessary combinations and is O(n!) (or worse, just guessing). But the golfed function uses the choose function, which is a closed formula =n!/(n-k)!k! which only requires 2 extra calculations when incrementing n by 1, and is therefore O(n^1). Note that we are looking at the binomial expansion in the ungolfed version; but in the golfed version we just multiply n integers together. I.e. g(n)=n! is not O(n!) complexity

@ThomasKwa Yeah, polynomial time in n, not in log n.

CJam (25 24 bytes)
{_,{1$_,,2$~f&:!.*:^t}/}

This is an anonymous function which takes an array of 0 or 1 which serves as an indicator function for \$S\$ and returns an array of 0 or 1 which serves as an indicator function for \$T\$. E.g. to find \$T_{\{1, 4\}, 4}\$ you pass [0 1 0 0 1] and it returns [0 1 0 1 1].
Online demo
Explanation
Recall that \$t_{n,i}\$ is the sum of all product terms that use \$i\$ out of the \$n\$ arguments to \$f_S\$. Suppose that \$s\$ of the \$n\$ arguments are true. Then we have three cases for \$t_{n,i}(\alpha_0, \ldots, \alpha_{n-1})\$:

\$i > s\$ : none of the terms is true, so \$t_{n, i}(\alpha_0, \ldots, \alpha_{n-1}) = 0\$
\$i = s\$ : exactly one of the terms is true, so \$t_{n, i}(\alpha_0, \ldots, \alpha_{n-1}) = 1\$
\$i < s\$ : there are \$\binom{s}{i}\$ terms which are true, so \$t_{n, i}(\alpha_0, \ldots, \alpha_{n-1}) =  \binom{s}{i} \bmod 2\$

If we let \$\sigma\$ be the indicator function for \$S\$ and \$\tau\$ be the indicator function for \$T_{S, n})\$, we therefore get the matrix identity
$$\begin{pmatrix}1 & 0 & 0 & \ldots & 0 \\
\binom{1}{0} & 1 & 0 & \ldots & 0 \\
\binom{2}{0} & \binom{2}{1} & 1 & \ldots & 0 \\
\vdots & \vdots & \vdots & \ddots & 0 \\
\binom{n}{0} & \binom{n}{1} & \binom{n}{2} & \ldots & 1
\end{pmatrix}
\begin{pmatrix}\tau(0) \\ \tau(1) \\ \tau(2) \\ \vdots \\ \tau(n) \end{pmatrix}
=
\begin{pmatrix}\sigma(0) \\ \sigma(1) \\ \sigma(2) \\ \vdots \\ \sigma(n) \end{pmatrix}
$$
which is dead easy to solve because the coefficient matrix is already in row-reduced echelon form.
Note that this is quite a well-known matrix, because it's the binomial coefficients modulo 2, which famously forms a Sierpiński triangle. I calculate them using Lucas' theorem and bit-twiddling as 2$~f&:!

Notice that all three cases can be reduced to the third.

Yes, and I'm implicitly relying on that when calculating the matrix, but from a didactic point of view I think it's preferable to split them up.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Reverse a regex
The Challenge
Given a valid regex, output a regex that that matches the same set of strings, but reversed.
The Task
This challenge uses the most basic regex operations: ^, $, ?, +, *, [], {}, |.  There's no such thing as capture groups or any of that complicated stuff.  Special characters can be escaped.
Sample Input/Output
Note: Invalid input will never be given, and there are generally multiple possible answers for a given input!
Input      | Sample Output
-----------|-------------
abc        | cba
tuv?       | v?ut
a(b|c)     | (c|b)a
1[23]      | [23]1
a([bc]|cd) | (dc|[bc])a
^a[^bc]d$  | ^d[^bc]a$
x[yz]{1,2} | [yz]{1,2}x
p{2}       | p{2}
q{7,}      | q{7,}
\[c[de]    | [de]c\[
ab[c       | <output undefined>
a(?bc)     | <output undefined>
a[]]bc     | <output undefined>

Demo
Working demo that demonstrates correct inputs/outputs.  This has some additional logic for validating inputs that isn't necessary in a real answer.  Consider invalid inputs to be undefined behavior.
Specifics
For simplicity, all special characters either have their special meaning or are escaped; that is, [[] isn't a character range for [.  Length ranges come from standard POSIX EREs; that is, {n}, {n,}, and {n,m} are supported.  The character ranges [] and [^] are supported.  Because of these rules, and since no invalid input is given, you really need only copy the contents of these directly to the output.  Lastly, greediness doesn't matter, i.e. it doesn't matter if the reversed regex finds a different match first, it just needs to find a match for the same set of strings.
Scoring
Smallest program in bytes (barring cheating such as network requests) wins.  Program can either use real IO or simply define a function.

Because there's nothing for the ? to attach to.  Try typing /a(?bc)/ into the browser's console.

Looks good now. You might want to add something like (^a|b)(c$|d) as a test case though.

Can we assume that the input will contain only printable ASCII characters? In particular, no linefeed characters?

As a side note, I'm pretty sure those "cheating" programs are covered in the standard loopholes post, which is somewhere that I can't find right now because I'm dumb. You might want to link to that.

Should we consider qualifiers applied on groups i.e. (a)?(b)+ ↦ (b)+(a)??

Your list of regex operation is missing (), which is used in your example.

Retina, 136 114 110 bytes
Yo dawg, I heard you like regex...
^
;
(T`^$`$^`;.
(.*);(\[(\\.|[^]])*]|\\.|.)([*+?]|{\d+(,|,\d+)?})?
$2$4!$1;
^\(!
)
^\)(.*)!(.+?)
($2$1
;$|!
<empty>

Where <empty> represents an empty trailing line. Run the code from a single file with the -s flag.
...when you wanna reverse regex you should use regex. When you wanna use regex you should use a regex-based programming language.
This code assumes that the input contains neither ; nor ! nor spaces. While I agree that that's a pretty strong and potentially invalid assumption, you could replace those three in the code with any three unprintable characters (like null bytes, bell character,  you name it), and it wouldn't affect the code size or functionality at all.
I'll add an explanation when I'm done golfing.

"I herd* you liek*"

I think the code also assumes that the regex does not contain any raw new line character.

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Oh, that is true, I was under the assumption that there will be no unprintable characters in the input. I will fix that once we get clarification from the OP. (If any characters can appear, there are still certain combinations that won't show up in what this challenge considers a valid regex, e.g. ]]], so either way, this answer won't need much modification.)

done golfing after over a year? :P

JavaScript ES6, 574 bytes
I can probably remove a few var statements.
R=e=>{for(var s=0,c=[],h=/(\?|\+|\{\d*,*\d*\}|\*)(\?*)/,t=0;t<e.length;t++)switch(s){case 0:switch(e[t]){case"\\":t++,c.push("\\"+e[t]);break;case"[":j=t,s=1;break;case"(":k=t,s=2;break;default:var l=e.search(h,t);(l>=t+1||0>l)&&c.push(l==t+1?e[t]+e.slice(t,e.length).match(h)[0]:e[t])}break;case 1:"\\"==e[t]?t++:"]"==e[t]&&(c.push(e.slice(j,t+1)+(e.search(h,t)==t+1?e.slice(t,e.length).match(h)[0]:"")),s=0);break;case 2:"\\"==e[t]?t++:")"==e[t]&&(a=R(e.slice(k+1,t)),c.push("("+a+")"),s=0)}c.reverse(),r=c;var i=c.length-1;return"^"==c[i]&&(r[i]="$"),"$"==c[0]&&(r[0]="^"),r.join``}}

JS ES6, untested, 559 bytes
Will test at home.
R=e=>{for(s=0,c=[],h=/(\?|\+|\{\d*,*\d*\}|\*)(\?*)/,t=0;t<e.length;t++)switch(s){case 0:switch(e[t]){case"\\":t++,c.push`\\${e[t]}`;break;case"[":j=t,s=1;break;case"(":k=t,s=2;break;default:l=e.search(h,t);(l>=t+1||0>l)&&c.push(l==t+1?e[t]+e.slice(t,e.length).match(h)[0]:e[t])}break;case 1:"\\"==e[t]?t++:"]"==e[t]&&(c.push(e.slice(j,t+1)+(e.search(h,t)==t+1?e.slice(t,e.length).match(h)[0]:"")),s=0);break;case 2:"\\"==e[t]?t++:")"==e[t]&&(a=R(e.slice(k+1,t)),c.push`(${a})`,s=0)}c.reverse(),r=c;i=c.length-1;return"^"==c[i]&&(r[i]="$"),"$"==c[0]&&(r[0]="^"),r.join``}}

JavaScript ES5, ungolfed, 961 bytes
function revRegex(str){
 var mode = 0;
 var oS = [];
 var post = /(\?|\+|\{\d*,*\d*\}|\*)(\?*)/;
 for(var i=0;i<str.length;i++){
  switch(mode){
   case 0: switch(str[i]){
    case "\\": i++; oS.push("\\"+str[i]); break;
    case "[": j=i; mode = 1; break;
    case "(": k=i; mode = 2; break;
    default:
     var pLoc = str.search(post,i);
     if(pLoc>=i+1||pLoc<0){ // current is not pLoc
      if(pLoc==i+1){
       oS.push(str[i] + str.slice(i,str.length).match(post)[0]);
      } else {
       oS.push(str[i]);
      }
     }
   }; break;
   case 1: if(str[i]=="\\") i++; else if(str[i]=="]"){oS.push

(str.slice(j,i+1)+(str.search(post,i)==i+1?str.slice

(i,str.length).match(post)[0]:""));mode = 0}; break;
   case 2: if(str[i]=="\\") i++; else if(str[i]==")")

{a=revRegex(str.slice(k+1,i));oS.push("("+a+")");mode =

0};break;
  }
 }
 oS.reverse();
 r=oS;
 var l=oS.length-1;
 if(oS[l]=="^") r[l]="$";
 if(oS[0]=="$") r[0]="^";
 return r.join("");
}

lol, you used regex to reverse regex :D

@ΚριτικσιΛίθος Yes, I did :D I'd use it to parse HTML if I could...

"if you could"

@Optimizer Indeed!

Nice work! If you're still looking to golf this, I'm 99% sure that a few if(x==y)do_stuff(); statements will be at least 25% shorter than switch(x){case y:do_stuff();break;}.

@ETHproductions Thanks :) I think so, too; I'll put in the untested answer, but, atm, I'm isolated from Firefox.

@CᴏɴᴏʀO'Bʀɪᴇɴ i parsed html codes with regex but got a serious problem with unicode chars

@Agawa001 o__o Pro tip: this is the only valid way to parse HTML with Regex: code.replace(/<(.+)>.+?</\1>/,"");

@CᴏɴᴏʀO'Bʀɪᴇɴ This is an alternative: `code.replace(/.*/, "trollolol");

@CᴏɴᴏʀO'Bʀɪᴇɴ What if I write  b.toUpperCase())">Upper Case? Or heck, even just Blah? Your code doesn't strip those out! Anyway, time for me to go back to Hell. Regards, Satan.

The 574 bytes one gives R("a{3}b") -> "a{3}"

@feersum So does the other one... let me debug.

Here is a test case. At least the ungolfed version seems to be dropping several tokens. I get this result.

@MartinBüttner Thanks for the test case. I unfortunately cannot debug probably for another 6-7 hours.

JavaScript ES6, 343 bytes
t=r=>(u="substr",T="(?:[+?*]|{\\d+(?:,\\d*)?})?)([^]*)",(c=r[0])=="(")?([n,s]=v(r[u](1)),[_,q,s]=s.match("^(\\)"+T),["("+n+q,s]):c==")"||c==null?["",r]:c=="^"?["^",r[u](1)]:c=="$"?["^",r[u](1)]:r.match("^("+/(?:\[(?:[^\]\\]|\\[^])*\]|[^[\\]|\\[^])/.source+T).slice(1);(v=r=>{var o="";do{[n,r]=t(r);o=n+o;}while(n&&r);return[o,r]})(prompt())[0]

Original code (the functions, but without prompt):
function reverse(regex) {
    var out = "";
    do {
        // console.log("calling term");
        var [node, regex] = term(regex);
        // console.log("reverse: " + [node, regex]);
        out = node + out;
    } while (node && regex);
    return [out, regex];
}

function term(regex) {
    switch (regex[0]) {
        case "(":
            // console.log("calling reverse");
            var [node, sequel] = reverse(regex.substr(1));
            // console.log("term: " + regex + " / " + [node, sequel]);
            var [_, quantifier, sequel] = sequel.match(/^(\)(?:[+?*]|{\d+(?:,\d*)?})?)([^]*)/);
            return ["(" + node + quantifier, sequel];
        case ")":
        case void 0:
            return ["", regex];
        case "^":
            return ["$", regex.substr(1)];
        case "$":
            return ["^", regex.substr(1)];
        default:
            return regex.match(/^((?:\[(?:[^\]\\]|\\[^])*\]|[^[\\]|\\[^])(?:[+?*]|{\d+(?:,\d+)?})?)([^]*)/).slice(1);
    }
}

reverse("^\\(([The(){}*\\] ]{2,3}world\\\\(begin(ner|ning)?|ends*)+|Con\\|ti\\*n\\)ue...[^%\\[\\]()\\\\])$")[0]

The code is implemented as a recursive top-down parser, so it may cause stack overflow on deeply nested input.
The code may cause infinite loop in invalid cases, since I don't test them, taking advantage of the "undefined behavior" clause.

Python 3, 144 bytes
(This one does not support qualifiers on a group like (a)+(b)*(cde)?.)
import re;f=lambda x:''.join({e:e,'^':'$','$':'^','(':')',')':'('}[e]for e in re.findall(r'(?:\\.|\[(?:\\?.)+?\]|.)(?:[?+*]|\{.+?\})?',x)[::-1])

Test cases:
test_cases = [
    # Provided test cases
    r'abc',
    r'tuv?',
    r'a(b|c)',
    r'1[23]',
    r'a([bc]|cd)',
    r'^a[^bc]d$',
    r'x[yz]{1,2}',
    r'p{2}',
    r'q{7,}',
    r'\[c[de]',

    # Pathological cases
    r'a{3}b',
    r'(a)?(b)+',            # <-- currently failing!
    r'[\[]{5}[^\]]{6}',
    r'[\[]\]{7}',
    r'[\[\]]{8,9}',
    r'\(\)\^\$',

    # Undefined cases
    r'ab[c',
    r'a(?bc)',
    r'a[]]bc',
]

for t in test_cases:
    print(t, '->', f(t))

Result:
abc -> cba
tuv? -> v?ut
a(b|c) -> (c|b)a
1[23] -> [23]1
a([bc]|cd) -> (dc|[bc])a
^a[^bc]d$ -> ^d[^bc]a$
x[yz]{1,2} -> [yz]{1,2}x
p{2} -> p{2}
q{7,} -> q{7,}
\[c[de] -> [de]c\[
a{3}b -> ba{3}
(a)?(b)+ -> )+b))?a)                    # <-- note: wrong
[\[]{5}[^\]]{6} -> [^\]]{6}[\[]{5}
[\[]\]{7} -> \]{7}[\[]
[\[\]]{8,9} -> [\[\]]{8,9}
\(\)\^\$ -> \$\^\)\(
ab[c -> c[ba
a(?bc) -> (cb(?a
a[]]bc -> cb[]]a

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

authors: n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳


text:
An optimization challenge with strange coins
You have n coins which each weigh either -1  or 1. Each is labelled from 0 to n-1 so you can tell the coins apart.  You have one (magic) weighing device as well. At the first turn you can put as many coins as you like on the weighing device which is able to measure both negative and positive weights and it will tell you exactly how much they weigh.
However, there is something really strange about the weighing device.  If you put coins x_1, x_2, ..., x_j on the device the first time, then the next time you have to put coins (x_1+1), (x_2+1) , ..., (x_j+1) on the scale with the exception that you of course can't put on a coin numbered higher than n-1.   Not only that, for every new weighing you get to choose if you also want to put coin 0 on the scale.

Under this rule, what is the smallest number of weighings that will always tell you
  exactly which coins weigh 1 and which weigh -1?

Clearly you could just put coin 0 on the device in the first turn and then it would take exactly n weighings to solve the problem.
Languages and libraries
You can use any language or library you like (that wasn't designed for this challenge). However, I would like to be able to test your code if possible so if you can provide clear instructions for how to run it in Ubuntu that would be very much appreciated.
Score
For a given n your score is n divided by the number of weighings you need in the worst case. Higher scores are therefore better.  There is no input to this puzzle but your goal is to find an n for which you can get the highest score.
If there is a tie, the first answer wins.  In the extremely unlikely situation where someone finds a way to get an infinite score, that person wins immediately.
Task
Your task is simply to write code that gets the highest score.  Your code will have to both choose an n cleverly and then also optimize the number of weighings for that n.
Leading entries

4/3 7/5 in Python by Sarge Borsch
26/14 in Java by Peter Taylor

I'd love to get my hands on some anti-gravity coins.

@mbomb007 Just fill some balloons with helium :)

I have a solution that never uses the machine: Hold each coin and see which ones pull your hand up, and which pull your hand down.

Also, as a side note, it might be better to write "if you weigh coins a through b, then the next time you have to do a+1 through b+1" (maybe with an 'at least' thrown in too, and better formatting) instead of subscripts denoting the coin number. That makes it seem like it's some property or quantity of coin _, instead of the coin itself.

@QPaysTaxes Your first solution would count as n weighings with a score of 1.

@Lembik Aw, way to kill the fun :( (but yeah, I figured.)

Just to be sure, can you explain for every new weighing you get to choose if you want to put coin 0 on the scale.? Does this mean that if I choose to weigh two at once, I can weigh (x_0, x_1, x_2), (x_2, x_3), ... (x_0?, x_j-1, x_j), aka some of them with x_0?

... or if I choose to weigh 2 at a time from x_3 to x_8, must they either all or none be weighed with x_0 on the scale?

@mbomb007 At each weighing you can choose to weigh coin 0 as well as all the other coins you will be weighing. In other words, you have new choice to make for each weighing you do.

@mbomb007 @QPaysTaxes Regarding the notation x_i: We can have for example a first weighing of (x_1, x_2, x_3) = (3, 2, 7), and then the second weighing can be either (4, 3, 8) or (0, 4, 3, 8). The coin labels need not be consecutive, and the index i in x_i does not refer to the label of the coin.

Does the task define a standard way of testing solutions?

@SargeBorsch It doesn't. I think you can do it in 3^{n/2} time fairly easily. There may be a faster way of course.

I wrote some new code and got 1.4 score (was 1.33…)

btw I think that part of my code could be extracted and used to test any other solutions, but I'm too lazy to do it myself right now.

@MitchSchwartz Oh. Okay. The OP really needed some examples, because the wording was terribly vague. After looking at your answer, I understand.

C++, Score 23/12 25/13 27/14 28/14 = 2 31/15
The solutions of Matrix property X revisited (or the Joy of X) are directly usable as solutions to this problem. E.g. the solution of 31 rows 15 columns:
1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0
1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1
1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1
1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0
1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1
0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1
1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1
0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0
0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0
1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1
0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0
0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0
1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1

row N represent which coins you put on the scale for measurement N. Whatever the results of the weighting you get, there is obviously some set of coin values that gives that weight. If there is another combination too (the solution is not unique) consider how they differ. You must replace a set of coins weighting 1 by coins weighting -1. This gives a set of columns that correspond to that flip. There is also set of coins weighting -1 that you replace by 1. That is another set of columns. Because the measurements do not change between the two solutions that means the column sums of the two sets must be the same. But the solutions to Matrix property X revisited (or the Joy of X) are exactly these matrices where such column sets do not exist, so there are no duplicates and each solution is unique.
Each actual set of measurements can be described by some 0/1 matrix. But even if some column sets sum to the same vectors it could be that signs of the candidate solution coin values do not exactly correspond to such a set. So I don't know if matrices such as the one above are optimal. But at least they provide a lower bound. So the possibility that 31 coins can be done in less that 15 measurements is still open.
Notice that this is only true for a non fixed strategy where your decision to put coin 0 on the scales depends on the result of the previous weightings. Otherwise you will have solutions where the signs of the coins correspond with the sets that have the same column sum.

The current world record :)

How fast a computer do you estimate would be needed to get to 2?

@Lembik I'm not convinced 2 is possible. I don't know why, but the current results suggest you can only approach 2 arbitrarily close without ever reaching it

Did you get a chance to verify the 25 by 50 circulant matrix I pasted which should give 2? 01011011100010111101000001100111110011010100011010  as the first row of a circulant matrix.

I don't know how to even check that matrix without writing a dedicated program that will run for a long time

In theory it should take something like 2^(50/2) time to check maybe? I think that is slightly wrong but the idea is to use a "meet in the middle" approach.

Score = 26/14 ~= 1.857
import java.util.*;

public class LembikWeighingOptimisation {

    public static void main(String[] args) {
        float best = 0;
        int opt = 1;
        for (int n = 6; n < 32; n+=2) {
            long start = System.nanoTime();
            System.out.format("%d\t", n);
            opt = optimise(n, n / 2 + 1);
            float score = n / (float)opt;
            System.out.format("%d\t%f", opt, score);
            if (score > best) {
                best = score;
                System.out.print('*');
            }
            System.out.format(" in %d seconds", (System.nanoTime() - start) / 1000000000);
            System.out.println();
        }
    }

    private static int optimise(int numCoins, int minN) {
        MaskRange.N = numCoins;
        Set<MaskRange> coinSets = new HashSet<MaskRange>();
        coinSets.add(new MaskRange(0, 0));

        int allCoins = (1 << numCoins) - 1;

        for (int n = minN; n < numCoins; n++) {
            for (int startCoins = 1; startCoins * 2 <= numCoins; startCoins++) {
                for (int mask = (1 << startCoins) - 1; mask < (1 << numCoins); ) {
                    // Quick-reject: in n turns, do we cover the entire set?
                    int qr = (1 << (n-1)) - 1;
                    for (int j = 0; j < n; j++) qr |= mask << j;
                    if ((qr & allCoins) == allCoins && canDistinguishInNTurns(mask, coinSets, n)) {
                        System.out.print("[" + Integer.toBinaryString(mask) + "] ");
                        return n;
                    }

                    // Gosper's hack to update
                    int c = mask & -mask;
                    int r = mask + c;
                    mask = (((r^mask) >>> 2) / c) | r;
                }
            }
        }

        return numCoins;
    }

    private static boolean canDistinguishInNTurns(int mask, Set<MaskRange> coinsets, int n) {
        if (n < 0) throw new IllegalArgumentException("n");
        int count = 0;
        for (MaskRange mr : coinsets) count += mr.size();
        if (count <= 1) return true;
        if (n == 0) return false;

        // Partition.
        Set<MaskRange>[] p = new Set[Integer.bitCount(mask) + 1];
        for (int i = 0; i < p.length; i++) p[i] = new HashSet<MaskRange>();
        for (MaskRange range : coinsets) range.partition(mask, p);

        for (int d = 0; d < 2; d++) {
            boolean ok = true;
            for (Set<MaskRange> s : p) {
                if (!canDistinguishInNTurns((mask << 1) + d, s, n - 1)) {
                    ok = false;
                    break;
                }
            }

            if (ok) return true;
        }

        return false;
    }

    static class MaskRange {
        public static int N;
        public final int mask, value;

        public MaskRange(int mask, int value) {
            this.mask = mask;
            this.value = value & mask;
            if (this.value != value) throw new IllegalArgumentException();
        }

        public int size() {
            return 1 << (N - Integer.bitCount(mask));
        }

        public void partition(int otherMask, Set<MaskRange>[] p) {
            otherMask &= (1 << N) - 1;

            int baseline = Integer.bitCount(value & otherMask);
            int variables = otherMask & ~mask;
            int union = mask | otherMask;
            partitionInner(value, union, variables, baseline, p);
        }

        private static void partitionInner(int v, int m, int var, int baseline, Set<MaskRange>[] p) {
            if (var == 0) {
                p[baseline].add(new MaskRange(m, v));
            }
            else {
                int lowest = var & (1 + ~var);
                partitionInner(v,          m, var & ~lowest, baseline, p);
                partitionInner(v | lowest, m, var & ~lowest, baseline + 1, p);
            }
        }

        @Override
        public String toString() {
            return String.format("(x & %x = %x)", mask, value);
        }
    }
}

Save as LembikWeighingOptimisation.java, compile as javac LembikWeighingOptimisation.java, run as java LembikWeighingOptimisation.
Many thanks to Mitch Schwartz for pointing out a bug in the first version of the quick-reject.
This uses some fairly basic techniques which I can't rigorously justify. It brute-forces, but only for starting weighing operations which use at most half of the coins: sequences which use more than half of the coins aren't directly transferable to the complementary weighings (because we don't know the total weight), but on a hand-wavy level there should be about the same amount of information. It also iterates through starting weighings in order of the number of coins involved, on the basis that that way it covers dispersed weighings (which hopefully give information about the top end relatively early) without first crawling through a bunch which start with a dense subset at the bottom end.
The MaskRange class is a massive improvement on the earlier version in terms of memory usage, and removes GC from being a bottleneck.
20      [11101001010] 11        1.818182* in 5364 seconds
22      [110110101000] 12       1.833333* in 33116 seconds
24      [1000011001001] 13      1.846154* in 12181 seconds
26      [100101001100000] 14    1.857143* in 73890 seconds

Can you definitely not get 12/7? I am pretty sure that works. Also, how about 19/10? I thought my code gave me that once but I can't reproduce it now.

@Lembik, I've listed 12/7, but the best I can do for 19 is 19/11.

Oh yes sorry. Is it possible your heuristic throws away some solutions? I am pretty sure 19/10 should work too.

It's possible, yes, if the only solution has an initial weighing with more than half of the coins. I'd be mildly surprised, though.

Is it worth increasing the half threshold to slightly-more-than-half maybe just to see?

26/14 is great!

Python 2, score = 1.0
This is the easy score, in case nobody finds a better score (doubtful). n weighings for each n.
import antigravity
import random

def weigh(coins, indices):
    return sum(coins[i] for i in indices)

def main(n):
    coins = [random.choice([-1,1]) for i in range(n)]
    for i in range(len(coins)):
        print weigh(coins, [i]),

main(4)

I imported antigravity so the program can work with negative weights.

Very helpful. Thank you :)

Importing antigravity is basically a no-op, right?

@SargeBorsch For the purpose of this program, it is. But it does actually do something.

Python 3, score = 4/3 = 1.33… (N = 4) score = 1.4 (N = 7)
Update: implemented brute-force search in "static" solvers set, and got a new result
I think it can be further improved by searching for dynamic solvers, which can use weighting results for further decisions.
Here is a Python code that searches through all static solvers for small n values (these solvers always weigh the same coin sets, hence "static" name) and determines their worst case number of steps by simply checking that their measurement results allow only one matching coin set in all cases. Also, it keeps track of best score found so far and early prunes solvers which had shown that they are definitely worse than those which were found before. This was an important optimization, otherwise I could not wait for this result with n = 7.
(But it's clearly still not very well optimized)
Feel free to ask questions if it's not clear how it works…
#!/usr/bin/env python3
import itertools
from functools import partial

def get_all_possible_coinsets(n):
    return tuple(itertools.product(*itertools.repeat((-1, 1), n)))

def weigh(coinset, indexes_to_weigh):
    return sum(coinset[x] for x in indexes_to_weigh)

# made_measurements: [(indexes, weight)]
def filter_by_measurements(coinsets, made_measurements):
    return filter(lambda cs: all(w == weigh(cs, indexes) for indexes, w in made_measurements), coinsets)

class Position(object):
    def __init__(self, all_coinsets, coinset, made_measurements=()):
        self.all_coinsets = all_coinsets
        self.made_measurements = made_measurements
        self.coins = coinset

    def possible_coinsets(self):
        return tuple(filter_by_measurements(self.all_coinsets, self.made_measurements))

    def is_final(self):
        possible_coinsets = self.possible_coinsets()
        return (len(possible_coinsets) == 1) and possible_coinsets[0] == self.coins

    def move(self, measurement_indexes):
        measure_result = (measurement_indexes, weigh(self.coins, measurement_indexes))
        return Position(self.all_coinsets, self.coins, self.made_measurements + (measure_result,))

def get_all_start_positions(coinsets):
    for cs in coinsets:
        yield Position(coinsets, cs)

def average(xs):
    return sum(xs) / len(xs)

class StaticSolver(object):
    def __init__(self, measurements):
        self.measurements = measurements

    def choose_move(self, position: Position):
        index = len(position.made_measurements)
        return self.measurements[index]

    def __str__(self, *args, **kwargs):
        return 'StaticSolver({})'.format(', '.join(map(lambda x: '{' + ','.join(map(str, x)) + '}', self.measurements)))

    def __repr__(self):
        return str(self)

class FailedSolver(Exception):
    pass

def test_solvers(solvers, start_positions, max_steps):
    for solver in solvers:
        try:
            test_results = tuple(map(partial(test_solver, solver=solver, max_steps=max_steps), start_positions))
            yield (solver, max(test_results))
        except FailedSolver:
            continue

def all_measurement_starts(n):
    for i in range(1, n + 1):
        yield from itertools.combinations(range(n), i)

def next_measurement(n, measurement, include_zero):
    shifted = filter(lambda x: x < n, map(lambda x: x + 1, measurement))
    if include_zero:
        return tuple(itertools.chain((0,), shifted))
    else:
        return tuple(shifted)

def make_measurement_sequence(n, start, zero_decisions):
    yield start
    m = start
    for zero_decision in zero_decisions:
        m = next_measurement(n, m, zero_decision)
        yield m

def measurement_sequences_from_start(n, start, max_steps):
    continuations = itertools.product(*itertools.repeat((True, False), max_steps - 1))
    for c in continuations:
        yield tuple(make_measurement_sequence(n, start, c))

def all_measurement_sequences(n, max_steps):
    starts = all_measurement_starts(n)
    for start in starts:
        yield from measurement_sequences_from_start(n, start, max_steps)

def all_static_solvers(n, max_steps):
    return map(StaticSolver, all_measurement_sequences(n, max_steps))

def main():
    best_score = 1.0
    for n in range(1, 11):
        print('Searching with N = {}:'.format(n))
        coinsets = get_all_possible_coinsets(n)
        start_positions = tuple(get_all_start_positions(coinsets))

        # we are not interested in solvers with worst case number of steps bigger than this
        max_steps = int(n / best_score)

        solvers = all_static_solvers(n, max_steps)
        succeeded_solvers = test_solvers(solvers, start_positions, max_steps)

        try:
            best = min(succeeded_solvers, key=lambda x: x[1])
        except ValueError:  # no successful solvers
            continue
        score = n / best[1]
        best_score = max(score, best_score)
        print('{}, score = {}/{} = {}'.format(best, n, best[1], score))
    print('That\'s all!')

def test_solver(start_position: Position, solver, max_steps):
    p = start_position
    steps = 0
    try:
        while not p.is_final():
            steps += 1
            if steps > max_steps:
                raise FailedSolver
            p = p.move(solver.choose_move(p))
        return steps
    except IndexError:  # solution was not found after given steps — this solver failed to beat score 1
        raise FailedSolver

if __name__ == '__main__':
    main()

The output:
Searching with N = 1:
(StaticSolver({0}), 1), score = 1/1 = 1.0
Searching with N = 2:
(StaticSolver({0}, {0,1}), 2), score = 2/2 = 1.0
Searching with N = 3:
(StaticSolver({0}, {0,1}, {0,1,2}), 3), score = 3/3 = 1.0
Searching with N = 4:
(StaticSolver({0,1}, {1,2}, {0,2,3}, {0,1,3}), 3), score = 4/3 = 1.3333333333333333
Searching with N = 5:
Searching with N = 6:
Searching with N = 7:
(StaticSolver({0,2}, {0,1,3}, {0,1,2,4}, {1,2,3,5}, {0,2,3,4,6}), 5), score = 7/5 = 1.4
Searching with N = 8:
Searching with N = 9:
(I gave up waiting at this moment)

This line
(StaticSolver({0,2}, {0,1,3}, {0,1,2,4}, {1,2,3,5}, {0,2,3,4,6}), 5), score = 7/5 = 1.4 uncovers the best solver found. The numbers in {} braces are the indices of coins to put on weighting device at each step.

P.S. I wrote this while the electricity source in my home was broken, so I had a laptop on battery power and no Internet connectivity, and I simply had no better things to do than to crack some puzzles. I guess I'd not bother if all was fine :D


text:
ASCII Character Jumble
Write a program that takes as its input a string consisting of printable characters (ASCII 20-7E) and an integer n in [2,16] and performs the following modification to the string.

Each character in the string is converted to its ASCII code (the examples given are in hexadecimal, though base 10 is also acceptable).
The ASCII codes are converted to base n and are concatenated together.
The new string is split every other character. If there are an odd number of characters, then the last character is removed entirely.
Printing ASCII codes (in base 16) are converted back into their characters, whereas non-printing ASCII codes are removed.
The resulting string is printed.

Test case
Input
Hello, World!
6

Steps
Hello, World!
48 65 6C 6C 6F 2C 20 57 6F 72 6C 64 21
2002453003003031125222330331030024453
20 02 45 30 03 00 30 31 12 52 22 33 03 31 03 00 24 45

The output of this program is  E001R"31$E.

This is code golf, so standard rules apply. Shortest code in bytes wins.

This encoding algorithm can be useful for sending secret messages!

Gotta do this sometime!

@ΚριτικσιΛίθος while the program works for every possible input string, not every output string is unique. For example, in base 7, the string J would go through the steps J -> 50 -> 101 -> 10 -> (no output), as would the string K or L.

Like @Eridan said, this is a lossy encryption since odd sequences get the last character lopped off. Though I'm sure to the ignorant observer it could be a snarky way of communicating :)

Can a function be written?

Step 1 is confusing - no need to convert chars to hexadecimal - in the example: H is ASCII 72 (decimal) or 48 (hex), but what I need is 200 (base 6). All the row 2 in the example is useless and confusing in my opinion

@edc65 You're right about not needing the hex codes, though that's what I tend to prefer when looking at an ASCII table. I have changed the instructions, but the examples are how I would look at the problem.

Pyth - 22 bytes
Hope to golf a lot more, pretty straightforward.
sfq3l`TmCid16csjRQCMz2

Try it online here.

q3l`T is wonderful.

Shouldn't fgTd be enough?

CJam, 33 bytes
q~:i\fb:~0+2/W<Gfb:c' ,-'ÿ),127>-

Takes input in the form 6 "Hello, World!". Test it here.
See Dennis's answer for a similar but better solution with a nice explanation.

Bash + common linux utils, 118
printf %s "$1"|xxd -p|sed -r "s/../\U& /g;y/ /n/;s/^/dc -e$2o16i/e;s/../& /g;s/ .$//;"|xxd -rp|sed 's/[^[:print:]]//g'

I think you could shorten printf %s "$1" into echo -n "$1" to save 2 bytes

@Aaron That works until the input string is -e.  Try echo -n "-e"

Damn, nicely spotted !

JavaScript (ES6), 137 147
Using the most verbose functions available in JavaScript

f=(s,b)=>alert(s.replace(/./g,x=>x.charCodeAt().toString(b)).match(/../g).map(x=>(x=String.fromCharCode('0x'+x))<='~'&x>' '?x:'').join``)

// Just for test purpose, redefine alert()
alert=x=>document.write('<pre>'+x+'</pre>')

f('Hello, World!',6)
f('PORK',3)

I think you can save some bytes by using [for(z of ...)if(...)...] instead of map(...).filter(...)

@Ypnypn I did not found a way to use your hint (apart from using array comprehension that is ES7) but you pressed me to rethink it all. Thx. I hope you'll keep your +1 even if x=>x>= has gone

What's wrong with using ES7?

@Ypnypn I prefer an answer that can work even with subpar javascript engines like Chrome</troll off>

@edc65 +1 because Chrome is subpar! (Please don't lynch me internet!) But why have you opened <troll on> then closed <troll off>?

CJam, 24 bytes
l:irifbe_2/{Gbc',32>&}/

Note that there is a DEL character (0x7F) between ' and ,. Try it online in the CJam interpreter.
How it works
l:i                     Read a line from STDIN and cast each char to integer.
   ri                   Read another integer (base) from STDIN.
     fb                 Convert each integer from line 1 to that base.
       e_2/             Flatten and split into chunks of length 2.
                        If the last chunk has only one element, it will get
                        converted into a control character, which will be
                        removed later.
          {         }/  For each digit pair:
           Gb             Convert the pair from base 16 to integer.
             c            Cast to character.
              ',          Push the string of ASCII characters up to '~'.
                32>       Remove the first 32 (control characters).
                   &      Intersect.

What about the DEL character...? It looks like you've worked around that, but I can't see it in your explanation!

StackExchange filters unprintable characters. The DEL character is only present in thr permalink, and invisible even there.

I mean... Delete is a control character, but is not one of the first 32 characters. It is character number 127, 0x7F, for people who are not familiar with ASCII.

I'm not sure I understood your question. Are you wondering how I filter it from the output?

Yes. Your code explanation doesn't seem to say how you filter the DEL character from the output.

@wizzwizz4 , pushes an exclusive range; '<DEL>, pushes the string of all ASCII characters with code points strictly below 127. 32> removes the remaining control characters from that string, and & intersects the character on the stack with the generated string of printable ASCII characters. For each character, this gives either a singleton or an empty string.

Your explanation says it pushes them up to ~... :facepalm: Up to and including ~. Ok, I understand now. Thanks for taking the time to explain it.

Julia, 118 bytes
f(s,n)=join(map(i->(c=string(Char(parse(Int,i,16))))^isprint(c),matchall(r"..",join(map(i->base(n,Int(i)),[s...])))))

Ungolfed:
function f(s::AbstractString, n::Integer)
    # Construct an array of ASCII codes in base n
    v = map(i -> base(n, Int(i)), [s...])

    # Join into a string and get all pairs, truncating
    # to an even length
    m = matchall(r"..", join(v))

    # Parse each pair as an integer in base 16, get the
    # character associated with that code point, convert
    # to a string, and include if it's printable
    x = map(i -> (c = string(Char(parse(Int, i, 16)))^isprint(c), m)

    # Join as a string and return
    return join(x)
end

TeaScript, 23 bytes
TeaScript is JavaScript for golfing
£lc¡T(y©K(2)ßC(P(l,16±µ

Relatively straight-forward but delightfully short. I can probably golf down a few more characters with some more operators. A few other new features might also be able to be used to cut down some bytes.
Ungolfed && Explanation
x.l(#
    l.c().T(y)
).K(2)
.m(#
    C(
      P(l,16)
    )
).j``

I believe this is 23 chars (29 bytes) long.

@w0lf That would be with UTF-8 encoding but because all characters are less then 256 we can safely count them as one byte

Mathematica, 134 bytes
Print@FromCharacterCode@Select[#~FromDigits~16&/@StringPartition[""<>ToCharacterCode@InputString[]~IntegerString~Input[],2],31<#<127&]

If a function is allowed:
Mathematica, 112 bytes
FromCharacterCode@Select[#~FromDigits~16&/@StringPartition[""<>ToCharacterCode@#~IntegerString~#2,2],31<#<127&]&

Ruby 92
->s,n{o=''
s.chars.map{|x|x.ord.to_s n}.join.scan(/../).map{|x|x>?2&&x<?8&&o<<x.to_i(16)}
o}

Online test here.

Python 2, 174 bytes
def J(a,b,i=0):
 h=r=''
 B=lambda n,b:n*'x'and B(n/b,b)+chr(48+n%b+7*(n%b>9))
 for c in a:h+=B(ord(c),b)
 while i<len(h):v=int(h[i:i+2],16);r+=chr(v)*(31<v<127);i+=2
 print r

Try it here
Not really the best tool for the job. Since Python has no convert-to-arbitrary-base function, I had to implement my own. That was fun, at least--particularly finding a [marginally] shorter expression for the digits than "0123456789ABCDEF"[n%b]. For iterating over two characters at a time, I found a while loop was slightly shorter than a functional approach.
181 bytes as a full program:
B=lambda n,b:n*'x'and B(n/b,b)+chr(48+n%b+7*(n%b>9))
a=raw_input()
b=input()
h=r=''
for c in a:h+=B(ord(c),b)
i=0
while i<len(h):v=int(h[i:i+2],16);r+=chr(v)*(31<v<127);i+=2
print r

Vyxal s, 13 bytes
C$vτHfṅǒHCkQ↔

Try it Online!

MATLAB, 103 bytes
function k(s,n),b=dec2base(s,n)';b(~cumsum(b-'0',1))='';c=base2dec(textscan(b,'%2c'),16)';char(c(c>31))

I've written a function k that takes a string s and an integer n as input. e.g.:
k('Hello, World!',6)

gives
 E001R"31$E

Most annoying thing I had to work around is leading zeros showing up when converting to base n. Getting these out of the array that was to be split after every 2nd character cost quite a lot of bytes. Not sure if it is possible to save any more bytes using this approach.

PHP - 286 bytes
Put the string in $s and the integer in $b.
<?php $s=$_GET["s"];$b;$m="array_map";echo implode($m(function($v){return ctype_print($v)?$v:"";},$m("chr",$m("hexdec",str_split(strlen(implode($a=$m(function($v){global$b;return base_convert($v,16,$b);},$m("dechex",$m("ord",str_split($s))))))%2==1?substr(implode($a),0,-1):$a,2)))));?>

Pass the value to GET["s"].

Ly, 26 bytes
ir[sp>lS<]>ry[puu' oy1G*]p

Try it online!
This code uses the S instruction to convert the codepoints to digits one input character at a time.  Then it just prints pairs of digits delimited with spaces from the accumulation stack.
ir
i                          - read input as codepoints
 r                         - reverse stack
  [      ]                 - for each input char/codepoint...
   sp                      - stash codepoint and delete
     >l                    - switch to accum stack, load codepoint
       S                   - convert codepoint to digits
        <                  - switch back to input stack
          >r               - switch to accum stack, reverse digits
            y[          ]  - loop until stack size is <2
              p            - delete loop iterator artifact
               uu          - print two digits
                 ' o       - print a space
                    y1G    - is the stack size >1?
                       *   - multiple to combine top two of stack
                         p - print iterator artifact

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/