My old programming problem

submitted by fschmidt from self.programming

Back before programmers were scum, I hired programmers based on intelligence. When they applied for a job, I gave them this problem. The indented text is mine. Roughly 1% of applicants solved it. Programmers from all backgrounds and all races solved it. The only category that never solved it is women.

all 25 comments
sorted by:
top
newinsightfulfun

[–]Vulptex 2 insightful - 2 fun2 insightful - 1 fun3 insightful - 2 fun -  (2 children)

How many of the women actually attempted it? I've noticed a lot of them bail out the second they see something that looks complicated. Maybe most people just don't like complicated things unless they're pressured into them, which men certainly are.

[–]fschmidt[S] 2 insightful - 2 fun2 insightful - 1 fun3 insightful - 2 fun -  (1 child)

How many of them women actually attempted it?

I don't know.

[–]Vulptex 1 insightful - 2 fun1 insightful - 1 fun2 insightful - 2 fun -  (0 children)

I know one whom this problem would probably be trivial for.

[–]ID10T 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 1 fun -  (9 children)

This was a super fun one to solve. My solution in Python: https://replit.com/@lolatu/Card-Shuffle-Problem?v=1

Includes the naive solution for comparison, which times out for 1002, 101.

[–]fschmidt[S] 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 1 fun -  (8 children)

Correct. But these days values are more important than intelligence. One has to reject modern values to be a good programmer or to be good at anything.

[–]ID10T 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (7 children)

Haha, I don't know what that means. What are "modern values" that are incompatible with good programming?

I've worked with many good programmers over the years, and many more shit ones. In general I'm happy that modern conventions like having scripted infrastructure builds, automated CI deployment with automated testing, everything in repositories, etc... over the old ways, of some greybeard having the only keys to the castle, and generally slowing down everything.

[–]fschmidt[S] 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (6 children)

Well I don't know what that means. What is "CI" and why do modern people use meaningless acronyms for everything? What is an "infrastructure build"? I write programs, not infrastructure. My applications are in Luan so there is nothing to build. All the code is in Mercurial, of course. Releasing it is just a command in the shell which pushes the code to the server. Why is anything else needed?

[–]ID10T 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (5 children)

Lol ok. The benefits of writing infrastructure as code are massive. Last place I worked at, had some asshole who took 3 days to build a new server from scratch whenever we needed to scale our platform. I wrote scripts to build all our infrastructure, and scaling to meet traffic surges became as easy as a few button clicks. You ever deal with load balanced server clusters? Lambdas? Cloud networking? You have an application that has 10k requests per second on a given API endpoint, you have to deal with that.

[–]fschmidt[S] 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 1 fun -  (4 children)

So by "infrastructure" you just mean setting things up to run? Look at my Mercurial hosting service and look at its source. This includes Luan code and Nginx configuration. Just clone the repo and run the "update.sh" script and everything is configured. So is this a "scripted infrastructure build"?

[–]ID10T 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (3 children)

Sure, if your infrastructure consists of a single server, that would be most of it. Obviously it can get massively more complex if you're building a large platform like Twitter.

Like here's a quick tutorial on setting up an Elastic Container Service that connects to MySQL RDS on AWS with Terraform (sorry about the acronyms lol): https://medium.com/warp9/get-started-with-aws-ecs-cluster-using-terraform-cfba531f7748

Note that it configures all the networking on AWS, putting the containers in a Virtual Private Cloud, configuring security groups, etc...

Working on larger platforms, it's mandatory that there is little to no manual configuration of anything. As when shit goes south and needs to be rebuilt, you have to be able to do it quickly, and can't rely on what's in the brain of 1 or 2 devops engineers. The bus factor alone makes scripting your infrastructure a necessity.

[–]fschmidt[S] 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (2 children)

Obviously it can get massively more complex if you're building a large platform like Twitter.

How many programmers deal with this level of scale? At least 90% of cases are fine with a single server in which case the effort to get down to zero manual configuration isn't worth it.

[–]ID10T 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (0 children)

Not sure what the percentage is. I've had to deal with a pretty massive scale at the last two companies I was at, over ten years now. I think as builders of things, we all hope that our things will become popular. If they do, then you have to be able to scale to meet the demand.

It's been really fun learning how to build an application that can handle tens even hundreds of thousands of requests a second. It's perhaps not a common challenge for most, but it's wild to set up a whole infrastructure that can do that and see it working is highly satisfying.

[–]jingles 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (0 children)

I used to write my websites in C language.

Twitter is not a complicated website.

[–]HeyBobby 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (2 children)

Pretty simple problem. Programmers must not have been good back then. This is like a level 5 codewars practice exercise.

[–]fschmidt[S] 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (1 child)

The brute force simulation approach takes too long, or at least it did back then. So one has to find a better approach than just simulating shuffles.

[–]Vulptex 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (0 children)

I mean the simulation approach could be used to lead you to the faster solution.

[–][deleted] 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (2 children)

What number did you get ?

This is classical combinatorics. No programming needed whatsoever.

It is solvable with a pencil and some estimates of multinomials.

[–]fschmidt[S] 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (1 child)

If it is so easy then you solve it. The last 3 digits of the solution is "600".

[–][deleted] 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (0 children)

I didn't state that it is easy. I'm well known for erroneous calculations. That is why I proposed to rather put a good estimate on it.

But since a lot of task on ProjectEuler are very similar, I'd rather see people looking into the math than simply brute-forcing it.

[–]trident765 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (6 children)

This problem has no solution. The cards added to the top of the deck makes the shuffling of one size deck too different from the other. So there is no pattern that can be observed and exploited.

Of course, I am sure a Silicon Valley scum will be able to solve this by applying some bizarre mathematical trick. But knowledge of these mathematical tricks has little use in the real world.

I had a friend who was good at solving these types of problems but he a dumbass when it came to common sense. First he lost a bunch of money by investing in obscure cryptocurrencies. And when psychopaths took over my department at work he was completely oblivious to what was happening. He embraced liberalism with all his heart, and believed that those who spread disinfo about the vaccine are a threat to society.

[–]fschmidt[S] 1 insightful - 1 fun1 insightful - 0 fun2 insightful - 1 fun -  (5 children)

Of course there is a solution. And while a little math is needed, the core insight isn't mathematical.

This problem served me well while western culture was still sane. I got good programmers by using it. But it is no longer useful because the main issue with programmers now is values, not out-of-the-box thinking.

[–]trident765 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 1 fun -  (3 children)

Ok I solved it by recognizing that the result of shuffling n times is the mapping indices to perform n shuffles. So I precomputed the first n shuffles (I used 400000 for n), and then bulk shuffled the fast way that I just described until I got a result that was in the precomputed shuffles.

[–]fschmidt[S] 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 1 fun -  (2 children)

What answer did you get? If the answer is 400001 then how would you find it?

[–]trident765 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 1 fun -  (1 child)

I got 5812104600.

If the answer is 400001 then how would you find it?

After the 2nd bulk shuffle the deck would be at the 800000th shuffle. If the answer is 400001, then the 800000th shuffle will be identical to the 399999th shuffle, so I will find the 800000th (399999th) shuffle in the precomputed table, and then this would tell me to subtract 800000 - 399999 = 400001.

Here is my code:

https://pastebin.com/YTjL9d1i

[–]fschmidt[S] 2 insightful - 1 fun2 insightful - 0 fun3 insightful - 1 fun -  (0 children)

I see. My solution is different. Each card follows some path through the deck and returns to its original position. Each card in a path takes the same number of shuffles to return to its original position. So the solution is the least common multiple of the lengths of all the paths in the deck.

local Luan = require "luan:Luan.luan"
local error = Luan.error
local range = Luan.range or error()
local Math = require "luan:Math.luan"
local min = Math.min or error()
local Number = require "luan:Number.luan"
local long = Number.long or error()
local Io = require "luan:Io.luan"
local print = Io.print or error()

local function lcm(x,y)
    local rtn = x
    while rtn % y ~= 0 do
        rtn = long(rtn + x)
    end
    return rtn
end

local function shuffles(n_cards,i_cut)

    local map = {}
    do
        local n = min( i_cut, n_cards - i_cut )
        for i in range( 0, n - 1 ) do
            local j = n_cards - 2*i
            map[ i_cut - i ] = j
            map[ n_cards - i ] = j - 1
        end
        if n == i_cut then
            for i in range( 1, n_cards - 2*i_cut ) do
                map[ i_cut + i ] = i
            end
        else
            for i in range( 1, i_cut - n ) do
                map[i] = i
            end
        end
    end

    local a = {}
    for i in range(1,n_cards) do
        a[i] = true
    end

    local rtn = 1
    for i in range(1,n_cards) do
        if a[i] then
            local n = 0
            local j = i
            while a[j] do
                a[j] = false
                n = n + 1
                j = map[j]
            end
            rtn = lcm(rtn,n)
        end
    end
    return rtn
end

print( shuffles(1002,101) )