### Author Topic: A collection of programming problems  (Read 1770 times)

#### daydreamer

• Member
• Posts: 2393
• my kind of REAL10 Blonde
##### Re: A collection of programming problems
« Reply #15 on: December 23, 2022, 05:59:03 AM »
Use it in American movie universe : every phone number starts with 555-four digit number?
Linear ? Does he mean limited to scalar single thread code, prohibit simd and simt solutions ?
Isnt restricting to same fixed random seed, on purpose to be able to compare speed, with different solutions from different coders?

my none asm creations
http://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

#### Siekmanski

• Member
• Posts: 2717
##### Re: A collection of programming problems
« Reply #16 on: December 23, 2022, 06:01:20 AM »
You could use the same principle as my "CalculateMedian" routine.

http://masm32.com/board/index.php?topic=8671.msg94735#msg94735

Highest phone number = 9999999 = 1250000 bytes to populate = 1.1921 MB memory usage.

Read in all phone numbers and set the corresponding bit in the memory table.
for example: 1234567
1234567 shr 3 = 154320 -> jump to byte offset 154320 in memory.
1234567 and 7 = 7    -> set bit 7

Do this for all phone numbers and set the corresponding bits.

When done start reading the first bit, if set the phone number = 0000000
Read the next bit, if set the phone number is 0000001
Read the next bit, if set the phone number is 0000002 etc. till you reach bit number 9999999.

If a bit is not set it is not a phone number.

This way you have automatically sorted the telephone numbers and you will get rid of duplicate numbers.
Very fast routine and it uses only 1.1921 MB memory
Creative coders use backward thinking techniques as a strategy.

#### daydreamer

• Member
• Posts: 2393
• my kind of REAL10 Blonde
##### Re: A collection of programming problems
« Reply #17 on: December 23, 2022, 06:05:40 AM »
The random generator is excellent. It's something else
As in Great entropy? But if you choose crappiest entropy rndgenerator might result in only 10k phone numbers ?

my none asm creations
http://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### Re: A collection of programming problems
« Reply #18 on: December 23, 2022, 06:56:39 AM »
You could use the same principle as my "CalculateMedian" routine.

http://masm32.com/board/index.php?topic=8671.msg94735#msg94735

Sorry, I can't see what the two things have in common. Can you explain?

Quote
Highest phone number = 9999999 = 1250000 bytes to populate = 1.1921 MB memory usage.

Read in all phone numbers and set the corresponding bit in the memory table.

That is exactly what my program does, see attachment in reply #7.

In the meantime, I found the little bugger - it's fixed, see attachment.

Code: [Select]
`  elements=1000000 Dim Tel(elements-1) As DWORD For_ ecx=0 To elements-1 ; one Million random numbers add Rand(900000), 100000 ; range 100,000 ... 999,999 mov Tel(ecx), eax Next...  lea edi, Tel(0)  xor ebx, ebx  .Repeat mov eax, [edi+4*ebx] ; get a number bts [esi], eax ; set a bit at this number's distance inc ebx  .Until ebx>=elements ; n input numbers`
Code: [Select]
`8426 µs for creating an array of random phone numbers1042 µs for getting the max = 9999973193 µs for setting the bits10 ms   for sorting & storing 603368 phone numbers10000010000110000210000310000510000610000710000810000910001296 ms  for nrQsortA (there are duplicates)100000100001100002100002100003100005100006100007100008100009`
As you can see, with these parameters we have about 40% duplicates. The algo is damn fast, 10x QuickSort with the chosen range, but, as mentioned before, there is no way to keep the duplicates. The interesting question is now what is the actual usage of a DWORD sorter? Should the result have duplicates or not? I guess we need both algos, depending on the actual requirements.

@Z: There is even a Sudoku example

« Last Edit: December 23, 2022, 08:22:15 AM by jj2007 »

#### zedd151

• Member
• Posts: 1942
##### Re: A collection of programming problems
« Reply #19 on: December 23, 2022, 08:48:26 AM »

I’ll look at that later…

edit... a couple minutes later. lol I though you made that puzzle. Anyway, I checked it for validity and it is valid with one solution (for the uniquiness rule). It is a rather easy puzzle though, rated at only 214 (via 'hodoku.exe') for anyone interested in such things.
Regards, zedd.

#### Siekmanski

• Member
• Posts: 2717
##### Re: A collection of programming problems
« Reply #20 on: December 23, 2022, 09:41:00 AM »
> Sorry, I can't see what the two things have in common. Can you explain?

Hi Jochen,

I remembered I used the simulair approach to count colors used in a picture and the median calculation to exclude sorting a while ago.
The number storing as a position in a table to exclude sorting would also be usefull for the phone number approuch.
Sorry, didn't know you used the same technique because I missed the source code in your second .zip

Creative coders use backward thinking techniques as a strategy.

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### Re: A collection of programming problems
« Reply #21 on: December 23, 2022, 10:09:05 AM »
The number storing as a position in a table to exclude sorting would also be usefull for the phone number approuch.
Sorry, didn't know you used the same technique because I missed the source code in your second .zip

Hi Marinus,

I didn't invent the technique - I just translated David Maynard's instructions to Assembly.

Quote
Problem: Given a list of one million random 7-digit phone numbers write a program that prints a sorted list of the phone numbers with duplicates removed, using less than 2 M Bytes of memory and that runs in linear time.

Solution:

Create a bit vector of 10 million bits (10/8 = 1.25 million bytes) and initialize all bits to 0. Now read through the list of telephone numbers and convert each telephone number into in integer, i, between 0 an 9,999,999. Now set the ith bit of the bit vector to 1. bitVector = 1;
Now iterate thought the bit vector from bitVector
• through bitVector[9,999,999] and if the bit is set format the index i, as a 7 digit telephone number, and print it.

Note: This problem was used as a Google Interview question.

#### hutch--

• Member
• Posts: 10583
• Mnemonic Driven API Grinder
##### Re: A collection of programming problems
« Reply #22 on: December 23, 2022, 12:55:52 PM »
Generate an exhaustive linear list of 7 digit numbers then shuffle them to make them random, no duplicates.
hutch at movsd dot com
http://www.masm32.com

#### zedd151

• Member
• Posts: 1942
##### Re: A collection of programming problems
« Reply #23 on: December 23, 2022, 04:09:47 PM »
Generate an exhaustive linear list of 7 digit numbers then shuffle them to make them random, no duplicates.
I see your line of thinking,  except that deviates from the given criteria:
Quote
Problem: Given a list of one million random 7-digit phone numbers write a program that prints a sorted list of the phone numbers with duplicates removed, using less than 2 M Bytes of memory and that runs in linear time.
Regards, zedd.

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### Re: A collection of programming problems
« Reply #24 on: December 23, 2022, 09:28:45 PM »
Generate an exhaustive linear list of 7 digit numbers then shuffle them to make them random, no duplicates.

Quote
Rand(1, 50, numbers() As DWORD, unique:6)            ; min, max, array, unique:n: get 6 unique elements in the range 1...49

Feasible but attention, if you set elements=1000000, unique:elements, you run into serious performance issues

#### hutch--

• Member
• Posts: 10583
• Mnemonic Driven API Grinder
##### Re: A collection of programming problems
« Reply #25 on: December 23, 2022, 10:08:25 PM »

Do it with a hash table and keep pouring them through until you have the count you want.
hutch at movsd dot com
http://www.masm32.com

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### Re: A collection of programming problems
« Reply #26 on: December 24, 2022, 06:37:25 AM »
Do it with a hash table and keep pouring them through until you have the count you want.

We are talking DWORDs here, not strings.

#### hutch--

• Member
• Posts: 10583
• Mnemonic Driven API Grinder
##### Re: A collection of programming problems
« Reply #27 on: December 24, 2022, 06:56:28 AM »
That can be done with a hash table but there is another technique, a bucket sort if you have enough memory, one pass in, one pass out. It may not fit into the memory constraint criterion but done right, its fast.
hutch at movsd dot com
http://www.masm32.com

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### Re: A collection of programming problems
« Reply #28 on: December 24, 2022, 10:10:42 PM »
I'll call it BitSort, and it will be added to the next MasmBasic version - source & exe attached. The algo is simple and 160 bytes short. Credits go to David Maynard

Code: [Select]
`invoke BitSort, pArray, elements`
BitSort returns a ptr to the array in eax (or zero if HeapAlloc fails), plus #elements in ecx

It is blazing fast for not-so-high maximum values, such as "7 digit phone numbers". For example, with 100 Mio elements and range 1,000,000 ... 9,999,999, it's a factor 16 faster than nrQsortA. And, of course - no duplicates:

Code: [Select]
`604 ms for sorting 7600084 elements with BitSort10 s for sorting 100000000 elements with nrQsortABitSort 1000000BitSort 1000001BitSort 1000004BitSort 1000005BitSort 1000006BitSort 1000007BitSort 1000008BitSort 1000010BitSort 1000011BitSort 1000012BitSort 1000013nrQsortA 1000000nrQsortA 1000000nrQsortA 1000000nrQsortA 1000000nrQsortA 1000000nrQsortA 1000000nrQsortA 1000001nrQsortA 1000001nrQsortA 1000001nrQsortA 1000001nrQsortA 1000001`
For settings with few duplicates, nrQsortA and ArraySort can be faster, though.
« Last Edit: December 24, 2022, 11:19:05 PM by jj2007 »

#### NoCforMe

• Member
• Posts: 1124
##### Re: A collection of programming problems
« Reply #29 on: December 31, 2022, 03:42:57 PM »
Just in case you have nothing better to do

Example:
Quote
Given a list of one million random 7-digit phone numbers write a program that prints a sorted list of the phone numbers with duplicates removed, using less than 2MB of memory and that runs in linear time

Interesting challenge, but can you explain what "runs in linear time" means? That's a term I'm not familiar with.