#algos-and-data-structs | Python | Page 86

stable sand Sep 17, 2020, 10:31 PM

#

If I were to do it in only two lines

#

answer = thatrandomorder print(thatrandomorder)

Random order being h[0] + h[1] + s[0] etc

royal kestrel Sep 18, 2020, 12:38 AM

#

so my general question is this problem :

#

Given two lists, find the first occurrence of triplets (three identical items) on both lists. If triplets are found in both lists, then return a new 6-element list containing both triplets. If no such triplets exist in a list, then a string "None" is added to the new list instead of a triplet. You must use one for loop and one while loop to implement this function.

#

    size = len(list1) 
    newList = [] 
    for list2 in range(size): 
        k = list2 + 1
        for j in range(k, size): 
            if list1[list2] == list1[j] and list1[list2] not in newList: 
                newList.append(list1[list2]) 
    return newList```

#

my code ^

#

currently my code only takes in one reoccuring value from the two lists. I want my program to output the three identical values in each list into a new list and if there are no 3 same values in either list1 or list2 the program should output 'none'

oblique panther Sep 18, 2020, 1:19 AM

#

@royal kestrel are there any other constraints?

#

I'm not clear on what a triplet is

#

I assume the "first triplet" is whichever triplet is established at the lowest index, whatever a triplet is.

eager hamlet Sep 18, 2020, 3:26 AM

#

Write a program that calculates the price a customer has to pay for a purchase, making optimal use of the special offers to make the price as low as possible. You are not allowed to add items, even if that would lower the price.

For the prices and offers given above, the (lowest) price for three flowers and two vases is 14z: two vases and one flower for the reduced price of 10z and two flowers for the regular price of 4z.

PROGRAM NAME: shopping
INPUT FORMAT
The input file has a set of offers followed by a purchase.
Line 1: s, the number of special offers, (0 <= s <= 99).
Line 2..s+1: Each line describes an offer using several integers. The first integer is n (1 <= n <= 5), the number of products that are offered. The subsequent n pairs of integers c and k indicate that k items (1 <= k <= 5) with product code c (1 <= c <= 999) are part of the offer. The last number p on the line stands for the reduced price (1 <= p <= 9999). The reduced price of an offer is less than the sum of the regular prices.
Line s+2: The first line contains the number b (0 <= b <= 5) of different kinds of products to be purchased.
Line s+3..s+b+2: Each of the subsequent b lines contains three values: c, k, and p. The value c is the (unique) product code (1 <= c <= 999). The value k indicates how many items of this product are to be purchased (1 <= k <= 5). The value p is the regular price per item (1 <= p <= 999). At most 5*5=25 items can be in the basket.
SAMPLE INPUT (file shopping.in)
2
1 7 3 5
2 7 1 8 2 10
2
7 3 2
8 2 5
OUTPUT FORMAT
A single line with one integer: the lowest possible price to be paid for the purchases.
SAMPLE OUTPUT (file shopping.out)
14

#

how would i solve this with dynamic programming?

somber basin Sep 18, 2020, 5:23 AM

#

I dont understand this

📎 Screenshot_2020-09-17_222244.png

#

please help

strong tiger Sep 18, 2020, 5:25 AM

#

You will need to multiply it by 2**(1/12) repeatedly

somber basin Sep 18, 2020, 5:25 AM

#

yeah im having trouble like where to put it

#

im new to programming its for a college course

strong tiger Sep 18, 2020, 5:27 AM

#

from math import pow
start = int(input())
current = start
frequencies = [current]
r = pow(2,1/12)
for i in range(4):
    current *= r
    frequencies.append(current)
print(("{:.2f} " * len(frequencies)).format(*frequencies).strip())

#

This should give you a nice list of frequencies

#

Oh, you need to use the pow func

somber basin Sep 18, 2020, 5:28 AM

#

it didnt work for the assignment

#

sorry im kinda slow

#

it said it produced no output

#

its like for the basics

strong tiger Sep 18, 2020, 5:29 AM

#

You need to print it

somber basin Sep 18, 2020, 5:30 AM

#

um

#

print?

#

like print()

#

but like what do i print

strong tiger Sep 18, 2020, 5:32 AM

#

You use a format string

#

There, I edited the code

somber basin Sep 18, 2020, 5:32 AM

#

thats really advanced

#

it didnt work with my program

#

sorry you dont have to do this

#

im just really confused

strong tiger Sep 18, 2020, 5:33 AM

#

You're on python 3 right?

somber basin Sep 18, 2020, 5:33 AM

#

yea but its on zybooks

strong tiger Sep 18, 2020, 5:33 AM

#

!docs str.format

halcyon plankBOT Sep 18, 2020, 5:33 AM

#

`str.format`

str.format(*args, **kwargs)```
Perform a string formatting operation. The string on which this method is called can contain literal text or replacement fields delimited by braces `{}`. Each replacement field contains either the numeric index of a positional argument, or the name of a keyword argument. Returns a copy of the string where each replacement field is replaced with the string value of the corresponding argument.

```py
>>> "The sum of 1 + 2 is {0}".format(1+2)
'The sum of 1 + 2 is 3'
```  See [Format String Syntax](string.html#formatstrings) for a description of the various formatting options that can be specified in format strings.

Note... [read more](https://docs.python.org/3/library/stdtypes.html#str.format)

somber basin Sep 18, 2020, 5:33 AM

#

zybooks is where i learn it but i have to teach myself the material

#

its been hard trying to learn it

strong tiger Sep 18, 2020, 5:34 AM

#

I've edited it again to strip the string

#

Maybe now?

somber basin Sep 18, 2020, 5:35 AM

#

half of it was right

#

want me to screenshot?

strong tiger Sep 18, 2020, 5:35 AM

#

Wait, you need to type in the exact code they're expecting you to write?

#

Ok

somber basin Sep 18, 2020, 5:35 AM

#

like

#

hold on ill screenshot

#

its supposed to work with any input someone enters

#

not just one

strong tiger Sep 18, 2020, 5:36 AM

#

Oh, east

#

*easy

somber basin Sep 18, 2020, 5:36 AM

#

📎 Screenshot_2020-09-17_223632.png

strong tiger Sep 18, 2020, 5:36 AM

#

That should do it

#

I've edited it again

somber basin Sep 18, 2020, 5:37 AM

#

IT WORKEED

#

but i still dont understand it

strong tiger Sep 18, 2020, 5:37 AM

#

The last part of it?

somber basin Sep 18, 2020, 5:37 AM

#

like what you typed

#

can you send a video or something of where you learned how to program?

#

i really need it

#

with python that is

oblique panther Sep 18, 2020, 5:38 AM

#

!resources

halcyon plankBOT Sep 18, 2020, 5:38 AM

#

Resources

The Resources page on our website contains a list of hand-selected learning resources that we regularly recommend to both beginners and experts.

strong tiger Sep 18, 2020, 5:38 AM

#

I used a mobile app called SoloLearn

#

Let me show you this

#

!exec
from math import pow
start = int(input())
current = start
frequencies = [current]
r = pow(2,1/12)
for i in range(4):
current *= r
frequencies.append(current)
print(("{:.2f} " * len(frequencies)).format(*frequencies).strip())

#

!eval
from math import pow
start = int(input())
current = start
frequencies = [current]
r = pow(2,1/12)
for i in range(4):
current *= r
frequencies.append(current)
print(("{:.2f} " * len(frequencies)).format(*frequencies).strip())

halcyon plankBOT Sep 18, 2020, 5:39 AM

#

You are not allowed to use that command here. Please use the #bot-commands channel instead.

somber basin Sep 18, 2020, 5:39 AM

#

@strong tiger i have 3 more of these things to do so are you down to help me out?

#

no worries if you cant

strong tiger Sep 18, 2020, 5:40 AM

#

It's 2:40 am in my timezones, so sorry but no

somber basin Sep 18, 2020, 5:40 AM

#

kk thanks for the help

balmy siren Sep 18, 2020, 6:07 AM

#

@oblique panther Hey man, sorry for late reply?? Actually took two days for my report :D
Yeah, did you solve that question ?

topaz acorn Sep 18, 2020, 11:34 AM

#

.

wicked pebble Sep 18, 2020, 2:13 PM

#

Hi, I'm practicing my Python skills and am planning to try out the next Google Kickstart round. I tried the first problem in the Round D of KickStart 2020, and it all works fine on my IDE(Atom). Also, the time complexity is O(n) (O(3n) to be precise). However, I'm getting a RE(runtime error) every single time. What am I doing wrong? I know this section's for CS, but I really want some help on improving my competitive coding skills. Here is the link to the problem : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff08/0000000000387171#problem
Here's my code:

import sys
n = int(input())

cases = {}
record = {}

for a in range(n):
input()
cases[a] = list(map(int, input().split()))

for a in range(n):
case = cases[a]
max_day = -sys.maxsize()
records = 0
for i in range(len(case)):
if case[i] > max_day:
max_day = case[i]
if case[i] > case[(i+1) % len(case)]:
records += 1
record[a + 1] = records

for r in record.keys():
print('Case #' + str(r) + ': ' + str(record[r]))

Coding Competitions

Kick Start - Google’s Coding Competitions

Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all.

#

here's proof that it works just fine

#

📎 unknown.png

#

Plus I'm using PyPy 2 for faster times, but it still gives me the runtime errors

wide prism Sep 18, 2020, 3:47 PM

#

probably worth saying that O(n) is precisely the same as O(3n)

#

can you say what the errors you're getting are? one thing to try is removing the parentheses from sys.maxsize(), looks to me like that is an int not a callable

#

(actually since V_i has to be non-negative you might as well make max_day start out at -1 or something---and if V_i could be any integer -sys.maxsize still isn't really what you'd want)

#

not sure about the resources you're given to use in the environment on this site but another thing you could try is not reading the whole input into a dict and then processing it, but working through it as you read it in

#

hope some part of that helps, gl

oblique panther Sep 18, 2020, 4:20 PM

#

@wicked pebble what runtime error?

#

Be sure to include enough of the error message that we can tell what line is causing it.

#

Also, your question is on topic for this channel, so no worries there

wicked pebble Sep 18, 2020, 4:24 PM

#

Alright, I'm trying to read the errors but..

#

It's too generic

#

Here it is:

#

📎 unknown.png

oblique panther Sep 18, 2020, 4:24 PM

#

BTW I'm at the gym. Waiting for some hogs to get off the bench.

#

So I can't run anything

wicked pebble Sep 18, 2020, 4:25 PM

#

lol

#

Actually, I can confirm it works fine

#

like, it's in the photo above

oblique panther Sep 18, 2020, 4:25 PM

#

Is it not giving you any more data than that?

wicked pebble Sep 18, 2020, 4:25 PM

#

Yep. Good ol' RE

oblique panther Sep 18, 2020, 4:25 PM

#

There's nothing you can click on?

wicked pebble Sep 18, 2020, 4:26 PM

#

yep

oblique panther Sep 18, 2020, 4:26 PM

#

I guess I'd write some test cases.

wicked pebble Sep 18, 2020, 4:26 PM

#

just Runtime Error

#

Ok, I would really appreciate that

#

if you understood the problem

oblique panther Sep 18, 2020, 4:26 PM

#

Well, I'm suggesting that you write them

wicked pebble Sep 18, 2020, 4:26 PM

#

ohh

#

hmm

#

I feel like this is more of a

#

efficiency issue

#

because I;ve run some

#

sample tests myself but

#

itall just works fine

#

@wide prism Thanks, like I said there's no info other than Runtime Error 😦 I also changed the initial value of max_day to -1, still doesn't work...
Also, a question for all people umm.. which one is faster: a 2D list or lists in a dictionary?

#

Apparently a hash table's faster, but I'm not sure

wide prism Sep 18, 2020, 4:31 PM

#

well, not reading the whole thing into memory at once is the next thing i'd try
it does pass a local test case on my end once the maxsize thing is fixed, which is part of why i suspect something like that

wicked pebble Sep 18, 2020, 4:33 PM

#

Ohh, that could also be a problem.. hmm... should I try completing a test case before getting another one?

#

I could maybe make it into O(2n) (It's probably about the same thing as O(3n), but maybe less time?) with printing each result as I complete them...

#

Brb with the code

wide prism Sep 18, 2020, 4:37 PM

#

oh actually it does say you have a gb so i think that should be enough?

wicked pebble Sep 18, 2020, 4:43 PM

#

umm.. actually

#

n = int(input())

for a in range(n):
    length = int(input())
    case = list(map(int, input().split()))
    max_day = -1
    records = 0
    for i in range(length):
        if case[i] > max_day:
            if i == (length - 1):records += 1
            else:
                max_day = case[i]
                if case[i] > case[i + 1]:records += 1
    print('Case #' + str(a + 1) + ': ' + str(records))

#

Still a runtime error..

wide prism Sep 18, 2020, 4:45 PM

#

if case[i] > case[i + 1]:records += 1
well this can run off the edge of the list

wicked pebble Sep 18, 2020, 4:46 PM

#

which is why I included

#

if i == (length - 1):records += 1

wide prism Sep 18, 2020, 4:47 PM

#

ah gotcha, my bad. just saw you changed the line from before and didn't look up

wicked pebble Sep 18, 2020, 4:47 PM

#

hmm.. could it just be that

#

Python is terrible for competitive programming

#

lol

#

I mean, I think the algorithm doesn't really have any room for faster times or less space..

#

Still, it's a contest managed by Google, so it would be weird if they made it impossible for Python programmers..

#

Holy shit

#

Ah sorry um

#

I found the problem

#

The program was printing the test case thing

#

before the next case was inputted so

#

it wasn't what Google wanted

#

Wow, separating the cases into separate parts really did work!

#

Thank you so much!!!

#

It got passed

#

n = int(input())

record = []

for a in range(n):
    length = int(input())
    case = list(map(int, input().split()))
    max_day = -1
    records = 0
    for i in range(length):
        if case[i] > max_day:
            if i == (length - 1):records += 1
            else:
                max_day = case[i]
                if case[i] > case[i + 1]:records += 1
    record.append(records)
for a in range(n):
    print('Case #' + str(a + 1) + ': ' + str(record[a]))

#

Also, running I was running the thing with PyPy 2, which is the latest version of PyPy Google supports...

#

I'm so happy rn, thank y'all

somber basin Sep 18, 2020, 6:58 PM

#

📎 Screenshot_2020-09-18_115801.png

#

📎 Screenshot_2020-09-18_115820.png

#

Can someone please help me with this?

#

I dont understand it.

#

Please ping me when someone can help.

naive cloak Sep 18, 2020, 7:00 PM

#

When opening a file and reading it using a for loop, why are the changes made during the for loop saved?
I was told that python creates a pointer that moves per line and the position of this pointer is saved, but I'd like to verify with you.
Here is an example code which is wrong on purpose:
`
file_logs = open(path)

n = 0
l = 0

for line in file_logs:
if line.find(email) == -1: continue
n = n+1

for line in file_logs:
l = l + 1
`
here the second part doesn't run, is it because of the pointer being already at the end?

quasi oracle Sep 18, 2020, 7:12 PM

#

@naive cloak yes

#

You could use file_logs.seek(0) to bring it back to the top

#

Though it's better to do everything you need with that line the first time you pass over it

naive cloak Sep 18, 2020, 7:14 PM

#

Thanks!

meager mauve Sep 18, 2020, 10:12 PM

#

can someone explain me what is the complexity (big o notation) of this code?

📎 unknown.png

topaz pulsar Sep 18, 2020, 10:19 PM

#

@meager mauve O(inf) i think, because i is never decremented so if i is initially greater than zero, it will run indefinitely

#

but if that i = i is supposed to be i = i -1 then should be O(n^2) as the while loop runs n times (as i == n) and the inner for-loops number of runs also depends on the value of i (making that nested loop O(n) as well)

quasi oracle Sep 18, 2020, 10:21 PM

#

@modest jay don't post random videos in on-topic channels

fiery cosmos Sep 18, 2020, 11:16 PM

#

I'm really struggling on working out how to read a CSV file in python
(all on trinket)

brave oak Sep 19, 2020, 12:08 AM

#

I'm really struggling on working out how to read a CSV file in python
(all on trinket)
@fiery cosmos use the csv module

vivid dome Sep 19, 2020, 12:22 AM

#

So what is a Computer Science degree worth these days?

agile sundial Sep 19, 2020, 12:32 AM

#

probably better for the #career-advice channel

somber basin Sep 19, 2020, 5:44 AM

#

📎 Screenshot_2020-09-18_115801.png

#

📎 Screenshot_2020-09-18_115820.png

#

plz help someone

quasi oracle Sep 19, 2020, 11:46 AM

#

@somber basin we don't help with graded work

west surge Sep 19, 2020, 2:36 PM

#

What makes you think it's graded? Just wondering

formal prism Sep 19, 2020, 2:41 PM

#

Hello guys, i have a question for you.

I want to build (from zero, and not using any source codes available on internet) a music player, using (only) Python!
And what i want to know the essencialities of a music player that must have to work properly!
Thanks, and waiting for responses. (Also, sorry if i did some english mistakes.)

quasi oracle Sep 19, 2020, 2:52 PM

#

What makes you think it's graded? Just wondering
@west surge each question says how many points it's worth

#

also it's built in a pretty classic homework form

west surge Sep 19, 2020, 2:54 PM

#

Why can't we help with graded things again?

quasi oracle Sep 19, 2020, 2:57 PM

#

Because graded work should be able to judge a person's understanding of the material taught.
It's ok to explain something as a general concept, but we won't solve someone's graded work for them. And in this case, they should mainly review the material taught in class.

somber basin Sep 19, 2020, 2:58 PM

#

Well I have to teach myself the material and I brought it here because I am generally confused

#

I just don’t know how to do it

#

But sorry for bringing it here

west surge Sep 19, 2020, 2:59 PM

#

So can we help them review the material taught or something instead of shooing them away?

quasi oracle Sep 19, 2020, 3:02 PM

#

Yeah, we can.
This isn't about shooing them away, they requested help specifically with solving their assignment, and that's something that we explicitly state that we don't allow here

west surge Sep 19, 2020, 3:08 PM

#

I just think we should at least try to help them with something instead of saying we don't help with graded work

quasi oracle Sep 19, 2020, 3:12 PM

#

You're welcome to, but it's up to them to request help with the material they don't understand, instead of with what they're being graded on.

west surge Sep 19, 2020, 3:13 PM

#

Ok.

#

@somber basin so what are you having trouble understanding

somber basin Sep 19, 2020, 3:15 PM

#

well this other guy helped me with floats and i asked him to explain what he did but he didn’t

#

but the wording on this one is confusing

west surge Sep 19, 2020, 3:18 PM

#

Essentially it's asking you to store the input in variables then print them on the same line

#

do you understand that much?

somber basin Sep 19, 2020, 4:43 PM

#

ah yes i understand that @west surge

sullen fox Sep 19, 2020, 8:34 PM

#

Hi, if someone could help me with this it would be really appreciated, thanks Create a program that will:

Convert the list to a tuple
Convert the tuple into a set
Print the combined values of the 3rd and 5th value of the tuple
UNPACK the tuple into variables called num1, num2 etc.

snow swift Sep 19, 2020, 8:39 PM

#

what do you have so far @sullen fox

sullen fox Sep 19, 2020, 8:48 PM

#

@snow swift just my_list = list(tupe)
print(my_list) ive been researching how to convert list to tuple but im not sure

somber basin Sep 19, 2020, 9:03 PM

#

📎 Screenshot_2020-09-19_140258.png

#

how do I convert an integer into a character and then output the function?

#

Ive almost got it with a friends help

snow swift Sep 19, 2020, 9:06 PM

#

reread the question @somber basin

#

it may be helpful

somber basin Sep 19, 2020, 9:06 PM

#

oh fuck me

#

lmao

#

i see it now

#

i tried it and it still didnt work

snow swift Sep 19, 2020, 9:22 PM

#

post code

somber basin Sep 19, 2020, 9:24 PM

#

📎 Screenshot_2020-09-19_142417.png

#

its just the chr() function im confused about

#

i know its like unicode or something

#

you give it a number and gives you something back like a letter

snow swift Sep 19, 2020, 9:26 PM

#

ok

#

so how dou think you should use it

#

currently you're not evalulating it within the f string

#

you're just printing "chr(user_int)", literally

somber basin Sep 19, 2020, 9:28 PM

#

ah

#

maybe i should just take the f away

#

it still says im printing chr() again

snow swift Sep 19, 2020, 9:30 PM

#

https://realpython.com/python-f-strings/

Python 3's f-Strings: An Improved String Formatting Syntax (Guide) ...

As of Python 3.6, f-strings are a great new way to format strings. Not only are they more readable, more concise, and less prone to error than other ways of formatting, but they are also faster! By the end of this article, you will learn how and why to start using f-strings to...

#

recommend learning how f strings work

somber basin Sep 19, 2020, 9:31 PM

#

kk thanks

graceful dagger Sep 19, 2020, 9:33 PM

#

Im new to python and learning how to use class i dont rlly understand how it works can anyone help

📎 Screen_Shot_2020-09-19_at_5.30.43_PM.png

somber basin Sep 19, 2020, 9:42 PM

#

bro idk

#

its not working

winged citrus Sep 19, 2020, 9:59 PM

#

Im new to python and learning how to use class i dont rlly understand how it works can anyone help
@graceful dagger google and read first. Then ask more specific questions. class is a general OOP concept. It's meant to keep data and methods that act on that data together. The idea is to encapsulate the data as private so objects outside the class cannot see the class's implementation/detals.

graceful dagger Sep 19, 2020, 10:06 PM

#

k

west surge Sep 19, 2020, 10:27 PM

#

@somber basin it most likely wants you to do print(some_var, some_var, some_var)

somber basin Sep 19, 2020, 10:27 PM

#

oh i got it now

#

thanks for your help

eager hamlet Sep 19, 2020, 11:16 PM

#

The King can move to any adjacent square from to as long as it does not fall off the board:

A Knight can jump from to , as long as it does not fall off the board:

During the play, the player can place more than one piece in the same square. The board squares are assumed big enough so that a piece is never an obstacle for any other piece to move freely.

The player's goal is to move the pieces so as to gather them all in the same square - in the minimal number of moves. To achieve this, he must move the pieces as prescribed above. Additionally, whenever the king and one or more knights are placed in the same square, the player may choose to move the king and one of the knights together from that point on, as a single knight, up to the final gathering point. Moving the knight together with the king counts as a single move.

Write a program to compute the minimum number of moves the player must perform to produce the gathering. The pieces can gather on any square, of course.

#

INPUT FORMAT
Line 1: Two space-separated integers: R,C, the number of rows and columns on the board. There will be no more than 26 columns and no more than 30 rows.
Line 2..end: The input file contains a sequence of space-separated letter/digit pairs, 1 or more per line. The first pair represents the board position of the king; subsequent pairs represent positions of knights. There might be 0 knights or the knights might fill the board. Rows are numbered starting at 1; columns are specified as upper case characters starting with `A'.
SAMPLE INPUT (file camelot.in)
8 8
D 4
A 3 A 8
H 1 H 8
The king is positioned at D4. There are four knights, positioned at A3, A8, H1, and H8.

OUTPUT FORMAT
A single line with the number of moves to aggregate the pieces.
SAMPLE OUTPUT (file camelot.out)
10
SAMPLE OUTPUT ELABORATION
They gather at B5.
Knight 1: A3 - B5 (1 move)
Knight 2: A8 - C7 - B5 (2 moves)
Knight 3: H1 - G3 - F5 - D4 (picking up king) - B5 (4 moves)
Knight 4: H8 - F7 - D6 - B5 (3 moves)
1 + 2 + 4 + 3 = 10 moves.

#

so how would i do this without exceeding the meager 1 second time limit?

oblique panther Sep 20, 2020, 1:28 AM

#

@eager hamlet as I recall, it's a well-known problem that challenges like this don't scale the time limit to account for the general speed of the implementation language.

eager hamlet Sep 20, 2020, 1:29 AM

#

wait what's that supposed to mean

#

also i just decided to brute force it (i can hardcode the distances anyways)

oblique panther Sep 20, 2020, 1:30 AM

#

I remember listening to an episode of Talk Python and they mentioned that competitions don't have a higher time limit if you choose to solve the problem in Python

#

because Python is much much slower than C

eager hamlet Sep 20, 2020, 1:30 AM

#

yeah

#

it's 1 second for all langs

oblique panther Sep 20, 2020, 1:31 AM

#

that's just a flaw in how they evaluate

#

what's actually interesting is the runtime complexity of your solution

#

but I don't know that it's actually possible to determine the runtime complexity of a program automatically

#

I would focus on solving the problem and then figuring out the runtime complexity of your solution.

#

@eager hamlet A Knight can jump from to , as long as it does not fall off the board:

eager hamlet Sep 20, 2020, 1:44 AM

#

yeah

oblique panther Sep 20, 2020, 1:44 AM

#

it looks like part of your message was cut off

eager hamlet Sep 20, 2020, 1:44 AM

#

there was a diagram

oblique panther Sep 20, 2020, 1:44 AM

#

from what to what?

eager hamlet Sep 20, 2020, 1:44 AM

#

those were images

#

corresponding to a diagram

oblique panther Sep 20, 2020, 1:44 AM

#

well, we'd need to know the rules for how knights move

eager hamlet Sep 20, 2020, 1:44 AM

#

basically just normal chess knight movements

oblique panther Sep 20, 2020, 1:44 AM

#

alright

humble drum Sep 20, 2020, 1:44 AM

#

Question : What IDE you recommend for python (i.e PyCharm, Atom, etc.)

oblique panther Sep 20, 2020, 1:45 AM

#

@humble drum that question is not on topic for this channel and is on topic for #tools-and-devops; I prefer PyCharm.

humble drum Sep 20, 2020, 1:45 AM

#

@humble drum that question is not on topic for this channel and is on topic for #tools-and-devops; I prefer PyCharm.
@oblique panther Oh, sorry

oblique panther Sep 20, 2020, 1:47 AM

#

@eager hamlet if I have time I'm going to look at a list of graph algorithms because I think this is a special case of some known graph algorithm.

#

but I would encourage you to do the same.

eager hamlet Sep 20, 2020, 1:48 AM

#

i mean with caching i could speed it up a bit

#

and hardcoding the distances is also a thing

oblique panther Sep 20, 2020, 1:48 AM

#

hardcoding the distances?

eager hamlet Sep 20, 2020, 1:49 AM

#

yeah

oblique panther Sep 20, 2020, 1:49 AM

#

so, hardcoding how much a given type of piece (knight or king) can move?

#

also, are they gathering at a given square, or are you solving for the square that they can arrive at in the fewest number of moves?

stable pecan Sep 20, 2020, 1:54 AM

#

you can convert your chess board into a graph, where nodes represent squares on the board and two nodes are connected if a knight can move from one to the other --- then you use https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm to get distances

Floyd%E2%80%93Warshall_algorithm

eager hamlet Sep 20, 2020, 1:56 AM

#

@oblique panther any square, they just have to all gather at it

oblique panther Sep 20, 2020, 1:58 AM

#

Sounds like salt-die is right

#

does FW "remember" the path you used to get there, though @stable pecan?

#

I guess you have the matrix at the end

stable pecan Sep 20, 2020, 2:04 AM

#

it is possible to reconstruct the paths with simple modifications to the algorithm

#

you can optimize it a bit

#

sort of doing depth-first over the entire set of knights

#

instead of doing all shortest paths for each knight

#

which should be quite a bit faster on average

#

says my intuition

oblique panther Sep 20, 2020, 2:07 AM

#

do you have experience with this kind of thing other than just algorithm courses in a CS undergrad?

stable pecan Sep 20, 2020, 2:13 AM

#

i'm a mathematician not a CS person -- but I study complex networks

#

which is tangentially related

#

though, i'm writing a solution now that starts like this:

import numpy as np
from scipy.ndimage import convolve

KERNEL = [
    [0, 1, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 1, 0]
]

#

maybe you can guess where this is going

quasi oracle Sep 20, 2020, 2:30 AM

#

The issue with the King makes it a bit more complicated, since you don't necessarily want a knight to take the shortest path, but one which will allow it to "grab" the king

#

Though with your kernel idea, you could do the same with the king, and then "intersect" the two matrices

stable pecan Sep 20, 2020, 2:32 AM

#

that is exactly what i'm doing!

eager hamlet Sep 20, 2020, 3:00 AM

#

frick

#

my program failed on the third test case

#

way too slow

oblique panther Sep 20, 2020, 3:07 AM

#

@eager hamlet you could make a test case and see if it's correct for that test case

eager hamlet Sep 20, 2020, 3:07 AM

#

it's correct

#

it's just slow as all hell

oblique panther Sep 20, 2020, 3:07 AM

#

that way you don't have to worry about the online test cutting you off

eager hamlet Sep 20, 2020, 3:07 AM

#

and that's just for a 15x15

stable pecan Sep 20, 2020, 3:16 AM

#

this is messy, but i'm about to sleep if anyone wants to continue it:

import numpy as np
from scipy.ndimage import convolve

KERNEL = np.array([
    [0, 1, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 1, 0],
], dtype=float)

ROW, COL = 10, 10
nknights = 4

knights = np.zeros((nknights, ROW, COL))
knights[np.arange(nknights), [1, 3, 7, 6], [3, 7, 6, 2]] = 1


j = 1
last = knights.copy()
while (solution := np.where(knights == 0, float('inf'), knights).sum(axis=0)).min() == float('inf'):
    last = np.clip(np.stack([convolve(last[i], KERNEL, mode='constant') for i in range(nknights)]), 0, 1)
    knights = np.where(knights == 0, j * last, knights)
    knights[np.arange(nknights), [1, 3, 7, 6], [3, 7, 6, 2]] = 0
    j += 1

eager hamlet Sep 20, 2020, 3:16 AM

#

oof man

#

usaco doesn't support np

#

bullcrap but that's how it is

oblique panther Sep 20, 2020, 3:18 AM

#

@stable pecan were you just doing that this whole time?

stable pecan Sep 20, 2020, 3:18 AM

#

yeah

oblique panther Sep 20, 2020, 3:18 AM

#

that's some dedication

stable pecan Sep 20, 2020, 3:18 AM

#

i like fiddling with numpy

oblique panther Sep 20, 2020, 3:19 AM

#

I need to get a grasp on how to slice numpy matrices

stable pecan Sep 20, 2020, 3:20 AM

#

i don't like having to convolve each layer separately

quasi oracle Sep 20, 2020, 3:21 AM

#

That's some gross walrus

stable pecan Sep 20, 2020, 3:21 AM

#

that's a tame walrus

#

i mean, do you want to recalculate that?

quasi oracle Sep 20, 2020, 3:24 AM

#

You could always calculate it at the end of the loop 🙃 but I'm just nitpicking

stable pecan Sep 20, 2020, 3:24 AM

#

there's a nice library, graph-tool, that's a graph library with c++ extensions that one could use --- i'm going to guess that networkx is too slow

eager hamlet Sep 20, 2020, 3:26 AM

#

usaco doesn't do any third-party libraries

quasi oracle Sep 20, 2020, 3:26 AM

#

I need to get a grasp on how to slice numpy matrices
@oblique panther same as lists, except you have multiple dimensions

stable pecan Sep 20, 2020, 3:27 AM

#

not exactly the same, because numpy has fancy-indexing

quasi oracle Sep 20, 2020, 3:27 AM

#

yeah. that's what I mean by multiple dimensions

oblique panther Sep 20, 2020, 3:27 AM

#

@quasi oracle I need to get "from nth column, n < 10, the elements that are nan and for which the cell in the same row but the 11th column equals a specific value"

stable pecan Sep 20, 2020, 3:28 AM

#

no that's different

#

fancy-indexing is when you pass arrays in, not when you index with tuples and slices

quasi oracle Sep 20, 2020, 3:28 AM

#

ah that

stable pecan Sep 20, 2020, 3:28 AM

#

also masking

quasi oracle Sep 20, 2020, 3:29 AM

#

What do you mean by "from nth column, n < 10"

#

You mean in one of those columns?

oblique panther Sep 20, 2020, 3:30 AM

#

the solution I have in mind involves iterating over the columns (which is always 11, but the 11th column is special and is skipped) and doing a calculation

eager hamlet Sep 20, 2020, 3:31 AM

#

what's convolve

oblique panther Sep 20, 2020, 3:31 AM

#

the number of rows is a variable

stable pecan Sep 20, 2020, 3:31 AM

#

whats convolve?!?!

#

it's my favorite thing in the world!

quasi oracle Sep 20, 2020, 3:31 AM

#

https://en.wikipedia.org/wiki/Kernel_(image_processing)

#

Might induce initial shock, but it's pretty cool

eager hamlet Sep 20, 2020, 3:32 AM

#

idk man usaco is more algorithms than it is knowing this kinda stuff

stable pecan Sep 20, 2020, 3:32 AM

#

you should link image convolution, not signal one

eager hamlet Sep 20, 2020, 3:32 AM

#

not saying it's not important

stable pecan Sep 20, 2020, 3:32 AM

#

they're similar, but the signal one is more confusing

eager hamlet Sep 20, 2020, 3:32 AM

#

did you know that usaco still supports python 2

quasi oracle Sep 20, 2020, 3:33 AM

#

fixed

stable pecan Sep 20, 2020, 3:33 AM

#

yeah

#

i once found this nice site with a animated gif explaining the kernel

#

but i dunno where it is now

#

📎 download.gif

#

there we go

quasi oracle Sep 20, 2020, 3:38 AM

#

the solution I have in mind involves iterating over the columns (which is always 11, but the 11th column is special and is skipped) and doing a calculation
@oblique panther

array = np.array(...)

nans = np.isnan(array[:, :10])
value_in_row = array[:, 10] == value
solution = nans * value_in_row

This should give you a mask for the first 10 columns

oblique panther Sep 20, 2020, 3:38 AM

#

Thanks!

quasi oracle Sep 20, 2020, 3:39 AM

#

Maybe it'll require adding a dimension for value_in_row for the broadcast

oblique panther Sep 20, 2020, 3:39 AM

#

it would need to be the same shape as array, yes?

quasi oracle Sep 20, 2020, 3:40 AM

#

It would need to have the same number in the same dimension, or a 1

#

And the same number of dimensions

#

Which is pretty upsetting. I prefer Matlab's behavior

oblique panther Sep 20, 2020, 3:40 AM

#

why

quasi oracle Sep 20, 2020, 3:41 AM

#

Matlab just assumes that any missing dimensions have a 1 in them

lost loom Sep 20, 2020, 3:44 AM

#

alright i got a question regarding this

📎 unknown.png

#

Fairly certain i understand all of it except the square brackets part

#

📎 unknown.png

quasi oracle Sep 20, 2020, 3:44 AM

#

Where is that from?

lost loom Sep 20, 2020, 3:44 AM

#

what do the square brackets actually mean

#

Its a bellman function

#

or equation rather

#

reinforcement learning

#

just trying to figure out what the square brackets mean cause from what i can tell it can mean a few different things

quasi oracle Sep 20, 2020, 3:45 AM

#

Seems like parentheses to me

lost loom Sep 20, 2020, 3:46 AM

#

so just multiplying perhaps

quasi oracle Sep 20, 2020, 3:46 AM

#

yeah

oblique panther Sep 20, 2020, 3:53 AM

#

@quasi oracle I think I would have to intersect that with a mask for every column except the desired one

quasi oracle Sep 20, 2020, 3:54 AM

#

I'm still not 100% sure what you're going for. Mind giving an example? (with maybe 3 columns and not 11)

oblique panther Sep 20, 2020, 3:55 AM

#

| A | B | C |
|-|-|-|
|1|5|True|
|Nan|2|True|
|5|7|False|
|3|Nan|False|

#

So for each column, replace all the Nans in that column with the average of all the other values in that column

#

as long as the boolean value in C is the same for that row

quasi oracle Sep 20, 2020, 3:56 AM

#

Well a numpy array has one type, so ideally that would be 0's and 1's

oblique panther Sep 20, 2020, 3:56 AM

#

it is

quasi oracle Sep 20, 2020, 3:57 AM

#

" is the same " the same as what?

oblique panther Sep 20, 2020, 3:57 AM

#

if a given row has a nan and its boolean value is True

quasi oracle Sep 20, 2020, 3:57 AM

#

ok

oblique panther Sep 20, 2020, 3:58 AM

#

we only want to consider rows for which the boolean value is also True

#

or False if the value for the row with the nan is False

quasi oracle Sep 20, 2020, 3:58 AM

#

So what do you mean by

I think I would have to intersect that with a mask for every column except the desired one

oblique panther Sep 20, 2020, 3:58 AM

#

the fact that it's True or False is arbitrary, they're just two classes.

#

I'm going to do an assignment expression with the matrix

#

matrix[is_nan & row_is_relevant] = np.mean(matrix[~is_nan & row_is_relevant & true_matrix].flat)

#

to replace all the nans in the current column with the calculated value

#

(that statement isn't correct)

quasi oracle Sep 20, 2020, 4:00 AM

#

You could calculate the nanmean over the 0th axis

oblique panther Sep 20, 2020, 4:02 AM

#

ah

#

didn't know that was a thing

#

even though it's a CS class, it's not a programming class, so the prof just said that we're allowed to use Python if we want and we can use pandas and numpy only if we do.

#

and I found out from the TA that the goal is to demonstrate how long these sorts of algorithms take.

quasi oracle Sep 20, 2020, 4:11 AM

#

What's the class about?

oblique panther Sep 20, 2020, 4:15 AM

#

data science

lost loom Sep 20, 2020, 4:34 AM

#

Another lil math question

#

is E[x | y] just the expected value of x given y

quasi oracle Sep 20, 2020, 4:35 AM

#

yeah

lost loom Sep 20, 2020, 4:35 AM

#

alright cool

#

thank you

wooden oasis Sep 20, 2020, 2:47 PM

#

Can anyone help me with a couple of codes

rigid lagoon Sep 20, 2020, 4:09 PM

#

Why does L1 norm cause zero weights (sparsity) but L2 norm not?
Because of their derivative (Abs(w) and w2)?
Close to zero, we have different derivatives for L1 and L2 penalty, right?

eager hamlet Sep 20, 2020, 6:20 PM

#

i think that's for #data-science-and-ml

#

problem: ```
During the play, the player can place more than one piece in the same square. The board squares are assumed big enough so that a piece is never an obstacle for any other piece to move freely.

The player's goal is to move the pieces so as to gather them all in the same square - in the minimal number of moves. To achieve this, he must move the pieces as prescribed above. Additionally, whenever the king and one or more knights are placed in the same square, the player may choose to move the king and one of the knights together from that point on, as a single knight, up to the final gathering point. Moving the knight together with the king counts as a single move.

Write a program to compute the minimum number of moves the player must perform to produce the gathering. The pieces can gather on any square, of course.

PROGRAM NAME: camelot
INPUT FORMAT
Line 1: Two space-separated integers: R,C, the number of rows and columns on the board. There will be no more than 26 columns and no more than 30 rows.
Line 2..end: The input file contains a sequence of space-separated letter/digit pairs, 1 or more per line. The first pair represents the board position of the king; subsequent pairs represent positions of knights. There might be 0 knights or the knights might fill the board. Rows are numbered starting at 1; columns are specified as upper case characters starting with `A'.
SAMPLE INPUT (file camelot.in)
8 8
D 4
A 3 A 8
H 1 H 8
The king is positioned at D4. There are four knights, positioned at A3, A8, H1, and H8.

OUTPUT FORMAT
A single line with the number of moves to aggregate the pieces.
SAMPLE OUTPUT (file camelot.out)
10
SAMPLE OUTPUT ELABORATION
They gather at B5.
Knight 1: A3 - B5 (1 move)
Knight 2: A8 - C7 - B5 (2 moves)
Knight 3: H1 - G3 - F5 - D4 (picking up king) - B5 (4 moves)
Knight 4: H8 - F7 - D6 - B5 (3 moves)
1 + 2 + 4 + 3 = 10 moves.```
code: https://paste.pythondiscord.com/vacipihuvo.sql

#

(knights and kings move as they do in chess)

oblique panther Sep 20, 2020, 6:30 PM

#

@eager hamlet what is your question? since we established that this is a variation of Floyd-Warshall

eager hamlet Sep 20, 2020, 6:36 PM

#

uh yeah

#

it's way too slow

#

and it's not the calculating the distances that sucks

#

(it only takes like .1 seconds)

#

at most .5

#

but it's the actual brute forcing

oblique panther Sep 20, 2020, 8:36 PM

#

@eager hamlet which part are you brute forcing?

#

Note also that due to the slower speed of a Python program, it may not be possible to solve the largest test cases for some problems even with the inflated time limit given to Python submissions -- consider using a faster language for problems where execution time is critical. Executions are run with the "-O" flag to enable some optimization.
http://www.usaco.org/index.php?page=instructions

rustic isle Sep 20, 2020, 9:27 PM

#

Hi everyone!
(I put this here because I don’t really know to put it)

I’m going to make a python based driving AI in BeamNG as my final project for high school.

Does anybody want to take part ?
PS : I’m French but that won’t be a problem
If you want to join me, send a private message

fiery cosmos Sep 20, 2020, 9:50 PM

#

Okay. this is really pissing me off because I can't find a solution to this on google. I have ALREADY extended the length of my path variables with regedit and I'm still getting this message. please help

📎 unknown.png

cursive aspen Sep 20, 2020, 10:07 PM

#

@fiery cosmos run as admin

fiery cosmos Sep 20, 2020, 10:08 PM

#

if thats the problem i'm going to be pissed.

#

nope. same problem

lost bough Sep 20, 2020, 10:22 PM

#

The Python installer mentions something about "Disable PATH length limit" - give that option a try, or see if there are other ways to achieve the same result via registry hacks.

fiery cosmos Sep 20, 2020, 10:22 PM

#

i'm pretty sure i've already tried that.

#

as mentioned above.

lost bough Sep 20, 2020, 10:22 PM

#

Yeah but the limit is still there, according to the error. blobthonkang

fiery cosmos Sep 20, 2020, 10:22 PM

#

oh

#

yeah looked that up on google and i've already done all that.

lost bough Sep 20, 2020, 10:25 PM

#

Could it be that they hard-coded the default Path length limit into their installer? I mean, I trust you found all the same posts I did, but apparently going "ok" and manually adding the directory to Path works for some.

fiery cosmos Sep 20, 2020, 10:26 PM

#

i've also just tried that. unless I added the wrong path, it still doesn't work.

snow swift Sep 20, 2020, 10:27 PM

#

just add it manually ig

fiery cosmos Sep 20, 2020, 10:27 PM

#

@snow swift ^

snow swift Sep 20, 2020, 10:27 PM

#

wait why did you ping me

fiery cosmos Sep 20, 2020, 10:27 PM

#

read the message above.

#

ive already tried adding it manually

snow swift Sep 20, 2020, 10:29 PM

#

@lost bough pretty sure that's for file path length limit

fiery cosmos Sep 20, 2020, 10:30 PM

#

📎 unknown.png

snow swift Sep 20, 2020, 10:32 PM

#

start a new cmd prompt window?

#

idk

fiery cosmos Sep 20, 2020, 10:33 PM

#

what? why?

snow swift Sep 20, 2020, 10:35 PM

#

because path changes don't apply to current cmd prompts

fiery cosmos Sep 20, 2020, 10:35 PM

#

okay but like... i'm confused

#

just open a cmd and everything will work?

oblique panther Sep 20, 2020, 10:58 PM

#

@fiery cosmos this question would be best for an individual help session. See #❓｜how-to-get-help

waxen meadow Sep 21, 2020, 12:27 AM

#

Guys how could i get my computer audio?? (obs: its not the microphone)
like in real time

ornate fog Sep 21, 2020, 12:43 AM

#

Hey guys, could I get some help with my code. I’m taking a intro to computer science class atm and I am confused with my code, when I check it it’s giving me an eof error. But when i run it, it works, it has to deal with payday days and booleans, so how can I fix it and avoid it in the future?. payday1 = int(input("Enter today's day numerically: "))

if (payday1 == 15):
print("Its payday!")

if (payday1 != 15):
print("Sorry, not a payday.")

payday2 = int(input("Enter today's day numerically: "))

if (payday2 == 30):
print("Its payday!")

if (payday2 != 30):
print("Sorry, not a payday.")

#

The error is occurring with the second input

low obsidian Sep 21, 2020, 1:13 AM

#

Try This:
if payday1 == 15:
print("Its payday!")

elif payday1 != 15:
print("Sorry, not a payday.")

payday2 = int(input("Enter today's day numerically: "))

if payday2 == 30:
print("Its payday!")

elif payday2 != 30:
print("Sorry, not a payday.")

#

@ornate fog

ornate fog Sep 21, 2020, 1:18 AM

#

Ok

ornate fog Sep 21, 2020, 1:39 AM

#

Input 2 is messed up still

#

📎 image0.jpg

#

It may be on the teacher’s end??

oblique panther Sep 21, 2020, 3:12 AM

#

@ornate fog can you open a help session, copy and paste your exact code into the chat, and ping me on that help session?

#

Though it appears you're not currently online. Note however that while your class is intro to computer science, this particular question is just about programming, so it's not on topic for this channel.

manic shard Sep 21, 2020, 5:08 AM

#

sure ?

#

whats your issue

#

cool

frank harbor Sep 21, 2020, 5:14 AM

#

I have a Python assignment that has to deal with storing groups of information in different sequence types, and writing lines of codes to store them in the said sequences, is there anyone here that could help me out?

snow swift Sep 21, 2020, 5:14 AM

#

@frank harbor post code

#

Don't ask to ask

frank harbor Sep 21, 2020, 5:24 AM

#

Group 1: Stores types of foods that should be selectable and modifiable: Brownie, apple, pear, orange, watermelon
Group 2: Stores numeric quantities (should be parallel to group 1) : 7, 4, 3 ,9 ,8
Group 3: Stores a sentence typed in english (should be able to be analyzed based on its letters, numbers, and symbols): The dog took the bone from the man.

#

I just don't really know where to start

flat sorrel Sep 21, 2020, 6:13 AM

#

!e

grp1, grp2, grp3 = [], [], []
original = [('Brownie', 7, 'The dog took the bone from the man.'), ('apple', 4, 'second sentence')]

for info in original:
    food = info[0]
    number = info[1]
    sentence = info[2]
    print(food, number, sentence)

halcyon plankBOT Sep 21, 2020, 6:13 AM

#

You are not allowed to use that command here. Please use the #bot-commands channel instead.

flat sorrel Sep 21, 2020, 6:14 AM

#

Start from this ^

little skiff Sep 21, 2020, 9:57 AM

#

Got buried in General so I will share it here, encryption algorithm I created!
https://135code.com/135cipher (click 'About' to learn how it works).

135code

A home for custom algorithms and an API to match.

fallow lynx Sep 21, 2020, 11:44 AM

#

I am not a computer scientist, if I were, I think I'd already know the answer to this question. In python, what is the best way to achieve this:

I have an RESTful API I am using that is built on top of the requests library. That API has about 6 or 7 endpoints that I call. I would like to wrap each endpoint with a retry capability in case the http request fails. Basically, if error 429, wait a certain amount of time and try again.

I was thinking I could wrap each function. But then I would have to write 6 or 7 wrapper functions. Isn't there a way I could to this with just one function, and not have to introduce as much code to maintain? For example:

get_option_chain('GOOG') # API Endpoint 1
get_quote('G00G')  # API Endpoint 2
get_price_history('GOOG', startDate, endDate) # API Endpoint 3

retry(get_price_history('GOOG', startDate, endDate), timeout) # Something like this, can you do this?

fallow lynx Sep 21, 2020, 12:09 PM

#

I think I figured it out.

from time import time, sleep

def retry(function, timeout = 30, *args, **kwargs):
  done = False
  start = time()
  while done:
    if (time()-start) > timeout:
      done = True
      ret = function(args, kwargs)
    else:
      try:    
        ret = function(args, kwargs)
      except:
        pass
        sleep(0.1)
      else:
        done = True
  return ret

oblique panther Sep 21, 2020, 3:48 PM

#

@fallow lynx this is a question for #web-development

proven nimbus Sep 21, 2020, 3:48 PM

#

Hi I’m trying to creat a list of five random integers between 0 and 9 but I’m so confused on how tot do that

#

to*

oblique panther Sep 21, 2020, 3:49 PM

#

!docs random

halcyon plankBOT Sep 21, 2020, 3:49 PM

#

`random`

Source code: Lib/random.py

This module implements pseudo-random number generators for various distributions.

For integers, there is uniform selection from a range. For sequences, there is uniform selection of a random element, a function to generate a random permutation of a list in-place, and a function for random sampling without replacement.

On the real line, there are functions to compute uniform, normal (Gaussian), lognormal, negative exponential, gamma, and beta distributions. For generating distributions of angles, the von Mises distribution is available.... read more

oblique panther Sep 21, 2020, 3:49 PM

#

@proven nimbus take a look at that page

runic tinsel Sep 21, 2020, 3:49 PM

#

the link that says random or the read more link at the bottom

proven nimbus Sep 21, 2020, 3:53 PM

#

I have the random integers generating but I’m trying to get a list of 5 of them. It’s only printing one . Here’s my current code

#

*** from random import randrange
mylist = []

x = randrange(10)
mylist.append(x)

print(mylist)***

agile sundial Sep 21, 2020, 3:56 PM

#

well you only added one number to the list

oblique panther Sep 21, 2020, 3:59 PM

#

@proven nimbus try using random.sample and range

#

there isn't actually a function in random specifically for getting a list of n random integers, but it can be created easily using those two.

snow swift Sep 21, 2020, 7:55 PM

#

@oblique panther random.sample is w/o replacement

#

better to use randrange in a loop

quasi oracle Sep 21, 2020, 8:00 PM

#

random.choices will do the job if you need replacement

stable pecan Sep 21, 2020, 8:00 PM

#

choices also nice because you can use weights

proven nimbus Sep 22, 2020, 12:03 AM

#

I also have a code to print three random floats

#

But I’m trying to append it cause I need them in a list

#

But I don’t know where in the code to place it

#

import random
for i in range(3):
print(random.random())

#

This is what I have rn

#

But I need the random floats in a list

#

When it prints

snow swift Sep 22, 2020, 12:24 AM

#

instead of print using lst.append() where lst is a list

#

@proven nimbus

frank harbor Sep 22, 2020, 2:14 AM

#

What does it mean when my instructor says two sequence types need to be "parallel"?

#

How is that established?

snow swift Sep 22, 2020, 2:19 AM

#

example usage?

#

probably means something like having keys in one list

#

and values in another

#

@frank harbor

#

nonstandard terminology for surr

frank harbor Sep 22, 2020, 2:22 AM

#

📎 Capture.PNG

#

Its worded oddly, i just don't really get what he wants

snow swift Sep 22, 2020, 2:31 AM

#

it just means that each element in group 2 corresponds to a element in group 1

#

but that doesn't really matter for the question

real fulcrum Sep 22, 2020, 2:42 AM

#

📎 graph.PNG

#

how do i make my graph start at (0,0)?

flat sorrel Sep 22, 2020, 2:54 AM

#

https://matplotlib.org/3.1.1/api/_as_gen/matplotlib.pyplot.xlim.html

fierce bear Sep 22, 2020, 7:01 AM

#

@split crystal dont know if i picked the right one but here is the code

#

      lenght = len(sequence)
      if lenght <= 1:
        return sequence
      else:
        pivot = sequence.pop()

      item_greater = []
      items_lower = []

      for  item in sequence:
        if item > pivot:
              items_greater.append(item)

      else:
             items_lower.append(item)

    return quick_sort(items_lower) + [pivot] + quick_sort(items_greater)

print(quick_sort([5,6,7,8,9,8,7,6,5,6,7,8,9,0]))```

#

i ran it on google colab and it said there is an error at line 19

split crystal Sep 22, 2020, 7:02 AM

#

Oh, grab one of the non-topic related ones. Scroll up top, and right now, there's #help-carrot and #help-burrito available

fierce bear Sep 22, 2020, 7:03 AM

#

ah ok

#

sent

fair summit Sep 22, 2020, 7:26 AM

#

@fierce bear your return is mis-indented, but keep in mind a proper implementation of quicksort is in place, you must not create new arrays to append to

fierce bear Sep 22, 2020, 7:27 AM

#

ah ok thanks

oblique panther Sep 22, 2020, 5:38 PM

#

Oh, grab one of the non-topic related ones. Scroll up top, and right now, there's #help-carrot and #help-burrito available
@split crystal questions about sorting algorithms are definitely on topic for this channel

fiery cosmos Sep 22, 2020, 8:36 PM

#

📎 Capture1.PNG

#

import os

os.system ('cls')

division = 1/0.2
print(division)

oblique panther Sep 22, 2020, 9:00 PM

#

@fiery cosmos try opening a help session. See #❓｜how-to-get-help

#

However it's not clear what you're trying to do

fiery cosmos Sep 22, 2020, 9:06 PM

#

Im just trying to know why do i got i that error message

fiery cosmos Sep 22, 2020, 11:54 PM

#

is computer science in college/university very math heavy ?

barren jasper Sep 23, 2020, 12:53 AM

#

im not taking a python compsci class

#

but my ap (college level) computer science class uses java, and it is very math heavy

#

so i think it would be math heavy regardless of what language you use

fair summit Sep 23, 2020, 1:00 AM

#

depends on the exact program, but yes, it likely will be fairly math heavy @fiery cosmos

#

the scope of what "math" is needed, as well as what you even consider math can vary tho, for example:

computer graphics is super heavy in linear algebra
optimization is heavy on calculus
DSA courses will have discrete math requirements, and so will theory of computation classes
ML is heavy in stats and proba, as well as linalg/calc depending on what you do
and you have a bunch of other "nicher" courses like type theory which can go extremely deep into category theory, cryptography depends heavily on many numerical analysis, etc

#

really, computer science is a branch of math itself

oblique panther Sep 23, 2020, 5:17 AM

#

@fiery cosmos computer science is applied math, but programming and computer science aren't exactly the same thing. I'm focusing on AI and there's a lot of linear algebra and statistics, but you don't have to perform calculations by hand because that's what the computer is for. But you do have to understand how to apply the math towards a given problem.

#

If you're interested in computer science but don't think you like math, it may be that you don't enjoy performing calculations by hand (I don't, and that's why I hated math for many years), or that you just haven't enjoyed the way it was presented. The only math class I enjoyed in high school was geometry because it was theory rich but the calculations weren't hard if you understood the theory.

waxen meadow Sep 23, 2020, 1:56 PM

#

https://stackoverflow.com/questions/64027528/how-could-i-get-my-intern-computer-audio-in-real-time

Guys could you help me 👆

Stack Overflow

How could i get my intern computer audio in real time?

Ok so i would like to make a program that listen my computer audio in real time, and when it says some word what i defined as important it alerts me... (the code is in python), I used the speech

oblique panther Sep 23, 2020, 2:52 PM

#

@waxen meadow this isn't a computer science question. I would try opening a help session. See #❓｜how-to-get-help

eager hamlet Sep 23, 2020, 2:57 PM

#

so, trying this problem: ```
During the play, the player can place more than one piece in the same square. The board squares are assumed big enough so that a piece is never an obstacle for any other piece to move freely.

The player's goal is to move the pieces so as to gather them all in the same square - in the minimal number of moves. To achieve this, he must move the pieces as prescribed above. Additionally, whenever the king and one or more knights are placed in the same square, the player may choose to move the king and one of the knights together from that point on, as a single knight, up to the final gathering point. Moving the knight together with the king counts as a single move.

Write a program to compute the minimum number of moves the player must perform to produce the gathering. The pieces can gather on any square, of course.

PROGRAM NAME: camelot
INPUT FORMAT
Line 1: Two space-separated integers: R,C, the number of rows and columns on the board. There will be no more than 26 columns and no more than 30 rows.
Line 2..end: The input file contains a sequence of space-separated letter/digit pairs, 1 or more per line. The first pair represents the board position of the king; subsequent pairs represent positions of knights. There might be 0 knights or the knights might fill the board. Rows are numbered starting at 1; columns are specified as upper case characters starting with `A'.
SAMPLE INPUT (file camelot.in)
8 8
D 4
A 3 A 8
H 1 H 8
The king is positioned at D4. There are four knights, positioned at A3, A8, H1, and H8.

OUTPUT FORMAT
A single line with the number of moves to aggregate the pieces.
SAMPLE OUTPUT (file camelot.out)
10
SAMPLE OUTPUT ELABORATION
They gather at B5.
Knight 1: A3 - B5 (1 move)
Knight 2: A8 - C7 - B5 (2 moves)
Knight 3: H1 - G3 - F5 - D4 (picking up king) - B5 (4 moves)
Knight 4: H8 - F7 - D6 - B5 (3 moves)
1 + 2 + 4 + 3 = 10 moves.```(knights and kings move as they do in chess)

#

however, the bfs for my current code: https://paste.pythondiscord.com/hetocatawe.sql works too slow for a 26*30 (a whole fricking 6 seconds)

#

any optimization tricks? the problem's in the knightExpand, all others are for context

#

(ping please)

oblique panther Sep 23, 2020, 3:26 PM

#

@eager hamlet do you have a testcase? I can try finding the bottleneck.

eager hamlet Sep 23, 2020, 3:28 PM

#

oh

#

@oblique panther it's just doing knightCalc for each square (max dims 26 * 30)

#

barren holly Sep 23, 2020, 3:31 PM

#

where do i get help

oblique panther Sep 23, 2020, 3:31 PM

#

@barren holly see #❓｜how-to-get-help

#

@eager hamlet what do you pass to knightExpand?

eager hamlet Sep 23, 2020, 3:41 PM

#

uh a point

#

coordinates

oblique panther Sep 23, 2020, 3:42 PM

#

I'm not clear what the entry point is

eager hamlet Sep 23, 2020, 3:44 PM

#

the entry point?

#

what's that

oblique panther Sep 23, 2020, 3:45 PM

#

where the program is intended to start from

#

I made the camelot.in file but I don't know how to see the solution.

eager hamlet Sep 23, 2020, 3:46 PM

#

oh um

#

i haven't done the whole thing

#

these are just some precalculations

oblique panther Sep 23, 2020, 3:49 PM

#

well as you work on it, what I would do is see how the performance scales relative to the dimensions of the board and the number of pieces.

#

and for each component, look up if there's a more efficient known solution for that component

#

but it's a known problem that Python can't always compute fast enough for these challenges, so I would focus on learning what solutions are possible and how they work

eager hamlet Sep 23, 2020, 3:52 PM

#

but given this code, are there any optimizations?

oblique panther Sep 23, 2020, 3:58 PM

#

I'm not sure what it does

#

I'd want to run it through a profiler though

fiery cosmos Sep 23, 2020, 8:10 PM

#

Hi guys i'm totally new to python, I reckon this is the better place for me to ask where to get started on python(im a computer science student)

#

TIA

vocal gorge Sep 23, 2020, 8:18 PM

#

!resources

halcyon plankBOT Sep 23, 2020, 8:18 PM

#

Resources

The Resources page on our website contains a list of hand-selected learning resources that we regularly recommend to both beginners and experts.

oblique panther Sep 23, 2020, 8:54 PM

#

@fiery cosmos check out the resources link that ConfusedReptile summoned. Note that programming in general isn't what is meant by "computer science" for this channel.

fiery cosmos Sep 23, 2020, 8:58 PM

#

Thank you

eager hamlet Sep 23, 2020, 11:29 PM

#

problem: https://paste.pythondiscord.com/eqosotokar.py
my code: https://paste.pythondiscord.com/tupopidewo.py
too slow for: https://train.usaco.org/usacodatashow?a=Lm0EIbK73LK
any help? (it's the knightExpand that takes too long, any optimizations? maybe caching or something? and ping plz)

#

(i opened a help channel already so i can delete my message if you guys want)

#

@plush rain don't think this is the right place

plush rain Sep 23, 2020, 11:31 PM

#

@eager hamlet sorry about that

stuck tide Sep 24, 2020, 12:22 AM

#

Have someone read "Hands On Machine Learning" ?

eager hamlet Sep 24, 2020, 12:23 AM

#

kinda sounds like a #data-science-and-ml question but im reading it

stuck tide Sep 24, 2020, 12:23 AM

#

If the answer is yes. Can you give me any advises to have the best knowleage?

eager hamlet Sep 24, 2020, 12:23 AM

#

no

#

maybe go to #data-science-and-ml and ask your question bruh

bronze drift Sep 24, 2020, 6:44 PM

#

i have this

sum=0;
for(i=0;i<n;i++)
  for(j=0;j<i;j++)
    sum++;

why is this Big oh n^2 and not Big oh n * i ?

half lotus Sep 24, 2020, 6:53 PM

#

Think of the number of operations as a series

#

Roughly (n - 0) + ... + (n - n) operations in total

#

That's equivalent to

📎 unknown.png

#

1/2 can be taken out since it's constant

#

n(n + 1) can be written as n² + n

#

And with big o you only look at highest order term

#

hence n²

#

It's clearer and more accurate to write the series as (n - (n - 1)) + ... + (n - 0) actually

#

Or maybe just start at (n - n), I don't know. The exclusivity is confusing me a bit right now. It's not really important here. Either way, it'll come out to n²

bronze drift Sep 24, 2020, 6:59 PM

#

like if is like this

sum =0;
  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
      sum++;

it's clear that it is n^2

#

but then j < i . idk i just thought it would be n * i

half lotus Sep 24, 2020, 7:00 PM

#

I'm not sure how to explain it in a more intuitive way, but mathematically it does come out to n²

bronze drift Sep 24, 2020, 7:00 PM

#

is it cuz i depends on n?
i < n

#

how'd u even come up with that series tho

half lotus Sep 24, 2020, 7:01 PM

#

For the sake of an example, pick a value for n, like 4

#

And step through the code to see how many times it does sum++

#

And you'll eventually start to see a pattern

gusty grove Sep 25, 2020, 11:45 AM

#

for n = 10:
1 + 2 + 3 + ... + 10
now you can create groups like this:
1 + 10 = 11
2 + 9 = 11
3 + 8 = 11
...
as you can see it always adds up to 11 or n+1

#

since there are n/2 groups

#

you have a total sum of (n+1)*n/2 for n=10: (10+1)*(10/2) = 55

fiery cosmos Sep 25, 2020, 4:05 PM

#

does anyone know how to make a ransomware from python?

#

GWgoaThinken

fair summit Sep 25, 2020, 4:08 PM

#

!rule 5

halcyon plankBOT Sep 25, 2020, 4:08 PM

#

Rules

5. Do not provide or request help on projects that may break laws, breach terms of services, be considered malicious/inappropriate or be for graded coursework/exams.

quasi oracle Sep 25, 2020, 4:32 PM

#

@fiery cosmos yeah don't ask about this sort of stuff here

fiery cosmos Sep 25, 2020, 4:32 PM

#

oh

#

srry :(

brazen glade Sep 25, 2020, 4:33 PM

#

I have a question. Do types like lists, tuples, modules, strings, and numbers all inherit from 'object' with this 'new style' python class concept?

fair summit Sep 25, 2020, 4:36 PM

#

yes

topaz pulsar Sep 25, 2020, 4:36 PM

#

I don't think modules can as they are files of code but those other objects do, if you want to see what a class inherits from you can do <object>.__mro__ but that only works on classes, not instances, if you have an instance you will need to check <instance>.__class__.__mro__

#

wait do modules inherit from class??

fair summit Sep 25, 2020, 4:37 PM

#

every value in python inherit from object

#

every type inherit from type, which inherits from object

topaz pulsar Sep 25, 2020, 4:37 PM

#

i was thinking of like <module 'math' (built-in)> which is a file so i didn't think it was an 'object' as such

fair summit Sep 25, 2020, 4:37 PM

#

it is

topaz pulsar Sep 25, 2020, 4:38 PM

#

ah ok then

brazen glade Sep 25, 2020, 4:39 PM

#

It's weird in my head to think of a given top-level module like "videogame.py" as a sub-class instead of thinking of executable scripts like that as being its own non-data type entity

brave oak Sep 25, 2020, 7:38 PM

#

i was thinking of like <module 'math' (built-in)> which is a file so i didn't think it was an 'object' as such
@topaz pulsar modules are typically loaded from disk, yes

#

but a module object is just an abstraction

#

you could create one purely in code if you wanted

#

but a module object is just an abstraction
@brave oak and this is distinct from a source file existing on disk, which is also called a “module”

topaz pulsar Sep 25, 2020, 7:58 PM

#

👍 thanks for the clarification

fiery cosmos Sep 26, 2020, 4:29 AM

#

I'm currently in 11th .
Can someone help me with the program -
Series and sum (1/1! + 1/2! + 1/3! + 1/n!= Sum)

oblique panther Sep 26, 2020, 4:50 AM

#

@fiery cosmos that's a math question. However there is a math discord.

fiery cosmos Sep 26, 2020, 4:50 AM

#

Wait whaa

oblique panther Sep 26, 2020, 4:50 AM

#

https://discord.gg/rk4BWZ

feral wadi Sep 26, 2020, 5:31 AM

#

@oblique panther you're a jenius

oblique panther Sep 26, 2020, 5:31 AM

#

nope

#

2 + 2 = 5

#

change my mind

feral wadi Sep 26, 2020, 5:32 AM

#

aah

#

i were saying you got resources for all problems man

oblique panther Sep 26, 2020, 5:38 AM

#

@fiery cosmos I'm not sure why you deleted your message

#

feel free to ask it again if it relates to the topic of this channel, otherwise take a look at #❓｜how-to-get-help to open a help session

fiery cosmos Sep 26, 2020, 5:45 AM

#

ok

#

i realised i was too tired to continue

north cosmos Sep 26, 2020, 9:00 AM

#

@oblique panther thx a lot i needed that a lot, you're a life saver

fiery cosmos Sep 26, 2020, 9:46 AM

#

Binary number configaration of abc....

fiery cosmos Sep 26, 2020, 1:59 PM

#

Well...

#

📎 Screenshot_20200920_120812.jpg

agile sundial Sep 26, 2020, 2:00 PM

#

division by zero..

crimson jacinth Sep 26, 2020, 7:20 PM

#

can i post an OOP question here?

half lotus Sep 26, 2020, 7:23 PM

#

Sure

crimson jacinth Sep 26, 2020, 7:30 PM

#

basically, I want to create a plugin architecture where users can implement certain optional features and my base application will be able to call the implemented methods at runtime if the optional feature method was implemented.

#

How can I know that a certain feature was implemented for a given subclass?

#

Here is an example:

class PluginBase():
  registry = []
    def __init_subclass__(cls, **kwargs):
        super().__init_subclass__(**kwargs)
        cls.registry.append(cls())

    def abstractMethod1():

    def abstractMethod2():


class PluginA(PluginBase):
    def abstractMethod1():
      print("Plugin A implements method 1")

class PluginB(PluginBase):
    def abstractMethod2():
      print("plugin B implements method 2")

how can i know at runtime that B supports method 2 but not method 1 and A supports the opposite?
Can I use decorators to achieve this?

oblique panther Sep 26, 2020, 9:40 PM

#

@crimson jacinth that question isn't on topic for this channel, so someone who knows the answer might not see it. Take a look at #❓｜how-to-get-help

#

However I would check if abc can solve this

#

!docs abc

halcyon plankBOT Sep 26, 2020, 9:43 PM

#

`abc`

Source code: Lib/abc.py

This module provides the infrastructure for defining abstract base classes (ABCs) in Python, as outlined in PEP 3119; see the PEP for why this was added to Python. (See also PEP 3141 and the numbers module regarding a type hierarchy for numbers based on ABCs.)... read more

oblique panther Sep 26, 2020, 9:49 PM

#

!docs abc.ABCMeta.register

halcyon plankBOT Sep 26, 2020, 9:49 PM

#

`abc.ABCMeta.register`

register(subclass)```
Register *subclass* as a “virtual subclass” of this ABC. For example:

```py
from abc import ABC

class MyABC(ABC):
    pass

MyABC.register(tuple)

assert issubclass(tuple, MyABC)
assert isinstance((), MyABC)
```   Changed in version 3.3: Returns the registered subclass, to allow usage as a class decorator.

Changed in version 3.4: To detect calls to [`register()`](#abc.ABCMeta.register "abc.ABCMeta.register"), you can use the [`get_cache_token()`](#abc.get_cache_token "abc.get_cache_token") function.

ancient galleon Sep 26, 2020, 11:44 PM

#

📎 screen_shot_2020-09-21_at_8.07.22_pm.png

agile sundial Sep 27, 2020, 12:33 AM

#

funny, but off topic for this channel

austere sparrow Sep 27, 2020, 2:26 PM

#

@brazen glade This is off topic for this channel. See #❓｜how-to-get-help

#

okay, I'm kinda late to the party 😐

pulsar light Sep 27, 2020, 4:39 PM

#

can anyone explain what kubernetes is and does?

rocky stirrup Sep 27, 2020, 4:47 PM

#

import sys,re
var=open("res.txt",'w')
a=1
for i in open(sys.argv[1],'r'):
x=re.search("[.!]??(.$)",i,re.S)
var.write("Ligne "+str(a)+" résultat : "+x.group(1))
a+=1

#

Hey ,please can someone tell me what the pattern in line 5 do !?

fiery cosmos Sep 27, 2020, 4:59 PM

#

Anyone know how to make a bar graph that is stacked without using matplotlib

oblique panther Sep 27, 2020, 5:03 PM

#

@pulsar light try asking in #tools-and-devops
@fiery cosmos try asking in #data-science-and-ml

pulsar light Sep 27, 2020, 5:03 PM

#

@oblique panther yeah , i did . thanks :)

oblique panther Sep 27, 2020, 5:07 PM

#

@rocky stirrup [.!]? matches any number of . or ! in a row, but it's okay if they're not there

#

(.$) matches the last character of the string, whatever it is

#

I'm trying to figure out what the ? in the middle is for

oblique panther Sep 27, 2020, 7:02 PM

#

😻

agile sundial Sep 27, 2020, 7:03 PM

#

:)

eager hamlet Sep 27, 2020, 7:47 PM

#

well
the channel got renamed

silk chasm Sep 27, 2020, 7:49 PM

#

was this computer science?

west surge Sep 27, 2020, 8:03 PM

#

Yes

wheat laurel Sep 27, 2020, 9:12 PM

#

I have a list of strings [s1, s2, s3, ... , si] and some function f which takes a list of strings, but can only function on a maximum number of characters. Say 100 - I need to break up the list into smaller sections and process them using f, then combine them afterwards.

The issue is that if s1 has 100 chars and the rest have 1, then splitting it in half won't be a suitable solution as the created split will still have too many chars.

I wasn't sure what the best approach for this is - it seems like something that should be a thing though. Perhaps a recursive solution would be best?

oblique panther Sep 27, 2020, 9:13 PM

#

well
the channel got renamed
@eager hamlet isn't it awesome?!?!?!?!?!?!

#

@wheat laurel as I recall, if your goal is to group the strings into the fewest number of chunks, you can use a greedy solution

wheat laurel Sep 27, 2020, 9:15 PM

#

yeah - I want the fewest number

#

greedy is a pretty broad term afaik tho?

#

unless you just mean -

while < max:
   add to list

#

something like that - and if it's more than max, make a new one

oblique panther Sep 27, 2020, 9:16 PM

#

by greedy solution, I mean that a locally optimal decision will result in a globally optimal solution

#

and there might be a more elegant way of saying that

wheat laurel Sep 27, 2020, 9:17 PM

#

maybe, i don't really know what you mean by it exactly

oblique panther Sep 27, 2020, 9:17 PM

#

so if you start from the beginning of the list and take as many consecutive strings whose char counts add up to just below the limit for a chunk

wheat laurel Sep 27, 2020, 9:17 PM

#

yes i just said that and gave pseudo code

oblique panther Sep 27, 2020, 9:18 PM

#

you don't have to think about whether some other grouping would be more optimal

wheat laurel Sep 27, 2020, 9:18 PM

#

ok fair, yeah that might be the most straightforward too 🤔

#

thought maybe it called for recursion, i never use that ha

oblique panther Sep 27, 2020, 9:18 PM

#

does each chunk have to be in the same order as in the original list?

wheat laurel Sep 27, 2020, 9:18 PM

#

order is very important

oblique panther Sep 27, 2020, 9:18 PM

#

alright

#

do you have any test cases?

wheat laurel Sep 27, 2020, 9:20 PM

#

no - I'll create one, i reckon s = ["hello", "this", "is", "an", "example", "of", "a", "list", "to", "process"] with max_chars = 10 or so might be a fair start

#

S = ["hello", "this", "is", "an", "example", "of", "a", "list", "to", "process"]

max_chars = 10

processed = []
chars = 0
p = []
for s in S:
    if len(functools.reduce(operator.add, p + [s])) > max_chars:
        print("neeed a new list", s)
        processed.append(p)
        p = []

    else:
        p.append(s)

@oblique panther kinda rough i guess

#

🤔 guess it'll do

📎 unknown.png

#

I don't do a fat lot of this kinda stuff to be honest - so if there are any obvious improvements I'd be happy to hear them 🙂

#

I thought there might be a name for this, felt like something that was probably a common task / 101 comp sci question kinda thing

oblique panther Sep 27, 2020, 9:29 PM

#

you don't need to combine reduce with add because sum basically already does that. It just applies __add__ between everything in an iterable, however that happens to be implemented, starting with 0.

#

I wish union was already implemented to do that with | but such is life.

wheat laurel Sep 27, 2020, 9:30 PM

#

S = ["hello", "this", "is", "an", "example", "of", "a", "list", "to", "process"]
max_chars = 10
if len("".join(S)) > max_chars:
    processed = []
    p = []
    for s in S:
        if len("".join(p + [s])) > max_chars:
            processed.append(p)
            p = []
        else:
            p.append(s)
else:
    processed = S

#

idk, nesting ifs and fors feels like it might be a bit messy?

oblique panther Sep 27, 2020, 9:31 PM

#

I'm not sure I follow the logic here

#

why is the for loop for scanning S inside an if statement?

wheat laurel Sep 27, 2020, 9:31 PM

#

because if the list is small enough to start with I don't bother

oblique panther Sep 27, 2020, 9:32 PM

#

well, I would start by putting this into a function that takes a list of strings and a char limit

wheat laurel Sep 27, 2020, 9:32 PM

#

s = ['hello', 'i'] wouldn't need to be split

oblique panther Sep 27, 2020, 9:33 PM

#

and if the sum of the char counts is below the given char limit already, then you can just return it right away

#

otherwise you can continue as normal without having to nest everything further to the right.

wheat laurel Sep 27, 2020, 9:33 PM

#

yeah that's cool

oblique panther Sep 27, 2020, 9:33 PM

#

it's a good thought to handle that possibility in advance. I didn't think of that.

#

though a minor consideration is that if you'd be returning the same list that you got to start with

#

whereas if you're making a new list to contain all the chunks, you're creating a new object

#

and that could lead to unexpected behavior.

wheat laurel Sep 27, 2020, 9:36 PM

#

yea - i need to iterate over lists so i"ll return [given] instead of given if it's less than the max len

#

def split_list(*, list_to_split, max_chars):
    if len("".join(list_to_split)) < max_chars:
        ret = [list_to_split]
    else:
        processed = []
        p = []
        for element in list_to_split:
            if len("".join(p + [element])) > max_chars:
                processed.append(p)
                p = []
            else:
                p.append(element)
        ret = processed
    return ret

S = ["hello", "this", "is", "an", "example", "of", "a", "list", "to", "process"]
max_chars = 10

split_list(list_to_split=S, max_chars = max_chars)

oblique panther Sep 27, 2020, 9:43 PM

#

@wheat laurel ret = [list_to_split] actually has the effect of putting list_to_split inside of a new list in which it's the only element

#

so it would be a list of one list of strings

wheat laurel Sep 27, 2020, 9:43 PM

#

yeah - but then I can iterate over whatever is returned and pass the lists to a function which accepts lists

#

if i don't then I'll have to catch the cases of having a lists of strings or a list of lists

oblique panther Sep 27, 2020, 9:43 PM

#

if that's what you want then that's exactly right

#

here's how I'd write it though

#

if sum(len(s) for s in list_to_split) < max_chars:
    return [list_to_split.copy()]

# rest of the code, not in an else block

#

that way the list being returned also contains a new list, and changes to the inner list doesn't affect the original list.

wheat laurel Sep 27, 2020, 9:45 PM

#

changes to the inner list doesn't affect the original list
ah yes, bloody pass by reference

oblique panther Sep 27, 2020, 9:45 PM

#

you don't like that?

wheat laurel Sep 27, 2020, 9:46 PM

#

idk really - i feel that passing by value is more explicit? like how R will copy lists

oblique panther Sep 27, 2020, 9:46 PM

#

eh, it's what I'm used to, I guess.

wheat laurel Sep 27, 2020, 9:46 PM

#

i guess as long as it's consistent it's all good 🙂

oblique panther Sep 27, 2020, 9:47 PM

#

the other remark that I currently have is that I don't agree with using ''.join to get the sum of the lengths. I think using a list comp is more explicit

wheat laurel Sep 27, 2020, 9:47 PM

#

you prefer sum(len(s) for s in list_to_split) to len("".join(list_to_split)), ha i was just writing that

#

think using a list comp is more explicit
yeah you're probably right, probably clearer

oblique panther Sep 27, 2020, 9:48 PM

#

I have to leave all of the sudden but I'll see if I can check this later.

wheat laurel Sep 27, 2020, 9:48 PM

#

no problem , feel free to ping, no worries though - thank you !

oblique panther Sep 27, 2020, 9:48 PM

#

but I asked someone else if a greedy solution was wrong and they said "how else would you do it?", so I assume that's the right track.

wheat laurel Sep 27, 2020, 9:49 PM

#

now i want to find a different way 🙂

oblique panther Sep 27, 2020, 9:49 PM

#

if you decide you don't care about order, you could potentially do it in fewer chunks.

wheat laurel Sep 27, 2020, 9:50 PM

#

yeah, order is super important for this tho unfortunately

fiery cosmos Sep 27, 2020, 9:59 PM

#

https://paste.pythondiscord.com/raw/logoxigesu

oblique panther Sep 27, 2020, 10:50 PM

#

@fiery cosmos I suggest asking a question about the code that you've linked to

wheat laurel Sep 27, 2020, 10:56 PM

#

idk if you had any other thoughts on that list thing @oblique panther but it doesn't seem to work on the data I'm working with, maybe it's the data and i need to test more... seems that there are some dropped values from input to output though, idk if that's some of the internal logic. Maybe I need a better test set 🤔

#

ah yeah, if it's greater than the max then the element can just be ignored it seems

#

hrm

#

yeah it's actually quite a lot messier than assumed to be

oblique panther Sep 27, 2020, 11:08 PM

#

@wheat laurel I know this is a strange question but I what way and how is it not working? Are you getting error messages? Are there hidden test cases that you're apparently not passing?

wheat laurel Sep 27, 2020, 11:09 PM

#

no error

#

just there are cases when an element won't be included into any list

#

so the output will have less information than the input

brave oak Sep 27, 2020, 11:12 PM

#

is this what was #computer-science?

wheat laurel Sep 27, 2020, 11:13 PM

#

yep

oblique panther Sep 27, 2020, 11:13 PM

#

Ya

#

Best name change

wheat laurel Sep 27, 2020, 11:17 PM

#

@oblique panther here's a test case i think:

#

# wget https://raw.githubusercontent.com/Arken94/LanguageIdentification/master/LangId.train.French


p = pathlib.Path("./LangId.train.French")
text = p.read_text()
list_to_split = text.split(" ")

max_chars = 200

amount = sum(len(x) for x in list_to_split)
list_to_split = list_to_split.copy()

if sum(len(str(s)) for s in list_to_split) < max_chars:
    ret = [list_to_split]
else:
    processed = []
    p = []
    for element in list_to_split:
        if sum(len(str(s)) for s in p + [element]) < max_chars:
            p.append(element)
        else:
            processed.append(p + [element])
            p = []

    ret = processed

#

📎 unknown.png

#

idk why ret is more there it was less before but still, they should be the same size

#

📎 unknown.png

#

@oblique panther just to be clear - are you following / considering this or not? If not that's fine, i'll just stop throwing stuff in here that's all

oblique panther Sep 27, 2020, 11:24 PM

#

@wheat laurel I haven't been at my computer for an hour and a half or so but I've been checking here periodically. Though it doesn't hurt to continue discussing the question because anyone can chime in.

wheat laurel Sep 27, 2020, 11:25 PM

#

no worries

#

i'll leave it - if anyone else sees and is curious they can ping me tho

#

# first compute the indicies to split on
count = 0
indices = [0]
for i, el in enumerate(list_to_split):
    count += len(str(el))
    if count > max_chars:
        indices.append(i)
        count = 0

# compute split points for the new lists
split_lists = [list_to_split[s[0] : s[1]] for s in zip(indices[:-1], indices[1:])]

this doesn' tseem to work either

#

hrmok

📎 unknown.png

oblique panther Sep 27, 2020, 11:38 PM

#

@wheat laurel can you post a test case as raw text rather than as an image?

wheat laurel Sep 27, 2020, 11:39 PM

#

sure

#

that's jsut output tho

#


lst = ['Approbation',
 'du',
 'procès',
 '-',
 'verbal',
 'de',
 'la',
 'séance',
 'précédente',
 '\nLe',
 'procès',
 '-',
 'verbal',
 'de',
 'la',
 'séance',
 'd',
 "'",
 'hier',
 'a',
 'été',
 'distribué',
 '.',
 '\nY',
 'a',
 '-',
 't',
 '-',
 'il',
 'des',
 'observations']

max_chars = 50

# first compute the indicies to split on
count = 0
indices = [0]
for i, el in enumerate(lst):
    count += len(str(el))
    if count > max_chars:
        indices.append(i)
        count = 0

# compute split points for the new lists
split_lists = [list_to_split[s[0] : s[1]] for s in zip(indices[:-1], indices[1:])]

# flatten the above - this should be the same as the input now
assert flat == list(itertools.chain.from_iterable(split_lists))

north cosmos Sep 28, 2020, 2:02 AM

#

new channel?

agile sundial Sep 28, 2020, 2:16 AM

#

wonder if the changelog says anything about that

lean dome Sep 28, 2020, 2:20 AM

#

Just a rename of computer-science, to make the purpose clearer to people who weren't already familiar with the meaning of the term

oblique panther Sep 28, 2020, 2:35 AM

#

@wheat laurel flattening the list of lists back out doesn't prove that your solution is correct

#

one thing you can do to clean it up is have another function to count the total chars

#

def _count_chars(list_of_strs):
    return sum(len(s) for s in list_of_strs)

#

that being said I'm not sure why you're using enumerate. I was able to solve it without using that.

#

in my solution, there are three possible situations for each new string that you need to account for. but one of them is an edge case.

boreal linden Sep 28, 2020, 7:09 AM

#

hey guys, if I want to sum the min n/4 elements in an array, I can use linear median finding to do it in O(n). However, I feel like this is also O(n) for the problem, do you agree?

#

create a sorted array B of length n/4, fill B up with the first n/4 digits, then compare the largest integer of B to the next integer in A. If the next integer in A is smaller, insert it in B and remove the larger one. Lastly, compute sum(B). Runs in O(n)

#

assuming A is the array where you find the n/4 min element sum from

flat sorrel Sep 28, 2020, 7:55 AM

#

I believe initially populating B would require O(n log n). The ith insertion would cost you C * log(i - 1) where C is a constant. The total cost of populating B with the first n/4 elements would thus be C * sum(log(i) for i = 1 to i/4 - 1) = C * log((i/4-1)!) which would then be O(n log n)

rocky stirrup Sep 28, 2020, 8:15 AM

#

hey , I should reduce this code from 7 lines to only 2 , can someone help me :

#

def fac(*x):
for a in range(len(x)):
r = 1
for i in range(list(x).pop(a)):
r+= r * i
print("\nLa factorielle de",x[a],"est :",r)
fac(x-1,y-1)

fervent quiver Sep 28, 2020, 8:36 AM

#

How do you get the last item of lifoqueue?

#

Im trying to do something like

from queue import LifoQueue
stack = LifoQueue()

print(stack[-1])

#

if that was a list it wouldnt give me an error

#

but for lifoqueue, it does

flat sorrel Sep 28, 2020, 8:37 AM

#

what do you mean by last item of lifoqueue?

#

the last inserted item?

fervent quiver Sep 28, 2020, 8:37 AM

#

yea

flat sorrel Sep 28, 2020, 8:38 AM

#

isn't that just lifoqueue.get()?

fervent quiver Sep 28, 2020, 8:38 AM

#

get would remove the last item tho

flat sorrel Sep 28, 2020, 8:39 AM

#

well you could just add it back in immediately

fervent quiver Sep 28, 2020, 8:39 AM

#

oh yea, that'd be the best solution then

#

thanks

flat sorrel Sep 28, 2020, 8:40 AM

#

@rocky stirrup That would belong in #esoteric-python

wheat laurel Sep 28, 2020, 8:43 AM

#

@oblique panther shows it's incorrect, not correct

#

I've done it now anyway

fringe salmon Sep 28, 2020, 9:20 AM

#

could somebody help me with depth-first-search

#

could somebody help me with depth-first-search
@fringe salmon i've understood it but its harder in implementing in python

agile sundial Sep 28, 2020, 1:16 PM

#

@fringe salmon what specifically do you need help with

fringe salmon Sep 28, 2020, 1:53 PM

#

source code, i've understood it but having trouble making graph with all the func such as. insert_node(), insert_new_edge() and all

#

ans also i want to add DFS

oblique panther Sep 28, 2020, 2:38 PM

#

I've done it now anyway
@wheat laurel so it's turned in and you can't change your solution?

wheat laurel Sep 28, 2020, 2:40 PM

#

@oblique panther there's no "turned in", it was just something that I wanted to do for a module that I was working on

oblique panther Sep 28, 2020, 2:42 PM

#

@wheat laurel if you don't intend to continue working on it and it's not for a grade, I can show you the solution

wheat laurel Sep 28, 2020, 2:42 PM

#

sure, would be interesting - i just used pandas in the end

oblique panther Sep 28, 2020, 2:43 PM

#

How did you do it with pandas?

wheat laurel Sep 28, 2020, 2:44 PM

#

took a cumulative sum of the char counts modulo the max size, which gives a monotonic sequence, and grouped by that

#

i figured it might be a classic CS problem or something I guess, but all good

oblique panther Sep 28, 2020, 2:46 PM

#

Well, it's a straightforward way to teach greedy algorithms, so in that sense it is a classic CS problem

wheat laurel Sep 28, 2020, 2:47 PM

#

well it wasn't so straightforward with those 😄

oblique panther Sep 28, 2020, 2:55 PM

#

!e

def _count_chars(list_of_strs):
    return sum(len(s) for s in list_of_strs)

def chunk_strs(list_of_strs, chunk_size):
    if _count_chars(list_of_strs) < chunk_size:
        return [list_of_strs.copy()]
  
    outer_list = [[]]

    for s in list_of_strs:
        if len(s) > chunk_size:
            raise ValueError('We don\'t know what to do when one string is longer than the chunk size.')
        if _count_chars(outer_list[-1]) + len(s) > chunk_size:
            outer_list.append([s])
            continue
        outer_list[-1].append(s)
    
    return outer_list

sample = ["hello", "this", "is", "an", "example", "of", "a", "list", "to", "process"]

print(chunk_strs(sample, 10))

halcyon plankBOT Sep 28, 2020, 2:55 PM

#

@oblique panther :white_check_mark: Your eval job has completed with return code 0.

[['hello', 'this'], ['is', 'an'], ['example', 'of', 'a'], ['list', 'to'], ['process']]

oblique panther Sep 28, 2020, 2:55 PM

#

@wheat laurel if the next string would take you over the limit, you add a new list that contains it to the end. Otherwise you just keep adding the current string to the last list.

#

I wasn't sure how you were supposed to handle individual strings that are larger than the limit, so that raises an error.

wheat laurel Sep 28, 2020, 2:57 PM

#

@oblique panther ah ok, cool 🙂 I don't do much in this kinda style (?) I guess, more pandas (hence me falling back on that 😄 )

#

thanks

oblique panther Sep 28, 2020, 2:59 PM

#

pandas is spooky for me, so that's cool

#

@fringe salmon could you share the code you have so far?

oblique panther Sep 28, 2020, 3:43 PM

#

@fringe salmon the most straightforward way to have a DFS is to have a way to keep track of which nodes you've visited, and then use recursion. So if a node has two or more edges, you take one edge and follow it as far as you can before following the second edge.

fringe salmon Sep 28, 2020, 3:44 PM

#

i'm sharing my code of what i've done till far

oblique panther Sep 28, 2020, 3:44 PM

#

class Graph:

    def dfs(self):
        visited = set()  # assuming nodes are hashable--use a dataclass?
        def _dfs(current_node):
            # actual search
        _dfs(self.nodes[0])

fringe salmon Sep 28, 2020, 3:50 PM

#

https://codeshare.io/5P7x1o

#

you can make changes in dfs()

#

@oblique panther

oblique panther Sep 28, 2020, 3:53 PM

#

@fringe salmon it won't load, can you use our pastebin?

#

!paste

halcyon plankBOT Sep 28, 2020, 3:53 PM

#

Pasting large amounts of code

If your code is too long to fit in a codeblock in discord, you can paste your code here:
https://paste.pydis.com/

After pasting your code, save it by clicking the floppy disk icon in the top right, or by typing ctrl + S. After doing that, the URL should change. Copy the URL and post it here so others can see it.

fringe salmon Sep 28, 2020, 3:54 PM

#

https://paste.pythondiscord.com/hugikuqelu.rb

oblique panther Sep 28, 2020, 3:57 PM

#

@fringe salmon alright, so can you think of how you'd use recursion to solve this?

#

remember that my suggestion is to have a separate function defined within Graph.dfs that you use for recursion.

fringe salmon Sep 28, 2020, 4:00 PM

#

do you have any recursion exiting line to start with

#

i'm having trouble there

oblique panther Sep 28, 2020, 4:01 PM

#

recursion exiting line?

#

as in, the base case?

fringe salmon Sep 28, 2020, 4:08 PM

#

as in, the base case?
@oblique panther yeah

oblique panther Sep 28, 2020, 4:08 PM

#

so if you get to a node, how would you know if there's no more work to do for that node?

fringe salmon Sep 28, 2020, 4:10 PM

#

each node has an attribute node.visited which is by default set to False

#

if its True then there is no more work to do

oblique panther Sep 28, 2020, 4:13 PM

#

try that

fringe salmon Sep 28, 2020, 4:26 PM

#

hey, it worked ig

#

@oblique panther

#

    def find_node(self, node_val):
        for node in self.nodes:
            if node.value == node_val:
                node_val = node
        return node_val

    def clear_visited(self):
        for node in self.nodes:
            node.vistied = False

    def dfs(self, start_node):
        # checks back all node.visted back to False
        self.clear_visited()
        # check for start_node value in nodes
        start_node = self.find_node(start_node)
        # using dfs_helper
        return self.dfs_helper(start_node)

    def dfs_helper(self, start_node):
        ret_list = [start_node.value]
        start_node.visited = True

        for neighbour in start_node.edges:
            if not neighbour.node_to.visited:
                ret_list.extend(self.dfs_helper(neighbour.node_to))

        return ret_list

oblique panther Sep 28, 2020, 4:29 PM

#

@fringe salmon you have test cases for which this worked?

fringe salmon Sep 28, 2020, 4:30 PM

#

graph = Graph()
graph.insert_node(1)
graph.insert_node(2)
graph.insert_node(3)
graph.insert_new_edge(100, 1, 2)
graph.insert_new_edge(101, 2, 3)
graph.insert_new_edge(102, 3 ,1)
print(graph.get_adjacency_list())
print(graph.get_edge_list())
print(graph.dfs(1))```

oblique panther Sep 28, 2020, 4:30 PM

#

and it worked?

#

the output was what you expected?

fringe salmon Sep 28, 2020, 4:31 PM

#

📎 Screenshot_2020-09-28_at_10.01.08_PM.png

#

first two lines are adjacency_list and edge_list

#

code is still dicy, but it works

exotic kiln Sep 28, 2020, 5:12 PM

#

I need a article about append method time comparison, between list-dict-queue-dequeue vs.vs.. can someone give link?

oblique panther Sep 28, 2020, 5:31 PM

#

@exotic kiln I don't know one off the top of my head. Do you have a question about that?

#

also I don't believe there's really a difference between queues and deques other than that deques let you do more

#

a queue lets you pop from the start of the queue and append to the end. A deque lets you append or pop from either side, but all of these operations are still O(1)

austere sparrow Sep 28, 2020, 5:33 PM

#

@exotic kiln https://wiki.python.org/moin/TimeComplexity

oblique panther Sep 28, 2020, 5:36 PM

#

collections gives you a deque but not a queue or a stack because you can do O(1) queue and stack operations with a deque.

austere sparrow Sep 28, 2020, 5:37 PM

#

we also have an immutable (in some sense) linked list/stack, but it only supports up to 1000 elements 🙂

fair summit Sep 28, 2020, 8:51 PM

#

@austere sparrow what are you referring to here ?

quasi oracle Sep 28, 2020, 8:56 PM

#

I'd guess the program's stack, with a 999 recursion limit

fiery cosmos Sep 28, 2020, 8:56 PM

#

what is recursion?

quasi oracle Sep 28, 2020, 8:57 PM

#

When a function calls itself

fiery cosmos Sep 28, 2020, 8:57 PM

#

def a():
  if True:
    a()

quasi oracle Sep 28, 2020, 8:59 PM

#

Yeah, and this one would definitely lead you to the recursion limit

fiery cosmos Sep 28, 2020, 9:00 PM

#

so there is a 999 recursion limit, its not like a while True:?

stable pecan Sep 28, 2020, 9:03 PM

#

python will execute a while True loop indefinitely, but it won't allow infinite recursion

agile sundial Sep 28, 2020, 9:03 PM

#

because it has to make a new stack frame (for each recursion)

fiery cosmos Sep 28, 2020, 9:04 PM

#

What is a stack frame?

quasi oracle Sep 28, 2020, 9:06 PM

#

Each function call has its own context: The function that called it, its arguments etc. That takes memory. So if you have infinite recursive calls, you'll run out of memory

fiery cosmos Sep 28, 2020, 9:08 PM

#

so if you did while True: print('i') it would stop at 999 because then it would take up all the memory or is this only for recursion

quasi oracle Sep 28, 2020, 9:09 PM

#

No, because a while loop is not recursion

#

It doesn't call another function

#

You stay within the same function

stable pecan Sep 28, 2020, 9:13 PM

#

consider a function that makes a local variable:

def f():
    a = 1
    f()

everytime that function is called(and it calls itself) we have to recreate the local variables inside the function, using memory

#

we don't have to do that with a while loop

fiery cosmos Sep 28, 2020, 9:13 PM

#

oh i get it now

#

thank you very much

#

but if I did py def f(): if True: f()
would the function be taking up memory?

stable pecan Sep 28, 2020, 9:18 PM

#

yes, it stores other things, not just local variables --- the other things are in the stack frame

#

the local variables are in the stack frame too

fiery cosmos Sep 28, 2020, 9:20 PM

#

sorry but what is a stack frame?

stable pecan Sep 28, 2020, 9:21 PM

#

each stack frame represents a function that is executing but hasn't returned yet

#

stack frames include arguments to the function, which function called this function, and local variables

fiery cosmos Sep 28, 2020, 9:23 PM

#

but if i were to return something the stack frame would end?

stable pecan Sep 28, 2020, 9:23 PM

#

the current frame would end, yes

fiery cosmos Sep 28, 2020, 9:24 PM

#

ok i think i understand now

#

thank you

stable pecan Sep 28, 2020, 9:24 PM

#

np

wheat laurel Sep 28, 2020, 11:19 PM

#

What can't a while loop so that recursion can

desert cedar Sep 28, 2020, 11:24 PM

#

Aything that can be done recursivly can also be done iterativly ( in a loop) @wheat laurel

loud trail Sep 28, 2020, 11:24 PM

#

it can prevent mutation

#

rather, algorithms that might require mutating or overwriting a variable with a while loop can be implemented with only immutable variables with recursion

wheat laurel Sep 28, 2020, 11:27 PM

#

Ah, ok, that's interesting

ancient galleon Sep 28, 2020, 11:29 PM

#

Is it easy to switch from Java to Python

agile sundial Sep 29, 2020, 1:12 AM

#

yeah, i did it

oblique panther Sep 29, 2020, 1:15 AM

#

@ancient galleon yes, but then you can't switch back

agile sundial Sep 29, 2020, 1:15 AM

#

wait, i did that too

oblique panther Sep 29, 2020, 1:15 AM

#

how

brave oak Sep 29, 2020, 1:16 AM

#

it's Forbidden

#

like 403

fiery cosmos Sep 29, 2020, 2:03 AM

#

Hey anyone on here want to help me with deep first search , breadth first search, A* search, etc. Im struggling hard to putting those searches into code using the class structures I am given. If you could help DM me and ill better explain.

#

Hey anyone on here want to help me with deep first search , breadth first search, A* search, etc. Im struggling hard to putting those searches into code using the class structures I am given. If you could help DM me and ill better explain.

snow swift Sep 29, 2020, 3:06 AM

#

just post your question here @fiery cosmos

frail valve Sep 29, 2020, 3:14 AM

#

if you could put a python interpreter in a microcontroller environment , how much memory would be needed

brave oak Sep 29, 2020, 3:15 AM

#

if you could put a python interpreter in a microcontroller environment , how much memory would be needed
@frail valve check MicroPython out

frail valve Sep 29, 2020, 3:16 AM

#

is 1 , 2 , 4 , 8 meg extermal dram needed

strange zealot Sep 29, 2020, 4:01 AM

#

whats a deque

#

is there something faster than stack/queue

#

which are O(1)

flat sorrel Sep 29, 2020, 4:02 AM

#

It's just a queue that can be accessed from both sides

#

the speed is basically the same

flat smelt Sep 29, 2020, 4:03 AM

#

deque is just double end queue, means you can add and reove itemms from both sides

strange zealot Sep 29, 2020, 5:05 AM

#

oh nice

nimble wasp Sep 29, 2020, 5:58 AM

#

@desert cedar can you do Tower of Hanoi using loop?

fair summit Sep 29, 2020, 7:36 AM

#

in case you are not asking about him specifically, yes, it is possible to solve tower of hanoi iteratively

#

any algorithm's solution can be converted back and forth between iterative and recursive

#

@nimble wasp

minor chasm Sep 29, 2020, 10:42 AM

#

and ~~there isnt much diff~~ in performance either

#

no diff at all

#

correct me if im wrong

fair summit Sep 29, 2020, 10:44 AM

#

complexity-wise, you're correct, but this depends on the language and its implementation

#

in python, recursion is pretty much universally slower than iteration

#

not to mention stack overflows and whatnot

minor chasm Sep 29, 2020, 10:44 AM

#

well in python ye coz GIL lul

fair summit Sep 29, 2020, 10:44 AM

#

it's not related to the GIL

minor chasm Sep 29, 2020, 10:45 AM

#

isnt it coz of no tail optimisation in python ?

#

nvm

#

i was thinking of concurrency

#

lul

#

while i said GIL ripo

fair summit Sep 29, 2020, 10:46 AM

#

there is no tail call optimization in python, which is one issue, yes
but other than that, a function call creates a stack frame (its own context), whereas a loop under the hood is simply a jump back to the first instruction in the loop

#

there are pretty detailed posts online as to why recursion, on "standard" computers are almost universally slower than iteration (when they can't be optimized into a loop, like in a tail call)

minor chasm Sep 29, 2020, 10:48 AM

#

ahh i think i read about it, just cant recall it lol

#

but thnx for clearning things up for me

fair summit Sep 29, 2020, 10:48 AM

#

TCO isn't so popular because cases where it can be applied are so trivial we might as well write a loop directly

minor chasm Sep 29, 2020, 10:49 AM

#

ahh fair enough.

#

so what about between iters and loops

#

so iter is faster that loops isnt it? aside the size overhead in iter?

#

just want to refresh bit i learned lul

#

from what i can recall iter does loop unrolling, so its much faster

#

but as size grows larger its not convients isnt it ?

fair summit Sep 29, 2020, 10:56 AM

#

if you're referring to iter in python, all it does is return an iterator given an object, if we're assuming it's a generator, it uses python frames to store the current state of the generator, you can visualize next(it) as returning the value and mutating it to be set to the new frame

minor chasm Sep 29, 2020, 10:56 AM

#

also is there cost for abstraction ?

fair summit Sep 29, 2020, 10:57 AM

#

in python, yes, pretty much nothing has zero cost

minor chasm Sep 29, 2020, 11:00 AM

#

I understand the generator bit ty. ohhh gotcha... so looping through iter doesnt make it faster i c. thnx heaps for clearing things up for me bud

flat sorrel Sep 29, 2020, 11:00 AM

#

If you are optimizing to the point where you have to worry about that, you shouldn't be using Python xD

minor chasm Sep 29, 2020, 11:01 AM

#

well im new to python somewhat

#

lol

#

just was making sure what python is capable of

#

ahaa

#

n recalling somebit i learned lol

#

it was bugging me if i got the wrong stuffs 😄

#

thnx 😄

bronze sail Sep 29, 2020, 4:28 PM

#

this is new computer science now? 😮

#

dicts in python are hashable right? fast as sets?

#

if key in some_dict

fair summit Sep 29, 2020, 4:30 PM

#

The dict itself isn't hashable, but yes, to answer your question, x in d is about as fast as sets

bronze sail Sep 29, 2020, 4:32 PM

#

ok

#

Set having dicts inside is hashable tho? 😄

fair summit Sep 29, 2020, 4:36 PM

#

No

oblique panther Sep 29, 2020, 6:01 PM

#

@bronze sail dicts are never hashable because the key-values in the dict can change at any time. Sets aren't hashable for the same reason even though all their elements are hashable

#

however there's a frozenset class that is hashable.

#

list : tuple :: set : frozenset

#

basically

wide prism Sep 29, 2020, 7:27 PM

#

user-made objects are an exception to the if-hashable-then-immutable rule, right? since they're hashed by their id instead of their "value" (by default)
why was this exception made? alternatively, why wasn't the same thing done for dicts and other mutable containers?

oblique panther Sep 29, 2020, 7:47 PM

#

@wide prism the rule is that if two objects evaluate as equal according to __eq__, then they should both hash the same way or not be hashable. Though frozenset is actually an exception because it will evaluate as equal to regular sets of the same values.

#

if there's a rule about if-hashable-then-immutable, that's probably only applicable to built-in types.

#

!e print(frozenset({1, 2, 3}) == {1, 2, 3})

halcyon plankBOT Sep 29, 2020, 7:48 PM

#

@oblique panther :white_check_mark: Your eval job has completed with return code 0.

True

oblique panther Sep 29, 2020, 7:51 PM

#

for user-defined types, I guess the expectation is that you would only define __hash__ for classes that have integral, identifying attributes, but it would be up to you to not change them after instantiation.

#

you can configure dataclasses to be frozen to emulate immutability but you can still find ways to change the attributes.

wide prism Sep 29, 2020, 8:00 PM

#

hmm, well the question was less "what are the rules here" and more about that the rules here seem strangely picked to me, in particular as opposed to making hash always not work on mutable things by default (including things of user-made types). idk if i'm missing some consideration or they are just a little inelegant

halcyon plankBOT Sep 29, 2020, 8:26 PM

#

You are not allowed to use that command here. Please use the #bot-commands channel instead.

strange merlin Sep 29, 2020, 8:26 PM

#

@fiery cosmos pls dont try to break the bot

oblique panther Sep 29, 2020, 8:55 PM

#

!e

class A: pass

a = A()
print(hash(a), id(a))

halcyon plankBOT Sep 29, 2020, 8:55 PM

#

@oblique panther :white_check_mark: Your eval job has completed with return code 0.

8791455726321 140663291621136

oblique panther Sep 29, 2020, 9:00 PM

#

@wide prism it might make more sense if you think of it from the angle that mutability is the default in Python.

cobalt sedge Sep 30, 2020, 8:41 AM

#

Given a positive integer k and an array A[1..n] that contains the final exam scores of n students in class in ascending order, design a divide and conquer algorithm to efficiently count the number of students that have final exam scores in (100(i − 1)/k, 100i/k] for integers 1 ≤ i ≤ k. Let group i be the set of students with final exam scores in (100(i − 1)/k, 100i/k] for integers 1 ≤ i ≤ k. The counting result should be stored in G[1..k], i.e. G[i] stores the number of students in group i. The elements in G is initialized to 0. For security reason, you have the following constraints:

(i) You can not directly accessA[j]for1≤j≤n and G[i]for1≤i≤k.

(ii) A function Compare(s,t) is given for returning a boolean value in O(1) time. It returns true if A[s] and A[t] are in the same group, it returns false otherwise. Each index can only be used in Compare(s, t) for at most once, e.g. if Compare(1, 4) is called, then Compare(1, 3), Compare(3, 1), Compare(3, 4) and Compare(4, 3) cannot be called.

(iii) A procedure Increase(j, val) is given for updating an element of G in O(1) time. It computes the group that the student with score A[j] belongs to, and it increases the corresponding element of G by val. E.g. if A[j] in (100(i − 1)/k, 100i/k], then G[i] is increased by val. Similar to (ii), each index j can only be used in Increase(j, val) for at most once. Note that Increase(j, val) has no return value.

Violating any one of the above constraints will cause the algorithm fail. Your algorithm should run in O(k log n) time. You can assume the maxi- mum score is 100 and no student get zero mark.

#

I have considered this problem for a very long time but I still cannot come up with a possible algorithm, even cant solve it brutally 😦

oblique panther Sep 30, 2020, 1:16 PM

#

@cobalt sedge the "divide and conquer" part is a hint to me that they want you to solve it with recursion

#

Also the fact that it's sorted means that you can determine if it contains a given value in logarithmic time using binary search

#

Not sure if that will be useful

cobalt sedge Sep 30, 2020, 2:17 PM

#

thx for ur help, but i still dont have any idea

cinder wigeon Sep 30, 2020, 5:17 PM

#

for student in range(1, n + 1):
  Increase(student, 1)

#

GWchinaSakuraThinking

#

Definitely not O(k log n), but hope I at least understood the question

#

For security reason, you have the following constraints:
this teacher tried really hard to make his problem seem "realistic"

#

🤣

oblique panther Sep 30, 2020, 5:56 PM

#

@cobalt sedge can you explain what this range is supposed to mean (100(i − 1)/k, 100i/k]?

fair summit Sep 30, 2020, 5:58 PM

#

looks like an interval

oblique panther Sep 30, 2020, 5:58 PM

#

right but it seems arbitrary

#

or maybe it is

#

I'm trying to conceptualize what this range represents in terms of something you'd intuitively want to know about grade distribution

#

...final exam scores in (100(i − 1)/k, 100i/k] for integers 1 ≤ i ≤ k. Let group i be the set of students with final exam scores in (100(i − 1)/k, 100i/k] for integers 1 ≤ i ≤ k. The counting result should be stored in G[1..k], i.e. G[i] stores the number of students in group i.```

#

this is a terrible definition of i. Is it an integer or a set?

fiery cosmos Sep 30, 2020, 6:56 PM

#

Hello everyone I am very new to programming in Python and have just started learning.

#

I was wondering if I could get some guidance regarding DS Algo

cinder wigeon Sep 30, 2020, 6:57 PM

#

@oblique panther
It's supposed to be, that the students need to be split into k bins. For example, for k=10, the first bin would have 10% worst students, second one, 10% to 20% and so on

fiery cosmos Sep 30, 2020, 6:58 PM

#

What I

I was wondering if I could get some guidance regarding DS Algo
@fiery cosmos What I wanted to know was what are the pre requisites to data structures and algorithms, I already am well versed in calculus and a little bit of probability but what else is required?

cinder wigeon Sep 30, 2020, 6:59 PM

#

Why do you ask?

oblique panther Sep 30, 2020, 7:00 PM

#

@fiery cosmos if you're in a computer science program, you'd want to check the bulletin for your program to see what classes are required to take it. However discrete math and basic algebra is probably the most useful.

fiery cosmos Sep 30, 2020, 7:00 PM

#

Oh thanks for the info.

oblique panther Sep 30, 2020, 7:01 PM

#

in my school, you have to take two semesters of calculus to graduate, but only one CS class indirectly depends on having taken both.

fiery cosmos Sep 30, 2020, 7:01 PM

#

My college begins in November and since I was bored I thought of just beginning with this stuff.

obtuse jungle Sep 30, 2020, 7:02 PM

#

i think my uni doesn't actually have any (real) math requirements for any of the cs classes

fiery cosmos Sep 30, 2020, 7:02 PM

#

Well do I also need to learn Multi Variable calculus?

obtuse jungle Sep 30, 2020, 7:02 PM

#

no

#

unless ur uni says so

#

though there are a few cs classes that might be considered math classes in thin disguises

fiery cosmos Sep 30, 2020, 7:03 PM

#

Oh ok. I have opted for CS with specialization in Electronics and ML but I will also take math since I am interested.

obtuse jungle Sep 30, 2020, 7:04 PM

#

unless you want to eventually do things like numerical methods, which would generally require some healthy math background

#

but those classes are normally not major-required

#

well, MVC is helpful for ML

#

it gives a heavy step forward in intuiting a lot of fundamental ML algorithms, manifold stuff, blah blah

fiery cosmos Sep 30, 2020, 7:05 PM

#

Also when is it advisable to take up competitive programming?

obtuse jungle Sep 30, 2020, 7:05 PM

#

if you want to do compettiive programming, now, i guess?

#

you can go on... one of those websites that have vaguely perpetually on-going competitions

#

and then start doing ""real"" ones whenever

fiery cosmos Sep 30, 2020, 7:06 PM

#

if you want to do compettiive programming, now, i guess?
@obtuse jungle Actually I am just a neewbie. I have not much idea about programming in general.

obtuse jungle Sep 30, 2020, 7:06 PM

#

oh uhh

fiery cosmos Sep 30, 2020, 7:07 PM

#

This is why I ask.

obtuse jungle Sep 30, 2020, 7:07 PM

#

well you could certainly try them after your freshman year

#

or like, after first semester if your first CS class is fairly intensive

#

you probably won't be winning anything but you can familiarize yourself with the structure of the problems

#

but uhh, probably after your first algorithms class is when you would have a better school-taught foundation for them

fiery cosmos Sep 30, 2020, 7:08 PM

#

OK thanks.

cobalt sedge Sep 30, 2020, 7:34 PM

#

@oblique panther thanks for your help again, i think the trickiest point is that u cannot compare more than once for each score

#

And the range I think is the one VimVim mentioned

hexed raptor Sep 30, 2020, 8:07 PM

#

how to make a guessing game

#

:#

#

:3

cinder wigeon Sep 30, 2020, 8:18 PM

#


from __future__ import annotations
from collections.abc import Collection, Sequence
import math
import random


def bin_sort(items: Sequence, bins: Sequence):
    k = len(bins)
    time = 0
    update_access = set()
    compare_access = set()

    def get_bin(item):
        for i in range(1, k + 1):
            if 100 * ((i - 1) / k) < item <= 100 * (i / k):
                return i - 1

    def update_bin(item_index, value):
        nonlocal update_access, time
        time += 1
        if item_index in update_access:
            raise Exception("SECURITY BREACH")
        update_access.add(item_index)

        bins[get_bin(items[item_index])] += value

    def same(index_x, index_y):
        nonlocal compare_access, time
        time += 1
        if index_x in compare_access or index_y in compare_access:
            raise Exception("SECURITY BREACH")
        compare_access |= {index_x, index_y}
        return get_bin(items[index_x]) == get_bin(items[index_y])

    def main(start, end):
        gap = end - start
        if gap < 3:
            for offset in range(gap + 1):
                update_bin(start + offset, 1)
            return
        half_gap = math.floor(gap * 0.5)
        center = start + half_gap
        if same(start, center):
            update_bin(start, half_gap + 1)
        else:
            update_bin(start, 1)
            update_bin(center, 1)
            main(start + 1, center - 1)
        main(center + 1, end)

    main(0, len(items) - 1)
    return time

#

if __name__ == '__main__':
    bins = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    # items = [15, 15, 15, 40, 40, 60, 69, 70, 71, 72, 73, 74, 75, 89, 95]
    items = [int(random.randrange(1, 99)) for _ in range(100000)]
    items.sort()
    speed = bin_sort(items, bins)
    res = dict(zip(["0-10", "10-20", "20-30", "30-40","40-50", "50-60", "60-70", "70-80", "80-90", "90-100"], bins))
    print(res)
    print(speed)

#

@cobalt sedge

#

I think that should work