title: Implement decimal-multiplication modulo

text:
# Question
Title: Implement decimal-multiplication modulo
Most people can't easily do modulus (or work out if a number is divisible by another number) in their heads because long division is harder than addition, subtraction and multiplication. The following method describes a way to calculate modulus in your head, as long as you can remember just a few different numbers. This challenge is to write some code that replicates this method instead of using the built-in modulo operator.

I apologise in advance for all of the restrictions, they are there to (hopefully) stop people from trying to work around the problem, instead of solving it the way it's presented. Another way of thinking about this is to assume that division is prohibitively expensive but the other three basic operators are relatively cheap to perform.

---

Decimal-multiplication modulo (*d* mod *n*) works by splitting the dividend (*d*) into chunks of the same length as the divisor (*n*), working from **right to left**. Then, working from **left to right**, each chunk is summed to a running total and the total is multiplied by a constant (*c*) before summing the next chunk. *c* is calculated by subtracting *n* from the next highest power of 10.

* You **may** use any method to calculate the lowest power of 10 that is greater than *n*, including logarithms
* You **may** keep subtracting *n* from *c* until *c* is less than *n* (but not negative)
* You **must not** use division or modulo to calculate *c*
* You **must not** convert any number to any base other than base 10
* You **may** use any method to split *d* into groups of decimal digits, including division and modulo if it makes your code easier
* You **must only** use the following mathematical operators on the chunks
    + addition: `+`, `++`
    + subtraction: `-`, `--` (not on numbers with more digits than *n* has)
    + multiplication: `*` (only by *c*)
    + comparison (`<`, `>`, `==`, `<=`, `>=`, `!=`/`<>`)
* You **must not** use subtraction on any number with more digits than *n*, except when calculating *c*
* You **must not** subtract any value other than *c*, except when calculating *c*
* You **must not** multiply by any value other than *c*
* You **must not** use negative numbers at any point, including as the result of any calculation

You don't have to implement the method exactly as described here as long as you stick to its principles. E.g., if the divisor is 37 and one of the chunks is 56, you can subtract 37 from 56 to give 19 before using it further.

Your code will take two integers or string representations of decimal integers, whichever is most natural for your language. The first will be non-negative (*d* ≥ 0), the second will be positive (*n* ≥ 1). Your code will output a decimal integer or a string representation containing the result 0 ≤ *d* mod *n* ≤ n - 1.

### Example

**1234** mod **37**

The lowest power of 10 higher than **37** is 100

c = 100 - **37** = 63 (26 is also acceptable as it is 63 - **37**)

**37** has two digits so split **1234** into two-digit chunks:

```
1234
% 37
====
12 34  -> vv
--
26 *  0 + 12 = 12
   --
26 * 12 + 34 = 346

```

346 has more than two digits, repeat the process:

```
 346
% 37
====
 3 46  -> vv
--
26 *  0 +  3 = 3
   --
26 *  3 + 46 = 124

```

124 also has more than two digits, repeat the process once more:

```
 124
% 37
====
 1 24  -> vv
--
26 *  0 +  1 = 1
   --
26 *  1 + 24 = 50

```

Since 50 has two digits and is larger than **37**, subtract **37** from it as many times as needed to bring the total below **37**.

```
  50
- 37
====
  13

```

13 is indeed **1234** mod **37**.

This is , so the lowest score wins!

# Answer
## ES7, 86 bytes

```
f=(d,n,t=10**(''+n).length)=>d<n?d:f(d<t?d-n:(g=d=>d<t?d:g((d-d%t)/t)*(t-n)+d%t)(d),n)

```

Ungolfed:

```
function modulo(d, n) {
    var t = Math.pow(10, 1 + Math.floor(Math.log10(n)));
    var c = t - n;
    function chunk(p) {
        if (p < t) return p; // reached the leftmost chunk
        // first recursively process the left part of the number
        return chunk(Math.floor(p / t)) * c + p % t;
    }
    while (d >= t) d = chunk(d);
    while (d >= n) d -= n;
    return d;
}

```
> 1 votes

---
Tags: code-golf, number, restricted-source
---


title: Same-color arithmetic progressions

text:
# Question
Title: Same-color arithmetic progressions
Van der Waerden's theorem says that

> For any given positive integers `r` and `k`, there is some number `N` such that if the integers `{1, 2, ..., N}` are colored, each with one of `r` different colors, then there are at least `k` integers in arithmetic progression all of the same color. The least such `N` is the Van der Waerden number `W(r, k)`.

Your goal is to compute the Van der Waerden number `W(r, k)` given positive-integer inputs `r` and `k`. Fewest bytes wins.

Beware that this function grows extremely quickly and is time-consuming to compute. Even `W(4, 4)` is unknown. You may assume your code runs on an ideal computer with unlimited resources (time, memory, stack depth, etc). Your code must theoretically give the right answer even for values for which the answer is not known.

Built-ins that compute this function are not allowed.

**Example**

For `r = 2` colors and progressions of length `k = 3`, there is a length-`8` sequence that avoids such a progression, i.e. `3` equally-spaced elements of the same color:

```
B R R B B R R B

```

But, there's no such length-`9` sequence, so `W(2, 3) == 9`. For instance,

```
R B B R B R R B R
  ^     ^     ^

```

contains the length-`3` same-color arithmetic progression shown.

**Test cases**

You'll probably only be able to test small cases.

```
+-----+-----+-----+-----+-----+-----+------+
|     | k=1 | k=2 | k=3 | k=4 | k=5 | k=6  |
+-----+-----+-----+-----+-----+-----+------+
| r=1 |   1 |   2 |   3 |   4 |   5 |    6 |
| r=2 |   1 |   3 |   9 |  35 | 178 | 1132 |
| r=3 |   1 |   4 |  27 | 293 |     |      |
| r=4 |   1 |   5 |  76 |     |     |      |
+-----+-----+-----+-----+-----+-----+------+

```

```
var QUESTION_ID=71776,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/71776/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 8 votes
## Python 3.5, ~~125~~ ~~124~~ 119 bytes

```
f=lambda r,k,*L:any(L[:x*k:x]==k*(*{*L[:x*k:x]},)for x in range(1,len(L)+1))*len(L)or max(f(r,k,i,*L)for i in range(r))

```

It's funny because, over the course of golfing this, the program actually got *more* efficient. Anything beyond `f(2,4)` or `f(3,3)` still takes forever, though.

### Explanation

The initial version checked whether a sequence contained a progression of length `k` by trying all possible start indices and steps.

```
def f(r,k,L=[]):
 for i in range(len(L)):
  for j in range(len(L)):
   if len(set(L[i::j+1]))==1 and len(L[i::j+1])==k:
    return len(L)
 return max(f(r,k,L+[i])for i in range(r))

```

The golfed version only needs to try all possible steps since it *prepends* new sequence elements. The `x*k` cap is to take care of cases like `[0, 0, 1]`, which contains a progression of length 2 but would not satisfy the uniqueness check uncapped.

As for the check

```
L[:x*k:x]==k*(*{*L[:x*k:x]},)

```

On the first pass of the golfed version, when `L` is empty, `len(L)` is 0. Thus the second half of the `or` will always be executed. After that `L` is non-empty, so `{*L[:x*k:x]}` (which is just Python 3.5 for `set(L[:x*k:x])`) will have at least one element.

Since `L[:x*k:x]` can have at most `k` elements and for `L` non-empty `k*(*{*L[:x*k:x]},)` has at least `k` elements, the two can only be equal when there are exactly `k` elements in both. For this to happen `{*L[:x*k:x]}` must have exactly one element, i.e. we only have one colour in our progression.

---
Tags: code-golf, math, sequence, combinatorics, subsequence
---


title: Generate Programs in Increasing size

text:
# Question
Title: Generate Programs in Increasing size
In this challenge, you will write a program which outputs a program which is the **double** the length of the original program. The outputted program should output a new program a program double *its* length.

## Examples

If my program is `a`:

```
< a
> aa

< aa
> aaaa

< aaaa
> aaaaaaaa

```

## Rules

* No quine built-ins
* The original program must be at least one byte
* The sequence should theoretically work infinitely
* Your program is not allowed to read from anything (file, stdio)

Your score is the size of the original program.

# Answer
> 12 votes
## CJam, 10 bytes

```
{"_~"+_}_~

```

Test it here.

### Explanation

```
{"_~" e# Generalised quine framework, leaves the block and the string "_~"
      e# on the stack.
+     e# Prepend the block to the string.
_     e# Duplicate the resulting array.
}_~

```

# Answer
> 8 votes
## JavaScript, ~~62~~ ~~61~~ 37 bytes

Thanks to @Doᴡɴɢᴏᴀᴛ for the help!

---

*Original \[37 bytes\]:*

```
f=_=>'f='+'_'.repeat((10+f).length)+f

```

*Child \[74 bytes\]:*

```
f=______________________________________=>'f='+'_'.repeat((10+f).length)+f

```

*Grandchild \[148 bytes\]:*

```
f=________________________________________________________________________________________________________________=>'f='+'_'.repeat((10+f).length)+f

```

---

**Alternate (with printing to console, and as a full program):**

*Original \[61 bytes\]:*

```
f=_=>console.log(`f=${'_'.repeat((0+f).length+5)+f};f()`);f()

```

*Child \[122 bytes\]:*

```
f=______________________________________________________________=>console.log(`f=${'_'.repeat((0+f).length+5)+f};f()`);f()

```

*Grandchild \[244 bytes\]:*

```
f=________________________________________________________________________________________________________________________________________________________________________________________=>console.log(`f=${'_'.repeat((0+f).length+5)+f};f()`);f()

```

---

**How it works!**

**1.** `f=_=>` Define function f as `console.log(...)`

**2.** `;f()` Run function f.

**3.** *(in function f)*

* `console.log(...)` Print the following:

+ `f=` literal text "f="
    + `${'_'.repeat((0+f).length+5)` "\_" repeated for the length of f, altered to account for characters not included in the stringification of f
    + `+f}` The stringification of function f
    + `;f()` literal text ";f()"

**Notes**

* `console.log` is necessary instead of `alert` because `alert` doesn't seem to play well with really long strings (at least on my machine/browser configuration)
* The `_`'s are inserted into the name of the (unused) parameter of function f, to ensure that they are included in the stringification of f.
* Main improvement (aside from getting rid of the `console.log`) of the first solution over the second: adding `10` to the function instead of `0` to cast it to string makes it one byte longer, eliminating the need to add 1 to the length afterwards, saving a byte.

# Answer
> 6 votes
## Minkolang 0.15, ~~19~~ 14 bytes

```
"66*2-rIDdr$O.

```

Original, child, grandchild.

### Explanation

```
"66*2-      $O.    Standard quine formulation

      r            Reverse stack
       I           Push length of stack
        D          Pop n and duplicate top of stack n times
         d         Duplicate top of stack
          r        Reverse stack

```

What the bit in between `r`s does is duplicate the ending period enough times to fulfill the doubling criterion. `.` is the "stop program" character, so the many periods at the end do nothing except be there.

# Answer
> 3 votes
# CJam, 12 bytes

```
{"_~"1$1$}_~

```

When run, this will print

```
{"_~"1$1$}_~{"_~"1$1$}_~

```

which, in turn, will print

```
{"_~"1$1$}_~{"_~"1$1$}_~{"_~"1$1$}_~{"_~"1$1$}_~

```

and so on.

Try it online!

# Answer
> 2 votes
# Python 3, 51 bytes

```
x=r"print('x=r\"'+x+'\"'+';exec(x*2)');";exec(x*2)

```

This includes a trailing newline.

Which outputs:

```
x=r"print('x=r\"'+x+'\"'+';exec(x*2)');";exec(x*2)
x=r"print('x=r\"'+x+'\"'+';exec(x*2)');";exec(x*2)

```

# Answer
> 2 votes
# GolfScript, 11 bytes

```
{: ".~"]}.~

```

Try it online!

### How the source code works

```
{: ".~"]}.~

{       }    Define and push a code block.
         .~  Push a copy and execute it.
 :           Save the code block in the space character.
             Every subsequent space will now execute the code block.
   ".~"      Push that string.
       ]     Wrap the entire stack in an array.

```

If the above source code is executed once, the stack will end up as

```
["" {: ".~"]} ".~"]

```

where the empty string at the beginning corresponds to the initial state of the stack (empty input).

Two copies of the source code would leave a final state of

```
[["" {: ".~"]} ".~"] {: ".~"]} ".~"]

```

and so on.

### What happens next

After executing the source code, the interpreter does the following:

1. It wraps the entire stack in an array, and pushes that array on the stack.

For a single copy of the source code, the stack now contains

```
["" {: ".~"]} ".~"] [["" {: ".~"]} ".~"]]

```
2. It executed `puts` with the intention of printing the wrapped stack, followed by a linefeed.

`puts` is defined as `{print n print}`, so it does the following.

1. `print` prints the wrapped up copy of the stack without inspecting it (i.e., without converting it to its string representation). This sends

    ```
    {: ".~"]}.~

    ```

    to STDOUT and pops the stack copy from the top of the stack.

    The stack now contains

    ```
    ["" {: ".~"]} ".~"]

    ```
    2. executes the code block we defined previously.

    `:` begins by saving `["" {: ".~"]} ".~"]` in the space character, then `".~"` pushes itself and `]` wraps the stack in an array.
    3. `n` pushes a string consisting of a single linefeed.

    The stack now contains

    ```
    [["" {: ".~"]} ".~"] ".~"] "\n"

    ```
    4. is executed once more. However, it was redefined when we called it for the first time and now contains an array, not a code block.

    In fact, it pushes `["" {: ".~"]} ".~"]`, leaving the stack as

    ```
    [["" {: ".~"]} ".~"] ".~"] "\n" ["" {: ".~"]} ".~"]

    ```
    5. Finally, `print` prints the topmost stack item without inspecting it, sending

    ```
    {: ".~"]}.~

    ```

    to STDOUT.

# Answer
> 1 votes
# , 26 chars / 36 bytes

```
⟮ô`\u27ee⦃ᶈ0}\u27ef
`ď2)⟯

```

`Try it here (Firefox only).`

Note that there is a trailing newline.

# Explanation

Standard quine: `⟮ⒸⅩ222+ᶈ0`

Modifications:

* Use `ô` function to output the quines all results instead last result (as done using implicit output)
* Use `\u27ee⦃ᶈ0}\u27ef\n` and close copy block to prevent conflicts with later copy blocks.
* Use `ď2` to repeat string twice.

---
Tags: code-golf, sequence, quine, code-generation
---


# Question
Title: Last Nonzero Digits of a Factorial in Base
You should write a program or function which given three positive integers `n b k` as input outputs or returns the last `k` digits before the trailing zeros in the base `b` representation of `n!`.

## Example

```
n=7 b=5 k=4
factorial(n) is 5040
5040 is 130130 in base 5
the last 4 digits of 130130 before the trailing zeros are 3013
the output is 3013

```

## Input

* 3 positive integers `n b k` where `2 <= b <= 10`.
* The order of the input integers can be chosen arbitrarily.

## Output

* A list of digits returned or outputted as an integer or integer list.
* Leading zeros are optional.
* **Your solution has to solve any example test case under a minute** on my computer (I will only test close cases. I have a below-average PC.).

## Examples

*New tests added to check correctness of submissions. (They are not part of the under 1 minute runtime rule.)*

Input =\> Output (with the choice of omitting leading zeros)

```
3 10 1  =>  6

7 5 4  =>  3013

3 2 3  =>  11

6 2 10  =>  101101

9 9 6  =>  6127

7 10 4  =>  504

758 9 19  =>  6645002302217537863

158596 8 20  =>  37212476700442254614

359221 2 40  =>  1101111111001100010101100000110001110001

New tests:
----------

9 6 3  =>  144

10 6 3  =>  544

```

This is code-golf, so the shortest entry wins.

# Answer
# Dyalog APL, 23 bytes

```
⌽k↑⌽{⍵↓⍨-⊥⍨0=⍵}b⊥⍣¯1⊢!n

```

This program works as long as the factorial does not exceed internal representation limit. In Dyalog APL, the limit can be raised by `⎕FR←1287`.

Assumes the variables n, b, and k have been set (e.g. `n b k←7 5 4`), but if you rather want prompting for *n*, *b*, and *k* (in that order) then replace the three characters with .
> 1 votes

# Answer
# Mathematica, ~~57~~ 48 bytes

Saved 9 bytes thanks to @2012rcampion .

```
IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&

```
> 7 votes

# Answer
## Python, 198 192 181 chars

```
def F(n,b,k):
 p=5820556928/8**b%8;z=0;e=f=x=1
 while n/p**e:z+=n/p**e;e+=1
 z/=1791568/4**b%4;B=b**(z+k)
 while x<=n:f=f*x%B;x+=1
 s='';f/=b**z
 while f:s=str(f%b)+s;f/=b
 return s

```

It's fast enough, ~23 seconds on the biggest example. And no factorial builtin (I'm looking at you, Mathematica!).
> 7 votes

# Answer
# Pyth, ~~26~~ 35 bytes

```
M?G%GHg/GHH.N>ju%g*GhHT^T+YslNN1T_Y

```

This is a function of 3 arguments, number, base, number of digits.

Demonstration.

The slowest test case, the final one, takes 15 seconds on my machine.
> 6 votes

# Answer
## PARI/GP, 43 bytes

Trading speed for space yields this straightforward algorithm:

```
(n,b,k)->digits(n!/b^valuation(n!,b)%b^k,b)

```

Each of the test cases runs in less than a second on my machine.
> 2 votes

# Answer
# Haskell, ~~111~~ 109 bytes

```
import Data.Digits
f n b k=digits b$foldl(((unDigits b.reverse.take k.snd.span(<1).digitsRev b).).(*))1[1..n]

```

Usage: `f 158596 8 20` -\> `[3,7,2,1,2,4,7,6,7,0,0,4,4,2,2,5,4,6,1,4]`

Takes about 8 seconds for `f 359221 2 40` on my 4 year old laptop.

How it works: fold the multiplication (`*`) into the list `[1..n]`. Convert every intermediate result to base `b` as a list of digits (least significant first), strip leading zeros, then take the first `k` digits and convert to base 10 again. Finally convert to base `b` again, but with most significant digit first.
> 2 votes

# Answer
# Python 3, 146 bytes

```
import math
i,f=input(),int
n=i.split()
e=math.factorial(f(n[0]))
d=''
while e>0:
 d=str((e%f(n[1])))+d;e=e//f(n[1])
print(d.strip('0')[-f(n[2]):])

```

I'm not sure the test cases will all run fast enough - the larger ones are very slow (as it is looping through the number).

Try it online here (but be careful).
> 1 votes

# Answer
# Java, ~~303~~ ~~299~~ 296 bytes

```
import java.math.*;interface R{static void main(String[]a){BigInteger c=new BigInteger(a[1]),b=c.valueOf(1);for(int i=new Integer(a[0]);i>0;i--){b=b.multiply(b.valueOf(i));while(b.mod(c).equals(b.ZERO))b=b.divide(c);b=b.mod(c.pow(new Integer(a[2])));}System.out.print(b.toString(c.intValue()));}}

```

On my computer, this averages a little under a third of a second on the `359221 2 40` testcase. Takes input via command line arguments.
> 1 votes

# Answer
# bc, 75 bytes

```
define void f(n,b,k){
obase=b
for(x=1;n;x%=b^k){
x*=n--
while(!x%b)x/=b}
x}

```

This uses some GNU extensions to reduce code size; a POSIX-conforming equivalent weighs in at 80 bytes:

```
define f(n,b,k){
obase=b
for(x=1;n;x%=b^k){
x*=n--
while(x%b==0)x/=b}
return(x)}

```

To keep run times reasonable, we trim the trailing zeros (`while(!x%b)x/=b`) and truncate to the final `k` digits (`x%=b^k`) as we compute the factorial (`for(x=1;n;)x*=n--`).

### Test program:

```
f(3, 10, 1)
f(7, 5, 4)
f(3, 2, 3)
f(6, 2, 10)
f(9, 9, 6)
f(7, 10, 4)
f(758, 9, 19)
f(158596, 8, 20)
f(359221, 2, 40)
f(9, 6, 3)
f(10, 6, 3)
quit

```

Runtime of the full test suite is approx 4¼ seconds on my 2006-vintage workstation.
> 1 votes

# Answer
## PHP, 80 bytes

```
function f($a,$b,$c){echo substr(rtrim(gmp_strval(gmp_fact($a),$b),"0"),-1*$c);}

```

Used as `f(359221,2,40)` for the last test case. Runs pretty smoothly for all test cases.

Try here !
> 0 votes

---
Tags: code-golf, number-theory, base-conversion, restricted-time, factorial
---


# Question
Title: Enhanced Builder Pattern, verified at compile time
Question: can you design a Builder Pattern API which verifies at compile time that every field is set exactly once?

To be eligible, the size of the compiler output should not be exponential in the number of fields. The best solution will be the shortest implementation for a class of 22 fields.

---

## Example of a possible surface API in java

Given an class for immutable data structure such as this one:

```
public class Human {
  private final String name;
  private final Int age;
  private final Double money;

  public Human(String name, Int age, Double money) {
    this.name = name;
    this.age = age;
    this.money = money;
  }

  public String getName() { return name; }
  public Int getAge() { return age; }
  public Double getMoney() { return money; }
}

```

The goal is to design an API to construct instances this `Humain` class with the following requirements, checked at compile time (the code in example is just a possible design, you can come up with anything that is equivalent in term of functionally):

* Possible to set parameters in any order:

```
Human h = HumanBuilder().withName("n").withMoney(0.15).withAge(1).build();
Human g = HumanBuilder().withName("n").withAge(1).withMoney(0.15).build();

```
* Possible to set parameters in different places of the code:

```
// Given appropriate takesCareOfTheMan & takesCareOfTheMoney methods
Human h = takesCareOfTheMan(takesCareOfTheMoney(HumanBuilder())).build();
Human g = takesCareOfTheMoney(takesCareOfTheMan(HumanBuilder())).build();

```
* Impossible to set the same parameter twice:

```
// This should not compile:
// Human h = HumanBuilder().withName("n").withAge(1).withAge(2).withMoney(0.15).build();

```
* Impossible to omit a parameter:

```
// This should not compile:
// Human h = HumanBuilder().withName("n").withMoney(0.15).build();

```

# Answer
How about something like this, in Haskell:

```
{-# LANGUAGE GADTs, DataKinds, KindSignatures, StandaloneDeriving #-}
module Builder ( Human', Human, mkHuman, unHuman
               , withName, withAge, withMoney
               ) where

data Optional (b :: Bool) (a :: *) where
    Missing :: Optional False a
    Present :: a -> Optional True a
deriving instance (Show a) => Show (Optional b a)

data Human' b1 b2 b3 where
    MkHuman :: Optional b1 String -> Optional b2 Int -> Optional b3 Double -> Human' b1 b2 b3
deriving instance Show (Human' b1 b2 b3)

type Human = Human' True True True

mkHuman :: Human' False False False
mkHuman = MkHuman Missing Missing Missing

unHuman :: Human -> (String, Int, Double)
unHuman (MkHuman (Present name) (Present age) (Present money)) = (name, age, money)

withName :: String -> Human' False b2 b3 -> Human' True b2 b3
withName name (MkHuman _ age money) = MkHuman (Present name) age money

withAge :: Int -> Human' b1 False b3 -> Human' b1 True b3
withAge age (MkHuman name _ money) = MkHuman name (Present age) money

withMoney :: Double -> Human' b1 b2 False -> Human' b1 b2 True
withMoney money (MkHuman name age _) = MkHuman name age (Present money)

```

Example usage:

```
h1, h2 :: Human
h1 = withName "n" . withMoney 0.15 . withAge 1 $ mkHuman
h2 = withName "n" . withAge 1 . withMoney 0.15 $ mkHuman

takesCareOfTheName :: Human' False b2 b3 -> Human' True b2 b3
takesCareOfTheName = withName "John"

-- This doesn't typecheck
h3 :: Human
h3 = withName "newName" h1

-- Neither does this
h4 :: Human
h4 = withName "n" . withAge 1 $ mkHuman

```
> 3 votes

# Answer
OK here's one, also in Haskell, that is much more extensible: notice how `Human` is merely a `Builder` with a specific index of field types.

```
{-# LANGUAGE GADTs, DataKinds, KindSignatures, StandaloneDeriving #-}
{-# LANGUAGE TypeOperators, TypeFamilies #-}
{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances, FlexibleContexts #-}

data Optional (b :: Bool) (a :: *) where
    Missing :: Optional False a
    Present :: a -> Optional True a
deriving instance (Show a) => Show (Optional b a)

data Builder (as :: [*]) (bs :: [Bool]) where
    BNil :: Builder '[] '[]
    BCons :: Optional b a -> Builder as bs -> Builder (a ': as) (b ': bs)

type family Empty_ as where
    Empty_ '[] = '[]
    Empty_ (a ': as) = False ': Empty_ as

type family Full_ as where
    Full_ '[] = '[]
    Full_ (a ': as) = True ': Full_ as

type family Empty builder where
    Empty (Builder as) = Builder as (Empty_ as)

type family Full builder where
    Full (Builder as) = Builder as (Full_ as)

data Tuple as where
    TNil :: Tuple '[]
    (:>) :: a -> Tuple as -> Tuple (a ': as)

infixr 5 :>

fromFull :: Full (Builder as) -> Tuple as
fromFull BNil = TNil
fromFull (BCons (Present x) xs) = x :> fromFull xs

class Buildable as where
    emptyBuilder :: Empty (Builder as)

instance Buildable '[] where
    emptyBuilder = BNil

instance (Buildable as) => Buildable (a ': as) where
    emptyBuilder = BCons Missing emptyBuilder

type Human = Builder '[String, Int, Double]

mkHuman :: Empty Human
mkHuman = emptyBuilder

data Nat = Z | S Nat

data Lookup i as where
    Here :: a -> Lookup Z (a ': as)
    There :: Lookup i as -> Lookup (S i) (a ': as)

type family FillAt i bs where
    FillAt Z (False ': bs) = True ': bs
    FillAt (S i) (b ': bs) = b ': FillAt i bs

class Fill bs (i :: Nat) where
    fill :: Lookup i as -> Builder as bs -> Builder as (FillAt i bs)

instance Fill (False ': bs) Z where
    fill (Here x) (BCons Missing xs) = BCons (Present x) xs

instance (Fill bs i) => Fill (b ': bs) (S i) where
    fill (There k) (BCons x xs) = BCons x $ fill k xs

withName :: (Fill bs Z) => String -> Human bs -> Human (FillAt Z bs)
withName = fill . Here

withAge :: (Fill bs (S Z)) => Int -> Human bs -> Human (FillAt (S Z) bs)
withAge = fill . There . Here

withMoney :: (Fill bs (S (S Z))) => Double -> Human bs -> Human (FillAt (S (S Z)) bs)
withMoney = fill . There . There . Here

unHuman :: Full Human -> (String, Int, Double)
unHuman h = case fromFull h of
    name :> age :> money :> TNil -> (name, age, money)

h1, h2 :: Full Human
h1 = withName "n" . withMoney 0.15 . withAge 1 $ mkHuman
h2 = withName "n" . withAge 1 . withMoney 0.15 $ mkHuman

takesCareOfTheName :: (Fill bs Z) => Human bs -> Human (FillAt Z bs)
takesCareOfTheName = withName "John"

-- -- This doesn't typecheck
-- h3 :: Full Human
-- h3 = withName "newName" h1

-- -- Neither does this
-- h4 :: Full Human
-- h4 = withName "n" . withAge 1 $ mkHuman

```
> 1 votes

# Answer
```
import shapeless.<:!<

case class HumanBuilder[A]( name: String, age: Int, money: Double) {

  def withName(name: String)(implicit ev: A <:!< Name): HumanBuilder[A with Name] = this.copy[A with Name](name = name)
  def withAge(age: Int)(implicit ev: A <:!< Age): HumanBuilder[A with Age] = this.copy[A with Age](age = age)
  def withMoney(money: Double)(implicit ev: A <:!< Money): HumanBuilder[A with Money] = this.copy[A with Money](money = money)

  def build()(implicit ev: A =:= Builder with Name with Age with Money): Human = Human(name, age, money)
}

object HumanBuilder {

  def apply(): HumanBuilder[Builder] = HumanBuilder[Builder]("", 0, 0.0)

}

trait Builder
trait Name
trait Age
trait Money

case class Human(name: String, age: Int, money: Double)

```

Usage

```
    scala> HumanBuilder().withName("test").withAge(10).withMoney(1.0).build()
res1: puzzle.Human = Human(test,10,1.0)

scala> HumanBuilder().withMoney(3.0).withName("test").withAge(10).build()
res2: puzzle.Human = Human(test,10,3.0)

scala> HumanBuilder().withName("test").withAge(10).withMoney(1.0).withMoney(3.0).build()
<console>:14: error: ambiguous implicit values:
 both method nsubAmbig1 in package shapeless of type [A, B >: A]=> shapeless.package.<:!<[A,B]
 and method nsubAmbig2 in package shapeless of type [A, B >: A]=> shapeless.package.<:!<[A,B]
 match expected type shapeless.<:!<[puzzle.Builder with puzzle.Name with puzzle.Age with puzzle.Money,puzzle.Money]
       HumanBuilder().withName("test").withAge(10).withMoney(1.0).withMoney(3.0).build()
                                                                           ^

scala> HumanBuilder().withName("test").withAge(10).build()
<console>:14: error: Cannot prove that puzzle.Builder with puzzle.Name with puzzle.Age =:= puzzle.Builder with puzzle.Name with puzzle.Age with puzzle.Money.
       HumanBuilder().withName("test").withAge(10).build()

```
> 1 votes

# Answer
In Scala, you could do the following:

```
// Or import shapeless._
object Lib {
  trait Nat
  trait Succ[N <: Nat] extends Nat
  trait Z extends Nat
}

```

```
object Builder {
  import Lib._

  case class Human(age: Int, name: String, money: Double)

  trait WithAge { def age: Int }
  trait WithName { def name: String }
  trait WithMoney { def money: Double }

  trait HumanBuilder {
    type N <: Nat
    type Next[N0 <: Nat] = this.type { type N = Succ[N0] }

    var age: Int = _
    var name: String = _
    var money: Double = _

    def thiz[A]: A = asInstanceOf[A] // ez typecheck
    def withAge(a: Int): Next[N] with WithAge = { age = a; thiz }
    def withName(n: String): Next[N] with WithName = { name = n; thiz }
    def withMoney(m: Double): Next[N] with WithMoney = { money = m; thiz }
  }

  object HumanBuilder {
    def apply() = new HumanBuilder { type N = Z }

    type WithList = WithAge with WithName with WithMoney
    type WithSize = { type N = Succ[Succ[Succ[Z]]] }

    implicit class Build(hb: HumanBuilder with WithList with WithSize) {
      def build(): Human = Human(hb.age, hb.name, hb.money)
    }
  }
}

```

Tests:

```
object Usage extends App {
  import shapeless.test.illTyped
  import Builder._

  illTyped("""
    HumanBuilder()
      .withName("n")
      .withAge(1).withAge(2)
      .withMoney(0.15)
      .build()
  """)

  illTyped("""
    HumanBuilder()
      .withName("n")
      // .withAge(1)
      .withMoney(0.15)
      .build()
  """)

  val h: Human = HumanBuilder()
    .withName("n")
    .withAge(1)
    .withMoney(0.15)
    .build()

  println(h)
}

```
> 0 votes

---
Tags: compile-time
---


title: TinyBF to Brainf*** converter

text:
# Question
Title: TinyBF to Brainf*** converter
We have a Brainf\*** to TinyBF converter, but not the other way around, so here's one.

## Rules:

* Your interpreter must take a valid TinyBF program, on one line, and it must output the corresponding BrainF\*** program, on one line, with optional trailing whitespace/newline. No leading whitespace is allowed
* The input may or may not contain characters that are not any of the four TinyBF characters. If so, you must print all of these characters in the same spots.
* An answer will be accepted on April 1st (not joking), based on some obscure criteria I will use (jk ;) I will accept the shortest program that does not cheat by the following rules)
* No 0-byte or 1-byte solutions, because it ruins the fun if you make (or there is) a programming language just for this purpose)

## Test Cases

---

Input 1: `+++++>+++++=>=|>>+=>>+|=>|>+=>+|` (Computes 5 (byte 1) + 5 (byte 2) = 10 (byte 3))
Output 1: `+++++>+++++<[>>+<<-]>[>+<-]`

Input 2: `+++>++++Hi+++:P+=>=|>|>+>+=>>&&+|=>>|=>>=+!!>>=+|>>>+|` (Computes 3 (byte 1) * 8 (byte 2) = 24 (byte 3)) Output 2: `+++>++++Hi+++:P+<[>[>+>+<<&&-]>>[<<+!!>>-]<<<-]`

# Answer
> 1 votes
## Python 2, 106 bytes

```
a=0
r=''
for c in input():a=[a,~a][c=='='];r+={'+':'+-','>':'><','|':'[]'}.get(c,c)[a%-2]*(c!='=')
print r

```

Implements the TinyBF specification as found here. Try it online. Improvements were made using techniques from @Dica's answer. Requires quoted string input.

# Answer
> 3 votes
# Python 3, 97 bytes

This script is based on @Mego's answer

```
a=0
for c in input():a-=c=='=';print({'+':'+-','>':'><','|':'[]'}.get(c,c)[a%-2]*(c!='='),end='')

```

---
Tags: code-golf, brainfuck
---


title: Read a retro display

text:
# Question
Title: Read a retro display
Art stolen from What size is the digit?

---

7-segment digits can be represented in ASCII using `_|` characters. Here are the digits `0-9`:

```
 _     _  _       _   _  _   _   _
| | |  _| _| |_| |_  |_   | |_| |_|
|_| | |_  _|   |  _| |_|  | |_|  _|

```

Your job is to parse the art into normal numbers.

### Notes on numbers

* Each digit has a different width.
    + `1` has a width of `1`
    + `3` and `7` are `2` wide
    + `245689` and `0` are all `3` wide

Also between each digit is one char of padding. Here is the full char set:

```
 // <-- should be one space, but SE formatting messed it up
|
|
-------------
 _
 _|
|_
-------------
_
_|
_|
-------------

|_|
  |
-------------
 _
|_
 _|
-------------
 _
|_
|_|
-------------
_
 |
 |
-------------
 _
|_|
|_|
-------------
 _
|_|
 _|
-------------
 _
| |
|_|

```

### Input

Input can be either from the console or as a string arg to a function.

### Output

Output is either put to the console or is returned from the function.

## Examples:

```
  _  _   _
|  |  | |_
|  |  | |_|
1776

 _   _     _
 _| | | | |_
|_  |_| | |_|
2016

   _       _
| |_| |_| |_
|  _|   |  _|
1945

   _   _   _   _   _   _
| | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_|
1000000

 _     _  _       _   _  _   _   _
| | |  _| _| |_| |_  |_   | |_| |_|
|_| | |_  _|   |  _| |_|  | |_|  _|
0123456789

```

This is code-golf so shortest byte count wins!

# Answer
> 4 votes
## Pyth, ~~33~~ 30 bytes

```
sm@."/9Àøw"%%Csd409hTcC.z*3d

```

Here's the idea: Once we transpose the input, and split into digits, we can sort of hash the individual digit strings and assign them to their values.

```
sm@."/9Àøw"%%Csd409hTcC.z*3d     Implicit: z=input
                      C.z        Transpose input.
                     c   *3d     Split that on "   ", a space between digits.
 m@."/9Àøw"%%Csd409hT            Map the following lambda d over that. d is a digit string.
             Csd                   Flatten the digit string, and convert from base 256.
            %   409                Modulo that by 409
           %       hT              and then by 11. All digits go to a distinct num mod 11.
   ."/9Àøw"                        The compressed string "03924785/61".
  @                                Index into that string.
s                                Flatten and implicitly output.

```

Try it here.

# Answer
> 4 votes
# Ruby, 184 bytes

```
a=0
l=$<.map{|x|x.bytes.map{|y|y==32?0:1}+[0]*2}
(0..l[0].count-1).map{|i|l[0][i]+2*l[1][i]+4*l[2][i]}.each{|x|
x>0?(a=x+2*a):(p Hash[[40,6,32,20,18,26,42,8,44,64].zip(0..9)][a];a=0)}

```

## Explanation

* takes the input from stdin
* converts the strings to binary sequences, 1/0 for segment on/off
* encodes columns to 3bit binary number
* encodes sequences of 3 bit numbers to 9 bit numbers, use '0' columns as stop symbols
* use a lookup table to convert the 9 bit numbers to digits

This is my first code-golf. Thanks for the fun!

# Answer
> 2 votes
# Japt, 119 bytes

```
Ur"[|_]"1 z r" +
"R x1 qR² £"11
1 1
1151151
111
 15111
115 1
 1
115 1
111
1511
111
15  1
11511
111
115 1
111
11"q5 bXÃq

```

`Try it here!`

Oh geez, this one's really long. I don't think I have finished golfing.

# Explanation

## Preparation

We take the input and convert any `|_` to `1`. Then we transpose, strip out ending spaces, and split along double-newlines.

## Translation

We map over the resulting array and find the index where the form appears in a reference array. Here's a diagram to help:

```
MAPITEM
  11
  1 1 --> This same form appears at index 0 in the reference array
  11                            |
                                |
                                V
                        change the mapitem to 0!

```

After that, we join the array of numbers and output!

**NOTE**: You may be wondering why we have to change each art character to a series of 1's. This is because there seems to be a bug (or something like that) which doesn't let me store the characters as is with `|_`.

# Answer
> 2 votes
# Python2, ~~299~~ ~~261~~ 244 bytes

```
s=lambda a,i=0:[a]if i==len(a[0])else[[j[:i]for j in a]]+s([j[i+1:]for j in a])if all(j[i]==' 'for j in a)else s(a,i=i+1)
p=lambda l:['95572431508448853268'.find(`sum(ord(c)**i for i,c in enumerate("".join(n)))%108`)/2for n in s(l.split('\n'))]

```

I really liked this challenge, good job !

## Explanation

The function `s` takes the three lines as input, it tries to find a digit separation (all characters are spaces). When such a separation is found it calls `s` with the rest of the three lines and add the value returned by the call to the three lines that compose the digit. If there is no separation it means there is only one digit.

The function `p` is the entry point so it takes a string that represent the digits. The digits are stored as a "hash" computed with `sum(ord(c)**i for i,c in enumerate("".join(n)))%108` to save space (thanks to other answers !).

## Exemple

```
digits="""
 _     _
| | |  _|
|_| | |_ """[1:]  # remove the '\n' at the beginning

p(digits)  # [0, 1, 2]

```

## Other versions

261 bytes (py3):

```
s=lambda a,i=0:[a]if i==len(a[0])else[[j[:i]for j in a]]+s([j[i+1:]for j in a])if all(j[i]==' 'for j in a)else s(a,i=i+1)
def p(l):[print([91,21,84,31,58,76,88,41,80,68].index(sum(ord(c)**i%20 for i,c in enumerate("".join(n)))),end="")for n in s(l.split('\n'))]

```

249 bytes, this one transpose the lines (py2):

```
f="".join
s=lambda a,i=0:[a]if i==len(a)else[a[:i]]+s(a[i+1:])if all(c==' 'for c in a[i])else s(a,i=i+1)
h=lambda s:ord(s[0])**len(s)+h(s[1:])if s else 0
p=lambda l:["10220907112527153129".index(`h(f(map(f,n)))%34`)/2for n in s(zip(*l.split('\n')))]

```

# Answer
> 2 votes
# Pyth, 39 bytes

```
sm@"413-928-506--7"%%Crd6C\524cjbC.z*3d

```

This seems to work? Try it online.

# Answer
> 2 votes
# JavaScript (ES6), 169 bytes

```
a=>[...(a=a.split`
`)[0]].map((b,c)=>(d={' ':0,'|':1,'_':2})[b]+d[a[1][c]]*2+d[a[2][c]]).join``.split(0).map(b=>[343,3,182,83,243,281,381,23,383,283].indexOf(+b)).join``

```

Starts by splitting into three lines, remapping each column into a value, and then building a unique identity for each column from those values. It then splits by `0` (the identity for the space between columns), and finally maps each identity to it's number values, which it concatenates and outputs.

# Answer
> 0 votes
# Python 3, ~~281~~ 254 bytes

## Edit

I just looked at the code for the other python answer and noticed that much of the code is similar. This was arrived at independently.

(newlines added for "readability")

```
def p(i):
 n=[[]]
 for l in zip(*i.split('\n')):
  if all(i==" "for i in l):n+=[[]]
  else:n[-1]+=l
 return''.join(map(lambda l:str([''.join(l[2:])==x for x in
             "|_ _ ||,|,|___ | ,_ ||,  _  ||, ___  |,|___  |,  ||,|___ ||, ___ ||"
                     .split(',')].index(1)),n))

```

Ungolfed:

```
def parse(input):
    lines = list(input.split('\n'))
    numbers = [[]]
    for lst in zip(*lines):
        if all(i==" " for i in lst):
            numbers += [[]]
        else:
            numbers[-1] += lst
    return ''.join(map(digit, numbers))

def digit(num):
    fingerprint =
        "|_ _ ||,|,|___ | ,_ ||,  _  ||, ___  |,|___  |,  ||,|___ ||, ___ ||".split(',')
    return str([''.join(num[2:]) == y for y in fingerprint].index(True))

```

Tests:

```
assert (parse("   _   _   _   _   _   _ \n| | | | | | | | | | | | |\n| |_| |_| |_| |_| |_| |_|") == '1000000')
assert (parse("   _       _ \n| |_| |_| |_ \n|  _|   |  _|") == '1945')
assert (parse(" _   _     _ \n _| | | | |_ \n|_  |_| | |_|") == '2016')
assert (parse(" _     _  _       _   _  _   _   _ \n| | |  _| _| |_| |_  |_   | |_| |_|\n|_| | |_  _|   |  _| |_|  | |_|  _|") == '0123456789')
assert (parse("  _  _   _ \n|  |  | |_ \n|  |  | |_|") == '1776')

```

## How it works

(Note: I am explaining the ungolfed program here since it is more readable and it has the exact same code, with the exception that the `digit` function is in-lined into a lambda)

```
def parse(input):
    lines = list(input.split('\n'))
    numbers = [[]]

```

The main function is `parse`. It first splits the input into lines and creates the `numbers` array.

```
    for lst in zip(*lines):
        if all(i==" " for i in lst):
            numbers += [[]]
        else:
            numbers[-1] += lst

```

This is my favorite part (since it took so long to figure out). Here we `zip` the lines so we can basically vertically traverse the input. When the line has chars on it we add it to the last number in the `numbers` array. If it does not have any chars on it we add a new number to the array.

```
    return ''.join(map(digit, numbers))

```

Really simple, `numbers` is mapped with the `digit` function and is converted to a string.

```
def digit(num):
    fingerprint =
        "|_ _ ||,|,|___ | ,_ ||,  _  ||, ___  |,|___  |,  ||,|___ ||, ___ ||".split(',')
    return str([''.join(x[2:]) == y for x, y in zip([num]*10, fingerprint)].index(True))

```

This is (fairly) simple. `fingerprint` is the string representation of the digits created above minus the first 2 chars (this was the smallest fingerprint I could find). We return the index of the first match.

# Answer
> 0 votes
# Haskell, ~~270~~ 207 bytes

Don't be too hard, this is my first ever haskell program ;) I'm almost certain this can be golfed further, but I don't know how given my limited knowledge of the language.

```
import Data.Lists
b n=map c$splitOn["   "]$transpose$lines n
c n|e<-drop 2$concat n,Just r<-elemIndex True[e==f|f<-splitOn",""|_ _ ||,|,|___ | ,_ ||,  _  ||, ___  |,|___  |,  ||,|___ ||, ___ ||"]=(show r)!!0

```

Ungolfed:

```
module Main where
import Data.Lists

main :: IO ()
main = print $ parse " _     _  _       _   _  _   _   _ \n| | |  _| _| |_| |_  |_   | |_| |_|\n|_| | |_  _|   |  _| |_|  | |_|  _|"

parse :: String -> String
parse n = let lst = transpose $ lines n
              numbers = splitOn ["   "] lst --"   " lst
              number = map digit numbers
          in number

digit :: [String] -> Char
digit n | e <- drop 2 $ intercalate "" n
        , fingerprint <- ["|_ _ ||","|","|___ | ","_ ||","  _  ||"," ___  |","|___  |","  ||","|___ ||"," ___ ||"]
        , Just res <- elemIndex True [e == finger | finger <- fingerprint]
        = head $ show res

```

Big thanks to @nimi for the tips!

---
Tags: code-golf, string, parsing
---


title: Convert a "mixed-base" string to ASCII

text:
# Question
Title: Convert a "mixed-base" string to ASCII
Given an input of a string with bytes that may be in either binary, octal, or hex, output the string's ASCII equivalent.

Input will be provided in the following format, for example:

```
501200100001147

```

which represents

```
0x50 0o120 0b01000011 0x47

```

which is equivalent (in ASCII) to

```
PPCG

```

Binary, octal, and hex will always be provided with 8, 3, and 2 digits respectively.

For the purposes of this challenge, only printable ASCII must be supported. This is the range `32..126` inclusive. Therefore, it is impossible for there to be ambiguity. Note that

* A string represents binary if and only if it starts with a `0` and its second character is either a `0` or a `1`. All printable ASCII characters have their high bit off in binary (i.e. start with a `0`), and none of them start with `00` or `01` in either hex or octal.
* With binary out of the way, note that all printable ASCII characters start with `2`-`7` in hex and `0`-`1` in octal. Therefore, it is possible to unambiguously distinguish between hex and octal as well.

You may assume that hex input is provided as either lowercase or uppercase, whichever is more convenient.

Regex makes the parsing portion of the challenge semi-trivial. I don't want to ban the use of regex outright, but if you have a non-regex solution longer than its regex-using counterpart, feel free to post it along with the "real" answer anyway, since I'd be interested to see it as well. :)

Since this is , the shortest code in bytes will win.

Test cases:

```
In                   Out
-----------------------------------
501200100001147    | PPCG
5C01101111100      | \o@
313206306400110101 | 12345
2A200530402C       | * + ,
0011111100111111   | ??
<empty string>     | <empty string>

```

# Answer
# Lex + C, ~~156~~ 124 bytes

```
%{
p(b){putchar(strtol(yytext,0,b));}
%}
%option noyywrap
%%
0[01]{7} {p(2);}
[01].. {p(8);}
.. {p(16);}
%%
main(){yylex();}

```

Compile with:

```
lex mixed_base.l
cc -o mixed_base lex.yy.c

```
> 4 votes

# Answer
## ES6, ~~86~~ 80 bytes

Regex-based solution:

```
s=>s.replace(/0[01]{7}|[01]?../g,n=>String.fromCharCode(0+'bkxo'[n.length&3]+n))

```

Recursive non-regex solution for 95 bytes:

```
f=(s,r='')=>s?f(s.slice(l=s<'02'?8:s<'2'|2),r+String.fromCharCode(0+'bkxo'[l&3]+s.slice(0,l))):r

```
> 3 votes

# Answer
## Python 3, 165 bytes

Without Regex

```
x=input();i=0;s=""
while i<len(x):
 a=x[i:i+2];c=int(a[0])
 if a in["00","01"]:y=8;b=2
 elif 1<c<8:y=2;b=16
 elif c<2:y=3;b=8
 s+=chr(int(x[i:i+y],b));i+=y
print(s)

```
> 0 votes

---
Tags: code-golf, base-conversion
---


title: Convert to ASCII Agrippa Numbers

text:
# Question
Title: Convert to ASCII Agrippa Numbers
# Challenge

Given a natural number, output it in the ASCII form of Agrippa's number system.

# Description

I like odd alphabets and numeral systems. My favorite numeral system is one given by Heinrich Cornelius Agrippa. It gives a succinct way to write numbers in the range `[0,9999]`, where single digits are written as follows:

Larger numbers less than `10^4` are a combination of single digits, but rotated/horizontally-mirrored on a single central bar as follows:

```
[0° mirrored, 10's  ] | [0°,            1's  ]
[180°,        1000's] | [180° mirrored, 100's]

```

Here are a few examples:

The ASCII equivalents are:

```
Ones:
  0  1  2  3  4  5  6  7  8  9
  |  |- |_ |\ |/ |~ || |^ |v |]
  |  |  |  |  |  |  |  |  |  |

Tens:
  0  1  2  3  4  5  6  7  8  9
  | -| _| /| \| ~| || ^| v| [|
  |  |  |  |  |  |  |  |  |  |

Hundreds:
  0  1  2  3  4  5  6  7  8  9
  |  |  |  |  |  |  |  |  |  |
  |  |_ |- |/ |\ |~ || |v |^ |]

Thousands:
  0  1  2  3  4  5  6  7  8  9
  |  |  |  |  |  |  |  |  |  |
  | _| -| \| /| ~| || v| ^| [|

 1510:  1511:  1471:  1486:  3421:
 -|     -|-    ^|-    v||    _|-
 _|~    _|~    _|\    -|\    \|\

```

Numbers larger than `9999` are broken up into sections of 4 digits (with leading zeros added to get a multiple of four) and each is converted. For example:

```
314159: (0031 4159)
         /|-  ~|]
          |   /|_

```

# Rules

* Your answer may be a function or full program
* The input is a positive integer
* Entries must support inputs over `10^8`
* Each four digit section takes exactly six characters
* Sections of four are separated by a single space
* Trailing newline is optional
* Up to two trailing spaces per line are allowed
* I will not accept my own answer
* Score is in bytes, lowest score wins!

# Answer
# Haskell, 310 bytes

* Defining `reverse` (as I did: `r`) is one byte shorter than importing `Data.List` and using it just *once*
* Defining `z=0:z` and `(!)=(!!).(++z)` is the shortest way yet that I've found to return `0` for out of bounds
* I've checked and quickChecked the `take4s` function, but it still feels like magic to me

# Here's the code:

```
l=lines"    \n--__\n__--\n\\//\\\n/\\\\/\n~~~~\n||||\n^^vv\nvv^^\n][]["
d x|x<1=[]|1<2=mod x 10:d(div x 10)
(&)=(!!)
z=(0::Int):z
(!)=(&).(++z)
t a=[[a!q|q<-[p..p+3]]|p<-[0,4..length a-1]]
g[c,d,b,a]=[[l&b&1,'|',l&a&0,' '],[l&d&3,'|',l&c&2,' ']]
r[]=[]
r(x:y)=r y++[x]
f=unlines.foldl1(zipWith(++)).map g.r.t.d

```

# Less golfed:

```
import Data.List (reverse)

dict = lines "    \n--__\n__--\n\\//\\\n/\\\\/\n~~~~\n||||\n^^vv\nvv^^\n][]["

-- Note that (digits x) returns the digits of x in little-endian order
digits x  | x < 1     = []
          | otherwise = mod x 10 : digits (div x 10)

-- Note: zeros needs the type signature, because otherwise it won't match [Int] (inferred from (!!))
zeros = (0::Int) : zeros

-- list ! position gives the element at the position, or 0 for out of bounds
(!) = (!!) . (++zeros)

-- This partitions the digits into groups of four, padded right
take4s a = [[a!q | q <-[p..p+3]] | p <- [0,4..length a - 1]]

convertOne[c,d,b,a] = [[dict !! b !! 1, '|', dict !! a !! 0, ' '], [dict !! d !! 3, '|', dict !! c !! 2, ' ']]

f = unlines . foldl1(zipWith (++)) . map convertOne . reverse . take4s . digits

```

# Tests (escape characters removed):

```
mapM_ print $ lines $ f 1510
-|
_|~

mapM_ print $ lines $ f 1511
-|-
_|~

mapM_ print $ lines $ f 1471
^|-
_|\

mapM_ print $ lines $ f 1486
v||
_|\

mapM_ print $ lines $ f 3421
_|-
\|\

mapM_ print $ lines $ f 1234567891011121314
_|\ ||^ -|  -|_ -|/
 |_ /|~ ^|] _|_ _|/

mapM_ print $ lines $ f 1024628340621757567
 |_ _|v  || ^|~ ||^
 |_ /|| \|\ -|_ v|~

```
> 3 votes

# Answer
## JavaScript (ES6), ~~180~~ 159 bytes

```
s=>`000${s}`.slice(-s.length&-4).replace(/..../g,([t,h,d,u])=>(r+=' _-\\/~|v^['[t]+`|${'_-/\\~|v^]'[h]} `,' -_/\\~|^v['[d]+`|${' -_\\/~|^v]'[u]} `),r='')+`\n`+r

```

Where `\n` represents a literal newline character.

Edit: Updated for the switch from `,'` to `|`. Saved 14 bytes by using a single `replace` to do all the work. Saved 3 bytes by using `&-4` instead of `<<2>>2`. Saved 2 bytes by abusing destructuring assignment. Saved 2 bytes by abusing template strings.
> 3 votes

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


title: Output the given English pronoun table

text:
# Question
Title: Output the given English pronoun table
Output the provided table of English pronouns exactly, in as few bytes as possible.

### Code rules

* The code will take no input
* The table is tab-delimited
* Each line begins with a single tab `\t` if there is no row heading
* Each line ends in a single newline `\n` (not `\r\n`), including the last line
* There are four tabs between "Plural" and the newline (`Plural\t\t\t\t\n`) because it refers to the next four columns as well, but no other line has trailing tabs or spaces

### Spelling rules

* There is no Possessive Pronoun for "it", so the data is "-"
* The only pronoun to use an apostrophe is "one's". "It's" means "it is" or "is has" and is a contraction, not a pronoun
* Some people use "themself" for the singular, gender non-specific, third person, but in this table it is "themselves"
* This table is not complete; other non-standard, alternate and rare forms are not included

### Output

Use this link to check your output.

### Pretty-printed (do not output this!)

```
                Singular                                                  Plural
                                   Possessive   Possessive                                   Possessive   Possessive
                Subject   Object   Determiner   Pronoun      Reflexive    Subject   Object   Determiner   Pronoun      Reflexive
First Person    I         me       my           mine         myself       we        us       our          ours         ourselves
Second Person   you       you      your         yours        yourself     you       you      your         yours        yourselves
Third Person    he        him      his          his          himself      they      them     their        theirs       themselves
                she       her      her          hers         herself
                it        it       its          -            itself
                one       one      one's        one's        oneself
                they      them     their        theirs       themselves

```

# Answer
## Bubblegum, 191 bytes

Hexdump (reversible with `xxd -r`), as source code contains unprintables:

```
00000000: a58f 3d0e c230 0c85 67e7 146c 4cdc 0221  ..=..0..g..lL..!
00000010: 3151 512e 508a 4b83 f223 d949 a1b7 274e  1QQ.P.K..#.I..'N
00000020: 5260 410c 4479 9fa3 67f9 4586 56bb 6b34  R`A.Dy..g.E.V.k4
00000030: 1d81 9cc6 44ea 8cbc 14b4 f17c c33e c0a1  ....D......|.>..
00000040: 94c6 3323 b39e 70b5 c580 64b5 43fa 741b  ..3#..p...d.C.t.
00000050: f2ce 4707 471c 0c3e 92f3 7f82 da69 e2b0  ..G.G..>.....i..
00000060: 6a90 d83b d883 45b0 33c8 5caa 8c66 803b  j..;..E.3.\..f.;
00000070: 4264 f091 44f9 91ec 0959 b5d8 7b77 5946  Bd..D....Y..{wYF
00000080: 671f 1751 0617 4ac4 f79e e49c 464d af98  g..Q..J.....FM..
00000090: 1161 d436 89ab 6c4e 0823 ce02 2bd0 54c8  .a.6..lN.#..+.T.
000000a0: d9a9 29c0 329a b6ad e28c 34ab 4087 7219  ..).2.....4.@.r.
000000b0: 36c2 ecf9 b460 d59a df2c cddf bf3d 01    6....`...,...=.

```

Look, *someone* had to do it...
> 4 votes

---
Tags: code-golf, kolmogorov-complexity
---


title: A Free Sample of Autocorrelation

text:
# Question
Title: A Free Sample of Autocorrelation
Consider a 1-dimensional, real-valued vector *x* that represents observations of some process measured at equally spaced intervals over time. We call *x* a **time series**.

Let *n* denote the length of *x* and  denote the arithmetic mean of *x*. The **sample autocovariance function** is defined as

for all -*n* \< *h* \< *n*. This measures the linear dependence between two points on the same series observed at different times.

The **sample autocorrelation function**, or ACF, is defined as

This measures the linear predictability of the series *x* at time *t*, which we denote *x**t*, using only the value *x**t+h*.

Note that these sample estimates do not match the naïve calculations based on the theoretical properties. That is, the sample autocorrelation function is *not* equal to the Pearson correlation coefficient of *x* with the *h*-step lag of *x*.

## Task

Given an array *x* and a nonnegative integer *h*, print or return the first *h*+1 **lag** autocorrelations of *x*, beginning with lag 0. The lag autocorrelations are those corresponding to negative inputs in the above formulas.

You can assume that 0 \< *h* \< *n*, where *n* is the length of *x*, and that 2 \< *n* \< 256.

Output should be correct to within 1E-4. There are no restrictions on the use of built-in functions or running time.

## Examples

```
h, x -> output
--------------
5, [2.4, 2.4, 2.4, 2.2, 2.1, 1.5, 2.3, 2.3, 2.5, 2] -> [1.00000000,  0.07659298, -0.06007802, -0.51144343, -0.02912874, -0.10468140]
1, [2134, 1863, 1877, 1877, 1492, 1249] -> [1.0000000, 0.3343041]
2, [13067.3, 13130.5, 13198.4] -> [1.0000000000, -0.0002854906, -0.4997145094]

```

# Answer
# Jelly, ~~26~~ ~~25~~ ~~24~~ ~~23~~ 20 bytes

```
×L_SµḊ;0µƓÐ¡×¹S€µF÷Ḣ

```

Try it online!

### How it works

```
×L_SµḊ;0µƓÐ¡×¹S€µF÷Ḣ  Main link. Input: x (list) STDIN: h (integer)

×L                    Multiply all items in x by the length of x.
  _S                  Subtract the sum of x from all products.
                      Let's call the result X.
    µ                 Begin a new monadic chain. Argument: t (list)
     Ḋ                Remove the first element of t.
      ;0              Append a 0 to the result.
        µ             Push the previous chain and begin a new one.
                      Argument: X
         Ɠ            Read h from STDIN.
          Ð¡          Repeat the Ḋ;0 chain h times, collecting the h+1 intermediate
                      results in a list A.
            ×¹        Multiply the vectors in A by X.
              S€      Compute the sum of each vectorized product.
                µ     Begin a new, monadic chain. Argument: S (sums)
                 F    Flatten S. This does nothing except creating a deep copy.
                   Ḣ  Pop the first element of S.
                  ÷   Divide all elements of the copy by the first element.

```
> 4 votes

# Answer
# R, ~~3~~ ~~31~~ 25 bytes

```
# changes the builtin to only return the acf
body(acf)=body(acf)[1:18]

```

Usage (returns an array with the autocorrelations)

```
(acf(c(2.4, 2.4, 2.4, 2.2, 2.1, 1.5, 2.3, 2.3, 2.5, 2),5))
# , , 1
#
#             [,1]
# [1,]  1.00000000
# [2,]  0.07659298
# [3,] -0.06007802
# [4,] -0.51144343
# [5,] -0.02912874
# [6,] -0.10468140

```

Background:

The 31 byte solution based on the original `acf` built in

```
function(n,h)c(acf(n,h,,F)$acf)

```

Note that the 3 byte option `acf` is the originalbuilt in that will plot (and print to 3 digits) while returning the required autocorrelation as an element in a list.

usage

```
 acf(c(2.4, 2.4, 2.4, 2.2, 2.1, 1.5, 2.3, 2.3, 2.5, 2),5)

```

output:

```
#    Autocorrelations of series ‘c(2.4, 2.4, 2.4, 2.2, 2.1, 1.5, 2.3, 2.3, 2.5, 2)’, by lag
#
#     0      1      2      3      4      5
# 1.000  0.077 -0.060 -0.511 -0.029 -0.105

```

If we want the correlations to display to more than 3 decimal places then 28 bytes will do it (or 31, if we want to suppress the plot)

```
# will still plot (28 bytes)
function(n,h)c(acf(n,h)$acf)
# won't plot (31 bytes)
function(n,h)c(acf(n,h,,F)$acf)

```
> 7 votes

# Answer
# Python 3, ~~147~~ ~~130~~ ~~126~~ 120 bytes

```
def p(h,x):x=[t-sum(x)/len(x)for t in x];return[sum(s*t for s,t in zip(x[n:],x))/sum(b*b for b in x)for n in range(h+1)]

```

This solution is probably going to be golfed further, It's just a start.

You can call it with:

```
p(5,[2.4, 2.4, 2.4, 2.2, 2.1, 1.5, 2.3, 2.3, 2.5, 2])

```
> 3 votes

# Answer
# Octave, ~~47~~ 37 bytes

```
@(h,x)xcov(x,'coeff')(numel(x)+(0:h))

```
> 2 votes

# Answer
# MATL, 20 bytes

```
tYm-tPX+tX>/GnqiQ:+)

```

*EDIT (May 20, 2016): as of version 18.0.0 of the language, use `Y+` instead of `X+`. The link includes this change.*

**Try it online!**

Correlation is closely related to convolution. We normalize by subtracting mean, then convolve, normalize again by dividing by maximum value, and then pick the desired lags.

```
tYm-       % implicit input. Duplicate and subtract mean
tPX+       % duplicate, flip, convolve
tX>/       % duplicate, divide by maximum value
Gnq        % length of array, n. Subtract 1
iQ:        % input number h. Generate vector [1,2,...,h+1]
+          % add to obtain vector [n,n+1,...,n+h]
)          % use that vector as an index. Implicitly display

```
> 2 votes

# Answer
# Mathematica, 27 bytes

*Thanks to LegionMammal978 for saving 1 byte.*

We could beat Jelly if function names were not so long.

```
#2~CorrelationFunction~{#}&

```

---

**Test case**

```
%[5,{2.4,2.4,2.4,2.2,2.1,1.5,2.3,2.3,2.5,2}]
(* {1.,0.076593,-0.060078,-0.511443,-0.0291287,-0.104681} *)

```
> 1 votes

---
Tags: code-golf, math, statistics
---


title: Octal, Decimal, or Hexadecimal?

text:
# Question
Title: Octal, Decimal, or Hexadecimal?
Given an input string containing only letters and numbers, write a program or function that prints the possible printable ASCII characters (Hex 20-7E) that correspond with the string's value in bases 8, 10, and 16 (where possible). The characters must be written in increasing order in terms of the bases with which they correspond (base 8 first, etc). The output can be in array format (like `[& . F]`) or separated by spaces or newlines (a trailing newline is optional) like the samples.

If there is not a possible printable ASCII character that can be formed, the program must not have any output.

**Samples**

```
31
==> 1

47
==> ' / G

69
==> E i

7A
==> z

100
==> @ d

156
==> n

189
==> <empty>

potaTO
==> <empty>

5G
==> <empty>

19
==> <empty>

```

---

This is , so the answer with the fewest bytes wins. Standard rules apply.

# Answer
> 6 votes
## JavaScript (SpiderMonkey 30+), 74 bytes

```
s=>[for(b of'o0x')if((c=+(0+b+s))>31&c<127)String.fromCharCode(c)].join` `

```

# Answer
> 4 votes
# MATL, 23 ~~24~~ ~~28~~ bytes

*1 byte off thanks to @David*

```
8H6hhYs"G@ZA32:126m?6Mc

```

**Try it online!**

```
8H6hhYs         % array [8,10,16]
"               % for each base
  G             %   push input. Do nothing the first time
  @             %   push base (8, 10 or 16)
  ZA            %   convert from base to decimal. Takes implicit input the first time
  32:126m       %   is result in acceptable range?
  ?             %   if so
    6M          %     push result of base conversion again
    c           %     convert to char
                %   implicitly end if
                % implicitly end for each
                % implicitly display stack contents

```

# Answer
> 4 votes
# Python 3, ~~84~~ 82 bytes

```
def a(s):
 for n in 8,10,16:
  try:b=int(s,n);31<b<127and print(chr(b))
  except:0

```

# Answer
> 3 votes
## Pyth, ~~23~~ ~~21~~ ~~20~~ 18 bytes

```
@rd\m.xCizd0[8T16

```

Output as an array. There's a literal `\x80` between the backslash and the C, which I've replaced with a .

```
@rd\•m.xCizd0[8T16    Implicit: z=input
     m     d [8T16    Map the following lambda d over [8, 10, 16]:
      .x                try:
         izd              convert z from that base
        C                                          and convert to char
            0           except: return the number 0
@                     Filter that on presence in
 rd\•                   strings from space to \x80 (the printable ASCII characters).

```

Try it here.

# Answer
> 2 votes
# Jolf, 26 bytes

Try it here! Test suite

```
 fΜ‘Ci8iΗi’dpAHdh sH"[ -~]

```

# Explanation

```
 fΜ‘Ci8iΗi’dpAHdh sH"[ -~]
   ‘      ’                array containing
    Ci8                     input as base 8
       i                    input as base 10
        Ηi                  input as base 16
  Μ        d               mapped
            pAH             with from char code
_f             d           filtered
                _sH"[ -~]   with strings matching that.

```

# Answer
> 1 votes
# Bash + GNU utilities + ascii, 36

Not sure if the use of the `ascii` utility is allowed. Input is taken as a commandline parameter.

```
ascii $1|tac|grep -Po '(?<=s as `).'

```

`ascii` may be installed on Ubuntu with `sudo apt-get install ascii`.

# Answer
> 1 votes
# C (function), 76

* 2 bytes saved thanks to @anatolyg.
* 5 bytes saved thanks to @luserdroog.

```
j,c;f(char*s){for(j=8;c=strtol(s,0,j);j=j*j/6)isprint(c)?printf("%c ",c):0;}

```

Ideone.

# Answer
> 1 votes
# Javascript ES6, 89 chars

```
s=>'0o,,0x'.split`,`.map(x=>(x+=s)>31&x<128&&String.fromCharCode(x)).filter(x=>x).join` `

```

Test:

```
f=s=>'0o,,0x'.split`,`.map(x=>(x+=s)>31&x<128&&String.fromCharCode(x)).filter(x=>x).join` `
"31,47,69,7A,100,156,189,potaTo,5G,19".split`,`.map(f) == "1,' / G,E i,z,@ d,n,,,,"

```

# Answer
> 1 votes
## Lua, 147 Bytes

I don't think I can golf it down a lot more, I've tested a lot of ways to do it, and here come the shortest. Even using an old compiler which contains the deprecated function `table.foreach(table,function)` doesn't shave off some bytes.

This program takes a string as argument, and print the concatenation of a table values separated by spaces.

```
t={}for _,i in pairs({8,10,16})do x=tonumber(arg[1],i)x=x and x or 0 t[#t+1]=127>x and 19<x and string.char(x)or nil end print(table.concat(t," "))

```

### Ungolfed and explanations

```
t={}                        -- Initalise the array containing the chars to print
for _,i in pairs({8,10,16}) -- Iterate over the array {8,10,16}
do
  x=tonumber(arg[1],i)      -- convert the input in base i to a number in base 10
  x=x and x or 0            -- if the input wasn't a number, x is nil
                            -- use a ternary operator to set x in this case
  t[#t+1]=127>x and 19<x    -- if x is the bytecode of a printable character
    and string.char(x)or nil-- insert this character into t
end
print(table.concat(t," "))  -- concatenate the values in t with " " as separator
                            -- and print it

```

If you're wandering why there's a variable set but not used in a golfed code (the variable `_` in the for loop), here's why:

You have 2 ways to iterate over an array in Lua, either in a for style:

```
for i=1,#table do --[[code here, use table[i] ]] end

```

or in a foreach style:

```
for key,value do pairs(table) do --[[code here]] end

```

I was needing the values contained in the table `{8,10,16}` as they are the different bases I have to iterate over. But functions with multiple return won't allow you to chose which one you actually want to be returned, they follow an order. To have the variable `value` set, I need to catch the value of `key` too: that's what we call a dummy `_`.

# Answer
> 0 votes
# JavaScript ES6, ~~89~~ 88 bytes

Saved 1 byte thanks to Neil!

```
n=>[..."0x+"].map(t=>String.fromCharCode(eval(`0${t+n}`))).filter(k=>~k.search(/[ -~]/))

```

Returns an array. If that's not okay, this works for an extra 8 bytes, displaying the possible matches.

```
n=>[..."0x+"].map(t=>String.fromCharCode(eval(`0${t+n}`))).filter(k=>~k.search(/[ -~]/)).join` `

```

```
F=n=>[..."0x+"].map(t=>String.fromCharCode(eval(`0${t+n}`))).filter(k=>~k.search(/[ -~]/)).join` `
//`
U=x=>o.innerHTML=F(+i.value);
i.onchange=i.onkeydown=i.onkeyup=i.onkeypress=U;U();
```

```
*{font-family:Consolas,monospace;}
```

```
<input id=i type="number" value=31><div id=o></div>
```

# Answer
> 0 votes
# R, 84 bytes

```
function(x){s=sapply;y=s(c(8,10,16),strtoi,x=x);cat(s(y[y%in%c(32:126)],intToUtf8))}

```

uses `strtoi` to convert to each of the bases and then convert to character if in the appropriate range. Could save 4 more bytes by removing `cat` if we allowed the default printing of characters (wrapped in `""`)

---
Tags: code-golf, base-conversion
---


title: What character is that HTML entity?

text:
# Question
Title: What character is that HTML entity?
The goal is really simple. Receiving a string as input, parse all the HTML entities that correspond to the following characters (including their uppercase variants):

```
áàãâäéèêëíìîïóòõôöúùûüýÿ

```

Parsing rules:

* Each entity starts with `&` and ends with `;`
* The first character after the `&` will be the modified character (letter case is important!)
* The remaining characters refer to the name of the accent to use (`acute`, `grave`, `circ`, `tilde` and `uml`). The accent name **MUST** be in lowercase! *
* Any HTML entity that produces a character that isn't on that list, or that is invalid, should be left untouched (E.g.: `&`, `&etilde;`, `&a;`)
* Numeric entities should be ignored, since they don't fit in the rules above

This change was introduced as of 18-02-2016. All the existing answers that accept HTML entities with uppercase accent names are valid. Any future answer must follow this rule.

**Examples:**

```
á //á
Téhèh //Téhèh
an & //an &

```

**Output:**

The output can be in ISO-8859-*X* (1-15), windows-1252 or UTF-8/16/32.
You can pick **one and only one** of the valid encodings and use it for **any** output. You can safely assume that the input will be in ASCII.

Any of the following is a valid output for `á`:

* `á` (ISO-8859-1/15 or windows-1252, equivalent to `\xE1`)
* `Ã¡` (UTF-8, equivalent to `\xC3\xA1` or `\u00E1`)
* (UTF-8, equivalent to `a\xCC\x81` or `a\u0301`)
* Any combination of diacritics, without using HTML entities.

The output has to be visually similar, when rendered/displayed, to the characters on the list.

---

Remember, all the standard loopholes *and built-ins* * are **disallowed**. Since this is , the shortest answer wins.

* This change was made due to the great disapproval of bonuses and penalities, and at the time of writting, doesn't invalidate any answer

# Answer
> 4 votes
# Japt, ~~81~~ 75 bytes

```
Ur`&([%vYy](ac©e|uml)|%v(g?ve|circ)|[AaOo]Èìe);`@Yg +'Ì+"?????"g"gutca"bYgJ

```

The six `?`s represent unprintable chars. Test it online!

Note: This outputs the third encoding option; that is, the letter followed by the raw UTF-8 encoding of the corresponding combining diacritical mark.

### How it works

```
Ur"&(    );"       // Replace each ampersand and semicolon that have one of these between them:
([%vYy](acute|uml) //  A vowel or Yy followed by "acute" or "uml",
|%v(grave|circ)    //  or a vowel followed by "grave" or "circ",
|[AaOo]tilde       //  or "a" or "o" followed by "tilde";
@                  // replace each match X and its middle Y with this function:
""g"gutca"bYgJ     //  Take the unprintable at index (index of the second char in Y in "gutca") in this string.
Yg +'Ì+            //  Concatenate the first char in Y and "Ì" to the beginning.
                   // Implicit output

```

Hexdump of the code:

```
00000000: 55 72 60 26 28 5b 25 76 59 79 5d 28 61 63 a9 65  Ur`&([%vYy](ac©e
00000010: 7c 75 6d 6c 29 7c 25 76 28 67 9f 76 65 7c 63 69  |uml)|%v(g.ve|ci
00000020: 72 63 29 7c 5b 41 61 4f 6f 5d c8 ec 65 29 3b 60  rc)|[AaOo]Èìe);`
00000030: 40 59 67 20 2b 27 cc 2b 22 80 81 82 83 88 22 67  @Yg +'Ì+"....."g
00000040: 22 67 75 74 63 61 22 62 59 67 4a                 "gutca"bYgJ

```

# Answer
> 12 votes
# JavaScript (ES6), ~~141~~ ~~122~~ 134 bytes

```
a=>a.replace(/&([aeiouyAEIOUY](acute|uml)|[aeiouAEIOU](grave|circ)|[aoAO]tilde);/g,b=>b[1]+{g:"̀",a:"́",c:"̂",t:"̃",u:"̈"}[b[2]])

```

Followed daavko's example using diacritical marks, and I feel like an idiot for not thinking of using it sooner. Actually gets surprisingly short for JavaScript.

EDIT: Neil caught some bad cases of undefined, which are now fixed.

# Answer
> 10 votes
# Retina, 115 bytes

I'm new to code-golf, but I think this might work.
This version was made before the rule, which doesn't allow replacing uppercase html entities (for example `&AACUTE;`) was introduced.

```
i`&([aeiouy])acute;
$1́
i`&([aeiou])grave;
$1̀
i`&([ao])tilde;
$1̃
i`&([aeiou])circ;
$1̂
i`&([aeiouy])uml;
$1̈

```

Quite simple search and replace. Uses UTF-8.

Uses \[letter\]\xCC\x\[diacritical mark hex code\] approach. Diacritical mark is added after every relevant letter.

For some reason, the default Droid Sans Mono font in the interpreter can't render the "circ" and "uml" letters properly. If you change it through developer tools to something like DejaVu Sans, it shows just fine. I think this is a limitation of the font, not the program. But if it's program's fault, I'll try to fix it.

Here is a 129 byte version, which doesn't replace uppercase HTML entites (for example `&AACUTE;`)

```
&([aeiouyAEIOUY])acute;
$1́
&([aeiouAEIOU])grave;
$1̀
&([aoAO])tilde;
$1̃
&([aeiouAEIOU])circ;
$1̂
&([aeiouyAEIOUY])uml;
$1̈

```

Try it online!
Try it online! 129-byte version

# Answer
> 3 votes
# JavaScript (ES6), 288 bytes

```
a=>(z=(b,c=1,d=2,e=3,f=0,g=4)=>({b:b+191,grave:c,acute:d,circ:e,tilde:f,uml:g}),y={a:z(0,1,2,3,4,5),e:z(8),i:z(12),o:z(18,1,2,3,4,5),u:z(25),y:z(28,0,2,0)},a.replace(/&\w+;/gi,b=>(x=y[b[1].toLowerCase()])&&(w=x[b.slice(2,-1)])?String.fromCharCode(x.b+w+32*(b[1]>'_')+153*/Yu/.test(b)):b))

```

Creates a character map object (with the base numeric code for each character), and uses offsets (or 0 if non-existent) to determine if an entity should be converted and what it's character code is. Symmetry in the cases means adding 32 if lowercase, except for `Ÿ`, where it uses a different offset for UTF8.

---
Tags: code-golf, parsing
---


title: Output MSB-set aligned, delimited ASCII

text:
# Question
Title: Output MSB-set aligned, delimited ASCII
Write some code that takes a single string as input and outputs MSB-set aligned ASCII.

Only ASCII characters less than 128 (0x80) will be in the input. The output format is generated as follows:

* For each character convert it to its binary representation, remove the MSB (always `0` in the input) and then add a delimiter-bit (`X`) to both ends. The value will now be 9 bits long and both begin and end in `X`
* Output each character in order, MSB to LSB, making sure that the MSB of each output byte is either `1` or `X`
* If the MSB of the next byte would normally be `0`, output the fewest `.`s needed between two consecutive `X`s to align the MSB with a `1` or `X`
* Output the data as binary digits, with `X` for each delimiter and `.` for each padding bit
* At the end of the data, write a `.` after the last `X`, then as many `.`s as necessary to complete the last byte
* Separate each byte (group of 8 digits) with a single whitespace character (space, tab, newline, etc.)
* A whitespace character at the end of the last output line is optional
* Empty input must produce `........` as the output
* Your code must work on any length strings that your language can handle and at least 255 characters

Input: `Hello, World!`

```
Bytes    -> Delimited -> * Output    Start and End of each character
01001000    X1001000X    X1001000    'H'
01100101    X1100101X    XX110010    'e'       'H'
01101100    X1101100X    1X.X1101    'l'       'e'
01101100    X1101100X    100XX110    'l'       'l'
01101111    X1101111X    1100X.X1    'o'       'l'
00101100    X0101100X    101111X.              'o'
00100000    X0100000X    X0101100    ','
01010111    X1010111X    X.....X0    ' '       ','
01101111    X1101111X    100000XX    'W'       ' '
01110010    X1110010X    1010111X              'W'
01101100    X1101100X    X1101111    'o'
01100100    X1100100X    X.X11100    'r'       'o'
00100001    X0100001X    10XX1101    'l'       'r'
                         100X..X1    'd'       'l'
                         100100X.              'd'
                         X0100001    '!'
                         X.......              '!'

```

The `*` marks the Most Significant Bit in the output. Each bit in this column is either `1` or `X`. Removing any number of `.`s would cause either a `0` or `.` in the MSB column. If the input was `Hello, W` the last byte output would be `........`.

As usual, lowest score wins!

# Answer
> 1 votes
# Python 3, ~~144~~ ~~140~~ ~~131~~ ~~130~~ 137 bytes

*Damn bugs :(*

```
O=""
for Q in input():
 C="X%07dX"%int(bin(ord(Q))[2:])
 while"1">C[8-len(O)%8]:C="."+C
 O+=C
O+="."
while O:print((O+"."*8)[:8]);O=O[8:]

```

This is really straight forward.

### Ungolfed with explanation

```
# initialize output buffer
output = ""
# loop through input
for char in input():
    # get charcode, binary, remove 0b, parse as int, format
    code = "X%07dX" % int(bin(ord(char))[2:])
    # pad code while the line starting character would be 0
    while "1" > code[8 - len(output) % 8]:
        code = "." + code
    # append result to output buffer
    output += code
# add dot to ensure padding in end
output += "."
# loop while any output is left
while output:
    # print line of output, with padding
    print((output + "." * 8)[:8])
    # remove printed output
    output = output[8:]

```

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

```
f=(s,t=[...s].map(c=>(c.charCodeAt()*2+257).toString(2).replace(/^1|1$/g,'X')).join``)=>t.match(r=/^(.{8})*?0/)?f(s,t.replace(r,s=>s.replace(/X[01]*?$/,".$&"))):t+'.'.repeat(8-t.length%8)

```

Works by recursively finding `0`s at illegal positions and inserting a `.` before the preceding `X`. Ungolfed:

```
function f(s) {
    t = '';
    for (i = 0; i < s.length; i++) {
        c = s.charCodeAt(i);
        c = c.toString(2);
        c = '000000' + c;
        c = 'X' + c.slice(-7) + 'X';
        t += c;
    }
    while (m = t.match(/^(.{8})*?0/)) {
        p = t.lastIndexOf('X', m[0].length);
        t = t.slice(0, p) + '.' + t.slice(p);
        // if one dot isn't enough, next loop will just add another
    }
    return t + '.'.repeat(8 - t.length % 8); // pad up to 8 characters
}

```

---
Tags: code-golf
---


title: Random passwords vs Common passwords

text:
# Question
Title: Random passwords vs Common passwords
On Github, there is a list of the 10,000 most common passwords. I've also generated my own list of random passwords.

Your job is to identify the difference between the two lists (with 100% accuracy).

Therefore, your program needs to accept a string, and return:

1. A truthy value if the password is on the common passwords list
2. A falsy value if the password is on the random passwords list
3. Anything you'd like if the password isn't on either

For those that are interested, my program generates passwords between 5-10 characters in length, and each character is either a lowercase letter or a digit.

Note: You should not use these passwords in anything secure. My generation algorithm is not secure at all, and the results are posted online for all to see

# Answer
> 6 votes
# CJam, ~~2262~~ ~~908~~ ~~620~~ ~~512~~ 503 bytes

```
0000000: 6c3a4c412c73277b2c39373e2b3a422d2c4c4c65752e3d65  l:LA,s'{,97>+:B-,LLeu.=e
0000018: 602c33653c5f333d5c5b513222011523a1d079937afebb7b  `,3e<_3=\[Q2"..#..y.z..{
0000030: 31a4ddf41a5e5038ef2aced9debeac5dc01fc4d27d809e0a  1....^P8.*.....]....}...
0000048: 2631e25b9e7d3314f1438f227b3235366233366242663d2f  &1.[.}3..C."{256b36bBf=/
0000060: 2b7d3a447e332205a4f76b4584be674d02001a36a250f949  +}:D~3"...kE..gM...6.P.I
0000078: 7bd0f1966deff2baab26a259813a0caa266155328064f0ee  {...m....&.Y.:..&aU2.d..
0000090: 20245dfab515c8faf39b08e80880c6e06c51728c57c153ec   $].............lQr.W.S.
00000a8: 9907a8365894bb8163bacd3a67173b50641c928f3ca87e89  ...6X...c..:g.;Pd...<.~.
00000c0: 81c1e95e5f049b61688fc7316e6a639876d00cdf4c01a100  ...^_..ah..1njc.v...L...
00000d8: 998bd12ccf3fb8ca61c89f5a57cedf8170b4b062653d947e  ...,.?..a..ZW...p..be=.~
00000f0: 9f6d5ba729db151b79151ae044cd6416274c73110e777172  .m[.)...y...D.d.'Ls..wqr
0000108: 22445132220133e9dcda9e224435224dc7621a0ae9224433  "DQ2".3...."D5"M.b..."D3
0000120: 220980cb1f885db429b742f47062cc1190767d82e6e956b7  ".....].).B.pb...v}...V.
0000138: 1de25dd9c2be7bf5224451322201c9167dd15a8c8cdd110f  ..]...{."DQ2"...}.Z.....
0000150: e956678cd6467ed95c22d7700c1d37a5b1ad94d3b3a3531e  .Vg..F~.\".p..7.......S.
0000168: 639ba99f27cde7e9c81c686adb874d6d5ac411d8d5e44363  c...'.....hj..MmZ.....Cc
0000180: deff8759ed48c97a32b5eeed5ef23be112773a0e0454e6a5  ...Y.H.z2...^.;..w:..T..
0000198: d064d43adf998c7050910c723616dccb5874a8b3640e39e0  .d.:...pP..r6...Xt..d.9.
00001b0: b7545841c7b3152d13ab3e83857530313cb737c799837a4b  .TXA...-..>..u01<.7...zK
00001c8: 396a39e68c9722443322d87648012832adde4e33e27615e2  9j9..."D3".vH.(2..N3.v..
00001e0: 4b6bf7e94bec9022445d3d7b4c5c23297d253a2b215e7c    Kk..K.."D]={L\#)}%:+!^|

```

This prints a positive integer for common passwords and zero for others.

### Verification

```
$ xxd -c 24 -g 24 testall.cjam
0000000: 714e257b3a4c412c73277b2c39373e2b3a422d2c4c4c6575  qN%{:LA,s'{,97>+:B-,LLeu
0000018: 2e3d65602c33653c5f333d5c5b513222011523a1d079937a  .=e`,3e<_3=\[Q2"..#..y.z
0000030: febb7b31a4ddf41a5e5038ef2aced9debeac5dc01fc4d27d  ..{1....^P8.*.....]....}
0000048: 809e0a2631e25b9e7d3314f1438f227b3235366233366242  ...&1.[.}3..C."{256b36bB
0000060: 663d2f2b7d3a447e332205a4f76b4584be674d02001a36a2  f=/+}:D~3"...kE..gM...6.
0000078: 50f9497bd0f1966deff2baab26a259813a0caa2661553280  P.I{...m....&.Y.:..&aU2.
0000090: 64f0ee20245dfab515c8faf39b08e80880c6e06c51728c57  d.. $].............lQr.W
00000a8: c153ec9907a8365894bb8163bacd3a67173b50641c928f3c  .S....6X...c..:g.;Pd...<
00000c0: a87e8981c1e95e5f049b61688fc7316e6a639876d00cdf4c  .~....^_..ah..1njc.v...L
00000d8: 01a100998bd12ccf3fb8ca61c89f5a57cedf8170b4b06265  ......,.?..a..ZW...p..be
00000f0: 3d947e9f6d5ba729db151b79151ae044cd6416274c73110e  =.~.m[.)...y...D.d.'Ls..
0000108: 77717222445132220133e9dcda9e224435224dc7621a0ae9  wqr"DQ2".3...."D5"M.b...
0000120: 224433220980cb1f885db429b742f47062cc1190767d82e6  "D3".....].).B.pb...v}..
0000138: e956b71de25dd9c2be7bf5224451322201c9167dd15a8c8c  .V...]...{."DQ2"...}.Z..
0000150: dd110fe956678cd6467ed95c22d7700c1d37a5b1ad94d3b3  ....Vg..F~.\".p..7......
0000168: a3531e639ba99f27cde7e9c81c686adb874d6d5ac411d8d5  .S.c...'.....hj..MmZ....
0000180: e44363deff8759ed48c97a32b5eeed5ef23be112773a0e04  .Cc...Y.H.z2...^.;..w:..
0000198: 54e6a5d064d43adf998c7050910c723616dccb5874a8b364  T...d.:...pP..r6...Xt..d
00001b0: 0e39e0b7545841c7b3152d13ab3e83857530313cb737c799  .9..TXA...-..>..u01<.7..
00001c8: 837a4b396a39e68c9722443322d87648012832adde4e33e2  .zK9j9..."D3".vH.(2..N3.
00001e0: 7615e24b6bf7e94bec9022445d3d7b4c5c23297d253a2b21  v..Kk..K.."D]={L\#)}%:+!
00001f8: 5e7c7d2524656070                                  ^|}%$e`p
$ echo $LANG
en_US
$ cjam testall.cjam < 10k-common-passwords.txt
[[9989 1] [4 2] [2 3] [3 5] [2 7]]
$ cjam testall.cjam < generated_passwords.txt
[[1000 0]]

```

# Answer
> 3 votes
## Python, ~~719~~ 664 bytes

```
import re
lambda s:re.search(r"(?!.*([xvonkj]0|p[9q5]|i2|q[4rt]|xk|m8|jp|jg|4k|2n|0b|y.[xj7]|mnw|c.3|7.2|4wu|061|zt[ub]|r6[d8]|o.0|jd[be]|j[wz]o|hk[cj]|^(wb|wd|v3|ub|s2|s1|pb|ml|j5|hv|h1|g8|g6|ft|f4|94|0t)|(we|ha|93|80)4|(xj|x5|03|qa|fz|w)9|3[65]0|zbx|(w.|v|o.?|54)7|[th]82|ssg|g(lc|ij|v|1[34]|bx|bk)|wvf|uax|mss|uhl|306|4.[mr]|9p|rob$))^.*((^([14]?\D+|\D*\d+|\d{3}\D{5}|(?=^\D*\d\D*$).{6}|\D+4\D+|[1-4a-eqwr]+)|sx|[ekru]s|t4u|zx|[avy]y|x[prs]|w[mp2]|uz|tp|tn|sc|qq|qj|p[mov]|r[deq]|oo|n[4tu]|me|k[23c]|jf|[2ag]t|ed|bq|a1|3r|5g)$|\W|123|^(nc|tr|w0|sa|rj|q[bnqu]|ni|mo|mw|le|kc|ib|hz|g9|f0|cb|b9|8d|7k|6u|5w|3m|1q)|z.g|bo|em|x35|t.d|p.o|p39|mar|ki4|id8|ebk|53x)",s)

```

I'm having a bit of trouble testing this in Retina, so here's Python for now. Test by giving the `lambda` a name and running it on the word lists:

```
>>> len([x for x in common if f(x)])
10000
>>> len([x for x in generated if f(x)])
0

```

It's a *very* large regex, so I'm taking a break from golfing it for a bit.

# Answer
> 2 votes
# Bash - 5324 bytes

```
gunzip -c rp.gz|grep $1|wc -l

```

where rp.gz is located at http://dl.tyzoid.com/rp.gz

This returns 1 if on the random list. This is falsy, as bash evalutes 0 as a truty value.

# Answer
> 1 votes
# Haskell, 8047 bytes

```
main=interact$show.flip notElem(words"viy130k57 d69z0 iz7q4d u26q3h 4mr6bhwa4 d36p5d 83554s 70r310py dz3js3 i1w86i0 2c4bk9 26w4kg52 u8i1g22ge 86k4br 875orut1 kw5786758 4k87v nfi5f2h9 x303978 43r4qb 963lnbs h5c1vq6s2 0iyv53vr2 nf5tmbp8 31ieq5xlh 9b450m ohv69d 5297m29 jvsxd20k fuha432 o8i84sh mss63 56vl8kzv8 73hh251 zr3r3zph 5f195v3kq 4o224g8 yi3y1lgi7 5ihcc t1krtr8w6 g7x9cuv4 128ov7 10adfe9 1p3lw 2523v xpj3h6z w2546kzx5 4042nle 0vv7i7ng xxzmf5vl efh601zby 19i0o63 8l20191 xm7e96pl 691p7m3p2 ksx29c2q3 auhli 7jq5e9e 786wo1q 1gwiaj7y8 3r19f26 x2nnr7 3u235s 076zr95m xzr32d 0lo70 v6o391 72pm08fo 79p1v9 uw98b 9mh7q3 2mh6bz a4qqw8d zve8z 790gkwc t975y 7d206t06 0zkvd9q0e y0cb34 9tltcs41w 079bp2y lwk12f 58gz4p 7lrkl io89he175 49dcu m2qg1 1ic76l kt9k9525i 6jwd8 4m9xwe86 3212janr r694ax 2raflx7s s26km575 n0z3hsdhj 9zl3x5 88c96968n 1lbw1v 20kri 799934a91 6c51846 61o78mjun 3d1yn 13113u8ev z22n5ni 0jxuc 79zwnl3tx xv4h4kz7 001n9 2u0f2 8msf6t g83r6v 81j4tt5e 20ucmaf j576783 v64ar 3u16pj83p r817zu6d xgc63 4y1rpo0 031606p 43q08m3x 1sg237d1n dt85c vg30a u4ge5t 4bv27l432 0612939 8glq6zo g64m0r4 593erv6 962a24u 94rop d28fs6k xy78efw3 yd0kyj1 y02rl 3n21q esg5y9m9 8408qpscw 5lapn9k26 4x1k27 7mb8054 4s1x7olv5 10s7726 00eib 84pu58e6 505l3s6 ldgx9e7d hv4d6u56s 5ren77w uf6pmf2 0sfum 1ik8mx vzqtj77 cvjc1ta us90844jb 84r0d4td plab52n 7946vj4l7 qy5gjtr 49lpq 4w49fm 44y0rh472 07jt8 1tju72 q0733u1 375ojd0 1t28s9ag1 ppj60t704 wi67b877 jgrrh388 ftvu98 h214l3x 3nirvrdu mrg14 52s65y 9f587 2629v os80p7 3h89mqk xt5845q9m 68h53w 8b3309g 16967k 38356nk 34oyt he3v5vn2 m1g2c8 8n324x6 2by0e7x 1a4mit7 ge91p60y b170o 9v5rys 6wq3959ue ed9u3 kd4wy1 c853gz k56gel09h 789ygx5pk 1f9f2 84fxtdx d02fdz9i 6gj4i4 6p8jtsax 3v38hkcs2 80090i 8084xb4m c4xv4x79 pilbux017 9m193zg5 qwq5o6x5 90cw69n96 n237351i cm40sj1x 3727d9p q0x74ityn 3ez6679 t7vs045 r7jg22xyr 3z34a96 miu8lm62 cpzjf226u vb2545x 4f9qg7sdq 2rf6t kq0ixi32n rjdeuj g8x5p3 d776c 4x1385 830nug s1tysl o679090 93kgz18 91pu8l n05i73 mdmq4c 31her5 6r10e0il i02np063 75jf619gg 1cft96o9 9j9x4g 12to97 5z6o922 2z1mtcg 3ea7l4 12h2gl0 bl12h638 k1sd9a4y v06po5yn 3ac6le459 0f1ljw ctkjzo4 u9k5rzx82 pa5d2om 32c4713q2 1bp33y 9384p7 v12i1aqp7 nb2w98 76ss0 24cy672 lasprob p1y3g4 ssekkgij 8x1o4 n1rgsm51d 2f73n9t 7gq430y 7lu476llc l8y3oa yjjb67d8 9n01v95gy w7792 061d339f xj989 v3tm27h rqytegr1c qoe96g o81680pg 563bmt680 s2lx9qc14 wpd4o1jb x67a06h83 ll508m 13067 m6578u vn64b 8zm25nd v0ny28346 nh5etpuub 6sl8acai 3hbd5 94103 981by1ri n4k4jzi m5704w7lt a6x3f 9chs9 ivk55n 14j50d 77p684h nt569aek br6yv97 iso7qi 7h1eh 0801fwq 54en7 8celizu j4c1i1409 9di5p1 to3re10m1 t1v246wkb 1n0l9r9 x46l2vwbp m4st1un7u 5apkz94 z9lp3i 3754cl r67up 446exk983 40n6454sf b6y1z1uf b8ca9w0je n9ga6 06156 3n551 71860lr sh9n3 zo6x54 5qwx9 6p2ko1d lzafd6a esv073963 871fu3 64wd2 68j49k4q 3s6b901 3k6x0 3br349yx2 2ev963aa op5t394ig jdbh9 sk364u8 u25m3s0r1 1050ln80w 322ggt12 7xq6z75 279q2 oxys3id7 c78v2 7jfjk1 8aq82y4b 0f43100 4afw4ck p88s6h0k azuaxn q128b 7y0ewmp ikpgn519d 54zq981 18chi4u 5xski3b ztb242 8199b0 886f7 lytj1 d52kr nv060 68tdhr01 0nky3o r9y6g fn24cg3 2i585fw0 c5oj4 d8220hbh rtjwom45 x8ws8 l0vk6945 140jsy6 cx70q6vc s26536 3un5314 koxd24tgw khpz47o 8h0wcv10m dc33280 14i9770 cnj67sv n142iu 3yysx7e6d k5g38u4 7vs103i5 21o1tmi bz7di 4u3m7y2m5 407z8ln9o 3dvz58 372fz3lhq lc8g15yp p9f6lq 5zaz5n5y f4j25y46 s369474nb 6qtfog8 x69wy42 ma2b56i34 e2tv3 jqp515 agbkd95 x3h7kqa0 v27rnd 14zo577s im809s n8pr1y3 o6w6u915z 4v1566be 1k8v4 ie2t65f yoci2 43f3741pr 1iihw59 99k77378o 081sgssg 8e472q 86ui90 9154298yg 03azelrv it3500 8p52k hc5tj my7ok34u9 4k2l9 svys9nx3s 6jc7b54 4wuhh ehkc19 7m242 1p5255e20 7uj997 8gsxl 4m4l4 u0057w 698u0vd8 1pbh99 g30zxku dvj20a7a uyt82 3nhy7i794 98aps9z f9zhx9i5 k686or3 2pc8fo086 f12p2r5y4 gg133 7d7moa92 6787230in ro8113t5 sk01s6ua y219c2679 4p2j48u tww6708 8g0ze8kxh ox2up4c06 acyflgv r2cf66p 51hgd6biq cepo0k5 3gkz3 so47e745 d1550k5 084h64t n5402i a2354hgu 1969f31xc 4ug5te 88av1 psaao7r r73zl z0dupumi 8o3ln n1k76r 3yj1i14 7ea10s8ny ek468v2 07sqhdn pc52r 3q01f1 dhku90f 1wqu1pitk 4xq2d se6v9du e99e82qt 0094y96 36cjds546 2ga756498 63w66053i 76pe39 5j9645gq ld8l156 m0bcb9hj 32kuy b751a8e25 02v61 j4zf5q6 80x964nyd 52ij7 u26vv r718r2d 09czm6116 1bd9a 12t874q5b 7i4ro i07mwc7g5 i4jug5y6 0srfbc0g9 l7j853e p0bcges6 46g56mn c6p6g38v7 5rr875 atpqnbl w177s30 e4pm1d117 y79mt10c 7xa2l69 nw7rrm4z8 36te6593 6r1x9z xai3b 4t6r0uz87 9m568v573 u40y29157 vvl2t4 f1kc0m wp56h1qkm 3xq8ivnr3 535i062 69m2kwb1 d4w2ze 1wjqh0 pb948 w9874d j5oo220d 28hro vx873f55x 5n2q70f 74358tngl 038048 662b16s i0psi7chi 3e98l80d5 hu7rwtl 3j7igy914 0v98t 9s17y8t 61g71jq6 375h1d icx59 plyp2n nm26m22c 3k2028 n13j9l9gh 1sy2a 76f4f glcn1 h3z12 0ctw14 ws2qr p97658 ann1oe63 67i2c5sp 5c6yu 894g7 kl8i8 kqlr6d 29w3z wk8qh26 62ma13brr ho08mctfw 65q3h2 8se1b7 970y4c577 c3f793 2mu9e od8vjhyt 17628 81pfy7 ee14q69t4 005r25c86 50w71m3l9 6se3p8l 9d9c5r7 hdq9rfb0b y29cf26 729xvd u4n91c 35u2q h16334 36xk98 ov1t6 54h6k9 ml63553 2c27tlqc fv1tv v767658 x1u10k 92q1j7b9 40e5is 6su1q59 h90636ll 757m459y0 ke163r6 qf5v8f2n m6h2a 4p88p yfmq2975a g4bv1t k8d8whp65 qz175so3 520g61e 55m6bh235 j6n5y 6w0t76th b0wtl7q lcuw96 mp2l8d1c w4kr923y1 d8741bp4v l245i3 fcmnw 9m4kg85z 6bis4cjs 1sf0g8gq uu36o4l0 a3h31u pvy4em 5q1t37g sb5cbsv3g yejeol og087z9 3d26hrlw7 05s7g2 4yp46v6 1sd3ot g04evj87 d1w1ra6 89g5t8 64a42ihm coh4kq 01ejx 4frus6 3k938303 0y0z1xyx 799v26 7651514aw 3ddi4i8l oc8aa 9u42f 70t17439 vg7o54 xw8c3yz 1i1aq3p23 k6i4j4 41et377k 9r25jic 65o4n1s zt8s9a8 4n88b7 or0974 96it6 ox041b kkk0hi 5ocny 316547 r873o h1z5mb wbw0497 6i422j 54d54bt reh822 r6818 dogwoi2n7 wvfur h51y36k 49d0lhf3m 73714y 3ukt0 45eeq s6686xxn 3395o i67mh66 68093462 4j9ls 74047i54o 1k6i5fawg p3m491 mqy94h6 666kf ue5ry g6g6xw 0bmgtx 75j9nsvf 90g583 hkjhib2 p9460431 a3wi5nd5 hgc0w7 9r1spo63z 87913e 6bz0fc m82jox78 q4c87t 8i6i51c83 ezp12r 6g5i7 ubarl 14k71597 901b2 kb2ya9 xkl93 awh7jmblw q2gbkmvk 91nw3a05i 6qga3 lcg5m 01wur23b 29t7171u cs9u8 a4v3xg0 j5kqpfciu u1o31 xjt16f5v 02165z3 17ow5 lqrq9 v9jt5 g8113 qa9637 ez29eqc9t 2a6ra1r 00767x y9pjem d8xw7s 2i5c5 kve255m7u 41v7yn8 o952s446 q26okdrbr f50xm5 a3l8v744 l8q977 ub2ag2 2307p 079pv6 n4wup 5b46t 0i599u7q t46j1ush8 03a6x c5idf535 566f3l8 r42t11p9 966e5412 82rl29tn9 k032o4 hlra31t2 87f8q8s 57u1vt5o8 g6081 pny7v101a g7ar1z zw697yh4 v96p1180 dg86uo9qh 0oo5r2n1 wse3c6 87qf041y hylxbrj yul0jc1 70394 3i44dn yoi246 7ccmsts0 2c2iqn qytx7c42w hgy3zx1k 0h76k267 vf528wz84 24i92r34t i15h1 0l2n93b 4ysso34 gb4p098p9 5x0p4pk5v la00fg39 2596p esno00 pfz9149 3tl43q0 p9mw947g xrd60n2g 5pcp2n 22vu57d1 169vqkf s6uwxk7 4cx1s 5z89490d8 u2o88803m f4236 94xpjzu 975gcg2b1 2s6ow85w0 r68w68 4valqzgs1 j967p577 wdz4t oy567kh05 v382yl ma0k273m 0qv13 3h79r 1a7286 xlv11nqg g64q2pq7f hh7bl2t65 8oqmq 3230i 9kspnz0 1o58m8 g3g8un0 9s70irfzh 4mqjge4 0pmjw 87jq5lvc 6rr41zav6 146v3 2pj9i leawe46 aojfx1h rbz7s7n0 aka0x 4q31u e069n swj06 l52s891 w7ta9p7 8641c3bj5 o8p3jx mci7g yb0mx95 jperua8 x1sh6whl q13u23s p9h3m 4u561 544u556g psm8vv 5338dmhe 6nmacyod 7qk0e0cx4 1s6zv2ycy 40360 2m3w8h2ee 110o27 w730108t 4547b0 0e998 d62io mjri4m90m 822xgu 7404u73i3 6g73d1 292uv351 789e6 f6721070g 5752261 y5l2i vh471uy 1p06933q o2l85722 axoz605ic yd97s 78whg y8eeb5b sr76mqe wc0855h6j 4ztui 4bc8n5 hvyuovxl4 0tifec 2coog5s6n j2mbd344h bgbx7 m7a4t2j77 vdc2d854 mizbxb2 1xj676 5oi49bw66 t451834gd 1xh7o t006va 6c0jy 126ly2n5 i432l5t61 myrou93w v0t5fi5s4 1zne2o rysfj8k 44x53c 9kk15 8938quif d6f7x 3nz3p cjg70t v309011 07nw947ey 6rc18 n11551so 24dtm5159 qpd4p40 f3794b9y9 8hcx5oo5 570bu cl442vxg l59bl10jx lj5gz00u b7tn6uu08 45m43uf53 t62861qf9 780288ew 3867o8p7 3k8uc we7zh sub593fof qxyi7 q634jlqz 9acjc 24v0eksmu ltx1crj 0y0b73qt 64c8yd 5hbes3 c791g97o2 tg9j2 8736l v2am0 4yq2yg943 193di7141 ss6xq y60lv92r 77b1v383 o9acsyje 163449n0 mnw167 2skcq u5z4v3i 4u70jc 8w872 42q9k44f fshyn004 qr1fa 59599zxbh g25wi69l 61vfy6 01474kb7 6mp11b 62t63e3l 198njo 673s491p ab8dr4qz 2s243 7hwz6lq79 d999oo3 6vsy1 6pf862 79x2dmq85 7q6q48i2 21g4mzy25 do85ib82x r0wb2 6zq2rmf 5q2jp41 bc60yv x18t30 5c0zt6m3 na80h6tc y5r6n o40r45v 0ufog 49w11ce0 10i3cbapw 606z0ti kowx5iro l59quc0 4t00o8")

```

This seems to be the best that I can figure out without breaking out compression algorithms, and none of the languages I like to use really have a brief built-in compression method.

The "algorithm" is extremely simple; check if it's in the list of random passwords and return False if it is and True if it isn't.

---
Tags: code-golf
---


# Question
Title: Code golf: Solve a Knights and Knaves logic problem by parsing English
## Background

There are two people, Bill and John. One of them is a knight, which always tells the truth, and the other is a knave, which always tells a lie. You don't know who is the knight and who is the knave. Each person then says several statements about who is the knave and who is the knight. Using this information, you must come to a conclusion as to who is the knight and who is the knave.

The Knights and Knaves logic problem is based on Booleen algebra. The words that a person says form a Booleen satisfiability problem. The knave's statements must always be false and the other knight's statements must always be true.

John says "Both I am a knave and Bill is a knave". If John were the knight, then this statement would be false, so he can't be the knight. If he were the knave and Bill were the knight, this statement would still be false, even thought the first part is true. So, John is the knave.

# The Challenge

Your challenge is to write the shortest program possible that will take a list of statements made by each person and will figure out who is the knave and who is the knight. There are a lot of details to cover, so this problem is described in three sections.

## Input

Input will be two lines followed by a newline. Each line will give the name of one of the characters, followed by a colon, followed by several sentences said by that person. If one person is the knight, then all of his sentences will be true, and all of the knave's sentences will be false. The first letter of a sentence will always be capitalized, and every sentence will end with a period. Here is an example:

```
Joe: Both I am a knight and neither Steve is a knave nor I am a knave.
Steve: Joe is a knave. Either Joe is a knight or I am a knight.

```

## Parsing

Each sentence consists of at least one clause. Each clause contains one of several things (hopefully you can understand my notation):

```
both [clause] and [clause]
either [clause] or [clause]
neither [clause] nor [clause]
[I am | (other person's name) is] a [knight | knave]

```

This is unambigious becuase it can be understood in a way similar to Polish notation. Here is an example of a sentence:

```
Both I am a knight and neither Steve is a knave nor I am a knave.

```

The translation into Booleen algebra is straightforward. The "both" statements are ANDs, the "either" statements are XORs, and the "neither" statements are NORs.

```
(I am a knight) AND ((Steve is a knave) NOR (I am a knave))

```

## Output

Output will consist of two lines. Each line consists of a person's name (in order) and then says whether he is the knight or the knave. There will always be one knight and one knave. Here is the output for the above example:

```
Joe is the knave.
Steve is the knight.

```

If the problem is unsolvable (either you can't tell who is what, or there is no solution), then your program can do anything EXCEPT produce a valid output.

# More examples

Input

```
Sir Lancelot: Either both I am a knight and Merlin is a knave or both I am a knave and Merlin is a knight.
Merlin: Either both I am a knight and Sir Lancelot is a knight or both I am a knave and Sir Lancelot is a knave.

```

Output

```
Sir Lancelot is the knight.
Merlin is the knave.

```

Input

```
David: Neither I am a knave nor Patrick is a knight. Either I am a knight or Patrick is a knave.
Patrick: Either I am a knight or both I am a knight and David is a knight.

```

Output

```
David is the knave.
Patrick is the knight.

```

Input

```
Lizard: I am a knight.
Spock: I am a knave.

```

One possible output

```
Rock Paper Scissors

```

## Rules, Regulations and Notes

1. Standard code golf rules apply
2. Your program must be only made up of printable ASCII
3. All input and output will be from STDIN and STDOUT

# Answer
## Python, 491 chars

Works by converting each line to a Python expression, and eveluating it.
The knave and knight are evaluated as 0 and 1. For the two people, we try both options.
For example, `Joe: Steve is a knave` becomes `Joe==(Steve==knave)`. This way, if `Joe` is a knave, the result is true only if he's lying.
You get ugly errors when it's impossible or undecided. If impossible, `r[0]` is an index error, because `r` is empty. If undecidable, concatenating `r[1:]` to a list of strings causes trouble.

```
import sys
def p():
    a=s.pop(0)
    try:return{"both":"(%s*%s)","either":"(%s|%s)","neither":"(1-(%s|%s))"}[a.lower()]%(p(),p())
    except KeyError:r=s[2];del s[:4];return"(%s==%s)"%((a,m)[a=="I"],r)
x=[];w=[]
for l in sys.stdin:
    m,l=l.split(":");w+=[m]
    for s in l.split("."):
        s=s.split()
        while s:x+=["%s==%s"%(m,p())]
k=("knave","knight")
r=[a for a in[{w[0]:z,w[1]:1-z}for z in(0,1)]if all(eval(l,{k[0]:0,k[1]:1},a)for l in x)]
print"\n".join(x+" is the "+k[r[0][x]]+"."for x in w+r[1:])

```
> 6 votes

# Answer
### Ruby, 352 characters

The solution became quite long so there might still be some place to golf. It requires the input to be well-formed (as all the examples above are - but don't try to name a person "Both"...).

```
q=->{gets.split /: |\.\s/}
C,*E=q[]
D,*F=q[]
r=->c,m{t=c.shift;t[1]?(x=r[c,m];c.shift;y=r[c,m];t[0]==?B?x&y :t[0]==?E?x^y :1-(x|y)):(c.shift(2);h=c.shift[2]==?I?m : 1-m;t==?I?h :1-h)}
s=->u,v,b{u.map{|c|r[c.gsub(v,?J).upcase.split,b]==b}.all?}
t=->b{s[E,D,b]&&s[F,C,1-b]}
u=->v,b{v+" is the kn#{b ?:ight: :ave}."}
puts t[1]^t[0]&&u[C,t[1]]+$/+u[D,t[0]]

```
> 3 votes

# Answer
# Perl - 483 bytes

```
(($a,$b),($c,$d))=map{split':'}@ARGV;$h='y';$i='x';$s=' is the kn';$g='ight.';$v='ave.';for($b,$d){$_.=' 1';s/ am a | is a /==/g;s/knight/1)/g;s/knave/0)/g;s/I=/(\$$i=/g;s/($a|$c)=/(\$$h=/g;s/([^.]+)\./($1)and/g;s/ or / xor /g;s/ nor / or /g;while(s/(?<= )(\w+ \((?:[^()]+|(?1))\) \w+ \((?:[^()]+|(?1))\))/($1)/g){}s/neither/!/gi;s/both|either//gi;$h=$i++}$x=0;$y=1;$k=!eval($b)&&eval($d);$x=$y--;$n=!eval($d)&&eval($b);print"$a$s$v
$c$s$g"if($k&&!$n);print"$a$s$g
$c$s$v"if($n&&!$k)

```

Similar to the Python solution. It reduces the sentences to Perl code and then `eval`s them. It can print almost-valid output if the input is weird but doesn't print anything if it's undecidable. Well-formed input works as expected. The sentences are passed in on the command line inside quotes and no special flags are needed.
> 0 votes

---
Tags: code-golf, printable-ascii, puzzle-solver
---