/dpt/ - Daily Programming Thread

There are literally no female C programmers anywhere on Earth.

26-year-old virgin here. Also, on my objective opinion, Java > C#.

I'm a female, and I identify as a C-programmer.

I taught C to my girlfriend :)

Attached: 1537657358312.png (700x700, 189K)

>t. never talked to a girl

How the fuck did you do that?

>C-3.3 Let A be an array of size n ≥ 2 containing integers from 1 to n−1, inclusive, with exactly one repeated. Describe a fast algorithm for finding the integer in A that is repeated.

My solution is worst case n^2 and is kind of brute force, I take it that's not what the author means by "fast"?

>n^2
Pathetic. You could even sort the array in n log n, and get the duplicate from that. He's looking for O(n) solution, and you can get that very simply with hashes.

The book hasn't yet covered hashes ;_;

That is objective and correct. Try building anything bigger than a email server in C#. Lmao.

hashing would also require linear space complexity, as opposed to sorting.
that being said, OP, there's a faster way because the array contains n integers 1 to n-1 and only exactly one is repeated. does the sum of the elements in that array contain any relevant information?

to add to this, you don't really need "hashing" for the solution with linear space complexity, you just build a counting array A of size N and count in A[i-1] for every number i. but, again, there's a better solution.

Okay I will :)

Ok thank you for the advice, I will give it some thought.

so subtract actual sum vs expected sum

Oh yeah, you're right. You could just count the sum and subtract n * (n - 3) / 2 from it. I didn't notice the integers being restricted in size. Oh well, it's linear time, same as the hash solution.

27 y/o kissless virgin reporting in
This years prospect: loss of virginity

nah
you can do this in O(n) and O(1)
what is the sum of the integers from 1 to n-1?

well it's (n-1)*(n-2)/2

call it s = (n-1)*(n-2)/2
while the sum of the elements in the array will be (n-1)*(n-2)/2 + x
where x is the repeated element

O(n) space O(1) time

easy and if any integers are skipped, subtract as you go along

Learning mysql and trying to practice. I made up a small chat system and got a problem of concurrency insert into. Any good reading about the subject and how it can be solved ?

obviously i mean O(n) time and O(1) space

It's O(n) in both. You can't read all the integers in constant time.

Let me know when you build a distributed computing framework in C# that rivals the likes of Spark and Hadoop.

Our university is recommending a textbook by Savitch entitled "An Introduction to Problem Solving & Programming" for the undergraduate course which focuses on Java.

I've purchased it, and I am waiting for delivery, I am also working through the first three chapters of SICP. The other books recommended were "How To Design Programs" and "Concepts, Techniques, and Models of Computer Programming" however for something language specific to Java; I am curious if there is something more worth reading?

Could someone kindly recommend me any Java books they have found useful? I am a novice programmer, but I would like to better myself.

I don't think MySQL has any issues with concurrency.

Clever.

Not really a programming problem so much as a math problem though.

>Not really a programming problem so much as a math problem though.
Same thing.

I thought it would be fun to make some edits to QuasarRAT, so yea

sum(int *a, int n)
is constant time ;)
O(INT_MAX) = O(1)

you don't really need any math for this, it's just basic problem solving.
you don't even need the closed formula for the sum of an integer interval to maintain linear time complexity, you could also just sum up the numbers between 1 and n-1 yourself.

That's weird, cause when I sent a message at the same time a friend send it, one of them disappeared. Maybe the bug is somewhere else ? I'll try to monitor that and see if it happens again

Not really.

>Maybe the bug is somewhere else ?
In your code, yes. MySQL is well-established enough to have a very stable support for concurrent calls. Otherwise web pages would crash all the time.

it's O(1) in space
you start with a sum from 1 to n and subtract until the result is the repeated integer

[1, 5, 8]

and n is 9
the sum will be sum(0 to 9)

for the skipped integers you'd run a for loop
for example from 5 to 8 and from 1 to 4

overall time complexity is O(n)
space is O(1)

i just realized though, O(1) space probably requires the integers to be sorted though, which actually means you'd have to do O(nlogn) time anyways, so might as well SORT and ignore thinking about sums

lol

The clever trick is the mathematical insight to sum the number and the difference between the sum and the expected sum with no repetition is the repeated number.
Obvious once you've heard it but I wouldn't have thought of it.

That^ is my reply to the outliner 'challenge' posted v
For anyone to critique

Python is for people who are unable to learn programming.

why would you need to sort when the final sum and final answer requires no info about the order of the numbers

how is that a bad thing

did this one:
github.com/precla/iuvui

might add some graph or any kind of visualization for the current power consumption that gets read via 'intel-undervolt measure'

there's another purely algorithmic solution to this with constant space and linear time complexity that i can think of. can you guys figure it out?

skipped integers
array contains integers from 1 to n-1
not ALL integers from 1 to n-1

there's n integers from 1 to n-1 and only exactly one repeated. which integer are you gonna skip, huh?

>Let A be an array of size n ≥ 2 containing integers from 1 to n−1, inclusive, with exactly one repeated.
let's say n-1 is 5
doesn't that mean that you can have array
[1,4,4,5]
and not
[1,2,3,4,4,5]
4 is repeated in both
it also says n>= so it can be anywhere between 2 and n-1 in size

ah, but you can probably loop from 1 to n-1 anyway and keep a missingSum variable or something

in the end you'll still get the missing element
ExpectedSumWithoutRepetitions - missingSum + MISSINGELEMENT = SumWithRepetitions

yeah O(n) anyway, i'll just test it in puthon

Your issue will be scaling, take a buttfucking using windows servers, or take a bit Fucking running gnu Linux and having to run your code in vms, unless you write it all in .net core then you could start to build something big if you so desire but why not just use java at that point

me too

you can't have [1, 4, 4, 5] since our array has size n = 6.

>it also says n>= so it can be anywhere between 2 and n-1 in size
that's not what this means.

i'll provide a hint since i gotta leave soon: we've got an array of size N and only exactly one element is repeated, so when we apply bucket sort, which is possible because of the 1...N-1 requirement, our buckets only have size 1, or we've already found the duplicate ...
now, how to adjust bucket sort to achieve constant space complexity?

what is it
also does it take into account skipping integers, because that's actually what the text of the exercise is

C how to program, covers basic data structures, how programs compile, how memory is store, good to know stuff

>now, how to adjust bucket sort to achieve constant space complexity?
you can't

this is why math is for fags and trannies, missing a small detail like this will fuck you over and the solution always requires some dumb little gimmick

You could do a counting sort. That can be done in linear time, but also requires linear space. That's the best I got.

sum(A) - ((n-1)(n-2)) / 2

O(n) time, O(1) space

ok this doesn't actually work if the input has skipped integers, which the text of the question clearly permits
you can also use product(A)/(n-1)!
this doesn't work if you read the exercises correctly
but i assume it's what they meant

i wish they'd just said "containing THE integers from 1 to n-1 inclusive" and not "containing integers from 1 to n-1"

fucking author writes a book and can't even express himself unequivocally

there are no skipped integers, get that nonsense out of your head. here's a quick proof:
A contains n elements, with exactly one repeated.
this means that n-1 elements of A have to be unique, otherwise we'd have more repetitions.
since we've only got unique integers 1 to n-1 available, our n-1 unique integers are exactly 1 to n-1.
there are no skipped integers.
this is literally the most basic application of the pigeonhole principle that one can think of, jesus christ.

math is for fags and trannies because you're too fucking stupid to read, gotcha. don't they teach you that shit in school? ain't got nothing to do with math.

sure you can, think harder.

for a linear space complexity, you need to re-use the array that you've already got. maybe that helps, together with the other hints?

>fucking author writes a book and can't even express himself unequivocally
it's unequivocal, you dumb fuck.

Yeah I'm retarded, it's n(n-1). All of [n,n-1] is there though based on the problem statement, since only one element is repeated.

let's discuss stuff on kotchan.org/chat/int which is opensource btw

neither bucket nor radix sort can be done in O(1) space

if you could, they'd be known as inplace sorts, which they are not

How can I get a job as highschool computer science teacher and what kind of things am I expected to cover at that age?
What SHOULD I teach?

stuff is good to know, yes it good stuff man

Attached: 1548783299052.png (447x483, 200K)

*for a constant space complexity

THINK for a second. yes, generalized bucket sort is not an inplace sort, but here your buckets are all guaranteed to have size 1. this allows you to do things that you would otherwise not be able to do.

i'll leave now. you disappoint me, /dpt/.

>for a linear space complexity, you need to re-use the array that you've already got.
Can't do that if your numbers are not ordered. If they are ordered it's as trivial as pairwise compare ever adjacent pair.

>A contains n elements, with exactly one repeated.
>this means that n-1 elements of A have to be unique, otherwise we'd have more repetitions.

that's what i was thinking at first too, but it's never stated the repeated element occurs exactly twice though. [1,2,3,3,3] might be a valid instance.

but then you could just do some kind of binary search in log n

So I'm trying to find who said what quote in a given text using python, I was thinking of like a pattern match
re.findall('"\" \" said"', paragraph)
so it's like it finds anything with quote start, quote end, then if it has the word "said" so I know if that quote has an author attributed to it.
But this isn't doing anything, so I guess I'm not understanding how re uses pattern matching.
I'm using
docs.python.org/3/library/re.html
for documentation.

ok you're right i'm sorry and take everything back, turns out i'm the dumbfuck
that being said, the algorithm i'm thinking of for will still work in linear time and with constant space because it doesn't use that property.

it won't work because there is the danger of overwriting the repeated element

I don't get how you could do a binary search if you don't know the order of the element you're searching for.

well maybe you can do something to prevent it from getting overwritten?
you've got enough space in that array, mate.
i think i've given enough hints.

> so I guess I'm not understanding how re uses pattern matching
It's regex man, try
'"(.*?)" said'

Because that guy told me to use C#

yea i don't think it would work if numbers could be skipped

>girl

this

So what does the
(.*?)
do? I don't see anything like that on the re page.
It talks about qualifiers, are those it?

they couldn't, it's my bad i put that rumor out

sum difference or product difference or whatever is sufficient for finding the repetition

re is short for regular expression, also known as regex. i'm not going to teach you regex, just google the term and you'll find a million tutorials.

Hm, adding tricks won't work since sum([1,3,3,3]) = sum([1,2,3,4]) = sum([2,2,2,4]). Some sort of XOR trick might work. I'm not convinced counting sort and friends work here, but maybe I'm missing something.

ok, post code

>I'm not convinced counting sor
Like I said, counting sort works in linear time and space.

i bet you could define a function that takes two arguments called g where you can do
reduce(g, initial, A) that distinguishes the repeated argument

OR you could get ur sum and get a*x where x is your repeated element and a is the number of times it was repeated

but hey, you have the length = n
but your array has a length of n+1 if it's repeated twice, n+2 if it's repeated three times etc.

so a is 2 if length(A) is n+2

it's the same trick as with the sum, using the mismatch between what's expected if no element is repeated and what you actually have on hand in A

Learning how to use openframeworks.

Well counting sort is linear in the range of the values, which is in this case n.

But whatever, I think I have something that works. Just treat it as a linked list where the successor to element I is at index A[i], then traverse it as if it were a linked list. Then you just have to regurgitate the solution to "detect a cycle in a linked list" problem, since it's obvious the list must contain a cycle.

Solution:

def find_dup(A):
slow = 0
fast = 1
time = 1

while slow != fast:
fast = A[fast]
if time % 2 == 1:
slow = A[slow]
time += 1

return fast

i even wrote it in go, everyone's favorite language
play.golang.org/p/EZZqB7mWbfq
but here's another task: prove that the time complexity is actually linear. hint: it's easy.

Cool idea.

very nice

pic isn't entirely unlike lorinda cherry desu

Either I'm dumb or your code is, but to me it looks like that has the potential to be stuck in an infinite loop.