Wikipedia:Reference desk/Archives/Computing/2023 July 16

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 16

Horrid Google Books Captcha

I have to use Google Books a lot for study purposes (it's not something I do as a hobby). I have one HUGE problem. At some point it starts to ask me to complete a few Captcha. It usually start with a reasonable amount of them, but it turns fast into a torture of DOZENS of slow-loading images every few minutes until I'm spending more time doing them than researching. It is actually an enormous loss of time. Probably from its point of view it looks like a lot of "suspicious" traffic but I simply cannot make a pause every three minutes. This situation really needs to stop. Is there ANY way to avoid this horrid tragedy? Please help me. Thank you. 95.236.12.144 (talk) 14:11, 16 July 2023 (UTC)

From my experience Google generally is less aggressive with CAPTCHAs (less likely to serve them and when they do they tend to be easier) if you are logged in to a Google account on that browser session, so if you have a Google account, make sure you are signed in. (When you visit books.google.it or whatever, there should be a icon for your account at the top right rather than a sign in option.) If you don't have an account, you could try creating one although I'm not sure how much having a Google account helps if you don't use it enough that Google feels it belongs to a real person. Also make sure you turn off any proxies or VPNs and don't use things like Tor. Nil Einne (talk) 17:48, 16 July 2023 (UT

Combining multiple lists into one

I have multiple lists having data in form 12AB1234. I want to combine them into one while preserving their order. For eg: L1: 1,2,4 ; L2: 2,3,4 so combined should be 1,2,3,4. Also if say L2 is 1,3,4 then order of 2 and 3 cant be determined, so 1,2,3,4 or 1,3,2,4 both are fine. How to do this using python (or if possible, using excel). -- 2409:408D:41C:3A9:A1F8:2F53:D5FF:F036 (talk) 17:59, 16 July 2023 (UTC)

Copy each list onto the end of the one before, ignoring duplicates. This assumes the following points:

• Items have no inherent order: their order is defined by the way they appear in the lists.
• Any two items present in more than one list will always be in the same order. (A necessary consequence of the above.)

In python you can use the keyword in and say if item in list: to test each item as you add it. You could write this concisely using a list comprehension.

Oh, I begin to see the problem - in your first L2 example, 3 comes between 2 and 4, therefore it should be added to the output list between 2 and 4. This means you need to maintain a position in the output list, based on which of its items you have thus far encountered in the current input list. New items go there - to start with, they go at the beginning of the current output list.

But we may discover from a later list that they are in the wrong place! For instance: starting with the list 1, 2, 3, we add the list Q, producing Q, 1, 2, 3, but now we have a third list 2, Q which gives us no new items but tells us Q was in the wrong place. This is a nice problem. It has a computer science textbook feel about it.

We have an article about Merge algorithms. Or is Merge (version control) more relevant? Or indeed Longest common subsequence.

I am clearly floundering! I may come back to this later, perhaps somebody else will have fun with it in the meantime.

 Card Zero  (talk) 19:15, 16 July 2023 (UTC)

[OP here] Thanks for confirming that this is an actually hard problem. Now that LCS link you gave gets way too technical for me. But I think it has certain similarity to my problem. I think you understood the problem, especially with your Q example it gets more clearer to me. Its not from a textbook , its something i actually want to solve (Not for assignment or work, just out of interest). Also to give more details (which might be irrelevant, and also are not exactly true). The final list is based on scores of student in particular exam. The sublists are shortlists given by certain institutes based on that score. Not all students apply in all institutes. and none of shortlists mention scores, just the roll no. I have shortlists, I want full list. -- 2409:408D:41C:3A9:D8EA:B37F:A718:E982 (talk) 05:35, 17 July 2023 (UTC)

One model for this is: imagine we forgot the order of the letters of the alphabet. We have several fragments of the alphabet, each with a small number of letters, all in order, but with no clue about where letters are missing. I'm considering a solution where each letter maintains a list, "smaller items", of letters discovered to be earlier in the alphabet. When all processing of inputs is done, we sort the letters by the length of their "smaller items" lists, and the output consists of equally-ranked groups, which would equate to groups of letters whose order is uncertain, or students who might have the same score. So for instance the letters with zero-length "smaller items" lists are candidates for the start of the alphabet. (This solution won't look very good in Big O notation, because each new less-than or greater-than relationship we discover entails processing the whole chain of them, and the chains increase in length as we go on.)

# each letter has a set of all lesser letters.
letters = {}

def input(s):
	for index, c in enumerate(s):
		if(c not in letters):
			letters[c] = set()
		if(index > 0):
			earlier_letters = recursive_set(s[index-1])
			letters[c] = letters[c].union(earlier_letters)
			for k in letters:
				if(c in letters[k]):
					letters[k] = letters[k].union(earlier_letters)
				
def recursive_set(letter):
	result = {letter}
	for c in letters[letter]:
		result = result.union(recursive_set(c))
	return result

def number_earlier(item):
	return len(item[1])
	
def output():
	letter_list = list(letters.items())
	letter_list.sort(key=number_earlier)
	print(letter_list)
	print([x[0] for x in letter_list])
			
input("bfjk")
input("knpq")
input("hjnru")
input("acz")

output()

 Card Zero  (talk) 10:40, 17 July 2023 (UTC)

Is it possible for one list to have ...,p,...,q,... while another has ...,q,...,p,...? Or for one to have ...,p,...,q,..., another ...,q,...,r,..., and a third ...,r,...,p,..., forming a cycle p < q < r < p ?  If not, the "comes before" relation induces a partial order, which can be extended to a total order by topological sorting.  --Lambiam 12:54, 19 July 2023 (UTC)

Thank you Card zero for this solution. I think approach would work (I haven't tried, as i need to change it to work for strings instead of characters). Also, Lambiam, no such circular things are not possible(hopefully). Even if it happen then, as you see my previous comment, it would mean they have equal scores so order won't matter for them. Also I think my situation is total order, but i don't understand that topological sort. or maybe it is same as solution given above -- 2409:408D:315:F632:AC75:EC4B:CACA:BD70 (talk) 21:36, 21 July 2023 (UTC)