Intersecting number wheels: Difference between revisions
(Added Algol 68) |
(Promote to full task status.) |
||
| Line 1: | Line 1: | ||
{{ |
{{task}} |
||
A number wheel has: |
A number wheel has: |
||
Revision as of 14:26, 29 September 2019
You are encouraged to solve this task according to the task description, using any language you may know.
A number wheel has:
- A name which is an uppercase letter.
- A set of ordered values which are either numbers or names.
A number is generated/yielded from a named wheel by:
- 1. Starting at the first value of the named wheel and advancing through subsequent values and wrapping around to the first value to form a "wheel":
- 1.a If the value is a number, yield it.
- 1.b If the value is a name, yield the next value from the named wheel
- 1.c Advance the position of this wheel.
Given the wheel
A: 1 2 3
the number 1 is first generated, then 2, then 3, 1, 2, 3, 1, ...
Note: When more than one wheel is defined as a set of intersecting wheels then the first named wheel is assumed to be the one that values are generated from.
- Examples
Given the wheels:
A: 1 B 2 B: 3 4
The series of numbers generated starts:
1, 3, 2, 1, 4, 2, 1, 3, 2, 1, 4, 2, 1, 3, 2...
The intersections of number wheels can be more complex, (and might loop forever),
and wheels may be multiply connected.
Note: If a named wheel is referenced more than once by one or many other wheels, then there is only one position of the wheel that is advanced by each and all references to it.
E.g.
A: 1 D D D: 6 7 8 Generates: 1 6 7 1 8 6 1 7 8 1 6 7 1 8 6 1 7 8 1 6 ...
- Task
Generate and show the first twenty terms of the sequence of numbers generated from these groups:
Intersecting Number Wheel group:
A: 1 2 3
Intersecting Number Wheel group:
A: 1 B 2
B: 3 4
Intersecting Number Wheel group:
A: 1 D D
D: 6 7 8
Intersecting Number Wheel group:
A: 1 B C
B: 3 4
C: 5 B
Show your output here, on this page.
ALGOL 68
<lang algol68>BEGIN
# a number wheel element #
MODE NWELEMENT = UNION( CHAR # wheel name #, INT # wheel value # );
# a number wheel #
MODE NW = STRUCT( CHAR name, REF INT position, FLEX[ 1 : 0 ]NWELEMENT values );
# get the next value from a number wheel in an array of number wheels #
# note: invalid wheel names will cause subscript range errors #
OP NEXT = ( []NW wheels )INT:
BEGIN
INT result;
BOOL found := FALSE;
INT w := LWB wheels; # start with the first wheel #
WHILE NOT found DO
IF position OF wheels[ w ] > UPB values OF wheels[ w ] THEN
# passed the end of the wheel, go back to the start #
position OF wheels[ w ] := LWB values OF wheels[ w ]
FI;
NWELEMENT e = ( values OF wheels[ w ] )[ position OF wheels[ w ] ];
position OF wheels[ w ] +:= 1;
CASE e
IN ( INT n ): BEGIN result := n; found := TRUE END
, ( CHAR c ): BEGIN
w := LWB wheels;
WHILE name OF wheels[ w ] /= c DO w +:= 1 OD
END
ESAC
OD;
result
END # NEXT # ;
# prints the first n values from an array of wheels #
PROC show = ( INT n, []NW wheels )VOID:
BEGIN
print( ( "First ", whole( n, 0 ), " values from the Intersecting Number Wheels:" ) );
FOR i FROM LWB wheels TO UPB wheels DO
print( ( newline, " ", name OF wheels[ i ], ":" ) );
FOR v FROM LWB values OF wheels[ i ] TO UPB values OF wheels[ i ] DO
CASE ( values OF wheels[ i ] )[ v ]
IN ( INT n ): print( ( " ", whole( n, 0 ) ) )
, ( CHAR c ): print( ( " ", c ) )
ESAC
OD
OD;
print( ( newline, " " ) );
FOR i TO n DO print( ( " ", whole( NEXT wheels, 0 ) ) ) OD;
print( ( newline, newline ) )
END # show # ;
# show some wheels in action #
show( 20, ( NW( "A", LOC INT := 1, ( 1, 2, 3 ) ) ) );
show( 20, ( NW( "A", LOC INT := 1, ( 1, "B", 2 ) )
, NW( "B", LOC INT := 1, ( 3, 4 ) ) ) );
show( 20, ( NW( "A", LOC INT := 1, ( 1, "D", "D" ) )
, NW( "D", LOC INT := 1, ( 6, 7, 8 ) ) ) );
show( 20, ( NW( "A", LOC INT := 1, ( 1, "B", "C" ) )
, NW( "B", LOC INT := 1, ( 3, 4 ) )
, NW( "C", LOC INT := 1, ( 5, "B" ) ) ) )
END</lang>
- Output:
First 20 values from the Intersecting Number Wheels:
A: 1 2 3
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
First 20 values from the Intersecting Number Wheels:
A: 1 B 2
B: 3 4
1 3 2 1 4 2 1 3 2 1 4 2 1 3 2 1 4 2 1 3
First 20 values from the Intersecting Number Wheels:
A: 1 D D
D: 6 7 8
1 6 7 1 8 6 1 7 8 1 6 7 1 8 6 1 7 8 1 6
First 20 values from the Intersecting Number Wheels:
A: 1 B C
B: 3 4
C: 5 B
1 3 5 1 4 3 1 4 5 1 3 4 1 3 5 1 4 3 1 4
Factor
An attempt has been made to simplify the interface as much as possible by creating a natural literal syntax for number wheel groups. This should be useful for exploring these types of sequences in the future.
nw-parser is an EBNF grammar that turns
"A: 1 B C\nB: 3 4\nC: 5 B"
into
{
{ "A" T{ number-wheel { seq T{ circular { seq { 1 "B" "C" } } } } { i 0 } } }
{ "B" T{ number-wheel { seq T{ circular { seq { 3 4 } } } } { i 0 } } }
{ "C" T{ number-wheel { seq T{ circular { seq { 5 "B" } } } } { i 0 } } }
}
— a dictionary-like structure that is transformed into a lazy list which yields the expected sequence elements.
<lang factor>USING: accessors assocs circular io kernel lists lists.lazy math math.parser multiline peg.ebnf prettyprint prettyprint.custom sequences strings ; IN: rosetta-code.number-wheels
TUPLE: group pretty list ;
C: <group> group
M: group pprint* pretty>> write ;
TUPLE: number-wheel seq i ;
- <number-wheel> ( seq -- number-wheel )
<circular> 0 number-wheel boa ;
- yield ( assoc -- n )
dup first first [ dup integer? ] [ dupd of [ i>> ] [ [ 1 + ] change-i seq>> nth ] bi ] until nip ;
- number-wheel>lazy ( assoc -- list )
0 lfrom swap [ yield nip ] curry lmap-lazy ;
EBNF: nw-parser [=[
num = [0-9]+ => [[ >string string>number ]]
name = [a-zA-Z]+ => [[ >string ]]
wheel = (" "~ (num | name))+ "\n"?
=> [[ but-last first <number-wheel> ]]
group = (name ":"~ wheel)+ => [[ number-wheel>lazy ]]
]=]
SYNTAX: NUMBER-WHEELS: parse-here dup nw-parser <group> suffix! ;
- .take ( n group -- )
list>> ltake list>array [ pprint bl ] each "..." print ;</lang>
Now the interface defined above may be used: <lang factor>USING: generalizations io kernel prettyprint rosetta-code.number-wheels ;
NUMBER-WHEELS: A: 1 2 3
NUMBER-WHEELS: A: 1 B 2 B: 3 4
NUMBER-WHEELS: A: 1 D D D: 6 7 8
NUMBER-WHEELS: A: 1 B C B: 3 4 C: 5 B
[
"Intersecting number wheel group:" print [ . ] [ "Generates:" print 20 swap .take nl ] bi
] 4 napply</lang>
- Output:
Intersecting number wheel group: A: 1 2 3 Generates: 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ... Intersecting number wheel group: A: 1 B 2 B: 3 4 Generates: 1 3 2 1 4 2 1 3 2 1 4 2 1 3 2 1 4 2 1 3 ... Intersecting number wheel group: A: 1 D D D: 6 7 8 Generates: 1 6 7 1 8 6 1 7 8 1 6 7 1 8 6 1 7 8 1 6 ... Intersecting number wheel group: A: 1 B C B: 3 4 C: 5 B Generates: 1 3 5 1 4 3 1 4 5 1 3 4 1 3 5 1 4 3 1 4 ...
Go
<lang go>package main
import (
"fmt" "strconv"
)
type wheel struct {
next int values []string
}
func generate(wheels map[string]wheel, start string, maxCount int) {
fmt.Printf(" ")
count := 0
w := wheels[start]
for {
s := w.values[w.next]
v, err := strconv.Atoi(s)
w.next++
if w.next == len(w.values) {
w.next = 0
}
if err == nil {
fmt.Printf("%d ", v)
count++
if count == maxCount {
fmt.Println("...\n")
return
}
} else {
for {
w2 := wheels[s]
ss := s
s = w2.values[w2.next]
w2.next++
if w2.next == len(w2.values) {
w2.next = 0
}
wheels[ss] = w2
v, err = strconv.Atoi(s)
if err == nil {
fmt.Printf("%d ", v)
count++
if count == maxCount {
fmt.Println("...\n")
return
}
break
}
}
}
}
}
func printWheels(wheels map[string]wheel, names ...string) {
fmt.Println("Intersecting Number Wheel group:")
for _, name := range names {
fmt.Printf(" %s: %v\n", name, wheels[name].values)
}
fmt.Println(" Generates:")
} func main() {
wheels := make(map[string]wheel)
wheels["A"] = wheel{0, []string{"1", "2", "3"}}
printWheels(wheels, "A")
generate(wheels, "A", 20)
wheels["A"] = wheel{0, []string{"1", "B", "2"}}
wheels["B"] = wheel{0, []string{"3", "4"}}
printWheels(wheels, "A", "B")
generate(wheels, "A", 20)
wheels["A"] = wheel{0, []string{"1", "D", "D"}}
delete(wheels, "B")
wheels["D"] = wheel{0, []string{"6", "7", "8"}}
printWheels(wheels, "A", "D")
generate(wheels, "A", 20)
wheels["A"] = wheel{0, []string{"1", "B", "C"}}
wheels["B"] = wheel{0, []string{"3", "4"}}
wheels["C"] = wheel{0, []string{"5", "B"}}
delete(wheels, "D")
printWheels(wheels, "A", "B", "C")
generate(wheels, "A", 20)
}</lang>
- Output:
Intersecting Number Wheel group:
A: [1 2 3]
Generates:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ...
Intersecting Number Wheel group:
A: [1 B 2]
B: [3 4]
Generates:
1 3 2 1 4 2 1 3 2 1 4 2 1 3 2 1 4 2 1 3 ...
Intersecting Number Wheel group:
A: [1 D D]
D: [6 7 8]
Generates:
1 6 7 1 8 6 1 7 8 1 6 7 1 8 6 1 7 8 1 6 ...
Intersecting Number Wheel group:
A: [1 B C]
B: [3 4]
C: [5 B]
Generates:
1 3 5 1 4 3 1 4 5 1 3 4 1 3 5 1 4 3 1 4 ...
Julia
<lang julia>const d1 = Dict("A" => [["1", "2", "3"], 1]) const d2 = Dict("A" => [["1", "B", "2"], 1], "B" => [["3", "4"], 1]) const d3 = Dict("A" => [["1", "D", "D"], 1], "D" => [["6", "7", "8"], 1]) const d4 = Dict("A" => [["1", "B", "C"], 1], "B" => [["3", "4"], 1],
"C" => [["5", "B"], 1])
function getvalue!(wheelname, allwheels)
wheel = allwheels[wheelname] s = wheel[1][wheel[2]] wheel[2] = mod1(wheel[2] + 1, length(wheel[1])) return haskey(allwheels, s) ? getvalue!(s, allwheels) : s
end
function testwheels(wheels, numterms = 20, firstwheel = "A")
println("\nNumber Wheels:")
for k in sort(collect(keys(wheels)))
print("$k: [")
for s in wheels[k][1]
print(s, " ")
end
println("\b]")
end
print("Output: ")
for _ in 1:numterms
print(getvalue!(firstwheel, wheels), " ")
end
println("...")
end
foreach(testwheels, [d1, d2, d3, d4])
</lang>
- Output:
Number Wheels: A: [1 2 3] Output: 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ... Number Wheels: A: [1 B 2] B: [3 4] Output: 1 3 2 1 4 2 1 3 2 1 4 2 1 3 2 1 4 2 1 3 ... Number Wheels: A: [1 D D] D: [6 7 8] Output: 1 6 7 1 8 6 1 7 8 1 6 7 1 8 6 1 7 8 1 6 ... Number Wheels: A: [1 B C] B: [3 4] C: [5 B] Output: 1 3 5 1 4 3 1 4 5 1 3 4 1 3 5 1 4 3 1 4 ...
Python
Python: Original class and generator based
<lang python>from itertools import islice
class INW():
""" Intersecting Number Wheels represented as a dict mapping name to tuple of values. """
def __init__(self, **wheels):
self._wheels = wheels
self.isect = {name: self._wstate(name, wheel)
for name, wheel in wheels.items()}
def _wstate(self, name, wheel):
"Wheel state holder"
assert all(val in self._wheels for val in wheel if type(val) == str), \
f"ERROR: Interconnected wheel not found in {name}: {wheel}"
pos = 0
ln = len(wheel)
while True:
nxt, pos = wheel[pos % ln], pos + 1
yield next(self.isect[nxt]) if type(nxt) == str else nxt
def __iter__(self):
base_wheel_name = next(self.isect.__iter__())
yield from self.isect[base_wheel_name]
def __repr__(self):
return f"{self.__class__.__name__}({self._wheels})"
def __str__(self):
txt = "Intersecting Number Wheel group:"
for name, wheel in self._wheels.items():
txt += f"\n {name+':':4}" + ' '.join(str(v) for v in wheel)
return txt
def first(iter, n):
"Pretty print first few terms"
return ' '.join(f"{nxt}" for nxt in islice(iter, n))
if __name__ == '__main__':
for group in[
{'A': (1, 2, 3)},
{'A': (1, 'B', 2),
'B': (3, 4)},
{'A': (1, 'D', 'D'),
'D': (6, 7, 8)},
{'A': (1, 'B', 'C'),
'B': (3, 4),
'C': (5, 'B')}, # 135143145...
]:
w = INW(**group)
print(f"{w}\n Generates:\n {first(w, 20)} ...\n")</lang>
- Output:
Intersecting Number Wheel group:
A: 1 2 3
Generates:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ...
Intersecting Number Wheel group:
A: 1 B 2
B: 3 4
Generates:
1 3 2 1 4 2 1 3 2 1 4 2 1 3 2 1 4 2 1 3 ...
Intersecting Number Wheel group:
A: 1 D D
D: 6 7 8
Generates:
1 6 7 1 8 6 1 7 8 1 6 7 1 8 6 1 7 8 1 6 ...
Intersecting Number Wheel group:
A: 1 B C
B: 3 4
C: 5 B
Generates:
1 3 5 1 4 3 1 4 5 1 3 4 1 3 5 1 4 3 1 4 ...
Python: Simplified proceedural
<lang python>def nextfrom(w, name):
while True:
nxt, w[name] = w[name][0], w[name][1:] + w[name][:1]
if '0' <= nxt[0] <= '9':
return nxt
name = nxt
if __name__ == '__main__':
for group in
A: 1 2 3 A: 1 B 2; B: 3 4 A: 1 D D; D: 6 7 8 A: 1 B C; B: 3 4; C: 5 B.strip().split('\n'):
print(f"Intersecting Number Wheel group:\n {group}")
wheel, first = {}, None
for w in group.strip().split(';'):
name, *values = w.strip().split()
wheel[name[:-1]] = values
first = name[:-1] if first is None else first
gen = ' '.join(nextfrom(wheel, first) for i in range(20))
print(f" Generates:\n {gen} ...\n")</lang>
- Output:
Intersecting Number Wheel group:
A: 1 2 3
Generates:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 ...
Intersecting Number Wheel group:
A: 1 B 2; B: 3 4
Generates:
1 3 2 1 4 2 1 3 2 1 4 2 1 3 2 1 4 2 1 3 ...
Intersecting Number Wheel group:
A: 1 D D; D: 6 7 8
Generates:
1 6 7 1 8 6 1 7 8 1 6 7 1 8 6 1 7 8 1 6 ...
Intersecting Number Wheel group:
A: 1 B C; B: 3 4; C: 5 B
Generates:
1 3 5 1 4 3 1 4 5 1 3 4 1 3 5 1 4 3 1 4 ...
zkl
<lang zkl>fcn intersectingNumberWheelsW(wheels){ // ("A":(a,b,"C"), "C":(d,e) ...)
ws:=wheels.pump(Dictionary(),fcn([(k,v)]){ return(k,Walker.cycle(v)) }); // new Dictionary
Walker.zero().tweak(fcn(w,wheels){
while(1){
w=wheels[w].next(); // increment wheel w if(Int.isType(w)) return(w);
}
}.fp("A",ws)) // assume wheel A exists and is always first
}</lang> <lang zkl>wheelSets:=T( Dictionary("A",T(1,2,3)), Dictionary("A",T(1,"B",2), "B",T(3,4)), Dictionary("A",T(1,"D","D"), "D",T(6,7,8)), Dictionary("A",T(1,"B","C"), "C",T(5,"B"), "B",T(3,4)) ); foreach ws in (wheelSets){
println("Wheel set:");
ws.pump(String,fcn([(k,v)]){ " %s: %s\n".fmt(k,v.concat(" ")) }).print();
println("-->",intersectingNumberWheelsW(ws).walk(20).concat(" "));
}</lang>
- Output:
Wheel set: A: 1 2 3 -->1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 Wheel set: A: 1 B 2 B: 3 4 -->1 3 2 1 4 2 1 3 2 1 4 2 1 3 2 1 4 2 1 3 Wheel set: A: 1 D D D: 6 7 8 -->1 6 7 1 8 6 1 7 8 1 6 7 1 8 6 1 7 8 1 6 Wheel set: A: 1 B C C: 5 B B: 3 4 -->1 3 5 1 4 3 1 4 5 1 3 4 1 3 5 1 4 3 1 4