title: Find self-locating strings in a number

text:
# Question
Title: Find self-locating strings in a number
*Based on this Numberphile video*

A self-locating string is a number (or set of numbers) in a decimal expansion which corresponds to its location, from the start of the decimal.

For example, take the number:

```
.2734126393112

```

Here, we can identify certain items quickly, e.g:

```
.27 _3_ _4_ 1263 _9_ 3112

```

There are a few more complex cases in here though, too. For instance, the numbers `11` and `12` both appear *starting* in their respective positions:

```
.2734126393112
 123456789ABCD
           ^
           11

            ^
            12

```

So the list of self-locating strings in this case would be `[3, 4, 9, 11, 12]`, as even though some of them overlap, they both start in the correct places. If we sum these up, we get 39, or the *self-reference index* (SRI) of this terminating decimal.

## Input

A terminating decimal, either an array of digits (after the point) or a decimal type with `0.` at the start/`.`.

## Output

The SRI of the input number.

## Rules

* In the case that there are no self-referential numbers, the SRI is 0. This must be returned/printed, as opposed to exiting or returning undefined.
* The decimal expansion can be assumed to terminate, and will be no more than 128 digits in length.
* The counting of the indexes should be 1-based, e.g the first decimal is at position `1`, etc.
* Standard I/O rules + standard loopholes apply.
* This is , so shortest answer in bytes wins

## Test cases

```
0.1207641728 -> 3
.12345678910 -> 55
0.1234567890112 -> 68
.0 -> 0
0.654321 -> 0
.54321 -> 3

```

# Answer
# Jelly,  ~~9~~  8 bytes

```
ṫJw"Jẹ1S

```

A monadic Link accepting a list of the digits after the decimal point which yields an integer.

**Try it online!**

### How?

```
ṫJw"Jẹ1S - Link: list of digits, A        e.g. [3,2,1,0,5]
 J       - range of length (of A)              [1,2,3,4,5]
ṫ        - tail from index (vectorises)        [[3,2,1,0,5],[2,1,0,5],[1,0,5],[0,5],[5]]
    J    - range of length (of A)              [1,2,3,4,5]
   "     - zip with:
  w      -   first index of substring or 0     [3,1,0,0,1]
               Note: w has implicit decimalisation of its right argument,
                    so [7,6,5,4]w65 is equivalent to [7,6,5,4]w[6,5] = 2
      1  - literal one                         1
     ẹ   - indexes of                          [2,5]
       S - sum                                 7

```
> 2 votes

# Answer
# APL (Dyalog Extended), 16 bytes

```
+/⍬∘⍋(⍸⊣⊃¨⍕⍛⍷¨)⊂

```

Try it online!

Takes a string of digits.

### How it works

```
+/⍬∘⍋(⍸⊣⊃¨⍕⍛⍷¨)⊂  ⍝ Input: character vector of digits
  ⍬∘⍋             ⍝ X←Array of 1-based indices
     (    ⍕⍛ ¨)   ⍝ Stringify each of X
     (      ⍷¨)⊂  ⍝ And for each of above, build a boolean array where
                  ⍝   substring matches are marked as 1
                  ⍝ e.g. '10'⍷'10428104' is [1 0 0 0 0 1 0 0]
       ⊣⊃¨        ⍝ Extract X-th indices from each of above
      ⍸           ⍝ Convert ones to its 1-based locations
+/                ⍝ Sum

```
> 5 votes

# Answer
# 05AB1E, 9 bytes

```
āʒ.$yÅ?}O

```

Try it online!
> 4 votes

# Answer
# Python 2, ~~112~~ \\$\cdots\\$ ~~52~~ 51 bytes

Saved 9 bytes thanks to ElPedro!!!
Saved a byte thanks to Jonathan Allan!!!
Saved ~~3~~ 4 bytes thanks to Poon Levi!!!

```
f=lambda s,i=0:s>s[:i]and(s[:i]+`i`in s)*i+f(s,i+1)

```

Try it online!

Takes a number in the form `.abc...` as string input and returns its SRI.
> 3 votes

# Answer
# JavaScript (ES6),  ~~50~~  48 bytes

Takes input as a string. A recursive approach.

```
f=(s,n=1)=>s?+s.match('^'+n)+f(s.slice(1),n+1):0

```

Try it online!

`s.match('^'+n)` is either *null* or a singleton array holding \\$n\\$ as a string. By applying the unary `+`, these values are coerced to \\$0\\$ or \\$n\\$ respectively.

---

# JavaScript (ES6), 52 bytes

Takes input as a string.

```
s=>[...s].reduce(t=>t+!(i-s.indexOf(i+1,i))*++i,i=0)

```

Try it online!
> 3 votes

# Answer
# PowerShell, ~~60~~ 56 bytes

```
param($n)1..128|%{$o+=$_*($_-eq$n.indexOf("$_",$_))};+$o

```

Try it online!

Takes input `$n` as a string (else you'll get floating point inaccuracies), then constructs a range from `1` to `128`. We then loop through those numbers (the `|%{...}`) and each iteration we're accumulating into `$o` the current number times if the current number `$_` is `-eq`ual to the `.indexOf` the current number `"$_"` starting at position `$_` in the input string `$n`. In other words, if the current number matches the first index starting at that position, the current number is added to our output. After the loop, we tack on a `+` at the front to account for the zero case (i.e., no numbers in the collection). That result is left on the pipeline and output is implicit.

*-4 bytes thanks to inspiration from ElPedro.*
> 3 votes

# Answer
# , 1̶0̶2̶, 99 bytes

Thanks to @Giuseppe for 99 bytes

```
U=`[`
`[`=Map
sum(which(paste0[U[list(x<-scan()),`+`[(L=seq(x))-1,seq[nchar(L)]]],collapse=""]==L))

```

Try it online!

Few bytes can be saved if there is a second 2-byte 3-argument operator like `[`. First time messing with `[`, it is fun.
> 3 votes

# Answer
# , ~~30~~ 29 bytes

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

```

Try it online!
> 2 votes

# Answer
# Ruby, ~~46~~ 44 bytes

```
->n{r=0;n.chars.sum{n[r+=1,r]=~/^#{r}/?r:0}}

```

Try it online!

Thanks Value Ink, as usual, for -2 bytes.
> 2 votes

# Answer
# Perl 5 `-pl`, 27 bytes

Requires input to be in the format `.####...`:

```
$\+=++$a*/\G$a/ while/./g}{

```

Try it online!

## Original version below handles input with or without a leading `0`.

### Perl 5 `-pal`, 34 bytes

```
s/^0//;$\+=++$a*/\G$a/ while/./g}{

```

Try it online!
> 1 votes

# Answer
# Perl 6, ~~31~~ 30 bytes

```
{sum m:ex/\d+<!{$/-$/.from}>/}

```

Try it online!

### Explanation:

```
{                            }   # Anonymous code block returning
 sum                             # The sum of
     m:ex/                  /    # All possible matches
          \d+                    # Of numbers
             <!{$/-       }>     # That are equal
                   $/.from       # To their position in the string

```
> 1 votes

# Answer
# Python 2, ~~64~~ 60 bytes

```
lambda i:sum(x for x in range(len(i))if`x`==i[x:x+len(`x`)])

```

Try it online!

The `0` result works because an empty list in Python is equivalent to `False` which is equivalent to `0` and when you `sum(0)` you very conveniently get `0`.
> 0 votes

# Answer
# Retina 0.8.2, 29 bytes

```

¶$.`$.`$*;$'¶
Gm`^(.+);+\1
;

```

Try it online! Link includes test cases. Assumes input begins with the decimal point. Explanation:

```

¶$.`$.`$*;$'¶

```

For each offset in the string, list the offset in decimal, then again in unary, then the suffix starting at that offset, wrapping the whole thing in newlines so that the characters in the input string don't contaminate the data.

```
Gm`^(.+);+\1

```

Keep only the lines where the suffix starts with the offset.

```
;

```

Take the total of the matching unary offsets.
> 0 votes

# Answer
# Charcoal, 18 bytes

```
ＩΣＥＬθ×ι⁼Ｉι✂θι⁺ιＬＩι

```

Try it online! Link is to verbose version of code. Assumes input begins with the decimal point. Explanation:

```
    θ               Input string
   Ｌ                Length
  Ｅ                 Map over implicit range
                 ι  Current index
                Ｉ   Cast to string
               Ｌ    Length
              ι     Current index
             ⁺      Added
            ι       Current index
           θ        Input string
          ✂         Sliced
         ι          Current index
        Ｉ           Cast to string
       ⁼            Equals
      ι             Current index
     ×              Multiplied
 Σ                  Take the sum
Ｉ                   Cast to string for implicit print

```
> 0 votes

# Answer
# Python 2, 53 bytes

```
f=lambda s,i=0:s>''and(s.find(`i`)==0)*i+f(s[1:],i+1)

```

A recursive version of a previous version of Noodle9's Python 2 answer.

**Try it online!**
> 0 votes

# Answer
# PowerShell, 49 bytes

`[Double]` has 15 to 17 significant decimal digits precision, so we can consider a finite number of digits

```
param($n)1..99|%{$s+=$_*($n-match"^.{$_}$_")}
+$s

```

Try it online!

---

# PowerShell, 54 bytes

any string representation of decimal number

```
param($n)$n|% t*y|%{$s+=++$i*($n-match"^.{$i}$i")}
+$s

```

Try it online!
> 0 votes

# Answer
# Haskell, 71 bytes

```
import Data.List
f l=sum[i|(i,x)<-zip[0..]$tails l,show i`isPrefixOf`x]

```

Try it online!
> 0 votes

# Answer
# Java 8, 86 bytes

```
s->{int r=0,i=0;for(;i<s.length();)r+=s.substring(i++).startsWith(i+"")?i:0;return r;}

```

To the point approach. Will see if I can find something shorter later on. Also, this is probably the first time I've used `startsWith` in Java (either in or outside codegolfing). ;)

Input as a String.

Try it online.

**Explanation:**

```
s->{                       // Method with String parameter and integer return-type
  int r=0,                 //  Result-sum, starting at 0
  i=0;for(;i<s.length();)  //  Loop `i` in the range [0,input-length):
    r+=                    //   Increase the result-sum by:
       s.substring(i++)    //    Take the substring of the input, starting at index `i`
                           //    And increase `i` by 1 afterwards with `i++`
        .startsWith(i+"")? //    If this substring starts with `i` (converted to String):
          i                //     Increase the result-sum by `i`
         :                 //    Else:
          0;               //     Leave the result-sum the same by increasing with 0
  return r;}               //  And return the sum as result

```
> 0 votes

# Answer
# C# (Visual C# Interactive Compiler), 74 bytes

```
a=>Enumerable.Range(1,a.Length).Sum(x=>a.Remove(0,x).StartsWith(x+"")?x:0)

```

Try it online!
> 0 votes

# Answer
# T-SQL, 103 bytes

```
SELECT number+1FROM spt_values
WHERE type='P'and-~number=substring(concat(@,''),number+3,len(number+1))

```

**Try it online**
> 0 votes

# Answer
# Zsh, 43 bytes

```
repeat $#1 ((r+=0${(M)1[++i,-1]#$i}))
<<<$r

```

Try it online!

Takes input as a string. Repeatedly `(M)`atches the part of the string string at position `++i` to `-1` that `#`starts with `$i`, and adds it to `$r`. The `0` ensures that a valid number is added in the case of no match, so `$r` is set to a value before being printed.
> 0 votes

# Answer
# Japt `-x`, 12 bytes

```
ÊÇ¥UtZZsl¹*Z

```

Try it online!
> 0 votes

---
Tags: code-golf, number
---


title: Visualize sorting

text:
# Question
Title: Visualize sorting
Say I have a list such as `[3, 0, 4, 2, 1]`, and I use selection sort to sort it, I could visualize it like this:

```
3,0,4,2,1
|-|
0,3,4,2,1
  |-----|
0,1,4,2,3
    |-|
0,1,2,4,3
      |-|
0,1,2,3,4

```

This challenge is about visualizing sorting like this.

## Input

Your input will be a list of positive integers, in any format you like.

## Task

Your submission should sort the input list by only swapping two elements at a time, and at each swap, the submission should display the list, and a character under each of the elements being swapped. If a number that was swapped has more than one digit, the character can be anywhere underneath it. At the end, the submission should display the sorted list.

## Other rules

* The sorting must use fewer swaps than n4, where n is the length of the list.
* The sorting doesn't have to be deterministic.
* The characters under the swapped can be any char except space.

# Answer
> 10 votes
# Perl, 62 bytes

Includes +3 for `-p`

Give input as a single line of numbers on STDIN:

```
perl -M5.010 visisort.pl <<< "3 0 4 2 1"

```

Repeatedly swaps the first inversion. Swap complexity is `O(n^2)`, time complexity is `O(n^3)`. Uses the numbers being swapped as mark:

```
3 0 4 2 1
3 0
0 3 4 2 1
    4 2
0 3 2 4 1
  3 2
0 2 3 4 1
      4 1
0 2 3 1 4
    3 1
0 2 1 3 4
  2 1
0 1 2 3 4

```

`visisort.pl`:

```
#!/usr/bin/perl -p
$&>$'&&say$_.$"x"@-".!s/(\S+) \G(\S+)/$2 $1/.$&while/\S+ /g

```

The program also supports negative values and floating point numbers

If you insist on a connecting character the code becomes 66 bytes:

```
#!/usr/bin/perl -p
$&>$'&&say$_.$"x"@-".!s/(\S+) \G(\S+)/$2 $1/.$1.-$2while/\S+ /g

```

But now it doesn't support negative numbers and 0 anymore (but the program only has to support positive integers anyways. The `0` in the example is a mistake)

# Answer
> 9 votes
# PHP, 248 Bytes

Bubblesort boring wins

```
<?for($c=count($a=$_GET[a]);$c--;){for($s=$i=0;$i<$c;){$l=strlen($j=join(",",$a));if($a[$i]>$a[$i+1]){$t=$a[$i];$a[$i]=$a[$i+1];$a[$i+1]=$t;$m=" ";$m[$s]=I;$m[$s+strlen($a[$i].$a[$i+1])]=X;echo"$j\n$m\n";}$s+=strlen($a[$i++])+1;}}echo join(",",$a);

```

PHP, 266 Bytes a way with array\_slice and min

modified output `I X` instead of `*~~*`

```
<?for($c=count($a=$_GET[a]);$i<$c;){$j=join(",",$s=($d=array_slice)($a,$i));$x=array_search($m=min($s),$s);echo($o=join(",",$a));$a[$x+$i]=$a[$i];$a[$i]=$m;if($i++!=$c-1){$t=" ";$t[$z=($f=strlen)($o)-($l=$f($j))]=I;$t[$l+$z-$f(join(",",$d($s,$x)))]=X;echo"\n$t\n";}}

```

282 Bytes

```
<?for($c=count($a=$_GET[a]);$i<$c;){$j=join(",",$s=($d=array_slice)($a,$i));$x=array_search($m=min($s),$s);echo($o=join(",",$a));$a[$x+$i]=$a[$i];$a[$i]=$m;if($i++!=$c-1)echo"\n".str_repeat(" ",($f=strlen)($o)-($l=$f($j))).($x?str_pad("*",$l-$f(join(",",$d($s,$x))),"~"):"")."*\n";}

```

## How it works

Looks for the minimum in an array and take this on first position Look for the minimum without first position .... and so on If a value is double the first value will be swap

## Output Example

```
31,7,0,5,5,5,753,5,99,4,333,5,2,1001,35,1,67
*~~~~*
0,7,31,5,5,5,753,5,99,4,333,5,2,1001,35,1,67
  *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*
0,1,31,5,5,5,753,5,99,4,333,5,2,1001,35,7,67
    *~~~~~~~~~~~~~~~~~~~~~~~~~*
0,1,2,5,5,5,753,5,99,4,333,5,31,1001,35,7,67
      *~~~~~~~~~~~~~~*
0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67
        *
0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67
          *
0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67
            *~~~*
0,1,2,4,5,5,5,753,99,5,333,5,31,1001,35,7,67
              *~~~~~~*
0,1,2,4,5,5,5,5,99,753,333,5,31,1001,35,7,67
                *~~~~~~~~~~*
0,1,2,4,5,5,5,5,5,753,333,99,31,1001,35,7,67
                  *~~~~~~~~~~~~~~~~~~~~~*
0,1,2,4,5,5,5,5,5,7,333,99,31,1001,35,753,67
                    *~~~~~~*
0,1,2,4,5,5,5,5,5,7,31,99,333,1001,35,753,67
                       *~~~~~~~~~~~*
0,1,2,4,5,5,5,5,5,7,31,35,333,1001,99,753,67
                          *~~~~~~~~~~~~~~~*
0,1,2,4,5,5,5,5,5,7,31,35,67,1001,99,753,333
                             *~~~~*
0,1,2,4,5,5,5,5,5,7,31,35,67,99,1001,753,333
                                *~~~~~~~~*
0,1,2,4,5,5,5,5,5,7,31,35,67,99,333,753,1001
                                    *
0,1,2,4,5,5,5,5,5,7,31,35,67,99,333,753,1001

```

# Answer
> 9 votes
## JavaScript (ES6), 158 bytes

```
a=>{for(;;){console.log(``+a);i=a.findIndex((e,i)=>e<a[i-1]);if(i<0)break;console.log(` `.repeat(`${a.slice(0,i)}`.length-1)+`|-|`);t=a[i];a[i]=a[--i];a[i]=t}}

```

Bubble sort. Sample output:

```
3,0,4,2,1
|-|
0,3,4,2,1
    |-|
0,3,2,4,1
  |-|
0,2,3,4,1
      |-|
0,2,3,1,4
    |-|
0,2,1,3,4
  |-|
0,1,2,3,4

```

# Answer
> 3 votes
## Haskell, ~~165~~ ~~164~~ 162 bytes

```
s%c=drop 2$show s>>c
p#x|(h,t:s)<-span(/=minimum x)x=id=<<[show$p++x,"\n ",[' '|p>[]],p%" ","|",h%"-",['|'|h>[]],"\n",(p++[t])#(drop 1h++take 1h++s)]|1<2=""
([]#)

```

This visualizes selection sort. Usage example:

```
*Main> putStr $ ([]#) [31,7,0,5,5,5,753,5,99,4,333,5,2,1001,35,1,67]
[31,7,0,5,5,5,753,5,99,4,333,5,2,1001,35,1,67]
 |----|
[0,7,31,5,5,5,753,5,99,4,333,5,2,1001,35,1,67]
   |-------------------------------------|
[0,1,31,5,5,5,753,5,99,4,333,5,2,1001,35,7,67]
     |-------------------------|
[0,1,2,5,5,5,753,5,99,4,333,5,31,1001,35,7,67]
       |--------------|
[0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67]
         |
[0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67]
           |
[0,1,2,4,5,5,753,5,99,5,333,5,31,1001,35,7,67]
             |---|
[0,1,2,4,5,5,5,753,99,5,333,5,31,1001,35,7,67]
               |------|
[0,1,2,4,5,5,5,5,99,753,333,5,31,1001,35,7,67]
                 |----------|
[0,1,2,4,5,5,5,5,5,753,333,99,31,1001,35,7,67]
                   |---------------------|
[0,1,2,4,5,5,5,5,5,7,333,99,31,1001,35,753,67]
                     |------|
[0,1,2,4,5,5,5,5,5,7,31,99,333,1001,35,753,67]
                        |-----------|
[0,1,2,4,5,5,5,5,5,7,31,35,333,1001,99,753,67]
                           |---------------|
[0,1,2,4,5,5,5,5,5,7,31,35,67,1001,99,753,333]
                              |----|
[0,1,2,4,5,5,5,5,5,7,31,35,67,99,1001,753,333]
                                 |--------|
[0,1,2,4,5,5,5,5,5,7,31,35,67,99,333,753,1001]
                                     |
[0,1,2,4,5,5,5,5,5,7,31,35,67,99,333,753,1001]
                                         |

```

How it works:

`s % c` is a helper function that makes `length (show s) - 2` copies of character `c`. It's used for spacing before both `|`, one time with `c == ' '` and one time with `c == '-'`.

The main function `#` takes a list `p` which is the sorted part of the list and `x` which is the yet to sort part. The pattern match `(h,t:s)<-span(/=minimum x)x` splits the list `x` at its minimum element and binds `h` to the part before the minimum, `t` to the minimum itself and `s` to the part after the minimum. The rest is formatting two lines: 1) the list at its current state (`p++x`) and 2) the `|----|` part followed by a recursive call of `#` with `t` appended to `p` and the head of `h` inserted between the tail of `h` and `s`.

PS: works also with negativ and/or floating point numbers:

```
*Main> putStr $ ([]#) [-3,-1,4e33,-7.3]
[-3.0,-1.0,4.0e33,-7.3]
 |----------------|
[-7.3,-1.0,4.0e33,-3.0]
      |-----------|
[-7.3,-3.0,4.0e33,-1.0]
           |------|
[-7.3,-3.0,-1.0,4.0e33]
                |

```

Edit: @BlackCap saved 2 bytes. Thanks!

# Answer
> 1 votes
# Python 2, 267 bytes

It works with decimals and negative numbers as well.

```
p=1
while p!=len(a):
 q=p-1;k=a[p:];m=min(k);n=k.index(m)+p;b=map(str,a)
 if a[q]>m:print','.join(b)+'\n'+''.join(' '*len(i)for i in b[:q])+' '*q+'*'+'-'*(len(b[n])+n-q-2)+''.join('-'*len(i)for i in b[q:n])+'*';a[q],a[n]=[a[n],a[q]]
 p+=1
print','.join(map(str,a))

```

Example:

```
7,2,64,-106,52.7,-542.25,54,209,0,-1,200.005,200,3,6,1,0,335,-500,3.1,-0.002
*----------------------*
-542.25,2,64,-106,52.7,7,54,209,0,-1,200.005,200,3,6,1,0,335,-500,3.1,-0.002
        *-------------------------------------------------------*
-542.25,-500,64,-106,52.7,7,54,209,0,-1,200.005,200,3,6,1,0,335,2,3.1,-0.002
             *-----*
-542.25,-500,-106,64,52.7,7,54,209,0,-1,200.005,200,3,6,1,0,335,2,3.1,-0.002
                  *-------------------*
-542.25,-500,-106,-1,52.7,7,54,209,0,64,200.005,200,3,6,1,0,335,2,3.1,-0.002
                     *-----------------------------------------------------*
-542.25,-500,-106,-1,-0.002,7,54,209,0,64,200.005,200,3,6,1,0,335,2,3.1,52.7
                            *--------*
-542.25,-500,-106,-1,-0.002,0,54,209,7,64,200.005,200,3,6,1,0,335,2,3.1,52.7
                              *-----------------------------*
-542.25,-500,-106,-1,-0.002,0,0,209,7,64,200.005,200,3,6,1,54,335,2,3.1,52.7
                                *------------------------*
-542.25,-500,-106,-1,-0.002,0,0,1,7,64,200.005,200,3,6,209,54,335,2,3.1,52.7
                                  *-------------------------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,64,200.005,200,3,6,209,54,335,7,3.1,52.7
                                    *--------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,200.005,200,64,6,209,54,335,7,3.1,52.7
                                      *-------------------------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,200,64,6,209,54,335,7,200.005,52.7
                                          *------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,64,200,209,54,335,7,200.005,52.7
                                            *-----------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,200,209,54,335,64,200.005,52.7
                                              *----------------------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,52.7,209,54,335,64,200.005,200
                                                   *----*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,52.7,54,209,335,64,200.005,200
                                                      *--------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,52.7,54,64,335,209,200.005,200
                                                         *-----------------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,52.7,54,64,200,209,200.005,335
                                                             *---------*
-542.25,-500,-106,-1,-0.002,0,0,1,2,3,3.1,6,7,52.7,54,64,200,200.005,209,335

```

# Answer
> 1 votes
# JavaScript (ES6), 147 ~~155~~

Using n\*n compares, but (I believe) the minimum number of swaps. And the swap positions are more variable compared to the boring bubble sort.

```
l=>l.reduce((z,v,i)=>l.map((n,j)=>s+=`${j>i?n<l[i]?l[p=j,t=s,i]=n:0:u=s,n},`.length,s=p=0)|p?z+`
${l[p]=v,' '.repeat(u)}^${Array(t-u)}^
`+l:z,''+l)

```

*Less golfed* and hopefully more understandable

```
l=>
  l.reduce( (z,v,i) => // update z for each list element v at position i
    ( // begin outer loop body
      // loop to find the least value that is to be placed at pos i
      l.map( (n,j) => // for each list element n at position j
        ( // begin inner loop body
          j > i ? // check if at position after i
            n < l[i] && // check if lower value
            (
              p = j, // remember position in p
              l[i] = n, // store value in l[i] (could change later)
              t = s // in t, string length of list elements up element preciding j
            )
          : // else, position up to i
            u = s, // in u, string length of list elements up element preciding i
          s += `${n},`.length, // string length of list elements up to this point (value length + comma)
        ) // end inner loop body
        , s = p = 0 // init s and p at start of inner loop
      ),
      p ? (// if found a lower value, complete the swap and update output
          l[p] = v, // complete swap, l[i] was assigned before
          z + '\n' + ' '.repeat(u) + // spaces to align
               '^' + // left marker
               Array(t-u) + // swap highlight, using sequence of commas
               '^\n' + // right marker, newline
               l + // list values after the swap, newline
      )
      : z // else output is unchanged
    ) // end outer loop body
    , ''+l // init string output at start of outer loop
  ) // output is the result of reduce

```

**Test**

```
f=
l=>l.reduce((z,v,i)=>l.map((n,j)=>s+=`${j>i?n<l[i]?l[p=j,t=s,i]=n:0:u=s,n},`.length,s=p=0)|p?z+`
${l[p]=v,' '.repeat(u)}^${Array(t-u)}^
`+l:z,''+l)

function sort()
{
  var list=I.value.match(/-?[\d.]+/g).map(x=>+x)
  O.textContent = f(list)
}

sort()
```

```
#I { width:80% }
```

```
<input id=I value='3, 0, 4, 2, 1'>
<button onclick='sort()'>Sort</button>
<pre id=O></pre>
```

# Answer
> 1 votes
# Jelly, 36 bytes

```
I;0CMḢ;L‘ṬCœṗ¹UF©µÐĿ,n+32Ọ$¥¥2\;/®ṭG

```

Try it online!

## Explanation

```
I;0CMḢ;L‘ṬCœṗ¹UF©µÐĿ,n+32Ọ$¥¥2\;/®ṭG
                 µÐĿ                 Repeat until we see a previously seen value:
I;0                                    Take differences of adjacent inputs, and 0
   CM                                  Find the indices (M) of the smallest (C)
           œṗ                          Split {the input} into pieces
        ‘Ṭ                               that end
      ;L  C                              everywhere except
     Ḣ                                 the first of the chosen deltas
             ¹                         Resolve parser ambiguity
              U                        Reverse each piece
               F                       Concatenate the pieces back into a list
                ©                      Store the value in a register
                                     Then, on the accumulated list of results:
                             2\        Look at each consecutive pair of results
                    ,       ¥  ;/      and return the first element, followed by
                      +32Ọ$            the character with code 32 plus
                     n     ¥           1 (if unequal), 0 (if equal)
                                 ®ṭ  Append the value of the register
                                   G Output in grid form

```

The example shown in the TIO link is a particularly hard one for this program; the `;0` near the start is necessary to ensure that the loop ends just at the point where the input becomes sorted. This normally isn't necessary (because it will end after one more iteration), but if the last swap is of the first two elements (as seen here), the one-more-iteration won't happen and makes it impossible to finish the list consistently. As such, we need to ensure we don't swap anything on the last loop iteration.

# Answer
> 0 votes
# Java 7, ~~256 241~~ 282 Bytes

*Thanks to @Geobits and @Axelh for saving 15 bytes*

```
 void f(int[]a){int m,i,j,l=a.length;for(i=0;i<l;j=a[i],a[i]=a[m],a[m]=j,i++){for(int k:a)System.out.print(k+" ");System.out.println();for(j=i+1,m=i;j<l;m=a[j]<a[m]?j:m,j++);for(j=0;j<=m&i!=l-1;j++)System.out.print(j==i|j==m?a[j]+" ":"  ");System.out.println();}}

```

# Ungolfed

```
 void f(int[]a){
    int m,i,j,l=a.length;
for(i=0;i<l;j=a[i],a[i]=a[m],a[m]=j,i++){
    for(int k:a)
        System.out.print(k+" ");
    System.out.println();
     for(j=i+1,m=i;j<l;m=a[j]<a[m]?j:m,j++);
      for(j=0;j<=m&i!=l-1;j++)
      System.out.print(j==i|j==m?a[j]+" ":"  ");
      System.out.println();

}
}

```

### output

```
3 0 1 4 2
3 0
0 3 1 4 2
  3 1
0 1 3 4 2
    3   2
0 1 2 4 3
      4 3
0 1 2 3 4

```

# Answer
> 0 votes
# , ~~66~~ 65 bytes

```
[:(>@,@(2({.;'^ '{~=/)\])@,{:)@":]C.~a:,[:<"1\@;({.,.}.)&.>@C.@/:

```

Try it online!

---
Tags: code-golf, sorting
---


# Question
Title: Cubify This! A lesson in grayscale... er... color... er... whatever
Being a big fan of the Rubik's cube and of cool art, I've been working on combining the two together to do some really cool stuff. Basically solving miniature Rubik's cubes to form rudimentary pixels in the formation of Rubik's cube art. Examples of such art can be seen via this link: http://google.com/search?q=rubik%27s+cube+art

Now, the purpose of this Code Golf is to create code that accepts an image as input, and then converts it in the following manner:

The image is initially reduced to web-safe grayscale colors. The reason behind this is because we need to isolate the web-safe grayscale palette (i.e. 000000, 333333, 666666, 999999, CCCCCC, and FFFFFF). An algorithm on the colorimetric method of converting to grayscale is available at: http://en.wikipedia.org/wiki/Grayscale#Colorimetric\_.28luminance-preserving.29\_conversion\_to\_grayscale, should you wish to use that as inspiration.

One would then render out the grayscale to the appropriate colors. To break it down quickly: 000000 will refer to Rubik's blue, 333333 will refer to Rubik's red, 666666 will refer to Rubik's green, 999999 will refer to Rubik's orange, CCCCCC will refer to Rubik's yellow, and FFFFFF will refer to Rubik's white.

I would rather that your resulting code can render from the photo's palette straight to Rubik's colors. The two-stage method from converting to web-safe grayscale and then to the corresponding Rubik's palette is just to give you an idea on the logic behind the process, but if it is easier for you to do this, by all means do so.

The actual RGB values for the Rubik's palette must correspond to the following:

* Red: #C41E3A
* Green: #009E60
* Blue: #0051BA
* Orange: #FF5800
* Yellow: #FFD500
* White: #FFFFFF

To give you an example, I have cropped Abraham Lincoln's head from the following picture: , and rendered the algorithm to produce the following:

The grid is there so that you can see how each individual miniature Rubik's cube would have to be configured to make up the image. The true size of the resulting image is 45 pixels by 45 pixels, meaning (45/3) * (45/3) = 15 * 15 = 225 miniature Rubik's cubes would be used to make this image. I am not expecting you to present the resulting image with a grid as I have.

So this is what's required:

1. The image to be processed by this algorithm must be x pixels wide by y pixels high, such that x and y are multiples of 3. This is to aid with the ease of rendering as part of a Rubik's cube mosaic. If your image is quite large, reducing it to something around the 45 x 45 to 75 x 75 or thereabouts in dimensions prior to processing is advised. Bear in mind, this resizing component is OPTIONAL.
2. The image needs to be converted to the sextacolored Rubik's cube palette to create the mosaic.
3. The resulting image needs to be a valid graphic file after processing. To prove your code works, run it against an image of one of the presidents of the United States of America, or a well known Hollywood celebrity. I have already used Abraham Lincoln in my example, so this president can no longer be used. Ensure that you provide the language you have used, the byte count as well as the president/celebrity used to test your code, including before and after shots...
4. Each entry must have a unique president/celebrity as their test case. I will not accept duplicates. This will ensure that duplicate results are not used to test different code entries. It's all very well to say that your code works, it's another thing to prove it.

5. Shortest code wins.

I'm changing this to a popularity contest... I'd rather see who can do this without having to compete on byte count... So I'll award this along with a bounty after the 28th of February, 2014.

# Answer
# Imagemagick (108)

Version: ImageMagick 6.8.7-7 Q16 x86\_64 2013-11-27

The following call:

```
$ convert -resize 75x75 -fx "q=p.intensity;q<1/6?#0051BA:q<2/6?#C41E3A:q<3/6?#009e60:q<4/6?#ff5800:q<5/6?#FFD500:#FFF" input output

```

where `input` and `output` have to be modified for the input and output filename.

I only counted the chars between `-resize` and `#FFF"`, if you think this is invalid feel free to comment.

I used Lenna as image (she appeared in a Playboy, and anyone doing that should count as a Hollywood celebrity, right?)

Input:

Output:

```
$ convert -resize 75x75 -fx "q=p.intensity;q<1/6?#0051BA:q<2/6?#C41E3A:q<3/6?#009e60:q<4/6?#ff5800:q<5/6?#FFD500:#FFF" Lenna.png LennaRubik.png

```

Output enlarged:

Notes: according to the imagemagick docs you cannot have more than one conditional operator in a statement, but the call still seems to work fine, so probably this was fixed and the docs were just not updated.

Running identify on the result image (to show the colors are indeed fine):

```
$ identify -verbose LennaRubik.png
  (...)
  Colors: 6
  Histogram:
       338: (  0, 81,186) #0051BA srgb(0,81,186)
      1652: (  0,158, 96) #009E60 srgb(0,158,96)
      1187: (196, 30, 58) #C41E3A srgb(196,30,58)
      1674: (255, 88,  0) #FF5800 srgb(255,88,0)
       706: (255,213,  0) #FFD500 srgb(255,213,0)
        68: (255,255,255) #FFFFFF white
  (...)

```

If you think Lenna doesn't count as a proper celebrity, here is Bruce Willis:
> 17 votes

# Answer
# Mathematica

We'll work with a square region from a U.S. stamp featuring Greta Garbo. It will be referred to as `j`.

```
f[i_,rs_,m_:True]:=
Module[{(*rs=rastersize-4*)r={0.77,0.12,0.23},gr={0,0.62,0.38},b={0,0.32,0.73},o={1,0.35,0},y={1,0.84,0},w={1,1,1},
c1={r,gr,b,o,y,w},grayGreta,garboColors},
grayGreta=(*Reverse@*)ImageData[ColorQuantize[Rasterize[i,(*ImageResolution \[Rule]15*)RasterSize->rs+1,ImageSize->rs],6]];
garboColors=Union@Flatten[grayGreta,1];
ArrayPlot[grayGreta/.Thread[garboColors-> RGBColor@@@c1],
Mesh->If[m==True,{rs-1,rs-1},None],MeshStyle->Black]]

```

The function f takes 3 parameters:

* `i` which refers to the image
* `rs`, the raster size
* `m`, a boolean variable that states whether Mesh lines should be used. (The default setting is True).

---

Using raster sizes of 15, 30, 45, and 75:

```
GraphicsGrid[{{f[j, 15], f[j, 30]}, {f[j, 45], f[j, 75]}}, ImageSize -> 800]

```

I can't imagine anyone making a Rubrik's cube with so many pieces! Interesting exercise nonetheless.

---

## Playing around with colors

This is from an earlier entry. The code is slightly different. `Graphics` is used instead of `ArrayPlot`. Also, we use the full stamp even though it is not square.

There are 6!=720 permutations of the Rubrik cube colors.

The following displays the center image of the upper row (set 6 images below). When the grayscale values are arranged from darkest to lightest, the colors are {r,gr,b,o,y,w}. Other variations nonetheless work.

`i` is the original image in grayscale.

```
Graphics[Raster[(g=Reverse@ImageData[ColorQuantize[Rasterize[i,RasterSize->75],6]])
/.Thread[Union@Flatten[g,1]-> {{7,1,2},{0,6,4},{0,3,7},{10,4,0},{10,8,0},{10,10,10}}/10]]]

```

---

`i` is the original grayscale image of the full Greta Garbo stamp.

`Rasterize[garbo,RasterSize->75` rasterizes the image into a 75 by 75 array.

`ColorQuantize[<>, 6]` reduces the grayscale values to a set of 6.

`ImageData` retrieves the data array from the image; it comes upside-down.

`Reverse` flips the data array, hence the picture, right-side up.

`garboColors` are the 6 grayscale values in the quantized image.

`Graphics[Raster` displays the final image.

`rubrikColors` are RGB values of the 6 Rubrik cube colors.

Various color permutations of Red, Green, Blue, Orange, Yellow, and White are given.

```
r={0.77,0.12,0.23};gr={0,0.62,0.38};b={0,0.32,0.73};o={1,0.35,0};y={1,0.84,0};w={1,1,1};
c1={r,gr,b,o,y,w};
c2={r,b,gr,o,y,w};
c3={b,r,gr,o,y,w};
c4={gr,b,r,o,y,w};
c5={b,r,gr,y,o,w};

```

And the code:

```
grayGreta=Reverse@ImageData[ColorQuantize[Rasterize[i,RasterSize->75],6]];
garboColors=Union@Flatten[grayGreta,1];
Grid[{{i,
Graphics[Raster[grayGreta/.Thread[garboColors-> c1]]],
Graphics[Raster[grayGreta/.Thread[garboColors-> c2]]]},
{Graphics[Raster[grayGreta/.Thread[garboColors-> c3]]],
Graphics[Raster[grayGreta/.Thread[garboColors-> c4]]],
Graphics[Raster[grayGreta/.Thread[garboColors-> c5]]]}}]

```

---

## Garbos Galore

Here are 72 (of the 720) images of Greta Garbo that use the 6 Rubrik cube colors. Some images work better than others, don't you think?

```
GraphicsGrid@Partition[(Graphics[Raster[grayGreta /. Thread[garboColors -> #]]] &
/@ Take[Permutations[{r, gr, b, o, y, w}, {6}], 72]), 12]

```
> 15 votes

# Answer
# Smalltalk (Smalltalk/X), 289 139\*

input: i; output: r

```
r:=i magnifiedTo:75@75.
r colorMapProcessing:[:c||b|b:=c brightness.Color rgbValue:(#(16r0051BA 16rC41E3A 16r009e60 16rff5800 16rFFD500 16rFFFFFF)at:(b*6)ceiling)]

```

input:

output:

enlarged:

(for all youngsters: this is NOT Madonna ;-)

\[\*\] I have not counted the magnification to 75x75 (the first line) - could have used an already resized as input. Hope that is ok with you.
> 6 votes

# Answer
## Postscript, and TRUE Rubik colors! ;-)

Well, this solution is a bit of off-topic here, as it's restricted to somewhat highly specialized sphere. But after much frustration with e.g. "weird numbers question" (being unable to produce something practically working) I decided to publish something and so pulled this out of my pile of half-finished scribbles and made it presentable.

The solution exploits the fact, that 1st revision of this question defines required colors by link to a site, which clearly states, that Pantone(R) colors are to be used, and RGB colors are approximations only. Then I thought, why would I do approximations, when I can do genuine color? -:)

```
10 dict begin
/Size 75 def
/Names  [(PMS 012C) (PMS 021C) (PMS 347C)   (PMS 200C)    (PMS 293C)   ] def
/Colors [[0 .16 1 0][0 .65 1 0][1 0 .39 .38][0 .9 .72 .28][1 .56 0 .27]] def
<</PageSize [Size dup]>> setpagedevice
Size dup scale
true setoverprint
(%stdin) (r) file 100 string readline pop
(r) file <</CloseSource true>>/DCTDecode filter
0 1000000 string
dup <</CloseTarget true>>/NullEncode filter
{
    3 index 3 string readstring
    {
        4 -1 roll 1 add 4 1 roll
        {} forall
        0.11 mul exch 0.59 mul add exch 0.3 mul add cvi
        1 index exch write
    } {pop exit} ifelse
} loop
closefile
0 3 -1 roll getinterval
exch closefile
/data exch def
/n data length sqrt cvi def
1 1 Names length {
    /N exch def
    {
        dup N Names length 1 add div gt
            {N 1 add Names length 1 add div gt
                {1} {0} ifelse}
            {pop 1}
        ifelse
    } settransfer
    [/Separation Names N 1 sub get /DeviceCMYK {
        Colors N 1 sub get
        { 1 index mul exch } forall pop
    }] setcolorspace
    <<
        /ImageType        1
        /Width            n
        /Height           n
        /ImageMatrix      [n 0 0 n neg 0 n]
        /BitsPerComponent 8
        /Decode           [0 1]
        /DataSource       data
    >> image
} for
showpage
end

```

This code is to be saved as e.g. `rubik.ps` and then fed to Ghostscript with usual incantation:

```
gs -q -sDEVICE=psdcmyk -o out.psd rubik.ps

```

It then waits you on the next line, for input of JPG file name e.g.

```
kelly.jpg

```

and, if all goes well, saves the output to `out.psd` file.

Input must be square RGB JPEG (any size), output is PSD with spot color channels. You'll need Photoshop to view the file. Changing GS device from `psdcmyk` to anything else will produce nothing usable. JPEG as input - because postscript interpreter can decode data stream from it directly. Square shape - because the program relies on `sqrt` of string length to find width (and height) of the image.

First lines define output image size (can be changed from default 75) and the color palette (colors and their number can be changed too). Anything else is not hard-coded, I think.

What's going on? Stream of RGB triplets is converted on the fly to the string of grayscale values (with simple formula), usual 8-bit contone image dictionary is built and used to paint 5 identical images on top of each other in 5 `Separation` color spaces. The trick is to apply transfer functions before each invocation of `image` operator. E.g. for yellow paint this function returns 0 for input values in 0.167 .. 0.333 range only, and 1 otherwise.

Input:

Screenshot of output 75x75 open in Photoshop, enlarged 800%:

And Photoshop channels palette:
> 4 votes

# Answer
# Brainfuck

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

```

This requires a BF interpreter/compiler that has -1 as EOF and that has higher than 8 bit cells IF one of the red pixels are 255. Or else it will stop premature since it won't be able to differ between EOF and value 0xFF. With jitbf you have whatever the machine has as integer size and can do this to force -1 as EOF:

```
jitbf --eof -1 rubiks.bf < angelina.pnm > angelina-rubix.pnm

```

The image file format rendered is the full RGB PNM file (P6), raw as option in Gimp.

It uses the green channel only (which is one of many ways to convert a color image to greyscale). It reduces the value by 43 without reduceing the value below zero to find out which rubiks color to use and have a switch that prints out the correct RBG color that corresponds.

Image of Angelina Jolie from Hackers (1995) scaled down to 75x75 and processed with the application:

Same, only I used the original size:

And since I'm psychic here's a president as well:
> 4 votes

# Answer
# C#

```
using System;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        unchecked
        {
            var t = new[] { 0xFFC41E3A, 0xFF009E60, 0xFF0051BA, 0xFFFF5800, 0xFFFFD500, 0xFFFFFFFF }.Select(v => Color.FromArgb((int)v)).ToArray();
            var o = new Bitmap(Bitmap.FromFile(args[1]));
            var m = double.Parse(args[0]);
            var r = Math.Min(m / o.Width, m / o.Height);
            var w = (int)(o.Width * r);
            var h = (int)(o.Height * r);

            o = new Bitmap(o, w - (w % 3), h - (h % 3));
            for (int y = 0; y < o.Height; y++)
                for (int x = 0; x < o.Width; x++)
                    o.SetPixel(x, y, N(o.GetPixel(x, y), t));
            o.Save(args[2], ImageFormat.Png);
        }
    }

    static Color N(Color c, Color[] t)
    {
        return t.OrderBy(v => Math.Abs(W(v) - W(c))).First();
    }

    static double W(Color c)
    {
        return .11 * c.B + .59 * c.G + .30 * c.R;
    }
}

```

You need to run it with 3 parameters:

`foo.exe 75 d:\test.jpg d:\out.png`

Where `75` is max. width/height, `d:\test.jpg` is input file and `d:\out.png` is the output file.

Output for various images in this contest:

My own celebrity:

Output:

However, other (larger than 75x75) sizes do result in better images:

And, if we stick with presidents:

Since this is no (longer?) codegolf I didn't bother to "minimize" the code too much. Also, since the instructions did not specifically mention the image had to be the same width as height (square) I didn't bother with cropping; I *do*, however, make sure the image is a multiple of 3 pixels wide/high. If you want square images, use square inputs Finally; the algorithm is far from optimal.

A few more (since people upvote hot chicks / internet heroes more )
> 3 votes

# Answer
# Piet

It is presented here with a codel size of 20 for readability's sake. To counter that same aspiration, it has been half-heartedly if not golfed then at least been subject to compacting efforts.

Tested with npiet like so:

```
npiet -q rc.png < infile.ppm > outfile.ppm

```

Assumes the files are of the "plain" RGB variety (P3), i.e. with the image data as numbers in plaintext and not binary. It ignores the maximum colour value and just assumes that it is 255. In the output, every whitespace is a newline.

Looping over each pixel, the following happens:

1. The colours we are to choose from are pushed to stack, lightest first, so that the darkest colours end up on top.
2. The RGB triplet is read in and converted to greyscale. Since floating point mathematics is not built-in nor trivial to implement, integer maths is used: `grey = (red * 299 + green * 587 + blue * 114) / 1000`.
3. The greyscale value is divided by 43, to obtain a number 0..5 (colour index = ci).
4. This number is increased by 1, multiplied by 3 and duplicated on stack. The top value is then decreased by 3, giving us two values on top of stack: `[(ci - 1) * 3] [ci * 3]`.
5. These new values are used with the `roll` instruction, which will - with the parameters given above - bring the desired RGB triplet to the top of the stack. (You can think of it as taking a deck of cards and cutting it so that you hold `ci * 3` cards in your hand, and then taking the top card of that little stack you're holding and putting it down on the pile still on the table, then placing what you hold top of that; repeat this `(ci - 1) * 3` times.)
6. Triplet is output in the usual way.
7. The unused triplets are popped from stack.
8. If at the end, we exit, otherwise we go back to step 1.

Input:

Output 75x75 (input was scaled before passing it to the program itself):

Output very large indeed:
> 2 votes

# Answer
# Python

Format: `python rubik.py <input> <max_cubes> <output>`.

Coverts pixel to grayscale using suggested algorithm.

```
import Image, sys

def rubik(x, max_cubes = 25):

    img = x
    max_cubes *= 3

    if x.size[0] > max_cubes or x.size[1] > max_cubes:

        print "Resizing image...",

        if x.size[0] > x.size[1]:
            img = x.resize((max_cubes, int(max_cubes * float(x.size[1]) / x.size[0])), Image.ANTIALIAS)
        else:
            img = x.resize((int((max_cubes * float(x.size[0]) / x.size[1])), max_cubes), Image.ANTIALIAS)

    if x.size[0] % 3 or x.size[1] % 3:
        print "Sizes aren't multiples of 3"
        return

    print "Image resized to %i x %i pixels" % img.size

    out = Image.new('RGB', img.size)

    print "Converting image...",

    for x in xrange(out.size[0]):
        for y in xrange(out.size[1]):
            r, g, b = img.getpixel((x, y))
            if r == g == b == 255:
                out.putpixel((x,y), (255, 255, 255))
            else:
                l = 0.2126 * r + 0.7152 * g + 0.0722 * b
                l /= 255
                out.putpixel((x,y), (
                        (0x00, 0x51, 0xBA),
                        (0xC4, 0x1E, 0x3A),
                        (0x00, 0x9E, 0x60),
                        (0xFF, 0x58, 0x00),
                        (0xFF, 0xD5, 0x00)
                    )[int(5 * (l <= 0.0031308 and 12.92 * l  or 1.055 * l ** (1/2.4) - 0.055))])

    print "Image converted successfully."

    print "Stats:"
    h, v = img.size[0] / 3, img.size[1] / 3
    print "   ", h, "horiz. Rubik cubes"
    print "   ", v, "vert. Rubik cubes"
    print "   ", h * v, "total Rubik cubes"

    return out.resize((out.size[0], out.size[1]))

if __name__ == "__main__":
    rubik(Image.open(sys.argv[1]).convert("RGB"), int(sys.argv[2])).save(sys.argv[3])

```

Input:

<sub>(source: ilmamilio.it)</sub>

Output with `max_cubes = 25`:

Output with `max_cubes = 75`:

Output with `max_cubes = 225`:
> 1 votes

# Answer
# Objective-C

I saw this challenge last night and had an ever so slightly confusing time with `-[NSArray indexOfObject:inSortedRange:options:usingComparator:]`, hence the delay.

```
- (UIImage  *)rubiksImage:(UIImage *)inputImg
{
    //Thank you http://stackoverflow.com/a/11687434/1153630 for the greyscale code
    CGRect imageRect = CGRectMake(0, 0, inputImg.size.width, inputImg.size.height);

    int width = imageRect.size.width;
    int height = imageRect.size.height;

    uint32_t *pixels = (uint32_t*)malloc(width * height * sizeof(uint32_t));

    memset(pixels, 0, width * height * sizeof(uint32_t));

    CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB();
    CGContextRef context = CGBitmapContextCreate(pixels, width, height, 8, width * sizeof(uint32_t), colorSpace, kCGBitmapByteOrder32Little | kCGImageAlphaPremultipliedLast);

    CGContextDrawImage(context, imageRect, [inputImg CGImage]);

    const int RED = 1;
    const int GREEN = 2;
    const int BLUE = 3;

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            uint8_t* rgbaPixel = (uint8_t*)&pixels[y * width + x];
            uint32_t grayPixel = 0.3 * rgbaPixel[RED] + 0.59 * rgbaPixel[GREEN] + 0.11 * rgbaPixel[BLUE];

            NSArray *r = [self rubixColorFromGrey:grayPixel];

            rgbaPixel[RED] = [r[2] integerValue];
            rgbaPixel[GREEN] = [r[1] integerValue];
            rgbaPixel[BLUE] = [r[0] integerValue];
        }
    }

    CGImageRef newCGImage = CGBitmapContextCreateImage(context);

    CGContextRelease(context);
    CGColorSpaceRelease(colorSpace);
    free(pixels);

    UIImage* newUIImage = [UIImage imageWithCGImage:newCGImage];

    CGImageRelease(newCGImage);

    return newUIImage;
}

- (NSArray *)rubixColorFromGrey:(uint32_t)p
{
    NSArray *colors = @[@0, @51, @102, @153, @204, @255];

    NSUInteger index = [colors indexOfObject:@(p)
                               inSortedRange:NSMakeRange(0, colors.count)
                                     options:NSBinarySearchingInsertionIndex | NSBinarySearchingFirstEqual
                             usingComparator:^(id a, id b) {
                                return [a compare:b];
                             }];
    switch (index) {
        case 0:
            return rgb(0, 81, 186);
            break;
        case 1:
            return rgb(196, 30, 58);
            break;
        case 2:
            return rgb(0, 156, 96);
            break;
        case 3:
            return rgb(255, 82, 0);
            break;
        case 4:
            return rgb(255, 213, 0);
            break;
        case 5:
            return rgb(255, 255, 255);
            break;

        default:
            break;
    }

    return colors; //go wild
}

NSArray *rgb(int r, int g, int b)
{
    return @[@(r), @(g), @(b)];
}

```

I ran it on my iPad like so:

```
UIImageView *img = [[UIImageView alloc] initWithImage:[self rubiksImage:[UIImage imageNamed:@"danny.png"]]];
[img setCenter:self.view.center];
[self.view addSubview:img];

```

**Before** **After**

**Before** **After**
> 1 votes

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


title: Integer Logarithm

text:
# Question
Title: Integer Logarithm
# Objective

Take \\$a \in ℤ\_{\>1}\\$ and \\$b \in ℤ\_+\\$ as inputs. Write a function \\$f\\$ such that:

$$ f(a,b) = \left\\{ \begin{array}{ll} \log\_ab & \quad \text{if} \space \log\_ab \in ℚ \\ -1 & \quad \text{otherwise} \end{array} \right. $$

# Rules

* Types and formats of the inputs doesn't matter.
* Type and format of the output doesn't matter either, but the fraction must be irreducible. In C++, `std::pair<int,unsigned>` is an example. (Regarding logarithms, the numerator and the denominator need not to be arbitrary-length integers.)
* Regardless of whether the input type can handle arbitrary-length integers, the algorithm must be "as if" it were handling those. So using floating-point numbers is implicitly banned.
* If \\$a\\$ and \\$b\\$ aren't in the sets as specified above, the challenge falls in *don't care* situation.
* \\$f\\$ may be curried or uncurried.
* As this is a code-golf, the shortest code in bytes wins.

# Test cases

```
a   b   => answer
-----------------
2   8   => 3/1
3   9   => 2/1
8   2   => 1/3
9   3   => 1/2
4   8   => 3/2
64  256 => 4/3
999 1   => 0/1
-----------------
2   7   => -1
10  50  => -1
5   15  => -1

```

# Answer
# Sledgehammer, 11 bytes

Alternatively, 83 bits.

I ended up forgetting to actually *answer* this with Sledgehammer for a while...

```
⣜⢍⡪⡱⣰⡵⠅⣧⣼⣅⣸

```

Compressed from this Wolfram Language code:

```
If[NumberQ[x1 = Log[Input[], Input[]]], x1, -1]

```

, where `NumberQ` is a built-in that checks whether `Log` has returned an actual number and not a symbolic expression, i.e. when it is rational.
> 1 votes

# Answer
# Mathematica, ~~47~~ ~~45~~ ~~43~~ 29 bytes SBCS

```
If[NumberQ[c=#~Log~#2],c,-1]&

```

You can try it online!

Thanks to @J42161217 for saving me a total of 16 bytes!!
> 8 votes

# Answer
# Python 3, ~~103~~ ~~101~~ 97 bytes

Saved 2 bytes thanks to Kevin Cruijssen!!!
Saved 4 bytes thanks to Value Ink!!!

```
from math import*
def f(a,b):
 l=log(b,a)
 n,m=l.as_integer_ratio()
 return -1if a**n-b**m else l

```

Try it online!
> 5 votes

# Answer
# Charcoal, ~~88~~ 82 bytes

```
≔Ｅθ⟦⟧ζ≔²ηＷ⊖⌈θ¿⌊﹪θη≦⊕ηＵＭθ⎇﹪κηκ∧⊞Ｏ§ζλη÷κηＦζＦι⊞υκＵＭυＥζ№λιＵＭυ÷ι⊟Φ⊕⌈ι∧λ¬⌈﹪ιλ¿›⌈υ⌊υ-1Ｉ⊟υ

```

Try it online! Link is to verbose version of code. Takes input as a list in \[value, base\] order and outputs numerator and denominator. Edit: Saved 6 bytes by simplifying my check for exclusive factors. Explanation:

```
≔Ｅθ⟦⟧ζ≔²ηＷ⊖⌈θ¿⌊﹪θη≦⊕ηＵＭθ⎇﹪κηκ∧⊞Ｏ§ζλη÷κη

```

Factorise both numbers by trial division.

```
ＦζＦι⊞υκ

```

Collect the factors from both inputs, in case some factors are only present in one of them.

```
ＵＭυＥζ№λιＵＭυ÷ι⊟Φ⊕⌈ι∧λ¬⌈﹪ιλ

```

Divide the multiplicity of each factor in both the base and the value by their GCD.

```
¿›⌈υ⌊υ-1

```

If this is not unique then output `-1`.

```
Ｉ⊟υ

```

If it is unique then output it.
> 5 votes

# Answer
# 05AB1E, ~~18~~ 17 bytes

*-1 byte thanks to Kevin Cruijssen*

```
Ó0ζD€¿÷ʒOĀ}DËiнë®

```

Try it online!

```
Ó                   # prime factorize each input
 0ζ                 # zip the factorizations together with filler 0
                    # for each pair of exponents:
    D€¿             #  get the gcd
       ÷            #  divide both by the gcd (reducing the fraction)
        ʒ  }        # filter the pairs, keep only those where:
         O          #  the sum
          Ā         #  is not 0
            DËi     # if all the resulting pairs are equal:
               н    #  output the first pair
                ë   # otherwise:
                 ®  #  output -1

```
> 5 votes

# Answer
# Python 3, ~~94~~ ~~79~~ 76 bytes

Nothing clever here; this is the obvious brute force approach.

**Edit**: Unified return point and switched to lambda syntax.

**Edit 2**: Shaved off three bytes due to @xnor's `next` trick and rules clarification.

```
lambda a,b:next(((i,j)for i in range(b)for j in range(1,a)if a**i==b**j),-1)

```

Try it online!
> 4 votes

# Answer
# bc, 110 bytes

```
define f(a,b){
c=0
d=1
while(0!=e=a^c-b^d){if(a<2^d){print"-1";return}
if(e>1)d=d+1 else c=c+1}
print c,"/",d}

```

Try it online!

As with a number of my solutions, it outputs its answer and returns 0, which the test code ignores.

The use of scale= in the provided input is only so the expected value can be passed in. (You can't have a string value in bc.) The code is strictly integer... provided you pass in integers. The code may fail if a or the needed root of a is less than two. (See two failing samples in TIO.)
> 3 votes

# Answer
# JavaScript (Node.js),  ~~72~~  68 bytes

Takes input as `(a)(b)`, where \\$a\\$ and \\$b\\$ are BigInts. Returns either `[numerator, denominator]` or \\$-1\\$.

```
a=>g=(b,p=0n,q=1n)=>p>b?-1:(d=a**p-b**q)?g(b,d>0?++q&&p:-~p,q):[p,q]

```

Try it online!

### How?

We start with \\$p=0\\$ and \\$q=1\\$. We iteratively increment \\$q\\$ if \\$a^p\>b^q\\$ or increment \\$p\\$ if \\$a^p\b\\$ (no solution).
> 3 votes

# Answer
# Ruby, 72 bytes

```
->a,b{n,d=[*1..a*b].product([*1..a]).find{|n,d|a**n==b**d};n ?n/1r/d:-1}

```

Try it online!
> 1 votes

---
Tags: code-golf, math, arithmetic, integer, rational-numbers
---


title: Broken Keyboard

text:
# Question
Title: Broken Keyboard
You're writing your favorite language and you want to display the following string: `abcdefghijklmnopqrstuvwxyz` to your happy customer. Unfortunately, your keyboard is broken and you can now only type symbols `!+-*/[]()`.

You must submit a code that evaluates to be the string `abcdefghijklmnopqrstuvwxyz` or print the string `abcdefghijklmnopqrstuvwxyz` and contain only symbols `!+-*/[]()`. For example, `+![]+[]` in javascript evaluates to be the string `0`.

The shortest valid submission in 7 days wins. If there're multiple ones, I'll accept the one with the earliest last modification time. Good luck!

# Answer
## `c`, 149 bytes

DISCLAIMER: This answer has *nothing* to do with the water closet.

The `c` flag `c`onfuses the interpeter with strings and character arrays, therefore outputting the lowercase alphabet. Note that I already had this idea before this challenge.

How to enter an empty input: just type `""` as the input, W will not recognize this operand.

```
]+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

```

## Explanation

After compilation, it looks like this:

<pre><code>] % Roll the whole stack into a list (surrounding the input).
  % The stack: []

+ % W is short of operands, so an implicit argument is added.
  % The input is 0 by default if it's empty.
  % The stack: [0]

) % Increment all (automatically vectorizes)
  % The stack: [1]

+ % Join with the implicit input
  % The stack: [0,1]
)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+

% After all that boring stuff, the stack becomes:

% [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

97+

% For clarity the 97 )'s are converted to addition. Stack:

% [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]

Flag:C % Convert the numeric array to a string

% Output: abcdefghijklmnopqrstuvwxyz
```
</code></pre>
> 6 votes

# Answer
# Lenguage, \\$1.5161 \times 10^{27}\\$ characters

*Everyone's* favourite language when short of available characters!

A program consisting of *any* 1516111794593168227366643743 characters will print `abcdefghijklmnopqrstuvwxyz` then exit.

This is because that length in binary, left padded to a multiple of 3 bits with zeros is:

```
001 001 110 011 000 011 001 001 010 010 001 001 001 001 001 111
011 001 001 001 001 001 011 110 001 001 010 100 000 011 111

```

Which translated from Binaryfuck to Brainfuck is this  **~~50 49 41~~  31 character** program:

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

```

Which we can easily **try online!**

### How?

Brainfuck starts with an infinite tape of zeros, which may be incremented or decremented (\\$0\\$ decrements to \\$255\\$ and \\$255\\$ increments to \\$0\\$).
`[...]` or `]` are ignored if the value under the head is \\$0\\$ otherwise `]` loops back to its matching `[`
`>` and `<` move the head right and left respectively.
`.` prints the value under the head as a character.

```
--[<+<-->>-----]<-----<[-->.+<]  | print the alphabet  - tape = ". . n A x . ."
--                               | x -= 2  -> x = 254
  [            ]                 | while x != 0:
   <+                            |   move to A; A += 1
     <--                         |   move to n; n -= 2
        >>-----                  |   move to x; x -= 5
                                 |     -> 254//5 + 1 + 255//5 = 102 loops
                                 |        leaving n = 52, A = 102, x = 0
                <-----           | move to A; A -= 5
                      <          | move to n
                       [      ]  | while n != 0:
                        --       |   n -= 2
                          >.     |   move to A; print character(A)
                            +<   |   A += 1; move to n
                                 |     -> 52//2 = 26 loops, printing 'abc...xyz'

```

---

It might just be quicker to order a new keyboard though.
> 10 votes

# Answer
# Brain-Flak, 396 bytes

```
((((((((((((((((((((((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])[()])

```

Try it online!

## Explanation

This answer is pretty simple. We push `z` by doing a bunch of `()`s

```
( () × 122 )

```

Then we use that as a starting place to count down each letter subtracting one each time.

```
( ... [()])

```

Where the `...` is the code that pushed all the letters prior.

The unfortunate thing is that the structure of the goal string actually makes it a lot harder to do anything fancy. `[]` is basically useless since by the time we have anything on the stack we just want to count down. And as if that weren't enough all of the fun operations `{...}`, `{}` and `<>` are unusable.

This answer is likely optimal for brain-flak (without using `-r`).

# Brain-Flak -r, 296 bytes

```
((((((((((((((((((((((((((()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()())())())())())())())())())())())())())())())())())())())())())())())())())())

```

Try it online!

## Explanation

This works like the last one except we start at `a` and count up. This is cheaper since `a` has a smaller code point and adding one is cheaper than subtracting one. It saves exactly 100 bytes because there are 26 letters in the alphabet, going down to 'a' from 'z' saves 2 bytes per letter down which is 50 and changing minus one to plus one saves 2 bytes per letter, which is another 50.

The one issue is that this method does put things in the reverse order so we need `-r` to correct it, which is a flag that just reverses the order that things are output.
> 6 votes

# Answer
# Javascript, ~~19793~~ ~~9031~~ 3318 chars

```
(![]+[])[+!![]]+([][(!![]+[])[!![]+!![]+!![]]+([][[]]+[])[+!![]]+(!![]+[])[+[]]+(!![]+[])[+!![]]+([![]]+[][[]])[+!![]+[+[]]]+(!![]+[])[!![]+!![]+!![]]+(![]+[])[!![]+!![]+!![]]]()+[])[!![]+!![]]+([]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[!![]+!![]+!![]]+([][[]]+[])[!![]+!![]]+(!![]+[])[!![]+!![]+!![]]+(![]+[])[+[]]+(+(!![]+!![]+!![]+[!![]+!![]+!![]+!![]]+(!![]+!![])+(!![]+!![]+!![]+!![]+!![]+!![]+!![]+!![]+!![])+(+!![])+(!![]+!![]+!![]+!![]+!![]+!![]+!![]+!![])+(!![]+!![]+!![])+(!![]+!![]+!![]+!![]+!![]+!![]+!![]+!![])+(+!![])+(+!![])+(+[])+(!![]+!![])+(!![]+!![]+!![]+!![]+!![]+!![])+(+!![])+(+!![])+(!![]+!![]+!![])))[(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[+!![]+[+[]]]+([]+[])[([]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[!![]+!![]+!![]]+(!![]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[+!![]+[+[]]]+([][[]]+[])[+!![]]+(![]+[])[!![]+!![]+!![]]+(!![]+[])[+[]]+(!![]+[])[+!![]]+([][[]]+[])[+[]]+([]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[!![]+!![]+!![]]+(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[+!![]+[+[]]]+(!![]+[])[+!![]]][([][[]]+[])[+!![]]+(![]+[])[+!![]]+([]+(+[])[([]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[!![]+!![]+!![]]+(!![]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[+!![]+[+[]]]+([][[]]+[])[+!![]]+(![]+[])[!![]+!![]+!![]]+(!![]+[])[+[]]+(!![]+[])[+!![]]+([][[]]+[])[+[]]+([]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[!![]+!![]+!![]]+(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[+!![]+[+[]]]+(!![]+[])[+!![]]])[+!![]+[+!![]]]+(!![]+[])[!![]+!![]+!![]]]](!![]+!![]+[!![]+!![]+!![]+!![]+!![]+!![]+!![]])+(!![]+[])[+!![]]+(![]+[])[!![]+!![]+!![]]+(!![]+[])[+[]]+([][[]]+[])[+[]]+(+(!![]+!![]+!![]+!![]+!![]+[!![]+!![]+!![]]+(!![]+!![]+!![]+!![]+!![]+!![])+(+[])+(!![]+!![]+!![]+!![]+!![])+(+!![])+(+!![])+(!![]+!![]+!![]+!![]+!![])))[(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[+!![]+[+[]]]+([]+[])[([]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[!![]+!![]+!![]]+(!![]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[+!![]+[+[]]]+([][[]]+[])[+!![]]+(![]+[])[!![]+!![]+!![]]+(!![]+[])[+[]]+(!![]+[])[+!![]]+([][[]]+[])[+[]]+([]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[!![]+!![]+!![]]+(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[+!![]+[+[]]]+(!![]+[])[+!![]]][([][[]]+[])[+!![]]+(![]+[])[+!![]]+([]+(+[])[([]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[!![]+!![]+!![]]+(!![]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[+!![]+[+[]]]+([][[]]+[])[+!![]]+(![]+[])[!![]+!![]+!![]]+(!![]+[])[+[]]+(!![]+[])[+!![]]+([][[]]+[])[+[]]+([]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[!![]+!![]+!![]]+(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+(![]+[])[!![]+!![]]+(![]+[])[+!![]]+(!![]+[])[+[]]])[+!![]+[+[]]]+(!![]+[])[+!![]]])[+!![]+[+!![]]]+(!![]+[])[!![]+!![]+!![]]]](!![]+!![]+!![]+[!![]+!![]+!![]+!![]+!![]+!![]])

```

See, this is what happens when people can't be bothered to write javascript by hand. They use generators. Still, that was an interesting challenge!

A better generator dropped over ~~10k~~ 16k chars. Wow.
> 3 votes

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


# Question
Title: Write the longest period iterating quine bounded by 500 bytes
Your job is to create the longest period iterating quine, where the length of each program in the sequence is bounded by 500 bytes.

That is, if you repeat the following steps:

1. Start with your initial program
2. Run the current program
3. Go back to step 2

You will eventually get back to your original program. The number of programs in the cycle is your score, which you are trying to maximize.

None of the programs may raise any errors. Each program must be run the same way as well (e.g. no different versions, implementations, compiler options, platforms, etc...) (EDIT: Yes, any external state such as that of a pseudo random number generator was included in the last statement. The external state must be "reset" after each run. If you use true random numbers, worst case is assumed.)

What separates this challenge from The longest period iterating quine (other than 100 v.s. 500) is that every program in the cycle must also be 500 bytes or less. This means that the longest possible cycle is (256^501 - 1)/255 or less. That of course is a big number, but not that big in terms of how much code it takes to calculate. So the challenge is about using as many of the (256^501 - 1)/255 possibilities as you can, not a busy beaver challenge.

The programs are not permitted to access its own source code. However an empty program *is* permitted if you want (as long as you follow the other rules).

Since checking the programs manually would be hard, you may figure out the score using theoretical methods. You must include an explanation of the score and correctness with your program. If you can not figure out the score, you may instead use a lower bound of the number of programs in the cycle as a defacto score. You are allowed to update this as you find better lower bounds, or if you find the exact actual score.

This is , so highest score wins!

EDIT: It is recommended that you write what your score is in scientific notation, so that answers are more easily comparable. It is perfectly fine to have other forms of the score as well, especially if they are connected to your program more clearly. Also, readers are encouraged to edit previous answers to comply with this.

# Answer
> 15 votes
# Perl 6, \\$126^{398} \approx 8.86 \times 10^{835}\\$ iterations

```
$!=Q~~;<say "\$!=Q~{chrs(my@a=[R,] polymod :126[$!.ords]+1: 126 xx*)x?(@a-399)}~;<$_>~~.EVAL">~~.EVAL

```

Try it online!

This iterates through all the possible combinations of the first 126 bytes of length 398 and under (excluding strings with leading NUL bytes). If you want to see that it actually returns to the first iteration, you can reduce the length to 1 by changing the limit like so.

### Explanation:

Each iteration increments the string, stored in base 126 form, and then converts it back to base 126. It does this until it reaches a string with length 399, and then resets the string back to empty again. If you're having trouble conceptualising the number, imagine it with ten bytes instead. Starting from `0`, increment up to 4 digits, `1000` and reset. This is \\$10^{4-1}\\$ iterations (including `0` or empty string in my program's case).

```
$!=Q~~;         # Start with an empty string
< ... >~~.EVAL  # Set a string to $_ and EVAL it
  say "\$!=Q~{...}~;<$_>~~.EVAL"   # Print the program with the string replaced by
                       :126[$!.ords]   # The string converted from base 126
                                    +1 # Incremented
          [R,] polymod                : 126 xx*  # Back to base 126
chrs(                                )  # Back to a string
     my@a=                            x?(@a-399)  # Only if it isn't 399 characters

```

# Answer
> 3 votes
# Runic Enchantments, ~~64654106~~; 122387-1 ≈ 2.638 × 10807 iterations

```
"3X4+kSq'ƃZ,r{1?{1[:1Z%1+:a=+:d=+:3X4+=+:6X2+=+:'€(c*?~1-1kq}͍f1+0Bl1=6*?S1-Skql͗2=4*?{͍]}B͍l1=6*?kS1-Sq]}@

```

Try it online!

*Alert: The  is incorrectly displayed, it should be \`\` (0x80).*

Rather than the stack, use a string and the stack operators modified with `͍` to modify a string rather than the stack (see prior revision). As such, each char is limited to 1 byte (0-127 range, minus the problematic characters), but with over 3 times as many of them (due to there being less processing boilerplate due to not having to skip Unicode combining characters, as well as some other byte savings) it achieves a higher number of iterations.

If encoding as a true big endian is allowed (that is, having byte values above 127 without interjecting `0x00` bytes) this can achieve 251387-1 ≈ 4.717 × 10928 iterations. However, TIO's Latin encoding prevents this as noted by Erik the Outgolfer in his Python 2 answer. I would need to check if it works locally before claiming this score.

Should be able to replace `f1+0B` with `'0B` (there's an unprinting `0x16` there), but it was fighting me (things didn't want to branch/skip/return correctly), so I left it alone. This would raise the big-endian structure from 387 to 388.

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), flags: `/u:System.Numerics.BigInteger` and `/r:System.Numerics`

# Score: 10332

Thanks to JoKing who increased my score from 10255 * 2 - 1 to now!

```
var i=Parse("0");var s="var i=Parse({0}{2}{0});var s={0}{1}{0};Write(s,(char)34,s,(++i).ToString().Length<333?i:0);";Write(s,(char)34,s,(++i).ToString().Length<333?i:0);

```

Try it online!

# Explanation

Increments a BigInteger every iteration, until it's length becomes too large, which in that case we instantly revert back to the original quine.

```
//The BigInteger that will be incremented
var i=Parse("0");
//The string that encodes the quine
var s="var i=Parse({0}{2}{0});var s={0}{1}{0};Write(s,(char)34,s,(++i).ToString().Length<333?i:0);";
//Print out the string, with every {0} replaced with quotes and the {1} replaced with the original string
Write(s,(char)34,s,
//And the {2} is replaced to the BigInteger+1 if the BigInteger wouldn't be too long, else 0
(++i).ToString().Length<333?i:0);

```

# Answer
> 1 votes
# DOS COM, 49 bytes, period 2^3608

```
00000000  be 31 01 89 f7 b9 f4 02  f9 ac 14 00 aa 39 ce 72  |.1...........9.r|
00000010  f8 31 c9 b4 3c ba 2b 01  cd 21 89 c3 b4 40 b9 f4  |.1..<.+..!...@..|
00000020  01 ba 00 01 cd 21 b4 3e  cd 21 c3 71 2e 63 6f 6d  |.....!.>.!.q.com|
00000030  00                                                |.|

```

Original assembly to create:

```
 BITS 16
 ORG 0100h
   mov si, l
   mov di, si
   mov cx, 500 + 0100h
   stc
n: lodsb
   adc al, 0
   stosb
   cmp si, cx
   jb n
   xor cx, cx
   mov ah, 3ch
   mov dx, f
   int 21h
   mov bx, ax
   mov ah, 40h
   mov cx, 500
   mov dx, 0100h
   int 21h
   mov ah, 3eh
   int 21h
   ret
f: db "q.com", 0
l: db 0

```

This little jewel writes the next phase to q.com rather than standard output because of nulls and other stuff the terminal cannot handle. The root quine technique is equivalent to stringification and the payload room is used as a 3608 bit counter. Due to the way DOS works, the initial state of the counter contains debris from whatever was in memory prior to its first execution.

The original 49 byte input is unreachable, so if you want to score this as 500 bytes go ahead.

# Answer
> 1 votes
# Clean, \\$251^{226} \approx 2.1 \times 10^{542}\\$

* ~~25139~~ removed dependency on `Text`
* ~~251122~~ golfed incrementing function
* ~~251128~~ combined prefix and suffix source strings
* ~~251188~~ removed dependency on `Gast.GenLibTest`

Presented in xxd format due to nonprintables / invalid UTF-8:

```
00000000: 6d6f 6475 6c65 2071 3b69 6d70 6f72 7420  module q;import
00000010: 5374 6445 6e76 3b53 7461 7274 3d28 7325  StdEnv;Start=(s%
00000020: 2830 2c34 3129 2c3f 5b27 0101 0101 0101  (0,41),?['......
00000030: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000040: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000050: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000060: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000070: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000080: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000090: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000a0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000b0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000c0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000d0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000e0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
000000f0: 0101 0101 0101 0101 0101 0101 0101 0101  ................
00000100: 0101 0101 0101 0101 0101 0101 275d 2c73  ............'],s
00000110: 2528 3432 2c39 3939 292c 712c 732c 7129  %(42,999),q,s,q)
00000120: 3b71 3d69 6e63 2721 273b 3f5b 683a 745d  ;q=inc'!';?[h:t]
00000130: 2363 3d68 2b69 6628 616e 7928 283d 3d29  #c=h+if(any((==)
00000140: 6829 5b27 ff09 0c26 5b27 5d29 2702 2727  h)['...&['])'.''
00000150: 0127 3d5b 633a 6966 2863 3e68 2969 643f  .'=[c:if(c>h)id?
00000160: 745d 3b3f 653d 653b 733d 226d 6f64 756c  t];?e=e;s="modul
00000170: 6520 713b 696d 706f 7274 2053 7464 456e  e q;import StdEn
00000180: 763b 5374 6172 743d 2873 2528 302c 3431  v;Start=(s%(0,41
00000190: 292c 3f5b 2727 5d2c 7325 2834 322c 3939  ),?[''],s%(42,99
000001a0: 3929 2c71 2c73 2c71 293b 713d 696e 6327  9),q,s,q);q=inc'
000001b0: 2127 3b3f 5b68 3a74 5d23 633d 682b 6966  !';?[h:t]#c=h+if
000001c0: 2861 6e79 2828 3d3d 2968 295b 27ff 090c  (any((==)h)['...
000001d0: 265b 275d 2927 0227 2701 273d 5b63 3a69  &['])'.''.'=[c:i
000001e0: 6628 633e 6829 6964 3f74 5d3b 3f65 3d65  f(c>h)id?t];?e=e
000001f0: 3b73 3d22                                ;s="

```

Try it online!

Increments a 226-byte string through all byte values excluding `\0`, `\n`, `\r`, `'` and `\`.

The reason we avoid these characters is:

* `\0` makes the compiler angry
* `\n` and `\r` can't appear in charlists
* `'` would end the charlist
* `\` could cause problems if it comes before an escapable character

Once the string is all `\377`s it wraps around to all `\001`s, giving the original program.

# Answer
> 1 votes
# Python 2, 500 bytes, \\$252^{219}\\$

```
#coding=L1
s=""""""
for i in range(220-len(s.lstrip("ÿ")))[:219]:s=s[:i]+chr(ord(s[i])%255-~(s[i]in"!$&"))+s[i+1:]
S='#coding=L1\ns="""%s"""\nfor i in range(220-len(s.lstrip("\xff")))[:219]:s=s[:i]+chr(ord(s[i])%%%%255-~(s[i]in"!$&"))+s[i+1:]\nS=%%r;print S%%%%s%%%%S';print S%s%S

```

Note that there is a trailing newline. It might get removed above if the syntax highlighter forces its way in.

Unfortunately, you can't execute this program in TIO, as it's encoded in Latin-1.

Above, `s` contains 219 0x01 bytes. After the program runs, its source is printed, except for one difference: `s` has been incremented like a base-252 big-endian number, so its leftmost character has been "incremented" to 0x02. The bytes 0x00, 0x22, 0x25 and 0x5C are avoided, so, if any character of the string becomes one of those after the incrementation, the character itself is incremented again.

* 0x00 (null): A Python source file can't contain null characters.
* 0x22 (`"`): There's a danger of three 0x22 bytes forming in a row, that is, `"""`, or the last character of the string becoming `"`, so the string would be closed prematurely.
* 0x25 (`%`): printf-like string formatting is used before completion of the quine skeleton, so a `%` not adjacent to another `%` in `s` will cause trouble. Unfortunately, it's not possible to reorder the formatting to avoid this caveat.
* 0x5C (`\`): There's a possibility that the `\` is used as an escape mark in the string, instead of verbatim, so it's avoided.

Therefore, 252 out of 256 bytes are usable. If `s` contains 219 0xFF (`ÿ`) bytes, it's simply reverted to 219 0x01 bytes, hence completing the cycle.

Given the above, we have \\$252^{219}\\$ possible strings, hence as many programs overall.

\\$252^{219}=8067118401622543607173815381864126969021321378412714150085501148172\\081568355283332551767558738710128769977220628694979838777041634307806013053\\042518663967641130129748108465109552157004184441957823830340121790768004370\\530578658229253323149648902557120331892465175873053680188287802536817909195\\292338112618632542000472094347226540339409672851252596442228662174845397731\\175044304251123874046626291460659909127172435776359148724655575878680270692\\451120531744950544969860952702932354413767504109600742385916705785109741289\\800204288\\$

# Answer
> 1 votes
# Python 2, 57 bytes, 16444 ≈ 4.258 \\$\times\\$ 10534 iterations

-1 byte and \\$\times\\$16 iterations thanks to @AndersKaseorg

```
b=0x0;s="print'b=%#x;s=%r;exec s'%(-~b%4**888,s)";exec s

```

Increments a hexadecimal counter on each iteration and when it reaches \\$16^{444}\\$ it resets to \\$0\\$

Try it online!

# Answer
> 0 votes
# Gol\>\<\>, 70 bytes, 39039000 iterations

```
":1=l8:*6+=S&Q~:'~'=Q~~'H#'||lPaa*5*=?1:1=Q$~$~|:1)lPaa*5*(Q?:|r2ssH##

```

Wow, that is a lot lower than I thought it would be... Next step! Making it have more iterations!!!

Try it online!

# Answer
> 0 votes
# Python 3.8 (pre-release), 500 bytes, 221290 ≈ 7.477 \\$\times\\$ 10679

```
#coding=L1
c=r"##################################################################################################################################################################################################################################################################################################|";exec(s:='from itertools import*;print("#coding=L1\\nc=r\\"%s|\\";exec(s:=%r)"%([*filter(c[:-1].__lt__,map("".join,combinations_with_replacement(map(chr,range(35,256)),290))),"#"*290][0],s))')

```

Try it online!

Try a smaller version online!

# Python 3.8 (pre-release), 500 bytes, 93314 ≈ 1.269 \\$\times\\$ 10618

```
c=r"##########################################################################################################################################################################################################################################################################################################################|";exec(s:='from itertools import*;print("c=r\\"%s|\\";exec(s:=%r)"%([*filter(c[:-1].__lt__,map("".join,combinations_with_replacement(map(chr,range(35,128)),314))),"#"*314][0],s))')

```

Ascii version

Try it online!

Try a smaller version online!

# Explanation

The value assigned to `c` iterates through all possible strings of length 290 (314 in the ascii version) formed from the characters in the range `\x23` to `\xff` (`\x23` to `\x7f` in the ascii version)

Since the string assigned to `c` is prefixed with a `r` backslashes in the string are not treated as the beginning of escape sequences, this allows the use of backslashes inside the string assigned to `c` without causing problems.

Since a string like `r'\'` still cause problems a `|` is added to the end of the string assigned to `c`.

---
Tags: code-challenge, quine, code-generation
---


title: Dice from Changing Random Generator

text:
# Question
Title: Dice from Changing Random Generator
## Introduction

You are given a random integer generator with the following implementation

* The first invocation always returns 1.
* The second invocation returns a random integer between 1 and 2.
* The third invocation returns a random integer between 1 and 3.
* The nth invocation returns a random integer between 1 and n, inclusive.

Based on the above function, write a random dice generator that is perfectly random, returning a value between 1 and 6 (inclusive) with equal probability.

## Rules

* Your program/function should result in a random integer between 1 and 6, inclusive, in some usable form, i.e., to standard output or as a function return value.
* The ascending random number generator above can be defined as a "free" function in your program (i.e., doesn't count toward your character count), or a separate script/program that is executed as needed, assuming the state (`n`) is persistent between calls.
* Assume that no more than 1000 dice rolls will ever be requested in a single use case of your program, and the initial random number generator can be reset to `1` at the end of 1000 dice rolls to avoid overflow of `n`.
* Your program may not use *any* other source of random numbers except the ascending random generator defined above. You may of course request multiple random numbers from the random number generator for each single dice roll output.
* This is code-golf, so winner is shortest answer or most votes in the event of a tie. If you can generate 1000 dice rolls using less than 1000 generated random numbers, give yourself a **10-point efficiency bonus**.

## Example

```
./asc-rand
1 # random integer between 1 and 1
./asc-rand
1 # random integer between 1 and 2
./asc-rand
3 # random integer between 1 and 3
./asc-rand
4 # random integer between 1 and 4

# dice-gen generates random dice based on output of asc-rand program.
./dice-gen
3
./dice-gen
6
./dice-gen
5
./dice-gen
1

```

# Answer
# J - 13 char

This makes the same assumptions as Golfscript: that the number of dice is in stdin and we list the dice rolls that are to come out.

```
r=:1+?  NB. free random function
r>:i.".1!:1]1

```

Explained by explosion:

```
r=:1+?           NB. r(x) = 1 + a random number between 0 and n-1
           ]1    NB. input file handle
       1!:1      NB. read in a string
     ".          NB. convert to integer
 >:i.            NB. make a list of numbers, from 1 to that integer
r                NB. apply the random function

```

If that is somehow unsatisfactory, here is a longer, 21-char program, that can be called with `f''` to generate random numbers, featuring a state and everything.

```
r=:1+?  NB. free random function
c=:0
f=:3 :'r c=:1+c'

```
> 2 votes

# Answer
## Python, 31 chars

Similarly to scleaver, define the generator like this:

```
from random import randint
n=0
def r():
    global n;n+=1
    return randint(1,n)

```

Then a function to return dice rolls:

```
D=lambda:eval('r(),'*6)[-1]%6+1

```

Call `D()` any time you need a uniformly random dice roll.
> 6 votes

# Answer
## Scala 23

```
def s={r;r;r;r;r;r%6+1}

```

The method r can be (approx.) implemented like this:

```
var cnt = 0
val rnd = new util.Random

def r = {
  cnt %= 1000
  cnt += 1
  rnd.nextInt (cnt)
}

```

a rough test:

```
scala> (1 to 6).map (i => ((1 to 600) map (_=>s)).filter (_ == i).size)
res26: scala.collection.immutable.IndexedSeq[Int] = Vector(110, 105, 91, 96, 106, 102)

```

Every 6th call should produce an equal distribution over the 6 values, so I throw away 5.
> 3 votes

# Answer
## GolfScript (15 chars)

This assumes that the number of rolls required is supplied on stdin and lists that many results to stdout.

```
# The free increasing random function
0:N;{N):N rand)}:r;

~{r{;r}5*6%)n}*

```

Online demo

While I could get the 10 point bonus for using fewer than 1000 rolls to generate 1000 numbers, it would cost me far more than 10 characters. The trivial approach of extracting suitable entropy when N is a multiple of a power of 2 or 3 falls well short because the number of results available mod 3 is only 333 + 111 + 37 + 12 + 4 + 1 = 498. Therefore it's necessary to take a sample-and-reject approach. Using this approach you can get an expected 2242 rolls from 1000 calls to `r`, but there's extra overhead from the book-keeping and `base` is a very long function name.
> 2 votes

# Answer
# Python 65 63

```
i=7
while i>5:[R()for x in range(9)];i=int(`R()`[-1])
print i+1

```

The function `R()` is the ascending randomizer.

### Usage:

```
$ ./rollDice.py
3
$ ./rollDice.py
5

```
> 1 votes

# Answer
# Python, 56

r is defined as:

```
from random import randint
n=0
def r(z):
    global n;n+=1
    return randint(1,n)

```

the dice generator d:

```
import math;d=lambda:math.ceil(6.*r(r(r(r(r(r(0))))))/n)

```

usage, eg, for 100 rolls:

```
for i in range(100):print d()

```
> 1 votes

# Answer
# Mathematica 51

The random number generator, `r`, is reset by setting the global variable, `n` to 1.

```
n = 1; r[c_] := RandomInteger[{1, c}]

```

**Code**

Not in the running for the shortest code...

```
h := (n++; If[n < 4 \[Or] (y = r@n) > 6 Quotient[n, 6], h, y~Mod~6 + 1])

```

---

**Usage**

```
t = Table[h, {60000}];
n
SortBy[Tally[t], First]

```

60000 rolls of the dice required 60031 calls to `h`. `Tally` shows the breakdown by numbers 1-6.

> 60031
>
> {{1, 9923}, {2, 9966}, {3, 10016}, {4, 10028}, {5, 10009}, {6, 10058}}
> 1 votes

# Answer
## Perl, 22 or 45

Implementation of the ascending random number generator:

```
my $n=0;
sub r { $n++; return 1+int(rand$n); }

```

Generating:

```
#copy of the Scala solution; short code; uses 6N rolls
sub s{r;r;r;r;r;1+r%6}
#more efficient implementation, uses approximately 6+N+lnN rolls
sub roll { do{$a=r-1}while($a>$n-$n%6);return 1+(1+$a)%6 }

```

Testing out:

```
n number   chisquare
1 10001867 0.348569
2 10004853 2.355161
3 9994395  3.141602
4 10000177 0.003133
5 9999227  0.059753
6 9999481  0.026936
T 60000000 5.935154
60000000 dice rolls took 60000042 calls to r and 570.432735 seconds

```
> 1 votes

# Answer
# JavaScript (Node.js), 35 bytes

```
//random number generating function
g=1;f=()=>(1+g>1000?g++:5*Math.random())|0

```

```
i=0;while(i++<5)f();t=()=>f()%6+1|0

```

Try it online!
> 0 votes

# Answer
# x86 opcode, 15 bytes

```
f:  mov cx, 6
    call r ; return in AX
    loop $-3
    cwd
    div word [f+1]
    inc dx
    ret ; return in DX

```
> 0 votes

# Answer
# GolfScript, 8 bytes

```
f;3f*f(-

```

Try it online!

It pops the generator once, then gets rid of the result. Then it rolls f2, and multiplies it by 3 (3 or 6), then subtracts f3-1 (0, 1, 2) which results in (3-2, 3-1, 3-0) or (6-2, 6-1, 6-0) W5.

Golfscript and the random function existed before this question was posted, so is a legal submission.

This is the run-only-once submission. If you need to run it several times in one call,

# GolfScript, 12 bytes

```
f;3f*f-)0:i;

```

Try it online!

This resets your i call to 0 so it resets accordingly. This TIO shows 50 random results.
> 0 votes

# Answer
# C (gcc), 31 bytes

```
f(i){for(i=5;i--;)c;i=~-c%6+1;}

```

Every 6 calls, the probability of every number between 1 and 6 inclusive being generated is equal.

`c` is `#define`d as a call to a function that generates the perfect random numbers.

Try it online!
> 0 votes

---
Tags: code-golf, random
---