title: Talent rolls in DSA

text:
# Question
Title: Talent rolls in DSA
Some friends and I have played some DSA (a mainly german tabletop RPG much like D&D). I was wondering what the chance on passing rolls are, so you will have to write some code to calculate it.

Your character is defined by stats (from 8 to 14) and (TV) Talent values (0 to 21). For now we will use climbing as an example.

### Talent tests

A talent (climbing) looks like this: (Courage-Dexterity-Strength) TV: 7. To test a character on a talent you roll on these stats with a 20-sided dice and try to get below or equal to the stat, if you do that well. If not, you can use your TV points to reduce the roll with a ratio of 1:1.

### Example

A hunter with courage 12, dexterity 13 and strength 14 is trying to climb a tree, his TV is 7.

He rolls a 3, the value is below 12 so he passed that roll.

Then he rolls a 17, 17 is 4 more than 13, so 4 TV get used up with 3 left.

For the last roll you get a 14, spot on passed.

All rolls are passed and the hunter managed to climb the tree, 3 TV are left.

### Input

4 values in any format you choose, taken from the standard input of your language. It has to be in this order though.

E.g. `12 13 14 7` or `12,13,14,7` or as an array {12,13,14,7} or mixed `[12, 14, 8], 3`

### Output

The chance of how often the rolls pass.

E.g. (for values above)`0.803`

```
12,14,8,3 = 0.322

11,11,12,11 = 0.840

```

For the bonus: Again formating is not the issue here, output it however you like but in following order:

```
failed/with 0/with 1/with 2/with 3/with 4/with 5/with 6/with 7

```

and so on until no TV is left.

```
12,13,14,7 = 0.197/0.075/0.089/0.084/0.078/0.073/0.068/0.063/0.273

12,14,8,3 = 0.678/0.056/0.051/0.047/0.168

```

### Challenge and rules and bonus

* You shall find out given the input the chance to pass the rolls to a +- 0.5% accuracy.
* -20% if your program also outputs the chances to pass with `n` TV (see output).
* This is , so shortest code in bytes wins!

# Answer
> 2 votes
# Pyth - ~~21~~ ~~20~~ 19 bytes

*Saved 1 bytes thanks to @ThomasKwa*

```
.Omgvzsg#0-VdQ^SyT3

```

Test Suite.

# Answer
> 1 votes
## Dyalog APL, 28 bytes

```
{(+/÷⍴)⍵≥∊+/¨0⌈(⊂⍺)-⍨¨⍳3⍴20}

```

This approach is the same as @Maltysen's. We can't be *sure* of 0.5% accuracy if we just draw a few thousand random dice rolls, so we instead take the average over all possible rolls. This takes the three stats as the left argument, and the talent value on the right.

Try it here!

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


title: Befunge Brain Teasers

text:
# Question
Title: Befunge Brain Teasers
### Introduction

For the ones wondering what Befunge exactly is, it is a two-dimensional stack based language made in 1993 by Chris Pressy. I made **7 brain teasers** that need to be solved in **Befunge-93**. This is quite an experimental challenge, but I thought it's worth a shot :). A full list of all commands used in Befunge-93 can be found here.

### How to play?

The task is a bit like a cops-and-robbers without the cops. It's just basically cracking submissions in order to get points. Every puzzle contains question marks. These must be replaced by any printable ascii character in the range `32 - 127`, that includes whitespace. See the following example:

```
??????@

```

Given is that the output must be `hi`. After some puzzling, we can find out that the solution was:

```
"ih",,@

```

**But!** You **do not** give the solution. That is for the prevention of cheating. You don't post the solution, but the **hash**. The hash is generated with the following snippet:

```
String.prototype.hashCode = function() { var namevalue = document.getElementById("inputname").value;  var namenumber = 123;for (var character = 0; character < namevalue.length; character++) {namenumber += namevalue.substring(0, 1).charCodeAt(0);}var hash = 123 + namenumber, i, chr, len;if (this.length === 0) {return 0;}for (i = 0, len = this.length; i < len; i++) {chr = this.charCodeAt(i);hash = ((hash << 5) - hash) + chr; hash |= 0; }hash = Math.abs(hash);if ((hash).toString(16).length < 20) {for (var rand = 123; rand < 199; rand++) {hash = hash * rand;if ((hash).toString(16).length >= 20) {  break; }}}return (hash).toString(16).substring(2, 12);};function placeHash() { var pretext = document.getElementById("inputhash").value; var resultinghash = pretext.hashCode(); document.getElementById("resulthash").innerHTML = 'Your hash: <span class="hashtext">' + resultinghash + "</span>";}
```

```
p {font-family: monospace;color: black;} .hashtext{color: red;font-weight:bold}
```

```
<div class="container"><p>Personal hash generator:<p><textarea id="inputhash" placeholder="Your submission" cols="40" rows="4"></textarea><br><textarea id="inputname" placeholder="Your name" cols="40" rows="1"></textarea><br><button class="hashbutton" onclick="placeHash()">Generate Hash!</button><br><p id="resulthash">Your hash:</p></div><!-- Created by Adnan -->
```

### How to use the snippet?

* First, paste the solution into the submission section
* Second, enter your username (nothing else, this will actually be verified after the time limit)
* Third, press **Generate Hash!** to obtain your *personal* hash.
* Copy and paste the hash into your submission.

### The puzzles

**Puzzle 1** (Score: 3)

```
 ??
???      ?
??????????
         @

```

Output (note the trailing whitespace):

```
1 2 3 4 5 6 7 8 9 10

```

---

**Puzzle 2** (Score: 3)

```
 ????    ?
??????????
??       ?
         @

```

Output:

```
abcdefghijklmnopqrstuvwxyz

```

---

**Puzzle 3** (Score: 5)

```
  ?????????
    ?????  ???
    ?     ?
    ? ?   ?  ?
          ?
          ?  ?
  ??????  ?  ?
    ?     ?  ?
       ?  ?  @
  ??????? ?
    ?  ?
????  ??
?  ??

```

Output:

```
Hello World!

```

---

**Puzzle 4** (Score: 2)

```
??????@

```

Output (note the trailing whitespace):

```
123

```

---

**Puzzle 5** (Score: 5)

```
    ?
  ?????
???@?????
 ??????
?????????

```

Output:

```
Befunge

```

---

**Puzzle 6** (Score: 5)

```
?    ?   ?
     ?
??????????
     ?
     ?
     ????????                         ??????????????
     ?????"floG edoC dna selzzuP gnimmargorP "??????
     @

```

Output:

```
###################################
 Programming Puzzles and Code Golf
###################################

```

---

**Puzzle 7** (Score: 3)

```
???? ?????
   ???????
  @???????

```

Output:

```
012345678910

```

---

* This is , the person with the most amount of points wins!
* In case of a tie, the person who submitted *all* submissions first, wins.
* The **last day for submission** is **January 10 UTC**. After that, you have 2 days to post the full solution, with the hashes already included. These will be verified :).

### How to post?

Use the following snippet to post your submission:

```
#N solutions:

Puzzle 1: `[hash 1]`

Puzzle 2: `[hash 2]`

etc.

```

It is not necessary to solve the puzzles in order. **All programs have been tested here** and will be used for verification.

Good luck!

# Answer
> 5 votes
# 7 solutions, 26 points

I'm typing this on my phone, because I don't have access to my computer currently. I actually had to work out Puzzle 6 by pen & paper.

### Puzzle 1 (Score **3**): `4f52d5b243`

```
 1v
v:<      <
>.1+:56+-|
         @

```

This one is fairly straight forward. Get a `1` on the stack, then print-increment-compare-loop until `11` is hit.

### Puzzle 2 (Score **3**): `85226eba20`

```
 "`"     v
v"z":,:+1<
>-       |
         @

```

Basically the same as the previous one, just with characters instead of numbers. Used a different IP route though.

### Puzzle 3 (Score **5**): `1ff5bcb1d9`

```
  "!dlroW"v
    >,,,,  ,,v
    ,     "
    , ?      ,
          o
          l
  ??,???  l
    ,     e
       ?  "  @
  ??^,"H" <
    ?  ?
????  ??
?  ??

```

Here I cheaped out a little bit. Push the string to the stack and print characters manually, navigating through the spaces. I had loads of extra room, so I just left most of the question marks in. Note the trailing spaces on rows 6 to 8, I didn't remove them when calculating the hash.

### Puzzle 4 (Score **2**): `f8b7bdf741`

```
"{".  @

```

Really simple, just get the character with the correct code and print as a number, with two free spaces.

### Puzzle 5 (Score **5**): `c4db4b6af9`

```
    v
  ??"??
#,_@e">>:
 <"B"<^
ung"<^"ef

```

This was a fun one to get right. May not work correctly on some interpreters due to wrapping strings & jumps, works on the linked one. Basically, the code pushes the output string and then enters the standard printing loop, wrapping on the sides.

### Puzzle 6 (Score **5**): `356e912eec`

```
1        v
     #
     v??v_

     5
      75<^                              p15:-1g15,:*
     >5+:,"floG edoC dna selzzuP gnimmargorP ">:#,_@
     @

```

Now this was the "masterpiece". I actually took a piece of paper and spent some time on this. (Actually, I did some extra work by missing the space in the string when copying.) Note the trailing spaces on row 4, I didn't remove them when calculating the hash.

The code works by first pushing a one to enter the main loop. The loop uses the `#` on the second line as a counter, and both prints and pushes a `#` on every iteration. After that a newline is printed and pushed. Next, the given string is pushed. Finally, the code enters a printing loop, which prints everything on the stack in reverse, which means the string, then the newline, and finally the remaining `#`s.

### Puzzle 7 (Score **3**): `0881fc2619`

```
"0"> :,1+v
   |-":":<
  @>"10",,

```

This is almost the same as Puzzle 2, but with a different route, different output characters, an additional `01` in the end and a quick wrap to finish it off.

# Answer
> 3 votes
## 4 solutions, 15 points

I hope I didn't mess up the trailing whitespace anywhere when generating the hashes.

### Puzzle 1 (Score **3**): `de1de4c4c8`

```
 v
v<       >
>1+:.:9`!|
         @

```

### Puzzle 3 (Score **5**): `071cad0879`

```
  "!dlroW"v
    >,,,,  ,,v
    ,     "
    ,        ,
          o
          l
    ,     l
    ,     e
          "  @
    ^,"H" <

```

### Puzzle 4 (Score **2**): `531940bc43`

```
"{".  @

```

### Puzzle 5 (Score **5**): `5bafaed8e9`

```
    ^
  v >,,
n"<@,, ,"
 "e"^>,
uge"<^"Bf

```

---
Tags: code-challenge, programming-puzzle, befunge
---


title: Pronoun operation

text:
# Question
Title: Pronoun operation
## The challenge

Write a function or a program that takes a string composed of one or more **subjective personal pronouns**, separated by **+** signs, as an argument. The output must be a single pronoun, that is the result of the relation defined in the next paragraph.

Of course, feel free to edit as you wish to correct those grammatical errors that are surely present ;)

This is a code-golf challenge, so the shortest code wins.

## The relation

The goal of this task is to translate in "math-speak" something that we use daily. How do we think of "You and I" ? Well, "We", don't we? So, if the input is `You+I` the output should be the string `We`. With more than two pronouns, it should look like: `You+He+They` -\> `You`

The relation is defined as this table:

```
      I  You    He   We   You   They
I     I  We     We   We   We    We
You      You    You  We   You   You
He              He   We   You   They
We                   We   We    We
You                       You   You
They                            They

```

## The 'You' Problem

Well, as you can see I'm not a native English speaker. In my language (Italian) there's a difference between the plural *you* (*voi*, in italian) and the singular *you* (*tu*). When I thought this challenge I didn't think in English, so there's the problem that it is impossible to recognize if I'm using plural or singular form. Fortunately (or obviously?), the input/output doesn't change in both forms, so you can use one of them and you will cover both cases!

## About the input

The input will be always in the form "Pronoun+Pronoun+Pronoun" ... The pronouns will have the first letter in uppercase and the rest in lowercase. Pluses will be not be surrounded by spaces, only by pronouns. Empty input is possible and the result must be empty output.

## Bonus

A little bonus of 15% if the program will manage two new pronouns: **She** and **It**. They are the same as He, obviously. Remember that this relation is reflexive, so She -\> She and It -\> It. Therefore, any combination that includes only She, He or It should output They.

## Examples

```
You+I          -> We
You+He+They    -> You
I+You+He+They  -> We
They           -> They
They+You       -> You
You+You+I+You  -> We

For Bonus
She            -> She
She+He         -> They
I+It+He        -> We
It+You         -> You

```

# Answer
# Retina, ~~62 61 56 53~~ 52 bytes

```
(.+)\+(?=\1)

.*(W|.I|I.).*
We
.*Y.*
You
.{4,}
They

```

Further golfing and explanation comes later.

The 4 substitution steps do the following:

* anything multiple times is itself
* if there is any We or I + anyhing the result is We
* for anything else containing You the result is You
* if we still have multiple parts or a sole They it's They as only He's and They's can be left

Try it online here.

*3 bytes saved thanks to Martin Büttner.*
> 9 votes

# Answer
# JavaScript (ES6), 130 bytes

```
s=>(a=",I,You,He,We,They".split`,`,m="012345014444042242042345044444042545",r=0,s.split`+`.map(p=>r=m[+m[a.indexOf(p)]+r*6]),a[r])

```

## Explanation

```
s=>(

  // a = array of each pronoun (including an empty string at index 0)
  a=",I,You,He,We,They".split`,`,

  // m = 6 x 6 map of pronoun indices for each combination of pronouns
  m="012345014444042242042345044444042545",

  r=0,                        // r = index of result pronoun
  s.split`+`.map(p=>          // for each pronoun in the input string
    r=m[+m[a.indexOf(p)]+r*6] // combine each pronoun with the previous one
  ),
  a[r]                        // return the resulting pronoun
)

```

## Test

```
var solution = s=>(a=",I,You,He,We,They".split`,`,m="012345014444042242042345044444042545",r=0,s.split`+`.map(p=>r=m[+m[a.indexOf(p)]+r*6]),a[r])
```

```
<input type="text" id="input" value="You+You+I+You" />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
```
> 6 votes

# Answer
# Python ~~159~~ 153 bytes

**EDIT**: Thanks @Pietu1998

This is a direct translation of the Javascript ES6 answer:

```
a=",I,You,He,We,They".split(',')
m="012345014444042242042345044444042545"
r=0
for p in raw_input().split('+'):r=int(m[int(m[a.index(p)])+r*6])
print a[r]

```

Try it here
> 2 votes

# Answer
## Perl 5, 67 bytes

79 bytes really, but there's a 15% bonus.

```
$a{$_}=""for split/[+\s]/,<>;@_=%a;say@_<3?@_:I~~@_||We~~@_?We:You~~@_?You:They

```
> 1 votes

# Answer
# Ruby, ~~150~~ ~~136~~ ~~131~~ ~~119~~ 111 bytes

```
ARGV.each{|a|puts %w[We You I He They][a.bytes.inject(0){|m,c|m|({87=>15,73=>7,89=>11,84=>9,72=>8}[c]||0)}%5]}

```

Bonus feature: handles multiple expressions on the same command line.
> 1 votes

---
Tags: code-golf, natural-language
---


title: Pathological Sorting

text:
# Question
Title: Pathological Sorting
# Pathological Sorting

Your boss has demanded that you develop a sorting algorithm to improve the performance of your company's application. However, having written the application, you know that you're unlikely to be able to make it significantly faster. Not wanting to disappoint your boss, you've decided to develop a new algorithm that works even better than \*sort on certain sets of data. Of course, you can't make it obvious that the algorithm only works on some cases, so you want to make it obscure as possible.

The objective of this contest is to write a sorting routine in the language of your choice that performs better on certain sets of data than others, with repeatable results. The more specific the classification that determines speed, the better. The algorithm must do sorting of some kind, so an algorithm that depends on the data already being completely sorted (as in, an algorithm that does nothing), or an algorithm that depends on the data being completely sorted in reverse, are both invalid. The sorting algorithm must correctly sort any set of data.

After presenting your routine, please include an explanation of why it only works on certain sets of data, and include test runs on at least one set of good (fast) data and one set of bad (slow) data. The point here is to be able to prove to your boss that you've stumbled upon a better way to sort, so more test data is better. Of course, you're only going to show your boss the test results from the good data, so the flaw in the required testing data can't be too obvious. If applicable to your language, please show that your algorithm is faster than your language's built-in sorting algorithm.

For example, one might submit an insertion sort algorithm, with the good data being data that is already nearly sorted, and bad data being completely random data, since insertion sort approaches O(n) on nearly-sorted data. However, this isn't very good, since my boss would probably notice that all of the testing data is nearly sorted to begin with.

This is a , so the answer with the most votes after 7 days (May 21) wins.

If no one beats me to it, I'd like to submit a community wiki answer that takes advantage of uniformly distributed data sets.

# Answer
> 9 votes
It's been a pretty long time, but I remember back in Algorithms 101 we were taught some sorting algorithm that used randomization. I wasn't a very good student so I don't really remember how it went or why it worked quickly on average.

Nevertheless, I've decided that this problem calls for a solution that uses randomization, which will hopefully work in my favor on average.

```
import random

def arrayIsSorted (arr) :
    for i in range(len(arr)-1) :
        if arr[i]>arr[i+1] : return False
    return True

def rSort (arr) :
    random.seed (42)
    counter = 0
    while not arrayIsSorted(arr) :
        random.shuffle (arr)
        counter+=1
    print ("Sorted in %d iterations." % counter)
    return arr

```

Since true randomization is important, I make sure to seed the RNG with the answer to Life, the Universe and Everything. After a bit of testing it turns out that that was a smart move! Check out how fast these 2 completely arbitrary lists get sorted:

```
rSort ([6,1,4,2,3,7,5])
rSort ([8,9,6,1,4,7,2,3,5])

```

Both of these get sorted in only 1 iteration - you couldn't possibly ask for a faster function than that!

Now, admittedly, some other lists produce slightly worse results...

```
rSort ([5,1,4,2,3,7,6])
rSort ([8,9,6,1,4,7,2,5,3])

```

These get sorted in 4,176 and 94,523 iterations respectively, which actually takes more than a second... but let's just keep that fact to ourselves so as not to distract anyone from how amazing this algorithm is!

Edit:

I've been asked to prove my algorithm's efficiency on a list of 100 items, so here you go:

```
rSort ([70, 6, 52, 97, 85, 61, 62, 48, 30, 3, 11, 88, 39, 91, 98, 8, 54, 92, 44, 65, 69, 21, 58, 41, 60, 76, 27, 82, 93, 81, 20, 94, 22, 29, 49, 95, 40, 19, 55, 42, 43, 1, 0, 67, 35, 15, 51, 31, 16, 25, 5, 53, 37, 74, 86, 12, 13, 72, 56, 32, 47, 46, 59, 33, 80, 4, 45, 63, 57, 89, 7, 77, 14, 10, 34, 87, 18, 79, 9, 66, 24, 99, 64, 26, 78, 38, 90, 28, 83, 75, 68, 2, 17, 73, 96, 71, 23, 84, 36, 50])

```

Even this long and completely arbitrary list gets sorted instantly! Truly I must have stumbled upon the best sorting algorithm in the world!

# Answer
> 2 votes
If you can create your own data, then it's pretty straightforward - get data that looks random, but includes a key for faster sorting. All other data uses the original sorting method, so the *average* times are better.

One easy way is to make sure each data item has a unique key, and then just hash the keys. Take for example a list with the numbers from 1-10,000, all multiplied by 16, and with a random number from 0-15 added to it (see **fillArray()** below). They will look random, but each one has a unique sequential key. For sorting, divide by 16 (in C the \>\>4 is very fast) and then just place the number into an array using the resulting key as the index. One pass and you're done. In testing, I found quicksort was 30 times slower on ten million numbers.

```
void fillArray(int *a,int len)
{
  for (int i=0;i<len;++i)
    a[i]=(i<<4)|(rand()&0xF);
  // shuffle later
}
void sortArray(int *a,int len)
{
  int key=0;
  int *r=new int[len];
  for (int i=0;i<len;++i)
  {
    key=a[i]>>4;
    r[key]=a[i];
  }
  memcpy(a,r,len*sizeof(int));
  delete[] r;
}
void shuffleArray(int *a,int len)
{
  int swap=0, k=0;
  for (int i=0;i<len;++i)
  {
    k=rand()%len;
    swap=a[k];
    a[k]=a[i];
    a[i]=swap;
  }
}
int qCompare(const void*a,const void*b)
{
  int result=*((int*)a)-*((int*)b);
  return result;
}
void main()
{
  int aLen=10000;
  int *a=new int[aLen];
  srand (time(NULL));
  fillArray(a,aLen);
  // time them
  long t0=0, d0=0, d1=0;
  // qsort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  qsort(a,aLen,sizeof(int),&qCompare);
  d0=::GetTickCount()-t0;
  // oursort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  sortArray(a,aLen);
  d1=::GetTickCount()-t0;
  delete[] a;
}

```

Anything that has a unique key can be sorted this way - if you have the memory to store it, of course. For example, many databases use a unique numeric customer id - if the list is small/sequential enough this could be held in memory. Or some other way to translate a record into a unique number. For more info, research Hash Sorts, since that's what this is...

---
Tags: popularity-contest, sorting, underhanded
---


# Question
Title: Eternal 2014 — PCG.SE New Year’s Puzzle 2015
So, now that it's 2015, and a bunch of answers from last year's puzzle are now starting to produce invalid output, it's time for a question involving the number 2015.

Except... why? Wouldn't you like it if your date-based answers to last year's problem were to stay valid? Why don't we change our calendar so that it's *never* 2015, and we simply continue living in 2014, forever and ever?

Let's define a new date notation, called **Eternal 2014 notation**, as follows:

> * For dates 2014 and before, the dates will be the same as in the proleptic Gregorian calendar.
> * For dates in years 2015 and onward, the year will stay 2014, and the month will be the number it would be if the same month cycle in 2014 were to continue forever past month 12. So `2015-02-08` would be `2014-14-08`, and `2020-12-31` would be `2014-85-02`. Note that leap days are not accounted for because 2014 is not a leap year.

Your task is to build a program or function that will take a Julian astronomical date as input and return a string with the date corresponding to that Julian date in Eternal 2014 notation, in either `YYYY-MM-DD` or `DD/MM/YYYY` format.

You may assume that the Julian day entered will always be an integer from `1721426` (January 1, 1) to `2914695` (January 23, 3268) inclusive. Years may contain leading zeros to pad to 4 digits or not, but months and days must always have leading zeros to pad to two digits (and years may not contain leading zeros to pad to any number of digits other than 4).

Here are some example inputs and their outputs, in all acceptable formats:

```
> 1721426
1-01-01
01/01/1
0001-01-01
01/01/0001

> 2086302
999-12-31
31/12/999
0999-12-31
31/12/0999

> 2456659
2014-01-01
01/01/2014

> 2456789
2014-05-11
11/05/2014

> 2457024
2014-13-01
01/13/2014

> 2457389
2014-25-01
01/25/2014

> 2469134
2014-411-07
07/411/2014

> 2567890
2014-3657-29
29/3657/2014

> 2914695
2014-15059-23
23/15059/2014

```

You may not use any built-in date processing libraries in your language. All calculations must be done algorithmically within the program's source code itself.

The shortest program (in bytes) to achieve this in any language wins.

# Answer
## Python 2, 166 bytes

```
n=input()
d=m=y=1
M=([3]+[3,2]*3)*2
while n>1721426:
 n-=1;d+=1;M[2]=y%400<1or y%4<1<y%100
 if d>M[m%12]+28:m+=1;d=1
 if m>12<2014>y:y+=1;m=1
print'%02d/'*2%(d,m)+`y`

```

This cycles through every day from January 1, 1 (1721426) to the given date, incrementing the current day, month and year as it goes. The last test case takes about a second on my computer.

Output is printed in the second format:

```
01/01/1
31/12/999
23/15059/2014

```
> 12 votes

# Answer
# Ostrich 0.5.0, 197 bytes

```
G~:J1401+4J*274227+146097/F3*4/F+38~+:f4*3+:e1461:p%4/F:g5*2+:h153:s%5/F1+:D;hs/F2+12:n%1+:M;ep/F4716-n2+M-n/F+:Y;{2014:Y;D365+:D;{M1-12%[31:x28x 30:yxyxxyxyx]=:dD<.{Dd-:D;M1+:M;}*}(}Y2014-*D"/M"/Y

```

Ungolfed (ha):

```
G~:J;
4716:y;1401:j;2:m;12:n;4:r;1461:p;3:v;5:u;153:s;2:w;274277:B;38~:C;
Jj+4J*B+146097/F3*4/F+C+:f;
rf*v+:e;
ep%r/F:g;
ug*w+:h;
hs%u/F1+:D;
hs/Fm+n%1+:M;
ep/Fy-nm+M-n/F+:Y;
{
2014:Y;
D365+:D;
{
M1-12%[31 28 31 30 31 30 31 31 30 31 30 31]=:d
D<.{Dd-:D;M1+:M;}*
}(
}Y2014-*
D"/M"/Y

```

I'm... really just exhausted from all the New Year's happiness and what not. That's why I haven't golfed this very much. I may or may not come back to make it better later.

Algorithm from https://en.wikipedia.org/wiki/Julian\_day#Gregorian\_calendar\_from\_Julian\_day\_number
> 3 votes

# Answer
## PHP (278)

Run on command line using `php -R '<code>'`. (The flag counts as one character.)

```
if(0<$N=($n=$argn-1721426)-735233){$n=$N%365+735233;$o=12*($N/365|0);}for($y=1+400*($n/146097|0)+100*(($n%=146097)/36524|0)+(($n%=36524)/1461<<2)+(($n%=1461)/365|0);($n%=365)>=$d=@++$m-2?30+($m+($m>>3)&1):29-($y%4||!($y%100)&&$y%400);)$n-=$d;printf("$y-%02d-%02d",$m+@$o,$n+1);

```

More readable version (run using filename and without `-R`):

```
<?php

// step 1: read the input and fix up 2014 dates
if (0 < $N = ($n = fgets(STDIN) - 1721426) - 735233) {
    $n = $N % 365 + 735233; // wrap around to 2014-01-01
    $o = 12 * ($N / 365 | 0); // compute month offset
}

for (

// step 2: extract year
$y = 1
    + 400 * ($n / 146097 | 0)
    + 100 * (($n %= 146097) / 36524 | 0)
    + (($n %= 36524) / 1461 << 2)
    + (($n %= 1461) / 365 | 0);

// step 3: extract month and day
($n %= 365) >= $d = @++$m - 2
    ? 30 + ($m + ($m >> 3) & 1)
    : 29 - ($y % 4 || !($y % 100) && $y % 400);

) $n -= $d;

// step 4: print date string, adding the month offset
// previously computed in step 1.
printf("$y-%02d-%02d", $m + @$o, $n + 1);

```
> 0 votes

# Answer
# C 176

**Thanks to @ceilingcat for some very nice pieces of golfing - now even shorter**

```
y=1;m;d;main(n,a)int**a;{for(n=atoi(a[1]);n-->1721426;)++d>(~m%2+m%12/7?30:m%12-1?29:y%(y%100?4:400)?27:28)&&(d=!++m,m>11&y<2014)&&(m=!++y);printf("%d-%02d-%02d\n",y,m+1,d+1);}

```

It uses the same algorithm as the Python 2 answer by @grc

Try it online!
> 0 votes

---
Tags: code-golf
---


# Question
Title: Make the pattern from composition notebooks
This challenge was xnor's idea, taken from Digital Trauma's challenge donation thread.

---

Your challenge is to write a program that, as xnor put it, "procedurally generate\[s\] the splotchy black-and-white marbled pattern on the covers of composition notebooks":

Your program can either display it on the screen or save it in a file. The image should be at least 300 pixels in each dimension, and it should be different between runs of the program. Your program should not just load an external image and use that as its output; the image should be generated by your program.

This is a , and it will use xnor's criteria for voting:

* Similarity to the reference texture above.
* Simplicity of generation method.

# Answer
> 16 votes
# Mathematica

```
Blur[Binarize[Blur[RandomImage[1, {1000, 1000}, ImageSize -> Large], 6], .52]]

```

Quite simple. Creates a random grayscale image, blurs it, takes the pixels above a threshold, and blurs it again. It uses a couple of hand-tweaked values. The result:

---
Tags: popularity-contest, graphical-output
---


title: How Slow Is Python Really (Part II)?

text:
# Question
Title: How Slow Is Python Really (Part II)?
This is a follow up to How slow is Python really? (Or how fast is your language?).

It turns out it was a bit too easy to get a x100 speedup for my last question. For those who have enjoyed the challenge but want something harder where they can really use their low level skills, here is part II. The challenge is to get a x100 speedup for the following python code as tested on my computer.

To make it more difficult I am using pypy this time. The current timing for me is **1 minute and 7 seconds** using pypy 2.2.1.

**Rules**

1. The first person to submit code which I can run, is correct and is x100 times faster on my machine will be awarded a bounty of 50 points.
2. I will award the win to the fastest code after a week.

```
import itertools
import operator
import random

n = 8
m  = 8
iters = 1000

# creates an array of 0s with length m
# [0, 0, 0, 0, 0, 0, 0, 0]
leadingzerocounts = [0]*m

# itertools.product creates an array of all possible combinations of the
# args passed to it.
#
# Ex:
#   itertools.product("ABCD", "xy") --> Ax Ay Bx By Cx Cy Dx Dy
#   itertools.product("AB", repeat=5) --> [
#    ('A', 'A', 'A', 'A', 'A'),
#    ('A', 'A', 'A', 'A', 'B'),
#    ('A', 'A', 'A', 'B', 'A'),
#    ('A', 'A', 'A', 'B', 'B'),
#    etc.
#   ]
for S in itertools.product([-1,1], repeat = n+m-1):
    for i in xrange(iters):
        F = [random.choice([-1,0,0,1]) for j in xrange(n)]

        # if the array is made up of only zeros keep recreating it until
        # there is at least one nonzero value.
        while not any(F):
            F = [random.choice([-1,0,0,1]) for j in xrange(n)]

        j = 0
        while (j < m and sum(map(operator.mul, F, S[j:j+n])) == 0):
            leadingzerocounts[j] +=1
            j += 1
print leadingzerocounts

```

The output should be similar to

```
[6335185, 2526840, 1041967, 439735, 193391, 87083, 40635, 19694]

```

You must use a random seed in your code and any random number generator that is good enough to give answers close to the above will be accepted.

**My Machine** The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code.

**Explanation of code**

This code iterates over all arrays S of length n+m-1 that are made up for -1s and 1s. For each array S it samples 1000 non-zero random arrays F of length n made up of -1,0 or 1 with probability of 1/4, 1/2,/14 of taking each values. It then computes the inner products between F and each window of S of length n until it finds a non-zero inner product. It adds 1 to `leadingzerocounts` at each position it found a zero inner product.

**Status**

* **Perl**. 2.7 times slowdown by @tobyink. (Compared to pypy not cpython.)
* **J**. 39 times speedup by @Eelvex.
* **C**. 59 times speed up by @ace.
* **Julia**. 197 times faster not including start up time by @one-more-minute. 8.5 times speed up including start up time (it's faster using 4 processors in this case than 8).
* **Fortran**. 438 times speed up by @semi-extrinsic.
* **Rpython**. 258 times speed up by @primo.
* **C++**. 508 times speed up by @ilmale.

(I stopped timing the new improvements because they are too fast and iters was too small.)

---

It was pointed out that timings below a second are unreliable and also some languages have a start-up cost. The argument is that if you are to include that you should also include the compilation time of C/C++ etc. Here are the timings for the fastest code with the number of iterations increased to 100,000.

* **Julia**. 42 seconds by @one-more-minute.
* **C++**. 14 seconds by @GuySirton.
* **Fortran**. 14s by @semi-extrinsic.
* **C++**. 12s by @ilmale.
* **Rpython**. 18s by @primo.
* **C++**. 5s by @Stefan.

## **The winner is.. Stefan!**

Follow-up challenge posted. How high can you go? (A coding+algorithms challenge) . This one is harder.

# Answer
> 14 votes
# C++ bit magic

## ~16ms multithreaded, 56ms singlethreaded. ~4000 speedup.

(speedup is based on multithreaded code on my i7-2820QM and the 1 min 9 seconds mentioned in the question. Since the OP's system has worse single threaded performance than my CPU but better multi threaded perfiormance i expect this number to be accurate)

The multithreaded part is quite inefficient due to the spawning of threads. I could probably do better by leveraging my custom job library but that one has bugs under unix systems.. For an explanation and almost identical code without threading refer to https://codegolf.stackexchange.com/a/26485/20965.

### edit

I gave each thread it's own RNG and cut down the bit length to 32 which reduced the runtime by a few ms.

```
#include <iostream>
#include <bitset>
#include <random>
#include <chrono>
#include <stdint.h>
#include <cassert>
#include <array>
#include <tuple>
#include <memory>
#include <thread>
#include <future>
#include <string.h>

#ifdef _MSC_VER
uint32_t popcnt( uint32_t x ){ return _mm_popcnt_u32(x); }
#else
uint32_t popcnt( uint32_t x ){ return __builtin_popcount(x); }
#endif

void convolve()
{
    static const unsigned threadCount = 32;
    static const unsigned n = 8;
    static const unsigned m = 8;
    static const unsigned totalIters = 1000;
    static_assert( n <= 16, "packing of F fails when n > 16.");
    static uint32_t fmask = (1 << n) -1; fmask |= fmask << 16;

    std::array< uint32_t, m * threadCount > out;
    std::vector< std::future<void> > threads;

    for( int threadId = 0; threadId < threadCount; threadId++)
    {
        threads.emplace_back( std::async( [&, threadId]
        {
            std::random_device rd;
            std::knuth_b gen(rd());
            uint32_t nextRandomNumber = gen();

            const unsigned iters = totalIters / threadCount;

            std::array< uint32_t, m > leadingZeros;
            for( auto& x : leadingZeros )
                x = 0;

            for( unsigned i = 0; i < iters; i++ )
            {
                // generate random bit mess
                uint32_t F;
                do {
                    // this funky looking construction shortens the dependancy chain of F
                    F = nextRandomNumber & fmask;
                    nextRandomNumber = gen();
                } while ( 0 == ((F % (1 << n)) ^ (F >> 16 )) );

                // Assume F is an array with interleaved elements such that F[0] || F[16] is one element
                // here MSB(F) & ~LSB(F) returns 1 for all elements that are positive
                // and  ~MSB(F) & LSB(F) returns 1 for all elements that are negative
                // this results in the distribution ( -1, 0, 0, 1 )
                // to ease calculations we generate r = LSB(F) and l = MSB(F)

                uint32_t r = F % ( 1 << n );
                // modulo is required because the behaviour of the leftmost bit is implementation defined
                uint32_t l = ( F >> 16 ) % ( 1 << n );

                uint32_t posBits = l & ~r;
                uint32_t negBits = ~l & r;
                assert( (posBits & negBits) == 0 );

                uint32_t mask = posBits | negBits;
                uint32_t totalBits = popcnt( mask );
                // if the amount of -1 and +1's is uneven, sum(S*F) cannot possibly evaluate to 0
                if ( totalBits & 1 )
                    continue;

                uint32_t adjF = posBits & ~negBits;
                uint32_t desiredBits = totalBits / 2;

                uint32_t S = (1 << (n + m -1));
                // generate all possible N+1 bit strings
                // 1 = +1
                // 0 = -1
                while ( S-- )
                {
                    for( int shift = 0; shift < m; shift++ )
                    {
                        uint32_t s = (S >> shift) % ( 1 << n );
                        auto firstBits = (s & mask) ^ adjF;

                        if ( desiredBits == popcnt( firstBits ) )
                        {
                            leadingZeros[shift] = leadingZeros[shift] + 1;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }

            memcpy( out.data() + (threadId * m), leadingZeros.data(), sizeof( leadingZeros[0] ) * m );
        } ));

    };

    std::array< uint32_t, m > leadingZeros;
    for( auto& x : leadingZeros )
        x = 0;

    for( auto& thread : threads )
    {
        thread.wait();
    }

    for( int i = 0; i < (threadCount * m); i++ )
    {
        leadingZeros[i % m] += out[i];
    }

    for( auto x : leadingZeros )
        std::cout << x << ", ";

    std::cout << std::endl;
}

int main()
{
    typedef std::chrono::high_resolution_clock clock;
    int rounds = 100;

    // do some rounds to get the cpu up to speed..
    for( int i = 0; i < rounds / 10; i++ )
    {
        convolve();
    }

    auto start = clock::now();

    for( int i = 0; i < rounds; i++ )
        convolve();

    auto end = clock::now();
    double seconds = std::chrono::duration_cast< std::chrono::microseconds >( end - start ).count() / 1000000.0;

    std::cout << seconds/rounds*1000 << " msec/round" << std::endl;

    return 0;
}

```

Sample output:

```
   6317312, 2515072, 1034368, 434048, 190144, 85200, 39804, 19168,
   6226944, 2481408, 1031168, 438080, 192896, 86816, 40484, 19490,
   6321152, 2524672, 1045376, 442880, 195680, 88464, 41656, 20212,
   6330624, 2517504, 1031104, 430208, 187696, 83976, 38976, 18708,
   6304768, 2510336, 1030720, 433056, 190880, 86824, 40940, 19840,
   6272512, 2494720, 1028160, 432352, 189168, 84752, 39540, 19052,
   6233600, 2507520, 1046912, 447008, 198224, 89984, 42092, 20292,

```

# Answer
> 17 votes
# C++ x150 x450 x530

Instead of array I used bits (and dark magic).
Thanks @ace for the faster random function.

How does it work: the first 15th bits of the integer `s` represent the array `S[15]`; the zeroes represent -1, the ones represent +1. The array `F` is build in a similar way. But with two bit for each symbol.

* 00 represent -1
* 01 and 10 represent 0
* 11 represent 1

Cause `S` and `F` have a different representation I have to interleave `S` with itself to be comparable with `F`.

* 0 (-1) became 00 (-1 in the representation of `F`)
* 1 (+1) became 11 (+1 in the representation of `F`)

Now we can simply use Carnot to compute the inner product. Remember that one variable can only assume value 00 or 11

0 . 00 = 11 (-1 * -1 = +1)
0 . 01 = 10 (-1 * 0 = 0)
0 . 10 = 01 (-1 * 0 = 0)
0 . 11 = 00 (-1 * +1 = -1)
1 . 00 = 00 (+1 * -1 = -1)
1 . 10 = 10 (+1 * 0 = 0)
1 . 01 = 01 (+1 * 0 = 0)
1 . 11 = 11 (+1 * +1 = +1)

Looks like a not xor to me. :)

Sum the ones is just a game of shift and mask, nothing really complex.

```
#include <array>
#include <ctime>

// From standford bithacks
// http://graphics.stanford.edu/~seander/bithacks.html
inline int32_t interleaveBit(int32_t x)
{
   static const uint32_t B[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
   x = (x | ( x << 8)) & B[3];
   x = (x | ( x << 4)) & B[2];
   x = (x | ( x << 2)) & B[1];
   x = (x | ( x << 1)) & B[0];
   return x | (x << 1);
}

inline int32_t sumOnes(int32_t v)
{
   static int b[] = { 1, 0, 0, 1};
   int s = 0;
   for( int i = 0; i < 8; ++i)
   {
      const int a = 3&(v>>(i*2));
      s += b[a];
   }
   return s;
}

inline int32_t sumArray(int32_t v)
{
   static int b[] = { -1, 0, 0, 1};
   int s = 0;
   for( int i = 0; i < 8; ++i)
   {
      const int a = 3&(v>>(i*2));
      s += b[a];
   }
   return s;
}

uint32_t x, y = 24252, z=57768, w=1564; //PRNG seeds

int32_t myRand()
{
   uint32_t t;
   t = x ^ (x<<1);
   x = y;
   y = z;
   z = w;
   w = w ^ ( w >> 19) ^ t ^ (t >> 8);
   return w;
}

int main()
{
   std::array<int, 8> leadingZero{0};
   x = static_cast<int32_t>(time(nullptr)); // seed PRNG
   const int maxS = 1 << 15;
   for(int s = 0; s < maxS; ++s)
   {
      const int32_t x = interleaveBit(s);
      for(int i = 0; i < 1000; ++i)
      {
         int32_t random;
         do
         {
            random = 0xFFFF & myRand();
         }while(sumOnes(random) == 0);
         int j = 7;
         while( j >= 0 )
         {
            const int32_t h = (x >> (j*2));
            const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
            if(sumArray(l) == 0)
            {
               leadingZero[j]++;
            } else
            {
               break;
            }
            j--;
         }

      }
   }
   for(int i = 7; i >= 0; --i)
   {
      printf("%d ", leadingZero[i]);
   }
   printf("\n");
   return 0;
}

```

Here a sample output:

```
6332350 2525218 1041716 438741 192917 87159 41023 19908

real 0m0.372s
user 0m0.371s
sys  0m0.001s

```

The program has been compiled with:

```
gcc -std=c++11 -O3 -msse4.2 -Wall -lstdc++ 26371.cpp -o fastPy

```

on Fedora 20 with gcc 4.8.2 The Cpu is a i7 8core.

Probably I can gain some ms tweaking compiler parameters.

While this is the OP solution time on my machine:

```
time pypy 26371.py
[6330609, 2523914, 1040885, 439303, 192708, 86987, 40710, 19498]

real 0m53.061s
user 0m53.016s
sys  0m0.022s

```

---

Edit:

Just adding openmp and change the order of the for I have a x3 gain, leading to a x450 performance improvement against OP code. :D In this case the `leadingZero` array must be atomic. The random global... are random, they will be more random.

```
 #pragma omp parallel for
 for(int i = 0; i < 1000; ++i)
 {
    int32_t random;
    do
    {
       random = 0xFFFF & myRand();
    }while(sumOnes(random) == 0);
    for(int s = 0; s < maxS; ++s)
    {
       const int32_t x = interleaveBit(s);
       int j = 7;
       while( j >= 0 )
       {
          const int32_t h = (x >> (j*2));
          const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
          if( sumArray(l) == 0 )
          {
             leadingZero[j]++;
          } else
          {
             break;
          }
          j--;
       }
    }
 }

```

need to add `-fopenmp` to the compiler flag

---

Edit:2 As suggester by user71404 I changed the sumOnes and sumArray functions and now it's uber fast.

```
real  0m0.101s
user  0m0.101s
sys   0m0.000s

```

With openmp is slower, cause the atomics add too much overhead.

```
real  0m0.253s
user  0m1.870s
sys   0m0.001s

```

Without atomics is even faster, but I get wrong result.

2137992 1147218 619297 321243 155815 70946 32919 15579

```
real   0m0.048s
user   0m0.338s
sys    0m0.001s

```

To understand sumArray consider that 16 bit represent and array of 8 numbers.
00 have no 1 and represent -1
01 and 10 have one 1 and represent 0
11 have two 1s and represent 1
So that built-in count the number of bit set to 1 \[http://en.wikipedia.org/wiki/Hamming\_weight\] and to each group we remove 1. Cool.

sumOnes is just black magic.

Here the latest compile flags and code.

gcc -std=c++11 -mfpmath=sse -O3 -flto -march=native -funroll-loops -Wall -lstdc++

```
#include <cstdint>
#include <cstdio>
#include <ctime>

inline int32_t interleaveBit(int32_t x)
{
   static const uint32_t B[] = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
   x = (x | ( x << 8)) & B[3];
   x = (x | ( x << 4)) & B[2];
   x = (x | ( x << 2)) & B[1];
   x = (x | ( x << 1)) & B[0];
   return x | (x << 1);
}

inline int32_t sumOnes(int32_t v)
{
   /* 0xAAAA == 0b1010 1010 1010 1010 */
   return !!(0xAAAA & (v ^ ~(v << 1)));
}

inline int32_t sumArray(int32_t v)
{
   return __builtin_popcount(v) - 8;
}

uint32_t x, y = 24252, z = 57768, w = 1564; //PRNG seeds

int32_t myRand()
{
   uint32_t t;
   t = x ^ (x << 1);
   x = y;
   y = z;
   z = w;
   w = w ^ ( w >> 19) ^ t ^ (t >> 8);
   return w;
}

int main()
{
   int leadingZero[8] = { 0 };
   x = static_cast<int32_t>(time(nullptr)); // seed PRNG
   const int maxS = 1 << 15;
   for( int i = 0; i < 1000; ++i )
   {
      int32_t random;
      do
      {
         random = 0xFFFF & myRand();
      } while(sumOnes(random) == 0 );
      for( int s = 0; s < maxS; ++s )
      {
         const int32_t x = interleaveBit(s);
         int j = 7;
         while( j >= 0 )
         {
            const int32_t h = (x >> (j * 2));
            const int32_t l = 0xFFFF & (~(random ^ h)); // inner product
            if( sumArray(l) == 0 )
            {
               leadingZero[j]++;
            } else
            {
               break;
            }
            j--;
         }
      }
   }
   printf("[%d, %d, %d, %d, %d, %d, %d, %d]\n",
      leadingZero[7], leadingZero[6],
      leadingZero[5], leadingZero[4],
      leadingZero[3], leadingZero[2],
      leadingZero[1], leadingZero[0]);
   return 0;
}

```

# Answer
> 10 votes
# Julia: 0.7s, 120x faster

As user20768 demonstrated, a straightforward port of the code to Julia is about twice as fast as PyPy. But we can do a lot better than that.

```
function pleadingzerocounts(; n = 8,
                              m = 8,
                              iters = 1000)
  @parallel (+) for S = 1:2^(8+8-1)
    leading_counts = zeros(Int, m)
    F = Array(Int, n)
    for i = 1:iters
      flag = 0
      while flag == 0
        for i = 1:n
          v = (1-(rand(Int8)&3))%2
          @inbounds F[i] = v
          flag += v & 1
        end
      end
      for j = 1:m
        sum = 0
        for i = 1:n
          @inbounds sum += S & (1 << (j + i - 2)) > 0 ? F[i] : -F[i]
        end
        sum == 0 ?
          (leading_counts[j] += 1) :
          break
      end
    end
    leading_counts
  end
end

function main()
  # Warm up the JIT
  pleadingzerocounts()
  # Then go for real
  println(@time pleadingzerocounts())
end

```

You can run this using `julia -p 8 -e 'require("golf.jl");main()'` (the 8 is the number of processes, you might want to play around with it). On the latest Julia prerelease this takes 0.7s vs. 1m22s for PyPy.

If you have enough cores on your computer, and perhaps spin up a few AWS instances, you should be able to shave off some more :)

# Answer
> 5 votes
### C, 1.210s

**With OP's code running 1m45.729s on my machine.**

Compilation:

```
gcc -O3 -march=native -fwhole-program -fstrict-aliasing -ftree-vectorize -Wall ./test2.c -o ./test2

```

Special thanks: @dyp for compilation flags and ideas for optimisations.

```
#include <stdio.h>
#include <time.h>

#define n (8)
#define m (8)
#define iters (1000)
int leadingzerocounts[m]; // declared as global so initialised to 0
unsigned int x,y=34353,z=57768,w=1564; //PRNG seeds

/* xorshift PRNG
 * Taken from https://en.wikipedia.org/wiki/Xorshift#Example_implementation
 * Used under CC-By-SA */
int myRand() {
    unsigned int t;
    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = w ^ (w >> 19) ^ t ^ (t >> 8);
}

int dotproduct(int*F, int*S) {
    unsigned int i;
    int sum=0;
    for(i=0; i<n; i++) {
        sum+=F[i]*S[i];
    }
    return sum;
}

int main() {
    unsigned int i, j, tmp;
    x=(int)time(NULL); //seed PRNG

    int S[n+m-1];
    for(i=0; i<(1<<(n+m-1)); i++) {
        tmp=i;
        for(j=0; j<n+m-1; j++) {
            S[j]=(tmp&1)*(-2)+1;
            tmp>>=1;
        }
        for(j=0; j<iters; j++) {
            int F[n];
            unsigned int k, flag=0;
            do {
                for(k=0; k<n; k++) {
                    F[k]=(1-(myRand()&3))%2;
                    flag+=(F[k]&1);
                }
            } while(!flag);
            for(k=0; k<m&&!dotproduct(F, S+k); k++) {
                leadingzerocounts[k]++;
            }
        }
    }
    for(i=0; i<m; i++) printf("%d ", leadingzerocounts[i]);
    return 0;
}

```

Sample output:

```
6334411 2527506 1042239 439328 192914 87005 40847 19728

```

# Answer
> 5 votes
**Perl**

This is nowhere near as fast as the C solution, but is pretty fast for a high-level interpreted language I think. It shaves about 40% off the running time of the Python implementation.

```
#!/usr/bin/env perl

use v5.10;
use strict;
use warnings;
use Algorithm::Combinatorics qw( variations_with_repetition );
use List::Util qw( any sum );

use constant {
  N        => 8,
  M        => 8,
  ITERS    => 1000,
};

my @leadingzerocounts;

my $variations = variations_with_repetition([-1, 1], N + M - 1);
while (my $S = $variations->next)
{
  for my $i (1 .. ITERS)
  {
    my @F;
    until (@F and any { $_ } @F)
    {
      @F = map +((-1,0,0,1)[rand 4]), 1..N;
    }

    my $j = 0;
    while ($j < M)
    {
      last if sum map $F[$_]*$S->[$j+$_], 0..N-1;
      $leadingzerocounts[$j++]++;
    }
  }
}

say join ", ", @leadingzerocounts;

```

The Algorithm::Combinatorics is available in Ubuntu (`sudo apt-get install libalgorithm-combinatorics-perl`). The other modules used are core Perl modules, so should already be installed as part of the base Ubuntu installation.

# Answer
> 4 votes
# Julia: 4.66x slower!

I am really beginning to doubt the statistics on their website...

Note that the following Julia code is effectively a direct transcription of the OP's Python code without any optimisations. I use the `time()` function to exclude Julia's slow startup time...

```
srand(27182818284590)
t = time()

require("Iterators")

n = 8
m = 8
iters = 1000
bothzero = 0
leadingzerocounts = zeros(m)

for S in Iterators.product(fill([-1,1], n+m-1)...)
    for i = 1:iters
        F = [[-1 0 0 1][rand(1:4)] for j = 1:n]
        while all((x) -> x == 0, F)
            F = [[-1 0 0 1][rand(1:4)] for j = 1:n]
        end
        j = 1
        while j <= m && sum(map(*, F, S[j:j+n-1])) == 0
            leadingzerocounts[j] += 1
            j += 1
        end
    end
end

println(leadingzerocounts)

t = time() - t
println("$t seconds")

```

Julia: 5 m 32.912 s

OP's code in PyPy: 1 m 11.506 s

Julia output:

```
6332170
2525472
1041522
438761
193119
86873
40705
19662

```

# Answer
> 4 votes
**Julia: 1 min 21.4s (2.2x faster)** (modification of Arman's code)

**Op's code in PyPy: 3 min 1.4 s**

Both done in the REPL, not including time to load packages.

```
function foo()
    n = 8
    m = 8
    iters = 1000
    bothzero = 0
    leadingzerocounts = zeros(Int,m)
    P=[-1,0,0,1]

    for S in Iterators.product(fill([-1,1], n+m-1)...)
        Sm=[S...]
        for i = 1:iters
            F = P[rand(1:4,n)]
            while all(F==0)
                F = P[rand(1:4,n)]
            end
            j = 1

            while j <= m && dot(F,Sm[j:j+n-1]) == 0
                leadingzerocounts[j] += 1
                j += 1
            end
        end
    end

    println(leadingzerocounts)
end

```

There are some problems with Arman's code making it very slow: It uses a lot of anonymous functions and higher order functions unnecessarily. To test if all of a vector F is zero, why not just write all(F==0) instead of all(x-\>x==0,F)? It is shorter, and a literally a thousand times faster.

It also uses sum(map(\*,x,y)) as the dot product instead of simply dot(x,y). The first version **650 times slower** for a vector of 10k doubles. And the dot product function is implemented as a for loop in pure Julia.

Also, array comprehensions are slow. It is better to write \[0,1,0,-1\]\[rand(1:4,n)\] instead of \[\[-1 0 0 1\]\[rand(1:4)\] for j = 1:n\].

Finally, global variables are bad juju in Julia. Julia is only fast if you write code in such a way that allows the JIT and type inference to work. A big part of this is type stability: The compiler must be able to be sure that a variable's type will not change while inside a loop, for example.

# Answer
> 4 votes
## RPython 0.187s (258x faster)

Original Source w/ PyPy2.2.1: **1m 6.718s**

Now with threading, back-support for standard Python has been dropped. The number of worker threads can be specified as a command line parameter, default is two.

```
from time import time, sleep
from math import fmod

from rpython.rlib.rthread import start_new_thread, allocate_lock, get_ident
class Random:
  __slots__ = ['s']

  def __init__(self, s=1):
    self.s = s

  def init_genrand(self, seed):
    self.s = seed

  def genrand32(self):
    # xorshift PRNG with period 2^32-1
    # see http://core.kmi.open.ac.uk/download/pdf/6250138.pdf
    self.s ^= (self.s << 13)
    self.s ^= (self.s >> 17)
    self.s ^= (self.s << 5)
    return self.s

class ThreadEnv:
  __slots__ = ['n', 'm', 'iters', 'counts', 'running', 'lock']

  def __init__(self):
    self.n = 8
    self.m = 8
    self.iters = 1000
    self.counts = [0]*8
    self.running = 0
    self.lock = None

env = ThreadEnv()
truth = [-1,0,0,1]

def main(argv):
  argc = len(argv)
  if argc < 4 or argc > 5:
    print 'Usage: %s N M ITERS [NUM_THREADS=2]'%argv[0]
    return 1

  if argc == 5:
    num_threads = int(argv[4])
  else:
    num_threads = 2

  env.n = int(argv[1])
  env.m = int(argv[2])
  env.iters = int(argv[3]) // num_threads
  env.counts = [0]*env.m
  env.lock = allocate_lock()

  for i in xrange(num_threads-1):
    start_new_thread(run,())
    env.running += 1

  env.running += 1

  # use the main process as a worker
  run()

  # wait for any laggers
  while env.running:
    sleep(0.01)

  print env.counts
  return 0

def run():
  n, m, iters = env.n, env.m, env.iters
  counts = [0]*m
  sbits = [0]*(n+m-1)

  random = Random()
  seed = int(fmod(time(), 2147483.648)*1000) ^ get_ident()
  random.init_genrand(seed)

  for S in xrange(1<<n+m-1):
    i = 0
    sbit = 0
    while not sbit:
      sbits[i] ^= 3
      sbit = sbits[i]
      i += 1

    for i in xrange(iters):
      f = 0
      while not f:
        F = random.genrand32()

        G, x = F, 0
        for k in xrange(n):
          x += truth[(G&3)^sbits[k]]
          f |= x
          G >>= 2

      if not x:
        counts[0] += 1
        for j in xrange(1, m):
          G, x = F, 0
          for k in xrange(j, n+j):
            x += truth[(G&3)^sbits[k]]
            G >>= 2
          if x: break
          counts[j] += 1

  # passing True stalls until a lock can be obtained
  env.lock.acquire(True)

  for i in xrange(m):
    env.counts[i] += counts[i]
  env.running -= 1

  env.lock.release()

def target(*args):
  return main, None

```

RPython is a restricted subset of Python, which can be translated to C and then compiled using the RPython Toolchain. Its expressed purpose is to aid in the creation of language interpreters, but it can also be used to compile simple programs like the one above. Most of the 'fancier' features of Python, such as `itertools` or even `map` are not available.

To compile, make a local clone of the current pypy repository, and run the following:

```
$ pypy %PYPY_REPO%/rpython/bin/rpython --thread convolution.py

```

The resulting executable will be named `convolution-c` or similar in the current working directory.

I've parameterized the input variables, so the program should be run as:

```
convolution-c 8 8 1000

```

to match the sample code.

---

**Implementation Notes**

`S in itertools.product([-1,1], repeat = n+m-1)` becomes `S in xrange(1<<n+m-1)`, interpreting `S` as a bit map: \[`0`, `1`\] → \[`-1`, `1`\]

Likewise, `F` is also a bit map, with each two bits representing a single value:
\[`00`, `01`, `10`, `11`\] → \[`-1`, `0`, `0`, `1`\]

A truth table is used to lookup the product, rather than performing a mulitplication.

Because 32-bit signed integers are used, `n` may be no larger than 15, and `n+m` no larger than 31. Arbitrary integer support can be achieved with the `rpython.rlib.rbigint` module, if necessary.

The first iteration of the dot-product loop is unrolled, and combined with the nullity test of `F`.

A homebrew PRNG is used, source listed. The author of the paper demonstrates a period of 2<sup>32</sup>-1, and claims that it passes all Diehard tests save one, although I haven't personally confirmed this.

The random seed changes every millisecond, which is as about as good using a timestamp will allow. Additionally, each worker thread `xor`s their process id with this value, to ensure that they each have a different seed.

---

**Sample Timings**

2 worker threads:

```
$ timeit convolution-c 8 8 1000 2
[6331845, 2526161, 1042330, 440018, 193724, 87147, 40943, 19603]

Elapsed Time:     0:00:00.375
Process Time:     0:00:00.687
System Calls:     6927

```

4 worker threads:

```
$ timeit convolution-c 8 8 1000 4
[6334565, 2527684, 1043502, 440216, 193225, 87398, 40799, 19338]

Elapsed Time:     0:00:00.218
Process Time:     0:00:00.796
System Calls:     3417

```

**8 worker threads:**

```
$ timeit convolution-c 8 8 1000 8
[6327639, 2522483, 1039869, 437884, 192460, 86771, 40420, 19403]

Elapsed Time:     0:00:00.187
Process Time:     0:00:00.734
System Calls:     3165

```

OP's original source:

```
$ timeit pypy convolution-orig.py
[6330610, 2525644, 1041481, 438980, 193001, 86622, 40598, 19449]

Elapsed Time:     0:01:06.718
Process Time:     0:01:06.718
System Calls:     11599808

```

---

**Timing for 100000 iterations:**

```
$ timeit convolution-c 8 8 100000 8
[633156171, 252540679, 104129386, 43903716, 19307215, 8709157, 4072133, 1959124]

Elapsed Time:     0:00:16.625
Process Time:     0:01:02.406
System Calls:     171341

```

# Answer
> 2 votes
# Nimrod

```
import times, locks, strutils, unsigned

const
  N = 8
  M = 8
  iters = 1000
  numThreads = 8

type
  SVec = array[0..N+M-1, int]
  FVec = array[0..N-1, int]
  ComputeThread = TThread[int]

var
  rngSeed = int(epochTime()*1000)
  totalLeadingZeros: array[0..M-1, int]
  lock: TLock

type
  RNGState = object
    x, y, z, w: uint32

proc newRNG(seed: int): RNGState =
  result.x = uint32(seed)

proc random(rng: var RNGState): int =
  let t = rng.x xor (rng.x shl 11)
  rng.x = rng.y; rng.y = rng.z; rng.z = rng.w
  rng.w = rng.w xor (rng.w shr 19) xor t xor (t shr 8)
  result = int(rng.w)

proc initVecRand(v: var FVec, rng: var RNGState) =
  const values = [ -1, 0, 0, 1 ]
  var rnd = rng.random
  var bitAcc = 0
  for i in 0 .. <len(v):
    let val = values[rnd and 3]
    rnd = rnd shr 2
    v[i] = val
    bitAcc = bitAcc or val
  if bitAcc == 0:
    initVecRand(v, rng)

proc convolve(s: SVec, f: FVec, offset: int): int =
  for i in 0 .. <len(f):
    result += s[i+offset]*f[i]

proc iterate(v: var SVec) =
  for i in 0 .. <len(v):
    if v[i] == -1:
      v[i] = 1
      return
    v[i] = -1

proc mainThread(id: int) {.thread.} =
  const numS = 1 shl (N+M-1)
  var
    s: SVec
    f: FVec
    leadingZeros: array[0..M-1, int]
    rng = newRNG(rngSeed + id)
  for k in 0 .. <len(s):
    s[k] = -1
  for i in 1..numS:
    for j in countUp(id, iters, numThreads):
      initVecRand(f, rng)
      if convolve(s, f, 0) == 0:
        leadingZeros[0] += 1
        for k in 1 .. <M:
          if convolve(s, f, k) == 0:
            leadingZeros[k] += 1
          else:
            break
    iterate(s)
  acquire(lock)
  for i in 0 .. <M:
    totalLeadingZeros[i] += leadingZeros[i]
  release(lock)

proc main =
  let startTime = epochTime()
  var threads: array[1..numThreads, ComputeThread]
  initLock(lock)
  for i in 1..numThreads:
    createThread(threads[i], mainThread, i)
  for i in 1..numThreads:
    joinThread(threads[i])
  echo("Leading zeros: ", @totalLeadingZeros)
  let endTime = epochTime()
  echo("Time taken:    ", formatFloat(endTime - startTime, ffDecimal, 3),
       " seconds")

main()

```

Example output:

```
Leading zeros: @[6333025, 2525808, 1042466, 439138, 192391, 86751, 40671, 19525]
Time taken:    0.145 seconds

```

Nimrod compiles to C, therefore the choice of C compiler for the backend matters, too.

Using clang, compile with:

```
nimrod cc --threads:on --cc=clang --passc:-flto -d:release conv.nim

```

Using gcc, compile with:

```
nimrod cc --threads:on --cc=gcc --passc:-flto -d:release conv.nim

```

Omit `--passc:-flto` if you have an older C compiler that doesn't support LTO. Omit the `--cc=...` option if you are fine with the default choice for the C compiler. The code requires Nimrod 0.9.4 or 0.9.5.

On my quadcore iMac (2.66 GHz core i5), the code runs in about .15 seconds with gcc 4.9, .16 seconds with clang, compared to 88 seconds for PyPy 2.2.1 (i.e. a 500+ times speedup). Unfortunately, I don't have access to a machine with more than four cores that also has PyPy installed or where I could easily install PyPy, though I get about .1 seconds (with a lot of measurement noise) on a 64-core AMD Opteron 6376 1.4 GHz (according to /proc/cpuinfo) with gcc 4.4.6.

The implementation tries to be faithful to the original rather than optimizing code at the cost of readability, while not forgoing obvious optimizations. Interestingly enough, tail recursion in `initVecRand()` is a bit faster than a loop with a break instruction with both gcc and clang. Manually unrolling one iteration of the `convolve` test loop inside the main loop also produced a speedup, presumably due to better branch prediction.

# Answer
> 2 votes
# Java

I translated the above C++ solution to Java:

```
import java.util.Random;
import java.util.Arrays;

public class Bench2 {
  public static int[] bits = { 0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF };
  public static int[] oneValues = { 1, 0, 0, 1 };
  public static int[] values = { -1, 0, 0, 1 };
  public static int n = 8;
  public static int m = 8;
  public static int iters = 1000;

  private static int x,y=34353,z=57768,w=1564;

  public static void main( String[] args ) {
    x = (int) (System.currentTimeMillis()/1000l);

    int[] leadingzerocounts = new int[ m ];
    Arrays.fill( leadingzerocounts, 0 );

    int maxS = 1 << 15;

    for( int s = 0; s < maxS; s++ ) {
      int x = interleaveBit( s );

      for( int i=0; i<iters; i++ ) {
        int random;

        do {
          random = 0xFFFF & fastRandom( );
        } while( sumOnes( random ) == 0 );

        int j = 7;

        while( j >= 0 ) {
          int h = ( x >> (j*2) );
          int l = 0xFFFF & (~(random ^ h));

          if( sumArray( l ) == 0 ) {
            leadingzerocounts[ j ]++;
          } else {
            break;
          }

          j--;
        }
      }
    }

    for( int i = 7; i >= 0; --i ) {
      System.out.print( leadingzerocounts[ i ] + " " );
    }

    System.out.println( );
  }

  public static int interleaveBit( int x ) {
    x = (x | ( x << 8)) & bits[3];
    x = (x | ( x << 4)) & bits[2];
    x = (x | ( x << 2)) & bits[1];
    x = (x | ( x << 1)) & bits[0];
    return x | (x << 1);
  }

  public static int sumOnes( int v ) {
    return (0xAAAA & (v ^ ~(v << 1)));
    // int s = 0;

    // for( int i = 0; i < 8; ++i ) {
    //   int a = 3 & ( v >> (i*2) );
    //   s += oneValues[ a ];
    // }

    // return s;
  }

  public static int sumArray( int v ) {
    return Integer.bitCount( v ) - 8;
    // int s = 0;

    // for( int i=0; i<8; ++i ) {
    //   int a = 3 & ( v >> (i*2) );
    //   s += values[ a ];
    // }

    // return s;
  }

  public static int fastRandom( ) {
    long t;
    t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (int)( w ^ (w >> 19) ^ t ^ (t >> 8));
  }
}

```

On my machine I get following output for the java program:

```
time java Bench2
6330616 2524569 1040372 439615 193290 87131 40651 19607
java Bench2  0.36s user 0.02s system 102% cpu 0.371 total

```

The OPs program runs about 53 seconds on my machine:

```
time pypy start.py
[6330944, 2524897, 1040621, 439317, 192731, 86850, 40830, 19555]
pypy start.py  52.96s user 0.06s system 99% cpu 53.271 total

```

The c++ program executed only about 0.15 seconds:

```
time ./benchcc
[6112256, 2461184, 1025152, 435584, 193376, 87400, 40924, 19700]
./benchcc  0.15s user 0.00s system 99% cpu 0.151 total

```

That is about 2.5x faster than the corresponding java solution (I didn't exclude VM startup). This java solutions is about 142x faster than the program executed with PyPy.

Since I was personally interested, I set `iters` to 100\_000 for Java and C++ but the factor of 2.5 didn't decrease in favor of Java if anything got bigger.

EDIT: I ran the programs on a 64bit Arch Linux PC.

EDIT2: I want to add that I started with a rough translation of the python code:

```
import java.util.Random;
import java.util.Arrays;

public class Bench {
    public static int[] values = { -1, 0, 0, 1 };
    public static int n = 8;
    public static int m = 8;
    public static int iters = 1000;

    private static int x,y=34353,z=57768,w=1564;

    public static void main( String[] args ) {
        x = (int) (System.currentTimeMillis()/1000l);

        int[] leadingzerocounts = new int[ m ];
        Arrays.fill( leadingzerocounts, 0 );

        int[] S = new int[ n+m-1 ];
        Arrays.fill( S, -1 );

        do {
            for( int i=0; i<iters; i++ ) {
                int[] F = new int[ n ];

                do {
                    randomArray( F );
                } while( containsOnlyZeros( F ) );

                for( int j=0; j < m && check( F, S, j ); j++ ) {
                    leadingzerocounts[ j ] += 1;
                }
            }
        } while( next( S ) );

        System.out.println( Arrays.toString( leadingzerocounts ) );
    }

    public static void randomArray( int[] F ) {
        for( int i = 0; i<F.length; i++ ) {
            F[ i ] = (1-(fastRandom()&3))%2;
        }
    }

    public static boolean containsOnlyZeros( int[] F ) {
        for( int x : F ) {
            if( x != 0 ) {
                return false;
            }
        }

        return true;
    }

    public static boolean next( int[] S ) {
        for( int i=0; i<S.length; i++ ) {
            if( ( S[ i ] = -S[ i ] ) == 1 ) {
                return true;
            }
        }

        return false;
    }

    public static boolean check( int[] F, int[] S, int j ) {
      int sum = 0;

      for( int i=0; i<n; i++ ) {
          sum += F[ i ] * S[ j + i ];
      }

      return sum == 0;
    }

    public static int fastRandom( ) {
        long t;
        t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = (int)( w ^ (w >> 19) ^ t ^ (t >> 8));
    }
}

```

This program ran about 3.6 seconds:

```
time java Bench
[6330034, 2524369, 1040723, 439261, 193673, 87338, 40840, 19567]
java Bench  3.64s user 0.01s system 101% cpu 3.600 total

```

Which is about 14 times faster than the PyPy solution. (Choosing the standard random function over the fastRandom function leads to an execution time of 5 seconds)

# Answer
> 2 votes
**Python 3.5 + numpy 1.10.1, 3.76 seconds**

The tests were run on my Macbook Pro. OP's code took ~6 mins on the same machine.

The reason I'm answering this question in fact is because I don't have 10 reputations and can't answer Part I :-p

For the past few days, I have been trying to figure out how to perform massive convolutions efficiently with numpy (without relying on a third-party package, even scipy). As I came across this series of challenges during my research, I decided to give it a try. I may have come to this game to late, but here is my attempt using Python 3.5 and numpy 1.10.1.

```
def test_convolv():
    n = 8
    m  = 8
    iters = 1000
    ilow = np.ceil(0+n/2).astype(int)
    ihigh = np.ceil(m+n/2).astype(int)

    leadingzerocounts = np.zeros(m)

    # Pre-compute S & F
    S = np.array(list(itertools.product([-1,1], repeat = n+m-1)))
    choicesF = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n*iters).reshape(iters,n)
    imask = ~np.any(choicesF, axis=1)
    while np.any(imask):
        imasksize = np.count_nonzero(imask)
        choicesF[imask,:] = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n*imasksize).reshape(imasksize, n)
        imask = ~np.any(choicesF, axis=1)

    for i in np.arange(iters):
        F = choicesF[i, :]
        # This is where the magic is: by flattening the S array,
        # I try to take advantage of speed of the np.convolve
        # (really numpy.multiarray.correlate).
        FS = (np.convolve(S.reshape(-1), F, 'same').reshape(S.shape))[:, ilow:ihigh]
        jmask_not = (FS[:, 0] != 0)
        leadingzerocounts[0] = leadingzerocounts[0]+np.count_nonzero(~jmask_not)
        for j in np.arange(n-1)+1:
            jmask = (FS[jmask_not, j] != 0)
            leadingzerocounts[j] = leadingzerocounts[j] + np.count_nonzero(~jmask)
            jmask_not[(jmask_not.nonzero()[0])[jmask]] = False

    print(leadingzerocounts)

```

I pre-computed the S and F arrays, and flattened the S array while performing the convolution, which (based on my experiments) could take advantage of the speed of np.convolve. In other words, as I didn't find a vectorized convolution routine, I fake-vectorized the code by flattening the whole array and hoped np.convolved would do the vectorization under the hood for me, which seemed to be working. Note I used mode='same' and trimmed the leading and trailing elements that were useless.

On my Macbook Pro, the test results give **3.76 seconds**. When I ran OP's code (modified to Python 3.5), I got about **6 minutes**. The speedup is about 100 times.

One drawback is that because the S and F arrays are to be stored, the memory requirement can be a problem if the sizes are too big.

I used the same method for Part I and I got a ~ 60-100x speedup on my laptop.

As I did everything on my Macbook Pro, if someone could test my code and let me know how it goes on your machine, I would appreciate it very much!

# Answer
> 1 votes
# J, <sup>130x</sup>~50x speedup?

```
n =: m =: 8
len =: 1000
S =: (] - 0 = ])S0=: #:i.2^<:+/n,m
k =: (n#0) -.~ (_1 0 0 1) {~ (n#4) #: i.4^n
sn =: (]-0=])#:i.2^n
ku =: ~. k
M =: 0=+/"1 sn *"1/ ku
fs =: (ku&i.)"1 k
snum =: n #.\"1 S0

run =: 3 : 0
 r =: n#0
 for_t. (snum) do.
   rn =: fs{~? len # #k
   r =: r + +/"1*/\rn{"1 t{M
 end.
 r
)
echo run 0
exit''

```

Times on a random debian:

```
u#>time j slowpy.ijs
6334123 2526955 1041600 440039 193567 87321 40754 19714

real    0m2.453s
user    0m2.368s
sys     0m0.084s

u#>time python slow_pyth.py
[6331017, 2524166, 1041731, 438731, 193599, 87578, 40919, 19705]

real    5m25.541s
user    5m25.548s
sys     0m0.012s

```

I think there is room for improvement.

# Answer
> 1 votes
# Fortran: 316x

Okay, Fortran: I've got it up to **106x** **155x** **160x** **316x** speedup when using an Xorshift RNG and OpenMP on a 4 core i7 CPU. Other than that, there are no big tricks. For the iterator to construct S, I just use the binary representation of the 16-bit integer i. You'll note that apart from the inline RNG and the "iterator"/mapping from i to S, the code is just as high-level as the Python code.

Edit: removed the "if" in the Xorshift, now using "r = abs(w/...)" instead of "r=w/...". Goes from 106x to 155x.

Edit2: This generates 15x as many random numbers as the C++ solution. If someone has a zero-overhead solution for converting a random int into an array of 0s and 1s in Fortran, I'm all ears. Then we could beat C++ :)

Edit3: The first edit introduced a bug, as Lembik pointed out. This is fixed now, with a tiny improvement in speedup. I will try to use the suggestion by Eelvex to get more speedup.

Edit4: Profiling indicated that converting to real and back to integer with nint() was slow. I replaced this with one integer division doing both scaling and rounding, going from 160x to 316x speedup.

Compile with:

> gfortran -O3 -march=native -fopenmp golf.f90

```
program golf
implicit none
integer, parameter :: m=8, n=8
integer :: F(n), S(m+n-1), leadingzerocounts(m)
integer :: j,k,bindec,enc,tmp,x=123456789,y=362436069,z=521288629,w=88675123
integer*2 :: i
real :: r

leadingzerocounts=0

!$OMP parallel do private(i,enc,j,bindec,S,F,k,tmp,x,y,z,w,r) reduction(+:leadingzerocounts) schedule(dynamic)
do i=0,32766
  enc=i
  ! Short loop to convert i into the array S with -1s and 1s
  do j=16,2,-1
    bindec=2**(j-1)
    if (enc-bindec .ge. 0) then
      S(j-1)=1
      enc=enc-bindec
    else
      S(j-1)=-1
    endif
  end do
  do j=1,1000
    F=0
    do while (.not. any(F /= 0))
      do k=1,n
        ! Start Xorshift RNG
        tmp = ieor(x,ishft(x,11))
        x = y
        y = z
        z = w
        w = ieor(ieor(w,ishft(w,-19)),ieor(tmp,ishft(tmp,-8)))
        ! End Xorshift RNG
        ! Just scale it inside the nint:
        !F(k)=nint(w/2147483648.0)
        ! Scaling by integer division is faster, but then we need the random
        ! number to be in (-2,2) instead of [-1,1]:
        F(k)=w/1073741824

      end do
    end do
    do k=1,m
      if (dot_product(F,S(k:k+n-1)) /= 0) exit
      leadingzerocounts(k)=leadingzerocounts(k)+1
    end do
  end do
end do
!$OMP end parallel do

print *, leadingzerocounts

end

```

Example output:

> $ time ./a.out
> 6329624 2524831 1039787 438809 193044 6860 40486 19517
> ./a.out 1.45s user 0.00s system 746% cpu 0.192 total

OP's code:

> $ time pypy golf.py
> pypy golf.py 60.68s user 0.04s system 99% cpu 1:00.74 total

# Answer
> 1 votes
**C++: x200 (4-core i7, should scale to x400 on 8-core)**

Trying for a more straightforward **C++11** (Tested with VS 2012, gcc and clang) solution with parallelization.

To get this to compile and run under Linux with gcc 4.8.1:

> g++ -O3 -msse -msse2 -msse3 -march=native -std=c++11 -pthread -Wl,--no-as-needed golf.cpp

Under Linux we also need `std::launch::async` to force multiple threads. I was missing that in an earlier version.

In Visual Studio (2012+) this should just work but make a release build for timing...

On my oldish dual core i3 this runs in **~0.9** seconds. On my i7 quad core this is 0.319s vs. pypy 66 seconds.

On an 8-core i7 this should in the x400 speedup range. Switching to C style arrays would speed it up but I was interested in staying with C++ containers. For me it's interesting to see the speedup you can get while staying relatively close to the problem domain and at a relatively high level, something I think C++ is really good at. Also of note is the relative ease of paralleization using C++11 constructs.

@ilmale's bit solution is very cool and works for -1/1/0. One could also throw SSE at this and maybe get a significant speedup.

Beyond the parallelization there's another "trick" in there which is reducing the number of summations. Sample results: 6332947 2525357 1041957 438353 193024 87331 40902 19649

```
#include <vector>
#include <iostream>
#include <thread>
#include <future>
#include <time.h>
#include <ctime>
#include <algorithm>

using namespace std;

// Bring some of these constants out to share
const size_t m = 8;
const int nthreads = 16;
const size_t cn = 15;
const int two_to_cn = 32768;

static unsigned int seed = 35;

int my_random() // not thread safe but let's call that more random!
{
   seed = seed*1664525UL + 1013904223UL; // numberical recipes, 32 bit
   return ((seed>>30)&1)-!!((seed>>30)&2); // Credit to Dave!
}

bool allzero(const vector<int>& T)
{
   for(auto x : T)
   {
      if(x!=0)
      {
         return false;
      }
   }
   return true;
}

// Return the position of the first non-zero element
size_t convolve_until_nonzero(size_t max_n, const vector<int>& v1, const vector<int>& v2)
{
   for(size_t i = 0; i<max_n; ++i)
   {
      int result = 0;
      for(size_t j = 0; j<v2.size(); ++j)
      {
         result += v1[i+j]*v2[j];
      }
      if(result!=0)
      {
         return i;
      }
   }
   return max_n;
}

void advance(vector<int>& v)
{
   for(auto &x : v)
   {
      if(x==-1)
      {
         x = 1;
         return;
      }
      x = -1;
   }
}

vector<int> convolve_random_arrays(vector<int> S, int range)
{
   const int iters = 1000;
   int bothzero = 0;
   int firstzero = 0;

   time_t current_time;
   time(&current_time);
   seed = current_time;

   vector<int> F(m);
   vector<int> leadingzerocounts(m+1);

   for(auto &x: leadingzerocounts)
   {
      x = 0;
   }

   for(int i=0; i<range; ++i)
   {
      for(int j=0; j<iters; ++j)
      {
         do
         {
            for(auto &x : F)
            {
               x = my_random();
            }
         } while(allzero(F));
         leadingzerocounts[convolve_until_nonzero(m, S, F)]++;
      }
      advance(S);
   }

   // Finish adding things up...
   for(int i=m-1; i>0; --i)
   {
      leadingzerocounts[i] += leadingzerocounts[i+1];
   }

   vector<int> withoutfirst(leadingzerocounts.begin()+1, leadingzerocounts.end());
   return withoutfirst;
}

int main(int argc, char* argv[])
{

   vector<int> leadingzerocounts(m);

   for(auto &x: leadingzerocounts)
   {
      x = 0;
   }

   clock_t start = clock();

   vector<int> S(cn);
   for(auto &x : S)
   {
      x = -1;
   }

   vector< future< vector< int > > > fs; // The future results of the threads

   // Go make threads to work on parts of the problem
   for(int i=0; i<nthreads; ++i)
   {
      vector<int> S_reversed = S; // S counts using LSBs but we want the thread start to be in MSBs
      reverse(S_reversed.begin(), S_reversed.end());
      fs.push_back(async(std::launch::async, convolve_random_arrays, S_reversed, two_to_cn/nthreads));
      advance(S);
   }
   // And now collect the data
   for(auto &f : fs)
   {
      vector<int> result = f.get();
      for(int i=0; i<result.size(); ++i)
      {
         leadingzerocounts[i] += result[i];
      }
   }

   for(auto count : leadingzerocounts)
   {
      cout << count << endl;
   }

   return 0;
}

```

---
Tags: fastest-code
---


title: A simple DNA simulator

text:
# Question
Title: A simple DNA simulator
Your code is going to generate a very simple ASCII-art representation of DNA, forever. It will take two numbers as input in any format you want: as a list, as arguments to a function, on stdin, etc.

* A floating-point interval `I` in seconds between 0.0 and 1.0 (inclusive)
* A zoom level `Z` as an integer from 1 to 64 (inclusive)

Your code will print one line to stdout or its equivalent every `I` seconds, producing an infinite output that looks something like this (for zoom level 4):

```
    A
 T-----a
G-------c
 G-----c
    g
 t-----A
a-------T
 c-----G
    T
 A-----t
C-------g
...

```

Specifically, our representation of DNA is a pair of sine waves connected by hyphens, one consisting of the characters `a`, `c`, `g`, and `t`, the other of the characters `A`, `C`, `G`, and `T`. If `x` is the 0-indexed number of the line we're currently printing, the 0-based position of the character in the lowercase wave is given by `(sin(πx / Z) + 1) * Z`, and in the uppercase wave is given by `(-sin(πx / Z) + 1) * Z`, both **rounded** (not floored) to the nearest integer. Further details:

* In cases where the two waves overlap, you need to alternate which wave is in the front, starting with the uppercase wave. (Starting with the lowercase wave would give us a double helix that does not exist!)
* Ignoring case, A always pairs with T and C always pairs with G, as in real DNA. The pairs themselves should be randomly chosen with a uniform distribution over the four possibilities. It does not matter if the choice of pairs is the same or different on successive runs of your code. The statistical quality of your random choices is not an issue as long as the output has no obvious pattern and a period at least in the billions (flawed PRNGs like RANDU are fine.)
* You must either have no trailing spaces or pad every line to the maximum position of the waves at that zoom level (in the example above, nine characters.) Zoom level 1 may have one optional additional trailing space for mathematical reasons.

Because DNA is small, your code will need to be as short as possible.

**More examples:**

Zoom level 8:

```
        T
     C-----g
  A-----------t
 C-------------g
G---------------c
 T-------------a
  T-----------a
     T-----a
        c
     g-----C
  t-----------A
 g-------------C
a---------------T
...

```

Zoom level 2:

```
  A
T---a
  c
g---C
  G
A---t
  c
a---T
...

```

Zoom level 1 (note the leading space):

```
 G
 a
 C
 t
...

```

# Answer
> 4 votes
# Ruby, Rev B ~~171~~ 161 bytes

~~Fixing the output for z=1 cost 10 bytes. It's a special case: the helix is really 3 characters wide if you looked at it at 90 degrees, but as we look at it at 0 degrees it looks only 1 character wide.~~ **zero leading spaces on z=1 no longer required**

Some savings by eliminating brackets and by multiplying y.abs by 2 before truncation when calculating the number of - characters needed.

Finally, I avoided the `include Math` (required for `sin` and `PI`) by using complex number arithmetic with powers of the number `i`. The imaginary part of the complex number is equivalent to sin x, except that it repeats with period 4 instead of period 2\*PI. Saving for this change was either 1 or 0 bytes.

```
->z,i{x=0
loop{y=z*("i".to_c**x).imag
s=(?-*(y.abs*2)).center z*2+1
s[z-y+0.5]='TGAC'[r=rand(4)]
x!=0&&s[z+y+0.5]='actg'[r]
puts s
sleep i
x+=2.0/z
x>3.99&&x=0}}

```

# Ruby, Rev A 165 bytes

This is way longer than expected. There are a few potential golfing opportunities to be explored.

```
include Math
->z,i{x=0
loop{y=z*sin(x)
s=('--'*(y.abs+h=0.5)).center(z*2+1)
s[z+h-y]='TGAC'[r=rand(4)]
x!=0&&s[z+h+y]='actg'[r]
puts s
sleep(i)
x+=PI/z
x>6.28&&x=0}}

```

Commented in test program

```
include Math
f=->z,i{x=0
  loop{y=z*sin(x)
    s=('--'*(y.abs+h=0.5)).center(z*2+1)  #make a space-padded string of z*2+1 characters, containing enough - signs
    s[z+h-y]='TGAC'[r=rand(4)]            #insert random capital letter, saving index in r
    x!=0&&s[z+h+y]='actg'[r]              #insert small letter. This will normally go on top of the capital as it is done second, but supress for x=0 to make helix
    puts s
    sleep(i)
    x+=PI/z                               #increment x
    x>6.28&&x=0                           #reset x if equal to 2*PI (this proofs against loss of floating point precision, making correct output truly infinite.)
  }
}

Z=gets.to_i
I=gets.to_f
f[Z,I]

```

# Answer
> 3 votes
## C, ~~569~~ ~~402~~ 361 bytes

```
#include<stdlib.h>
u,l,r,m,n,Z,I,y=0,x=0;main(c,char**v){Z = atoi(v[1]);I=atof(v[2])*1000000;srand(time(0));char *a="ACGTtgca";while(1){r=rand()%4;usleep(I);double s=sin(3.14*x++/Z);u=floor(((-1*s+1)*Z)+0.5);l=floor(((s+1)*Z)+0.5);m=(u<l)?u:l;n=u<l?l:u;char z[n+1];memset(z,' ',n);z[l]=a[r+4];z[u]=a[r];for(y=m+1;y<n;y++)z[y]='-';z[n+1]='\0';printf("%s\n",z);}}

```

Whipped this up pretty quick so I am sure there are some other things I could do to decrease my score but I am just happy I got this program to compile and run properly on the first attempt.

De-golf version:

```
#include<stdio.h>
#include<math.h>
#include<unistd.h>
#include<time.h>
#include<stdlib.h>
u,l,r,m,n,Z,I,y=0,x=0;
main(c,char**v){
   Z = atoi(v[1]);
   I=atof(v[2])*1000000;
   srand(time(0));
   char *a="ACGTtgca";
   while(1){
      r=rand()%4;
      usleep(I);
      double s=sin(3.14*x++/Z);
      u=floor(((-1*s+1)*Z)+0.5);
      l=floor(((s+1)*Z)+0.5);
      m=(u<l)?u:l;
      n=u<l?l:u;
      char z[n+1];
      memset(z,' ',n);
      z[l]=a[r+4];
      z[u]=a[r];
      for(y=m+1;y<n;y++)z[y]='-';
      z[n+1]='\0';
      printf("%s\n",z);
   }
}

```

UPDATE: I adjusted the loop to print everything in one print statement and used the fact that variables are defined as int by default to shave some bytes. UPDATE2: Some var renaming and some logic shortening to shave a few more bytes.

# Answer
> 3 votes
# C, ~~294~~ ~~289~~ ~~285~~ ~~283~~ ~~281~~ ~~270~~ ~~265~~ ~~237~~ 218 bytes

```
#include<math.h>
o,i,p,r;char*c="acgtTGCA",d[256]={[0 ...254]='-'};P(w,z)float w;{for(;;poll(0,0,r=w*1e3))p=fabs(sinf(M_PI*i++/z))*z+.5,r=rand()&3,o^=4*!p,printf(p?"%*c%s%c\n":"%*c\n",z-p+1,c[r+o],d+256-p*2,c[r+4-o]);}

```

Or the longer version which parses input from main:

```
#include<stdlib.h>
#include<math.h>
o,i,p,r;char*c="acgtTGCA",d[256]={[0 ...254]='-'};main(n,v)char**v;{for(;n=strtod(v[2],0);poll(0,0,n=atof(v[1])*1e3))p=fabs(sinf(M_PI*i++/n))*n+.5,r=rand()&3,o^=4*!p,printf(p?"%*c%s%c\n":"%*c\n",n-p+1,c[r+o],d+256-p*2,c[r+4-o]);}

```

It's a pretty dumb overall implementation, with some printf tricks thrown in. It has some missing includes, uses K&R syntax for the function, and relies on GCC's range initialisers, so this isn't very standard. Also the function version still uses globals, so it can only be called once!

The function version takes 2 parameters; wait (in seconds) and zoom. Here's a caller for it:

```
#include <stdlib.h>
int main( int argc, const char *const *argv ) {
    if( argc != 3 ) {
        printf( "Usage: %s <delay> <zoom>\n", argv[0] );
        return EXIT_FAILURE;
    }
    const float delay = atof( argv[1] );
    const int zoom = strtod( argv[2], 0 );
    if( delay < 0 || zoom <= 0 ) {
        printf( "Invalid input.\nUsage: %s <delay> <zoom>\n", argv[0] );
        return EXIT_FAILURE;
    }
    P( delay, zoom );
    return EXIT_SUCCESS;
}

```

Run as:

```
./dna <delay> <zoom>
./dna 0.5 8

```

Breakdown:

```
// Globals initialise to 0
o,                                 // Ordering (upper/lower first)
i,                                 // Current iteration
p,                                 // Current indent
r;                                 // Current random value
char*c="acgtTGCA",                 // The valid letters
    d[256]={[0 ...254]='-'};       // Line of dashes (for printing)
main(n,v)char**v;{                 // K&R-style main definition (saves 2 bytes)
    // n will be used for Zoom, random number & casting delay
    for(
        ;n=strtod(v[2],0);         // Store zoom
        poll(0,0,n=atof(v[1])*1e3) // After each loop, use poll to delay
                                   // (Use variable to cast delay to int)
    )
        p=fabs(sinf(M_PI*i++/n))*n+.5,   // Calculate separation / 2
        r=rand()&3,                      // Pick random number [0-4)
        o^=4*!p,                         // Reverse order if crossing
        printf(p                         // Print... if not crossing:
                ?"%*c%s%c\n"             //  indent+character+dashes+character
                :"%*c\n",                //  Else indent+character
                n-p+1,                   // Width of indent + 1 for char
                c[r+o],                  // First character
                d+256-p*2,               // Dashes
                c[r+4-o]                 // Second character
        );
}

```

# Answer
> 2 votes
# JavaScript (ES6) ~~241~~ ~~244~~ ~~227~~ ~~222~~ 231 bytes

This looked interesting - I love ASCII art!
Just started, still in the process of golfing it...

```
(I,Z)=>{c=i=0,setInterval(_=>{with(Math)m=sin(PI*i++/Z),a=round(++m*Z),b=round((2-m)*Z),r=random()*4|0,D="TGAC"[r],d="actg"[r],e=a-b,c^=!e,p=" ".repeat(a>b?b:a)+(c?D:d)+"-".repeat(e?abs(e)-1:0)+(e?a>b?d:D:""),console.log(p)},I*1e3)

```

**--- EDIT: turns out I can't actually put it in eval() - otherwise it can't access vars I and Z (so adds 9 bytes)**

*\- saved 6 bytes thanks to user81655*
*\- saved 5 bytes thanks to Dave*

## Explanation

```
(I,Z)=>{
  c=i=0,                                // clear vars
  setInterval(_=>{                      // repeat

    with(Math)
      m=sin(PI*i++ / Z),                // calculate waves
      a=round(++m * Z),
      b=round((2-m) * Z),
      r=random()*4|0,                   // get random amino-acids
      D="TGAC"[r],
      d="actg"[r],
      e=a-b,
      c^=!e,                            // alternate upper/lowercase
      p=                                // prepare output
        " ".repeat(
          a>b ? b : a
        )+(
          c ? D : d
        )+

        "-".repeat(
          e ? abs(e)-1 : 0
        )+(
          e ? a>b ? d : D : ""
        ),

      console.log(p)                    // return output
  },I*1e3)                              // repeat for every 'I' seconds
}

```

---
Tags: code-golf, math, ascii-art
---


title: Explain the decimals

text:
# Question
Title: Explain the decimals
Given a decimal in the form of `<float>, <precision>`, you draw the graphical representation of the decimal part (i.e. fraction) of the float. Examples:

1. Input: `6.75, 4`, output:

```
6||| 7
 ----

```

`6.75` (first number from the input) is the number to explain, `4` (the second number from the input) is the number of dashes below the pipes. `6` is the floored 6.75, `7` is the ceiled `6.75`. The number of pipes is the `decimal part of first input number * second input number`.
2. Input: `10.5, 6`, output:

```
10|||   11
  ------

```
3. Input: `20.16, 12`, output

```
20||          21
  ------------

```

`.16` actually takes 1.92 pipes, but since I can't draw 1.92 pipes, I ceil it to 2.
4. Input: `1.1, 12`, output:

```
1|           2
 ------------

```

`.1` is 1.2 pipes in this case, so it's floored to 1 pipe.
5. Also, an edge case. Input: `5, 4` (i.e. the number is an integer), output:

```
5    6
 ----

```

---

* The number to explain is the positive float, limited only by your language abilities.
* The precision number is an even integer, greater than 2 (i.e. minimal required precision is 4). It can be arbitrary large too.
* *\>= n.5* pipes are rounded up, to *n+1* (i.e 1.5 is rounded to 2 and 2.5 is rounded to 3). *\< n.5* pipes are rounded to *n* (i.e. 1.4 is rounded to 1 and 2.4 is rounded to 2).
* If it would be more convenient for your language, you can take the input as an array, e.g. `[6.75, 4]`. If you take the input in the reversed order, i.e. `[4, 6.75]`, please specify it in your answer.

# Answer
## CJam, 32 bytes

```
l~1md@:X*mo'|*XSe]1$)NW$s,S*'-X*

```

Takes the precision first and the decimal second, separated by a space.

Run all test cases.

### Explanation

```
l~   e# Read input and evaluate, pushing precision and decimal on the stack.
1md  e# Divmod 1, separating the decimal into integer and fractional part.
@:X  e# Pull up precision, store in X.
*mo  e# Multiply precision by fractional part and round.
'|*  e# Push that many vertical bars.
XSe] e# Pad with length X with spaces.
1$)  e# Copy integer part and increment.
N    e# Push linefeed.
W$   e# Copy integer part.
s,   e# Get number of digits as length of string representation.
S*   e# Push that many spaces, to indent the hyphens correctly.
'-X* e# Push X hyphens.

```
> 6 votes

# Answer
## Mathematica, 119 bytes

```
a=ToString;b=Array;a[c=Floor@#]<>{b["|"&,d=Round[#2#~Mod~1]],b[" "&,#2-d],a[c+1],"
"," "&~b~IntegerLength@c,"-"&~b~#2}&

```

I tried... Testing:

```
In[1]:= a=ToString;b=Array;f=a[c=Floor@#]<>{b["|"&,d=Round[#2#~Mod~1]],b[" "&,#2-d],a[c+1],"\n"," "&~b~IntegerLength@c,"-"&~b~#2}&;

In[2]:= f[6.75, 4]

Out[2]= 6||| 7
         ----

In[3]:= f[10.5, 6]

Out[3]= 10|||   11
          ------

In[4]:= f[20.16, 12]

Out[4]= 20||          21
          ------------

In[5]:= f[1.1, 12]

Out[5]= 1|           2
         ------------

In[6]:= f[5, 4]

Out[6]= 5    6
         ----

```
> 4 votes

# Answer
## Javascript ES6, ~~105~~ 104 bytes

```
(f,p)=>(i=f|0)+("|".repeat(j=(f-i)*p+.5|0)+" ".repeat(p-j))+(i+1)+(`
`+i).replace(/\d/g," ")+"-".repeat(p)

```

Saved 1 byte thanks to, um, how do you type ՊՓԼՃՐՊՃՈԲՍԼ anyway?
> 4 votes

# Answer
# Java, ~~253~~ ~~206~~ 181 bytes

*Saved 47 bytes thanks to @Kenney by inlining conditions and variables used once, and sorting out redundant variables.*

*Saved 25 bytes again thanks to @Kenney by inlining 2 loops with ternary operators.*

Pure String Manipulation:

Inlined loops version (181 bytes):

```
String m(float f,int p){int g=(int)f,i=0;String h="",q=""+g;int c=q.length();for(;i<c+p;)h+=i++<c?" ":"-";for(i=c;i<p+c;)q+=i++<c+Math.round((f-g)*p)?"|":" ";return q+(g+1)+"\n"+h;}

```

4 loops version (206 bytes):

```
String m(float f,int p){int g=(int)f,i=0;String h="",q=""+g;int c=q.length();for(;i++<c;)h+=" ";for(;i<=c+p;i++)h+="-";for(i=c;i<c+Math.round((f-g)*p);i++)q+="|";for(;i++<p+c;)q+=" ";return q+(g+1)+"\n"+h;}

```

Ungolfed version:

```
String m(float f,int p){
//initialize some useful values, d is the number of pipes needed
int g=(int)f,d=Math.round((f-g)*p),i=0;
String h="",q=""+g;//append the floored value to the pipe string first
int c=q.length();
for(;i<c;i++)h+=" ";//pad hyphen string with spaces for alignment
for(++i;i<=c+p;i++)h+="-";//append hyphens
for(i=c;i<c+d;i++)q+="|";//append pipes
for(;i<p+c;i++)q+=" ";//append spaces for padding
return q+(g+1)+"\n"+h;}//concatenate the strings in order, separating the strings with a UNIX newline, and return it.

```

Working example here at ideone.com. The full program accepts STDIN input as `<float>,<precision>`.

NOTE: Java's `Math.round(float)` rounds using `RoundingMode.HALF_UP`as the default, which is the OP's required behaviour.

The output of the test cases provided was diff-matched to what the OP provided.
> 3 votes

# Answer
# Japt, ~~47~~ 46 bytes

```
Uf +'|pA=ºU-Uf)*V c)+SpV-A +Uc +R+SpUk l)+'-pV

```

Just a bunch of adding and repeating.

Try it online
> 3 votes

# Answer
## Haskell, 113 bytes

```
(%)=replicate.round
s=show
x!y|(n,m)<-properFraction x=[s n,(y*m)%'|',(y-y*m)%' ',s$n+1,"\n",s n>>" ",y%'-']>>=id

```

Usage example:

```
*Main> putStrLn $ 20.16 ! 12
20||          21
  ------------

```

`properFraction` splits the decimal into it's integer and fraction part. The output is a list of the parts (initial number, bars, spaces, ...) which is concatenated into a single string (via `>>=id`).
> 2 votes

# Answer
# MATL, 49 bytes

```
2#1\tYUbiXK*Yo'|'1bX"tnKw-Z"hb1+YUhht4Y2m13*_45+c

```

Uses release 6.0.0 of the language/compiler. Runs on Matlab or Octave.

Takes numbers in the same order as in the challenge.

### Examples

```
>> matl
 > 2#1\tYUbiXK*Yo'|'1bX"tnKw-Z"hb1+YUhht4Y2m13*_45+c
 >
> 20.16
> 12
20||          21
  ------------

>> matl
 > 2#1\tYUbiXK*Yo'|'1bX"tnKw-Z"hb1+YUhht4Y2m13*_45+c
 >
> 5
> 4
5    6
 ----

```

### Explanation

```
2#1\       % implicit input 1st number. Separate decimal and integer part
tYU        % duplicate integer part and convert to string
biXK*Yo    % input 2nd number. Copy it. Multiply by decimal part of 1st number and round
'|'1bX"    % row vector of as many '|' as needed
tnKw-Z"    % row vector of as many spaces as needed
h          % concat horiontally
b1+YUhh    % integer part of 1st number plus 1. Convert to string. Concat twice
t4Y2m      % detect numbers in this string
13*_45+c   % transform numbers into spaces, and non-numbers into '|'
           % implicitly display both strings

```
> 2 votes

# Answer
# Perl, 90 bytes

```
print$f,"|"x($d=.5+($b=pop)*(($a=pop)-($f=0|$a))),$"x(1+$b-$d),$f+1,$/,$"x length$f,"-"x$b

```

Expects input as commandline arguments. Save in a file (say `90.pl`) and run as `perl 90.pl 6.75 4`

***With comments***

```
print $f,                        # floored input (initialized below due to expr nesting)
      "|" x ($d=.5+              # rounded pipe count (`x` operator casts to int)
             +($b=pop)           # second argument  (executed first)
             *( ($a=pop)         # first argument   (executed second)
               -($f=0|$a) )      # minus floored first argument = fractional part
            ),
      $"x(1+$b-$d),              # spaces
      $f+1,                      # floored + 1
      $/,                        # newline
      $"  x length $f,           # 2nd line alignment
      "-" x $b                   # the 'ruler'

```
> 2 votes

# Answer
# Python 3, ~~116~~ 108 bytes

```
def f(F,P):l=int(F);h,p=str(l+1),int((F-l)*P+.5);l=str(l);print(l+"|"*p+" "*(P-p)+h);print(" "*len(l)+"-"*P)

```

trinket.io link

Thank you to Seeq for saving a few characters.

### First version:

```
def f(F,P):
 l=int(F)
 h,s,p=str(l+1)," ",int((F-l)*P+.5)
 l=str(l)
 print(l+"|"*p+s*(P-p)+h)
 print(s*len(l)+"-"*P)

```

Ungolfed version:

```
def frac(F,P):
        low = int(F)
        high = low+1
        pipes = int((F-low)*P+.5)
        print(str(low)+"|"*pipes+" "*(P-pipes)+str(high))
        print(" "*len(str(low))+"-"*P)

```
> 1 votes

# Answer
# Stackgoat, ~~31~~ 27 bytes

```
CFv1%C*D'|^w1P-Y^vHXNY^w'-^

```

Similar to most of the other answers. I'll see if I can golf more. The input can be comma separated, space separated, or almost anything separated.

## Explanation

```
CF   // Input, floored, push to stack
v1%  // Decimal part
C*   // Times second part
D    // Duplicate that result
'|^  // Repeat | by previous number
w    // Second input
1P   // Move # of |'s to the top of stack
-    // Subtract
Y^   // Repeat " " by above number
vH   // Ceil first input
X    // Newline
Z+   // Add to
N    // Get length of first #
Y^   // Repeat by spaces
w'-  // Repeat - second input times

```
> 1 votes

# Answer
# Lua, 157 bytes

Long, but can't find a shorter solution

```
function f(d,n)r=""a=math.floor(d)d,s=d-a,a..r for i=1,#s do r=r.." "end for i=1,n do s,r=s..(i-.5>n*d and" "or"|"),r.."-"end s=s..a+1 return s.."\n"..r end

```

### Ungolfed

```
function g(d,n)
  r=""
  a=math.floor(d)
  d,s=d-a,a..r                         -- d now contains its decimal part
  for i=1,#s do r=r.." "end            -- padding the hyphens
  for i=1,n
  do
    s,r=s..(i-.5>n*d and" "or"|"),r.."-"
    -- s is concatenated with a "|" if i-.5>n*d, a space otherwise
  end
  s=s..a+1
  return s.."\n"..r
end

```

You can test lua online, the following test cases could be useful :)

```
function f(d,n)r=""a=math.floor(d)d,s=d-a,a..r for i=1,#s do r=r.." "end for i=1,n do s,r=s..(i-.5>n*d and" "or"|"),r.."-"end s=s..a+1 return s.."\n"..r end
print(f(16.75,4))
print(f(5,4))
print(f(20.16,12))

```
> 1 votes

# Answer
# C, ~~233~~ 231 bytes

```
#include <stdlib.h>
#include <math.h>
i,n,l;main(c,v)char**v;{double m;l=atol(v[2]);n=(int)(modf(atof(v[1]),&m)*l+0.5);c=printf("%.f",m);for(;i++<l;)putchar(i>n?32:'|');printf("%.f\n",m+1);printf("%*s",c,"");for(;--i;)putchar(45);}

```

## Ungolfed:

```
#include <stdlib.h>
#include <math.h>
i,n,l;

main(c,v)
char**v;
{
    double m;
    l=atol(v[2]); /* Get length from command line */
    n=(int)(modf(atof(v[1]),&m)*l+0.5); /* Get number of pipes and lower limit */
    c=printf("%.f",m); /* print lower limit */

    /* print pipes and spaces */
    for(;i++<l;)
            putchar(i>n?32:'|');

    /* print upper limit */
    printf("%.f\n",m+1);

    /* print spaces before dashes */
    printf("%*s",c,"");

    /* print dashes */
    for(;--i;)
            putchar(45);
}

```
> 1 votes

---
Tags: code-golf, ascii-art
---