Rosetta Code

Addition chains: Difference between revisions

Page Discussion

Addition chains (view source)

Revision as of 08:45, 7 May 2024

8,674 bytes added ,  21 days ago
m
→‎{{header|11l}}: Void
 
(7 intermediate revisions by 5 users not shown)
Line 22:
* non-brauer-chains(19) : count = 2 Ex: ( 1 2 3 6 7 12 19)
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">F bauer(n)
V chain = [0] * n
V in_chain = [0B] * (n + 1)
[Int] best
V best_len = n
V cnt = 0
 
F extend_chain(Int x, Int =pos) -> Void
I @best_len - pos < 32 & x < @n >> (@best_len - pos)
R
 
@chain[pos] = x
@in_chain[x] = 1B
pos++
 
I @in_chain[@n - x]
I pos == @best_len
@cnt++
E
@best = @chain[0 .< pos]
@best_len = pos
@cnt = 1
E I pos < @best_len
L(i) (pos - 1 .< -1).step(-1)
V c = x + @chain[i]
I c < @n
@extend_chain(c, pos)
 
@in_chain[x] = 0B
 
extend_chain(1, 0)
R (best [+] [n], cnt)
 
L(n) [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
V (best, cnt) = bauer(n)
print("L(#.) = #., count of minimum chain: #.\ne.g.: #.\n".format(n, best.len - 1, cnt, best))</syntaxhighlight>
 
{{out}}
<pre>
L(7) = 4, count of minimum chain: 5
e.g.: [1, 2, 4, 6, 7]
 
L(14) = 5, count of minimum chain: 14
e.g.: [1, 2, 4, 8, 12, 14]
 
L(21) = 6, count of minimum chain: 26
e.g.: [1, 2, 4, 8, 16, 20, 21]
 
L(29) = 7, count of minimum chain: 114
e.g.: [1, 2, 4, 8, 16, 24, 28, 29]
 
L(32) = 5, count of minimum chain: 1
e.g.: [1, 2, 4, 8, 16, 32]
 
L(42) = 7, count of minimum chain: 78
e.g.: [1, 2, 4, 8, 16, 32, 40, 42]
 
L(64) = 6, count of minimum chain: 1
e.g.: [1, 2, 4, 8, 16, 32, 64]
 
L(47) = 8, count of minimum chain: 183
e.g.: [1, 2, 4, 8, 12, 13, 26, 39, 47]
 
L(79) = 9, count of minimum chain: 492
e.g.: [1, 2, 4, 8, 16, 24, 26, 52, 78, 79]
 
L(191) = 11, count of minimum chain: 7172
e.g.: [1, 2, 4, 8, 16, 32, 48, 52, 53, 106, 159, 191]
 
L(382) = 11, count of minimum chain: 4
e.g.: [1, 2, 4, 8, 16, 17, 33, 50, 83, 166, 332, 382]
 
L(379) = 12, count of minimum chain: 6583
e.g.: [1, 2, 4, 8, 16, 32, 64, 96, 104, 105, 210, 315, 379]
 
</pre>
 
=={{header|C}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 220 ⟶ 300:
for (i = 0; i < 12; ++i) findBrauer(nums[i], 12, 79);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 306 ⟶ 386:
=={{header|C sharp|C#}}==
{{trans|Java}}
<langsyntaxhighlight lang="csharp">using System;
 
namespace AdditionChains {
Line 353 ⟶ 433:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>N = 7
Line 406 ⟶ 486:
While this worked, something made it run extremely slow.
{{trans|D}}
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <tuple>
#include <vector>
Line 451 ⟶ 531:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 504 ⟶ 584:
=={{header|D}}==
{{trans|Scala}}
<langsyntaxhighlight Dlang="d">import std.stdio;
import std.typecons;
 
Line 542 ⟶ 622:
find_brauer(i);
}
}</langsyntaxhighlight>
{{out}}
<pre>N = 7
Line 593 ⟶ 673:
 
=={{header|EchoLisp}}==
<langsyntaxhighlight lang="scheme">
;; 2^n
(define exp2 (build-vector 32 (lambda(i)(expt 2 i))))
Line 640 ⟶ 720:
(printf "L(%d) = %d - brauer-chains: %d non-brauer: %d chains: %a %a "
n *minlg* [*counts* 0] [*counts* 1] [*chains* 0] [*chains* 1]))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 663 ⟶ 743:
===Version 1===
{{trans|Kotlin}}
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 816 ⟶ 896:
findBrauer(num, 12, 79)
}
}</langsyntaxhighlight>
 
{{out}}
Line 903 ⟶ 983:
{{trans|Phix}}
Much faster than Version 1 and can now complete the non-Brauer analysis for N > 79 in a reasonable time.
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,020 ⟶ 1,100:
}
fmt.Printf("\nTook %s\n", time.Since(start))
}</langsyntaxhighlight>
 
{{out}}
Line 1,111 ⟶ 1,191:
=={{header|Groovy}}==
{{trans|Java}}
<langsyntaxhighlight Groovylang="groovy">class AdditionChains {
private static class Pair {
int f, s
Line 1,164 ⟶ 1,244:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>N = 7
Line 1,213 ⟶ 1,293:
Minimum length of chains: L(n)= 12
Number of minimum length Brauer chains: 6583</pre>
 
=={{header|Haskell}}==
 
Implementation using backtracking.
 
<syntaxhighlight lang="haskell">import Data.List (union)
 
-- search strategies
total [] = []
total (x:xs) = brauer (x:xs) `union` total xs
 
brauer [] = []
brauer (x:xs) = map (+ x) (x:xs)
 
-- generation of chains with given strategy
chains _ 1 = [[1]]
chains sums n = go [[1]]
where
go ch = let next = ch >>= step
complete = filter ((== n) . head) next
in if null complete then go next else complete
 
step ch = (: ch) <$> filter (\s -> s > head ch && s <= n) (sums ch)
 
-- the predicate for Brauer chains
isBrauer [_] = True
isBrauer [_,_] = True
isBrauer (x:y:xs) = (x - y) `elem` (y:xs) && isBrauer (y:xs)</syntaxhighlight>
 
Usage examples
 
<pre>λ> chains total 9
[[9,8,4,2,1],[9,5,4,2,1],[9,6,3,2,1]]
 
λ> chains total 13
[[13,12,8,4,2,1],[13,9,8,4,2,1],[13,12,6,4,2,1],[13,7,6,4,2,1],[13,9,5,4,2,1],[13,8,5,4,2,1],
[13,12,6,3,2,1],[13,7,6,3,2,1],[13,10,5,3,2,1],[13,8,5,3,2,1]]
 
λ> chains brauer 13
[[13,12,8,4,2,1],[13,9,8,4,2,1],[13,12,6,4,2,1],[13,7,6,4,2,1],[13,9,5,4,2,1],[13,12,6,3,2,1],
[13,7,6,3,2,1],[13,10,5,3,2,1],[13,8,5,3,2,1]]
 
λ> filter (not . isBrauer) $ chains total 13
[[13,8,5,4,2,1]]</pre>
 
Tasks implementation
 
<syntaxhighlight lang="haskell">task :: Int -> IO()
task n =
let ch = chains total n
br = filter isBrauer ch
nbr = filter (not . isBrauer) ch
in do
printf "L(%d) = %d\n" n (length (head ch) - 1)
printf "Brauer chains(%i)\t: count = %i\tEx: %s\n" n (length br) (show $ reverse $ head br)
if not $ null nbr
then
printf "non-Brauer chains(%i)\t: count = %i\tEx: %s\n\n" n (length ch - length br) (show $ reverse $ head nbr)
else
putStrLn "No non Brauer chains\n"</syntaxhighlight>
 
<pre>λ> mapM_ task [7,14,21,29,32,42,64]
L(7) = 4
Brauer chains(7) : count = 5 Ex: [1,2,4,6,7]
No non Brauer chains
 
L(14) = 5
Brauer chains(14) : count = 14 Ex: [1,2,4,8,12,14]
No non Brauer chains
 
L(21) = 6
Brauer chains(21) : count = 26 Ex: [1,2,4,8,16,20,21]
non-Brauer chains(21) : count = 3 Ex: [1,2,4,8,9,12,21]
 
L(29) = 7
Brauer chains(29) : count = 114 Ex: [1,2,4,8,16,24,28,29]
non-Brauer chains(29) : count = 18 Ex: [1,2,4,8,12,13,16,29]
 
L(32) = 5
Brauer chains(32) : count = 1 Ex: [1,2,4,8,16,32]
No non Brauer chains
 
L(42) = 7
Brauer chains(42) : count = 78 Ex: [1,2,4,8,16,32,40,42]
non-Brauer chains(42) : count = 6 Ex: [1,2,4,8,16,18,24,42]
 
L(64) = 6
Brauer chains(64) : count = 1 Ex: [1,2,4,8,16,32,64]
No non Brauer chains</pre>
 
For the extra task used compiled code, not GHCi.
 
<syntaxhighlight lang="haskell">extraTask :: Int -> IO()
extraTask n =
let ch = chains brauer n
in do
printf "L(%d) = %d\n" n (length (head ch) - 1)
printf "Brauer chains(%i)\t: count = %i\tEx: %s\n" n (length ch) (show $ reverse $ head ch)
putStrLn "Non-Brauer analysis suppressed\n"
 
main = mapM_ extraTask [47, 79, 191, 382, 379]</syntaxhighlight>
 
<pre>L(47) = 8
Brauer chains(47) : count = 183 Ex: [1,2,4,8,12,13,26,39,47]
Non-Brauer analysis suppressed
 
L(79) = 9
Brauer chains(79) : count = 492 Ex: [1,2,4,8,16,24,26,52,78,79]
Non-Brauer analysis suppressed
 
L(191) = 11
Brauer chains(191) : count = 7172 Ex: [1,2,4,8,16,32,48,52,53,106,159,191]
Non-Brauer analysis suppressed
 
L(382) = 11
Brauer chains(382) : count = 4 Ex: [1,2,4,8,16,17,33,50,83,166,332,382]
Non-Brauer analysis suppressed
 
L(379) = 12
Brauer chains(379) : count = 6583 Ex: [1,2,4,8,16,32,64,96,104,105,210,315,379]
Non-Brauer analysis suppressed</pre>
 
Calculation took about 16 seconds (compiled with -O2 flag). If one doesn't need to count all chains, but just get an example it will be found much faster due to Haskell laziness.
 
=== Nearly optimal chains ===
 
In practical work use binary chains or the smart algorithm given in ''F. Bergeron, J. Berstel, and S. Brlek, published in
Journal de théorie des nombres de Bordeaux, 6 no. 1 (1994), p. 21-38,'' [http://www.numdam.org/item?id=JTNB_1994__6_1_21_0].
 
<syntaxhighlight lang="haskell">binaryChain 1 = [1]
binaryChain n | even n = n : binaryChain (n `div` 2)
| odd n = n : binaryChain (n - 1)
 
dichotomicChain n
| n == 3 = [3, 2, 1]
| n == 2 ^ log2 n = takeWhile (> 0) $ iterate (`div` 2) n
| otherwise = let k = n `div` (2 ^ ((log2 n + 1) `div` 2))
in chain n k
where
chain n1 n2
| n2 <= 1 = minChain n1
| otherwise = case n1 `divMod` n2 of
(q, 0) -> minChain q `mul` minChain n2
(q, r) -> [r] `add` (minChain q `mul` chain n2 r)
 
c1 `mul` c2 = map (head c2 *) c1 ++ tail c2
c1 `add` c2 = map (head c2 +) c1 ++ c2
log2 = floor . logBase 2 . fromIntegral</syntaxhighlight>
 
<pre>λ> binaryChain 191
[191,190,95,94,47,46,23,22,11,10,5,4,2,1]
 
λ> dichotomicChain 191
[191,187,176,88,44,22,11,8,4,3,2,1]
 
λ> binaryChain 1910
[1910,955,954,477,476,238,119,118,59,58,29,28,14,7,6,3,2,1]
 
λ> dichotomicChain 1910
[1910,1888,944,472,236,118,59,44,22,15,14,7,6,3,2,1]</pre>
 
=={{header|Java}}==
{{trans|D}}
<langsyntaxhighlight Javalang="java">public class AdditionChains {
private static class Pair {
int f, s;
Line 1,269 ⟶ 1,510:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>N = 7
Line 1,321 ⟶ 1,562:
=={{header|Julia}}==
{{trans|Python}}
<langsyntaxhighlight lang="julia">checksequence(pos, seq, n, minlen) =
pos > minlen || seq[1] > n ? (minlen, 0) :
seq[1] == n ? (pos, 1) :
Line 1,346 ⟶ 1,587:
println("Number of minimum length Brauer chains: $nchains")
end
</langsyntaxhighlight>{{out}}
<pre>
N = 7
Line 1,390 ⟶ 1,631:
 
I've then extended the code to count the number of non-Brauer chains of the same minimum length - basically 'brute' force to generate all addition chains and then subtracted the number of Brauer ones - plus examples for both. For N <= 64 this adds little to the execution time but adds about 1 minute for N = 79 and I gave up waiting for N = 191! To deal with these glacial execution times, I've added code which enables you to suppress the non-Brauer generation for N above a specified figure.
<langsyntaxhighlight lang="scala">// version 1.1.51
 
var example: List<Int>? = null
Line 1,480 ⟶ 1,721:
println("Searching for Brauer chains up to a minimum length of 12:")
for (num in nums) findBrauer(num, 12, 79)
}</langsyntaxhighlight>
 
{{out}}
Line 1,566 ⟶ 1,807:
=={{header|Lua}}==
{{trans|D}}
<langsyntaxhighlight lang="lua">function index(a,i)
return a[i + 1]
end
Line 1,633 ⟶ 1,874:
end
 
main()</langsyntaxhighlight>
{{out}}
<pre>N = 7
Line 1,686 ⟶ 1,927:
{{trans|Go}}
This is a translation of the second Go version.
<langsyntaxhighlight Nimlang="nim">import times, strutils
 
const
Line 1,764 ⟶ 2,005:
if nonBrauerCount > 0:
echo "Non-Brauer example: ", nonBrauerExample.join(", ")
echo "\nTook ", now() - start</langsyntaxhighlight>
 
{{out}}
Line 1,852 ⟶ 2,093:
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="perl">use strict;
use feature 'say';
 
Line 1,960 ⟶ 2,201:
# 47, 79, 191, 382, 379, 379, 12509);
say "Searching for Brauer chains up to a minimum length of 12:";
for (@nums) { findBrauer $_, 12, 79 }</langsyntaxhighlight>
{{out}}
<pre style="height:35ex">N = 7
Line 2,011 ⟶ 2,252:
Note the internal values of l(n) are [consistently] +1 compared to what the rest of the world says.
 
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">nums</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">21</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">29</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">42</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">64</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">47</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">191</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">382</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">379</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">13</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">max_non_brauer</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">37979</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">isBrauer</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
Line 2,040 ⟶ 2,283:
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">tries</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #7060A8;">ppOpt</span><span style="color: #0000FF;">({</span><span style="color: #000000004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">addition_chains</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">target</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">={</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
Line 2,062 ⟶ 2,305:
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">len</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"working... %s, %,d permutations"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">ppf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]),</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">}))</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
Line 2,081 ⟶ 2,324:
<span style="color: #008080;">if</span> <span style="color: #000000;">next</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">target</span> <span style="color: #008080;">and</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">></span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">[$]</span> <span style="color: #008080;">and</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">len</span> <span style="color: #008080;">and</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ndone</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ndone</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ndone</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">addition_chains</span><span style="color: #0000FF;">(</span><span style="color: #000000;">target</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
Line 2,093 ⟶ 2,336:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Searching for Brauer chains up to a minimum length of %d:\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">maxlen</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nums</span><span style="color: #0000FF;">)-</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">3</span><span style="color: #0000FF;">:</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">brauer_count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
Line 2,105 ⟶ 2,348:
<span style="color: #000000;">ns</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nbc</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" eg "</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">ppf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">non_brauer_example</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">","</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed_short</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8008080;">progressif</span> <span style="color: #0000FF7060A8;">(platform</span><span style="color: #0080000000FF;">""()!=</span><span style="color: #0000FF004600;">)JS</span> <span style="color: #000080;font-style:italic008080;">-- (wipe it clean)then</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (wipe it clean)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"l(%d) = %d, Brauer:%d,%s Non-Brauer:%d,%s (%s, %d perms)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">num</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nbc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ns</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
 
{{out}}
Line 2,146 ⟶ 2,391:
=={{header|Python}}==
{{trans|Java}}
<langsyntaxhighlight lang="python">def prepend(n, seq):
return [n] + seq
 
Line 2,184 ⟶ 2,429:
nums = [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
for i in nums:
find_brauer(i)</langsyntaxhighlight>
{{out}}
<pre>
Line 2,236 ⟶ 2,481:
 
====Faster method====
<langsyntaxhighlight lang="python">def bauer(n):
chain = [0]*n
in_chain = [False]*(n + 1)
Line 2,272 ⟶ 2,517:
for n in [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]:
best, cnt = bauer(n)
print(f'L({n}) = {len(best) - 1}, count of minimum chain: {cnt}\ne.g.: {best}\n')</langsyntaxhighlight>
{{out}}
<pre>
Line 2,294 ⟶ 2,539:
This implementation uses the [https://docs.racket-lang.org/rosette-guide/index.html Rosette] language in Racket. It is inefficient as it asks an SMT solver to enumerate every possible solutions. However, it is very straightforward to write, and in fact is quite efficient for computing <code>l(n)</code> and finding one example (solve n = 379 in ~3 seconds).
 
<langsyntaxhighlight lang="racket">#lang rosette
 
(define (basic-constraints xs n)
Line 2,350 ⟶ 2,595:
 
(for ([x (in-list '(191 382 379 12509))])
(compute/time x #:enumerate? #f))</langsyntaxhighlight>
 
{{out}}
Line 2,440 ⟶ 2,685:
(formerly Perl 6)
{{trans|Kotlin}}
<syntaxhighlight lang="raku" perl6line>my @Example = ();
 
sub check-Sequence($pos, @seq, $n, $minLen --> List) {
Line 2,536 ⟶ 2,781:
 
say "Searching for Brauer chains up to a minimum length of 12:";
find-Brauer $_, 12, 79 for 7, 14, 21, 29, 32, 42, 64 #, 47, 79, 191, 382, 379, 379, 12509 # un-comment for extra-credit</langsyntaxhighlight>
{{out}}
<pre>Searching for Brauer chains up to a minimum length of 12:
Line 2,587 ⟶ 2,832:
=={{header|Ruby}}==
{{trans|D}}
<langsyntaxhighlight lang="ruby">def check_seq(pos, seq, n, min_len)
if pos > min_len or seq[0] > n then
return min_len, 0
Line 2,635 ⟶ 2,880:
end
 
main()</langsyntaxhighlight>
{{out}}
<pre>
Line 2,688 ⟶ 2,933:
=={{header|Scala}}==
Following Scala implementation finds number of minimum length Brauer chains and corresponding length.
<syntaxhighlight lang="scala">
<lang Scala>
object chains{
 
Line 2,721 ⟶ 2,966:
}
}
</syntaxhighlight>
</lang>
<pre>
N = 7
Line 2,778 ⟶ 3,023:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Module Module1
 
Function Prepend(n As Integer, seq As List(Of Integer)) As List(Of Integer)
Line 2,836 ⟶ 3,081:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>N = 7
Line 2,891 ⟶ 3,136:
 
Non-Brauer analysis limited to N = 191 in order to finish in a reasonable time - about 10.75 minutes on my machine.
<langsyntaxhighlight ecmascriptlang="wren">var maxLen = 13
var maxNonBrauer = 191
 
Line 2,978 ⟶ 3,223:
} else System.print("Non-Brauer analysis suppressed")
}
System.print("\nTook %(System.clock - start) seconds.")</langsyntaxhighlight>
 
{{out}}
Line 3,067 ⟶ 3,312:
=={{header|zkl}}==
{{trans|EchoLisp}}
<langsyntaxhighlight lang="zkl">var exp2=(32).pump(List,(2).pow), // 2^n, n=0..31
_minlg, _counts, _chains; // counters and results
Line 3,101 ⟶ 3,346:
}
}
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">fcn task(n){
_minlg=(0).MAX;
chains(n,List(1),0);
Line 3,108 ⟶ 3,353:
.fmt(n,_minlg,_counts.xplode(),_chains.filter()));
}
T(7,14,21,29,32,42,64,47,79).apply2(task);</langsyntaxhighlight>
{{out}}
<pre>
Alextretyak
1,480

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/263616...364304"