Project Euler / programming problems

Vsotvep · April 12, 2022, 3:29pm

My key is

471207_Uzvdv1PUUyckzGr8xIS40Sdz3yeoiiA5

I can’t promise I’ll become active again, but at least I just solved 50 in python (mainly because I want to get those first 50 done now).

shinuito · April 12, 2022, 3:32pm

I’ve just been doing them as they came up in the thread. So I’ve only the first 10 done.

If anyone active has the first 40+ solved, I don’t suppose they would want to keep going in order really?

I’m not sure if @_zaki @bugcat @esoka etc would want to come back to continue on in order.

bugcat · April 12, 2022, 3:33pm

Ah, I went MIA a bit >w<

shinuito · April 12, 2022, 3:36pm

If you stopped at 7? I’m only a few ahead really. It probably wouldn’t take too long to catch up and move onto 11 say

yebellz · April 12, 2022, 3:39pm

Those both seem a bit more tedious than mathematically interesting. I’ve been putting those off mainly because of that.

Some thoughts

I guess the most straightforward way to tackle Monopoly is just random simulation of enough rolls until the order of the top-3 likelihoods seems to have converged. However, the most tedious thing is coding up all of the rules about cards and board movement.

Another approach could be to calculate the steady-state probabilities of the Markov given the transition probabilities implied by the dice rolling and card rules. However, again its tedious to deal with coding up the transition probabilities. It seems that the proper handling of the state space involves the combination of both the board position and the states of each deck, however, I imagine that ignoring the deck state (and just assuming a random shuffle before each card draw) and reducing it to just caring about board state might be accurate enough. Technically, tracking dice state might also matter, but maybe it’s also a reasonable approximation to ignore that.

I’m guessing that the final answer will still have Jail and Go in the top-3.

About Sudoku, I guess it’s no harder than coding up a Sudoku solver, potentially needing the guess and check method for some problems, but a shortcut is just to quit as soon as the first top-left 3 digits are solved, and also focus on guess and check on that region first.

As a fall back, a simple first-order logic solver could probably get the top-left 3 digits solved for many of the problems and partially solve enough of the rest to just manually finish those. I guess coding a partial solver and then partially solving less than 50 remaining sudoku puzzles by hand is not too much effort. Maybe a hybrid approach is actually the fastest (in terms of real elapsed time, including coding time) way to get to the solution.

antonTobi · April 12, 2022, 3:39pm

Some of the earlier ones I don’t mind doing again, since it was many years ago I did them the first time and it could be fun to try it with a new language and/or new techniques.

bugcat · April 12, 2022, 3:40pm

How about “community programming problems”?

We all create problems ourselves, throw them into a hat and pick them out randomly.

yebellz · April 12, 2022, 3:41pm

We did a little bit of that above

yebellz:

Project Anton #1

The below Python 3 code demonstrates a log-sum-exp approximation for multiplication, which is precise for reasonably-sized integer values a and b. That is, the final expression often evaluates as True for “not too large” integers a and b.
import math
a, b = 6, 7
round(math.exp(math.log(a) + math.log(b))) == a * b
For large enough positive integer values of a and b, the above approximation becomes inaccurate. What is the smallest product a * b for which the last line of the above code evaluates as False?

Note: this question assumes Python 3.X and depends on the exact behavior of the math library. If the specific version makes a difference, please specify in your answer.

shinuito · April 12, 2022, 3:42pm

I think the main problem is coming up with problems that are actually do-able.

The ones that might sound interesting usually aren’t doable

I’ve heard of a place possibly related to this forum, which has some open programming type problems one could look into

Something about putting black and white stones on a grid.

(the joke had to be made )

antonTobi · April 12, 2022, 3:46pm

I suggested 2 problems early on in this thread, which I think are a similar level to the early Project Euler problems

benjito · April 12, 2022, 6:23pm

I love it when interesting math problems pop up in real-life dev.

Here’s one that came up recently:

Write a injective mapping from board positions => natural numbers such that:

fewer stones on the board map to smaller numbers.
The max value in the range should be minimized (soft requirement, but maybe <3^361 is a good number to aim for).

I don’t think it’s that hard mathematically compared to EP, but you do get to flex the combinatorics muscles.

Vsotvep · April 12, 2022, 6:42pm

How does that relate to real-life dev?

Mathematically it’s quite trivial to create the mapping. If there are N_k board positions with k stones, then the fact that I know there exist that many board positions means I have a bijection between the set

{0, 1, … , N_k-1}

and the board positions. So, you just send the n-th board position with k stones to

n + ∑_i<k N_i.

The question is really asking how many board positions there are.

Programmatically, another solution is to first figure the total number of board positions, then create an enumeration, and use some sorting algorithm of your choice to sort the numbers.

yebellz · April 12, 2022, 6:49pm

Solution

52631578947368421

Code

nines = 9
while nines % 19:
    nines = 10 * nines + 9
print(nines // 19)

Solution

1480

Code

pairs = [(3, 4), (6, 8), (9, 12), (12, 16), (5, 12), (8, 15)]
count = 0
for x, y in pairs:
    count += 2 * (20 - x) * (20 - y)
print(count)

yebellz · April 12, 2022, 6:59pm

The number of legal 19x19 board positions has been precisely computed: Counting Legal Positions in Go

Mathematically, it’s straightforward to implicitly define this bijection function. Sort all board positions first by number of stones, and then by the ternary number represented by the stones.

In practice, I think that it might be intractable to implement some code that takes a legal board position as input and precisely computes the value of the minimal bijection function. On the other hand, it’s trivial to design some code to compute non-minimal bijection functions.

I wonder how this sort of challenge came up in real-life for @benjito.

benjito · April 12, 2022, 9:38pm

Joseki deduping!

shinuito · April 12, 2022, 9:50pm

Right so you take a joseki sequence and you’d like to map it to an integer which would conveniently show up in a url for example.

The fact you can forget the history, and just map from the board position is also convenient for merging any branches.

Seems interesting

antonTobi · April 12, 2022, 10:10pm

Nice!

But shouldn’t it be like this?

pairs = [(3, 4), (6, 8), (9, 12), (12, 16), (5, 12), (8, 15)]
count = 0
for x, y in pairs:
    count += 4 * (19 - x) * (19 - y)
print(count)

(I also see you didn’t count the boring grid-parallell ones, but I’ll allow it since it makes the solution cleaner )

antonTobi · April 12, 2022, 10:18pm

Also, follow-up math problem to the first one:

Let N be any natural number that is not divisible by 2 or 5. Does there always exist a natural number K such that N * K contains only ones?

For example if N = 13 we have K = 8547 since 13 * 8547 = 111111.

(this doesn’t really fit in the thread since it doesn’t involve programming, but I’ve only half-solved this one myself so interested to see how someone else solves it)

yebellz · April 12, 2022, 11:57pm

Whoops

Oh, you’re not using a board with 19x19 squares?

I was counting distinct pairs, so 1-1 and 4-5 is the same as 4-5 and 1-1.

Ha, I completely forgot about those…

antonTobi · April 13, 2022, 12:04am

Spoilers

Me too

Here is an image showing the 4(5-3)(5-4) = 8 different ways of putting a (3, 4) distance on a 5*5 board: