Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Thu Oct 31, 2019 8:26 pm

Your wish is my command.

Finding points on a grid it is.

Starting small scale so only stars our galaxy and only those from a certain star catalog.
Memory in C++ is a leaky abstraction .

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: Liberation through Computer Literacy

Thu Oct 31, 2019 9:44 pm

The original challenge was to find a few objects in a simple grid. If this challenge is beyond that and the next star wars, I'm out.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Thu Oct 31, 2019 10:38 pm

Yes, the original challenge was to find a few near neighbors to some selected point among a lot of other random points.

I think the data set has to be big enough to make the search computationally intensive, within reason, otherwise it's a trivial challenge. On the other hand it has to be small enough to fit into the typical Pi's RAM space. Say 1GB. I don't want to have to be messing with files on disk to get the job done.

If I remember correctly my original challenge was phrased in terms of a 2048 by 2048 grid of points. I was kind of thinking of an occupancy of 10% or so. So 400,000 points to search.

But of course we don't actually need to maintain a two dimensional array of 4 million elements. Most of which would be empty. We only need to store those random points that are occupied in such a way that they can be searched. We can hold 10 or more million points in RAM I suspect. Not the full 113, 000, 000 points in the chosen star catalog but enough.

I did mention selecting a subset of stars, in some busy part of the sky.
Memory in C++ is a leaky abstraction .

jcyr
Posts: 504
Joined: Sun Apr 23, 2017 1:31 pm
Location: Atlanta

Re: Liberation through Computer Literacy

Thu Oct 31, 2019 10:51 pm

Heater wrote:
Thu Oct 31, 2019 10:38 pm
Yes, the original challenge was to find a few near neighbors to some selected point among a lot of other random points.

I think the data set has to be big enough to make the search computationally intensive, within reason, otherwise it's a trivial challenge. On the other hand it has to be small enough to fit into the typical Pi's RAM space. Say 1GB. I don't want to have to be messing with files on disk to get the job done.
Assuming however many data points exist in some kind of file, there is no need to store any of them other than the N closest.

Checkout https://projecteuler.net/ for a large collection of literacy inducing problems.
Last edited by jcyr on Thu Oct 31, 2019 11:08 pm, edited 1 time in total.
It's um...uh...well it's kinda like...and it's got a bit of...

User avatar
Paeryn
Posts: 2752
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: Liberation through Computer Literacy

Thu Oct 31, 2019 11:06 pm

I might not be attempting this one Haskell, not after fighting the memory issues last time, though that was more down to the amount of temporary Strings my method created which are far from memory efficient. Strings are stored as linked lists of utf-16 chars, the overheads in 32-bit are huge but in 64-bit are insane!

I'll team up with Kira and do it in C/C++, he may be a good programmer but he's a lousy typist (not to mention how many mice he gets through). I might even try my hand at Rust.
She who travels light — forgot something.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Thu Oct 31, 2019 11:09 pm

Yeah. As a practical matter it's a pain to have to download and store huge files of test data.

Perhaps it's better for the purposes of the challenge to generate the random "star field" from a know pseudo random number generator algorithm and seed. Small and quick.
Memory in C++ is a leaky abstraction .

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Thu Oct 31, 2019 11:14 pm

It's up to you of course but it would be nice to see a variety of languages in the solutions. You are the Haskell guy.

I already started on a Rust solution.
Memory in C++ is a leaky abstraction .

jcyr
Posts: 504
Joined: Sun Apr 23, 2017 1:31 pm
Location: Atlanta

Re: Liberation through Computer Literacy

Thu Oct 31, 2019 11:36 pm

How about a less trivial challenge?

Tatami are rectangular mats, used to completely cover the floor of a room, without overlap.

Assuming that the only type of available tatami has dimensions 1×2, there are obviously some limitations for the shape and size of the rooms that can be covered.

For this problem, we consider only rectangular rooms with integer dimensions a, b and even size s = a×b.
We use the term 'size' to denote the floor surface area of the room, and, without loss of generality, we add the condition a ≤ b.

There is one rule to follow when laying out tatami: there must be no points where corners of four different mats meet.

Because of this rule, certain even-sized rooms cannot be covered with tatami: we call them tatami-free rooms.
Further, we define T(s) as the number of tatami-free rooms of size s.

The smallest tatami-free room has size s = 70 and dimensions 7×10.
All the other rooms of size s = 70 can be covered with tatami; they are: 1×70, 2×35 and 5×14.
Hence, T(70) = 1.

Similarly, we can verify that T(1320) = 5 because there are exactly 5 tatami-free rooms of size s = 1320:
20×66, 22×60, 24×55, 30×44 and 33×40.
In fact, s = 1320 is the smallest room-size s for which T(s) = 5.

Find the smallest room-size s for which T(s) = 200.

Solved in C++ (50 lines of code) on PI4 in 10.2 seconds, on Jetson Nano in 6 seconds.
Last edited by jcyr on Fri Nov 01, 2019 12:49 am, edited 2 times in total.
It's um...uh...well it's kinda like...and it's got a bit of...

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Thu Oct 31, 2019 11:52 pm

You have not convinced me that getting a fast solution to searching a large number of points is trivial.
Memory in C++ is a leaky abstraction .

User avatar
Paeryn
Posts: 2752
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 12:26 am

Go on then, I'll do a Haskell version when I have time. Kira says he prefers to do the C version on his own anyway as apparently I disrupt his delicate deep contemplation time (though to me it looks like he's just sleeping on the keyboard).
She who travels light — forgot something.

jcyr
Posts: 504
Joined: Sun Apr 23, 2017 1:31 pm
Location: Atlanta

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 12:47 am

Heater wrote:
Thu Oct 31, 2019 11:52 pm
You have not convinced me that getting a fast solution to searching a large number of points is trivial.
For me to do that, you'd have to propose and specify an actual problem.
It's um...uh...well it's kinda like...and it's got a bit of...

ejolson
Posts: 3838
Joined: Tue Mar 18, 2014 11:47 am

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 3:34 am

jcyr wrote:
Thu Oct 31, 2019 11:36 pm
Tatami are rectangular mats, used to completely cover the floor of a room, without overlap.
For reference, this is problem 256 on Project Euler.

https://projecteuler.net/problem=256

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 5:09 am

ejolson wrote:
Fri Nov 01, 2019 3:34 am
jcyr wrote:
Thu Oct 31, 2019 11:36 pm
Tatami are rectangular mats, used to completely cover the floor of a room, without overlap.
For reference, this is problem 256 on Project Euler.

https://projecteuler.net/problem=256
That seems more reasonable and has a practical use.

ejolson
Posts: 3838
Joined: Tue Mar 18, 2014 11:47 am

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 4:39 pm

John_Spikowski wrote:
Fri Nov 01, 2019 5:09 am
ejolson wrote:
Fri Nov 01, 2019 3:34 am
jcyr wrote:
Thu Oct 31, 2019 11:36 pm
Tatami are rectangular mats, used to completely cover the floor of a room, without overlap.
For reference, this is problem 256 on Project Euler.

https://projecteuler.net/problem=256
That seems more reasonable and has a practical use.
In an attempt to cheer up the lead developer of FidoBasic, I mentioned the Tatami question. Unfortunately, Fido became barking mad and growled, why should I do your homework problems in graph theory?

I tried to explain, it's not about graph theory but carpets. With that the dog developer started whining, carpets bring back bad memories from puppyhood, when I got scolded for digging a hole in one and making another wet.

I could not help remarking how such a scolding was deserved and then went on, Tatami are rectangular mats that--as if by magic--can travel in time. At the mention of time, Fido's ears perked up. What are the technical specifications? My friend K9 is borrowing the Tardis while Dr Who is at the dentist. For me to show up with a substandard tapestry covered with cat hair would be embarrassing. How does a time machine compare with a Tatami?

I assured Fido that Tatami were not covered with cat hair (are they?) and then went on to explain how those rectangular mats are capable of traveling forward in time at the exact rate of one second per second. This seemed to calm the dog developer, who began pawing at the keyboard. For the sake of computer literacy, I hope Fido is not still working on a sluggish bootloader.
Last edited by ejolson on Fri Nov 01, 2019 5:21 pm, edited 5 times in total.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 4:54 pm

John_Spikowski,
That seems more reasonable and has a practical use
Hmm... The likes of Google might disagree. For them the problem of finding a few points from among millions is something they have to do many times every second of every day to earn their daily bread.

On the other hand, I have never seen anyone tiling anything with Tatami.

If I was going to go with non-square tiles in my bathroom they would be Penrose Tiles.
Memory in C++ is a leaky abstraction .

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 5:16 pm

I was thinking yoga mats might be an application.

My kitty (Savu - Finnish for smoke) thinks it's a good project she can get her claws into.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 5:56 pm

Onko sinulla suomalaista kissaa?
Memory in C++ is a leaky abstraction .

ejolson
Posts: 3838
Joined: Tue Mar 18, 2014 11:47 am

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 6:25 pm

Heater wrote:
Fri Nov 01, 2019 5:56 pm
Onko sinulla suomalaista kissaa?
In order to be fully liberating, computer literacy must be accessible to plants and animals of all species, phylum, race, gender and nationality among other things. If any content cannot be made compliant with the ADA Americans with Disabilities Act

https://www.ada.gov/pcatoolkit/toolkitmain.htm

that content must be deleted, see in particular Chapter 5 on website design. Printed books are currently excepted due to environmental concerns related to burning all of them.

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 6:37 pm

Heater wrote:
Fri Nov 01, 2019 5:56 pm
Onko sinulla suomalaista kissaa?
Sorry I'm Polish decent. I inherited Savu.

User avatar
Burngate
Posts: 6100
Joined: Thu Sep 29, 2011 4:34 pm
Location: Berkshire UK Tralfamadore
Contact: Website

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 7:06 pm

ejolson wrote:
Fri Nov 01, 2019 6:25 pm
... computer literacy must be accessible to plants and animals of all species, phylum, ...
What have you got against fungi and their relatives? It's not as if they didn't give us penicillin and the like. And where would we be without yeast?

I can understand missing out viruses and phages, and even bacteria, archaia, etc. even though soil and our guts rely on them to work, but really ...

User avatar
davidcoton
Posts: 4263
Joined: Mon Sep 01, 2014 2:37 pm
Location: Cambridge, UK

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 8:49 pm

John_Spikowski wrote:
Fri Nov 01, 2019 6:37 pm
Heater wrote:
Fri Nov 01, 2019 5:56 pm
Onko sinulla suomalaista kissaa?
Sorry I'm Polish decent. I inherited Savu.
Czy masz fińskiego kota?
Signature retired

User avatar
John_Spikowski
Posts: 1614
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: Liberation through Computer Literacy

Fri Nov 01, 2019 9:33 pm

You can find a job with the Finnish language.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Sat Nov 02, 2019 8:35 am

Oddly enough every place I worked in Finland required one to work in English. Being international companies like Nokia.

Except one smaller branch of a smaller corporation that used Swedish in all it's code comments and documentation. Luckily they only had a about three lines of comments in their code base so it did not cause to much confusion for me.

I did once find comments in Finnish in piles of assembler. But that was in England! In the BIOS of the PC's Nokia was exporting in the 1980's. Again luckily confusion was avoided by their sparsity.

(If anyone ever tells you to comment your code well, just say "no" and point them to this post for the reason why.)
Memory in C++ is a leaky abstraction .

ejolson
Posts: 3838
Joined: Tue Mar 18, 2014 11:47 am

Re: Liberation through Computer Literacy

Sat Nov 02, 2019 4:13 pm

Burngate wrote:
Fri Nov 01, 2019 7:06 pm
ejolson wrote:
Fri Nov 01, 2019 6:25 pm
... computer literacy must be accessible to plants and animals of all species, phylum, ...
What have you got against fungi and their relatives? It's not as if they didn't give us penicillin and the like. And where would we be without yeast?
With a sound not unlike when the dog developer rolled down the stairs as a puppy, Fido burst through the door yelping. What wrong? I asked. The lead developer of FidoBasic howled, I've just returned from touring five of the ten events nearest to the second age of personal computing in four dimensional space time. Oh that, I replied. How are Dr Who's teeth?

Tail wagging the lead developer of FidoBasic went on, it turns out that the animated orange cat is not fully ADA compliant since Scratch can't be used with screen readers for the blind. Further, there was an antidiscrimination lawsuit in which some fungi acting on behalf of the toxoplasma gondii claimed the latter had been denied liberation through computer literacy as part of an intentional act favouring the mouse. As a result Scratch will soon be deleted from the curriculum reform and replaced by FidoBasic.

How can that be, I questioned. FidoBasic hasn't even entered beta-testing yet. The canine coder growled, ADA support is so important that testing is not needed--just the paperwork to show compliance. K9 helped me. To convince the lawyers, the key was demonstrating the use of line numbers in FidoBasic source code.
Last edited by ejolson on Sat Nov 02, 2019 5:05 pm, edited 2 times in total.

Heater
Posts: 13930
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Sat Nov 02, 2019 5:02 pm

Oh boy, that means node-red is taboo as well.

Pretty much half the educational material put out by the Pi Foundation is likely cause for a law suite.
Memory in C++ is a leaky abstraction .

Return to “General programming discussion”