Solve hanging lantern problem: Difference between revisions
Added Uiua solution
(Added Uiua solution) |
|||
| (6 intermediate revisions by 5 users not shown) | |||
Line 422:
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
_elements = 5
local fn GetLantern( arr(_elements) as long ) as long
long i, res = 0
for i = 1 to _elements
if arr(i) != 0
arr(i) = arr(i) - 1
res = res + fn GetLantern( arr(0) )
arr(i) = arr(i) + 1
end if
next
if res = 0 then res = 1
end fn = res
long i, j, a(_elements)
for i = 1 to _elements
a(i) = i
print "[";
for j = 1 to i
if j == i then print a(j); else print a(j); ",";
next
print "] = "; fn GetLantern( a(0) )
next
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
[1] = 1
[1,2] = 3
[1,2,3] = 60
[1,2,3,4] = 12600
[1,2,3,4,5] = 37837800
</pre>
=={{header|J}}==
Line 500 ⟶ 538:
4 3 1 2
4 3 2 1</syntaxhighlight>
=={{header|jq}}==
The main focus of this entry is illustrating how cacheing can be added to the naive recursive algorithm.
Some trivial optimizations are also included.
With these changes, the algorithm becomes quite performant. For example, the C implementation of jq accurately computes the value for the lantern configuration
[1,2,3,4,5,6,7] in less than a second on a 2.53GHz machine.
For lantern configurations with more than 2^53 permutations, the accuracy of the C implementation of jq is insufficient, but the Go implementation (gojq) can be used. For the configuration [1,2,3,4,5,6,7,8], gojq takes just over 4 minutes to produce the correct answer on the same machine.
<syntaxhighlight lang=jq>
# Input: an array representing a configuration of one or more lanterns.
# Output: the number of distinct ways to lower them.
def lanterns:
def organize: map(select(. > 0)) | sort;
# input and output: {cache, count}
def n($array):
($array | organize) as $organized
| ($organized|length) as $length
| if $length == 1 then .count = 1
elif $length == 2 and $organized[0] == 1 then .count = ($organized | add)
else .cache[$organized|tostring] as $n
| if $n then .count = $n
else reduce range(0; $length) as $i ({cache, count: 0, a : $organized};
.a[$i] += -1
| .a as $new
| n($new) as {count: $count, cache: $cache}
| .count += $count
| .cache = ($cache | .[$new | tostring] = $count)
| .a[$i] += 1 )
| {cache, count}
end
end;
. as $a | null | n($a) | .count;
"Lantern configuration => number of permutations",
([1,3,3],
[100,2],
(range(2; 10) as $nlanterns
| [range(1; $nlanterns)])
| "\(.) => \(lanterns)" )
</syntaxhighlight>
'''Invocation'''
<pre>
gojq -n -rf lanterns.jq
</pre>
{{output}}
<pre>
Lantern configuration => number of permutations
[1,3,3] => 140
[100,2] => 5151
[1] => 1
[1,2] => 3
[1,2,3] => 60
[1,2,3,4] => 12600
[1,2,3,4,5] => 37837800
[1,2,3,4,5,6] => 2053230379200
[1,2,3,4,5,6,7] => 2431106898187968000
[1,2,3,4,5,6,7,8] => 73566121315513295589120000
</pre>
=={{header|Julia}}==
Line 765 ⟶ 867:
There are 65191584694745586153436251091200000 ways to take these 9 columns down.
</pre>
=={{header|Nim}}==
Recursive solution.
The number of elements in the columns are provided as command arguments.
<syntaxhighlight lang="Nim">import std/[os, strutils]
proc sequenceCount(columns: var seq[int]): int =
for icol in 1..columns.high:
if columns[icol] > 0:
dec columns[icol]
inc result, sequenceCount(columns)
inc columns[icol]
if result == 0: result = 1
let ncol = paramCount()
if ncol == 0:
quit "Missing parameters.", QuitFailure
var columns = newSeq[int](ncol + 1) # We will ignore the first column.
for i in 1..ncol:
let n = paramStr(i).parseInt()
if n < 0:
quit "Wrong number of lanterns.", QuitFailure
columns[i] = n
echo columns.sequenceCount()
</syntaxhighlight>
=={{header|Pascal}}==
Line 1,261 ⟶ 1,390:
[6,5,4,3,1,2]
[6,5,4,3,2,1]</pre>
=={{header|Ruby}}==
===Directly computing the count===
Compute the count directly:
<syntaxhighlight lang="ruby" line>Factorial = Hash.new{|h, k| h[k] = k * h[k-1] } # a memoized factorial
Factorial[0] = 1
def count_perms_with_reps(ar)
Factorial[ar.sum] / ar.inject{|prod, m| prod * Factorial[m]}
end
ar, input = [], ""
puts "Input column heights in sequence (empty line to end input):"
ar << input.to_i until (input=gets) == "\n"
puts "There are #{count_perms_with_reps(ar)} ways to take these #{ar.size} columns down."
</syntaxhighlight>
{{Out}}
<pre>Input column heights in sequence (empty line to end input):
1
2
3
4
5
6
7
8
There are 73566121315513295589120000 ways to take these 8 columns down.
</pre>
=={{header|Uiua}}==
{{works with|Uiua|0.10.0}}
<syntaxhighlight lang="Uiua">
Fac ← /×+1⇡
Lant ← ÷⊃(/(×⊙Fac)|Fac/+)
Lant [1 2 3]
Lant [1 3 3]
Lant [1 3 3 5 7]
</syntaxhighlight>
{{out}}
<pre>
60
140
5587021440
</pre>
=={{header|Wren}}==
Line 1,266 ⟶ 1,441:
{{trans|Python}}
The result for n == 5 is slow to emerge.
<syntaxhighlight lang="
lantern = Fn.new { |n, a|
var count = 0
Line 1,301 ⟶ 1,476:
{{libheader|Wren-big}}
Alternatively, using library methods.
<syntaxhighlight lang="
import "./big" for BigInt
| |||