Anonymous user
Talk:Zig-zag matrix: Difference between revisions
→Pattern of memory addresses: Previous pattern searches.
No edit summary |
(→Pattern of memory addresses: Previous pattern searches.) |
||
| (26 intermediate revisions by 12 users not shown) | |||
Line 158:
Many languages have built-in sort functions, and J is no different in that regard. It is, however, different in how far it generalizes the concept. In J, more than just sorting an array, you can (must) ''grade'' it. That is, "this comes first, this comes second, this comes third". That is the function of the primitive <tt>/:</tt> (read "grade down", and its counterpart, <tt>\:</tt> "grade up").
For example, if we grade a list, it is like grading a school class; it tells us who's first, who's second, etc:
/: '
4 5
Then, if we use those numbers to index into the list:
4 5
ABCDEF
Voila, the list is sorted (we could've done this in one step, with <tt>/:~'
AD =: (] antid integers) 3 3
Line 188:
3 7 8
Which is exactly what we wanted.
=== reshaping ===
Line 252:
And that's why I like J.
== further J exposition ==
One thing that may not be clear about the J code, and therefore might render it confusing, is that is has no variables. It is completely functional, and the arguments are implicit (the arragement of the expression determines how and where inputs and results are passed).
A verbose version of this functional expression might be written:
<pre>
zigZag =: rearrange (antidiagonals integerList)
rearrange =: reshape reorder
reshape =: $
reorder =: grade@flatten
grade =: /:
flatten =: ;
antidiagonals =: sumOfCoords rClass identity
sumOfCoords =: sum@antibase
sum =: +/
antibase =: #:
rClass =: <@maybeRevers classify
maybeRevers =: permute~ evenOrOdd
permute =: A.
evenOrOdd =: _2 mod len
mod =: |
len =: #
classify =: /.
identity =: ] NB. Copy of argument
integerList =: zeroToN_1@product
zeroToN_1 =: i.
product =: */ NB. Note resemblance to sum ('/' is zipWith)
</pre>
To explicitly recreate the function calls that occur when the function is invoked (with assignments being what the interpreter actually does, and everything else just to show you what's going on):
<pre>
INPUT =: 3 3
PRODUCT =: product INPUT
PRODUCT
9
INTEGERLIST =: zeroToN_1 PRODUCT
INTEGERLIST
0 1 2 3 4 5 6 7 8
INPUT <@antibase INTEGERLIST
+---+---+---+---+---+---+---+---+---+
|0 0|0 1|0 2|1 0|1 1|1 2|2 0|2 1|2 2|
+---+---+---+---+---+---+---+---+---+
INPUT sum@antibase INTEGERLIST
0 1 2 1 2 3 2 3 4
SUMOFCOORDS=:INPUT sumOfCoords INTEGERLIST
SUMOFCOORDS
0 1 2 1 2 3 2 3 4
SUMOFCOORDS <classify INTEGERLIST NB. Anti-diagonals
+-+---+-----+---+-+
|0|1 3|2 4 6|5 7|8|
+-+---+-----+---+-+
SUMOFCOORDS evenOrOdd classify INTEGERLIST NB. Anti-diagonal lengths alternate, even and odd
_1 0 _1 0 _1
0 permute 1 2 3 NB. 0 permute X is just X
1 2 3
_1 permute 1 2 3 NB. _1 permute X is X reversed
3 2 1
maybeRevers 1 2 3 NB. Odd lengths reversed
3 2 1
maybeRevers 1 2 3 4 NB. Even lengths left alone
1 2 3 4
ANTID =: SUMOFCOORDS rClass INTEGERLIST
ANTID NB. Anti-diagonals, appropriately reversed
+-+---+-----+---+-+
|0|1 3|6 4 2|5 7|8|
+-+---+-----+---+-+
flatten ANTID NB. Not exciting
0 1 3 6 4 2 5 7 8
grade FLAT_ANTID NB. How to permute, in order to sort
0 1 5 2 4 6 3 7 8
REORDERED=:reorder ANTID
REORDERED
0 1 5 2 4 6 3 7 8
INPUT reshape REORDERED NB. Make it a matrix
0 1 5
2 4 6
3 7 8
ZIGZAG=:INPUT reshape REORDERED NB. Done
ZIGZAG
0 1 5
2 4 6
3 7 8
</pre>
So, to transliterate this to another (inconsistent) pseudo-language:
<pre>
function zigZag(int-list INPUT) as matrix
{
return rearrange(INPUT, antidiagonals(INPUT,integerList(INPUT))
}
function rearrange(int-list SHAPE, int-list-list ANTIDIAGONALS) as matrix
{
return reshape(SHAPE,reorder(ANTIDIAGONALS))
}
function reorder(int-list-list ANTIDIAGONALS) as int-list
{
RESULTS = []
for each ANTIDIAGONAL in ANTIDIAGONALS
{
RESULTS.append(ANTIDIAGONAL) // Flatten the list-list to a list
}
return grade(RESULTS)
}
function antidiagonals(int-list INPUT, int-list INTEGERS) as int-list-list
{
// Note classify has a function-argument
CLASSES = classify(sumOfCoords(INPUT, INTEGERS), INTEGERS)
RESULTS = []
for each CLASS in CLASSES
{
RESULTS.append(maybeReverse(CLASS))
}
return RESULTS
}
function sumOfCoords(int-list INPUT, int-list INTEGERS) as int-list
{
COORDINATES = antibase(INPUT, INTEGERS)
RESULTS = []
for each COORDINATE in COORDINATES
{
RESULTS.append(sum(COORDINATE))
}
return RESULTS
}
function maybeReverse(int-list LIST) as int-list
{
if ( len(LIST) mod 2 )
{
return reverse(LIST) // FIXME: Fully implement A. (permutation table)
}
else
{
return LIST
}
}
function integerList(int-list INPUT) as int-list
{
PROD = product(INPUT)
return [0 .. (PROD-1)]
}
</pre>
The uninmplemented functions (e.g. <tt>antibase</tt>) are primitives, or simple combinations of primitives, in J. You can get the formal specifications at [http://www.jsoftware.com/help/dictionary/vocabul.htm The J Vocabulary]. For example, see the [http://www.jsoftware.com/help/dictionary/d402.htm definition of antibase].
==Reply ==
Thanks for the info! I've updated the Haskell example with a better algorithm based on your techniques. (By the way, I think this explanation is worth keeping around; perhaps it should be moved to something like [[Zig Zag/J explanation]] and linked from the example?) --[[User:Kevin Reid|Kevin Reid]] 17:49, 4 August 2008 (UTC)
:I took the fact that you sorted in the Haskell example and worked it out for myself for the Python example, before thinking of reading this talk page. So I have my own [http://paddy3118.blogspot.com/2008/08/zig-zag.html explanation]. --[[User:Paddy3118|Paddy3118]] 04:12, 5 August 2008 (UTC)
Even though J looks so strange and hard to me, this algo so explained and encoded gave me the idea that J deserves a look and more:) --[[User:ShinTakezou|ShinTakezou]] 01:00, 16 December 2008 (UTC)
== Error in Pascal example ==
Pascal example works only for odd matrix dimensions.
--[[User:Blentabler|Blentabler]]
Now fixed --[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk:Tigerofdarkness|talk]]) 10:11, 2 September 2016 (UTC)
== The first N squared integers ==
Integers start at minus a very big number. So this is not what the task description means. Positive integers start at 1, this would be my preferred requirement, but many already start at zero which is neither positive nor negative. The task description needs correction.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:55, 24 January 2020 (UTC)
: I agree wholeheartedly. Or, as one often votes on Rosetta Code, '''+1'''. I also have brought up more than a few similar arguments before, as in ''' ''a positive integer > 0'',''' or ''' ''a positive integer'',''' and then use a '''0''' (zero) in the example input for the task. It's an uphill battle, not the least of which is when a '''number''' is used when an '''integer''' is meant. I have since stopped pointing out the obvious, ya can't win when ya argue with people who buy ink by the barrel. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 20:46, 24 January 2020 (UTC)
:It is an old task with many solutions; maybe rewording to include a start of zero ''or'' one would be better as the main idea of the task is the zig-zaggedness and starting from one or zero would still allow implementations to be compared? --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 21:21, 24 January 2020 (UTC)
::Hmm, just saw that the example counts from zero. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 21:26, 24 January 2020 (UTC)
:: I addressed this problem when I entered the '''REXX''' language solution, the computer program allowed the invoker to specify a starting ''number'', but any integer could be used. It doesn't fix the problem with the task's requirements, but it allows the user to choose which integer to start the zig-zag matrix with. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 21:39, 24 January 2020 (UTC)
: The problem with using phrases like ''natural numbers'' and/or ''counting numbers'' is that there isn't a clear and agreed-upon definition(s), some include zero, others do not. The same problem exists with ''whole numbers''. Note that Wikipedia says that in computer science, ''natural numbers'' always includes zero. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 21:42, 24 January 2020 (UTC)
== what is the first natural number? ==
So the question is now, what is the first ''natural number''? -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 21:52, 24 January 2020 (UTC)
:If we allow zero or one to ''both'' be allowed then it could mean minimal rework of examples whilst hopefully retaining the spirit of the old task?
:(I am a little biased, as this is one of the existing tasks that first attracted me to RC - I based the second task I started, "Spiral matrix", on this one and have fond memories).
:--[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 09:20, 25 January 2020 (UTC)
== Pattern of memory addresses ==
If we assume that each entry is stored consecutively in memory like so (using size 5 as an example), and assuming an 8-bit computer where each memory address holds a byte and each address is 16-bit
<pre>;these are memory locations, the values within are as in the example.
$1200 $1201 $1202 $1203 $1204
$1205 $1206 $1207 $1208 $1209
$120A $120B $120C $120D $120E
$120F $1210 $1211 $1212 $1213
$1214 $1215 $1216 $1217 $1218
</pre>
Then to get to the next memory address, we add the following numbers to the one we're at.
Let N = the size of the array and K = N-1. Then:
<pre>
$1200 + 1 = $1201
$1201 + K = $1205
$1205 + N = $120A
$120A - K = $1206
$1206 - K = $1202
$1202 + 1 = $1203
$1203 + K = $1207
$1207 + K = $120B
$120B + K = $120F
$120F + N = $1214
$1214 - K = $1210
$1210 - K = $120C
$120C - K = $1208
$1208 - K = $1204
$1204 + N = $1209
$1209 + K = $120D
$120D + K = $1211
$1211 + K = $1215
$1215 + 1 = $1216
$1216 - K = $1212
$1212 - K = $120E
$120E + N = $1213
$1217 + 1 = $1218
</pre>
It seems to follow this pattern:
<pre> +1, +K, +N, -2K, +1, +3K, +N, -(K^2), +1, +N, +3K, +1, -2K, +N, +K, +1</pre>
I tried it again with a N=4 and got this sequence:
<pre> +1, +K, +N, -2K, +1, +(K^2), +1, -2K, +N, +K, +1</pre>
If you remove the <math>k^2</math> and +1 after it, the sequence is symmetric.
Might be helpful for establishing a pattern. I'll work on it more later. This logic should extend to 32-bit CPUs if you multiply N and K by 4.--[[User:Puppydrum64|Puppydrum64]] ([[User talk:Puppydrum64|talk]]) 17:06, 15 September 2021 (UTC)
:Hi Puppydrum64; at the top of the talk page the author of the J example talks about his solution that exploits patterns in indices. I just noticed that sort was involved and worked out something for the Python entry and explained it in my blog: [http://paddy3118.blogspot.com/2008/08/zig-zag.html paddy3118 blog explanation].
: There ''are'' patterns to be found :-)
: --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 07:44, 18 September 2021 (UTC)
| |||