title: Draw a simple cube

text:
# Question
Title: Draw a simple cube
We don't have a single challenge about drawing a real 3 dimensional cube, so here it goes:

# Challenge

Your task is to draw a rotated, cube with perspective. It can be in a separate window or as an image.

# Input

Your input is 3 separate numbers between 0 and 359.99... These represent the rotation around the x, y and z axis in degrees.

```
0 0 0
30 0 40
95 320 12

```

# Output

You can either display it in a separate window or save an image. You can use any type of display (vector based, rasterized, etc.).

Edit: ASCII is allowed too, to allow golfing languages with only textual output.

The output for rasterized or ASCII graphics must be at least 50\*50 (pixels for rasterization, characters for ASCII)

# Additional information

The positive z axis points out from the window, the x axis is horizontal, and the y axis is vertical. Basically the OpenGL standard.

Rotations are counter-clockwise if you look at the cube in the negative direction of a specific axis, e.g looking down for the y axis.

The camera should be on the z axis at a reasonable distance from the cube in the negative z direction, the cube should be at (0;0;0). The. cube also needs to be fully visible, and take up at least 50% of the drawing frame. The camera should look in the positive z direction at the cube.

The rotations of the cube get applied in the x-\>y-\>z order.

The cube is rotated around it's center, it doesn't move.

To project a cube in 2d space, you need to divide the x and y coordinates of the cube with the distance parallel to the z-axis between the point and the camera.

# Rules

Rendering libraries are allowed, but the vertices need to be defined in the code. No 3d cube model class.

# Test cases

# Answer
# Shoes (Ruby) ~~235~~ 231

Everything computed from scratch.

```
Shoes.app{p,a,b,c=ARGV.map{|j|j.to_f/90}
k=1+i="i".to_c
p=(0..3).map{|j|y,z=(k*i**(j+a)).rect
x,z=(((-1)**j+z*i)*i**b).rect
q=(x+y*i)*i**c
[90*(k+q/(z-4)),90*(k+q/(4+z))]}
4.upto(15){|j|line *(p[j%4][0].rect+p[(j+j/4)%4][1].rect)}}

```

Call from commandline eg `shoes cube3d.rb 0 30 0`

The idea is to simultaneously generate / rotate the four vertices of a tetrahedron in 3d. Then, as these are reduced to 2d, we generate the four vertices of the inverse tetrahedron (the total 8 vertices being those of the cube.) This gives 4 pairs of vertices corresponding to the 4 body diagonals. Finally the 2d vertices are connected by lines: each vertex of the original tetrahedron must be connected to each vertex of the inverse tetrahedron forming the 12 edges and 4 body diagonals of the cube. The ordering ensures the body diagonals are not plotted.

**Test cases output**

Note that, to be consistent with the last two test cases, rotation about the z axis is clockwise from the POV of the viewer. This seems to be in contradiction with the spec however. Rotation direction can be reversed by modifying `*i**c` -\> `/i**c`

**ungolfed**

```
Shoes.app{
  p,a,b,c=ARGV.map{|j|j.to_f/90}   #Throw away first argument (script name) and translate next three to fractions of a right angle.
  k=1+i="i".to_c                   #set up constants i=sqrt(-1) and k=1+i

  p=(0..3).map{|j|                 #build an array p of 4 elements (each element wil be a 2-element array containing the ends of a body diagonal in complex number format)
    y,z=(k*i**(j+a)).rect          #generate 4 sides of square: 1+i,i-1,-1-i,-i+1, rotate about x axis by a, and store in y and z as reals
    x,z=(((-1)**j+z*i)*i**b).rect  #generate x axis displacements 1,-1,1,-1, rotate x and z about y axis by b, store in x and z as reals
    q=(x+y*i)*i**c                 #rotate x and y about z axis, store result in q as complex number
  [90*(k+q/(z-4)),90*(k+q/(4+z))]} #generate "far" vertex q/(4+z) and "near" vertex q/-(4-z) opposite ends of body diagonal in 2d format.

  4.upto(15){|j|                   #iterate through 12 edges, use rect and + to convert the two complex numbers into a 4 element array for line method
    line *(p[j%4][0].rect+         #cycle through 4 vertices of the "normal" tetrahedron
     p[(j+j/4)%4][1].rect)         #draw to three vertices of the "inverted" tetrahedron. j/4=1,2,3, never 0
  }                                #so the three edges are drawn but the body diagonal is not.
}

```

Note that for historical reasons a scale factor of 90 is applied in line 9 (chosen to be the same as 90 degrees in line 2 for golfing) but in the end there was no golfing advantage in using this particular value, so it has become an arbitrary choice.
> 2 votes

# Answer
## HTML/CSS/JS, 739 bytes, probably non-competing

But I just wanted to show off CSS 3D transforms.

```
w=_=>o.style.transform=`rotateZ(${z.value}deg) rotateY(${y.value}deg) rotateX(${-x.value}deg)`
```

```
input {
  width: 5em;
}

#c{width:90px;height:90px;margin:90px;position:relative;perspective:180px}#o{position:absolute;width:90px;height:90px;transform-style:preserve-3d;transform-origin:45px 45px 0px;}#o *{position:absolute;width:90px;height:90px;border:2px solid black}#f{transform:translateZ(45px)}#b{transform:rotateX(180deg)translateZ(45px)}#r{transform:rotateY(90deg)translateZ(45px)}#l{transform:rotateY(-90deg)translateZ(45px)}#u{transform:rotateX(90deg)translateZ(45px)}#d{transform:rotateX(-90deg)translateZ(45px)}
```

```
<div oninput=w()>
  X:<input id="x" type="number" value="0" min="0" max="360">
  Y:<input id="y" type="number" value="0" min="0" max="360">
  Z:<input id="z" type="number" value="0" min="0" max="360">
</div>
<!-- Above code for ease of use of snippet. Golfed version: <div oninput=w()><input id=x><input id=y><input id=z></div> -->

<div id=c><div id=o><div id=f></div><div id=b></div><div id=r></div><div id=l></div><div id=u></div><div id=d>
```
> 4 votes

# Answer
# Maple, ~~130+14~~ (in progress)

```
with(plots):f:=(X,Y,Z)->plot3d(0,x=0..1,y=0..1,style=contour,tickmarks=[0,0,0],labels=["","",""],axes=boxed,orientation=[Z,-X,Y]);

```

This plots a constant function inside a box, then uses plot options to hide ticks, labels and the function itself. Adding `projection=.5` to the options brings the camera closer, enabling perspective view.
I wrote this before the specs were finalized and the rotation order is `x, y', z''` instead of `x, y, z`. Until I fix the angles, here is another solution

# POV-Ray, 182

```
#include"a.txt"
#include"shapes.inc"
camera{location 9*z look_at 0}
light_source{9*z color 1}
object{Wire_Box(<-2,-2,-2>,<2,2,2>,.01,0)texture{pigment{color rgb 1}}rotate<R.x,-R.y,-R.z>}

```

reads input through the `a.txt` file which should contain
`#declare R=<xx,yy,zz>;`
with `xx,yy,zz` being the rotation angles
> 0 votes

---
Tags: code-golf, graphical-output, geometry, 3d
---


title: Scale up an image!

text:
# Question
Title: Scale up an image!
Your task is to write a program/function to scale up an image (list of strings) by a factor of `n`.

# Specs

* You will receive two inputs: an image, and a positive integer.
* The image will only contain ASCII printable characters (U+0020-U+007F).

# Scoring

This is . Shortest solution in bytes wins.

# Testcases

### Testcase 1

```
abc
xyz

2

aabbcc
aabbcc
xxyyzz
xxyyzz

```

### Testcase 2

```
|_|

3

|||___|||
|||___|||
|||___|||

```

# Answer
> 1 votes
## Actually, 23 bytes

```
╗'
@s`╜;)*(Zk♂ΣiΣn`M'
j

```

Takes the string input (with newlines represented as `\n`s to make multi-line input work) as the first input and the integer as the second.

Try it online!

Explanation (newlines replaced with `\n`):

```
╗'\n@s`╜;)*(Zk♂ΣiΣn`M'\nj
╗                          push n to reg0
 '\n@s                     split s on newlines
      `╜;)*(Zk♂ΣiΣn`M      for each line:
       ╜;)*(Z                make n copies and zip them
             k♂ΣiΣ           join the strings ("abc" -> ["abc", "abc"] -> "aabbcc" with n = 2)
                  n          make n copies of the result line
                     '\nj  join on newline

```

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


# Question
Title: How can I shorten this python code analyzing a 3d grid?
My Python 3 function `golf(...)` should take a list of lists of lists of strings representing a solid cube and return whether there are any places in which two equal strings are directly next to each other on the x, y or z axis (not diagonally).
If there are no adjacent duplicates, True shall be returned, else False.

The input list and all of its sublists have the same length as they represent a cube, and their length is greater than 1 but lower than or equal to 5. The only possible values for the Strings inside the nested lists are "X" and "Z".
The maximum code length should be less than 200 bytes.

This is an example test case:

```
golf([[["X", "Z"],
       ["Z", "X"]],
      [["Z", "X"],
       ["X", "Z"]]]) == True
golf([[["X", "Z"],
       ["Z", "X"]],
      [["X", "Z"],
       ["Z", "X"]]]) == False

```

My current solution has 234 bytes:

```
def golf(c):
 r=range(len(c));R=[(a,b)for a in r for b in r];j="".join
 return all("XX"not in l and"ZZ"not in l for l in[j(c[x][y][z]for x in r)for y,z in R]+[j(c[x][y][z]for y in r)for x,z in R]+[j(c[x][y][z]for z in r)for x,y in R])

```

How can I golf this code any further to save another 35 bytes?

# Answer
# Python 3, ~~108~~ 107 bytes

Since the cube only contains the strings `"X"` and `"Z"`, there are only two valid cube patterns. The one that starts with `XZXZX...` and the one that starts with `ZXZXZ...`.

My solutions generates these 2 cubes and checks if the inputted cube is one of them.

`def golf(l):L=len(l);r=range(L);return l in[[[list("XZ"*L)[(i+j+k)%2:][:L]for j in r]for k in r]for i in r]`

`i` iterates over the possible cubes. Since the dimension is at least 2, we can reuse `r` instead of writing `for i in(0,1)`.
> 9 votes

# Answer
## Python 3, 60 bytes

```
golf=g=lambda l:all(g(a)*g(b)*(a!=b)for a,b in zip(l,l[1:]))

```

The function recursively decides whether an N-dimensional array is alternating by checking if:

* Any two adjacent elements are unequal
* Each element is alternating

This successfully bottoms out for the strings `'X'` and `'Z'` because their length is `1`, so the `all` is taken of an empty list.
> 7 votes

# Answer
# Python 3 with NumPy, 125 bytes

```
import numpy
def golf(a):a=numpy.array(a);return(a[:-1]!=a[1:]).all()&(a[:,:-1]!=a[:,1:]).all()&(a[:,:,:-1]!=a[:,:,1:]).all()

```

# Python 3, ~~146~~ 128 bytes

```
e=lambda x,y:x!=y
z=lambda f:lambda*l:all(map(f,*l))
u=lambda f,g:lambda a:z(f)(a,a[1:])&z(g)(a)
golf=u(z(z(e)),u(z(e),u(e,id)))

```
> 5 votes

---
Tags: code-golf, geometry, tips, python
---


title: "KNOT" or "NOT"?

text:
# Question
Title: "KNOT" or "NOT"?
Write a program that processes an ASCII art representation of a tangled string and decides whether or not it can be untangled into a simple loop. The tangle is represented using the characters `-` and `|` to represent horizontal and vertical segments, and `+` to represent corners. Places where the string passes over itself are represented as follows:

```
            |                           |
         -------                     ---|---
            |                           |
(Horizontal segment on top)   (Vertical segment on top)

```

The ends of the string are connected together; there are no loose ends.

If your program decides that the string cannot be untangled into a simple loop, it should output the word `KNOT`. Otherwise, it should output the word `NOT`.

**This is a challenge, so the shortest valid answer (measured in bytes of source code) will win.**

### Limits

The ASCII input will consist of up to 25 lines of 80 characters. You may assume that all the lines are padded with spaces to the same length.

### Examples

**Input:**

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

```

**Output:**

```
KNOT

```

**Input:**

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

```

**Output:**

```
NOT

```

### References

# Answer
> 114 votes
# Python 3, ~~457~~ ~~316~~ 306 bytes

```
E=enumerate
V={'+'}
Q=[[(-j,i,k)for i,u in E(open(0))for j,v in E(u)for k in[{v}&V,'join'][u[j:j+2]=='|-']]]
while Q:
 a,b,c,d,*e=A=tuple(x//2for y,x in sorted((y,x)for x,y in E(Q.pop())));e or exit('NOT')
 if{A}-V:V|={A};Q+=[[c,d,a,b]+e,A,A[2:]+A[:2]][a<c<b<d:][c<a<d<b:]
 if b==d:Q=[[a,c]+e]
exit('KNOT')

```

## Huh?

The program first converts the knot to a rectangular diagram, which has the following restrictions:

1. No two vertical or horizontal segments lie on the same line.
2. No vertical segment crosses over a horizontal segment.

For example, the first test case is converted to the following rectangular diagram:

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

```

which we uniquely represent by the sequence of y coordinates of the vertical segments, from right to left:

```
(5,10, 1,9, 8,10, 9,12, 5,12, 1,4, 0,3, 2,4, 3,7, 6,8, 7,11, 2,11, 0,6)

```

It then searches for simplifications of the rectangular diagram as described in Ivan Dynnikov, “Arc-presentations of links. Monotonic simplification”, 2004. Dynnikov proved that from any rectangular diagram of the unknot, there is a sequence of simplifying moves that ends at the trivial diagram. Briefly, the allowed moves include:

1. Cyclically permuting the vertical (or horizontal) segments;
2. Swapping consecutive vertical (or horizontal) segments under certain configuration constraints.
3. Replacing three adjacent vertices that lie in the very corner of the diagram with one vertex.

See the paper for pictures. This is not an obvious theorem; it does not hold if, say, Reidemeister moves that do not increase the number of crossings are used instead. But for the particular kinds of simplifications above, it turns out to be true.

(We simplify the implementation by only permuting vertical segments, but also allowing the entire knot to be transposed to interchange horizontal with vertical.)

## Demo

```
$ python3 knot.py <<EOF
+-------+    +-------+
|       |    |       |
|   +---|----+   +-------+
|   |   |        |   |   |
+-------|------------|---+
    |   |        |   |
    +---+        +---+
EOF
KNOT
$ python3 knot.py <<EOF
+----------+
|          |
|    +--------------+
|    |     |        |
|    |   +-|----+   |
|    |   | |    |   |
|    +-----+    |   |
|        |      |   |
|        +------|---+
|               |
+---------------+
EOF
NOT
$ python3 knot.py <<EOF  # the Culprit
        +-----+
        |     |
+-----------+ |
|       |   | |
|   +-+ | +---|-+
|   | | | | | | |
| +-|-------+ | |
| | | | | |   | |
+-|-+ | | +---+ |
  |   | |       |
  +---|---------+
      | |
      +-+
EOF
NOT
$ python3 knot.py <<EOF  # Ochiai unknot
    +-----+
    |     |
  +-|---------+
  | |     |   |
  | | +-+ |   |
  | | | | |   |
+-|-|---|-|-+ |
| | | | | | | |
| | | +---|---+
| | |   | | |
+-------+ | |
  | |     | |
  | +-------+
  |       |
  +-------+
EOF
NOT
$ python3 knot.py <<EOF  # Ochiai unknot plus trefoil
    +-----+ +-----+
    |     | |     |
  +-|---------+   |
  | |     | | |   |
  | | +-+ | +---+ |
  | | | | |   | | |
+-|-|---|-|-+ +---+
| | | | | | |   |
| | | +---|-----+
| | |   | | |
+-------+ | |
  | |     | |
  | +-------+
  |       |
  +-------+
EOF
KNOT
$ python3 knot.py <<EOF  # Thistlethwaite unknot
      +---------+
      |         |
    +---+ +---------+
    | | | |     |   |
    | +-------+ |   |
    |   | |   | |   |
    |   | | +---+   |
    |   | | | |     |
    |   | +-------+ |
    |   |   | |   | |
    |   +-------+ | |
    |       | | | | |
+-----------+ | | | |
|   |         | | | |
| +-----------+ | | |
| | |           | | |
| | +-------------+ |
| |             |   |
| |             +-----+
| |                 | |
| |                 +---+
| |                   | |
+---------------------+ |
  |                     |
  +---------------------+
EOF
NOT
$ python3 knot.py <<EOF  # (−3,5,7)-pretzel knot
      +-------------+
      |             |
    +-|-----+       |
    | |     |       |
  +-|-+   +-------+ |
  | |     | |     | |
+-|-+   +---+   +---+
| |     | |     | |
| |   +---+   +---+
| |   | |     | |
| | +---+   +---+
| | | |     | |
| +---+   +---+
|   |     | |
|   |   +---+
|   |   | |
|   | +---+
|   | | |
|   +---+
|     |
+-----+
EOF
KNOT
$ python3 knot.py <<EOF  # Gordian unknot
+-------------+                 +-------------+
|             |                 |             |
| +---------+ |                 | +---------+ |
| |         | |                 | |         | |
| | +-------------+         +-------------+ | |
| | |       | |   |         |   | |       | | |
| | | +---------+ |         | +---------+ | | |
| | | |     | | | |         | | | |     | | | |
| +-------+ | +-------+ +-------+ | +-------+ |
|   | |   | |   | |   | |   | |   | |   | |   |
+-------+ | +-------+ | | +-------+ | +-------+
    | | | |     | | | | | | | |     | | | |
    | +-------+ | | | | | | | | +-------+ |
    |   | |   | | | | | | | | | |   | |   |
    +-------+ | | | | | | | | | | +-------+
        | | | | | | | | | | | | | | | |
        | +-----+ | | | | | | +-----+ |
        |   | |   | | | | | |   | |   |
        +---------+ | | | | +---------+
            | |     | | | |     | |
          +---------+ | | +---------+
          | | |       | |       | | |
          | | +-----------------+ | |
          | |         | |         | |
          | +---------------------+ |
          |           | |           |
          +-----------+ +-----------+
EOF
NOT

```

---
Tags: code-golf, ascii-art, decision-problem, knot-theory
---


title: Encrypting and Decrypting Challenge

text:
# Question
Title: Encrypting and Decrypting Challenge
## Encrypting Challenge

Your encrypting program must be able to do following things:

1. Input password
2. Generate random key
3. Encrypt random key with set key
Then, the decrypting program must be able to these things:
4. Input encrypted password
5. Input encrypted random key
6. Decrypt random key
7. Decrypt password with decrypted random key
8. Print password

The encryption must be setted with the key. It must be a table encryption or a encryption which makes the unencrypted values to a part of the key. This is . The shortest program wins!

# Answer
# Pyth, 16+16 = 32 bytes

Encryption:

```
s@LG+VxLGQxLG*zl

```

Try it online!

Decryption:

```
s@LG-VxLGQxLG*zl

```

Try it online!

Uses Vigenère cipher.
> 0 votes

---
Tags: code-golf, encryption
---


title: Compute CRC32 Hash

text:
# Question
Title: Compute CRC32 Hash
# Credits

This challenge originated from @miles.

---

Create a function that computes the CRC32 hash of an input string. The input will be an ASCII string of any length. The output will be the CRC32 hash of that input string.

# Explanation

The algorithm of CRC32 and other CRC are essentially the same, so only CRC3 will be demonstrated here.

Firstly, you have the generator polynomial, which is actually a 4-bit \[n+1\] integer (would be 33-bit in CRC32).

In this example, the generator polynomial is `1101`.

Then, you will have the string to be hashed, which in this example would be `00010010111100101011001101`.

```
00010010111100101011001101|000 (1)    append three [n] "0"s
   1101                        (2)    align with highest bit
00001000111100101011001101|000 (3)    XOR (1) and (2)
    1101                       (4)    align with highest bit
00000101111100101011001101|000 (5)    XOR (3) and (4)
     1101                      (6)    align with highest bit
00000011011100101011001101|000 (7)    XOR (5) and (6)
      1101                     (8)    align with highest bit
00000000001100101011001101|000 (9)    XOR (7) and (8)
          1101                 (10)   align with highest bit
00000000000001101011001101|000 (11)   XOR (9) and (10)
             1101              (12)   align with highest bit
00000000000000000011001101|000 (13)   XOR (11) and (12)
                  1101         (14)   align with highest bit
00000000000000000000011101|000 (15)   XOR (13) and (14)
                     1101      (16)   align with highest bit
00000000000000000000000111|000 (17)   XOR (15) and (16)
                       110 1   (18)   align with highest bit
00000000000000000000000001|100 (19)   XOR (17) and (18)
                         1 101 (20)   align with highest bit
00000000000000000000000000|001 (21)   XOR (19) and (20)
^--------REGION 1--------^ ^2^

```

The remainder obtained at `(21)`, when region 1 is zero, which is `001`, would be the result of the CRC3 hash.

# Specs

* The generator polynomial is `0x104C11DB7`, or `0b100000100110000010001110110110111`, or `4374732215`.
* Input can be a string or a list of integers, or any other reasonable format.
* Output be a hex string or just an integer, or any other reasonable format.
* Built-ins that compute the CRC32 hash are not allowed.

# Goal

Standard rules for apply.

The shortest code wins.

## Test cases

```
input         output      (hex)
"code-golf"   147743960   08CE64D8
"jelly"       1699969158  65537886
""            0           00000000

```

# Answer
# Intel x86, ~~34~~ ~~30~~ ~~29~~ 27 bytes

Takes the address of the zero-terminated string in ESI, and returns the CRC in EBX:

```
31 db ac c1 e0 18 74 01 31 c3 6a 08 59 01 db 73
06 81 f3 b7 1d c1 04 e2 f4 eb e7

```

**Disassembly (AT&T syntax):**

```
00000000    xorl    %ebx, %ebx
00000002    lodsb   (%esi), %al
00000003    shll    $24, %eax
00000006    je      0x9
00000008    xorl    %eax, %ebx
0000000a    pushl   $8
0000000c    popl    %ecx
0000000d    addl    %ebx, %ebx
0000000f    jae     0x17
00000011    xorl    $0x4c11db7, %ebx
00000017    loop    0xd
00000019    jmp     0x2
0000001b

```

Incorporating suggestions from Peter Cordes to save four more bytes. This assumes a calling convention where the direction flag for string instructions is cleared on entry.

Incorporating suggestion of Peter Ferrie to use push literal and pop to load a constant, saving one byte.

Incorporating suggestion of Peter Ferrie to jump to the second byte of an `xorl %eax, %ebx` instruction which is a `retl` instruction, combined with changing the interface of the routine to take a zero-terminated string instead of length, saving two bytes in total.
> 12 votes

# Answer
# Jelly, 34 bytes

```
l2_32Ḟ4374732215æ«^
Oḅ⁹æ«32Çæ»32$¿

```

Try it online!
> 4 votes

# Answer
# Ruby, 142 bytes

Anonymous function; takes a string as input, returns an integer.

```
->s{z=8*i=s.size;r=0;h=4374732215<<z
l=->n{j=0;j+=1 while 0<n/=2;j}
s.bytes.map{|e|r+=e*256**(i-=1)};r<<=32
z.times{h/=2;r^=l[h]==l[r]?h:0}
r}

```
> 4 votes

# Answer
# Jelly, 23 bytes

```
ḅ⁹Bµ4374732215B×ḢḊ^µL¡Ḅ

```

Input is in form of a list of integers. Try it online! or verify all test cases.

### How it works

While Jelly has bitwise XOR, padding the input with zeroes and aligning the polynomial with the most significant binary digit makes this approach, which uses lists of bits instead, a tad shorter.

```
ḅ⁹Bµ4374732215B×ḢḊ^µL¡Ḅ  Main link. Argument: A (list of bytes)

ḅ⁹                       Convert A from base 256 to integer.
  B                      Convert the result to binary, yielding a list.
   µ                     Begin a new, monadic chain. Argument: B (list of bits)
    4374732215B          Convert the integer to binary, yielding a list.
                Ḣ        Pop and yield the first, most significant bit of B.
               ×         Multiply each bit in the polynomial by the popped bit.
                 ^       Compute the element-wise XOR of both lists.
                         If one of the lists is shorter, the elements of the other
                         lists do not get modified, thus avoiding the necessity
                         of right-padding B with zeroes.
                  µ      Convert the previous chain into a link.
                   L¡    Execute the chain L times, where L is the number of bits
                         in the original bit list.
                     Ḅ   Convert from binary to integer.

```
> 4 votes

# Answer
# Pyth, 42 bytes

```
?!Q0h<#^2 32.uxN.<4374732215.as-lN32.<CQ32

```

Test suite.
> 3 votes

# Answer
## CJam, ~~37~~ 36 bytes

```
q256b32m<{Yb4374732215Yb.^Yb_Yb32>}g

```

Test it here.

### Explanation

```
q               e# Read input.
256b            e# Convert to single number by treating the character codes
                e# as base-256 digits.
32m<            e# Left-shift the number by 32 bits, effectively appending 32
                e# zeros to the binary representation.
{               e# While the condition on top of the stack is truthy...
  Yb            e#   Convert the number to base 2.
  4374732215Yb  e#   Convert the polynomial to base 2.
  .^            e#   Take the bitwise XOR. If the number is longer than the
                e#   polynomial, the remaining bits will be left unchanged.
  Yb            e#   Convert the list back from base 2, effectively stripping
                e#   leading zeros for the next iteration.
  _             e#   Duplicate the result.
  Yb            e#   Convert back to base 2.
  32>           e#   Remove the first 32 bits. If any are left, continue the loop.
}g

```
> 3 votes

# Answer
# Pyth, 28 bytes

```
uhS+GmxG.<C"Á·"dlhG.<Cz32

```

Try it online: Demonstration or Test Suite

### Explanation:

```
uhS+GmxG.<C"..."dlhG.<Cz32   implicit: z = input string
                      Cz     convert to number
                    .<  32   shift it by 32 bits
u                            apply the following expression to G = ^,
                             until it get stuck in a loop:
     m           lhG            map each d in range(0, log2(G+1)) to:
          C"..."                   convert this string to a number (4374732215)
        .<      d                  shift it by d bits
      xG                           xor with G
   +G                           add G to this list
 hS                             take the minimum as new G

```
> 3 votes

# Answer
## JavaScript (ES6), 180 bytes

```
f=(s,t=(s+`\0\0\0\0`).replace(/[^]/g,(c,i)=>(c.charCodeAt()+256*!!i).toString(2).slice(!!i)))=>t[32]?f(s,t.replace(/.(.{32})/,(_,m)=>(('0b'+m^79764919)>>>0).toString(2))):+('0b'+t)

```

The lack of a 33-bit XOR operator, or even an unsigned 32-bit XOR operator, is unhelpful.
> 2 votes

# Answer
# CJam, 33 bytes

```
q256bYb_,{(4374732215Ybf*1>.^}*Yb

```

Input is in form of a string. Try it online!

### How it works

```
q                                  Read all input from STDIN.
 256bYb                            Convert it from base 256 to base 2.
       _,{                   }*    Compute the length and repeat that many times:
          (                          Shift out the first bit.
           4374732215Yb              Convert the integer to base 2.
                       f*            Multiply each bit by the shifted out bit.
                         1>          Remove the first bit.
                           .^        Compute the element-wise XOR of both lists.
                                     If one of the lists is shorter, the elements
                                     of the other lists do not get modified, thus
                                     avoiding the necessity of right-padding B with
                                     zeroes.
                               Yb  Convert the final result from base 2 to integer.

```
> 1 votes

---
Tags: code-golf, bitwise, hashing
---


title: Is this uniquely concatenable?

text:
# Question
Title: Is this uniquely concatenable?
In this challenge about prefix code, we learnt that prefix codes are uniquely concatenable.

That means, they can be joined together without separator, and without ambiguity.

For example, since \[1,2,45\] is a prefix code, I can join them together without separator as such: 1245245112145, and there will be no ambiguity.

However the converse is not always true.

For example, \[3,34\] is not a prefix code. However, I can do the same: 3333434334333, and there will be no ambiguity. You would just need a smarter parser.

However, \[1,11\] is not uniquely concatenable, because 1111 can be interpreted in 5 ways.

# Goal

Your task is to write a program/function that takes a list of strings (ASCII) as input, and determine if they are uniquely concatenable.

# Details

Duplicate counts as false.

# Scoring

This is . Shortest solution in bytes wins.

# Testcases

True:

```
[12,21,112]
[12,112,1112]
[3,4,35]
[2,3,352]

```

False:

```
[1,1]
[1,2,112]
[1,23,4,12,34]
[1,2,35,4,123,58,8]

```

# Answer
> 5 votes
# 05AB1E, 15 bytes

On the phone, so explanation will have to follow later. Code:

```
gF¹N>ã})€`€JDÚQ

```

Uses **CP-1252** encoding. Try it online!.

Takes too much memory for the last test case, so that might not work...

# Answer
> 4 votes
## CJam (54 bytes)

```
q_N/:A\,{_Am*:${~1$,<=},{~\,>}%La:L-}*A,A_&,-A*](\M*&!

```

Takes input on stdin as newline-separated list.

Online demo

If we didn't have to handle duplicate codewords, this could be shortened to 44:

```
q_N/\,{_W$m*:${~1$,<=},{~\,>}%La:L-}*](\M*&!

```

Or if CJam had an array subtraction which only removed one item from the first list for each item in the second, it could be 48...

### Dissection

This is the Sardinas-Patterson algorithm but de-optimised. Since each dangling suffix only comes up at most once, running the main loop as many times as there are characters in the input (including separators) guarantees to be sufficient.

Note that I had to work around what is arguably a bug in the CJam interpreter:

```
"abc" "a" #   e# gives 0 as the index at which "a" is found
"abc" "d" #   e# gives -1 as the index at which "d" is found
"abc" ""  #   e# gives an error

```

So the prefix check is complicated to `1$,<=` instead of `\#!`

```
e# Take input, split, loop once per char
q_N/\,{
  e# Build the suffixes corresponding to top-of-stack and bottom-of-stack
  _W$m*
  e# Map each pair of Cartesian product to the suffix if one is the prefix of the other;
  e# otherwise remove from the array
  :${~1$,<=},{~\,>}%
  e# Filter out empty suffixes iff it's the first time round the loop
  La:L-
}*
e# If we generated an empty suffix then we've also looped enough times to generate all
e# of the keywords as suffixes corresponding to the empty fix, so do a set intersection
e# to test this condition.
](\M*&!

```

---
Tags: code-golf
---