title: Extension of the Game of Sevens

text:
# Question
Title: Extension of the Game of Sevens
# Introduction

Output all the numbers in specific base that would appear in an adapted version of the game of seven.

# Challenge

Your task is to output all the numbers in a given base in a given range, skipping the ones matching certain conditions.

You will be given four inputs: `base` `elim` `start` and `end`. The roles of the four variables are as follows:

* `base` specifies what base we are using for the other three variables, and also for output. One way to express it is using a single character that is '8', '9' or a capital letter from 'A' to 'Z', using 'A' for decimal system, and 'G' for hexadecimal system. The bases expected to be supported are 8 to 35 (inclusive). This is just my suggested way to express the `base` and I will use it in the **Example Input and Output** section, but it is also fine to use your own way to express it. For example, you may choose to format `base` as its usual decimal representation.
* `start` and `end` are two strings that specify the range of numbers to be output, expressed in the given `base`. If `base` is `G` and `start` is `10` and `end` is `1F`, you need to output `10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F`, but you also need to eliminate some out them based on what `elim` is, to be explained soon.
* `elim` is a single character and must be a valid digit in the given `base`. All numbers containing the digit `elim` or are multiples of `elim` should be eliminated from the list to generate the final output.

In the case above, if `elim` is `7`, then `17` need to be eliminated because it contains the digit `7`. `15` and `1C` also need to be eliminated because they are multiples of `7`. So the final output would be `10 11 12 13 14 16 18 19 1A 1B 1D 1E 1F`

# Test Cases

```
Input -> Output

G,7,10,1F -> 10 11 12 13 14 16 18 19 1A 1B 1D 1E 1F
A,3,1,100 -> 1 2 4 5 7 8 10 11 14 16 17 19 20 22 25 26 28 29 40 41 44 46 47 49 50 52 55 56 58 59 61 62 64 65 67 68 70 71 74 76 77 79 80 82 85 86 88 89 91 92 94 95 97 98 100
G,A,96,C0 -> 97 98 99 9B 9C 9D 9E 9F B0 B1 B2 B3 B5 B6 B7 B8 B9 BB BC BD BF C0

```

The third test case is added after the original post. All the answers posted before the edit has been tested and passed the third test.

# Specs

* The input will always be valid so don't worry about exception handling.
* This is , the lowest number of bytes wins.
* You can take input and provide output through any standard form, and you are free to choose the format.
* As usual, default loopholes apply here.
* This is based on the (real-life version of) the game of sevens.
* I require `base` to be at least 8 purely due to personal taste. I just don't want to see the number of digits in the sequence grow too fast.

# Scoreboard

Snippet taken from this question. Run the snippet to get the scoreboard.

```
var QUESTION_ID=154147,OVERRIDE_USER=77134;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/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} /* font fix */ body {font-family: Arial,"Helvetica Neue",Helvetica,sans-serif;} /* #language-list x-pos fix */ #answer-list {margin-right: 200px;}
```

```
<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
# Emojicode, ~~141~~ 116 bytes

*thanks to @NieDzejkob for 25 bytes!*

```
abcdi⏩c➕1d❎0i b☁i ab ai a

```

Try it online!

```

  a b c d		 4 arguments of type  (integer)
   i  ⏩ c  ➕ 1 d 		 for i in range(c, d+1)
      			   if cond_a and cond_b
      ❎  0   i b		     cond_a: i%b != 0
      ☁   i a   b a	     cond_b: i in base-a doesnt have b in base-a
    				   then
        i a			     print i in base-a

```
> 10 votes

# Answer
# Jelly,  ~~12~~  11 bytes

-1 thanks to Erik the Outgolfer (use of "order"  in place of divisible with swapped arguments, `ḍ@`)

```
r/ọÐḟ⁵bċÐḟ⁵

```

A full program taking three inputs as command line arguments, all of which employ decimal notation - a list `[start, end]`, and two numbers, `base` and `elim` \- which prints the Jelly representation of a list of lists, where each represents the digits of a number in `base` and each digit is a decimal number (e.g. 1043 in base 20 would be `[2,12,3]`, i.e. 2×202+12×201+3×200).

**Try it online!**

A small note: this won't work for ranges that include negative values, but the linked challenge starts from 1 and counts up.

### How?

```
r/ọÐḟ⁵bċÐḟ⁵ - Main link: list, [start, end]; number, base
 /          - reduce [start, end] with:
r           - inclusive range => [start, start+1, ..., end]
   Ðḟ       - filter discard if:
     ⁵      -   program's 5th argument (the 3rd input), elim
  ọ         -   order (how many times the element is divisible by elim, or 0 if not)
      b     - convert to base "base"
        Ðḟ  - filter discard if:
          ⁵ -   program's 5th argument (the 3rd input), elim
       ċ    -   count (0 if elim is not a digit)

```
> 5 votes

# Answer
# Julia 0.6, 69 bytes

```
f(b,e,r,g=filter)=g(z->!contains(z,base(b,e)),base.(b,g(x->x%e>0,r)))

```

Inputs are `base, elim, start:end` where `start:end` is a `UnitRange`. as base 10 integers. Outputs a list of strings of the numbers in the given base. Filters for divisibility in integer form, uses `base.` to elementwise convert to strings, then filters on digit containment. Called example: `f(10,3,1:100)`

Try it online!
> 2 votes

# Answer
# Japt, 16 bytes

Hastily rewritten after the spec was changed to allow decimal input so can probably be improved upon.

Takes input in the order `start`, `end`, `base`, `elim` and outputs an array of numbers in the given base.

```
òV kvX msW køXsW

```

Try it

---

## Explanation

```
                   :Implicit input of integers U=start, V=end, W=base & X=elim
òV                 :[U,V]
   k               :Remove
    vX             :  elements divisible by X
       m           :Map
        sW         :  Convert to base-W string
           kø      :Remove elements containing
             XsW   :  X converted to a base-W string
                   :Implicit output of resulting array

```
> 1 votes

# Answer
# Python 2, ~~102~~ 94 bytes

```
lambda b,e,l,u:[i for i in range(l,u+1)if i%e*x(i,b,e)]
x=lambda n,b,e:n<1or(e-n%b)*x(n/b,b,e)

```

Try it online!

Input and output is in base 10.
> 1 votes

# Answer
# JavaScript, 82 bytes

A quickie before I hit the boozer! Takes input in base-10 in the order `base`, `elim`, `start` & `end` and outputs a space delimited string of base-10 numbers with a single trailing space.

```
(b,l,s,e)=>(g=o=>++s>e?o:g(s%l&&!~s[t=`toString`](b).search(l[t](b))?o+s+` `:o))``

```

Try it online
> 1 votes

# Answer
# Perl 6,  ~~94~~  57 bytes

```
->\a,$b,\c,\d {grep {!/$b/},grep({$_%$b.parse-base(a)},[...] (c,d)».parse-base(a))».base(a)}

```

Test it (94)

Since the rules have changed:

```
->\b,$e,\r{grep {!/"$e.base(b)"/},grep(*%$e,r)».base(b)}

```

Test it ( Int, Int, Range )
Output is a list of strings in the base

## Expanded

```
->
  \b,  # base  (Int)
  $e,  # elim  (Int)
  \r   # range (Int Range)
{
  grep
    {!/"$e.base(b)"/},  # remove the values that contain the character

    grep(
      * % $e,           # remove values that are divisible by elim
      r                 # the input Range

    )».base(b)          # convert each into base ｢b｣
}

```
> 1 votes

# Answer
# Java 8, 92 bytes

```
(b,k,s,e)->{String r="",t;for(;s<=e;r+=t.contains(k)?"":t+" ")t=b.toString(s++,b);return r;}

```

Input as `Integer (base), String (elem), int (start), int (end)`.

**Explanation:**

Try it online.

```
(b,k,s,e)->{              // Method with the four parameters, and String return-type
  String r="",            //  Result-String, starting empty
         t;               //  Temp-String
  for(;s<=e;              //  Loop from start to end (inclusive)
      r+=                 //    After every iteration: append the result-String with:
         t.contains(k)?   //     If the temp-String contains the elem we exclude
          ""              //      Don't append anything to the result-String
         :                //     Else:
          t+" ")          //      Append the temp-String + a space
    t=b.toString(s++,b);  //   Convert the number to the given base and set the temp-String
  return r;}              //  Return the result-String

```

The three test cases are inputted like this:

```
16,"7",16,31
10,"3",1,100
16,"A",151,192

```
> 0 votes

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


title: Rubik's Cube Scrambles

text:
# Question
Title: Rubik's Cube Scrambles
Your task is to create a random sequence of moves, which can be used to scramble a Rubik's Cube. Such a scramble is made up of exactly 25 moves. Each move consist of of the letters `UDRLFB` optionally followed by one of the suffixes `'2`.

This notation is called the Singmaster notation. `UDRLFB` represents one of the 6 faces and the optional suffix `'2` represents the turning angle. This information is in no way necessary to solve the task.

To assure, that the scrambles are of 'good quality', the following two rules have to apply:

* Two consecutive moves must not have the same letter. This bans the consecutive moves `UU`, `DD`, `RR`, `LL`, `FF` and `BB` and all their combinations using the optional suffixes like `U2U` or `U'U'`.

These move pairs are banned, because they can easily reduced to 1 or 0 moves. `U2U` has the same effect as `U'`, `R'R` the same effect as .
* Three consecutive moves must not be of the same letter group. The letter groups are `UD`, `RL` and `FB`. This rule additionally bans the consecutive moves `UDU`, `DUD`, `RLR`, `LRL`, `FBF`, `BFB` and all their combinations using the optional suffixes like `U2DU`, `RL'R` or `B2FB'`.

The groups sort the faces by their move axis. `U` and `D` are in the same group, because both turn around the same axis. Therefore an `U` move doesn't influence the pieces of the `D` face, and a `D` move doesn't influence pieces of the `U` face. Therefore the two moves can be exchanged, `UDU` has the same effect as `UUD`, and this can be reduced to `U2D`.

## Challenge

Write a script or a function, that generates one random scramble. There is no input. The script / function has to print the 25 moves without separation or separated by one space or return the correspondent string.

Your program has to be able to create every single scramble, which satisfies the rules above. Of course assuming, that the random number generator is true random, and not pseudo random.

This is code-golf. The shortest code (counted in bytes) wins.

## Examples outputs:

Calling the script / function 3 times should print / return something like:

```
R'B2R2F2R2FB'R2DR2ULFB2RB'U2B'FL'BR'U'RB'
U'DBR'B2U'B'U'RUF'B'RDR2U'B'LR'B'F2D2UF2L'
BR2F'B'R'D'R'U2B'F2D2R'F2D'F'D2R2B'L2R'UB'R2L'D

```

If you separate the moves by a space each:

```
R2 L' F2 U2 D' R2 L2 F L' D2 U R B D' U2 L B2 L U B2 D U2 R' D2 U'
B R D2 F U2 B' R2 F2 B' U' L' R2 B U2 R' D B' F' U2 R' B' L R D2 R2
B2 R2 U D' B R D' R L2 D2 L2 R B2 F U' F2 B2 U' F U' D F R2 U2 B'

```

Notice, that all these outputs consists of 25 moves, but have different lengths, because of the optional suffixes. It's not allowed to print a space, when either `2` or `'` are uses as suffix. You have to print `L2UR2F'R'U2` or `L2 U R2 F' R' U2`. `L2U R2F'R'U2` is not allowed.

# Answer
> 6 votes
# CJam, ~~47~~ 45 bytes

This solution uses an approach that's different from any other posted so far. It takes advantage of CJam's concise list operations to generate the available move list and select one at random each iteraton. Modifiers are simply generated independently.

Try it online.

```
{BA^2/6,_B-?A:B-mr0=:A"UDRLFB"=3mr[L2'']=}25*

```

### Explanation

```
{               "Loop...";
  BA^2/           "If the two previous moves were not from the same group, ...";
  6,              "... then produce the available move list [0 1 2 3 4 5], ...";
  _B-             "... else produce the available move list [0 1 2 3 4 5] with
                   the second previous move removed";
  ?
  A:B             "Save the previous move as the second previous move";
  -               "Remove the previous move from the available move list";
  mr0=            "Randomly select an available move";
  :A              "Save this move as the previous move";
  "UDRLFB"=       "Map this move to its character (implicitly printed)";
  3mr[L2'']=      "Randomly select a modifier (implicitly printed)";
}25*            "... 25 times";

```

# Answer
> 9 votes
# C,129

```
f(){int i,n,m,r,s,t;for(i=26;i--;i<25&&printf("%c%c","URFDLB"[s%6],"'2"[r%3])){for(n=m,t=1;t;t=m*n==9)m=(r=rand()%15)/3+1;s+=m;}}

```

The inner loop generates a value of `m` in the range `1..5` which when added to `s` and taken modulo 6, ensures that no two consecutive moves are on the same side of the cube. The old value of `m` is stored in `n` and the test `m*n==9` ensures that the value `m`=3 is never generated twice in a row (so opposite faces cannot be picked twice in a row; note the order of faces in the string.)

The least significant part of `r` is used to decide which suffix (`'`, `2` or null) to use, taking advantage of the null character at the end of `"'2"`.

The outer loop runs 26 times. The first time, `U` can never be picked, so `printf` is suppressed for the first iteration.

**Ungolfed code in test program**

The ungolfed code puts a space between each move for clarity (the golfed code does not, in order to save one byte.) Additionally the golfed code saves a semicolon by relocating the `printf` within the `for` bracket.

```
f(){
  int i,n,m,r,s,t;
  for(i=26;i--;){
    for(n=m,t=1;t;t=m*n==9)m=(r=rand()%15)/3+1;
    s+=m;
    i<25&&printf("%c%c ","URFDLB"[s%6],"'2"[r%3]);
  }
}

main(){
  int j;
  srand(time(0));
  for(j=0;j<5;j++)f(), puts("");
}

```

Typical output

```
U' B D2 B' R' L F' D2 B D2 B2 R' B2 U D2 F' R U R' L B' L R2 B2 F'
U B U B F L2 D2 B' U' L B L R' D B U' D R D' B' F2 D' B D R
L D F2 B2 R' U F B' D2 L U R' L' U2 F' R F D U2 B L' B' U L2 F'
R2 B' F2 R2 L2 F' U2 L U' B' F R' D' F2 D F' L2 U2 R' D' B2 D F R2 L'
U2 F2 B2 D' F D F R L2 U' B D2 L' R D R F2 R' F2 U2 D R' D2 L F2

```

# Answer
> 4 votes
# Pyth, ~~65~~ 66

I've never really golfed in Pyth, maybe written a program or two. This is basically @steveverrill's solution translated to Pyth. Improvement suggestions are welcome.

**Update:** added 1 byte to make scrambles also start with `U`. Maybe the C solution is relying on undefined behavior to make it work...

```
=YO6V25JZK1WK=GO15=Z/+3G3=Kq9*ZJ)~YZpd+@"URFDLB"%Y6?@"'2"%G3>2%G3k

```

I believe this should be done with less assignments, but that would require me to modify the algorithm a lot. (Well, might try.)

Here's an explanation based on the C code:

```
=YO6           s = random.choice(range(6))
V25            for i in range(25):
  JZ               n = m
  K1               t = 1
  WK               while t:
    =GO15              r = random.choice(range(15))
    =Z/+3G3            m = (r + 3) / 3
    =Kq9*ZJ            t = 9 == m * n
  )
  ~YZ              s += m
  pd               print(..., end = " ")
  +                ... + ...
  @"URFDLB"%Y6     "URFDLB"[s % 6]
  ?@"'2"%G3>2%G3k  "'2"[G % 3] if 2 > G % 3 else ""

```

# Answer
> 4 votes
# JavaScript (ES6) 175 ~~178 204~~

**Edit** 3 bytes less, 1 by changing the code and 2 by changing the way bytes are counted (not counting `F=`)

The code to avoid repetitons is taken from @stevemiller. His way of managing the letter groups is even better, but i'm not going to steal it.

Bonus: you can optionally specify the number of moves.

```
(n=25,R=n=>Math.random()*n|0)=>(r=>{for(N=_=>'UDRLFB'[(r-=~R(5))%6],b=N(a=N(s=''));n;~(a+b+c).search('^([UD]*|[RL]*|[FB]*)$')?0:s+=(--n,a=b,b=c)+["","'",2][R(3)])c=N()})(0)||s

```

*Less golfed*

```
(n = 25) =>
{
  R = n => Math.random()*n | 0;
  N = _ => 'UDRLFB'[(r += 1+R(5)) % 6];
  r = 0;
  b = N();
  a = N();
  for(s = '' ; n; )
     c = N(),
     ~(a+b+c).search('^([UD]*|[RL]*|[FB]*)$')
       ? 0
       : s += (--n, a=b, b=c) + ["","'",2][R(3)];
  return s
}

```

**Test**

```
var F=
(n=25,R=n=>Math.random()*n|0)=>(r=>{for(N=_=>'UDRLFB'[(r-=~R(5))%6],b=N(a=N(s=''));n;~(a+b+c).search('^([UD]*|[RL]*|[FB]*)$')?0:s+=(--n,a=b,b=c)+["","'",2][R(3)])c=N()})(0)||s

function go() {
  console.log(F(+M.value))
}

go()
```

```
Moves <input type=number min=1 id=M value=25 max=999>
<button onclick='go()'>Test</button>
```

# Answer
> 2 votes
# Javascript - 112

```
for(c=b=j=25,r=Math.random;j;c+b-5|c-m&&b-m?document.write("URFBLD"[j--,c=b,b=m]+" 2'"[0|r()*3]+" "):0)m=0|r()*6

```

# Answer
> 2 votes
# Ruby, ~~116 107 105~~ 95 bytes

```
->{(0..r=l=m=24).map{m=rand 6while l==m||r/2==l/2&&l/2==m/2;r=l;l=m;'RLFBUD'[m]+" '2"[rand 3]}}

```

Try it online!

# Answer
> 2 votes
# Java 8, ~~189~~ 183 bytes

```
v->{for(int i=26,n,m=0,r=0,s=0,t;i-->0;){for(n=m,t=1;t>0;t=m*n==9?1:0)m=(r=(int)(Math.random()*15))/3+1;s+=m;if(i<25)System.out.print("URFDLB".charAt(s%6)+(r%3<1?"'":r%3<2?"2":""));}}

```

Port of *@LevelRiverSt*'s C answer. I tried some things myself, but this was shorter than what I had..

Try it online.

# Answer
> 1 votes
## Clojure, 223 bytes

```
(let[R(range)F(fn[f p c](apply concat(filter f(partition-by p c))))](apply str(map str(take 25(F(fn[p](<(count p)3))(zipmap"UDLF""1122")(F(fn[p](=(count p)1))int(for[_ R](rand-nth"UDRLFB")))))(for[_ R](rand-nth[""\'\2])))))

```

This relies heavily on the "sequence -\> partition-by -\> filter -\> concat" pattern, it is used to filter out "illegal" sequences of faces. This seq is then mapped to string together with a random postfix (including the empty string).

Ungolfed starting point:

```
(->> (for[_(range)](rand-nth"UDRLFB"))
     (partition-by int)           ; "identity" would be the correct fn to use here
     (filter(fn[p](=(count p)1))) ; Only one identical value in partition
     (apply concat)
     (partition-by(zipmap"UDLF""1122")) ; R & B are in the implicit nil group
     (filter(fn[p](<(count p)3)))       ; Only 1 or 2 consecutive faces from a group
     (apply concat)
     (take 25))

```

---
Tags: code-golf, random, generation, rubiks-cube
---


title: Diluted Integer Sums

text:
# Question
Title: Diluted Integer Sums
A positive integer can be *diluted* by inserting a `0` between two bits in its binary expansion. This means that an `n`-bit number has `n-1` dilutions, which are not necessarily all distinct.

For example, for `12` (or `1100` in binary), the dilutions are

```
11000 = 24
   ^

11000 = 24
  ^

10100 = 20
 ^

```

In this challenge, we're going to be taking the sum of all the dilutions, exclusive of the original number. For `12`, taking the sum of `24, 24, 20` results in `68`, so `68` should be the output for `12`.

### Challenge

Given a positive integer `n > 1` as input, output/return the diluted sum as explained above.

### Examples

```
in    out
---   ---
2       4
3       5
7      24
12     68
333  5128
512  9216

```

### Rules

* The input and output can be assumed to fit in your language's native integer type.
* The input and output can be given in any convenient format.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
> 12 votes
# Python 2, ~~43~~ 39 bytes

```
f=lambda n,i=2:n/i and n*2-n%i+f(n,i*2)

```

Try it online!

---

## How?

Each call of the recursive function calculates a single dilution. The position of the inserted `0` is `log2(i)`. The function recurses until `i` gets bigger than `n` and the insertion would be on the left of the number. If `i>n`, `n/i` evaluates to `0`, which is a falsy value in Python.

`n*2` shifts the entire number one binary digit left, `n%i` or `n % 2**(position of insertion)` calculates the value of the part that should not be shifted left. This value gets subtracted from the shifted number.

## Example (n=7)

```
call       n/i          bin(n)  n*2     n%i   dilution       return value

f(7, i=2)  3 => truthy  0b111   0b1110  0b1   0b1101 = 13    13 + f(7, 2*2) = 13 + 11 = 24
f(7, i=4)  1 => truthy  0b111   0b1110  0b11  0b1011 = 11    11 + f(7, 4*2) = 11 + 0 = 11
f(7, i=8)  0 => falsy                                        0

```

# Answer
> 7 votes
# Jelly, 11 bytes

```
BJṖ2*ɓdḅḤ}S

```

Try it online!

### How it works

```
BJṖ2*ɓdḅḤ}S  Main link. Argument: n (integer)

B            Binary; convert n to base 2. This yields a digit array A.
 J           Indices; yield [1, ..., len(A)].
  Ṗ          Pop; remove the last element, yielding [1, 2, ..., len(A)-1].
   2*        Elevate 2 to these powers, yielding [2, 4, ..., 2**(len(A)-1)].
             Let's call the result B.
     ɓ       Begin a new, dyadic chain, with left argument n and right argument B.
      d      Divmod; yield [n/b, n%b], for each b in B.
        Ḥ}   Unhalve right; yield 2b for each b in B, i.e., [4, 8, ..., 2**len(A)].
       ḅ     Unbase; convert each [n/b, n%b] from base 2b to integer, yielding
             (2b)(n/b) + (n%b).
          S  Take the sum.

```

# Answer
> 5 votes
# MATL, 13 bytes

```
tZl:W&\5ME*+s

```

Try it at MATL Online! Or verify all test cases.

### Explanation

Consider input `12` as an example.

```
t     % Implicit input. Duplicate
      % STACK: 12, 12
Zl    % Binary logarithm
      % STACK: 12, 3.584962500721156
:     % Range (rounds down)
      % STACK: 12, [1 2 3]
W     % Power with base 2, element-wise
      % STACK: 12, [2 4 8]
&\    % 2-output modulus, element-wise: pushes remainders and quotients
      % STACK: [0 0 4], [6 3 1]
5M    % Push array of powers of 2, again
      % STACK: [0 0 4], [6 3 1], [2 4 8]
E     % Multiply by 2
      % STACK: [0 0 4], [6 3 1], [4 8 16]
*     % Multiply, element-wise
      % STACK: [0 0 4], [24 24 16]
+     % Add, element-wise
      % STACK: [24 24 20]
s     % Sum of array. Implicit display
      % STACK: 68

```

# Answer
> 4 votes
# Japt, ~~12~~ 11 bytes

```
¢¬£¢iYTÃÅxÍ

```

Try it

---

## Explanation

```
                 :Implicit input of integer U
¢                :Convert to base-2 string
 ¬               :Split to an array of individual characters/digits
  £    Ã         :Map over the elements, with Y being the current 0-based index
   ¢             :  Convert U to a base-2 string
    iYT          :  Insert a 0 in that string at index Y
        Å        :Slice off the first element of the array
          Í      :Convert each element to a base-10 integer
         x       :Reduce by addition

```

# Answer
> 4 votes
# C,  ~~58~~  56 bytes

*Thanks to @Dennis for saving two bytes!*

```
s,k;f(n){for(s=0,k=2;k<=n;k*=2)s+=n/k*k*2+n%k;return s;}

```

Try it online!

# C (gcc), 50 bytes

```
s,k;f(n){for(s=0,k=2;k<=n;)s+=n%k+n/k*(k+=k);k=s;}

```

Returning by `k=s;` is undefined behaviour, but works with gcc when optimizations are disabled. Also, `n%k+n/k*(k+=k)` has unspecified behaviour, but seems to work fine with gcc.

Try it online!

# Answer
> 4 votes
# , ~~20 15~~ 14 bytes

```
+/@}:@:+[\&.#:

```

Try it online.

### 15 bytes

```
1#.-,+:-#.\.@#:

```

Try it online!

```
     +:             Input×2
       -            Subtract
        #.\.@#:     The list of binary suffixes of input (in decimal)
   -,               Append negative input
1#.                 Add them up

```

# Answer
> 4 votes
# Jelly, ~~9~~ 8 bytes

```
BḊḄÐƤạḤS

```

Try it online!

```
B                        to binary          42 -> 1 0 1 0 1 0
 Ḋ                       drop first                 0 1 0 1 0
  ḄÐƤ                    each suffix to decimal   10 10 2 2 0
      Ḥ                  double the input                  84
     ạ                   absolute difference   74 74 82 82 84
       S                 add them up                      396

```

Vice versa, `B¹ƤṖ+BḄS`: get prefixes, drop last, add them to input, and sum.

# Answer
> 3 votes
# JavaScript (ES6), ~~41~~ 40 bytes

*Saved 1 byte thanks to Mr.Xcoder*

```
f=(n,k=1)=>k<n&&(n&k)+2*(n&~k)+f(n,k-~k)

```

### Test cases

```
f=(n,k=1)=>k<n&&(n&k)+2*(n&~k)+f(n,k-~k)

console.log(f(2  )) //    4
console.log(f(3  )) //    5
console.log(f(7  )) //   24
console.log(f(12 )) //   68
console.log(f(333)) // 5128
console.log(f(512)) // 9216
```

# Answer
> 3 votes
# Retina, ~~53~~ ~~50~~ 47 bytes

```
.+
*
+`(_+)\1
$1O
O_
_
L$`\B
$`O$'
+%`\B
¶$`¶
_

```

Try it online! Link includes test cases. Edit: Saved 3 bytes thanks to @MartinEnder. Explanation:

```
.+
*
+`(_+)\1
$1O
O_
_

```

Convert from decimal to binary, but using O to represent 0, as it's not a digit, and _ to represent 1, as it's the default repetition character in Retina 1.

```
L$`\B
$`O$'

```

Insert an O between each pair of digits, and collect the results as a list.

```
+%`\B
¶$`¶

```

Convert from binary to unary. (This conversion produces extra `O`s, but we don't care.)

```
_

```

Sum and convert to decimal.

# Answer
> 2 votes
# Pyth, 13 bytes

```
smiXd.BQZ2Ssl

```

**Try it here!**

### Explanation

```
smiXd.BQZ2Ssl | Full program.

           sl | The base-2 logarithm of the input, floored to an integer.
          S   | Create the integer range [1 ... the floored logarithm].
 m            | And map a function over it.
------------+-+-----------------------------------------------------
  iXd.BQZ2  | The function to be mapped (uses a variable d).
     .BQ    | In the binary representation of the input...
   X    Z   | ... Insert a zero...
    d       | ... At index d.
  i      2  | And convert the result from base 2 to an integer.
------------+-+-----------------------------------------------------
s             | Sum the resulting list.

```

# Answer
> 2 votes
# Jelly, 10 bytes

```
BµLḤ_J’×µḄ

```

Try it online!

Not the shortest currently, but it could be if there's a way around `Bµ µḄ`...

### Explanation

```
BµLḤ_J’×µḄ    Main link. Argument: n (integer)
B             Binary; convert n to an binary of binary digits. Call this A.
 µ            Start a new monadic link with argument A.
  L           Length; yield len(A). We'll call this l.
   Ḥ          Unhalve; yield l * 2.
     J        Length range; yield [1, 2, ..., l].
    _         Subtract; yield [l*2 - 1, l*2 - 2, ..., l].
      ’       Decrement; subtract one from each item.
       ×      Multiply each item by the corresponding item in A. Call this B.
        µ     Start a new monadic link with argument B.
         Ḅ    Unbinary; convert from a binary array to a decimal.

```

Basically, this works by multiplying each binary digit by a magic number. I can't explain it without visualizing it, so here's the binary number we'll be working with:

```
1111

```

As explained by the challenge, he output we want is the sum of these binary numbers:

```
10111  = 2^4 + 2^2 + 2^1 + 2^0
11011  = 2^4 + 2^3 + 2^1 + 2^0
11101  = 2^4 + 2^3 + 2^2 + 2^0

```

However, we don't actually have to insert zeroes: Jelly's "unbinary" atom will accept numbers other than just `0` and `1`. When we allow ourselves to use `2`, this pattern gets simpler:

```
2111   = 2*2^3 + 1*2^2 + 1*2^1 + 1*2^0
2211   = 2*2^3 + 2*2^2 + 1*2^1 + 1*2^0
2221   = 2*2^3 + 2*2^2 + 2*2^1 + 1*2^0

```

When we sum up the digits in each column, we get

```
6543   = 6*2^3 + 5*2^2 + 4*2^1 + 3*2^0 = 48 + 20 + 8 + 3 = 79.

```

The trick this answer uses is to generate this pattern, and multiply each digit by the corresponding digit in the original to cancel out the necessary columns. 12, for example, would be represented as

```
 1100
×6543
=6500  = 6*2^3 + 5*2^2 + 0*2^1 + 0*2^0 = 48 + 20 + 0 + 0 = 68.

```

# Answer
> 1 votes
# Husk, ~~13~~ 12 bytes

-1 byte thanks to @Mr. Xcoder!

```
ṁḋ§z·+Θḣotṫḋ

```

Try it online!

### Explanation

```
ṁḋ§z·+Θḣ(tṫ)ḋ  -- example input: 6
            ḋ  -- convert to binary: [1,1,0]
  §            -- fork argument
        (tṫ)   -- | tail of tails: [[1,0],[0]]
       ḣ       -- | heads: [[1],[1,1],[1,1,0]]
   z           -- and zipWith the following (example with [1,0] [1])
    · Θ        -- | prepend 0 to second argument: [0,1]
     +         -- | concatenate: [1,0,0,1]
               -- : [[1,0,1,0],[1,1,0,0]]
ṁ              -- map the following (example with [1,0,1,0]) and sum
 ḋ             -- | convert from binary: 10
               -- : 22

```

# Answer
> 1 votes
# Java 8, 55 bytes

```
n->{int r=0,i=2;for(;i<=n;r+=n%i+n/i*(i*=2));return r;}

```

Port of Steadybox' C answer, and golfed 3 bytes in the process.

Try it online.

# Answer
> 1 votes
# , ~~141~~ 48 bytes

```
function(n,l=2^(1:log2(n)))sum(n%%l+(n%/%l*2*l))

```

Try it online!

~~Either I'm doing something really wrong or R is just terrible at bit manipulation.~~ Porting Luis Mendo's approach is easy, correct, and golfy.

But if you really just want to muck around with bit operations, MickyT suggested the following 105 byter:

```
function(i)sum(sapply(1:max(which(b<-intToBits(i)>0)),function(x)packBits(head(append(b,F,x),-1),"i")))-i

```

Try it online!

# Answer
> 1 votes
# Python 3, ~~92~~ ~~80~~ 78 bytes

```
def b(x):x=f'{x:b}';return sum(int(x[:i]+'0'+x[i:],2)for i in range(1,len(x)))

```

Try It Online

Thanks to Mr.XCoder and ovs for -12 bytes and -2 bytes respectively.

# Answer
> 1 votes
# 05AB1E, 14 bytes

```
.²LoDŠ‰ø`r·*+O

```

Try it online!

# Answer
> 1 votes
## Batch, ~~92~~ 77 bytes

```
@set/an=2,t=0
:l
@if %1 geq %n% set/at+=%1*2-(%1%%n),n*=2&goto l
@echo %t%

```

Edit: Switched to the same formula everyone else is using.

# Answer
> 1 votes
# Pip, ~~21~~ 18 bytes

```
2*a-a%2**_MS1,#TBa

```

Try it online!

### Explanation

Call our input number `a`. For each binary index `i` at which we want to insert a zero, we can calculate the bits left of the insertion point as `a // 2**i` (where `//` is integer division and `**` is exponentiation), the bits right of the insertion point as `a % 2**i`, and therefore the diluted integer as `2 * (a // 2**i) * 2**i + (a % 2**i)`. But `(a // 2**i) * 2**i` is equal to `a - (a % 2**i)`, and so we can rearrange to a shorter formula: `2 * (a - a % 2**i) + a % 2**i` = `2 * a - a % 2**i`.

```
2*a-a%2**_MS1,#TBa
                       a is 1st command-line argument (implicit)
               TBa     Convert a to binary
              #        Length of the binary expansion
            1,         Range from 1 up to (but not including) that number
          MS           Map this function to the range and sum the results:
2*a-a%2**_              The above formula, where _ is the argument of the function
                       The final result is autoprinted

```

# Answer
> 0 votes
# Jelly, 14 bytes

```
BLḊṬœṗ¥€Bj€0ḄS

```

Try it online!

# Answer
> 0 votes
# Perl 5, 36 + 1 (`-p`) = 37 bytes

```
$\+=$_*2-($_&$.-1)while($.*=2)<=$_}{

```

Try it online!

# Answer
> 0 votes
# Attache, 57 bytes

```
Sum##UnBin=>{Join[Join=>_,"0"]}=>SplitAt#1&`:@{#_-1}##Bin

```

Try it online!

I thought I'd approach the problem from a non-bit manipulation approach, as such an approach is impractical in Attache. I have to investigate some of the parts of this approach for alternatives.

## Explanation

Here is an expanded version:

```
Define[$joinByZero, {Join[Join=>_,"0"]}]

Define[$insertionPoints,
    SplitAt#1&`:@{#_-1}
]

Define[$f,
Sum##UnBin=>joinByZero=>insertionPoints##Bin
]

```

This simply takes the binary representation of the number, splits it at certain points, inserts zeroes there, converts back to decimal, and sums them together.

# Answer
> 0 votes
# , 33 bytes

```
1#.[:}:#.@(<\;@(,0;])"0<@}.\.)@#:

```

Most probably there is much room for further golfing.

## How?

`@#:` convert to binary and

`<@}.\.` \- find all suffices, drop the first digit from each and box

`<\` \- find all prefixes and box them

`(,0;])"0` \- to each prefix append 0 then append the corresponding beheaded suffix

`;@` raze (unbox)

`1#.[:}:#.@` \- convert to decimal, curtail and sum

Try it online!

---
Tags: code-golf, arithmetic, number-theory, binary
---


# Question
Title: I want my book to be away from this table
**Story**

So I have a book that I want to separate from my table with nothing but other books. I want to know how many books do I need to achieve this with \\$n\\$ book lengths.

Here's a visualization that my friend at Wolfram drew for me:

More information about the topic in Wolfram and Wikipedia.

**Challenge**

Given an integer input \\$n\\$, output how many books needed for the top book to be \\$n\\$ book length away from the table horizontally.
*or*
Find the smallest integer value of \\$m\\$ for input \\$n\\$ in the following inequality. $$\sum\_{i=1}^{m}\frac{1}{2i} \geq n$$

***Edit:*** for fractions use at least a IEEE single-precision floating point. sorry for editing challenge after posting

(OEIS A014537)

**Test cases**

```
 1          4
 2         31
 3        227
 5      12367
10  272400600

```

# Answer
> 13 votes
# Octave, ~~41~~ ~~40~~ 33 bytes

*1 byte saved thanks to @Dennis*

```
@(n)find(cumsum(.5./(1:9^n))>n,1)

```

**Try it online!**

### Explanation

This uses the fact that harmonic numbers can be lower-bounded by a logarithmic function.

Also, the `>=` comparison can be replaced by `>` because harmonic numbers cannot be even integers (thanks, @Dennis!).

```
@(n)                                   % Anonymous function of n
                     1:9^n             % Range [1 2 ... 9^n]
                .5./(     )            % Divide .5 by each entry
         cumsum(           )           % Cumulative sum
                            >n         % Is each entry greater than n?
    find(                     ,1)      % Index of first true entry

```

# Answer
> 11 votes
# Python 3, 35 bytes

```
f=lambda n,k=2:n>0and-~f(n-1/k,k+2)

```

Try it online!

# Answer
> 10 votes
# Husk, 8 bytes

```
V≥⁰∫m\İ0

```

Try it online!

Since Husk uses rational numbers when it can, this has no floating point issues

### Explanation

```
      İ0    The infinite list of positive even numbers
    m\      Reciprocate each
   ∫        Get the cumulative sum
V           Find the index of the first element
 ≥⁰         that is greater than or equal to the input

```

# Answer
> 5 votes
# JavaScript, 30 bytes

A recursive function so it'll crap out pretty early.

```
f=(n,x=0)=>n>0?f(n-.5/++x,x):x

```

Try it online

# Answer
> 4 votes
# Haskell, 38 bytes

```
k!n|n<=0=0|x<-n-1/(2*k)=1+(k+1)!x
(1!)

```

# Answer
> 3 votes
# Javascript (ES6), 34 bytes

```
n=>eval("for(i=0;n>0;n-=.5/i)++i")

```

### Ungolfed

```
n => {
    for(i = 0; n > 0; ++i)
        n -= .5 / i
    return i;
}

```

### Test Cases

```
f=n=>eval("for(i=0;n>0;n-=.5/i)++i")
```

```
<button onclick="console.log(f(1))">Run for n = 1</button>
<button onclick="console.log(f(2))">Run for n = 2</button>
<button onclick="console.log(f(3))">Run for n = 3</button>
<button onclick="console.log(f(5))">Run for n = 5</button>
<button onclick="console.log(f(10))">Run for n = 10</button>
```

# Answer
> 3 votes
# Swift, 65 bytes

```
func f(n:Double){var i=0.0,s=i;while s<n{i+=1;s+=0.5/i};print(i)}

```

Try it online!

### Ungolfed

```
func f(n:Double) {
  var i = 0.0, s = 0.0
  while s < n {
    i += 1;
    s += 0.5 / i
  }
  print(i)
}

```

# Answer
> 3 votes
# , 39 bytes

```
function(n){while((F=F+.5/T)<n)T=T+1;T}

```

Try it online!

Brute Force!

# Answer
> 2 votes
# Jelly, 8 bytes

```
RİSH:ð1#

```

This is *very* slow.

Try it online!

# Answer
> 2 votes
# Haskell, ~~71~~ ~~49~~ 48 bytes

```
f x=length.fst.span(<x).scanl(+)0$(0.5/)<$>[1..]

```

@BMO saved me a whopping 22 bytes!

# Answer
> 2 votes
# Julia 0.6, ~~30~~ 27 bytes

```
<(n,i=1)=n>0?n-.5/i<i+1:i-1

```

Try it online!

Only works up to `n = 6`, because Julia has no tail call optimization.

-3 bytes thanks to Dennis.

# Answer
> 2 votes
# TI-BASIC, 27 bytes

Prompts user for input and displays output on termination. Note: `⁻¹` is the -1 (inverse) token.

```
Input N
1
Repeat 2N≤Σ(I⁻¹,I,1,Ans
Ans+1
End
Ans

```

# Answer
> 1 votes
# Japt, 12 bytes

The same length as, but slightly more efficient than, the recursive option.

```
@T¨(Uµ½÷X}a1

```

Try it

---

## Explanation

```
@T¨(Uµ½÷X}a1
                 :Implicit input of integer U
@        }a1     :Return the first number X >=1 that returns truthy when passed through the following function
 T               :Zero
  ¨              :Greater than or equal to
    Uµ           :Decrement U by...
      ½÷X        :0.5 divided by X

```

# Answer
> 1 votes
# 05AB1E, 11 bytes

```
XµN·zODI›}N

```

Try it online!

**Explanation**

```
Xµ       }    # loop until counter is 1
  N·z         # push 1/(2*N)
     O        # sum the stack
      DI›     # break if the sum is greater than the input
          N   # push N

```

# Answer
> 1 votes
# Pyth, 10 bytes

```
f!>Qsmc1yh

```

Try it online!

Extremely slow.

# Pyth, 10 bytes

```
fgscL1STyQ

```

Try it online!

# Answer
> 1 votes
# J, 22 bytes

*-6 bytes thanks to frownyfrog*

```
I.~0+/\@,1%2*1+[:i.9&^

```

Try it online!

## original answer

Luis's answer in J:

```
1+]i.~[:<.[:+/\1%2*1+[:i.9&^

```

## Ungolfed

```
1 + ] i.~ [: <. [: +/\ 1 % 2 * 1 + [: i. 9&^

```

Mostly curious to see if it can be drastically improved (*cough* paging miles)

## Explanation

```
1 +      NB. 1 plus...
] i.~    NB. find the index of the arg in...
[: <.    NB. the floor of...
[: +/\   NB. the sumscan of...
1 %      NB. the reciprical of...
2 *      NB. two times...
1 +      NB. 1 plus...
[: i.    NB.  the integers up to
9&^      NB. 9 raised to the power of the arg

```

Try it online!

# Answer
> 0 votes
# PHP, 35 bytes

```
while($argv[1]>$s+=.5/++$i);echo$i;

```

Run it using the CLI:

```
$ php -d error_reporting=0 -r 'while($argv[1]>$s+=.5/++$i);echo$i;' 5

```

# Answer
> 0 votes
# Wolfram Language (Mathematica), 40 bytes

```
⌈x/.NSolve[HarmonicNumber@x==2#,x]⌉&

```

Try it online!

# Answer
> 0 votes
# Java 8, 49 bytes

```
n->{float r=0,s=0;for(;s<n;)s+=.5f/++r;return r;}

```

**Explanation:**

Try it online. (Times out for test cases above `n=7`.)

```
n->{             // Method with integer parameter and float return-type
  float r=0,     //  Result-float, starting at 0
        s=0;     //  Sum-float, starting at 0
  for(;s<n;)     //  Loop as long as the sum is smaller than the input
    s+=.5f/++r;  //   Increase the sum by `0.5/(r+1)`,
                 //   by first increasing `r` by 1 with `r++`
  return r;}     //  Return the result-float

```

# Answer
> 0 votes
# tinylisp, 98 bytes

```
(load library
(d _(q((k # N D)(i(l N(* D # 2))(_(inc k)#(+(* N k)D)(* D k))(dec k
(q((#)(_ 1 # 0 1

```

The last line is an unnamed lambda function that takes the number of book-lengths and returns the number of books needed. Try it online!

### Explanation

The only numeric data type tinylisp has is integers, so we calculate the harmonic series as a fraction by keeping track of the numerator and denominator. At each step, `N` is the numerator, `D` is the denominator, and `k` is the sum index. We want the new partial sum to be `N/D + 1/k`, or `(N*k + D)/(D*k)`. Thus, we recurse with a new numerator of `N*K + D`, a new denominator of `D*k`, and a new index of `k+1`.

The recursion should halt once the partial sum is greater than or equal to `#`, the desired number of book-lengths. At this point, we've gone one book too far, so we return `k-1`. The condition is `1/2 * N/D < #`; multiplying out the denominator, we get `N < D*#*2`, which is the golfiest way to write it.

The recursive helper function `_` does all these calculations; the main function is merely a one-argument wrapper that calls `_` with the correct starting values for `k`, `N`, and `D`.

---
Tags: code-golf, math, number, sequence, rational-numbers
---


title: Reverse columns while preserving shape

text:
# Question
Title: Reverse columns while preserving shape
## Introduction

Suppose you have a list of lists of integers (or any objects really, but let's stick to integers for simplicity). The lists may be of different lengths, and some of them may be empty. Let's write the lists in a tabular format:

```
[[ 1,   2,   3,   4,   5],
 [ 6,   7],
 [ 8,   9,  10,  11],
 [],
 [12,  13,  14],
 [15,  16,  17,  18]]

```

This table has 5 vertical columns, containing the numbers `1, 6, 8, 12, 15`, `2, 7, 9, 13, 16`, `3, 10, 14, 17`, `4, 11, 18`, and `5`. If we reverse each column, we obtain the lists `15, 12, 8, 6, 1`, `16, 13, 9, 7, 2`, `17, 14, 10, 3`, `18, 11, 4`, and `5`. Let's plug those numbers back into the columns of the table while keeping the lengths of the rows the same as before:

```
[[15,  16,  17,  18,   5],
 [12,  13],
 [ 8,   9,  14,  11],
 [],
 [ 6,   7,  10],
 [ 1,   2,   3,   4]]

```

Your task is to implement this operation.

## Input and output

Your input is a list of lists of nonnegative integers, representing the rows. The rows may have different lengths, and some of them may be empty. There will always be at least one row. Your output is the result of reversing each column, as detailed above. Input and output may be in any reasonable format.

The lowest byte count in each language wins. Standard rules apply.

## Test cases

```
[[]] -> [[]]
[[],[]] -> [[],[]]
[[8,5,1]] -> [[8,5,1]]
[[1,200],[0,3]] -> [[0,3],[1,200]]
[[],[3,9],[1],[]] -> [[],[1,9],[3],[]]
[[],[5,8,7],[0,6,5,7,1]] -> [[],[0,6,5],[5,8,7,7,1]]
[[1,8,5],[7,5,4],[],[1]] -> [[1,5,4],[7,8,5],[],[1]]
[[],[],[2],[],[31],[],[5],[],[],[],[7]] -> [[],[],[7],[],[5],[],[31],[],[],[],[2]]
[[1,10,100,1000],[2,20,200],[3,30],[4],[5,50,500],[6,60],[7]] -> [[7,60,500,1000],[6,50,200],[5,30],[4],[3,20,100],[2,10],[1]]
[[8,4],[3,0,4,8,1],[8],[0,8],[9,7,1,6],[3,8,1,9,5]] -> [[3,8],[9,7,1,9,5],[0],[8,8],[3,0,1,6],[8,4,4,8,1]]
[[3,9,3],[5],[1],[3,5],[9,0,6,2],[1,3],[4,9,2],[6,6,7,8,7]] -> [[6,6,7],[4],[1],[9,9],[3,3,2,8],[1,0],[5,5,6],[3,9,3,2,7]]
[[8,5,6],[3,5,2,4,9],[4,3,8,3,7],[6,1,1],[1,8,9,9],[9,1,2],[8,7]] -> [[8,7,2],[9,1,9,9,7],[1,8,1,3,9],[6,1,8],[4,3,2,4],[3,5,6],[8,5]]
[[2,4],[1,4],[0,8,7,3],[4,9,2,5],[2,8,0],[0,8,3],[7,3,1],[],[3,3,7,8]] -> [[3,3],[7,3],[0,8,7,8],[2,8,1,5],[4,9,3],[0,8,0],[1,4,2],[],[2,4,7,3]]

```

# Answer
# Jelly, 16 bytes

```
ḟṚṁṣj
z-ç€-ZFḟ-ṁ

```

Try it online! or verify all test cases.

### How it works

```
z-ç€-ZFḟ-ṁ  Main link. Argument: M (matrix / 2D array)

z-          Zip the rows of M, using -1 as filler.
  ç€-       Map the helper link over the result, with right argument -1.
     Z      Zip the rows of the result.
      F     Flatten the resulting matrix.
       ḟ-   Filterfalse -1; remove all occurrences of -1.
         ṁ  Mold; shape the result like M.

ḟṚṁṣj       Helper link.
            Left argument: A (row / 1D array). Right argument: -1

ḟ           Filterfalse; remove all occurrences of -1.
 Ṛ          Reverse the resulting vector.
   ṣ        Split A at occurrences of -1.
  ṁ         Mold; shape the vector to the left like the 2D array to the right.
    j       Join the resulting 2D array, separating by -1.

```
> 5 votes

# Answer
# APL (Dyalog Unicode), ~~20~~ ~~19~~ 16 bytesSBCS

-4 thanks to ngn.

Full program. Prompts for input from STDIN.

```
⍟0~¨⍨↓⍉⌽@×⍤1⍉↑*⎕

```

Try it online!

**Explanation with example walk-through**

prompt for evaluated input
`[[1,8,5],[7,5,4],[],[1]]`

`*` raise *e* to the power of that (*e*n which ensures that there will be no zeros)
`[[2.7,2981,148.4],[1096.6,148.4,54.6],[],[2.7]]`

mix the lists into a single matrix, padding with zeros:
`┌ ┐`
`│2.7E0 3.0E3 1.5E2│`
`│1.1E3 1.5E2 5.5E1│`
`│0.0E0 0.0E0 0.0E0│`
`│2.7E0 0.0E0 0.0E0│`
`└ ┘`

transpose
`┌ ┐`
`│2.7E0 1.1E3 0.0E0 2.7E0│`
`│3.0E3 1.5E2 0.0E0 0.0E0│`
`│1.5E2 5.5E1 0.0E0 0.0E0│`
`└ ┘`

`⌽@×⍤1` reverse the positive elements of each row
`┌ ┐`
`│2.7E0 1.1E3 0.0E0 2.7E0│`
`│1.5E2 3.0E3 0.0E0 0.0E0│`
`│5.5E1 1.5E2 0.0E0 0.0E0│`
`└ ┘`

transpose
`┌ ┐`
`│2.7E0 1.5E2 5.5E1│`
`│1.1E3 3.0E3 1.5E2│`
`│0.0E0 0.0E0 0.0E0│`
`│2.7E0 0.0E0 0.0E0│`
`└ ┘`

split the matrix into a list of lists
`[[2.7,148.4,54.6],[1096.6,2981,148.4],[0,0,0],[2.7,0,0]]`

`0~¨⍨` remove zeros from each list
`[[2.7,148.4,54.6],[1096.6,2981,148.4],[],[2.7]]`

natural logarithm
`[[1,5,4],[7,8,5],[],[1]]`
> 5 votes

# Answer
# Japt, ~~15~~ 13 bytes

*saved 2 bytes thanks to @Shaggy*

```
y@=XfÊX£o
®fÄ

```

Test it online!

The second line can be removed if we are allowed to pad the rows with null values, saving 4 bytes.

### Explanation

```
 y@  =XfÊ X£  o      Implicit: U = input array
UyX{U=Xfl Xm{Uo}}    (Ungolfed)
UyX{            }    Map each column X in the input by this function:
    U=Xfl              Set U to X filtered to only items whose factorial is truthy;
                       this just gets rid of the empty slots in the column.
          Xm{  }       Map each item in X to
             Uo          the last item in U, popping this item from the list.
                       Due to the way .map works in JS, this is only called on real items
                       and not empty slots, so this preserves empty slots.
                     Newline: set U to the resulting column-reversed array
 ®   fÄ              Due to the way y works, there will now be `undefined` in some rows.
UmZ{Zf+1}            (Ungolfed)
 mZ{    }            Map each row Z in U to
    Zf+1               Z filtered to only items where the item + 1 is truthy.
                     undefined + 1 is NaN, which is falsy, and thus eliminated.
                     Implicit: output result of last expression

```
> 4 votes

# Answer
# K4, 36 bytes

**Solution:**

```
+{x[w]:|x w:&~^x;x}'x'[::;]@!|/#:'x:

```

**Examples:**

```
q)k)+{x[w]:|x w:&~^x;x}'x'[::;]@!|/#:'x:(1 2 3 4 5;6 7;8 9 10 11;0#0N;12 13 14;15 16 17 18)
15 16 17 18 5
12 13
8  9  14 11

6  7  10
1  2  3  4

q)k)+{x[w]:|x w:&~^x;x}'x'[::;]@!|/#:'x:(0#0N;5 8 7; 0 6 5 7 1)

0 6 5
5 8 7 7 1

```

**Explanation:**

This one has been a pain, and I'm still working to simplify the elided indexing.

Instead of indexing in at, for example, `x[0]` which would return the first *row*, we want to take the first *column*, which can be done using `x[;0]`.

However passing variable `y` into `x[;]` treats it as doing `x[y]` not `x[;y]` hence shoving the `::` in there: `x[::;]`.

This is equivalent to flipping the list of lists, but flip requires all lists to be equal length!

```
+{x[w]:|x w:&~^x;x}'x'[::;]@!|/#:'x: / the solution
                                  x: / save input as variable x
                               #:'   / count (#:) each (')
                             |/      / take the max of these lengths
                            !        / til, range 0..max-1
                           @         / apply (index into)
                      [::;]          / :: is a kind of null,
                    x'               / index into x at each of these
 {              ; }'                 / two statement lambda on each (')
              ^x                     / null x (returns true if entry is null)
             ~                       / not, so flip true/false
            &                        / where, indexes where true
          w:                         / save as variable w
        x                            / index into w at these indexes
       |                             / reverse
  x[w]:                              / store this back in variable x at indexes w
                 x                   / return x from function
+                                    / flip the result

```
> 3 votes

# Answer
# Haskell, 174 bytes

```
f x=map g.h.map(g.reverse>>=(!)).h$take(maximum$length<$>x).(++z).map pure<$>x
g=concat
h x|g x==[]=x|4>2=foldr(zipWith(:))z x
x!(c:d)|c==[]=c:x!d|a:b<-x=[a]:b!d
_!y=y
z=[]:z

```

Try it online!

### Ungolfed/Explanation

The idea is to wrap all elements in `[]` and pad the rows with `[]` (turned out to be shorter than padding with a negative integer, this allows negative inputs as well which is nice), then transpose, reverse all rows and transpose again and flatten each row:

```
map concat                                   -- flatten each row
  . transpose'                               -- transpose (*)
  . map (\row-> reverse (concat row) ! row)  -- reverse each row (see below)
  . transpose'                               -- tranpose (*)
  $ take (maximum $ length <$> x)            -- only keep up as many as longest row
      . (++ z)                               -- pad row with [],[],..
      . map (\e-> [e])                       -- wrap elements in []
 <$> x

```

* This transpose function (`h`) simply returns the list if there are no elements at all.

The reverse function has to ignore `[]` elements (eg. `[[],[1],[],[3],[4]]` -\> `[[],[4],[],[3],[1]]`), it does so by receiving two arguments: The first one are the elements in reverse order (eg. `[4,3,1]`) and the second one the original row.

```
x@(a:b) ! (c:d)
 | c == []   = c:x ! d    -- if current element is []: skip it
 | otherwise = [a]:b ! d  -- else: replace with new one (a) and continue
_ ! y = y                 -- base case (if no new elements are left): done

```
> 3 votes

# Answer
# Python 2, ~~111~~ ~~105~~ 92 bytes

```
def f(l):x=map(lambda*n:[v for v in n if-1<v],*l);return[map(list.pop,x[:len(k)])for k in l]

```

Try it online!
> 2 votes

# Answer
## JavaScript (ES6), ~~79~~ 76 bytes

```
(a,d=[],g=s=>a.map(b=>b.map((c,i)=>(d[i]=d[i]||[])[s](c))))=>g`push`&&g`pop`

```

Edit: Saved 3 bytes thanks to @ETHproductions.
> 2 votes

# Answer
# APL (Dyalog Unicode), 27 bytesSBCS

```
≢¨⍴¨∘↓∘⍉⍉∘↑{⍵\⌽⍵/⍺}⍤1∘⍉∘↑=⍨

```

Try it online!
> 1 votes

# Answer
## Clojure, 123 bytes

```
#(map(fn[i R](map(fn[j _](let[V(for[Q %](get Q j))F filter](nth(reverse(F + V))(count(F +(take i V))))))(range)R))(range)%)

```

I was expecting `(+ nil)` to throw an exception, but it evaluates to `nil` :o

This operates without padding, instead it counts how many of the previous rows are at least as long as the current row `R`.
> 0 votes

---
Tags: code-golf, array
---


title: Generate me a QFP chip!

text:
# Question
Title: Generate me a QFP chip!
# Generate me a QFP chip!

From the sandbox!

QFP is a type of form factor for an electrical component where pins come out the sides of a chip. Here are is a picture of a typical QFP component:

you can see that the general formula is to have 4 sides of equal numbers of pins.

Your challenge is to create a program that takes in an integer, thich represents the number of pins on one side, and creates an ASCII QFP component with numbered pins.

## Input:

a single integer which represents the number of pins on one side

## Output:

An ASCII QFP chip with an apropriate pinout.

## Example:

input:1

```
  4
 ┌┴┐
1┤ ├3
 └┬┘
  2

```

input:2

```
  87
 ┌┴┴┐
1┤  ├6
2┤  ├5
 └┬┬┘
  34

```

input:12

```
   444444444333
   876543210987
  ┌┴┴┴┴┴┴┴┴┴┴┴┴┐
 1┤            ├36
 2┤            ├35
 3┤            ├34
 4┤            ├33
 5┤            ├32
 6┤            ├31
 7┤            ├30
 8┤            ├29
 9┤            ├28
10┤            ├27
11┤            ├26
12┤            ├25
  └┬┬┬┬┬┬┬┬┬┬┬┬┘
   111111122222
   345678901234

```

## Rules:

* all QFP chips must be enclosed and sealed as well as ascii provides. spacing is of utmost importance. Dust inside a microprocessor is bad stuff!
* pin numbering must be done as in the examples (Read left to right, top to bottom, numbered counter clockwise)
* You may start numbering at 0, but this must not affect the chip (an input of 12 still needs 12 pins per side)
* The only valid characers in your output are `1,2,3,4,5,6,7,8,9,0,┌,┴,┐,├,┘,┬,└,┤`, spaces, and newlines.
* all encodings for languages are allowed, but your output MUST be consistent with the rules above.

This is a codegolf, and as such, The code with the least number of bytes wins! Good Luck!

# Answer
> 3 votes
# Mathematica, 271 bytes

```
c=Table;d=StringPadLeft[#<>"\n",(b=IntegerLength[4a])+a+2]&/@(#)&;d@Reverse@#4<>{e=" "~c~b,"┌"<>"┴"~c~a,"┐
",({#,"┤"," "~c~a,"├",#2,"
"}&)~MapThread~{#,Reverse@#3},e,"└","┬"~c~a,"┘
",d@#2}&@@Partition[Characters@StringPadLeft[ToString/@Range[4#]],a=#]&

```

Anonymous function. Takes a number as input and returns a string as output. The non-box-drawing Unicode character is U+F3C7 (private use) for `\[Transpose]`.

# Answer
> 7 votes
# Kotlin, 397 393 bytes

Unnamed lambda.

You can try it here, but you'll have to paste the source in yourself because the editor doesn't seem to save programs in UTF-8 encoding. The ungolfed version is a full program, so you should be able to use that in its entirety.

**Golfed**

```
{n:Int->operator fun String.mod(x:Int){(1..x).map{print(this)}};val l={s:String->s.padStart(n/10+2)};var s=(1..n).map{"${n*4+1-it}".reversed()};val z={i:Int->l(" ")%1;s.map{print(it.getOrElse(i,{' '}))};"\n"%1};(s[0].length-1 downTo 0).map(z);l("┌")%1;"┴"%n;"┐\n"%1;(1..n).map{l("$it┤")%1;" "%n;"├${n*3+1-it}\n"%1};l("└")%1;"┬"%n;"┘\n"%1;s=(1..n).map{"${n+it}"};(0..s.last().length-1).map(z)}

```

**(Sort of) Ungolfed**

```
fun main(args: Array<String>) {
    var q = { n: Int ->
        operator fun String.mod(x: Int) {
            (1..x).map { print(this) }
        }

        val l = { s: String ->
            s.padStart(n / 10 + 2)
        }

        var s = (1..n).map { "${n * 4 + 1 - it}".reversed() }

        val z = { i: Int ->
            l(" ")%1
            s.map { print(it.getOrElse(i, { ' ' })) }
            "\n"%1
        }

        (s[0].length - 1 downTo 0).map(z)

        l("┌")%1
        "┴"%n
        "┐\n"%1

        (1..n).map { l("$it┤") % 1;" " % n;"├${n * 3 + 1 - it}\n" % 1 }

        l("└")%1
        "┬"%n
        "┘\n"%1

        s = (1..n).map { "${n + it}" }
        (0..s.last().length - 1).map(z)
    }

    q(30)
}

```

Saved a bunch of bytes by overloading the `%` operator and using it to print. I'll probably revisit this later - I think I can save quite a few bytes if I use `mod` or some other operator as a concatenation function. More interpolation and less print calls.

# Answer
> 3 votes
## Python 2, ~~352~~ ~~343~~ 331 bytes

```
def q(n,j=''.join,k='\n'.join,m=map):a,b,c,d=zip(*[iter(m(str,range(n*4)))]*n);l=len(`n-1`);r=lambda x:k(m(lambda s:' '*(l+1)+j(s),m(j,[m(lambda t:t or' ',v)for v in m(None,*x)])));return k([r(d[::-1]),' '*l+u'┌'+u'┴'*n+u'┐',k(x.rjust(l)+u'┤'+' '*n+u'├'+y for x,y in zip(a,c[::-1])),' '*l+u'└'+u'┬'*n+u'┘',r(b)])

```

Try it here. Note the file must start with the UTF-8 BOM `\xef\xbb\xbf` for the unicode literals to work in the standard CPython interpreter. These 3 bytes are counted against the size here. `repl.it` is already using unicode so the link just has the code shown here.

Thanks @tuskiomi for the encoding idea that saved ~~9~~ 21 bytes.

Partially ungolfed:

```
def q(n):
  a,b,c,d = zip(*[iter(map(str,range(n*4)))]*n) # get numbers for sides
  l = len(`n-1`) # left padding
  r = lambda x: '\n'.join(
    map(lambda s: ' '*(l+1) + ''.join(s), # padding and row of digits
      map(''.join,
        [map(lambda t: t or ' ', v)  # rows of digits with spaces where missing
          for v in map(None, *x)]))
  )
  return '\n'.join([
    r(d[::-1]), # top row in reverse order
    ' '*l+u'\u250c'+u'\u2534'*n+u'\u2510', # top border
    # 1st, 3rd (reversed) side numbers
    '\n'.join(x.rjust(l) + u'\u2524'+ ' '*n + u'\u251c' + y for x,y in zip(a,c[::-1])),
     ' '*l+u'\u2514'+u'\u252c'*n+u'\u2518', # bottom border
    r(b) # bottom numbers
  ])

```

# Answer
> 3 votes
## JavaScript (ES6), ~~295~~ 284 bytes (268 chars), non-competing

```
n=>(a=[...(' '[r='repeat'](W=n+6)+`
`)[r](W++)],a.map((_,i)=>i<n*2&&([p,s,L,R,C]=i<n?[(i+3)*W-1,1,i+1,n*3-i,0]:[i-n+3-W,W,n*5-i,i+1,1],[...(' '+L).slice(-2)+'┤┴'[C]+' '[r](n)+'├┬'[C]+R].map(c=>a[p+=s]=c))),[2,3,W-4,W-3].map((p,i)=>a[W*p+2-6*(i&1)]='┌┐└┘'[i]),a.join``)

```

This code doesn't support pin numbers above 99 and therefore probably doesn't qualify as a fully valid entry. That's why I mark it as non-competing for now.

It could be easily modify to support an arbitrary large number of pins by using wider static margins around the chip. However, that may infringe the rules as well (not sure about that). Fully dynamic margins would cost significantly more bytes.

## Demo

```
let f =

n=>(a=[...(' '[r='repeat'](W=n+6)+`
`)[r](W++)],a.map((_,i)=>i<n*2&&([p,s,L,R,C]=i<n?[(i+3)*W-1,1,i+1,n*3-i,0]:[i-n+3-W,W,n*5-i,i+1,1],[...(' '+L).slice(-2)+'┤┴'[C]+' '[r](n)+'├┬'[C]+R].map(c=>a[p+=s]=c))),[2,3,W-4,W-3].map((p,i)=>a[W*p+2-6*(i&1)]='┌┐└┘'[i]),a.join``)

console.log(f(2))
console.log(f(4))
console.log(f(12))
```

# Answer
> 1 votes
# Java 11, ~~451~~ ~~425~~ 393 bytes

```
n->{int d=(n+"").length(),i,j=-1,l=(int)Math.log10(n*4);String p=" ".repeat(d),P=p+" ",r=P;for(;j++<l;r+="\n"+(j<l?P:p))for(i=n*4;i>n*3;)r+=(i--+"").charAt(j);r+="┌"+"┴".repeat(n)+"┐\n";for(i=0;i<n;r+="├"+(n*3-i+++1)+"\n")r+=p.substring((i+"").length())+i+"┤"+" ".repeat(n);r+=p+"└"+"┬".repeat(i)+"┘\n"+P;for(j=-1;j++<l;r+="\n"+P)for(i=n;i<n*2;)r+=(++i+"").charAt(j);return r;}

```

-26 bytes thanks to *@ceilingcat*.

**Explanation:**

Try it online.

```
n->{                      // Method with integer parameter and String return-type
  int d=(n+"").length(),  //  The amount of digits of the input
      i,j=-1,             //  Index integers
      l=(int)Math.log10(n*4);
                          //  Amount of digits of 4x the input, minus 1
  String p=" ".repeat(d), //  Padding String for the corners, set to `d` amount of spaces
         P=x+" ",         //  Padding String for the numbers, set to one additional space
         r=P;             //  Result-String, starting at `P` to pad the number
  for(;j++<l;             //  Loop `j` in the range (-1, l]:
      ;                   //    After every iteration:
       r+="\n"            //     Append a new-line, and padding spaces:
       +(j<l?P:p))        //      `p` if it's the last iteration; `P` otherwise
    for(i=n*4;i>n*3;      //   Inner loop `i` in the range [4n, 3n):
      r+=(i--+"")         //    Convert the current number to a String,
         .charAt(j));     //    and append the `j`'th digit to the result-String
  r+="┌"                  //  Append the top-left corner of the chip
     +"┴".repeat(n)       //  Append the top row of the chip
     +"┐\n";              //  Append the top-right corner of the chip, plus a new-line
  for(i=0;i<n             //  Loop `i` in the range [0, n):
      ;                   //    After every iteration:
       r+="├"             //     Append the right border of the chip
          +(n*3-i+++1)    //     Append the number
          +"\n")          //     And a trailing newline
    r+=p.substring((i+"").length())
                          //   Append padding spaces in front of the left number
       +i                 //   Append the current number
       +"┤"               //   Append the left border of the chip
       +" ".repeat(n);    //   Append the inner spaces
  r+=p                    //  Append padding spaces in front of the corner
     +"└"                 //  Append the bottom-left corner of the chip
     +"┬".repeat(i)       //  Append the bottom part of the chip
     +"┘\n"               //  Append the bottom-right corner of the chip, plus a new-line
     +P;                  //  Append padding spaces in front of the bottom number
  for(j=-1;j++<l;         //  Loop `j` in the range (-1, l]:
      ;                   //    After every iteration:
       r+="\n"            //     Append a new-line
          +P)             //     Append padding spaces for the number
    for(i=n;i<n*2;        //   Inner loop `i` in the range [n, 2n):
      r+=(++i+"")         //    Convert the current number to a String,
         .charAt(j));     //    and append the `j`'th digit to the result-String
  return r;}              //  Return the result-String

```

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


title: Palindrome Compression

text:
# Question
Title: Palindrome Compression
# Challenge

Write a program that compresses and decompresses ASCII text losslessly. It should be specialized to work well with palindromes, including case-insensitive and punctuation-insensitive palindromes. The best compression with the smallest source wins.

## Scoring

`total_bytes_saved / sqrt(program_size)` \- Highest score wins

`total_bytes_saved` is how many bytes smaller the compressed strings are than the originals, total across the test cases below. `program_size` is the size in bytes of the source code of both the compression and decompression programs. Code shared between the two need only be counted once.

For instance, if there are 10 test cases and a 100 byte program saved 5 bytes on 7 test cases, 10 each on 2 of them, but the last test case was 2 bytes longer, the solution would score 5.3. (`(7 * 5 + 10 * 2 - 2) / sqrt(100) = 5.3`)

## Test Cases

* `tacocat`
* `toohottohoot`
* `todderasesareddot`
* `amanaplanacanalpanama`
* `wasitacaroracatisaw?`
* `Bob`
* `IManAmRegalAGermanAmI`
* `DogeeseseeGod`
* `A Santa at NASA`
* `Go hang a salami! I'm a lasagna hog.`

## Rules

1. Standard loopholes apply.
2. The compression must work on all printable ASCII (bytes 32-126, inclusive) text strings, not just palindromes. It doesn't actually have to save space for any inputs, however.
3. Output can be any sequence of bytes or characters, regardless of its implementation or internal representation (strings, lists, and arrays are all fair game, for instance). If encoding to UTF-8, count bytes, not characters. Wide strings (e.g. UTF-16 or UTF-32) are not allowed unless the only codepoints possibly used are between 0 and 255.
4. Compression/Decompression builtins are not allowed.

For the sake of our own enjoyment, post the compressed strings with your source code.

**UPDATE 1:** Scoring changed from `total_bytes_saved / program_size` to `total_bytes_saved / sqrt(program_size)` in order to give more weight to better compression and less weight to aggressive golfing. Adjust your scores accordingly.

**UPDATE 2:** fixed `wasitacaroraratisaw?` to be `wasitacaroracatisaw?`

# Answer
> 17 votes
## JavaScript (ES6), 3.143 (81 bytes saved, 664 byte program)

```
R='replace',S=String.fromCharCode,T=c=>c.charCodeAt(),U='toUpperCase',V='0000000',W=(a,b,c=2)=>a.toString(c).slice(b),X=x=>'0b'+x,Y=a=>[...a].reverse().join``,Z=/[^]/g
C=s=>S(...((Y(q=s[U]()[R](/[^A-Z]/g,m=''))==q?(q=q.slice(0,p=-~q.length/2),p%1&&10):11)+q[R](Z,x=>W(T(x),2))+111+s[R](Z,c=>/[a-z]/.test(c)?W("00",m,m=1):m+(/[A-Z]/.test(c,m='')?"01":W(c<'!'?2:T(c)+384)))+V).match(/(?!0+$).{8}/g).map(X))
D=s=>{s=s[R](Z,c=>W(256+T(c),1))+V;M=r=>(s=s[R](p=s.match(`^${r}|`)[0],''),p);for([,a]=M`1.|0`,t=u=i='';!M`111`;)t+=W(X(M`.{5}`)-~8,0,36);for(t+=W(Y(t),a?a/0:1);p;)u+=M`0(?=00)|00?1`?(c=t[i++])?+p[1]?c[U]():c:'':M`10`?' ':M`11`&&S(X(M`.{7}`));return u+W(t,i)}

```

Now that I'm fairly satisfied with this program (and the scoring system), I'll write a bit of an explanation.

The basic idea is to compress the input into a string of bits, then compress each set of 8 bits into a byte. For the purposes of explanation, I'll just manipulate the bit string.

The bit string can be separated into several sections:

```
input  -> Taco Cat.
output -> 0101000000100011011111110100001100100011101011100000000

0      | 10100 00001 00011 01111 111 | 01 00001 10 01 0001 110101110
header | letter data                 | styling data

```

The header is a very simple mapping:

```
0  -> odd-length palindrome
10 -> even-length palindrome
11 -> non-palindrome

```

Letter data is also fairly simple. First, all non-letters are extracted from the string, and all letters are converted to uppercase. If the resulting string is a palindrome, the reversed half is stripped. Then this mapping is applied:

```
A -> 00001
B -> 00010
C -> 00011
D -> 00100
...
Z -> 11010

```

This section is terminated with `111`. After that comes the styling data, which stores upper/lower-case data and non-letters. This works like so:

```
01 -> next letter as uppercase
0...01 (n 0s) -> next (n-1) letters as lowercase
10 -> space
11xxxxxxx -> character with code point 0bxxxxxxx

```

So going through the example shown above, we have

```
header: 0 -> palindrome
letter data: 10100 00001 00011 01111 111 -> taco
styling data:
  01        -> T
  00001     -> aco
  10        -> <space>
  01        -> C
  0001      -> at
  110101110 -> .

```

When the end of the bit string is reached, all remaining characters from the letter data are appended to the result. This saves us from having to do one last `000...001` and allows us to truncate these bits from the string.

Going through the test cases:

```
tacocat -> 3 bytes (-4)
    24 bits: 010100000010001101111111
toohottohoot -> 5 bytes (-7)
    35 bits: 10101000111101111010000111110100111
todderasesareddot -> 7 bytes (-10)
    49 bits: 0101000111100100001000010110010000011001100101111
amanaplanacanalpanama -> 8 bytes (-13)
    59 bits: 00000101101000010111000001100000110000001011100000100011111
wasitacaroracatisaw? -> 11 bytes (-9)
    84 bits: 010111000011001101001101000000100011000011001001111111000000000000000000001110111111
Bob -> 2 bytes (-1)
    16 bits: 0000100111111101
IManAmRegalAGermanAmI -> 13 bytes (-8)
    98 bits: 00100101101000010111000001011011001000101001110000101100111010100010100101000001010100000010100101
DogeeseseeGod -> 7 bytes (-6)
    54 bits: 000100011110011100101001011001100101111010000000000101
A Santa at NASA -> 8 bytes (-7)
    63 bits: 100000110011000010111010100000011110110010000011000011001010101
Go hang a salami! I'm a lasagna hog. -> 20 bytes (-16)
   154 bits: 1000111011110100000001011100011100001100110000101100000010110101001111010011000000110001100000000111010000110011101001110011000110000000001100000111010111

```

# Answer
> 2 votes
# Python 2: 2.765 (70 bytes saved, 641 byte program)

I changed my approach a little. It now works well on imperfect palindromes. There are no compressed strings that will be longer than the input. Perfect even-length palindromes will always compress to 50% the original size.

```
A=lambda x:chr(x).isalpha()
def c(s):
 r=bytearray(s);q=len(r);L=0;R=q-1;v=lambda:R+1<q and r[R+1]<15
 while L<=R:
  while not A(r[L])and L<R:L+=1
  while not A(r[R])and R:
   if v()and r[R]==32:r[R]=16+r.pop(R+1)
   R-=1
  j=r[L];k=r[R]
  if A(j)*A(k):
   if L!=R and j&31==k&31:
    r[L]+=(j!=k)*64;r[R]=1
    if v():r[R]+=r.pop(R+1)
   else:r[L]|=128;r[R]|=128
  L+=1;R-=1
 while r[-1]<16:r.pop()
 return r
def d(s):
 r='';t=[]
 for o in s:
  if 15<o<32:r+=' ';o-=16
  while 0<o<16:r+=chr(t.pop());o-=1
  if o==0:continue
  if 127<o<192:o-=64;t+=[o^32]
  elif o>192:o-=128
  elif A(o):t+=[o]
  r+=chr(o)
 while t:r+=chr(t.pop())
 return r

```

# Results

```
'tacocat' <==> 'tac\xef'
4/7 (3 bytes saved)
'toohottohoot' <==> 'toohot'
6/12 (6 bytes saved)
'todderasesareddot' <==> 'todderas\xe5'
9/17 (8 bytes saved)
'amanaplanacanalpanama' <==> 'amanaplana\xe3'
11/21 (10 bytes saved)
'wasitacaroracatisaw?' <==> 'wasita\xe3ar\xef\x09?'
12/20 (8 bytes saved)
'Bob' <==> '\x82\xef'
2/3 (1 bytes saved)
'IManAmRegalAGermanAmI' <==> 'I\x8d\xa1n\x81m\x92e\xa7\xa1\xec'
11/21 (10 bytes saved)
'Dogeeseseegod' <==> '\x84ogees\xe5'
7/13 (6 bytes saved)
'A Santa at NASA' <==> 'A S\xa1\xaeta\x12\x14'
9/15 (6 bytes saved)
"Go hang a salami! I'm a lasagna hog." <==> "\x87o hang a salam\xa9!\x11'\x01\x11\x17\x13."
24/36 (12 bytes saved)

```

And as a bonus, it saves 6 bytes on my incorrect palindrome I had before.

```
'wasita\xe3ar\xef\x02\xf2\x06?' <==> 'wasitacaroraratisaw?'
6 bytes saved

```

# Explanation

Decompression uses a stack. Codepoints from 32-127 are treated literally. If a character is a letter, a value is pushed onto the stack as well. Values 128-192 are used for case flipped letters, so the caseflipped letter (`o^32` because of how ASCII is laid out) gets pushed onto the stack and the normal letter gets added to the string. Values 192-255 are used to add letters without pushing to the stack, so this is used when letters do not match and for the middle letter in odd-length palindromes. Codepoints 1-15 indicate that the stack should be popped that number of times. Codepoints 17-31 are similar, but they print a space first before popping from the stack. There is also an implicit "pop until empty" instruction at the end of an input.

The compressor works from both ends and folds in matching letters as values 1-31. It skips over non-letters. When the letters match but the case does not, it adds 64 to the left letter and increments the right letter. This allows it to save space on `IManAmRegalAGermanAmI`. At the middle or when the letters do not match, it ors 128 to both sides. I can't add there because I need to avoid the special case where `left == right`. When folding neighboring pop markers on the right side, I have to check that the neighboring one won't overflow into codepoint 16 because I need that for spaces. (This is not actually an issue for any of the test case strings)

**EDIT 1**: No more ungolfed version.

# Answer
> 1 votes
# Python3, 1.833 (25 bytes saved, 186 byte program)

Just simple 0-order equal-probability entropy coding. No palindrome-specific optimizations.

```
def C(s):
    u=0
    for c in s:u=u*96+ord(c)-31
    return u.to_bytes((u.bit_length()+7)//8,'big')
def D(a):
    u,s=int.from_bytes(a,'big'),''
    while u:s,u=s+chr((u%96)+31),u//96
    return s[::-1]

```

# Answer
> 0 votes
# Java 8, score: 1.355 (20 bytes saved / 218 (107+111) bytes)

Compress function (contains three unprintable ASCII characters):

```
s->{int l=s.length();return s.contains(new StringBuffer(s).reverse())?s.substring(l/2)+(l%2<1?"":""):s;}

```

Decompress function (contains two unprintable ASCII characters):

```
s->{return s.contains("")?new StringBuffer((s=s.replaceAll("","")).substring(s.length()&1^1)).reverse()+s:s;}

```

**Explanation:**

Try it online.

Only compresses perfect palindromes.

```
s->{                      // Method with String as both parameter and return-type
  int l=s.length();       //  Get the length of the input
  return s.contains(new StringBuffer(s).reverse())?
                          //  If the input is a palindrome:
    s.substring(l/2)      //   Only return the second halve of the String
    +(l%2<1?"":"")        //   + either one (if even) or two (if odd) unprintables
   :                      //  Else:
    s;}                   //   Simply return the input again

s->{                      // Method with String as both parameter and return-type
  return s.contains("")?  //  If the input contains an unprintable:
    new StringBuffer((s=s.replaceAll("",""))
                          //   Remove the unprintables
                     .substring(s.length()&1^1))
                          //   And take either the full string (if even),
                          //   or minus the first character (if odd)
    .reverse()            //    And reverse that part
    +s                    //   And append the rest of the input (minus the unprintables)
   :                      //  Else:
    s;}                   //   Simply return the input again

```

---
Tags: code-challenge, compression
---


title: Low pass filter

text:
# Question
Title: Low pass filter
The goal of this challenge is to implement a digital low-pass filter.

You are free to implement any type of digital filter you want, however whatever results produced must pass the validation script below.

Here's a general description of what the validation script expects:

1. When an FFT is taken of the filtered signal, the filtered signal amplitude at any frequency bucket:
    1. If the input signal has a frequency bucket with a value below -80dB, then the output signal bucket needs only be at or below the -80dB level.
    2. A decade below the cutoff frequency must not differ from the source signal amplitude by more than 3dB at the corresponding frequency bucket.
    3. At or above the cutoff frequency must be at least 3dB below the source signal amplitude at the corresponding frequency bucket of the input signal.
2. The output signal must be in the time domain and have the same number of samples and sample rate as the input signal.
3. You need not preserve any phase information or worry about aliasing.
4. The output signal must consist of only finite real values (no NaN/ infinities).

# Input

Your program is given the following inputs:

* A time domain sampled signal consisting of real numbers representing the amplitude of the signal at the sample time. Your program will be given the entire sample data at the beginning, but this is not necessarily the same between different runs of your program. You may assume the number of samples is sufficiently small that you don't have to worry about running out of memory. You may assume any single input sample is between \[-1, 1\]
* A positive real number representing the sample rate (in Hz)
* A positive real number representing the cutoff frequency (in Hz)

You are free to dictate the exact form of the input as long as no additional information is given (ex.: passing a data pointer+length for the time domain signal is ok, but passing in FFT information is not). The input can come from any source desired (file io, stdio, function parameter, etc.)

# Output

Your program should output the time domain filtered signal. The output may be written to any source desired (file io, stdio, function return value, etc.). You should not need the filtered signal sample rate since it should be the same as the input sample rate.

# Validation Python function

This should work with Python 2 or 3 (requires NumPy)

```
from __future__ import division, print_function
import numpy as np

def validate(original, filtered, srate, cfreq):
    '''
    Validates that the filtered signal meets the minimum requirements of a low-pass filter.
    A message of the failure mode is printed to stdout

    @param original the original signal (numpy array)
    @param filtered the filtered signal (numpy array)
    @param srate the sample rate (float)
    @param cfreq the cutoff frequency (float)
    @return True if filtered signal is sufficent, else False
    '''
    # check length
    if(len(original) != len(filtered)):
        print('filtered signal wrong length')
        print('len(original): %d, len(filtered): %d'%(len(original),len(filtered)))
        return False
    # assert filtered signal is not complex
    if(np.any(np.iscomplex(filtered))):
        print('filtered contains complex values')
        return False
    # assert filtered signal is all finite floats
    if(not np.all(np.isfinite(filtered))):
        print('filtered signal contains non-finite floating point values')
        return False
    o_fft = abs(np.fft.rfft(original))
    f_fft = abs(np.fft.rfft(filtered))
    f_fft /= np.amax(o_fft)
    o_fft /= np.amax(o_fft)
    fft_freqs = np.fft.rfftfreq(len(original), 1/srate)

    orig_small_mask = (o_fft < 1e-4)
    big_mask = ~orig_small_mask
    # check small values
    if(np.any(f_fft[orig_small_mask] > 1e-4)):
        print('input signal had a bucket below -80 dB which the filtered signal did not')
        return False

    ob_fft = o_fft[big_mask]
    fb_fft = f_fft[big_mask]
    fftb_freqs = fft_freqs[big_mask]
    low_mask = (fftb_freqs < 0.1*cfreq)
    high_mask = (fftb_freqs >= cfreq)
    lows = abs(fb_fft[low_mask]/ob_fft[low_mask])
    highs = abs(fb_fft[high_mask]/ob_fft[high_mask])
    # check pass bands
    if(np.any(lows > np.sqrt(2)) or np.any(lows < 1/np.sqrt(2))):
        print('pass region is outside of +/- 3dB')
        return False
    # check filter bands
    if(np.any(highs > 1/np.sqrt(2))):
        print('filter region is not at least -3dB below original')
        return False
    # passed all tests!
    return True

```

# Examples

Here are some Python functions which can be used to generate example datasets. Note that these scripts require NumPy. The output of each function is a tuple containing `(samples, sample_rate, cutoff_freq)`. Note that it is very easy to get a different test case by choosing a different cutoff frequency; the example ones are just somewhat "interesting" cases.

```
from __future__ import division, print_function
import numpy as np
def case1():
    # simple sine wave, cutoff including primary frequency
    t = np.linspace(0, 1, 10000)
    srate = 1/(t[1]-t[0])
    return np.sin(2*pi*t),srate,1

def case2():
    # simple sine wave, cutoff above primary frequency
    t = np.linspace(0, 1, 10000)
    srate = 1/(t[1]-t[0])
    return np.sin(2*pi*t),srate,10

def case3():
    # random noise
    t = np.linspace(0, 1, 10001)
    srate = 1/(t[1]-t[0])
    return np.random.rand(t.size)*2-1,srate,10

def case4():
    # sinc function
    t = np.linspace(-1, 1, 10000)
    srate = 1/(t[1]-t[0])
    return np.sinc(2*np.pi*srate*t), srate, 10

def case5():
    n = 200000
    t = np.linspace(0, 1, n)
    y = np.zeros(t.size)
    for i in range(3):
        amp = np.random.rand(1)
        freq = i*103+101
        phase = np.random.rand(1)*2*np.pi
        tdecay = 1e-3
        decay = 1e-1
        for j in range(1,10):
            fj = freq*j
            if(fj >= 0.9*n):
                break
            y += amp*(np.sin(2*np.pi*fj*t+phase))*np.exp(-decay*(j-1)**2)*np.exp(-tdecay*t)
    y -= np.mean(y)
    y /= max(np.amax(abs(y)),1)
    srate = 1/(t[1]-t[0])
    return y,srate, 1e3

```

# Scoring

This is code golf, shortest answer in bytes wins. Standard loop-holes apply. You may use any built-ins desired.

# Answer
> 1 votes
# Python: 99 bytes

```
from numpy.fft import *
def f(o,s,c):
 a = rfft(o);b=rfftfreq(o.size,1/s);a[b>=c]=0;return irfft(a)

```

This is a very simple rectangle/brick filter. It takes the real fft of the signal, sets all components equal to or higher than the cutoff frequency to 0, then returns the inverse real fft.

# Answer
> 1 votes
# SmileBASIC, 54 bytes

```
DEF L D,S,C
DIM A[99]BQPARAM A,1,S,C,1BIQUAD D,D,A
END

```

Call as:

**L** *sample array* **,** *sample rate* **,** *cutoff frequency*

(untested)

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


title: RoboZZle interpreter

text:
# Question
Title: RoboZZle interpreter
Your task is to write a RoboZZle interpreter. If you're not familiar with the game, please watch the video at robozzle.com or read my description below.

A robot lives on a rectangular grid of squares coloured red, green, blue, or black. Black squares are inaccessible. The others are accessible and some of them contain a star. The goal is to collect all the stars without stepping on the black squares or falling off the map. The robot occupies one square and faces a particular direction - left, right, up, or down. It follows assembly-like instructions grouped into subroutines F1,F2,...,F5. An instruction is a pair of a predicate ("none", "if on red", "if on green", "if on blue") and an action ("go forward", "turn left", "turn right", "paint the current square red", "paint it green", "paint it blue", "do nothing", "call F1", ..., "call F5"). Calls to subroutines use a stack and can be recursive. Just like in conventional programming, after the last instruction of a subroutine is completed, execution carries on from the point where the subroutine was called. Execution begins from the first instruction of F1 and continues until either the robot has visited all squares with stars, or when the robot steps on a black square or outside the map, or 1000 instructions have been executed (failed predicates and "do nothing" actions don't count), or there are no more instructions to execute (stack underflow).

Inputs:

* `a` \- a 12x16 character matrix (as usually represented in your language, e.g. array of strings) that encodes a map - `'#'` for inaccessible (black) squares, `'*'` for squares with a star, `'.'` for the rest
* `c` \- a 12x16 character matrix describing the colours of accessible squares - `'R'`(red), `'G'`(green), or `'B'`(blue). Inaccessible squares will be represented by an arbitrary letter from the three.
* `y` and `x` \- the robot's 0-based row and column; `a[y][x]` is guaranteed to be `'.'`
* `d` \- the direction the robot is facing: `0 1 2 3` for right, down, left, up, i.e. towards `(y,x+1)`,`(y+1,x)`,`(y,x-1)`,`(y-1,x)`
* `f` \- a single string, the concatenated implementations of F1...F5. Each implementation is a (possibly empty) sequence of predicate-action pairs (at most 10 pairs per subroutine), terminated with a `'|'`.

+ predicates: `'_'` none, `'r'` red, `'g'` green, `'b'` blue
    + actions: `'F'` go forward, `'L'` turn left, `'R'` turn right, `'r'` paint red, `'g'` paint green, `'b'` paint blue, `'1'` call F1, ..., `'5'` call F5, `'_'` do nothing

You don't have to name you inputs like the above, but their values must be as specified.

Output: `1` (or `true`) if the robot collects all stars according to the rules, `0` (`false`) otherwise.

Example:

```
a=["################","################","##*....*...*#.##","##.####.#####.##","##.####.#####.##","##.####*...*#.##","##.########.####","##*........*#.##","################","################","################","################"]
c=["RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRBBBBRGGGGRRRR","RRBRRRRGRRRRRRRR","RRBRRRRGRRRRRRRR","RRBRRRRRGGGBRRRR","RRBRRRRRRRRGRRRR","RRRBBBBGGGGBRBRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR","RRRRRRRRRRRRRRRR"]
y=2; x=6; d=2

// and then depending on "f":
f="_FrLg2_1|_FbLrR_2||||" // result:1
f="_FrRg2_1|_FbLrR_2||||" // result:0 (stepped on a black square)
f="_FrLrL_1|_FbLrR_2||||" // result:0 (1000-step limit exceeded)
f="_FrLg2__|________||||" // result:0 (stack underflow)

```

Another example, involving "paint" instructions:

```
a=["#***************","#*###*###*###*##","#*###*###*###*##","***#***#***#***#","***#***#***#***#","*###*###*###*###","***#***#***#***#","***#***#***#***#","***#***#***#***#","*###*###*###*###","*.*#***#***#***#","***#***#***#***#"]
c=["RGGGGGGGGGGGGGGG","RBRRRGRRRGRRRGRR","RBRRRGRRRGRRRGRR","RBRRGGGRGGGRGGGR","BRRRGGGRGGGRGGGR","BRRRGRRRGRRRGRRR","BRRRGGGRGGGRGGGR","RBRRGGGRGGGRGGGR","BRRRGGGRGGGRGGGR","BRRRGRRRGRRRGRRR","BGRRGGGRGGGRGGGR","RBRRGGGRGGGRGGGR"]
y=10; x=1; d=0
f="_2_R_R_1|_FgRgFgFg3rRr4b2_Fgb|_F_F_R|_2_L_r||"
// result:1

```

To generate your own test, go to a puzzle from the list at robozzle.com, try to solve it (or not solve it), press F12 in your browser, type in the JS console:

```
r=robozzle;s=JSON.stringify;with(r.level)console.log('a='+s(Items)+'\nc='+s(Colors)+'\ny='+RobotRow+'\nx='+RobotCol+'\nd='+RobotDir+'\nf='+s(r.encodeSolution()))

```

and reformat the result for your language.

Shortest wins. No loopholes.

# Answer
# Prolog (SWI), 574 bytes

```
Z*A:-findall(X^Y-D,(nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D)),L),list_to_assoc(L,A).
N^C^G^[P,I|R]^F^X^Y^D:-map_assoc(\=(74),G);N<1e3,get_assoc(X^Y,G,J),J>67,put_assoc(X^Y,G,78,H),T=N+1,((I\=95,(P=95;get_assoc(X^Y,C,P)))->(between(49,53,I),plus(48,M,I),nth1(M,F,Q),append(Q,R,S),T^C^H^S^F^X^Y^D;member(I,`RL`),E is(D-I//3)mod 4,T^C^H^R^F^X^Y^E;I=70,(D=0,U is X+1;D=1,V is Y+1;D=2,U is X-1;D=3,V is Y-1),(U=X;V=Y),T^C^H^R^F^U^V^D;I>97,put_assoc(X^Y,C,I,W),T^W^H^R^F^X^Y^D);N^C^H^R^F^X^Y^D).
A+C+F+L:-A*G,C*B,split_string(F,"|","",P),maplist(string_codes,P,[M|N]),0^B^G^M^[M|N]^L.

```

Try it online!

This defines a predicate that when called succeeds if the all the stars are successfully collected and fails otherwise. The predicate takes the arguments as such: `a+c+f+x^y^d.`. `a` and `c` must be lists of backtick quoted strings, while `f` must be a double quoted string.

## Explanation

This program contains three predicates, `*/2`, `^/2`, and `+/2`. The `*/2` predicates which is defined on the first line is responsible for part of the input processing. The `^/2` predicate recursively calculates how the robot moves step by step and succeeds if the robot legally collects all the stars and fails otherwise. The `+/2` predicate is the main predicate of the program and prepares the input for the `^/2` predicate with some help from the `*/2` predicate. Note that each of these predicates technically takes only two arguments but using operators and pattern matching they can behave as if they had more arguments (I discuss this phenomenon more in depth here).

### `*/2`

```
Z*A:-findall(X^Y-D,(nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D)),L),list_to_assoc(L,A).

```

This predicate takes two arguments. The first is a list of lists of character codes (this is how Prolog parses backtick quoted strings). The second is a associative map from points in the 12x16 map (represented as `X^Y`) to 32 plus the character code stored at that point in the list of lists of character codes. The 32 is added to each of the character codes so that for the color matrix it will turn the uppercase color characters into lowercase color characters.

The way it does this is generates a list of pairs of points and the character codes at that point using `findall/3`. It then uses `list_to_assoc/2` to create the corresponding associative map from points to the character code at that point.

The `findall/3` predicate is a builtin takes a "template" as its first argument, a goal as its second argument and a list as its third argument. The predicate fills the list with all the possible values of the template that cause the goal to succeed. Due to operator precedence, the template that is passed to `findall/3` in `*/2` is parsed as `(X^Y)-D`. The `-` operator represents a pair of two values in Prolog so the template represents the point's location (`X^Y`) paired with 32 plus the point's character code (`D`). Note that the `^` used in representing the point is in no way connected to the `^/2` predicate.

Let us consider the goal that is passed to the `findall/3` predicate.

```
nth0(Y,Z,O),nth0(X,O,C),plus(32,C,D) % Note that the O (oh) is not a 0 (zero)

```

The goal contains three predicates each of which need to succeed for the goal to succeed. The `nth0/3` predicate which is used twice is used to get the value at a particular index of the list (the `0` in its name indicates it is zero indexed). The first call to it stores the `Y`th row of the character matrix in `O` while the second call stores the `X`th character in that row in `C`. The final predicate `plus/3` succeeds if its first two arguments sum to its third argument. This is used to make the character code in the pair is 32 greater than the character code in the character matrix which as stated above will turn all uppercase letters into lowercase letters.

Finally `findall/3` stores all of the `X^Y-D` combinations that cause its goal to succeed in the list `L` which the associative map is built from.

### More Coming Soon...
> 6 votes

# Answer
# JavaScript (ES6), ~~298~~ ~~276~~ 264 bytes

*Saved 8 bytes thanks to @ngn*

Takes input as `(a,c,x,y,d,f)`, where `a` and `c` are arrays of arrays of characters. Returns `0` or `1`.

```
(a,c,x,y,d,f,k=1e3)=>(g=(F,p=0,s=f.split`|`[F],r=a[y])=>!k|!r|x&16||r[x]<'$'?2:/\*/.test(a)?(r[x]=o=0,(I=s[p+1],P=s[p])&&(P<'b'|P==c[y][x].toLowerCase()&&I!='_'&&k--?+I?o=g(I-1):I=='L'?d--:I=='R'?d++:I<'b'?y+=(d&=3,x-=~-d%2,2-d)%2:c[y][x]=I:0,o||g(F,p+2))):1)(0)&1

```

### Test cases

```
let f =

(a,c,x,y,d,f,k=1e3)=>(g=(F,p=0,s=f.split`|`[F],r=a[y])=>!k|!r|x&16||r[x]<'$'?2:/\*/.test(a)?(r[x]=o=0,(I=s[p+1],P=s[p])&&(P<'b'|P==c[y][x].toLowerCase()&&I!='_'&&k--?+I?o=g(I-1):I=='L'?d--:I=='R'?d++:I<'b'?y+=(d&=3,x-=~-d%2,2-d)%2:c[y][x]=I:0,o||g(F,p+2))):1)(0)&1

getA = _ => [
  "################",
  "################",
  "##*....*...*#.##",
  "##.####.#####.##",
  "##.####.#####.##",
  "##.####*...*#.##",
  "##.########.####",
  "##*........*#.##",
  "################",
  "################",
  "################",
  "################"
].map(s => [...s]);

getC = _ => [
  "RRRRRRRRRRRRRRRR",
  "RRRRRRRRRRRRRRRR",
  "RRRBBBBRGGGGRRRR",
  "RRBRRRRGRRRRRRRR",
  "RRBRRRRGRRRRRRRR",
  "RRBRRRRRGGGBRRRR",
  "RRBRRRRRRRRGRRRR",
  "RRRBBBBGGGGBRBRR",
  "RRRRRRRRRRRRRRRR",
  "RRRRRRRRRRRRRRRR",
  "RRRRRRRRRRRRRRRR",
  "RRRRRRRRRRRRRRRR"
].map(s => [...s]);

y=2; x=6; d=2;

[
  "_FrLg2_1|_FbLrR_2||||", // result:1
  "_FrRg2_1|_FbLrR_2||||", // result:0 (stepped on a black square)
  "_FrLrL_1|_FbLrR_2||||", // result:0 (1000-step limit exceeded)
  "_FrLg2__|________||||"  // result:0 (stack underflow)
]
.forEach(code => console.log('Example #1', code, '-->', f(getA(), getC(), x, y, d, code)));

getA = _ => [
  "#***************",
  "#*###*###*###*##",
  "#*###*###*###*##",
  "***#***#***#***#",
  "***#***#***#***#",
  "*###*###*###*###",
  "***#***#***#***#",
  "***#***#***#***#",
  "***#***#***#***#",
  "*###*###*###*###",
  "*.*#***#***#***#",
  "***#***#***#***#"
].map(s => [...s]);

getC = _ => [
  "RGGGGGGGGGGGGGGG",
  "RBRRRGRRRGRRRGRR",
  "RBRRRGRRRGRRRGRR",
  "RBRRGGGRGGGRGGGR",
  "BRRRGGGRGGGRGGGR",
  "BRRRGRRRGRRRGRRR",
  "BRRRGGGRGGGRGGGR",
  "RBRRGGGRGGGRGGGR",
  "BRRRGGGRGGGRGGGR",
  "BRRRGRRRGRRRGRRR",
  "BGRRGGGRGGGRGGGR",
  "RBRRGGGRGGGRGGGR"
].map(s => [...s]);

y=10; x=1; d=0;

[
  "_2_R_R_1|_FgRgFgFg3rRr4b2_Fgb|_F_F_R|_2_L_r||" // result:1
]
.forEach(code => console.log('Example #2', code, '-->', f(getA(), getC(), x, y, d, code)));
```

### Commented

```
(                                           // main function taking:
  a, c, x, y, d, f,                         //   - input variables
  k = 1e3                                   //   - k = instruction counter
) => (                                      //
  g = (                                     // g = recursive execution function, taking:
    F,                                      //   - F = subroutine id
    p = 0,                                  //   - p = instruction pointer
    s = f.split`|`[F],                      //   - s = instruction string
    r = a[y]                                //   - r = current row in a[]
  ) =>                                      //
    !k |                                    // if we've executed 1000 instructions
    !r | x & 16 ||                          // or we've felt out of the map
    r[x] < '$' ?                            // or we've reached a black square:
      2                                     //   exit with error code 2
    :                                       // else:
      /\*/.test(a) ? (                      //   if there are still some stars:
        r[x] = o = 0,                       //     mark the current cell as visited
        (I = s[p + 1], P = s[p]) &&         //     I = instruction, P = predicate
        (                                   //     if P is defined:
          P < 'b' |                         //       if the predicate is '_'
          P == c[y][x].toLowerCase()        //       or it matches the color of the cell
          && I != '_'                       //       and the instruction is not '_',
          && k-- ?                          //       then decrement k and:
            +I ?                            //         if I is '1' ... '5':
              o = g(I - 1)                  //           process call to subroutine
            :                               //         else:
              I == 'L' ?                    //           if I is 'L':
                d--                         //             turn left
              :                             //           else:
                I == 'R' ?                  //             if I is 'R':
                  d++                       //               turn right
                :                           //             else:
                  I < 'b' ? (               //               if I is not a color:
                    y += (                  //                 I must be 'F',
                      d &= 3,               //                 so make the bot advance
                      x -= ~-d % 2,         //                 by updating x
                      2 - d                 //                 and y
                    ) % 2                   //
                  ) :                       //               else:
                    c[y][x] = I             //                 paint the current cell
          :                                 //       else:
            0,                              //         do nothing
          o ||                              //       provided that o is equal to 0,
          g(F, p + 2)                       //       go on with the next instruction
        )                                   //     end of instruction execution
      ) :                                   //   else:
        1                                   //     success: return 1
  )(0) & 1                                  // initial call to the subroutine F1

```
> 4 votes

# Answer
# APL (Dyalog Classic), ~~236~~ 233 bytes

-3 thanks to Erik the Outgolfer

Now that I've given away the bonus, I'm posting a sample solution to my own challenge. There's room for improvement here - feel free to copy and golf further.

```
a c r d f←⎕⋄c←819⌶c⋄F←0,('|'=¯1⌽f)/⍳≢f⋄t←n←0
{~(⊂r)∊⍳⍴a:0⋄'#'=r⌷a:0⋄p q←2↑f↓⍨⊃⌽t⋄(_←p≡'|')∧×≢t:0⋄_:∇t↓←¯1⋄(⊃⌽t)+←2⋄~p∊'_',r⌷c:∇0⋄n+←1⋄n>999:0⋄(r⌷a)←'.'⋄~'*'∊a:1⋄r+←(q≡'F')×11 9○0j1*d⋄d+←4|'.R.L'⍳q⋄q∊'rgb':∇(r⌷c)←q⋄q∊⎕d:∇t,←F[⍎q]⋄∇0}0

```

Try it online!

Same as the above, expanded with comments:

```
⎕io←0                   ⍝ 0-based indices (not counted in the score)
a c r d f←⎕             ⍝ decompose eval'ed input (⎕) into variables
c←819⌶c                 ⍝ make c lowercase
F←0,('|'=¯1⌽f)/⍳≢f      ⍝ split f at the '|'-s
t←n←0                   ⍝ t:stack, n:step counter
{                       ⍝ lambda
  ~(⊂r)∊⍳⍴a:0           ⍝ if the robot is off the map, return 0
  '#'=r⌷a:0             ⍝ if the robot is on a wall, return 0
  p q←2↑f↓⍨⊃⌽t          ⍝ current instruction - p:predicate, q:action
  (_←p≡'|')∧1≥≢t:0      ⍝ if at end of func and stack is empty, return 0
  _:∇t↓←¯1              ⍝ if at end of func, pop from stack and recurse
  (⊃⌽t)+←2              ⍝ increment program counter (top of stack)
  ~p∊'_',r⌷c:∇0         ⍝ if predicate doesn't match cell colour, recurse
  n+←1⋄n>999:0          ⍝ if too meany steps, return 0
  (r⌷a)←'.'             ⍝ consume star
  ~'*'∊a:1              ⍝ if no more stars left, return 1
  r+←(q≡'F')×11 9○0j1*d ⍝ if action is F, move forward
  d+←4|'.R.L'⍳q         ⍝ if action is L or R, turn left or right
  q∊'rgb':∇(r⌷c)←q      ⍝ if action is paint (r,g,b), do it
  q∊⎕d:∇t,←F[⍎q]        ⍝ if action is F1...F5, push on stack and recurse
  ∇0                    ⍝ action is nop (_), recurse
}0                      ⍝ call the lambda (argument will be ignored)

```
> 2 votes

---
Tags: code-golf, grid, interpreter
---