# Question
Title: Stitch Together a Palindrome from Palindromic Substrings
Given a string `l`, find all palindromic substrings `p` of `l` (including duplicates and single character strings). Next, rearrange all sub-strings in `p` into a valid palindrome (there may be multiple correct answers). If it is not possible to rearrange `p` into a single palindrome, your program may have undefined behavior (error, stack-overflow, exiting, hanging/untimely murder of John Dvorak, etc...)

---

# Examples

## Valid Test Cases

```
l = anaa
p = ['a', 'n', 'a', 'a', 'aa', 'ana']
result = anaaaaana or aanaaanaa or aaananaaa

l = 1213235
p = ['1', '2', '1', '3', '2', '3', '5', '121', '323']
result = 1213235323121

l = racecar
p = ['r', 'a', 'c', 'e', 'c', 'a', 'r', 'cec', 'aceca', 'racecar']
result = racecarcecaacecracecar (there are others)

l = 11233
p = ['1', '11', '1', '2', '3', '33', '3']
result = 113323311 or 331121133

l = abbccdd
p = ['a', 'b', 'bb', 'b', 'c', 'cc', 'c', 'd', 'dd', 'd']
result = bbccddaddccbb or ccbbddaddbbcc or (etc...)

l = a
p = ['a']
result = a

```

## Invalid Test Cases (Not Possible)

```
l = 123456789
p = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
result = <not possible, behavior undefined>

l = hjjkl
p = ['h', 'j', 'jj', 'j', 'k', 'l']
result = <not possible, behavior undefined>

l = xjmjj
p = ['x', 'j', 'jmj', 'm', 'j', 'jj', 'j']
result = <not possible, behavior undefined>

```

---

# Rules

* If the input word is a palindrome itself, it will always be valid as input.
* Only one substring should be returned, which one you choose is arbitrary as long as it's valid.
* If the input has no viable output, your code may have undefined behavior.
* Inputs will only contain ASCII-Printable characters between `0x20-0x7E`.
* This is , lowest byte-count is the winner.

# Answer
# Brachylog, 10 bytes

```
{s.↔}ᶠpc.↔

```

Try it online!

Fails (i.e. prints `false.`) if not possible.

### Explanation

```
{   }ᶠ         Find all…
 s.              …substrings of the input…
  .↔             …which are their own reverse
      p        Take a permutation of this list of palindromes
       c.      The output is the concatenation of this permutation
        .↔     The output is its own reverse

```
> 8 votes

# Answer
# Coconut, 140 bytes

```
s->p(map(''.join,permutations(p(v for k in n(s)for v in n(k[::-1])))))[0]
from itertools import*
n=scan$((+))
p=list..filter$(x->x==x[::-1])

```

Try it online!
> 3 votes

# Answer
# JavaScript (ES6), 193 bytes

*"Look Ma, no permutation built-in!"* (So yes ... it's long ...)

Returns an empty array if there's no solution.

```
f=(s,a=[].concat(...[...s].map((_,i,a)=>a.map((_,j)=>s.slice(i,j+1)))).filter(P=s=>[...s].reverse().join``==s&&s),m=S=[])=>S=a.map((_,i)=>f(s,b=[...a],[...m,b.splice(i,1)]))>''?S:P(m.join``)||S

```

### Demo

```
f=(s,a=[].concat(...[...s].map((_,i,a)=>a.map((_,j)=>s.slice(i,j+1)))).filter(P=s=>[...s].reverse().join``==s&&s),m=S=[])=>S=a.map((_,i)=>f(s,b=[...a],[...m,b.splice(i,1)]))>''?S:P(m.join``)||S

console.log(f('anaa'))
console.log(f('1213235'))
console.log(f('hjjkl'))
console.log(f('a'))
```

### How?

Let's split the code into smaller parts.

We define **P()**, a function that returns **s** if **s** is a palindrome, or **false** otherwise.

```
P = s => [...s].reverse().join`` == s && s

```

We compute all substrings of the input string **s**. Using **P()**, we isolate the non-empty palindromes and store them in the array **a**.

```
a = [].concat(...[...s].map((_, i, a) => a.map((_, j) => s.slice(i, j + 1)))).filter(P)

```

The main recursive function **f()** takes **a** as input and compute all its permutations. It updates **S** whenever the permutation itself is a palindrome (once joined), and eventually returns the final value of **S**.

```
f = (                        // given:
  a,                         //   a[] = input array
  m = S = []                 //   m[] = current permutation of a[]
) =>                         //   and S initialized to []
  S = a.map((_, i) =>        // for each element at position i in a[]:
    f(                       //   do a recursive call with:
      b = [...a],            //     b[] = copy of a[] without the i-th element
      [...m, b.splice(i, 1)] //     the element extracted from a[] added to m[]
    )                        //   end of recursive call
  ) > '' ?                   // if a[] was not empty:
    S                        //   let S unchanged
  :                          // else:
    P(m.join``) || S         //   update S to m.join('') if it's a palindrome

```
> 3 votes

# Answer
# Jelly, 13 bytes

```
ŒḂÐf
ẆÇŒ!F€ÇḢ

```

Try it online!

Prints `0` in the invalid case.
> 2 votes

# Answer
# 05AB1E, ~~13~~ 12 bytes

```
ŒʒÂQ}œJʒÂQ}¤

```

Try it online!

-1 byte thanks to Magic Octopus Urn and Emigna.
> 2 votes

# Answer
# Stax, 13 bytes

```
ç»¬►Ö∞j∞:Æ╘τδ

```

Run test cases (It takes about 10 seconds on my current machine)

This is the corresponding ascii representation of the same program.

```
:e{cr=fw|Nc$cr=!

```

It's not quite *pure* brute-force, but it's just as small as the brute-force implementation I wrote. That one crashed my browser after about 10 minutes. Anyway, here's how it works.

```
:e                  Get all contiguous substrings
  {cr=f             Keep only those that are palindromes
       w            Run the rest of the program repeatedly while a truth value is produced.
        |N          Get the next permutation.
          c$        Copy and flatten the permutation.
            cr=!    Test if it's palindrome.  If not, repeat.
                    The last permutation produced will be implicitly printed.

```
> 2 votes

# Answer
# Ruby, ~~131~~ ~~123~~ 120 bytes

```
->s{m=->t{t==t.reverse}
(1..z=s.size).flat_map{|l|(0..z-l).map{|i|s[i,l]}}.select(&m).permutation.map(&:join).detect &m}

```

Try it online!

A lambda accepting a string and returning a string. Returns `nil` when no solution exists.

-5 bytes: Replace `select{|t|l[t]}` with `select(&l)`

-3 bytes: Replace `map{..}.flatten` with `flat_map{...}`

-1 bytes: Loop over substring length and substring start, instead of over substring start and substring end

-2 bytes: Declare `z` at first use instead of beforehand

```
->s{
  l=->t{t==t.reverse}        # Lambda to test for palindromes
  (1..z=s.size).flat_map{|l| # For each substring length
    (0..z-l).map{|i|         # For each substring start index
      s[i,l]                 # Take the substring
    }
  }                          # flat_map flattens the list of lists of substrings
  .select(&l)                # Filter to include only palindromic substrings
  .permutation               # Take all orderings of substrings
  .map(&:join)               # Flatten each substring ordering into a string
  .detect &l                 # Find the first palindrome
}

```
> 2 votes

# Answer
# Python 3, 167 bytes

```
lambda a:g(sum(k,[])for k in permutations(g(a[i:j+1]for i in range(len(a))for j in range(i,len(a)))))[0]
g=lambda k:[e for e in k if e==e[::-1]]
from itertools import*

```

Try it online!

-2 bytes thanks to Mr. Xcoder
> 1 votes

# Answer
# Pyth, 13 bytes

```
h_I#sM.p_I#.:

```

Try it online!

-1 byte thanks to Mr. Xcoder
> 1 votes

# Answer
# Japt, 19 bytes

Hampered by Japt not (yet) being able to get *all* substrings of a string (and partly by my current levels of exhaustion!).

Outputs `undefined` if there's no solution.

```
Êõ@ãX fêQÃc á m¬æêQ

```

Try it

---

## Explanation

```
                        :Implicit input of string U
Ê                       :Length of U
 õ                      :Range [1,Ê]
  @      Ã              :Pass each X through a function
   ãX                   :  Substrings of U of length X
      f                 :  Filter
       êQ               :    Is it a palindrome?
          c             :Flatten
            á           :Permutations
              m         :Map
               ¬        :  Join to a string
                æêQ     :Get first element that is a palindrome

```
> 1 votes

# Answer
# Husk, 12 bytes

```
ḟS=↔mΣPfS=↔Q

```

Try it online!

## Explanation

```
ḟS=↔mΣPfS=↔Q  Implicit input, a string.
           Q  List of substrings.
       f      Keep those
        S=↔   that are palindromic (equal to their reversal).
      P       Permutations of this list.
    mΣ        Flatten each.
ḟ             Find an element
 S=↔          that is palindromic.

```
> 1 votes

# Answer
# , 53 bytes

```
[:{:@(#~b"1)@(i.@!@#;@A.])@(#~(0<#*b=.]-:|.)&>)@,<\\.

```

Try it online!
> 0 votes

---
Tags: code-golf, array, permutations, palindrome
---


title: Parse Query Parameters

text:
# Question
Title: Parse Query Parameters
The challenge is this:

You are given a url that is as follows:

`http://sub.example.com/some/dir/file.php?action=delete&file=test.foo&strict=true`

There can be either `http` or `https`, there can be any number of subdomains or directories, and the end file can have any name.

You are to create a full program (that can be compiled/interpreted) that when given a key will return the correct value and if no key is found it will return an empty string.

For example:

```
> https://example.com/index.php?action=delete
...> get(action) #=> delete
> https://this.example.com/cat/index.php?action=delete
...> get(action) #=> delete
> http://example.com, https://action.example.com/actionscript/action.jpg
...> get(action) #=> none
> https://example.com/index.php?genre=action&reaction=1&action=2
...> get(action) #=> 2

```

There are no language restrictions and score is calculated a 1 point for every byte. Smallest score wins.

To clarify:

* You do not need to handle URL encoding
* The script only needs to run once and produce a result
* The script can take any input form: STDIN, Prompt, even passed as a function argument

Example:

Javascript, ~~101~~ 105 bytes

```
function p(k){var m;return((m=location.href.match(new RegExp('.*[&\?]'+k+'=([^&]*).*')))!==null?m[1]:'');}

```

# Answer
# Pyth - 22 21 18 bytes

Uses the obvious method of constructing a dictionary and using `}` to check existence. Thanks to @FryAmTheEggman for the error handling trick.

```
#@.dcR\=cecw\?\&zq

```

Can probably be golfed a little more. Doing explanation now. Added explanation:

```
#                 Error handling loop
 @                Implicitly print dict lookup
  .d              Dictionary constructor, takes list of pairs
   cR\=           Map split with "=" as the second arg
    c    \&       Split by "&"
     e            Last in sequence of
      c           Split
       w          Second input
       \?         By "?"
 q                Quit loop

```

Try it online here.
> 6 votes

# Answer
# Retina, ~~30~~ 27 bytes

```
!`(?<=^\1 .*[?&](.*)=)[^&]+

```

This is a full program that expects the key and the URL to be space-separated on STDIN, e.g.

```
action http://sub.example.com/some/dir/file.php?action=delete&file=test.foo&strict=true

```

This is essentially just a (.NET-flavoured) regex, which matches the correct value by checking that the preceding key is equal to the first string in the input (using a backreference). The only thing that's a bit odd about the regex is that .NET matches lookbehinds from right to left, which is why the "backreference" actually references a group that appears later in the pattern. The `!`` instructs Retina to print the actual match (if there is one) instead of the number of matches.

For those who don't regex, here is an annotated version. Read the lookbehind from the bottom up, because that's how it's processed:

```
(?<=        # A lookbehind. Everything we match in here will not be returned as part of
            # actual match. Start reading this from the corresponding parenthesis.
  ^         # Ensure we're at the beginning of the input, so that we've checked
            # against the entire input key.
  \1        # Backreference to the key to check that it's the one we've asked for.
  [ ]       # Match a space.
  .*        # Consume the rest of the URL.
  [?&]      # Match a ? or a & to ensure we've actually captured the entire key.
  (         # End of group 1.
    .+      # Match the key.
  )         # Capturing group 1. Use this to keep track of the key.
  =         # Make sure we start right after a '='
)           # Start reading the lookbehind here.
[^&]+       # Match the value, i.e. as many non-& characters as possible.

```
> 9 votes

# Answer
# JavaScript (*ES6*) 64

**Edit** Saved 1 byte thx @ismael-miguel

A function with url and key as parameters.

Test running the snippet in Firefox.

```
f=(u,k,e='')=>u.replace(RegExp(`[?&]${k}=([^&]*)`),(m,g)=>e=g)&&e

// TEST
out=x=>O.innerHTML += x+'\n';

test=[
   'https://example.com/index.php?action=delete',
   'https://this.example.com/cat/index.php?action=delete',
   'http://example.com',
   'https://action.example.com/actionscript/action.jpg',
   'https://example.com/index.php?genre=action&reaction=1&action=2'
]

test.forEach(u=>out('Url '+u+'\nValue ['+f(u,'action')+']'))
```

```
<pre id=O></pre>
```
> 6 votes

# Answer
# Perl, 25 bytes

```
/[?&]$^I=([^&]*)/;$_=$1

```

This reads the URL from STDIN and the key as an argument to `-i`. It also requires the `-p` switch. I've added two bytes to the count to account for `i` and `p`.

### Example

```
$ perl 2>&- -e'/[?&]$^I=([^&]*)/;$_=$1' -piaction <<< 'http://example.com/?action=delete'
delete

```
> 6 votes

# Answer
## Bash - 55 53

*2 bytes saved thanks to izabera*

```
[[ $1 =~ [?\&]$2=([^&]*) ]]
echo ${BASH_REMATCH[1]}

```

Takes the URL as the first arg and the key to find as the second.

```
bash url.sh "https://this.example.com/cat/index.php?action=delete&foo=bar&spam=eggs" spam

```
> 4 votes

# Answer
# PHP 4.1, ~~43~~36 bytes

There's no mention to do not use built-in function, so, here is my go:

```
<?=parse_str(parse_url($U,6))?0:$$P;

```

This restricts the use of the keys `U` and `P` on your URL.
You can pass the data as you please (POST, GET, COOKIE, ...), being the key `U` the url and `P` the parameter.

Thank you, @manatwork for this shorter version!

Also, an alternative, without the previous restrictions:

```
<?=parse_str(parse_url($U,6),$A)?0:$A[$P];

```

---

Old versions:

```
<?parse_str(parse_url($U,6),$A);echo$A[$P];

```

If you are fine with not being able to use the keys `U` and `P`:

```
<?parse_str(parse_url($U,6));echo$$P;

```
> 4 votes

# Answer
## Python, 87 bytes

The script takes the first url as the first argument and the key as the second.

```
 import re,sys;print re.search(r'[?|&]'+sys.argv[2]+'+=([a-z.]+)',sys.argv[1]).group(1);

```

Sample output:

```
>> runfile('test.py', args='http://sub.example.com/some/dir/file.php?action=delete&file=test.foo&strict=true file')
>> test.foo

```
> 4 votes

# Answer
# CJam, 22 bytes

```
l'?'&er"&="l*/1>s'&/0=

```

Try it online in the CJam interpreter.

### How it works

```
l      e# Read a line from STDIN.
'?'&er e# Replace question marks with ampersands.
"&="l* e# Place the second line from STDIN between '&' and '='.
/      e# Split the first string at occurrences of the second.
1>s    e# Discard the first chunk.
'&/0=  e# Discard everything following an ampersand.

```
> 3 votes

# Answer
# Pyth, 25 bytes

```
|smecd\=fqhcT\=zcecw\?\&"

```

Expects the input on two lines, the key followed by the URL.

## Explanation

```
                   cw\?     Split the second input (the URL) by "?"
                  e         The end (the parameter list)
                 c     \&   Split the parameter list by "&"
        f                   Filter each parameter T
            cT\=            Split by "="
           h                The first part (the key)
          q     z           Equals the first input (the search key)
  m                         Map each valid parameter d
    cd\=                    Split d by "="
   e                        The value
 s                          Print as a string
|                        "  Otherwise, if the key isn't found, print nothing

```

Try it here
> 2 votes

# Answer
# Bash, 37

```
a=${2#*\?};eval "${a//&/;};echo \$$1"

```

Pass the key in the first argument and the URL in the second.

Strips everything off up to and including the first `?`, then treats the remainder as a series of assignments (RFC 1738 URLs can't contain spaces or any of the shell metacharacters, so this works). Finally, print the requested result; by default, strings not found are assumed empty.

Limitation - any key that already exists in the environment may be 'found' when not present in the input.
> 2 votes

# Answer
# Javascript, ~~235~~ ~~228~~ ~~203~~ 190 bytes

Takes the URL as the first input and the key as the second.

```
b=document.createElement('a'),b.href=prompt(u={}),a=b.search;if(a!=""){t=a.substring(1).split("&");for(i=t.length;i--;){p=t[i].split("=");u[p[0]]=p[1]}}c=u[prompt()];alert(c==undefined?"":c)

```
> 1 votes

# Answer
# Rebol - 97

```
e:["&"| end]p: func[u a][parse u[thru"?"any[copy k to"=""="copy v to e e(if k = a[return v])]]{}]

```

Ungolfed:

```
e: ["&" | end]

p: func [u a] [
    parse u [
        thru "?"
        any [
            copy k to "=" "=" copy v to e e
            (if k = a [return v])
        ]
    ]
    {}
]

```

Example usage (in Rebol console):

```
>> p "http://sub.example.com/some/dir/file.php?action=delete&file=test.foo&strict=true" "action"
== "delete"

>> p "https://example.com/index.php?action=delete" "action"
== "delete"

>> p "https://this.example.com/cat/index.php?action=delete" "action"
== "delete"

>> p "http://example.com, https://action.example.com/actionscript/action.jpg" "action"
== ""

>> p "https://action.example.com/actionscript/action.jpg" "action"
== ""

>> p "http://example.com" "action"
== ""

>> p "https://example.com/index.php?genre=action&reaction=1&action=2" "action"
== "2"

```
> 1 votes

# Answer
# K, 24

```
{((!)."S=&"0:*|"?"\:x)y}

```

.

```
{((!)."S=&"0:*|"?"\:x)y}["https://example.com/index.php?genre=action&reaction=1&action=2";`genre]
"action"

```

### Explanation:

The function takes two parameters, the url `x` and the key `y`

First we split the url on the `?` character.

```
k)"?"\:"https://example.com/index.php?genre=action&reaction=1&action=2"
"https://example.com/index.php"
"genre=action&reaction=1&action=2"

```

Then we take the last element using `*|` (first reverse)

```
k)*|"?"\:"https://example.com/index.php?genre=action&reaction=1&action=2"
"genre=action&reaction=1&action=2"

```

Process the string using `0:`. The LHS of `0:` is a three character string, where the first is the datatype of the key (`S` for symbol, `I` for int etc), the second is the key-value delimiter (`=` in this case) and the third is the record delimiter (`&` here).

```
k)"S=&"0:*|"?"\:"https://example.com/index.php?genre=action&reaction=1&action=2"
genre    reaction action
"action" ,"1"     ,"2"

```

Turn this into a dictionary using `!`

```
k)(!)."S=&"0:*|"?"\:"https://example.com/index.php?genre=action&reaction=1&action=2"
genre   | "action"
reaction| ,"1"
action  | ,"2"

```

Then do a lookup on this dictionary for whichever key you're looking for.

```
k)((!)."S=&"0:*|"?"\:"https://example.com/index.php?genre=action&reaction=1&action=2")`genre
"action"

```

Turn it into a function using `{}` and replace the url string with `x` and the lookup key with `y`, then pass the url and key in as paramters (`func[param1;param2;...;paramN]`)

```
k){((!)."S=&"0:*|"?"\:x)y}["https://example.com/index.php?genre=action&reaction=1&action=2";`genre]
"action"

```
> 1 votes

# Answer
# Gema: ~~44~~ 38 characters

Expects first the parameter name then the URL on separate lines.

```
\B\L*\n=@set{p;$1}
\I$p\=/[^&]+/=$1
?=

```

Sample run:

```
bash-4.3$ gema -p '\B\L*\n=@set{p;$1};\I$p\=/[^&]+/=$1;?=' <<< $'action\nhttps://example.com/index.php?genre=action&reaction=1&action=2'
2

```
> 0 votes

# Answer
# C, 123 bytes

```
char*f(char*s,char*n){for(char*x=n;*s&&(*x||*s!='=');x=*x++==*s++?x:n);return *s=='='?(n=strstr(s++,"&"))?(*n=0)?s:s:s:"";}

```

Note: this function assumes you aren't passing a constant char to it.
> 0 votes

# Answer
# JavaScript, 40 bytes

```
u=>q=>new URL(u).searchParams.get(q)||``

```

Test it
> 0 votes

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


title: Can you outgolf Bill Gates?

text:
# Question
Title: Can you outgolf Bill Gates?
> Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number **P(n)** is the minimum number of flips required for **n** pancakes.

In 1979, a young Bill Gates and Christos Papadimitriou, wrote a paper proving an upper bound of **P(n) = (5n+5)/3**.

I think it's safe to assume that Gates (and/or Papadimitriou) wrote a program to perform pancake sorting using the algorithm they developed (possibly later than 1979). Since Gates was a skilled programmer, they probably tried to golf this code as well as they could, but the size of the source code is not publicly available (AFAIK).

### Challenge:

Create a function / program that performs pancake sorting, where the maximum number of flips doesn't exceed the bound found by Gates and Papadimitriou.3 You may choose if you want the list ascending or descending, as long as it's consistent.

You may assume that **n \< 50**. You must therefore limit the number of flips to (some randomly selected **n**-values):

```
 n   P(n)
38   65
49   83
50   85

```

The output should be the position of the spatula before each flip. The output may be zero or one-indexed, and you may choose if you count from the top or bottom.

### Additional rules:

* The runtime must be deterministic
* There is no fixed time limit, but you must be able to provide the output for a list with 50 elements

### Test lists:

I can't provide the hardest lists (if so, I would write a paper, not a challenge), so I'll provide some random lists of numbers you can test your functions/programs on. I might add others if it turns out these lists where "easy".

```
9, 63, 62, 75, 45, 78, 59, 75, 69, 3, 28, 94, 51, 10, 45, 93, 97, 80, 72, 36, 80, 88, 30, 93, 84, 80, 17, 31, 6, 80, 76, 91, 9, 76, 38, 33, 22, 15, 45, 46, 15, 98, 2, 56, 90, 27, 27, 26, 69, 25
...
74, 89, 57, 52, 70, 96, 16, 5, 77, 84, 54, 13, 90, 64, 31, 80, 3, 25, 13, 19, 13, 34, 1, 79, 35, 43, 4, 19, 82, 29, 48, 95, 97, 28, 45, 62, 64, 82, 70, 34, 38, 15, 51, 83, 21, 66, 4, 42, 74, 84
...
62, 73, 7, 90, 83, 18, 12, 35, 72, 71, 99, 67, 87, 62, 65, 70, 14, 72, 55, 92, 87, 3, 7, 4, 4, 95, 49, 25, 4, 18, 49, 39, 26, 1, 45, 64, 23, 66, 39, 17, 33, 24, 58, 72, 77, 46, 99, 71, 10, 21

```

---

Hopefully, Bill Gates and Papadimitriou will see this challenge, and provide their code, so that we can determine if you did in fact outgolf them.

3Better upper bounds have been found, but you do not need to care about those.

# Answer
> 4 votes
# Python 2 (PyPy), ~~238~~ ~~235~~ 222 bytes

```
a=input();n=len(a);r=range(n);a=zip(a,r);a=map(sorted(a).index,a)+[n]
def s(u,m):
 if m<1:return[0]
 for k in r:
  v=u[k::-1]+u[k+1:]
  if sum(1<abs(v[i]-v[i+1])for i in r)<m:
   p=s(v,m-1)
   if p:return[k]+p
print s(a,5*n/3)

```

\*(2 spaces = tab)

Try it online!

Saved 13 bytes borrowing a method for ranking a list.

DFS with a simple heuristic that checks whether a flip separates a pair of "pancakes" that would be adjacent when sorted. Sorts it in ascending order. Output is 0-indexed from the left where 0 flips the first 2 and so on. The number of moves used is `(5/3)*n+1 < 5/3*(n+1)` where `(18/11)*n < (5/3)*n+1 < 5/3*(n+1)` and `(18/11)*n` is a tighter upper bound found in 2009.

---
Tags: code-golf, number, sorting, optimization, stack
---


title: Noah's (upgraded) ark

text:
# Question
Title: Noah's (upgraded) ark
As preparation for the nth Exodus, Noah decides to write a program that will decide If he will let animals on his ark. However, Noah wants to go back to grass roots. Thus he decides that the program should be as small and as simple as possible.

**GOAL:**
Recreate the Contrabulous Choosematron, in a way that follows evangelical stories.

**INPUT:**

The program is simple, and elegant, and takes in 2 inputs:
The species of animal \[String\]
and The animal's gender \[boolean\]

**OUTPUT:**

The program then puts out Either 'Y' or 'N', Which determines whether or not the given animal is allowed onto the ark.

**RULES:**

Only one Animal of each species and gender is allowed on the ark. No more.
Your output can be any set of boolean values (true false, yes no, y n, yin yang) so long as they're easily distinguishable.
If your program should want to accept a list of input, rather than use STDIN, that's fine. However, each output has to be in corresponding order of the input (FIFO), as well as be in the exact same format as the input.
**This is a golf, so the lowest byte count wins, good luck**!!!!

**EXAMPLE:**

> "Monkey" true\<
> y
> "Monkey" false\<
> y
> "Monkey" false\<
> n
> "Monkey with symbols" false\<
> y
> "monkey" true\<
> n

This is valid, as your program doesn't need to distinguish that `Monkey`, and `monkey with symbols` are the same thing species, however, `Monkey` and `monkey` are very much the same thing, and so the last critter would be denied.

# Answer
# Perl, ~~15~~ 13 bytes

Includes +1 for `-n`

Input on STDIN (or 1 or more filenames as argument like `cat`), one animal and gender per line in any consistent notation. Prints a line with 1 for true, an empty line for false

```
perl -M5.010 -n ark.pl

```

`ark.pl`

```
say!${+lc}++

```
> 3 votes

# Answer
# Python 2, 72 bytes

Takes input as a list of strings of the form "animalname T". The idea is it just uses each string as an identifier and should only print true if the string has not occurred in the list so far.

```
def f(l):k=map(str.lower,l);print[j not in k[:i]for i,j in enumerate(k)]

```

Try it here!
> 3 votes

# Answer
# Python, ~~54 52~~ 50 bytes

```
def f(s,l={}):x=s.lower();r=x in l;l[x]=1;return r

```

Test case is at **ideone**

This borrows this neat idea from @gowrath, but extends it by using the fact that when a function is defined with a default argument that is mutable, like a dictionary, it acts as a memoisation (the object retains state between function calls).

Saved 2 bytes by returning None for truthy ("Y") and 0 for falsey ("N").
Save 2 more by (confusingly) returning False for truthy ("Y") and True for falsey ("N").
> 1 votes

# Answer
# Java, ~~246~~ 218 bytes

Lowered byte count thanks to Kevin!.

Takes STDIN as input, outputs weather or not the animal is allowed to board.

```
import java.util.*;class B{public static void main(String[]a){List l=new ArrayList();Scanner s=new Scanner(System.in);for(;;){String b=s.nextLine().toLowerCase();l.add(b);System.out.println(l.contains(b)?"n":"y");}}}

```
> 0 votes

# Answer
## Groovy 43 Bytes

```
{s->y=[];s.collect{!y.contains(it)&&y.add(it)}}

```

Try it here: https://groovyconsole.appspot.com/edit/5147446497771520

It uses a list of tuples as the input:

```
z = [new Tuple('Monkey',true), new Tuple('Monkey',false), new Tuple('Monkey',true), new Tuple('Bee',true)]

```

Which results in:

```
[true, true, false, true]

```

The add function in groovy always returns true, and in groovy tuples have inherent comparison ability for primitive objects, so the contains actually works well for strings and integers without changing it.

So, basically just check if the list contains it and add it to the list.

* If the list already contains it we get (false && N/A)
* If it does not we get (True && True) and it is added to the running list.

This is all you really need to accomplish this, if you want to tell me to turn it into a closure or something as well it would probably cap out at approximately 45-50 bytes in Groovy.
> 0 votes

# Answer
# Perl (35 + 1 for -p) 36

Takes input from STDIN, one animal per line in the form `animal T`. Where `T` is anything you want to be used for the gender (e.g. `T`/`F`, `M`/`F`). You could even have multi-character genders, or more than 2 genders (e.g. `male`/`female`/`apache helicopter`).

Includes all character on the line, so if you're inputting from a file you need a newline after the last animal.

```
$\=($a{lc()}?N:Y);$a{lc()}=1;$_='';

```
> 0 votes

# Answer
## PowerShell v3+, 33 bytes

```
$a=@();$args|%{$_-notin$a;$a+=$_}

```

Takes input as command-line arguments of strings of the form `Animal Gender` where `Gender` is (pretty much) any identifier you want. Sets an empty array `$a`, then loops through the input arguments. Places the Boolean result of the `-notin` operator on the pipeline, and adds the current element into the `$a` array. PowerShell by default is case-insensitive when comparing strings, so `Monkey f`, `monkey f`, `mOnKeY F` and other variations will all evaluate as the same.

The resulting Booleans are left on the pipeline, and output via implicit `Write-Output` happens at program completion.

### Example

```
PS C:\Tools\Scripts\golfing> .\noahs-upgraded-ark.ps1 'Monkey m' 'Monkey f' 'Monkey f' 'Monkey with symbols m' 'monkey m'
True
True
False
True
False

```
> 0 votes

# Answer
# Dyalog APL, 16 bytes

Case sensitive solution:

```
(⍳⍴)∊(∪⍳⍨)

```

`(⍳⍴)` which indices

are member of

`⍳⍨` each entry's first occurrence in the list

Unfortunately, case-insensitivity is bulky:

```
(⍳⍴)∊(∪c⍳c←819⌶)

```

`c←819⌶` assign the lowercase function to *c*

`c⍳c` is the same as `⍳⍨c`. See explanation above.

TryAPL online! (casing is not supported on TryAPL)
> 0 votes

# Answer
# Swift 2.2 169 bytes

I did not accept input from standard in I just passed an array of dictionaries to function x.

### Golfed

```
var a=[String]();let x={(d:[[String:Bool]]) in for r in d{for(s,t)in r{let y=s.lowercaseString+t.description;a.append(y);print(a.indexOf(y)==(a.count-1) ? true:false)}}}

```

### UnGolfed

```
var a=[String]();
let x={(d:[[String:Bool]]) in
    for r in d{
        for(s,t)in r{
            let y=s.lowercaseString+t.description;
            a.append(y);
            print(a.indexOf(y)==(a.count-1) ? true:false)
        }
    }
}

```

### Input

```
x([["Monkey":true],["Monkey":false],["monkey":true],["Zebra":true]])

```

---

Also just for giggles did a crappy javascript version since I did not see anyone else do a javascript one.

## JS (ES6) 125 bytes

### Golfed

```
a=[],i=0,j=0;y=(r)=>{for(;j<r.length;j+=2){var y=r[j].toLowerCase()+r[j+1];a[i]=y;console.log(a.indexOf(y)==i++?true:false)}}a=[],i=0,j=0;y=(r)=>{for(;j<r.length;j+=2){var y=r[j].toLowerCase()+r[j+1];a[i]=y;console.log(a.indexOf(y)==i++?true:false)}}

```

### UnGolfed

```
a=[],i=0,j=0;
y=(r)=>{
  for(;j<r.length;j+=2){
    var y=r[j].toLowerCase()+r[j+1];
    a[i]=y;
    console.log(a.indexOf(y)==i++?true:false)
  }
}

```

### Input

```
y(["Monkey", true, "Monkey", false, "monkey",true,"zebra",false])

```
> 0 votes

# Answer
# Jelly, 4 bytes

```
ŒuŒQ

```

Try it online!

Each animal in the list (argument) is `[species, gender]`, where `gender` can either be `1` for male or `0` for female. Output is a list of `0`s and `1`s, where `0` means "not allowed" and `1` means "allowed". This is a function, and therefore a footer has been added to show the actual result.
> 0 votes

# Answer
# Ruby, ~~50~~ 48 bytes

```
->a,*s{a.map{|x|x[0].upcase!
(s<<x).count(x)<2}}

```

Try it online!

A lambda accepting an array of `[animal, gender]` pairs and returning a boolean array.

-2 bytes: Initialize the list of seen animals as a splat arg

```
->a,*s{                # s is the list of animals seen so far, initially []
  a.map{ |x|           # x is the current animal
    x[0].upcase!       # Transform x's name in place to uppercase
    (d<<x).count(x)<2  # Add x to s, and return true if s has only 1 instance of x
  }
}

```
> 0 votes

---
Tags: code-golf, permutations
---


title: Biggest number challenge (Brainfuck)

text:
# Question
Title: Biggest number challenge (Brainfuck)
This is a brainfuck version of Largest Number Printable, and this.

---

Let's think about brainfuck interpreter such that,

1. Has array that can be stretched left & right arbitrary large
2. Each cell can contain arbitrary large integer
    * Can contain negative integer too
3. When the interpreter starts, every cell is intialized by 0
4. `.` prints integer representation of value of cell, then LF.

For example, `<<+++.>--.` prints

```
3
-2

```

, then terminate.

---

# Description

Your goal is to write a brainfuck program that prints a number/numbers. The bigger the number, the more points you'll get.

There are some rules to follow.

* Your program **must** terminate.
* You **should not** use `,`.
* You **can** print multiple integers.
* Your score will be largest number that the program prints.
* Maximum code length is 1024 bytes. (Only `[]+-><.` counts)

Here is sample brainfuck interpreter that you could test.

---

# Leaderboards

:)

# Answer
> 0 votes
# Score: 2↑↑45306

Edit: Replaced it with a more modifiable version. Try 2↑↑2, 2↑↑3, and 2↑↑4 (2↑↑5 times out)

Just testing the waters with a short answer.

```
+>+>++>++>++>++++>++[>[<+++++>-]<<]>
>++<
[
    >[->>+>+<<<]
    >>>
    [
        <[-<+<+>>]
        <[->+<]
        >>-
    ]
    <[-]<<<-
]
>.

```

The ↑↑ indicate Knuth's arrow notation, where a single ↑, such as `X↑Y`, means (((X\*Y)\*Y)\*Y)... X times = X^Y, and two ↑↑s means (((X↑Y)↑Y)↑Y)... X times. For example, 2↑↑4 = 2222.

(I'm not familiar with bignum notation, so please tell me if there's a shorter way of representing this, or there's an error in my calculations)

# Explanation:

```
+>+>++>++>++>++++>++[>[<+++++>-]<<]>

```

Produces the number 45306. (Taken from the brainfuck constants page on Esolangs, an immensely useful page). This will be used as the counter.

```
>++<

```

Sets the current value as two and move back to the counter

```
[ Loop until the counter is 0

    Square the current value
    >[->>+>+<<<]
    >>>
    [
        <[-<+<+>>]
        <[->+<]
        >>-
    ]<[-]

    Decrement the counter
    <<<-
]

```

A few ways to extend this:

* Increase the counter. Pretty easy to do.
* Increase the initial value. To be simple, you could just set the initial value and the counter as the same number
* Remove the clear cell in the squaring operation, which compounds the result
* Create another counter and put another loop around the whole thing
    + This effectively adds another Knuth's Arrow to the result (I think)
    + Further addition, for each iteration of the outer loop, copy the current value to use as the inner loop's counter
    + And then put another loop around the whole lot again.

---
Tags: code-challenge, brainfuck
---


title: Romanize Korean

text:
# Question
Title: Romanize Korean
> Yes, It's basically You're a Romanizer, Baby, but *harder*. like, *way* harder.

Learning Korean is HARD. at least for a person outside Asia. But they at least have the chance to learn, right?

# What you must do

You will be given a Korean Statement. For example, `안녕하세요`. You must convert the input to its Roman pronunciation. For the given example, the output can be `annyeonghaseyo`.

# Now it gets technical

A Korean character has three parts, Starting consonant, Vowel, and Ending consonant. The Ending consonant may not exist in the character.

For example,  is (Starting consonant) and (Vowel), and  is (Starting consonant), (Vowel), and (Ending consonant).

Evert consonant and vowel has its pronunciation. The pronunciation for each consonant is as following.

```
Korean                 ㄱ   ㄲ  ㄴ  ㄷ   ㄸ  ㄹ  ㅁ  ㅂ  ㅃ  ㅅ  ㅆ  ㅇ   ㅈ   ㅉ  ㅊ ㅋ  ㅌ   ㅍ  ㅎ
Romanization Starting   g   kk  n   d   tt  r   m   b   pp  s   ss  –   j   jj  ch  k   t   p   h
               Ending   k   k   n   t   –   l   m   p   –   t   t   ng  t   –   t   k   t   p   h

```

( - means no pronunciation or not used. you do not have to handle them.)

and Pronunciation for each vowels is as following.

```
Hangul          ㅏ  ㅐ  ㅑ  ㅒ   ㅓ  ㅔ  ㅕ  ㅖ  ㅗ   ㅘ   ㅙ  ㅚ ㅛ  ㅜ  ㅝ  ㅞ  ㅟ   ㅠ  ㅡ   ㅢ ㅣ
Romanization    a   ae  ya  yae eo  e   yeo ye  o   wa  wae oe  yo  u   wo  we  wi  yu  eu  ui  i

```

# Now its the real hard part

The consonant's pronunciation changes by the Ending consonant in before. The pronunciation for every Starting/Ending consonant is as the following image. (You do not have to do the hyphen between pronunciations. Its unnecessary. If a cell has two or more pronunciations, choose one. If there's no ending consonant, use the original pronunciation.)

# Examples

```
Korean => English
안녕하세요 => annyeonghaseyo
나랏말싸미 듕귁에달아 => naranmalssami dyunggwigedara  //See how the ㅅ in 랏 changes from 't' to 'n'

```

Example suggestion welcomed. You can get answers for your own inputs here. (The one in "General text", Revised is what I'm asking for)

# Answer
> 9 votes
# Python 3.6, ~~400~~ 394 bytes

**Edit:** Thanks to RootTwo for -6 bytes.

This is my first submission on CodeGolf, so I'm pretty sure there are better ways to golf it, but I thought I'd still post it, as nobody has mentioned the key idea yet, and this is still significantly shorter than other solutions.

```
import re,unicodedata as u
t='-'.join(u.name(i)[16:]for i in input()).lower()
for i in range(19):t=re.sub('h-[gdb]|(?<!n)([gdbsjc]+)(?!\\1)(?!-?[aeiouyw]) gg dd bb -- - h(?=[nmrcktp])|hh hj l(?=[aeiouyw]) l[nr] [nt][nr] tm pm [pm][nr] km kn|kr|ngr c yi weo'.split()[i],([lambda m:'ktpttt'['gdbsjc'.index(m[0][-1])]]+'kk,tt,pp, ,,t,c,r,ll,nn,nm,mm,mn,ngm,ngn,ch,ui,wo'.split(","))[i],t)
print(t)

```

## How it works

The solution attempts to exploit the fact (which I learned from the original Japanese romanization challenge) that romanized character names are accessible through Python's unicodedata module. For Korean language, they take the form of `HANGUL SYLLABLE <NAME>`. Unfortunately, processing these names to meet the provided specification and to cover all the syllable combination scenarios still requires quite a bit of effort (and bytes).

The obtained character names list all consonants in their voiced form anywhere in the syllable, e.g. `GGAGG` for , `R/L` are transcribed as intended (starting `R`, ending `L`), and `CH` is given as `C` (this actually saves us a bit of headache).

First of all, we strip off the `HANGUL SYLLABLE` part (first 16 chars), mark the syllable boundaries with `-`, and then apply a series of RegEx'es to do the conversions.

The first RegEx looks particularly nasty. What it basically does, is conversion of starting consonants into their ending equivalents (also removing the extra letter in case of double consonants), when they are not followed by a vowel, or for some letters - when they are preceded by `h`. The `(?<!n)` lookbehind prevents matching `g` which is part of `ng`, and `(?!\\1)` lookahead ensures that we don't convert, e.g., `ssa` to `tsa`.

The next few RegEx'es convert starting double consonants into their unvoiced equivalents. Here's where `-` separators also come in handy as they help discerning boundary collisions (`g-g`) from double consonants (`gg`). Now they can also be removed.

Next, we handle the remaining `h+consonant` combinations, `l->r` before vowels, and other special cases.

Finally, we restore `c` to `ch`, and resolve some other pecularities of our incoming char names, such as `yi` instead of `ui` and `weo` instead of `wo`.

I'm not an expert in Korean and can't comment much more, but this seems to pass all the tests posted in the task and on Github. Obviously, a few more bytes could be shaved off, if the output is acceptable in uppercase, as this is what we get from the name function.

# Answer
> 5 votes
# JavaScript (ES6), 480 bytes (WIP)

This is an early attempt based on the current specs to get the ball rolling. It may require some fixing when the questions in the comments are addressed.

```
s=>[...s].map(c=>c<'!'?c:(u=c.charCodeAt()-44032,y='1478ghjlmnpr'.search((p=t).toString(36)),t=u%28,u=u/28|0,v=u%21,x=[2,5,6,11,18].indexOf(u=u/21|0),~x&~y&&(z=parseInt(V[y+68][x],36))>10?V[z+69]:V[p+40]+V[u+21])+V[v],t=0,V='8a6y8ye6e46ye4y64w8wa6o6y4u/w4w6wi/yu/eu/ui/i/g/k21d/t7r/3b/p0s/ss95j5ch/270h922/197l999930/77ng/77270h/bbcd6afaa8gghi5ffak8alaa8llmn4gghp8abaa8gghq5gghr5ggha5gghs8ng1ng3g/2ll/n1n3d/7r/m1m3b/0s/5ch/h'.replace(/\d/g,n=>'pnkmojeta/'[n]+'/').split`/`).join``

```

### Test cases

```
let f =

s=>[...s].map(c=>c<'!'?c:(u=c.charCodeAt()-44032,y='1478ghjlmnpr'.search((p=t).toString(36)),t=u%28,u=u/28|0,v=u%21,x=[2,5,6,11,18].indexOf(u=u/21|0),~x&~y&&(z=parseInt(V[y+68][x],36))>10?V[z+69]:V[p+40]+V[u+21])+V[v],t=0,V='8a6y8ye6e46ye4y64w8wa6o6y4u/w4w6wi/yu/eu/ui/i/g/k21d/t7r/3b/p0s/ss95j5ch/270h922/197l999930/77ng/77270h/bbcd6afaa8gghi5ffak8alaa8llmn4gghp8abaa8gghq5gghr5ggha5gghs8ng1ng3g/2ll/n1n3d/7r/m1m3b/0s/5ch/h'.replace(/\d/g,n=>'pnkmojeta/'[n]+'/').split`/`).join``

console.log(f("안녕하세요"))
console.log(f("나랏말싸미 듕귁에달아"))
```

### How?

Once decompressed, the array **V** contains the following data:

```
00-20 vowels
a/ae/ya/yee/eo/e/yeo/ye/o/wa/wae/oe/yo/u/wo/we/wi/yu/eu/ui/i

21-39 starting consonants
g/kk/n/d/tt/r/m/b/pp/s/ss//j/jj/ch/k/t/p/h

40-67 ending consonants
/k/k//n///t/l////////m/p//t/t/ng/t/t/k/t/p/h

68-79 indices of substitution patterns for consecutive consonants
      ('a' = no substitution, 'b' = pattern #0, 'c' = pattern #1, etc.)
bbcde/afaaa/gghij/ffaka/alaaa/llmno/gghpa/abaaa/gghqj/gghrj/gghaj/gghsa

80-97 substitution patterns
ngn/ngm/g/k/ll/nn/nm/d/t/r/mn/mm/b/p/s/j/ch/h

```

We split each Hangul character into starting consonant, vowel and ending consonant. We append to the result:

* `V[80 + substitution] + V[vowel]` if there's a substitution
* `V[40 + previousEndingConsonant] + V[21 + startingConsonant] + V[vowel]` otherwise

# Answer
> 2 votes
# Tcl, 529 bytes

```
fconfigure stdin -en utf-8
foreach c [split [read stdin] {}] {scan $c %c n
if {$n < 256} {append s $c} {incr n -44032
append s [string index gKndTrmbPsS-jJCktph [expr $n/588]][lindex {a ae ya yae eo e yeo ye o wa wae oe yo u wo we wi yu eu ui i} [expr $n%588/28]][string index -Ak-n--tl-------mp-BGQDEkFph [expr $n%28]]}}
puts [string map {nr nn
A- g An ngn Ar ngn Am ngm A kk
t- d p- b B- s D- j
nr ll l- r ln ll lr ll
A k B t G t D t E t F t
K kk T tt P pp S ss J jj C ch Q ng
- ""} [regsub -all -- {[tpBDEFh]([nrm])} $s n\\1]]

```

### Algorithm

1. Decomposition into lead, vowel, and tail indices
2. First lookup to intermediate alphabetic representation
3. Apply an initial pass for all the xn→nn/xm→nm transforms
4. Apply a final pass for the remaining transforms

This algorithm is crunched for purposes of the challenge; the trade-off being that the input is assumed to *not* contain any Latin alphabetic characters, nor to use characters outside the U+AC00 Hangul block as described in the challenge. Were this real code, I'd keep all the transforms in Jamo until the final pass.

I suppose I could throw some more brainpower at crunching those vowels and some of the repetitions in the lookup table, but this is as good as it gets from me today.

### Testing

Make sure you can supply UTF-8 input to the Tcl interpreter. This is most easily accomplished with a simple UTF-8 text file. Alas, Tcl still does not default to UTF-8 by default; this cost me 33 bytes.

Here’s my (currently pathetic) test file:

```
한
안녕하세요
나랏말싸미 듕귁에달아

```

### Notes

I know nothing about Korean language (except what little I have learned here). This is a first attempt, pending potential revision due to updates in the question specification.

And, about that, some additional information is useful. In particular, there is not a 1:1 correspondence between lead and tail consonants as seems to be suggested in the challenge. The following two sites helped immensely figuring that out:
Wikipedia: Korean language, Hangul
Wikipedia: Hangul Jamo (Unicode block)

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


title: Palindromic numbers with a binary twist

text:
# Question
Title: Palindromic numbers with a binary twist
**Warning : this is NOT a "hey, let's draw a cake in ASCII-art" challenge! Please keep reading ;)**

Some time ago it was my birthday, I'm 33 now.

So there is this awkward social tradition consisting in inviting family and friends, putting number-like candles on a cake, sing songs and open gifts.

```
   33
--------

```

Instead of numbers, I can use the binary system to put standard candles: I place 6 of them on the cake and light two of them.

```
 100001
--------

```

I can see that **both decimal and binary numbers of my age are palindromic!**

# Challenge

I want to know if any other number can be put on a cake with candles and be palindromic, decimal and binary.

Write a program/function to test if a number is palindromic in **both** decimal and binary. But wait, there's more : **in binary, leading zeros count for the test!**

## Input

A **decimal** number x that I want to test if it is birthday palindromic with 0 \< x \< 232-1 (yes, the people in my dimension live very long)

## Output

Truthy if it meets exactly these two conditions, Falsey else:

* The decimal representation of the number is a standard palindrome
* The binary representation of the number is a standard palindrome, **and adding leading zeros may help with this**

## Test cases

```
1 > 1 => Truthy
6 > 110 (0110) => Truthy
9 > 1001 => Truthy
10 > 1010 (01010) => Falsey, 10 is not palindromic
12 => 1100 (001100) => Falsey, 12 is not palindromic
13 => 1101 (...01101) => Falsey, neither 13 nor 1101 are palindromic
14 => 1110 (01110) => Falsey, 14 is not palindromic
33 > 100001 => Truthy
44 > 101100 (..0101100) => Falsey, 101100 is not palindromic
1342177280 > 1010000000000000000000000000000 (00000000000000000000000000001010000000000000000000000000000) => Falsey, 1342177280 is not palindromic (but the binary representation is)
297515792 > 10001101110111011101100010000 (000010001101110111011101100010000) => Truthy

```

## Rules

Good luck, and eventually happy birthday!

# Answer
> 17 votes
# 05AB1E, 7 bytes

```
b0Ü‚DíQ

```

Try it online! or as a Test Suite

**Explanation**

```
b         # convert input to binary
 0Ü       # remove trailing zeroes
   ‚      # pair with input
    D     # duplicate
     í    # reverse each (in the copy)
      Q   # check for equality

```

# Answer
> 11 votes
# Python 3, 59 bytes

```
lambda a:all(c==c[::-1]for c in[str(a),bin(a).strip('0b')])

```

Try it online!

-3 bytes thanks to Rod
-3 bytes thanks to Connor Johnston

# Answer
> 8 votes
# JavaScript (ES6), 65 bytes

Returns `0` or `1`.

```
n=>(g=b=>[...s=n.toString(b)].reverse().join``==s)()&g(2,n/=n&-n)

```

### How?

The helper function ***g()*** takes an integer ***b*** as input and tests whether ***n*** is a palindrome in base ***b***. If ***b*** is not specified, it just converts ***n*** to a string before testing it.

We get rid of the trailing zeros in the binary representation of ***n*** by isolating the least significant *1* with `n&-n` and dividing ***n*** by the resulting quantity.

Fun fact: it's truthy for `0` because `(0/0).toString(2)` equals `"NaN"`, which is a palindrome. (But `0` is not a valid input anyway.)

### Test cases

```
let f =

n=>(g=b=>[...s=n.toString(b)].reverse().join``==s)()&g(2,n/=n&-n)

console.log(f(1 )) // Truthy
console.log(f(6 )) // Truthy
console.log(f(9 )) // Truthy
console.log(f(10)) // Falsey
console.log(f(12)) // Falsey
console.log(f(13)) // Falsey
console.log(f(14)) // Falsey
console.log(f(33)) // Truthy
console.log(f(44)) // Falsey
```

# Answer
> 5 votes
# Mathematica, ~~52~~ 49 bytes

```
i=IntegerReverse;i@#==#&&!i[#,2,Range@#]~FreeQ~#&

```

Try it on Wolfram Sandbox

### Usage

```
f = (i=IntegerReverse;i@#==#&&!i[#,2,Range@#]~FreeQ~#&);

```

---

```
f[6]

```

> `True`

```
f /@ {9, 14, 33, 44}

```

> `{True, False, True, False}`

### Explanation

```
i=IntegerReverse;i@#==#&&!i[#,2,Range@#]~FreeQ~#&

i=IntegerReverse                                   (* Set i to the integer reversing function. *)
                 i@#==#                            (* Check whether the input reversed is equal to input. *)
                       &&                          (* Logical AND *)
                          i[#,2,Range@#]           (* Generate the binary-reversed versions of input, whose lengths *)
                                                   (* (in binary) are `{1..<input>}` *)
                                                   (* trim or pad 0s to match length *)
                                        ~FreeQ~#   (* Check whether the result is free of the original input *)
                         !                         (* Logical NOT *)

```

### Version with builtin `PalindromeQ`

```
PalindromeQ@#&&!IntegerReverse[#,2,Range@#]~FreeQ~#&

```

# Answer
> 4 votes
# Pyth - 13 bytes

```
&_I.s.BQ`Z_I`

```

Test Suite.

# Answer
> 3 votes
# Jelly, 8 bytes

```
Bt0ŒḂaŒḂ

```

Try it online!

# Answer
> 3 votes
# Japt, 14 bytes

```
s ê¬©¢w n2 ¤ê¬

```

Test it online!

### Explanation

```
 s ê¬ © ¢   w n2 ¤  ê¬
Us êq &&Us2 w n2 s2 êq   Ungolfed
                         Implicit: U = input integer
Us êq                    Convert U to a string and check if it's a palindrome.
        Us2 w            Convert U to binary and reverse.
              n2 s2      Convert to a number, then back to binary, to remove extra 0s.
                    êq   Check if this is a palindrome.
      &&                 Return whether both of these conditions were met.

```

# Answer
> 2 votes
# Proton, 57 bytes

```
a=>(b=c=>c==c[to by-1])(str(a))*b(bin(a)[2to].strip('0'))

```

Try it online!

# Answer
> 2 votes
# APL, 27 31 Bytes

```
∧/(⌽≡⊢)∘⍕¨{⍵,⊂{⍵/⍨∨\⍵}⌽2⊥⍣¯1⊢⍵}

```

How's it work? Using 6 as the argument...

```
      2⊥⍣¯1⊢6 ⍝ get the bit representation
1 1 0

      ⌽2⊥⍣¯1⊢6 ⍝ reverse it (if it's a palindrome, it doesn't matter)
0 1 1

      {⍵/⍨∨\⍵}⌽2⊥⍣¯1⊢6 ⍝ drop off the trailing (now leading 0's)
1 1

      6,⊂{⍵/⍨∨\⍵}⌽2⊥⍣¯1⊢6 ⍝ enclose and concatenate the bits to the original number
┌─┬───┐
│6│1 1│
└─┴───┘

      (⌽≡⊢)∘⍕ ⍝ is a composition of
      ⍕ ⍝ convert to string and
      (⌽≡⊢) ⍝ palindrome test

      (⌽≡⊢)∘⍕¨6,⊂{⍵/⍨∨\⍵}⌽2⊥⍣¯1⊢6 ⍝ apply it to each of the original argument and the bit representation
  1 1

      ∧/(⌽≡⊢)∘⍕¨6,⊂{⍵/⍨∨\⍵}⌽2⊥⍣¯1⊢6  ⍝ ∧/ tests for all 1's (truth)
  1

```

Try it on TryAPL.org

# Answer
> 2 votes
# Brachylog, 7 bytes

```
↔?ḃc↔.↔

```

Try it online!

That's a lot of 's…

### Explanation

With the implicit input and output, the code is: `?↔?ḃc↔.↔.`

```
?↔?        The Input is a palindrome
   ḃ       Convert it to the list of its digits in binary
    c      Concatenate it into an integer
     ↔     Reverse it: this causes to remove the trailing 0's
      .↔.  The resulting number is also a palindrome

```

# Answer
> 1 votes
# Perl, 53 +3 (-pal) bytes

```
$_=sprintf"%b",$_;s/0+$//;$_="$_/@F"eq reverse"@F/$_"

```

try it online

# Answer
> 1 votes
# APL (Dyalog Classic), 26 bytes

```
{≡∘⌽⍨⍕⍵,⍵,⍨(<\⊂⊢)⌽2⊥⍣¯1⊢⍵}

```

## Explanation

```
                  2⊥⍣¯1⊢⍵  encode ⍵ as binary
                 ⌽         reverse
           (<\⊂⊢)          partition from first 1
      ⍵,⍵,⍨                prepend and append ⍵
    ⍕                     turn into text string
≡∘⌽⍨                       match text with its reverse (f⍨X is XfX, where f is a composed function that reverses its right argument and matches with left)

```

Try it online!

# Answer
> 1 votes
# Octave, ~~68~~ 66 bytes

```
@(x)all([d=num2str(x) b=deblank(['' dec2bin(x)-48])]==flip([b d]))

```

Try it online!

Initial offering from Octave.

We basically create an array containing the number as a decimal string and the number as a binary string with trailing 0's removed. Then we create an array with the same to strings but with the binary and decimal numbers flipped. Finally both arrays are compared and the result is either true if they match (both palindromes) or false if they don't (one or both not palindromes).

---

* Save 2 bytes using `flip` instead of `fliplr`.

# Answer
> 1 votes
# Pyt, 10 bytes

Returns \[1\] if true, \[0\] if false

```
ĐɓƖ₫áĐ₫=ʁ∧

```

Try it online!

Explanation:

```
              Implicit input
Đ             Duplicate input
ɓ             Get input in binary (as string)
Ɩ             Cast to integer
₫             Reverse the digits (this removes any trailing zeroes)
á             Push the stack into a list
Đ             Duplicate the list
₫             Reverse the digits of each element of the list
=             Are the two lists equal element-wise
ʁ∧            Reduce the list by bitwise AND

```

# Answer
> 0 votes
# C# (.NET Core), ~~130 129 179~~ 173 + 23 bytes

a few things, thank you to Ed Marty for pointing out that i need to check for as many 0's padded in front for a palindrome. And i need to make sure that i can check up to x^32-1.

```
x=>{var a=Convert.ToString(x,2);var b=x+"";Func<string,bool>p=z=>z.SequenceEqual(z.Reverse());return new int[a.Length].Select((_,z)=>p(new string('0',z)+a)).Any(z=>z)&p(b);}

```

Try it online!

# Answer
> 0 votes
# Retina, 72 bytes

```
.+
$*_;$&
+`(_+)\1
$+0
0_
_
0+;
;
+`\b(\w)((\w*)\1)?\b
$3
(\B;\B)|.*
$.1

```

Try it online! Link includes test cases. Works by creating a unary duplicate of the original number, but using `_`s so that it's not confused by e.g. an input of `11`. The unary number is then converted to "binary" and trailing zeros stripped. Palindromes then get successively truncated and the last stage tests whether there is anything left.

# Answer
> 0 votes
# Mathematica, 70 bytes

```
(P=PalindromeQ)[PadRight[#~IntegerDigits~2,#~IntegerExponent~2]]&&P@#&

```

# Answer
> 0 votes
# Husk, 14 bytes

```
¤&S=↔ȯ↓=0↔ḋ⁰d⁰

```

Try it online!

### Ungolfed/Explanation

```
             d⁰  -- digits of input in decimal
          ḋ⁰)    -- digits of input in binary
         ↔       --   reverse
     (↓=0        --   and drop all leading zeros
¤&               -- test the two lists if
  S=↔            --   they're equal to their own reverse

```

# Answer
> 0 votes
# Gaia, 10 bytes

```
ṙṭ@ḍ2⁻Πbṭ∧

```

Try it online!

### Explanation

Instead of checking with leading zeroes in binary, I check without without the trailing zeros.

```
ṙ           String representation of number
 ṭ          Is palindromic?
  @         Push input again
   ḍ        Prime factors
    2⁻      Remove all 2s
      Π     Product
       b    Convert to binary
        ṭ   Is palindromic?
         ∧  Logical and

```

# Answer
> 0 votes
# C (gcc), 105 bytes

```
r(n,b){int s=0,c=n;for(;n;n/=b)s=s*b+n%b;return s==c;}
c;f(n){for(c=n;c%2<1;c/=2);return r(n,10)&r(c,2);}

```

Try it online!

# Answer
> 0 votes
# Pyth, ~~25~~ ~~22~~ ~~19~~ ~~18~~ 17 bytes

-~~3~~ ~~6~~ ~~7~~ 8 bytes by learning the language further

```
Ks_.Bsz&_IzqKs_`K

```

Explanation:

```
Ks        Set K to the integer version of...
 _.BsJ    Reverse string of the binary input
&         And
 _Iz      Is the input equal to the reverse of itself?
 qKs_`K   Is K equal to int(the reverse of basically string(K))

```

I am sure that this can be golfed down, I'll be working on that.

Test Suite

# Answer
> 0 votes
# Python 2, 56 bytes

```
lambda n:all(s==s[::-1]for s in(`n`,bin(n).strip("0b")))

```

Try it online!

Uses Python's `strip` method to both remove the `bin(..)`'s output's leading `0b` *and* the binary number's trailing zeros (as they will always have a matching bit).

# Answer
> 0 votes
# Java 8, ~~105~~ 104 bytes

```
n->{String t=n+n.toString(n,2).replaceAll("0*$","")+n;return t.contains(new StringBuffer(t).reverse());}

```

**Explanation:**

Try it here.

```
n->{                         // Method with Integer parameter and boolean return-type
  String t=n                 //  Create a String `t` starting with the input Integer
    +n.toString(n,2)         //  Append the binary representation of the input Integer,
      .replaceAll("0*$","")  //   with all trailing zeroes removed
    +n;                      //  Append the input Integer again
  return t.contains(new StringBuffer(t).reverse());
                             //  Return true if `t` is a palindrome
}                            // End of method

```

# Answer
> 0 votes
# PHP, 69+1 bytes

```
$q=trim(decbin($p=$argn),0);if(strrev($p)==$p&&strrev($q)==$q)echo$p;

```

Run as pipe with `-nR`
Echoes the original input for truthy / nothing for falsey

Try it online!

# Answer
> 0 votes
# APL2 (not Dyalog), 36 bytes

```
(N≡⌽N←⍕N)^∨/(((⌽B)⍳1)↓B)⍷B←(32⍴2)⊤N←

```

First let B be the 32-bit representation of N:

```
B←(32⍴2)⊤N

```

Then mirror B and find the position of the 1st 1:

```
(⌽B)⍳1

```

Then drop that many positions from B. This will preserve the correct number of leading 0s.

Then perform FIND and an OR-REDUCTION to see if the cropped B contains its own mirror.

Now let's look at N, the decimal. The left-most bracketed expression converts N to a character vector and checks if it MATCHes its own mirror.

Finally, an AND joins the two checks.

---

In APL2 I can't make a neat lambda so I wrote a one-liner and included the assignment arrow. Hope this isn't cheating.

---
Tags: code-golf, number, binary, palindrome
---


title: Conjugate permutations

text:
# Question
Title: Conjugate permutations
A permutation of size **n** is a reordering of the first **n** positive integers. (meaning each integer appears once and exactly once). Permutations can be treated like functions that change the order of a list of items of size **n**. For example

```
(4 1 2 3) ["a", "b", "c", "d"] = ["d", "a", "b", "c"]

```

Thus permutations can be composed like functions.

```
(4 1 2 3)(2 1 3 4) = (4 2 1 3)

```

This brings about a lot of interesting properties. Today we are focusing on ***conjugacy***. Permutations **y** and **x** (both of size **n**) are conjugates iff there are permutations **g** and **g-1** (also of size **n**) such that

```
x = gyg<sup>-1</sup>
```

and **gg-1** is equal to the identity permutation (the first **n** numbers in proper order).

Your task is to take two permutations of the same size via standard input methods and decide whether they are conjugates. You should output one of two consistent values, one if they are conjugates and the other if they are not.

This is so answers will be scored in bytes with fewer bytes being better.

There are lots of theorems about conjugate permutations that are at your disposal, so good luck and happy golfing.

You may take input as an ordered container of values (either 1-n or 0-n) representing the permutation like above, or as a function that takes a ordered container and performs the permutation. If you choose to take function you should take it as an argument rather than have it at a predefined name.

## Test Cases

```
(1) (1) -> True
(1 2) (2 1) -> False
(2 1) (2 1) -> True
(4 1 3 2) (4 2 1 3) -> True
(3 2 1 4) (4 3 2 1) -> False
(2 1 3 4 5 7 6) (1 3 2 5 4 6 7) -> True

```

# Answer
# Python 2, 87 bytes

```
f=lambda P,k:k<1or len({sum([x==eval('L['*k+'x'+']'*k)for x in L])for L in P})&f(P,k-1)

```

Try it online!

Takes input with `P` as a pair of both permutations and `k` their length. Outputs `1` for conjugates and `0` not.

This uses the result:

> Two permutations **x** and **y** are conjugate exactly if their **k**-th powers **xk** and **yk** have an equal number of fixed points for every **k** from **0** to **n**.

Two conjugate permutations satisfy this because their **k**-th powers are also conjugate, and conjugacy preserves the count of fixed points.

It's less obvious that any two non-conjugate permutations always differ. In particular, conjugacy is determined by the sorted list of cycle lengths, and these can be recovered from the counts of fixed points. One way to show this is with linear algebra, though it might be overkill.

Let **X** be the permutation matrix for **x**. Then, the number of fixed points of **xk** is **Tr(Xk)**. These traces are the power sum symmetric polynomials of the eigenvalues of **Xk** with multiplicity. These polynomials for **k** from **0** to **n** let us recover the corresponding elementary symmetric polynomials of these eigenvalues, and therefore the characteristic polynomial and so the eigenvalues themselves.

Since these eigenvalues are roots of unity corresponding to the cycles of **x**, from these we can recover the cycle sizes and their multiplicities. So, our "signature" identifies the permutation up to conjugation.
> 6 votes

# Answer
# , ~~25 bytes~~ ~~23 bytes~~ 16 bytes

*miles'* tacit solution :

```
-:&([:/:~#&>)&C.

```

OP's explicit solution :

```
c=:4 :'-://:~"1#&>C.&>x;y'

```

This checks whether permutations x and y have the same cycle type, using the built-in `C.` function to produce cycle representations.

```
   4 1 3 2   c   4 2 1 3
1
   3 2 1 4   c   4 3 2 1
0
   2 1 3 4 5 7 6   c   1 3 2 5 4 6 7
1

```
> 6 votes

# Answer
# MATL, ~~20~~ ~~19~~ ~~17~~ 16 bytes

```
xY@!"&G@)@b)X=va

```

Input: two column vectors (using `;` as separator). Output: `1` if conjugate, `0` if not.

Try it online! Or verify all test cases.

### Explanation

No theorems about permutations used (out of sheer ignorance); just brute force and these two facts:

* For two permutations **p** and **q**, the composition **pq** is equivalent to using **p** to index the elements of **q**.
* The condition **x** = **gyg**−1 is equivalent to **xg** = **gy**.

Commented code:

```
x      % Implicitly input first permutation, x. Delete it. Gets copied into clipboard G
Y@     % Implicitly input second permutation, y. Push a matrix with all permutations
       % of its elements, each permutation on a different row. So each matrix row is
       % a permutation of [1 2 ...n], where n is the size of y
!      % Transpose. Now each permutation is a column
"      % For each column
  &G   %   Push x, then y
  @    %   Push current column. This is a candidate g permutation
  )    %   Reference indexing. This gives g composed with y
  @    %   Push current column again
  b    %   Bubble up. Moves x to the top of the stack
  )    %   Reference indexing. This gives x composed with g
  X=   %   Are they equal as vectors? Gives true or false
  v    %   Concatenate stack so far. The stack contains the latest true/false result
       %   and possibly the accumulated result from previous iterations
  a    %   Any: gives true if any element is true. This is the "accumulating" function
       % Implicit end. Implicit display

```
> 4 votes

# Answer
# Jelly, 11 bytes

```
Œ!©Ụ€ịị"®⁸e

```

Try it online!

### How it works

```
Œ!©Ụ€ịị"®⁸e  Main link. Left argument: x. Right argument: y

Œ!©          Take all permutations g of x. Copy the result to the register.
   Ụ€        Grade up each; sort the indices of each permutation g by their
             corresponding values. For permutations of [1, ..., n], grading up
             essentially computes the inverse, g⁻¹.
     ị       Let each g⁻¹ index into y, computing g⁻¹y.
      ị"®    Let the results index into the corresponding g, computing g⁻¹yg.
         ⁸e  Test if x occurs in the result.

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), 44 bytes

```
Equal@@(PermutationCycles[#,Sort[0#]&]&/@#)&

```

Try it online!

---

# Wolfram Language (Mathematica), 44 bytes

```
x_±y_:=Or@@(#[[x]]==y[[#]]&/@Permutations@x)

```

Using CP-1252 encoding, where `±` is one byte.

Try it online!
> 2 votes

# Answer
# Husk, 9 bytes

```
¤¦ṠmöLU¡!

```

Returns `1` for conjugate and `0` for non-conjugate. Try it online!

## Explanation

The conjugacy class of a permutation **P** of **L = \[1,2,..,n\]** is determined by the multiset containing the least period of each number in **L** under **P**. When **P** is taken in list format, I can replace **L** with **P** and get the same multiset. The program computes the corresponding multiset for each input and checks if one is a sub-multiset of the other. Since they have the same number of elements, this is equivalent to being the same multiset.

```
¤¦ṠmöLU¡!  Implicit inputs: two lists of integers.
¤          Apply one function to both and combine with another function.
  ṠmöLU¡!  First function. Argument: a list P.
  Ṡm       Map this function over P:
       ¡!  iterate indexing into P,
      U    take longest prefix with unique elements,
    öL     take its length.
 ¦         Combining function: is the first list a subset of the other, counting multiplicities?

```
> 1 votes

# Answer
# Perl, ~~61~~ ~~58~~ 57 bytes

Includes `+2` for `ap`

Give 0-based permutations as 2 lines on STDIN

```
perl -ap '$_=[@1]~~[@1=map{-grep$_-$G[$i++%@G],@F=@G[@F]}@G=@F,0]'
3 0 2 1
3 1 0 2
^D

```

Algorithm is a minor variation on the one in xnor's solution

This older version of the code hits a perl bug and dumps core for several inputs on my latest perl `5.26.1`, but it works on an older perl `5.16.3`.

```
@{$.}=map{-grep$_==$F[$i++%@F],@G=@F[@G]}@G=@F,0}{$_=@1~~@2

```

It's possibly yet another instance of my old perlgolf enemy, the fact that perl doesn't properly refcount its stack.
> 1 votes

# Answer
## JavaScript (ES6), ~~66~~ 64 bytes

```
(a,b,g=a=>b+a.map(h=(e,i)=>e-i&&1+h(a[e],i)).sort())=>g(a)==g(b)

```

If I've read the other answers correctly, the problem is equivalent to counting the periods of all the elements and checking that the two lists have the same number of each period. Edit: Saved 1 byte thanks to @Arnauld by calculating one less than the period. Saved another byte thanks to @Arnauld by abusing JavaScript's weird coercion rules to compare the arrays. Another byte could be saved by currying but I don't like curry unless it's chicken tikka masala.
> 1 votes

---
Tags: code-golf, decision-problem, combinatorics, permutations, abstract-algebra
---


title: Interpret deadfish

text:
# Question
Title: Interpret deadfish
> Please participate in the ***meta discussion about reopening this challenge*** before casting a vote.

# Introduction

This challenge was inspired by .

Deadfish is a non-Turing-complete programming language, created by Jonathan Todd Skinner. It has an accumulator register and contains 4 commands, `i`, `d`, `s`, and `o`, standing for increment, decrement, square, and output, respectively. While this seems simple enough, the original implementation has some quirks that must be present in your interpreter.

Unlike a similar challenge here, this does not require the interpreter to be interactive.

# Challenge

The challenge is to write a fully functional Deadfish interpreter, quirks included. The following requirements must be met:

* The accumulator must be more than 8 bits wide.
* When an `i` is encountered, increment the accumulator by 1.
* When a `d` is encountered, decrement the accumulator by 1.
* When an `s` is encountered, square the value of the accumulator.
* When an `o` is encountered, print the value of the accumulator along with a newline.
* When any other character is encountered, including control characters and whitespace but not a newline, print a newline.
* If and only if the accumulator equals `-1` or `256`, set the accumulator to `0`.

# Test cases

From the esolangs article:

```
iissso -> 0
diissisdo -> 288
iissisdddddddddddddddddddddddddddddddddo -> 0

```

# Rules

* Input may be accepted through STDIN or as argument(s).
* Standard loopholes are disallowed
* This is , so the shortest solution in bytes wins

# Answer
> 0 votes
# Proton, 114 bytes

```
a=0s={"i":(a=>a+1),"d":(a=>a-1),"s":(a=>a*a),"o":(a=>[print(a),a][1])}for i:input(){a=s[i](a)if a in[-1,256]{a=0}}

```

Try it online!

The fact that this even parses correctly demonstrates how weird Proton 1 is o\_O

---
Tags: code-golf, interpreter, deadfish
---


title: Take a byte out of it!

text:
# Question
Title: Take a byte out of it!
Your task is to, given an unsigned integer `n`, find the largest number which can be created by removing a single byte (8 consecutive bits) of data.

---

## Example

Given the number `7831`, we first convert it to binary (removing any leading zeroes):

```
1111010010111

```

We then find the consecutive group of 8 bits which, when removed, will yield the largest new result. In this case, there are 3 solutions, shown below

```
1111010010111
  ^      ^
   ^      ^
    ^      ^

```

Removing this any of these yields `11111`, which we then convert back to its decimal value `31` for the answer.

---

## Test Cases

```
256        ->   1
999        ->   3
7831       ->   31
131585     ->   515
7854621    ->   31261
4294967295 ->   16777215 (if your language can handle 32 bit integers)

```

---

## Rules

* It is guaranteed that the bit length of `n` will be larger than 8.
* Your solution should theoretically work for any bit length of `n` larger than 8, but in practice, needs only work for integers **255 \< n \< 216**
* Input/Output should be in decimal.
* You may submit a full program or a function.
* This is , so the shortest program (in bytes) wins!

# Answer
> 16 votes
# Jelly, 6 bytes

```
BḄ-8ƤṀ

```

A monadic link taking a number and returning a number.

**Try it online!**

### How?

Uses a nice quick, `Ƥ`, developed by miles...

```
BḄ-8ƤṀ - Link: number
B      - convert to a binary list
    Ƥ  - for loop over some slices to be determined...
  -8   - this is a negative nilad, therefore: use overlapping outfixes of length 8
       -   (exactly what the specification asks us to inspect)
 Ḅ     -   convert from a binary list to an integer (vectorises)
     Ṁ - maximum

```

# Answer
> 8 votes
# , 12 bytes

```
[:>./8#.\.#:

```

Try it online!

```
          #:     to binary
     8  \.       remove consecutive groups of eight
      #.         convert each result to decimal
  >./            maximum
[:               do nothing, this lets me avoid parentheses

```

# Answer
> 7 votes
# Python 2, 41 bytes

```
f=lambda n:n>>8and max(n>>8,2*f(n/2)+n%2)

```

Try it online!

# Answer
> 6 votes
## JavaScript (ES6), 54 bytes

```
f=(n,v=n>>8,b=1,m=0)=>b>v?m:f(n,(v^n)&b^v,b+b,v>m?v:m)
```

```
<input type=number min=256 max=2147483647 oninput=o.textContent=f(this.value)><pre id=o>
```

Works up to 2\**31-1. Because someone asked for a bit-twiddling answer...

# Answer
> 4 votes
# Pyth, 21 bytes

```
L&K.>b8eS,K+*2y/b2%b2

```

This is a recursive function (must be called with `y`, or see the link).

**Try it here!**

# Answer
> 3 votes
# Mathematica, 69 bytes

```
Max@Array[Drop[#&@@s,#;;#+7]~FromDigits~2&,Last[s=#~RealDigits~2]-7]&

```

Try it online!

This solution works for **large** numbers Try it online!

-3 bytes from KellyLowder

# Answer
> 3 votes
# Python 3, 68 66 60 bytes

 -2 bytes thanks to Mr. Xcoder!

 -4 bytes thanks to ovs!

 -2 bytes thanks to Erik the Outgolfer!

```
lambda n:max(n%2**i|n>>i+8<<i for i in range(len(bin(n))-9))

```

Try it online!

# Answer
> 3 votes
# Wolfram Language (Mathematica), 46 bytes

```
Floor@If[#<256,0,Max[#/256,2#0[#/2]+#~Mod~2]]&

```

Try it online!

This version can only handle inputs up to 2518-1, otherwise we run into Mathematica's stack size limit. (The bound may vary between Mathematica installations.) The second solution in this answer avoids that.

# How it works

A recursive approach based on the following logic:

* The maximal value should be `0` for any input less than `256`, since taking a byte out of the number eats the whole number. This is our base case, which is why it's included even though the specs promise us we won't have to handle such inputs.
* Otherwise, we take the `Max` of two options: eat the lowest byte (giving us the input divided by `256`) or chop off the lowest bit, recurse on the remaining integer, and append the lowest bit back when we're done.

# Wolfram Language (Mathematica), 55 bytes

```
Max@Table[Mod[#,m=2^k]+Floor[#/m/2^8]m,{k,0,Log2@#-8}]&

```

Try it online!

An alternate version that builds a table instead of recursion, so it works for numbers of any size that Mathematica can handle.

# Answer
> 2 votes
# Java (OpenJDK 8), ~~138~~ 134 bytes

```
i->{int l=0,m=0,x;String y=i.toString(i,2);for(;l<y.length()-7;m=x>m?x:m)x=i.valueOf(y.substring(0,l)+y.substring(l+++8),2);return m;}

```

Try it online!

# Answer
> 2 votes
# Jelly, 12 bytes

```
BJṡ8ḟ@€ƊịBḄṀ

```

Try it online!

Saved bytes thanks to Jonathan Allan!

# Answer
> 2 votes
# C (gcc), ~~91~~ bytes

```
j;m;t;f(x){for(j=m=0;t=x>>j+8;m<t?m=t:j++)t=t<<j|x%(1<<j);return m;}

```

-23 bytes from Colera Su

Supports up to `2**31-1`

Try it online!

Starts with the low 8 bits `(j=0)`, then goes up, changing output if the number with bits `[j,j+8)` cut out is bigger than our current, and continuing until x has no bits above `j+8`

# Answer
> 2 votes
# Retina, ~~71~~ ~~67~~ 64 bytes

```
.+
$*
+`(1+)\1
$+0
01
1
.
$`_$'¶
_.{7}

A`_
O^`
1G`
+1`\B
:$`:
1

```

Try it online! Link only includes the faster test cases, so as not to unduly overload Dennis's server. Edit: Saved 3 bytes thanks to @MartinEnder. Explanation:

```
.+
$*
+`(1+)\1
$+0
01
1

```

Convert from decimal to binary.

```
.
$`_$'¶
_.{7}

A`_

```

Construct a list of strings obtained by deleting 8 consecutive digits in all possible ways.

```
O^`
1G`

```

Sort them in reverse order and take the first (largest).

```
+1`\B
:$`:
1

```

Convert back to decimal. (See @MartinEnder's explanation.)

# Answer
> 2 votes
# ReRegex, ~~294~~ 275 bytes

*Saved 19 bytes by using better 'function' definitions*

I'd say this is pretty good for a Regex only language.

The base lib does allow for conversion between Unary and Decimal (Which is needed as the challenge spec explicitly states decimal), but does not support Binary; So I had to write that as part of the script adding 120 bytes to it.

```
#import base
b(\d*):(_*)\2_b/b1$1:$2b/b(\d*):(_+)\2b/b0$1:$2b/b(\d+):b/$1/b:b/0/B(_*):1/B$1$1_:/B(_*):0/B$1$1:/B(_*):B/$1/j(\d*),\1(\d)(\d{7})(\d*):/j$1$2,$1$2$3$4:,B:$1$4B/j(\d*),\1\d{0,7}:,?(.*)/,$2,/,((_+)_+),(\2),/,$1,/,(_+),(\1_*),/,$2,/^,(_*),$/d<$1>/j,b:u<(?#input)>b:

```

Try it online!

## By Individual Regexes.

```
#import base
b(\d*):(_*)\2_b/b1$1:$2b/
b(\d*):(_+)\2b/b0$1:$2b/
b(\d+):b/$1/
b:b/0/
B(_*):1/B$1$1_:/
B(_*):0/B$1$1:/
B(_*):B/$1/
j(\d*),\1(\d)(\d{7})(\d*):/j$1$2,$1$2$3$4:,B:$1$4B/
j(\d*),\1\d{0,7}:,?(.*)/,$2,/
,((_+)_+),(\2),/,$1,/
,(_+),(\1_*),/,$2,/
^,(_*),$/d<$1>/
j,b:u<(?#input)>b:

```

## Steps

Firstly, we import the 'base' library, which gives two regexes. One which converts `u<numbers>` into unary. And one which converts `d<unary_underlines>` back into decimal. This is because the challenge requires IO in base10.

Then we define a handful of regexes which convert unary into binary.

```
b(\d*):(_*)\2_b/b1$1:$2b/
b(\d*):(_+)\2b/b0$1:$2b/
b(\d+):b/$1/
b:b/0/

```

The first of these, `b(\d*):(_*)\2_b/b1$1:$2b/` searches for `b`, optionally followed by some binary digits, then a `:`, Then any amount of underlines, followed by the exact same amount of underlines plus one, and finally another `b`.

We then replace that with `b1` followed by the binary digits from before, `:`, and just the first half of the underscores, and finally the last `b`.

So this checks if the unary is not divisible by two, and if so, prepends 1 to it's binary digits, then divides it minus one by two.

The second one, `b(\d*):(_+)\2b/b0$1:$2b/` is almost idendical, however does not check for an extra `_`, meaning it only matches if it is divisible by two, and in this case prepends a `0` instead.

The third one checks if we're out of unary digits, and if so, strips away the padding to just leave the binary digits.

The last one checks if there never was any binary digits supplied, and in that case just leaves `0`.

The next group of Regexes we define are to convert binary back into unary, and are slightly more simple.

```
B(_*):1/B$1$1_:/
B(_*):0/B$1$1:/
B(_*):B/$1/

```

The first of this group, `B(_*):1/B$1$1_:/`, much like its antithesis, detects a `B`, followed by any amount of Unary digits, then `:1`. It doesn't check for the matching `B` in this case, as it is only searching for one digit at a time. If this is matched, it doubles the previously matched amount of unary digits and adds one, then removes the one.

The second, `B(_*):0/B$1$1:/`, is almost idendical to the first, except matches a `0` rather than a `1`, and does not add an additional unary digit.

The last of these, `B(_*):B/$1/`, checks if there are no more binary digits, and if so unwraps the unary. Unlike its antithesis, this does not need a special 0 case.

Next we define the `j` regexes, which act as a splitting function.

```
j(\d*),\1(\d)(\d{7})(\d*):/j$1$2,$1$2$3$4:,B:$1$4B/
j(\d*),\1\d{0,7}:,?(.*)/,$2,/

```

The first, `j(\d*),\1(\d)(\d{7})(\d*):/j$1$2,$1$2$3$4:,B:$1$4B/` does most of the heavy lifting. It searches for `j`, optionally followed by binary digits which are the "incrementer", then a comma followed by the incrementer then exactly 8 binary digits followed by the rest of the binary number, then a `:`. The first of the 8 digits is appended to the incrementer, thus incrementing it, then everything but those 8 digits from the binary input is appended after the `:` following a `,`. So (If we were using 2 digits instead of 8) `j,1001:` would become `j1:1001:,01` then `j10:1001,01,11`. Additionally, the appended array elements are wrapped in `B`s, to convert them back to unary.

The other, `j(\d*),\1\d{0,7}:,?(.*)/,$2,/` checks if there are less than 8 binary digits left to check after the incrementer, and if so, removes everything other than the array wrapped in `,`s. Eg. `,_,___,`

During and after the creation of the array we define the comparison regexes.

```
,((_+)_+),(\2),/,$1,/
,(_+),(\1_*),/,$2,/

```

The first of these, `,((_+)_+),(\2),/,$1,/` checks a comma followed by some amount of underscores, then some more, followed by a comma, then the first amount of underscores, than a comma. It then replaces it with the total amount of underscores in the first element surrounded by `,`s.

The latter, `,(_+),(\1_*),/,$2,/`, checks for a comma followed by some amount of underscores followed by another comma, then the same amount or more underscores, and a last comma. This will instead leave the right element.

Finally, when there is on element left thus matching `^,(_*),$`, we remove the surrounding commas and convert back to decimal via `d<>`. Then no-more regexes can fire and the output is presented.

The input is initially placed into the template `j,b:u<(?#input)>b:`, which first converts the decimal input to unary, eg `5` -\> `j,b:_____b:`, then the resulting unary to binary, `j,101:` Then splits the binary (which doesn't work for the example), gets the largest element, converts back to decimal, and done.

# Answer
> 1 votes
# JavaScript (ES6), ~~94~~ 91 bytes

*-3 bytes thanks to Justin Mariner*

```
f=(n,d='',c=n.toString(2).match(`(${d}).{8}(.*)`))=>c?Math.max('0b'+c[1]+c[2],f(n,d+'.')):0

```

Just throwing out a JavaScript string-based solution, but I'm hoping someone will post a separate bitwise-based solution so I might learn something.

My solution recursively grabs an 8-bit chunk from the string, taking the maximum value that is found.

```
f=(n,d='',c=n.toString(2).match(`(${d}).{8}(.*)`))=>c?Math.max('0b'+c[1]+c[2],f(n,d+'.')):0

console.log(f(256));
console.log(f(999));
console.log(f(7831));
console.log(f(131585));
console.log(f(7854621));
console.log(f(4294967295));
```

# Answer
> 1 votes
# C# (.NET Core), 122+13=135 120+13=133 bytes

```
n=>{int m=0,i=0,t;for(var b=Convert.ToString(n,2);i<b.Length-7;m=t>m?t:m)t=Convert.ToInt32(b.Remove(i++,8),2);return m;}

```

Try it online!

+13 for `using System;`

I imagine there is a way of doing this with out using `Convert`. Either way, I'm sure this could be reduced.

### Acknowledgements

-2 bytes thanks to Kevin Cruijssen

### UnGolfed

```
n=>{
    int m=0,
        i=0,
        t;

    // convert n to a binary string,
    // go through removing each possible byte,
    // check if this is the biggest int so far
    for (var b=Convert.ToString(n,2); i<b.Length-7; m=t>m?t:m)
        t=Convert.ToInt32(b.Remove(i++,8),2); // remove 8 bits from position i, then convert from binary string to int

    return m;
}

```

# Answer
> 1 votes
# MATL, ~~23~~ 21 bytes

```
Bn8-:"GB[]@8:q+(XBvX>

```

Try it online!

```
B                       % Implicitly grab input, convert to binary
 n8-:                   % Create list of 1,2,... n-8, with n the size of the binary string
     "                  % Loop over this list
      GB                % Grab the input again, convert to binary once more.
        @8:q+           % Create indices of a slice of length 8
             [](        % Index into binary string, delete the slice
                XB    % Convert the remainder from binary to integer
                  vX> % Get the maximum number so far.

```

Sadly, `Bn8-:8:!+q&)` only produces the slices to be removed, not the remainder we'd like to keep.

# Answer
> 1 votes
# PHP, 67+1 bytes

```
do$r=max($r,$argn&($x=2**$i++-1)|$z=$argn>>8&~$x);while($z);echo$r;

```

Run as pipe with `-nR` or try it online.

# Answer
> 1 votes
# Pyth, 19 bytes

```
eSmi.>>.<.BQd8d2a6l

```

Alternative answer:

```
eSmi.<<8.>.BQdd2a6l

```

Explanation:

```
eSmi.>>.<.BQd8d2a6lQ | Implicit Q at the end, where Q = input
  m             a6lQ | Map the over [0, 1, 2, ... , floor(log base 2 of Q) - 7]
         .BQ         |  Convert Q to binary string
       .<   d        |  Cyclically rotate left by d
      >      8       |  Get string from position 8 to end.
    .>        d      |  Cyclically rotate right by d
   i           2     |  Convert from binary string to integer
eS                   | Find the last element of sorted list (maximum value)

```

The other answer uses a similar approach, except that it rotates right first, and gets all bits except the last 8.

# Answer
> 0 votes
# Java (OpenJDK 8), 73 bytes

```
n->{int m=0,i=1;for(;i<n>>7;i*=2)m=Math.max(m,n&~-i|(n>>8&-i));return m;}

```

Try it online!

# Answer
> 0 votes
# Octave, ~~81~~ 80 bytes

```
@(x)max(bin2dec(dec2bin(x*(c=2.^(0:(b=nextpow2(x+1)-8))))(:,[1:b b+9:end]))'./c)

```

Try it online!

This is a different solution to my original attempt, saving a further 14 bytes.

The code is broken down as follows:

```
@(x)max(                                                                       )
        bin2dec(                                                          )'./c
                                                         (:,[1:b b+9:end])
                dec2bin(x*(                            ))
                           c=2.^(0:                   )
                                   (b=nextpow2(x+1)-8)

```

On the sixth line the number of groups is calculated by finding the exponent of the next power of two larger than the input (number of bits in input number), and subtracting 7 as we are removing 8 bits from each group - the resulting number is stored in `b` for later.

We then calculate an array of powers of two on the fifth line which is large enough for all the possible groups that can be removed. We save this in variable `c` for later.

On the next line up (forth line), we multiply the input by the array of powers of two (essentially bit shifting each number up), and convert the result to binary. If we take the example of 7831, this results in a 2D array containing:

```
000001111010010111
000011110100101110
000111101001011100
001111010010111000
011110100101110000
111101001011100000

```

If we then chop out the centre 8 bits, that is equivalent to removing each of the groups of 8 bits. This is done by the third line.

The resulting array is converted back to decimal on the second line. We also have to divide by `c` to undo the scaling that was done to each group initially.

Finally on the first line an anonymous function is declared, and the maximum value from all groups is calculated.

---

* Save 1 byte by using `nextpow2(x+1)` rather than `nnz(bin2dec(x))`

---

---

### Original attempt - ~~120 98~~ 95 bytes

```
@(x)max(bin2dec(reshape(repmat(a=(d=@dec2bin)(x)',1,b=nnz(a)-7)(d(255*2.^(0:b-1))'<49),[],b)'))

```

Try it online!

The code is split up as follows:

```
@(x)max(                                                                                )
        bin2dec(                                                                             )
                reshape(                                                              ,[],b)'
                        repmat(a=(d=@dec2bin)(x)',1,b=nnz(a)-7)(                     )
                                                                d(255*2.^(0:b-1))'<49

```

Basically it calculates a matrix containing the possible groups of values that can be removed, and then works out which ends up giving the largest number.

Working line by line, the fifth line calculates the groups that can be removed. For example, take 7831. This is a 13bit number, giving the groups:

```
1111100000000
1111000000001
1110000000011
1100000000111
1000000001111
0000000011111

```

The result of the fifth line is a 2D logical array which can be used for indexing.

The fourth line of the code converts the input to an array of the bits (represented as characters '0' and '1'), and then replicates it `n`-7 times (where `n` in number of bits) giving one line for each possible grouping. The group mask above is used to remove each of the possible groups.

On the third line, the result is then reshaped to undo the unwanted flattening that resulted from applying the group mask. The second line converts back to an array of resulting decimal numbers. And the first line defines the anonymous function to be the maximum value of array of possible groups.

---

* Saved 22 bytes by generating the matrix of groups using maths.
* Saved 3 bytes in conversion from binary strings to logical group mask.

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

```
map{$\=$"if($"=oct$s=~s/.{$_}\K.{8}//r)>$\}2..length($s=sprintf'0b%b',$_)-10}{

```

Try it online!

# Answer
> 0 votes
# Ruby, 55 bytes

```
->n{(8../$/=~"%b"%n).map{|r|n>>8&(a=-1<<r-8)|n&~a}.max}

```

Try it online!

# Answer
> 0 votes
# Perl, 53 bytes

(the `use 5.10.1` to bring perl to lanugage level 5.10.1 is free)

Give the input number on STDIN. Will run out of memory for big numbers, but the 32-bit number in the input is not yet a problem

```
#!/usr/bin/perl
use 5.10.1;
$_=sprintf"%b",<>;/.{8}(?{\$F[oct"0b$`$'"]})^/;say$#F

```

---
Tags: code-golf, number, integer, binary, base-conversion
---


title: Infer geometric sequences

text:
# Question
Title: Infer geometric sequences
Haskell has this neat(-looking) feature where you can give it three numbers and it can infer an arithmetic sequence from them. For example, `[1, 3..27]` is equivalent to `[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27]`.

That's cool and all but arithmetic sequences are fairly limiting. Addition, *pfft*. Multiplication's where it's at. Wouldn't it be cooler if it did geometric sequences like `[1, 3..27]` returning `[1, 3, 9, 27]`?

## Challenge

Write a **program/function** that takes three positive integers **a**, **b**, and **c** and outputs `[**a**, **b**, **b** × (**b** ÷ **a**), **b** × (**b** ÷ **a**)<sup>**2**</sup>, ..., **x**]` where **x** is the greatest integer ≤ **c** that can be represented as `**b** × (**b** ÷ **a**)<sup>**n**</sup>` where **n** is a positive integer.

That is, the output should be **r**, such that:

```
**r**<sub>**0**</sub> = **a**
**r**<sub>**1**</sub> = **b**
**r**<sub>**n**</sub> = **b** × (**b** ÷ **a**)<sup>**n**-**1**</sup>
**r**<sub>**last**</sub> = greatest integer ≤ **c** that can be represented as **b** × (**b** ÷ **a**)<sup>**n**</sup>
         where **n** is a positive integer
```

### Specifications

* Standard I/O rules **apply**.
* Standard loopholes are **forbidden**.
* **b** will always be divisible by **a**.
* **a** \< **b****c**
* This challenge is not about finding the shortest approach in all languages, rather, it is about finding the **shortest approach in each language**.
* Your code will be **scored in bytes**, usually in the encoding UTF-8, unless specified otherwise.
* Built-in functions (Mathematica might have one :P) that compute this sequence are **allowed** but including a solution that doesn't rely on a built-in is encouraged.
* Explanations, even for "practical" languages, are **encouraged**.

### Test cases

```
**a**   **b**   **c**     **r**

1   2   11    [1, 2, 4, 8]
2   6   100   [2, 6, 18, 54]
3   12  57    [3, 12, 48]
4   20  253   [4, 20, 100]
5   25  625   [5, 25, 125, 625]
6   42  42    [6, 42]
```

In a few better formats:

```
1 2 11
2 6 100
3 12 57
4 20 253
5 25 625
6 42 42

1, 2, 11
2, 6, 100
3, 12, 57
4, 20, 253
5, 25, 625
6, 42, 42

```

# Answer
> 7 votes
# Husk, 8 bytes

```
~↑≤Ṡ¡o//

```

Input is in order **b, c, a**. Try it online!

## Explanation

```
~↑≤Ṡ¡o//  Implicit inputs.
       /  a/b as exact rational number.
     o/   Divide by a/b (so multiply by b/a).
    ¡     Iterate that function
   Ṡ      on a. Result is the infinite list [a, b, b^2/a, b^3/a^2, ..
 ↑        Take elements from it while
~ ≤       they are at most c.

```

The control flow in this program is a bit hard to follow. First, **b** is fed to the rightmost `/`, producing a function `/b` that divides by **b**. Next, `~` splits the remaining program into three parts: `~(↑)(≤)(Ṡ¡o//b)`. This feeds **c** to  and **a** to `Ṡ¡o//b`, and combines the results with . The result of `≤c` is a function that checks if its argument is at most **c**, and `↑≤c` takes the longest prefix of elements for which this holds.

It remains to show how `(Ṡ¡o//b)a` evaluates to the desired infinite list. The part in parentheses is split into `Ṡ(¡)(o//b)`. Then  feeds **a** to `o//b`, feeds the result to `¡`, and then gives **a** to its second argument. The expression `(o//b)a` gives a function that takes a number and divides it by **a/b**, and `¡` iterates this function on its second argument, which is **a**.

Here is a series of transformations that visualize the explanation:

```
  (~↑≤Ṡ¡o//) b c a
= (~↑≤Ṡ¡o/(/b)) c a
= ~(↑)(≤)(Ṡ¡o/(/b)) c a
= ↑(≤c)((Ṡ¡o/(/b)) a)
= ↑(≤c)(Ṡ(¡)(o/(/b)) a)
= ↑(≤c)(¡(o/(/b)a) a)
= ↑(≤c)(¡(/(/ba))a)
Last line in English: takeWhile (atMost c) (iterate (divideBy (divideBy b a)) a)

```

Alternative solution using explicit variables in order **a, b, c**:

```
↑≤⁰¡*/⁵²

```

# Answer
> 5 votes
# Python 2, 42 bytes

```
a,b,c=input()
x=b/a
while c/a:print a;a*=x

```

Try it online!

### Recursive approach, ~~42~~ 41 bytes

-1 byte thanks to ovs

```
f=lambda a,b,c:c/a*[a]and[a]+f(b,b*b/a,c)

```

Try it online!

# Answer
> 4 votes
# Proton, 35 bytes

```
f=(a,b,c)=>c//a?[a]+f(b,b*b/a,c):[]

```

Try it online!

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

*Saved 4 bytes thanks to @Neil*

Takes input as `(b,c)(a)`.

```
(b,c)=>g=a=>a>c?[]:[a,...g(b,b*=b/a)]

```

### Test cases

```
let f =

(b,c)=>g=a=>a>c?[]:[a,...g(b,b*=b/a)]

console.log(JSON.stringify(f(2,11)(1)))
console.log(JSON.stringify(f(6,100)(2)))
console.log(JSON.stringify(f(12,57)(3)))
console.log(JSON.stringify(f(20,253)(4)))
console.log(JSON.stringify(f(42,42)(6)))
```

### Commented

```
(b, c) =>                 // main function taking b and c
  g = a =>                // g = recursive function taking a
    a > c ?               //   if a is greater than c:
      []                  //     stop recursion and return an empty array
    :                     //   else:
      [ a,                //     return an array consisting of a, followed by
        ...g(             //     the expanded result of a recursive call to g()
          b,              //       with a = b
          b *= b / a      //       and b = b * ratio
        ) ]               //     end of recursive call

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), 22 bytes

```
PowerRange[#,#3,#2/#]&

```

Try it online!

# Answer
> 3 votes
# Pari/GP, 38 bytes

```
f(a,b,c)=powers(b/a,logint(c\a,b/a),a)

```

Try it online!

# Answer
> 2 votes
# Python 3, ~~93~~ ~~90~~ ~~74~~ 73 bytes

```
x=lambda a,b,c,i=0,q=[]:a*(b/a)**i>c and q or x(a,b,c,i+1,q+[a*(b/a)**i])

```

Try It Online

Thanks to Rod and user202729 for helping me reduce quite some bytes!

# Answer
> 2 votes
# Octave, ~~38~~ 35 bytes

```
@(a,b,c)exp(log(a):log(b/a):log(c))

```

Try it online!

Turns out @LuisMendo's MATL approach also saves 3 bytes in Octave, despite repeating `log` three times.

# Answer
> 2 votes
# Perl 6, ~~26~~ 24 bytes

```
{$^a,$^b,$b²/$a...^*>$^c}
{$^a,*×$^b/$a...^*>$^c}

```

Try it online!

Perl 6's sequence operator `...` can infer geometric series natively.

Update: ...It *can*, but in this situation not inferring it is a bit shorter.

# Answer
> 1 votes
# 05AB1E, 12 bytes

Input in the order `c,b,a`

```
ÝmI¹Ý<m/ʒ¹›_

```

Try it online!

**Explanation**

```
Ý              # push the range [0 ... c]
 m             # raise b to the power of each
  I            # push a
   ¹Ý          # push the range [0 ... c]
     <         # decrement each
      m        # push a to the power of each
       /       # elementwise division of ranges
        ʒ      # filter, keep only elements that are
         ¹›_   # not greater than c

```

# Answer
> 1 votes
# MATL, 17 bytes

```
t:,qtiw^w]x/tb>~)

```

Try it online!

Just to get the ball rolling in MATL. I can't imagine there isn't a less verbose way of solving this.

# Answer
> 1 votes
## Haskell, 35 bytes

```
(a#b)c|a>c=[]|d<-div b a*b=a:(b#d)c

```

Try it online!

# Answer
> 1 votes
# MATL, 12 bytes

```
y/ivZlZ}3$:W

```

Try it online! Or verify all test cases.

### Explanation

```
y     % Implicitly take two inputs, and duplicate the first onto the top
/     % Divide
i     % Take third input
v     % Vertically concatenate the three numbers into a column vector
Zl    % Binary logarithm, element-wise
Z}    % Split the vector into its three components
3$:   % Three-input range. Arguments are start, step, upper limit
W     % 2 raised to that, element-wise. Implicit display

```

# Answer
> 0 votes
# Perl, 38 bytes

Include `+3` for `-n` (the `use 5.10.0` to unlock the perl 5.10 features is free)

```
#!/usr/bin/perl -n
use 5.10.0;
/ \d+/;say,$_*=$&/$`until($_+=0)>$'

```

Then run as:

```
geosequence.pl <<< "1 3 26"

```

# Answer
> 0 votes
# Red, 50 bytes

```
g: func[a b c][if a <= c[print a g b b * b / a c]]

```

Try it online!

# Answer
> 0 votes
# Japt, 14 bytes

```
ÆWpX zVpXÉÃf§U

```

Try it

---

## Explanation

```
                    :Implicit input of integers U=c, V=a & W=b
Æ         Ã         :Range [0,U) and pass each X through a function
 WpX                :  W to the power of X
     z              :  Floor divide by
      VpXÉ          :  V to the power of X-1
           f§U      :Filter elements less than or equal to U

```

# Answer
> 0 votes
# Clean, 63 bytes

```
import StdEnv
$a b c=takeWhile((>=)c)[a:map(\n=b*b^n/a^n)[0..]]

```

Try it online!

# Answer
> 0 votes
# TI-BASIC, 31 bytes

Takes input from user and outputs in `Ans`. I solved for n in c = bn / an-1, getting n = 1 + ln(c/b) / ln(b/a). That's the same as n = 1 + logb/a(c/b). For the purposes of golfing, I start my sequence at -1 and end it at n-1 rather than 0 to n.

```
Prompt A,B,C
seq(B(B/A)^N,N,-1,logBASE(C/B,B/A

```

# Answer
> 0 votes
# APL (Dyalog Unicode), 38 bytes

```
{(g≤⊃⌽⍵)⊆g←f,(⍵[1]*p+1)÷(f←⊃⍵)*p←⍳⊃⌽⍵}

```

Try it online!

Prefix Dfn. Takes input in order `a b c`, and uses `⎕IO←0` (**I**ndex **O**rigin)

Thanks to @ErikTheOutgolfer for shaving 6 bytes out of this before I even posted it.

### How?

```
{(g≤⊃⌽⍵)⊆g←f,(⍵[1]*p+1)÷(f←⊃⍵)*p←⍳⊃⌽⍵} ⍝ Prefix Dfn. Input ⍵ is a vector
                                    ⌽⍵  ⍝ Reverse ⍵. Yields c b a
                                   ⊃    ⍝ Pick the first element (c)
                                  ⍳     ⍝ Index. Yields the integers 0..c-1
                                p←      ⍝ Assign to the variable p
                               *        ⍝ Exponentiate
                         (f←⊃⍵)         ⍝ Pick the first element of ⍵ (a) and assign to f
                                        ⍝ This yields the vector (a^0, a^1, ..., a^c-1)
                        ÷               ⍝ Element-wise division
                    p+1)                ⍝ The vector 1..c
                   *                    ⍝ Exponentiate
              (⍵[1]                     ⍝ Second element (because of ⎕IO←0) of ⍵ (b)
                                        ⍝ This yields the vector (b^1, b^2, ..., b^c)
            f,                          ⍝ Prepend f (a). This yields the vector
                                        ⍝ (a, b^1/a^0, b^2/a^1, ...)
          g←                            ⍝ Assign the vector to g
         ⊆                              ⍝ Partition. This takes a boolean vector as left
                                        ⍝ argument and drops falsy elements of the right argument.
     ⊃⌽⍵)                               ⍝ Pick the last element of ⍵ (c)
  (g≤                                   ⍝ Check if each element of g≤c. Yields the boolean
                                        ⍝ vector that is the left argument for ⊆

```

# Answer
> 0 votes
# APL (Dyalog), 23 bytes (SBCS)

This takes arguments **a b** on the left and **c** on the right,

```
{⊃(⍵∘≥⊆⊢)⊣/⍵2⍴⍺,÷\⍵⍴⌽⍺}

```

Try it online!

There is likely a shorter way, but I thought that `÷\` was cute.

### Explained:

`{...}` Anonomous function ⍺ is `a b`,  is `c`. Lets say `a b c = 2 6 100`

`⌽⍺` Reverse : `6 2`

`⍵⍴` Repeat  times: `6 2 6 2 6 2 6 2 ...`

`÷\` Reduce by division on prefixes: `6 (6÷2) (6÷(2÷6)) (6÷(2÷(6÷2))).. = 6 3 18 9 54 ..`

`⍺,` Prepend : `2 6 6 3 18 9 54 27 162 81 ...`

`⊣/⍵2⍴` Get every other element (plus some trailing repeats):

`⍵2⍴` Make an  row, `2` column matrix from `2 6 6 3 18 9 54 ...`

`⊣/` Get the first column

`⊆⊢` Split the array into blocks where

`⍵∘≥`  is greater than or equal to all the elements

Take the first such block

# Answer
> 0 votes
# Stax, 14 bytesCP437

```
ü╞¥ß¥║/,5å╘⌂åº

```

16 bytes when unpacked,

```
E~Y/y{;^<}{[*gfm

```

Run and debug online!

Takes input in the form of `[b, a, c]`.

Pretty sure @recursive has better solutions.

## Explanation

```
E~                              Parse  input, put `c` on input stack
  Y/                            Store `a` in register `y` and calculate `b`/`a`
    y                           Put `y` back to main stack, stack now (from top to bottom): [`a`, `b`/`a`]
     {   }{  gf                 generator
      ;^<                       Condition: if the generated number is smaller than the top of input stack (i.e. `c`)
           [*                   duplicate the second item in main stack and multiply it with the item at the top
                                   i.e. multiply last generated value by `b/a` and generate the value
              m                 Output array, one element on each line

```

# Answer
> 0 votes
# S.I.L.O.S, 73 bytes

```
readIO
k=i
readIO
j=i
readIO
r=j/k
a=k
lbla
printInt a
a*r
b=i-a+1
if b a

```

Try it online!

We read the three numbers. Calculate the common ratio by the second number/ first one. Then we run through the series until we are greater than the upper bound.

# Answer
> 0 votes
# C (gcc), 82 bytes

```
n;f(a,b,c){float r=0;for(n=0;r<=c;)(r=pow(b,n)/pow(a,n++-1))<=c&&printf("%f ",r);}

```

Try it online!

Calculates and prints `r_n = b^n/a^(n-1)` until `r_n > c`.

Must be compiled with `-lm`!

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