Easy programming puzzle

[WhiteCube]

Variables X and Y hold integers.

Swap the values of X and Y without using a third variable.

Spoiler: one answer

X=(X xor Y)
Y=(X xor Y)
X=(X xor Y)

 

[VBService]

X = X + Y  # Now X holds the sum of X and Y
Y = X - Y  # Subtract Y from the sum, so Y becomes the original X
X = X - Y  # Subtract the new Y (original X) from the sum, so X becomes the original Y

[ working code on-line ]

X = -5
Y = 2

print(f"X = {X}, Y = {Y}")

X = X + Y  # Now X holds the sum of X and Y
Y = X - Y  # Subtract Y from the sum, so Y becomes the original X
X = X - Y  # Subtract the new Y (original X) from the sum, so X becomes the original Y

print(f"X = {X},  Y = {Y}")

 

[WhiteCube]

Code breaking, on the back of an envelope.

I'm using the RSA algorithm, but I'm not using large primes.

My public key is 291. The encoding/decoding uses modulo 391.

What's my private key?

Spoiler: The answer

75

 

[VBService]

IMHO,

Using the sympy library makes this task easy to solve, even for someone new to code-breaking. Here's a simple python program to find the private key.
The RSA algorithm usually relies on large prime numbers,

I'm using the RSA algorithm, but I'm not using large primes

but here we have small values that are easier to work with.
To find the private key:

1. We factorize n=391 to get p and q.
2. Using these, we calculate ϕ(n).
3. Finally, we find the modular inverse of the public key e=291 with respect to ϕ(n), which gives us the private key d.

[ working code on-line ]

import sympy

# Given values
n = 391
e = 291

# Step 1: Factorize n to find p and q
factors = sympy.factorint(n)
p, q = factors.keys()

# Step 2: Calculate φ(n) = (p - 1) * (q - 1)
phi_n = (p - 1) * (q - 1)

# Step 3: Find the modular inverse of e modulo φ(n) to get d
d = sympy.mod_inverse(e, phi_n)

# Print the results
print(f"Factors of n: p = {p}, q = {q}")
print(f"φ(n) = {phi_n}")
print(f"Private key d = {d}")

 

[WhiteCube]

Nice.
There is another way.

Spoiler: hint

encode, decode, test, repeat

 

[WhiteCube]

The funny thing that pops up when breaking this code by brute force is I found more than one solution.

 75 291
115 251

115 and 251 are inverses and work as key pairs, as expected.

75 and 115 are not inverses, but they do work as key pairs.

291 and 251 work together too.

I can't explain that.

 

[WhiteCube]

I have 32 important files, all the same length.

A person deletes one of my files.

I restore the missing file, without using a backup copy or an undelete command.

How did I do that?

Spoiler: answer

One of my files contains nothing but parity bits.

 

[WhiteCube]

More fun with parity.

I can have 256 equal length files, and I want to be able to restore them if any 2 get deleted.

How many of the files need to be parity files?

Spoiler: one way

I can do it with 9. Can anyone do it with less?

 

[WhiteCube]

Simulate randomly throwing 20 rocks into 5 buckets.

pseudocode

function zork()
  return a random number from 0 to 4

procedure sim()
  define buckets as an array of 5 integers
  initialise buckets to all 0
  loop 20 times
    buckets[zork()] += 1
  end loop
  print buckets

buckets should always add up to 20, it does not, sometimes its over 20, sometimes its under.

What's wrong with my logic?

Spoiler: answer

buckets[zork()] += 1
was interpreted as

buckets[zork()] = buckets[zork()] + 1
2 random numbers, not 1

 

[WhiteCube]

Here's a surprisingly low number.

Not counting rotations and reflections, how many tic-tac-toe boards are draws?

Spoiler: answer

3

 

[WhiteCube]

I found those draw boards by mistake.

I was reading one of the stack exchange forums and someone couldn't get their tic-tac-toe program fast enough to search down to a reasonable depth.

I thought, that can't be right. So I wrote a ttt program to see how complicated the game is.

Turns out I misread the question, it was talking about "Ultimate" tic-tac-toe, which has a larger board and more rules.

I assumed when the poster wrote "my ultimate tic-tac-toe program" they were just being overly descriptive.

 

[WhiteCube]

I didn't find this easy, it took me over a day, and lots of coffee.

Given that ^ means "to the power of" and % means "modulo",

if v != 0 and s > 0 and n is a large number, are these two programs equivalent?

p = true
IF (v != 1)
  i = 0
  WHILE ((v != n-1) AND p)
    IF (i == s-1)
      p = false
    ELSE
      i = i + 1
      v = (v^2) % n
PRINT p

p = true
FOR i = 1 TO s
  y = (v^2) % n
  IF (y == 1 AND v != 1 AND v != n-1)
    exit FOR loop
  v = y
IF (v != 1)
  p = false
PRINT p

Spoiler: answer

yes