# Question
Title: Little Chandler is sad. Draw him a cloud to cheer him up
Little Chandler is sad. Draw him a cloud to cheer him up.
*Note: Drawing a cloud won't actually cheer him up.*

A circle can be defined as a 3-tuple `(x,y,r)` where `x` is the x position of the circle on a Cartesian plane, `y` is the y position of the circle on a Cartesian plane, and `r` is the radius of the circle. `x` and `y` may be negative. `r` is always positive. The input is a list of circles in the form of space separated 3-tuples. For instance:

```
3,1,1 3,2,1.5 1,2,0.7 0.9,1.2,1.2 1,0,0.8

```

The `3,1,1` means "A circle with centre point at `3,1` with 1 radius. `3,2,1.5` means "A circle with centre point at `3,2` with 1.5 radius.

If we draw all of these circles of the input on a graph, it looks like this (I've included grid lines and labels for clarity only; they are not required):

Notice how all the circles are *cohesive*. That is, they're all overlapped together such that it forms one large group without any small groups of circles separated from the rest. The input is *guaranteed* to be cohesive.

Suppose now we draw a line that travels around the "border" formed by these circles, without any of the other lines. It would be like drawing the border of the silhouette formed by all the circles. The resulting cloud would look something like this:

So this cloud has been formed by drawing only the arcs of the circles in the input that form a border, resulting in a single shape. In other words, the cloud is formed by only drawing the arcs that are not within another circle. Your program will take in input in the form explained above, and output an image that displays the resulting cloud. The overall shape of the cloud must be correct, but the scale, colour, line thickness, and how it looks at vertexes is up to you. Note that the cloud must be visible, so you can't pull something like "This program draws a white cloud on a white background", "This program draws a cloud at a infinitesimally small scale", "This program draws a cloud with 0 line thickness", etc. Also note that the colour of the border must be different from the colour of the fill or background.

Another example. Input:

```
1,4,2 5,2,1 3,1,1 3.5,2,1.2 3,3,0.7 1,2,0.7

```

Output:

If there is a "hole" in the cloud, you should draw the hole as well. Input:

```
0,5,4 3,4,4 4,3,4 5,0,4 4,-3,4 3,-4,4 0,-5,4 -3,-4,4 -4,-3,4 -5,0,4 -4,3,4 -3,4,4

```

Output:

Here is an important rule: your program must draw *only* the lines that form the border. This means that you CANNOT simply draw the circles fully, and then draw the circles slightly smaller with a white fill -- because that method still draws lines that don't form a border, it just covers them up afterwards. The purpose of the rule was to prevent the "draw the circles, then draw the circles again with a white fill" implementations, or anything similar to that. The answer is expected to actually calculate where to draw things before drawing it.

This is code golf, so the shortest character count wins.

# Answer
# Mathematica ~~177 126 121~~ 119

## Solving by Disk Regions: the mathematician's approach

The logic is to

* Create Region 1 (R1), the circles (without their interiors);
* Create Region 2 (R2), the disks (without the circle borders).
* Create Region 3 (R3 = R1-R2).
\-

This is precisely the approach taken below. It produced the 3 figures above.

```
input = "3,1,1 3,2,1.5 1,2,0.7 0.9,1.2,1.2 1,0,0.8";
circles = ((x - #)^2 + (y - #2)^2 == #3^2) & @@@
     ToExpression[#~StringSplit~","] &@(StringSplit@input);
R1 = ImplicitRegion[Or @@ circles, {x, y}];
r1 = RegionPlot[R1, PlotLabel -> "R1: circles containing borders",
   AspectRatio -> 1, PlotRange -> {{-1, 5}, {-1, 5}}];

innerDisks = ((x - #)^2 + (y - #2)^2 < #3^2) & @@@
     ToExpression[#~StringSplit~","] &@(StringSplit@input);
R2 = ImplicitRegion[Or @@ innerDisks, {x, y}];
r2 = RegionPlot[R2, PlotLabel -> "R2: disks within circle borders",
   AspectRatio -> 1, PlotRange -> {{-1, 5}, {-1, 5}}];
R3 = RegionDifference[R1, R2]
r3 = RegionPlot[R3, PlotLabel -> "R3 = R1-R2", AspectRatio -> 1,
   PlotRange -> {{-1, 5}, {-1, 5}}];
GraphicsGrid[{{r1, r2, r3}}, ImageSize -> 600]

```

Implicit region #1 is the union of the circles. Implicit region #2 is the union of the disks lying within the circles. Their difference is the border.

> RegionDifference\[
> ImplicitRegion\[(-3 + x)^2 + (-1 + y)^2 == 1 || (-3 + x)^2 + (-2 + y)^2 == 2.25 || (-1 + x)^2 + (-2 + y)^2 == 0.49 || (-0.9 + x)^2 + (-1.2 + y)^2 == 1.44 || (-1 + x)^2 + y^2 == 0.64, {x, y}\],
> ImplicitRegion\[(-3 + x)^2 + (-1 + y)^2 \< 1 || (-3 + x)^2 + (-2 + y)^2 \< 2.25 || (-1 + x)^2 + (-2 + y)^2 \< 0.49 || (-0.9 + x)^2 + (-1.2 + y)^2 \< 1.44 || (-1 + x)^2 + y^2 \< 0.64, {x, y}\]\]

---

## Solving by Disk Regions: the engineer's approach (119 chars)

The following takes the union of the disk regions, discretizes that region, and finds it's boundary. The points in the diagram demarcate the intervals of the Delaunay mesh. We display the discretized region below to highlight the object that furnishes the boundary of interest (the outline of the cloud).

```
s = StringSplit;RegionBoundary@DiscretizeRegion[RegionUnion[Disk[{#, #2}, #3] &@@@
ToExpression[#~s~","] &@(s@InputString[])]]

```

**"3,1,1 3,2,1.5 1,2,0.7 0.9,1.2,1.2 1,0,0.8"**

The region boundary is discretized.

---

## Solving by Detecting Edges: The Photographer's Approach - 121 chars

It draws the disks in black, rasterizes the image, detects the edges, and inverts black and white.

```
s=StringSplit;ColorNegate@EdgeDetect@Rasterize@Graphics[Disk[{#,#2},#3]&@@@
((ToExpression/@s[#,","])&/@s[InputString[]])]

```
> 26 votes

# Answer
# T-SQL ~~235~~ ~~234~~ ~~229~~ ~~212~~ ~~171~~ 73 bytes

This makes use of spatial functionality in SQL Server 2012+. When it is run in SSMS (SQL Server Management Studio) is produces a spatial results pane. ~~The input is from variable @i. I could reduce it further if the input could be taken from a table.~~

Since table input is now allowed.

```
SELECT Geometry::UnionAggregate(Geometry::Point(X,Y,0).STBuffer(R))FROM A

```

I've left the previous solution below.

```
DECLARE @ VARCHAR(999)='WITH a AS(SELECT *FROM(VALUES('+REPLACE(@i,' ','),(')+'))A(X,Y,R))SELECT Geometry::UnionAggregate(Geometry::Point(X,Y,0).STBuffer(R))FROM a'EXEC(@)

```

**Edit**: Remove stray space, surplus **into** and subquery

171: Replaced table creation with CTE and @s with @.

Break down of the Dynamic SQL

```
DECLARE @i VARCHAR(100) = '1,4,2 5,2,1 3,1,1 3.5,2,1.2 3,3,0.7 1,2,0.7' -- Input
DECLARE @ VARCHAR(999) = '
WITH a AS(                                       --CTE to produce rows of x,y,r
    SELECT *FROM(VALUES('+
        REPLACE(@i,' ','),(')                    --Format @i to a value set
        +'))A(X,Y,R)
)
SELECT Geometry::UnionAggregate(                 --Aggregate Buffered Points
    Geometry::Point(X,Y,0).STBuffer(R)           --Create point and buffer
    )
FROM a                                           --from the table variable
'
EXEC(@)                                          --Execute Dynamic sql

```
> 28 votes

# Answer
## Mathematica, ~~175~~ ~~158~~ 149 bytes

```
s=StringSplit;l=ToExpression[#~s~","]&@s@InputString[];RegionPlot[Or@@(Norm@{x-#,y-#2}<#3&@@@l),{x,m=Min@(k={{##}-#3,{##}+#3}&@@@l),M=Max@k},{y,m,M}]

```

I remember from discussion in the sandbox that this approach was supposed to be valid, but I'm not entirely sure how it sits with the new wording of the rules, so @Lilac, let me know if you think this violates the rules.

Basically, I'm creating a logical condition which is true for all points inside the cloud and false for all points outside it. I'm feeding that to `RegionPlot` which then renders the region of all points where the expression is `True` as well as an outline around it.

Ungolfed:

```
s = StringSplit;
l = ToExpression[#~s~","] &@s@InputString[];
RegionPlot[
 Or @@ (Norm@{x - #, y - #2} < #3 & @@@ l),
 {x, m = Min@(k = {{##} - #3, {##} + #3} & @@@ l), M = Max@k},
 {y, m, M}
]

```
> 23 votes

# Answer
## Python 3.3 (183 177 164 160 bytes)

```
B=list(map(eval,input().split()))
print("".join(" ## "[sum(any(r*r>(x-d%80/4+10)**2+(y+d//80/4-10)**2for
x,y,r in B)for d in[i,i+1,i+80])]for i in range(6400)))

```

It requires an 80 character wide console, which I know is the default in Windows. It works best if your console has a square font. Here are some excerpts from some of the test inputs.

**Original:**

```
           ########
          ##       #
         ##         #
     #####          #
    ##   #          #
   ##               #
  ##                #
 ##                 #
 #                  #
 #                 ##
  #               ##
  #       ##      #
   #      # #    ##
   #      #  #####
   #      #
    #    ##
     #  ##
      ###

```

**Another:**

```
    ########
  ###       ##
 ##           #
 #            #
##             #
#              #
#              #
#              #
#              #
#               ##
#                 #
 #                 ##
 #                   ######
  #                        #
   ##      ###             #
     #    ## #             #
     #    #  #             #
      #  ## ##             #
       ###  #             ##
            #       #######
            #      ##
            #      #
             #    ##
              #####

```

**Hole:**

```
                              ############
                            ###           ##
                          ###               ##
                         ##                   #
                  ########                     #######
                ###                                   ##
              ###                                       ##
             ##                                           #
            ##                                             #
           ##                                               #
          ##                                                 #
         ##                                                   #
        ##                                                     #
       ##                                                       #
      ##                                                         #
      #                                                          #
     ##                                                           #
     #                                                            #
    ##                                                             #
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
   ##                                                               #
  ##                                                                 #
  #                                                                  #
 ##                                                                   #
 #                                                                    #
##                                                                     #
#                                 ####                                 #
#                                ##   #                                #
#                               ##     #                               #
#                              ##       #                              #
#                              #        #                              #
#                              #        #                              #
#                               #      ##                              #
#                                #    ##                               #
#                                 #  ##                                #
#                                  ###                                 #
 #                                                                    ##
 #                                                                    #
  #                                                                  ##
  #                                                                  #
   #                                                                ##
    #                                                              ##
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
    #                                                              #
     #                                                            ##
     #                                                            #
      #                                                          ##
      #                                                          #
       #                                                        ##
        #                                                      ##
         #                                                    ##
          #                                                  ##
           #                                                ##
            #                                              ##
             #                                            ##
              #                                          ##
               ##                                      ###
                 ##                                  ###
                   #######                    ########
                          #                  ##
                           ##              ###
                             ##          ###
                               ###########

```
> 18 votes

# Answer
# Python - ~~253~~ ~~249~~ ~~215~~ 199

This is an advertisement for the awesome shapely library, whose geometry operations made writing the solution straightforward by drawing the outline(s) of the union of overlapping circles (=buffered points):

```
from pylab import*
from shapely.geometry import*
c=Point()
for s in raw_input().split():
 x,y,r=eval(s)
 c=c.union(Point(x,y).buffer(r))
plot(*c.exterior.xy)
for i in c.interiors:
 plot(*i.xy)
show()

```

Output:

Edit(s):

* 249: Replaced `sys.argv[1:]` by `raw_input().split()`, saving a `import sys`
* 215: Removed `k={'color':'k'}` luxury, replaced `savefig` by `show`
* 199: Replaced `map(float,s.split(','))` by `eval(s)`
> 15 votes

# Answer
## Python – 535

```
import math as m
import matplotlib.pyplot as l
c = "3,1,1 3,2,1.5 1,2,0.7 0.9,1.2,1.2 1,0,0.8"
a = [[float(y) for y in x.split(",")] for x in c.split(" ")]
for a2 in a:
    for x in xrange(0,200):
        q=x*m.pi/100.0
        p=(a2[0]+m.sin(q)*a2[2], a2[1]+m.cos(q)*a2[2])
        cc = []
        for z in a:
            if z != a2:
                if ((z[0] - p[0]) ** 2 + (z[1] - p[1]) ** 2 ) < (z[2] ** 2) :
                    cc.append(z)
        if not cc:
            l.scatter(p[0],p[1])
l.show()

```
> 11 votes

# Answer
## Python – ~~296~~ ~~249~~ ~~231~~ ~~223~~ 212

```
from pylab import*
a=map(eval,raw_input().split())
for x,y,r in a:
 for i in range(200):
  q=i*pi/100;p=x+r*sin(q);t=y+r*cos(q);[z for z in a if z!=(x,y,r)and(z[0]-p)**2+(z[1]-t)**2<z[2]**2]or scatter(p,t)
show()

```

Credit goes to @richard-green (permission was given) for the original solution, I've just whittled it down a bit.
> 9 votes

# Answer
# Python 274 bytes

This takes input from stdin and checks every point on the display, drawing the pixels one by one as it goes. Not exactly efficient but it follows all the rules.

```
c=[eval(s)for s in raw_input().split()]
import pygame
S=pygame.display.set_mode((500,500))
S.fill([255]*3)
for p in((x,y)for x in range(500)for y in range(500)if 0<min((((x-250)/25.-a)**2+((y-250)/25.-b)**2)**.5-r for(a,b,r)in c)<.1):S.set_at(p,[0]*3)
pygame.display.update()

```

Note that the pygame display will terminate as soon as the drawing is complete, I wasn't sure if I should include it as part of my answer but to view it you can either throw a `raw_input` in at the end or add a little loop if you want to stop the OS from complaining about it not responding and such:

```
alive = True
while alive:
    pygame.display.update()
    for e in pygame.event.get():
        if e.type == pygame.QUIT:
            alive = False

```

Example images:

`1,4,2 5,2,1 3,1,1 3.5,2,1.2 3,3,0.7, 1,2,0.7`

`0,5,4 3,4,4 4,3,4 5,0,4 4,-3,4 3,-4,4 0,-5,4 -3,-4,4 -4,-3,4 -5,0,4 -4,3,4 -3,4,4`
> 7 votes

# Answer
# JavaScript (E6) + HTML 322

JSFiddle

Each circle is subdivided in about 100 small arcs, and each arc is drawn if its middle point is not inside any of the other circles.

```
<canvas id='c'/>
<script>
t=c.getContext("2d"),z=99,c.width=c.height=400,
l=prompt().split(' ').map(c=>c.split(',').map(v=>40*v)),
l.map(c=>{
  for(i=z;--i+z;)
    s=4/z,r=c[2],x=c[0]+r*Math.cos(a=i*s),y=c[1]+r*Math.sin(a),
    t.beginPath(),
    l.some(q=>c!=q&(d=x-q[0],e=y-q[1],d*d+e*e<q[2]*q[2]))||t.arc(z+c[0],z+c[1],r,a-s,a+s),
    t.stroke()
})
</script>

```
> 7 votes

# Answer
## Perl - 430

```
@e=map{[map{int($_*32)}split',']}(split' ',<>);for$g(@e){for(0..3){($a[$_]>($q=$$g[$_&1]+(($_>>1)*2-1)*$$g[2]))^($_>>1)&&($a[$_]=$q)}}for(2,3){$a[$_]-=$a[$_-2]-1}for(@e){($x,$y,$r)=@$_;$x-=$a[0];$y-=$a[1];for$k($x-$r..$x+$r){for$l($y-$r..$y+$r){$i=(int(sqrt(($x-$k)**2+($y-$l)**2)+0.5)<=>$r)-1;$f[$l][$k]=($j=$f[$l][$k])<-1||$i<-1?-2:$i||$j;}}}print"P1
$a[2] $a[3]
".join("
",map{join' ',map{$_+1?0:1}@$_,('0')x($a[2]-@$_)}@f)."
"

```

Writes a pbm file to stdout.

Test image (converted to png):
> 3 votes

---
Tags: code-golf, math, graphical-output, geometry
---


title: Uncertainty in the Timeline of a Day

text:
# Question
Title: Uncertainty in the Timeline of a Day
Suppose your alarm wakes you up one morning, but you hit snooze so you can sleep for 8 more minutes. When it rings again you grudgingly get up and take a shower, which you estimate takes 15 to 17 minutes. You then brush your teeth for exactly 2 minutes, and get dressed, which takes about 3 to 5 minutes. Finally, you eat a hurried breakfast in 6 to 8 minutes and run out the door.

We can denote this timing sequence as `8 15-17 2 3-5 6-8`.

*Given the uncertainty of your morning's routine, what is the probability you were doing each task at some particular number of minutes since you first woke up?*

Assuming every task takes a whole number of minutes, we can chart every possible combination of uncertain time spans (e.g. 3, 4, and 5 minutes for brushing teeth). This chart shows all 27 possibilities, with time increasing to the right, and each task of N minutes represented by (N - 1) dashes and one vertical bar, just to mark its ending. The minute boundaries occur *between* characters, so the space between the `8` and `9` column is `8 min 59 sec` turning into `9 min`.

```
         1111111111222222222233333333334
1234567890123456789012345678901234567890  <-- Minute
-------|--------------|-|--|-----|
-------|--------------|-|--|------|
-------|--------------|-|--|-------|
-------|--------------|-|---|-----|
-------|--------------|-|---|------|
-------|--------------|-|---|-------|
-------|--------------|-|----|-----|
-------|--------------|-|----|------|
-------|--------------|-|----|-------|
-------|---------------|-|--|-----|
-------|---------------|-|--|------|
-------|---------------|-|--|-------|
-------|---------------|-|---|-----|
-------|---------------|-|---|------|
-------|---------------|-|---|-------|
-------|---------------|-|----|-----|
-------|---------------|-|----|------|
-------|---------------|-|----|-------|
-------|----------------|-|--|-----|
-------|----------------|-|--|------|
-------|----------------|-|--|-------|
-------|----------------|-|---|-----|
-------|----------------|-|---|------|
-------|----------------|-|---|-------|
-------|----------------|-|----|-----|
-------|----------------|-|----|------|
-------|----------------|-|----|-------|
1234567891111111111222222222233333333334  <-- Minute
         0123456789012345678901234567890

```

It is clear that the routine could have taken 40 minutes at most and 34 minutes at least.

The question is, at a particular minute, say minute 29, what is the chance you were doing each of the 5 tasks? Assume each uncertain time frame is uniformly distributed over the exact whole minutes. So a 4-7 task has 25% chance of taking 4, 5, 6, or 7 minutes.

From the chart it can be seen that at minute 29 there was a...

```
0/27 chance you were snoozing (task 1)
0/27 chance you were showering (task 2)
0/27 chance you were brushing (task 3)
24/27 chance you were dressing (task 4)
3/27 chance you were eating (task 5)

```

Similarly at minute 1 there was a `27/27` chance you were snoozing with `0/27` everywhere else.

At minute 38 for example, 17 of the potential routines have already ended. So in 10 out of 10 cases you will be eating. This means the probabilities look like

```
0/10 task 1, 0/10 task 2, 0/10 task 3, 0/10 task 4, 10/10 task 5

```

# Challenge

Write a *function* that takes an integer for the minute value, and a string consisting of a sequence of single integers, or pairs of integers `a-b` with `b` \> `a`, all separated by spaces (just like `8 15-17 2 3-5 6-8`). All the integers are positive. The input minute will be less than or equal to the maximum time possible (40 in example).

The function should return another string denoting the **unreduced** fractional chance of being in each task at the given minute.

# Examples

* `myfunc(29, "8 15-17 2 3-5 6-8")` returns the string `0/27 0/27 0/27 24/27 3/27`
* `myfunc(1, "8 15-17 2 3-5 6-8")` returns the string `27/27 0/27 0/27 0/27 0/27`
* `myfunc(38, "8 15-17 2 3-5 6-8")` returns the string `0/10 0/10 0/10 0/10 10/10`
* `myfunc(40, "8 15-17 2 3-5 6-8")` returns the string `0/1 0/1 0/1 0/1 1/1`

If your language does not have strings or functions you may use named variables, stdin/stdout, the command line, or whatever seems most appropriate.

# Scoring

This is code golf. The shortest solution in bytes wins.

# Answer
## CJam, ~~124 115 100 92~~ 89 bytes

This can be golfed a lot, but I have to sleep, so posting now itself :)

```
l~\:N;S/{'-/2*2<~i),\i>}%_{m*{(\+}%}*{[0\{1$+}*]}%:B;,,{0B{I>2<~N<!\N<*+}/}fI]_:+m*'/f*S*

```

Try it online here

Input is like:

```
29 "8 15-17 2 3-5 6-8"

```

Where first integer is the input minute and the second string is the time range sequence (as shown in examples in the question, just without the `,`)

Output for the above mentioned input:

```
0/27 0/27 0/27 24/27 3/27

```
> 3 votes

# Answer
## Mathematica, ~~237~~ 216 bytes

I'm sure I can shorten this a bit, but not now. At least I finally got to use the new associations from Mathematica 10! :)

```
f=(j=#;s=StringSplit;r=ToString;t=Lookup[Counts@Flatten[FirstPosition[#,n_/;n>=j]&/@Accumulate/@Tuples@i],#,0]&/@Range@Length[i=ToExpression[#~s~"-"&/@s@#2]/.{a_,b_}:>a~Range~b];Riffle[r@#<>"/"<>r@Tr@t&/@t," "]<>"")&

```

Ungolfed:

```
    f = (
   j = #;
   s = StringSplit;
   r = ToString;
   t = Lookup[
       Counts@Flatten[
         FirstPosition[#, n_ /; n >= j] & /@
          Accumulate /@ Tuples@i], #, 0] & /@
     Range@Length[
       i = ToExpression[#~s~"-" & /@ s@#2] /. {a_, b_} :> a~Range~b];
   Riffle[r@# <> "/" <> r@Tr@t & /@ t, " "] <> "") &

```

Usage as specified in the challenge:

```
f[29, "8 15-17 2 3-5 6-8"]

```

It returns `0/1` for all elements if the first input is larger than the maximum time span.
> 3 votes

# Answer
# Haskell, 232

```
f=(\(a,b)->[a..fst$head$reads(tail$b++" ")++[(a,b)]]).head.reads
n%l=(tail>>=zipWith(-))(0:map(\i->drop i&l*e[x|x<-map sum$mapM f$take i$w l,x>=n])[1..e$w l])>>=(++'/':show(id&l)++" ").show
(&)i=product.map(e.f).i.w
w=words
e=length

```

run like this:

```
*Main> putStrLn $ 1 % "8 15-17 2 3-5 6-8"
27/27 0/27 0/27 0/27 0/27

```
> 1 votes

# Answer
## APL, 162

```
{{⍵,'/',y}¨⌊|-2-/0,(y←+/,⍺≤⊃⌽x)×1,⍨¯1↓⍺{+/÷∘⍴⍨⍺≤,⍵}¨x←∘.+\{⊃{⍺,⍺↓⍳⍵}/⍎('-'⎕R' ')⍵}¨('\S+'⎕S'\0')⍵}

```

**Example runs**

```
      f←{{⍵,'/',y}¨⌊|-2-/0,(y←+/,⍺≤⊃⌽x)×1,⍨¯1↓⍺{+/÷∘⍴⍨⍺≤,⍵}¨x←∘.+\{⊃{⍺,⍺↓⍳⍵}/⍎('-'⎕R' ')⍵}¨('\S+'⎕S'\0')⍵}
      29 f '8 15-17 2 3-5 6-8'
 0 / 27  0 / 27  0 / 27  24 / 27  3 / 27

      1 f '8 15-17 2 3-5 6-8'
 27 / 27  0 / 27  0 / 27  0 / 27  0 / 27

      38 f '8 15-17 2 3-5 6-8'
 0 / 10  0 / 10  0 / 10  0 / 10  10 / 10

      40 f '8 15-17 2 3-5 6-8'
 0 / 1  0 / 1  0 / 1  0 / 1  1 / 1

```

I hope you don't mind the weird spacing
> 1 votes

---
Tags: code-golf, probability-theory
---


title: Generating a Student Timetable

text:
# Question
Title: Generating a Student Timetable
## Introduction

You are the computer science teacher in a large high school and have been tasked to create a system to generate the student timetables. You must, given a JSON dictionary of student names and the subjects they are taking, you must generate a timetable for each of the students.

## Specifications

Each student takes seven subjects (English Literature, English Language and Maths are compulsory but don't count towards the seven subjects):

```
Subject name - Abbreviation

Art - Ar
Biology - Bi
Business Studies - Bu
Chemistry - Ch
Computer Science - CS
French - Fr
Geography - Gg
History - Hi
IT - IT
Mandarin - Cn
Music - Mu
PE - PE
Physics - Ph
Spanish - Sp

Compulsory:

English Language - La
English Literature - Li
Maths - Ma

Other:

Tutor - Tu
Free - Ac

```

All abbreviations must be in the same case as above.

Each day has ten periods of lessons. A lesson can either span a single period or a double period. There must be three lessons of each subject with each having one double lesson (double period length) and two single lessons. The only exception to this rule is English Language which only occurs once a week and is a double.

There must be only one lesson of the same subject a day.

A school day is Monday to Friday.

Between periods 3 and 4 and between periods 5 and 6, there is a break. Lessons must not be placed over a break. From period six inclusive on a Wednesday to the end of the day, there are free periods. Period 1 on a Tuesday is Tutor period. Period 10 on a Friday is also Tutor. Period 10 on a Thursday is a free period.

Lessons must not be split into multiple groups meaning that people studying the same subject must be together in those subjects. Students may have any number of frees.

You must use the subject's abbbreviation in the timetable.

## Data input

The JSON data must either be read from a local file or placed as a string variable in your code. The file will be a list of students with their names and a list of subjects. For example:

```
[
{"name":"Sarah","subjects":["physics","it","biology","history","art","business studies","french"]},
{"name":"Jim","subjects":["history","business studies","biology","computer science","geography","chemistry"]},
{"name":"Mary","subjects":["it","computer science","biology","physics","chemistry","art"]},
{"name":"Chris","subjects":["biology","chemistry","physics","french","computer science","geography"]}
]

```

Your program should then generate a timetable for each of the students, fitting all of the subjects in.

If there are multiple solutions, choose the first.

***Note:*** The JSON file above has not been tested to see if it has a valid answer, it was just created to describe the formatting.

## Output

The output must be a JSON file or CSV with the format detailed in your answer. You can either make a file for each of the students or have the timetables for all students in the same file.

## Winning

The winning code is the shortest that successfully creates working timetables.

# Answer
**NodeJS**

**Edit** The algorthim is much faster now! There is definitely no solution for the given example!

I tried some algorithms to generate a time table and I am pretty sure that your example has no solution. So I changed the example to students.json:

```
[
{"name":"Sarah","subjects":["physics","it","biology","history","art","business studies","french"]},
{"name":"Jim","subjects":["history","business studies","biology","computer science","geography","chemistry"]},
{"name":"Mary","subjects":["it","computer science","biology","physics","chemistry","art"]},
{"name":"Chris","subjects":["biology","chemistry","physics","french","computer science","geography"]}
]

```

(I only deleted the `pe`) which generates this timeTable.json

```
 {
 "mon":
   [["Bi"],["Bi"],["Ar","Gg"],["La"],["La"],["Ch"],["Ch"],["CS"],["CS"],["Ph"]],
 "tue":
   [["Tu"],["Bi"],["Ar","Gg"],["Ma"],["Ma"],["Ch"],["CS"],["Ph"],["Ph"],["Bu"]],
 "wed":
   [["Bi"],["Ar","Gg"],["Ar","Gg"],["Li"],["Li"],["Fr"],["Fr"],["IT"],["IT"],["Hi"]],
 "thu":
   [["Li"],["Ma"],["Ch"],["CS"],["Bu"],["Ph"],["Fr"],["IT"],["Hi"],["Ac"]],
 "fri":
   [["Li"],["Ma"],["Fr"],["Bu"],["Bu"],["IT"],["Hi"],["Hi"],[],["Tu"]]
 }

```

And yes my programm is very long but I think code which is shortened afterwards makes it really hard to read and nowadays it isn't important to save bytes but time! If you have any suggestions or you found a bug =\> comment! You can start the file (timeTable.js) with `node timeTable.js students.js`

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

console.log('Timetable');
var json = JSON.parse(fs.readFileSync(process.argv[2], 'utf8'));

var backTracks = 0;
var lessons =
    ["art","biology","business studies","chemistry","computer science","french","geography","history","it","mandarin","music","pe","physics","spanish"];
var abbr = ["Ar","Bi","Bu","Ch","CS","Fr","Gg","Hi","IT","Cn","Mu","PE","Ph","Sp"];
var single = [2,2,2,2,2,2,2,2,2,2,2,2,2,2];
var double = [1,1,1,1,1,1,1,1,1,1,1,1,1,1];

var days = ["mon","tue","wed","thu","fri"];
var nrOfStudents = json.length;
var q = 0;

// convert json into correct position
for (var i = 0; i < json.length; i++) {
    var subjects = json[i].subjects;
    for (var s = 0; s < subjects.length; s++) {
        var pos = lessons.indexOf(subjects[s].toLowerCase());
        if (pos >= 0) {
            subjects[s] = pos;
        }
    }
}

// Special lessons
var timeTable = {"mon":[],"tue":[],"wed":[],"thu":[],"fri":[]};
timeTable.tue[0] = ["Tu"];
timeTable.fri[9] = ["Tu"];
timeTable.thu[9] = ["Ac"];
// one english double (Monday 4-5)
timeTable.mon[3] = ["La"];
timeTable.mon[4] = ["La"];
// one double two single for math and literature (Tue 4-5,Wed 4-5,Thu 1,2,Fri 1,2)
timeTable.tue[3] = ["Ma"];
timeTable.tue[4] = ["Ma"];
timeTable.wed[3] = ["Li"];
timeTable.wed[4] = ["Li"];
timeTable.thu[0] = ["Li"];
timeTable.thu[1] = ["Ma"];
timeTable.fri[0] = ["Li"];
timeTable.fri[1] = ["Ma"];

var timeTableBackup = {0:[],1:[],2:[],3:[],4:[]};

for (var i = 0; i < 5; i++) {
    var day = timeTable[days[i]];
    for (var j = 0; j < 10; j++) {
        if (!(j in day) || !Array.isArray(day[j])) {
            day[j] = [];
        }
    }
}

// sort subjects
var sortedSubs = [];
// 14 subjects
for (var i = 0; i < 14; i++) {
    sortedSubs[i] = {t:0,students:[],n:i};
}

for (var i = 0; i < json.length; i++) {
    var subjects = json[i].subjects;
    var student = json[i].name;
    for (var s = 0; s < subjects.length; s++) {
        sortedSubs[subjects[s]].t ++;
        sortedSubs[subjects[s]].n = subjects[s];
        sortedSubs[subjects[s]].students.push(student);
    }
}
console.log(sortedSubs);

sortedSubs = sortByKey(sortedSubs,"t");

var k = sortedSubs.length-1;
// remove all subs that weren't choosen by anyone
while(sortedSubs[k].t == 0) {
    var sub = sortedSubs.pop();
    single[sub.n] = 0;
    double[sub.n] = 0;
    k--;
}

var goBack = false;
var start = false;
var d = 0;
while (d < 5) {
    // 10 lessons per day
    var l = 0;
    while(l < 10) {
        var day = timeTable[days[d]];
        // if there is no subject
        if (day[l].length == 0) {
            var next = false;
            var s = start === false ? 0 : start;
            var firstChoice = false;
            while (!next && s < sortedSubs.length) {
                if (possibleToAdd(day,l,s)) { // different lessons on one day and possiblity to add lesson
                    goBack = false;
                    next = true;
                    if (!firstChoice) firstChoice = s;
                    // get the number of students that don't have this lesson
                    var except = nrOfStudents - sortedSubs[s].t;
                    if (except > 0) {
                        // get the first lesson which none of the students have
                        var breaked = false;
                        var tempL;
                        for (var ss = s+1; ss < sortedSubs.length; ss++) {
                            if (sortedSubs[ss].t <= except && possibleToAdd(day,l,ss)) {
                                var intersection = arrIntersect(sortedSubs[s].students,sortedSubs[ss].students);
                                // no student has both classes
                                if (intersection.length == 0) {
                                    if (!breaked) { // fill the current lesson (s) only once
                                        tempL = addLesson(day,l,s);
                                    }
                                    tempL = addLesson(day,l,ss);
                                    breaked = true;
                                }
                            }
                        }

                        if (breaked) {
                            l = tempL;
                        } else { // it wasn't possible to have two classes at this time
                            next = false;
                            var found = false;
                            // maybe there are other lessons which can be added => found = true
                            for (var z = s+1; z < sortedSubs.length; z++) {
                                if (possibleToAdd(day,l,z)) {
                                    found = true;
                                    break;
                                }
                            }
                            // otherwise fill this lesson with the first choice
                            if (!found) {
                                l = addLesson(day,l,firstChoice);
                            }
                        }
                    } else {
                        // everyone has this lesson :)
                        // on day lesson no. l: subject no. s
                        l = addLesson(day,l,s);
                    }
                } else {
                    if (start) goBack = true;
                }
                s++;
            }
            start = false;
        }
        // Friday last lesson
        if ((d == 4 && l == 9) || goBack) {
            // how many lessons are missing?
            var sum = double.reduce(function(pv, cv) { return pv + cv; }, 0)*2 + single.reduce(function(pv, cv) { return pv + cv; }, 0);
            if (sum > 0) {
                remove = removeLesson(d,l);
                if (remove) {
                    backTracks++;
                    if (backTracks % 50000 == 0) {
                        console.log('backTracks: '+backTracks+'...');
                    }
                    d = remove.back.day;
                    l = remove.back.lesson;
                    start = remove.start;
                } else {
                    console.log('I could not find a solution for this problem :( ');
                    console.log('backtracks: '+backTracks);
                    process.exit();
                    l = 10;
                    d = 5;
                }
            } else {
                l = 10;
                d = 5;
            }
        } else {
            l++;
        }
    }
    d++;
}

function removeLesson(d,l) {
    var day = timeTable[days[d]];
    var back = true;
    // what is the latest subject
    var latestSub = sortedSubs[sortedSubs.length-1].n;

    // backtrack
    while(back) {
        // if there is no lesson before => back to the last lesson the day before
        if (l == -1) {
            if (d == 0) {
                return false; // not possible at all
            }
            d--;
            day = timeTable[days[d]];
            l = day.length-1;
        }

        // if there is a non default lesson
        if (day[l].length > 0 && parseInt(day[l][0]) == day[l][0]) {
            // if the latestSub isn't part of this lesson we don't need to backtrack more
            if (day[l].indexOf(latestSub) < 0) { back = false; }
            var intersection = [];
            // if we are not in the first lesson => get double lessons
            if (l > 0) {
                intersection = arrIntersect(day[l],day[l-1]);
            }
            // if there are double lessons
            if (intersection.length > 0) {
                for (var i = 0; i < day[l].length; i++) {
                    // check if current lesson is a double lesson
                    if (intersection.indexOf(day[l][i]) >= 0) {
                        double[day[l][i]]++;
                    } else {
                        single[day[l][i]]++;
                    }
                }
                // remove all single lessons the lesson before
                for (var i = 0; i < day[l-1].length; i++) {
                    if (intersection.indexOf(day[l-1][i]) < 0) {
                        single[day[l-1][i]]++;
                    }
                }
                day[l] = [];
                l--;
            } else {
                for (var i = 0; i < day[l].length; i++) {
                    single[day[l][i]]++;
                }
            }
            // delete the day if the current lesson was the least possible solution
            if (back) {
                day[l] = [];
            }
        } else {
            l--;
        }
    }
    var start = false;
    // get start subject for this lesson d,l
    for (var s = 0; s < sortedSubs.length-1; s++) {
        if (day[l].indexOf(sortedSubs[s].n) >= 0) {
            start = ++s;
            day[l] = [];
            break;
        }
    }
    if (!start) {
        console.log('there is a bug');
        process.exit();
    }
    return {back:{day:d,lesson:l},start:start};
}

function addLesson(day,l,s) {
    // is a double lesson possible?
    if (double[sortedSubs[s].n] > 0 && l != 2 && l != 4 && l+1 < 10 && (day[l+1].length == 0 || parseInt(day[l+1][0]) == day[l+1][0])) {
        double[sortedSubs[s].n]--;
        for (var i = l; i <= l+1; i++) {
            if (Array.isArray(day[i])) {
                day[i].push(sortedSubs[s].n);
            } else {
                day[i] = [sortedSubs[s].n];
            }
        }
        l++;
    } else if (single[sortedSubs[s].n] > 0) { // put it into a single lesson
        single[sortedSubs[s].n]--;
        if (Array.isArray(day[l])) {
            day[l].push(sortedSubs[s].n);
        } else {
            day[l] = [sortedSubs[s].n];
        }
    } else {
        console.log('ERROR');
        process.exit();
    }
    return l;
}

function possibleToAdd(day,l,s) {
    // it is not allowed to have the same lesson twice on a day
    var notSet = true;
    for (var i = 0; i < l; i++) {
        if (day[i].indexOf(sortedSubs[s].n) >= 0) {
            notSet = false;
            break;
        }
    }
    if (!notSet) return false;

    // no double lesson 3+4 and (starting with 1)
    if (double[sortedSubs[s].n] > 0 && l != 2 && l != 4 && l+1 < 10 && (day[l+1].length == 0 || parseInt(day[l+1][0]) == day[l+1][0])) {
        return true;
    } else if (single[sortedSubs[s].n] > 0) {
        return true;
    } else {
        return false;
    }
}

function arrIntersect(array1,array2) {
    return array1.filter(function(n) {
        return array2.indexOf(n) != -1
    });
}

function sortByKey(array, key) {
    return array.sort(function(a, b) {
        var x = a[key];
        var y = b[key];
        return ((x < y) ? 1 : -1);
    });
}

// convert lesson numbers into abbr
for (var d = 0; d < 5; d++) {
    var day = timeTable[days[d]];
    // 10 lessons per day
    for (var l = 0; l < 10; l++) {
        for (var ll = 0; ll < day[l].length; ll++) {
            if (parseInt(day[l][ll]) == day[l][ll]) {
                day[l][ll] = abbr[day[l][ll]];
            }
        }
    }
}

console.log(timeTable);
console.log('Backtracks: '+backTracks);

fs.writeFile("timeTable.json", JSON.stringify(timeTable), function(err) {
    if(err) {
        console.log(err);
    } else {
        console.log("The file was saved (timeTable.json)!");
    }
});

```
> 0 votes

---
Tags: code-golf
---


title: Un-hash the Java Hash

text:
# Question
Title: Un-hash the Java Hash
# Hash Un-hashing

The basic goal of this challenge is to exploit the high probability of collision in the *Java Hash* function to create a list of plausible inputs that created an outputted hash. The program that can print the most results in one hour wins.

For example, hashing `golf` produces the number `3178594`. Other 'words' you could hash to get the same number would be: `hQNG`, `hQMf`, `hPlf`

## Details

The basic Java hash function is defined as:

```
function hash(text){
    h = 0;
    for(i : text) {
        h = 31*h + toCharCode(i);
    }
    return h;
}

```

You can use an altered or more efficient variant of the hash function (such as using bitwise to replace multiplication) if it produces the same results.

If your language of choice does not use signed ints or have integer overflow, you must implement a wrap function in the hash to emulate integer overflow so that 2147483648 would overflow to -2147483648.

You can choose not to worry about inputs that wrap around multiple times, such as those with 6-7 characters or more. If you choose to include those, you have a better chance of winning.

## Additional Requirements

* Your code should have at least one input: the hash itself. An optional second input is the maximum number of letters to guess. For example, `guessHash(53134)` might produce a list of all input combinations up to the absolute maximum amount (see the next requirement), and `guessHash(53134, 4)` will display all input combinations that contain 1-4 letters.
* As there are an infinite amount of results, the most letters that can be in a single result will be set at 256. If your program can manage to output all 256 letter results in a reasonable amount of time (see next requirement), you automatically win.
* Your program should not run for more than an hour on any `non-specialized` computer you use. `Non-specialized` means it can't run on a server system using 256 different cores or on a super-computer, it must be something that any regular consumer would/could buy. The shorter time period is for practicality, so that you don't have to use all your processing power for too long.
* All the results in your final list of inputs must produce the same hash as the inputted hash.
* You are to implement your own search, brute-force, or any algorithm to produce the final list.
* Using a native search method or search method from another library is not allowed (example: binary search library). Using `String.search(char)` or `Array.find(value)` is okay if it is not a primary feature of your search algorithm (such as to spot duplicate results or find if a letter exists in given string).
* The final list of input values should use all readable ASCII characters (32 to 126).

## Example

I went ahead and created a very inefficient version of this challenge to produce an example list! Each result I gave is separated by spaces, although you can print each result on a new line or any other readable method of organization.

```
i30( i3/G i2NG hQNG hQMf hPlf golf

```

You do not have to print results to a file, just record how many results you get.

## Judging

The number to un-hash is: `69066349`

I will pick the best answer based on which-ever code produces the most results. If you remember above where I said wrapping was optional, it'd be a good idea to include multiple wrappings if you want the most results in your final list.

---

If you have any questions or additional comments, feel free to ask.

**Good Luck!**

# Answer
# C, 3.2 × 1010 preimages

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[])
{
    char output[29] = { 0 }, preimages[64][8], zeros[512][8] = { "/*$+06(" };
    unsigned i, j, k, l, t;

    t = atoi(argv[1]);

    for(i = 7; i --> 0; t /= 31)
        preimages[0][i] = zeros[0][i] + (t % 31);

    for(i = 0, j = 2, k = 1; i < 6; i += 1, j *= 2)
        for(l = 0; k < j; k++, l++)
            strcpy(preimages[k], preimages[l]),
            preimages[k][i] -= 1,
            preimages[k][i + 1] += 31;

    for(i = 0, j = 3, k = 1; i < 6; i += 1, j *= 3)
        for(l = 0; k < j && k < 512; k++, l++)
            strcpy(zeros[k],zeros[l%(j/3)]),
            t = 1 + (l/(j/3)),
            zeros[k][i] -= t,
            zeros[k][i + 1] += 31 * t;

    for(i = 0, k = 0; i < (1L << 36); i++)
    {
        strcpy(&output[0],  zeros[(i >> 27) & 511]);
        strcpy(&output[7],  zeros[(i >> 18) & 511]);
        strcpy(&output[14], zeros[(i >>  9) & 511]);
        strcpy(&output[21], zeros[(i >>  0) & 511]);

        for(j = 0; j < 64; j += 4)
        {
           // k += 4;
           // if(k++ % 1000000 == 0) printf("%d\n", k);

           printf("%s%s\n%s%s\n%s%s\n%s%s\n",
               output, preimages[j + 0],
               output, preimages[j + 1],
               output, preimages[j + 2],
               output, preimages[j + 3]
           );
        }
    }
    return 0;
}

```

Calculates a preimage and adds and prefixes strings with hash 0. The time spent to generate the preimages should be negligible; all the code has to do is piece together five strings. That means that most of the time will be spent printing the results.

In one hour, only 3.2 × 1010 preimages can be printed. If I comment the *printf* statement out, the program reports that it has found **5.5 × 1012 preimages**. However, I don't know if the compiler just ignores parts of the code (and I don't have the assembly knowledge to verify).
> 6 votes

# Answer
# C#, 1.052 × 1010

The idea is to do the hash function in reverse to get all possible un-hashed strings from the given number. Integer overflow of the 32-bit hash value is also emulated in reverse by incrementing the given hash value by 2^32 on each iteration.

**UPDATE:** I've made several micro-optimisations that significantly improved the performance of my program. The new version produced 10.52 billion results in 15 minutes (compared to 9.05 billion in 1 hour for the previous version).

Futher improvement may be difficult since the output file was 117GB in size and that's about how much free space I have on my SSD. Writing results to the screen doesn't seem to be a viable option since it's almost a thousand times slower than writing to a file.

```
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

namespace Unhash
{
    class Program
    {
        const int minChar = 32;

        const int maxChar = 126;

        // limit maxStrLength to make sure that max hash value does not exceed long.MaxValue (2^63 - 1)
        const int maxStrLength = 12;

        static long[] minHashValues;

        static long[] maxHashValues;

        static Program()
        {
            minHashValues = new long[maxStrLength + 1];
            for (int strLength = 0; strLength <= maxStrLength; strLength++)
                minHashValues[strLength] = Pow(31, strLength) / (31 - 1) * minChar;

            maxHashValues = new long[maxStrLength + 1];
            for (int strLength = 0; strLength <= maxStrLength; strLength++)
                maxHashValues[strLength] = Pow(31, strLength) / (31 - 1) * maxChar;
        }

        static void GuessHash(int hash, int maxLength = 256)
        {
            Stopwatch sw = Stopwatch.StartNew();
            var timeLimit = new TimeSpan(0, 15, 0);

            if (maxLength > maxStrLength)
                maxLength = maxStrLength;

            long currentHash = (uint)hash;
            long step = 1L << 32;

            const int bufferSize = 32 * 1024;
            using (var writer = new StreamWriter("output.txt", false, new UTF8Encoding(false), bufferSize))
            {
                for (int strLength = 0; strLength <= maxLength; strLength++)
                {
                    long maxHash = maxHashValues[strLength];
                    if (currentHash > maxHash)
                        continue;

                    long minHash = minHashValues[strLength];
                    while (currentHash < minHash)
                        currentHash += step;

                    while ((currentHash <= maxHash) && (sw.Elapsed < timeLimit))
                    {
                        GuessLongHash(writer, currentHash, new char[strLength], strLength - 1);
                        currentHash += step;
                    }
                }
            }
        }

        static void GuessLongHash(StreamWriter writer, long hash, char[] chars, int charPos)
        {
            if (hash <= maxChar)
            {
                char ch = (char)hash;
                if (ch >= minChar)
                {
                    chars[charPos] = ch;
                    writer.WriteLine(new string(chars));
                }
                return;
            }

            char c = (char)(hash % 31);
            while (c < minChar)
                c += (char)31;

            while (c <= maxChar)
            {
                chars[charPos] = c;
                GuessLongHash(writer, (hash - c) / 31, chars, charPos - 1);

                c += (char)31;
            }
        }

        static long Pow(int value, int exponent)
        {
            long result = 1;
            for (int i = 0; i < exponent; i++)
                result *= value;
            return result;
        }

        static void Main(string[] args)
        {
            const int hash = 69066349;
            GuessHash(hash);
        }
    }
}

```
> 8 votes

# Answer
# Scala

One "useful" characteristic of Java's `String.hashCode` method is that if you have a string `z` with `z.hashCode() == 0`, then you also have that `(z + x).hashCode() == x.hashCode()` for any other string `x`. So even if we can find a relatively small number of strings with a given hashCode, we can just prefix it with a bunch of zero-hash strings, and generate as many strings as we like with that hashCode - the performance limit becomes string concatenation and IO at that point.

So how do we find a string with a particular hashCode? In truth, brute force would probably be enough, due to the zero-hash trick, but we can easily get more speed with a meet-in-the-middle trick.

Let's suppose we want a string of length 10. To do this, we calculate the hashes of all strings of length 5. In this case, the hash of `x + y` will be `x.hashCode() * 31 ** 5 + y.hashCode`, so we can either start with `x`, and look for strings `y` whose hash is `target - x.hashCode() * 31 ** 5`, or start with `y` and look for strings whose hash is `(target - y.hashCode) / (31 ** 5)` (where division is modulo 2^32). In fact, we do both.

Right now, even length strings are better optimised than odd length strings, for reasons that are probably apparent.

Using the zero-hash trick, I can get 1.6 million strings per second on my laptop - printing the output is the main bottleneck.

Without the zero-hash trick (for example, if you want short strings - too short to pad with zero-hash strings), the performance is more modest. The birthday paradox means it gets faster as it runs, but it seems to level-off at around 70000 strings per second, for strings of length 10.

There's one worthwhile optimisation to note. If we're storing the hashes for a large number of strings, it would seem to make sense to either keep them in a hashtable, or an equivalent on-disk structure. However, an on-disk structure is too slow, and there isn't room for everything in memory (on my laptop, at least). So instead, we keep the data in a fixed-size 1-way cache. This means that data can be lost from the cache, but it improves performance. By increasing `hashtableSize`, you can increase the size of this cache, using more memory, and leading to more matches.

```
import scala.collection.mutable
import scala.collection.JavaConversions._
import java.io.File
import java.io.RandomAccessFile
import java.io.FileWriter

object Unhash {
  val maxChar = 126.toChar
  val minChar = 32.toChar
  val hashtableSize = 0x4000000

  def allStrings(l: Int): Iterator[String] = {
    new Iterator[String] {
      val currentArray = Array.fill(l)(minChar)
      var _hasNext = l > 0
      def hasNext = _hasNext

      def next(): String = {
        if (!_hasNext) throw new NoSuchElementException
        val result = new String(currentArray)
        var i = 0
        while (i < l) {
          if (currentArray(i) != maxChar) {
            val result = new String(currentArray)
            currentArray(i) = (currentArray(i) + 1).toChar
            return result
          } else {
            currentArray(i) = minChar
            i += 1
          }
        }
        _hasNext = false
        return result
      }
    }
  }

  def pow(x: Int, n: Int) = {
    var r = 1
    var p = n
    var m = x
    while (p > 0) {
      if ((p & 1) == 1) r *= m
      m *= m
      p >>= 1
    }
    r
  }

  def guessHash(target: Int, length: Int) = {
    length match {
      case l if l % 2 == 0 => findEven(target, length / 2)
      case _ => findOdd(target, (length - 1) / 2)
    }
  }

  def findEven(target: Int, halfLength: Int) = {
    val hashes = new HashCache(halfLength, hashtableSize)
    val multFactor = pow(31, halfLength)
    val divideFactor = BigInt(multFactor).modInverse(BigInt(2) pow 32).intValue

    new Traversable[String] {
      def foreach[U](f: String => U) = {
        for (string <- allStrings(halfLength)) {
          val hash = string.hashCode
          hashes.put(string)

          // Find possible suffixes
          {
            val effectiveTarget = target - hash * multFactor
            for (x <- hashes.get(effectiveTarget)) f(string + x)
          }

          // Find possible prefixes
          {
            val effectiveTarget = (target - hash) * divideFactor
            for (x <- hashes.get(effectiveTarget)) f(x + string)
          }
        }
      }
    }
  }

  def findOdd(target: Int, halfLength: Int) = {
    val hashes = new HashCache(halfLength, hashtableSize)
    val multFactor = pow(31, halfLength)
    val divideFactor = BigInt(multFactor).modInverse(BigInt(2) pow 32).intValue

    new Traversable[String] {
      def foreach[U](f: String => U) = {
        for (string <- allStrings(halfLength);
             hash = string.hashCode;
             _ = hashes.put(string);
             firstChar <- minChar to maxChar) {
          // Adjust the target, by subtracting the contribution from the first char
          val currentTarget = target - firstChar * pow(31, 2 * halfLength)

          // Find possible suffixes
          {
            val effectiveTarget = currentTarget - hash * multFactor
            for (x <- hashes.get(effectiveTarget)) f(firstChar + string + x)
          }

          //Find possible prefixes
          {
            val effectiveTarget = (currentTarget - hash) * divideFactor
            for (x <- hashes.get(effectiveTarget)) f(firstChar + x + string)
          }
        }
      }
    }
  }

  def guessAnyLength(target: Int) = {
    new Traversable[String] {
      def foreach[U](f: String => U) = {
        val zeroHashes = findEven(0, 4).toArray
        for (len5 <- findEven(target, 4);
             zero1 <- zeroHashes.iterator;
             zero2 <- zeroHashes.iterator;
             zero3 <- zeroHashes.iterator) f(zero1 + zero2 + zero3 + len5)
      }
    }
  }

  def main(args: Array[String]) = {
    val startTime = System.nanoTime
    val Array(output, length, target) = args
    val t = target.toInt

    val resultIterator = length match {
      case "any" =>
        guessAnyLength(t)
      case _ =>
        val l = length.toInt
        guessHash(t, l)
    }

    var i = 0L
    var lastPrinted = System.nanoTime
    var lastI = 0L

    val outputWriter = new FileWriter(output)
    try {
      for (res <- resultIterator) {
        outputWriter.write(res + "\n")

        i += 1

        val now = System.nanoTime
        if (now > lastPrinted + 1000000000L) {
          println(s"Found $i total, at ${i - lastI} per second")
          lastPrinted = System.nanoTime
          lastI = i
        }
      }
    } finally {
      outputWriter.close()
    }

  }
}

class HashCache(stringLength: Int, size: Int) {
  require ((size & (size - 1)) == 0, "Size must be power of 2")
  val data = new Array[Char](stringLength * size)

  def get(hash: Int) = {
    val loc = hash & (size - 1)
    val string = new String(data, stringLength * loc, stringLength)
    if (string.hashCode == hash) Some(string)
    else None
  }

  def put(string: String) = {
    val loc = string.hashCode & (size - 1)
    string.getChars(0, stringLength, data, stringLength * loc)
  }
}

```
> 7 votes

# Answer
**PHP**

I found **81** possible solutions for 69066349 within 0.016 seconds with this code! Btw I didn't try to implement the overflow functionality.

```
$results = 0;

/**
 * Get the string for a hash
 * @param integer $hash hash value
 * @param integer $length length of the returned string
 * @return string $string
 */
function reverseHash($hash,$length=false,$val='',$counter=0) {
    global $results;
    if (!$length) {
        $length = 0;
        $copyHash = $hash;
        while (($copyHash-32)/31 > 0) {
            $copyHash = ($copyHash-126)/31;
            $length++;
        }
        echo 'MaxLength: '.$length.'<br>';
    }

    // if at least one more recursion is needed
    if ($counter < $length) {
        for ($i = 32; $i <= 126; $i++) {
            $string = false;
            $newhash = ($hash-$i)/31;
            $newval = chr($i).$val;
            if ($newhash > 0) {
                // if the new hash isn't an integer => $newval is wrong
                if (floor($newhash) == $newhash) {
                    $string = reverseHash($newhash,$length,$newval,$counter+1);
                }
                if ($string) {
                    return $string;
                }
            } else if ($counter <= $length-1 and $newhash == 0) {
                echo $newval.'<br>';
                $results++;
            }
        }
    } else {
        return false;
    }
}

$start = microtime(true);
reverseHash($_GET['hash']);
$end = microtime(true);
$dif = $end-$start;
echo "Time ".$dif." sec (".$results.")";

```
> 1 votes

---
Tags: number, restricted-source, fastest-code, hashing, search
---


title: Piem validator programme

text:
# Question
Title: Piem validator programme
Write a program that defines a function that can check if a string variable called "anything you want or inputted by the user" is or not a piem. (piem = a story or poem in which the word lengths represent the digits of π (from Wikipedia))

Some examples:

```
myfunction("I am clearly wrong") # False
myfunction("How I want a drink, alcoholic of course, after the heavy lectures involving quantum mechanics") #True (Taken from Wikipedia)
myfunction("Law ' s fine") # True

```

You should delete any kind of punctuation or newline before processing. Pure code golf, the shortest wins

# End date: evening of 1/10/2014

# Various answers

* How many digits do we need to handle? **More than 10**
* As a matter of interest, how should 0's in PI be interpreted? Skipped or 10 letter words? **As 10 letters words**
* "a variable called piem" – so the name of the parameter must be piem? **No, it hasn't, question text corrected**
* A fun bonus might be a solution that is itself a piem **If your solution is a piem you get \*0.5 bonus**
* For the sake of argument, is **_** always punctuation? **You can decide if it is punctuation or if it isn't**
* It's unclear what is meant by "any kind of punctuation" **I mean ,.'"?!;;()**
* So digits should be counted? And Law's fine would be false? **Digits should be treated as letters, Law's fine = False; Law ' s fine = True**

# Comments

* The APL solution should be counted in Bytes
* **If your solution works for 100+ digits of pi you get \*0.8 bonus**
* Because of the great interest the end date is one day more in the future.

# Answer
> 3 votes
# APL (39)

```
{N≡(≢N←≢¨('\w+'⎕S'\0')⍵)↑⍎¨'_. '~⍨99⍕○1}

```

It uses all the digits the APL interpreter's pi constant provides, to a limit of 99. In my case (Dyalog APL 14 32-bit) that was 16 digits. The 64-bit version likely has more digits. 16 digits is enough for the given examples to work, though.

Strings that have more than that amount of words will *fail*, even if all the digits it could check were true. (The same is true of other posts, as of this writing.) For example, if there were only 10 digits, the 'How I want a drink' one would fail. This can be fixed, but at the cost of 14 characters:

```
{(≢¨('\w+'⎕S'\0')⍵){∧/(⌊/≢¨⍺⍵)↑∨⌿⍺∘.=⍵}⍎¨'_. '~⍨99⍕○1}

```

That version will *accept* any string where the first *N* digits are correct.

# Answer
> 7 votes
# JavaScript (169)(140)(137)(135) (63)for 17 digits of pi

In my version `Law's fine` and `Law ' s fine` return both true.

Newest Version (63) by Ingo Bürk and hsl

```
f=s=>!s.split(/\W+/).some((x,i)=>x.length-(Math.PI*1e16+'')[i])

```

New Version (135) for 17 digits of pi (Thanks to Ingo Bürk):

```
f=(s)=>{
s=s.split(/[!"#$%&'()*+, \-.\/:;<=>?@[\\\]^_`{|}~]+/);
p=Math.PI*1e16+'';
    r=0;
    for(a=s.length;a--;)r+=s[a].length!=p[a];
    return !r
}

```

Old version (169) for 32 digits of pi:

```
f=(s)=>{
s=s.split(/[!"#$%&'()*+, \-.\/:;<=>?@[\\\]^_`{|}~]+/);
p="31415926535897932384626433832795".split('');
    r=1;
    for(a=s.length;a--;)if(s[a].length!=p[a]){r=0};
    return r;
}

```

# Answer
> 7 votes
# Ruby, 113 101 79 (98 * 0.8)

```
require"bigdecimal/math"
x=->p{!(BigMath.PI(999).to_s[2..-1]!~/^#{p.scan(/\w+/).map(&:size)*''}/)}

```

## Explanation

* Input is taken as the argument to a lambda. It expects a `String`.
* Pi is calculated up to `999` decimals and turned into a String with the `.` removed.
* Punctuation marks are removed from the poem and it is split into individual words. `"Let's"` is counted as two words: `"Let"` and `"s"`.
* Use `Array#map` to convert each word to the size of the word, concatenate them into a `String`.
* Using a Regexp, check if the two created `String`s begin with the same characters.

I have applied the bonus for handling 100+ digits. `_` is not handled as punctuation in this solution.

# Answer
> 4 votes
## Mathematica, 123 bytes * 0.8 = 98.4

```
f=#&@@RealDigits[Pi,10,Length[d=StringLength/@StringSplit@StringReplace[#,RegularExpression@"[!-.:-?]
"->""]/. 10->0]]==d&;

```

Almost the longest submission so far, but:

* It works for any number of digits of Pi.
* It removes all the required ASCII characters and the line break, without splitting the words in those places.
* It handles 0-digits in Pi correctly (as 10-letter words)

# Answer
> 1 votes
# Python 3 - 129

Doesn't account for punctuation:

```
import math
f=lambda p:all(1if len(p.split(' ')[i])!=int(str(math.pi).replace('.','')[i])else 1for i in range(len(p.split(' '))))

```

# Answer
> 1 votes
# Python - ~~130 127~~ *116* \- 17 digits of pi

As in @flawr 's answer, `Law ' s fine` and `Law's fine` both return True.

Thanks to @Emil for removing 12 characters from the program.

```
import re
f=lambda x:all(j==int("31415926535897932"[i])for i,j in enumerate([len(s)for s in re.findall("[\w]+",x)]))

```

# Answer
> 1 votes
## Java, 185

```
boolean f(String...s){s=s[0].replaceAll("\\W","~").replaceAll("~+","~").split("~");for(int i=0;i<s.length;){if(s[i].length()!=(int)(Math.PI*Math.pow(10,i++)%10))return 0>1;}return 1>0;}

```

# Answer
> 1 votes
# python 3, 17 digits of pi, 104

```
import re;f=lambda s:all(map(int.__eq__, map(int, '31415926535897932'), map(len,re.findall('[\w]+',s))))

```

# Answer
> 0 votes
## T-SQL ~~488~~ 383

And now for a large T-SQL solution :)

```
CREATE FUNCTION F(@s VARCHAR(MAX))RETURNS CHAR(6) AS BEGIN DECLARE @ CHAR='T',@p VARCHAR(50)='31415926535897932384626433832795028841971693993751',@i INT=0WHILE @='T'AND @s<>''BEGIN SET @i=PATINDEX('%[^a-z0-9]%',@s)IF @i=0RETURN'#True'IF @i-1<>LEFT(@p,1)RETURN'#False'SET @p=STUFF(@p,1,1,'')SET @s=STUFF(@s,1,@i,'')SET @s=STUFF(@s,1,PATINDEX('%[a-z0-9]%',@s)-1,'')END RETURN'#True'END

```

~~This creates an inline table valued function that uses a recursive CTE to detect word boundaries.~~

Creates a scalar function that chews it's way through the words and PI to 31 decimals (first 0). It is called in the following way

```
SELECT dbo.f('SQL I golf, a large procedure is normal. Hefty not terse') --#True

```

# Answer
> 0 votes
## CJam, 40

```
"
,.'\"?!;:"{-}/S%{,PAV#*iA%=V):V}/]0#)!

```

It's unclear what is meant by "any kind of punctuation"; this solution removes the `,.'"?!;;` characters.

# Answer
> 0 votes
# Bash and unix tools, 111

```
f() { grep ^"$(echo "$@"|grep -Po '[\w]+'|xargs -n1 sh -c 'echo ${#0}'|xargs|tr -d ' ')"<<<31415926535897932;

```

# Answer
> 0 votes
**NodeJS 32 digits 230 Bytes**

I can't get it shorter with JS :D

```
var p = "31415926535897932384626433832795", i = 0;
console.log(process.argv[2].split(/[\s,.]+/).every(function(w) {
    if (parseInt(p.charAt(i)) !== w.length) {
        return false;
    }
    i++;
    return true;
}) ? 'True' : 'False');

```

---
Tags: code-golf, pi
---


title: Find all strings at distance k

text:
# Question
Title: Find all strings at distance k
The edit (or Levenshtein) distance between two strings is the minimal number of single character insertions, deletions and substitutions needed to transform one string into the other.

The challenge is to write code to output all strings with edit distance exactly k from a fixed string of length 10, where k is a variable set in your code as is the fixed string. The alphabet is 0 or 1. To test, take

```
1111011010

```

as the fixed string. The twist is that you can't output the same string twice.

You may not use any library or built in functions that compute the Levenshtein distance for you.

**Score**

This is a standard code-golf challenge. You can assume k will be a one-digit number.

**Reference Implementation**

(added by Martin Büttner)

For reference, here is a Mathematica solution (which isn't valid, due to use of `EditDistance`) which can be used to check results for correctness:

```
s = "1111011010";
k = 2;
Union @ Cases[
     Join @@ Array[# <> "" & /@ {"0", "1"}~Tuples~# &, 2 k + 1, 10 - k],
     x_ /; x~EditDistance~s == k
]

```

For the first ten values of `k` I the following results:

```
 k | # of results

 0              1
 1             28
 2            302
 3           1652
 4           5533
 5          14533
 6          34808
 7          80407
 8         180663
 9         395923

```

# Answer
> 1 votes
# CJam, ~~72~~ 64 bytes

```
QaK{_{_,),\f{[\:Lm>_,L>{_)1^+_);@}*_'0+\'1+]{Lm<}/}~}%_&}*]W%:-p

```

Assumes the string is stored in `Q` and the integer in `K`. This can be achieved by executing

```
"1111011010":Q;1:K;

```

for example. Try it online.

### Example run

```
$ cjam <(echo '"1111011010":Q;1:K;'; cat edit-distance.cjam)
["1111011011" "11110110100" "11110110101" "111101101" "1111011000" "11110110110" "111101100" "1111011110" "11110110010" "111101110" "1111010010" "11110111010" "111101010" "1111001010" "11110101010" "1111111010" "11110011010" "111111010" "1110011010" "11111011010" "111011010" "1101011010" "11101011010" "1011011010" "11011011010" "0111011010" "10111011010" "01111011010"]
$ cjam <(echo '"1111011010":Q;1:K;'; sed 's/p/,p/' < edit-distance.cjam)
28
$ cjam <(echo '"1111011010":Q;2:K;'; sed 's/p/,p/' < edit-distance.cjam)
302

```

### How it works

The idea is to recursively compute all strings at distance d or less ("or less" part not exhaustive), then remove the strings at distance k - 1 or less from the array of strings at distance k or less.

```
Qa                " Push R := [Q].                                                    ";
K{                " Do the following K times:                                         ";
  _               " Push a copy of R.                                                 ";
  {               " For each S ∊ R:                                                   ";
    _,),\         " Push A := [ 0 1 ... len(S) ] below S.                             ";
    f{            " For each I ∊ A, push I S and:                                     ";
      [           "                                                                   ";
        \:Lm>     " Rotate S (L := I) characters to the right.                        ";
        _,L       " Push len(S) L.                                                    ";
        >{        " If len(S) > L:                                                    ";
          _)1^+   " XOR the last character code of a copy of S with 1.                ";
          _);@    " Remove the last character of a copy of S.                         ";
        }*        "                                                                   ";
        _'0+      " Append '0' to a copy of S.                                        ";
        \'1+      " Append '1' to S.                                                  ";
      ]           " Collect the modified values of S in an array T.                   ";
      {Lm<}/      " For each U ∊ T, push U rotated L characters to the left.          ";
    }~            " Dump the resulting array on the stack.                            ";
  }%              " Collect the results in R.                                         ";
  _&              " Remove duplicates from R.                                         ";
}*                "                                                                   ";
]W%               " Collect the different values of R in an array and reverse it.     ";
:-                " Reduce the array using setwise difference.                        ";
p                 " Print a string representation of the resulting array.             ";

```

# Answer
> 3 votes
# Scala 168 228

My first submission had a bug where it didn't consider multiple insertions at the same point in the input string.

After

```
val k = 1
val s = "1111011010"

```

The code that counts is:

```
def e(k:Int,s:String):Set[String]=if(k<1)Set(s)else e(k-1,s).flatMap(e=>"01"map(_+e))++(if(s=="")Set()else e(k,s.tail).map(s.head+_)++e(k-1,s.tail).flatMap(e=>(Set("0","1","")-(s take 1))map(_+e)))
print(e(k,s))

```

To run, save both sections together as a file and run like:

```
$ scala distancek.scala
Set(111111010, 111101010, 1111001010, 11110011010, 1101011010, 11101011010, 111101101, 111101100, 11111011010, 1111011011, 1111011000, 11110101010, 1111010010, 11110110110, 11110110101, 111101110, 11110110010, 0111011010, 1110011010, 11110110100, 10111011010, 11011011010, 01111011010, 1011011010, 1111111010, 111011010, 11110111010, 1111011110)
$

```

Recursive function to build the edited strings. k is the number of edits remaining, s is the string to edit. Slightly ungolfed:

```
def e(k:Int,s:String):Set[String]=
  if(k<1) Set(s)                           // No edits left
  else e(k-1,s).flatMap(e=>"01"map(_+e))++ // Insert a character, consume an edit, continue from the same point
      (if(s=="") Set()                     // We're at the end of the string so only insertions are allowed
       else e(k,s.tail).map(s.head+_)++    // skip past this character, making no edit
       e(k-1,s.tail).flatMap(e=>(Set("0","1","")-(s take 1))map(_+e))) // replace this character with its inverse or ""

```

Note that each step makes at least one of k, s smaller so we're guaranteed to terminate.

---

First submission (Incorrect)

```
print((0 to 10).permutations.flatMap{i=>((s.map(_+""):+"")zip i).:\(Set("")){case((s,i),a)=>a.flatMap{a=>(if(i<k)Set(1+s,0+s,"","0","1")-s else Set(s))map(_+a)}}}toSet)

```

We take the permutations of 0..10 and zip them with the word s + a terminal "" (for insertions at the end). All the positions \< k are positions where an edit should occur. For each edit we replace the string at that position with

```
Set(1+s,0+s,"","0","1")-s # don't count substituting s for itself as an edit.

```

and finally convert to a set to remove duplicates.

# Answer
> 2 votes
# JavaScript (E6) 167 ~~183~~

Assuming the definition of variables *k* (required distance) and *s* (fixed string, 1111011010 for test). As requested it outputs in console just the list of string, so good luck for counting.

```
o={},o[s]=1,
A=x=>o[x]||(o[x]=d,d-k||console.log(x)),
S=r=>{
  for(l='';A(l+1+r),A(l+0+r),c=r[0];l+=c)
    r=r.slice(1),A(l+r),A(l+1+r),A(l+0+r)
};
for(d=0;++d<=k;)
  for(q in o)S(q)

```

Less golfed and more sensible, a function with 2 parameters and a count in output

```
F=(k,s)=>
{
  o={}, o[s]=1, h=0,
  add=x=>{
    o[x]||(o[x] = d, d == k && console.log(++h,x));
  },
  scan=s=>{
    add(s+1)
    add(s+0)
    for (l='',r=s,i=0; r; l += c) // l,r:left and right
    {
      add(l+1+r)
      add(l+0+r)
      c=r[0]
      r=r.slice(1)
      add(l+r)
      add(l+1+r)
      add(l+0+r)
    }
  };
  for(d=0; ++d <= k;)
    for (q in o)
      scan(q)
}

```

**Test** In FireFox/FireBug console

```
F(1,'1111011010')

```

*Output*

```
1 11110110101
2 11110110100
3 11111011010
4 01111011010
5 111011010
6 0111011010
7 10111011010
8 1011011010
9 11011011010
10 1101011010
11 11101011010
12 1110011010
13 11110011010
14 111111010
15 1111111010
16 11110111010
17 111101010
18 1111001010
19 11110101010
20 1111010010
21 11110110010
22 111101110
23 1111011110
24 11110110110
25 111101100
26 1111011000
27 111101101
28 1111011011

```

Just counting, no string output:

```
10 -> 850064 (in 3min & 600 MB)
11 -> 1795537 (in 8min & 900 MB)

```

# Answer
> 2 votes
# Haskell, ~~136~~ 134

```
import Data.List
n%l=iterate(>>=foldr(\t@(x:y)r->['0':t,'1':t,'0':y,'1':y,y]++map(x:)r)["0","1"].init.tails)[l]!!n
r=nub(n%l)\\(n-1)%l

```

upon running `r` will become the list of all strings with edit distance of `3` from `"1111011010"`. the string is embedded in the code at line 5 and the required distance is at the end of the last line.

**edit:** explanation is removed because it is nor relevant anymore

# Answer
> 1 votes
## Mathematica, 244 bytes

```
l=Length;e[s_,t_]:=(m=l@s;n=l@t;Clear@f;f[0,m_]:=m;f[m_,0]:=m;For[j=0,j++<n,For[i=0,i++<m,p=f[i-1,j-1];f[i,j]=If[s[[i]]==t[[j]],p,Min[p,f[i,j-1],f[i-1,j]]+1]]];f[m,n])#<>""&/@Union@Cases[Join@@Array[{"0","1"}~Tuples~#&,2k+1,l@s-k],x_/;x~e~s==k]

```

This is basically the same as the reference implementation I added to the question, except I reimplemented `EditDistance` (as `e`) using the Wagner-Fischer algorithm.

That is, I simply generate all possible strings of the relevant lengths, and then I just reject all which aren't an edit distance of 2 away from the input string.

This expects the distance to be stored in `k` and the input as an array of characters in `s`.

Less golf:

```
l = Length;
e[s_, t_] := (
  m = l@s; n = l@t;
  Clear@f;
  f[0, m_] := m;
  f[m_, 0] := m;
  For[j = 0, j++ < n,
   For[i = 0, i++ < m,
    p = f[i - 1, j - 1];
    f[i, j] = If[s[[i]] == t[[j]],
      p,
      Min[p, f[i, j - 1], f[i - 1, j]] + 1
      ]
    ]
   ];
  f[m, n]
  )
# <> "" & /@
 Union@Cases[Join @@ Array[{"0", "1"}~Tuples~# &, 2 k + 1, l@s - k],
   x_ /; x~e~s == k]

```

# Answer
> 1 votes
## APL, ~~109~~ ~~103~~ 101

Assuming `s` and `k` are defined

```
~⍨/{{∪⊃,/{⍵≡'':⍕¨0 1⋄(,/⍕¨↑(⍎¨⍵)∘≠¨↓∘.=⍨x),(/∘⍵¨↓∘.≠⍨x),(,⍨-0,x)⌽¨,'01'∘.,⌽∘⍵¨0,x←⍳⍴⍵}¨⍵}⍣⍵⊂s}¨0,⍳k

```

**Explantion**
The program consists of 3 nested functions.

**The inner function `{⍵≡'':⍕¨0 1⋄(,/⍕¨↑(⍎¨⍵)∘≠¨↓∘.=⍨x),(/∘⍵¨↓∘.≠⍨x),(,⍨-0,x)⌽¨,'01'∘.,⌽∘⍵¨0,x←⍳⍴⍵}`returns all string that is distance 1 from the argument**

`(,⍨-0,x)⌽¨,'01'∘.,⌽∘⍵¨0,x←⍳⍴⍵` calculate insertions:
`⍴⍵` length of the argument
generate array from 1 to that number
`x←` assign to variable `x`
`0,` concatenate `0` to the start of the array
`⌽∘⍵¨` and for each of the number in the array, rotate the argument by that amount, generating an array of strings (rotate is defined as taking characters from the start of the string and appending to the back)
`'01'∘.,` generate a matrix whose first row are the strings with `0` concatenated to the start and the second row are the strings with `1` concatenated to the start `,` unravel the matrix to give a simple array of its elements
`(,⍨-0,x)` give the negatives of the array constructed by concatenating `0` to the start of `x`, and then concatenate that with another copy of it
`⌽¨` finally, rotate the strings back by using the negative numbers

`(/∘⍵¨↓∘.≠⍨x)` calculates deletions:
`∘.≠⍨x` generate a square matrix consisting of 0's on the diagonal and 1's elsewhere, whose side is same length as `x`
split the matrix rows to create a nested array
`/∘⍵¨` for each of those arrays, replicate the characters of the argument according the the array (in the case where the array only contains 0's and 1's, it means where there is a 1 in the array, keep the character in the corresponding index and where there is a 0, discard the corresponding character)

`(,/⍕¨↑(⍎¨⍵)∘≠¨↓∘.=⍨x)` calculates substitutions:
`∘.=⍨x` generate a square matrix consisting of 1's on the diagonal and 0's elsewhere, whose side is same length as `x`
split the matrix rows to create a nested array
`(⍎¨⍵)∘≠¨` generate an array by converting the argument into a numerical array of its digits, then XOR it with each of the arrays from the split
"mix" the nested array to create a matrix (reverse of split) `⍕¨` for each element of the matrix (which is either 1 or 0), convert to string
`,/` for each row of the matrix, concatenate the elements

`⍵≡'':⍕¨0 1` is a special case for the empty string (the substitution part will throw an error on empty string)
`⍵≡'':` if the argument is the empty string...
`⍕¨0 1` return this (an array of the strings `'0'` and `'1'`)

**The middle function `{∪⊃,/{...}¨⍵}` takes an array of strings and return an array of all strings that is distance 1 from any of them**

`{...}¨⍵` for each of the strings in the argument, use the inner function to get all strings distance 1 for it
`,/` concatenate all of the returned arrays
as the result is "wrapped" in a scalar, "unwrap" it
remove duplicates

**The outer function {{...}⍣⍵⊂s}, given a number, calculates all string that is *potentially* that distance from `s`**

`{...}⍣⍵` repeat the middle function  times ( is the argument)
`⊂s` "wrap" `s` and call the function with that as the argument

**The remaining part `~⍨/{...}¨0,⍳k`**

`0,⍳k` generate array from `0` to `k`
`{...}¨` for each of those numbers, call the outer function with it
`~⍨/` remove the strings found in distances 0,1,2,...,k-1 from the strings found in distance k. This is necessary because the "distance 1" function is stateless - it does not consider stuff like substituting the same character twice or inserting and deleting the same character.

---
Tags: code-golf, string, edit-distance
---


title: A simple Knight's problem

text:
# Question
Title: A simple Knight's problem
How many ways are there to place a black and a white knight on an N * M chessboard such that they do not attack each other?

A knight can move two squares horizontally and one square vertically, or two squares vertically and one square horizontally.

The knights have to be placed on different squares and the knights attack each other if one can reach the other in one move.

## Input:

The first line contains the number of test cases T. Each of the next T lines contains two integers N and M, representing the dimensions of the board.

## Output:

Output T lines, one for each test case, each containing the required answer for the corresponding test case.

**Sample input**:

```
3
2 2
2 3
4 5

```

**Sample output**:

```
12
26
312

```

**Constraints**

```
    1 <= T <= 10000
    1 <= N,M <= 100000
time limit 1 sec

```

**Source Limit:**

```
50000 Bytes

```

**Winning criteria**

```
Shortest code which runs with specified time limit decides the winner

```

i ll leave two days time for more users to try from today

# Answer
> 4 votes
# GNU Octave, 55 56 58 78 87\* 93 chars

```
a=t(:,1);b=t(:,2);-4*max(2*(g=a.*b)-3*(a+b)+4,0)+g.*--g

```

Octave doesn't take input from STDIN, so you've got to provide the input in the program:

```
t = [
    1 7;
    2 2;
    2 3;
    4 5;
    5000 6000
];                % test cases

a=t(:,1);b=t(:,2);-4*max(2*(g=a.*b)-3*(a+b)+4,0)+g.*--g

```

The logic is as follows:

`nchoosek(n*m, 2)` gives us the number of combinations of two positions we can have on a N\*M board. We then multiply it by two since we have two different knights.

Then we work out how many 3\*2 blocks fit in an N\*M board. For each 3\*2 block there are 4 different positions our knights can be attacking each other. So we multiply it by 4 and subtract it from the value we calculated above.

\*thanks to a simplification of the nchoosek I shamelessly stole from Matt.

## Edit

I've just tested this on my laptop to make sure it meets the time requirements.

It will compute 500,000 10,000,000 test cases in an average of 0.918787 0.231201 seconds

# Answer
> 3 votes
# Python 105 119 112 104

```
for a,b in[map(int,raw_input().split())for i in[1]*input()]:print a*b*(a*b-1)-4*(max(2*a*b-3*(a+b)+4,0))

```

This uses the same approach as Griffin's solution.

Now appropriately handles boards of size 1xn

# Answer
> 3 votes
# Mathematica 55 50 38 41

**Second attempt**

This is my rendering, in Mathematica, of @Matt's solution. Credit for the underlying reasoning goes to Matt. Griffin helped me understand how Matt's approach works.

It is faster than my first approach approach but still too slow to satisfy the time constraints for boards with 10^5\*10^5 cells. The pure function (38 chars) is defined as follows:

```
 #1 #2 (#1 #2-1)-4 Max[2 #1 #2-3 (#1+#2)+4,0]&

```

**Usage**

```
#1 #2 (#1 #2-1)-4 Max[2 #1 #2-3 (#1+#2)+4,0]& @@@ {{2, 2}, {2, 3}, {4, 5}}

(* out *)
{12, 26, 312}

```

The symbols, `@@@`, apply the function to the list. I included them in the character count.

---

**First Attempt: 50 chars but really, really slow.**

I'm including it because it may be of interest to some readers.

Mathematica doesn't take input from STDIN so I used an input more to its liking. There is no need to input the number of inputs; MMA will simply act on whatever number it is given.

**Code**

```
#1*#2*(#1*#2-1)-2 EdgeCount[#1~KnightTourGraph~#2] &

```

---

**Usage** (with spaces for readability).

```
#1*#2*(#1*#2 - 1) - 2 EdgeCount[#1~KnightTourGraph~#2] &; @@@ {{2,2}, {2,3}, {4,5}}

(* out *)
{12, 26, 312}

```

---

**Explanation**

Below is a graph of possible knight moves in a 4 by 5 chessboard.

```
k = KnightTourGraph[i, j, PlotLabel -> Subscript[K, i, j]]

```

There are `20*19 = 380` ways to arrange the black and white knight on the board. Below is the adjacency matrix:

```
AdjacencyMatrix[k] // MatrixForm

```

There are `68` cases in which the knights are in an attacking position. This corresponds tohow many one's there are in the matrix. It also happens to equal two times the number of edges and sum of the degrees of the vertices.

```
t = 2*EdgeCount[k]
(* out *)
68

```

Finally, `380-68 = 312`.

---

**Timing**

It takes just under one second to calculate the answer for all grids up to 15 by 15. Note: `312` is in row 4, column 5.

# Answer
> 1 votes
# C++, 232 250 228 192 173 characters

```
#include<iostream>
int main(){long long n,x,y,i;for(std::cin>>n;n--;)std::cin>>x>>y,i=(x*2-2)*(y-2<0?0:y-2)+(y*2-2)*(x-2<0?0:x-2)<<1,x*=y,std::cout<<x*x-x-i<<"\n";return 0;}

```

SEE IT RUN

I don't know what hardware ideone uses, but that can run for a 10000x10000 board 10000 times in .2 seconds.

How I simplified the problem:

I started out trying to find ways I could divide the board into known regions, with a certain density of bad positions per square. The simplest case is that if there are no edges within 2 squares of a square, that square has 8 possible failing positions. This turned out to be really complicated near the edges of the board where more than 2 edges can sometimes come into play (if, for example, you have a board that's only 2 wide), so I decided to try to simplify it based on direction, which turned out to be very easy.

First, I considered just one direction. On a chessboard of irrelevant length, how many moves are eliminated by the introduction of one unit of width? I made a table:

```
Width of board         Number of positions eliminated
1                      0
2                      2
3                      4
4                      6
N                      2N-2

```

I used my E=2N-2 formula along with the knowledge that for a board of length L, L-2 rows are viable (and thus count towards the exclusion count).

The program, conceptually, makes 4 sweeps, one in each direction (in practice it does 2, and multiplies by 2. It's a shortcut that works because of symmetry). Each sweep represents the moves excluded that tend in the direction of the sweep. The program then sums up each of the sweeps and subtracts from the total number of possible combinations.

Knight placement is random, but two knights cannot occupy the same space. Therefore, the total number of positions you can place a knight is the total numbers of squares the first time, then the number of squares minus one the second time (since there is a square that's taken).

# EDIT 1

fixed overflow, fixed forgetting to substract somewhere causing incorrect answers with a dimension of 1. Also swapped out 31's for 63's in bit twiddling since it uses 64 bit data types now

# EDIT 2

shortened further (introduced branching D: the non-branching version is 6 characters longer.)

# GOLF SCORECARD

* removed unnecessary clause: `(~u>>31&(x<<1)-2)` became `((x*2)-2)` in 2 places, saved 16 characters (234)
* swapped `~u>>63&u` for `u<0?0:u` in 2 places, saving 2 characters (232)
* swapped `x-2<0?0:x-2` for `u<0?0:u` and removed definition of u `u=x-2,` in 2 places, saving 4 characters (228, shorter than original solution)
* removed function f and moved functionality into main, saved 28 characters (200)
* removed `using namespace std;` and used std::cout, std::cin, and "\n", saved 5 characters (195)
* changed `std::cin>>n;for(;n>0;--n)` to `for(std::cin>>n;n;--n)`, saved 3 characters (192)
* removed `typedef long long L;` since its only used in one place now, saved 12 characters (180)
* removed 4 parens from statements like `((x*2)-2)`, saved 4 characters (176)
* removed brackets from loop by using commas instead of semicolons, compressed loop condition from `std::cin>>n;n;--n` to `std::cin>>n;n--;`, saved 3 characters (173)

# Answer
> 1 votes
# Go

```
package main
import "fmt"
func main() {
    var N int
    fmt.Scanln(&N)
    for ; N > 0; N-- {
        var m, n int64
        fmt.Scanln(&m, &n)
        grid := m*n
        total := grid*(grid-1)
        if m > 2 && n > 1 {
            total -= (m - 2)*(n - 1) * 4
        }
        if n > 2 && m > 1 {
            total -= (n - 2)*(m - 1) * 4
        }
        fmt.Println(total)
    }
}

```

## Explanation

* `grid` is number of grid
* `total` is initialized as all the possible ways the knights could be placed. Since they have to be different grids, `grid * (grid - 1)`
* Now we exclude the number of ways they may attack each other
    + Their position could be two squares difference horizontally and one square vertically. The number of ways is `(m - 2)*(n - 1)` when `m > 2 && n > 1`. The left can be higher of lower then the right, so `*2`. White and black are exchangable, so `*2` again.
    + Similar to the situation for two squares vertically and one square hotizontally

## Timing

* 4 `int64` multiplication and 7 `int64` plus/minus operation, should be done in 1 second.

---
Tags: code-golf, chess, puzzle-solver
---


title: Musical Quines on an ASCII Piano

text:
# Question
Title: Musical Quines on an ASCII Piano
There are 88 keys on a standard piano and 95 printable ascii characters (hex codes 20 through 7E):

```
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

```

<sup>('character' refers to any printable-ASCII character from here on)</sup>

In this JSFiddle I've taken advantage of that and made a simple syntax that generates piano tunes using AudioSynth. *(If anyone can direct me to a linkable set of **real** piano note sounds I'll be grateful.)*

Each character in the input string besides `() 01+-` corresponds to one piano key:

```
 CHARACTER:  !   "   #   $   %   &   '   *   ,   .   /   2   3   4   5   6   7   8   9   :   ;   <   =   >   ?   @   A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z   [   \   ]   ^   _   `   a   b   c   d   e   f   g   h   i   j   k   l   m   n   o   p   q   r   s   t   u   v   w   x   y   z   {   |   }   ~
KEY NUMBER:  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88
      NOTE:  A  A#   B   C  C#   D  D#   E   F  F#   G  G#   A  A#   B   C  C#   D  D#   E   F  F#   G  G#   A  A#   B   C  C#   D  D#   E   F  F#   G  G#   A  A#   B   C  C#   D  D#   E   F  F#   G  G#   A  A#   B   C  C#   D  D#   E   F  F#   G  G#   A  A#   B   C  C#   D  D#   E   F  F#   G  G#   A  A#   B   C  C#   D  D#   E   F  F#   G  G#   A  A#   B   C
    OCTAVE:  0   0   0   1   1   1   1   1   1   1   1   1   1   1   1   2   2   2   2   2   2   2   2   2   2   2   2   3   3   3   3   3   3   3   3   3   3   3   3   4   4   4   4   4   4   4   4   4   4   4   4   5   5   5   5   5   5   5   5   5   5   5   5   6   6   6   6   6   6   6   6   6   6   6   6   7   7   7   7   7   7   7   7   7   7   7   7   8

```

So `RPNPRRR` plays the first 7 notes of Mary Had a Little Lamb using the preset timing parameters you can see in the JSFiddle.

Space () represents a musical rest that lasts for one note interval. So `RPNPRRR PPP RUU` plays the first 13 notes of Mary Had a Little Lamb with rests in their proper places.

If any character besides `()01` is prefixed by a sequence of `0`'s and `1`'s (regex `[01]+`), that sequence is read as a binary number *b*, and the character is replaced with *b* copies of itself. So `101A11 10+1-0B01C` becomes `AAAAA ++-C` because `101` = 5, `11` = 3, etc. (A sequence of `0`'s and `1`'s at the end of the string has no effect.)

Matched parentheses (`()`) serve two purposes:

1. If their content ***does not*** end with a sequence of `0`'s and `1`'s, all the notes are played at the same time as a chord (which otherwise is no different than a note). So `(NQU)` is a C minor chord on octave 4.
If duplicate notes are present their sound is also duplicated. So `(NN)` and `(NNN)` sound different.
2. If their content ***does*** end with a sequence of `0`'s and `1`'s, that sequence is read as a binary number *b*, and the parentheses and their content are replaced with *b* copies of the content. So `(NQU11)` becomes 9 individual notes: `NQUNQUNQU`.

Parentheses Details:

* Nesting replicating parentheses (purpose 2) is fine: `(N(QU10)11)``(NQUQU11)``NQUQUNQUQUNQUQU`.
* Nesting non-replicating parentheses (purpose 1) is fine but has no effect: `(A((+)C))` is the same as `(A+C)`.
* You can also combine both: `((N(QU10))11)``(NQUQU)(NQUQU)(NQUQU)`.
* A sequence of `0`'s and `1`'s before non-replicating parentheses repeats them in the same way individual characters are repeated. So `10(NQU)` becomes `(NQU)(NQU)`.
* A sequence of `0`'s and `1`'s before replicating parentheses has no effect.
* `(` must always have a matching `)`, but not vice-versa: e.g. `N)` is valid.

Plus (`+`) and minus (`-`) respectively increase and decrease the the duration of notes **or** the time interval between notes, depending on their context:

* When *inside* non-replicating parentheses, they immediately increase or decrease the note duration variable by some preset number of milliseconds (see JSFiddle). So `(++)N` will play `N` at a longer duration than normal.
* When *outside* non-replicating parentheses, they increase or decrease the interval between the start of the next note and the note after it (and each subsequent interval) by some preset number of milliseconds. So in `++NP` the interval between the `N` and `P` is longer than usual.

The duration of notes and the time interval between them cannot drop below 0.

# Challenge

I intentionally chose `() 01+-` to be the 7 special characters because they can be innocuously placed in many contexts in lots of programming languages.

Your task is to write a quine in 512 bytes or less that produces the best sounding tune when the code itself is used as the input string in the JSFiddle.

You may choose any initial values (non-negative integers) for the 4 interval/duration parameters, but your tune must not last more than 10 minutes. You should also tell us if your tune sounds best in a particular instrument.

### Rules

* Only tabs, newlines, and printable-ASCII are allowed in your code. All non-printable ASCII is ignored by the tune creator.
* Output may go to a file or stdout or the closest alternative (e.g. JS alert). There is no input.
* No reading of source code. It must be a true quine.
* The removal of any **3 contiguous** source characters must make the program no longer function as a quine. This is to ensure people don't write a good song in a string then have a tiny quine portion to output it.
    + So if your program was `MYCODE` then `MYC`, `MYE`, `MDE`, and `ODE` should all not be quines (they may error or output something else).

This is a popularity-contest, the highest voted answer wins.

**Update:** Relaxed last rule.

# Answer
# C

I decided I liked the low rumbling noise generated by the string `/**/` which is not-so-coincidentally the way to open and close a comment in C. The only other interesting bit here is that `34` for a `"` is replaced by `35-1`(Ending in a `1` intentionally) to avoid god-awful chords. I also tried to make the ending sound dramatic. I really did. I intend to edit this later to make it sound a bit better.

```
/**/char*p= "/**/char*p= %c%s%c; int main(){printf(p,34,p,35-1);p++;/**/}/**/";
int main(){printf(p,34,p,35-1);p++;/**/}/**/

```

To my understanding of the rules, the commented sections still pass the final rule because their removal results in a failed quine.
> 6 votes

# Answer
# J

Yeah, I think you can guess how this is going to go.

It's hard to get anything cool done in J without parens, and since you can rarely end them with 0s and 1s, most things sound like someone sitting on the high and low halves of the keyboard at the same time. I tried my best, I'll have you know.

Here's a funky baseline for piano, I think. I really don't know the first thing about composition, I just grabbed a quine and twiddled the numbers around a bit.

```
(23 23,~,~i.124+-100){,'(23 23,~,~i.124+-100){,'''

```

And, just for fun, play this one as EDM. I call it *Japhex Twin*.

```
".s=:'''".s=:'',''''''''&,@(,&'''''''')@(#~>:@(=&''''''''))s'

```

You can confirm the quineiness of these fine snippets of code at tryj.tk.
> 5 votes

# Answer
# Musique Concrete with Python

I don't have a lot of time today but I wanted to get an answer in. The genre is an excuse for not sounding like anything. Maybe a sound effect in a video game?

```
BFIN10=r"print('BFIN10=r\"'+BFIN10+'\"'+'\nexec(BFIN10)')"
exec(BFIN10)

```
> 4 votes

# Answer
# C

```
int(printf)(char*,...); (main)(){char*b=",*",i=(34),*m=("int(printf)(char*,...); (main)(){char*b="),
*z="%s%c%s%c,i=(34),*m=(%c%s%c)%sz=%c%s%c,*B=%c%s%c,*f=(%c%s%c)%s(/*)*/%s/*(*/);}//(+++fim)",*B="(f,
i,m,z),(i,z,m),(m,i),(f,b),(m,i),(m,i),(f,z,m),(m,i),(f,z,b),(m,i),(b,z),(B,i),(38,i),(29,B),(26,i),
(26,i),(B,f),(42,i),(i,m,f),B",*f=(";(printf)");(printf)(/*)*/(f,i,m,z),(i,z,m),(m,i),(f,b),(m,i),(m
,i),(f,z,m),(m,i),(f,z,b),(m,i),(b,z),(B,i),(38,i),(29,B),(26,i),(26,i),(B,f),(42,i),(i,m,f),B/*(*/)
;}//(+++fim)

```

Broken up with line breaks for presentation purposes only; this is only a quine (and only meets length requirements) if newlines are removed.

The printf declaration was needed to compile `(printf)`. `/*(*/` and `/*)*/` were used to match parentheses in the code, while a mix of parentheses and the comma operator were used to form chords from the `printf` parameters.

Edit: Shortened to fit size requirements as well as make the piece go a bit faster.

This sounds best on the piano.
> 4 votes

# Answer
# Scheme

This may not be particularly melodic (actually it sounds like somebody dropped a dead pig into a baby-grand), but at least it is a short piece of music. It would be difficult to make anything much longer or less dead-flying-pig-like in scheme.

```
((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x))))

```
> 3 votes

# Answer
# Für Golfscript

```
":H;GHGHCFDA;[34]H+2*{-};":H;GHGHCFDA;[34]H+2*{-};

```

This satisfies the letter of the no-three-consecutive-letter-removal rule, though not the intent, I gather.
> 2 votes

# Answer
# Cobra / Batch

```
@number float# 2>nul||@echo off
/# 2>nul
for /f "delims=" %%a in (%0) do echo %%a
#/# 2>nul
class P# 2>nul
    def main# 2>nul
        r="# 2>nul"# 2>nul
        s="@number float{3}||@echo off{2}/{3}{2}for /f {1}delims={1} %%a in (%0) do echo %%a{2}#/{3}{2}class P{3}{2}    def main{3}{2}      r={1}{3}{1}{3}{2}       s={1}{0}{1}{3}{2}       Console.write(s,s,34to char,10to char){3}"# 2>nul
        Console.write(s,s,34to char,10to char,r)# 2>nul

```

Technically not a quine in Batch (it reads it's own source). It is however a quine in Cobra.

It sounds best with the piano mode, somewhat like ghost-level music from a Super Mario World-era video game.
> 1 votes

# Answer
# Pyth

```
J"+K+N+J+N+\K+N+K+NJ"K"J"+K+N+J+N+\K+N+K+NJ

```

Best played with the fourth setting (amount + and - change interval) at around 20, rest at defaults. Sounds best on the piano.
> 1 votes

# Answer
# Haskell

(I'm not sure whether the variable name violates the last rule.)

```
main=putStr$  jjlmjiebab ++ {--} show jjlmjiebab;jjlmjiebab = "main=putStr$  jjlmjiebab ++ {--} show jjlmjiebab;jjlmjiebab = "

```

Best played on piano with 1000 millisecond note duration and 250 millisecond note interval, with standard + and - values.
> 0 votes

---
Tags: popularity-contest, quine, music
---