title: Increment a GUID

text:
# Question
Title: Increment a GUID
Inspired by a recent Daily WTF article...

Write a program or function that takes a GUID (string in the format `XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX`, where each X represents a hexadecimal digit), and outputs the GUID incremented by one.

## Examples

```
>>> increment_guid('7f128bd4-b0ba-4597-8f35-3a2f2756dfbb')
'7f128bd4-b0ba-4597-8f35-3a2f2756dfbc'
>>> increment_guid('06b86883-f3e7-4f9d-87c5-a047e89a19fa')
'06b86883-f3e7-4f9d-87c5-a047e89a19fb'
>>> increment_guid('89f25f2f-2f7b-4aa6-b9d7-46a98e3cb2cf')
'89f25f2f-2f7b-4aa6-b9d7-46a98e3cb2d0'
>>> increment_guid('89f25f2f-2f7b-4aa6-b9d7-46a98e3cb29f')
'89f25f2f-2f7b-4aa6-b9d7-46a98e3cb2a0'
>>> increment_guid('8e0f9835-4086-406b-b7a4-532da46963ff')
'8e0f9835-4086-406b-b7a4-532da4696400'
>>> increment_guid('7f128bd4-b0ba-4597-ffff-ffffffffffff')
'7f128bd4-b0ba-4598-0000-000000000000'

```

## Notes

* Unlike in the linked article, incrementing a GUID that ends in F must “carry” to the previous hex digit. See examples above.
* You may assume that the input will not be `ffffffff-ffff-ffff-ffff-ffffffffffff`.
* For hex digits above 9, you may use either upper (A-F) or lower (a-f) case.
* Yes, GUIDs may start with a `0`.
* Your output must consist of *exactly* 32 hex digits and 4 hyphens in the expected format, including any necessary leading `0`s.
* You do not have to preserve the version number or other fixed bits of the GUID. Assume it's just a 128-bit integer where none of the bits have any special meaning. Similarly, GUIDs are assumed to sort in straightforward lexicographical order rather than in the binary order of a Windows `GUID` struct.
* If writing a function, the input may be of any sequence-of-`char` data type: `string`, `char[]`, `List<char>`, etc.

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

Saved 2 bytes thanks to *Kevin Cruijssen*

```
'-K1ìH>h¦Ž¦˜S·£'-ý

```

Try it online! or as a Test Suite

**Explanation**

```
'-K                  # remove "-" from input
   1ì                # prepend a 1 (to preserve leading 0s)
     H               # convert from hex to base 10
      >              # increment
       h             # convert to hex from base 10
        ¦            # remove the extra 1
         Ž¦˜S·       # push [8, 4, 4, 4, 12]
              £      # split into parts of these sizes
               '-ý   # join on "-"

```
> 8 votes

# Answer
# Python 2, 50

* 3 bytes saved thanks to @Dennis.

```
lambda s:UUID(int=UUID(s).int+1)
from uuid import*

```

Try it online!
> 19 votes

# Answer
# JavaScript (ES6), 85 bytes

The output string is in lowercase.

```
s=>(g=(c,x=+('0x'+s[--n])+!!c)=>1/x?g(x>>4)+(x&15).toString(16):~n?g(c)+'-':'')(n=36)

```

Try it online!

### Commented

```
s => (                   // s = GUID
  g = (                  // g = recursive function taking:
    c,                   //   c = carry from the previous iteration
    x = +('0x' + s[--n]) //   x = decimal conversion of the current digit
        + !!c            //       add the carry
  ) =>                   //
    1 / x ?              // if x is numeric:
      g(x >> 4) +        //   do a recursive call, using the new carry
      (x & 15)           //   and append the next digit
      .toString(16)      //   converted back to hexadecimal
    :                    // else:
      ~n ?               //   if n is not equal to -1:
        g(c)             //     do a recursive call, leaving the current carry unchanged
        + '-'            //     and append a hyphen
      :                  //   else:
        ''               //     stop recursion
)(n = 36)                // initial call to g with n = 36 and a truthy carry

```
> 11 votes

# Answer
# Python 2, 82 bytes

```
q='f0123456789abcdef--'
f=lambda s:[str,f][s[-1]in'f-'](s[:-1])+q[q.find(s[-1])+1]

```

Try it online!

No imports or hex conversion.

This scans from the back of the string, moving each character along the cycle `0123456789abcdef`, with `-` going to itself. After it hits a symbol other than `f` or `-`, it stops scanning leftwards, and just returns the remainder unchanged. This solution isn't specific to the UUID format -- any number of blocks of any number of hex letters would work.

The base case of `[str,f][s[-1]in'f-'](s[:-1])` is a trick I haven't seen used in a golf before. It terminates the recursion without any `if`, `and`, `or`, or other explicit control flow.

Based on the condition `[s[-1]in'f-']` of the last character, the code either returns `f(s[:-1])` or just `s[:-1]` unchanged. Since `str` is the identity on strings, we can select one of the functions `[str,f]` and apply it to `s[:-1]`. Note that the recursive call with `f` is not made if it is not chosen, getting around the common issue problem that Python eagerly evaluates unused options, leading to infinite regress in recursions.
> 5 votes

# Answer
# APL (Dyalog Unicode), 46 bytesSBCS

Anonymous tacit prefix function.

```
⎕CY'dfns'
(∊1hex 16(|+1⌽=)⍣≡1+@32dec¨)@('-'≠⊢)

```

Try it online!

`⎕CY'dfns'`**c**op**y** the "dfns" library (to get `hex` and `dec`)

`(``)`
the argument
differs from
`'-'` a dash
`(``)@` on the subset consisting of the locations **at** which the above criterion is true, apply:
`dec¨` convert each hexadecimal character to a decimal number
…`@32`**at** position 32 (the last digit), apply:
`1+` increment
`16(``)⍣≡` repeatedly apply with left argument 16 until stable:
`=` compare (gives mask where the hexadecimal digits are 16)
`1⌽` cyclically rotate one step left (this is the carry bit)
`|+` to that, add the division remainder when divided (by sixteen, thus making all 16 into 0)
`1hex`  turn digits into length-one hexadecimal character representations
**ϵ**nlist (flatten)
> 3 votes

# Answer
# Ruby `-pl`, ~~62~~ ~~57~~ 55 bytes

```
$_="%032x"%-~gsub(?-,"").hex
7.step(22,5){|i|$_[i]+=?-}

```

Try it online!
> 3 votes

# Answer
# Java 11, ~~152~~ ~~149~~ ~~111~~ 108 bytes

```
s->{var b=s.getLeastSignificantBits()+1;return new java.util.UUID(s.getMostSignificantBits()+(b==0?1:0),b);}

```

-38 bytes thank to *@OlivierGrégoire*.
-3 bytes thanks to *@ASCII-only*.

Try it online.

**Explanation:**

```
s->{         // Method with UUID as both parameter and return-type
  var b=s.getLeastSignificantBits()
             //  Get the 64 least significant bits of the input-UUID's 128 bits as long
        +1;  //  And increase it by 1
  return new java.util.UUID(
             //  Return a new UUID with:
    s.getMostSignificantBits()
             //   The 64 most significant bits of the input-UUID's 128 bits as long
    +(b==0?  //    And if the 64 least significant bits + 1 are exactly 0:
       1     //     Increase the 64 most significant bits by 1 as well
      :      //    Else:
       0,    //     Don't change the 64 most significant bits by adding 0
     b);}    //   And the 64 least significant bits + 1

```

---

**Old 149 bytes answer:**

```
s->{var t=new java.math.BigInteger(s.replace("-",""),16);return(t.add(t.ONE).toString(16)).replaceAll("(.{4})".repeat(5)+"(.*)","$1$2-$3-$4-$5-$6");}

```

Try it online.

**Explanation:**

```
s->{                              // Method with String as both parameter and return-type
  var t=new java.math.BigInteger( //  Create a BigInteger
         s.replace("-",""),       //  Of the input-string with all "-" removed
         16);                     //  Converted from Hexadecimal
  return(t.add(t.ONE)             //  Add 1
         .toString(16))           //  And convert it back to a Hexadecimal String
         .replaceAll("(.{4})".repeat(5)+"(.*)",
                                  //  And split the string into parts of sizes 4,4,4,4,4,rest
           "$1$2-$3-$4-$5-$6");}  //  And insert "-" after parts of size 8,4,4,4,
                                  //  and return it as result

```
> 3 votes

# Answer
# Python 3, 50 bytes

```
from uuid import*
lambda u:UUID(int=UUID(u).int+1)

```

Try it online!
> 3 votes

# Answer
# Python 2, ~~113~~ 112 bytes

```
def f(s):a=hex(int(s.replace('-',''),16)+1+2**128);return'-'.join((a[3:11],a[11:15],a[15:19],a[19:23],a[23:-1]))

```

Try it online!

Without imports
> 2 votes

# Answer
# Retina 0.8.2, 21 bytes

```
T`FfdlL`0dlL`.[-Ff]*$

```

Try it online! Link includes test cases. `9` becomes `a`. Explanation: The regex matches all trailing `f`s and `-`s plus one preceding character. The transliteration then cyclically increments those characters as if they were hex digits. Alternate approach, also 21 bytes:

```
T`L`l
T`fo`dl`.[-f]*$

```

Try it online! Link includes test cases. Works by lowercasing the input to simplify the transliteration. Would therefore be 15 bytes if it only had to support lowercase. Try it online! Link includes test cases.
> 2 votes

# Answer
# MATLAB, 138 bytes

```
a=1;Z=a;for r=flip(split(input(''),'-'))'
q=r{:};z=dec2hex(hex2dec(q)+a,nnz(q));try
z+q;a=0;catch
z=~q+48;end
Z=[z 45 Z];end;disp(Z(1:36))

```

Fixed a bug in case a chunk is all zeros. Also golfed off a lot by abusing try/catch. Net result: 0 bytes saved.

An attempt to 'cheat' by using `java.util.UUID` failed because the `long` value returned from `java.util.UUID.get[Most/Least]SignificantBits` gets converted to a `double` which incurs a loss of precision. I invite you to take a look at this table and silently utter "...but *why?*"

### Explanation

The `hex2dec` function spits out a `double`, so it cannot process the entire GUID at once to avoid exceeding `flintmax`. Instead, we have to process the GUID chunk by chunck, using `split`. The variable `a` checks if we need to carry a one, and cheatingly also is the initial increment we add. The condition for carrying over is whether the lengths of the original and incremented strings are no longer equal.

Original version was just under 160 bytes so I'd like to think this should not be easy to outgolf.
> 2 votes

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

```
x=>{for(int i=35,c;(x[i]=(char)((c=x[i--])<48?c:c==57?65:c>69?48:c+1))<49;);}

```

Try it online!

-1 byte thanks to @ASCIIOnly!

Anonymous function that takes a `char[]` as input and outputs by modifying an argument.

Input is scanned from right to left and replaced using the following rules.

* The `-` character is ignored and processing continues
* The `F` character is converted to `0` and processing continues
* The `9` character is converted to `A` and processing stops
* The characters `A-E` and `0-8` are incremented by 1 and processing stops
> 2 votes

# Answer
# Python 2, 99 bytes

```
s='%032x'%-~int(input().replace('-',''),16)
print'-'.join((s[:8],s[8:12],s[12:16],s[16:20],s[20:]))

```

Try it online!

No `uuid.UUID` usage.
> 2 votes

# Answer
# Powershell, 101 bytes

```
for($p=1;$d=+"$args"[--$i]){$d+=$p*(1-@{45=1;57=-7;70=23;102=55}.$d)
$p*=$d-in45,48
$r=[char]$d+$r}$r

```

Try it online!

No external library or hex conversion. Any string length. Lower case and upper case are allowed. Input string matching to `^[f-]*$` is allowed too.

This script scans from the back of the string and inrement each char by the value from hashtable:

* `-`: increment=1-1
* `9`: increment=1+7, result=`A`
* `F`: increment=1-23, result=`0`
* `f`: increment=1-55, result=`0`
* increment=1 for other chars

Next, the script uses `$p` to determine whether to increment the current char.

Test script:

```
$f = {

for($p=1;$d=+"$args"[--$i]){$d+=$p*(1-@{45=1;57=-7;70=23;102=55}.$d)
$p*=$d-in45,48
$r=[char]$d+$r}$r

}

@(
    ,('f','0')
    ,('F','0')
    ,('0','1')
    ,('9','A')
    ,('A','B')
    ,('a','b')
    ,('0-f','1-0')
    ,('0-F','1-0')
    ,("7f128bd4-b0ba-4597-8f35-3a2f2756dfbb","7f128bd4-b0ba-4597-8f35-3a2f2756dfbc")
    ,("06b86883-f3e7-4f9d-87c5-a047e89a19f9","06b86883-f3e7-4f9d-87c5-a047e89a19fa")
    ,("89f25f2f-2f7b-4aa6-b9d7-46a98e3cb2cf","89f25f2f-2f7b-4aa6-b9d7-46a98e3cb2d0")
    ,("8e0f9835-4086-406b-b7a4-532da46963ff","8e0f9835-4086-406b-b7a4-532da4696400")
    ,("7f128bd4-b0ba-4597-ffff-ffffffffffff","7f128bd4-b0ba-4598-0000-000000000000")
    ,("89f25f2f-2f7b-4aa6-b9d7-46a98e3cb29f","89f25f2f-2f7b-4aa6-b9d7-46a98e3cb2a0")
    ,("ffffffff-ffff-ffff-ffff-ffffffffffff","00000000-0000-0000-0000-000000000000")
) | % {
    $guid,$expected = $_
    $result = &$f $guid
    "$($result-eq$expected): $result"
}

```

Output:

```
True: 0
True: 0
True: 1
True: A
True: B
True: b
True: 1-0
True: 1-0
True: 7f128bd4-b0ba-4597-8f35-3a2f2756dfbc
True: 06b86883-f3e7-4f9d-87c5-a047e89a19fA
True: 89f25f2f-2f7b-4aa6-b9d7-46a98e3cb2d0
True: 8e0f9835-4086-406b-b7a4-532da4696400
True: 7f128bd4-b0ba-4598-0000-000000000000
True: 89f25f2f-2f7b-4aa6-b9d7-46a98e3cb2A0
True: 00000000-0000-0000-0000-000000000000

```
> 2 votes

# Answer
# Perl 6, 65 bytes

```
{(:16(TR/-//)+1).base(16).comb.rotor(8,4,4,4,*)».join.join('-')}

```

Test it
> 1 votes

# Answer
# Jelly, 20 bytes

-2 (and a bug fix) thanks to Dennis!

```
ØhiⱮṣ0µẎḅ⁴‘ḃ⁴ịØhṁj”-

```

**Try it online!**
> 1 votes

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

```
s=>s.replace(/.([f-]*)$/,(s,y)=>('0x'+s[0]-~0).toString(16)+y.replace(/f/g,0))

```

Try it online!
> 1 votes

# Answer
# PowerShell, 126 bytes

```
$a=("{0:X32}" -f (1+[Numerics.BigInteger]::Parse($args[0]-replace"-", 'AllowHexSpecifier')));5..2|%{$a=$a.Insert(4*$_,"-")};$a

```

Try it online!

Pretty trivial answer. Just thought I'd get the beloved PowerShell added to the list :)
> 1 votes

# Answer
# C (clang), 62 bytes

```
g(char*i){for(i+=36;(*--i-45?*i+=*i-70?*i-57?1:8:-22:0)<49;);}

```

Try it online!
> 0 votes

# Answer
# Perl 5, 64 bytes

```
$c=reverse((1+hex s/-//gr)->as_hex);$c=~s/..$//;s/[^-]/chop$c/ge

```

The number of parentheses necessary here makes me sad, but `->` binds very tightly, as `->as_hex` is the quickest way I can find to get hexadecimal-formatted output.

Run with `perl -Mbigint -p`. Basically, it just converts the number to a bigint hexadecimal, adds one, and then subtitutes the digits of the result back into the original value, leaving dashes untouched.
> 0 votes

# Answer
# Rust, 258 bytes

```
let x=|s:&str|s.chars().rev().scan(1,|a,c|{let d=c.to_digit(16).unwrap_or(99);match(d,*a){(15,1)=>{*a=1;Some(0)}(0..=14,1)=>{*a = 0;Some(d + 1)}_=> Some(d),}}).collect::<Vec<u32>>().iter().rev().for_each(|d| print!("{}", std::char::from_digit(*d, 16).unwrap_or('-')));

```

yes its long.. but technically its only one line with 1 expression? and no fancy libraries? and it will not crash on a fuzz input? ungolf:

```
let x=|s:&str|s.chars().rev().scan(1, |a, c| {
            let d = c.to_digit(16).unwrap_or(99);
            match (d, *a) {
                (15, 1) => {*a = 1;Some(0)}
                (0..=14, 1) => {*a = 0;Some(d + 1)}
                _ => Some(d),
            }
        }).collect::<Vec<u32>>().iter().rev()
        .for_each(|d| print!("{}", std::char::from_digit(*d, 16).unwrap_or('-')));

```

try it on rust playground
> 0 votes

# Answer
## 16/32/64-bit x86 assembly code, 28 bytes

bytes: 83C623FDAC3C2D74FB403C3A7502B0613C677502B03088460173E9C3

code:

```
     add esi, 35       ;point to end of string - 1
     std               ;go backwards
l1:  lodsb             ;fetch a character
     cmp al, '-'
     je  l1            ;skip '-'
     inc eax           ;otherwise increment
     cmp al, '9' + 1
     jne l2            ;branch if not out of numbers
     mov al, 'a'       ;otherwise switch '9'+1 to 'a'
l2:  cmp al, 'f' + 1   ;sets carry if less
     jne l3            ;branch if not out of letters
     mov al, '0'       ;otherwise switch 'f'+1 to '0'
                       ;and carry is clear
l3:  mov [esi + 1], al ;replace character
     jnb l1            ;and loop while carry is clear
     ret
```

Call with ESI pointing to GUID. Replace ESI with SI for 16-bit, or RSI for 64-bit (and +2 bytes).
> 0 votes

# Answer
# Common Lisp, 166 bytes

```
(lambda(s &aux(r(format()"~32,'0x"(1+(parse-integer(remove #\- s):radix 16)))))(format()"~{~a~^-~}"(mapcar(lambda(x y)(subseq r x y))#1='(0 8 12 16 20 32)(cdr #1#))))

```

Try it online!
> 0 votes

---
Tags: code-golf
---


title: Draw a path made by direction changers

text:
# Question
Title: Draw a path made by direction changers
This challenge takes place on a grid.

```
+----------+
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
+----------+

```

This one's 10 x 10, but it can be any rectangular shape.

There are four directions on this grid. Up, down, left and right.

The task is to draw a path starting with an upper case direction initial. In this example, will go directly upward from the U.

```
+----------+
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|   U      |
+----------+

```

The path will go upwards and be comprised of full-stop characters (.), until it hits a wall, when it will terminate with an asterisk (\*).

```
+----------+
|   *      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

```

In addition to path starts, there's also direction changers, represented by a lower case direction initial.

```
+----------+
|          |
|          |
|          |
|   r.....*|
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

```

Also, an upper case X us an obstacle which will terminate the path.

```
+----------+
|          |
|          |
|          |
|          |
|   r...*X |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

```

---

# Rules

* The input is a string consisting of a frame, (consisting of |, - and + characters) containing characters denoting path starts, direction changers, and obstacles.
* Your code should add full stop characters to follow the path described by starts and direction changers, and an asterisk when/if the path meets a wall or obstacle.
* There can be multiple path starts.
* The code will still terminate without error if the path describes a loop.
* If a path meets a path start, it will act as a direction changer.
* It's code golf, low-byte code and no standard loopholes, please.
* I always prefer links to an on-line interpreter.

---

# Test Cases

## 1: Simple

```
+----------+
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|   U      |
+----------+

+----------+
|   *      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

```

## 2: Right turn

```
+----------+
|          |
|          |
|          |
|   r      |
|          |
|          |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|   r.....*|
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

```

## 3: Crossroads

```
+----------+
|          |
|          |
|          |
|   r  d   |
|          |
| u    l   |
|          |
|          |
|   U      |
+----------+

+----------+
| *        |
| .        |
| .        |
| . r..d   |
| . .  .   |
| u....l   |
|   .      |
|   .      |
|   U      |
+----------+

```

## 4: 4 Crossing paths

```
+----------+
|      D   |
|          |
|          |
|R         |
|          |
|         L|
|          |
|          |
|   U      |
+----------+

+----------+
|   *  D   |
|   .  .   |
|   .  .   |
|R........*|
|   .  .   |
|*........L|
|   .  .   |
|   .  .   |
|   U  *   |
+----------+

```

## 5: First Loop

```
+----------+
|          |
|          |
|          |
|   r  d   |
|          |
|   u  l   |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|   r..d   |
|   .  .   |
|   u..l   |
|   .      |
|   .      |
|   U      |
+----------+

```

## 6: Starter as changer

```
+----------+
|          |
|          |
|          |
|   L      |
|          |
|          |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|*..L      |
|   .      |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

```

## 7: Straight Loop

```
+----------+
|          |
|          |
|          |
|          |
|   r  l   |
|          |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|          |
|   r..l   |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

```

## 8: Tight Knot

```
+----------+
|          |
|          |
|          |
|  d  l    |
|   r u    |
|  r u     |
|          |
|          |
|   U      |
+----------+

+----------+
|    *     |
|    .     |
|    .     |
|  d..l    |
|  .r.u    |
|  r.u     |
|   .      |
|   .      |
|   U      |
+----------+

```

## 9: An Obstacle

```
+----------+
|          |
|          |
|          |
|          |
|   r    X |
|          |
|          |
|          |
|   U      |
+----------+

+----------+
|          |
|          |
|          |
|          |
|   r...*X |
|   .      |
|   .      |
|   .      |
|   U      |
+----------+

```

## 10: S Shape

```
+----------+
|r     d   |
|          |
|  XXXXXXXX|
| d      l |
|ul        |
|XXXXXXX   |
|          |
|R       u |
|          |
+----------+

+----------+
|r.....d   |
|.     *   |
|. XXXXXXXX|
|.d......l |
|ul      . |
|XXXXXXX . |
|        . |
|R.......u |
|          |
+----------+

```

## 11: 4-Way Knot

```
+----------+
|      D   |
|          |
|   r      |
|R    d    |
|          |
|    u    L|
|      l   |
|          |
|   U      |
+----------+

+----------+
|    * D   |
|    . .   |
|   r.....*|
|R....d.   |
|   ....   |
|   .u....L|
|*.....l   |
|   . .    |
|   U *    |
+----------+

```

## 12: Busy Junctions

```
+----------+
|rrrrr rrrd|
| rlrl     |
|ul rrd    |
|ruX X     |
|udl ll    |
|ull       |
|rlr       |
|rdr  d    |
|Uruull    |
+----------+

+----------+
|rrrrr.rrrd|
|.rlrl    .|
|ul rrd   .|
|ruX.X.   .|
|udl.ll   .|
|ull.     .|
|rlr.     .|
|rdr..d   .|
|Uruull   *|
+----------+

```

## 13: Starts Into Edge

```
+----------+
|   U      |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
+----------+

+----------+
|   U      |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
|          |
+----------+

```

## 14: Crossing Dead Paths

```
+----------+
|          |
|          |
|          |
|      R   |
|          |
|          |
|          |
|          |
|         U|
+----------+

+----------+
|         *|
|         .|
|         .|
|      R..*|
|         .|
|         .|
|         .|
|         .|
|         U|
+----------+

```

# Answer
> 9 votes
# JavaScript (ES6),  ~~191 183~~  181 bytes

*Thanks to @tsh for helping fix a bug*

Takes input as a matrix of characters. Outputs by modifying the input.

```
f=(a,X,Y,d,n=0)=>a.map((r,y)=>r.map((v,x)=>(a+0)[i=' .*dlurDLUR'.indexOf(v),n]?X?X-x+~-d%2|Y-y+(d-2)%2?0:~i?f(a,x,y,i>2?i&3:d,n+1,r[x]=i?v:'.'):n?a[Y][X]='*':0:i>6&&f(a,x,y,i&3):0))

```

Try it online!

### Commented

```
f = ( a,                           // a[]  = input matrix
      X, Y,                        // X, Y = coordinates of the previous cell
      d,                           // d    = current direction (0 .. 3)
      n = 0                        // n    = number of iterations for the current path
    ) =>                           //
  a.map((r, y) =>                  // for each row r[] a position y in a[]:
    r.map((v, x) =>                //   for each character v at position x in r[]:
      (a + 0)[                     //
        i = ' .*dlurDLUR'          //     i = index of the character
            .indexOf(v),           //     blocking characters '-', '|' and 'X' gives -1
        n                          //     by testing (a + 0)[n], we allow each cell to be
      ]                            //     visited twice (once horizontally, once vertically)
      ?                            //     if it is set:
        X ?                        //       if this is not the 1st iteration:
          X - x + ~-d % 2 |        //         if x - X is not equal to dx[d]
          Y - y + (d - 2) % 2 ?    //         or y - Y is not equal to dy[d]:
            0                      //           ignore this cell
          :                        //         else:
            ~i ?                   //           if this is not a blocking character:
              f(                   //             do a recursive call:
                a,                 //               pass a[] unchanged
                x, y,              //               pass the coordinates of this cell
                i > 2 ? i & 3 : d, //               update d if v is a direction char.
                n + 1,             //               increment n
                r[x] = i ? v : '.' //               if v is a space, set r[x] to '.'
              )                    //             end of recursive call
            :                      //           else (this is a blocking character):
              n ?                  //             if this is not the 1st iteration:
                a[Y][X] = '*'      //               set the previous cell to '*'
              :                    //             else:
                0                  //               do nothing
        :                          //       else (1st iteration):
          i > 6 &&                 //         if v is a capital letter:
            f(a, x, y, i & 3)      //           do a recursive call with this direction
      :                            //     else ((a + 0)[n] is not set):
        0                          //       we must be in an infinite loop: abort
    )                              //   end of inner map()
  )                                // end of outer map()

```

# Answer
> 8 votes
# Python 2, ~~283~~ ~~279~~ ~~293~~ ~~288~~ 279 bytes

```
e=enumerate
def f(M):
 s=[(x,y,c)for y,l in e(M)for x,c in e(l)if'A'<c<'X'];v=set(s)
 for x,y,C in s:
	d=ord(C)%87%5;q=d>1;X,Y=x-d+q*3,y+~-d-q;c=M[Y][X];N=(X,Y,[C,c]['a'<c<'x'])
	if'!'>c:M[Y][X]='.'
	if(c in'-|X')*('/'>M[y][x]):M[y][x]='*'
	if(c in'udlr. *')>({N}<v):v|={N};s+=N,

```

Try it online!

Takes a list of lists.

Outputs by modifying the input array.

# Answer
> 6 votes
# Perl 5, ~~203~~ ~~188~~ 166 bytes

```
$l='\K[ a-z](?=';$t='([-|X])?';$s=$_;/
/;$n='.'x"@-";{$_|=s/(?|R[.*]*$l$t)|$t${l}[.*]*L)|D$n(?:[.*]$n)*$l$n$t)|$t$n$l$n([.*]$n)*U))/$&eq$"?$1?'*':'.':uc$&/es?redo:$s}

```

TIO

How it works

* `$s=$_` to save input into `$s` to restore lowercase changers. `$_|=$s` because bitwise or with space  will not change `.` and `*`, lowercase letters `urld` will be restored with bitwise or operation.
* `/\n/;$n='.'x"@-"` to get "width" and `$n` to match any character "width" times
* `$l='\K[ a-z](?=';$t='([-|X])?'` to reduce regex length ; `$l` to match a lowercase letter `urld` or a space on a path, `$t` to match a terminator.

After replacement : `(?|
R[.*]*\K[ a-z](?=([-|X])?)
|
([-|X])?\K[ a-z](?=[.*]*L)
|
D$n(?:[.*]$n)*\K[ a-z](?=$n([-|X])?)
|
([-|X])?$n\K[ a-z](?=$n([.*]$n)*U)
)`

* switches `/e` to eval, `/s` so that `.` (inside `$n`) matches also a newline character
* `$&eq$"?$1?'*':'.':uc$&` if matched is a space, if termiator matched `*` otherwise `.` otherwise uppercase.

# Answer
> 4 votes
# Clean, 409 bytes

```
import StdEnv,Data.List
q=flatlines
$m=foldl(zipWith\a b|a=='*'||b=='*'='*'=max a b)(q m)[q(foldl(\m(_,y,x)=[[if(b<>x||a<>y)if(k=='*')'.'k'*'\\k<-r&b<-[0..]]\\r<-m&a<-[0..]])m(last(takeWhile(not o hasDup)(inits(f 0y 0x)))))\\l<-m&y<-[0..],c<-l&x<-[0..]|isUpper c]
where f a y b x=let(u,v)=(a+y,b+x)in(case toLower((m!!u)!!v)of' '=[((a,b),u,v):f a u b v];'r'=f 0u 1v;'l'=f 0u -1v;'u'=f -1u 0v;'d'=f 1u 0v;_=[])

```

Try it online!

# Answer
> 3 votes
# Python 2, 250 bytes

```
def f(G,e=enumerate):
 for i,k in e(G):
	for j,l in e(k):
	 v=X=x=y=m,=l,
	 while(m in'-X|')<(l in'DLRU')>(X in v):v+=X,;y,x=zip((1,0,0,-1,y),(0,-1,1,0,x))['DLRU dlru'.find(m)%5];G[i][j]=(m,'.*'[G[i+y][j+x]in'-X|'])[m<'!'];i+=y;j+=x;X=x,i,j;m=G[i][j]

```

Try it online!

Takes a list of lists of 1-char strings, as explicitly allowed by the OP.

Changes the list in place.

For easier I/O, use this.

---
Tags: code-golf
---


# Question
Title: Create a grid as close to a square as possible
**Create a function or program that makes a grid as close to an square as possible**

* You will be given an integer *N* as input, whole numbers (1,2,3,25, etc)
* The output must be a perfect rectangular grid of *N* letters as close to a square as possible
* The (wannabe)square must consist of one of the the letters O or X as specified by user

**Points**:

* Hardcoded to only O or X: +1
* A param(0/1, true/false, something similar) to rotate output (like with 5 or 8): -10
* Design the square (use both O and X in some sort of pattern): -5

A pattern is considered valid if it contains both types of characters (where x/y-axis \>= 3) and the pattern stays the same when flipped horizontally or vertically (exchanging Xs with Os is allowed)

**Examples**

```
INPUT: 4         INPUT: 5       INPUT: 8              INPUT: 9
OO               OOOOO          XXXX                  XOX
OO                              XXXX                  OXO
                                or rotated 90deg      XOX

```

**Examples which aren't allowed (not same length row or columns)**

```
BAD RESULT: 5a        BAD RESULT: 5b      BAD RESULT: 8
OOO                   OO                  OOO
OO                    OO                  OOO
                      O                   OO

```

If possible please provide an online example.

# Answer
## CJam, 16 (31 - 10 - 5)

This takes two integers are input, first one being `0` or `1` for direction and second one being the number of `O` or `X` in the grid.

It prints an alternate `O` and `X`.

```
:X"OX"*X<\Xmqi){(_X\%}g_X\/?/N*

```

This is just the function body, to try it out add `l~` in front of the code like:

```
l~:X"OX"*X<\Xmqi){(_X\%}g_X\/?/N*

```

and give input like

```
0 10

```

to get output like

```
OXOXO
XOXOX

```

or input like

```
1 10

```

for

```
OX
OX
OX
OX
OX

```

Try it online here

---

How it works:

```
l~                                 "Put the two input integers to stack";
  :X                               "Assign the number of cells to X";
    "OX"*                          "Take string "OX" and repeat it X times";
         X<                        "Slice it to take only first X characters";
           \                       "Swap top two stack elements, now string is at bottom";
            Xmqi)                  "Take square root of X, ceil it and put on stack";
                 {(_X\%}g          "Keep decrementing until it is perfectly divisible by X";
                         _X\/      "Copy it, divide X by that and put it on stack";
                             ?     "Based on first input integer, take either of numbers";
                              /    "Divide the XOXO string that many times";
                               N*  "Join the string parts with a new line";

```

Example run:

```
l~ed:X"OX"*edX<ed\edXmqi)ed{(_X\%}ged_edXed\ed/ed?ed/edN*ed

#INPUT:
1 10

#OUTPUT:
Stack: [1 10]

Stack: [1 "OXOXOXOXOXOXOXOXOXOX"]

Stack: [1 "OXOXOXOXOX"]

Stack: ["OXOXOXOXOX" 1]

Stack: ["OXOXOXOXOX" 1 4]

Stack: ["OXOXOXOXOX" 1 2]

Stack: ["OXOXOXOXOX" 1 2 2]

Stack: ["OXOXOXOXOX" 1 2 2 10]

Stack: ["OXOXOXOXOX" 1 2 10 2]

Stack: ["OXOXOXOXOX" 1 2 5]

Stack: ["OXOXOXOXOX" 2]

Stack: [["OX" "OX" "OX" "OX" "OX"]]

Stack: ["OX
OX
OX
OX
OX"]

OX
OX
OX
OX
OX

```
> 6 votes

# Answer
# APL (36 - 5 - 10 = 21)

```
{'OX'⍴⍨⍺⌽⊃∆/⍨⍵=×/¨∆←∆[⍋|-/¨∆←,⍳2/⍵]}

```

The left argument is rotation, the right argument is the size. It also uses a simple pattern (it just alternates 'X' and 'O').

```
      0{'OX'⍴⍨⍺⌽⊃∆/⍨⍵=×/¨∆←∆[⍋|-/¨∆←,⍳2/⍵]}¨4 5 8 9
 OX  OXOXO  OXOX  OXO
 OX         OXOX  XOX
                  OXO
      1{'OX'⍴⍨⍺⌽⊃∆/⍨⍵=×/¨∆←∆[⍋|-/¨∆←,⍳2/⍵]}¨4 5 8 9
 OX  O  OX  OXO
 OX  X  OX  XOX
     O  OX  OXO
     X  OX
     O

```

Explanation:

* `∆←,⍳2/⍵`: generate all possible pairs of numbers from `1` to  and store in .
* `∆←∆[⍋|-/¨∆`...`]`: sort  ascending in the absolute difference of the two numbers in each pair, and store the result back in .
* `⊃∆/⍨⍵=×/¨∆`: for each pair, multiply the numbers together. Select only those pairs that multiply to , and take the first one that matches (which is the 'most square' because of the sort).
* `⍺⌽`: rotate the list of lengths (which has 2 elements) by .
* `'OX'⍴⍨`: create a matrix of that size, and fill it with alternating `O` and `X`.
> 3 votes

# Answer
# Python, 79 75 (no bonuses)

The bonuses seem tricky, so here is a pretty simple Python function:

```
def f(N):c=max(x*((x*x<=N)>N%x)for x in range(1,N+1));print(N/c*'O'+'\n')*c

```
> 2 votes

# Answer
### Haskell, 59 characters

```
r=replicate
f n=[r x$r y '0'|x<-[1..n],y<-[1..x],x*y==n]!!0

```
> 2 votes

# Answer
# JavaScript (E6) 84 (83+1) or 101 (116-10-5)

Pattern + rotation (parameter f, 0 or 1) - bonus 15

```
F=(n,f)=>{
  for(r=x=0;y=n/++x|0,x<=y;)x*y-n?0:z=f?x:y;
  for(o='';n;)o+=(n--%z?'':(r^=1,c='\n'))+'OX'[r^(c^=1)];
  alert(o)
}

```

No pattern, no rotation - penalty 1

```
F=n=>{
  for(x=0;y=n/++x|0,x<=y;)x*y-n?0:z=y;
  alert(('O'.repeat(z)+'\n').repeat(n/z));
}

```

**Test** In FireFox/FireBug console

```
F(30,0)

OXOXOX
XOXOXO
OXOXOX
XOXOXO
OXOXOX

F(30,1)

OXOXO
XOXOX
OXOXO
XOXOX
OXOXO
XOXOX

```
> 2 votes

# Answer
# CJam, ~~25~~ ~~22~~ 21 (31 - 10)

This is a function body. If you want a complete program, add `riri` to the front. If you want to use it as a code block, surround it in `{}`. Test it on cjam.aditsu.net.

It takes input as two integer arguments: the switch for whether the rectangle is vertical (any non-zero value) or horizontal (zero), and the number of `O`s to use.

```
:Xmqi){(_X\%}g_X\/@{\}{}?'O*N+*

```

## Explanation

```
:X "Assign the top item on the stack (the second input) to variable X";
mq "Take its square root";
i  "Convert to integer (round)";
)  "Increment it";

{  "Start code block";
  (  "Decrement";
  _X "Duplicate top item on stack; push X to the stack";
  \% "Swap top 2 items and take division remainder";
}g "Loop until top item on stack is 0; pop condition after checking it";

_X "Duplicate top item on stack; push X to the stack";
\/ "Swap top 2 items and divide";

"OMIT THIS BIT TO GET A 25-CHAR FUNCTION WITHOUT THE 10PT BONUS";
 @  "Rotate top 3 items on stack";
 {\}"Code block 1: swap top two items";
 {} "Code block 2: do nothing";
 ?  "If top item of stack is 0, run code block 1, otherwise run code block 2";

'O "Push the character O to the stack";
*  "Repeat it N times, where N is the second item from the top of the stack (O is first)";
N+ "Push a new line and concatenate it with the string on the top of the stack";
*  "Repeat the string N times";

```
> 2 votes

# Answer
# Ruby, 74

```
f=->n{w=(1..n).min_by{|z|n%z>0?n:(n/z-n/(n/z))**2};$><<("X"*w+"\n")*(n/w)}

```

## Explanation

* Input is taken as arguments to a lambda. It expects an `Integer`.
* Check if `n` (the input) is divisible by every integer from 1 to `n`.
    + If it is, calculate the difference between the length and width.
    + If it is not, return a large number (`n`).
* Take the smallest of length-width differences to best resemble a square.
* Use (the overly concise) `String#*` method to "draw" the square.
> 1 votes

# Answer
# APL (Dyalog Unicode), 30 - 15 = 15 bytesSBCS

Anonymous infix lambda. Takes *N* as right argument and param as left argument. Rectangles will either have stripes of X and O or be chequered.

```
{⍉⍣⍺⍴∘'XO'⊃∘c⌈.5×≢c←⍸⍵=∘.×⍨⍳⍵}

```

Try it online!

`{``}` "dfn";  is left argument (param),  is right argument (*N*):

`⍳⍵`**ɩ**ndices 1…N

`∘.×⍨` multiplication table of that

`⍵=` mask where *N* is equal to that

**ɩ**ndices of true values in the mask

`c←` store that in `c` (for **c**andidates)

tally the candidates

`.5×` one half multiplied by that

ceiling (round up)

`⊃∘c` pick that element from `c`

`⍴∘'XO'` use that to cyclically reshape "XO"

`⍉⍣⍺` transpose if param
> 1 votes

# Answer
# 05AB1E (legacy), score: 7 (22 bytes \- 15 bonus)

```
„OXI∍¹tï[D¹sÖ#<}äIiø}»

```

Try it online or verify some more test cases.

Takes the inputs `N` first, then the boolean (`0`/`1`) whether it should rotate or not.

Uses the Python legacy version of 05AB1E since zip with a string-list implicitly flattens and joins the characters, unlike the newer Elixir rewrite version of 05AB1E.

**Explanation:**

```
„OX         # Push string "OX"
   I∍       # Extend it to a size equal to the first input
            #  i.e. 9 → "OXOXOXOXO"
            #  i.e. 10 → "OXOXOXOXOX"
¹t          # Take the first input again, and square-root it
            #  i.e. 9 → 3.0
            #  i.e. 10 → 3.1622776601683795
  ï         # Then cast it to an integer, removing any decimal digits
            #  i.e. 3.0 → 3
            #  i.e. 3.1622776601683795 → 3
   [        # Start an infinite loop:
    D       #  Duplicate the integer
     ¹sÖ    #  Check if the first input is evenly divisible by that integer
            #   i.e. 9 and 3 → 1 (truthy)
            #   i.e. 10 and 3 → 0 (falsey)
        #   #  And if it is: stop the infinite loop
    <       #  If not: decrease the integer by 1
            #   i.e. 3 → 2
   }        # After the infinite loop:
ä           # Divide the string into that amount of equal sized parts
            #  i.e. "OXOXOXOXO" and 3 → ["OXO","XOX","OXO"]
            #  i.e. "OXOXOXOXOX" and 2 → ["OXOXO","XOXOX"]
 Ii }       # If the second input is truthy:
   ø        #  Zip/transpose; swapping rows/columns of the strings
            #   i.e. ["OXOXO","XOXOX"] → ["OX","XO","OX","XO","OX"]
»           # And finally join the strings in the array by newlines
            #  i.e. ["OXO","XOX","OXO"] → "OXO\nXOX\nOXO"
            #  i.e. ["OX","XO","OX","XO","OX"] → "OX\nXO\nOX\nXO\nOX"
            # (and output the result implicitly)

```
> 1 votes

# Answer
## GolfScript 26 (41 - 10 - 5)

```
:x),1>{x\%!},.,2/=.x\/@{\}*'X'*n+*1>'O'\+

```

Expects two parameters to be on the stack:

* `0` for normal or `1` for transposed
* the `n` value

The pattern is that the board is full of `X`s and the top left corner is an `O`. Needless to say, this pattern is maintained when transposing the board.

Demo: regular, transposed
> 0 votes

# Answer
# Mathematica, 71 chars

```
f@n_:=#<>"\n"&/@Array["O"&,{#,n/#}&[#[[⌊Length@#/2⌋]]&@Divisors@n]]<>""

```
> 0 votes

# Answer
# Petit Computer BASIC, 72 bytes

```
INPUT N,S$FOR I=1TO SQR(N)IF N%I<1THEN M=I
NEXT
?(S$*M+" "*(32-M))*(N/M)

```
> 0 votes

# Answer
# , 32 bytes - 15 = 17 bytes

```
'XO'$~[|.](%,])i.@]{~0 i:~i.@]|]

```

Try it online!

The rotation is controlled by a 0/1 flag taken as the left argument
> 0 votes

# Answer
# Retina 0.8.2, 66 bytes + 1 byte penalty = 67

```
.+
$*X
((^|\3)(X(?(3)\3)))+(\3)*$
$3 $3$#4$*X
X(?=X* (X+))| X+
$1¶

```

Try it online! Explanation:

```
.+
$*X

```

Convert the input to a string of `X`s.

```
((^|\3)(X(?(3)\3)))+(\3)*$

```

The first pass of the outer capture matches the start of the string while on subsequent passes the previous value of the inner capture is matched. The inner capture is then incremented and matched. The upshot of this is that the amount of string consumed by the outer capture is the square of the inner capture, which therefore cannot exceed the square root of the input. Meanwhile the subsequent repetition ensures that the inner capture is a factor of the length of the string.

```
$3 $3$#4$*X

```

Save the discovered factor and calculate the other divisor by adding on the number of subsequent repetitions.

```
X(?=X* (X+))| X+
$1¶

```

Rearrange the factors into a rectangle.
> 0 votes

# Answer
# Charcoal, 33 bytes - 10 - 5 = 18

```
Ｎθ≔⌊Φ⊕θ¬∨‹×ιιθ﹪θιηＥ÷θη⭆η§XO⁺ιλ¿Ｎ⟲

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input `N`.

```
≔⌊Φ⊕θ¬∨‹×ιιθ﹪θιη

```

Take the range `0`..`N`, keep only the numbers whose squares are not less than `N` and divide `N`, and take the minimum of those numbers.

```
Ｅ÷θη⭆η§XO⁺ιλ

```

Use the discovered factor to output a rectangle of the appropriate width and height using a chequerboard pattern. (This should be `ＵＯη÷θηXO¶OX` for a 1-byte saving but that's buggy right now.)

```
¿Ｎ⟲

```

If the second input is nonzero then rotate the output. (If requiring the second input to be `0` or `2` is acceptable, then this could be `⟲Ｎ` for a 1-byte saving.)
> 0 votes

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


title: The Path Of The Wildebeest

text:
# Question
Title: The Path Of The Wildebeest
Golf a program or function which gives the \\$n^{\text{th}}\\$ location of the wildebeest who starts at square \\$1\\$ on an infinite chessboard which is numbered in an anti-clockwise square spiral, where the wildebeest always visits the lowest numbered square she can reach that she has not yet visited.

Inspiration: The Trapped Knight and OEIS A316667.

Edit: This sequence is now on the OEIS as A323763.

The code may produce the \\$n^{\text{th}}\\$ location, the first \\$n\\$ locations, or generate the sequence taking no input.

Feel free to give her location after (or up to) \\$n\\$ leaps instead, but if so please state this clearly in your answer and make sure that an input of \\$n=0\\$ yields `1` (or `[1]` if appropriate).

This is , so the aim is to produce working code in as few bytes as possible in your chosen language.

Note: the wildebeest becomes trapped (much like the knight does at his \\$2016^{\text{th}}\\$ location, square \\$2084\\$, and the camel does at his \\$3723^{\text{rd}}\\$, square \\$7081\\$) at her \\$12899744968^{\text{th}}\\$ location on square \\$12851850258\\$. The behaviour of your code may be undefined for \\$n\\$ larger than this. (Thanks to Deadcode for the C++ code that found this!)

### Detail

The board looks like the below, and continues indefinitely:

```
101 100  99  98  97  96  95  94  93  92  91
102  65  64  63  62  61  60  59  58  57  90
103  66  37  36  35  34  33  32  31  56  89
104  67  38  17  16  15  14  13  30  55  88
105  68  39  18   5   4   3  12  29  54  87
106  69  40  19   6   1   2  11  28  53  86
107  70  41  20   7   8   9  10  27  52  85
108  71  42  21  22  23  24  25  26  51  84
109  72  43  44  45  46  47  48  49  50  83
110  73  74  75  76  77  78  79  80  81  82
111 112 113 114 115 116 117 118 119 120 121

```

A wildebeest is a "gnu" fairy chess piece \- a non-standard chess piece which may move both as a knight (a \\$(1,2)\\$-leaper) and as a camel (a \\$(1,3)\\$-leaper).
As such she could move to any of these locations from her starting location of \\$1\\$:

```
  .   .   .   .   .   .   .   .   .   .   .
  .   .   .   .  35   .  33   .   .   .   .
  .   .   .   .  16   .  14   .   .   .   .
  .   .  39  18   .   .   .  12  29   .   .
  .   .   .   .   .  (1)  .   .   .   .   .
  .   .  41  20   .   .   .  10  27   .   .
  .   .   .   .  22   .  24   .   .   .   .
  .   .   .   .  45   .  47   .   .   .   .
  .   .   .   .   .   .   .   .   .   .   .

```

The lowest of these is \\$10\\$ and she has not yet visited that square, so \\$10\\$ is the second term in the sequence.

Next she could move from \\$10\\$ to any of these locations:

```
  .   .   .   .   .   .   .   .   .   .   .
  .   .   .   .   .   .  14   .  30   .   .
  .   .   .   .   .   .   3   .  29   .   .
  .   .   .   .   6   1   .   .   .  53  86
  .   .   .   .   .   .   . (10)  .   .   .
  .   .   .   .  22  23   .   .   .  51  84
  .   .   .   .   .   .  47   .  49   .   .
  .   .   .   .   .   .  78   .  80   .   .
  .   .   .   .   .   .   .   .   .   .   .

```

However, she has already visited square \\$1\\$ so her third location is square \\$3\\$, the lowest she has not yet visited.

---

The first \\$100\\$ terms of the path of the wildebeest are:

```
1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 18, 15, 12, 16, 19, 22, 41, 17, 33, 30, 34, 13, 27, 23, 20, 24, 44, 40, 21, 39, 36, 60, 31, 53, 26, 46, 25, 28, 32, 29, 51, 47, 75, 42, 45, 71, 74, 70, 38, 35, 59, 56, 86, 50, 78, 49, 52, 80, 83, 79, 115, 73, 107, 67, 64, 68, 37, 61, 93, 55, 58, 54, 84, 48, 76, 43, 69, 103, 63, 66, 62, 94, 57, 87, 125, 82, 118, 77, 113, 72, 106, 148, 65, 97, 137, 91, 129, 85

```

The first \\$11\\$ leaps are knight moves so the first \\$12\\$ terms coincide with A316667.

# Answer
# JavaScript (Node.js),  ~~191 ... 166~~  164 bytes

*Saved 2 bytes thanks to @grimy.*

Returns the \\$N\\$th term.

```
n=>(g=(x,y)=>n--?g(Buffer('QPNP1O?O@242Q3C3').map(m=c=>g[i=4*((x+=c%6-2)*x>(y+=c%7-2)*y?x:y)**2,i-=(x>y||-1)*(i**.5+x+y)]|i>m||(H=x,V=y,m=i))&&H,V,g[m]=1):m+1)(1,2)

```

Try it online! or See a formatted version

## How?

### Spiral indices

In order to convert the coordinates \\$(x,y)\\$ into the spiral index \\$I\\$, we first compute the layer \\$L\\$ with:

$$L=\max(|x|,|y|)$$

Which gives:

$$\begin{array}{c|ccccccc} &-3&-2&-1&0&+1&+2&+3\\ \hline -3&3&3&3&3&3&3&3\\ -2&3&2&2&2&2&2&3\\ -1&3&2&1&1&1&2&3\\ 0&3&2&1&0&1&2&3\\ +1&3&2&1&1&1&2&3\\ +2&3&2&2&2&2&2&3\\ +3&3&3&3&3&3&3&3 \end{array}$$

We then compute the position \\$P\\$ in the layer with:

$$P=\begin{cases} 2L+x+y&\text{if }x\>y\\ -(2L+x+y)&\text{if }x\le y \end{cases}$$

Which gives:

$$\begin{array}{c|ccccccc} &-3&-2&-1&0&+1&+2&+3\\ \hline -3&0&1&2&3&4&5&6\\ -2&-1&0&1&2&3&4&7\\ -1&-2&-1&0&1&2&5&8\\ 0&-3&-2&-1&0&3&6&9\\ +1&-4&-3&-2&-3&-4&7&10\\ +2&-5&-4&-5&-6&-7&-8&11\\ +3&-6&-7&-8&-9&-10&-11&-12 \end{array}$$

The final index \\$I\\$ is given by:

$$I=4L^2-P$$

NB: The above formula gives a 0-indexed spiral.

In the JS code, we actually compute \\$4L^2\\$ right away with:

```
i = 4 * (x * x > y * y ? x : y) ** 2

```

And then subtract \\$P\\$ with:

```
i -= (x > y || -1) * (i ** 0.5 + x + y)

```

### Moves of the wildebeest

Given the current position \\$(x,y)\\$, the 16 possible target squares of the wildebeest are tested in the following order:

$$\begin{array}{c|cccccccc} &-3&-2&-1&x&+1&+2&+3\\ \hline -3&\cdot&\cdot&9&\cdot&11&\cdot&\cdot\\ -2&\cdot&\cdot&8&\cdot&10&\cdot&\cdot\\ -1&7&6&\cdot&\cdot&\cdot&12&13\\ y&\cdot&\cdot&\cdot&\bullet&\cdot&\cdot&\cdot\\ +1&5&4&\cdot&\cdot&\cdot&14&15\\ +2&\cdot&\cdot&2&\cdot&0&\cdot&\cdot\\ +3&\cdot&\cdot&3&\cdot&1&\cdot&\cdot \end{array}$$

We walk through them by applying 16 pairs of signed values \\$(dx,dy)\\$. Each pair is encoded as a single ASCII character.

```
 ID | char. | ASCII code | c%6-2 | c%7-2 | cumulated
----+-------+------------+-------+-------+-----------
  0 |  'Q'  |     81     |   +1  |   +2  |  (+1,+2)
  1 |  'P'  |     80     |    0  |   +1  |  (+1,+3)
  2 |  'N'  |     78     |   -2  |   -1  |  (-1,+2)
  3 |  'P'  |     80     |    0  |   +1  |  (-1,+3)
  4 |  '1'  |     49     |   -1  |   -2  |  (-2,+1)
  5 |  'O'  |     79     |   -1  |    0  |  (-3,+1)
  6 |  '?'  |     63     |   +1  |   -2  |  (-2,-1)
  7 |  'O'  |     79     |   -1  |    0  |  (-3,-1)
  8 |  '@'  |     64     |   +2  |   -1  |  (-1,-2)
  9 |  '2'  |     50     |    0  |   -1  |  (-1,-3)
 10 |  '4'  |     52     |   +2  |   +1  |  (+1,-2)
 11 |  '2'  |     50     |    0  |   -1  |  (+1,-3)
 12 |  'Q'  |     81     |   +1  |   +2  |  (+2,-1)
 13 |  '3'  |     51     |   +1  |    0  |  (+3,-1)
 14 |  'C'  |     67     |   -1  |   +2  |  (+2,+1)
 15 |  '3'  |     51     |   +1  |    0  |  (+3,+1)

```

We keep track of the minimum encountered value in \\$m\\$ and of the coordinates of the corresponding cell in \\$(H,V)\\$.

Once the best candidate has been found, we mark it as visited by setting a flag in the object \\$g\\$, which is also our main recursive function.

On the first iteration, we start with \\$x=1\\$ and \\$y=2\\$. This ensures that the first selected cell is \\$(0,0)\\$ and that it's the first cell to be marked as visited.
> 22 votes

# Answer
# Coconut, ~~337~~ 276 bytes

```
import math
def g((x,y))=
 A=abs(abs(x)-abs(y))+abs(x)+abs(y)
 int(A**2+math.copysign(A+x-y,.5-x-y)+1)
def f():
 p=x,y=0,0;s={p};z=[2,3,1,1]*2
 while 1:yield g(p);p=x,y=min(((a+x,b+y)for a,b in zip((1,1,2,-2,-1,-1,3,-3)*2,z+[-v for v in z])if(a+x,b+y)not in s),key=g);s.add(p)

```

Returns a generator of values. Could probably be golfed more. (Especially the sequence of difference tuples.) Spiral algorithm taken from this math.se answer.

Try it online!
> 8 votes

# Answer
# 05AB1E, ~~77~~ ~~65~~ ~~58~~ ~~57~~ 52 bytes

```
Xˆ0UF3D(Ÿ0KãʒÄ1¢}εX+}Dε·nàDtyÆ+yO·<.±*->}D¯KßDˆkèU}¯

```

-6 bytes thanks to *@Arnauld* by using a port of his formula.

Outputs the first \\$n+1\\$ values as a list (of decimals).

Try it online (the `ï` in the footer removes the `.0` to make the output more compact, but feel free to remove it to see the actual result).

**Code explanation:**

```
Xˆ             # Put integer 1 in the global_array (global_array is empty by default)
0U             # Set variable `X` to 0 (`X` is 1 by default)
F              # Loop the (implicit) input amount of times:
 3D(Ÿ          #  Push the list in the range [-3,3]: [-3,-2,-1,0,1,2,3]
     0K        #  Remove the 0: [-3,-2,-1,1,2,3]
       ã       #  Cartesian product with itself, creating each possible pair: [[3,3],[3,2],[3,1],[3,-1],[3,-2],[3,-3],[2,3],[2,2],[2,1],[2,-1],[2,-2],[2,-3],[1,3],[1,2],[1,1],[1,-1],[1,-2],[1,-3],[-1,3],[-1,2],[-1,1],[-1,-1],[-1,-2],[-1,-3],[-2,3],[-2,2],[-2,1],[-2,-1],[-2,-2],[-2,-3],[-3,3],[-3,2],[-3,1],[-3,-1],[-3,-2],[-3,-3]]
        ʒ   }  #  Filter this list of pairs by:
         Ä     #   Where the absolute values of the pair
          1¢   #   Contains exactly one 1
               #  (We now have the following pairs left: [[3,1],[3,-1],[2,1],[2,-1],[1,3],[1,2],[1,-2],[1,-3],[-1,3],[-1,2],[-1,-2],[-1,-3],[-2,1],[-2,-1],[-3,1],[-3,-1]])
 εX+}          #  Add the variable `X` (previous coordinate) to each item in the list
 D             #  Duplicate this list of coordinates
  ε            #  Map each `x,y`-coordinate to:
   ·           #   Double both the `x` and `y` in the coordinate
    n          #   Then take the square of each
     à         #   And then pop and push the maximum of the two
   Dt          #   Duplicate this maximum, and take its square-root
     yÆ        #   Calculate `x-y`
       +       #   And add it to the square-root
   yO          #   Calculate `x+y`
     ·         #   Double it
      <        #   Decrease it by 1
       .±      #   And pop and push its signum (-1 if < 0; 0 if 0; 1 if > 0)
   *           #   Multiply these two together
    -          #   And subtract it from the duplicated maximum
   >           #   And finally increase it by 1 to make it 1-based instead of 0-based
  }D           #  After the map: Duplicate that list with values
    ¯K         #  Remove all values that are already present in the global_array
      ß        #  Pop the list of (remaining) values and push the minimum
       Dˆ      #  Duplicate this minimum, and pop and add the copy to the global_array
         k     #  Then get its index in the complete list of values
          è    #  And use that index to get the corresponding coordinate
           U   #  Pop and store this coordinate in variable `X` for the next iteration
}¯             # After the outer loop: push the global_array (which is output implicitly)

```

**General explanation:**

We hold all results (and therefore values we've already encountered) in the `global_array`, which is initially started as `[1]`.
We hold the current \\$x,y\\$-coordinate in variable `X`, which is initially `[0,0]`.

The list of coordinates we can reach based on the current \\$x,y\\$-coordinate are:

```
[[x+3,y+1], [x+3,y-1], [x+2,y+1], [x+2,y-1], [x+1,y+3], [x+1,y+2], [x+1,y-2], [x+1,y-3], [x-1,y+3], [x-1,y+2], [x-1,y-2], [x-1,y-3], [x-2,y+1], [x-2,y-1], [x-3,y+1], [x-3,y-1]]

```

The list I mention in the code explanation above holds these values we can jump to, after which the current \\$x,y\\$ (stored in variable `X`) is added.

Then it will calculate the spiral values based on these \\$x,y\\$-coordinates. It does this by using the following formula for a given \\$x,y\\$-coordinate:

$${T = max((2 * x) ^ 2, (2 * y) ^ 2)}$$ $${R = T - (x - y + √T) * signum((x + y) * 2 - 1) + 1}$$

Which is the same formula *@Arnauld* is using in his answer, but written differently to make use of 05AB1E's builtins for double, square, -1, +1, etc.

(If you want to see just this spiral part of the code in action: Try it online.)

After we've got all the values we can reach for the given \\$x,y\\$-coordinate, we remove all values that are already present in the `global_array`, and we then get the minimum of the (remaining) values.
This minimum is then added to the `global_array`, and variable `X` is replaced with the \\$x,y\\$-coordinate of this minimum.

After we've looped the `input` amount of times, the program will output this `global_array` as result.
> 8 votes

---
Tags: code-golf, sequence, integer, chess
---


title: Golf the pseudoprimes!

text:
# Question
Title: Golf the pseudoprimes!
## Introduction / Background

In a recent discussion in the crypto chat I was challenged to discuss / help with the Fermat primality test and Carmichael numbers. This test is based on the premise that `a^(p-1) mod p==1` will always hold for primes `p`, but not always for composites. Now a carmichael number is essentially the Fermat's test worst enemy: A number for which you *have to* pick `a` to be not co-prime with `p` to get `a^(p-1) mod p!=1`. Now if `a` is not co-prime, you essentially found a non-trivial factor of `p` and as we all know factoring can be quite hard. Especially if all factors are sufficiently large. You may now realize why the Fermat test isn't used in practice as often (well there are better algorithms), it's because there are numbers for which you as a defender (in security terms) would have to do a similar amount of work as an attacker (namely factor the number).

So now that we know *why* these numbers are somewhat fascinating, we're gonna generate them in the shortest way possible, so we can just memorize the generating code if we ever need any!

Carmichael numbers are also known as A002997 on OEIS.
There is a related challenge already, but entries from there are not competitive here because they are optimized for speed as opposed to size. The same argument holds for the inverse direction, entries here are likely to make trade-offs against speed in favor of size.

## Specification

### Input

This is a standard challenge, so you take a positive or non-negative integer `n` as input. `n` may be 0- or 1-indexed as you prefer (please indicate).

### Output

Your output will either be the `n`-th carmichael number or the first `n` carmichael numbers, as you prefer (please indicate).

### Specification

An integer `x` is a Carmichael number if and only if `x` is composite and for all integers `y` with `gcd(x,y)=1`, it holds that `y^(x-1) mod x==1`.

### Who wins?

This is , so the shortest code in byte wins!
Standard IO and loophole rules apply.

### Test Cases

The first few carmichael numbers are:

```
 561,1105,1729,2465,2821,6601,8911,10585,15841,
 29341,41041,46657,52633,62745,63973,75361,101101,
 115921,126217,162401,172081,188461,252601,278545,
 294409,314821,334153,340561,399001,410041,449065,
 488881,512461

```

# Answer
> 8 votes
# Mathematica, 71 bytes

```
(t=s=1;While[t<=#,If[++s~Mod~CarmichaelLambda@s==1&&!PrimeQ@s,t++]];s)&

```

Try it online!

`50->1461241` Try it online!

# Answer
> 6 votes
# Python 2, 92 bytes

```
f=lambda j,n=1:j and f(j-([(k/n)**~-n%n for k in range(n*n)if k/n*k%n==1]<[1]*~-n),n+1)or~-n

```

Try it online!

1-indexed and slow as molasses.

In the list comprehension, I use Dennis’s method for generating all integers coprime to `n` (n’s *totatives*), and then I compute `x**~-n%n` for all of them. Let’s call this list `L`.

To detect a Carmichael number, I compare this list *lexicographically* to a list consisting of `n-1` ones. Why does this work?

Each element of `L` is a positive integer: `(k/n)` is coprime to `n`, so `(k/n)**~-n` also is, so `(k/n)**~-n%n > 0`. Thus, the only possible values of `L` that are lexicographically *less than* `[1]*(n-1)` are the ones consisting entirely of *less than* `n-1` ones. (`L` can’t contain *more* than `n-1` values, as `n` can’t have more than `n-1` totatives! So comparisons like `[1,1,1,1,3] < [1,1,1,1]` are out.)

Checking that there are less than `n-1` entries in `L` ensures that `n` is composite. (Having `n-1` totatives is an equivalent condition to primality.) And then, the condition for being a Carmichael number is exactly that every element of `L` equals `1`. So this lexicographic comparison detects exactly the `L`s we’re interested in.

Mr. Xcoder saved a byte by switching to recursive lambda form: `j` counts down every time we hit a Carmichael number, and `n` counts up every time we recurse. So once `j` hits zero, `n-1` equals the `original_value_of_j`’th Carmichael number.

# Answer
> 6 votes
# Jelly,  ~~12~~  11 bytes

-1 byte thanks to miles & Mr. Xcoder (use of Carmichael function atom & a golf thereof)

```
%Æc’=ÆP
⁹Ç#

```

A monadic link taking `n` and returning a list of the first `n` Carmichael numbers.

**Try it online!**

### How?

Much like the previous (below) except that there is a built-in for the Carmichael function - which yields the smallest power such that the input raised to that power is congruent to one modulo that power for all integers co-prime to that integer. Thus we may exclude the false-positives (primes) in less bytes and have faster code!

```
%Æc’⁼ÆP - isCarmichael: number, n (any integer)
 Æc     - Carmicael function of n
%       - n modulo that
   ’    - decremented (0 for Carmichael numbers and primes)
     ÆP - is n prime? (1 for primes 0 otherwise)
    ⁼   - equal?

⁹Ç# - Main link: number, n
  # - count up finding the first n values satisfying:
 Ç  - ...condition: call the last link as a monad
⁹   - ...starting with a value of: literal 256

```

---

Previous **12 bytes**:

```
Ṗ*%⁼Ṗ_ÆP
⁹Ç#

```

Try it online! (Yeah, it times out for `n=3`).

### How?

A number, `c`, is a Carmichael number if it is composite and it is true that any integer, `x`, raised to `c` is congruent to `x` modulo `c`.

We only need to check this for positive `x` up to `x=c` itself.

Note also that at `x=c` the check is whether `x` raised to the power of `x` is congruent to `x` modulo `x`, which is true - so we don't need to check this (this makes for shorter code).

```
Ṗ*%⁼Ṗ_ÆP - Link 1, isCarmichaelNumber: integer c (greater than 1)
Ṗ        - pop c (uses the implicit range(c)) = [1, 2, 3, ..., c-1]
 *       - raise to the power of c (vectorises) = [1^c, 2^c, 3^c, ..., (c-1)^c]
  %      - modulo by c (vectorises) = [1^c%c, 2^c%c, 3^c%c, ..., (c-1)^c%c]
    Ṗ    - pop c = [1, 2, 3, ..., c-1]
   ⁼     - equal? (non-vectorising) = 1 if so, 0 if not
      ÆP - isPrime?(c) = 1 if so, 0 if not
     _   - subtract = 1 if Carmichael 0 if not
         -     (Note the caveat that c must be an integer greater than 1, this is because
         -      popping 1 yields [] thus the equality check will hold; same for 0,-1,...)

⁹Ç# - Main link: number, n
  # - count up finding the first n values satisfying:
 Ç  - ...condition: call the last link as a monad
⁹   - ...starting with a value of: literal 256

```

# Answer
> 3 votes
# RegexMathEngine (ECMAScript+`(?^=)`), 59 bytes

```
^((?=(x(x+?))\2*$)(?^=x\3*$)(?=(x+)(\4+$))\5(?!\2*$)){2,}x$

```

Try it on replit.com! \- harness (RegexMathEngine)

A regex takes a number as input in unary, as a string of `x` characters whose length represents the number. Its output is a match iff the number is a Carmichael number.

This is launched in RegexMathEngine's sequence mode to satisfy the challenge's specifications, outputting the first `n` Carmichael numbers, where `n` can be given either as a command-line argument or through standard input.

Korselt's criterion is used to identify Carmichael numbers.

```
^                      # tail = N = input number
# Assert that N has at least 2 unique prime factors, and that each of its prime
# factors P are of exactly single multiplicity (i.e. that N is square-free), and
# for each, P-1 divides N-1.
(
    (?=(x(x+?))\2*$)   # \2 = smallest prime factor of tail; \3 = \2-1
    (?^=x\3*$)         # Lookinto – Assert \3 divides N-1
    (?=(x+)(\4+$))     # \4 = tail / \2 (implicitly); \5 = tool to make tail = \4
    \5                 # tail = \4
    (?!\2*$)           # Assert that tail is no longer divisible by \2, i.e. that
                       # that prime factor was of exactly single multiplicity.
){2,}                  # Iterate the above at least 2 times, with no maximum
x$                     # Assert tail == 1

```

# Regex (ECMAScript 2018 or better), 59 bytes

```
^((?=(x(x+?))\2*$)(?=(x+)(\4+$)(?<=^\3*x))\5(?!\2*$)){2,}x$

```

A port of the lookinto version, to variable-length lookbehind.

harnesses:
Try it online! \- ECMAScript 2018
Try it online! \- Python (`import regex`)
Try it online! \- .NET

# Regex (ECMAScript 2018 or better / Java), 66 bytes

```
^((?=(x(x+?))\2*$)(?<=(?=x\3*$)^.*)(?=(x+)(\4+$))\5(?!\2*$)){2,}x$

```

Java's lookbehind is restricted, but is able to do a simple return to start as is done here.

harnesses:
Try it online! \- ECMAScript 2018
**Try it online! \- Java**
Try it online! \- Python (`import regex`)
Try it online! \- .NET

# Regex (ECMAScript), ~~86~~ ~~89~~ 85 bytes

*-4 bytes by changing `(?=A)(?!B)` to `(?!B)A`; on some regex engines this results in a slowdown, but RegexMathEngine optimizes this so there is no difference in speed*

`^(?!(x(x+))(?!\2*$)\1*(?!(xx+)\3+$)\1$)((?=(xx+?)\5*$)(?=(x+)(\6+$))\7(?!\5*$)){2,}x$`

Try it on replit.com! \- harness (RegexMathEngine, ECMAScript mode)

harnesses (ECMAScript):
Try it online! (slow 85 byte version)
Try it online! (faster 89 byte version)

```
^                      # tail = N = input number
(?!                    # Negative lookahead – assert that neither of the
                       # following two alternatives can match:
    # Cycle through factors \1, with \2 = \1-1, for which \2 does not divide N-1
    (x(x+))            # \1 = conjectured factor of N; \2 = \1-1
    (?!\2*$)           # Assert N-1 is not divisible by \2
    \1*                # Assert N is divisible by \1 - works along with the
                       # subsequent "\1$"; tail = \1
    # If the factor \1, which already passed the above tests, is prime, then
    # fail the outside negative lookahead, because N is not a Carmichael number.
    (?!(xx+)\3+$)
    \1$
)
# Assert that N has at least 2 unique prime factors, and that all of its prime
# factors are of exactly single multiplicity (i.e. that N is square-free).
(
    (?=(xx+?)\5*$)     # \5 = smallest prime factor of tail
    (?=(x+)(\6+$))     # \6 = tail / \5 (implicitly); \7 = tool to make tail = \6
    \7                 # tail = \6
    (?!\5*$)           # Assert that tail is no longer divisible by \5, i.e. that
                       # that prime factor was of exactly single multiplicity.
){2,}
x$

```

The main magic of this regex is in the part that asserts that all of the prime factors of N are of exactly single multiplicity. It is the same trick as used by my Match strings whose length is a fourth power and Find the Smoothest Number regexes: repeated implicit division by the smallest prime factor.

# Regex (ECMAScript), ~~97~~ ~~93~~ ~~92~~ 90 bytes

*-4 bytes by changing* `(?=A)(?!B)` *to* `(?!B)A`; *on some regex engines this results in a slowdown*
*-1 byte by using* `\b` *to streamline searching through all divisors of N*
*-2 bytes by excluding 1 as a divisor in the square test rather than the divisor search*

`^(?!(x(x+))(?!\2*$)\1*(?!(xx+)\3+$)\1$|(x*)\4*(?=\4\b)(x(x+))(?=(\5*)\6+$)\5*$\7)(xx+)\8+$`

It's also possible to directly test that N has no perfect-square factors (i.e., that N is square-free). This uses a variant of the multiplication algorithm explained in this post, adapted to asserting that \\$A^2=C\\$.

Using that algorithm on this problem does not provide any benefit, however. It results in a slower regex, with a larger size. Without the prime multiplicity test (which in one loop asserts both that there are at least 2 prime factors and that they are each of single multiplicity), we have to separately assert that N is composite.

Try it on replit.com! \- harness (RegexMathEngine, ECMAScript mode)

harnesses (ECMAScript):
Try it online! (Slow 90 byte version)
Try it online! (Faster 94 byte version)

```
^                      # tail = N = input number
(?!                    # Negative lookahead – assert that neither of the
                       # following two alternatives can match:
    # Cycle through factors \1, with \2 = \1-1, for which \2 does not divide N-1
    (x(x+))            # \1 = conjectured factor of N; \2 = \1-1
    (?!\2*$)           # Assert N-1 is not divisible by \2
    \1*                # Assert N is divisible by \1 - works along with the
                       # subsequent "\1$"; tail = \1
    # If the factor \1, which already passed the above tests, is prime, then
    # fail the outside negative lookahead, because N is not a Carmichael number.
    (?!(xx+)\3+$)
    \1$
|
    # Assert that N isn't square-free, i.e. has at least one divisor >1 that is
    # a perfect square (outside the negative lookahead, assert the opposite).
    (x*)\4*(?=\4\b)    # cycle tail through all divisors of N, including N itself

    # Match iff tail is a perfect square
    (x(x+))            # \5 = potential square root >= 2; \6 = \5 - 1
    (?=
        (\5*)\6+$      # iff \5 * \5 == our number, then the first match here must result in \7 == 0
    )
    \5*$\7             # test for divisibility by \5 and for \7 == 0 simultaneously
)
(xx+)\8+$              # Assert that N is composite

```

# Answer
> 2 votes
# , ~~72~~ ~~59~~ 51 bytes

```
1{(((0>.-)0&p:*~:@q:-:0=q:|&<:])([,(+*)~)])/^:_@,&2

```

Try it online!

# Answer
> 1 votes
# Retina, ~~94~~ ~~90~~ 81 bytes

```
\d*$
x
"$+"}/^((?=(x(x+?))\2*$)(?=(x+)(\4+$)(?<=^\3*x))\5(?!\2*$)){2,}x$/^+`$
x
x

```

Try it online! 1-indexed. Edit: Saved ~~4~~ 13 bytes by porting @Deadcode's latest Carmichael test, which is also slightly less slow, but still times out for `n>6` on TIO. crossed out 4 is still regular 4 Explanation:

```
\d*$
x

```

Increment the current value. On the first pass, this also deletes `n` from the output buffer (but `$+` can still access it).

```
/^((?=(x(x+?))\2*$)(?=(x+)(\4+$)(?<=^\3*x))\5(?!\2*$)){2,}x$/

```

Test whether the current value is a Carmichael number. This uses @Deadcode's latest regex.

```
^+`

```

Repeat until the current value is a Carmichael number.

```
$
x

```

Increment the current value.

```
"$+"}

```

Repeat the initial increment and above loop `n` times.

```
x

```

Convert the result to decimal.

# Answer
> 1 votes
# Haskell, 95 bytes

```
s=filter
c n=s(\x->let l=s((1==).gcd x)f;f=[1..x-1]in l/=f&&all(\y->y^(x-1)`mod`x==1)l)[1..]!!n

```

Try it online!

Degolfed:

```
-- function to filter out Carmichael numbers
filterFunction x =
    let coprimes = filter ((1 ==) . gcd x) lesserNumbers
        lesserNumbers = [1 .. x - 1]
    in
        -- the number x is Carmichael if it is not prime
        lesserNumbers /= coprimes &&
            -- and all of its coprimes satisfy the equation
            all (\y -> y ^ (x - 1) `mod` x == 1) coprimes

-- get n'th Carmichael number (zero-based)
c n = filter filterFunction [1..] !! n

```

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


title: Determine dice value from side view

text:
# Question
Title: Determine dice value from side view
Write program or function which will take left and right value of dice as integers (1-6) and return value on top.

Dice layout:

```
    +---+
    | 1 |
+---+---+---+---+
| 2 | 3 | 5 | 4 |
+---+---+---+---+
    | 6 |
    +---+

  ,^.
<´ 5 `>  <-- Top value
|`._,´|
.6 | 4,  <-- Side values
 `.|,´

```

So inputting `6 4` will return `5`.

Order is important:

```
2 3 -> 1
3 2 -> 6

```

Program doesn't have to work with invalid input values.

To discourage obvious approach (using table with all combinations), using any builtin text encoding or de/compression routines or base encoding or anything else similar to reduce size is not allowed. Note that using table is still allowed and rolling your own decompression is allowed too, as long as it's not done using some ready library function.

For reference purposes, here's a table of all combinations (i.e. all possible inputs and outputs):

```
23, 35, 42, 54 -> 1
14, 31, 46, 63 -> 2
12, 26, 51, 65 -> 3
15, 21, 56, 62 -> 4
13, 36, 41, 64 -> 5
24, 32, 45, 53 -> 6

```

Shortest code wins, and standard loopholes apply.

# Answer
> 59 votes
# Python, 30

```
lambda a,b:a^b^7*(2<a*a*b%7<5)

```

No lookups, just bit bashing.

The opposite faces come in pairs that are three-bit complements of each other, meaning that they XOR to 7.

```
1,6
2,5
3,4

```

Given two faces from one set, we want to get a face from the other set. For `(1,2,3)`, we can do this with XOR (`^`). So, `^` gives the right answer up to three-bit complement, meaning `x^7`. We can conditionally complement by `x^7*_`.

To decide whether or not to take the complement (XOR with 7), we check whether the triplet violates the right-hand rule. That means, that `a,b` goes in the reverse cyclic order of

```
1,6
2,5
3,4

```

treating each line as one of the three categories. Since the elements in each line are negatives mod 7, we can "hash" them by doing `x*x%7`.

```
1,6 -> 1
2,5 -> 4
3,4 -> 2

```

Each line is obtained from the cyclically previous by multiplying by 4 modulo 7, so we can check whether this relationship holds for `(b,a)` to decide whether to complement: `a*a%7==b*b*4%7`.

This is equivalent to checking whether, modulo 7, `a**2 * b**(-2)` equals `4`. Since `b**6` equals `1` modulo 6, this is equivalent to `a**2 * b**4`. Since the other possible value is 2 (by checking cases), we can check if it's 4 by comparing to 3.

# Answer
> 65 votes
There's a nice polynomial expression modulo 7 for the third side given two sides *a* and *b*.

$${3(a^3b - ab^3) \mod 7}$$

or factored

$${3ab(a^2-b^2) \mod 7}$$

The modulo 7 maps to a remainder in {0,1,2,3,4,5,6}.

I explain why it works in this Math SE answer, though I do think there probably is a cleaner argument I'm missing. The only other two-term polynomial that works is

$${(3a^5b^5 - a^3b) \mod 7}$$

which I originally found by transforming my bit-bashing into arithmetic operations, then did a brute-force search over polynomials of this form to find the nicer one.

Please feel free to add ports of this into your favorite language; this is a CW post.

**J, 9 by Synthetica**

```
7|3***+*-

```

See my post

**Dyalog APL, 9 by ngn** (typo fixed by Adám)

```
7|3×××+×-

```

Blatantly stolen from above J answer.

**TI-Basic, 14 by Timtech**

```
7fPart((A³B-AB³)/21

```

**Pyth, 16 by FryAmTheEggman**

```
M%*3-*H^G3*^H3G7

```

Defines a function `g` of two values.

**Golfscript, 18 by Peter Taylor** (old polynomial)

```
~1$*.5?3*@.*@*- 7%

```

**CJam, 18 by Martin Büttner** (ported from Peter's GolfScript) (old polynomial)

```
l~1$*_5#3*@_*@*m7%

```

**Mathematica, 20 by Martin Büttner**

```
Mod[+##(#-#2)3##,7]&

```

Yes, that's a unary plus, and no, there's no shorter way that doesn't use a unary plus.

**dc, 21 by Toby Speight**

```
sb7+d3^lb*rlb3^*-3*7%

```

I have to add 7 to `a` to ensure the difference is always positive (dc has a signed `%` operator).

**Julia, ~~24~~ ~~23~~ 21 by Martin Büttner, fixed by MarcMush**

```
a\b=(3a^5*b^4-a^3)b%7

```

Try it online!

**CoffeeScript, ~~28~~ 26 by rink.attendant.6**

```
x=(a,b)->3*a*b*(a*a-b*b)%7

```

**JavaScript (ES6), ~~28~~ 26 by rink.attendant.6**

```
x=(a,b)=>3*a*b*(a*a-b*b)%7

```

Essentially the same as CoffeeScript.

**Python 28, by xnor**

```
lambda a,b:3*a*b*(a*a-b*b)%7

```

**Bash, 31**

Nothing special:

```
echo $[3*($1**3*$2-$1*$2**3)%7]

```

or alternatively:

```
echo $[3*$1*$2*($1*$1-$2*$2)%7]

```

Another (longer but perhaps interesting) approach.

**Nim, 36 by Sillesta**

```
proc(x,y:int):int=3*x*y*(x*x-y*y)%%7

```

**Java 7, ~~46~~ 44 by rink.attendant.6**

```
int f(int a,int b){return(a*a-b*b)*a*b*3%7;}

```

**Java 8, ~~25~~ 23 by Kevin Cruijssen**

```
a->b->(a*a-b*b)*a*b*3%7

```

**PHP, ~~49~~ 47 by rink.attendant.6**

```
function x($a,$b){echo($a*$a-$b*$b)*3*$a*$b%7;}

```

**Batch, 52 unclemeat**

```
set/aa=(3*(%1*%1*%1*%2-%1*%2*%2*%2)%%7+7)%%7
echo %a%

```

CMD does not support true modulus natively (so can't handle negative numbers) - hence `%%7+7)%%7`.

**LESS (as a parametric mixin), ~~62~~ 60 by rink.attendant.6**

```
.x(@a,@b){@r:mod(3*@a*@b*(@a*@a-@b*@b),7);content:~"'@{r}'"}

```

See my post below.

**05AB1E, ~~10~~ 8 by Emigna (-2 bytes by Kevin Cruijssen)**

```
nÆs`3P7%

```

Try it online.

**Haskell, <sub>~~31~~ ~~27~~</sub> 25 by Generic Display Name**

```
a#b=3*a*b*(a*a-b*b)`mod`7

```

Try it online!

**Excel, 27 by by Wernisch**

```
=MOD(3*(A1^3*B1-A1*B1^3),7)

```

**Excel VBA, 25 by Taylor Raine**

```
?3*[A1^3*B1-A1*B1^3]Mod 7

```

**Forth (gforth) 41 by reffu**

```
: f 2>r 2r@ * 2r@ + 2r> - 3 * * * 7 mod ;

```

Try it online!

**C#, 23 by Kevin Cruijssen**

```
a=>b=>(a*a-b*b)*a*b*3%7

```

**Jelly, 9 by caird coinheringaahing**

```
_×+×××3%7

```

Try it online!

Exactly the same as the J and APL answers, but in reverse

# Answer
> 9 votes
# CJam, ~~43~~ 28 bytes

No idea if a full table based approach will be shorter, but here goes:

```
l_~^56213641532453s@S-#)g7*^

```

Input like

```
2 3

```

Output:

```
1

```

This is a mixture of my previous algorithm to determine the correct face out of 2 faces and xnor's approach of xors.

Try it online here

# Answer
> 5 votes
# LESS, 62 bytes

Uses the algorithm in this post:

```
.x(@a,@b){@r:mod(3*@a*@b*(@a*@a+6*@b*@b),7);content:~"'@{r}'"}

```

It could be shorter if the integer value was used, but to get it to display I needed to use the CSS `content` property which required variable interpolation.

Nonetheless, it's not often that a CSS preprocessor language is used for code golf!

To use with some HTML, you'd do this:

```
p::after { .x(1, 3); }

```

```
<p>Number on top: </p>

```

# Answer
> 4 votes
# Pyth, 30 bytes

```
K"23542 31463 12651 "h/x+K_Kz6

```

Requires the two digits as input, with no space in between (ex. `23` not `2 3`).

**Explanation:**

Any two digit sequence that lies within `23542` represents two sides that have `1` on top. Likewise, `31463` for 2, etc. Reversing this string gives the sequences for `4` through `6`.

This code just does a lookup in the string `"23542 31463 12651 15621 36413 24532"`, divides the index by 6, and increments to determine what the top side must be.

Test online here.

Thanks to @FryAmTheEggman for tips on golfing this.

# Answer
> 3 votes
Takes a similar approach as es1024 with a different lookup string:

# JavaScript (ES6), ~~73~~ ~~72~~ 61 bytes

```
t=(l,r)=>-~('354233146312651215623641332453'.search([l]+r)/5)

```

# JavaScript (ES5), ~~88~~ ~~87~~ 77 bytes

```
function t(l,r){return -~('354233146312651215623641332453'.indexOf([l]+r)/5)}

```

# CoffeeScript, ~~71~~ 62 bytes

~~And just for the fun of it, the code is 1 byte shorter in CoffeeScript as ES6 due to the permitted omission of parentheses~~

Due to the use of the `-~` trick, this turned out to be the same number of characters as ES6.

```
t=(l,r)->-~('354233146312651215623641332453'.indexOf([l]+r)/5)

```

# Answer
> 3 votes
# J (9)

Uses the algorithm from this post.

```
7|3***+*-

```

Tree graph of the function (might clear some things up):

```
    f=:7|3***+*-
    f
7 | 3 * * * + * -
   5 !: 4 < 'f'
  ┌─ 7
  ├─ |
──┤   ┌─ 3
  │   ├─ *
  └───┤   ┌─ *
      │   ├─ *
      └───┤   ┌─ +
          └───┼─ *
              └─ -

```

Demonstration:

```
   3 f 5
1
   4 f 6
2
   2 f 6
3
   2 f 1
4
   1 f 2
3
   4 f 5
6

```

# Answer
> 0 votes
# Lua 118

Had to restore last version because of a bug I can't find, nor have time to look for it.

```
z=io.read;o={"","","34","5 2","2165","46 13",""," 31064","  5612","   2 5","    43"}a=z();b=z();print(o[a+b]:sub(a,a))

```

Still working on this though.

# Answer
> 0 votes
# PHP, 81 bytes

Same as my JavaScript solution:

```
function t($l,$r){echo(int)(1+strpos('354233146312651215623641332453',$l.$r)/5);}

```

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

Not the shortest but I tried a different approach than currently in the answers.

```
f=(a,b)=>[a,b,7-a,7-b].reduce((p,v,i,r)=>p?p:'2312132'.indexOf([v]+r[i+1])+1,0)

```

# Answer
> 0 votes
# Lua, 89 bytes

A straightforward port of xnor's Python solution.

```
x=require('bit32').bxor
function(a,b)c=a*a*b%7;return x(a,x(b,2<c and c<5 and 7 or 0))end

```

# Answer
> 0 votes
# Bash, 85

This doesn't compete golf-wise with @xnor's magic polynomial. But I think this is another interesting way to calculate the answer:

```
g(){
((d[$1$2]))||{
d[$1$2]=$3
g $2 $1 $[7-$3]
g $2 $3 $1
}
}
g 1 2 3
echo ${d[$1$2]}

```

Specifically we know the the following about dice:

* If the left face is 1 and the right face is 2, then the top face is 3
* Rotation around opposite vertices by 120° gives some more triples of face values. E.g we rotate {l=1,r=2,t=3} once we get {l=2,r=3,t=1} and rotating again we get {l=3,r=1,t=2}
* The sum of opposite faces is always 7

Combining the above recursively (using {1,2,3} hardcoded as a starting point), we can generate the entire mapping of {l,r}-\>t for all possible values. This answer defines a recursive function g() that populates a full array such that d\[lr\]=t. The recursive function is initially called with {1,2,3} and recurses all over the whole cube until there are no more array elements that have not been set. The function recurses into itself in two ways:

* with l and r swapped and t subtracted from 7 (opposite faces)
* with {l,r,t} rotated to {r,t,l}

It then does a simple array lookup of the values required.

# Answer
> 0 votes
# Dyalog APL, 9 bytes

Blatant character substitution of ɐɔıʇǝɥʇuʎs's J solution:

```
7|3×××+×-

```

Edit: I later noticed that this exact solution was suggested by ngn on Jan 17, 15.

```
  the division remainder when divided by seven of
  |        three times
  |        | the product of the arguments
  |        |   times   \┌───┐
  |        |     \  ┌───┤ × │
┌────┐   ┌────┐   ┌─┴─┐ └───┘ ┌───┐
│ 7| ├───┤ 3× ├───┤ × │   ┌───┤ + │ - the sum of the arguments
└────┘   └────┘   └─┬─┘ ┌─┴─┐ └───┘
                    └───┤ × │ ---- times
                        └─┬─┘ ┌───┐
                          └───┤ - │ - the difference between the arguments
                              └───┘

```

TryAPL online!

# Answer
> 0 votes
# Julia, 26 bytes

```
f(a,b)=a$b$7*(2<a^2*b%7<5)

```

or

```
f(a,b)=(3*a^5*b^5-a^3*b)%7

```

or

```
f(a,b)=3*a*b*(a+b)*(a-b)%7

```

# Answer
> 0 votes
# Common Lisp, 45 bytes

```
(lambda(a b)(mod(* 3 a b(-(* a a)(* b b)))7))

```

Try it online!

Port of xnor solution.

# Answer
> 0 votes
# C# (Visual C# Interactive Compiler), 49 bytes

```
x=>1+("3542331463126512156236413"+x).IndexOf(x)/5

```

Try it online!

-1 byte thanks to @GB!

The input is a 2 character string containing the visible left and right digits.

Below is the solution that I came up with independently. Leveraging the lookup string from rink.attendant.6's JavaScript answer, I was able to shave off 5 bytes (but now our answers are pretty similar ;)

# C# (Visual C# Interactive Compiler), 55 bytes

```
x=>1+"42354 31463 51265 21562 41364 24532".IndexOf(x)/6

```

Try it online!

---
Tags: code-golf
---


title: Trapped Knight Sequence

text:
# Question
Title: Trapped Knight Sequence
## Introduction

Inspired by the very recent video The Trapped Knight - Numberphile, I came up with a challenge.

The trapped knight sequence is a finite integer sequence of length 2016, starting from 1, and has the following construction rules:

1. Write a number spiral in the following manner:

```
17 16 15 14 13 ...
18  5  4  3 12 ...
19  6  1  2 11 ...
20  7  8  9 10 ...
21 22 23 24 25 ...
```
2. Place a knight on 1.
3. Move the knight to the grid with the smallest number it can go that has not been visited before, according to the rules of chess (i.e. 2 units vertically and 1 unit horizontally, or vice versa).
4. Repeat until the knight gets stuck.

Here is the first three steps:

**Step 1**

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

```

Possible moves are 10, 12, 14, 16, 18, 20, 22, 24, among which the smallest is 10, so the second term is 10.

**Step 2**

```
  4  [ 3]  12  [29]  54
( 1)   2   11   28  [53]
  8    9  <10>  27   52
[23]  24   25   26  [51]
 46  [47]  48  [49]  50

```

Possible moves are ~~1~~, 3, 23, 29, 47, 49, 51, 53, among which the smallest is 3, so the third term is 3.

**Step 3**

```
 35  [34]  33  [32]  31
[16]  15   14   13  [30]
  5    4  < 3>  12   29
[ 6] ( 1)   2   11  [28]
  7  [ 8]   9  (10)  27

```

Possible moves are 6, 8, ~~10~~, 16, 28, 30, 32, 34, among which the smallest is 6, so the fourth term is 6.

The sequence stars with:

```
1 10 3 6 9 4 7 2 5 8 11 14 ...

```

and ends with

```
... 2099 2284 2477 2096 2281 2474 2675 2884 3101 2880 2467 2084

```

## Challenge

Write a shortest program or function, receiving an integer in the range `[1, 2016]` (or `[0, 2015]` if 0-indexed is used) as input, output the number at that index in the trapped knight sequence. You can choose to index the sequence with 0-indexed or 1-indexed, but you must specify which indexing scheme you use.

## Test cases (1-indexed)

```
n    | s(n)
-----+-----
   1 |    1
   2 |   10
   3 |    3
   6 |    4
  11 |   11
  21 |   23
  51 |   95
 101 |   65
 201 |  235
 501 |  761
1001 | 1069
2001 | 1925
2016 | 2084
```

For all possible outputs, please refer to this page.

## Winning Criteria

The shortest code of each language wins. Restrictions on standard loopholes apply.

# Answer
# JavaScript (ES7),  ~~182~~  181 bytes

```
f=(n,[x,y]=[2,1],a=[...Array(4e3)].map((_,n)=>[1,-1].map(s=>(i&1?-s:s)*(i+s*n-(n>0?n:-n)>>1),i=n**.5|0,n-=i*++i)))=>n--?f(n,a.find(([X,Y],j)=>(i=j,(x-X)*(y-Y))**2==4),a,a[i]=[]):i+1

```

Try it online!

### How?

A slightly modified version of my answer to the The Path Of The Wildebeest is definitely shorter (and faster) than that. But I wanted to try a different approach. Incidentally, I think it might be easier to implement this method in *some* esolangs.

Algorithm:

1. Initialization: we build the full list of coordinates for the first 4000 squares of the spiral, which is enough to process all moves of the knight before it gets trapped (the highest reached square being \\$3199\\$).
2. We look for the first square \\$(X,Y)\\$ such that:

$$((x-X)\times(y-Y))^2=4$$

where \\$(x,y)\\$ are the current coordinates of the knight.

The above condition is true only if \\$|x-X|=1\\$ and \\$|y-Y|=2\\$, or \\$|x-X|=2\\$ and \\$|y-Y|=1\\$, which covers all possible knight moves.
3. We set \\$(x,y)=(X,Y)\\$ and invalidate the entry in the list so that it's not picked a second time.
4. We either restart at step 2 or return the last index that was found if we're done.

---

# Node.js, 155 bytes

```
n=>(g=(x,y)=>n--?g(Buffer('QHUbcdWJ').map(m=c=>g[i=4*((x+=c%6-2)*x>(y+=c%7-2)*y?x:y)**2,i-=(x>y||-1)*(i**.5+x+y)]|i>m||(H=x,V=y,m=i))|H,V,g[m]=1):m+1)(1,2)

```

Try it online!
> 4 votes

# Answer
# 05AB1E, 53 bytes

```
Xˆ0UF2D(Ÿ0KãʒÄ1¢}εX+}Dε·nàDtyÆ+yO·<.±*->}D¯KßDˆkèU}¯θ

```

Exact port of my 05AB1E answer for *The Path of the Wildebeest* challenge, except with the `3` replaced with a `2`, and a trailing `θ` is added to output the 0-indexed value instead of the entire sequence of the first \\$n+1\\$ items.

Try it online or verify some more test cases (times out for the largest test cases).

**Explanation:**

See the explanation in my linked *The Path of the Wildebeest* answer. The only modified parts are the:

```
2D(Ÿ    # Get a list in the range [-2,2]: [-2,-1,0,1,2]

```

and a trailing:

```
θ       # Only leave the last item of the list

```

---

EDIT: A port of *@Arnauld*'s approach in his JavaScript (ES7) answer is (currently):

# 05AB1E, ~~57~~ 56 bytes

```
0D‚DˆUF64D(ŸãΣ·nàDtyÆ+yO·<.±*->}©ʒX-Pn4Q}¯¡˜2£DˆU}®J¯Jk>θ

```

Try it online or verify some more test cases (times out for the largest test cases).

**Explanation:**

```
‚%                # Create a pair of zeros: [0,0]
                  # (by pairing the (implicit) input with itself,
                  #  and then using modulo (implicit) input)
  DˆU             # Set both variable `X` to this, and add it to the global_array
F                 # Loop the (implicit) input amount of times:
 64D(Ÿ            #  Create a list in the range [-64,64]
      ã           #  Create each possible pair of `x,y`-coordinates
       Σ·nàDtyÆ+yO·<.±*->}
                  #  Sort this list in a spiral
        ©         #  Save it in the register (without popping)
 ʒ      }         #  Filter the list of coordinates by:
  X-              #   Subtract the coordinate of variable `X`
    P             #   Take the product
     n            #   Take the square
      4Q          #   Check if its equal to 4
                  # Since 05AB1E cannot remove inner lists, we use a workaround:
         ¯¡       # Split this list on each coordinate in the global_array
           ˜      # Flatten the entire list
            2£    # Only leave the first two integers as `x,y`-coordinate
                  # (if 05AB1E could remove inner lists, this would've been `¯Kн` instead)
              DˆU # Replace variable `X` with this, and add it to the global_array
}®                # After the loop: push all coordinates sorted in a spiral from the register
  J               # Join each coordinate together to a string
   ¯J             # Push the global_array, and also join them together to a string
                  # (if 05AB1E could index inner lists, both `J` could have been removed)
     k            # Get the index of each item of the global_array in the spiral list
      >           # Increase the 0-indexed index by 1 to make it 1-based
       θ          # And only leave the last one (which is output implicitly)

```

The sorting part `Σ·nàDtyÆ+yO·<.±*->}` is copied from my other answer. This can most likely be golfed though, since we don't need the values of the spiral, but only need to sort the \\$x,y\\$-coordinates.
> 3 votes

# Answer
# MATL, ~~41~~ 37 bytes

```
62lYLt1=i:"YYw(t5Mf'<@{}'ot_h+)X<y=])

```

Input is 0-based.

Try it online!
> 2 votes

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


title: A Radiation Hardened Palindromic Quine

text:
# Question
Title: A Radiation Hardened Palindromic Quine
There are radiation hardened quines, palindromic quines, but has anyone tried both?! I think not!

## Rules

So the challenge here is to make a quine that if any symbol is deleted it prints its *original* source code, *and* the quine needs to be the same read forward and backwards(before radiation damage)! All code will be scored based on *bytes* required to write it.

## Things to avoid

1. Do not use any programs that are capable of directly examining their code and outputting it (that even means programs that take their source and dump it into some sort of data)
2. Do not use *anything* that somehow cheats all of this (like a function that outputs itself and some other character... please)

***DO YOUR BEST!!!***

# Answer
> 12 votes
# Gol\>\<\>, 78 bytes

```
\<"2ss}}l2%?:}a`(:&K&:&]r&[r~H>.!01<<\

\<<10!.>H~r[&r]&:&K&:(`a}:?%2l}}ss2"<\

```

Try it online!

Verification!

A variation on the radiation hardened quine I posted yesterday. It's a little more complex since it needs to reverse the copied section using the undocumented `[]` operators, as well as redirect the pointer in one copy. If you're a little confused about why it doesn't look like a palindrome, remember that `><>` is a palindrome itself.

---
Tags: code-golf, quine, palindrome, radiation-hardening
---


title: Non trivial powers

text:
# Question
Title: Non trivial powers
Write the shortest program to print the non-trivial powers ≤ 2^12 in order

non-trivial power means the base and exponent are \> 1

Leading whitespace is optional
When there are multiple solutions, the order is not important, so

`16 = 4^2, 2^4` is ok

Sample output:

```
      4 = 2^2
      8 = 2^3
      9 = 3^2
     16 = 2^4, 4^2
     25 = 5^2
     27 = 3^3
     32 = 2^5
     36 = 6^2
     49 = 7^2
     64 = 2^6, 4^3, 8^2
     81 = 3^4, 9^2
    100 = 10^2
    121 = 11^2
    125 = 5^3
    128 = 2^7
    144 = 12^2
    169 = 13^2
    196 = 14^2
    216 = 6^3
    225 = 15^2
    243 = 3^5
    256 = 2^8, 4^4, 16^2
    289 = 17^2
    324 = 18^2
    343 = 7^3
    361 = 19^2
    400 = 20^2
    441 = 21^2
    484 = 22^2
    512 = 2^9, 8^3
    529 = 23^2
    576 = 24^2
    625 = 5^4, 25^2
    676 = 26^2
    729 = 3^6, 9^3, 27^2
    784 = 28^2
    841 = 29^2
    900 = 30^2
    961 = 31^2
   1000 = 10^3
   1024 = 2^10, 4^5, 32^2
   1089 = 33^2
   1156 = 34^2
   1225 = 35^2
   1296 = 6^4, 36^2
   1331 = 11^3
   1369 = 37^2
   1444 = 38^2
   1521 = 39^2
   1600 = 40^2
   1681 = 41^2
   1728 = 12^3
   1764 = 42^2
   1849 = 43^2
   1936 = 44^2
   2025 = 45^2
   2048 = 2^11
   2116 = 46^2
   2187 = 3^7
   2197 = 13^3
   2209 = 47^2
   2304 = 48^2
   2401 = 7^4, 49^2
   2500 = 50^2
   2601 = 51^2
   2704 = 52^2
   2744 = 14^3
   2809 = 53^2
   2916 = 54^2
   3025 = 55^2
   3125 = 5^5
   3136 = 56^2
   3249 = 57^2
   3364 = 58^2
   3375 = 15^3
   3481 = 59^2
   3600 = 60^2
   3721 = 61^2
   3844 = 62^2
   3969 = 63^2
   4096 = 2^12, 4^6, 8^4, 16^3, 64^2

```

# Answer
## Ruby 1.9, ~~112 111~~ 99 characters

```
4097.times{|x|s=[]
2.upto(64){|a|2.upto(12){|b|a**b==x&&s<<[a,b]*?^}}
puts [x,s*", "]*" = "if s[0]}

```

This takes about 0.8 seconds to complete on my system. A faster solution is 111 characters long:

```
h={};(2..64).map{|a|(2..12).map{|b|a**b<4097&&(h[a**b]||=[])<<[a,b]*?^}}
puts h.sort.map{|a,b|[a,b*", "]*" = "}

```
> 6 votes

# Answer
## Python, 113

```
R=range
for k in R(4097):
 v=', '.join(`i`+'^'+`j`for i in R(2,65)for j in R(2,13)if i**j==k)
 if v:print k,'=',v

```

This takes a few seconds to complete.
A faster (148 chars) version, using a dictionary to avoid the outermost loop, runs in ~ 0.01 sec:

```
R=range(2,65)
p={}
for i in R:
 for j in R:
    if i**j<4097:p[i**j]=p.get(i**j,[])+[`i`+'^'+`j`]
for k,v in sorted(p.items()):print k,'=',', '.join(v)

```
> 7 votes

# Answer
## Windows PowerShell, 102

With help by Ventero for the initial code.

```
$OFS=', '
4..4KB|%{$x=$_
if($s=2..64|%{$a=$_
2..12|?{[math]::pow($a,$_)-eq$x}|%{"$a^$_"}}){"$x = $s"}}

```
> 4 votes

# Answer
## ~~Interactive~~ J, ~~118~~ ~~101~~ 98

```
3 :0"0 i.4097
if.#l=.":2j2+63(<.@%~j.|)I.y=,^/~2+i.63
do.echo(":y),' = ',l rplc j`^,' ';', 'end.
)

```

(last newline unneeded)

Still a lot of code for the presentation...

Note: in theory changing `63` and `63` to `y` and `y` saves 2 more bytes but that version uses extreme amount of memory.

*Edited by randomra.*
> 4 votes

# Answer
## Bash, 138 chars

```
i=2;j=1
f(){((v>4096))&&((j=1,++i))
a[$v]+="$i^$j, "
((v=i**++j,i<65))&&f
}
f
f(){
echo $j = ${a[$j]}
((j++<v))&&f
}
f|sed '/=$/d;s/.$//'

```

### Edits

* **(169 : 155)** 2 `for` for a `while`.
* **(155 : 148)** Append with `+=`
* **(148 : 147)** output with `while`, reusing j
* **(147 : 142)** use sed to remove empty lines
* **(142 : 137)** put `v` in `(())`, use v for 4096 (last value)
* **(137 : 134)** remove sed quotes, join `(())` expressions
* **(134 : 132)** replace loops with recursive functions
* **(132 : 142)** forgot the comma `,` :(
* **(142 : 138)** tired of updates :p
> 3 votes

# Answer
## PHP, 138 characters - Output

```
<?for($b=1;++$b<65;)for($e=1;++$e<13;)if(4097>$f=pow($b,$e))$p[$f][]="$b^$e";ksort($p);foreach($p as$n=>$c)echo"$n = ".join($c,", ")."\n";

```

**Ungolfed**

```
<?php

// Array of combinations

$powers = array();

// Loop through every base from 2 to 64, as 64 is the highest you can go

for($base = 2; $base < 65; $base++){

    // Loop through all powers from 2 to 12, as 12 is the maximum

    for($power = 2; $power < 13; $power++){

        // Calculate the power

        $end = pow($base, $power);

        // Kill the loop if the result is too high

        if($end > 4096){
            break;
        }

        // Add the combination if the result is within limits

        $powers[$end][] = $base."^".$power;
    }
}

// Sort the powers by the total amount

ksort($powers);

// Output the powers in the correct format

foreach($powers as $number => $combinations){
    echo $number." = ".implode($combinations, ", ")."\n";
}

```
> 2 votes

# Answer
## Python, 127 chars

```
F={}
for i in range(693):a,b=i/11+2,i%11+2;F[a**b]=F.get(a**b,'')+', %d^%d'%(a,b)
for k in sorted(F)[:81]:print k,'=',F[k][2:]

```
> 2 votes

# Answer
# Mathematica, 152 byte

```
Print/@Cases[Range@4096,n_/;(2<=##&&##==##&)@@(f=#2&@@@FactorInteger@#&)@n:>{n,Row[{n^(1/#),#}~Row~"^"&/@Reverse@Rest@Divisors@#,", "]&@@f@n}~Row~" = "]

```

This got embarrassingly long. Something like 25 characters are spent on output formatting. The actual code is fairly simple: filter those numbers where all exponents in the prime factorisation are equal. Then, for each of those produce one result for each divisor of the exponent (excluding 1, including itself).
> 2 votes

# Answer
# OCaml + Batteries, 220 206 158 156 characters

Taking a hint from the best-scored solutions:

```
Printf.(iter(fun x->match
String.join", "[?List:sprintf"%d^%d"b e|b<-2--64;e<-2--12;float
x=float b**float e?]with""->()|s->printf"%5d = %s\n"x s)(4--4096))

```

(Line endings at significative whitespace to keep lines short.) A faster but longer version that generates powers instead of testing them:

```
Printf.(List.(iter(fun l->printf"%5d = %s\n"(fst(hd l))(String.join", "(map
snd l)))(group(fun(x,_)(y,_)->x-y)[?List:truncate p,sprintf"%d^%d"b
e|b<-2--64;e<-2--12;p<-List:[float b**float e];p<=4096.?])))

```
> 1 votes

# Answer
# JavaScript, 160

```
o={}
i=2
s=''
n=4097
for(k=4;k<n;k=++i*i)for(j=2;k<n;k*=i)
{a=i+'^'+j
if(o[k])o[k]+=', '+a
else o[k]=a
j++}for(i=0;i<n;i++)if(o[i])s+='\n'+i+' = '+o[i]
alert(s)

```

### 194

```
o={},i=2,s='',n=4096
for(k=4;k<=n;k=i*i){for(j=2;k<=n;k*=i){o[k]=o[k]||[]
o[k].push(i+'^'+j)
j++}i++}
for(i=0;i<n;i++){if(o[i]){s+='\n'+i+' = '
for(j in o[i])s+=(j==0?'':', ')+o[i][j]}}
alert(s)

```
> 1 votes

# Answer
## C (589 bytes)

```
int pow(int a,int b){
   int res = 1;
   while(b>0){
    while(b%2 == 0){
        a *= a; b/=2;
    }
    b--;
    res = res*a;
}
return res;
}
char s[99],t[9];

int main(){
   int N,T,a,i,f,e,n;
  for(n = 2; n <= 1<<12; n++){
      strcpy(s,"");
      T = N = n;
      f = 0;
      int sqt = sqrt(N)+1;
      for(i = 2; i <= sqt; i++){
         for(e=0;0==N%i;e++,N/=i);
           for(a = i; e > 1;e = e%2?(e+1)/2:e/2)
              for(a=i;a<T;pow(a,e)==T?f++?0:printf("%d =",T),sprintf(t,", %d^%d",a,e),strcat(s,t):0,a*=i);
    }
    f?puts(s+1):0;
   }
   return 0;
 }

```

I didn't golfed also this approach is not the best one but yet fast enough to produce an exact 0s in ideone.
> 1 votes

# Answer
## Haskell, 146 characters

```
c[a]=a
c(a:z)=a++", "++c z
n#[]=""
n#s=shows n$" = "++c s++"\n"
main=putStr$(\n->n#[shows x$'^':show y|x<-[2..64],y<-[2..12],x^y==n])=<<[4..4096]

```
> 1 votes

# Answer
# Pyth, 39 bytes

```
jm++^Fhd" = "j", "jL\^d<.g^Fk^tS64 2 81

```

Try it online here.

```
jm++^Fhd" = "j", "jL\^d<.g^Fk^tS64 2 81
                               S64       [1-64]
                              t          Discard first element
                             ^     2     Cartesian product of the above with itself
                        .g               Group the pairs, as k, using:
                          ^Fk              [a,b] -> a^b
                       <             81  Take the first 81 results of the above (those where exponential <= 4096)
 m                                       Map the remaining groups, as d, using:
                  jL\^d                    Join each pair in d on "^"
             j", "                         Join on ", "
  +     " = "                              Prepend " = "
   +^Fhd                                   Prepend the result of the exponent of one of the pairs
j                                        Join the result of the above on newlines, implicit print

```

If the output format is flexible enough to remove the need for spaces, -5 bytes to replace `" = "` with `\=` and `", "` with `\,`
> 1 votes

# Answer
## Haskell, 131

```
p[]=return()
p((x,y,z):s)=do print$show x++" = "++show y++"^"++show z;p s
main=p [(x,y,z)|x<-[2..2^12],y<-[2..x],z<-[2..x],x==y^z]

```
> 0 votes

# Answer
## JavaScript, 148 chars

```
s=''
for(i=2;i<4097;i++){q=''
for(a=2;a<65;a++)for(b=2;b<13;b++)if(Math.pow(a,b)==i)q+=a+'^'+b+', '
if(q)s+=i+' = '+q.slice(0,-2)+"\n"}alert(s)

```
> 0 votes

# Answer
# JavaScript (ES6) 134 ~~127~~

**Edit** revised, bugfixed and shortened **Edit 2**After some research, I realized that this answer was invalid for chronological reasons. The question predates `arrow functions` by years.

All that said, the other JS answers are way too complicated

```
/* for TEST:redefine console.log */ console.log=x=>O.innerHTML+=x+'\n';

for(l=[],b=1;++b<65;)for(e=2,r=b;(r*=b)<4197;)(l[r]=l[r]||[]).push(b+'^'+e++);l.some(function(v,i){console.log(i+' = '+v.join(', '))})
```

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

# Answer
# C 184

Should compile (with warnings) with any C compiler

```
char*l[5000],*t=l+4100,*u;
main(b,e,r)
{
  for(;++b<65;)
    for(e=2,r=b;(r*=b)<4100;l[r]=u)
      t+=1+sprintf(u=t,"%s, %d^%d",l[r]?l[r]:"",b,e++);
  for(r=1;++r<4097;)
    l[r]&&printf("%d =%s\n",r,l[r]+1);
}

```
> 0 votes

# Answer
## Pyth, 55 chars

```
=Tr2 64V^2 12JYFZTFbTIqN^ZbaJj\^[Zb))))IJjk[Nd\=dj", "J

```

My first time using Pyth, so it can probably be improved. It's a brute force that checks up to 64^64, thus is quite slow. You can save time by only checking up to 64^12 but it would cost a byte.
> 0 votes

# Answer
# 05AB1E, 36 bytes

```
2žxŸãΣ`m}99£.γ`m}εн`m'=yε'^ý}„, ý)}»

```

I have the feeling this can be improved a bit by using a slightly different approach..

Try it online.

**Explanation:**

```
2žxŸ           # Create a list in the range [2,64]
    ã          # Create each possible pair by taking the cartesian product with itself
Σ`m}           # Sort these `a,b`-pairs by their result of `a ** b`
    99£        # Only leave the first 99 pairs
       .γ`m}   # And then group the `a,b`-pairs by their result of `a ** b`
ε              # Now map each list of pairs `y` to:
 н             #  Take the first pair of list `y`
  `m           #  Take the `a ** b` value
 '=           '#  Push character "=" to the stack
 yε            #  Inner map over the pairs of list `y`:
   '^ý        '#   Join each pair with a "^" delimiter
      }„, ý    #  After the inner map: join these strings with a ", " delimiter
 )             #  Wrap all values on the stack into a list
}»             # After the outer map: join every inner list by spaces,
               # and the outer list by newlines (and output the result implicitly)

```
> 0 votes

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