title: Gear Train, Rotating

text:
# Question
Title: Gear Train, Rotating
Gears transfer different amount of speeds, depending on the size of the meshed gear.

Jack has a machine, that rotates a Gear Train. but you don't know the speed of the last gear.

Luckily, You are a great code golfer, so you can help him!

# So, What should I do?

Each gear is represented by 2 numbers, the radius of the inner gear and the radius of the outer gears.

If gear `A` is `[a,b]` and gear `B` is `[c,d]`, then the ratio between the speed of `A` and the speed of `B` would be `c:b`.

Given a list of gears (list of 2-tuples), output the speed of the last gear.

You can assume the speed of the first gear is `1`.

# Worked out example

Let's say our input is `[[6,12],[3,10],[5,8]]`.

The first gear, `[6,12]`, would have a speed of `1`.

Then, the second gear, `[3,10]`, would have a speed of `1*12/3 = 4`.

Then, the last gear, `[5,8]`, would have a speed of `4*10/5 = 8`.

# Testcases

```
input                    output
[[1,1],[2,2]]            0.5     (1/2)
[[1,2],[1,2],[1,2]]      4       (2/1*2/1)
[[6,12],[3,10],[5,8]]    8       (12/3*10/5)

```

# Rules

Basic rules apply.

# Answer
## Haskell, 19 bytes

```
foldr1(/).tail.init

```

Given a flat list like `[a,b,c,d,e,f]`, `tail.init` removes the first and last elements, and then `foldr1(/)` creates a cascade of divisions `b/(c/(d/e))))` that works out to alternating `*` and `/`: `b/c*d/e`.
> 9 votes

# Answer
# Jelly, 6 bytes

```
ḊṖU÷@/

```

Test suite.

```
ḊṖU÷@/   Main monadic chain. temp <- third argument (first input)
Ḋ        temp <- temp with first element removed
 Ṗ       temp <- temp with last element removed
  U      temp <- temp reversed
   ÷@/   temp <- temp reduced by reversed floating-point division.
         implicitly output temp.

```
> 7 votes

# Answer
# C, ~~115~~ ~~123~~ ~~121~~ ~~83~~ ~~80~~ ~~76~~ ~~71~~ 70 bytes

*4 bytes saved thanks to @LeakyNun!*

My first golf, probably not the best.

```
c;float r=1;float g(a,s)int*a;{for(;c<s-2;)r*=a[++c]/a[++c];return r;}

```

Takes an array and size.

Ungolfed:

```
int counter;
float ret=1;
float gear(int *arr, int size) {
    for(; counter < size-2; )
        ret = ret * arr[++counter] / arr[++counter];
    return ret;
}

```
> 6 votes

# Answer
# Jelly, 7 bytes

```
U÷Ḣµ2\P

```

Try it online! or verify all test cases.
> 5 votes

# Answer
## JavaScript (ES6), 44 bytes

```
a=>(t=1,a.reduce((x,y)=>(t*=x[1]/y[0],y)),t)

```

37 bytes for a flattened array:

```
a=>1/a.slice(1,-1).reduce((x,y)=>y/x)

```

Unlike (e.g.) Haskell, `reduceRight` is such a long name that it's cheaper to `reduce` the wrong way and take the reciprocal at the end.
> 4 votes

# Answer
# Pyth, 8 bytes

```
.UcZb_Pt

```

Test suite.
> 3 votes

# Answer
# J, 8 bytes

```
%/@}:@}.

```

Try it online!

## Usage

```
>> f =: %/@}:@}.

>> f 1 1 2 2
<< 0.5

>> f 1 2 1 2 1 2
<< 4

>> f 6 12 3 10 5 8
<< 8

```

where `>>` is STDIN and `<<` is STDOUT.

## Explanation

"Reduce" in `J` defaults from right to left, which took off a few bytes :p

```
divide       =: %
reduce       =: /
atop         =: @
remove_first =: }.
remove_last  =: }:

f =: (divide reduce) atop (remove_last) atop (remove_first)

```
> 3 votes

# Answer
## Mathematica, 26 bytes

```
#2/#&~Fold~#[[-2;;2;;-1]]&

```

An unnamed function that takes a flat even-length list of values and returns the exact result (as a fraction if necessary).

This uses the same approach as some other answers of folding division over the reversed list (after removing the first and last element).
> 3 votes

# Answer
# MATL, 9 bytes

```
6L)9L&)/p

```

Input format is any of these:

```
[[6,12],[3,10],[5,8]]
[6,12,3,10,5,8]
[6 12 3 10 5 8]

```

*EDIT (July 30, 2016): the linked code replaces `9L` by `1L` to adapt to recent changes in the language.*

**Try it online!**

### Explanation

```
6L    % Predefined literal: index from second to second-last element
)     % Apply index to implicit input. Removes first and last elements
9L    % Predefined literal: index for elements at odd positions
&)    % Two-output indexing. Gives an array with the odd-position elements
      % and the complementary array, with the even-position elements of the
      % original array
/     % Divide those two arrays element-wise
p     % Product of all entries. Implicitly display

```
> 2 votes

# Answer
# JavaScript, 54 bytes

```
(a,s=1)=>a.map((v,i)=>s*=(x=a[i+1])?v[1]/x[0]:1).pop()

```

## Usage

```
f=(a,s=1)=>a.map((v,i)=>s*=(x=a[i+1])?v[1]/x[0]:1).pop()

document.write([
  f([[1,1],[2,2]]),
  f([[1,2],[1,2],[1,2]]),
  f([[6,12],[3,10],[5,8]])
].join('<br>'))
```

## Ungolfed

```
function ( array ) {
  var s = 1;                                  // Set initial speed

  for ( var i = 0; i < array.length ; i++ ) { // Loop through array
    if ( array[i + 1] === undefined ) {       // If last element
      return s;                               // Return speed
    } else {                                  // Else
      s = s * ( array[i][0] / array[i+1][0])  // Calculate speed
    }
  }
}

```

Of course, the golfed variant is a bit different. With `.map()`, it replaces the first value of the array with the speed after the second wheel, the second value with the speed of the third wheel, and the last value and the second last value with the speed of the last wheel. So, we just take the last element with `.pop()`.
> 1 votes

# Answer
# PHP, ~~80~~ ~~79~~ 69 bytes

```
<?for($r=1;++$i<count($a=$_GET[a]);)$r*=$a[$i-1][1]/$a[$i][0];echo$r;

```

takes input from GET parameter `a`; prints result

initializes `$r` with 1, then loops from second to last tuple to multiply with first element of previous and divide through second element of current tuple.

---

Thanks to Jörg for reminding me of `$_GET`; that saved 7 bytes.

---

more elegant version, 88 bytes:

```
<?=array_reduce($a=$_GET[a],function($r,$x){return$r*$x[1]/$x[0];},$a[0][0]/end($a)[1]);

```
> 1 votes

# Answer
# 05AB1E, 5 bytes

```
¦¨.«/

```

Port of *@xnor*'s Haskell answer, so also takes the input as a flattened list.

Try it online or verify all test cases.

**Longer, but more interesting answer (9 bytes):**

```
ü2εÅ/`/}P

```

Takes the input as pairs, like the challenge description.

Try it online or verify all test cases.

**Explanation:**

```
¦¨       # Remove the first and last items of the (implicit) input-list
  .«     # Then left-reduce it by:
    /    #  Dividing
         # (after which the result is output implicitly)

ü2       # Create overlapping pairs of the (implicit) input-list of pairs
  ε      # Map over each overlapping 2x2 block:
   Å/    #  Pop and push its main anti-diagonal: [[a,b],[c,d]] → [b,c]
     `   #  Pop and push both values separated to the stack
      /  #  Divide the first by the second: b/c
  }P     # After the map: pop and push the product of the list
         # (which is output implicitly as result)

```
> 1 votes

# Answer
# JavaScript, ~~59~~ ~~58~~ 56 bytes

```
a=>a.reduce((p,c)=>p*c[1]/c[0],a[0][0]/a[a.length-1][1])

```

# Explanation

Reduce the array and multiply by every second value and divide by every first value. So for `[[6,12],[3,10],[5,8]]` it does `12/6*10/3*8/5`. Of course, the actual computation we wanted was `12/3*10/5` so we just want to ignore that first `/6` and last `*8` by multiplying `*6` back in and dividing `/8` back out. That cancelling out is done by setting `6/8` as the initial value for the reduce.
> 0 votes

# Answer
# Python 2, 52 bytes

```
lambda x:reduce(lambda x,y:y/float(x),x[1:-1][::-1])

```

An anonymous function that takes input of a flattened list via argument and returns the output.

This makes use of the division cascade idea, as in xnor's answer.

Try it on Ideone
> 0 votes

# Answer
# Python 3, 59 bytes

```
lambda x:eval('/'.join('{}*{}'.format(*i)for i in x)[2:-2])

```

An anonymous function that takes input of a non-flattened list via argument and returns the output.

**How it works**

For every pair of integers in the input, a string of the form `'int1*int2'` is created. Joining all these pairs on `/` gives a string of the form `'int1*int2/int3*int4/...'`, which is the desired calculation, but includes the undesired first and last integers. These are removed by slicing out the first two and last two characters in the sting, leaving the desired calculation. This is then evaluated and returned.

Try it on Ideone
> 0 votes

# Answer
# Pascal (FPC), 94 bytes

A recursive (had to do it..) function that takes a static 2D array and its length (no. of rows) as an input. Using some pointer math on the array.

```
function r(a:pdouble;n:integer):double;begin r:=a[1]/a[2];if n=2then exit;r:=r*r(a+2,n-1);end;

```

Try it online!

Ungolfed:

```
function ratio(a: pdouble; n: integer): double;
begin
  ratio := a[1] / a[2];
  if n=2 then
    Exit;
  ratio := ratio * ratio(a+2, n-1);
end;

```
> 0 votes

# Answer
## Actually, 14 bytes

```
pXdX2@╪k`i/`Mπ

```

Try it online! (currently not working because TIO is a few versions behind)

This program takes a flattened list as input.

Explanation:

```
pXdX2@╪k`i/`Mπ
pXdX            remove the first and last elements
    2@╪k        push a list where each element is a list containing every two elements of the original list (chunk into length-2 lists)
        `i/`M   map division over each sublist
             π  product

```
> 0 votes

# Answer
# R, 64 bytes

Turns out the vectorized approach and the `for` loop are equivalent in this case:

```
x=scan();prod(sapply(1:(sum(1|x)/2-1)*2,function(i)x[i]/x[i+1]))

```

or the `for` loop:

```
x=scan();for(i in 1:(sum(1|x)/2-1)*2)T=c(T,x[i]/x[i+1]);prod(T)}

```

\`
> 0 votes

# Answer
# Vyxal, 6 bytes

```
ḢṪ‡$/ḭ

```

Try it Online!
> 0 votes

---
Tags: code-golf
---


title: Find a recursive acronym

text:
# Question
Title: Find a recursive acronym
# Introduction

A recursive acronym is an acronym that contains or refers to itself, for example: `Fish` could be a recursive acronym for `Fish is shiny hero`, notice how that also contains the acronym itself. Another example is `Hi` -\> `Hi igloo`. Or even `ppcg paints` -\> `ppcg paints cool galaxies pouring acid into night time stars`

So basically, a sentence is a recursive acronym if the first letters of each of the words spell out the first word or words.

---

# Challenge

Make a program that takes a string of 1 or more words separated by a space character, and outputs a recursive acronym, or an empty string if it's impossible. It is impossible to make a recursive acronym for a string like, for example, `ppcg elephant` because you would start by taking the `p` from `ppcg` then adding that to the acronym, then taking the `e` from `elephant`. But now we have a contradiction, since the acronym currently spells out "pe..", which conflicts with "pp..". That's also the case with, for example, `hi`. You would take the `h` from `hi`, but the sentence is now over and there are no more letters to spell out `hi` and we are just left with `h` which doesn't match `hi`. (The string needs an amount of words more than or equal to the amount of letters in the acronym)

Input and output are not case sensitive

---

# Restrictions

* Anything inputted into your program will be valid English words. But you must make sure to output valid English words too (you can use a database or just store a word for each of the 26 letters)
* Standard loopholes and default IO rules apply

---

# Test Cases

```
hi igloo -> hi
ppcg paints -> (impossible)
ppcg paints cool giraffes -> ppcg
ppcg paints cool galaxies pouring acid into night time stars -> ppcgpaints
ppcg paints cool galaxies pouring acid into night time -> ppcg
ppcg questions professional pool challengers greatly -> (impossible)
I -> I

```

---

# Scoring

This is , so the smallest source code in bytes wins

# Answer
> 5 votes
# Japt, 13 bytes

```
¸
mÎ¬
VøUÎ ©V

```

Try it online!

# Answer
> 5 votes
# 05AB1E, 16 bytes

```
ð¡©ηʒJ®€нJηså}θJ

```

Try it online!

# Answer
> 2 votes
# Perl 6, ~~50 42 58~~ 49 bytes

*-9 bytes thanks to nwellnhof*

```
{~first {m:g/<<./.join~~/^$^a/},[R,] [\~] .words}

```

Try it online!

First option. ~~I'm exploiting the fact the `ord` only returns the ordinal value of first letter of a string, while `chrs` takes a list of ords and returns a string.~~ Or the regex from moonheart's answer is shorter `:(`. For reference, the previous answer was `.words>>.ord.chrs` instead of `[~] m:g/<<./`

### Explanation:

```
{~first {m:g/<<./.join~~/^$^a/},[R,] [\~] .words}
{                                               } # Anonymous code block
  first  # Find the first
                                [R,] [\~] .words  # Of the reverse of the triangular joined words
         {                    }  # That matches:
          m:g/   /   # Match all from the original string
              <<.    # Single letters after a word boundary
                  .join    # Joined
                       ~~/^$^a/   # And starts with the given word
 ~  # And stringify Nil to an empty string

```

# Answer
> 2 votes
## Haskell, ~~51~~ 48 bytes

Edit: -3 bytes thanks to @xnor.

```
(\w->[r|p<-scanl1(++)w,map(!!0)w==p,r<-p]).words

```

Finds acronym.

Try it online!

```
\w->            .words -- let 'w' be the input list split into words
   p<-scanl1(++)w      -- loop 'p' through the list starting with the first word
                       --  and appending the next words one by one, e.g.
                       --  "Fish","is","shiny","hero" -> "Fish","Fishis","Fishisshiny","Fishisshinyhero"
     ,map(!!0)w==p     -- if the word made out of the first characters of the
                       --  words of 'w' equal 'p'
  [r|   r<-p]          -- return the letters of 'p' - if the check before
                       --  never evaluates to True then no letters, i.e. the
                       --  the empty string is returned

```

# Answer
> 1 votes
# Retina 0.8.2, 60 bytes

```
^
$'¶
\G(\w)\w* ?
$1
+`^(.+)(\w.*¶\1 )
$1 $2
!`^(.+)(?=¶\1 )

```

Try it online! Finds the recursive acronym, if any. Explanation:

```
^
$'¶

```

Duplicate the input.

```
\G(\w)\w* ?
$1

```

Reduce the words on the first line to their initial letters.

```
+`^(.+)(\w.*¶\1 )
$1 $2

```

Insert spaces to match the original words, if possible.

```
!`^(.+)(?=¶\1 )

```

Output the first line if it is a prefix of the second line.

# Answer
> 1 votes
# Rust, 155, try it online!

Selected: Problem 1: Finding acronym

```
type S=String;fn f(t:&str)->S{let l=t.to_lowercase();let w=l.split(' ').fold(S::new(),|a,b|a+&b[..1])+" ";if (l+" ").contains(w.as_str()){w}else{S::new()}}

```

Ungolfed, just a bit:

```
fn f(t: &str) -> String {
    let l = t.to_lowercase();
    let w = l.split(' ').fold(String::new(), |a, b| a + &b[0..1]) + " ";
    if (l + " ").contains(w.as_str()) {
        w
    } else {
        String::new()
    }
}

```

Or if we can assume that the input is all lowercase, just 130:

```
type S=String;fn f(l:S)->S{let w=l.split(' ').fold(S::new(),|a,b|a+&b[..1])+" ";if (l+" ").contains(&w.as_str()){w}else{S::new()}}

```

# Answer
> 1 votes
# Perl 6, 56 bytes

```
$!=[~] m:g{<<.};say $! if m:g{<<\w+}.map({$_ eq $!}).any

```

Try it online!

Previously regexes were confusing and unusable to me. Suddenly I understand them perfectly. What happened to me :P

Fulfills choice 1.

# Answer
> 1 votes
# K (ngn/k), 40 bytes

First option:

```
{$[1=#:x;x;$[(*:t)~,/*:'t:" "\x;*:t;`]]}

```

Try it online!

# Answer
> 1 votes
# Jelly, 9 bytes

```
Ḳµ;\fZḢWƊ

```

A full-program printing the recursive abbreviation if it is possible.

**Try it online!**

### How?

```
Ḳµ;\fZḢWƊ - Main Link: list of characters
Ḳ         - split at space (let's call this v)
 µ        - start a new monadic chain (i.e. f(v)):
   \      - cumulative reduce v with:
  ;       -   concatenation -> [v(1), v(1);v(2), v(1);v(2);v(3); ...]
        Ɗ - last three links as a monad (i.e. f(v)):
     Z    -   transpose -> [[v(1)[1], v(2)[1], ...],[v(1)[1],v(2)[2],...],...]
      Ḣ   -   head -> [v(1)[1], v(2)[1], ...] ... i.e. 'the potential abbreviation'
       W  -   wrap in a list -> ['the potential abbreviation']
    f     - filter discard those from the left list that are not in the right list
          - implicit print -- a list of length 0 prints nothing
          -                   while a list of a single item prints that item

```

# Answer
> 1 votes
# JavaScript \[ES6\], 74 bytes

```
s=>s.split` `.map(w=>(b+='('+w,e+=')?',t+=w[0]),b=e=t='')&&t.match(b+e)[0]

```

Creates a regular expression to match on. See examples in code.

All test cases:

```
let f=

s=>s.split` `.map(w=>(b+='('+w,e+=')?',t+=w[0]),b=e=t='')&&t.match(b+e)[0]

console.log(f('hi igloo'))
// 'hi'.match('(hi(igloo)?)?')[0] == 'hi'

console.log(f('ppcg paints'))
// 'pp'.match('(ppcg(paints)?)?')[0] == ''

console.log(f('ppcg paints cool giraffes'))
// 'ppcg'.match('(ppcg(paints(cool(giraffes)?)?)?)?')[0] == 'ppcg'

console.log(f('ppcg paints cool galaxies pouring acid into night time stars'))
// 'ppcgpaints'.match('(ppcg(paints(cool(galaxies(pouring(acid(into(night(time(stars)?)?)?)?)?)?)?)?)?)?')[0] == 'ppcgpaints'

console.log(f('ppcg paints cool galaxies pouring acid into night time'))
// 'ppcgpaint'.match('(ppcg(paints(cool(galaxies(pouring(acid(into(night(time)?)?)?)?)?)?)?)?)?')[0] == 'ppcg'

console.log(f('ppcg questions professional pool challengers greatly'))
// 'pqppcg'.match('(ppcg(questions(professional(pool(challengers(greatly)?)?)?)?)?)?')[0] == ''

console.log(f('I'))
// 'I'.match('(I)?')[0] == 'I'

console.log(f('increase i'))
// 'ii'.match('(increase(i)?)?')[0] == ''

console.log(f('i increase'))
// 'ii'.match('(i(increase)?)?')[0] == 'i'
```

# Answer
> 1 votes
# Vyxal, 8 bytes

```
⌈:¦$∩h¦↔

```

Try it Online!

# Answer
> 0 votes
# Python 2, 106 bytes

First option - finding recursive acronym.
Returns result in list.

```
I=input().split()
print[' '.join(I[:i])for i in range(1,-~len(I))if[j[0]for j in I]==list(''.join(I[:i]))]

```

Try it online!

# Python 2, 120 bytes

First option - finding recursive acronym.

```
def F(I,a=[],r=''):
 for j in I.split():
  a+=j,
  if list(''.join(a))==[i[0]for i in I.split()]:r=' '.join(a)
 return r

```

Try it online!

# Answer
> 0 votes
# Ruby `-apl`, 57 bytes

```
$_=y="";$F.all?{|w|$F.map(&:chr).join[/^#{y+=w}/]?$_=y:p}

```

Try it online!

# Answer
> 0 votes
# Javascript, 71 bytes

Approach 1

```
l=s=>{p=s.split(' ');k=p.reduce((r,x)=>r+x[0],'');return k==p[0]?k:''}

```

Ungolfed:

```
l=s=>{
    p = s.split(' ');
    k = p.reduce((r,x)=>r+x[0],'');
    return k==p[0] ? k : '';
}

```
* Split the string by space.
* Create new string by taking first character from each word.
* Compare it with the first word.

# Answer
> 0 votes
# Python 2, 109 bytes

```
def f(s,J=''.join):s=s.split();return[J(s[:i])for i in range(len(s)+1)if J(zip(*s)[0]).find(J(s[:i]))==0][-1]

```

Try it online!

# Answer
> 0 votes
# Scala, 76 bytes

Solution for simple case (acronyms without whitespaces)

```
def^(s:String)={val l=s.split(" ");if(l(0)==l.map(_(0)).mkString)l(0)else""}

```

# Scala, ~~144 bytes~~ 100 bytes (see solution by ASCII-only in the comments)

```
def^(s:String)={val l=s.split(" ");l.scanLeft(List[String]())(_:::List(_)).find(_.mkString==l.map(_(0)).mkString).map(_.mkString).getOrElse("")}

```

Test in REPL

```
scala> def^(s:String)={val l=s.split(" ");if(l(0)==l.map(_(0)).mkString)l(0)else""}
$up: (s: String)String

scala> ^("hi igloo")
res12: String = hi

scala> ^("ppcg paints cool giraffes")
res13: String = ppcg

scala> ^("ppcg paints Xcool giraffes")
res14: String = ""

scala> ^("ppcg paints cool galaxies pouring acid into night time stars")
res15: String = ""

scala>

scala> def^(s:String)={val l=s.split(" ");l.scanLeft(List[String]())(_:::List(_)).find(_.mkString==l.map(_(0)).mkString).map(_.mkString).getOrElse("")}
$up: (s: String)String

scala> ^("hi igloo")
res16: String = hi

scala> ^("ppcg paints cool giraffes")
res17: String = ppcg

scala> ^("ppcg paints Xcool giraffes")
res18: String = ""

scala> ^("ppcg paints cool galaxies pouring acid into night time stars")
res19: String = ppcgpaints

```

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


title: Finite Field Multiplication

text:
# Question
Title: Finite Field Multiplication
## Overview

Given the integer representation of three elements in GF(2^64), give the product of the first two elements over GF(2^64) with the reducing polynomial defined as the polynomial m such that m(x) = x^64 + n(x), where n is the polynomial representation of the third element.

## You want me to *what*?

A finite field GF(p^q), where p is a prime and q is a natural number, contains p^q elements. (GF stands for Galois Field, which is another name for a finite field.) The elements of this finite field can be given many interpretations, but the two most common are as the integers between 0 and p^q-1, and as the polynomials with term coefficients between 0 and p-1 and degree less than q. There is a one-to-one correspondence between the base-p integer interpretations and the polynomial interpretations, from a one-to-one mapping between digits and term coefficients:

```
Integer interpretation (binary) | Polynomial interpretation (given x)
--------------------------------+------------------------------------
0                               | 0
1                               | 1
10                              | x
11                              | x + 1
100                             | x^2
101                             | x^2 + 1
1101                            | x^3 + x^2 + 1

```

Finite field arithmetic makes the most intuitive sense under the polynomial interpretation, but for brevity, the integer interpretation is used, and operations are described according to the integer representations of the finite field elements involved.

Addition in GF(p^q), like polynomial addition, operates with no carryover. Each digit in the sum is equal to the sum of digits in the addends, mod p. Likewise, subtraction in GF(p^q), like polynomial subtraction, is borrowless, with each digit in the difference being the difference in the corresponding digit in the minuend and subtrahend, mod p. If p = 2, both carryless addition and borrowless subtraction are equivalent to a bitwise XOR.

Multiplication in GF(p^q) relies on (but is *not*) polynomial multiplication, but with each term coefficient reduced mod p. If the factors are interpreted as integers rather than as polynomials, the operation can be implemented like long multiplication, but with summation of intermediate terms done without carry, as with finite field addition:

```
     1111
   * 1101
   ------
     1111
   1111
^ 1111
---------
  1001011

```

Multiplication in GF(p^q) also relies on a reducing polynomial, an irreducible polynomial with term coefficients in the set of integers between 0 and p-1, degree q, and leading coefficient 1 (and thus corresponding to an element in GF(p^(q+1))). Irreducible, in this context, means that it is not equal to any reduced polynomial product, as described above, of any other polynomials with term coefficients in the set of integers between 0 and p-1.

Last, multiplication in GF(p^q) relies on polynomial division, but with each term coefficient reduced mod p. Like reduced polynomial multiplication, this operation can be done directly on the integer representation by doing long division, but with borrowless subtraction rather than subtraction with borrow:

```
            1100
       ,--------
11111 / 10001001
      ^ 11111
      -------
         11100
       ^ 11111
       -------
            1101

```

Now, for the actual description of multiplication in GF(p^q).

First, the carryless product of the factors is calculated, as described above, keeping all digits in the product. Then, the remainder of the carryless division of this carryless product and the reducing polynomial (as interpreted as the integer interpretation of an element of GF(p^(q+1))) is taken. This remainder is the final product.

## Task

Given 3 64-bit words A, B, and C, return pmod(pmul(A, B), C+1\<\<64)), where pmul is the carryless multiplication operation as described above, and pmod is the remainder of the carryless division operation as described above. C + 1\<\<64 can be assumed to correspond to an element in GF(2^65) that in turn represents an irreducible polynomial.

As with most code golf challenges, standard loopholes apply, and shortest program wins.

## Test cases

Each test case is represented in four hexadecimal numbers, with the first three being the three arguments A, B, and C, as described above, and the fourth being the expected return value. (All values were calculated by Nemo, an open-source package for Julia that provides support for finite fields, among other things.)

```
0x0000000000000000 0x0000000000000000 0x000000000000001B 0x0000000000000000
0x0000000080000000 0x0000000080000000 0x000000000000001B 0x4000000000000000
0x0000000100000000 0x0000000100000000 0x000000000000001B 0x000000000000001B
0x0000000200000000 0x0000000200000000 0x000000000000001B 0x000000000000006C
0x0000000000000001 0x0000000000000001 0x702414004010004F 0x0000000000000002
0x0000000080000000 0x0000000100000000 0x702414004010004F 0x8000000000000000
0x0000000F00000000 0x0000000F00000000 0x702414004010004F 0x686D881284A01126
0x0000208000000000 0x0080000000000002 0x702414004010004F 0x870AF102748F8A93

```

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language, copied from here:

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

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

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

# Answer
# APL (Dyalog Unicode), ~~39~~ 36 bytesSBCS

```
{×≢⍵:(⍺×⊃⌽⍵)≠((⍺⍺×⊃⍺)≠1↓⍺,0)∇¯1↓⍵⋄0}

```

Try it online!

-3 bytes thanks to @ngn.

A recursive inline operator (dop). You can assign it to `f` and use it as `a(m f)b`.

A port of orlp's Python answer, but using bit arrays instead of integers. Dyalog APL has neither 64-bit integers nor bitwise ops, but can simulate them pretty well using array ops.

### How it works

```
{×≢⍵:(⍺×⊃⌽⍵)≠((⍺⍺×⊃⍺)≠1↓⍺,0)∇¯1↓⍵⋄0}  ⍝ ⍺←A, ⍵←B, ⍺⍺←M
{×≢⍵:                            ⋄ }  ⍝ If B has at least one bit,
                            ∇         ⍝   Recursive call with M fixed with...
                      1↓⍺,0           ⍝     A shifted left once
                     ≠                ⍝     XORed with
              (⍺⍺×⊃⍺)                 ⍝     M × highest bit of A
             (             )          ⍝     as left arg, and
                             ¯1↓⍵     ⍝     B shifted right once as right arg
     (⍺×⊃⌽⍵)≠                         ⍝   XOR the result with A × LSB of B
                                  0   ⍝ Otherwise, return a zero,
                                      ⍝ which is equivalent to 64 zero bits

```

The single zero is returned only on recursion. Then it becomes the right arg of `(⍺×⊃⌽⍵)≠`, and it acts exactly like a vector of 64 zeros (since `(⍺×⊃⌽⍵)` evaluates to a 64-length vector).
> 6 votes

# Answer
# Perl 5 `-p`, 51 bytes

```
$\=$'*($\>>63)^$\<<1^$`*($&<<$_&1)for-63..!/ .* /}{

```

Try it online!

I originally thought this would be hard for perl, but this isn't too bad. All the `$`s of course still hurt for arithmetic challenges..
> 5 votes

# Answer
# Python 2, 57 bytes

```
f=lambda a,b,m:a*b and b%2*a^f(a*2%2**64^(a>>63)*m,b/2,m)

```

I really tried to golf this in Rust, but the language is just not suitable for golfing. So here it is in Python.
> 4 votes

# Answer
# Jelly, 22 bytes

```
Bæc/ḣ-64æcB}ʋƬUSḣ64UḂḄ

```

Try it online!

Works either as a function or a full program. This takes two arguments: a 2-element list `[A,B]` for the numbers to multiply; and the argument `C` that specifies the polynomial. The TIO link contains a footer that prints the result in hexadecimal, making it easier to verify the test case.

## Algorithm

The calculation is done by representing each finite field element that we're working on as a list of bits that represent the coefficients of the polynomial. (For working on finite fields with this representation, we'd really want them to be little-endian, but Jelly's base conversion operators are big-endian, and thus the program ends up swapping endianness a couple of times.) Converting A and B to this form, then convolving them (which is the same operation as polynomial multiplication), gives us a polynomial (not necessarily a normalised one) representing the result.

We then need to normalize it (i.e. reduce it to degree at most 63) by doing the polynomial long division, i.e. taking the result modulo *x*64+C (where C is interpreted as a polynomial). This is the same as taking the result modulo *x*64−C because addition and subtraction are equivalent in binary finite fields. If we right-shift the result polynomial by 64 degrees, then multiply by C and add back the parts of the polynomial that fell off during the shift, this doesn't change the value modulo *x*64−C (because some multiple of *x*64 got subtracted from the result and the same multiple of C got added, thus reducing the result by a multiple of *x*64−C and thus not changing the remainder upon dividing by *x*64−C). Additionally, because C has degree at most 63 (it's a "64-bit word" interpreted as a polynomial), the shift-multiply-add sequence must reduce the degree of the resulting polynomial unless it's already 63 or lower, i.e. it's already normalized. It's therefore possible to repeat the shift-multiply-add (with polynomial addition and multiplication in GF(2), i.e. pointwise XOR and XOR-convolution) until we reach a value that remains unchanged, which must be the normalized result.

This algorithm is tweaked a little to be terser in Jelly. There are only two major changes. One is that we don't bother using only 0 and 1 as coefficients in the polynomials; in GF(2), 0 and 2 are the same number (all that matters is oddness versus evenness), so we just use regular pointwise addition (which doesn't carry from one coefficient into the next) instead of pointwise XOR and regular convolution instead of XOR-convolution (this saves lots of bytes during the program and requires only a  to fix the coefficients back to the 0-or-1 representation near the end). The other is that instead of immediately adding back the coefficients that got shifted off, they're remembered in a list and added back at the end (which is clearly equivalent because if we added them back immediately, they would just get shifted off again on the next iteration of the shift-multiply-add loop). (We actually remember the whole polynomial, but just take the least significant 64 coefficients for summing purposes.)

In order for the sum to work correctly, we need to use a little-endian representation (so that the coefficients that are added to each other when summing, i.e. the ones that are the same distance from the left end of the list, correspond to the same power of *x*0). It's possible to do the sum and the cut down to 64 coefficients either way round, and doing the sum first saves on the need for an extra quick to specify which array rank we want to work on. Then we convert the polynomial back to a big-endian representation, and then to a number, as the program's output.

## Explanation

```
Bæc/ḣ-64æcB}ʋƬUSḣ64UḂḄ
B                        Convert {[A,B]} to big-endian binary
 æc                      Take the convolution of
   /                       the converted version of A with that of B
             Ƭ           Repeatedly loop, until nothing changes:
            ʋ              (grouping/bracketing mark, sets the Ƭ's scope)
    ḣ                      take the prefix
     -                       that omits
      64                     the last 64 elements
        æc                 and take its convolution with
          B                  the big-endian binary representation of
           }                   the second argument
              U          Reverse {the result of} each {iteration}
               S         Sum corresponding elements {of the reversed results}
                ḣ64      Take the first 64 elements of the sum
                   U     Reverse back
                    Ḃ    Replace each element with its value mod 2
                     Ḅ   Convert from big-endian binary to decimal

```

The `U`s mark where the program changes from big-endian to little-endian notation for its polynomial, and where it changes back again.
> 4 votes

# Answer
# MMIX, 36 bytes (9 instrs)

```
00000000: e3030000 76040100 3f010101 70ff0003  ẉ¤¡¡v¥¢¡?¢¢¢p”¡¤
00000010: 3b000001 c6030304 c60000ff 5b01fffa  ;¡¡¢İ¤¤¥İ¡¡”[¢”«
00000020: f8040000                             ẏ¥¡¡

```

Disassembled and commented

```
ffm SET  $3,0           // r = 0
0H  ZSOD $4,$1,$0       // loop: t0 = B & 1? A : 0
    SRU  $1,$1,1        // B >>= 1
    ZSN  $255,$0,$3     // t1 = A >> 63? C : 0
    SLU  $0,$0,1        // A <<= 1
    XOR  $3,$3,$4       // r ^= t0
    XOR  $0,$0,$255     // A ^= t1
    PBNZ $1,0B          // if(B) goto loop
    POP  4,0            // return r

```

Russian peasant multiplication. Surprisingly simple! I think this is the first time MMIX has tied for shortest.
> 3 votes

# Answer
# PARI/GP, 69 bytes

```
f(a,b,c)=lift(g(a)*g(b)%(x^64+g(c)))%(x-2)
g(n)=Pol(Mod(binary(n),2))
```

Attempt This Online!
> 0 votes

---
Tags: code-golf, math, abstract-algebra
---


title: Tips for golfing in Postscript?

text:
# Question
Title: Tips for golfing in Postscript?
As one of the less popular languages, it's difficult to find literature on the avant garde of postscript hackery. So what discoveries have the golfers here made to exploit the stack model (or other features) to overcome Postscript's inherent verbosity?

# Answer
While most postscript operators are syntactically identifiers (and therefore must be space- (or otherwise-) delimited), the names `[`, `]`, `<<`, and `>>` are self-delimiting and scanner will detect them without intervening space. For the same reason, you cannot refer to these names with the usual `/literal` syntax (eg. `/[` is two tokens: an empty literal name equivalent to `()cvn cvlit`, and the executable name `[` equivalent to `([)cvn cvx exec`).

In order to redefine these names, which cannot be mentioned by name, we can use strings which are implicitly converted to names when used as keys in a dictionary (convenient!).

This example illustrates abusing these operators to perform arithmetic.

```
%!
([)0 def
(])1 def
(<<){add}def
(>>){mul}def
 ]]<<]]]<<<<>> =
%1 1 add 1 1 1 add add mul = %prints 6

```

Also `<<` and `[` (and `mark`) all mean the same thing.

---

My own postscript interpreter, xpost, also makes the right-curly brace available with some restrictions. discussion
> 4 votes

# Answer
## Embedded Decoder

A Postscript program has a unique(?) ability to read it's own program text as data. This is normally used by the `image` operator which receives a *data-acquisition-procedure* as input, and this procedure often uses `currentfile` followed by `readline`, `readstring`, or `readhexstring`. But seen another way, `image` is just another looping operator, so any loop can *read-ahead*. An example is the line-printer emulator from the Green Book.

Using the `token` operator invokes the scanner on a file or string, pulling off a number or space- (or otherwise-: see other answer) -delimited name.

A simple PS interpreter in PS:

```
{currentfile token not {exit} if dup type /arraytype ne {exec} if }loop

```

---

## Binary Operator String Decoder

Since I can't seem to get *raw* binary tokens to work for me (see other answer), I've made use of the "embedded decoding" idea to exploit the binary token mechanism to pack code into 8-bit strings, and then manipulate and parse the commands from the string *on the fly*.

```
/.{
    <920>  % two-byte binary-encoded name template with 0x92 prefix
    dup 1 4 3 roll put  % insert number into string
    cvx exec  % and execute it
}def
/${
    //.   %the /. procedure body defined above
    73 .  %"forall" (by code number)
}def

```

The `.` procedure takes a number from the stack and inserts it as the second byte in a two-byte string, the first byte being the prefix-byte for a binary token, specifying an executable system name. We save a byte in the hexstring by using a rule of the scanner that an odd number of nibbles in the hexstring is padded with an extra 0 nibble, so 3 hex nibbles produces a 2-byte string. The string is then marked *executable* and called with `exec` which invokes the scanner, produces the desired executable system name, and then loads the name and executes the operator. The `$` does this on each byte of a string on the stack, using the `.` procedure *twice*, once as the loop body, and then to execute the looping operator `forall` by number.

More compactly, these procedures look like this:

```
 /.{<920>dup 1 4 3 roll put cvx exec}def/${//. 73 .}def
%123457890123456789012345678901234567890123456789012345
%        1         2         3         4         5

```

So, 55 chars buys binary token strings. Or, for 6 (maybe 7, if you terminate it with a space) chars, you can load the G library with `(G)run` which defines `.` and `$` as above (+ a few others to extend the range of ascii-reachable codes).

Further illustrated in my crossword puzzle answer.
> 4 votes

# Answer
Here's a quickie: wrap multiple definitions in `[...>>begin` to eliminate the keyword `def` (nb. `[` is the same as `<<`).

```
 def def
[>>begin

```

So remember: **more than ~~three~~ two ... *flock together*!** ;)
> 4 votes

# Answer
## Replace hexstrings with ASCII85

Probably old news, but I just learned it. :)

You can do it using the postscript interpreter interactively with an encoding filter and cut-and-paste. But I'm going to show how to use `dc` to do it "by hand".

So, here's a hex string. We split it into 4-byte chunks.

```
95 20 6e d8   d0 59 49 35   50 74 ba c5   08 2d

```

Firing up dc, we input these as 32-bit (unsigned) big-endian-byte-order numbers. Then *mod*-off base-85 digits (there should be 5 until you get to 0).

```
0> dc
16i
95206ED8
Ai
d85%n85/
82
d85%n85/
83
d85%n85/
82
d85%n85/
78
d85%n85/
47
d85%n85/
0

```

Padding the last chunk with `00 00`, yields (decimal), omitting the same number of bytes that we padded.

```
47 78 82 83 82   66 81 72 79 83   25 72 82 25 69  2 53 30 [2 53]

```

Add 33 to shift into the printable range of ASCII and poof! ASCII85.

> 80 111 115 116 115 99 114 105 112 116 58 105 115 58 102 35 86 63
> which decodes to: Postscript:is:f#V? %%%Oops! should say 'fun'! I screwed up somewhere. :)

Wrap it in `<~` ... `~>`, and Level-2 Postscript can access 8-bit data, cheaper than hex.
> 4 votes

# Answer
When generating graphical output and console output does not matter, use `=` instead of `pop`.
> 4 votes

# Answer
# Factor-out repeated uses of long operator names

If you're already using a `<<>>begin` dictionary, there is a constant overhead of `/?{}` 4 characters per redefinition. So an operator of length *n* repeated *N* times will yield a character-count change of
(4 + *n*) - (*N* * (*n* \- 1)).

Setting this formula equal to 0 gives the equation of the *break-even* point. From this we can solve for each variable in terms of the other, yielding
*n* = - (*N* \- 4) / (1 - *N*) and
*N* = (4 + *n*) / (*n* \- 1) .

No we can answer questions like, "For how many uses of 'print' is it worthwhile to abbreviate?" *n* = 5, so *N* = 9/4. Take the ceiling, since you can't effectively call print 1/4 times. So, 3. 3 uses. And indeed,

```
print print print
/P{print}p p p

```

(assuming you've already paid the overhead of `<<>>begin` to activate the definition, of course).

Of course, binary tokens makes this kind of moot, giving you the first 255 names from the system name table as 2-bytes: 0x92, 0x??. And binary tokens are also self-delimiting, requiring no whitespace before or after, since the high-bit of the first byte is outside of the ascii range.
> 2 votes

# Answer
# Binary Tokens

For the ultimate *zip-up* of a PostScript program that final frontier is *binary tokens* which allows you to remove long operator names completely, at the cost of no longer having an ASCII-clean program.

So starting with a compacted block of postscript code

```
[/T[70{R 0 rlineto}48{}49{}43{A rotate}45{A neg rotate}91{currentdict
end[/.[currentpoint matrix currentmatrix]cvx>>begin begin}93{. setmatrix
moveto currentdict end end begin}>>/S{dup B eq{T begin exch{load exec}forall
end}{exch{load exch 1 add S}forall}ifelse 1 sub }>>begin moveto 0 S stroke

```

We look up all the names in the back of the PLRM (Appendix F, pp. 795-797)

```
appearance
in
vim    dec  meaning

<92>   146  'executable system name' binary token prefix
^A     1    add
^M     13   begin
^^     30   currentdict
'      39   currentmatrix
(      40   currentpoint
2      50   cvx
8      56   dup
9      57   end
=      61   eq  !)
>      62   exch
?      63   exec
I      73   forall
U      85   ifelse
d      100  load
h      104  matrix
k      107  moveto
n      110  neg
<85>   133  rlineto
<88>   136  rotate
§      167 stroke
©      169 sub

```

And then type them in prefixed by a `146` (decimal) byte. vim help for entering arbitrary bytes

Then in vim, the condensed file can be typed directly, so:

> \[/T\[70{R 0`^V`146`^V`133}48{}49{}43{A`^V`146`^V`136} 45{A`^V`146`^V`110`^V`146`^V`136} 91{`^V`146`^V`30`^V`146`^V`57 \[/.\[`^V`146`^V`40`^V`146`^V`104 `^V`146`^V`39\]`^V`146`^V`50\>\> `^V`146`^V`13`^V`146`^V`13}93{. `^V`146`^V`156 `^V`146`^V`107`^V`146`^V`30 `^V`146`^V`57`^V`146`^V`57 `^V`146`^V`13}\>\>/S{`^V`146`^V`56 B`^V`146`^V`61{T`^V`146`^V`13 `^V`146`^V`62{`^V`146`^V`100 `^V`146`^V`63}`^V`146`^V`73 `^V`146`^V`57}{`^V`146`^V`62{ `^V`146`^V`100`^V`146`^V`62

... you have to enter a space here to terminate the `^V`-62 and start the 1, but you can back up and delete it later ...

> 1`^V`146`^V`1S}`^V`146`^V`73} `^V`146`^V`85

... have to enter a space here to terminate the `^V`-85 and start the 1, but you can back up and delete it later ...

> 1`^V`146`^V`169}\>\>`^V`146`^V`13 `^V`146`^V`107

... 3rd digit of 3-digit code terminates the byte-entry so the following `0` here is normal, conveniently ...

> 0 S`^V`146`^V`167

Which will look like this on screen (in vim):

```
[/T[70{R 0<92><85>}48{}49{}43{A<92><88>}45{A<92>n<92><88>}
91{<92>^^<92>9[/.[<92>(<92>h<92>']<92>2>>
<92>^M<92>^M}93{.<92><9c><92>k<92>^^<92>9<92>9<92>^M}
>>/S{<92>8B<92>={T<92>^M<92>>{<92>d<92>?}<92>I<92>9}{<92>>
{<92>d<92>>1<92>^AS}<92>I}<92>U1<92>©}>><92>^M
<92>k0 S<92>§

```

This one can often be omitted entirely if the aim is just to show a picture. Ghostscript paints most things to the screen without needing `showpage`.

```
¡    161   showpage

```

\[*This actually isn't working. Ghostscript's giving me `undefined` and `syntaxerror` for these tokens. Maybe there's some **mode** I need to enable.*\]
> 2 votes

# Answer
# Change negative rolls to positive

Negative rolls can always be changed to positive rolls.

```
3 -1 roll
3 2 roll

5 -2 roll
5 3 roll

```
> 2 votes

# Answer
## Use my G library

https://github.com/luser-dr00g/G

It's a text file. No extension, for the shortest possible syntax to load it.

It permits this 203-char Sierpinksi Triangle program

```
[48(0-1+0+1-0)49(11)43(+)45(-)/s{dup
0 eq{exch{[48{1 0 rlineto}49 1 index
43{240 rotate}45{120 rotate}>>exch
get exec}forall}{exch{load
exch 1 sub s}forall}ifelse 1 add}>>begin
9 9 moveto(0-1-1)9 s fill

```

to be rewritten in 151 bytes as

```
3(G)run $
{A - B + A + B - A}
{B B}

{A - B - B}7{[ex{du w{(>K?\2u)$}if}fora]}rep
cvx[/A{3 0 rl}/B 1 in/-{120 rot}/+{-120 rot}>>b
100 200(k?B9)$ showp

```

workfile with comments

Using the abbreviated system names feature, `1(G)run` completely removes the burden of long operator names. An operator name need only be long enough to distinguish it from the others.

So

* `add` becomes `ad`
* `mul` becomes `mu`
* `index` becomes `i`
* *etc, etc.*

Use the PLRM Appendix F for the standard table of operator names.

And the feature of Operator Strings is available even if the abbreviated names is not selected. The bare library has a "base-level" selected by adding simply `(G)run` with no further decorations.

The base level includes a new function `.` which accepts the integer code for an operator (the same Appendix F mentioned above) and executes it.

The new function `$` iterates through a string and calls `.` upon each one. So the ascii code directly selects the operator by number.

A new function `@` lets you reach down to the bottom of the table in Appendix F by treating the space character (Ascii 0x20) as 0.

A new function `#` lets you reach further up into the table by first adding 95 (0x5F) so the space char 0x20 is treated as 127 (0x7F), the very next code after the last printable ascii character `~` 126 (0x7E).

Two new functions `!` lets you access a deeply nested structure of arrays and/or dicts with an *index array* of indices/keys, rather than tedious expressions of many `get` (and `put`) operators.

`(G)run` 7 chars buys the base-level.

`1(G)run` 8 chars buys that AND abbreviated system names.

`3(G)run $` 9 chars immediately begins an *implicit-procedure block* scanning sources lines until the next blank line, and defining the first line as a procedure called `A`, the next line is defined as a procedure called `B`, etc. This should remove most of the `def`s needed for defining lots of stuff, without needing to wrap them in a dictionary, nor even explicitly giving them names.
> 1 votes

# Answer
# Error handling with `stopped`

For example, suppose `f` takes an argument from the stack and you want to apply `f` until the stack is empty.

`{f}loop`

will give a stack underflow when the stack becomes empty. So you could use

`{count 0 gt{f}if}loop`

but a shorter solution is:

`{{f}loop}stopped`

(Note that this leaves `true` on the stack.)
> 1 votes

# Answer
# Hex colors in a string

`(AZm){255 div}forall setrgbcolor` selects the HTML color `#415a6b`, because `A` is hex `41`, etc, so `(AZm)` is the same as `<415a6b>`.

So if you have a bunch of different colors to use, you can put them on the stack ready to apply `setrgbcolor` for only 3 extra bytes per color. For example, this puts 5 colors `#616263`, `#646566`, ..., `#6d6e6f` (as 15 numbers between 0 and 1) on the stack:

`(abcdefghijklmno){255 div}forall`

In general you might have to use unprintable characters in the string.
> 0 votes

---
Tags: code-golf, tips
---


# Question
Title: Shortest Code to randomly place points and connect them
**The Task**

This is quite a simple coding task, all your program has to do is place a point on a canvas (or your alternative in another coding language) and connect it to all the dots already placed. Your program must take in one input, the number of dots that should be placed, and output some sort of display with the dots connected. Example

**Requirements**

* I have to be able to run it, which means that it has to have a compiler/tool to run it either online, or publicly available to download.
* You are allowed to use any library created before this challenge was set, as long as it wasn't designed for the sole purpose of solving this.
* This is a shortest code task, which means characters. Comments, code that changes colour (for prettiness) and libraries will be ignored.
* Your answer must be unique, don't steal other peoples code, shorten it a few characters and repost it.
* It must be able to run in less than 5 minutes, for the values of 5 and 100. It must also use a resolution of at least 200\*200 and put each dot in a random location on the canvas using a non-trivial distribution.

**Current Leaderboard**

```
Flawr        - Matlab        - 22  - Confirmed
Falko        - Python 2      - 41  - Confirmed
Wyldstallyns - NetLogo       - 51  - Confirmed
Ssdecontrol  - R             - 66  - Confirmed
9214         - Red           - 81  - Confirmed
David        - Mathematica   - 95  - Confirmed
Razetime     - Red           - 118 - Confirmed
ILoveQBasic  - QBasic        - 130 - Confirmed
Adriweb      - TI-Nspire Lua - 145 - Confirmed
Manatwork    - Bash          - 148 - Confirmed
Doorknob     - Python 2      - 158 - Confirmed
Kevin        - TCL           - 161 - Confirmed
M L          - HPPPL         - 231 - Confirmed
Manatwork    - HTML/JS       - 261 - Confirmed - Improved code of Scrblnrd3
Makando      - C#            - 278 - Confirmed
Scrblnrd3    - HTML/JS       - 281 - Confirmed
Geobits      - Java          - 282 - Confirmed

```

If I've missed you out, I'm very sorry, just add a comment to your work saying so and I'll add it as soon as I see it =)

**TL;DR**

* Input - Number of dots (int, can be hard coded)
* Output - Image of randomly placed dots, all connected to each other (graphic)
* Winner - Shortest code

# Answer
> 22 votes
# Matlab (22)

```
gplot(ones(n),rand(n))

```

It is assumend that n is the number of points, and it looks like this for n=10:

`n=6`:

### Explaination

`gplot` is a command for plotting graphs. The first argument is a `n x n` incidence matrix (full of ones, obviously). The second argument should be a `n x 2` matrix with the coordinates of the points, but it does not matter if the second dimension is bigger that 2, so I just generate an `n x n` matrix of random values (which is 2 characters shorter than generating an `n x 2` matrix).

## Links to documentation

# Answer
> 27 votes
# Java : ~~318 282~~ 265

Because, ya know, Java:

```
class M{public static void main(String[]a){new Frame(){public void paint(Graphics g){int i=0,j,d=640,n=25,x[]=new int[n],y[]=x.clone();for(setSize(d,d);i<n;i++)for(j=0,x[i]=(int)(random()*d),y[i]=(int)(random()*d);j<i;g.drawLine(x[i],y[i],x[j],y[j++]));}}.show();}}

```

Its just a simple loop that makes random dots and draws lines between the current dot and all previous ones.

Example with 25 dots:

With line breaks and imports:

```
import java.awt.*;
import static java.lang.Math.*;

class M{
    public static void main(String[]a){
        new Frame(){
            public void paint(Graphics g){
                int i=0,j,d=640,n=25,x[]=new int[n],y[]=x.clone();
                for(setSize(d,d);i<n;i++)
                    for(j=0,x[i]=(int)(random()*d),y[i]=(int)(random()*d);
                        j<i;
                        g.drawLine(x[i],y[i],x[j],y[j++]));
            }
        }.show();
    }
}

```

Edit: Since we're not counting imports, I imported a couple more things to save some characters later.

Edit 2: OP added an allowance for hardcoding number of dots. -17 chars :)

# Answer
> 11 votes
# Python 2 - ~~41~~ 35

After importing some libraries as allowed for this challenge

```
from pylab import rand as r
from pylab import plot as p
from itertools import product as x
from itertools import chain as c

```

we can plot some number of connected points with just one line of code:

```
X=r(5,2);p(*zip(*c(*list(x(X,X)))))

```

(The screenshot was generated with 10 points.)

# Answer
> 8 votes
# Mathematica ~~95~~ 87

With some help from belisarius.

```
CompleteGraph[n, VertexSize -> {2, 2},
VertexCoordinates -> Table[RandomInteger[{0, 199}, 2], {n}]]

```

**n=5**

---

**n=100**

Timing: 2.082654 sec

# Answer
> 7 votes
# Python 2, 158

Import statements not included in character count, as noted in question ("libraries will be ignored").

```
from PIL import Image,ImageDraw
from random import randint

s=[(randint(0,200),randint(0,200))for _ in range(int(input()))]
i=Image.new('RGB',(200,200))
[ImageDraw.Draw(i).line((p,q),255)for p in s for q in s]
i.show()

```

Sample outputs:

n=2 (...):

n=10 (looks like fancy 3d thing or something):

n=100 (looks like someone went BLELEEEAARARGHHH with a red pen):

n=500, 1000, 10000 (runs in about 1.5 seconds, 5-6 seconds, and 3.5 minutes respectively):

Note: the 10000 points one was run with a slightly optimized version that changed line 3 (not including imports) to this:

```
d=ImageDraw.Draw
for p in s:
  for q in s:d.line((p,q),255)

```

Otherwise it would have taken forever. :P

Ungolfed:

```
from PIL import Image, ImageDraw
from random import randint
point_count = int(input())
image_size = 200
points = [(randint(0, image_size), randint(0, image_size)) for _ in range(point_count)]
image = Image.new('RGB', (200, 200))
draw = ImageDraw.Draw(image)
for start_point in points:
    for end_point in points:
        draw.line((start_point, end_point), 255)
image.show()

```

# Answer
> 5 votes
## R, 66

This one is borderline cheating but I still think it's within the rules. Set up by loading the `igraph` package with `library(igraph)`, which can be downloaded from CRAN with `install.packages("igraph")`. Then assign the input to variable `N`. As per the rules, these are not counted in the total.

```
G=graph.adjacency(matrix(1,N,N),"un")
plot(G,layout=layout.random)

```

### N = 50

Note that this code also draws self-connections. Eliminating them (although there's no rule against them) adds 6 characters:

```
G=graph.adjacency(matrix(1,N,N),"un",diag=F)
plot(G,layout=layout.random)

```

## R, 141

This is an honest-to-goodness solution in base R:

```
p=replicate(2,runif(N))
g=as.matrix(expand.grid(1:N,1:N))
plot.new()
apply(g,1,function(i) segments(p[i[1],1],p[i[1],2],p[i[2],1],p[i[2],2]))

```

although you still have to enter `N` by hand.

### N = 50

I'm wondering if a `for` loop would be fewer characters than `apply` but I'm happy with what I've got.

# Answer
> 5 votes
# QBasic or QuickBasic, 130 characters

```
SCREEN 1:RANDOMIZE:N=10:DIM X(100),Y(100):FOR I=1 TO N:X(I)=RND*320:Y(I)=RND*200:FOR J=1 TO I:LINE(X(I),Y(I))-(X(J),Y(J)):NEXT J,I

```

### Code variations

* If you do not want to be prompted for a seed, replace `RANDOMIZE` with `RANDOMIZE TIMER`.
* If you want to be prompted for N, replace `N=10` with `INPUT N` or `INPUT "N";N`.

### Sample runs

For `N=5`, tested with QBasic 1.1 running on DOSBox 0.74:

For `N=100`, tested with QBasic 1.1 running on DOSBox 0.74:

# Answer
> 4 votes
# Bash + ImageMagick: 148 characters

```
c=()
while((i++<$1)); do
p=$[RANDOM%200],$[RANDOM%200]
c+=($p)
for e in ${c[@]};do
d+="line $p $e"
done
done
convert -size 200x200 xc: -draw "$d" x:

```

Sample run:

```
bash-4.3$ time ./line.sh 5

real    0m5.256s
user    0m0.137s
sys     0m0.017s

```

Sample output:

Sample run:

```
bash-4.3$ time ./line.sh 25

real    0m3.043s
user    0m0.574s
sys     0m0.023s

```

Sample output:

Sample run:

```
bash-4.3$ time ./line.sh 100

real    0m5.662s
user    0m11.156s
sys     0m0.076s

```

Sample output:

# Answer
> 4 votes
## \[TI-Nspire\] Lua - ~~145~~ ~~135~~ 130

(Updated fixed version)

"Importing" math.random as "r", first, as allowed : `r=math.random`

Actual code :

```
function on.paint(g)t={}for b=1,2*n-1,2 do t[b]=r(318)t[b+1]=r(212)for c=1,b-1,2 do g:drawLine(t[b],t[b+1],t[c],t[c+1])end end end

```

Note : This code works on the TI-Nspire calculators *(TI added Lua scripting to recent OSes of this platform, with an even-based API allowing users to graph stuff etc. for example.)*
It can also be tried online here (just erase the demo script and prepend mine with `n=10` for example)

# Answer
> 4 votes
# TCL 161 chars

Clearly not going to win, but beats several others presented here, and I think it makes good use of a highly undervalued language.

```
for {set i 0} {$i<10} {incr i} {lappend l [expr rand()*291] [expr rand()*204]}
pack [canvas .c]
foreach {x y} $l {foreach {w z} $l {.c create line $x $y $w $z}}

```

The default canvas size on my system appears to be 291x204. Not sure why, but using it saves 13 characters.

Fairly fast, 400 points in \< 5 seconds, 500 in ~10 s. Size and points can be scaled arbitrarily and colors and line styles can be altered, at the cost of characters of course. Un-golfed and using variables to make it clearer and easier to scale and color:

```
set n 20
set width 500
set height 500
set bg_color black
set line_color white
for {set i 0} {$i < $n} {incr i} {
        lappend points [expr rand() * $width] [expr rand() * $height]
}
canvas .c -width $width -height $height -background $bg_color
pack .c
foreach {x1 y1} $points {
        foreach {x2 y2} $points {
                .c create line $x1 $y1 $x2 $y2 -fill $line_color
        }
}

```

# Answer
> 4 votes
# Red, 118 bytes

```
a: collect[loop n[keep random d: 200x200]]
view[base d draw collect[foreach p a[foreach q a[keep reduce['line p q]]]]]

```

This was fun to figure out. Thanks to Toomas Vooglaid on Gitter and 9214 for helping with this. `n` is hardcoded.

-1 byte from Bubbler.

-2 bytes from Galen Ivanov.

## Screenshots

# Answer
> 3 votes
# C# Windows forms, 268

```
static void k(int n,int s){var f=new Form{Height=s+50,Width=s+25};f.Paint+=(u,v)=>{var r=new Random();var p=new Point[n];while(n>0)p[--n]=new Point(r.Next(s),r.Next(s));foreach(var a in p)foreach(var b in p)f.CreateGraphics().DrawLine(Pens.Tan,a,b);};f.ShowDialog();}

```

**N=5**

**N=50**

# Full code is given below

```
using System;
using System.Drawing;
using System.Windows.Forms;

namespace WindowsFormsApplication2
{
    static class Program
    {
        static void Main()
        {
            k(50, 200);
        }
        static void k(int n, int s)
        {
            var f = new Form {Height = s + 50, Width = s + 25};
            f.Paint += (u, v) =>
            {
                var r = new Random();
                var p = new Point[n];
                while (n > 0)
                    p[--n] = new Point(r.Next(s), r.Next(s));
                foreach (var a in p)
                    foreach (var b in p)
                        f.CreateGraphics().DrawLine(Pens.Tan, a, b);
            };
            f.ShowDialog();
        }
    }
}

```

# Answer
> 3 votes
# Red, 81 bytes

```
?(draw d: 200x200 loop n: 10[foreach x append[]y: random d[repend[]['line x y]]])

```

Try it locally in REPL

# Answer
> 2 votes
# HTML/JS, 210, thanks to manatwork

```
<canvas id=q /><script>c=q.getContext("2d");r=Math.random;e=prompt(a=[]);for(i=0;i<e;i++){a[i]={x:r()*300,y:r()*150};for(j in a)c.beginPath()+c.moveTo(a[i].x,a[i].y)+c.lineTo(a[j].x,a[j].y)+c.stroke()}</script>

```

JSFiddle

# Answer
> 2 votes
# C# WPF  ~~306~~  296

```
partial class W:Window{public W(){InitializeComponent();int x=5,i=0,j,z=200;int[]f=new int[x],s=new int[x];var r=new Random();var X=new Grid();AddChild(X);for(;i<x;i++){f[i]=r.Next(z);s[i]=r.Next(z);for(j=i;j>=0;)X.Children.Add(newLine(){X1=s[j],Y1=f[j--],X2=s[i],Y2=f[i],Stroke=Brushes.Red});}}}

```

I would like to say that I could remove Stroke=Brushed.Red. But Sadly that means that I am painting transparent lines, and my Guess is that it wouldn't really count. :P I can also shave of a couple of bytes by just creating a grid in the XAML view. But that seemed unfair, so I stripped the XAML to become a blank canvas. (I don't count the XAML as bytes...)

```
partial class W:Window
{
    public W()
    {
        InitializeComponent();
        int x=5,i=0,j,z=200;
        int[]f=new int[x],s=new int[x];
        var r = new Random();
        var X = new Grid();
        AddChild(X);
        for (;i<x;i++)
        {
            f[i]=r.Next(z);
            s[i]=r.Next(z);
            for (j=i;j>=0;)
                X.Children.Add(new Line()
                {
                    X1 = s[j],
                    Y1 = f[j--],
                    X2 = s[i],
                    Y2 = f[i],
                    Stroke = Brushes.Red
                });
        }
    }
}

```

XAML

```
<Window x:Class="W"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="MainWindow" Height="350" Width="525">
</Window>

```

# 5

# 100

# Answer
> 1 votes
# HPPPL, ~~231~~ 220

(HP Prime Programming Language for the HP Prime color graphing calculator)

golfed it down. 11 fewer chars by drawing all possible new lines right after every new point creation. Only two nested loops instead of the previous three.

```
export c(n) begin rect();local g,h;a:=makemat(0,n,2);for g from 1 to n do a(g,1):=ip(random(1,320));a(g,2):=ip(random(1,240));if g>1 then for h from 1 to g-1 do line_p(a(h,1),a(h,2),a(g,1),a(g,2));end;end;end;freeze;end;

```

Ungolfed (270 chars):

```
export randomnet(n)
begin
rect();
local g,h;
a:=makemat(0,n,2);
for g from 1 to n do
  a(g,1):=ip(random(1,320));
  a(g,2):=ip(random(1,240));
    if g>1 then
      for h from 1 to g-1 do
        line_p(a(h,1),a(h,2),a(g,1),a(g,2));
      end;
    end;
end;
freeze;
end;

```

examples:

c(10)

c(30)

The HP Prime color graphing calculator has a 320x240 pixel color display.

An emulator that also works with the connectivity kit is available at the HP website or here: http://www.hp-prime.de/en/category/6-downloads

... still waiting for the hardware to arrive. Update on the execution time will follow.

Today my HP Prime arrived. Here is the execution time for n=100 on an actual calculator:

Around 0.65 s for n=100.

The emulator is about 4 times as fast (around 0.178 s) on my Core i5 2410M laptop.

# Answer
> 1 votes
## NetLogo, 51 bytes

```
crt 9 [create-links-with other turtles fd random 9]

```

Replace 9s with other constants or variables as needed.

# Answer
> 0 votes
# 05AB1E (legacy), 17 chars

Imports (excluded from character count):

```
"exec('global r,p;from pylab import rand as r,plot as p')".E\

```

---

```
’p(*Œ¬(*r(,2))’.E

```

Beats all other answers. Port of Falko's Python answer. Go upvote him! Input is hard-coded before the first `,`.

```
’...’.E  # trimmed program
     .E  # evaluate...
’...’    # "p(*zip(*r(num,2)))"...
     .E  # as Python code

====================

p(*zip(*r(num,2)))  # full program
p(               )  # display plot with lines connecting all points at coordinates in ordered pairs...
  *                 # in...
   zip(         )   # each element of...
       *            # first element of...
        r(   , )    # array of...
          num       # input...
        r(     )    # arrays each containing...
              2     # literal...
        r(     )    # random numbers from 0 to 1, half-inclusive...
   zip(         )   # paired with corresponding element in...
       *            # second element of...
        r(   , )    # array of...
          num       # input...
        r(     )    # arrays each containing...
              2     # literal...
        r(     )    # random numbers from 0 to 1, half-inclusive

```

# Character scoring abuse (actually longer), 20 characters

```
""Ç6°βƵ6BÎ.:.E

```

---

```
"..."Ç6°βƵ6BÎ.:.E  # trimmed program
               .E  # evaluate...
     Ç             # list of charcodes of...
"..."              # literal...
        β          # converted from list of base-10 values of base...
       °           # 10 to the power of...
      6            # literal...
        β          # digits to decimal...
           B       # in base...
         Ƶ6        # 107...
             .:    # with all...
            Î      # 0...
             .:    # s replaced with...
            Î      # input

====================

p(*zip(*r(num,2)))  # full program
p(               )  # display plot with lines connecting all points at coordinates in ordered pairs...
  *                 # in...
   zip(         )   # each element of...
       *            # first element of...
        r(   , )    # array of...
          num       # input...
        r(     )    # arrays each containing...
              2     # literal...
        r(     )    # random numbers from 0 to 1, half-inclusive...
   zip(         )   # paired with corresponding element in...
       *            # second element of...
        r(   , )    # array of...
          num       # input...
        r(     )    # arrays each containing...
              2     # literal...
        r(     )    # random numbers from 0 to 1, half-inclusive

```

# Answer
> 0 votes
# PostScript, 48 bytes

```
00000000: 8814 3292 6c7b 7261 6e64 887f 9204 7d92  ..2.l{rand....}.
00000010: 837b 7b92 6b92 1a92 1992 1a34 9252 7b92  .{{.k......4.R{.
00000020: 4e92 6392 a792 4d7d 9283 7d92 657d 92a3  N.c...M}..}.e}..

```

Number of points is in the second byte (here it is 0x14 = 20 points).

Un-tokenized version:

```
20                          % number of points
2 mul{rand 127 and}repeat   % random points on stack
{
    {
        moveto              % move to top point on stack
        count copy          % duplicate stack
            count 4 idiv{   % for each duplicated point
            gsave
            lineto stroke   % draw a line to it
            grestore        % (removing it from the stack)
        }repeat
    }loop
}stopped                    % stop when stack is empty

```

---
Tags: code-golf, geometry, graphical-output, random
---


title: Make a "proof" generator

text:
# Question
Title: Make a "proof" generator
# Introduction

How to prove that 1 = 2:

```
1 = 2
2 = 4 (*2)
-1 = 1 (-3)
1 = 1 (^2)

```

You can just multiply both sides by 0, but that's cheating. This is just bending the rules a little bit.

# Your challenge:

Write a program/function that, when given two integers, outputs a "proof" that the two are equal.

# Rules

* Your program's output must start with `a = b`, where a and b are the integers, and end with `c = c`, where c can be any number. Don't output the operations.
* Your output can only use integers.
* The only operations you can use are addition, multiplication, division, subtraction, and exponentiation, and you cannot multiply, divide or exponentiate by 0.
* Each line must be one of the above operations done to both sides of the equation in the previous line.

For example, you could go:

```
4 = 9
5 = 10 (+1)
1 = 2 (/5)
8 = 16 (*8)
-4 = 4 (-12)
16 = 16 (^2)

```

# Scoring

This is , shortest wins!

# Answer
# JavaScript (Node.js), ~~57~~ 54 bytes

```
a=>b=>a+`=${b}
${a+a}=${b+b}
${a-=b}=${-a}
${a*=a}=`+a

```

Try it online!

## How?

There always exists a multiple of \\$0.5\\$ which, when subtracted from each number, creates a pair of the form \\$-a = a\\$. If \\$a-x=c\\$, then \\$b-(a-x+b)=-c\\$, so then if \\$a-x+b=x\\$, then \\$x=\frac{(a+b)}2\\$. This might not be an integer, so multiply by 2 beforehand.

-3 bytes thanks to Arnauld.
> 11 votes

# Answer
# , ~~64~~ 51 bytes

-7 bytes thanks to Dominic van Essen.

```
cat(sep=c("=","
"),x<-scan(),2*x,y<-2*x-sum(x),y^2)

```

Try it online!

The steps followed are:

```
a = b
2a = 2b (*2)
a-b = b-a (-(a+b))
(a-b)^2 = (b-a)^2 (^2)

```
> 7 votes

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

```
xIÂ-Dn)'=δý»

```

Try it online!

A port of my Jelly answer. I thought that 05AB1E's stack-based functionality would be shorter, but it isn't great at joining.

-1 byte thanks to ovs!

```
xIÂ-Dn)'=δý» - Full program. Takes [a, b] on the stack
x            - Push [2a, 2b];   Stack = [[a, b], [2a, 2b]]
 I           - Push [a, b];     Stack = [[a, b], [2a, 2b], [a, b]]
  Â          - Bifurcate;       Stack = [[a, b], [2a, 2b], [a, b], [b, a]]
   -         - Subtract;        Stack = [[a, b], [2a, 2b], [a-b, b-a]]
    D        - Duplicate;       Stack = [[a, b], [2a, 2b], [a-b, b-a], [a-b, b-a]]
     n       - Square;          Stack = [[a, b], [2a, 2b], [a-b, b-a], [(a-b)², (b-a)²]]
      )      - Wrap into array; Stack = [[[a, b], [2a, 2b], [a-b, b-a], [(a-b)², (b-a)²]]]
       '=    - Push '='
         δý  - Join each with '='
           » - Join array by newlines

```
> 7 votes

# Answer
# Jelly, 14 bytes

```
,Ḥ;_U,²$Ɗj€”=Y

```

Try it online!

Uses ophact's observation, that for any \\$a, b\\$, it is sufficient to yield the 4 equations

$$ a = b \\ 2a = 2b \\ a-b = b-a \\ (a-b)^2 = (b-a)^2 $$

## How it works

```
,Ḥ;_U,²$Ɗj€”=Y - Main link. Takes [a, b] on the left
 Ḥ             - Double, yielding [2a, 2b]
,              - Pair; [[a, b], [2a, 2b]]
        Ɗ      - Previous three links as a monad f([a, b]):
    U          -   Reverse; [b, a]
   _           -   Subtract; [a-b, b-a]
       $       -   Previous two links as a monad f([a-b, b-a]]):
      ²        -     Square; [(a-b)², (b-a)²]
     ,         -     Pair; [[a-b, b-a], [(a-b)², (b-a)²]]
  ;            - Concatenate; [[a, b], [2a, 2b], [[a-b, b-a], [(a-b)², (b-a)²]]
         j€”=  - Join each with "="
             Y - Join with newlines

```
> 6 votes

# Answer
# Python 2, <sup>~~84~~ \\$\cdots\\$ ~~73~~</sup> 71 bytes

Saved 5 bytes thanks to ovs!!!
Saved 2 bytes thanks to dingledooper!!!

```
k=a,b=input()
d=a-b
for a,b in k,[2*a,2*b],[d,-d],[d*d]*2:print a,'=',b

```

Try it online!
> 3 votes

# Answer
# Python 2, ~~79~~ 78 bytes

```
for x in'input()','2*a,2*b','a-b>>1,b-a>>1','a*a,'*2:a,b=eval(x);print a,'=',b

```

Try it online!

---

# Python 3, 70 bytes

```
def f(a,b):x=a-b;return f'{a}={b}\n{2*a}={2*b}\n{x}={-x}\n{x*x}={x*x}'

```

Try it online!
> 3 votes

# Answer
# C (clang), 65 bytes

```
#define r;printf("%d=%d\n",a
f(a,b){r,b)r+a,b+b)r-=b,-a)r*=a,a);}

```

Try it online! Uses ophact's approach.

Using clang instead of gcc saves a byte, as clang handles the undefined behavior in the second `printf` differently than gcc:

```
printf("%d=%d\n",a-=b,-a);

```

The order of the arguments' evaluation is unspecified. In gcc, the `-a` is evaluated before `a-=b`; thus, the second argument is not affected by the subtraction and must be `b-a` to get the proper value. However, in clang, the `a-=b` is evaluated first so the second argument is affected by the subtraction so `-a` is the correct value.

---

# C (gcc), <sup>~~76~~ ~~74~~ </sup> 66 bytes

*-8 bytes thanks to tsh*

```
#define r;printf("%d=%d\n",a
f(a,b){r,b)r+a,b+b)r-=b,b-a)r*=a,a);}

```

Try it online!
> 3 votes

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

Same as the javascript but using C#'s "superior code golfing" interpolation

```
a=>b=>a+@$"={b}
{a+a}={b+b}
{a-=b}={-a}
{a*=a}="+a

```

Try it online!
> 2 votes

# Answer
# Charcoal, 20 bytes

```
≔⁻⊗θΣθηＥ⟦θ⊗θηＸη²⟧⪫ι=

```

Try it online! Link is to verbose version of code. Takes input as a list `[a, b]`. Explanation: Based on @ophact's approach.

```
≔⁻⊗θΣθη

```

Vectorised subtract the sum of the list from its double, thus giving `[a-b, b-a]`.

```
Ｅ⟦θ⊗θηＸη²⟧⪫ι=

```

Loop over the lists `[a, b]`, `2[a, b]`, `[a-b, b-a]` and `[a-b, b-a]²`, joining each list with `=` and implicitly printing them on separate lines.
> 2 votes

# Answer
# Vyxal `j`, 12 bytes

```
:d?Ḃ-:²Wƛ\=j

```

Try it Online!

Why write your own original answer when you can just port 05ab1e amiright? :p

## Explained

```
:d?Ḃ-:²Wƛ\=j
:d           # [a, b], [2a, 2b]
  ?Ḃ-        # [a - b], [b - a]
     :²      # that, but squared
       Wƛ\=j # join each on "=" and then join that on newlines with the j flag

```
> 1 votes

# Answer
# Julia 1.0, 48 bytes

port of ophact's answer

```
a\b="$a=$b
$(2a)=$(2b)
$(a-=b)=$(-a)
$(a*=a)=$a"

```

Try it online!

## alternative answer, 48 bytes too

output is a list of strings

```
a\b=join.([a=>b,2a=>2b,(a-=b)=>-a,a*a=>a*a],'=')

```

Try it online!
> 1 votes

# Answer
# Python 3, 72 bytes

```
f=lambda a,b:f"{a}={b}\n{2*a}={2*b}\n{a-b}={b-a}\n{(a-b)**2}={(a-b)**2}"

```

Uses ophact's observation to answer in 4 steps.

Try it online!
> 1 votes

# Answer
# GolfScript, 37 bytes

```
~:%;:$' = ':&%n$2*&%2*n$%-&%$-.n\2?.&\

```

Try it online!
> 0 votes

# Answer
# Desmos, 207 characters

Try it online!

Organized for readability

Code:

```
<input 1>
<input 2>
<input 3>
a=ans_0
b=ans_1
c=ans_2
m=-(a+b)/2                           #Parenthesises placed here to show that addition occurs before addition; they don't appear in actual graph
d=-((a-m)^2-c)
l=[a,a+m,(a+m)^2,(a+m)^2+d]
l_1=[b,b+m,(b+m)^2,(b+m)^2+d]
(-1,[0,-1,-2,-3])
(0,[0,-1,-2,-3])
(1,[0,-1,-2,-3])
(4,0)
(4,-1)
(4,-2)
(4,-3)
                                    #LABELS (From higher to lower)
${l}
=
${l_1}
(given)
(${m})
(`^2`)
(${d})

```

Explanation:

`a` and `b` are the starting numbers, and `c` is the target number. Like my other programs, `ans_n` correspond to the line number, acting as inputs.

`m` is the midpoint of `a` and `b`. The reason that it is subtracted from `a` and `b` is so that they become equidistant from 0. NOTE: `m` is negative simply for formatting the proof; simply treat it as a positive and that all operations involving it are subtractions.

`d` is simply the distance between `c` and `(a-m)^2`. The squaring ensures that the term is positive, making both sides of the equation equal to each other. From there, the distance is added on to the result, making both sides of the equation equal to `c`.

`l` and `l_1` are lists. This is used to provide the labels. From left to right, the terms in the lists are as follows: the input, the input minus `m`, the square of (the input minus `m`), and the square of (the input minus `m`) plus `d`.

The first point, `(-1,[0,-1,-2,-3])`, uses `${l}` as a label. The list within the point creates multiple copies of the point at those y values, and the label uses the corresponding value from `l` to make it have the corresponding value on the graph. For example, `(-1,0)` would have `a` as its label. Likewise, the third point, `(1,[0,-1,-2,-3])`, would use `l_1` to produce its labels in a similar manner. The second point, however, would simply have the label be `=`.

Point `(4,0)` has the label `(given)`, which is self explanatory.

Point `(4,-1)` has the label `(${m})`, which uses `m` to produce the label of `(m)`.

Point `(4,-2)` has the label `(`^2`)`. The backticks are used to format the `^2` as a square and not as `^2`.

Point `(4,-3)` has the label `(${d})`, which uses `d` to produce the label of `(d)`.
> 0 votes

---
Tags: code-golf, arithmetic
---


title: Abandon all squares, ye who divide me

text:
# Question
Title: Abandon all squares, ye who divide me
# Definitions

* A **perfect square** is an integer which can be expressed as the square of another integer. For example, `36` is a perfect square because `6^2 = 36`.
* A **squarefree number** is an integer which is not divisible by any perfect square, except by `1`. For example, `10` is a squarefree number. However, `12` is not a squarefree number, because `12` is divisible by `4` and `4` is a perfect square.

# Task

Given a positive integer `n`, output the largest squarefree number which divides `n`.

# Testcases

```
n   output
1   1
2   2
3   3
4   2
5   5
6   6
7   7
8   2
9   3
10  10
11  11
12  6
13  13
14  14
15  15
16  2
17  17
18  6
19  19
20  10
21  21
22  22
23  23
24  6
25  5
26  26
27  3
28  14
29  29
30  30
31  31
32  2
33  33
34  34
35  35
36  6
37  37
38  38
39  39
40  10
41  41
42  42
43  43
44  22
45  15
46  46
47  47
48  6
49  7
50  10

```

# Scoring

This is . Shortest answer in bytes wins.

Standard loopholes apply.

# Reference

# Answer
> 46 votes
# 05AB1E, 2 bytes

```
fP

```

Try it online!

### How it works

```
f   Implicitly take input and compute the integer's unique prime factors.
 P  Take the product.

```

# Answer
> 15 votes
# Brachylog, 3 bytes

```
ḋd×

```

Try it online!

A very original answer...

### Explanation

```
ḋ          Take the prime factors of the Input
 d         Remove duplicates
  ×        Multiply

```

# Answer
> 14 votes
## JavaScript (ES6), ~~55~~ ~~54~~ ~~50~~ 46 bytes

Quoting OEIS:
*a(n) is the smallest divisor u of n such that n divides u^n*

Updated implementation:
*a(n) is the smallest ~~divisor u of n~~ positive integer u such that n divides u^n*

```
let f =

n=>(g=(p,i=n)=>i--?g(p*p%n,i):p?g(++u):u)(u=1)

for(n = 1; n <= 50; n++) {
  console.log(n,f(n));
}
```

# Answer
> 12 votes
# MATL, ~~6~~ 4 bytes

*2 bytes saved with help from @LeakyNun*

```
Yfup

```

Try it online!

### Explanation

Consider input `48`.

```
Yf   % Implicit input. Push prime factors with repetitions.  STACK: [2 2 2 2 3]
u    % Unique.                                               STACK: [2 3]
p    % Product of array. Implicit display.                   STACK: 6

```

# Answer
> 11 votes
# Jelly, 4 bytes

```
ÆfQP

```

Try it online!

```
ÆfQP  Main link, argument is z
Æf    Takes the prime factors of z
  Q   Returns the unique elements of z
   P  Takes the product

```

# Answer
> 9 votes
# CJam, 8 bytes

```
rimf_&:*

```

Why does every operation in this program have to be 2 bytes -\_-

Try it online!

```
ri       e# Read int from input
  mf     e# Get the prime factors
    _&   e# Deduplicate
      :* e# Take the product of the list

```

# Answer
> 9 votes
## Retina, ~~36~~ ~~30~~ 28 bytes

```
+`((^|\3)(^(1+?)|\3\4))+$
$3

```

Input and output in unary.

Try it online! (Includes a header and footer for decimal \<-\> unary conversion and to run multiple test cases at once.)

### Explanation

The idea is to match the input as a square times some factor. The basic regex for matching a square uses a forward-reference to match sums of consecutive odd integers:

```
(^1|11\1)+$

```

Since we don't want to match perfect squares, but numbers that are divisible by a square, we replace that `1` with a backreference itself:

```
(^(1+?)|\1\2\2)+$

```

So now the outer group `1` will be used **n** times where **n2** is the largest square that divides the input and group `2` stores the remaining factor. What we want is to divide the integer by **n** to remove the square. The result can be expressed as the number of iterations of group `1` times group `2`, but this is a bit tricky to do. Retina's `$*` will probably soon be improved to take a non-character token as its right hand argument in which case we could simply replace this with `$#1$*$2`, but that doesn't work yet.

Instead, we decompose the odd numbers differently. Let's go back to the simpler example of matching perfect squares with `(^1|11\1)+$`. Instead of having a counter `\1` which is initialised to **1** and incremented by **2** on each iteration, we'll have two counters. One is initialised to **0** and one is initialised to **1**, and they're both incremented by **1** on each iteration. So we've basically decomposed the odd numbers **2n+1** into **(n) + (n+1)**. The benefit is that we'll end up with **n** in one of the groups. In its simplest form, that looks like this:

```
((^|1\2)(^1|1\3))+$

```

Where `\2` is **n** and `\3` is **n+1**. However, we can do this a bit more efficiently by noticing that the **n+1** of one iteration is equal to the **n** of the next iteration, so we can save on a `1` here:

```
((^|\3)(^1|1\3))+$

```

Now we just need to go back to using an initial factor instead of `1` to match inputs that are divided by a perfect square:

```
((^|\3)(^(1+?)|\3\4))+$

```

Now all we need to do is replace this entire thing with `$3` at the end, which stores the initial factor times the number of steps, which drops one factor of the square from the input.

This is done repeatedly with the `+` at the very beginning of the program, to account for inputs that contain higher powers than squares.

# Answer
> 8 votes
# Octave, 27 bytes

```
@(x)prod(unique(factor(x)))

```

Similar approach as the other answers. The difference is: The functions have much longer names. I believe the code explains itself really: Takes the `prod`uct of the `unique` prime `factor`s of a number.

# Answer
> 7 votes
# Wolfram Language, ~~29~~ 28 bytes

-1 Thanks to @Martin Ender ♦

```
Most[1##&@@FactorInteger@#]&

```

**Explanation:**

```
           FactorInteger@#    (*Get prime factorization as {{a,b},{c,d}}*)
     1##&@@                   (*Multiply list elements together, to get the product of the factors and the product of their exponents*)
Most[                     ]&  (*Take the first element*)

```

# Answer
> 7 votes
# Python, 37 bytes

```
f=lambda n,r=1:1>>r**n%n or-~f(n,r+1)

```

Try it online!

The largest squarefree divisor of `n` is that smallest number `r` with all of `n`'s prime factors. We can check this as `r**n%n==0`, since `r**n` make `n` copies of each prime factor of `r`, and is divisible by `n` only if each of `n`'s prime factors is represented.

The `1>>r**n%n` is equivalent to `int(r**n%n==0)`. If `True` can be used output 1, it's 2 bytes shorter to do.

```
f=lambda n,r=1:r**n%n<1or-~f(n,r+1)

```

# Answer
> 6 votes
# Mathics, 40 bytes

```
Times@@(Transpose@FactorInteger@#)[[1]]&

```

Try it online!

# Answer
> 5 votes
## Alice, 4 bytes

```
iDo@

```

Try it online!

Input and output are given as the code point of a character (works for all valid Unicode code points).

### Explanation

Well, Alice has a built-in `D` whose definition is "Deduplicate prime factors". That is, as long as a value is divisible by some **p2** for a prime **p**, divide that value by **p**. This happens to be exactly the function required in this challenge. The rest is just input, output, terminate the program.

The reason this was added to Alice actually has nothing to do with this integer sequence. I was trying to stick to a theme of associating divisors with substrings and prime factors with characters. And I needed a function that goes with "deduplicate characters" (which is much more useful in general, because it let's you treat strings as sets, especially when used together with the various multiset operators).

# Answer
> 4 votes
# Haskell, 31 bytes

```
f n=until(\r->r^n`mod`n<1)(+1)1

```

Try it online!

# Answer
> 3 votes
# Pyke, 3 bytes

```
P}B

```

Try it online!

```
P   -   factors(input)
 }  -  uniquify(^)
  B - product(^)

```

# Answer
> 3 votes
# Prolog (SWI), ~~84~~ 39 bytes

```
f(N,P):-between(1,N,P),P^N mod N=:=0,!.

```

Try it online!

Adapted the idea of @xnor's Haskell answer to Prolog.

# Answer
> 2 votes
# PHP, 70 Bytes

```
for($r=1,$i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r%$i?$r*=$i:1);echo$r;

```

Try it online!

# Answer
> 1 votes
# Pyth, ~~8~~ 6 bytes

```
*F+1{P

```

\*-2 bytes thanks to @LeakyNun

Would be 3 if Pyth had a built-in for products of lists...

Try it!

```
*F+1{P
      Q     # Implicit input
     P      # Prime factors of the input
    {       # Deduplicate
  +1        # Prepend 1 to the list (for the case Q==1)
*F          # Fold * over the list

```

# Answer
> 1 votes
# C, ~~65~~ 50 bytes

Thanks to @Ørjan Johansen for removing the need for `r`. Thanks to this and some other dirty tricks I was able to squeeze 15 bytes off!

```
d;f(n){for(d=1;d++<n;)n%(d*d)||(n/=d--);return n;}

```

`while` is gone and replaced with `||` and index twiddling. `<=` should have been `<` all along.

~~`<=` turned to `<` by moving the increment to get `n%(++d*d)` (should be well defined due to operator precedence).~~

---

Original code:

```
d;r;f(n){for(r=d=1;d++<=n;)while(n%d<1)r*=r%d?d:1,n/=d;return r;}

```

# Answer
> 0 votes
# R, 52 bytes

```
`if`((n=scan())<2,1,prod(unique(c(1,gmp::factorize(n))))

```

reads `n` from stdin. Requires the `gmp` library to be installed (so TIO won't work). Uses the same approach as many of the above answers, but it crashes on an input of `1`, because `factorize(1)` returns an empty vector of class `bigz`, which crashes `unique`, alas.

# Answer
> 0 votes
# Axiom, 89 bytes

```
f(x:PI):PI==(x=1=>1;g:=factor x;reduce(*,[nthFactor(g,i) for i in 1..numberOfFactors g]))

```

test and results

```
(38) -> [[i, f(i)] for i in 1..30 ]
   (38)
   [[1,1], [2,2], [3,3], [4,2], [5,5], [6,6], [7,7], [8,2], [9,3], [10,10],
    [11,11], [12,6], [13,13], [14,14], [15,15], [16,2], [17,17], [18,6],
    [19,19], [20,10], [21,21], [22,22], [23,23], [24,6], [25,5], [26,26],
    [27,3], [28,14], [29,29], [30,30]]

```

this is the one not use factor() function

```
g(x:PI):PI==(w:=sqrt(x);r:=i:=1;repeat(i:=i+1;i>w or x<2=>break;x rem i=0=>(r:=r*i;repeat(x rem i=0=>(x:=x quo i);break)));r)

```

but it is only 125 bytes

# Answer
> 0 votes
# Pari/GP, 28 bytes

```
n->factorback(factor(n)[,1])

```

Try it online!

# Answer
> 0 votes
# Actually, 2 bytes

Try it online!

Explanation:

```
yπ
y   prime divisors
 π  product

```

# Answer
> 0 votes
# Pyt, 3 bytes

```
←ϼΠ

```

Explanation:

```
←                  Get input
 ϼ                 Get list of unique prime factors
  Π                Compute product of list
                   Implicit print

```

# Answer
> 0 votes
# Vyxal, 2 bytes

```
ǏΠ

```

Try it Online!

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